Sparse Evaluation Graphs[Choi, Cytron, Ferrante, POPL’91]

Generalization of SSA approach

Graph connects nodes that generate, use and combine

Sparse evaluation graph -

• specific to data flow problem and data flow quantity

Reduces the number of points computed

Forward and backward

O(N3) time to construct

start

X:= 1

y:=2

if x=1

y:=y+1

T

T

:= y

:= x

2

3

4

5

6

7

8

9

10

Live Variables - y

Previous slide

Next slide

Back to first slide

View graphic version