Def-Use chains - first sparse [Reif & Tarjan, SIAM JC’81]

Directly connects defs and uses

Fewer chains

Problems:

Cannot handle backward

Not as precise as CFG for some problems

• conditional constant propagation

Worst case space is O(E2V)

1

start

x:= 1

y:=2

if x=1

y:=y+1

T

T

:= y

:= x

2

3

4

5

6

7

8

9

10

x

y

0

Previous slide

Next slide

Back to first slide

View graphic version