ALGORITHM (Gries Method with Constant Folding)

i = 1 (current triple under consideration)

v = 1 (value number)

p = 1 (pointer to table of available computations)

go to OPTYPE

NEXT: if i == last triple

terminate algorithm

else

i = i + 1

OPTYPE: if operator (OP) is assignment (=)

go to ASSIGN

else (operator is arithmetic type)

go to COMP

COMP: Examine operands of triple

If operand 1 is not yet assigned a value number

valnum operand = v

v = v + 1.

If operand 2 is not yet assigned a value number

valnum operand = v

v = v + 1.

value number of operand 1 = v1

value number of operand 2 = v2

If both operand 1 and operand 2 are constants (then FOLD)

c = yes

d = no

evaluate CONST = OP v1 v2

If CONST is in symbol table

valnum triple (i) = valnum CONST

else

valnum CONST = v

v = v + 1

valnum triple (i) = valnum CONST

go to NEXT

Search for OP v1,v2 in available computations table.

If found then triple is redundant

c = no

d = no

value number triple (i) = value number found

go to NEXT

If not found then triple is not redundant.

Enter triple into available computations table

as follows: (p) OP v1,v2

value number(p) = v

c = no

d = yes

value number triple (i) = v

v = v + 1

p = p + 1

go to NEXT

ASSIGN: If operand 2 is not assigned a value number,

valnum operand 2 = v

v = v + 1

value number operand 1 = value number operand 2

c = no

d = yes

go to NEXT