Assignment Dependent Dynamic Rules

Introduction

The purpose of this assignment is to make yourself more familiar with the advanced dynamic rule concepts of scope labels and rule dependencies.

In this assignment you will:

1. Extend the constant propagation to
   1. propagate constant records
   2. evaluate a field access of a constant record
   3. propagate constant array indexes
   4. improve constant propagation after constant for loops
2. Extend the copy propagation to
   1. propagate records that contain variables

All the exercises take just a few lines of code: the main job is to fully understand the dynamic rules constructs that are used. If you need more code for an exercise, then you are doing something wrong.

Template

In the template archive, you will find a tiger-propagate.str module. This module implements a complete Tiger source to source transformation (i.e. you can apply it to a Tiger source file and it will produce a Tiger source file). The template file implements constant propagation and copy propagation, which have been introduced in the lecture on dependent dynamic rewrite rules.

tiger-propagate.str imports some evaluation rules from Tiger:

• Eval-Conditional
• Eval-Operator
• Eval-Primitive
• Eval-Iteration

Subset

In this assignment we assume a subset of Tiger without function declarations.

(A1) Constant Record Propagation

Extend the constant propagation with propagation of constant records.

Example

Invoking your solution on the Tiger program

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

should for example result in

printint(13)

Tips

Note that tiger-propagate has some useful switches for debugging: --dead off will ommit the dead code elimination, --ensugar off will not ensugar and --pp off will not pretty print the Tiger AST.

Note that a field access on a constant record is not allowed in Tiger. You will have to implement the evaluation of field accesses before you can run the output of your tool with run-tiger .

(A2) Evaluate Field Access of Constant Record

To make the constant propagation useful, you need to evaluate the field access on constant records.

Notice that a field access on a constant record is not allowed in Tiger. You will have to implement the evaluation of field accesses before you can run the output of your tool with run-tiger .

(B1) Copy Propagation for Records

Implement copy propagation of records that contain variables.

Example

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:

printint(x)

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.

When copy propagating records with variables the same problem dependency 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

(A3) Constant Propagation for Arrays

Implement constant propagation of entries of one-dimensional arrays.

We assume that there are no aliases (i.e. different variables that point to the same array).

Example

If an entry of an array is constant, then it can be propagated. For example, after the assignment

x[4] := 5

All uses of x[4] can be replaced by 5. Of course, there are some tricky dependency issues: an assignment to the array variable makes all propagation rules for this array obsolete. The same holds for an assignment that uses an unknown index.

These issues, and the possible propagations, are illustrated in the following program:

let type intarray = array of int
    var x : intarray := intarray [10] of 0
    var z : int
 in z := 4
  ; x[3] := z
  ; printint(x[3])

  ; x := intarray [10] of 1
  ; printint(x[3])

  ; x[3] := z
  ; printint(x[3])

  ; x[i] := 5

  ; printint(x[3])
end

let var x : intarray := intarray[10] of 0
    var z : int
 in z := 4;
    x[3] := 4;
    printint(4);

    x := intarray[10] of 1;
    printint(x[3]);

    x[3] := 4;
    printint(4);

    x[i] := 5;
    printint(x[3])
end

(A4) Improve Constant Propagation after Constant For Loops

Constant propagation of array entries is not really useful if you cannot propagate constants assigned to array entries in a loop.

For example,

let type intarray = array of int
    var xs : intarray := array [10] of 0
    var sum : int := 0
 in xs[0] := 1

  ; for i := 1 to 10 do
      xs[i] := xs[i -1] * 2

  ; printint(xs[10])

  ; for i := 0 to 10 do
      sum := sum + xs[i]

  ; printint(sum)
end

In this code nothing can be propagated because all assignments occur in loops. First, make sure that you understand how this works in the current implementation of constant propagation of for loops.

We can improve the propagation of constant loops in two ways: by unrolling the code loop (duplicating the code) or virtually unrolling them at compile-time by applying the constant propagator to each iteration. Implement the second option in your constant propagator.

In this way, the much more constants can be propagated, leading to a compile-time calculation of the sum.

let type intarray = array of int
    var xs : intarray := array[10] of 0
    var sum : int := 0
 in xs[0] := 1;

    for i := 1 to 10 do
      xs[i] := 2 * xs[i + -1];

    printint(1024);

    for i := 0 to 10 do
      sum := sum + xs[i];

    printint(2047)
end

(You need to turn dead code elimination off in this example: for some reason the type declaration is removed by the dead declaration eliminator).

The loops are no longer necessary, which dead code elimination could handle (this is not part of the assignment).