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"_ % 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 _Example run:_ "strength.til" is the simple TIL multiplies example program that happens to have an embedded opportunity for strength reduction. cat strength.til // Test of strength reduction for i := 1 to 9 do for j := 1 to 10 do write i*j; end end 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 -- Main.JamesCordy - 03 Jan 2008