demo/neatcc.ms

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