TXL solution to [[TIL Chairmarks]] #3.3, Strength reduction, recognize opportunities to reduce multiplication by an iterator to iterative addition.

Thie simple example demonstrates the basics of strength reduction optimizations using TXL.  Strength reduction is normally a part of optimization for high performance numerical applications on modest processors such as ARM.

-- Main.JamesCordy - 03 Jan 2008


_File "TILstrengthred.Txl"_


<verbatim>
% Basic strength reduction in TIL programs using TXL
% Jim Cordy, January 2008

% Given a TIL program, look for opportunities to leverage loops to
% reduce multiplications to additions (strength reduction).

% This program could be combined with other optimization rules
% to form a comprehensive source optimizer.


% 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 [strengthReduceMultiplications]
end function


% Strength reduction in for loops - recognize expresssions of the form
% "x+*i" in for loops iterating "i", and reduce to addition.

rule strengthReduceMultiplications
	 % Find a for statement
	 replace [repeat statement]
		  'for I [id] := Low [expression] 'to High [expression] 'do
				InnerStatements [repeat statement]
		  'end
		  Rest [repeat statement]

	 % That has an expression multiplied by the iterator 
	 % (for simplicity we assume a simple variable reference in this example)
	 deconstruct * [term] InnerStatements
		  J [id] * I

	 % Where the expression is not changed in the loop
	 deconstruct not * [statement] InnerStatements
		  J := _ [expression] ;
	 deconstruct not * [statement] InnerStatements
		  'for J := _ [expression] 'to _ [expression] 'do
				_ [repeat statement]
		  'end

	 % Construct a unique new variable name
	 construct JI [id]
		  J [_ I] [!]

	 % And convert to additive form
	 by
		  var JI;
		  '// can be constant-folded later
		  JI := ((Low)-1) * J; 
		  'for I := Low 'to High 'do
				JI := JI + J;
				InnerStatements [replaceMultiply J I JI] 
		  'end
		  Rest 
end rule


rule replaceMultiply J [id] I [id] JI [id]
	 replace [term]
		  J * I
	 by
		  JI
end rule
</verbatim>


_Example run:_ "strength.til" is the simple TIL multiplies example program that happens to have an embedded opportunity for strength reduction.


<verbatim>
<linux> cat strength.til
// Test of strength reduction
for i := 1 to 9 do
	 for j := 1 to 10 do
		  write i*j;
	 end 
end

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

// Test of strength reduction
for i := 1 to 9 do
	 var i_j1;
	 // can be constant-folded later
	 i_j1 := ((1) - 1) * i;
	 for j := 1 to 10 do
		  i_j1 := i_j1 + i;
		  write i_j1;
	 end
end

<linux> 
</verbatim>

-- Main.JamesCordy - 03 Jan 2008