Introduction

In this project you will implement a dataflow analysis framework, and then you will use your framework to implement several analyses and optimizations.

Dataflow Analysis Framework

First, you will implement an intra-procedural dataflow analysis framework.

Input

To run an analysis your framework will need to take the following as input:
  1. The lattice
  2. Flow functions
  3. The information to use for the beginning of the function
  4. A representation of the program

Output

Your framework should compute one piece of information (an element of the lattice) for the beginning of each basic block, and one piece of information for the beginning of each instruction.

Algorithm

Your framework will run a forward optimistic iterative dataflow analysis that computes a piece of information (an element of the lattice) at the beginning of each instruction. In particular, your framework should initialize all information to bottom, except for the information at the beginning of the function, which is initialized to the values provided by the programmer for that purpose. Then your framework should run an worklist algorithm to find a fixed-point solution to the provided flow functions.

Note that in class we stored one piece of information for each edge in the CFG. There are two conceptual differences between what we did in class, and how LLVM is setup: (1) the CFG in LLVM is based on basic blocks and (2) in LLVM there is no explicit representation of edges. Because of this, the best way to store information while doing your fixed point computation is to store one piece of information for the beginning of each basic block. However, your framework should not only return the information at the beginning of each basic block, but also the information at the beginning of each instruction.

Inferface Design

From a Software Engineering point of view, there are many ways to design the interface that your framework will provide to clients. This flexibility is intended: you will have to think carefully to create an interface that is simple, clear, easy-to-use and very well documented. If you design your interface well to begin with, you will be able to work on the implementation of your framework and the clients of the framework in parallel. To guide you in your interface design, you will be required to present your interface and discuss it with the instructor in a short meeting on Friday May 9th.

Clients of your Dataflow Analysis Framework

You will now implement several analyses in your framework, and several optimizations that will uses the results to perform some transformations.

Analysis Use of Analysis Results
Constant Propagation Optimization: Constant Folding, Branch Folding
Available Expressions Optimization: Common Sub-expression Elminiation
Range Analysis Bug finder: Warn programmer if can't show array access in bounds
Intra-Procedural Pointer Analysis Catalyst: Improve all other analyses using this information

Deliverables

Write a ~10 page report describing your design and implementation. This is an open-ended project, so there isn't a single format we require, but here is a (non-exhaustive) list of guidelines:

Finally, submit via email a cse231-proj2.turnin.tar.gz archive that contains:

  1. Your project report, report.pdf.
  2. A MEMBERS file that lists your group members in the same format as in Project 1.
  3. Your benchmark suite.
  4. The source code for your implementation. Do not submit the entire LLVM source, only submit the files you have added/modified. If you have added or modified any files outside of the llvm/src/lib/CSE231 directory we have provided, list their locations in a file called MANIFEST. If your code requires special build instructions, include a file BUILD_INSTRUCTIONS that lists those instructions.