Statement Folding Using TXL

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.

-- JamesCordy - 04 Jan 2008

File "TILstmtfold.Txl"

% 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

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

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

-- JamesCordy - 04 Jan 2008