TXL solution to [[TIL Chairmarks]] #3.2, Common subexpression elimination.

Thie simple example demonstrates the basics of common subexpression elimination at the statement level using TXL.  In a realistic application for optimizing numerical programs, this would be combined with constant folding and code motion transformations to yield a higher quality result.

-- Main.JamesCordy - 19 Oct 2007


_File "TILcommonsubexp.Txl"_


<verbatim>
% TXL transformation to recognize and optimize common subexpressions
% Jim Cordy, March 2007

% This program finds subexpressions that are used two or more times without
% intervening changes to the variables used in it, and introduces a new
% temporary variable to optimize it to a single computation.

% Based on the TIL base grammar
include "TIL.Grm"

% Preserve comments, we're probably going to maintain the result
include "TILCommentOverrides.Grm"

% Override grammar to abstract compound statements
redefine statement
		  [compound_statement]
	 |	...
end redefine

define compound_statement
		  [if_statement]
	 |	[while_statement]
	 |	[for_statement]
end define

% Allow statements to be attributed so we don't mistake one we've
% generated for one we need to process

redefine statement 
		  ...
	 |	[statement] [attr 'NEW]
end redefine

% Main function

function main
	 replace [program]
		  P [program]
	 by
		  P [optimizeSubexpressions]
end function

rule optimizeSubexpressions
	 replace [statement*]
		  S1 [statement]
		  SS [statement*]

	 % Don't process statements we generated
	 deconstruct not * [attr 'NEW] S1
		  'NEW

	 % What we're looking for is an expression ...
	 deconstruct * [expression] S1
		  E [expression]

	 % ... that is nontrivial ...
	 deconstruct * [op]  E
		  _ [op]

	 % ... and repeated 
	 deconstruct * [expression] SS
		  E

	 % See if we can abstract it (checks if variables assigned between)
	 where
		  SS [?replaceExpnCopies S1 E 'T]

	 % If so, generate a new temporary variable name ...
	 construct T [id]
		  _ [unquote "temp"] [!]

	 % ... declare it, assign it the common expression,
	 % and replace instances of the expression with it
	 construct NewS [statement*]
		  'var T; 'NEW
		  T := E; 'NEW
		  S1 [replaceExpn E T]
		  SS [replaceExpnCopies S1 E T]
	 by
		  NewS 
end rule

% Recursively replace copies of a given expression with a given temporary variable id,
% provided the variables used in the expression are not assigned in between

function replaceExpnCopies S1 [statement] E [expression] T [id]
	 construct Eids [id*]
		  _ [^ E]

	 % If the previous statement did not assign any of the variables in the expression
	 where not
		  S1 [assigns each Eids]

	 % Then we can continue to substitute the temporary variable for the expression
	 % in the next statement ...
	 replace [statement*]
		  S [statement]
		  SS [statement*]

	 % ... as long as it isn't a compound statement that internally assigs one of 
	 % the variables in the expression 
	 where not all
		  S [assignsOne Eids]
			 [isCompoundStatement]
	 by
		  S [replaceExpn E T]
		  SS [replaceExpnCopies S E T]
end function

% Condition function checking to see if a statement assigns a variable

function assignsOne Eids [id*]
	 match [statement]
		  S [statement]
	 where 
		  S [assigns each Eids]
end function

function assigns Id [id]
	 match * [statement]
		  Id := _ [expression] ;
end function

function isCompoundStatement
	 match [statement]
		  _ [compound_statement]
end function

rule replaceExpn E [expression] T [id]
	 replace [expression]
		  E
	 by
		  T
end rule
</verbatim>


_Example run:_ "commonsubexpeg.til" is a meaningless little program with lots of common subexpressions, both optimizable and not.


<verbatim>
<linux> cat commonsubexpeg.til 
// Silly TIL example with lots of common subexpressions
var a;
var b;
var c;
a := 1;
b := a + 1;
var i;
i := 7;
c := a + 1;
i := i - c;
c := b + i;
for i := 1 to 10 do
	 a := b + i;
	 if b + i != 10 then
		  c := b;
	 else
		  c := b + i;
	 end
	 b := b + i;
end 
while b != 10 do
	 a := b + i;
	 if b + i != 10 then
		  a := c;
	 else
		  c := b + i;
	 end
	 b := b + i;
end
write (i - c);

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

// Silly TIL example with lots of common subexpressions
var a;
var b;
var c;
a := 1;
var temp1;
temp1 := a + 1;
b := temp1;
var i;
i := 7;
c := temp1;
i := i - c;
c := b + i;
for i := 1 to 10 do
	 var temp2;
	 temp2 := b + i;
	 a := temp2;
	 if temp2 != 10 then
		  c := b;
	 else
		  c := temp2;
	 end
	 b := temp2;
end
while b != 10 do
	 var temp3;
	 temp3 := b + i;
	 a := temp3;
	 if temp3 != 10 then
		  a := c;
	 else
		  c := temp3;
	 end
	 b := temp3;
end
write (i - c);

<linux> 
</verbatim>

-- Main.JamesCordy - 19 Oct 2007