This project will put the final touches on the Good language for this course. It will consist of two main pieces:
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.
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.
runs_faster = True while runs_faster: runs_faster = False if can_do_optimization: # Do optimization runs_faster = True
The next set of optimizations should all be implemented inside the optimization loop:
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.
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:
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:
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.
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.
When you submit your program, you must include:
All graded material must be in the folder named "Project8/".