path: root/doc/cibic.tex

\documentclass[10pt, a4paper]{article}

\usepackage{xeCJK, fontspec}
\usepackage{amsmath, verbatim}
\usepackage{setspace, float}
\usepackage{graphicx, wrapfig, algorithmicx}
\usepackage{rotating, enumerate, minted, fancyvrb, longtable}
\usepackage[left=1in, right=1in]{geometry}
\usepackage[font=small]{caption}

\defaultfontfeatures{Mapping=tex-text}
\setCJKmainfont[BoldFont={STHeiti}]{Adobe Song Std}
%\XeTeXlinebreaklocale "zh"
%\XeTeXlinebreakskip = 0pt plus 1pt minus 0.1pt

%\setlength{\parindent}{2em}
%\setlength{\parskip}{1em}
\makeatletter
\def\verbatim@font{\ttfamily\small}
\makeatother

%\makeatletter
%\let\@afterindentrestore\@afterindentfalse
%\let\@afterindentfalse\@afterindenttrue
%\@afterindenttrue
%\makeatother

\xeCJKsetup{CJKglue=\hspace{0pt plus .08 \baselineskip }}

\newcommand{\ud}{\mathrm{d}}
\usemintedstyle{colorful}
\begin{document}
\title{\Large{CIBIC: C Implemented Bare and Ingenuous Compiler}}

\author{\textsc{尹茂帆 Ted Yin}\\ \\\multicolumn{1}{p{.7\textwidth}}
    {\centering\emph{F1224004 5120309051\\
Shanghai Jiao Tong University ACM Class}}}
\maketitle
\begin{abstract}
    This report presents the design and features of a simple C compiler which
    generates MIPS assembly code. Although not all the language requirements and
    features are implemented according to the standard, it still supports major
    C features, such as basic types (void, int, char), basic flow control syntax
    (if, while-loop, for-loop), user-defined types (aka. typedef), functions,
    pointers (including function pointers), struct/union (may be nested), etc.
    Besides, it makes use of SSA (Single Static Assignment) form for the IR
    (Intermediate Representation) and optimization. The whole compiler is
    written in pure C, obeying C89/C99 standard. The report first introduces the
    lexer and parser generation, then focuses on the data structures being used
    in the AST (Abstract Syntax Tree) and symbol tables, and makes a conclusion
    on the supported syntactical features. Next, the report shows the
    intermediate representation design and claims the techniques that have been
    used in the project. Finally, various optimization techniques are presented
    and discussed, some are accompanied with code snippets.
\end{abstract}
\tableofcontents
\section{Lexer and Parser}
CIBIC makes good use of existing lexer and parser generators. It uses Flex to
generate lexer while using Bison as parser generator. Both generators read
boilerplate text which contains C code fragments to be filled in the generated
lexer/parser. The best practice, I suggest, is to avoid embedding too much
concrete code in the boilerplate. Instead, we shall write well-designed
functions in a separate file (``\texttt{ast.c}'' in CIBIC) and invoke functions
in the boilerplate. The reason is that it is almost not practical nor
convenient to debug the generated lexer or parser. Using the seperation method,
we can set up breakpoints in the seperate file easily and debug on the fly. The
declarations of all functions that may be invoked during parsing can be found
in``\texttt{ast.h}''.

It requires a little more effort to track the location of each token using
Flex.  Luckily, Flex provides with a macro called ``\texttt{YY\_USER\_ACTION}''
to let the user do some extra actions after each token is read. So I maintained
a global variable ``\texttt{yycolumn}'' to keep the current column, a global
char array ``\texttt{linebuff}'' to buffer the text being read for error
report.
\begin{listing}[H]
    \centering
    \RecustomVerbatimEnvironment{Verbatim}{BVerbatim}{}
    \begin{minted}{c}
int yycolumn = 1;
char linebuff[MAX_LINEBUFF], *lptr = linebuff;

#define YY_USER_ACTION \
    do { \
        yylloc.first_line = yylloc.last_line = yylineno; \
        yylloc.first_column = yycolumn; \
        yylloc.last_column = yycolumn + yyleng - 1; \
        yycolumn += yyleng; \
        memmove(lptr, yytext, yyleng);  \
        lptr += yyleng; \
    } while (0);

#define NEW_LINE_USER_ACTION \
    do { \
        yycolumn = 1; \
        lptr = linebuff; \
    } while (0)
\end{minted}
\caption {Code Snippet to Track Down Location}
\end{listing}
\subsection{Friendly Error Report}
CIBIC generates friendly and accurate error report. The corresponding line and
column number are printed. Besides, if it is an syntax error, CIBIC will print
the context where the error occurs just like clang.
\begin{figure}[H]
    \centering
\begin{BVerbatim}
2:28: error: syntax error, unexpected ';', expecting ',' or ')'
    int this_is_an_example(;
                           ^

2:13: error: syntax error, unexpected identifier
    typedef a
            ^
\end{BVerbatim}
\caption {Some Error Report Examples}
\end{figure}

\section{Semantic Analysis and Implementation}
The parsing process is also an AST (Abstrct Syntax Tree) construction process.
By calling the corresponding functions, the generated parser creates tree nodes
and merge them into subtrees. The major issue here is how to design a proper
data structure to represent and maintain the AST. In CIBIC, all nodes in an AST
are instances of struct ``CNode'' in figure \ref{fig:struct_cnode}.
\begin{figure}[H]
    \centering
    \texttt {
    \begin{tabular}{|c|}
        \hline
        type \\
        \footnotesize{describe syntax information e.g. expression or declarator} \\ \hline
        rec: \\
        \footnotesize{\textbf{union of intval / subtype / strval}} \\
        \footnotesize{stores detailed information e.g. which kind of expression it is} \\ \hline
        ext: \\
        \footnotesize{\textbf{struct of type, var, autos, const\_val, is\_const, offset}} \\
        \footnotesize{extended info, where annotation is made} \\ \hline
        chd \\
        \footnotesize{the left most child of the node} \\ \hline
        next \\
        \footnotesize{the next sibling} \\ \hline
        loc \\
        \footnotesize{\textbf{struct of row, col}} \\
        \footnotesize{the location in the source code, for error report} \\ \hline
        \end{tabular}
    }
    \caption{The Structure of a CNode instance}
    \label{fig:struct_cnode}
\end{figure}
Since a node may have variable number of children, the most common and
efficient approach is to implement a left-child right-sibling binary tree. The
field ``\texttt{chd}'' points to the child and ``\texttt{next}'' points to the
next sibling. This implementation is extremely flexible because we do not need
to know the number of children in advance, which brings us the convenience of
appending argument nodes to a function invocation node in the boilerplate.

After construction of the AST, the tree will be traversed by calling mutually
recursive functions declared in ``\texttt{semantics.h}''. The entry call is
``\texttt{semantics\_check}'' which will set up the symbol tables and call
``\texttt{semantics\_func}'' and ``\texttt{semantics\_decl}'' to analyze
function definitions and global declarations. These functions will further
invoke more basic functions such as ``\texttt{semantics\_comp}'' (handles
compound statements) to fully check the semantics and gather variable typing
information.

The key data structures in the semantic checking are \textbf{symbol tables}.
Symbol tables maintain variables and types in different scopes across different
name spaces. When a variable is defined, the corresponding type specifer will
be checked and binds to the variable. Also, when the scope ends, all variable
bindings living within the scope will be removed from the table. Although they
are removed from the table, the bindings are still referenced by some nodes on
the AST, so that the AST becomes ``\textbf{annotated AST}''. In CIBIC, the
variable reference is stored in ``\texttt{ext.var}'' field of
``\texttt{CNode}'' and the type information of an subexpression is annotated at
``\texttt{ext.type}''. Thus, in a word, symbol tables stores all symbols that
are currently \textbf{visible}.

In C language, there are four name spaces: for label names, tags, members of
structures or unions and all other identifiers. Goto statments are not
implemented in CIBIC, so there're actually three name spaces. Since each kind of
structures or unios have its own name space for its fields, we treat them
specially and create a new table for each of them. For tags and all other
identifiers, we set up two global tables. Besides name spaces, scoping is also a
very important concept in C. It seems to be an orthogonal concept to name
spaces.

Considering these two concepts, CIBIC implements a struct named
``\texttt{CScope}'' to maintain all the information as shown in figure
\ref{fig:struct_cscope}.
\begin{figure}[H]
    \centering
    \texttt {
    \begin{tabular}{|c|}
        \hline
        lvl \\
        \footnotesize{current nesting level of scopes, e.g. 0 for global scope} \\ \hline
        func \\
        \footnotesize{current function, helpful when analyzing a return statement} \\ \hline
        inside\_loop \\
        \footnotesize{if the scope is inside a loop, help full when analyzing a break statement} \\ \hline
        top \\
        \footnotesize{points to the top of the scope stack} \\ \hline
        ids \\
        \footnotesize{name space for all other variables} \\ \hline
        tags \\
        \footnotesize{name space for all tags (name of structs or unions)} \\ \hline
        \end{tabular}
    }
    \caption{The Structure of a CScope instance}
    \label{fig:struct_cscope}
\end{figure}

Note that ``\texttt{top}'' points to an instance of ``\texttt{CSNode}'' which
has two fields ``\texttt{symlist}'' and ``\texttt{next}''. ``\texttt{symlist}''
points to a list of symbols in the same scope while ``\texttt{next}'' links to
the outer scope which is another instance of ``\texttt{CSNode}''. As for
``\texttt{ids}'' and ``\texttt{tags}'', they are pointers to
``\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}''. Inspired by \cite{grune12},
the structure of each node is designed as in figure \ref{fig:struct_ctnode}.

\begin{figure}[H]
    \centering
    \texttt {
    \begin{tabular}{|c|}
        \hline
        key \\
        \footnotesize{char *} \\ \hline
        val \\
        \footnotesize{void *, in order to also be used in checking duplicate parameters, etc.} \\ \hline
        next \\
        \footnotesize{the next element which has the same hash value} \\ \hline
        lvl \\
        \footnotesize{scope level} \\ \hline
        \end{tabular}
    }
    \caption{The Structure of a CTNode instance}
    \label{fig:struct_ctnode}
\end{figure}

Thanks to the level information kept in each ``\texttt{CTNode}'', we do not
have to establish a hash table for every scopes, which may be memory consuming.
Instead, whenever a new scope begins, CIBIC simply pushes a new frame to scope
stack. This is achieved by creating an instance of ``\texttt{CSNode}'', setting
its ``\texttt{next}'' field to the ``\texttt{top}'' field of the
``\texttt{CScope}'' then letting the ``\texttt{top}'' points to the new frame,
finally increasing ``\texttt{lvl}'' by one. Whenever a new symbol is being
added to ``\texttt{CScope}'', CIBIC adds the symbol to one of the tables
``\texttt{ids}'' and ``\texttt{tags}'', then also appends the symbol to the
``\texttt{symlist}'' of the top of the scope stack. The most elegant
characteristics of open addressing hash tables is, for the same name appears in
different scopes, the symbol defined at the inner most is always ahead of
others in the chain of the table because it is the most recently added. So,
for lookups, CIBIC just need to return the first node having the same name in
the chain, which is very time-efficient. At last, when a scope ends, CIBIC
scans the whole ``\texttt{symlist}'' of the top scope frame, and tries to remove
these symbols from the table. Figure \ref{fig:nested_scope} presents the content
of the scope stack when the analysis proceeds into the inner most declaration of
a. Chains with hash code 0097 and 0098 in figure \ref{fig:scope_stack} reveal
the underlying mechanism.
\begin{figure}[H]
%    \centering
    \begin{minipage}{0.35\textwidth}
%    \RecustomVerbatimEnvironment{Verbatim}{BVerbatim}{}
    \begin{minted}{c}
int main() {
    int a, b;
    if (a > 0)
    {
        int a, b;
        if (a > 0)
        {
            int a, b;
        }
    }
}
    \end{minted}
    \caption {Nested Scope Example}
    \label{fig:nested_scope}
\end{minipage}
%    \centering
    \begin{minipage}{0.5\textwidth}
    \begin{BVerbatim}
    [0072]->[int@747e780:0]
    [0097]->[a@7484ae0:3]->[a@7484890:2]->[a@7484580:1]
    [0098]->[b@7484bb0:3]->[b@7484960:2]->[b@7484710:1]
    [0108]->[printf@747f150:0]
    [0188]->[scanf@747f640:0]
    [0263]->[__print_string@7484010:0]
    [0278]->[__print_char@7483fc0:0]
    [0623]->[__print_int@747f8b0:0]
    [0778]->[malloc@7484100:0]
    [0827]->[void@747eee0:0]
    [0856]->[main@7484530:0]
    [0908]->[memcpy@7484060:0]
    [0971]->[char@747e9f0:0]
    \end{BVerbatim}
    \caption {CIBIC Dump: Scope Stack}
    \label{fig:scope_stack}
\end{minipage}
\end{figure}

\subsection{Type System}
C has a small set of basic types. In CIBIC, basic types include \texttt{char},
\texttt{int} and \texttt{void} (literally, \texttt{void} is not an actual
type). However, C supports two powerful type aggregation: arrays and structures
(unions), and also supports an indirect access tool: pointer. This makes the
type system much more complex and usable in practice. CIBIC uses the concept
``type tree'' to organize types. All basic types are the leaves of a type tree,
while aggregate types and pointers are the intermediate nodes. Figure
\ref{fig:type_tree} shows a typical type tree of a C struct.

\begin{figure}
    \centering
    \includegraphics[scale=0.5]{tree.png}
    \caption{A Typical Type Tree}
    \label{fig:type_tree}
\end{figure}

A type tree is good at preserving type hierarchy info which may be extremely
useful in type checking. For example, when checking a expression \texttt{*a},
compiler first check if the root of the type tree of a is a pointer. If not,
error message will be printed and semantic checking fails. Otherwise, the type
of the expression result is the subtree of the only child of the root. Also, a
type tree enables us to implement complex type nesting, which will be discussed
later on.
\subsection{\texttt{typedef} support}
CIBIC has support for user-defined types, which are defined via the keyword
``\texttt{typedef}''.  However, ``\texttt{typedef}'' is notoriously difficult
to deal with due to the ambiguity caused by the language design. For example,
in ``\texttt{int A}'', A is a \textbf{variable} of integer type, but in
``\texttt{A a}'', A is a user-defined \textbf{type}. The subtle semantic
difference is caused by context. In former case, A is identified as a
identifier token, while in latter case, identified as a type specifier. The
meaning of a token should be made clear during lexical analysis which does not
take in account of context. So the most direct and effective way to implement
\texttt{typedef} is to hack the lexer and parser. CIBIC maintains a
``\texttt{typedef\_stack}'' to denote current parsing status. When a parser has
just read a type specifier, before it moves on, it invokes
``\texttt{def\_enter(FORCE\_ID)}'' to notify ``\texttt{typedef\_stack}'' the
subsequent string token must be an identifier instead of a type specifier. As
for ``\texttt{typedef}'' statements, the parser will invoke
``\texttt{def\_enter(IN\_TYPEDEF)}'' to record the newly defined typename by
adding an entry to a hash table. As for the lexer, when a string token is being
read, it invokes ``\texttt{is\_identifier}'' to make sure whether the string is
an \texttt{IDENTIFIER} or a \texttt{USER\_TYPE}.

Listing \ref{list:typedef} demonstrates a very subtle use of \texttt{typedef},
which can be parsed perfectly by CIBIC.

\begin{listing}[H]
    \centering
    \RecustomVerbatimEnvironment{Verbatim}{BVerbatim}{}
    \begin{minted}{c}
/* It's quite common to define a shorthand `I' for `struct I'. */
typedef struct I I;
/* Declaration of a function with parameter `a' of user-defined type `I'. */
int incomp(I a);
/* The definition of `I' is postponed. */
struct I {
    int i, j;
};
/* Function definition of previous declared one. */
int incomp(I a) {}
/* Define `b' as an int type. */
typedef int b;
int main() {
    /* Variable `b' is of type `b', an integer actually. */
    I i;
    b b;
    incomp(i);
}
\end{minted}
\caption {\texttt{typedef} Example}
\label {list:typedef}
\end{listing}
\newpage
\subsection{Complex Declaration and Function Pointer}
With the help of type tree, CIBIC supports complex type declaration and
function pointers. The code below shows declaration with different semantics.
The subsequent dump information shows the corresponding type trees. The
hexidecimal value after ``\texttt{@}'' is the memory address of corresponding
instance in the implementation. For example, local variable \texttt{a} is an
instance of struct whose address is \texttt{735da40}, and \texttt{next} field
of \texttt{struct A} also points to the type with the same address. In fact,
the address of a struct type instance is regarded as its unique id in CIBIC.
This guarantees that the type tree is correctly structured as shown in figure
\ref{fig:type_tree}. It is also worth noting that three different delcarations
of ``arrays'' have inherently different meaning. Also the code shows us a very
complex declaration of a function \texttt{func}. It is a selector which returns
one of the pointers to a function in its parameters.

\begin{listing}[H]
    \centering
    \RecustomVerbatimEnvironment{Verbatim}{BVerbatim}{}
    \begin{minted}[linenos=true,firstnumber=1]{c}
struct A {
    int x, y;
    struct B {
        int i, j;
    } b;
    struct A *next;
};

/* a function that returns a pointer to function */
int (*func(int flag, int (*f)(), int (*g)()))() {
    if (flag) return f;
    else return g;
}

int main() {
    struct A a;
    /* the follow types are distinctly different */
    int a0[10][20]; /* two-dimensional array */
    int (*a1)[20];  /* a pointer to array */
    int *a2[20];    /* an array of pointers */
    int **a3;       /* pointer to pointer */
    /* pointer to a function */
    int (*f)(), (*h)();
    /* function declaration, not a variable */
    int (*g(int ***e[10]))();
    /* complex type casting is also supported */
    f = (int (*)())(0x12345678);
    f = func(1, f, main); /* f */
    h = func(0, f, main); /* main */
    /* 0 1 */
    printf("%d %d\n", f == main, h == main);
}
    \end{minted}
 \caption {Complex Declaration Example}
\end{listing}
\begin{figure}[H]
    \centering
    \begin{BVerbatim}
[func:{name:func}{size:-1}
    {params:
        [var@735fd60:flag :: [int]],
        [var@735ff00:f :: [ptr]->
                [func:{name:}{size:-1}
                    {params:}
                    {local:}]->[int]],
        [var@7360080:g :: [ptr]->
                [func:{name:}{size:-1}
                    {params:}
                    {local:}]->[int]]}
    {local:}]->[ptr]->
        [func:{name:}{size:-1}
            {params:}
            {local:}]->[int]

[func:{name:main}{size:-1}
    {params:}
    {local:
        [var@7360d70:h :: [ptr]->
                [func:{name:}{size:-1}
                    {params:}
                    {local:}]->[int]],
        [var@7360c00:f :: [ptr]->
                [func:{name:}{size:-1}
                    {params:}
                    {local:}]->[int]],
        [var@7360a00:a3 :: [ptr]->[ptr]->[int]],
        [var@7360820:a2 :: [arr:{len:20}{size:80}]->[ptr]->[int]],
        [var@7360640:a1 :: [ptr]->[arr:{len:20}{size:-1}]->[int]],
        [var@7360460:a0 :: [arr:{len:10}{size:800}]->[arr:{len:20}{size:80}]->[int]],
        [var@7360110:a :: 
            [struct@735da40:{name:A}{size:20}{fields:
                [var@735d9b0:b :: 
                    [struct@735b730:{name:B}{size:8}{fields:
                        [var@735d7d0:i :: [int]],
                        [var@735d8b0:j :: [int]]}]],
                [var@735b5c0:x :: [int]],
                [var@735b6a0:y :: [int]],
                [var@735db50:next :: [ptr]->
                        [struct@735da40:{name:A}]]}]]}]->[int]

    \end{BVerbatim}
    \caption {CIBIC Dump: Complex Declaration}
\end{figure}

Accompanied by complex type declaration, complex type casting is also allowed in
CIBIC. In the code above, an integer \texttt{0x12345678} is casted into a
pointer to a function with empty parameter list returning an integer, and assign
to function pointer f. Note that in order to deal with the form like
``\texttt{(int (*)())}'', syntax description in ``\texttt{cibic.y}'' is rewritten
according to the standard and made more general.

Function pointers are easy to implement in MIPS assembly. But their declarations
could be more complex and esoteric than we expect it to be. Although these
constructions are rarely used, the compilers that support function pointer are
supposted to understand them. For example, ``\texttt{int (*g(int
***e[10]))();}'' declares a function g which takes an array of pointers as
parameters and returns a function pointer. The code below demonstrates a
non-typical use of function pointer. It can be compiled correctly by CIBIC. When
x is non-zero, the program prints ``i'm f'' five times, otherwise, prints ``i'm
g''. Note that we make use of the language feature of C that the empty parameter
list means uncertain number of parameters, so that f and g can pass func itself
to the invocation of func.
\begin{listing}[H]
    \centering
    \RecustomVerbatimEnvironment{Verbatim}{BVerbatim}{}
    \begin{minted}{c}
typedef void (*Func_t)();
void f(Func_t func, int step) {
    if (!step) return;
    printf("i'm f\n");
    func(func, step - 1);
}
/* void (*func)() has the same meaning as Func_t func */
void g(void (*func)(), int step) {
    if (!step) return;
    printf("i'm g\n");
    func(func, step - 1);
}
int main() {
    void (*func)(void (*ifunc)(), int step);
    int x = 1;
    if (x) func = f;
    else func = g;
    func(func, 5);
    return 0;
}
    \end{minted}
    \caption {Self-reference function pointer}
\end{listing}
\section{Intermediate Representation}
A good IR (intermediate representation) should be both easy to modify (or
optimize) and convenient to be transformed into assembly. A typical bad design
is to make up an IR that totally resembles assembly instructions. This does not
make much sense because when IR almost looks like assembly, we actually do not
need IR at all, even though this makes it easier to translate. Moreover, if IR
to assembly is a ``one-to-one correspondence'', we can not benefit much from
the IR in the optimization, even suffer from debugging since one semantically
clear operation may be splitted into several confusing assembly-like IR
instructions.

In CIBIC, there are mainly three kinds of IR instructions: flow control,
assignment and calculation. For example, \texttt{BEQ}, \texttt{BNE},
\texttt{GOTO}, \texttt{RET}, and \texttt{CALL} are flow control instructions;
\texttt{ARR}, \texttt{WARR}, \texttt{MOVE} are assignment instructions;
\texttt{MUL}, \texttt{DIV}, \texttt{ADD}, \texttt{SUB}, etc. are calculation
instructions. There are also a few special types of instructions, like
\texttt{PUSH}, \texttt{LOAD}. \texttt{PUSH} indicates an argument is pushed to
the stack. \texttt{LOAD} is just a ``pseudo-instruction'', it is only designed
for helping the unification of SSA form because every variable needs to be
defined somewhere. So local variables are parameters are first ``loaded'' at the
beginning of a function. Therefore for some variables \texttt{LOAD} does not
need to be translated into a de facto load instruction (for example, spilled
variables). All kinds of instructions used in IR is shown in table.
\begin{center}
    \texttt {
    \begin{longtable}{|r|c|c|c|l|}
            OpCode  &  Dest.    &  Src. 1  &  Src. 2  &   Explanation \\  \hline
            BEQ     &  block    &  cond    &  val     &   if (cond == val) goto block \\
            BNE     &  block    &  cond    &  val     &   if (cond != val) goto block \\
            GOTO    &  block    &  NULL    &  NULL    &   goto block \\
            CALL    &  ret      &  func    &  NULL    &   ret = call func \\
            RET     &  NULL     &  ret     &  NULL    &   return ret \\  \hline
            PUSH    &  NULL     &  arg     &  NULL    &   push arg \\
            LOAD    &  var      &  NULL    &  NULL    &   load var \\  \hline
            ARR     &  var      &  arr     &  index   &   var = arr[index] \\
            WARR    &  arr      &  var     &  index   &   arr[index] = var \\
            MOVE    &  var1     &  var2    &  NULL    &   var1 = var2 \\  \hline
            ADDR    &  var1     &  var2    &  NULL    &   var1 = addr var2 \\
            MUL     &  res      &  var1    &  var2    &   res = var1 * var2 \\
            DIV     &  res      &  var1    &  var2    &   res = var1 / var2 \\
            MOD     &  res      &  var1    &  var2    &   res = var1 \% var2 \\
            ADD     &  res      &  var1    &  var2    &   res = var1 + var2 \\
            SUB     &  res      &  var1    &  var2    &   res = var1 - var2 \\
            SHL     &  res      &  var1    &  var2    &   res = var1 << var2 \\
            SHR     &  res      &  var1    &  var2    &   res = var1 >> var2 \\
            AND     &  res      &  var1    &  var2    &   res = var1 \& var2 \\
            XOR     &  res      &  var1    &  var2    &   res = var1 \^{} var2 \\
             OR     &  res      &  var1    &  var2    &   res = var1 | var2 \\
            NOR     &  res      &  var1    &  var2    &   res = var1 nor var2 \\
             EQ     &  res      &  var1    &  var2    &   res = var1 == var2 \\
             NE     &  res      &  var1    &  var2    &   res = var1 != var2 \\
             LT     &  res      &  var1    &  var2    &   res = var1 < var2 \\
             GT     &  res      &  var1    &  var2    &   res = var1 > var2 \\
             LE     &  res      &  var1    &  var2    &   res = var1 <= var2 \\
             GE     &  res      &  var1    &  var2    &   res = var1 >= var2 \\
            NEG     &  res      &  var1    &  NULL    &   res = -var1 \\
        \end{longtable}
    }
\end{center}

Here are some remarks:
\begin{enumerate}
    \item Because C standard requires shortcuit of ``\texttt{\&\&}'' and
        ``\texttt{||}'' operator, they are transformed into branches, will not
        be shown in the IR.

    \item Multi-dimensional arrays require a little more care. In C, all arrays
        are treated as one-dimensional array in the end. For instance,
        \texttt{a[2][3][4]} (\texttt{a} is declared as \texttt{int a[5][5][5]})
        is transformed into \texttt{*(a + 2 * 100 + 3 * 20 + 4 * 4)}, so its IR,
        for example could be:
\begin{center}
    \texttt{
        \begin{tabular}{l}
            t5 = a\_0 + 200 \\
            t3 = t5 + 60 \\
            b\_1 = t3[16] \\
        \end{tabular}
    }
\end{center}
\item Pointer dereference such as \texttt{a = *ptr} can be easily represented by
    \texttt{a = ptr[0]}.
\item Since structs and unions can not be entirely stored in a register, CIBIC
    regard a instance of a struct or union as a pointer to it. Since the memory
    offset of an attribute can be determined after semantics analysis, access to
    a struct (or union) can be represented in the same way as array:
    \begin{center}
        \begin{minipage}{0.3\textwidth}
            \begin{minted}{c}
struct A {
    struct B {
        int i, j;
    } b;
    int x, y;
} a, a2;
int main() {
    struct B b;
    a.b.i = 1;
    a.b.j = 2;
    a.x = 3;
    a.y = 4;
    a2.b = b;
    a.b = a2.b;
}
            \end{minted}
        \end{minipage}
        \begin{minipage}{0.3\textwidth}
            \begin{BVerbatim}
t1 = a_0 + 8
t1[4] = 1
t4 = t1
t4[0] = 2
a_0[4] = 3
a_0[0] = 4
a2_0[8] = b_0
t12 = a2_0 + 8
a_0[8] = t12
        \end{BVerbatim}
        \end{minipage}
    \end{center}
    The only problem left is the ambiguity. If we regard a instance of a struct
    as a pointer to it, how could we distinguish a struct copy assignment from
    a struct pointer assignment? The answer is: this is not an ambiguity at
    all, since all the type information of operands are preserved, we can
    easily tell the difference by looking at type information. So actually, the
    printed IR above does not contain all the information, it is just a human
    readable form to easy our debug. The underlying type information is
    preserved in IR data structure and passed to the translator so can be used
    to guide the final translation. Of course, the code above does produce
    correct result compiled by CIBIC.
\end{enumerate}

\begin{listing}[H]
    \centering
    \RecustomVerbatimEnvironment{Verbatim}{BVerbatim}{}
    \begin{minted}{c}
calc_dominance_frontier();
/* build SSA */
insert_phi(vars);
renaming_vars(oprs);
/* optimization on SSA */
const_propagation();
subexp_elimination();
const_propagation();
strength_reduction();
deadcode_elimination();
/* out of SSA */
mark_insts();
build_intervals();
register_alloc();
    \end{minted}
    \caption{Workflow of IR in CIBIC}
    \label{list:workflow}
\end{listing}

\subsection{Single Static Assignment Form}
CIBIC makes good use of SSA (Single Static Assignment) form. SSA form is a
property of an IR, which says that each variable is assigned \textbf{exactly
once}. The property can simplify the liveness analysis and optimization, since
all variables are assigned only once so the ``define-use'' relationship is much
clearer that the original IR.

However, it is not trivial to convert an IR to SSA form, mainly because of the
``merging issue''. In figure \ref{fig:phi_function}, the control flow branches
at the \texttt{if} statement and merges again when getting out of if. The
question is, should we use \texttt{x\_1} or \texttt{x\_2} in the \texttt{y = x
+ 1} statement? The answer is, it is only known at runtime. So a
``phi-function'' \texttt{x\_3 = phi(x\_1, x\_2)} will be inserted at the merge
point to wrap two possibilities.  Unfortunately, not only does this
circumstance appear in if statement, but also exist in loops. How do we know
where we should add an phi-function for certain variable? The answer is we can
just insert phi-functions at dominance frontiers in the control flow graph.
\subsection{Phi-functions}
There are several ways of computing dominance frontiers of a control flow
graph.  But they all first construct the dominator tree and then deduce the
frontiers.  Well-known algorithms for finding out the dominator tree are the
straightforward iterative algorithm and Lengauer-Tarjan algorithm. The improved
version on latter algorithm provides with a nearly linear time complexity $O(m
\alpha(m, n))$. However, according to the research \cite{tarjan06} done by L.
Georgiagids, R.  F. Werneck, R. E. Tarjan et al, practical performance of
iterative algorithm is acceptable and even better than sophisticated LT
algorithm. CIBIC adopts a variant \cite{cooper01} of the original iterative
algorithm. It is faster than LT algorithm on real programs and easy to
implement.
\begin{figure}
    \centering
    \begin{minipage}{0.4\textwidth}
        \includegraphics[scale=0.5]{phi1.png}
    \end{minipage}
    \begin{minipage}{0.4\textwidth}
        \includegraphics[scale=0.5]{phi2.png}
    \end{minipage}
    \caption{Before and After Inserting Phi-function}
    \label{fig:phi_function}
\end{figure}
\subsection{Register Allocation}
CIBIC uses linear scan register allocation \cite{moe02} to allocate registers
\emph{before translating out of SSA form}. This method is different from
traditional one and can make use of lifetime holes and instruction weights to
improve the quality of the allocation.

To run the allocation algorithm, we shall first compute live intervals.
Unfortunately, the pseudo-code provided in the paper \cite{moe02} does not take
the loop cases into account. In another paper \cite{wimmer10}, I found the
correct algorithm for coping with loops. Unfortunately, the pseudo-code in two
papers are written in different forms and have different concepts in some
details. So I learned from both of them and got my own algorithm (almost like
the one in paper \cite{moe02}). Since the graph is traversed \textbf{only
once}, the implementation is quite efficient (the traditional method for
non-SSA IR requires iteration thus the time complexity is not guaranteed).

In linear scan algorithm described in paper \cite{moe02}, we should maintain
four sets: unhandled, handled, active, inactive. However, for the
implementation, we do not need to maintain handled set because once a variable
is handled, we can just evict it from the current active or inactive set and
there is no need to put it again into another handled set. Besides, the
unhandled set can be implemented as a sorted array, because intervals are
picked in increasing order of their start points. Therefore, in CIBIC, only
active and inactive sets are maintained by double-linked lists with sentinel
nodes. The double-linked design makes it easy to remove an interval from the
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{Compilation Speed}
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 compilation speed.
\subsection{Compilation 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 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 (not
fully implemented) inline optimization 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 argue that all test cases provided 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 \texttt{if} statement or loops (except
test case: ``superloop''). Therefore, the advantage of SSA (especially the
advanced register allocation algorithm) is not shown very well.

\begin{figure}[H]
    \centering
    \includegraphics[scale=0.5]{all.png}
\end{figure}
\begin{figure}[H]
    \centering
    \includegraphics[scale=0.5]{all2.png}
\end{figure}
\begin{figure}[H]
    \centering
    \includegraphics[scale=0.5]{all3.png}
\end{figure}

The above figures show the ``normalized instruction'' for each compiler
implementation with respect to different test cases. The ``normalized
instruction'' is obtained by dividing the number of instructions by the best
for the same test case, thus the lower, the better. There are 40 test cases
taken into account. Some good implementations are picked out and bolded in the
figures, while others are simply colored gray.

Although CIBIC does not generate the best code in some test cases, the overall
code quality is very good. Moreover, CIBIC has not implemented inline
optimization yet. As I know, compilers that are presented in bolded lines in
the second and the third figure all implement inline optimization, and before
the optimization, their performance are not as good as CIBIC. Therefore CIBIC
could do much more better.

\subsection{Optimization}
CIBIC implements the following optimizations: 
\begin{itemize}
    \item constant propagation
    \item dead code elimination
    \item strength reduction
    \item common subexpression elimination
\end{itemize}

Unfortunately, these optimization do not seem 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 techniques 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}.

Constant propagation could be safely applied if there were not any indirect
modification to the propagated variable. Unfortunately, this is not always true.
A typical indirection modification is via calling a function which modifies a
global variable. Because of the function call, the modification is hidden from
the compiler. Another common indirect modification is done via a pointer. A
direct approach to get over these problem is to prevent the propagation over a
function call and to mark those variable whose address is being referenced (by
``\texttt{\&}'' operator) to disable the propagation of their value.

The same things may also happen in common subexpression elimination. The code
below demonstrates two typical situations in which the aggressive elimination
may produce a wrong result.
\begin{figure}[H]
    \begin{minipage}{0.4\textwidth}
        \RecustomVerbatimEnvironment{Verbatim}{BVerbatim}{}
    \centering
        \begin{minted}{c}
int N = 0;
void f() { N = 2; }
int main() {
    int a, b;
    a = N + 1;
    f();
    b = N + 1;
    printf("%d\n", b); /* 3 */
}
        \end{minted}
    \end{minipage}
    %    \centering
    \begin{minipage}{0.5\textwidth}
        \RecustomVerbatimEnvironment{Verbatim}{BVerbatim}{}
        \centering
\begin{minted}{c}
    int flag = 0;
    int check(int x, int y) {
        return x > 0 && y > 0 && (flag ^= 1);
    }
    int main() {
        int x = 1, y = 2;
        printf("%d\n", check(x, y)); /* 1 */
        printf("%d\n", check(x, y)); /* 0 */
        printf("%d\n", check(x, y)); /* 1 */
    }
\end{minted}
    \end{minipage}
    \label{fig:cse}
\end{figure}
Global common subexpression elimination should be performed while walking down
the dominator tree \cite{sassa07}. Luckily, The dominator tree can be easily
obtained because it is an important by-product of SSA construction. 

In CIBIC, all optimizations need to be performed only once or twice as shown in
listing \ref{list:workflow}. Because the implemented optimizations do not
require iteration.

\section{Conclusion}
CIBIC is a simple but efficient C compiler implementation in C. It supports key
characteristics of C language such as structs/unions, arrays, and various type
of pointers. \texttt{typedef}, a very useful syntactic sugar is also
implemented in CIBIC. Furthermore, CIBIC makes use of SSA to generate code of
decent quality. As a lightweight compiler, it compiles much faster than gcc
(gcc implements a lot more features though).

Some standard syntax and features written in C are not supported by CIBIC:
\texttt{enum}, \texttt{switch}, linking, preprocessing (such as
\texttt{\#define}), etc. However, it is very possible to extend CIBIC to
support these features. Some, for example \texttt{switch} statements are easy
to be added.
\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
        (2006): 69-94.
    \bibitem{cooper01}
        Cooper, Keith D., Timothy J. Harvey, and Ken Kennedy. ``A simple, fast
        dominance algorithm.'' Software Practice \& Experience 4 (2001): 1-10.
    \bibitem{moe02}
        M\"ossenb\:ock, Hanspeter, and Michael Pfeiffer. ``Linear scan register
        allocation in the context of SSA form and register constraints.''
        Compiler Construction.  Springer Berlin Heidelberg, 2002.
    \bibitem{wimmer10}
        Wimmer, Christian, and Michael Franz. ``Linear scan register allocation
        on SSA form.'' Proceedings of the 8th annual IEEE/ACM international
        symposium on Code generation and optimization. ACM, 2010. 
    \bibitem{sassa07}
        Tokyo Institute of Technology. Optimization in Static Single Assignment
        Form
\end{thebibliography}
\end{document}