Complexity of Constant Propagation?

Uday Khedker

(www.cse.iitb.ac.in/˜uday)

Department of Computer Science and Engineering, Indian Institute of Technology, Bombay

September 2017

Part 1

About These Slides

These slides constitute the lecture notes for CS618 Program Analysis course at IIT Bombay and have been made available as teaching material accompanying the book:

• Uday Khedker, Amitabha Sanyal, and Bageshri Karkare. Data Flow Analysis: Theory and Practice. CRC Press (Taylor and Francis Group).

2009.

(Indian edition published by Ane Books in 2013)

Apart from the above book, some slides are based on the material from the following book

• M. S. Hecht. Flow Analysis of Computer Programs. Elsevier North-Holland Inc. 1977.

These slides are being made available under GNU FDL v1.2 or later purely for academic or research use.

CS 618 General Frameworks: Outline

Outline

• Modelling General Flows

• Constant Propagation

• Strongly Live Variables Analysis (after mid-sem)

• Pointer Analyses (after mid-sem)

• Heap Reference Analysis (after mid-sem)

Precise Modelling of General Flows

CS 618

Complexity of Constant Propagation?

1 a=b+ 1 1 2 a=b+ 1 2

3 b=c+ 1 3 4 c=d+ 1 4

5 d= 2 5

1 a=b+ 1 1 2 a=b+ 1 2

3 b=c+ 1 3 4 c=d+ 1 4

5 d= 2 5

2 a=b+ 1 2 3 b=c+ 1 3 4 c=d+ 1 4 5 d= 2 5

Iteration #1

CS 618

Complexity of Constant Propagation?

1 a=b+ 1 1 2 a=b+ 1 2

3 b=c+ 1 3 4 c=d+ 1 4

5 d= 2 5

1 a=b+ 1 1 2 a=b+ 1 2

3 b=c+ 1 3 4 c=d+ 1 4 5 d= 2 5

Iteration #1

1 a=b+ 1 1 2 a=b+ 1 2

3 b=c+ 1 3 4 c= 3 4 5 d= 2 5

Iteration #2

1 a=b+ 1 1 2 a=b+ 1 2

3 b=c+ 1 3 4 c=d+ 1 4

5 d= 2 5

2 a=b+ 1 2 3 b=c+ 1 3 4 c=d+ 1 4 5 d= 2 5

Iteration #1

2 a=b+ 1 2 3 b=c+ 1 3 4 c= 3 4 5 d= 2 5

Iteration #2

1 a=b+ 1 1 2 a=b+ 1 2

3 b= 4 3 4 c= 3 4 5 d= 2 5

CS 618

Complexity of Constant Propagation?

1 a=b+ 1 1 2 a=b+ 1 2

3 b=c+ 1 3 4 c=d+ 1 4

5 d= 2 5

1 a=b+ 1 1 2 a=b+ 1 2

3 b=c+ 1 3 4 c=d+ 1 4 5 d= 2 5

Iteration #1

1 a=b+ 1 1 2 a=b+ 1 2

3 b=c+ 1 3 4 c= 3 4 5 d= 2 5

Iteration #2

1 a=b+ 1 1 2 a=b+ 1 2

3 b= 4 3 4 c= 3 4 5 d= 2 5

1 a= 5 1 2 a= 5 2

3 b= 3 3 4 c= 3 4 5 d= 2 5

X p1

X p2

Xp3

x f(x)

Paths Terminating atp2 Data Flow Value

p1,p2 x

p1,p2,p3,p2 f(x)

p1,p2,p3,p2,p3,p2 f(f(x)) =f²(x) p1,p2,p3,p2,p3,p2,p3,p2 f(f(f(x))) =f³(x)

. . . .

CS 618

Loop Closures of Flow Functions

X p1

X p2

Xp3

x f(x)

Paths Terminating atp2 Data Flow Value

p1,p2 x

p1,p2,p3,p2 f(x)

p1,p2,p3,p2,p3,p2 f(f(x)) =f²(x) p1,p2,p3,p2,p3,p2,p3,p2 f(f(f(x))) =f³(x)

. . . .

• For static analysis we need to summarize the value atp2by a value which is safe afteranyiteration.

f^∗(x) =x⊓f(x)⊓f²(x)⊓f³(x)⊓f⁴(x)⊓. . .

X p1

X p2

Xp3

x f(x)

Paths Terminating atp2 Data Flow Value

p1,p2 x

p1,p2,p3,p2 f(x)

p1,p2,p3,p2,p3,p2 f(f(x)) =f²(x) p1,p2,p3,p2,p3,p2,p3,p2 f(f(f(x))) =f³(x)

. . . .

• For static analysis we need to summarize the value atp2by a value which is safe afteranyiteration.

f^∗(x) =x⊓f(x)⊓f²(x)⊓f³(x)⊓f⁴(x)⊓. . .

• f^∗ is called theloop closureoff.

CS 618

Loop Closure Boundedness

• Boundedness off requires the existence of somek such that f^∗(x) =x⊓f(x)⊓f²(x)⊓. . .⊓f^k−1(x)

• This follows from the descending chain condition

• For efficiency, we need a constantk that is independent of the size of the lattice

• Flow functions in bit vector frameworks have constant Gen and Kill f^∗(x) = x⊓f(x)⊓f²(x)⊓f³(x)⊓. . .

f²(x) = f(Gen∪(x−Kill))

= Gen∪((Gen∪(x−Kill))−Kill)

= Gen∪((Gen−Kill)∪(x−Kill))

= Gen∪(Gen−Kill)∪(x−Kill)

= Gen∪(x−Kill) = f(x) f^∗(x) = x⊓f(x)

CS 618

Loop Closures in Bit Vector Frameworks

• Flow functions in bit vector frameworks have constant Gen and Kill f^∗(x) = x⊓f(x)⊓f²(x)⊓f³(x)⊓. . .

f²(x) = f(Gen∪(x−Kill))

= Gen∪((Gen∪(x−Kill))−Kill)

= Gen∪((Gen−Kill)∪(x−Kill))

= Gen∪(Gen−Kill)∪(x−Kill)

= Gen∪(x−Kill) = f(x) f^∗(x) = x⊓f(x)

• Loop Closures of Bit Vector Frameworks are 2-bounded.

• Flow functions in bit vector frameworks have constant Gen and Kill f^∗(x) = x⊓f(x)⊓f²(x)⊓f³(x)⊓. . .

f²(x) = f(Gen∪(x−Kill))

= Gen∪((Gen∪(x−Kill))−Kill)

= Gen∪((Gen−Kill)∪(x−Kill))

= Gen∪(Gen−Kill)∪(x−Kill)

= Gen∪(x−Kill) = f(x) f^∗(x) = x⊓f(x)

• Loop Closures of Bit Vector Frameworks are 2-bounded.

• Intuition: Since Gen and Kill are constant, same things are generated or killed in every application off.

Multiple applications off are not required unless the input value changes.

CS 618

Larger Values of Loop Closure Bounds

• Fast Frameworks≡2-bounded frameworks (eg. bit vector frameworks) Both these conditions must be satisfied

◮ Separability

Data flow values of different entities are independent

◮ Constant or Identity Flow Functions

Flow functions for an entity are either constant or identity

• Non-fast frameworks

At least one of the above conditions is violated

f :L→Lishbh1,bh2, . . . ,bhmiwherebhi computes the value ofbxi

CS 618

Separability

f :L→Lishbh1,bh2, . . . ,bhmiwherebhi computes the value ofbxi

Separable Non-Separable

Example: All bit vector frameworks Example: Constant Propagation

f :L→Lishbh1,bh2, . . . ,bhmiwherebhi computes the value ofbxi

Separable

h b x

, b x

, . . . , b x

i

f

h b y

, y b

, . . . , b y

i

Non-Separable

h b x

, b x

, . . . , b x

i

f

h b y

, b y

, . . . , y b

i

Example: All bit vector frameworks Example: Constant Propagation

CS 618

Separability

f :L→Lishbh1,bh2, . . . ,bhmiwherebhi computes the value ofbxi

Separable

h b x

, b x

, . . . , b x

i

bh2

h b y

, b y

, . . . , b y

i

Non-Separable

h b x

, b x

, . . . , b x

i

f

h b y

, b y

, . . . , y b

i

Example: All bit vector frameworks Example: Constant Propagation

f :L→Lishbh1,bh2, . . . ,bhmiwherebhi computes the value ofbxi

Separable

h b x

, b x

, . . . , b x

i

bh2

h b y

, b y

, . . . , b y

i

bh:bL →bL

Non-Separable

h b x

, b x

, . . . , b x

i

f

h b y

, b y

, . . . , y b

i

Example: All bit vector frameworks Example: Constant Propagation

CS 618

Separability

f :L→Lishbh1,bh2, . . . ,bhmiwherebhi computes the value ofbxi

Separable

h b x

, b x

, . . . , b x

i

bh2

h b y

, b y

, . . . , b y

i

bh:bL →bL

Non-Separable

h b x

, b x

, . . . , b x

i

bh2

h b y

, y b

, . . . , b y

i

Example: All bit vector frameworks Example: Constant Propagation

f :L→Lishbh1,bh2, . . . ,bhmiwherebhi computes the value ofbxi

Separable

h b x

, b x

, . . . , b x

i

bh2

h b y

, b y

, . . . , b y

i

bh:bL →bL

Non-Separable

h b x

, b x

, . . . , b x

i

bh2

h b y

, y b

, . . . , b y

i

bh:L→bL

Example: All bit vector frameworks Example: Constant Propagation

CS 618

Separability of Bit Vector Frameworks

• bL is{0,1},Lis{0,1}^m

• ⊓b is either boolean AND or boolean OR

• ⊤b and⊥b are 0 or 1 depending on⊓.b

• bhis abit functionand could be one of the following:

Raise Lower Propagate Negate

⊤b

⊥b

⊤b

⊥b

⊤b

⊥b

⊤b

⊥b

⊤b

⊥b

⊤b

⊥b

⊤b

⊥b

⊤b

⊥b

• bL is{0,1},Lis{0,1}^m

• ⊓b is either boolean AND or boolean OR

• ⊤b and⊥b are 0 or 1 depending on⊓.b

• bhis abit functionand could be one of the following:

Raise Lower Propagate Negate

⊤b

⊥b

⊤b

⊥b

⊤b

⊥b

⊤b

⊥b

⊤b

⊥b

⊤b

⊥b

⊤b

⊥b

⊤b

⊥b

CS 618

Larger Values of Loop Closure Bounds

1 a=b+ 1 1

2 a=b+ 1 2 3 b=c+ 1 3 4 c=d+ 1 4

5 d= 2 5

Composite flow function for the loop is

f(hv_a,vb,vc,vdi) =hv_b+ 1,vc+ 1,vd+ 1,2i

1 a=b+ 1 1

2 a=b+ 1 2 3 b=c+ 1 3 4 c=d+ 1 4

5 d= 2 5

Composite flow function for the loop is

f(hv_a,vb,vc,vdi) =hv_b+ 1,vc+ 1,vd+ 1,2i f is not 2-bounded because:

CS 618

Larger Values of Loop Closure Bounds

1 a=b+ 1 1

2 a=b+ 1 2 3 b=c+ 1 3 4 c=d+ 1 4

5 d= 2 5

Composite flow function for the loop is

f(hv_a,vb,vc,vdi) =hv_b+ 1,vc+ 1,vd+ 1,2i f is not 2-bounded because:

f(hb⊤,⊤,b ⊤,b ⊤i)b = hb⊤, ⊤,b ⊤,b 2i

1 a=b+ 1 1

2 a=b+ 1 2 3 b=c+ 1 3 4 c=d+ 1 4

5 d= 2 5

Composite flow function for the loop is

f(hv_a,vb,vc,vdi) =hv_b+ 1,vc+ 1,vd+ 1,2i f is not 2-bounded because:

f(hb⊤,⊤,b ⊤,b ⊤i)b = hb⊤, ⊤,b ⊤,b 2i f²(h⊤,b ⊤,b ⊤,b ⊤i)b = h⊤,b ⊤,b 3, 2i

CS 618

Larger Values of Loop Closure Bounds

1 a=b+ 1 1

2 a=b+ 1 2 3 b=c+ 1 3 4 c=d+ 1 4

5 d= 2 5

Composite flow function for the loop is

f(hv_a,vb,vc,vdi) =hv_b+ 1,vc+ 1,vd+ 1,2i f is not 2-bounded because:

f(hb⊤,⊤,b ⊤,b ⊤i)b = hb⊤, ⊤,b ⊤,b 2i f²(h⊤,b ⊤,b ⊤,b ⊤i)b = h⊤,b ⊤,b 3, 2i f³(h⊤,b ⊤,b ⊤,b ⊤i)b = h⊤,b 4, 3, 2i

1 a=b+ 1 1

2 a=b+ 1 2 3 b=c+ 1 3 4 c=d+ 1 4

5 d= 2 5

Composite flow function for the loop is

f(hv_a,vb,vc,vdi) =hv_b+ 1,vc+ 1,vd+ 1,2i f is not 2-bounded because:

f(hb⊤,⊤,b ⊤,b ⊤i)b = hb⊤, ⊤,b ⊤,b 2i f²(h⊤,b ⊤,b ⊤,b ⊤i)b = h⊤,b ⊤,b 3, 2i f³(h⊤,b ⊤,b ⊤,b ⊤i)b = h⊤,b 4, 3, 2i f⁴(h⊤,b ⊤,b ⊤,b ⊤i)b = h5, 4, 3, 2i

CS 618

Larger Values of Loop Closure Bounds

1 a=b+ 1 1

2 a=b+ 1 2 3 b=c+ 1 3 4 c=d+ 1 4

5 d= 2 5

Composite flow function for the loop is

f(hv_a,vb,vc,vdi) =hv_b+ 1,vc+ 1,vd+ 1,2i f is not 2-bounded because:

f(hb⊤,⊤,b ⊤,b ⊤i)b = hb⊤, ⊤,b ⊤,b 2i f²(h⊤,b ⊤,b ⊤,b ⊤i)b = h⊤,b ⊤,b 3, 2i f³(h⊤,b ⊤,b ⊤,b ⊤i)b = h⊤,b 4, 3, 2i f⁴(h⊤,b ⊤,b ⊤,b ⊤i)b = h5, 4, 3, 2i f⁵(hb⊤,⊤,b ⊤,b ⊤i)b = h5, 4, 3, 2i

Constant Propagation

CS 618

Example of Constant Propagation

n1

a= 1 b= 2 c=a+b

n1

n2 c=a+b d=a∗b n2

n3

d=c−1 a= 2 b= 1 c=a+b

n3

n1

a= 1 b= 2 c=a+b

n1

n2 c=a+b d=a∗b n2

n3

d=c−1 a= 2 b= 1 c=a+b

n3

MoP hb⊤,⊤,b ⊤,b ⊤ib

h1,2,3,⊤ib

hb⊥,⊥,b 3,2i hb⊥,⊥,b 3,2i

h⊥,b ⊥,b 3,2i

h2,1,3,2i

CS 618

Example of Constant Propagation

n1

a= 1 b= 2 c=a+b

n1

n2 c=a+b d=a∗b n2

n3

d=c−1 a= 2 b= 1 c=a+b

n3

MoP hb⊤,⊤,b ⊤,b ⊤ib

h1,2,3,⊤ib

hb⊥,⊥,b 3,2i hb⊥,⊥,b 3,2i

h⊥,b ⊥,b 3,2i

h2,1,3,2i

MFP hb⊤,⊤,b ⊤,b ⊤ib

h1,2,3,⊤ib

hb⊥,⊥,b 3,⊥ib hb⊥,⊥,b ⊥,b ⊥ib

h⊥,b ⊥,b ⊥,b ⊥ib

h2,1,3,⊥ib

(⊤)b undef orud

−∞

. . .

. . .

(⊥)b nonconst ornc

b

⊓ hv,udi hv,nci hv,c1i hv,udi hv,udi hv,nci hv,c1i hv,nci hv,nci hv,nci hv,nci

hv,c2i hv,c2i hv,nci Ifc1=c2thenhv,c1ielsehv,nci

CS 618

Overall Lattice for Integer Constant Propagation

• Inn/Outn values are mappingsVar→bL: Inn,Outn∈Var→bL

• Overall latticeL is a set of mappingsVar→bL: L=Var→bL

• ⊓andb⊓get defined by⊑and⊑b

◮ Partial order is restricted to data flow values of the same variable Data flow values of different variables are incomparable

(x,v1)⊑(y,v2) ⇔ x=y∧v1⊑vb 2

OR x7→v1⊑y 7→v2 ⇔ x=y∧v1⊑vb 2

◮ For meet operation, we assume thatX is a total function Partial functions are made total by using⊤valueb

X⊓Y =

(x,v1⊓vb 2)|(x,v1)∈X,(x,v2)∈Y

OR X⊓Y =

x7→v1⊓vb 2|x 7→v1∈X,x7→v2∈Y

Accessing and manipulating a mappingX ⊆A→B

• X(a) denotes the image ofa∈A X(a)∈B

• X[a7→v] changes the image ofainX tov

X[a7→v] = (X− {(a,u)|u∈B}) ∪ {(a,v)}

CS 618

Defining Data Flow Equations for Constant Propagation

Inn =





BI={hy,udi |y ∈Var} n=Start

p∈pred(n)

Outp otherwise

Outn = fn(Inn)

fn(X) =













X[y 7→c] nisy =c,y ∈Var,c∈Const X[y 7→nc] nisinput(y),y ∈var

X[y 7→X(z)] nisy =z,y ∈Var,z ∈Var X[y 7→eval(e,X)] nisy =e,y ∈Var,e∈Expr

X otherwise

eval(e,X) =









nc a∈Opd(e)∩Var,X(a) =nc ud a∈Opd(e)∩Var,X(a) =ud

−X(a) eis −a X(a)⊕X(b) eis a⊕b

n1 input (e); n1

n2 a= 7;b= 2;f =e;

if (f>0) n2

n3 a= 2;

if (f ≥e+ 2) n3

n4 b=c+ 1;

if (b≥7) n4

n6 if (f ≥e+ 1) n6

n5 f =f+ 1; n5

n7 c=d∗a; n7n8 d=a+b; n8

n d=a+ 1; n n e=a+b; n

false

true false

false

true false

true

true

CS 618

Example Program for Constant Propagation

n1 input (e); n1

n2 a= 7;b= 2;f =e;

if (f>0) n2

n3 a= 2;

if (f ≥e+ 2) n3

n4 b=c+ 1;

if (b≥7) n4

n6 if (f ≥e+ 1) n6

n5 f =f+ 1; n5

n7 c=d∗a; n7n8 d=a+b; n8

n d=a+ 1; n n e=a+b; n

false

true false

false

true false

true

true

For readability, we have combined many statements in a single block. However, con- stant propagation requires every basic block to contain a single statement because of the presence of dependent parts in flow functions.

Iteration #1 iteration #2 iteration #3 iteration #4 Inn₁ ⊤b,⊤b,⊤b,⊤b,⊤b,⊤b

Outn1 ⊤b,⊤b,⊤b,⊤b,⊥b,⊤b Inn₂ ⊤b,⊤b,⊤b,⊤b,⊥b,⊤b Outn2 7,2,⊤b,⊤b,⊥b,⊥b

Inn₃ 7,2,⊤b,⊤b,⊥b,⊥b ⊥b,2,⊤b,3,⊥b,⊥b ⊥b,2,6,3,⊥b,⊥b ⊥b,⊥b,6,3,⊥b,⊥b Outn3 2,2,⊤b,⊤b,⊥b,⊥b 2,2,⊤b,3,⊥b,⊥b 2,2,6,3,⊥b,⊥b 2,⊥b,6,3,⊥b,⊥b Inn₄ 2,2,⊤b,⊤b,⊥b,⊥b 2,2,⊤b,3,⊥b,⊥b 2,2,6,3,⊥b,⊥b 2,⊥b,6,3,⊥b,⊥b Outn4 2,⊤b,⊤b,⊤b,⊥b,⊥b 2,⊤b,⊤b,3,⊥b,⊥b 2,7,6,3,⊥b,⊥b

Inn₅ 2,⊤b,⊤b,⊤b,⊥b,⊥b 2,⊤b,⊤b,3,⊥b,⊥b 2,7,6,3,⊥b,⊥b Outn5 2,⊤b,⊤b,⊤b,⊥b,⊥b 2,⊤b,⊤b,3,⊥b,⊥b 2,7,6,3,⊥b,⊥b

Inn6 2,2,⊤b,⊤b,⊥b,⊥b 2,2,⊤b,3,⊥b,⊥b 2,2,6,3,⊥b,⊥b 2,⊥b,6,3,⊥b,⊥b Outn6 2,2,⊤b,⊤b,⊥b,⊥b 2,2,⊤b,3,⊥b,⊥b 2,2,6,3,⊥b,⊥b 2,⊥b,6,3,⊥b,⊥b

Inn7 2,2,⊤b,⊤b,⊥b,⊥b 2,2,⊤b,3,⊥b,⊥b 2,⊥b,6,3,⊥b,⊥b Outn₇ 2,2,⊤b,⊤b,⊥b,⊥b 2,2,6,3,⊥b,⊥b 2,⊥b,6,3,⊥b,⊥b

Inn8 2,2,⊤b,⊤b,⊥b,⊥b 2,2,⊤b,3,⊥b,⊥b 2,2,6,3,⊥b,⊥b 2,⊥b,6,3,⊥b,⊥b Outn₈ 2,2,⊤b,4,⊥b,⊥b 2,2,⊤b,4,⊥b,⊥b 2,2,6,4,⊥b,⊥b 2,⊥b,6,⊥b,⊥b,⊥b

Inn9 2,2,⊤b,4,⊥b,⊥b 2,2,6,⊥b,⊥b,⊥b 2,⊥b,6,⊥b,⊥b,⊥b Outn₉ 2,2,⊤b,3,⊥b,⊥b 2,2,6,3,⊥b,⊥b 2,⊥b,6,3,⊥b,⊥b Inn10 ⊥b,2,⊤b,⊤b,⊥b,⊥b ⊥b,2,⊤b,3,⊥b,⊥b ⊥b,⊥b,6,3,⊥b,⊥b

CS 618

Result of Constant Propagation

n1 input (e); n1

n2 a= 7;b= 2;f =e;

if (f>0) n2

n3 a= 2;

if (f ≥e+ 2) n3

n4 b=c+ 1;

if (b≥7) n4

n6 if (f ≥e+ 1) n6

n5 f =f+ 1; n5

n7 c=d∗a; n7n8 d=a+b; n8

a= 2

n d=a+ 1; n a= 2 n e=a+b; n

false

true false

false

true false

true

true

n1 input (e); n1

n2 a= 7;b= 2;f =e;

if (f>0) n2

n3 a= 2;

if (f ≥e+ 2) n3

n4 b=c+ 1;

if (b≥7) n4

n6 if (f ≥e+ 1) n6

n5 f =f+ 1; n5

n7 c=d∗a; n7

a= 2, d= 3

n8 d=a+b; n8

a= 2

n d=a+ 1; n a= 2 n e=a+b; n

false

true false

false

true false

true

true

CS 618

Result of Constant Propagation

n1 input (e); n1

n2 a= 7;b= 2;f =e;

if (f>0) n2

n3 a= 2;

if (f ≥e+ 2) n3

n4 b=c+ 1;

if (b≥7) n4

c= 6

n6 if (f ≥e+ 1) n6

n5 f =f+ 1; n5

n7 c=d∗a; n7

a= 2, d= 3

n8 d=a+b; n8

a= 2

n d=a+ 1; n a= 2 n e=a+b; n

false

true false

false

true false

true

true

n1 input (e); n1

n2 a= 7;b= 2;f =e;

if (f>0) n2

n3 a= 2;

if (f ≥e+ 2) n3

n4 b=c+ 1;

if (b≥7) n4

c= 6

n6 if (f ≥e+ 1) n6

n5 f =f+ 1; n5

n7 c=d∗a; n7

a= 2, d= 3

n8 d=a+b; n8

a= 2

n d=a+ 1; n a= 2 n e=a+b; n

false

true false

true false

true

true

CS 618

Monotonicity of Constant Propagation

Proof obligation: X1⊑X2 ⇒ fn(X1)⊑fn(X2) where,

fn(X) =













X[y7→c] nisy =c,y ∈Var,c∈Const (C1) X[y7→nc] nisinput(y),y ∈var (C2) X[y7→X(z)] nisy =z,y ∈Var,z ∈Var (C3) X[y7→eval(e,X)] nisy =e,y ∈Var,e∈Expr (C4)

X otherwise (C5)

• The proof obligation trivially follows for cases C1, C2, C3, and C5

• For case C4, it requires showing X1⊑X2 ⇒ eval(e,X1)⊑eval(e,X2) which follows from the definition ofeval(e,X)

n1

a= 1 b= 2 c=a+b

n1

n2 c=a+b d=a∗b n2

n3

d=c−1 a= 2 b= 1 c=a+b

n3

CS 618

Non-Distributivity of Constant Propagation

n1

a= 1 b= 2 c=a+b

n1

n2 c=a+b d=a∗b n2

n3

d=c−1 a= 2 b= 1 c=a+b

n3

a= 1,b= 2

• x=h1,2,3,?i(AlongOutn1 →Inn2)

n1

a= 1 b= 2 c=a+b

n1

n2 c=a+b d=a∗b n2

n3

d=c−1 a= 2 b= 1 c=a+b

n3

a= 1,b= 2

a= 2,b= 1

• x=h1,2,3,?i(AlongOutn1 →Inn2)

• y =h2,1,3,2i(AlongOutn3→Inn2)

CS 618

Non-Distributivity of Constant Propagation

n1

a= 1 b= 2 c=a+b

n1

n2 c=a+b d=a∗b n2

n3

d=c−1 a= 2 b= 1 c=a+b

n3

a= 1,b= 2

a= 2,b= 1

• x=h1,2,3,?i(AlongOutn1 →Inn2)

• y =h2,1,3,2i(AlongOutn3→Inn2)

• Function application before merging

f(x)⊓f(y) = f(h1,2,3,?i)⊓f(h2,1,3,2i)

= h1,2,3,2i ⊓ h2,1,3,2i

= hb⊥,⊥,b 3,2i

n1

a= 1 b= 2 c=a+b

n1

n2 c=a+b d=a∗b n2

n3

d=c−1 a= 2 b= 1 c=a+b

n3

a= 1,b= 2

a= 2,b= 1

• x=h1,2,3,?i(AlongOutn1 →Inn2)

• y =h2,1,3,2i(AlongOutn3→Inn2)

• Function application before merging

f(x)⊓f(y) = f(h1,2,3,?i)⊓f(h2,1,3,2i)

= h1,2,3,2i ⊓ h2,1,3,2i

= hb⊥,⊥,b 3,2i

• Function application after merging

f(x⊓y) = f(h1,2,3,?i ⊓ h2,1,3,2i)

= f(h⊥,b ⊥,b 3,2i)

= hb⊥,⊥,b ⊥,b ⊥ib

CS 618

Non-Distributivity of Constant Propagation

n1

a= 1 b= 2 c=a+b

n1

n2 c=a+b d=a∗b n2

n3

d=c−1 a= 2 b= 1 c=a+b

n3

a= 1,b= 2

a= 2,b= 1

• x=h1,2,3,?i(AlongOutn1 →Inn2)

• y =h2,1,3,2i(AlongOutn3→Inn2)

• Function application before merging

f(x)⊓f(y) = f(h1,2,3,?i)⊓f(h2,1,3,2i)

= h1,2,3,2i ⊓ h2,1,3,2i

= hb⊥,⊥,b 3,2i

• Function application after merging

f(x⊓y) = f(h1,2,3,?i ⊓ h2,1,3,2i)

= f(h⊥,b ⊥,b 3,2i)

= hb⊥,⊥,b ⊥,b ⊥ib

a= 1 b= 2

a= 2 b= 1

c=a+b

CS 618

Why is Constant Propagation Non-Distributive?

a= 1 b= 2

a= 2 b= 1

c=a+b

a= 1 a= 2 b= 1 b= 2

Possible combinations due to merging

a= 1 b= 2

a= 2 b= 1

c=a+b

a= 1 a= 2 b= 1 b= 2

Possible combinations due to merging

c=a+b= 3

• Correct combination.

CS 618

Why is Constant Propagation Non-Distributive?

a= 1 b= 2

a= 2 b= 1

c=a+b

a= 1 a= 2 b= 1 b= 2

Possible combinations due to merging

c=a+b= 3

• Correct combination.

a= 1 b= 2

a= 2 b= 1

c=a+b

a= 1 a= 2 b= 1 b= 2

Possible combinations due to merging

c=a+b= 2

• Wrong combination.

• Mutually exclusive information.

• No execution path along which this information holds.

CS 618

Why is Constant Propagation Non-Distributive?

a= 1 b= 2

a= 2 b= 1

c=a+b

a= 1 a= 2 b= 1 b= 2

Possible combinations due to merging

c=a+b= 4

• Wrong combination.

• Mutually exclusive information.

• No execution path along which this information holds.

n1 a=b n1

n2 a=b n1

n3 d= 2 n1

n4 a=b n1

n5 c=d n1

n6 a=b n1

n7 b=c n1

n8 a=b n1

n10 a=b nn109 a=b n1

CS 618

Tutorial Problem on Constant Propagation

How many iterations do we need?

n1 a=b n1

n2 a=b n1

n3 d= 2 n1

n4 a=b n1

n5 c=d n1

n6 a=b n1

n7 b=c n1

n8 a=b n1

n10 a=b nn109 a=b n1

2

n1 a=b n1

n2 a=b n1

n3 d= 2 n1

n4 a=b n1

n5 c=d n1

n6 a=b n1

n7 b=c n1

n8 a=b n1

n10 a=b nn109 a=b n1

3

CS 618

Tutorial Problem on Constant Propagation

How many iterations do we need?

n1 a=b n1

n2 a=b n1

n3 d= 2 n1

n4 a=b n1

n5 c=d n1

n6 a=b n1

n7 b=c n1

n8 a=b n1

n10 a=b nn109 a=b n1

4

n1 a=b n1

n2 a=b n1

n3 d= 2 n1

n4 a=b n1

n5 c=d n1

n6 a=b n1

n7 b=c n1

n8 a=b n1

n10 a=b nn109 a=b n1

5

CS 618

Tutorial Problem on Constant Propagation

How many iterations do we need?

n1 a=b n1

n2 a=b n1

n3 d= 2 n1

n4 a=b n1

n5 c=d n1

n6 a=b n1

n7 b=c n1

n8 a=b n1

n10 a=b nn109 a=b n1

6

n1 a=b n1

n2 a=b n1

n3 d= 2 n1

n4 a=b n1

n5 c=d n1

n6 a=b n1

n7 b=c n1

n8 a=b n1

n10 a=b nn109 a=b n1

• Every back edge occurs only once in the ifp fromn3ton1that goes vian5,n7, andn9.

• 5 + 1 iterations for computing data flow values (+1 iteration to detect convergence)

CS 618

Tutorial Problem on Constant Propagation

And now how many iterations do we need?

n1 a=b n1

n2 a=b n1

n3 a=b n1

n4 a=b n1

n5 b=c n1

n6 a=b n1

n7 c=d n1

n8 a=b n1

n10 a=b nn109 d = 2 n1

n1 a=b n1

n2 a=b n1

n3 a=b n1

n4 a=b n1

n5 b=c n1

n6 a=b n1

n7 c=d n1

n8 a=b n1

n10 a=b nn109 d = 2 n1

Back edgen10→n1 needs to be traversed once each for back edges n9→n8,n7→n6,n5→n4, and n3→n2 (in that order).

⇒ 8 + 1 iterations.

CS 618

Boundedness of Constant Propagation

1 a= 1 1

2 a= 1 2

3 a= 1 3

4 a=b+ 1 4

5 b=c+ 1 5

6 c=a+ 1 5

7 a= 1 1

1 a= 1 1

2 a= 1 2

3 a= 1 3

4 a=b+ 1 4

5 b=c+ 1 5

6 c=a+ 1 5

7 a= 1 1

Summary flow function:

(data flow value at node 7) f(hv_a,vb,vci) = h1⊓(vb+ 1),

(vc+ 1), (va+ 1) i

CS 618

Boundedness of Constant Propagation

1 a= 1 1

2 a= 1 2

3 a= 1 3

4 a=b+ 1 4

5 b=c+ 1 5

6 c=a+ 1 5

7 a= 1 1

Summary flow function:

(data flow value at node 7) f(hv_a,vb,vci) = h1⊓(vb+ 1),

(vc+ 1), (va+ 1) i

f⁰(⊤) = hb⊤,⊤,b ⊤ib f¹(⊤) = h1, ⊤,b ⊤ib

1 a= 1 1

2 a= 1 2

3 a= 1 3

4 a=b+ 1 4

5 b=c+ 1 5

6 c=a+ 1 5

7 a= 1 1

Summary flow function:

(data flow value at node 7) f(hv_a,vb,vci) = h1⊓(vb+ 1),

(vc+ 1), (va+ 1) i

f⁰(⊤) = hb⊤,⊤,b ⊤ib f¹(⊤) = h1, ⊤,b ⊤ib f²(⊤) = h1, ⊤,b 2i

CS 618

Boundedness of Constant Propagation

1 a= 1 1

2 a= 1 2

3 a= 1 3

4 a=b+ 1 4

5 b=c+ 1 5

6 c=a+ 1 5

7 a= 1 1

Summary flow function:

(data flow value at node 7) f(hv_a,vb,vci) = h1⊓(vb+ 1),

(vc+ 1), (va+ 1) i

f⁰(⊤) = hb⊤,⊤,b ⊤ib f¹(⊤) = h1, ⊤,b ⊤ib f²(⊤) = h1, ⊤,b 2i f³(⊤) = h1, 3, 2i

1 a= 1 1

2 a= 1 2

3 a= 1 3

4 a=b+ 1 4

5 b=c+ 1 5

6 c=a+ 1 5

7 a= 1 1

Summary flow function:

(data flow value at node 7) f(hv_a,vb,vci) = h1⊓(vb+ 1),

(vc+ 1), (va+ 1) i

f⁰(⊤) = hb⊤,⊤,b ⊤ib f¹(⊤) = h1, ⊤,b ⊤ib f²(⊤) = h1, ⊤,b 2i f³(⊤) = h1, 3, 2i f⁴(⊤) = hb⊥,3, 2i

CS 618

Boundedness of Constant Propagation

1 a= 1 1

2 a= 1 2

3 a= 1 3

4 a=b+ 1 4

5 b=c+ 1 5

6 c=a+ 1 5

7 a= 1 1

Summary flow function:

(data flow value at node 7) f(hv_a,vb,vci) = h1⊓(vb+ 1),

(vc+ 1), (va+ 1) i

f⁰(⊤) = hb⊤,⊤,b ⊤ib f¹(⊤) = h1, ⊤,b ⊤ib f²(⊤) = h1, ⊤,b 2i f³(⊤) = h1, 3, 2i f⁴(⊤) = hb⊥,3, 2i f⁵(⊤) = h⊥,b 3, ⊥ib

1 a= 1 1

2 a= 1 2

3 a= 1 3

4 a=b+ 1 4

5 b=c+ 1 5

6 c=a+ 1 5

7 a= 1 1

Summary flow function:

(data flow value at node 7) f(hv_a,vb,vci) = h1⊓(vb+ 1),

(vc+ 1), (va+ 1) i

f⁰(⊤) = hb⊤,⊤,b ⊤ib f¹(⊤) = h1, ⊤,b ⊤ib f²(⊤) = h1, ⊤,b 2i f³(⊤) = h1, 3, 2i f⁴(⊤) = hb⊥,3, 2i f⁵(⊤) = h⊥,b 3, ⊥ib f⁶(⊤) = h⊥,b ⊥,b ⊥ib

CS 618

Boundedness of Constant Propagation

1 a= 1 1

2 a= 1 2

3 a= 1 3

4 a=b+ 1 4

5 b=c+ 1 5

6 c=a+ 1 5

7 a= 1 1

Summary flow function:

(data flow value at node 7) f(hv_a,vb,vci) = h1⊓(vb+ 1),

(vc+ 1), (va+ 1) i

f⁰(⊤) = hb⊤,⊤,b ⊤ib f¹(⊤) = h1, ⊤,b ⊤ib f²(⊤) = h1, ⊤,b 2i f³(⊤) = h1, 3, 2i f⁴(⊤) = hb⊥,3, 2i f⁵(⊤) = h⊥,b 3, ⊥ib f⁶(⊤) = h⊥,b ⊥,b ⊥ib f⁷(⊤) = h⊥,b ⊥,b ⊥ib

1 a= 1 1

2 a= 1 2

3 a= 1 3

4 a=b+ 1 4

5 b=c+ 1 5

6 c=a+ 1 5

7 a= 1 1

f^∗(⊤) =

6 i=0fⁱ(⊤)

CS 618

Boundedness of Constant Propagation

The moral of the story:

• The data flow value of every variable could change twice

The moral of the story:

• The data flow value of every variable could change twice

• In the worst case, only one change may happen in every step of a function application

CS 618

Boundedness of Constant Propagation

The moral of the story:

• The data flow value of every variable could change twice

• In the worst case, only one change may happen in every step of a function application

• Maximum number of steps: 2× |Var|

The moral of the story:

• The data flow value of every variable could change twice

• In the worst case, only one change may happen in every step of a function application

• Maximum number of steps: 2× |Var|

• Boundedness parameterk is (2× |Var|) + 1

CS 618

Conditional Constant Propagation

n1 input (e); n1

n2 a= 7;b= 2;f =e; if (f>0) n2

n3 a= 2;

if (f ≥e+ 2) n3

n4 b=c+ 1;

if (b≥7) n4

n6 if (f ≥e+ 1) n6

n5 f =f+ 1; n5

n7 c=d∗a; n7n8 d=a+b; n8

n d=a+ 1; n n e=a+b; n

false

true false

false

true false

true

true

An execution trace of the program when the value read for variableeis some numberx≤0

(otherwise the loop will not be entered)

n1 input (e); n1

n2 a= 7;b= 2;f =e; if (f>0) n2

n3 a= 2;

if (f ≥e+ 2) n3

n4 b=c+ 1;

if (b≥7) n4

n6 if (f ≥e+ 1) n6

n5 f =f+ 1; n5

n7 c=d∗a; n7n8 d=a+b; n8

n d=a+ 1; n n e=a+b; n

false

true false

false

true false

true

true

h2,2,?,?,x,xi

An execution trace of the program when the value read for variableeis some numberx≤0

(otherwise the loop will not be entered)