11.2 Optimising Compilers

Question 1

Where does the optimiser fit in within the compiler pipeline

Answer 1

Middle: After front-end (AST), before backend (Binary).

Question 2

What are 3 different angles an optimiser could optimise for

Answer 2

• Execution time
• Memory or binary size
• Power consumption
• Example tradeoff between time and power is loop unrolling (more mem = more power etc.).

Question 3

What are compiler optimisation flags used for

Answer 3

• Choose which optimisation and what level
• Ofast can have up to 6x improvement

Question 4

How does the optimser (compiler) transform the IR (ie AST) (and what is a basic block)

Answer 4

• Transforms IR in-place replacing unop with op
• Basic block: series of statements (no branches)

Question 5

What is subexpression elimination (compiler). Use it on the following code

Answer 5

Question 6

What is dead code elimination (compiler). Use it on the following code

Answer 6

Question 7

What is constant folding (compiler). Use it on the following code

Answer 7

Question 8

What is loop-invariant hoisting (compiler), use it on the following code

Answer 8

Question 9

What is function inlining (compiler). Use it on the following code

Answer 9

Question 10

Strength reduction (compiler): What is a loop induction variable (linear)

Answer 10

• Replacing expensive loop multiplications with additions (1 cycle instead of 3)
• Linear function with i as variable

Question 11

Using a loop induction variable (linear), strength reduce the following code

Answer 11

Question 12

What are the 4 steps of strength reduction (compiler)

Answer 12

Question 13

What is the purpose of register allocation (in terms of an unlimited amount of variables) (and what is register spilling)

Answer 13

• Deciding which variable is stored in which register (or RAM / Disk)
• By finding out which variables are live.
• Register spilling: Not enough registers => some variables in RAM

Question 14

Register allocation: what is the purpose of liveness analysis and how to decide if a variable is live.

Answer 14

Question 15

What is the liveness analysis of the following program:

Answer 15

Question 16

How does a linear scan determine variable liveness and register allocation:

Answer 16

Question 17

What would a linear scan of the following program look like

Answer 17

Question 18

What is graph coloring for register allocation

Answer 18

Question 19

What would the graph coloring for the following program look like

Answer 19