demo/neatcc.ms

   1 .\" PSTITLE: The NEATCC C Compiler
   2 .so neat__.ms
   3 .ds en.cl "#468
   4 .post.info Title "The NEATCC C Compiler"
   5 .post.info Author "Ali Gholami Rudi"
   6 .de uc
   7 \s-1\\$1\s+1
   8 ..
   9 .chop uc
  10 .de cc
  11 \s-1\f(CB\\$1\fP\s+1
  12 ..
  13 .de IP
  14 .       br
  15 .       RT
  16 .       if \\n(.$>1 .nr en.ip \\$2
  17 .       in +\\n[en.ip]u
  18 .       ie \\w'\\$1'<\\n[en.ip] \h'|-\\n[en.ip]u'\\$1\h'|0i'\c
  19 .       el \h'|-\\n[en.ip]u'\\$1
  20 ..
  21 .chop cc
  22 .HD
  23 .TL
  24 \s+8The \*[uc NEATCC] C Compiler\s-8
  25 .AU
  26 \fIAli Gholami Rudi\fP
  27 .sp 3
  28 .LP
  29 \*[uc NEATCC] is a small C compiler that implements a large subset of
  30 \*[uc ANSI] C.  Despite its size, \*[uc NEATCC] implements effective
  31 optimizations and generates code for different architectures.  In this
  32 document, I shall briefly introduce \*[uc NEATCC], its intermediate code,
  33 its final code generation interface, and some other details that
  34 seem helpful for inspecting its source code and extending it.
  35
  36 .SH "Overview"
  37 In \*[uc NEATCC], compilation phases are implemented in different
  38 source files, which use the interfaces declared in ncc.h to
  39 interact.  The main components of \*[uc NEATCC] are implemented
  40 in the following files.
  41
  42 .sp
  43 .RS
  44 .IP cpp.c 1i
  45 Preprocessing.
  46 .IP tok.c
  47 Tokenisation.
  48 .IP ncc.c
  49 Parsing and directing compiler phases.
  50 .IP int.c
  51 Intermediate code generation.
  52 .IP gen.c
  53 Register allocation and sending intermediate code to backends.
  54 .IP reg.c
  55 Global register allocation.
  56 .IP x64.c
  57 Final code generation (x86.c and arm.c as well).
  58 .RE
  59
  60 .sp
  61 .LP
  62 Most \*[uc NEATCC] optimizations are performed on the intermediate
  63 code (implemented in int.c), such as using instruction immediates,
  64 removing unused values, or constant folding; they are enabled when the
  65 optimization level is at least one.  For global register allocation,
  66 \*[uc NEATCC] performs liveness analysis for local variables when the
  67 optimization level is two; level one enables a simpler register
  68 allocation algorithm and zero disables global register allocation
  69 altogether.
  70
  71 .SH "Intermediate Code"
  72 \*[uc NEATCC]'s parser (ncc.c) calls some of the functions defined in
  73 int.c (prefixed with \(lqo_\(rq), to generate the intermediate code.
  74 The latter also performs optimizations on the generated intermediate
  75 code, such as constant folding, in functions prefixed with \(lqio_\(rq.
  76 The intermediate code is stored as an array of ic struct, which is
  77 defined as follows:
  78
  79 .cc.beg
  80 .ps -1
  81 .vs -3
  82 .ta 2m 9m
  83 struct ic {
  84         long op;        /* instruction opcode */
  85         long a1;        /* first argument */
  86         long a2;        /* second argument */
  87         long a3;        /* third argument, jump target, argument count */
  88         long *args;     /* call arguments */
  89 };
  90 .cc.end
  91
  92 .sp
  93 .LP
  94 The arguments of instructions can be compiler temporaries (or
  95 intermediate values), immediates, branch instruction targets, local
  96 identifiers, and symbol identifiers.  A compiler temporary is
  97 specified as positive integer, indicating the instruction that defines
  98 them (thus, the value of compiler temporaries cannot be changed, once
  99 defined).  For instance, temporary number 5 is the output in the 5th
 100 intermediate code instruction, which may define it to be the result of
 101 adding two other temporaries.
 102
 103 Instruction opcode (\*[cc ic->op]) can be one of the macros prefixed with
 104 \(lq\*[cc O_]\(rq in ncc.h; \*[cc ic->op] also specifies the type of the operands
 105 with \*[cc O_MK] macro.
 106 .sp
 107 .IP "\*[cc "O_ADD"]:" 5m
 108 Performs addition for temporaries \*[cc ic->a1] and \*[cc ic->a2];
 109 the same applies to other binary instructions such as \*[cc O_SUB].
 110
 111 .IP "\*[cc "O_ADD|O_NUM"]:"
 112 Similar to \*[cc O_ADD] except that \*[cc ic->a2] is an immediate.
 113
 114 .IP "\*[cc "O_NEG"]:"
 115 Negates \*[cc ic->a1];
 116 the same applies to other unary instructions like \*[cc O_NOT].
 117
 118 .IP "\*[cc "O_CALL"]:"
 119 Calls a function, whose address is stored in \*[cc ic->arg1].
 120 \*[cc ic->a3] specifies the number of arguments
 121 and \*[cc ic->args] is the list of arguments.
 122
 123 .IP "\*[cc "O_CALL|O_SYM"]:"
 124 Similar to \*[cc O_CALL], except that the function is specified
 125 as a symbol identifier (instead of a temporary containing the
 126 address of the function) in \*[cc ic->a1].
 127
 128 .IP "\*[cc "O_MOV"]:"
 129 Assigns the value of \*[cc ic->a1],
 130 casting the value according to \*[cc "O_T(ic->op)"], if necessary.
 131
 132 .IP "\*[cc "O_MOV|O_NUM"]:"
 133 Like \*[cc O_MOV], but loads \*[cc ic->a1] as an immediate.
 134
 135 .IP "\*[cc "O_MOV|O_SYM"]:"
 136 Like \*[cc O_MOV], but loads the address of the given symbol
 137 \*[cc ic->a1] with offset \*[cc ic->a2].
 138
 139 .IP "\*[cc "O_MOV|O_LOC"]:"
 140 Like \*[cc O_MOV], but loads the address of the given local
 141 variable \*[cc ic->a1] with offset \*[cc ic->a2].
 142
 143 .IP "\*[cc "O_MSET"]:"
 144 Performs memset() with the given arguments.
 145
 146 .IP "\*[cc "O_MCPY"]:"
 147 Performs memcpy() with the given arguments.
 148
 149 .IP "\*[cc "O_RET"]:"
 150 Returns \*[cc ic->a1] from a function.
 151
 152 .IP "\*[cc "O_LD|O_NUM"]:"
 153 Loads the value of the address specified as \*[cc ic->a1]
 154 with offset \*[cc ic->a2];
 155 the same applies to \*[cc O_ST] for storing values, with the
 156 exception that the first argument is the destination and the
 157 second argument is the address.
 158
 159 .IP "\*[cc "O_LD|O_SYM"]:"
 160 Like \*[cc "O_LD|O_NUM"], except that \*[cc ic->a1] specifies a symbol.
 161
 162 .IP "\*[cc "O_LD|O_LOC"]:"
 163 Like \*[cc "O_LD|O_NUM"], except that \*[cc ic->a1] specifies a local.
 164
 165 .IP "\*[cc "O_JMP"]:"
 166 Unconditional branch to instruction \*[cc ic->a3].
 167
 168 .IP "\*[cc "O_JZ"]:"
 169 Conditional branch to instruction \*[cc ic->a3], if \*[cc ic->a1]
 170 is zero (\*[cc O_JNZ] for nonzero).
 171
 172 .IP "\*[cc "O_JCC"]:"
 173 Conditional branch to instruction \*[cc ic->a3], if
 174 the given relation (\*[cc "ic->op & 0x0f"]) holds for \*[cc ic->a1]
 175 and \*[cc ic->a2].
 176
 177 .SH "Stack Frame Layout"
 178 \*[uc NEATCC] uses the following stack frame layout for function.  Note
 179 that, some of these sections may be omitted for functions that do not
 180 require them.
 181
 182 .cc.beg
 183 [ STACK ARGUMENTS               ]
 184 [ SAVED REGISTER ARGUMENTS      ]
 185 [ THE PREVIOUS VALUE OF IP      ]
 186 [ THE PREVIOUS VALUE OF FP      ]  <- FP points here
 187 [ LOCAL VARIABLES               ]
 188 [ COMPILER TEMPORARIES          ]
 189 [ SAVED REGISTERS               ]
 190 [ FUNCTION ARGUMENTS            ]
 191 [ NEXT FRAME                    ]  <- SP points here
 192 .cc.end
 193
 194 .SH "Final Code Generation"
 195 The functions whose names begin with \(lqi_\(rq are the low-level
 196 architecture-specific code generation entry points.  For each output
 197 architecture, a header (e.g., x64.h) is included and these entry
 198 points are implemented in a C file (e.g., in x64.c).
 199
 200 The function \*[cc "i_reg(op, md, m1, m2, m3, mt)"]
 201 returns the mask of allowed registers for each
 202 operand of an instruction.  The first argument op, specifies the
 203 instruction (O_* macros); i_reg() sets the value md, m1, m2, and m3 to
 204 indicate the mask of acceptable registers for the destination,
 205 first, second, and third operands of the instruction.
 206 For immediates, the corresponding argument indicates the bit
 207 width of the operand (e.g., 8 means the operand is encoded in 8 bits).
 208 The value of these masks may be changed to zero to indicate fewer than three operands.
 209 If md is zero and m1 nonzero, the destination register should be equal to the first
 210 register, as is common in some \*[uc CISC] instructions.
 211 mt denotes the mask of
 212 registers that may lose their contents after the instruction.
 213 The function i_ins() generates code for the given instruction.
 214 The arguments indicate the instruction and its operands.
 215
 216 Some macros should be defined in architecture-dependent headers and a
 217 few variables should be defined for each architecture, such as
 218 tmpregs, which is an array of register numbers that can be used for
 219 holding temporaries and argregs, which is an array of register numbers
 220 for holding the first \*[uc N_ARGS] arguments.  Consult x64.h, as an
 221 example for the macros defined for each architecture.
 222
 223 .SH "Compiling \*[uc NEATCC]"
 224 The neatcc_make \*[uc GIT] repository, includes a makefile to obtain
 225 and build neatcc, neatld, and neatlibc (and a few other programs).
 226 To do so, use the following commands:
 227
 228 .cc.beg
 229 .ta 12m
 230 $ git clone git://repo.or.cz/neatcc_make.git
 231 $ cd neatcc_make
 232 $ make init     # fetches the required programs
 233 $ make neat     # compiles the programs using the host compiler
 234 $ make boot     # compiles neatcc using itself
 235 $ cd demo && make       # to make sure it works
 236 .cc.end
 237
 238 .LP
 239 The output architecture is x86-64 by default.  To compile for other
 240 architectures, the value of \*[uc OUT] Makefile variable can be
 241 changed.  For instance, the following commands build and bootstrap
 242 neatcc for \*[uc ARM32]:
 243
 244 .cc.beg
 245 .ta 12m
 246 $ make OUT=arm neat
 247 $ make OUT=arm boot
 248 .cc.end
 249
 250 .LP
 251 After compilation, the neatcc excutable in neatrun directory can be
 252 invoked as a C compiler.  It executes the linker or the compiler based
 253 on the presence of -c option.