Copy Propagation

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