Dependence Flow Graph[Johnson & Pingali, PLDI’93]

DFG: phi nodes at merge points and switch nodes at branch points

Cost: space O(EV)

time O(EV)

Both backward and forward problems

Efficient:

• propagates where needed, bypassing SESE regions

1

start

x:= 1

y1:=2

if x=1

y2:=y1+1

T

T

:= y3

:= x

2

3

4

5

6

7

8

9

10

y3=Ø(y1,y2)

Previous slide

Next slide

Back to first slide

View graphic version