\documentclass[10pt,a4paper]{article} \usepackage[latin1]{inputenc} \usepackage{amsmath,amsfonts,amssymb,booktabs,graphicx,listings,subfigure} \usepackage{float,hyperref} \title{Peephole Optimizer} \author{Jayke Meijer (6049885), Richard Torenvliet (6138861), Tadde\"us Kroes (6054129)} \begin{document} \maketitle \tableofcontents \pagebreak \section{Introduction} The goal of the assignment is to implement the optimization stage of the compiler. To reach this goal the parser and the optimizer part of the compiler have to be implemented. The output of the xgcc cross compiler on a C program is our input. The output of the xgcc cross compiler is in the form of Assembly code, but not optimized. Our assignment includes a number of C programs. An important part of the assignment is parsing the data. Parsing the data is done with Lex and Yacc. The Lexer is a program that finds keywords that meets the regular expression provided in the Lexer. After the Lexer, the Yaccer takes over. Yacc can turn the keywords in to an action. \section{Design} There are two general types of optimizations of the assembly code, global optimizations and optimizations on a so-called basic block. These optimizations will be discussed separately \subsection{Global optimizations} We only perform one global optimization, which is optimizing branch-jump statements. The unoptimized Assembly code contains sequences of code of the following structure: \begin{verbatim} beq ...,$Lx j $Ly $Lx: ... \end{verbatim} This is inefficient, since there is a jump to a label that follows this code. It would be more efficient to replace the branch statement with a \texttt{bne} (the opposite case) to the label used in the jump statement. This way the jump statement can be eliminated, since the next label follows anyway. The same can of course be done for the opposite case, where a \texttt{bne} is changed into a \texttt{beq}. Since this optimization is done between two series of codes with jumps and labels, we can not perform this code during the basic block optimizations. \subsection{Basic Block Optimizations} Optimizations on basic blocks are a more important part of the optimizer. First, what is a basic block? A basic block is a sequence of statements guaranteed to be executed in that order, and that order alone. This is the case for a piece of code not containing any branches or jumps. To create a basic block, you need to define what is the leader of a basic block. We call a statement a leader if it is either a jump/branch statement, or the target of such a statement. Then a basic block runs from one leader until the next leader. There are quite a few optimizations we perform on these basic blocks, so we will describe the types of optimizations here in stead of each optimization. \subsubsection*{Standard peephole optimizations} These are optimizations that simply look for a certain statement or pattern of statements, and optimize these. For example, \begin{verbatim} mov $regA,$regB instr $regA, $regA,... \end{verbatim} can be optimized into \begin{verbatim} instr $regA, $regB,... \end{verbatim} since the register \texttt{\$regA} gets overwritten by the second instruction anyway, and the instruction can easily use \texttt{\$regB} in stead of \texttt{\$regA}. There are a few more of these cases, which are the same as those described on the practicum page \footnote{\url{http://staff.science.uva.nl/~andy/compiler/prac.html}} and in Appendix \ref{opt}. \subsubsection*{Common subexpression elimination} A more advanced optimization is common subexpression elimination. This means that expensive operations as a multiplication or addition are performed only once and the result is then `copied' into variables where needed. \begin{verbatim} addu $2,$4,$3 addu = $t1, $4, $3 ... mov = $2, $t1 ... -> ... ... ... addu $5,$4,$3 mov = $4, $t1 \end{verbatim} A standard method for doing this is the creation of a DAG or Directed Acyclic Graph. However, this requires a fairly advanced implementation. Our implementation is a slightly less fancy, but easier to implement. We search from the end of the block up for instructions that are eligible for CSE. If we find one, we check further up in the code for the same instruction, and add that to a temporary storage list. This is done until the beginning of the block or until one of the arguments of this expression is assigned. We now add the instruction above the first use, and write the result in a new variable. Then all occurrences of this expression can be replaced by a move of from new variable into the original destination variable of the instruction. This is a less efficient method then the dag, but because the basic blocks are in general not very large and the execution time of the optimizer is not a primary concern, this is not a big problem. \subsubsection*{Fold constants} Constant folding is an optimization where the outcome of arithmetics are calculated at compile time. If a value x is assigned to a certain value, lets say 10, than all next occurences of \texttt{x} are replaced by 10 until a redefinition of x. Arithmetics in Assembly are always performed between two variables or a variable and a constant. If this is not the case the calculation is not possible. See \ref{opt} for an example. In other words until the current definition of \texttt{x} becomes dead. Therefore reaching definitions analysis is needed. Reaching definitions is a form of liveness analysis, we use the liveness analysis within a block and not between blocks. During the constant folding, so-called algebraic transformations are performed as well. Some expression can easily be replaced with more simple once if you look at what they are saying algebraically. An example is the statement $x = y + 0$, or in Assembly \texttt{addu \$1, \$2, 0}. This can easily be changed into $x = y$ or \texttt{move \$1, \$2}. Another case is the multiplication with a power of two. This can be done way more efficiently by shifting left a number of times. An example: \texttt{mult \$regA, \$regB, 4 -> sll \$regA, \$regB, 2}. We perform this optimization for any multiplication with a power of two. There are a number of such cases, all of which are once again stated in appendix \ref{opt}. \subsubsection*{Copy propagation} Copy propagation `unpacks' a move instruction, by replacing its destination address with its source address in the code following the move instruction. This is not a direct optimization, but this does allow for a more effective dead code elimination. The code of the block is checked linearly. When a move operation is encountered, the source and destination address of this move are stored. When a normal operation with a source and a destination address are found, a number of checks are performed. The first check is whether the destination address is stored as a destination address of a move instruction. If so, this move instruction is no longer valid, so the optimizations can not be done. Otherwise, continue with the second check. In the second check, the source address is compared to the destination addresses of all still valid move operations. If these are the same, in the current operation the found source address is replaced with the source address of the move operation. An example would be the following: \begin{verbatim} move $regA, $regB move $regA, $regB ... ... Code not writing $regA, -> ... $regB ... ... ... addu $regC, $regA, ... addu $regC, $regB, ... \end{verbatim} This code shows that \texttt{\$regA} is replaced with \texttt{\$regB}. This way, the move instruction might have become useless, and it will then be removed by the dead code elimination. \subsection{Dead code elimination} The final optimization that is performed is dead code elimination. This means that when an instruction is executed, but the result is never used, that instruction can be removed. To be able to properly perform dead code elimination, we need to know whether a variable will be used, before it is overwritten again. If it does, we call the variable live, otherwise the variable is dead. The technique to find out if a variable is live is called liveness analysis. We implemented this for the entire code, by analyzing each block, and using the variables that come in the block live as the variables that exit its predecessor live. \section{Implementation} We decided to implement the optimization in Python. We chose this programming language because Python is an easy language to manipulate strings, work object-oriented etc. It turns out that a Lex and Yacc are also available as a Python module, named PLY(Python Lex-Yacc). This allows us to use one language, Python, instead of two, i.e. C and Python. Also no debugging is needed in C, only in Python which makes our assignment more feasible. The program has three steps, parsing the Assembly code into a datastructure we can use, the so-called Intermediate Representation, performing optimizations on this IR and writing the IR back to Assembly. \subsection{Parsing} The parsing is done with PLY, which allows us to perform Lex-Yacc tasks in Python by using a Lex-Yacc like syntax. This way there is no need to combine languages like we should do otherwise since Lex and Yacc are coupled with C. The decision was made to not recognize exactly every possible instruction in the parser, but only if something is for example a command, a comment or a gcc directive. We then transform per line to an object called a Statement. A statement has a type, a name and optionally a list of arguments. These statements together form a statement list, which is placed in another object called a Block. In the beginning there is one block for the entire program, but after global optimizations this will be separated in several blocks that are the basic blocks. \subsection{Optimizations} The optimizations are done in two different steps. First the global optimizations are performed, which are only the optimizations on branch-jump constructions. This is done repeatedly until there are no more changes. After all possible global optimizations are done, the program is seperated into basic blocks. The algorithm to do this is described earlier, and means all jump and branch instructions are called leaders, as are their targets. A basic block then goes from leader to leader. After the division in basic blocks, optimizations are performed on each of these basic blocks. This is also done repeatedly, since some times several steps can be done to optimize something. \subsection{Writing} Once all the optimizations have been done, the IR needs to be rewritten into Assembly code. After this step the xgcc crosscompiler can make binary code from the generated Assembly code. The writer expects a list of statements, so first the blocks have to be concatenated again into a list. After this is done, the list is passed on to the writer, which writes the instructions back to Assembly and saves the file so we can let xgcc compile it. We also write the original statements to a file, so differences in tabs, spaces and newlines do not show up when we check the differences between the optimized and non-optimized files. \subsection{Execution} To execute the optimizer, the following command can be given:\\ \texttt{./main } \section{Testing} Of course, it has to be guaranteed that the optimized code still functions exactly the same as the none-optimized code. To do this, testing is an important part of out program. We have two stages of testing. The first stage is unit testing. The second stage is to test whether the compiled code has exactly the same output. \subsection{Unit testing} For almost every piece of important code, unit tests are available. Unit tests give the possibility to check whether each small part of the program, for instance each small function, is performing as expected. This way bugs are found early and very exactly. Otherwise, one would only see that there is a mistake in the program, not knowing where this bug is. Naturally, this means debugging is a lot easier. The unit tests can be run by executing \texttt{make test} in the root folder of the project. This does require the \texttt{textrunner} module. Also available is a coverage report. This report shows how much of the code has been unit tested. To make this report, the command \texttt{make coverage} can be run in the root folder. The report is than added as a folder \emph{coverage} in which a \emph{index.html} can be used to see the entire report. \subsection{Ouput comparison} In order to check whether the optimization does not change the functioning of the program, the output of the provided benchmark programs has to be compared to the output after optimization. If any of these outputs is not equal to the original output, our optimizations are to aggressive, or there is a bug somewhere in the code. \section{Results} The following results have been obtained:\\ \begin{tabular}{|c|c|c|c|c|c|} \hline Benchmark & Original & Optimized & Original & Optimized & Performance \\ & Instructions & instructions & cycles & cycles & boost(cycles)\\ \hline pi & 134 & & & & \\ acron & & & & & \\ dhrystone & & & & & \\ whet & & & & & \\ slalom & & & & & \\ clinpack & & & & & \\ \hline \end{tabular} \appendix \section{List of all optimizations} \label{opt} \textbf{Global optimizations} \begin{verbatim} beq ...,$Lx bne ...,$Ly j $Ly -> $Lx: ... $Lx: ... bne ...,$Lx beq ...,$Ly j $Ly -> $Lx: ... $Lx: ... \end{verbatim} \textbf{Standard basic block optimizations} \begin{verbatim} mov $regA,$regA -> --- // remove it mov $regA,$regB -> instr $regA, $regB,... instr $regA, $regA,... instr $regA,... instr $4,... mov [$4-$7], $regA -> jal XXX jal XXX sw $regA,XXX -> sw $regA, XXX ld $regA,XXX shift $regA,$regA,0 -> --- // remove it add $regA,$regA,X -> lw ...,X($regA) lw ...,0($regA) \end{verbatim} \textbf{Advanced basic block optimizations} \begin{verbatim} # Common subexpression elimination addu $regA, $regB, 4 addu $regD, $regB, 4 ... move $regA, $regD Code not writing $regB -> ... ... ... addu $regC, $regB, 4 move $regC, $regD # Constant folding li $regA, constA "" sw $regA, 16($fp) "" li $regA, constB -> "" sw $regA, 20($fp) "" lw $regA, 16($fp) "" lw $regB, 20($fp) "" addu $regA, $regA, $regA $li regA, (constA + constB) at compile time # Copy propagation move $regA, $regB move $regA, $regB ... ... Code not writing $regA, -> ... $regB ... ... ... addu $regC, $regA, ... addu $regC, $regB, ... # Algebraic transformations addu $regA, $regB, 0 -> move $regA, $regB subu $regA, $regB, 0 -> move $regA, $regB mult $regA, $regB, 1 -> move $regA, $regB mult $regA, $regB, 0 -> li $regA, 0 mult $regA, $regB, 2 -> sll $regA, $regB, 1 \end{verbatim} \end{document}