## Compilers - Exercise 5: Termination analysis

In this exercise we will use data-flow analysis to identify code that may not terminate. The idea is to compute a lower bound on the execution time of the code. Assume that we have as input a control-flow graph (CFG) as described in the lecture notes:

> data CFGNode = Node Id Instruction [Register] [Register] [Id]  [Id]
> --                                 defs       uses       succs preds

We will pretend that all instructions take 1 unit of time to execute - even function calls. The output of the analysis will be, for every node in the graph, the earliest time at which this node could have been reached, assuming that the start node is reached at time 0. Nodes that are never reached are assigned the special value Infinity. If all final (ie exit) nodes of the graph have the value Infinity, the code will never terminate. In fact, nodes assigned Infinity correspond to unreachable nodes that may be removed from the control flow graph.
1. One of the data-flow equations clearly will take the form

1. What is the equation for defining timeIn in terms of termOut?

2. As shown in the lecture notes, we use iteration to solve the system of DFA equations timeIn and timeOut for each node in the CFG.

What are the initial assignments for timeIn and timeOut?

3. Do any nodes need to be initialized with a value different from the others?

4. Is this a forward or backward data-flow analysis?

2. Draw the control flow graph for the following code, and show the operation of the iteration algorithm using the equations of part 1.
start:
a = b + c
d = a < 10
L0:
if d goto L1 else L2
b = a - 1
L1:
a = f(d,e)
if a goto L0 else L2
L2:
a = b
end


Paul Kelly  Imperial College London  2009. Acknowledgement: This exercise is loosely based on parts of Homework 4 of Andrew Myer's CS412 Introduction to Compilers course at Cornell.

## Exercise 5.1:

1. One of the data-flow equations clearly will take the form

1. What is the equation for defining timeIn in terms of timeOut?

2. As shown in the lecture notes, we use iteration to solve the system of DFA equations timeIn and timeOut for each node in the CFG.

What are the initial assignments for timeIn and timeOut?

Answer: You initialise all nodes (except start) to be Infinity, except for the entry node (start below), which you initialise to be zero.

3. Do any nodes need to be initialized with a value different from the others?

Answer: Yes, the entry node (labelled start below).

4. Is this a forward or backward data-flow analysis?

Answer: It's a forward dataflow problem. Information is propagated from start forwards. TimeIn depends on its predecessor .

2. Draw the control flow graph for the following code, and show the operation of the iteration algorithm using the equations of part 1.
      start:
1:      a = b + c
2:      d = a < 10
L0:
3:      if d goto L1 else L2
4:      b = a - 1
L1:
5:      a = f(d,e)
6:      if a goto L0 else L2
L2:
7:      a = b
end