readme s/\t/ /g
[xonotic/gmqcc.git] / 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 ....