1 /*
2 * IR - Lightweight JIT Compilation Framework
3 * (IR construction, folding, utilities)
4 * Copyright (C) 2022 Zend by Perforce.
5 * Authors: Dmitry Stogov <dmitry@php.net>
6 *
7 * The logical IR representation is based on Cliff Click's Sea of Nodes.
8 * See: C. Click, M. Paleczny. "A Simple Graph-Based Intermediate
9 * Representation" In ACM SIGPLAN Workshop on Intermediate Representations
10 * (IR '95), pages 35-49, Jan. 1995.
11 *
12 * The physical IR representation is based on Mike Pall's LuaJIT IR.
13 * See: M. Pall. "LuaJIT 2.0 intellectual property disclosure and research
14 * opportunities" November 2009 http://lua-users.org/lists/lua-l/2009-11/msg00089.html
15 */
16
17 #ifndef _GNU_SOURCE
18 # define _GNU_SOURCE
19 #endif
20
21 #ifndef _WIN32
22 # include <sys/mman.h>
23 # if defined(__linux__) || defined(__sun)
24 # include <alloca.h>
25 # endif
26 # if defined(__APPLE__) && defined(__aarch64__)
27 # include <libkern/OSCacheControl.h>
28 # endif
29 #else
30 # define WIN32_LEAN_AND_MEAN
31 # include <windows.h>
32 #endif
33
34 #include "ir.h"
35 #include "ir_private.h"
36
37 #include <stddef.h>
38 #include <stdlib.h>
39 #include <math.h>
40
41 #ifdef HAVE_VALGRIND
42 # include <valgrind/valgrind.h>
43 #endif
44
45 #define IR_TYPE_FLAGS(name, type, field, flags) ((flags)|sizeof(type)),
46 #define IR_TYPE_NAME(name, type, field, flags) #name,
47 #define IR_TYPE_CNAME(name, type, field, flags) #type,
48 #define IR_TYPE_SIZE(name, type, field, flags) sizeof(type),
49 #define IR_OP_NAME(name, flags, op1, op2, op3) #name,
50
51 const uint8_t ir_type_flags[IR_LAST_TYPE] = {
52 0,
53 IR_TYPES(IR_TYPE_FLAGS)
54 };
55
56 const char *ir_type_name[IR_LAST_TYPE] = {
57 "void",
58 IR_TYPES(IR_TYPE_NAME)
59 };
60
61 const uint8_t ir_type_size[IR_LAST_TYPE] = {
62 0,
63 IR_TYPES(IR_TYPE_SIZE)
64 };
65
66 const char *ir_type_cname[IR_LAST_TYPE] = {
67 "void",
68 IR_TYPES(IR_TYPE_CNAME)
69 };
70
71 const char *ir_op_name[IR_LAST_OP] = {
72 IR_OPS(IR_OP_NAME)
73 #ifdef IR_PHP
74 IR_PHP_OPS(IR_OP_NAME)
75 #endif
76 };
77
ir_print_escaped_str(const char * s,size_t len,FILE * f)78 void ir_print_escaped_str(const char *s, size_t len, FILE *f)
79 {
80 char ch;
81
82 while (len > 0) {
83 ch = *s;
84 switch (ch) {
85 case '\\': fputs("\\\\", f); break;
86 case '\'': fputs("'", f); break;
87 case '\"': fputs("\\\"", f); break;
88 case '\a': fputs("\\a", f); break;
89 case '\b': fputs("\\b", f); break;
90 case '\033': fputs("\\e", f); break;
91 case '\f': fputs("\\f", f); break;
92 case '\n': fputs("\\n", f); break;
93 case '\r': fputs("\\r", f); break;
94 case '\t': fputs("\\t", f); break;
95 case '\v': fputs("\\v", f); break;
96 case '\?': fputs("\\?", f); break;
97 default:
98 #ifdef __aarch64__
99 if (ch < 32) {
100 #else
101 if (ch >= 0 && ch < 32) {
102 #endif
103 fprintf(f, "\\%c%c%c",
104 '0' + ((ch >> 6) % 8),
105 '0' + ((ch >> 3) % 8),
106 '0' + (ch % 8));
107 break;
108 } else {
109 fputc(ch, f);
110 }
111 }
112 s++;
113 len--;
114 }
115 }
116
117 void ir_print_const(const ir_ctx *ctx, const ir_insn *insn, FILE *f, bool quoted)
118 {
119 char buf[128];
120
121 if (insn->op == IR_FUNC || insn->op == IR_SYM) {
122 fprintf(f, "%s", ir_get_str(ctx, insn->val.name));
123 return;
124 } else if (insn->op == IR_STR) {
125 size_t len;
126 const char *str = ir_get_strl(ctx, insn->val.str, &len);
127
128 if (quoted) {
129 fprintf(f, "\"");
130 ir_print_escaped_str(str, len, f);
131 fprintf(f, "\"");
132 } else {
133 ir_print_escaped_str(str, len, f);
134 }
135 return;
136 }
137 IR_ASSERT(IR_IS_CONST_OP(insn->op) || insn->op == IR_FUNC_ADDR);
138 switch (insn->type) {
139 case IR_BOOL:
140 fprintf(f, "%u", insn->val.b);
141 break;
142 case IR_U8:
143 fprintf(f, "%u", insn->val.u8);
144 break;
145 case IR_U16:
146 fprintf(f, "%u", insn->val.u16);
147 break;
148 case IR_U32:
149 fprintf(f, "%u", insn->val.u32);
150 break;
151 case IR_U64:
152 fprintf(f, "%" PRIu64, insn->val.u64);
153 break;
154 case IR_ADDR:
155 if (insn->val.addr) {
156 fprintf(f, "0x%" PRIxPTR, insn->val.addr);
157 } else {
158 fprintf(f, "0");
159 }
160 break;
161 case IR_CHAR:
162 if (insn->val.c == '\\') {
163 fprintf(f, "'\\\\'");
164 } else if (insn->val.c >= ' ') {
165 fprintf(f, "'%c'", insn->val.c);
166 } else if (insn->val.c == '\t') {
167 fprintf(f, "'\\t'");
168 } else if (insn->val.c == '\r') {
169 fprintf(f, "'\\r'");
170 } else if (insn->val.c == '\n') {
171 fprintf(f, "'\\n'");
172 } else if (insn->val.c == '\0') {
173 fprintf(f, "'\\0'");
174 } else {
175 fprintf(f, "%u", insn->val.c);
176 }
177 break;
178 case IR_I8:
179 fprintf(f, "%d", insn->val.i8);
180 break;
181 case IR_I16:
182 fprintf(f, "%d", insn->val.i16);
183 break;
184 case IR_I32:
185 fprintf(f, "%d", insn->val.i32);
186 break;
187 case IR_I64:
188 fprintf(f, "%" PRIi64, insn->val.i64);
189 break;
190 case IR_DOUBLE:
191 if (isnan(insn->val.d)) {
192 fprintf(f, "nan");
193 } else {
194 snprintf(buf, sizeof(buf), "%g", insn->val.d);
195 if (strtod(buf, NULL) != insn->val.d) {
196 snprintf(buf, sizeof(buf), "%.53e", insn->val.d);
197 if (strtod(buf, NULL) != insn->val.d) {
198 IR_ASSERT(0 && "can't format double");
199 }
200 }
201 fprintf(f, "%s", buf);
202 }
203 break;
204 case IR_FLOAT:
205 if (isnan(insn->val.f)) {
206 fprintf(f, "nan");
207 } else {
208 snprintf(buf, sizeof(buf), "%g", insn->val.f);
209 if (strtod(buf, NULL) != insn->val.f) {
210 snprintf(buf, sizeof(buf), "%.24e", insn->val.f);
211 if (strtod(buf, NULL) != insn->val.f) {
212 IR_ASSERT(0 && "can't format float");
213 }
214 }
215 fprintf(f, "%s", buf);
216 }
217 break;
218 default:
219 IR_ASSERT(0);
220 break;
221 }
222 }
223
224 #define ir_op_flag_v 0
225 #define ir_op_flag_v0X3 (0 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
226 #define ir_op_flag_d IR_OP_FLAG_DATA
227 #define ir_op_flag_d0 ir_op_flag_d
228 #define ir_op_flag_d1 (ir_op_flag_d | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
229 #define ir_op_flag_d1X1 (ir_op_flag_d | 1 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
230 #define ir_op_flag_d2 (ir_op_flag_d | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
231 #define ir_op_flag_d2C (ir_op_flag_d | IR_OP_FLAG_COMMUTATIVE | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
232 #define ir_op_flag_d3 (ir_op_flag_d | 3 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
233 #define ir_op_flag_r IR_OP_FLAG_DATA // "d" and "r" are the same now
234 #define ir_op_flag_r0 ir_op_flag_r
235 #define ir_op_flag_p (IR_OP_FLAG_DATA | IR_OP_FLAG_PINNED)
236 #define ir_op_flag_p1 (ir_op_flag_p | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
237 #define ir_op_flag_p1X1 (ir_op_flag_p | 1 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
238 #define ir_op_flag_p1X2 (ir_op_flag_p | 1 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
239 #define ir_op_flag_p2 (ir_op_flag_p | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
240 #define ir_op_flag_pN (ir_op_flag_p | IR_OP_FLAG_VAR_INPUTS)
241 #define ir_op_flag_c IR_OP_FLAG_CONTROL
242 #define ir_op_flag_c1X2 (ir_op_flag_c | 1 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
243 #define ir_op_flag_c3 (ir_op_flag_c | 3 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
244 #define ir_op_flag_S (IR_OP_FLAG_CONTROL|IR_OP_FLAG_BB_START)
245 #define ir_op_flag_S0X1 (ir_op_flag_S | 0 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
246 #define ir_op_flag_S1 (ir_op_flag_S | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
247 #define ir_op_flag_S1X1 (ir_op_flag_S | 1 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
248 #define ir_op_flag_S2 (ir_op_flag_S | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
249 #define ir_op_flag_S2X1 (ir_op_flag_S | 2 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
250 #define ir_op_flag_SN (ir_op_flag_S | IR_OP_FLAG_VAR_INPUTS)
251 #define ir_op_flag_E (IR_OP_FLAG_CONTROL|IR_OP_FLAG_BB_END)
252 #define ir_op_flag_E1 (ir_op_flag_E | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
253 #define ir_op_flag_E2 (ir_op_flag_E | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
254 #define ir_op_flag_T (IR_OP_FLAG_CONTROL|IR_OP_FLAG_BB_END|IR_OP_FLAG_TERMINATOR)
255 #define ir_op_flag_T2X1 (ir_op_flag_T | 2 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
256 #define ir_op_flag_T1X2 (ir_op_flag_T | 1 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
257 #define ir_op_flag_l (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_LOAD)
258 #define ir_op_flag_l0 ir_op_flag_l
259 #define ir_op_flag_l1 (ir_op_flag_l | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
260 #define ir_op_flag_l1X1 (ir_op_flag_l | 1 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
261 #define ir_op_flag_l1X2 (ir_op_flag_l | 1 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
262 #define ir_op_flag_l2 (ir_op_flag_l | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
263 #define ir_op_flag_l3 (ir_op_flag_l | 3 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
264 #define ir_op_flag_s (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_STORE)
265 #define ir_op_flag_s0 ir_op_flag_s
266 #define ir_op_flag_s1 (ir_op_flag_s | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
267 #define ir_op_flag_s2 (ir_op_flag_s | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
268 #define ir_op_flag_s2X1 (ir_op_flag_s | 2 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
269 #define ir_op_flag_s3 (ir_op_flag_s | 3 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
270 #define ir_op_flag_x1 (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_CALL | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
271 #define ir_op_flag_x2 (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_CALL | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
272 #define ir_op_flag_x3 (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_CALL | 3 | (3 << IR_OP_FLAG_OPERANDS_SHIFT))
273 #define ir_op_flag_xN (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_CALL | IR_OP_FLAG_VAR_INPUTS)
274 #define ir_op_flag_a1 (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_ALLOC | 1 | (1 << IR_OP_FLAG_OPERANDS_SHIFT))
275 #define ir_op_flag_a2 (IR_OP_FLAG_CONTROL|IR_OP_FLAG_MEM|IR_OP_FLAG_MEM_ALLOC | 2 | (2 << IR_OP_FLAG_OPERANDS_SHIFT))
276
277 #define ir_op_kind____ IR_OPND_UNUSED
278 #define ir_op_kind_def IR_OPND_DATA
279 #define ir_op_kind_ref IR_OPND_DATA
280 #define ir_op_kind_src IR_OPND_CONTROL
281 #define ir_op_kind_reg IR_OPND_CONTROL_DEP
282 #define ir_op_kind_ret IR_OPND_CONTROL_REF
283 #define ir_op_kind_str IR_OPND_STR
284 #define ir_op_kind_num IR_OPND_NUM
285 #define ir_op_kind_fld IR_OPND_STR
286 #define ir_op_kind_var IR_OPND_DATA
287 #define ir_op_kind_prb IR_OPND_PROB
288 #define ir_op_kind_opt IR_OPND_PROB
289 #define ir_op_kind_pro IR_OPND_PROTO
290
291 #define _IR_OP_FLAGS(name, flags, op1, op2, op3) \
292 IR_OP_FLAGS(ir_op_flag_ ## flags, ir_op_kind_ ## op1, ir_op_kind_ ## op2, ir_op_kind_ ## op3),
293
294 const uint32_t ir_op_flags[IR_LAST_OP] = {
295 IR_OPS(_IR_OP_FLAGS)
296 #ifdef IR_PHP
297 IR_PHP_OPS(_IR_OP_FLAGS)
298 #endif
299 };
300
301 static void ir_grow_bottom(ir_ctx *ctx)
302 {
303 ir_insn *buf = ctx->ir_base - ctx->consts_limit;
304 ir_ref old_consts_limit = ctx->consts_limit;
305
306 if (ctx->consts_limit < 1024 * 4) {
307 ctx->consts_limit *= 2;
308 } else if (ctx->consts_limit < 1024 * 4 * 2) {
309 ctx->consts_limit = 1024 * 4 * 2;
310 } else {
311 ctx->consts_limit += 1024 * 4;
312 }
313 buf = ir_mem_realloc(buf, (ctx->consts_limit + ctx->insns_limit) * sizeof(ir_insn));
314 memmove(buf + (ctx->consts_limit - old_consts_limit),
315 buf,
316 (old_consts_limit + ctx->insns_count) * sizeof(ir_insn));
317 ctx->ir_base = buf + ctx->consts_limit;
318 }
319
320 static ir_ref ir_next_const(ir_ctx *ctx)
321 {
322 ir_ref ref = ctx->consts_count;
323
324 if (UNEXPECTED(ref >= ctx->consts_limit)) {
325 ir_grow_bottom(ctx);
326 }
327 ctx->consts_count = ref + 1;
328 return -ref;
329 }
330
331 static void ir_grow_top(ir_ctx *ctx)
332 {
333 ir_insn *buf = ctx->ir_base - ctx->consts_limit;
334
335 if (ctx->insns_limit < 1024 * 4) {
336 ctx->insns_limit *= 2;
337 } else if (ctx->insns_limit < 1024 * 4 * 2) {
338 ctx->insns_limit = 1024 * 4 * 2;
339 } else {
340 ctx->insns_limit += 1024 * 4;
341 }
342 buf = ir_mem_realloc(buf, (ctx->consts_limit + ctx->insns_limit) * sizeof(ir_insn));
343 ctx->ir_base = buf + ctx->consts_limit;
344 }
345
346 static ir_ref ir_next_insn(ir_ctx *ctx)
347 {
348 ir_ref ref = ctx->insns_count;
349
350 if (UNEXPECTED(ref >= ctx->insns_limit)) {
351 ir_grow_top(ctx);
352 }
353 ctx->insns_count = ref + 1;
354 return ref;
355 }
356
357 void ir_truncate(ir_ctx *ctx)
358 {
359 ir_insn *buf = ir_mem_malloc((ctx->consts_count + ctx->insns_count) * sizeof(ir_insn));
360
361 memcpy(buf, ctx->ir_base - ctx->consts_count, (ctx->consts_count + ctx->insns_count) * sizeof(ir_insn));
362 ir_mem_free(ctx->ir_base - ctx->consts_limit);
363 ctx->insns_limit = ctx->insns_count;
364 ctx->consts_limit = ctx->consts_count;
365 ctx->ir_base = buf + ctx->consts_limit;
366 }
367
368 void ir_init(ir_ctx *ctx, uint32_t flags, ir_ref consts_limit, ir_ref insns_limit)
369 {
370 ir_insn *buf;
371
372 IR_ASSERT(consts_limit >= IR_CONSTS_LIMIT_MIN);
373 IR_ASSERT(insns_limit >= IR_INSNS_LIMIT_MIN);
374
375 memset(ctx, 0, sizeof(ir_ctx));
376
377 ctx->insns_count = IR_UNUSED + 1;
378 ctx->insns_limit = insns_limit;
379 ctx->consts_count = -(IR_TRUE - 1);
380 ctx->consts_limit = consts_limit;
381 ctx->fold_cse_limit = IR_UNUSED + 1;
382 ctx->flags = flags;
383
384 ctx->spill_base = -1;
385 ctx->fixed_stack_frame_size = -1;
386
387 buf = ir_mem_malloc((consts_limit + insns_limit) * sizeof(ir_insn));
388 ctx->ir_base = buf + consts_limit;
389
390 MAKE_NOP(&ctx->ir_base[IR_UNUSED]);
391 ctx->ir_base[IR_NULL].optx = IR_OPT(IR_C_ADDR, IR_ADDR);
392 ctx->ir_base[IR_NULL].val.u64 = 0;
393 ctx->ir_base[IR_FALSE].optx = IR_OPT(IR_C_BOOL, IR_BOOL);
394 ctx->ir_base[IR_FALSE].val.u64 = 0;
395 ctx->ir_base[IR_TRUE].optx = IR_OPT(IR_C_BOOL, IR_BOOL);
396 ctx->ir_base[IR_TRUE].val.u64 = 1;
397 }
398
399 void ir_free(ir_ctx *ctx)
400 {
401 ir_insn *buf = ctx->ir_base - ctx->consts_limit;
402 ir_mem_free(buf);
403 if (ctx->strtab.data) {
404 ir_strtab_free(&ctx->strtab);
405 }
406 if (ctx->binding) {
407 ir_hashtab_free(ctx->binding);
408 ir_mem_free(ctx->binding);
409 }
410 if (ctx->use_lists) {
411 ir_mem_free(ctx->use_lists);
412 }
413 if (ctx->use_edges) {
414 ir_mem_free(ctx->use_edges);
415 }
416 if (ctx->cfg_blocks) {
417 ir_mem_free(ctx->cfg_blocks);
418 }
419 if (ctx->cfg_edges) {
420 ir_mem_free(ctx->cfg_edges);
421 }
422 if (ctx->cfg_map) {
423 ir_mem_free(ctx->cfg_map);
424 }
425 if (ctx->cfg_schedule) {
426 ir_mem_free(ctx->cfg_schedule);
427 }
428 if (ctx->rules) {
429 ir_mem_free(ctx->rules);
430 }
431 if (ctx->vregs) {
432 ir_mem_free(ctx->vregs);
433 }
434 if (ctx->live_intervals) {
435 ir_mem_free(ctx->live_intervals);
436 }
437 if (ctx->arena) {
438 ir_arena_free(ctx->arena);
439 }
440 if (ctx->regs) {
441 ir_mem_free(ctx->regs);
442 if (ctx->fused_regs) {
443 ir_strtab_free(ctx->fused_regs);
444 ir_mem_free(ctx->fused_regs);
445 }
446 }
447 if (ctx->prev_ref) {
448 ir_mem_free(ctx->prev_ref);
449 }
450 if (ctx->entries) {
451 ir_mem_free(ctx->entries);
452 }
453 if (ctx->osr_entry_loads) {
454 ir_list_free((ir_list*)ctx->osr_entry_loads);
455 ir_mem_free(ctx->osr_entry_loads);
456 }
457 }
458
459 ir_ref ir_unique_const_addr(ir_ctx *ctx, uintptr_t addr)
460 {
461 ir_ref ref = ir_next_const(ctx);
462 ir_insn *insn = &ctx->ir_base[ref];
463
464 insn->optx = IR_OPT(IR_ADDR, IR_ADDR);
465 insn->val.u64 = addr;
466 /* don't insert into constants chain */
467 insn->prev_const = IR_UNUSED;
468 #if 0
469 insn->prev_const = ctx->prev_const_chain[IR_ADDR];
470 ctx->prev_const_chain[IR_ADDR] = ref;
471 #endif
472 #if 0
473 ir_insn *prev_insn, *next_insn;
474 ir_ref next;
475
476 prev_insn = NULL;
477 next = ctx->prev_const_chain[IR_ADDR];
478 while (next) {
479 next_insn = &ctx->ir_base[next];
480 if (UNEXPECTED(next_insn->val.u64 >= addr)) {
481 break;
482 }
483 prev_insn = next_insn;
484 next = next_insn->prev_const;
485 }
486
487 if (prev_insn) {
488 insn->prev_const = prev_insn->prev_const;
489 prev_insn->prev_const = ref;
490 } else {
491 insn->prev_const = ctx->prev_const_chain[IR_ADDR];
492 ctx->prev_const_chain[IR_ADDR] = ref;
493 }
494 #endif
495
496 return ref;
497 }
498
499 ir_ref ir_const_ex(ir_ctx *ctx, ir_val val, uint8_t type, uint32_t optx)
500 {
501 ir_insn *insn, *prev_insn;
502 ir_ref ref, prev;
503
504 if (type == IR_BOOL) {
505 return val.u64 ? IR_TRUE : IR_FALSE;
506 } else if (type == IR_ADDR && val.u64 == 0) {
507 return IR_NULL;
508 }
509 prev_insn = NULL;
510 ref = ctx->prev_const_chain[type];
511 while (ref) {
512 insn = &ctx->ir_base[ref];
513 if (UNEXPECTED(insn->val.u64 >= val.u64)) {
514 if (insn->val.u64 == val.u64) {
515 if (insn->optx == optx) {
516 return ref;
517 }
518 } else {
519 break;
520 }
521 }
522 prev_insn = insn;
523 ref = insn->prev_const;
524 }
525
526 if (prev_insn) {
527 prev = prev_insn->prev_const;
528 prev_insn->prev_const = -ctx->consts_count;
529 } else {
530 prev = ctx->prev_const_chain[type];
531 ctx->prev_const_chain[type] = -ctx->consts_count;
532 }
533
534 ref = ir_next_const(ctx);
535 insn = &ctx->ir_base[ref];
536 insn->prev_const = prev;
537
538 insn->optx = optx;
539 insn->val.u64 = val.u64;
540
541 return ref;
542 }
543
544 ir_ref ir_const(ir_ctx *ctx, ir_val val, uint8_t type)
545 {
546 return ir_const_ex(ctx, val, type, IR_OPT(type, type));
547 }
548
549 ir_ref ir_const_i8(ir_ctx *ctx, int8_t c)
550 {
551 ir_val val;
552 val.i64 = c;
553 return ir_const(ctx, val, IR_I8);
554 }
555
556 ir_ref ir_const_i16(ir_ctx *ctx, int16_t c)
557 {
558 ir_val val;
559 val.i64 = c;
560 return ir_const(ctx, val, IR_I16);
561 }
562
563 ir_ref ir_const_i32(ir_ctx *ctx, int32_t c)
564 {
565 ir_val val;
566 val.i64 = c;
567 return ir_const(ctx, val, IR_I32);
568 }
569
570 ir_ref ir_const_i64(ir_ctx *ctx, int64_t c)
571 {
572 ir_val val;
573 val.i64 = c;
574 return ir_const(ctx, val, IR_I64);
575 }
576
577 ir_ref ir_const_u8(ir_ctx *ctx, uint8_t c)
578 {
579 ir_val val;
580 val.u64 = c;
581 return ir_const(ctx, val, IR_U8);
582 }
583
584 ir_ref ir_const_u16(ir_ctx *ctx, uint16_t c)
585 {
586 ir_val val;
587 val.u64 = c;
588 return ir_const(ctx, val, IR_U16);
589 }
590
591 ir_ref ir_const_u32(ir_ctx *ctx, uint32_t c)
592 {
593 ir_val val;
594 val.u64 = c;
595 return ir_const(ctx, val, IR_U32);
596 }
597
598 ir_ref ir_const_u64(ir_ctx *ctx, uint64_t c)
599 {
600 ir_val val;
601 val.u64 = c;
602 return ir_const(ctx, val, IR_U64);
603 }
604
605 ir_ref ir_const_bool(ir_ctx *ctx, bool c)
606 {
607 return (c) ? IR_TRUE : IR_FALSE;
608 }
609
610 ir_ref ir_const_char(ir_ctx *ctx, char c)
611 {
612 ir_val val;
613 val.i64 = c;
614 return ir_const(ctx, val, IR_CHAR);
615 }
616
617 ir_ref ir_const_float(ir_ctx *ctx, float c)
618 {
619 ir_val val;
620 val.u32_hi = 0;
621 val.f = c;
622 return ir_const(ctx, val, IR_FLOAT);
623 }
624
625 ir_ref ir_const_double(ir_ctx *ctx, double c)
626 {
627 ir_val val;
628 val.d = c;
629 return ir_const(ctx, val, IR_DOUBLE);
630 }
631
632 ir_ref ir_const_addr(ir_ctx *ctx, uintptr_t c)
633 {
634 if (c == 0) {
635 return IR_NULL;
636 }
637 ir_val val;
638 val.u64 = c;
639 return ir_const(ctx, val, IR_ADDR);
640 }
641
642 ir_ref ir_const_func_addr(ir_ctx *ctx, uintptr_t c, ir_ref proto)
643 {
644 if (c == 0) {
645 return IR_NULL;
646 }
647 ir_val val;
648 val.u64 = c;
649 IR_ASSERT(proto >= 0 && proto < 0xffff);
650 return ir_const_ex(ctx, val, IR_ADDR, IR_OPTX(IR_FUNC_ADDR, IR_ADDR, proto));
651 }
652
653 ir_ref ir_const_func(ir_ctx *ctx, ir_ref str, ir_ref proto)
654 {
655 ir_val val;
656 val.u64 = str;
657 IR_ASSERT(proto >= 0 && proto < 0xffff);
658 return ir_const_ex(ctx, val, IR_ADDR, IR_OPTX(IR_FUNC, IR_ADDR, proto));
659 }
660
661 ir_ref ir_const_sym(ir_ctx *ctx, ir_ref str)
662 {
663 ir_val val;
664 val.u64 = str;
665 return ir_const_ex(ctx, val, IR_ADDR, IR_OPTX(IR_SYM, IR_ADDR, 0));
666 }
667
668 ir_ref ir_const_str(ir_ctx *ctx, ir_ref str)
669 {
670 ir_val val;
671 val.u64 = str;
672 return ir_const_ex(ctx, val, IR_ADDR, IR_OPTX(IR_STR, IR_ADDR, 0));
673 }
674
675 ir_ref ir_str(ir_ctx *ctx, const char *s)
676 {
677 size_t len;
678
679 if (!ctx->strtab.data) {
680 ir_strtab_init(&ctx->strtab, 64, 4096);
681 }
682 len = strlen(s);
683 IR_ASSERT(len <= 0xffffffff);
684 return ir_strtab_lookup(&ctx->strtab, s, (uint32_t)len, ir_strtab_count(&ctx->strtab) + 1);
685 }
686
687 ir_ref ir_strl(ir_ctx *ctx, const char *s, size_t len)
688 {
689 if (!ctx->strtab.data) {
690 ir_strtab_init(&ctx->strtab, 64, 4096);
691 }
692 IR_ASSERT(len <= 0xffffffff);
693 return ir_strtab_lookup(&ctx->strtab, s, (uint32_t)len, ir_strtab_count(&ctx->strtab) + 1);
694 }
695
696 const char *ir_get_str(const ir_ctx *ctx, ir_ref idx)
697 {
698 IR_ASSERT(ctx->strtab.data);
699 return ir_strtab_str(&ctx->strtab, idx - 1);
700 }
701
702 const char *ir_get_strl(const ir_ctx *ctx, ir_ref idx, size_t *len)
703 {
704 IR_ASSERT(ctx->strtab.data);
705 return ir_strtab_strl(&ctx->strtab, idx - 1, len);
706 }
707
708 ir_ref ir_proto_0(ir_ctx *ctx, uint8_t flags, ir_type ret_type)
709 {
710 ir_proto_t proto;
711
712 proto.flags = flags;
713 proto.ret_type = ret_type;
714 proto.params_count = 0;
715 return ir_strl(ctx, (const char *)&proto, offsetof(ir_proto_t, param_types) + 0);
716 }
717
718 ir_ref ir_proto_1(ir_ctx *ctx, uint8_t flags, ir_type ret_type, ir_type t1)
719 {
720 ir_proto_t proto;
721
722 proto.flags = flags;
723 proto.ret_type = ret_type;
724 proto.params_count = 1;
725 proto.param_types[0] = t1;
726 return ir_strl(ctx, (const char *)&proto, offsetof(ir_proto_t, param_types) + 1);
727 }
728
729 ir_ref ir_proto_2(ir_ctx *ctx, uint8_t flags, ir_type ret_type, ir_type t1, ir_type t2)
730 {
731 ir_proto_t proto;
732
733 proto.flags = flags;
734 proto.ret_type = ret_type;
735 proto.params_count = 2;
736 proto.param_types[0] = t1;
737 proto.param_types[1] = t2;
738 return ir_strl(ctx, (const char *)&proto, offsetof(ir_proto_t, param_types) + 2);
739 }
740
741 ir_ref ir_proto_3(ir_ctx *ctx, uint8_t flags, ir_type ret_type, ir_type t1, ir_type t2, ir_type t3)
742 {
743 ir_proto_t proto;
744
745 proto.flags = flags;
746 proto.ret_type = ret_type;
747 proto.params_count = 3;
748 proto.param_types[0] = t1;
749 proto.param_types[1] = t2;
750 proto.param_types[2] = t3;
751 return ir_strl(ctx, (const char *)&proto, offsetof(ir_proto_t, param_types) + 3);
752 }
753
754 ir_ref ir_proto_4(ir_ctx *ctx, uint8_t flags, ir_type ret_type, ir_type t1, ir_type t2, ir_type t3,
755 ir_type t4)
756 {
757 ir_proto_t proto;
758
759 proto.flags = flags;
760 proto.ret_type = ret_type;
761 proto.params_count = 4;
762 proto.param_types[0] = t1;
763 proto.param_types[1] = t2;
764 proto.param_types[2] = t3;
765 proto.param_types[3] = t4;
766 return ir_strl(ctx, (const char *)&proto, offsetof(ir_proto_t, param_types) + 4);
767 }
768
769 ir_ref ir_proto_5(ir_ctx *ctx, uint8_t flags, ir_type ret_type, ir_type t1, ir_type t2, ir_type t3,
770 ir_type t4, ir_type t5)
771 {
772 ir_proto_t proto;
773
774 proto.flags = flags;
775 proto.ret_type = ret_type;
776 proto.params_count = 5;
777 proto.param_types[0] = t1;
778 proto.param_types[1] = t2;
779 proto.param_types[2] = t3;
780 proto.param_types[3] = t4;
781 proto.param_types[4] = t5;
782 return ir_strl(ctx, (const char *)&proto, offsetof(ir_proto_t, param_types) + 5);
783 }
784
785 ir_ref ir_proto(ir_ctx *ctx, uint8_t flags, ir_type ret_type, uint32_t params_count, uint8_t *param_types)
786 {
787 ir_proto_t *proto = alloca(offsetof(ir_proto_t, param_types) + params_count);
788
789 IR_ASSERT(params_count <= IR_MAX_PROTO_PARAMS);
790 proto->flags = flags;
791 proto->ret_type = ret_type;
792 proto->params_count = params_count;
793 memcpy(proto->param_types, param_types, params_count);
794 return ir_strl(ctx, (const char *)proto, offsetof(ir_proto_t, param_types) + params_count);
795 }
796
797 /* IR construction */
798 ir_ref ir_emit(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2, ir_ref op3)
799 {
800 ir_ref ref = ir_next_insn(ctx);
801 ir_insn *insn = &ctx->ir_base[ref];
802
803 insn->optx = opt;
804 insn->op1 = op1;
805 insn->op2 = op2;
806 insn->op3 = op3;
807
808 return ref;
809 }
810
811 ir_ref ir_emit0(ir_ctx *ctx, uint32_t opt)
812 {
813 return ir_emit(ctx, opt, IR_UNUSED, IR_UNUSED, IR_UNUSED);
814 }
815
816 ir_ref ir_emit1(ir_ctx *ctx, uint32_t opt, ir_ref op1)
817 {
818 return ir_emit(ctx, opt, op1, IR_UNUSED, IR_UNUSED);
819 }
820
821 ir_ref ir_emit2(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2)
822 {
823 return ir_emit(ctx, opt, op1, op2, IR_UNUSED);
824 }
825
826 ir_ref ir_emit3(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2, ir_ref op3)
827 {
828 return ir_emit(ctx, opt, op1, op2, op3);
829 }
830
831 static ir_ref _ir_fold_cse(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2, ir_ref op3)
832 {
833 ir_ref ref = ctx->prev_insn_chain[opt & IR_OPT_OP_MASK];
834 ir_insn *insn;
835
836 if (ref) {
837 ir_ref limit = ctx->fold_cse_limit;
838
839 if (op1 > limit) {
840 limit = op1;
841 }
842 if (op2 > limit) {
843 limit = op2;
844 }
845 if (op3 > limit) {
846 limit = op3;
847 }
848 while (ref >= limit) {
849 insn = &ctx->ir_base[ref];
850 if (insn->opt == opt && insn->op1 == op1 && insn->op2 == op2 && insn->op3 == op3) {
851 return ref;
852 }
853 if (!insn->prev_insn_offset) {
854 break;
855 }
856 ref = ref - (ir_ref)(uint32_t)insn->prev_insn_offset;
857 }
858 }
859
860 return IR_UNUSED;
861 }
862
863 #define IR_FOLD(X) IR_FOLD1(X, __LINE__)
864 #define IR_FOLD1(X, Y) IR_FOLD2(X, Y)
865 #define IR_FOLD2(X, Y) case IR_RULE_ ## Y:
866
867 #define IR_FOLD_ERROR(msg) do { \
868 IR_ASSERT(0 && (msg)); \
869 goto ir_fold_emit; \
870 } while (0)
871
872 #define IR_FOLD_CONST_U(_val) do { \
873 val.u64 = (_val); \
874 goto ir_fold_const; \
875 } while (0)
876
877 #define IR_FOLD_CONST_I(_val) do { \
878 val.i64 = (_val); \
879 goto ir_fold_const; \
880 } while (0)
881
882 #define IR_FOLD_CONST_D(_val) do { \
883 val.d = (_val); \
884 goto ir_fold_const; \
885 } while (0)
886
887 #define IR_FOLD_CONST_F(_val) do { \
888 val.f = (_val); \
889 val.u32_hi = 0; \
890 goto ir_fold_const; \
891 } while (0)
892
893 #define IR_FOLD_COPY(op) do { \
894 ref = (op); \
895 goto ir_fold_copy; \
896 } while (0)
897
898 #define IR_FOLD_BOOL(cond) \
899 IR_FOLD_COPY((cond) ? IR_TRUE : IR_FALSE)
900
901 #define IR_FOLD_NAMED(name) ir_fold_ ## name:
902 #define IR_FOLD_DO_NAMED(name) goto ir_fold_ ## name
903 #define IR_FOLD_RESTART goto ir_fold_restart
904 #define IR_FOLD_CSE goto ir_fold_cse
905 #define IR_FOLD_EMIT goto ir_fold_emit
906 #define IR_FOLD_NEXT break
907
908 #include "ir_fold_hash.h"
909
910 #define IR_FOLD_RULE(x) ((x) >> 21)
911 #define IR_FOLD_KEY(x) ((x) & 0x1fffff)
912
913 /*
914 * key = insn->op | (insn->op1->op << 7) | (insn->op2->op << 14)
915 *
916 * ANY and UNUSED ops are represented by 0
917 */
918
919 ir_ref ir_folding(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2, ir_ref op3, ir_insn *op1_insn, ir_insn *op2_insn, ir_insn *op3_insn)
920 {
921 uint8_t op;
922 ir_ref ref;
923 ir_val val;
924 uint32_t key, any;
925 (void) op3_insn;
926
927 restart:
928 key = (opt & IR_OPT_OP_MASK) + ((uint32_t)op1_insn->op << 7) + ((uint32_t)op2_insn->op << 14);
929 any = 0x1fffff;
930 do {
931 uint32_t k = key & any;
932 uint32_t h = _ir_fold_hashkey(k);
933 uint32_t fh = _ir_fold_hash[h];
934 if (IR_FOLD_KEY(fh) == k
935 #ifdef IR_FOLD_SEMI_PERFECT_HASH
936 || (fh = _ir_fold_hash[h+1], (fh & 0x1fffff) == k)
937 #endif
938 ) {
939 switch (IR_FOLD_RULE(fh)) {
940 #include "ir_fold.h"
941 default:
942 break;
943 }
944 }
945 if (any == 0x7f) {
946 /* All parrerns are checked. Pass on to CSE. */
947 goto ir_fold_cse;
948 }
949 /* op2/op1/op op2/_/op _/op1/op _/_/op
950 * 0x1fffff -> 0x1fc07f -> 0x003fff -> 0x00007f
951 * from masks to bis: 11 -> 10 -> 01 -> 00
952 *
953 * a b => x y
954 * 1 1 1 0
955 * 1 0 0 1
956 * 0 1 0 0
957 *
958 * x = a & b; y = !b
959 */
960 any = ((any & (any << 7)) & 0x1fc000) | (~any & 0x3f80) | 0x7f;
961 } while (1);
962
963 ir_fold_restart:
964 if (!(ctx->flags2 & IR_OPT_IN_SCCP)) {
965 op1_insn = ctx->ir_base + op1;
966 op2_insn = ctx->ir_base + op2;
967 op3_insn = ctx->ir_base + op3;
968 goto restart;
969 } else {
970 ctx->fold_insn.optx = opt;
971 ctx->fold_insn.op1 = op1;
972 ctx->fold_insn.op2 = op2;
973 ctx->fold_insn.op3 = op3;
974 return IR_FOLD_DO_RESTART;
975 }
976 ir_fold_cse:
977 if (!(ctx->flags2 & IR_OPT_IN_SCCP)) {
978 /* Local CSE */
979 ref = _ir_fold_cse(ctx, opt, op1, op2, op3);
980 if (ref) {
981 return ref;
982 }
983
984 ref = ir_emit(ctx, opt, op1, op2, op3);
985
986 /* Update local CSE chain */
987 op = opt & IR_OPT_OP_MASK;
988 ir_ref prev = ctx->prev_insn_chain[op];
989 ir_insn *insn = ctx->ir_base + ref;
990 if (!prev || ref - prev > 0xffff) {
991 /* can't fit into 16-bit */
992 insn->prev_insn_offset = 0;
993 } else {
994 insn->prev_insn_offset = ref - prev;
995 }
996 ctx->prev_insn_chain[op] = ref;
997
998 return ref;
999 }
1000 ir_fold_emit:
1001 if (!(ctx->flags2 & IR_OPT_IN_SCCP)) {
1002 return ir_emit(ctx, opt, op1, op2, op3);
1003 } else {
1004 ctx->fold_insn.optx = opt;
1005 ctx->fold_insn.op1 = op1;
1006 ctx->fold_insn.op2 = op2;
1007 ctx->fold_insn.op3 = op3;
1008 return IR_FOLD_DO_EMIT;
1009 }
1010 ir_fold_copy:
1011 if (!(ctx->flags2 & IR_OPT_IN_SCCP)) {
1012 return ref;
1013 } else {
1014 ctx->fold_insn.op1 = ref;
1015 return IR_FOLD_DO_COPY;
1016 }
1017 ir_fold_const:
1018 if (!(ctx->flags2 & IR_OPT_IN_SCCP)) {
1019 return ir_const(ctx, val, IR_OPT_TYPE(opt));
1020 } else {
1021 ctx->fold_insn.type = IR_OPT_TYPE(opt);
1022 ctx->fold_insn.val.u64 = val.u64;
1023 return IR_FOLD_DO_CONST;
1024 }
1025 }
1026
1027 ir_ref ir_fold(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2, ir_ref op3)
1028 {
1029 if (UNEXPECTED(!(ctx->flags & IR_OPT_FOLDING))) {
1030 if ((opt & IR_OPT_OP_MASK) == IR_PHI) {
1031 opt |= (3 << IR_OPT_INPUTS_SHIFT);
1032 }
1033 return ir_emit(ctx, opt, op1, op2, op3);
1034 }
1035 return ir_folding(ctx, opt, op1, op2, op3, ctx->ir_base + op1, ctx->ir_base + op2, ctx->ir_base + op3);
1036 }
1037
1038 ir_ref ir_fold0(ir_ctx *ctx, uint32_t opt)
1039 {
1040 return ir_fold(ctx, opt, IR_UNUSED, IR_UNUSED, IR_UNUSED);
1041 }
1042
1043 ir_ref ir_fold1(ir_ctx *ctx, uint32_t opt, ir_ref op1)
1044 {
1045 return ir_fold(ctx, opt, op1, IR_UNUSED, IR_UNUSED);
1046 }
1047
1048 ir_ref ir_fold2(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2)
1049 {
1050 return ir_fold(ctx, opt, op1, op2, IR_UNUSED);
1051 }
1052
1053 ir_ref ir_fold3(ir_ctx *ctx, uint32_t opt, ir_ref op1, ir_ref op2, ir_ref op3)
1054 {
1055 return ir_fold(ctx, opt, op1, op2, op3);
1056 }
1057
1058 ir_ref ir_emit_N(ir_ctx *ctx, uint32_t opt, int32_t count)
1059 {
1060 int i;
1061 ir_ref *p, ref = ctx->insns_count;
1062 ir_insn *insn;
1063
1064 IR_ASSERT(count >= 0);
1065 while (UNEXPECTED(ref + count/4 >= ctx->insns_limit)) {
1066 ir_grow_top(ctx);
1067 }
1068 ctx->insns_count = ref + 1 + count/4;
1069
1070 insn = &ctx->ir_base[ref];
1071 insn->optx = opt | (count << IR_OPT_INPUTS_SHIFT);
1072 for (i = 1, p = insn->ops + i; i <= (count|3); i++, p++) {
1073 *p = IR_UNUSED;
1074 }
1075
1076 return ref;
1077 }
1078
1079 void ir_set_op(ir_ctx *ctx, ir_ref ref, int32_t n, ir_ref val)
1080 {
1081 ir_insn *insn = &ctx->ir_base[ref];
1082
1083 #ifdef IR_DEBUG
1084 if (n > 3) {
1085 int32_t count;
1086
1087 IR_ASSERT(IR_OP_HAS_VAR_INPUTS(ir_op_flags[insn->op]));
1088 count = insn->inputs_count;
1089 IR_ASSERT(n <= count);
1090 }
1091 #endif
1092 ir_insn_set_op(insn, n, val);
1093 }
1094
1095 ir_ref ir_param(ir_ctx *ctx, ir_type type, ir_ref region, const char *name, int pos)
1096 {
1097 return ir_emit(ctx, IR_OPT(IR_PARAM, type), region, ir_str(ctx, name), pos);
1098 }
1099
1100 ir_ref ir_var(ir_ctx *ctx, ir_type type, ir_ref region, const char *name)
1101 {
1102 return ir_emit(ctx, IR_OPT(IR_VAR, type), region, ir_str(ctx, name), IR_UNUSED);
1103 }
1104
1105 ir_ref ir_bind(ir_ctx *ctx, ir_ref var, ir_ref def)
1106 {
1107 if (IR_IS_CONST_REF(def)) {
1108 return def;
1109 }
1110 if (!ctx->binding) {
1111 ctx->binding = ir_mem_malloc(sizeof(ir_hashtab));;
1112 ir_hashtab_init(ctx->binding, 16);
1113 }
1114 /* Node may be bound to some special spill slot (using negative "var") */
1115 IR_ASSERT(var < 0);
1116 if (!ir_hashtab_add(ctx->binding, def, var)) {
1117 /* Add a copy with different binding */
1118 def = ir_emit2(ctx, IR_OPT(IR_COPY, ctx->ir_base[def].type), def, 1);
1119 ir_hashtab_add(ctx->binding, def, var);
1120 }
1121 return def;
1122 }
1123
1124 /* Batch construction of def->use edges */
1125 #if 0
1126 void ir_build_def_use_lists(ir_ctx *ctx)
1127 {
1128 ir_ref n, i, j, *p, def;
1129 ir_insn *insn;
1130 uint32_t edges_count;
1131 ir_use_list *lists = ir_mem_calloc(ctx->insns_count, sizeof(ir_use_list));
1132 ir_ref *edges;
1133 ir_use_list *use_list;
1134
1135 for (i = IR_UNUSED + 1, insn = ctx->ir_base + i; i < ctx->insns_count;) {
1136 uint32_t flags = ir_op_flags[insn->op];
1137
1138 if (UNEXPECTED(IR_OP_HAS_VAR_INPUTS(flags))) {
1139 n = insn->inputs_count;
1140 } else {
1141 n = insn->inputs_count = IR_INPUT_EDGES_COUNT(flags);
1142 }
1143 for (j = n, p = insn->ops + 1; j > 0; j--, p++) {
1144 def = *p;
1145 if (def > 0) {
1146 lists[def].count++;
1147 }
1148 }
1149 n = ir_insn_inputs_to_len(n);
1150 i += n;
1151 insn += n;
1152 }
1153
1154 edges_count = 0;
1155 for (i = IR_UNUSED + 1, use_list = &lists[i]; i < ctx->insns_count; i++, use_list++) {
1156 use_list->refs = edges_count;
1157 edges_count += use_list->count;
1158 use_list->count = 0;
1159 }
1160
1161 edges = ir_mem_malloc(edges_count * sizeof(ir_ref));
1162 for (i = IR_UNUSED + 1, insn = ctx->ir_base + i; i < ctx->insns_count;) {
1163 n = insn->inputs_count;
1164 for (j = n, p = insn->ops + 1; j > 0; j--, p++) {
1165 def = *p;
1166 if (def > 0) {
1167 use_list = &lists[def];
1168 edges[use_list->refs + use_list->count++] = i;
1169 }
1170 }
1171 n = ir_insn_inputs_to_len(n);
1172 i += n;
1173 insn += n;
1174 }
1175
1176 ctx->use_edges = edges;
1177 ctx->use_edges_count = edges_count;
1178 ctx->use_lists = lists;
1179 }
1180 #else
1181 void ir_build_def_use_lists(ir_ctx *ctx)
1182 {
1183 ir_ref n, i, j, *p, def;
1184 ir_insn *insn;
1185 size_t linked_lists_size, linked_lists_top = 0, edges_count = 0;
1186 ir_use_list *lists = ir_mem_calloc(ctx->insns_count, sizeof(ir_use_list));
1187 ir_ref *edges;
1188 ir_use_list *use_list;
1189 ir_ref *linked_lists;
1190
1191 linked_lists_size = IR_ALIGNED_SIZE(ctx->insns_count, 1024);
1192 linked_lists = ir_mem_malloc(linked_lists_size * sizeof(ir_ref));
1193 for (i = IR_UNUSED + 1, insn = ctx->ir_base + i; i < ctx->insns_count;) {
1194 uint32_t flags = ir_op_flags[insn->op];
1195
1196 if (UNEXPECTED(IR_OP_HAS_VAR_INPUTS(flags))) {
1197 n = insn->inputs_count;
1198 } else {
1199 n = insn->inputs_count = IR_INPUT_EDGES_COUNT(flags);
1200 }
1201 for (j = n, p = insn->ops + 1; j > 0; j--, p++) {
1202 def = *p;
1203 if (def > 0) {
1204 use_list = &lists[def];
1205 edges_count++;
1206 if (!use_list->refs) {
1207 /* store a single "use" directly in "refs" using a positive number */
1208 use_list->refs = i;
1209 use_list->count = 1;
1210 } else {
1211 if (UNEXPECTED(linked_lists_top >= linked_lists_size)) {
1212 linked_lists_size += 1024;
1213 linked_lists = ir_mem_realloc(linked_lists, linked_lists_size * sizeof(ir_ref));
1214 }
1215 /* form a linked list of "uses" (like in binsort) */
1216 linked_lists[linked_lists_top] = i; /* store the "use" */
1217 linked_lists[linked_lists_top + 1] = use_list->refs; /* store list next */
1218 use_list->refs = -(linked_lists_top + 1); /* store a head of the list using a negative number */
1219 linked_lists_top += 2;
1220 use_list->count++;
1221 }
1222 }
1223 }
1224 n = ir_insn_inputs_to_len(n);
1225 i += n;
1226 insn += n;
1227 }
1228
1229 ctx->use_edges_count = edges_count;
1230 edges = ir_mem_malloc(edges_count * sizeof(ir_ref));
1231 for (use_list = lists + ctx->insns_count - 1; use_list != lists; use_list--) {
1232 n = use_list->refs;
1233 if (n) {
1234 /* transform linked list to plain array */
1235 while (n < 0) {
1236 n = -n;
1237 edges[--edges_count] = linked_lists[n - 1];
1238 n = linked_lists[n];
1239 }
1240 IR_ASSERT(n > 0);
1241 edges[--edges_count] = n;
1242 use_list->refs = edges_count;
1243 }
1244 }
1245
1246 ctx->use_edges = edges;
1247 ctx->use_lists = lists;
1248 ir_mem_free(linked_lists);
1249 }
1250 #endif
1251
1252 void ir_use_list_remove_all(ir_ctx *ctx, ir_ref from, ir_ref ref)
1253 {
1254 ir_ref j, n, *p, *q, use;
1255 ir_use_list *use_list = &ctx->use_lists[from];
1256 ir_ref skip = 0;
1257
1258 n = use_list->count;
1259 for (j = 0, p = q = &ctx->use_edges[use_list->refs]; j < n; j++, p++) {
1260 use = *p;
1261 if (use == ref) {
1262 skip++;
1263 } else {
1264 if (p != q) {
1265 *q = use;
1266 }
1267 q++;
1268 }
1269 }
1270 if (skip) {
1271 use_list->count -= skip;
1272 do {
1273 *q = IR_UNUSED;
1274 q++;
1275 } while (--skip);
1276 }
1277 }
1278
1279 void ir_use_list_remove_one(ir_ctx *ctx, ir_ref from, ir_ref ref)
1280 {
1281 ir_ref j, n, *p;
1282 ir_use_list *use_list = &ctx->use_lists[from];
1283
1284 n = use_list->count;
1285 j = 0;
1286 p = &ctx->use_edges[use_list->refs];
1287 while (j < n) {
1288 if (*p == ref) {
1289 use_list->count--;
1290 j++;
1291 while (j < n) {
1292 *p = *(p+1);
1293 p++;
1294 j++;
1295 }
1296 *p = IR_UNUSED;
1297 break;
1298 }
1299 p++;
1300 j++;
1301 }
1302 }
1303
1304 void ir_use_list_replace_one(ir_ctx *ctx, ir_ref ref, ir_ref use, ir_ref new_use)
1305 {
1306 ir_use_list *use_list = &ctx->use_lists[ref];
1307 ir_ref i, n, *p;
1308
1309 n = use_list->count;
1310 for (i = 0, p = &ctx->use_edges[use_list->refs]; i < n; i++, p++) {
1311 if (*p == use) {
1312 *p = new_use;
1313 break;
1314 }
1315 }
1316 }
1317
1318 void ir_use_list_replace_all(ir_ctx *ctx, ir_ref ref, ir_ref use, ir_ref new_use)
1319 {
1320 ir_use_list *use_list = &ctx->use_lists[ref];
1321 ir_ref i, n, *p;
1322
1323 n = use_list->count;
1324 for (i = 0, p = &ctx->use_edges[use_list->refs]; i < n; i++, p++) {
1325 if (*p == use) {
1326 *p = new_use;
1327 }
1328 }
1329 }
1330
1331 bool ir_use_list_add(ir_ctx *ctx, ir_ref to, ir_ref ref)
1332 {
1333 ir_use_list *use_list = &ctx->use_lists[to];
1334 ir_ref n = use_list->refs + use_list->count;
1335
1336 if (n < ctx->use_edges_count && ctx->use_edges[n] == IR_UNUSED) {
1337 ctx->use_edges[n] = ref;
1338 use_list->count++;
1339 return 0;
1340 } else {
1341 /* Reallocate the whole edges buffer (this is inefficient) */
1342 ctx->use_edges = ir_mem_realloc(ctx->use_edges, (ctx->use_edges_count + use_list->count + 1) * sizeof(ir_ref));
1343 memcpy(ctx->use_edges + ctx->use_edges_count, ctx->use_edges + use_list->refs, use_list->count * sizeof(ir_ref));
1344 use_list->refs = ctx->use_edges_count;
1345 ctx->use_edges[use_list->refs + use_list->count] = ref;
1346 use_list->count++;
1347 ctx->use_edges_count += use_list->count;
1348 return 1;
1349 }
1350 }
1351
1352 /* Helper Data Types */
1353 void ir_array_grow(ir_array *a, uint32_t size)
1354 {
1355 IR_ASSERT(size > a->size);
1356 a->refs = ir_mem_realloc(a->refs, size * sizeof(ir_ref));
1357 a->size = size;
1358 }
1359
1360 void ir_array_insert(ir_array *a, uint32_t i, ir_ref val)
1361 {
1362 IR_ASSERT(i < a->size);
1363 if (a->refs[a->size - 1]) {
1364 ir_array_grow(a, a->size + 1);
1365 }
1366 memmove(a->refs + i + 1, a->refs + i, (a->size - i - 1) * sizeof(ir_ref));
1367 a->refs[i] = val;
1368 }
1369
1370 void ir_array_remove(ir_array *a, uint32_t i)
1371 {
1372 IR_ASSERT(i < a->size);
1373 memmove(a->refs + i, a->refs + i + 1, (a->size - i - 1) * sizeof(ir_ref));
1374 a->refs[a->size - 1] = IR_UNUSED;
1375 }
1376
1377 void ir_list_insert(ir_list *l, uint32_t i, ir_ref val)
1378 {
1379 IR_ASSERT(i < l->len);
1380 if (l->len >= l->a.size) {
1381 ir_array_grow(&l->a, l->a.size + 1);
1382 }
1383 memmove(l->a.refs + i + 1, l->a.refs + i, (l->len - i) * sizeof(ir_ref));
1384 l->a.refs[i] = val;
1385 l->len++;
1386 }
1387
1388 void ir_list_remove(ir_list *l, uint32_t i)
1389 {
1390 IR_ASSERT(i < l->len);
1391 memmove(l->a.refs + i, l->a.refs + i + 1, (l->len - i) * sizeof(ir_ref));
1392 l->len--;
1393 }
1394
1395 bool ir_list_contains(const ir_list *l, ir_ref val)
1396 {
1397 uint32_t i;
1398
1399 for (i = 0; i < l->len; i++) {
1400 if (ir_array_at(&l->a, i) == val) {
1401 return 1;
1402 }
1403 }
1404 return 0;
1405 }
1406
1407 static uint32_t ir_hashtab_hash_size(uint32_t size)
1408 {
1409 size -= 1;
1410 size |= (size >> 1);
1411 size |= (size >> 2);
1412 size |= (size >> 4);
1413 size |= (size >> 8);
1414 size |= (size >> 16);
1415 return IR_MAX(size + 1, 4);
1416 }
1417
1418 static void ir_hashtab_resize(ir_hashtab *tab)
1419 {
1420 uint32_t old_hash_size = (uint32_t)(-(int32_t)tab->mask);
1421 char *old_data = tab->data;
1422 uint32_t size = tab->size * 2;
1423 uint32_t hash_size = ir_hashtab_hash_size(size);
1424 char *data = ir_mem_malloc(hash_size * sizeof(uint32_t) + size * sizeof(ir_hashtab_bucket));
1425 ir_hashtab_bucket *p;
1426 uint32_t pos, i;
1427
1428 memset(data, -1, hash_size * sizeof(uint32_t));
1429 tab->data = data + (hash_size * sizeof(uint32_t));
1430 tab->mask = (uint32_t)(-(int32_t)hash_size);
1431 tab->size = size;
1432
1433 memcpy(tab->data, old_data, tab->count * sizeof(ir_hashtab_bucket));
1434 ir_mem_free(old_data - (old_hash_size * sizeof(uint32_t)));
1435
1436 i = tab->count;
1437 pos = 0;
1438 p = (ir_hashtab_bucket*)tab->data;
1439 do {
1440 uint32_t key = p->key | tab->mask;
1441 p->next = ((uint32_t*)tab->data)[(int32_t)key];
1442 ((uint32_t*)tab->data)[(int32_t)key] = pos;
1443 pos += sizeof(ir_hashtab_bucket);
1444 p++;
1445 } while (--i);
1446 }
1447
1448 void ir_hashtab_init(ir_hashtab *tab, uint32_t size)
1449 {
1450 IR_ASSERT(size > 0);
1451 uint32_t hash_size = ir_hashtab_hash_size(size);
1452 char *data = ir_mem_malloc(hash_size * sizeof(uint32_t) + size * sizeof(ir_hashtab_bucket));
1453 memset(data, -1, hash_size * sizeof(uint32_t));
1454 tab->data = (data + (hash_size * sizeof(uint32_t)));
1455 tab->mask = (uint32_t)(-(int32_t)hash_size);
1456 tab->size = size;
1457 tab->count = 0;
1458 tab->pos = 0;
1459 }
1460
1461 void ir_hashtab_free(ir_hashtab *tab)
1462 {
1463 uint32_t hash_size = (uint32_t)(-(int32_t)tab->mask);
1464 char *data = (char*)tab->data - (hash_size * sizeof(uint32_t));
1465 ir_mem_free(data);
1466 tab->data = NULL;
1467 }
1468
1469 ir_ref ir_hashtab_find(const ir_hashtab *tab, uint32_t key)
1470 {
1471 const char *data = (const char*)tab->data;
1472 uint32_t pos = ((uint32_t*)data)[(int32_t)(key | tab->mask)];
1473 ir_hashtab_bucket *p;
1474
1475 while (pos != IR_INVALID_IDX) {
1476 p = (ir_hashtab_bucket*)(data + pos);
1477 if (p->key == key) {
1478 return p->val;
1479 }
1480 pos = p->next;
1481 }
1482 return IR_INVALID_VAL;
1483 }
1484
1485 bool ir_hashtab_add(ir_hashtab *tab, uint32_t key, ir_ref val)
1486 {
1487 char *data = (char*)tab->data;
1488 uint32_t pos = ((uint32_t*)data)[(int32_t)(key | tab->mask)];
1489 ir_hashtab_bucket *p;
1490
1491 while (pos != IR_INVALID_IDX) {
1492 p = (ir_hashtab_bucket*)(data + pos);
1493 if (p->key == key) {
1494 return p->val == val;
1495 }
1496 pos = p->next;
1497 }
1498
1499 if (UNEXPECTED(tab->count >= tab->size)) {
1500 ir_hashtab_resize(tab);
1501 data = tab->data;
1502 }
1503
1504 pos = tab->pos;
1505 tab->pos += sizeof(ir_hashtab_bucket);
1506 tab->count++;
1507 p = (ir_hashtab_bucket*)(data + pos);
1508 p->key = key;
1509 p->val = val;
1510 key |= tab->mask;
1511 p->next = ((uint32_t*)data)[(int32_t)key];
1512 ((uint32_t*)data)[(int32_t)key] = pos;
1513 return 1;
1514 }
1515
1516 static int ir_hashtab_key_cmp(const void *b1, const void *b2)
1517 {
1518 return ((ir_hashtab_bucket*)b1)->key - ((ir_hashtab_bucket*)b2)->key;
1519 }
1520
1521 void ir_hashtab_key_sort(ir_hashtab *tab)
1522 {
1523 ir_hashtab_bucket *p;
1524 uint32_t hash_size, pos, i;
1525
1526 if (!tab->count) {
1527 return;
1528 }
1529
1530 qsort(tab->data, tab->count, sizeof(ir_hashtab_bucket), ir_hashtab_key_cmp);
1531
1532 hash_size = ir_hashtab_hash_size(tab->size);
1533 memset((char*)tab->data - (hash_size * sizeof(uint32_t)), -1, hash_size * sizeof(uint32_t));
1534
1535 i = tab->count;
1536 pos = 0;
1537 p = (ir_hashtab_bucket*)tab->data;
1538 do {
1539 uint32_t key = p->key | tab->mask;
1540 p->next = ((uint32_t*)tab->data)[(int32_t)key];
1541 ((uint32_t*)tab->data)[(int32_t)key] = pos;
1542 pos += sizeof(ir_hashtab_bucket);
1543 p++;
1544 } while (--i);
1545 }
1546
1547 static void ir_addrtab_resize(ir_hashtab *tab)
1548 {
1549 uint32_t old_hash_size = (uint32_t)(-(int32_t)tab->mask);
1550 char *old_data = tab->data;
1551 uint32_t size = tab->size * 2;
1552 uint32_t hash_size = ir_hashtab_hash_size(size);
1553 char *data = ir_mem_malloc(hash_size * sizeof(uint32_t) + size * sizeof(ir_addrtab_bucket));
1554 ir_addrtab_bucket *p;
1555 uint32_t pos, i;
1556
1557 memset(data, -1, hash_size * sizeof(uint32_t));
1558 tab->data = data + (hash_size * sizeof(uint32_t));
1559 tab->mask = (uint32_t)(-(int32_t)hash_size);
1560 tab->size = size;
1561
1562 memcpy(tab->data, old_data, tab->count * sizeof(ir_addrtab_bucket));
1563 ir_mem_free(old_data - (old_hash_size * sizeof(uint32_t)));
1564
1565 i = tab->count;
1566 pos = 0;
1567 p = (ir_addrtab_bucket*)tab->data;
1568 do {
1569 uint32_t key = (uint32_t)p->key | tab->mask;
1570 p->next = ((uint32_t*)tab->data)[(int32_t)key];
1571 ((uint32_t*)tab->data)[(int32_t)key] = pos;
1572 pos += sizeof(ir_addrtab_bucket);
1573 p++;
1574 } while (--i);
1575 }
1576
1577 void ir_addrtab_init(ir_hashtab *tab, uint32_t size)
1578 {
1579 IR_ASSERT(size > 0);
1580 uint32_t hash_size = ir_hashtab_hash_size(size);
1581 char *data = ir_mem_malloc(hash_size * sizeof(uint32_t) + size * sizeof(ir_addrtab_bucket));
1582 memset(data, -1, hash_size * sizeof(uint32_t));
1583 tab->data = (data + (hash_size * sizeof(uint32_t)));
1584 tab->mask = (uint32_t)(-(int32_t)hash_size);
1585 tab->size = size;
1586 tab->count = 0;
1587 tab->pos = 0;
1588 }
1589
1590 void ir_addrtab_free(ir_hashtab *tab)
1591 {
1592 uint32_t hash_size = (uint32_t)(-(int32_t)tab->mask);
1593 char *data = (char*)tab->data - (hash_size * sizeof(uint32_t));
1594 ir_mem_free(data);
1595 tab->data = NULL;
1596 }
1597
1598 ir_ref ir_addrtab_find(const ir_hashtab *tab, uint64_t key)
1599 {
1600 const char *data = (const char*)tab->data;
1601 uint32_t pos = ((uint32_t*)data)[(int32_t)(key | tab->mask)];
1602 ir_addrtab_bucket *p;
1603
1604 while (pos != IR_INVALID_IDX) {
1605 p = (ir_addrtab_bucket*)(data + pos);
1606 if (p->key == key) {
1607 return p->val;
1608 }
1609 pos = p->next;
1610 }
1611 return IR_INVALID_VAL;
1612 }
1613
1614 void ir_addrtab_set(ir_hashtab *tab, uint64_t key, ir_ref val)
1615 {
1616 char *data = (char*)tab->data;
1617 uint32_t pos = ((uint32_t*)data)[(int32_t)(key | tab->mask)];
1618 ir_addrtab_bucket *p;
1619
1620 while (pos != IR_INVALID_IDX) {
1621 p = (ir_addrtab_bucket*)(data + pos);
1622 if (p->key == key) {
1623 p->val = val;
1624 return;
1625 }
1626 pos = p->next;
1627 }
1628
1629 if (UNEXPECTED(tab->count >= tab->size)) {
1630 ir_addrtab_resize(tab);
1631 data = tab->data;
1632 }
1633
1634 pos = tab->pos;
1635 tab->pos += sizeof(ir_addrtab_bucket);
1636 tab->count++;
1637 p = (ir_addrtab_bucket*)(data + pos);
1638 p->key = key;
1639 p->val = val;
1640 key |= tab->mask;
1641 p->next = ((uint32_t*)data)[(int32_t)key];
1642 ((uint32_t*)data)[(int32_t)key] = pos;
1643 }
1644
1645 /* Memory API */
1646 #ifdef _WIN32
1647 void *ir_mem_mmap(size_t size)
1648 {
1649 void *ret;
1650
1651 #ifdef _M_X64
1652 DWORD size_hi = size >> 32, size_lo = size & 0xffffffff;
1653 #else
1654 DWORD size_hi = 0, size_lo = size;
1655 #endif
1656
1657 HANDLE h = CreateFileMapping(INVALID_HANDLE_VALUE, NULL, PAGE_EXECUTE_READWRITE, size_hi, size_lo, NULL);
1658
1659 ret = MapViewOfFile(h, FILE_MAP_READ | FILE_MAP_WRITE | FILE_MAP_EXECUTE, 0, 0, size);
1660 if (!ret) {
1661 CloseHandle(h);
1662 }
1663
1664 return ret;
1665 }
1666
1667 int ir_mem_unmap(void *ptr, size_t size)
1668 {
1669 /* XXX file handle is leaked. */
1670 UnmapViewOfFile(ptr);
1671 return 1;
1672 }
1673
1674 int ir_mem_protect(void *ptr, size_t size)
1675 {
1676 return 1;
1677 }
1678
1679 int ir_mem_unprotect(void *ptr, size_t size)
1680 {
1681 return 1;
1682 }
1683
1684 int ir_mem_flush(void *ptr, size_t size)
1685 {
1686 return 1;
1687 }
1688 #else
1689 void *ir_mem_mmap(size_t size)
1690 {
1691 int prot_flags = PROT_EXEC;
1692 #if defined(__NetBSD__)
1693 prot_flags |= PROT_MPROTECT(PROT_READ|PROT_WRITE);
1694 #endif
1695 void *ret = mmap(NULL, size, prot_flags, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
1696 if (ret == MAP_FAILED) {
1697 ret = NULL;
1698 }
1699 return ret;
1700 }
1701
1702 int ir_mem_unmap(void *ptr, size_t size)
1703 {
1704 munmap(ptr, size);
1705 return 1;
1706 }
1707
1708 int ir_mem_protect(void *ptr, size_t size)
1709 {
1710 if (mprotect(ptr, size, PROT_READ | PROT_EXEC) != 0) {
1711 #ifdef IR_DEBUG
1712 fprintf(stderr, "mprotect() failed\n");
1713 #endif
1714 return 0;
1715 }
1716 return 1;
1717 }
1718
1719 int ir_mem_unprotect(void *ptr, size_t size)
1720 {
1721 if (mprotect(ptr, size, PROT_READ | PROT_WRITE) != 0) {
1722 #ifdef IR_DEBUG
1723 fprintf(stderr, "mprotect() failed\n");
1724 #endif
1725 return 0;
1726 }
1727 return 1;
1728 }
1729
1730 int ir_mem_flush(void *ptr, size_t size)
1731 {
1732 #if ((defined(__GNUC__) && ZEND_GCC_VERSION >= 4003) || __has_builtin(__builtin___clear_cache))
1733 __builtin___clear_cache((char*)(ptr), (char*)(ptr) + size);
1734 #endif
1735 #if defined(__APPLE__) && defined(__aarch64__)
1736 sys_icache_invalidate(ptr, size);
1737 #endif
1738 #ifdef HAVE_VALGRIND
1739 VALGRIND_DISCARD_TRANSLATIONS(ptr, size);
1740 #endif
1741 return 1;
1742 }
1743 #endif
1744
1745 /* Alias Analyses */
1746 typedef enum _ir_alias {
1747 IR_MAY_ALIAS = -1,
1748 IR_NO_ALIAS = 0,
1749 IR_MUST_ALIAS = 1,
1750 } ir_alias;
1751
1752 #if 0
1753 static ir_alias ir_check_aliasing(ir_ctx *ctx, ir_ref addr1, ir_ref addr2)
1754 {
1755 ir_insn *insn1, *insn2;
1756
1757 if (addr1 == addr2) {
1758 return IR_MUST_ALIAS;
1759 }
1760
1761 insn1 = &ctx->ir_base[addr1];
1762 insn2 = &ctx->ir_base[addr2];
1763 if (insn1->op == IR_ADD && IR_IS_CONST_REF(insn1->op2)) {
1764 if (insn1->op1 == addr2) {
1765 uintptr_t offset1 = ctx->ir_base[insn1->op2].val.u64;
1766 return (offset1 != 0) ? IR_MUST_ALIAS : IR_NO_ALIAS;
1767 } else if (insn2->op == IR_ADD && IR_IS_CONST_REF(insn1->op2) && insn1->op1 == insn2->op1) {
1768 if (insn1->op2 == insn2->op2) {
1769 return IR_MUST_ALIAS;
1770 } else if (IR_IS_CONST_REF(insn1->op2) && IR_IS_CONST_REF(insn2->op2)) {
1771 uintptr_t offset1 = ctx->ir_base[insn1->op2].val.u64;
1772 uintptr_t offset2 = ctx->ir_base[insn2->op2].val.u64;
1773
1774 return (offset1 == offset2) ? IR_MUST_ALIAS : IR_NO_ALIAS;
1775 }
1776 }
1777 } else if (insn2->op == IR_ADD && IR_IS_CONST_REF(insn2->op2)) {
1778 if (insn2->op1 == addr1) {
1779 uintptr_t offset2 = ctx->ir_base[insn2->op2].val.u64;
1780
1781 return (offset2 != 0) ? IR_MUST_ALIAS : IR_NO_ALIAS;
1782 }
1783 }
1784 return IR_MAY_ALIAS;
1785 }
1786 #endif
1787
1788 static ir_alias ir_check_partial_aliasing(const ir_ctx *ctx, ir_ref addr1, ir_ref addr2, ir_type type1, ir_type type2)
1789 {
1790 ir_insn *insn1, *insn2;
1791 ir_ref base1, base2, off1, off2;
1792
1793 /* this must be already check */
1794 IR_ASSERT(addr1 != addr2);
1795
1796 insn1 = &ctx->ir_base[addr1];
1797 insn2 = &ctx->ir_base[addr2];
1798 if (insn1->op != IR_ADD) {
1799 base1 = addr1;
1800 off1 = IR_UNUSED;
1801 } else if (ctx->ir_base[insn1->op2].op == IR_SYM
1802 || ctx->ir_base[insn1->op2].op == IR_ALLOCA
1803 || ctx->ir_base[insn1->op2].op == IR_VADDR) {
1804 base1 = insn1->op2;
1805 off1 = insn1->op1;
1806 } else {
1807 base1 = insn1->op1;
1808 off1 = insn1->op2;
1809 }
1810 if (insn2->op != IR_ADD) {
1811 base2 = addr2;
1812 off2 = IR_UNUSED;
1813 } else if (ctx->ir_base[insn2->op2].op == IR_SYM
1814 || ctx->ir_base[insn2->op2].op == IR_ALLOCA
1815 || ctx->ir_base[insn2->op2].op == IR_VADDR) {
1816 base2 = insn2->op2;
1817 off2 = insn2->op1;
1818 } else {
1819 base2 = insn2->op1;
1820 off2 = insn2->op2;
1821 }
1822 if (base1 == base2) {
1823 uintptr_t offset1, offset2;
1824
1825 if (!off1) {
1826 offset1 = 0;
1827 } else if (IR_IS_CONST_REF(off1) && !IR_IS_SYM_CONST(ctx->ir_base[off1].op)) {
1828 offset1 = ctx->ir_base[off1].val.addr;
1829 } else {
1830 return IR_MAY_ALIAS;
1831 }
1832 if (!off2) {
1833 offset2 = 0;
1834 } else if (IR_IS_CONST_REF(off2) && !IR_IS_SYM_CONST(ctx->ir_base[off2].op)) {
1835 offset2 = ctx->ir_base[off2].val.addr;
1836 } else {
1837 return IR_MAY_ALIAS;
1838 }
1839 if (offset1 == offset2) {
1840 return IR_MUST_ALIAS;
1841 } else if (offset1 < offset2) {
1842 return offset1 + ir_type_size[type1] <= offset2 ? IR_NO_ALIAS : IR_MUST_ALIAS;
1843 } else {
1844 return offset2 + ir_type_size[type2] <= offset1 ? IR_NO_ALIAS : IR_MUST_ALIAS;
1845 }
1846 } else {
1847 insn1 = &ctx->ir_base[base1];
1848 insn2 = &ctx->ir_base[base2];
1849 while (insn1->op == IR_ADD) {
1850 insn1 = &ctx->ir_base[insn1->op2];
1851 if (insn1->op == IR_SYM
1852 || insn1->op == IR_ALLOCA
1853 || insn1->op == IR_VADDR) {
1854 break;
1855 } else {
1856 insn1 = &ctx->ir_base[insn1->op1];
1857 }
1858 }
1859 while (insn2->op == IR_ADD) {
1860 insn2 = &ctx->ir_base[insn2->op2];
1861 if (insn2->op == IR_SYM
1862 || insn2->op == IR_ALLOCA
1863 || insn2->op == IR_VADDR) {
1864 break;
1865 } else {
1866 insn2 = &ctx->ir_base[insn2->op1];
1867 }
1868 }
1869 if (insn1 == insn2) {
1870 return IR_MAY_ALIAS;
1871 }
1872 if ((insn1->op == IR_ALLOCA && (insn2->op == IR_ALLOCA || insn2->op == IR_VADDR || insn2->op == IR_SYM || insn2->op == IR_PARAM))
1873 || (insn1->op == IR_VADDR && (insn2->op == IR_ALLOCA || insn2->op == IR_VADDR || insn2->op == IR_SYM || insn2->op == IR_PARAM))
1874 || (insn1->op == IR_SYM && (insn2->op == IR_ALLOCA || insn2->op == IR_VADDR || insn2->op == IR_SYM))
1875 || (insn1->op == IR_PARAM && (insn2->op == IR_ALLOCA || insn2->op == IR_VADDR))) {
1876 return IR_NO_ALIAS;
1877 }
1878 }
1879 return IR_MAY_ALIAS;
1880 }
1881
1882 static ir_ref ir_find_aliasing_load(ir_ctx *ctx, ir_ref ref, ir_type type, ir_ref addr)
1883 {
1884 ir_ref limit = (addr > 0) ? addr : 1;
1885 ir_insn *insn;
1886 uint32_t modified_regset = 0;
1887
1888 while (ref > limit) {
1889 insn = &ctx->ir_base[ref];
1890 if (insn->op == IR_LOAD) {
1891 if (insn->op2 == addr) {
1892 if (insn->type == type) {
1893 return ref; /* load forwarding (L2L) */
1894 } else if (ir_type_size[insn->type] == ir_type_size[type]) {
1895 return ir_fold1(ctx, IR_OPT(IR_BITCAST, type), ref); /* load forwarding with bitcast (L2L) */
1896 } else if (ir_type_size[insn->type] > ir_type_size[type]
1897 && IR_IS_TYPE_INT(type) && IR_IS_TYPE_INT(insn->type)) {
1898 return ir_fold1(ctx, IR_OPT(IR_TRUNC, type), ref); /* partial load forwarding (L2L) */
1899 }
1900 }
1901 } else if (insn->op == IR_STORE) {
1902 ir_type type2 = ctx->ir_base[insn->op3].type;
1903
1904 if (insn->op2 == addr) {
1905 if (ctx->ir_base[insn->op3].op == IR_RLOAD
1906 && (modified_regset & (1 << ctx->ir_base[insn->op3].op2))) {
1907 /* anti-dependency */
1908 return IR_UNUSED;
1909 } else if (type2 == type) {
1910 return insn->op3; /* store forwarding (S2L) */
1911 } else if (ir_type_size[type2] == ir_type_size[type]) {
1912 return ir_fold1(ctx, IR_OPT(IR_BITCAST, type), insn->op3); /* store forwarding with bitcast (S2L) */
1913 } else if (ir_type_size[type2] > ir_type_size[type]
1914 && IR_IS_TYPE_INT(type) && IR_IS_TYPE_INT(type2)) {
1915 return ir_fold1(ctx, IR_OPT(IR_TRUNC, type), insn->op3); /* partial store forwarding (S2L) */
1916 } else {
1917 return IR_UNUSED;
1918 }
1919 } else if (ir_check_partial_aliasing(ctx, addr, insn->op2, type, type2) != IR_NO_ALIAS) {
1920 return IR_UNUSED;
1921 }
1922 } else if (insn->op == IR_RSTORE) {
1923 modified_regset |= (1 << insn->op3);
1924 } else if (insn->op == IR_MERGE || insn->op == IR_LOOP_BEGIN || insn->op == IR_CALL || insn->op == IR_VSTORE) {
1925 return IR_UNUSED;
1926 }
1927 ref = insn->op1;
1928 }
1929 return IR_UNUSED;
1930 }
1931
1932 /* IR Construction API */
1933
1934 ir_ref _ir_PARAM(ir_ctx *ctx, ir_type type, const char* name, ir_ref num)
1935 {
1936 IR_ASSERT(ctx->control);
1937 IR_ASSERT(ctx->ir_base[ctx->control].op == IR_START);
1938 IR_ASSERT(ctx->insns_count == num + 1);
1939 return ir_param(ctx, type, ctx->control, name, num);
1940 }
1941
1942 ir_ref _ir_VAR(ir_ctx *ctx, ir_type type, const char* name)
1943 {
1944 // IR_ASSERT(ctx->control);
1945 // IR_ASSERT(IR_IS_BB_START(ctx->ir_base[ctx->control].op));
1946 // TODO: VAR may be insterted after some "memory" instruction
1947 ir_ref ref = ctx->control;
1948
1949 while (1) {
1950 IR_ASSERT(ctx->control);
1951 if (IR_IS_BB_START(ctx->ir_base[ref].op)) {
1952 break;
1953 }
1954 ref = ctx->ir_base[ref].op1;
1955 }
1956 return ir_var(ctx, type, ref, name);
1957 }
1958
1959 ir_ref _ir_PHI_2(ir_ctx *ctx, ir_type type, ir_ref src1, ir_ref src2)
1960 {
1961 IR_ASSERT(ctx->control);
1962 IR_ASSERT(ctx->ir_base[ctx->control].op == IR_MERGE || ctx->ir_base[ctx->control].op == IR_LOOP_BEGIN);
1963 if (src1 == src2 && src1 != IR_UNUSED) {
1964 return src1;
1965 }
1966 return ir_emit3(ctx, IR_OPTX(IR_PHI, type, 3), ctx->control, src1, src2);
1967 }
1968
1969 ir_ref _ir_PHI_N(ir_ctx *ctx, ir_type type, ir_ref n, ir_ref *inputs)
1970 {
1971 IR_ASSERT(ctx->control);
1972 IR_ASSERT(n > 0);
1973 if (n == 1) {
1974 return inputs[0];
1975 } else {
1976 ir_ref i;
1977 ir_ref ref = inputs[0];
1978
1979 IR_ASSERT(ctx->ir_base[ctx->control].op == IR_MERGE || ctx->ir_base[ctx->control].op == IR_LOOP_BEGIN);
1980 if (ref != IR_UNUSED) {
1981 for (i = 1; i < n; i++) {
1982 if (inputs[i] != ref) {
1983 break;
1984 }
1985 }
1986 if (i == n) {
1987 /* all the same */
1988 return ref;
1989 }
1990 }
1991
1992 ref = ir_emit_N(ctx, IR_OPT(IR_PHI, type), n + 1);
1993 ir_set_op(ctx, ref, 1, ctx->control);
1994 for (i = 0; i < n; i++) {
1995 ir_set_op(ctx, ref, i + 2, inputs[i]);
1996 }
1997 return ref;
1998 }
1999 }
2000
2001 void _ir_PHI_SET_OP(ir_ctx *ctx, ir_ref phi, ir_ref pos, ir_ref src)
2002 {
2003 ir_insn *insn = &ctx->ir_base[phi];
2004 ir_ref *ops = insn->ops;
2005
2006 IR_ASSERT(insn->op == IR_PHI);
2007 IR_ASSERT(ctx->ir_base[insn->op1].op == IR_MERGE || ctx->ir_base[insn->op1].op == IR_LOOP_BEGIN);
2008 IR_ASSERT(pos > 0 && pos < insn->inputs_count);
2009 pos++; /* op1 is used for control */
2010 ops[pos] = src;
2011 }
2012
2013 void _ir_START(ir_ctx *ctx)
2014 {
2015 IR_ASSERT(!ctx->control);
2016 IR_ASSERT(ctx->insns_count == 1);
2017 ctx->control = ir_emit0(ctx, IR_START);
2018 }
2019
2020 void _ir_ENTRY(ir_ctx *ctx, ir_ref src, ir_ref num)
2021 {
2022 IR_ASSERT(!ctx->control);
2023 /* fake control edge */
2024 IR_ASSERT((ir_op_flags[ctx->ir_base[src].op] & IR_OP_FLAG_TERMINATOR)
2025 || ctx->ir_base[src].op == IR_END
2026 || ctx->ir_base[src].op == IR_LOOP_END); /* return from a recursive call */
2027 ctx->control = ir_emit2(ctx, IR_ENTRY, src, num);
2028 }
2029
2030 void _ir_BEGIN(ir_ctx *ctx, ir_ref src)
2031 {
2032 IR_ASSERT(!ctx->control);
2033 if (src
2034 && src + 1 == ctx->insns_count
2035 && ctx->ir_base[src].op == IR_END) {
2036 /* merge with the last END */
2037 ctx->control = ctx->ir_base[src].op1;
2038 ctx->insns_count--;
2039 } else {
2040 ctx->control = ir_emit1(ctx, IR_BEGIN, src);
2041 }
2042 }
2043
2044 ir_ref _ir_fold_condition(ir_ctx *ctx, ir_ref ref)
2045 {
2046 ir_insn *insn = &ctx->ir_base[ref];
2047
2048 if (insn->op == IR_NE && IR_IS_CONST_REF(insn->op2)) {
2049 ir_insn *op2_insn = &ctx->ir_base[insn->op2];
2050
2051 if (IR_IS_TYPE_INT(op2_insn->type) && op2_insn->val.u64 == 0) {
2052 return insn->op1;
2053 }
2054 }
2055 return ref;
2056 }
2057
2058 ir_ref _ir_IF(ir_ctx *ctx, ir_ref condition)
2059 {
2060 ir_ref if_ref;
2061
2062 condition = _ir_fold_condition(ctx, condition);
2063 IR_ASSERT(ctx->control);
2064 if (IR_IS_CONST_REF(condition)) {
2065 condition = ir_ref_is_true(ctx, condition) ? IR_TRUE : IR_FALSE;
2066 } else {
2067 ir_insn *prev = NULL;
2068 ir_ref ref = ctx->control;
2069 ir_insn *insn;
2070
2071 while (ref > condition) {
2072 insn = &ctx->ir_base[ref];
2073 if (insn->op == IR_GUARD_NOT) {
2074 if (insn->op2 == condition) {
2075 condition = IR_FALSE;
2076 break;
2077 }
2078 } else if (insn->op == IR_GUARD) {
2079 if (insn->op2 == condition) {
2080 condition = IR_TRUE;
2081 break;
2082 }
2083 } else if (insn->op == IR_IF) {
2084 if (insn->op2 == condition) {
2085 if (prev->op == IR_IF_TRUE) {
2086 condition = IR_TRUE;
2087 break;
2088 } else if (prev->op == IR_IF_FALSE) {
2089 condition = IR_FALSE;
2090 break;
2091 }
2092 }
2093 } else if (insn->op == IR_START || insn->op == IR_MERGE || insn->op == IR_LOOP_BEGIN) {
2094 break;
2095 }
2096 prev = insn;
2097 ref = insn->op1;
2098 }
2099 }
2100 if_ref = ir_emit2(ctx, IR_IF, ctx->control, condition);
2101 ctx->control = IR_UNUSED;
2102 return if_ref;
2103 }
2104
2105 void _ir_IF_TRUE(ir_ctx *ctx, ir_ref if_ref)
2106 {
2107 IR_ASSERT(!ctx->control);
2108 IR_ASSERT(if_ref);
2109 IR_ASSERT(ctx->ir_base[if_ref].op == IR_IF);
2110 ctx->control = ir_emit1(ctx, IR_IF_TRUE, if_ref);
2111 }
2112
2113 void _ir_IF_TRUE_cold(ir_ctx *ctx, ir_ref if_ref)
2114 {
2115 IR_ASSERT(!ctx->control);
2116 IR_ASSERT(if_ref);
2117 IR_ASSERT(ctx->ir_base[if_ref].op == IR_IF);
2118 /* op2 is used as an indicator of low-probability branch */
2119 ctx->control = ir_emit2(ctx, IR_IF_TRUE, if_ref, 1);
2120 }
2121
2122 void _ir_IF_FALSE(ir_ctx *ctx, ir_ref if_ref)
2123 {
2124 IR_ASSERT(!ctx->control);
2125 IR_ASSERT(if_ref);
2126 IR_ASSERT(ctx->ir_base[if_ref].op == IR_IF);
2127 ctx->control = ir_emit1(ctx, IR_IF_FALSE, if_ref);
2128 }
2129
2130 void _ir_IF_FALSE_cold(ir_ctx *ctx, ir_ref if_ref)
2131 {
2132 IR_ASSERT(!ctx->control);
2133 IR_ASSERT(if_ref);
2134 IR_ASSERT(ctx->ir_base[if_ref].op == IR_IF);
2135 /* op2 is used as an indicator of low-probability branch */
2136 ctx->control = ir_emit2(ctx, IR_IF_FALSE, if_ref, 1);
2137 }
2138
2139 ir_ref _ir_END(ir_ctx *ctx)
2140 {
2141 ir_ref ref;
2142
2143 IR_ASSERT(ctx->control);
2144 ref = ir_emit1(ctx, IR_END, ctx->control);
2145 ctx->control = IR_UNUSED;
2146 return ref;
2147 }
2148
2149 void _ir_MERGE_2(ir_ctx *ctx, ir_ref src1, ir_ref src2)
2150 {
2151 IR_ASSERT(!ctx->control);
2152 ctx->control = ir_emit2(ctx, IR_OPTX(IR_MERGE, IR_VOID, 2), src1, src2);
2153 }
2154
2155 void _ir_MERGE_N(ir_ctx *ctx, ir_ref n, ir_ref *inputs)
2156 {
2157 IR_ASSERT(!ctx->control);
2158 IR_ASSERT(n > 0);
2159 if (n == 1) {
2160 _ir_BEGIN(ctx, inputs[0]);
2161 } else {
2162 ir_ref *ops;
2163
2164 ctx->control = ir_emit_N(ctx, IR_MERGE, n);
2165 ops = ctx->ir_base[ctx->control].ops;
2166 while (n) {
2167 n--;
2168 ops[n + 1] = inputs[n];
2169 }
2170 }
2171 }
2172
2173 void _ir_MERGE_SET_OP(ir_ctx *ctx, ir_ref merge, ir_ref pos, ir_ref src)
2174 {
2175 ir_insn *insn = &ctx->ir_base[merge];
2176 ir_ref *ops = insn->ops;
2177
2178 IR_ASSERT(insn->op == IR_MERGE || insn->op == IR_LOOP_BEGIN);
2179 IR_ASSERT(pos > 0 && pos <= insn->inputs_count);
2180 ops[pos] = src;
2181 }
2182
2183 ir_ref _ir_END_LIST(ir_ctx *ctx, ir_ref list)
2184 {
2185 ir_ref ref;
2186
2187 IR_ASSERT(ctx->control);
2188 IR_ASSERT(!list || ctx->ir_base[list].op == IR_END);
2189 /* create a liked list of END nodes with the same destination through END.op2 */
2190 ref = ir_emit2(ctx, IR_END, ctx->control, list);
2191 ctx->control = IR_UNUSED;
2192 return ref;
2193 }
2194
2195 ir_ref _ir_END_PHI_LIST(ir_ctx *ctx, ir_ref list, ir_ref val)
2196 {
2197 ir_ref ref;
2198
2199 IR_ASSERT(ctx->control);
2200 IR_ASSERT(!list || ctx->ir_base[list].op == IR_END);
2201 /* create a liked list of END nodes with the same destination through END.op2 */
2202 ref = ir_emit3(ctx, IR_END, ctx->control, list, val);
2203 ctx->control = IR_UNUSED;
2204 return ref;
2205 }
2206
2207 void _ir_MERGE_LIST(ir_ctx *ctx, ir_ref list)
2208 {
2209 ir_ref ref = list;
2210
2211 if (list != IR_UNUSED) {
2212 uint32_t n = 0;
2213
2214 IR_ASSERT(!ctx->control);
2215
2216 /* count inputs count */
2217 do {
2218 ir_insn *insn = &ctx->ir_base[ref];
2219
2220 IR_ASSERT(insn->op == IR_END);
2221 ref = insn->op2;
2222 n++;
2223 } while (ref != IR_UNUSED);
2224
2225
2226 /* create MERGE node */
2227 IR_ASSERT(n > 0);
2228 if (n == 1) {
2229 ctx->ir_base[list].op2 = IR_UNUSED;
2230 _ir_BEGIN(ctx, list);
2231 } else {
2232 ctx->control = ir_emit_N(ctx, IR_MERGE, n);
2233 ref = list;
2234 while (n) {
2235 ir_insn *insn = &ctx->ir_base[ref];
2236
2237 ir_set_op(ctx, ctx->control, n, ref);
2238 ref = insn->op2;
2239 insn->op2 = IR_UNUSED;
2240 n--;
2241 }
2242 }
2243 }
2244 }
2245
2246 ir_ref _ir_PHI_LIST(ir_ctx *ctx, ir_ref list)
2247 {
2248 ir_insn *merge, *end;
2249 ir_ref phi, *ops, i;
2250 ir_type type;
2251
2252 if (list == IR_UNUSED) {
2253 return IR_UNUSED;
2254 }
2255 end = &ctx->ir_base[list];
2256 if (!end->op2) {
2257 phi = end->op3;
2258 end->op3 = IR_UNUSED;
2259 _ir_BEGIN(ctx, list);
2260 } else if (!end->op3) {
2261 _ir_MERGE_LIST(ctx, list);
2262 phi = IR_UNUSED;
2263 } else {
2264 type = ctx->ir_base[end->op3].type;
2265 _ir_MERGE_LIST(ctx, list);
2266 merge = &ctx->ir_base[ctx->control];
2267 IR_ASSERT(merge->op == IR_MERGE);
2268 phi = ir_emit_N(ctx, IR_OPT(IR_PHI, type), merge->inputs_count + 1);
2269 merge = &ctx->ir_base[ctx->control];
2270 ops = merge->ops;
2271 ir_set_op(ctx, phi, 1, ctx->control);
2272 for (i = 0; i < merge->inputs_count; i++) {
2273 end = &ctx->ir_base[ops[i + 1]];
2274 ir_set_op(ctx, phi, i + 2, end->op3);
2275 end->op3 = IR_END;
2276 }
2277 }
2278 return phi;
2279 }
2280
2281 ir_ref _ir_LOOP_BEGIN(ir_ctx *ctx, ir_ref src1)
2282 {
2283 IR_ASSERT(!ctx->control);
2284 ctx->control = ir_emit2(ctx, IR_OPTX(IR_LOOP_BEGIN, IR_VOID, 2), src1, IR_UNUSED);
2285 return ctx->control;
2286 }
2287
2288 ir_ref _ir_LOOP_END(ir_ctx *ctx)
2289 {
2290 ir_ref ref;
2291
2292 IR_ASSERT(ctx->control);
2293 ref = ir_emit1(ctx, IR_LOOP_END, ctx->control);
2294 ctx->control = IR_UNUSED;
2295 return ref;
2296 }
2297
2298 ir_ref _ir_CALL(ir_ctx *ctx, ir_type type, ir_ref func)
2299 {
2300 IR_ASSERT(ctx->control);
2301 return ctx->control = ir_emit2(ctx, IR_OPTX(IR_CALL, type, 2), ctx->control, func);
2302 }
2303
2304 ir_ref _ir_CALL_1(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1)
2305 {
2306 IR_ASSERT(ctx->control);
2307 return ctx->control = ir_emit3(ctx, IR_OPTX(IR_CALL, type, 3), ctx->control, func, arg1);
2308 }
2309
2310 ir_ref _ir_CALL_2(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2)
2311 {
2312 ir_ref call;
2313
2314 IR_ASSERT(ctx->control);
2315 call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), 4);
2316 ir_set_op(ctx, call, 1, ctx->control);
2317 ir_set_op(ctx, call, 2, func);
2318 ir_set_op(ctx, call, 3, arg1);
2319 ir_set_op(ctx, call, 4, arg2);
2320 ctx->control = call;
2321 return call;
2322 }
2323
2324 ir_ref _ir_CALL_3(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3)
2325 {
2326 ir_ref call;
2327
2328 IR_ASSERT(ctx->control);
2329 call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), 5);
2330 ir_set_op(ctx, call, 1, ctx->control);
2331 ir_set_op(ctx, call, 2, func);
2332 ir_set_op(ctx, call, 3, arg1);
2333 ir_set_op(ctx, call, 4, arg2);
2334 ir_set_op(ctx, call, 5, arg3);
2335 ctx->control = call;
2336 return call;
2337 }
2338
2339 ir_ref _ir_CALL_4(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3, ir_ref arg4)
2340 {
2341 ir_ref call;
2342
2343 IR_ASSERT(ctx->control);
2344 call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), 6);
2345 ir_set_op(ctx, call, 1, ctx->control);
2346 ir_set_op(ctx, call, 2, func);
2347 ir_set_op(ctx, call, 3, arg1);
2348 ir_set_op(ctx, call, 4, arg2);
2349 ir_set_op(ctx, call, 5, arg3);
2350 ir_set_op(ctx, call, 6, arg4);
2351 ctx->control = call;
2352 return call;
2353 }
2354
2355 ir_ref _ir_CALL_5(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3, ir_ref arg4, ir_ref arg5)
2356 {
2357 ir_ref call;
2358
2359 IR_ASSERT(ctx->control);
2360 call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), 7);
2361 ir_set_op(ctx, call, 1, ctx->control);
2362 ir_set_op(ctx, call, 2, func);
2363 ir_set_op(ctx, call, 3, arg1);
2364 ir_set_op(ctx, call, 4, arg2);
2365 ir_set_op(ctx, call, 5, arg3);
2366 ir_set_op(ctx, call, 6, arg4);
2367 ir_set_op(ctx, call, 7, arg5);
2368 ctx->control = call;
2369 return call;
2370 }
2371
2372 ir_ref _ir_CALL_N(ir_ctx *ctx, ir_type type, ir_ref func, uint32_t count, ir_ref *args)
2373 {
2374 ir_ref call;
2375 uint32_t i;
2376
2377 IR_ASSERT(ctx->control);
2378 call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), count + 2);
2379 ir_set_op(ctx, call, 1, ctx->control);
2380 ir_set_op(ctx, call, 2, func);
2381 for (i = 0; i < count; i++) {
2382 ir_set_op(ctx, call, i + 3, args[i]);
2383 }
2384 ctx->control = call;
2385 return call;
2386 }
2387
2388 void _ir_UNREACHABLE(ir_ctx *ctx)
2389 {
2390 IR_ASSERT(ctx->control);
2391 ctx->control = ir_emit3(ctx, IR_UNREACHABLE, ctx->control, IR_UNUSED, ctx->ir_base[1].op1);
2392 ctx->ir_base[1].op1 = ctx->control;
2393 ctx->control = IR_UNUSED;
2394 }
2395
2396 void _ir_TAILCALL(ir_ctx *ctx, ir_type type, ir_ref func)
2397 {
2398 IR_ASSERT(ctx->control);
2399 if (ctx->ret_type == (ir_type)-1) {
2400 ctx->ret_type = type;
2401 }
2402 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2403 ctx->control = ir_emit2(ctx, IR_OPTX(IR_TAILCALL, type, 2), ctx->control, func);
2404 _ir_UNREACHABLE(ctx);
2405 }
2406
2407 void _ir_TAILCALL_1(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1)
2408 {
2409 IR_ASSERT(ctx->control);
2410 if (ctx->ret_type == (ir_type)-1) {
2411 ctx->ret_type = type;
2412 }
2413 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2414 ctx->control = ir_emit3(ctx, IR_OPTX(IR_TAILCALL, type, 3), ctx->control, func, arg1);
2415 _ir_UNREACHABLE(ctx);
2416 }
2417
2418 void _ir_TAILCALL_2(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2)
2419 {
2420 ir_ref call;
2421
2422 IR_ASSERT(ctx->control);
2423 if (ctx->ret_type == (ir_type)-1) {
2424 ctx->ret_type = type;
2425 }
2426 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2427 call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), 4);
2428 ir_set_op(ctx, call, 1, ctx->control);
2429 ir_set_op(ctx, call, 2, func);
2430 ir_set_op(ctx, call, 3, arg1);
2431 ir_set_op(ctx, call, 4, arg2);
2432 ctx->control = call;
2433 _ir_UNREACHABLE(ctx);
2434 }
2435
2436 void _ir_TAILCALL_3(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3)
2437 {
2438 ir_ref call;
2439
2440 IR_ASSERT(ctx->control);
2441 if (ctx->ret_type == (ir_type)-1) {
2442 ctx->ret_type = type;
2443 }
2444 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2445 call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), 5);
2446 ir_set_op(ctx, call, 1, ctx->control);
2447 ir_set_op(ctx, call, 2, func);
2448 ir_set_op(ctx, call, 3, arg1);
2449 ir_set_op(ctx, call, 4, arg2);
2450 ir_set_op(ctx, call, 5, arg3);
2451 ctx->control = call;
2452 _ir_UNREACHABLE(ctx);
2453 }
2454
2455 void _ir_TAILCALL_4(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3, ir_ref arg4)
2456 {
2457 ir_ref call;
2458
2459 IR_ASSERT(ctx->control);
2460 if (ctx->ret_type == (ir_type)-1) {
2461 ctx->ret_type = type;
2462 }
2463 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2464 call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), 6);
2465 ir_set_op(ctx, call, 1, ctx->control);
2466 ir_set_op(ctx, call, 2, func);
2467 ir_set_op(ctx, call, 3, arg1);
2468 ir_set_op(ctx, call, 4, arg2);
2469 ir_set_op(ctx, call, 5, arg3);
2470 ir_set_op(ctx, call, 6, arg4);
2471 ctx->control = call;
2472 _ir_UNREACHABLE(ctx);
2473 }
2474
2475 void _ir_TAILCALL_5(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3, ir_ref arg4, ir_ref arg5)
2476 {
2477 ir_ref call;
2478
2479 IR_ASSERT(ctx->control);
2480 if (ctx->ret_type == (ir_type)-1) {
2481 ctx->ret_type = type;
2482 }
2483 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2484 call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), 7);
2485 ir_set_op(ctx, call, 1, ctx->control);
2486 ir_set_op(ctx, call, 2, func);
2487 ir_set_op(ctx, call, 3, arg1);
2488 ir_set_op(ctx, call, 4, arg2);
2489 ir_set_op(ctx, call, 5, arg3);
2490 ir_set_op(ctx, call, 6, arg4);
2491 ir_set_op(ctx, call, 7, arg5);
2492 ctx->control = call;
2493 _ir_UNREACHABLE(ctx);
2494 }
2495
2496 void _ir_TAILCALL_N(ir_ctx *ctx, ir_type type, ir_ref func, uint32_t count, ir_ref *args)
2497 {
2498 ir_ref call;
2499 uint32_t i;
2500
2501 IR_ASSERT(ctx->control);
2502 if (ctx->ret_type == (ir_type)-1) {
2503 ctx->ret_type = type;
2504 }
2505 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2506 call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), count + 2);
2507 ir_set_op(ctx, call, 1, ctx->control);
2508 ir_set_op(ctx, call, 2, func);
2509 for (i = 0; i < count; i++) {
2510 ir_set_op(ctx, call, i + 3, args[i]);
2511 }
2512 ctx->control = call;
2513 _ir_UNREACHABLE(ctx);
2514 }
2515
2516 ir_ref _ir_SWITCH(ir_ctx *ctx, ir_ref val)
2517 {
2518 ir_ref ref;
2519
2520 IR_ASSERT(ctx->control);
2521 ref = ir_emit2(ctx, IR_SWITCH, ctx->control, val);
2522 ctx->control = IR_UNUSED;
2523 return ref;
2524 }
2525
2526 void _ir_CASE_VAL(ir_ctx *ctx, ir_ref switch_ref, ir_ref val)
2527 {
2528 IR_ASSERT(!ctx->control);
2529 ctx->control = ir_emit2(ctx, IR_CASE_VAL, switch_ref, val);
2530 }
2531
2532 void _ir_CASE_DEFAULT(ir_ctx *ctx, ir_ref switch_ref)
2533 {
2534 IR_ASSERT(!ctx->control);
2535 ctx->control = ir_emit1(ctx, IR_CASE_DEFAULT, switch_ref);
2536 }
2537
2538 void _ir_RETURN(ir_ctx *ctx, ir_ref val)
2539 {
2540 ir_type type = (val != IR_UNUSED) ? ctx->ir_base[val].type : IR_VOID;
2541
2542 IR_ASSERT(ctx->control);
2543 if (ctx->ret_type == (ir_type)-1) {
2544 ctx->ret_type = type;
2545 }
2546 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2547 ctx->control = ir_emit3(ctx, IR_RETURN, ctx->control, val, ctx->ir_base[1].op1);
2548 ctx->ir_base[1].op1 = ctx->control;
2549 ctx->control = IR_UNUSED;
2550 }
2551
2552 void _ir_IJMP(ir_ctx *ctx, ir_ref addr)
2553 {
2554 IR_ASSERT(ctx->control);
2555 ctx->control = ir_emit3(ctx, IR_IJMP, ctx->control, addr, ctx->ir_base[1].op1);
2556 ctx->ir_base[1].op1 = ctx->control;
2557 ctx->control = IR_UNUSED;
2558 }
2559
2560 ir_ref _ir_ADD_OFFSET(ir_ctx *ctx, ir_ref addr, uintptr_t offset)
2561 {
2562 if (offset) {
2563 addr = ir_fold2(ctx, IR_OPT(IR_ADD, IR_ADDR), addr, ir_const_addr(ctx, offset));
2564 }
2565 return addr;
2566 }
2567
2568 void _ir_GUARD(ir_ctx *ctx, ir_ref condition, ir_ref addr)
2569 {
2570 IR_ASSERT(ctx->control);
2571 if (IR_IS_CONST_REF(condition)) {
2572 if (ir_ref_is_true(ctx, condition)) {
2573 return;
2574 }
2575 condition = IR_FALSE;
2576 } else {
2577 ir_insn *prev = NULL;
2578 ir_ref ref = ctx->control;
2579 ir_insn *insn;
2580
2581 while (ref > condition) {
2582 insn = &ctx->ir_base[ref];
2583 if (insn->op == IR_GUARD) {
2584 if (insn->op2 == condition) {
2585 return;
2586 }
2587 } else if (insn->op == IR_GUARD_NOT) {
2588 if (insn->op2 == condition) {
2589 condition = IR_FALSE;
2590 break;
2591 }
2592 } else if (insn->op == IR_IF) {
2593 if (insn->op2 == condition) {
2594 if (prev->op == IR_IF_TRUE) {
2595 return;
2596 } else if (prev->op == IR_IF_FALSE) {
2597 condition = IR_FALSE;
2598 break;
2599 }
2600 }
2601 } else if (insn->op == IR_START || insn->op == IR_MERGE || insn->op == IR_LOOP_BEGIN) {
2602 break;
2603 }
2604 prev = insn;
2605 ref = insn->op1;
2606 }
2607 }
2608 if (ctx->snapshot_create) {
2609 ctx->snapshot_create(ctx, addr);
2610 }
2611 ctx->control = ir_emit3(ctx, IR_GUARD, ctx->control, condition, addr);
2612 }
2613
2614 void _ir_GUARD_NOT(ir_ctx *ctx, ir_ref condition, ir_ref addr)
2615 {
2616 IR_ASSERT(ctx->control);
2617 if (IR_IS_CONST_REF(condition)) {
2618 if (!ir_ref_is_true(ctx, condition)) {
2619 return;
2620 }
2621 condition = IR_TRUE;
2622 } else {
2623 ir_insn *prev = NULL;
2624 ir_ref ref = ctx->control;
2625 ir_insn *insn;
2626
2627 while (ref > condition) {
2628 insn = &ctx->ir_base[ref];
2629 if (insn->op == IR_GUARD_NOT) {
2630 if (insn->op2 == condition) {
2631 return;
2632 }
2633 } else if (insn->op == IR_GUARD) {
2634 if (insn->op2 == condition) {
2635 condition = IR_TRUE;
2636 break;
2637 }
2638 } else if (insn->op == IR_IF) {
2639 if (insn->op2 == condition) {
2640 if (prev->op == IR_IF_TRUE) {
2641 condition = IR_TRUE;
2642 break;
2643 } else if (prev->op == IR_IF_FALSE) {
2644 return;
2645 }
2646 }
2647 } else if (insn->op == IR_START || insn->op == IR_MERGE || insn->op == IR_LOOP_BEGIN) {
2648 break;
2649 }
2650 prev = insn;
2651 ref = insn->op1;
2652 }
2653 }
2654 if (ctx->snapshot_create) {
2655 ctx->snapshot_create(ctx, addr);
2656 }
2657 ctx->control = ir_emit3(ctx, IR_GUARD_NOT, ctx->control, condition, addr);
2658 }
2659
2660 ir_ref _ir_SNAPSHOT(ir_ctx *ctx, ir_ref n)
2661 {
2662 ir_ref snapshot;
2663
2664 IR_ASSERT(ctx->control);
2665 snapshot = ir_emit_N(ctx, IR_SNAPSHOT, 1 + n); /* op1 is used for control */
2666 ctx->ir_base[snapshot].op1 = ctx->control;
2667 ctx->control = snapshot;
2668 return snapshot;
2669 }
2670
2671 void _ir_SNAPSHOT_SET_OP(ir_ctx *ctx, ir_ref snapshot, ir_ref pos, ir_ref val)
2672 {
2673 ir_insn *insn = &ctx->ir_base[snapshot];
2674 ir_ref *ops = insn->ops;
2675
2676 IR_ASSERT(val < snapshot);
2677 IR_ASSERT(insn->op == IR_SNAPSHOT);
2678 pos++; /* op1 is used for control */
2679 IR_ASSERT(pos > 1 && pos <= insn->inputs_count);
2680 ops[pos] = val;
2681 }
2682
2683 ir_ref _ir_EXITCALL(ir_ctx *ctx, ir_ref func)
2684 {
2685 IR_ASSERT(ctx->control);
2686 return ctx->control = ir_emit2(ctx, IR_OPT(IR_EXITCALL, IR_I32), ctx->control, func);
2687 }
2688
2689 ir_ref _ir_ALLOCA(ir_ctx *ctx, ir_ref size)
2690 {
2691 IR_ASSERT(ctx->control);
2692 return ctx->control = ir_emit2(ctx, IR_OPT(IR_ALLOCA, IR_ADDR), ctx->control, size);
2693 }
2694
2695 void _ir_AFREE(ir_ctx *ctx, ir_ref size)
2696 {
2697 IR_ASSERT(ctx->control);
2698 ctx->control = ir_emit2(ctx, IR_AFREE, ctx->control, size);
2699 }
2700
2701 ir_ref _ir_VLOAD(ir_ctx *ctx, ir_type type, ir_ref var)
2702 {
2703 ir_ref ref = ctx->control;
2704 ir_insn *insn;
2705
2706 while (ref > var) {
2707 insn = &ctx->ir_base[ref];
2708 if (insn->op == IR_VLOAD) {
2709 if (insn->op2 == var) {
2710 if (insn->type == type) {
2711 return ref; /* load forwarding (L2L) */
2712 } else if (ir_type_size[insn->type] == ir_type_size[type]) {
2713 return ir_fold1(ctx, IR_OPT(IR_BITCAST, type), ref); /* load forwarding with bitcast (L2L) */
2714 } else if (ir_type_size[insn->type] > ir_type_size[type]
2715 && IR_IS_TYPE_INT(type) && IR_IS_TYPE_INT(insn->type)) {
2716 return ir_fold1(ctx, IR_OPT(IR_TRUNC, type), ref); /* partial load forwarding (L2L) */
2717 }
2718 }
2719 } else if (insn->op == IR_VSTORE) {
2720 ir_type type2 = ctx->ir_base[insn->op3].type;
2721
2722 if (insn->op2 == var) {
2723 if (type2 == type) {
2724 return insn->op3; /* store forwarding (S2L) */
2725 } else if (ir_type_size[type2] == ir_type_size[type]) {
2726 return ir_fold1(ctx, IR_OPT(IR_BITCAST, type), insn->op3); /* store forwarding with bitcast (S2L) */
2727 } else if (ir_type_size[type2] > ir_type_size[type]
2728 && IR_IS_TYPE_INT(type) && IR_IS_TYPE_INT(type2)) {
2729 return ir_fold1(ctx, IR_OPT(IR_TRUNC, type), insn->op3); /* partial store forwarding (S2L) */
2730 } else {
2731 break;
2732 }
2733 }
2734 } else if (insn->op == IR_MERGE || insn->op == IR_LOOP_BEGIN || insn->op == IR_CALL || insn->op == IR_STORE) {
2735 break;
2736 }
2737 ref = insn->op1;
2738 }
2739
2740 IR_ASSERT(ctx->control);
2741 return ctx->control = ir_emit2(ctx, IR_OPT(IR_VLOAD, type), ctx->control, var);
2742 }
2743
2744 void _ir_VSTORE(ir_ctx *ctx, ir_ref var, ir_ref val)
2745 {
2746 ir_ref limit = var;
2747 ir_ref ref = ctx->control;
2748 ir_ref prev = IR_UNUSED;
2749 ir_insn *insn;
2750 bool guarded = 0;
2751
2752 if (!IR_IS_CONST_REF(val)) {
2753 insn = &ctx->ir_base[val];
2754 if (insn->op == IR_BITCAST
2755 && !IR_IS_CONST_REF(insn->op1)
2756 && ir_type_size[insn->type] == ir_type_size[ctx->ir_base[insn->op1].type]) {
2757 /* skip BITCAST */
2758 val = insn->op1;
2759 }
2760 }
2761
2762 IR_ASSERT(ctx->control);
2763 while (ref > limit) {
2764 insn = &ctx->ir_base[ref];
2765 if (insn->op == IR_VSTORE) {
2766 if (insn->op2 == var) {
2767 if (insn->op3 == val) {
2768 return;
2769 } else {
2770 if (!guarded) {
2771 if (prev) {
2772 ctx->ir_base[prev].op1 = insn->op1;
2773 } else {
2774 ctx->control = insn->op1;
2775 }
2776 MAKE_NOP(insn);
2777 }
2778 break;
2779 }
2780 }
2781 } else if (insn->op == IR_VLOAD) {
2782 if (insn->op2 == var) {
2783 break;
2784 }
2785 } else if (insn->op == IR_GUARD || insn->op == IR_GUARD_NOT) {
2786 guarded = 1;
2787 } else if (insn->op >= IR_START || insn->op == IR_CALL || insn->op == IR_LOAD || insn->op == IR_STORE) {
2788 break;
2789 }
2790 prev = ref;
2791 ref = insn->op1;
2792 }
2793 ctx->control = ir_emit3(ctx, IR_VSTORE, ctx->control, var, val);
2794 }
2795
2796 ir_ref _ir_TLS(ir_ctx *ctx, ir_ref index, ir_ref offset)
2797 {
2798 IR_ASSERT(ctx->control);
2799 return ctx->control = ir_emit3(ctx, IR_OPT(IR_TLS, IR_ADDR), ctx->control, index, offset);
2800 }
2801
2802 ir_ref _ir_RLOAD(ir_ctx *ctx, ir_type type, ir_ref reg)
2803 {
2804 IR_ASSERT(ctx->control);
2805 return ctx->control = ir_emit2(ctx, IR_OPT(IR_RLOAD, type), ctx->control, reg);
2806 }
2807
2808 void _ir_RSTORE(ir_ctx *ctx, ir_ref reg, ir_ref val)
2809 {
2810 IR_ASSERT(ctx->control);
2811 ctx->control = ir_emit3(ctx, IR_RSTORE, ctx->control, val, reg);
2812 }
2813
2814 ir_ref _ir_LOAD(ir_ctx *ctx, ir_type type, ir_ref addr)
2815 {
2816 ir_ref ref = ir_find_aliasing_load(ctx, ctx->control, type, addr);
2817
2818 IR_ASSERT(ctx->control);
2819 if (!ref) {
2820 ctx->control = ref = ir_emit2(ctx, IR_OPT(IR_LOAD, type), ctx->control, addr);
2821 }
2822 return ref;
2823 }
2824
2825 void _ir_STORE(ir_ctx *ctx, ir_ref addr, ir_ref val)
2826 {
2827 ir_ref limit = (addr > 0) ? addr : 1;
2828 ir_ref ref = ctx->control;
2829 ir_ref prev = IR_UNUSED;
2830 ir_insn *insn;
2831 ir_type type = ctx->ir_base[val].type;
2832 ir_type type2;
2833 bool guarded = 0;
2834
2835 if (!IR_IS_CONST_REF(val)) {
2836 insn = &ctx->ir_base[val];
2837 if (insn->op == IR_BITCAST
2838 && !IR_IS_CONST_REF(insn->op1)
2839 && ir_type_size[insn->type] == ir_type_size[ctx->ir_base[insn->op1].type]) {
2840 /* skip BITCAST */
2841 val = insn->op1;
2842 }
2843 }
2844
2845 IR_ASSERT(ctx->control);
2846 while (ref > limit) {
2847 insn = &ctx->ir_base[ref];
2848 if (insn->op == IR_STORE) {
2849 if (insn->op2 == addr) {
2850 if (ctx->ir_base[insn->op3].type == type) {
2851 if (insn->op3 == val) {
2852 return;
2853 } else {
2854 if (!guarded) {
2855 if (prev) {
2856 ctx->ir_base[prev].op1 = insn->op1;
2857 } else {
2858 ctx->control = insn->op1;
2859 }
2860 MAKE_NOP(insn);
2861 }
2862 break;
2863 }
2864 } else {
2865 break;
2866 }
2867 } else {
2868 type2 = ctx->ir_base[insn->op3].type;
2869 goto check_aliasing;
2870 }
2871 } else if (insn->op == IR_LOAD) {
2872 if (insn->op2 == addr) {
2873 break;
2874 }
2875 type2 = insn->type;
2876 check_aliasing:
2877 if (ir_check_partial_aliasing(ctx, addr, insn->op2, type, type2) != IR_NO_ALIAS) {
2878 break;
2879 }
2880 } else if (insn->op == IR_GUARD || insn->op == IR_GUARD_NOT) {
2881 guarded = 1;
2882 } else if (insn->op >= IR_START || insn->op == IR_CALL) {
2883 break;
2884 }
2885 prev = ref;
2886 ref = insn->op1;
2887 }
2888 ctx->control = ir_emit3(ctx, IR_STORE, ctx->control, addr, val);
2889 }
2890
2891 void _ir_VA_START(ir_ctx *ctx, ir_ref list)
2892 {
2893 IR_ASSERT(ctx->control);
2894 ctx->control = ir_emit2(ctx, IR_VA_START, ctx->control, list);
2895 }
2896
2897 void _ir_VA_END(ir_ctx *ctx, ir_ref list)
2898 {
2899 IR_ASSERT(ctx->control);
2900 ctx->control = ir_emit2(ctx, IR_VA_END, ctx->control, list);
2901 }
2902
2903 void _ir_VA_COPY(ir_ctx *ctx, ir_ref dst, ir_ref src)
2904 {
2905 IR_ASSERT(ctx->control);
2906 ctx->control = ir_emit3(ctx, IR_VA_COPY, ctx->control, dst, src);
2907 }
2908
2909 ir_ref _ir_VA_ARG(ir_ctx *ctx, ir_type type, ir_ref list)
2910 {
2911 IR_ASSERT(ctx->control);
2912 return ctx->control = ir_emit2(ctx, IR_OPT(IR_VA_ARG, type), ctx->control, list);
2913 }
2914
2915 ir_ref _ir_BLOCK_BEGIN(ir_ctx *ctx)
2916 {
2917 IR_ASSERT(ctx->control);
2918 return ctx->control = ir_emit1(ctx, IR_OPT(IR_BLOCK_BEGIN, IR_ADDR), ctx->control);
2919 }
2920
