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:

  let type intlist = {hd: int, tl: intlist}
  
      var tail : intlist := nil
      var list : intlist := intlist{ hd = x, tl = tail}
  
   in printint(list.hd)
  end

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:

  let type intlist = {hd : int, tl : intlist}
  in printint(x)
  end

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.

  let var x := 1
      var y := z
   in x + y * 3
  end

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:

  let var x := 1
      var y := z
   in 1 + z * 3
  end

After dead code elimination the result will be:

  1 + z * 3

Let's now take a look at this piece of code:

  let var x := 1
      var y := z
   in z := 5
    ; x + y * 3
  end

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.

  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

Copy propagation is very similar to constant propagation, that is, an assignment

  x := y

of a variable to a variable induces a dynamic rule, which replaces occurrences of x by y:

  ?|[ x := y ]|
  ; rules(
      CopyProp : |[ x ]| -> |[ y ]|
    )

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

  x := y;
  y := z + 3;
  z := x + 4

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

  <CopyProp> Var("x") => Var("y")
  <Assoc> Var("y") => [Var("x")]

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.

• 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:

  ; <Assoc <+ ![]> Var(y) => asc-list
  ; rules(Assoc: Var(y) -> [Var(x)| asc-list])

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

-- MartinBravenboer - 07 Feb 2003