code Implement several compiler optimizations.

Contents

Plan

Opt(imizer|tional)

As mentioned in class, this stage is now optional if you plan to complete the larger feature project.

The last stage is here! In this assignment, you will extend your compiler to support a general data-flow analysis framework and several optimizations implemented in this framework. It is also time to overload some favorite acronyms from the beginning of the course. DFA now means Data-Flow Analysis and CFG means Control-Flow Graph.

Basic Blocks and Control Flow Graphs

Build a control-flow graph representation of the TAC for each method. Design a package that builds a CFG for a method’s TACList. I suggest a simple representation where each CFG node is a single instruction. I provide a BasicBlock and ControlFlowGraph in the roost.ir package that you may use, modify, or replace. You will mainly need to write a transformation from TACList to ControlFlowGraph (and the reverse). To get this code, run git pull origin starter.

In the provided code, BasicBlock is restricted to hold one instruction, which is sufficient for this assignment. (Larger basic blocks avoid some computation and space overhead and facilitate more sophisticated instruction selection schemes that operate on the block level, but single-instruction blocks are a little easier to use for the analyses we are performing.) You will need to make some minor modifications, to connect these classes with your TAC representations, but otherwise they should work as is. You are of course welcome to change anything you want.

In addition to toString, the ControlFlowGraph supports generating dot files to show the control flow graph with the dotToFile method. If you generate a.dot, the following commands will convert it to a PDF showing the graph: dot -Tpdf < a.dot > a.pdf

Data-Flow Framework and Analyses

You will use a data-flow analysis framework with a general data-flow engine for forward and backward analyses to implement individual data-flow analyses on the engine. Each analysis simply describes its lattice and transfer functions. The engine uses the iterative algorithm we explored to solve the given data-flow equations on a CFG and provide access to the resulting IN and OUT values on each basic block. A later section in this document describes suggested code structure.

Data-Flow Framework

The provided code includes much of the general data-flow support you need to get started. As with basic blocks and control flow graphs, you may need to make some minor changes to connect these implementations with your compiler. As always, feel free to replace anything.

The provided roost.dataflow.Dataflow defines the general behavior of all data-flow analyses in terms of the data-flow framework parts we have studied in tutorials.

/**
  * Base class for data-flow analyses.
  *
  * @param direction: Direction of the dataflow analysis - Forward or Backward
  * @tparam T: Type of dataflow values.
  * @param boundary: Initial value for out[enter] or in[exit]
  * @param top: Top value of the lattice.
  * @param transfer: Transfer function.
  * @param meet: Meet operator as a 2-argument function.
  * @param equivalent: Function to judge equivalence of two dataflow values.
  */
class Dataflow[T](direction: Direction,
                  boundary: T,
                  top: T,
                  transfer: (BasicBlock, T) => T,
                  meet: (T, T) => T,
                  equivalent: (T, T) => Boolean) {
  /**
    * Run this dataflow analysis on the given CFG and return the result.
    *
    * @param cfg: Control flow graph to analyze.
    * @return: The analysis result as a DataflowResult.
    */
  def solve(cfg: ControlFlowGraph): DataflowResult[T]
}

/**
  * Captures the results of a dataflow analysis as named parts.
  *
  * @param cfg: Control Flow Graph on which the analysis was performed.
  * @param in: Maps each basic block to its IN value.
  * @param out: Maps each basic block to its OUT value.
  * @tparam T: The type of dataflow values.
  */
case class DataflowResult[T](cfg: ControlFlowGraph, in: Map[BasicBlock, T], out: Map[BasicBlock, T])

To implement a specific analysis, you can extend Dataflow with a Scala object, defining the various components of the data-flow framework, as in this example for unreachable code (code that follows a return):

object ReachableAnalysis extends Dataflow[Boolean](
  // This is a forward analysis.
  Forward,
  
  // Dataflow values are true (reachable), false (unreachable).
  // The boundary value (OUT[enter]) is true, i.e., reachable.
  true,
  
  // The top value in the lattice is false (unreachable).
  // Initially, all other OUTs will hold this value.
  false,
  
  // The transfer function is the identity function.
  // THIS ASSUMES that TAC returns have a control-flow edge to the exit block.
  (_, value) => value,
  
  // The meet operator is OR. If any predecessor is reachable, this block is reachable.
  (v1, v2) => v1 || v2,
  
  // Equality of dataflow values trivial for this analysis.
  (v1, v2) => v1 == v2
)

This analysis (and an example driver for it) are provided in roost.dataflow.ReachableAnalysis.

Your analyses will be much more interesting than this one. You likely will want to define some functions (e.g., the transfer function) out-of-line instead of simply as an anonymous function like above. Scala supports first-class functions.

Make reasonable design choices about how to represent data-flow facts. Feel free to use scala.collection classes wherever possible. Clarity of design and ease of implementation should be the primary motivation for any initial design choice.

Data-Flow Analyses

Implement the following analyses using the framework:

  • Live Variables Analysis: Compute the variables that may be live at each program point.
  • Reaching Copies: compute the definitions generated by Copy instructions that always reach each program point.
  • At least one of:
    • Constant Folding Analysis: determine variables whose values are constant at each program point. (Hint: data-flow values are maps from variables that hold constants to their constant values.)
    • Available Expressions: compute the expressions available at each program point. (If you implement this analysis, please see the note at the end of this document about case classes and equality.)

Optimizations

Use the results of the analyses you implemented to perform the following optimizations:

  • Dead Code Elimination (DCE): Removes code that updates variables whose values are not used in any executions. This optimization will use the results from the Live Variables analysis.
  • Copy Propagation (CP): Use the results from the reaching copies analysis to perform copy propagation.
  • Depending on which analyses you implemented, at least one of:
    • Constant Folding (CF): Uses the results from constant folding analysis and replaces each constant expression with the computed constant. (The Dragon book describes this optimization in detail.)

    • Common Subexpression Elimination (CSE): Reuses expressions already computed in the program. Here you will use the information computed with the Available Expressions analysis. If an expression is available before an instruction that re-computes that expression, replace the computation by the variable holding the result of that expression. If there is no such variable, create a temporary variable to store the result of the expression at the site where the expression is initially computed.

      Common subexpression elimination should also remove redundant run-time checks such as array bounds checks or null pointer checks. (Earlier, we may cast redundant null-check elimination as a distinct analysis and optimization. This works, but CSE can consider null checks or array bounds checks as “expressions” that can be removed if always “available” and provide a general way to eliminate some such checks.)

      Note that your CSE implementation will find only syntactically equivalent expressions.

To improve the effectiveness of your optimizations, try composing them in different orders and repeating the composed analyses. Each of these individual optimizations often creates opportunities for the others. (In the Tiny compiler, we even computed a fixed point over CF, CP, and DCE. You could think or experiment to determine whether this is reasonable here.)

Optimization Code Structure

A simple framework for optimizations is sketched in roost.opt.Optimization, with an example in roost.opt.UnreachableCodeElimination. This is the provided code you are most likely to reorganize or replace.

The optimize methods return Unit, but you can change them to return a Boolean indicating whether the TAC changed. While not required, this allows you to provide a --fix-opt command-line option that iteratively applies all optimizations over and over again until no additional changes happen (or a fixed upper bound on the number of iterations is reached).

Command Line Interface

In addition to the options from the previous assignments, your compiler should support the -O/--opt command-line option, which accepts a comma-separated list of optimization keys drawn from the following set:

  • dce for dead code elimination;
  • cf for constant folding;
  • cse for common subexpression elimination;
  • cp for copy propagaion; and
  • any others you implement.

Note: using a scopt option of Seq[String] may work well.

The compiler will perform the optimizations in the order they occur on the command line. The above arguments may appear multiple times in the same command line — in that case the compiler will execute them multiple times, in the specified order. The compiler should only perform the analyses necessary for the optimizations requested.

For example, the command line --opt cf,cp,dce,cse,dce would run 5 optimization passes. Repeating optimizations is legal.

Additionally:

  • The compiler should support the option --show-dataflow that causes it to show the data-flow facts computed computed for each program point by each analysis pass in the --opt list, in order, and clearly labeled.
  • The --show-ir option should cause the compiler to show the TAC for each function before any optimizations, and (if an --opt list is given) after each optimization pass, in order, and clearly labeled.

Extensions

If you are looking for more fun or starting points to explore a feature project on optimization, many more optimizations are possible in your framework. Talk to me.

Scala Case Classes, Equality, and Hashing.

By default, Scala uses structural equality for == tests on case classes. That is, two distinct objects of a case class will be considered equal if all of their fields are equal. Thus, the following prints true, even though x and y are distinct objects.

case class TACNot(dst: TACOperand, src: TACOperand) extends TACInstr

// ...

val x = TACNot(t1, t2)
val y = TACNot(t1, t2)

println(x == y) // prints true.

If you are storing TAC instructions in a set, searching for them in a list, or creating a map where the domain is TAC instructions, you may not be able to distinguish between two occurences of the same instruction. So, if the TAC instruction for t1 = !t2 appears in multiple places in a TAC list, the standard Scala collections implementations will consider them all equal to each other.

This will potentially be an issue for analyses like CSE, for which you may choose to construct sets of TAC instructions that compute the same expression. In such a case, you will likely want to use reference equality so that you can keep track of different occurences of the same instruction. To switch to reference equality exclusive (not necessarily recommended), add the following to your TACInstr base class:

abstract class TACInstr {
  override def equals(o: Any) = { 
    o.isinstanceOf[AnyRef] && this eq o.asInstanceOf[AnyRef] 
  }
}

The function eq is a pointer equality test. With this extension, the above test x == y yields false.

Also, objects considered equal must always have the same hash code. Whenever you add your own .equals method, you must ensure that hashCode is properly defined. For example, the following class ignores the y field in the equals method:

case class Point(x: Int, y: Int) {
  override def equals(o: Any) = {
    o.isinstanceOf[Point] && (x == o.asInstanceOf[Point].x)
  }
}

val x = Point(1,2)
val y = Point(1,3)
val set = new HashSet(x,y)

The set will contain both points, however, even though they are considered equal, because they hash to different values. So, you must add a hashCode method to reflect the notion of equality you are using:

case class Point(x: Int, y: Int) {
  override def equals(o: Any) = { 
    o.isinstanceOf[Point] && (x == o.asInstanceOf[Point].x) 
  }
  override def hashCode() = { x }
}

val x = Point(1,2)
val y = Point(1,3)
val set = new HashSet(x,y)