README

   1 This is a work in progress Quake C compiler. There are very few good QC
   2 compilers out there on the internet that can be used in the opensource
   3 community.  There are a lot of mediocre compilers, but no one wants those.
   4 This is the solution for that, for once a proper Quake C compiler that is
   5 capable of doing proper optimization.
   6
   7 The compiler is intended to implement modern day compiler design princibles
   8 and support modifications through extensions that are provided for the
   9 user through a low-level syntax specific-language inside the language itself
  10 to implement language functionality.
  11
  12 The design goals of the compiler are very large, it's intended the compiler
  13 supports a multitude of things, these things along with the status of
  14 completeness is represented below in a table.
  15
  16 +-------------------+-----------------------------+------------------+
  17 |     Feature       |  What's it for?             | Complete Factor  |
  18 +-------------------+-----------------------------+------------------+
  19 . Lexical analysis  .  Tokenization               .       90%        .
  20 .-------------------.-----------------------------.------------------.
  21 . Tokenization      .  Parsing                    .       90%        .
  22 .-------------------.-----------------------------.------------------.
  23 . Parsing / SYA     .  AST Generation             .       09%        .
  24 .-------------------.-----------------------------.------------------.
  25 . AST Generation    .  IR  Generation             .       ??%        .
  26 .-------------------.-----------------------------.------------------.
  27 . IR  Generation    .  Code Generation            .       ??%        .
  28 .-------------------.-----------------------------.------------------.
  29 . Code Generation   .  Binary Generation          .       ??%        .
  30 .-------------------.-----------------------------.------------------.
  31 . Binary Generation .  Binary                     .      100%        .
  32 +-------------------+-----------------------------+------------------+
  33
  34 Design tree:
  35         The compiler is intended to work in the following order:
  36                 Lexical analysis ->
  37                         Tokenization ->
  38                                 Parsing:
  39                                         Operator precedence:
  40                                                 Shynting yard algorithm
  41                                         Inline assembly:
  42                                                  Usage of the assembler subsystem:
  43                                                         top-down parsing and assemblation no optimization
  44                                         Other parsing:
  45                                                 recrusive decent
  46                                 ->
  47                                         Abstract syntax tree generation ->
  48                                                 Immediate representation (SSA):
  49                                                         Optimizations:
  50                                                                 Constant propagation
  51                                                                 Value range propogation
  52                                                                 Sparse conditional constant propagation (possibly?)
  53                                                                         Dead code elimination
  54                                                                         Constant folding
  55                                                                 Global value numbering
  56                                                                 Partial redundancy elimination
  57                                                                 Strength reduction
  58                                                                 Common subexpression elimination
  59                                                                 Peephole optimizations
  60                                                                 Loop-invariant code motion
  61                                                                 Inline expansion
  62                                                                 Constant folding
  63                                                                 Induction variable recognition and elimination
  64                                                                 Dead store elimination
  65                                                                 Jump threading
  66                                                 ->
  67                                                         Code Generation:
  68                                                                 Optimizations:
  69                                                                         Rematerialization
  70                                                                         Code Factoring
  71                                                                         Recrusion Elimination
  72                                                                         Loop unrolling
  73                                                                         Deforestation
  74                                                         ->
  75                                                                 Binary Generation
  76
  77 File tree and explination:
  78         gmqcc.h
  79                 This is the common header with all definitions, structures, and
  80                 constants for everything.
  81
  82         error.c
  83                 This is the error subsystem, this handles the output of good detailed
  84                 error messages (not currently, but will), with colors and such.
  85
  86         lex.c
  87                 This is the lexer, a very small basic step-seek lexer that can be easily
  88                 changed to add new tokens, very retargetable.
  89
  90         main.c
  91                 This is the core compiler entry, handles switches (will) to toggle on
  92                 and off certian compiler features.
  93
  94         parse.c
  95                 This is the parser which goes over all tokens and generates a parse tree
  96                 and check for syntax correctness.
  97
  98         typedef.c
  99                 This is the typedef system, this is a seperate file because it's a lot more
 100                 complicated than it sounds.  This handles all typedefs, and even recrusive
 101                 typedefs.
 102
 103         util.c
 104                 These are utilities for the compiler, some things in here include a
 105                 allocator used for debugging, and some string functions.
 106
 107         assembler.c
 108                 This implements support for assembling Quake assembler (which doesn't
 109                 actually exist untill now: documentation of the Quake assembler is below.
 110                 This also implements (will) inline assembly for the C compiler.
 111
 112         README
 113                 This is the file you're currently reading
 114
 115         Makefile
 116                 The makefile, when sources are added you should add them to the SRC=
 117                 line otherwise the build will not pick it up.  Trivial stuff, small
 118                 easy to manage makefile, no need to complicate it.
 119                 Some targets:
 120                         #make gmqcc
 121                                 Builds gmqcc, creating a `gmqcc` binary file in the current
 122                                 directory as the makefile.
 123                         #make test
 124                                 Builds the ir and ast tests, creating a `test_ir` and `test_ast`
 125                                 binary file in the current directory as the makefile.
 126                         #make test_ir
 127                                 Builds the ir test, creating a `test_ir` binary file in the
 128                                 current directory as the makefile.
 129                         #make test_ast
 130                                 Builds the asr test, creating a `test_ast` binary file in the
 131                                 current directory as the makefile.
 132                         #make clean
 133                                 Cleans the build files left behind by a previous build, as
 134                                 well as all the binary files.
 135                         #make all
 136                                 Builds the tests and the compiler binary all in the current
 137                                 directory of the makefile.
 138
 139 ////////////////////////////////////////////////////////////////////////
 140 ///////////////////// Quake Assembler Documentation ////////////////////
 141 ////////////////////////////////////////////////////////////////////////
 142 Quake assembler is quite simple: it's just an annotated version of the binary
 143 produced by any existing QuakeC compiler, but made cleaner to use, (so that
 144 the location of various globals or strings are not required to be known).
 145
 146 Constants:
 147         Using one of the following valid constant typenames, you can declare
 148         a constant {FLOAT,VECTOR,FUNCTION,FIELD,ENTITY}, all typenames are
 149         proceeded by a colon, and the name (white space doesn't matter).
 150
 151         Examples:
 152                 FLOAT: foo 1
 153                 VECTOR: bar 1 2 1
 154                 STRING: hello "hello world"
 155
 156 Comments:
 157         Commenting assembly requires the use of either # or ; on the line
 158         that you'd like to be ignored by the assembler. You can only comment
 159         blank lines, and not lines assembly already exists on.
 160
 161         Examples:
 162                 ; this is allowed
 163                 # as is this
 164                 FLOAT: foo 1 ; this is not allowed
 165                 FLOAT: bar 2 # neither is this
 166
 167 Functions:
 168         Creating functions is the same as declaring a constant, simply use
 169         FUNCTION followed by a colon, and the name (white space doesn't matter)
 170         and start the statements for that function on the line after it
 171
 172         Examples:
 173                 FLOAT: foo 1
 174                 FLOAT: bar 2
 175                 FUNCTION: test1
 176                         ADD foo, bar, OFS_RETURN
 177                         RETURN
 178
 179                 FUNCTION: test2
 180                         CALL0 test1
 181                         DONE
 182
 183 Internal:
 184         The Quake engine provides some internal functions such as print, to
 185         access these you first must declare them and their names. To do this
 186         you create a FUNCTION as you currently do. Adding a $ followed by the
 187         number of the engine builtin (negated).
 188
 189         Examples:
 190                 FUNCTION: print $4
 191                 FUNCTION: error $3
 192
 193 Misc:
 194         There are some rules as to what your identifiers can be for functions
 195         and constants.  All indentifiers mustn't begin with a numeric digit,
 196         identifiers cannot include spaces, or tabs; they cannot contain symbols,
 197         and they cannot exceed 32768 characters. Identifiers cannot be all
 198         capitalized either, as all capatilized identifiers are reserved by the
 199         assembler.
 200
 201         Numeric constants cannot contain special notation such as `1-e10`, all
 202         numeric constants have to be numeric, they can contain decmial points
 203         and signs (+, -) however.
 204
 205         Constants cannot be assigned values of other constants, their value must
 206         be fully expressed inspot of the declartion.
 207
 208         No two identifiers can be the same name, this applies for variables allocated
 209         inside a function scope (despite it being considered local).
 210
 211         There exists one other keyword that is considered sugar, and that
 212         is AUTHOR, this keyword will allow you to speciy the AUTHOR(S) of
 213         the assembly being assembled. The string represented for each usage
 214         of AUTHOR is wrote to the end of the string table. Simaler to the
 215         usage of constants and functions the AUTHOR keyword must be proceeded
 216         by a colon.
 217
 218         Examples:
 219                 AUTHOR: "Dale Weiler"
 220                 AUTHOR: "Wolfgang Bumiller"
 221
 222         Colons exist for the sole reason of not having to use spaces after
 223         keyword usage (however spaces are allowed).  To understand the
 224         following examples below are equivlent.
 225
 226         Example 1:
 227                 FLOAT:foo 1
 228         Example 2:
 229                 FLOAT: foo 1
 230         Example 3:
 231                 FLOAT:  foo 2
 232
 233         variable amounts of whitespace is allowed anywhere (as it should be).
 234         think of `:` as a delimiter (which is what it's used for during assembly).
 235
 236 ////////////////////////////////////////////////////////////////////////
 237 /////////////////////// Quake C Documentation //////////////////////////
 238 ////////////////////////////////////////////////////////////////////////
 239 TODO ....