Language Implementation Flashcards
The phases of compilation are commonly grouped in which two categories?
- Front end responsible for the analysis of source code
- Back end responsible for the synthesis of target code.
Name the 7 conventional phases of a compiler.
First 3 phases (Language dependent)
- Scanning
- Parsing
- Semantic Analysis
Middle 2 (Compiler technology dependent)
- Intermediate code generation
- Machine independent code improvement
Last 2 (Machine dependent)
- Target code generation
- Machine specifig code improvement
Why use intermediate code generation?
Most code improvement can be done more easily on less hierarchical structure than AST. In other words, ASTs are too hierarchical to hadle code improvement.
How can an intermediate code generator be created?
The typical appoarch is to group nodes into basic blocks and then create a control flow graph.
In intermediate code generation, what is a Basic Block?
Maximal-length set of instructions that should execute sequentially at runtime, with no branches in or out.
In Intermediate code generation, what is a Control flow graph?
This is used to show the relationship among the nodes.
Name two types of transformations that can be done to the control flow graph for machine independent code improvement.
- Local code improvement - modifies the instruction sequence within each basic block to eliminate redundant loads, stores, and arithmetic computations
- Global code improvement - identifies and removes a variety of redundancies across the boundaries between basic blocks within a subroutine
Machine Dependent
What does target code generation do?
- Strings the basic blocks together into a linear program
- Tanslates each block into the instruction set of the target machine
- Generates branch instructions (or “fall-throughs”) that correspond to the arcs of the control flow graph.
- The output of this phase differs from real assembly language primarily in its continued reliance on virtual registers
Machine Dependent
What are some machine specific code improvements?
Register allocation
- Map the unlimited virtual registers onto the bounded set of registers available in the target machine
- If there aren’t enough architectural registers to go around, we may need to generate additional loads and stores to multiplex a given architectural register among two or more virtual registers
Instruction scheduling
- Reordering the instructions of each basic block to fill the pipeline(s) of the target machine
Code improvement
What is IF Intermediate responsible for?
- Link between front and back end of compilers
- Can be classified by their level—degree of machine independence
- Common examples:
- Trees or DAGs (Directed Acyclic Graphs)
- Stack-based
- 3-address instructions
- Many compilers use more than one intermediate form
In the intermediate stage, what are the responsibilities of trees or DAGs?
- Reflect structure of language
- Facilitates
- Incremental program updates (e.g. in a language-based editor)
- Direct interpretation
- Can be specified by attribute grammars
In the intermediate form stage, what is stack based?
In the intermediate form stage, what is 3 address instructions?
Elaborate on address space organization.
What does a relocatable object include?
What info can be organized in memory when the program is loaded into memory?
- Code
- Constants
- Initialized Data
- Uninitialized Data
- Stack
- Heap
- Files
- Dynamic Libraries
The linker supports separate compilation.
Elaborate on linking.
Describe Static and Dynamic Linkers
What are the two subtasks that linking is involved with?
- Relocation (AKA Loading)
- Resolution of external references
Picture of Relocatable Objects
On a multi-user system, it is common for several instances of a program to be executing simultaneously. What do operating systems do to keep track of the different instances.
What are the three separate phases of machine independent code improvement?
What is peephole optimization?
Give an example of a redundant load or store that can be eliminated by peephole optimization.
Peephole Optimization
Give an example of replacing load with dup.
Peephole Optimization
Give an example constant folding (condensing constant arithmetic).
Peephole Optimization
Give an example of constant propagation.
Peephole Optimization
Give an example of a common subexpression elimination.
Peephole Optimization
Give an example of copy propagation.
Peephole Optimization
Give an example of strength reduction.
What are other types of optimizations?
Name two classes of loop improvement.
What are induction variables?
What is loop unrolling?
Describe Loop Reordering
