Assignment Data Flow Transformation

Introduction

In this assignment you will implement intra-procedural constant propagation and intra-procedural dead code elimination for a subset of Java. The goal is to better understand flow-sensitive data-flow transformations.

Reuse

As you have already seen in the lectures, constant propagation is very similar to interpretation. The main difference is that not all variables have constant values. So instead of only producing a single value, constant propagation should produce a program in which constant values have been folded and propagated where possible. Obviously you should be able to reuse a great deal from the interpreter you developed for the previous assignment. Also have a look at the constant propagation strategy for TIL in Chapter 6 of the examples in the manual.

Look at the same chapter to get inspiration for the dead code elimination strategy you should develop.

Restrictions

The transformations you will be developing are intra-procedural, which entails that they consider a single method at a time. In Java this means that assignments to fields and uses of fields should be considered as unknowns.

• Values assigned to fields cannot be propagated past method calls, since method calls may assign to these fields
• Assignments to fields are never dead since the object may be alive

Furthermore, you can may ignore control-flow constructs such as break, continue, and exceptions.

Testing

As usual, create unit tests for both transformations.

Setup

The following Stratego module is the basis for a constant propagation transformation transformation system. It reads in the compilation units declared on the command-line, parses them, applies propconst-compilation-unit to each, and then pretty-prints them. You can use the same setup as the basis for dead code elimination.

module java-propconst
imports libdryad
strategies

  main-java-propconst =
    xtc-multi-io-wrap(
      observables-wrap(propconst-java)
    )

  propconst-java =
    process-input-sources
    ; map(
        get-ast
        ; propconst-compilation-unit
        ; write-to
        ; xtc-transform(!"pp-java",pass-verbose)
      )

  /**
   * Loads Java source files in the Dryad repository.
   *
   * @type List(FILE) -> List(CompilationUnit Object)
   */
  process-input-sources =
    parse-java
    ; map(define-compilation-unit)
    ; dryad-reclassify
    ; map(dryad-type-checker)

strategies

  propconst-compilation-unit =
    id // your transformation here

The following make-propconst script can be used to compile the program.

#! /bin/sh

XTCFLAGS="$(pkg-config --variable=strcxtcflags dryad)"
STRCFLAGS="$(pkg-config --variable=strcflags dryad)"

strc -i java-propconst.str -m main-java-propconst $XTCFLAGS $STRCFLAGS --format-check -1

Application of java-propconst to one or more Java compilation units then proceeds as follows:

./java-propconst -i Factorial.java

This will print the transformed code to stdout.

The Transformations

Once you succeed in compiling and testing the template module above you can start implementing the constant propagation transformation and call it in the definition o propconst-compilation-unit. The transformation should traverse the code of the compilation unit until it finds method declarations. The bodies of these declarations should be transformed.

Template Testsuite

You can use the following template for your testsuite. The testing strategies allow you to test an arbitrary statement in your output program by labeling it with result:.

module test-java-propconst
imports java-propconst

strategies

  main-test-java-propconst =
    option-wrap(general-options,
      test-suite(!"WK10 assignment",
        observables-wrap(
          simple-tests
        )
      )
    )
    
strategies

  simple-tests = id
  ; test-compilation-unit(|
      "Evaluation to simple constant value"
    , "class Foo { public void foo() { int x = 3; result : x * x;} }"
    , ExprStm(Lit(Deci("9")))
    )
  ; test-compilation-unit(
     not(oncetd(?ExprName(Id("x"))))
    | "Evaluation to simple constant value"
    , "class Foo { public void foo() { int x = 3; int y; result : x * y;} }"
    )
  ; test-compilation-unit(
     oncetd(?ExprName(Id("y")))
    | "Evaluation to simple constant value"
    , "class Foo { public void foo() { int x = 3; int y; result : x * y;} }"
    )
    

/**
 * Testing utils
 */
strategies

  test-compilation-unit(check |msg, src) =
    apply-and-check(!msg
    , propconst-compilation-unit
      ; get-test-result             
    , <process-input> src   
    , check
    )
    
  test-compilation-unit(|msg, src, result) =
    apply-test(!msg
    , propconst-compilation-unit
      ; get-test-result
    , <process-input> src   
    , !result
    )

  get-test-result =
    oncetd(?Labeled(Id("result"), stm))
    ; !stm

  process-input =
    print-to
    ; ![<id>]
    ; parse-java
    ; map(define-compilation-unit)
    ; dryad-reclassify
    ; map(dryad-type-checker) 
    ; last
    ; get-ast

Script for compilation of the testsuite:

#! /bin/sh

# Add the Nix profile to the search path of pkg-config
export PKG_CONFIG_PATH=$HOME/.nix-profile/lib/pkgconfig:$PKG_CONFIG_PATH

XTCFLAGS="$(pkg-config --variable=strcxtcflags dryad)"
STRCFLAGS="$(pkg-config --variable=strcflags dryad)"

strc -i test-java-propconst.str -m main-test-java-propconst $XTCFLAGS $STRCFLAGS --format-check -1

Submission

Submit the Stratego modules along with any scripts and samples you have developed for building and testing.