CS536 Final Study Guide: 1 Topic Overview

CS536 Final Study Guide
December 12, 2010
1 Topic Overview
This is a brief overview of the topics you should be familiar with. The final will cover all of the material since the
midterm (everything after type checking).
• Runtime Storage
– Memory organization (text segment, data segment, heap, stack)

– Uses for each segment
– Activation records (contents and construction)
– Steps involved in function calls and returns
– Static vs. stack allocation (advantages and disadvantages)
• Variable Access
– Global variables
– Local variables
– Non-local variables (as in nested functions)
– Display vs. Access Link
– Variable access for dynamic scoping
– Shallow vs. deep binding
• Parameter Passing
– By-value
– By-reference
– By-value-result
– By-name
– By-need
• Function Access (Dispatch)
– Static dispatch (as in C)

– Message passing
– Table-driven virtual method dispatch
• Code Generation
– Function prolog, entry, and exit code

– Function calls
1
– Handling of conditionals
– Expression evaluation
– Simple register allocation for expressions
• Heap Management
– Free list memory management (allocation and deallocation)

– Disadvantages of manual memory allocation
– Reference counting (including disadvantages)
– Mark and sweep garbage collection
– Copying collection
– Generational collection
• Introductory Dataflow Analysis

– Problems that are hard to solve with ASTs
– Control flow graphs
2 Runtime Storage
You should understand the layout of a program in memory, including the uses for the various sections. You should be
very familiar with how functions are called and their local storage is managed, as well as the trade-offs between the
various different methods.
2.1 Specific Skills

• Draw the program stack in various states of program execution.
• Draw or describe the contents of an activation record.
• Recognize problems with a proposed stack layout.
3 Variable Access
You should know the differences between the different types of and locations for variable storage. You should know
how to access variables from any context we have discussed.
3.1 Specific Skills

• Compute the offsets of local variables and parameters from the frame pointer
• Show how the access link is used
• Show the variable references in a dynamically-scoped program
• Show the sequence of assignments for managing the display for non-local variables
4 Parameter Passing
You should know the trade-offs and implications of each of the parameter passing methods we have discussed.
2
4.1 Specific Skills
• Be able to describe the output of a code snippet under each of the methods
• Write a code snippet that shows different output under a set of parameter passing methods
5 Function Access
You should understand the code generated for each of the types of method dispatch, along with the associated run-time
costs.
5.1 Specific Skills

• Write the code to invoke a method using the dispatch schemes
• Draw the virtual function tables for a set of classes

• Identify which methods are invoked by a given line of code
6 Code Generation
You should be familiar with the code generated for the constructs we discussed in class. Code will be represented in a
simple abstract assembly syntax. You will not need to memorize any details of a specific instruction set architecture.
6.1 Specific Skills

• Recognize errors in presented code
• Generate a function entry or exit sequence

• Allocate registers for a given expression
7 Heap Management
You should be able to discuss the trade-offs and mechanics of the various heap management schemes. You should
understand how coalescing of free blocks is accomplished, along with the required metadata. You should understand
the problems addressed by copying and generational collectors.
7.1 Specific Skills

• Draw free lists before and after given sequences of actions
• Annotate code with reference counts

• Show the phases of a mark and sweep collector
• Draw the actions taken by a copying collector
8 Dataflow Analysis
You should understand the type of problem addressed by dataflow analysis. In particular, you should understand the
questions that are difficult to answer with an AST. You should also understand how a control flow graph can make
those questions more tractable.
3
8.1 Specific Skills
• Draw the CFG for a function

CS536 Final Study Guide: 1 Topic Overview

Uploaded by

Copyright:

Available Formats

CS536 Final Study Guide: 1 Topic Overview

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CS536 Final Study Guide: 1 Topic Overview

Uploaded by

Copyright:

Available Formats

CS536 Final Study Guide

December 12, 2010

– Memory organization (text segment, data segment, heap, stack)

• Function Access (Dispatch)

– Static dispatch (as in C)

– Function prolog, entry, and exit code

– Free list memory management (allocation and deallocation)

• Introductory Dataflow Analysis

2.1 Specific Skills

3.1 Specific Skills

5.1 Specific Skills

• Draw the virtual function tables for a set of classes

6.1 Specific Skills

• Generate a function entry or exit sequence

7.1 Specific Skills

• Annotate code with reference counts

You might also like