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 predsWe 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.
What are the initial assignments for timeIn and timeOut?
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
Answer:
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.
Answer: Yes, the entry node (labelled start below).
Answer: It's a forward dataflow problem. Information is propagated from start forwards. TimeIn depends on its predecessor .
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 endAnswer: Control flow graph:
Node id | Instruction | Uses | Defs | Succs | Preds |
0: | start | 1 | |||
1: | a = b + c | b,c | a | 2 | 0 |
2: | d = a 10 | a | d | 3 | 1 |
3: | if d goto L1 else L2 | d | 5,7 | 2 | |
4: | b = a - 1 | a | b | 5 | |
5: | a = f(d,e) | d,e | a | 6 | 4,3 |
6: | if a goto L0 else L2 | a | 3,7 | 5 | |
7: | a = b | b | a | 8 | 3,6 |
Iteration:
Node id | Preds | Step 0 | Step 1 | Step 2 | |||
timeIn | timeOut | timeIn | timeOut | timeIn | timeOut | ||
0: | 0 | 0 | 0 | 0 | 0 | ||
1: | 0 | 0 | 1 | 0 | 1 | ||
2: | 1 | 1 | 2 | 1 | 2 | ||
3: | 2 | 2 | 3 | 2 | 3 | ||
4: | |||||||
5: | 4,3 | 3 | 4 | 3 | 4 | ||
6: | 5 | 4 | 5 | 4 | 5 | ||
7: | 3,6 | 3 | 4 | 3 | 4 | ||