Language Implementation

Question 1

The phases of compilation are commonly grouped in which two categories?

Answer 1

• Front end responsible for the analysis of source code
• Back end responsible for the synthesis of target code.

Question 2

Name the 7 conventional phases of a compiler.

Answer 2

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

Question 3

Why use intermediate code generation?

Answer 3

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.

Question 4

How can an intermediate code generator be created?

Answer 4

The typical appoarch is to group nodes into basic blocks and then create a control flow graph.

Question 5

In intermediate code generation, what is a Basic Block?

Answer 5

Maximal-length set of instructions that should execute sequentially at runtime, with no branches in or out.

Question 6

In Intermediate code generation, what is a Control flow graph?

Answer 6

This is used to show the relationship among the nodes.

Question 7

Name two types of transformations that can be done to the control flow graph for machine independent code improvement.

Answer 7

• 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

Question 8

Machine Dependent

What does target code generation do?

Answer 8

• 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

Question 9

Machine Dependent

What are some machine specific code improvements?

Answer 9

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

Question 10

What is IF Intermediate responsible for?

Answer 10

• 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

Question 11

In the intermediate stage, what are the responsibilities of trees or DAGs?

Answer 11

• Reflect structure of language
• Facilitates
  
  • Incremental program updates (e.g. in a language-based editor)
  • Direct interpretation
  • Can be specified by attribute grammars

Question 12

In the intermediate form stage, what is stack based?

Answer 12

Question 13

In the intermediate form stage, what is 3 address instructions?

Answer 13

Question 14

Elaborate on address space organization.

Answer 14

Question 15

What does a relocatable object include?

Answer 15

Question 16

What info can be organized in memory when the program is loaded into memory?

Answer 16

• Code
• Constants
• Initialized Data
• Uninitialized Data
• Stack
• Heap
• Files
• Dynamic Libraries

Question 17

The linker supports separate compilation.

Elaborate on linking.

Answer 17

Question 18

Describe Static and Dynamic Linkers

Answer 18

Question 19

What are the two subtasks that linking is involved with?

Answer 19

• Relocation (AKA Loading)
• Resolution of external references

Question 20

Picture of Relocatable Objects

Answer 20

Question 21

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.

Answer 21

Question 22

What are the three separate phases of machine independent code improvement?

Answer 22

Question 23

What is peephole optimization?

Answer 23

Question 24

Give an example of a redundant load or store that can be eliminated by peephole optimization.

Answer 24

Question 25

Peephole Optimization Give an example of replacing load with dup.

Answer 25

Question 26

Peephole Optimization ## Footnote Give an example constant folding (condensing constant arithmetic).

Answer 26

Question 27

Peephole Optimization Give an example of constant propagation.

Answer 27

Question 28

Peephole Optimization ## Footnote Give an example of a common subexpression elimination.

Answer 28

Question 29

Peephole Optimization ## Footnote Give an example of copy propagation.

Answer 29

Question 30

Peephole Optimization ## Footnote Give an example of strength reduction.

Answer 30

Question 31

What are other types of optimizations?

Answer 31

Question 32

Name two classes of loop improvement.

Answer 32

Question 33

What are induction variables?

Answer 33

Question 34

What is loop unrolling?

Answer 34

Question 35

Describe Loop Reordering

Answer 35