PT Course
Home
Education Page
Description
Schedule
Slides
Literature
Lab
Assignments
Software
Resources
Subversion Server
Stratego/XT Manual
Stratego Library
Dryad Library
Java Syntax
Stratego/Java Syntax
JLS
JVM: Class files
Contact
Mailing List
IRC
Eelco Visser
Martin Bravenboer
Center for ST
Home
Master Program
Center
Home
Courses
People
Projects
Page
Edit Page
Rename Page
Attach File
Printable
Wiki Source
More ...
Web
Recent Changes
Notify Service
News
Page Index
Search
More ...
Wiki
About TWiki
Text Formatting
Registration
Change Password
Reset Password
Users
Groups
Log In
or
Register
Copy Propagation
Pt
---++ Introduction The goal of this assignment is to prepare the constant propagation implementation for the term rewrite system that is the target of the partial evaluator we are developing. A succesful partial evaluation of this term rewrite system (and many other Tiger program) requires the propagation of records with some variables. This kind of propagation is a more complex example of copy propagation. Consider this Tiger program: <verbatim> let type intlist = {hd: int, tl: intlist} var tail : intlist := nil var list : intlist := intlist{ hd = x, tl = tail} in printint(list.hd) end </verbatim> When we are just allowing propagation of constant records we cannot do many useful things on this program because the value of =x= is not known. However, if we would propagate the record including the variable =x=, we can reduce this program to: <verbatim> let type intlist = {hd : int, tl : intlist} in printint(x) end </verbatim> Quite an improvement! We will extend the modules in the package we've been working on in the ConstantRecordPropagation assignment. There is no need to install a new package. You might want to backup your work of the last time ;) . ---++ Copy Propagation The propagation of records with variables is more complex than the propagation of constant records. The difficulties are comparable to the copy propagation of just variables, so let's consider this first. <verbatim> let var x := 1 var y := z in x + y * 3 end </verbatim> In this piece of code we can propagate the constant value of variable =x= with constant propagation. Since the variable =y= has the same value as the variable =z= we can also replace the variable =y= in the expression with the variable =z= with copy propagation of this variable. This will result in: <verbatim> let var x := 1 var y := z in 1 + z * 3 end </verbatim> After dead code elimination the result will be: <verbatim> 1 + z * 3 </verbatim> Let's now take a look at this piece of code: <verbatim> let var x := 1 var y := z in z := 5 ; x + y * 3 end </verbatim> We cannot replace the use of =y= with =z= in this case because the variable =z= gets an other value in the assignment. The assignment to =z= will eliminiate all propagations that are _associated_ to =z= because =z= occurs in the value that is being propagated. When copy propagating records with variables the same problem occurs. In the following tiny adaption of the program in the introduction we cannot propagate the right hand side of the =list= variable because of the assignment to =x=. <verbatim> let type intlist = {hd: int, tl: intlist} var tail : intlist := nil var list : intlist := intlist{ hd = x, tl = tail} in x := 3 ; printint(list.hd) end </verbatim> Copy propagation is very similar to constant propagation, that is, an assignment <verbatim> x := y </verbatim> of a _variable_ to a variable induces a dynamic rule, which replaces occurrences of =x= by =y=: <verbatim> ?|[ x := y ]| ; rules( CopyProp : |[ x ]| -> |[ y ]| ) </verbatim> However, the difference are the cancelation rules for these dynamic rules. Not only an assignment to the variable on the left-hand side, but also an assignment to the variable on the right-hand side should cancel the rule. For example, in the sequnce <verbatim> x := y; y := z + 3; z := x + 4 </verbatim> the second occurrence of =x= should _not_ be replaced with =y= since =y= has been assigned a new value. For this purpose, the copy propagation strategy maintains an additional dynamic rule =Assoc= which maps a variable to the list of variables that it is replacing. Thus, in the example above, after the first assignment we have <verbatim> <CopyProp> Var("x") => Var("y") <Assoc> Var("y") => [Var("x")] </verbatim> When encountering an assignment all rules for the associated variables of the left-hand side should can thus be canceled. ---++ Implementation In this assignment you will implement copy propagation, including propagation of records with variables. First of all you should extend the constant propagation with copy propagation for simple variables. This transformation has already been implemented in the Tiger Compiler and is very similar to the constant propagation implementation. You can download the module and use it as much as you want in your implementation. * [[%ATTACHURL%/Tiger-CopyProp.str][Tiger-CopyProp.str]] After you have included the copy propagation of variables you are going to extend your code to copy propagate records with variables. Make sure the copy and constant propagation is working before you start with the copy propagation of records. It is a good idea to have _one_ dynamic rule, say =PropValue= which is responsible for propagating both constants _and_ `copies', instead of maintaining the =ConstProp= and =CopyProp= rules. ---++ Tips and tricks Notice that the traversals of both implementations are almost identical, but be careful: there are some differences! The last =strategies= section in the =Tiger-PE-ConstProp= module contains strategies you really shouldn't understand. They implement some operations on dynamic rules that are required for data-flow optimizations like constant propagation. You should just copy the equivalent sections from the =Tiger-CopyProp= to your implementation. You might want to create a separate module with the three sections. This will clean up the =Tiger-PE-ConstProp= module a little bit. Study the differences between the strategy defintions =restore=, =isect=, =updated=, =save= and =clean= in the constant and copy propagation modules. How are you going to merge these strategies? In the =Tiger-CopyProp= module the dynamic rule =Assoc= produces a list of variables given a variable. In this piece of code: <verbatim> ; <Assoc <+ ![]> Var(y) => asc-list ; rules(Assoc: Var(y) -> [Var(x)| asc-list]) </verbatim> the =Var(x)= is included in this list for =Var(y)=. To extend the list of this =Var(y)=, the =Assoc= rule is first applied to produce the old list and a new dynamic rule is generated that produces the new list. In this way you can collect terms in a dynamic rule during a traversal. Compile and test often! Working for a long time without compiling or running tests will make it difficult to find the cause of a problem or failure. If you want to run a slightly different test, just create a new file and do not modify one file every time you want another test. You can find the sources of the modules of the Stratego.StrategoStandardLibrary (SSL) in =/usr/share/ssl/doc= . If you cannot find a strategy that you would expect to be in a library, just do a grep in this directory or ask someone. -- Main.MartinBravenboer - 07 Feb 2003