% Backward static slicing of Tiny Imperative Language programs % Jim Cordy, February 2007 % Given a TIL program with a single statement marked up using the % XML markup <mark> </mark>, backward slices the program from that % statement and its referenced variables. % Works by inducing markup of unmarked statements from already marked-up % statements beginning with the original marked statement until a fixed % point is reached, then removing all remaining unmarked statements. % No dependency graph is required. % Begin with the TIL base grammar include "TIL.Grm" % Add allowance for XML markup of TIL statements redefine statement ... | [marked_statement] end redefine define marked_statement [xmltag] [statement] [xmlend] end define define xmltag < [SPOFF] [id] > [SPON] end define define xmlend < [SPOFF] / [id] > [SPON] end define % Conflate while and for statements into one form to optimize % handling of both forms in one rule redefine statement [loop_statement] | ... end redefine define loop_statement [loop_head] [NL][IN] [statement*] [EX] 'end [NL] end define define loop_head while [expression] do | for [id] := [expression] to [expression] do end define % The main function gathers the steps of the transformation: % induce markup to a fixed point, remove unmarked statements, % remove declarations for variables not used in the slice, % and strip the markups to yield the sliced program function main replace [program] P [program] by P [propogateMarkupToFixedPoint] [removeUnmarkedStatements] [removeRedundantDeclarations] [stripMarkup] end function % Back propogate markup of statements beginning with the initially % marked statement of interest. Continue until a fixed point, % when no new markups are induced rule propogateMarkupToFixedPoint replace [program] P [program] construct NP [program] P [backPropogateAssignments] [backPropogateReads] [whilePropogateControlVariables] [loopPropogateMarkup] [loopPropogateMarkupIn] [ifPropogateMarkupIn] [compoundPropogateMarkupOut] % We're at a fixed point when P = NP :-) deconstruct not NP P by NP end rule % Rule to back-propogate markup of assignments. % A previous assignment is in the slice if its assigned % variable is used in a following marked statement rule backPropogateAssignments skipping [marked_statement] replace [statement*] X [id] := E [expression] ; More [statement*] where More [hasMarkedUse X] by <mark> X := E; </mark> More end rule % Similar rule for back-propogating markup of read statements rule backPropogateReads skipping [marked_statement] replace [statement*] read X [id] ; More [statement*] where More [hasMarkedUse X] by <mark> read X; </mark> More end rule function hasMarkedUse X [id] match * [marked_statement] M [marked_statement] deconstruct * [expression] M E [expression] deconstruct * [id] E X end function % Assignments to variables inside a while loop containing statements % of a slice are also in the slice if the while condition uses them rule whilePropogateControlVariables replace $ [statement] while E [expression] do S [statement*] 'end deconstruct * [statement] S _ [marked_statement] by while E do S [markAssignmentsTo E] [markReadsOf E] 'end end rule rule markAssignmentsTo Exp [expression] skipping [marked_statement] replace $ [statement] X [id] := E [expression] ; deconstruct * [id] Exp X by <mark> X := E; </mark> end rule rule markReadsOf Exp [expression] skipping [marked_statement] replace $ [statement] read X [id] ; deconstruct * [id] Exp X by <mark> read X; </mark> end rule % Rule for propagating dependencies around loops. % An assignment inside a loop is in the slice if its assigned variable % is used in a marked statement anywhere inside the loop rule loopPropogateMarkup replace $ [statement] Head [loop_head] S [statement*] 'end construct MarkedS [marked_statement*] _ [^ S] construct MarkedE [expression*] _ [^ MarkedS] by Head S [markAssignmentsTo each MarkedE] [markReadsOf each MarkedE] 'end end rule % Rule for propagating dependencies into loops. % An assignment inside the loop is in the slice if its assigned variable % is used in a marked statement anywhere following the loop rule loopPropogateMarkupIn replace $ [statement*] Head [loop_head] S [statement*] 'end MoreS [statement*] construct MarkedMoreS [marked_statement*] _ [^ MoreS] construct MarkedMoreE [expression*] _ [^ MarkedMoreS] by Head S [markAssignmentsTo each MarkedMoreE] [markReadsOf each MarkedMoreE] 'end MoreS end rule % Rule for propagating dependencies into if statements. % An assignment inside the then or else part of the if is in the slice % if its assigned variable is used in a marked statement anywhere % following the if rule ifPropogateMarkupIn replace $ [statement*] if E [expression] then ST [statement*] ElseSE [opt else_statement] 'end MoreS [statement*] construct MarkedMoreS [marked_statement*] _ [^ MoreS] construct MarkedMoreE [expression*] _ [^ MarkedMoreS] by if E then ST [markAssignmentsTo each MarkedMoreE] ElseSE [markAssignmentsTo each MarkedMoreE] 'end MoreS end rule % Rule for propagating dependencies out. % A compound statement of any kind is in the loop if it contains % a marked statement rule compoundPropogateMarkupOut replace $ [statement*] CS [statement] More [statement*] deconstruct not CS _ [marked_statement] deconstruct * [statement] CS _ [marked_statement] by <mark> CS </mark> More end rule % Rule to remove all unmarked statements after the fixed point % is reached, yielding only the slice rule removeUnmarkedStatements replace [statement*] S [statement] More [statement*] deconstruct not S _ [marked_statement] deconstruct not S _ [declaration] by More end rule % Rule to remove declarations not needed in the slice rule removeRedundantDeclarations replace [statement*] var X [id] ; More [statement*] deconstruct not * [id] More X by More end rule % Rule to strip all markup when we're done rule stripMarkup replace [statement] < _ [id] > S [statement] </ _ [id] > by S end ruleExample run 1:
<linux> cat sliceg1.til var n; read n; var fac; fac := 1; var sum; sum := 0; var i; i := 1; while i != n+1 do fac := fac * i; sum := sum + i; i := i + 1; end <foo>write fac;</foo> write sum; <linux> txl sliceg1.til TILbackslice.Txl TXL v10.4d (4.2.07) (c)1988-2007 Queen's University at Kingston Compiling TILbackslice.Txl ... Parsing sliceg1.til ... Transforming ... var n; read n; var fac; fac := 1; var i; i := 1; while i != n + 1 do fac := fac * i; i := i + 1; end write fac; <linux>Example run 2:
<linux> cat sliceg2.til var x; x := 0; var t; t := 0; for i := 1 to 10 do if x = 1 then t := t * i; else t := t + i; end x := 1; end <mark>write x;</mark> <linux> txl sliceg2.til TILbackslice.Txl TXL v10.4d (4.2.07) (c)1988-2007 Queen's University at Kingston Compiling TILbackslice.Txl ... Parsing sliceg2.til ... Transforming ... var x; x := 0; for i := 1 to 10 do x := 1; end write x; <linux>Example run 3:
<linux> cat sliceg6.til var lines; lines := 0; var chars; var n; read n; var eof_flag; read eof_flag; chars := n; while eof_flag do lines := lines + 1; read n; read eof_flag; chars := chars + n; end <mark>write (lines);</mark> write (chars); <linux> txl sliceg6.til TILbackslice.Txl TXL v10.4d (4.2.07) (c)1988-2007 Queen's University at Kingston Compiling TILbackslice.Txl ... Parsing sliceg6.til ... Transforming ... var lines; lines := 0; var eof_flag; read eof_flag; while eof_flag do lines := lines + 1; read eof_flag; end write (lines); <linux>-- JamesCordy - 02 Mar 2007
% TXL transformation to recognize and optimize common subexpressions % Jim Cordy, March 2007 % This program finds subexpressions that are used two or more times without % intervening changes to the variables used in it, and introduces a new % temporary variable to optimize it to a single computation. % Based on the TIL base grammar include "TIL.Grm" % Preserve comments, we're probably going to maintain the result include "TILCommentOverrides.Grm" % Override grammar to abstract compound statements redefine statement [compound_statement] | ... end redefine define compound_statement [if_statement] | [while_statement] | [for_statement] end define % Allow statements to be attributed so we don't mistake one we've % generated for one we need to process redefine statement ... | [statement] [attr 'NEW] end redefine % Main function function main replace [program] P [program] by P [optimizeSubexpressions] end function rule optimizeSubexpressions replace [statement*] S1 [statement] SS [statement*] % Don't process statements we generated deconstruct not * [attr 'NEW] S1 'NEW % What we're looking for is an expression ... deconstruct * [expression] S1 E [expression] % ... that is nontrivial ... deconstruct * [op] E _ [op] % ... and repeated deconstruct * [expression] SS E % See if we can abstract it (checks if variables assigned between) where SS [?replaceExpnCopies S1 E 'T] % If so, generate a new temporary variable name ... construct T [id] _ [unquote "temp"] [!] % ... declare it, assign it the common expression, % and replace instances of the expression with it construct NewS [statement*] 'var T; 'NEW T := E; 'NEW S1 [replaceExpn E T] SS [replaceExpnCopies S1 E T] by NewS end rule % Recursively replace copies of a given expression with a given temporary variable id, % provided the variables used in the expression are not assigned in between function replaceExpnCopies S1 [statement] E [expression] T [id] construct Eids [id*] _ [^ E] % If the previous statement did not assign any of the variables in the expression where not S1 [assigns each Eids] % Then we can continue to substitute the temporary variable for the expression % in the next statement ... replace [statement*] S [statement] SS [statement*] % ... as long as it isn't a compound statement that internally assigs one of % the variables in the expression where not all S [assignsOne Eids] [isCompoundStatement] by S [replaceExpn E T] SS [replaceExpnCopies S E T] end function % Condition function checking to see if a statement assigns a variable function assignsOne Eids [id*] match [statement] S [statement] where S [assigns each Eids] end function function assigns Id [id] match * [statement] Id := _ [expression] ; end function function isCompoundStatement match [statement] _ [compound_statement] end function rule replaceExpn E [expression] T [id] replace [expression] E by T end ruleExample run: "commonsubexpeg.til" is a meaningless little program with lots of common subexpressions, both optimizable and not.
<linux> cat commonsubexpeg.til // Silly TIL example with lots of common subexpressions var a; var b; var c; a := 1; b := a + 1; var i; i := 7; c := a + 1; i := i - c; c := b + i; for i := 1 to 10 do a := b + i; if b + i != 10 then c := b; else c := b + i; end b := b + i; end while b != 10 do a := b + i; if b + i != 10 then a := c; else c := b + i; end b := b + i; end write (i - c); <linux> txl commonsubexpeg.til TILcommonsubexp.Txl TXL v10.5 (22.9.07) (c)1988-2007 Queen's University at Kingston Compiling TILcommonsubexp.Txl ... Parsing commonsubexpeg.til ... Transforming ... // Silly TIL example with lots of common subexpressions var a; var b; var c; a := 1; var temp1; temp1 := a + 1; b := temp1; var i; i := 7; c := temp1; i := i - c; c := b + i; for i := 1 to 10 do var temp2; temp2 := b + i; a := temp2; if temp2 != 10 then c := b; else c := temp2; end b := temp2; end while b != 10 do var temp3; temp3 := b + i; a := temp3; if temp3 != 10 then a := c; else c := temp3; end b := temp3; end write (i - c); <linux>-- JamesCordy - 19 Oct 2007
% Clone detection on Tiny Imperative Language programs % Jim Cordy, October 2007 % Given a TIL program, this program finds structured statement % clones that differ only by consistent renaming, and marks them % up in the source with their clone class. The clone classes % themselves are output on the standard error stream as well. % Usage: txl program.til TILclonesrenamed.Txl > program.clones 2> program.cloneclasses % Begin with the TIL base grammar include "TIL.Grm" % Overrides to conflate all structured statements into one nonterminal type. % Putting [structured_statement] before existing statement forms makes % it the preferred parse for the statements it matches. redefine statement [structured_statement] | ... end redefine define structured_statement [if_statement] | [for_statement] | [while_statement] end define % Overrides to allow XML markup of TIL statements. redefine statement ... | [marked_statement] end redefine define marked_statement [xmltag] [NL][IN] [statement] [EX] [xmlend] [NL] end define % [SPOFF] and [SPON] temporarily disable default spacing in tags define xmltag < [SPOFF] [id] [SP] [id] = [number] > [SPON] end define define xmlend < [SPOFF] / [id] > [SPON] end define % Main program function main replace [program] P [program] % First make a table of all structured statements that are % repeated but for consistent renaming construct StructuredClones [repeat structured_statement] _ [findStructuredStatementClones P] % Now mark up all consistently renamed instances of each of them in the program % CloneNumber keeps track of the index of each one in the table as we step % through it using 'each' export CloneNumber [number] 0 by P [markCloneInstances each StructuredClones] end function % We make a table of the cloned structured statements by first making a table % of all structured statements in the program, then looking for repeats function findStructuredStatementClones P [program] % Use the extract [^] function to make a table of all structured statements in the program % and normalize them to standard renaming construct StructuredStatements [repeat structured_statement] _ [^ P] [renameStructuredStatement] % Now add each one that is repeated to the table of clones construct StructuredClones [repeat structured_statement] _ [addIfClone StructuredStatements each StructuredStatements] % Output the table to the standard error stream as a clone class table construct CloneTable [repeat statement] _ [addCloneClass 0 StructuredClones] [print] % Pass the table back to the main function replace [repeat structured_statement] % empty to begin with by StructuredClones end function function addIfClone StructuredStatements [repeat structured_statement] Stmt [structured_statement] % A structured statement is cloned if it appears twice in the table of all statements deconstruct * StructuredStatements Stmt Rest [repeat structured_statement] deconstruct * [structured_statement] Rest Stmt % If it does appear (at least) twice, add it to the table of clones replace [repeat structured_statement] StructuredClones [repeat structured_statement] % Make sure it's not already in the table deconstruct not * [structured_statement] StructuredClones Stmt by StructuredClones [. Stmt] end function % Create a readable version of the clone class table for output function addCloneClass NM1 [number] Clones [repeat structured_statement] % Index of the class in the table of clones construct N [number] NM1 [+ 1] % Get the next clone deconstruct Clones Clone [structured_statement] Rest [repeat structured_statement] % Mark up the clone as a numbered clone class replace [repeat statement] Stmts [repeat statement] construct NewStmt [statement] <clone_class class=N> Clone </clone_class> % And add it to the table to output by Stmts [. NewStmt] [addCloneClass N Rest] end function % Once we have the table of all clones, we mark up each instance of each of them % in the program with its clone class, that is, the index of it in the clone table rule markCloneInstances StructuredClone [structured_statement] % Keep track of the index of this clone in the table import CloneNumber [number] export CloneNumber CloneNumber [+ 1] % Mark up all instances of it in the program % 'skipping' avoids marking any instance twice skipping [marked_statement] replace [statement] Stmt [structured_statement] % Normalize to standard renaming for comparison construct RenamedStmt [structured_statement] Stmt [renameStructuredStatement] % If the renamed structured statement is an instance of the clone class ... deconstruct RenamedStmt StructuredClone % ... then mark it as such by <clone class=CloneNumber> Stmt </clone> end rule % Rule to normalize structured statements by consistent renaming of identifiers % to normal form (x1, x2, x3, ...) rule renameStructuredStatement % For each outer structured statement in the scope skipping [structured_statement] replace $ [structured_statement] Stmt [structured_statement] % Make a list of all of the unique identifiers in the statement construct Ids [repeat id] _ [^ Stmt] [removeDuplicateIds] % Make normalized new names of the form xN for each of them construct GenIds [repeat id] Ids [genIds 0] % Consistently replace each instance of each one by its normalized form by Stmt [$ each Ids GenIds] end rule % Utility rule - remove duplicate ids from a list rule removeDuplicateIds replace [repeat id] Id [id] Rest [repeat id] deconstruct * [id] Rest Id by Rest end rule % Utility rule - make a normalized id of the form xN for each unique id in a list function genIds NM1 [number] % For each id in the list replace [repeat id] _ [id] Rest [repeat id] % Generate the next xN id construct N [number] NM1 [+ 1] construct GenId [id] _ [+ 'x] [+ N] % Replace the id with the generated one % and recursively do the next one by GenId Rest [genIds N] end functionExample run 1 (with exact clones):
<linux> cat cloneseg1.til // Silly meaningless example with lots of exact clones var n; write "Input n please"; read n; var f; f := 2; while n != 1 do while (n / f) * f = n do write f; n := n / f; end if n = 3 then n := 2; end f := f + 1; end while (n / f) * f = n do write f; if n = 3 then n := 2; end n := n / f; end while n != 1 do while (n / f) * f = n do write f; n := n / f; if n = 3 then n := 2; end end f := f + 1; while (n / f) * f = n do write f; n := n / f; end end <linux> txl cloneseg1.til TILclonesrenamed.Txl TXL v10.5 (22.9.07) (c)1988-2007 Queen's University at Kingston Compiling TILclonesrenamed.Txl ... Parsing cloneseg1.til ... Transforming ... <clone_class class=1> while (x1 / x2) * x2 = x1 do write x2; x1 := x1 / x2; end </clone_class> <clone_class class=2> if x1 = 3 then x1 := 2; end </clone_class> var n; write "Input n please"; read n; var f; f := 2; while n != 1 do <clone class=1> while (n / f) * f = n do write f; n := n / f; end </clone> <clone class=2> if n = 3 then n := 2; end </clone> f := f + 1; end while (n / f) * f = n do write f; <clone class=2> if n = 3 then n := 2; end </clone> n := n / f; end while n != 1 do while (n / f) * f = n do write f; n := n / f; <clone class=2> if n = 3 then n := 2; end </clone> end f := f + 1; <clone class=1> while (n / f) * f = n do write f; n := n / f; end </clone> end <linux>Example run 2 (with renamed clones):
<linux> cat cloneseg2.til // Silly meaningless example with lots of renamed clones var n; write "Input n please"; read n; var f; var g; f := 2; g := 7; while n != 1 do while (n / f) * f = n do write f; n := n / f; end if f = 3 then f := 2; end f := f + 1; end while (n / f) * f = n do write f; if n = 3 then n := 2; end n := n / f; end while n != 1 do while (n / f) * f = n do write f; n := n / f; if g = 3 then g := 2; end end f := f + 1; while (g / f) * f = g do write f; g := g / f; end end <linux> txl cloneseg2.til TILclonesrenamed.Txl TXL v10.5 (22.9.07) (c)1988-2007 Queen's University at Kingston Compiling TILclonesrenamed.Txl ... Parsing cloneseg2.til ... Transforming ... <clone_class class=1> while (x1 / x2) * x2 = x1 do write x2; x1 := x1 / x2; end </clone_class> <clone_class class=2> if x1 = 3 then x1 := 2; end </clone_class> var n; write "Input n please"; read n; var f; var g; f := 2; g := 7; while n != 1 do <clone class=1> while (n / f) * f = n do write f; n := n / f; end </clone> <clone class=2> if f = 3 then f := 2; end </clone> f := f + 1; end while (n / f) * f = n do write f; <clone class=2> if n = 3 then n := 2; end </clone> n := n / f; end while n != 1 do while (n / f) * f = n do write f; n := n / f; <clone class=2> if g = 3 then g := 2; end </clone> end f := f + 1; <clone class=1> while (g / f) * f = g do write f; g := g / f; end </clone> end <linux>-- JamesCordy - 16 Oct 2007
% Constant propagation and folding for TIL % Jim Cordy, January 2008 % Given a TIL program, recognize constant assignments to variables, % and replace references to the variable with the constant (constant propagation), % then recognize and compute constant expressions (constant folding). % This program could be combined with other optimization rules such as % code motion and redundant variable elimination to further optimize the result. % 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 [propagateConstants] [foldConstantExpressions] end function % Constant propagation - find each constant assignment to a variable, % and if it is not assigned again then replace references with the constant rule propagateConstants replace [repeat statement] Var [id] := Const [literal] ; Rest [repeat statement] deconstruct not * [statement] Rest Var := _ [expression] ; deconstruct * [primary] Rest Var by Var := Const; Rest [replaceExpn Var Const] end rule rule replaceExpn Var [id] Const [literal] replace [primary] Var by Const end rule % Constant folding - find and evaluate constant expressions rule foldConstantExpressions replace [expression] E [expression] construct NewE [expression] E % Generic folding of pure constant expressions [resolveAddition] [resolveSubtraction] [resolveMultiplication] [resolveDivision] % Other special cases involving constants (examples only, could be others) [resolveAdd0] [resolveSubtract0] [resolveMultiply1Right] [resolveMultiply1Left] [resolveParentheses] % Continue until we don't find anything to fold deconstruct not NewE E by NewE end rule rule resolveAddition replace [expression] N1 [integernumber] + N2 [integernumber] by N1 [+ N2] end rule rule resolveSubtraction replace [expression] N1 [integernumber] - N2 [integernumber] by N1 [- N2] end rule rule resolveMultiplication replace [term] N1 [integernumber] * N2 [integernumber] by N1 [* N2] end rule rule resolveDivision replace [term] N1 [integernumber] / N2 [integernumber] by N1 [/ N2] end rule rule resolveParentheses replace [primary] ( N [integernumber] ) by N end rule rule resolveAdd0 replace [expression] P [primary] + 0 by P end rule rule resolveSubtract0 replace [expression] P [primary] - 0 by P end rule rule resolveMultiply1Right replace [expression] P [primary] * 1 by P end rule rule resolveMultiply1Left replace [expression] 1 * P [primary] by P end ruleExample run: "const.til" is a meaningless little program with lots of opportunities for constant propagation and folding.
<linux> cat const.til // Silly meaningless example with opportunities to fold constants 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 // This one is constant for sure! c := a + y; m := y * b; n := r * y; end <linux> txl const.til TILconst.Txl TXL v10.5 (11.12.07) (c)1988-2007 Queen's University at Kingston Compiling TILconst.Txl ... Parsing const.til ... Transforming ... // Silly meaningless example with opportunities to fold constants 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 := 1 + z; a := 3; z := 5; j := 0; while j != 100 do r := 99; d := 7; k := 8; b := j * 5; d := 6 * d; e := (x + 5) * 99; j := j + 1; end // This one is constant for sure! c := 4; m := b; n := r; end <linux>-- JamesCordy - 03 Jan 2008
% TXL transformation to move all declarations in a TIL program to the % beginning of the program, making their meaning explicit % Jim Cordy, October 2005 % Based on the TIL base grammar include "TIL.Grm" % Preserve comments, we're probably going to maintain the result include "TILCommentOverrides.Grm" % Transformation rule to move all declarations to the beginning of the program - % does it the easy obvious way, extracting them all, deleting them all, then % putting the extracted ones first. function main % This is a function transformer, so it applies only once replace [program] Program [statement*] % Use the type extractor to get all statements as a flat sequence, % then filter for declarations only construct Declarations [statement*] _ [^ Program] [removeNonDeclarations] % Make a copy of the program with all declarations removed construct ProgramSansDeclarations [statement*] Program [removeDeclarations] % The result is a program consisting of the sequence of all the % declarations concatenated with the original program without declarations by Declarations [. ProgramSansDeclarations] end function rule removeDeclarations % Rule to remove every declaration at every level from statements replace [statement*] Declaration [declaration] FollowingStatements [statement*] by FollowingStatements end rule rule removeNonDeclarations % Rule to remove all statements that are not declarations from statements replace [statement*] NonDeclaration [statement] FollowingStatements [statement*] % Check that the statement isn't a declaration deconstruct not NonDeclaration _ [declaration] % If so, take it out by FollowingStatements end ruleExample run: "vareg.til" is a meaningless little program with lots of data dependencies for demonstration purposes.
<linux> cat vareg.til var d; d := 17; var r; r := 5; var y; read y; var z; read z; while y != 0 do var x; x := y + z; var a; a := 3; var j; j := 1; var b; while j != 100 do var k; k := a + z; b := j * z; d := (y + z) * d; var e; e := (x + z) * r; j := j + 1; end var c; c := a + y; var m; m := y * b; var n; n := r * y; write n; y := y - 1; end <linux> txl vareg.til TILtoglobal.Txl TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston Compiling TILtoglobal.Txl ... Parsing vareg.til ... Transforming ... var d; var r; var y; var z; var x; var a; var j; var b; var k; var e; var c; var m; var n; d := 17; r := 5; read y; read z; while y != 0 do x := y + z; a := 3; j := 1; while j != 100 do 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; write n; y := y - 1; end <linux>
% TXL transformation to move all declarations in a TIL program to their most local location % Jim Cordy, October 2005 % Based on the TIL base grammar include "TIL.Grm" % Preserve comments, we're probably going to maintain the result include "TILCommentOverrides.Grm" % Transformation to move all declarations to their most local location - % immediately before their first use, in the innermost block they can be. % It is done as two rules - one that moves declarations across statements % that do not depend on them, and one that moves declarations inside statements % they are not used outside of. rule main % Since this rule's pattern matches its result, it has no natural termination point replace [program] Program [program] % We therefore add an explicit fixed-point guard - after each application % of the two base transformations, we check to see that something more was actually done construct NewProgram [program] Program [immediatizeDeclarations] [localizeDeclarations] deconstruct not NewProgram Program by NewProgram end rule rule immediatizeDeclarations % Move all declarations past statements that don't depend on them % This rule uses a one-pass traversal ($) since the case of two declarations in a row % has no natural fixed point for this rule replace $ [statement*] 'var V [id]; Statement [statement] MoreStatements [statement*] % We can move the declaration past a statement if the statement does % not refer to the declared variable deconstruct not * [id] Statement V by Statement 'var V; MoreStatements end rule rule localizeDeclarations % Move any declarations outside a structured statement inside it if % the statements following it do not depend on the declared variable % Again, use a one pass ($) traversal replace $ [statement*] Declaration [declaration] CompoundStatement [statement] MoreStatements [statement*] % Check that it is some kind of compound statement (one with a statement list inside) deconstruct * [statement*] CompoundStatement _ [statement*] % Check that the following statements don't depend on the declaration deconstruct * [id] Declaration V [id] deconstruct not * [id] MoreStatements V % Alright, then maybe we can move it in. This transformation uses the natural % example-base style of TXL, and thus does each kind of compound statement separately % Another solution might use agile parsing to abstract similar cases into one by CompoundStatement [injectDeclarationWhile Declaration] [injectDeclarationFor Declaration] [injectDeclarationIfThen Declaration] [injectDeclarationIfElse Declaration] MoreStatements end rule function injectDeclarationWhile Declaration [declaration] % Note that there is no legal way that the while Expn can depend on the declaration, % since there are no assignments between the declaration and the Expn replace [statement] 'while Expn [expression] 'do Statements [statement*] 'end by 'while Expn 'do Declaration Statements 'end end function function injectDeclarationFor Declaration [declaration] % Note that there is no legal way that the while Expn can depend on the declaration, % since there are no assignments between the declaration and the Expn replace [statement] 'for Id [id] := Expn1 [expression] 'to Expn2 [expression] 'do Statements [statement*] 'end by 'for Id := Expn1 'to Expn2 'do Declaration Statements 'end end function function injectDeclarationIfThen Declaration [declaration] % Note that there is no legal way that the if Expn can depend on the declaration, % since there are no assignments between the declaration and the Expn replace [statement] 'if Expn [expression] 'then ThenStatements [statement*] OptionalElse [opt else_statement] 'end deconstruct Declaration 'var V [id]; deconstruct not * [id] OptionalElse V by 'if Expn 'then Declaration ThenStatements OptionalElse 'end end function function injectDeclarationIfElse Declaration [declaration] % Note that there is no legal way that the if Expn can depend on the declaration, % since there are no assignments between the declaration and the Expn replace [statement] 'if Expn [expression] 'then ThenStatements [statement*] 'else ElseStatements [statement*] 'end deconstruct Declaration 'var V [id]; deconstruct not * [id] ThenStatements V by 'if Expn 'then ThenStatements 'else Declaration ElseStatements 'end end functionExample run: "gvareg.til" is a meaningless little program with lots of data dependencies and all global declarations for demonstration purposes.
<linux> cat gvareg.til // Meaningless example TIL program with lots of data dependencies var d; var r; var y; var z; var x; var a; var j; var b; var k; var e; var c; var m; var n; d := 17; r := 5; read y; read z; while y != 0 do x := y + z; a := 3; j := 1; while j != 100 do 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; write n; y := y - 1; end <linux> txl gvareg.til TILtolocal.Txl TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston Compiling TILtolocal.Txl ... Parsing gvareg.til ... Transforming ... // Meaningless example TIL program with lots of data dependencies var d; d := 17; var r; r := 5; var y; read y; var z; read z; while y != 0 do var x; x := y + z; var a; a := 3; var j; j := 1; var b; while j != 100 do var k; k := a + z; b := j * z; d := (y + z) * d; var e; e := (x + z) * r; j := j + 1; end var c; c := a + y; var m; m := y * b; var n; n := r * y; write n; y := y - 1; end <linux>
% Clone detection on Tiny Imperative Language programs % Jim Cordy, October 2007 % Given a TIL program, this program finds exact clones % of stuctured statements (if, while and for statements) % and outputs the program with exact clones marked up % to indicate their clone class. % Usage: txl program.til TILclonesexact.Txl > program.clones % Begin with the TIL base grammar include "TIL.Grm" % Overrides to conflate all structured statements into one nonterminal type. % Putting [structured_statement] before existing statement forms makes % it the preferred parse for the statements it matches. redefine statement [structured_statement] | ... end redefine define structured_statement [if_statement] | [for_statement] | [while_statement] end define % Overrides to allow XML markup of TIL statements. redefine statement ... | [marked_statement] end redefine define marked_statement [xmltag] [NL][IN] [statement] [EX] [xmlend] [NL] end define % [SPOFF] and [SPON] temporarily disable default spacing in tags define xmltag < [SPOFF] [id] [SP] [id] = [number] > [SPON] end define define xmlend < [SPOFF] / [id] > [SPON] end define % Main program function main replace [program] P [program] % First make a table of all repeated structured statements construct StructuredClones [repeat structured_statement] _ [findStructuredStatementClones P] % Now mark up all instances of each of them in the program % CloneNumber keeps track of the index of each one in the table as we step % through it using 'each' export CloneNumber [number] 0 by P [markCloneInstances each StructuredClones] end function % We make a table of the cloned structured statements by first making a table % of all structured statements in the program, then looking for repeats function findStructuredStatementClones P [program] % Use the extract [^] function to make a table of all structured statements in the program construct StructuredStatements [repeat structured_statement] _ [^ P] % Now add each one that is repeated to the table of clones replace [repeat structured_statement] % empty to begin with by _ [addIfClone StructuredStatements each StructuredStatements] end function function addIfClone StructuredStatements [repeat structured_statement] Stmt [structured_statement] % A structured statement is cloned if it appears twice in the table of all statements deconstruct * StructuredStatements Stmt Rest [repeat structured_statement] deconstruct * [structured_statement] Rest Stmt % If it does appear (at least) twice, add it to the table of clones replace [repeat structured_statement] StructuredClones [repeat structured_statement] % Make sure it's not already in the table deconstruct not * [structured_statement] StructuredClones Stmt by StructuredClones [. Stmt] end function % Once we have the table of all clones, we mark up each instance of each of them % in the program with its clone class, that is, the index of it in the clone table rule markCloneInstances StructuredClone [structured_statement] % Keep track of the index of this clone in the table import CloneNumber [number] export CloneNumber CloneNumber [+ 1] % Mark up all instances of it in the program % 'skipping' avoids marking any instance twice skipping [marked_statement] replace [statement] StructuredClone by <clone class=CloneNumber> StructuredClone </clone> end ruleExample run:
<linux> cat cloneseg1.til // Silly meaningless example with lots of exact clones var n; write "Input n please"; read n; var f; f := 2; while n != 1 do while (n / f) * f = n do write f; n := n / f; end if n = 3 then n := 2; end f := f + 1; end while (n / f) * f = n do write f; if n = 3 then n := 2; end n := n / f; end while n != 1 do while (n / f) * f = n do write f; n := n / f; if n = 3 then n := 2; end end f := f + 1; while (n / f) * f = n do write f; n := n / f; end end <linux> txl cloneseg1.til TILclonesexact.Txl TXL v10.5 (22.9.07) (c)1988-2007 Queen's University at Kingston Compiling TILclonesexact.Txl ... Parsing cloneseg1.til ... Transforming ... var n; write "Input n please"; read n; var f; f := 2; while n != 1 do <clone class=1> while (n / f) * f = n do write f; n := n / f; end </clone> <clone class=2> if n = 3 then n := 2; end </clone> f := f + 1; end while (n / f) * f = n do write f; <clone class=2> if n = 3 then n := 2; end </clone> n := n / f; end while n != 1 do while (n / f) * f = n do write f; n := n / f; <clone class=2> if n = 3 then n := 2; end </clone> end f := f + 1; <clone class=1> while (n / f) * f = n do write f; n := n / f; end </clone> end <linux>-- JamesCordy - 15 Oct 2007
% TXL transformation to adapt existing "declaring for" semantics TIL programs % to a proposed new semantics in which "for" control variables must be declared % Jim Cordy, October 2005 % Note: In this program all keywords of TIL are quoted in patterns and replacements - % this is not strictly necessary, but is conventional style in modern TXL programs. % Based on the TIL base grammar include "TIL.Grm" % Preserve comments, we're probably going to maintain the result include "TILCommentOverrides.Grm" % Transformation rule to correct all for loops. % Default rewrite rule semantics in TXL are compositional fixed point, % which for most transformations is the desired semantics. However, % this transformation has no syntactic compositional fixed point. % So the alternatives are either a semantically-guarded transformation, % a grammar override, or an explicit once-over traversal. % This solution uses the last of these, not because it is the best solution % but because this example gives us an opportunity to demonstrate that possibility. function main % This is a function transformer, so it applies only once unless explicitly % reapplied. The "replace *" allows it to search deeply for its pattern. % The replacement reapplies it twice to implement an explicit traversal. replace * [statement*] 'for Id [id] := Expn1 [expression] 'to Expn2 [expression] 'do Statements [statement*] 'end MoreStatements [statement*] by 'var Id; 'for Id := Expn1 'to Expn2 'do Statements [main] 'end MoreStatements [main] end functionExample run:
<linux> cat multiples.til // Test of declaring for loop in TIL // Output first 10 multiples of numbers 1 through 9 for i := 1 to 9 do for j := 1 to 10 do write i*j; end end <linux> txl multiples.til TILfordeclare.Txl TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston Compiling TILfordeclare.Txl ... Parsing multiples.til ... Transforming ... // Test of declaring for loop in TIL // Output first 10 multiples of numbers 1 through 9 var i; for i := 1 to 9 do var j; for j := 1 to 10 do write i * j; end end <linux>
% Convert Tiny Imperative Language "for" statements to "while" form % Jim Cordy, August 2005 % This program converts all "for" statements in a TIL program to % their equivalent "while" form % Some details assumed: % % - It is not clear whether TIL is scoped or not. We assume not % since there is no explicit scoping statement in the language. % % - The "for" statement of TIL is a "declaring for". % We assume this means it automatically declares its control variable. % % These assumptions can be trivially changed here if TIL changes. % Based on the TIL grammar include "TIL.grm" % Preserve comments in output include "TILCommentOverrides.Grm" % Rule to convert every "for" statement rule main % Capture each "for" statement, in its statement sequence context % so that we can replace it with multiple statements replace [statement*] 'for Id [id] := Expn1 [expression] 'to Expn2 [expression] 'do Statements [statement*] 'end MoreStatements [statement*] % Need a unique new identifier for the upper bound construct UpperId [id] Id [_ 'Upper] [!] % Construct the iterator construct IterateStatement [statement] Id := Id + 1; % Replace the whole thing by 'var Id; Id := Expn1; 'var UpperId; UpperId := (Expn2) + 1; 'while Id - UpperId 'do Statements [. IterateStatement] 'end MoreStatements end ruleExample run:
<linux> cat multiples.til // Test of declaring for loop in TIL // Output first 10 multiples of numbers 1 through 9 for i := 1 to 9 do for j := 1 to 10 do write i*j; end end <linux> txl multiples.til TILfortowhile.Txl TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston Compiling TILfortowhile.Txl ... Parsing multiples.til ... Transforming ... // Test of declaring for loop in TIL // Output first 10 multiples of numbers 1 through 9 var i; i := 1; var i_Upper1; i_Upper1 := (9) + 1; while i - i_Upper1 do var j; j := 1; var j_Upper1; j_Upper1 := (10) + 1; while j - j_Upper1 do write i * j; j := j + 1; end i := i + 1; end <linux>
% Goto elimination in TIL programs % Jim Cordy, January 2008 % Given a TIL program in an extended dialect that includes labelled statements % and goto statements, recognize and resolve while-equivalent goto structures. % Begin with the TIL base grammar include "TIL.Grm" % Preserve comments in this transformation #pragma -comment % Add labels and goto statements to TIL redefine statement ... | [labelled_statement] | [goto_statement] | [null_statement] | [comment_statement] end redefine define labelled_statement [label] ': [statement] end define define goto_statement 'goto [label] '; [NL] end define % Allow for trailing labels define null_statement [NL] end define define comment_statement [comment] [NL] end define define label [id] end define % Main program - just applies the rules for cases we know how to transform function main replace [program] P [program] by P [transformForwardWhile] [transformBackwardWhile] end function % Case 1 - structures of the form % loop: % if Cond then goto endloop; end % LoopStatements % goto loop; % endloop: % TrailingStatements rule transformForwardWhile replace [repeat statement] L0 [label] ': 'if X [expression] Op [op] Y [expression] 'then 'goto L1 [label] '; 'end Rest [repeat statement] skipping [statement] deconstruct * Rest 'goto L0 '; L1 ': Follow [statement] FinalRest [repeat statement] construct NonRest [repeat statement] Rest [truncateGoto L0 L1] by 'while X Op [invertOp] Y 'do NonRest 'end Follow FinalRest end rule function truncateGoto L0 [label] L1 [label] replace * [repeat statement] 'goto L0 '; L1 ': Follow [statement] FinalRest [repeat statement] by % nothing end function % Since TIL doesn't have a not operator, we need to invert comparisons function invertOp construct Ops [repeat op] '= '!= construct InvertOps [repeat op] '!= '= replace [op] Op [op] by Op [replaceOriginalOp Op each Ops InvertOps] end function function replaceOriginalOp OriginalOp [op] PatternOp [op] ReplacementOp [op] replace [op] OriginalOp by OriginalOp [$ PatternOp ReplacementOp] end function % Case 2 - structures of the form % loop: % LoopStatements % if Cond then goto loop; end % TrailingStatements rule transformBackwardWhile replace [repeat statement] L0 [label] ': First [statement] Rest [repeat statement] skipping [statement] deconstruct * Rest 'if C [expression] 'then 'goto L0 '; 'end FinalRest [repeat statement] construct NonRest [repeat statement] Rest [truncateIfGoto L0] construct WhileStatement [repeat statement] 'while C 'do First NonRest 'end by First NonRest [. WhileStatement] [. FinalRest] end rule function truncateIfGoto L0 [label] skipping [statement] replace * [repeat statement] 'if C [expression] 'then 'goto L0 '; 'end FinalRest [repeat statement] by % nothing end functionExample run: "gotofactors.til" is a goto-based version of the factors.til example program.
<linux> cat gotofactors.til // Factor an input number - goto version var n; var f; write "Input n please"; read n; write "The factors of n are"; f := 2; // Outer loop over potential factors factors: if n = 1 then goto endfactors; end // Inner loop over multiple instances of same factor multiples: if (n / f) * f != n then goto endmultiples; end write f; n := n / f; goto multiples; endmultiples: f := f + 1; goto factors; endfactors: <linux> txl gotofactors.til TILgotoelim.Txl TXL v10.5 (11.12.07) (c)1988-2007 Queen's University at Kingston Compiling TILgotoelim.Txl ... Parsing gotofactors.til ... Transforming ... // Factor an input number - goto version var n; var f; write "Input n please"; read n; write "The factors of n are"; f := 2; // Outer loop over potential factors while n != 1 do // Inner loop over multiple instances of same factor while (n / f) * f = n do write f; n := n / f; end f := f + 1; end <linux>
% 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 functionExample 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>
% 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 functionExample 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.
<linux> 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 <linux> 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 <linux>
% TXL transformation to remove unused declarations in a TIL program % Jim Cordy, July 2006 % Based on the TIL base grammar include "TIL.Grm" % Preserve comments, we're probably going to maintain the result include "TILCommentOverrides.Grm" % Transformation rule to remove all redundant variable declarations from a program. % If a declared variable is not mentioned by the following statements, it is not used. rule main % Find each variable declaration replace [statement*] 'var Id [id] '; FollowingStatements [statement*] % Check to see if the declared identifier does not appear in the following statements deconstruct not * [id] FollowingStatements Id % If not, the declaration is redundant so we remove it by FollowingStatements end ruleExample run:
<linux> cat redundantvareg.til // Meaningless example TIL program with some redundant declarations // (the ones with names like rr, rx, ry, rm) var d; var y; d := 17; read y; var rr; while y != 0 do var rx; var a; a := 3; var j; j := 1; while j != 100 do a := a * 2; var ry; j := j + 1; end var c; c := a + j; var n; n := c * y; write n; y := y - 1; var rm; end <linux> txl redundantvareg.til TILredundant.Txl TXL v10.4c (15.3.06) (c)1988-2006 Queen's University at Kingston Compiling TILredundant.Txl ... Parsing redundantvareg.til ... Transforming ... // Meaningless example TIL program with some redundant declarations // (the ones with names like rr, rx, ry, rm) var d; var y; d := 17; read y; while y != 0 do var a; a := 3; var j; j := 1; while j != 100 do a := a * 2; j := j + 1; end var c; c := a + j; var n; n := c * y; write n; y := y - 1; end <linux>
Fifth international conference on
Generative Programming and Component Engineering (GPCE'06)
October 22-26, 2006, Portland, Oregon
colocated with OOPSLA'06
3 spaces * Main.yourWikiName - yourEmailAddress
on
, and add the "what" and "use to..." description for the site map. Make sure to list only links that include the name of the web, e.g. Sts.Topic links.
web="all"
search: (Set to on
for hidden webs)
6 spaces * Set NAME = value
#EEEEAA
, it gets expanded to #EEEEAA
.
WEBCOPYRIGHT
before WIKIWEBMASTER
since =Copyright © 1999-2020 by the contributing authors.
webmaster@strategoxt.org
variable.
%VARIABLES%
.