demo/neatcc.ms

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