3. Assignment

3.1 Jump Optimisation

a) Write a module that eliminates

• jumps to jumps,
• conditional jumps to jumps,
• jumps to conditional jumps,
• useless jumps,
• unused goto-labels.

b) Performs code straightening, i.e. two subsequent basic blocks are merged.
Both optimisations should be applied until no jump template can be found (i.e. iterative approach).

3.2 Loop Analysis

Identify loops.
The first step is to compute the domination relation. Based on the domination relation we can build the dominator tree. Please, extend the node structure cfg_node with variable idom (i.e. the node number of the immediate dominator). For debug purpose, visualise domination relation and dominator tree. In the sequel, compute the back-edges of a CFG and identify the loop-header. Construct for each back-edge its loop set and determine the relation among them (is a loop contained in another one). Visualise the loop nesting forest.

Hint: If a loop-header has more than one back-edge, extend algorithm for detecting loops (pg. 17). Instead of having only one node in set W, add all nodes (n1,...,nk) of the back-edges that belong to the loop-header, to set W.