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
[resolveAddition]
[resolveSubtraction]
[resolveMultiplication]
[resolveDivision]
% Other special cases involving constants (examples only, could be others)
[resolveAdd0]
[resolveSubtract0]
[resolveMultiply1Right]
[resolveMultiply1Left]
[resolveParentheses]
% Continue until we don't find anything to fold
deconstruct not NewE
E
by
NewE
end rule
rule resolveAddition
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
rule resolveAdd0
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