7964b74a90bf1bec096d655a94014ab12a99237d
[xonotic/gmqcc.git] / ir.h
1 #ifndef GMQCC_IR_HDR
2 #define GMQCC_IR_HDR
3 #include "gmqcc.h"
4
5 /*
6  * Type large enough to hold all the possible IR flags. This should be
7  * changed if the static assertion at the end of this file fails.
8  */
9 typedef uint8_t ir_flag_t;
10
11 struct ir_value;
12 struct ir_instr;
13 struct ir_block;
14 struct ir_function;
15 struct ir_builder;
16
17 struct ir_life_entry_t {
18     /* both inclusive */
19     size_t start;
20     size_t end;
21 };
22
23 enum {
24     IR_FLAG_HAS_ARRAYS              = 1 << 0,
25     IR_FLAG_HAS_UNINITIALIZED       = 1 << 1,
26     IR_FLAG_HAS_GOTO                = 1 << 2,
27     IR_FLAG_INCLUDE_DEF             = 1 << 3,
28     IR_FLAG_ERASABLE                = 1 << 4,
29     IR_FLAG_BLOCK_COVERAGE          = 1 << 5,
30
31     IR_FLAG_SPLIT_VECTOR            = 1 << 6,
32
33     IR_FLAG_LAST,
34     IR_FLAG_MASK_NO_OVERLAP      = (IR_FLAG_HAS_ARRAYS | IR_FLAG_HAS_UNINITIALIZED),
35     IR_FLAG_MASK_NO_LOCAL_TEMPS  = (IR_FLAG_HAS_ARRAYS | IR_FLAG_HAS_UNINITIALIZED)
36 };
37
38 struct ir_value {
39     ir_value(std::string&& name, store_type storetype, qc_type vtype);
40     ~ir_value();
41
42     std::string m_name;
43
44     qc_type m_vtype;
45     store_type m_store;
46     lex_ctx_t m_context;
47     qc_type m_fieldtype; // even the IR knows the subtype of a field
48     qc_type m_outtype;   // and the output type of a function
49     int m_cvq;       // 'const' vs 'var' qualifier
50     ir_flag_t m_flags;
51
52     std::vector<ir_instr *> m_reads;
53     std::vector<ir_instr *> m_writes;
54
55     // constant values
56     bool m_hasvalue;
57     union {
58         qcfloat_t    vfloat;
59         int          vint;
60         vec3_t       vvec;
61         int32_t      ivec[3];
62         char        *vstring;
63         ir_value    *vpointer;
64         ir_function *vfunc;
65     } m_constval;
66
67     struct {
68         int32_t globaladdr;
69         int32_t name;
70         int32_t local;         // filled by the local-allocator
71         int32_t addroffset;    // added for members
72         int32_t fieldaddr;     // to generate field-addresses early
73     } m_code;
74
75     // for accessing vectors
76     ir_value *m_members[3];
77     ir_value *m_memberof;
78
79     bool m_unique_life;      // arrays will never overlap with temps
80     bool m_locked;           // temps living during a CALL must be locked
81     bool m_callparam;
82
83     std::vector<ir_life_entry_t> m_life; // For the temp allocator
84 };
85
86 /*
87  * ir_value can be a variable, or created by an operation
88  * if a result of an operation: the function should store
89  * it to remember to delete it / garbage collect it
90  */
91 ir_value*       ir_value_vector_member(ir_value*, unsigned int member);
92 bool GMQCC_WARN ir_value_set_float(ir_value*, float f);
93 bool GMQCC_WARN ir_value_set_func(ir_value*, int f);
94 bool GMQCC_WARN ir_value_set_string(ir_value*, const char *s);
95 bool GMQCC_WARN ir_value_set_vector(ir_value*, vec3_t v);
96 bool GMQCC_WARN ir_value_set_field(ir_value*, ir_value *fld);
97 bool            ir_value_lives(ir_value*, size_t);
98 void            ir_value_dump_life(const ir_value *self, int (*oprintf)(const char*,...));
99
100 /* PHI data */
101 struct ir_phi_entry_t {
102     ir_value *value;
103     ir_block *from;
104 };
105
106 /* instruction */
107 struct ir_instr {
108     ir_instr(lex_ctx_t, ir_block *owner, int opcode);
109     ~ir_instr();
110
111     int m_opcode;
112     lex_ctx_t m_context;
113     ir_value *(_m_ops[3]) = { nullptr, nullptr, nullptr };
114     ir_block *(m_bops[2]) = { nullptr, nullptr };
115
116     std::vector<ir_phi_entry_t> m_phi;
117     std::vector<ir_value *> m_params;
118
119     // For the temp-allocation
120     size_t m_eid = 0;
121
122     // For IFs
123     bool m_likely = true;
124
125     ir_block *m_owner;
126 };
127
128 /* block */
129 struct ir_block {
130     ir_block(ir_function *owner, const std::string& name);
131     ~ir_block();
132
133     ir_function *m_owner;
134     std::string m_label;
135
136     lex_ctx_t m_context;
137     bool m_final = false; /* once a jump is added we're done */
138
139     ir_instr **m_instr = nullptr;
140     ir_block **m_entries = nullptr;
141     ir_block **m_exits = nullptr;
142     std::vector<ir_value *> m_living;
143
144     /* For the temp-allocation */
145     size_t m_entry_id  = 0;
146     size_t m_eid       = 0;
147     bool   m_is_return = false;
148
149     bool m_generated = false;
150     size_t m_code_start = 0;
151 };
152
153 ir_value*       ir_block_create_binop(ir_block*, lex_ctx_t, const char *label, int op, ir_value *left, ir_value *right);
154 ir_value*       ir_block_create_unary(ir_block*, lex_ctx_t, const char *label, int op, ir_value *operand);
155 bool GMQCC_WARN ir_block_create_store_op(ir_block*, lex_ctx_t, int op, ir_value *target, ir_value *what);
156 bool GMQCC_WARN ir_block_create_storep(ir_block*, lex_ctx_t, ir_value *target, ir_value *what);
157 ir_value*       ir_block_create_load_from_ent(ir_block*, lex_ctx_t, const char *label, ir_value *ent, ir_value *field, qc_type outype);
158 ir_value*       ir_block_create_fieldaddress(ir_block*, lex_ctx_t, const char *label, ir_value *entity, ir_value *field);
159 bool GMQCC_WARN ir_block_create_state_op(ir_block*, lex_ctx_t, ir_value *frame, ir_value *think);
160
161 /* This is to create an instruction of the form
162  * <outtype>%label := opcode a, b
163  */
164 ir_instr* ir_block_create_phi(ir_block*, lex_ctx_t, const char *label, qc_type vtype);
165 ir_value* ir_phi_value(ir_instr*);
166 void ir_phi_add(ir_instr*, ir_block *b, ir_value *v);
167 ir_instr* ir_block_create_call(ir_block*, lex_ctx_t, const char *label, ir_value *func, bool noreturn);
168 ir_value* ir_call_value(ir_instr*);
169 void ir_call_param(ir_instr*, ir_value*);
170
171 bool GMQCC_WARN ir_block_create_return(ir_block*, lex_ctx_t, ir_value *opt_value);
172
173 bool GMQCC_WARN ir_block_create_if(ir_block*, lex_ctx_t, ir_value *cond,
174                                    ir_block *ontrue, ir_block *onfalse);
175 /*
176  * A 'goto' is an actual 'goto' coded in QC, whereas
177  * a 'jump' is a virtual construct which simply names the
178  * next block to go to.
179  * A goto usually becomes an OP_GOTO in the resulting code,
180  * whereas a 'jump' usually doesn't add any actual instruction.
181  */
182 bool GMQCC_WARN ir_block_create_jump(ir_block*, lex_ctx_t, ir_block *to);
183 bool GMQCC_WARN ir_block_create_goto(ir_block*, lex_ctx_t, ir_block *to);
184
185 /* function */
186 struct ir_function {
187     ir_function(ir_builder *owner, qc_type returntype);
188     ~ir_function();
189
190     ir_builder *m_owner;
191
192     std::string m_name;
193     qc_type     m_outtype;
194     int        *m_params  = nullptr;
195     ir_flag_t   m_flags   = 0;
196     int         m_builtin = 0;
197
198     std::vector<std::unique_ptr<ir_block>> m_blocks;
199
200     /*
201      * values generated from operations
202      * which might get optimized away, so anything
203      * in there needs to be deleted in the dtor.
204      */
205     std::vector<std::unique_ptr<ir_value>> m_values;
206     std::vector<std::unique_ptr<ir_value>> m_locals;     /* locally defined variables */
207     ir_value *m_value = nullptr;
208
209     size_t m_allocated_locals = 0;
210     size_t m_globaltemps      = 0;
211
212     ir_block*  m_first = nullptr;
213     ir_block*  m_last  = nullptr;
214
215     lex_ctx_t  m_context;
216
217     /*
218      * for prototypes - first we generate all the
219      * globals, and we remember teh function-defs
220      * so we can later fill in the entry pos
221      *
222      * remember the ID:
223      */
224     qcint_t m_code_function_def = -1;
225
226     /* for temp allocation */
227     size_t m_run_id = 0;
228
229     /* vararg support: */
230     size_t m_max_varargs = 0;
231 };
232
233
234 ir_value*       ir_function_create_local(ir_function *self, const std::string& name, qc_type vtype, bool param);
235 bool GMQCC_WARN ir_function_finalize(ir_function*);
236 ir_block*       ir_function_create_block(lex_ctx_t ctx, ir_function*, const char *label);
237
238 /* builder */
239 #define IR_HT_SIZE          1024
240 #define IR_MAX_VINSTR_TEMPS 1
241
242 struct ir_builder {
243     ir_builder(const std::string& modulename);
244     ~ir_builder();
245
246     std::string m_name;
247     std::vector<std::unique_ptr<ir_function>> m_functions;
248     std::vector<std::unique_ptr<ir_value>>    m_globals;
249     std::vector<std::unique_ptr<ir_value>>    m_fields;
250     // for reusing them in vector-splits, TODO: sort this or use a radix-tree
251     std::vector<ir_value*>                    m_const_floats;
252
253     ht            m_htfunctions;
254     ht            m_htglobals;
255     ht            m_htfields;
256
257     // extparams' ir_values reference the ones from extparam_protos
258     std::vector<std::unique_ptr<ir_value>> m_extparam_protos;
259     std::vector<ir_value*>                 m_extparams;
260
261     // the highest func->allocated_locals
262     size_t        m_max_locals              = 0;
263     size_t        m_max_globaltemps         = 0;
264     uint32_t      m_first_common_local      = 0;
265     uint32_t      m_first_common_globaltemp = 0;
266
267     std::vector<const char*> m_filenames;
268     std::vector<qcint_t>     m_filestrings;
269
270     // we cache the #IMMEDIATE string here
271     qcint_t      m_str_immediate = 0;
272
273     // there should just be this one nil
274     ir_value    *m_nil;
275     ir_value    *m_reserved_va_count = nullptr;
276     ir_value    *m_coverage_func = nullptr;
277
278     /* some virtual instructions require temps, and their code is isolated
279      * so that we don't need to keep track of their liveness.
280      */
281     ir_value    *m_vinstr_temp[IR_MAX_VINSTR_TEMPS];
282
283     /* code generator */
284     std::unique_ptr<code_t> m_code;
285 };
286
287 ir_function* ir_builder_create_function(ir_builder*, const std::string& name, qc_type outtype);
288 ir_value*    ir_builder_create_global(ir_builder*, const std::string& name, qc_type vtype);
289 ir_value*    ir_builder_create_field(ir_builder*, const std::string& name, qc_type vtype);
290 ir_value*    ir_builder_get_va_count(ir_builder*);
291 bool         ir_builder_generate(ir_builder *self, const char *filename);
292 void         ir_builder_dump(ir_builder*, int (*oprintf)(const char*, ...));
293
294 /*
295  * This code assumes 32 bit floats while generating binary
296  * Blub: don't use extern here, it's annoying and shows up in nm
297  * for some reason :P
298  */
299 typedef int static_assert_is_32bit_float  [(sizeof(int32_t) == 4)   ? 1 : -1];
300 typedef int static_assert_is_32bit_integer[(sizeof(qcfloat_t) == 4) ? 1 : -1];
301
302 /*
303  * If the condition creates a situation where this becomes -1 size it means there are
304  * more IR_FLAGs than the type ir_flag_t is capable of holding. So either eliminate
305  * the IR flag count or change the ir_flag_t typedef to a type large enough to accomodate
306  * all the flags.
307  */
308 typedef int static_assert_is_ir_flag_safe [((IR_FLAG_LAST) <= (ir_flag_t)(-1)) ? 1 : -1];
309
310 #endif