SSA (SSA Based def use chains) [Cytron,Ferrante, Rosen, Wegman, Zadeck, TOPLS’91]

Every use has a single definition

Phi functions:

• Distinguish values of variables transmitted on distinct incoming control flow edges

Worst-case size is O(EV)

Same precision as CFG

Used extensively

Cannot be used for backward data flow problems

start

x:= 1

y1:=2

if x=1

y2:= y1+1

:= y3

:= x

if x=1

:= x

y3=Ø(y1,y2)

x y1 y2 y3

Previous slide

Next slide

Back to first slide

View graphic version