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.

-- Main.JamesCordy - 03 Jan 2008


_File "TILconst.Txl"_


<verbatim>
% 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
</verbatim>


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


<verbatim>
<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> 
</verbatim>

-- Main.JamesCordy - 03 Jan 2008