Programs for the Constant Propagation Problem

1 A Simple Example

The following example demonstrates the of type of constants that arise in many programs:

procedure p(f_{1}, f_{2}, f_{3}) begin

⋮ print (f_{1}) /* The constant 2 */

⋮ print (f_{2} ∗ f_{1}) /* The constant 10 */

⋮ print (f_{3}) /* Not a constant */

⋮ end

procedure main begin

x := 2

⋮ y := x /* y is a copy constant */

⋮ call p(y, 5, 6)

⋮ call p(y, 5, 7)

⋮ end

2 A Square Root Example

At the end of the following program x must have the constant 0.

procedure main begin

read (z)
if ⋯ then y := 2
else y := −3 fi
x := y ∗ y + y − 6
print (x)

end

Therefore, a compiler could have potentially replaced this code by:

procedure main begin

read (z) print (0)

end

3 Interprocedural Constants

The following example demonstrates some of the difficulties in analyzing recursive procedures.

global x procedure p(a) begin

read (c) if c > 0 then a := a − 2 call p(a) a := a + 2 fi x := −2 ∗ a + 5 print (x) /* x is not a constant here */

end

procedure main begin

call p(7)

print (x) /* x is a constant here */ end

4 The McCarthy 91 function

In the following code f yields x − 10 when x > 100 and 91 otherwise.

function f(x) begin

if x > 100 then return x − 10 else return f(f(x + 11)) fi

end

procedure main begin

read (x)

if x > 100 then print (91) else print (f(x)) fi

end

Therefore, the code could have been replaced by:

procedure main begin

read (x) print (91)

end