Limitations of Optimizing Compilers

Most code optimizations are done on an intermediate representation of the source code or at the assembly level (post-pass optimization). Read the Wikipedia [link] article on compiler optimization [link] and learn about optimization problems, types, factors, and techniques. Remember, no compiler optimization can effectively overcome a poor algorithm design or implementation.

Since compilers group transformations into phases, the user cannot choose exactly which transformations are performed nor can the user specify the order in which they are performed. Furthermore, the user cannot see the results of individual transformations. A particularly unfortunate case is when only one transformation in a particular phase causes buggy code to be produced. Designing compilers to overcome some of these limitations is an active area of research. One such optimizer and compiler that is being developed is VPO/VISTA.

VPO: Very Portable Optimizer

VPO is a compiler-independent and language-independent optimizer. [1]

"VPO employs a paradigm of compilation that has proven to be flexible and adaptable - all code improving transformations are performed on a single target-specific representation of the program, called RTLs [link] (Register Transfer Lists). RTLs are a low-level, machine and language independent representation that encodes machine-specific instructions. The comprehensive use of RTLs in VPO has several important consequences. One advantage of using RTLs as the sole intermediate representation is that the synthesis phases of the compiler can be invoked in any order and repeatedly if necessary. This largely eliminates code inefficiencies often caused by the ordering of the phases. In contrast, a more conventional compiler system will perform optimizations on various different representations."[2]

VISTA: VPO Interactive System for Tuning Applications

VISTA is a front end to VPO that enables the user to optimize the code interactively. One view displays assembly or RTL instructions and another view takes input on which optimizations to perform. Each optimization phase and transformation can be stepped through to see which which instructions are modified.

Now we will apply the interactive research compiler, VPO/VISTA, to the autocorrelation routine. VPO runs on Solaris, while VISTA runs in Java. We will run Java from a local windows machine since Code Composer runs on Windows. After compilation into an internal representation is completed, Java is used to start a "code server" on a Solaris machine over a network port, and a Java client is run locally to interactively optimize the code. The port over which the connection is made changes each time the optimizer is run. Your TA will give you instructions on which machine to connect to and your account information. You will transfer iirfilt.c, autocorr.c, and required header files to the remote machine. You will then compile autocorr.c and apply a a set of VISTA optimization sequences to the code. Next, you will then transfer autocorr.vpo.asm to the local machine and assemble it with the rest of PSD estimation application. Once you understand the VISTA optimization process and can interpret the results, you will use VISTA to fully optimize iirfilt.c.

Optimize autocorr.c

When VISTA is run a JAVA GUI will be opened. The right half of the GUI contains the assembly instructions, represented in the VPO-internal register-transfer-list (RTL) format. The left half contains the list of phases. Each phase contains multiple transformations; the "CD-player-like" buttons allow the user to move to the beginning and end of the entire phase list ( |< and >| ), move backward and forward one phase ( << and >> ), and move backward and forward one transformation ( < and > ). The buttons directly below the phase list allow phases to be added to the list.

Figure 1: Initial VISTA view with Ctl Flow(square) selected

First, select Ctl Flow(square) from the drop-down box. Can you identify what each loop/branch (depicted via arrows) corresponds to in the source code?

Figure 2: Initial VISTA view with instructions displayed in assembly form

To see how the RTL instructions originally listed in the right half of the GUI relate to assembly instructions, select Assembly in the drop-down box to see the corresponding assembly instructions. Note that the accumulators and registers are labeled with increasing numbers. These labels help indicate to the optimizer when a register is "dead", meaning that its contents are no longer needed. These "registers" can be mapped to physical registers by selecting Setup Trans Sequence, Register Assignment, and Done. Note that after Register Assignment is selected, Eval Order Deter and Global Inst Select are no longer available and others are made available. After Done is selected, you will then see familiar registers like A, B, AR1, etc. Next to "Register Assignment" in the left half of the window are the number of transformations and the code size in percent of the original code.

Now step through the individual register assigments. The > button will step through each transformation in two steps: pressing it once will highlight in yellow the instructions that may be modified (before-transformation state), and pressing it again will highlight the new instructions that replace the previous ones in light red (after-transformation state). Click on the << button to move backwards through the phases list, then step through some transformations using > and observe the results. Stepping through transformations in Inst Selection is especially informative. Note the code size, then go back and try the disabled optimizations. First, click |< to go back to the beginning of optimization, then select Option-> Discard changes after current state to remove Register Assignment. Now enter these optimizations: Eval Order Deter, Global Inst Select, and Register Assignment. Note the improvement in code size. What happens if Global Inst Select is instead selected first?

Figure 3: VISTA optimization phase entry

Now remove all optimizations and enter the optimizations shown in figure 3. Note that Fix Entry Exit and Inst Scheduling are required before assembly code can be written. If Fix Entry Exit is left out, no code is generated to preserve and restore register states at the beginning and end of the function. Inst Scheduling orders the instructions to avoid pipeline conflicts. If this optimization is left out, nops are entered after each instruction. Note that even though Inst Scheduling increases the reported size of the code, if it is left out the assembly code that VISTA writes to file will be even larger.

Figure 4: VISTA view before a particular transformation is applied

To finish the VISTA session and use the optimized code, click the Exit button in the lower portion of the GUI to generate a vpo.asm file that can be linked with the program. If you click on the "X" in the right side of the title bar, a vpo.asm file will not be generated.

Optimize pn.c, iirfilt.c, and autocorr.c

After inspecting the source code of the PSD estimator, you will likely discover inefficiencies. This implementation is provided as the "reference implementation" of the optimization process and to define the expected input and output of the application. The computational efficiency of your code will be judged against this implementation. Since a primary purpose of this lab is to learn optimization and efficient code techniques, the optimization portion of your lab grade will be based on the total execution time of rand_fillbuffer, iirfilt, and autocorr, which are contained in pn.c, iirfilt.c, and autocorr.c, respectively. You are not required to optimize memory use. You will not change lab4bmain.c, and you will preserve the input and output behavior of each function. Note that by execution time we mean cycle count, not the number of instructions in your program. Remember that several of the TMS320C54xx instructions take more than one cycle. The multicycle instructions are primarily the multi-word instructions, including instructions that take immediates, like stm, and instructions using direct addressing of memory (such as ld *(temp),A). Branch and repeat statements also require several cycles to execute. Most C instructions take more than one cycle. The debugger can be used to determine the exact number of cycles used by your code; ask your TA to demonstrate. However, since the number of execution cycles used by an instruction is usually determined by the number of words in its encoding, the easiest way to estimate the number of cycles used by your code is to count the number of instruction words in the .lst file or the disassembly window in the debugger.

You will create an optimized version of this code using any technique desired, and you will create an optimized version of iirfilt with VISTA.

Routine-Specific Optimization Tips

If you are programming the PN generator in assembly, you may wish to refer to the description of assembly instructions for logical operations in Section 2-2 of the C54x Mnemonic Instruction Set reference. Initialize the shift register to one. You can debug the PN output by comparing it to the output of the MATLAB code. Be prepared, as part of your quiz, to prove to a TA that your PN generator works properly.

Your IIR filtering routine can debugged by placing an impulse followed by zeros in autocorr_in instead of a PN sequence.

Your autocorrelation routine can be debugged by commenting out the IIR-filtering routine and placing the maximum DC value into autocorr_in in a similar manner as described the IIR-debugging step. Note that each of these tips is the most useful if the output is inspected in memory.

Grading

We will grade you based on the number of cycles used in the statements rand_fillbuffer();, iirfilt();, and autocorr();. Note that some instructions, like RPT, are non-repeatable instructions; their use may cause unnecessary glitches in I/O. For grading simplicity, your final code should not have modifications except in these three functions, and M should be set to 23. If the number of cycles used in each function is variable, the maximum possible number of cycles will be counted for each function. You must use the core.asm file in v:\ece320\54x\dsplib\core.asm or the C core file in v:\ece320\54x\dspclib\core.asm as provided by the TAs; these files may not be modified. We reserve the right to test your code by modifying the inputs.

You are also required to record some of your iirfilt VISTA results to a file so that improvements to VISTA can be identified. Each time you test a VISTA-generated function on the DSP, (1) record (yes or no) whether it works, and (2) how many cycles it takes to execute this function. You are not required to test every sequence you generate; if you are not happy with the code size of a sequence, keep trying until you have one worthy of testing. Once you test the code, record the results. When you have finished optimizing a function with VISTA, (1) write down a rough estimate of the total time you spent optimizing the function with VISTA (to the nearest 15 minutes or less), and (2) write down the VISTA optimization sequence that can be used to obtain your optimized code. Finally, record at what stage, if any, you altered the C code of the reference implementation. Valid answers are not at all, before VISTA was used, or after some VISTA optimization was attempted.

Record how much time you spent on the "free-style" optimization activity, as well as whether you used generated code as a starting point or "started from scratch". If you used VISTA, VPO, or TI generated code only for guidance this is to be recorded as "starting from scratch" or "None" in the free-style results table. If you modified a generated assembly file, record this as "VISTA", "VPO", or "TI" in the free-style results table.

Email your results at or before the time they are due. The address will be given to you by your TA. Enter in the subject line "[VISTA]<space>", without the quotes and a space where <space> appears. After the space you may put anything you want. Email your C code used in optimization (if it is different from the reference implementation), your free-style-optimized assembly code, and the results of your optimization process. Please attach the results as text; if you used a spreadsheet to record the results, export the file to a CSV file and attach the CSV file. Optionally, add any comments you might have about your experience with VISTA. Here are two tables listing what is required:

This lab is to be completed in two weeks, but the VISTA portion is to be completed in one week and the VISTA log should be sent in at that time. Grading for this lab will be a bit different from past labs:

Appendix A: Descriptions of some optimization phases