Page

Web

Wiki

# Strength Reduction Using TXL

Software Transformation Systems
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.

-- 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.

```<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>
```

-- JamesCordy - 03 Jan 2008