move docs to a seperate dir

8 files changed, 1077 insertions, 0 deletions

diff --git a/doc/all.gp b/doc/all.gp
new file mode 100644
index 0000000..ad0322d
--- /dev/null
+++ b/doc/all.gp
@@ -0,0 +1,61 @@
+reset
+# define axis
+# remove border on top and right and set color to gray
+set style line 11 lc rgb '#808080' lt 1
+set border 3 back ls 11
+set tics nomirror
+# define grid
+set style line 12 lc rgb '#808080' lt 0 lw 1
+set grid back ls 12
+
+set style line 11 linecolor rgb '#dd181f' linetype 1 linewidth 2  # red
+set style line 13 linecolor rgb '#aaaaaa' linetype 1 linewidth 1  # red
+set style line 12 linecolor rgb '#0060ad' linetype 1 linewidth 2  # blue
+
+set style line 1 lc rgb '#800000' lt 1 lw 2
+set style line 2 lc rgb '#ff0000' lt 1 lw 2
+set style line 3 lc rgb '#ff4500' lt 1 lw 2
+set style line 4 lc rgb '#ffa500' lt 1 lw 2
+set style line 5 lc rgb '#006400' lt 1 lw 2
+set style line 6 lc rgb '#0000ff' lt 1 lw 2
+set style line 7 lc rgb '#9400d3' lt 1 lw 2
+
+set border lw 2
+set title "Normalized Benchmark Result of the Test Cases"
+set terminal "pngcairo" size 800, 480 enhanced
+set key top left
+set output "all.png"
+set xlabel "Test Cases"
+set ylabel "Normalized Instruction (self / best)"
+set xrange [:39]
+set yrange [:10]
+plot for [i=2:35] 'all.csv' u :((column(i))) with lines ls 13 title '', \
+    for [i=6:6] 'all.csv' u :((column(i))) with lines ls 11 title 'zzy7896321', \
+    for [i=5:5] 'all.csv' u :((column(i))) with lines ls 7 title 'ascii991218', \
+    for [i=1:1] 'all.csv' u :((column(i))) with lines ls 12 title 'Determinant (CIBIC)'
+
+set border lw 2
+set title "Normalized Benchmark Result of the Test Cases"
+set terminal "pngcairo" size 800, 480 enhanced
+set key top left
+set output "all2.png"
+set xlabel "Test Cases"
+set ylabel "Normalized Instruction (self / best)"
+set yrange [:10]
+plot for [i=2:35] 'all.csv' u :((column(i))) with lines ls 13 title '', \
+    for [i=4:4] 'all.csv' u :((column(i))) with lines ls 5 title 'cycycy', \
+    for [i=3:3] 'all.csv' u :((column(i))) with lines ls 3 title 'jiziwei', \
+    for [i=1:1] 'all.csv' u :((column(i))) with lines ls 12 title 'Determinant (CIBIC)'
+
+set border lw 2
+set title "Normalized Benchmark Result of the Test Cases"
+set terminal "pngcairo" size 800, 480 enhanced
+set key top left
+set output "all3.png"
+set xlabel "Test Cases"
+set ylabel "Normalized Instruction (self / best)"
+set yrange [:10]
+plot for [i=2:35] 'all.csv' u :((column(i))) with lines ls 13 title '', \
+    for [i=7:7] 'all.csv' u :((column(i))) with lines ls 3 title 'daerduomkch', \
+    for [i=2:2] 'all.csv' u :((column(i))) with lines ls 1 title 'sadkangaroo', \
+    for [i=1:1] 'all.csv' u :((column(i))) with lines ls 12 title 'Determinant (CIBIC)'
diff --git a/doc/cibic.pdf b/doc/cibic.pdf
new file mode 100644
index 0000000..7daaf46
--- /dev/null
+++ b/doc/cibic.pdf
diff --git a/doc/cibic.tex b/doc/cibic.tex
new file mode 100644
index 0000000..2e14dc0
--- /dev/null
+++ b/doc/cibic.tex
@@ -0,0 +1,925 @@
+\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}
diff --git a/doc/conv.py b/doc/conv.py
new file mode 100644
index 0000000..4689d9b
--- /dev/null
+++ b/doc/conv.py
@@ -0,0 +1,20 @@
+from sys import stdout
+f = open("res.csv", "r")
+matrix = list()
+for line in f.readlines():
+    matrix.append([float(x) for x in line.split()[1:]])
+col = len(matrix[0])
+row = len(matrix)
+inf = 1e9
+for j in xrange(col):
+    best = inf
+    for i in xrange(row):
+        if matrix[i][j] < best:
+            best = matrix[i][j]
+    for i in xrange(row):
+        if matrix[i][j] > inf:
+            r = '-'
+        else:
+            r = str(matrix[i][j] / best)
+        stdout.write('{0} '.format(r))
+    stdout.write('\n')
diff --git a/doc/g1.gv b/doc/g1.gv
new file mode 100644
index 0000000..e762143
--- /dev/null
+++ b/doc/g1.gv
@@ -0,0 +1,10 @@
+digraph G {
+    a [shape = box, fontname = "monospace", label = "a = x_0\nif (a == 0) goto _L1"];
+    b [shape = box, fontname = "monospace", label = "x_1 = 1"];
+    c [shape = box, fontname = "monospace", label = "x_2 = 2"];
+    d [shape = box, fontname = "monospace", label = "y_0 = x_? + 1"];
+    a -> b;
+    a -> c;
+    b -> d;
+    c -> d;
+}
diff --git a/doc/g2.gv b/doc/g2.gv
new file mode 100644
index 0000000..76f9340
--- /dev/null
+++ b/doc/g2.gv
@@ -0,0 +1,10 @@
+digraph G {
+    a [shape = box, fontname = "monospace", label = "a = x_0\nif (a == 0) goto _L1"];
+    b [shape = box, fontname = "monospace", label = "x_1 = 1"];
+    c [shape = box, fontname = "monospace", label = "x_2 = 2"];
+    d [shape = box, fontname = "monospace", label = "x_3 = phi(x_1, x_2)\ny_0 = x_3 + 1"];
+    a -> b;
+    a -> c;
+    b -> d;
+    c -> d;
+}
diff --git a/doc/g3.gv b/doc/g3.gv
new file mode 100644
index 0000000..7dcf088
--- /dev/null
+++ b/doc/g3.gv
@@ -0,0 +1,16 @@
+digraph G {
+    a [shape = box, fontname = "monospace", label = "struct A"];
+    b [shape = box, fontname = "monospace", label = "b :: struct B"];
+    c [shape = box, fontname = "monospace", label = "i :: int"];
+    d [shape = box, fontname = "monospace", label = "j :: int"];
+    e [shape = box, fontname = "monospace", label = "x :: int"];
+    f [shape = box, fontname = "monospace", label = "y :: int"];
+    g [shape = box, fontname = "monospace", label = "next :: ptr"];
+    a -> b;
+    b -> c;
+    b -> d;
+    a -> e;
+    a -> f;
+    a -> g;
+    g -> a;
+}
diff --git a/doc/res.csv b/doc/res.csv
new file mode 100644
index 0000000..f1511dc
--- /dev/null
+++ b/doc/res.csv
@@ -0,0 +1,35 @@
+Determinant	268281	16494	485659	1326	145	231	141295	45550	171228	6197660	19	8647871	11943104	11293887	1202	71	707368	137	92	5605161	2562	5413	71	5383633	35	2046880	1968964	1332549	90066	358747	35	12492	89	59420	321	791769	1485528	3839587	587055	2942
+sadkangaroo	470199	12649	898668	12350	129	219	147434	48101	144124	9388990	17	5877835	8009492	9766599	1484	53	780277	131	76	6519697	2298	6224	77	9056881	47	2791288	2714008	1814324	81927	463938	26	6664	87	54927	128	744401	1364259	2691339	756016	2047
+jiziwei	284216	10980	481228	1297	124	208	174060	67544	142831	4988517	24	4796844	6558290	5984933	1179	75	665791	140	94	5190729	2283	5241	80	5394620	42	1863026	1787792	1373720	71398	352601	31	4899	106	62210	332	631716	1212686	2756245	480511	1797
+cycycy	331217	11680	564306	1340	146	230	155629	59368	172926	4630634	19	5051047	6255575	5504193	1605	75	917197	144	89	7307155	2498	5843	86	5949300	45	2062617	2021613	1439816	77747	459854	32	7450	84	36443	135	446812	1258157	3052422	649203	2303
+ascii991218	288191	12786	705286	1623	201	338	479133	168852	241329	5585522	28	3126726	6162973	4633633	2557	231	620133	525	86	6851891	4486	8533	260	4825010	133	1965883	2088031	1751200	90284	416151	57	21271	337	37794	225	831578	1728096	4864778	729995	3974
+zzy7896321	383297	15655	785716	24611	176	342	464800	168334	220835	8855289	124	6569724	6559649	5471018	2704	200	738033	447	114	9233836	4737	13923	247	6795825	139	2530006	2669110	2090170	94209	564013	57	19258	300	74171	381	1678583	1849356	4074810	871775	2633
+daerduomkch	360851	11074	679049	24554	146	243	186332	55772	162732	10723526	17	5117455	6144778	4528962	1690	41	969307	99	51	9599628	2985	5667	90	6523359	38	2793026	2820074	1708889	98393	589751	22	5629	127	42972	154	1794890	1682582	3310164	791286	2163
+memed4	1122293	25427	1756161	61182	251	403	468901	179596	509043	26459267	142	15400559	17510980	14272589	5527	219	2437917	490	152	23633204	8904	24545	255	17828124	174	6257039	6318863	5413898	165645	1656189	70	23372	431	109590	467	12040545	1697774	8591008	2541068	5956
+zhenni	4001975	30616	2395281	73507	255	395	208876	70112	722757	39849797	21	19568821	20518715	16281392	5906	98	4018808	210	178	27947957	8072	15797	125	29122931	74	8578522	8435554	7053654	238462	2248071	38	11831	246	130253	251	13480362	1909962	12103870	3024798	7347
+ihsgnef	521372	18136	1041606	24718	226	539	835416	288025	453059	13256699	28	8878523	10600276	9508158	2395	129	1252129	229	165	9612781	4016	9173	445	12457069	66	3580272	3764562	2775072	143282	747744	52	11058	430	54566	484	1811855	2319252	6520725	1260326	5307
+CosineUFO	844811	23186	1483171	22246	291	512	776032	272731	531049	17051343	28	11029509	16579517	12317195	5414	403	1784145	984	210	20463491	7645	10570	401	11906509	237	4151519	4488323	4030907	131818	1009844	113	44846	567	183731	1310	2777697	2364784	8832396	1356606	5514
+anshantby	583673	20654	1024584	36957	205	362	481182	178572	373231	14437588	23	9695213	11460532	9509303	3903	220	1730954	524	140	14176243	6448	7442	254	7653301	133	4001613	4094031	2861491	107023	953347	67	25091	357	70935	256	1960305	1788724	6340878	1297663	4834
+chenhao94	465285	16417	1056385	24551	187	282	505748	177541	267830	13824500	27	8262142	10447786	8355638	3556	236	1066463	564	130	9279591	5293	9627	264	8221219	142	3105464	3263888	2519281	94402	660824	71	26347	333	54602	238	888285	1728094	3959936	950972	4104
+Ander_cxt	535713	23975	1308422	34295	268	467	550781	195954	458526	16585195	21	15011117	20356849	18963807	4243	247	1936474	550	129	13578901	7437	12951	263	9640619	142	4562515	5126835	3259462	169934	1017081	70	34810	369	90249	439	2683596	2804309	10214630	1220665	6162
+secret_jc	509414	20833	1032817	9999999999	196	353	477082	178047	326030	14060851	26	11791076	12201587	9762270	3610	201	1163982	519	136	13772172	6557	11150	241	7088497	122	3870415	3974743	2416124	102811	766429	64	23859	312	49345	222	3809409	1621980	5306539	1101573	4434
+yefllower	430697	21880	950581	24595	148	273	202725	60891	336840	14819073	30	17365922	11104542	9443050	2283	86	1912437	167	113	11059701	4348	6588	84	14394218	47	3694032	3572748	2625333	96248	797683	45	18751	170	65251	182	8339213	1909961	6601444	1030081	3787
+brokenwing	1079596	16705	1078990	48594	171	310	153621	58923	339147	17480170	47	9145193	13132491	9934065	2560	108	1301212	181	123	14589216	3739	7868	131	15837018	77	3620494	3550946	3113246	134435	863923	41	13608	143	69905	172	1652482	1424901	6192584	1409597	3989
+xkszltl	488632	14816	797865	45701	191	297	204767	66005	282733	12915475	24	9103929	11075264	9265186	2014	78	1344746	132	92	11096063	3300	6565	69	7357900	43	3349899	3310623	2149421	111946	815466	37	7980	94	55553	157	2284180	2122175	5776130	947280	2345
+legendks	388745	26604	1112460	29506	246	430	755545	266075	381136	15634662	27	8999685	11834207	9602198	4748	401	1341965	996	198	14479612	6374	8997	386	6823843	245	3196170	3640530	3185526	123026	708951	108	45059	532	84292	334	2459707	1894868	6062020	1129659	4117
+chensqi	684242	18755	1106124	24805	342	564	796502	282444	501643	14792603	34	12202663	16775258	14134864	2825	113	1978635	297	183	16802641	4880	6850	405	8792849	54	4576597	4490821	2645024	168010	951568	127	11043	602	164880	735	3663430	2592153	8965363	1081518	5381
+ahaha	1557116	25046	1953240	61237	277	450	608131	225139	524652	24875984	191	13354044	15820676	13011725	5887	347	2039020	750	176	17767969	9919	33614	308	17257118	300	5928682	6148930	4892988	167761	1555740	94	35188	463	122618	300	2014584	1879696	9091694	1978987	5294
+jcAngel	531963	18456	1120397	36874	261	445	698217	261453	385529	13288033	22	9482225	13290187	11390251	4402	308	1339473	780	153	13139255	6554	7075	329	8780947	170	3748959	3976935	2867850	125056	764751	96	37402	462	76987	284	2271155	1955487	6764684	1048599	5373
+cheezer	328144	19357	1139114	24682	265	482	755567	266097	368443	11554324	34	7632821	11877529	9785395	4717	413	1127480	1026	235	14228028	6555	8600	403	7661063	251	3114795	3528243	2783799	102669	652959	119	44575	560	52560	324	2091470	1940369	5700312	883490	4273
+rauledly	473573	16459	887400	36983	173	417	655227	238392	245329	12924369	23	8215336	11741986	9911883	2398	80	1322793	190	143	13106114	4606	7355	337	7091442	59	3677902	3739726	2073771	113033	751064	39	9748	409	56884	165	1246729	2061551	5342105	1030745	4097
+ImaginationZ	607018	22789	1375347	24760	299	525	776032	271198	493550	15679696	27	11559931	14484392	12382296	5225	401	1622480	972	200	19328674	7220	9472	401	8802260	232	3938547	4271487	3712285	129482	929087	114	44066	545	174271	1285	3130164	2425417	8580877	1289876	5306
+Goblin911	300080	22316	1420994	29532	276	527	479154	182683	432054	17667024	148	11564367	16319729	14060264	4328	258	1509277	556	194	10125299	7571	13232	256	7953657	189	4765210	4722706	3699098	143135	711610	84	25423	353	96452	342	4000061	2364751	6321983	1544579	4968
+airsplay	478216	16419	1008165	36872	191	357	452518	169879	369027	14984924	20	8649573	10636004	8726018	3855	210	1332760	482	119	13645396	5807	7939	282	11314739	125	3762378	3940122	3270509	112428	779524	66	23072	350	67434	407	3674745	1258185	5383595	1218763	3837
+HeavnFeel	340959	19278	938132	12623	222	420	751452	278857	351148	10445082	64	10684213	21092476	19573368	3936	347	1195184	907	173	7930250	5755	12342	403	6241312	224	2744485	3034285	2395254	100595	647934	106	42818	527	56932	311	1846413	1606861	5340884	723828	4545
+zeonsgtr	547042	26519	1139159	24732	219	392	595841	232806	410746	12719690	27	10122991	12064708	10502983	3637	261	1512076	631	157	8830185	5529	13299	312	12440727	172	3567612	3655848	3048731	139243	840860	77	30782	374	76289	337	2232866	2016097	6249557	1165632	4724
+ywk248248	412747	20342	995257	48979	203	392	554891	212335	364432	12486962	184	8708067	12720739	9342514	3633	261	1385347	614	164	14652938	5934	21673	320	8217968	192	3188347	3351499	2751094	108747	913345	83	29267	397	97436	453	2517013	1637153	6202017	984445	4875
+vegetable_h	399656	19040	783136	12409	188	298	178154	55273	258240	11054537	25	11881402	16716027	16107571	1797	84	1229420	161	102	7255066	3099	6605	87	7374236	53	3443359	3253387	1997461	96265	573637	47	17933	104	67043	201	706397	1955439	5362620	850065	3335
+sy15	513364	18916	1214719	36836	201	349	466848	173977	382227	15186142	22	8069137	11187260	9037522	3500	197	1343493	484	122	13636943	5527	6820	267	13295916	119	3958250	4040576	3540431	137212	787763	69	24076	353	59690	166	1374554	1743244	5865837	1272769	4346
+rowdark	297263	18745	932704	24718	259	468	665479	232330	363255	9767039	36	7377854	10118223	9244589	4468	380	1040435	912	227	9738511	6655	7015	374	5684271	223	3020933	3351737	2572764	106841	594827	113	39458	538	57021	424	2092902	1940361	5773447	892914	4243
+swrrt_11	447661	16178	1701756	25763	186	289	237535	83413	515033	12584940	65	8179285	12369655	21457419	4974	103	1545734	180	98	11884105	16122	13181	219	8212313	61	4180943	3152282	3694545	122789	949240	47	17607	497	4634	654	9638242	1743221	50362061	1111851	9140
+ACMlzb	431740	19407	1087170	32147	203	348	466840	173439	351835	12600060	18	9612715	13325041	11075545	3519	194	1415982	499	137	15711998	6075	7864	227	7091563	105	3884590	3973462	2450646	110653	903861	59	27184	299	53531	213	13487080	1788712	5944893	1123313	4795