Page

Web

Wiki

# Constant Folding Using TXL

Software Transformation Systems
TXL solution to TIL Chairmarks #3.4, Constant folding, recognize and resolve opportunities to fold constant expressions.

Thie simple example demonstrates constant propagation and expression folding using TXL.

-- JamesCordy - 03 Jan 2008

File "TILconst.Txl"

```% Constant propagation and folding for TIL
% Jim Cordy, January 2008

% Given a TIL program, recognize constant assignments to variables,
% and replace references to the variable with the constant (constant propagation),
% then recognize and compute constant expressions (constant folding).

% This program could be combined with other optimization rules such as
% code motion and redundant variable elimination to further optimize the result.

% Begin with the TIL base grammar, using precedence
#define PRIORITY
include "TIL.Grm"

% Preserve comments in this transformation
#pragma -comment

redefine statement
...
|   [comment] [NL]
end redefine

% Main function - just apply stages of the transformation

function main
replace [program]
P [program]
by
P [propagateConstants]
[foldConstantExpressions]
end function

% Constant propagation - find each constant assignment to a variable,
% and if it is not assigned again then replace references with the constant

rule propagateConstants
replace [repeat statement]
Var [id] := Const [literal] ;
Rest [repeat statement]
deconstruct not * [statement] Rest
Var := _ [expression] ;
deconstruct * [primary] Rest
Var
by
Var := Const;
Rest [replaceExpn Var Const]
end rule

rule replaceExpn Var [id] Const [literal]
replace [primary]
Var
by
Const
end rule

% Constant folding - find and evaluate constant expressions

rule foldConstantExpressions
replace [expression]
E [expression]

construct NewE [expression]
E % Generic folding of pure constant expressions
[resolveSubtraction]
[resolveMultiplication]
[resolveDivision]

% Other special cases involving constants (examples only, could be others)
[resolveSubtract0]
[resolveMultiply1Right]
[resolveMultiply1Left]
[resolveParentheses]

% Continue until we don't find anything to fold
deconstruct not NewE
E
by
NewE
end rule

replace [expression]
N1 [integernumber] + N2 [integernumber]
by
N1 [+ N2]
end rule

rule resolveSubtraction
replace [expression]
N1 [integernumber] - N2 [integernumber]
by
N1 [- N2]
end rule

rule resolveMultiplication
replace [term]
N1 [integernumber] * N2 [integernumber]
by
N1 [* N2]
end rule

rule resolveDivision
replace [term]
N1 [integernumber] / N2 [integernumber]
by
N1 [/ N2]
end rule

rule resolveParentheses
replace [primary]
( N [integernumber] )
by
N
end rule

replace [expression]
P [primary] + 0
by
P
end rule

rule resolveSubtract0
replace [expression]
P [primary] - 0
by
P
end rule

rule resolveMultiply1Right
replace [expression]
P [primary] * 1
by
P
end rule

rule resolveMultiply1Left
replace [expression]
1 * P [primary]
by
P
end rule
```

Example run: "const.til" is a meaningless little program with lots of opportunities for constant propagation and folding.

```<linux> cat const.til
// Silly meaningless example with opportunities to fold constants
var x; var y; var z; var a; var b; var c;
var d; var e; var j; var k; var m; var n; var r;
y := 1;
z := 2;
while 1 do
x := y + z;
a := 3;
z := 5;
j := 0;
while j != 100 do
r := 99;
d := 7;
k := a + z;
b := j * z;
d := (y + z) * d;
e := (x + z) * r;
j := j + 1;
end
// This one is constant for sure!
c := a + y;
m := y * b;
n := r * y;
end

<linux> txl const.til TILconst.Txl
TXL v10.5 (11.12.07) (c)1988-2007 Queen's University at Kingston
Compiling TILconst.Txl ...
Parsing const.til ...
Transforming ...

// Silly meaningless example with opportunities to fold constants
var x;
var y;
var z;
var a;
var b;
var c;
var d;
var e;
var j;
var k;
var m;
var n;
var r;
y := 1;
z := 2;
while 1 do
x := 1 + z;
a := 3;
z := 5;
j := 0;
while j != 100 do
r := 99;
d := 7;
k := 8;
b := j * 5;
d := 6 * d;
e := (x + 5) * 99;
j := j + 1;
end
// This one is constant for sure!
c := 4;
m := b;
n := r;
end
<linux>
```

-- JamesCordy - 03 Jan 2008