diff options
| -rw-r--r-- | cibic.pdf | bin | 127049 -> 131330 bytes | |||
| -rw-r--r-- | cibic.tex | 52 |
2 files changed, 50 insertions, 2 deletions
| Binary files differ @@ -217,8 +217,8 @@ the outer scope which is another instance of ``\texttt{CSNode}''. As for ``\texttt{CTable}'',stores all the current symbols. As mentioned above, for each struct or union, there is also a pointer to ``\texttt{CTable}'' stores all field names. ``\texttt{CTable}'' is an open addressing hash table -containing nodes of the type ``\texttt{CTNode}''. The structure of each node is -depicted in figure \ref{fig:struct_ctnode}. +containing nodes of the type ``\texttt{CTNode}''. Inspired by \cite{grune12}, +the structure of each node is designed as in figure \ref{fig:struct_ctnode}. \begin{figure}[H] \centering @@ -746,7 +746,55 @@ set and the sentinel node helps us to move to another set conveniently. The algorithm also requires a pre-calculated weight of each interval (computed from the accesses to the interval) which helps to decide the spilled variable. \section{Performance and Optimization} +\subsection{Compile Time} +CIBIC compiles very fast for all the given source code and some additional test +cases. It costs CIBIC 0.10 second to compile all 52 programs, while gcc spends +1.90 seconds to complete in the same testing environment. Although the test may +not be complete or fair (since gcc is a much more sophisticated compiler), the +result does show a decent and promising compile speed. +\subsection{Compile Quality} +In the final examination, the performance of MIPS assembly generated by CIBIC +surpasses the ones generated by most of my classmates' Java-implemented +compilers. It is worth mentioning that all of those few (just about three or +four) compilers that produces better code are written in Java and none of them +always generates better code than CIBIC. Also, in the circumstances where the +code generated by CIBIC is not the best, the runtime difference between the +best performance code and the one by CIBIC is small. Moreover, as far as I +know, those compiler make use of inline optimization (not fully implemented) +which may be very effective for some special code. However, CIBIC does not +implement any form of inline optimization due to the limited time (To implement +a decent inline optimization for an SSA-based and C-implemented compiler +requires some extra work). Finally, I would like to aruge that all test cases +provied by teaching assistants may not be complete or convincing. The major +design flaw is all functions are very short and only have one or two nested if +statement or loops (except test case: ``superloop''). Therefore, the advantage +of SSA (especially the advanced register allocation algorithm) is not shown +very well. +\subsection{Optimization} +CIBIC implements the following optimizations: +\begin{itemize} + \item constant propagation + \item dead code elimination + \item strength reduction + \item common subexpression eliminiation +\end{itemize} + +Unfortunately, these optimization do not seems to be very effective to the +given test cases (although some may be effective to some specific test cases). +However, the assembly level optimization does have a considerable effect. Some important techinques are: +\begin{itemize} + \item reduce the use of \texttt{seq} and \texttt{sne} by fusing them with subsequent \texttt{beq} or \texttt{bne} + \item reduce the load of immediates + \item fuse the short-circuit operators and subsequent branch together (on the one hand it can reduce one or two extra jumps, on the other hand, the dominance of CFG may change so that common subexpression optimization can optimize more) +\end{itemize} + +We are not going to discuss optimization effectiveness in detail because all optimizations used by CIBIC are traditional. Instead, code snippets are presented and explained below to reveal \textbf{inappropriate naive implementation of some optimizations may be wrong}. \begin{thebibliography}{9} + \bibitem{grune12} + Grune, Dick, et al. Modern Compiler Design. Springer, 2012. + \bibitem{appel97} + Appel, Andrew W. and Ginsburg, Maia. Modern Compiler Implementation in + C. Cambridge University Press, 1997. \bibitem{tarjan06} Georgiadis, Loukas, Robert Endre Tarjan, and Renato Fonseca F. Werneck. ``Finding Dominators in Practice.'' J. Graph Algorithms Appl. 10.1 |