TXL solution to [[TIL Chairmarks]] #3.5, Statement folding, recognizing and optimizing compile-time known if statements, and possibly while and for statements.

Thie simple example demonstrates statement folding of if and while statements using TXL.  Assumes that it is used with a constant folding opimization to yield constant conditions.

-- Main.JamesCordy - 04 Jan 2008


_File "TILstmtfold.Txl"_


<verbatim>
% Statement folding using TIL
% Jim Cordy, January 2008

% Given a TIL program, look for opportunities to reduce code footprint
% by optimizing out unreachable code based on statically known conditions.

% Statement folders are a staple of embedded code versioning, used for code 
% reduction in limited memory applications such as mobile devices.
% It is also used in some languages as a surrogate for conditional compilation.

% This program is normally combined with a constant folding opimizer that 
% evaluates constant expressions to yield the statically known conditions.


% 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 - applies folders for the various statements

function main
	 replace [program]
		  P [program]
	 by
		  P [foldTrueIfStatements]
			 [foldFalseIfStatements]
			 [warnTrueWhileStatements]
			 [foldFalseWhileStatements]
end function


% Folding rules for constant condition if statements

rule foldTrueIfStatements
	 % Find an if statement
	 replace [repeat statement]
		  'if Cond [expression] 'then
				TrueStatements [repeat statement]
				ElseClause [opt else_statement]
		  'end
		  Rest [repeat statement]

	 % That has a constant true condition
	 where
		  Cond [isTrueEqual]
				 [isTrueNotEqual]

	 % By the true part
	 by
		  '// Folded true if
		  TrueStatements [. Rest] 
end rule

rule foldFalseIfStatements
	 % Find an if statement
	 replace [repeat statement]
		  'if Cond [expression] 'then
				TrueStatements [repeat statement]
				ElseClause [opt else_statement]
		  'end
		  Rest [repeat statement]

	 % That has a constant false condition
	 where not
		  Cond [isTrueEqual]
				 [isTrueNotEqual]

	 % By the false part
	 construct FalseStatements [repeat statement]
		  _ [getElseStatements ElseClause]
	 by
		  '// Folded false if
		  FalseStatements [. Rest] 
end rule

function getElseStatements ElseClause [opt else_statement]
	 deconstruct ElseClause
		  'else
				FalseStatements [repeat statement]
	 replace [repeat statement]
		  % default none
	 by
		  FalseStatements
end function


% Folding rules for constant condition while statements

rule warnTrueWhileStatements
	 % "replace $" indicates one-pass search, since we don't want to match 
	 % the same while statement twice

	 % Find a while statement 
	 replace $ [repeat statement]
		  'while Cond [expression] 'do
				TrueStatements [repeat statement]
		  'end
		  Rest [repeat statement]

	 % That has a constant true condition
	 where
		  Cond [isTrueEqual]
				 [isTrueNotEqual]

	 % Warn but leave alone
	 by
		  'while Cond 'do
				'// Warning: while condition always true
				TrueStatements 
		  'end
		  Rest
end rule

rule foldFalseWhileStatements
	 % Find a while statement
	 replace [repeat statement]
		  'while Cond [expression] 'do
				TrueStatements [repeat statement]
		  'end
		  Rest [repeat statement]

	 % That has a constant false condition
	 where not
		  Cond [isTrueEqual]
				 [isTrueNotEqual]

	 % And delete it!
	 by
		  '// Folded false while 
		  Rest
end rule


% Utility functions to detect true conditions - these can be as smart as we wish
% (For now just simple ones)

function isTrueEqual 
	 match [expression]
		  I [integernumber] '= J [integernumber]
	 where 
		  I [= J]
end function

function isTrueNotEqual 
	 match [expression]
		  I [integernumber] '!= J [integernumber]
	 where not 
		  I [= J]
end function
</verbatim>


_Example run:_ "foldstmt.til" is a meaningless little program with several opportunities for statement folding.


<verbatim>
<linux> cat foldstmt.til 
// Toy TIL example with constant conditions
var a; var b; var c; var i;
a := 1;
b := a + 1;
i := 7;
c := a + 1;
for i := 1 to 10 do
	 a := b + i;
	 if 11 = 10 then
		  c := b;
	 else
		  c := b + i;
		  a := a + 1;
	 end
	 while (2 = 1) do
		  b := b + i;
	 end
end 
while 5 != 10 do
	 a := b + i;
	 if 1 = 1 then
		  a := c;
	 else
		  c := b + i;
	 end
	 b := b + i;
	 if 17 = 42 then
		  c := b + b;
	 end
end
write (i - c);

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

// Toy TIL example with constant conditions
var a;
var b;
var c;
var i;
a := 1;
b := a + 1;
i := 7;
c := a + 1;
for i := 1 to 10 do
	 a := b + i;
	 // Folded false if
	 c := b + i;
	 a := a + 1;
	 // Folded false while 
end
while 5 != 10 do
	 // Warning: while condition always true
	 a := b + i;
	 // Folded true if
	 a := c;
	 b := b + i;
	 // Folded false if
end
write (i - c);

<linux>
</verbatim>

-- Main.JamesCordy - 04 Jan 2008