Code Generation

Question 1

What are the 3 main components of code generation?

Answer 1

1. Instruction Selection
2. Register Allocation
3. Instruction Scheduling

Question 2

What is Instruction Selection?

Answer 2

Essentially pattern matching statements in the Intermediate Representation to statements in the target code

Makes locally optimal choices

Assumes we have enough registers

Question 3

How might we optimise integer multiplication?

Answer 3

We can convert the problem into a series of bit shifts and additions, these operations are a lot quicker than multiplying.

Question 4

What does a pre-call do?

Answer 4

Allocate memory for a procedure to be called

Question 5

What does the Prologue do?

Answer 5

Initialises variables at the start of a function call

Question 6

Why are function calls problematic?

Answer 6

Though they make the programmer’s life easier,

There is a significant overhead when calling and exiting the function

Question 7

What is a live range?

Answer 7

The interval between a variable’s definition and its last use

Question 8

What is top-down register allocation?

Answer 8

Reserve registers for the most frequently used values.

All other values are loaded from memory when needed

Question 9

What is bottom up register allocation?

Answer 9

We assign values to registers when the values become live,

If there are no registers available, we choose the register whose value will be used latest in the future, and save its value in memory (spilling)

Question 10

What is spilling?

Answer 10

This is when there are no free registers left, so we must move values to memory

E.g If we have 10 live values, but only 9 registers

Question 11

How do you compute the priority function used in Instruction Scheduling?

Answer 11

weight = latency + max(weight of children)