Strength Reduction Using TXL

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