\documentclass[10pt,a4paper]{article} \usepackage[latin1]{inputenc} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{booktabs} \usepackage{graphicx} \usepackage{listings} \usepackage{subfigure} \usepackage{float} \usepackage{hyperref} \title{Peephole Optimizer} \author{Jayke Meijer (6049885), Richard Torenvliet (6138861), Tadde\"us Kroes (6054129)} \begin{document} \maketitle \pagebreak \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 of optimizations of the assembly code, global optimizations and optimizations on a so-called basic block. These optimizations will be discussed seperatly \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. The reason for this will become clearer in the following section. \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 (not including this leader) until the next leader (including this 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. 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. Now all occurences of this expression can be replaced by a move of a new variable that is generated above the first occurence, which contains the value of the expression. This is a less efficient method, but because the basic blocks are in general not very large and the exectution time of the optimizer is not a primary concern, this is not a big problem. \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 with PLY} \subsection{Optimizations} \subsection{Writing} \section{Results} \subsection{pi.c} \subsection{arcron.c} \subsection{whet.c} \subsection{slalom.c} \subsection{clinpack.c} \section{Conclusion} \appendix \section{Total list of 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{Simple 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} addu $regA, $regB, 4 addu $regD, $regB, 4 ... move $regA, $regD Code not writing $regB -> ... ... ... addu $regC, $regB, 4 move $regC, $regD \end{verbatim} \end{document}