Assignment 1: Basic Block Death

Well, maybe I should call this project "Kcolb Cisab" -- because it's mostly about backwards stuff? Nah. Too silly.

Starting with your (or my sample solution TGZ file) basic block optimizer, you're now going to add removal of dead stores and other dead operations.

Dead Operation Elimination

Dead operation elimination is a classical backward-flow problem -- however, it is slightly easier to solve it using a forward pass and a backward pass. The forward pass incrementally tracks how many times each tuple has been referenced; the backward pass then simply deletes the unreferenced tuples. Notice that the forward portion of the dead code elimination procedure is easily embedded within the incremental (forward) optimization code you have have already written.

The backward part done incrementally-forward is:

/* set initial reference counts (forward) */
for (t is each tuple generated in forward order) {
  switch (opcode of t) {
  case ST, STX, KILL:
    if (there is an available store with a matching
        subscript value and no ambiguously aliased
	intervening loads or stores) {
      set reference count of that store to 0;
    }
    set reference count of t to 1;
    break;
  case LAB:
    set reference count of t to 1;
    break;
  case SEL:
    if (select is conditional) {
      increment reference count of tested tuple;
    }
    set reference count of t to 1;
    break;
  default:
    increment reference counts of all tuples
     used as arguments to tuple t;
    set reference count of t to 0;
  }
}

That doesn't sound too bad, but that first if statement is a little scary. For example, consider a sequence like:

a[i]=1;
b=a[j];
a[i]=2;

Is the store a[i]=1 dead? Hint: no!

The full backward pass is:

/* remove dead code and propagate death (backward) */
for (b = each basic block) {
  for (t is each tuple within b, scanning backward) {
    if (t has a reference count of 0) {
      decrement reference counts of all tuples
       referenced as arguments to tuple t;
      delete tuple t;
    }
  }
}

Note that you really don't have to keep tuples around for more than one basic block at a time. All the end-of-block processing can happen as soon as the end of a block is detected.

Due Date

The due date for this assignment is 11:59PM March 22, 2021. You may submit as many times as you wish, but only the last submission that you make before the final deadline will be counted toward your course grade.

Submission Procedure

For each project, you will be submitting a tarball (i.e., a file with the name ending in .tar or .tgz) that contains all things relevant to your work on the project. Minimally, each project tarball includes the source code for the project and a semi-formal "implementors notes" document as a PDF named notes.pdf. It also may include test cases, sample output, a make file, etc., but should not include any files that are built by your Makefile (e.g., no binary executables). Make it very clear in your implementor's notes exactly what each file is.

Submit your tarball below. The file can be either an ordinary .tar file created using tar cvf file.tar yourprojectfiles or a compressed .tgz file file created using tar zcvf file.tgz yourprojectfiles. Be careful about using * as a shorthand in listing yourprojectfiles on the command line, because if the output tar file is listed in the expansion, the result can be an infinite file (which is not ok).