Project 8: Optimizations

Description

This project will put the final touches on the Good language for this course. It will consist of two main pieces:

  1. You will optimize the Bad Code generated internally in your compiler.
  2. You will optimize register usage during your conversion from intermediate code to Ugly Code.

As with previous projects, your program must have the "generate_bad_code_from_string" function and the "generate_ugly_code_from_string" function. However, you need to add a new boolean parameter to each function, named optimize_mode. If optimized_mode is True, you should perform the optimizations described in this project. If it is False, you should not perform any optimizations (same output as Project 7).

Note: You should only do the optimizations listed here. Use of interpretation (as opposed to the compilation optimization techniques described below) will be considered grounds for a zero on this Project. Please ask if the above doesn't make sense.

Intermediate Code Optimizations

You must implement a set of simple optimizations on your intermediate code, as described below. You do not have to use these exact techniques, but they are the ones I recommend for a straight-forward implementation.

  1. Break your intermediate code into Simple Blocks. The first block should begin at the first line of your code. After that, a new block should begin after each label and after each conditional and unconditional jump. To implement this feature, I recommend tagging each instruction with a "block ID". Start at zero and increment the block ID every time a new block begins.
  2. Determine which variables are local to a single block. To do this, scan through your intermediate code again, this time tracking three pieces of information about each variable: the first line where it is used, the last line where it is used, and the total number of lines on which it is used. If the first and last line are in the same block, that means the variable is local to a single block (we will use some of the other information later). You can also mark variables as SSA (Static Single Assignment) if they are set only on their first occurrence.
  3. Build an optimization loop. Before the loop, create a Boolean variable called something like "progress" and default it to true. At the beginning of the look set progress=False. Each time you perform a successful optimization set progress to true again so that the loop goes through one more iteration. The loop will end only once we're no longer able to successfully apply any optimizations.
    runs_faster = True
    while runs_faster:
        runs_faster = False
        if can_do_optimization:
            # Do optimization
            runs_faster = True
    
  4. The next set of optimizations should all be implemented inside the optimization loop:

  5. Dead-code elimination. If a copy or mathematical instruction writes its result to a variable that is never used anywhere else (i.e., this is the only line that this variable is found on.), you can remove this line of code.
  6. Constant propagation. If a val_copy is setting an SSA variable to a constant value, we can change all subsequent uses of that variable to the constant value AND remove the val_copy.
  7. Copy propagation. If we are using val_copy or ar_copy to copy the last use of a local variable to the first use of another local variable, we can combine these variables into one.
  8. Algebraic Simplification and Constant Folding. If we are doing math or tests with a known outcome, change it to val_copy. For example:

    add 5 7 s3     -> val_copy 12 s3
    div 27 4 s10   ->  val_copy 6 s10
    sub 22 10 s20  ->  val_copy 12 s20
    mult s5 0 s6   ->  val_copy 0 s6
    mult 1 s5 s6   ->  val_copy s5 s6
    sub s9 0 s11   ->  val_copy s9 s11
    test_less 5 10 s1  ->  val_copy 1 s1
    test_lte  2 1 s19  ->  val_copy 0 s19
    

    Make sure that if ever you change an instruction so that a variable is no longer used, you at least update the count of the number of times that variable is used.

Other possible optimizations include: removing unneeded jumps and not backing up unneeded temporary variables to the stack.

Technically, you may not need to implement all of these optimizations in order to achieve the improvements necessary for a perfect score on this project. I do recommend looking at the intermediate code that your program is producing and thinking about what optimizations you would be able to perform by hand. This will give you an idea about where your time might be best spent.

Register Allocation Optimizations

Accessing memory can take 100 times as long as using a register, so making better use of registers is an area ripe for optimization. The Intermediate code optimizations described above will remove instructions entirely, so we don't have to worry about the loads or stores associated with them, but for the remaining instructions we can be more careful with how we use registers. In the case of Ugly Lang, the instructions load, store, and mem_copy will each take 100 CPU cycles, while all others take 1.

Ideally, you should construct a control-flow graph in order to detect which simple blocks of code can connect to which other simple blocks, and thus isolate everywhere that particular variables are "live". Using this information, you can combine variables and optimally map each to registers.

For this project, however, you can take a simpler approach if you choose. Specifically, you can set up a structure to track which variables are stored in which registers over time. When a variable needs to be loaded, first check to make sure that its current value isn't already in a register -- if it is, skip the load! When you change the value in a register, flag that register as needing to be stored, but you don't necessarily need to execute the store command immediately (or, in some cases, ever!).

There are two times that you need to check to see if a value in a register needs to be stored back into memory:

  1. When that register needs something else loaded into it.
  2. At the end of a basic block.

When you do a check, you only need to store a value from a register back into a memory location only if it has been flagged as changed (i.e., it was the write argument of an instruction) AND we're not past the last use of a local variable (at which point we wouldn't need to know its new value).

How you choose which register to put a value into is also up for optimizations:

  1. The simplest approach is a round-robin: cycle through all of the registers so values are spread among them and any particular value is held onto for a few instructions.
  2. A somewhat better approach is to choose whichever register was least recently used. Thus a value that is used frequently is more likely to stay in a register.
  3. Since we already tracked the first and last line that a variable is used on, we can improve method #2 by putting a register to the top of the list when we pass its current variable's last use -- we know that we won't need it again.
  4. An even better approach is to look ahead to see what variables we are going to need soon, and preserve them if we already have them loaded into a register.

Remember that all of these methods work only within blocks. If you're crossing block boundaries, you need to clear out all registers, possibly storing the contents. Due to this, it is on these block boundaries that the control flow graphs with give much better results.

An other optimization you may consider is replacing certain load/store pairings with the mem_copy instruction. Load, store, and memcopy take 100 cycles to perform (the other Ugly Code instructions only take 1), so reducing IO to memory dramatically shortens execution time.

Testing Output

See Project 6.

Note: the bad_and_ugly_interpreter has been updated. Please use the one provided in the Stater Code. This version has the option of profiling your code (counting the number of execution cycles your bad/ugly code takes). You can invoke it by providing the function "run_bad_code_from_string" or "run_ugly_code_from_string" with the optional argument "profile_mode=True". Then the function (instead of returning the executed output) will return the number of cycles your code took.

Submission

When you submit your program, you must include:

  • A project.py with the "generate_bad_code_from_string" function and the "generate_ugly_code_from_string" function.
  • A README.txt file that includes the your name, a brief summary of what does and does not work in your code. Your README may also include any notes that you want us to read before grading your program, such as any external resources you used in its development.
  • You may divide your project code into multiple files to do so you will need to use relative imports (if that doesn't mean anything to you, just keep everything in the project.py file).

All graded material must be in the folder named "Project8/".