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 ....