TXL solution to [[TIL Chairmarks]] #3.1, Move all invariant assignments outside of while loops. This is a simple demonstration of the basics of data flow checking and code motion using TXL. For TIL this is not very challenging. In real languages and applications, more sophisticated data flow and alias analysis across procedures is needed. In TXL this more sophisticated analysis is done using source code markup to localize dependency information before actual code movement. -- Main.JamesCordy - 03 Nov 2005 _File "TILcodemotion.Txl"_ % Lift independent assignments outside of TIL while loops % J.R. Cordy, November 2005 % This TXL program will optimize a TIL program by moving all assignments % not dependent on computation inside while loops to the outside. % For loops can be done similarly, but are not handled by this program. % Based on the TIL grammar include "TIL.Grm" % Lift all independent assignments out of loops rule main % 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 first 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 _Example run:_ "lift.til" is a meaningless little program with lots of data dependencies, lots of opportunities for code motion, and all global declarations for demonstration purposes only. cat lift.til var x; var y; var z; var a; var b; var c; var d; var e; var j; var k; var m; var n; var r; y := 1; z := 2; while 1 do x := y + z; a := 3; z := 5; j := 0; while j != 100 do r := 99; d := 7; k := a + z; b := j * z; d := (y + z) * d; e := (x + z) * r; j := j + 1; end c := a + y; m := y * b; n := r * y; end txl lift.til TILcodemotion.Txl TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston Compiling TILcodemotion.Txl ... Parsing lift.til ... Transforming ... var x; var y; var z; var a; var b; var c; var d; var e; var j; var k; var m; var n; var r; y := 1; z := 2; a := 3; c := a + y; r := 99; n := r * y; while 1 do x := y + z; z := 5; j := 0; k := a + z; e := (x + z) * r; while j != 100 do d := 7; b := j * z; d := (y + z) * d; j := j + 1; end m := y * b; end