diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/all.gp | 61 | ||||
| -rw-r--r-- | doc/cibic.pdf | bin | 0 -> 683955 bytes | |||
| -rw-r--r-- | doc/cibic.tex | 925 | ||||
| -rw-r--r-- | doc/conv.py | 20 | ||||
| -rw-r--r-- | doc/g1.gv | 10 | ||||
| -rw-r--r-- | doc/g2.gv | 10 | ||||
| -rw-r--r-- | doc/g3.gv | 16 | ||||
| -rw-r--r-- | doc/res.csv | 35 |
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 Binary files differnew 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 |