A more sophisticated TXL solution to TIL Chairmarks #3.1, Move all invariant assigned computations outside of while loops.

This is a more sophisticated version of Lift Invariant Assignments Using TXL, which uses renaming of masking assignments in a loop to expose more opportunities to move assigned computations out of the loop. See the original for the basics of code motion in TXL, and this one for the renaming aspect.

-- JamesCordy - 04 Nov 2005

File "TILcodemotion2.Txl"

% Lift independent assigned computations outside of TIL while loops
% J.R. Cordy, November 2005

% This more sophisitcated TXL program will optimize a TIL program by moving all 
% assigned computations not dependent on computation inside while loops to the outside.
% The process works in two steps: 
%   (1) Renaming of masking assignments (subsequent assignments to a variable), 
%       which exposes hidden opportunities for code motion, and 
%   (2) Lifting of independent assignments, exactly as in the simpler assignment
%       only case in TILcodemotion.Txl
% Finally, declarations are synthesized and inserted for any new variables introduced 
% by the renaming.

% Based on the TIL grammar
include "TIL.Grm"

% Two main parts - the actual renaming and lifting, then the introduction of missing 
% declarations for any introduced renamed variables
function main
    replace [program]
        P [program]
    by
        P [renameAndLift]
          [declareNewVariables]
end function


% Main rule: Rename masking assignments and lift them outside loops until no more can be 
% renamed and no more can belifted
rule renameAndLift
    replace [program]
        P [program]

    % We continue as long as a match for either transform can be found - the form [?rule] 
    %   in TXL means test if a pattern match for the rule can be found
    % In TXL, the composition of two conditionals is "or", so this guard tests whether
    %   either rule can find a match
    where
        P [?renameMaskingAssignments]
          [?liftLoopAssignments]

    % If so, apply the rules and continue until the condition above fails 
    by
        P [renameMaskingAssignments]
          [liftLoopAssignments]
end rule


% Ruleset 1: Rename any masking assignments (i.e., re-assignments to the same variable)
% This exposes hidden opportunities to move assigned computations out of the loop
rule renameMaskingAssignments
    % Find every while loop
    replace [statement*]
        while Expn [expression] do
            Body [statement*]
        'end
        Rest [statement*]

    % Keep renaming until there are no more to rename
    where
        Body [?renameAssignment Body]
    by
        while Expn do
            Body [renameAssignment Body]
        'end 
        Rest
end rule

% Rename repeated assignments
rule renameAssignment Body [statement*]
    % Find an assignment
    replace [statement*]
        X [id] := E [expression];
        Rest [statement*]

    % Construct the context it appears in
    construct PreContext [statement*]
        Body [deleteAssignmentAndRest X]

    % Rename any subsequent assignment to X, if possible
    where
        Rest [?renameAssignmentsTo X PreContext]
    by
        X := E;
        Rest [renameAssignmentsTo X PreContext]
end rule

% Rename any subsequent assignment to X, if possible
rule renameAssignmentsTo X [id] PreContext [statement*]
    % Find a subsequent assignment to X
    replace [statement*]
        X := E [expression];
        Rest [statement*]

    % It only makes sense to rename it if its effect doesn't wrap around ...
    where not 
        PreContext [refers X]

    % ... and it is not an iteration 
    where not
        E [refers X]

    % ... and it is not assigned again
    where not
        Rest [assigns X]

    % If all that is ok, then rename it
    construct NewX [id]
        X [!]
    by  
        NewX := E;
        Rest [$ X NewX]      % [$ X NewX] means substitute NewX for X everywhere in Rest
end rule


% Ruleset 2: Lift all independent assignments out of loops
% This is exactly the same ruleset as in TILcodemotion.Txl - we could use a TXL "include"
% statement to reuse the original
rule liftLoopAssignments
    % Find every loop
    replace [statement*]
        while Expn [expression] do
            Body [statement*]
        'end 
        Rest [statement*]

    % Construct a list of all the top-level assignments in it
    construct AllAssignments [statement*]
        Body [deleteNonAssignments]

    % Construct a copy of the loop to work on
    construct LiftedLoop [statement*]
        while Expn do
            Body 
        'end 

    % Only proceed if there are assignments left that can be lifted out
    % The [?loopLift] form tests if the pattern of the [loopLift] rule can be matched -
    % "each AllAssignments" tests this for any of the top-level internal assignments
    where
        LiftedLoop [?loopLift Body each AllAssignments]

    % If the above guard succeeds, some can be moved out, so go ahead and move them,
    % replacing the original loop with the result
    by
        LiftedLoop [loopLift Body each AllAssignments]
        [. Rest]
end rule

% Attempt to lift a given assignment outside the loop
function loopLift Body [statement*] Assignment [statement]
    deconstruct Assignment
        X [id] := E [expression];

    % Extract a list of all the identifiers used in the expression
    construct IdsInExpression [id*]
        _ [^ E]

    % Replace the loop and its contents
    replace [statement*]
        Loop [statement*]

    % We can only lift the assignment out if all the identifiers in its
    % expression are not assigned in the loop ...
    where not
        Loop [assigns each IdsInExpression]

    % ... and X itself is assigned only once
    deconstruct * Body
        X := _ [expression];
        Rest [statement*]
    where not
        Rest [assigns X]

    % ... and the the effect of it does not wrap around the loop
    construct PreContext [statement*]
        Body [deleteAssignmentAndRest X]
    where not
        PreContext [refers X]

    % Now lift out the assignment
    by
        Assignment
        Loop [deleteAssignment Assignment]
end function


% Utility rules used above

% Delete a given assignment statement from a scope
function deleteAssignment Assignment [statement]
    replace * [statement*]
        Assignment
        Rest [statement*]
    by
        Rest
end function

% Delete all non-assignment statements in a scope -
% given a scope, yields the assignments only
rule deleteNonAssignments
    replace [statement*]
        S [statement]
        Rest [statement*]
    deconstruct not S
        _ [assignment_statement]
    by
        Rest
end rule

% Delete everything in a scope from the assignment to X on -
% given a scope and X, yields the context of the first assignment to X
function deleteAssignmentAndRest X [id]
    replace * [statement*]
        X := E [expression];
        Rest [statement*]
    by
        % nada
end function

% Condition - given a scope, does the scope assign to the identifier?
function assigns Id [id]
    match * [assignment_statement]
        Id := Expn [expression];
end function

% Condition - given a scope, does the scope refer to the identifier?
function refers Id [id]
    match * [id]
        Id
end function


% Ruleset 3: Declare any renaming variables we introduced
rule declareNewVariables
    replace [program]
        P [program]
    % Continue until we can't find any more
    where
        P [?declareNewVariable P]
    by
        P [declareNewVariable P]
end rule

function declareNewVariable P [program]
    replace * [statement*]
        X [id] := E [expression];
        MoreStatements [statement*]
    deconstruct not * [declaration] P
        'var X;
    by
        'var X;
        X := E;
        MoreStatements 
end function

Example run: "lift2.til" is a meaningless little program intended to demonstrate the difference between the simple assignment code motion solution of Lift Invariant Assignments using TXL and the more sophisticated one above. We first run the simple solution, and no opportunities for code motion are found. Then we run the solution above, which renames masking assignments to expose two computations that can be moved out of the loop.

<linux> cat lift2.til
var a; var b; var c; 
var x; var y; var z;
while 1 do
    x := a + b;
    y := x;
    a := y + 3;
    x := b + c;
    y := x - 2;
    z := x + a * y;
end
<linux> txl lift2.til TILcodemotion.Txl
TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston
Compiling TILcodemotion.Txl ... 
Parsing lift2.til ...
Transforming ...
var a;
var b;
var c;
var x;
var y;
var z;
while 1 do
    x := a + b;
    y := x;
    a := y + 3;
    x := b + c;
    y := x - 2;
    z := x + a * y;
end
<linux> txl lift2.til TILcodemotion2.Txl
TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston
Compiling TILcodemotion2.Txl ... 
Parsing lift2.til ...
Transforming ...
var a;
var b;
var c;
var x;
var y;
var z;
var x4;
x4 := b + c;
var y2;
y2 := x4 - 2;
while 1 do
    x := a + b;
    y := x;
    a := y + 3;
    z := x4 + a * y2;
end
<linux>