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 base1 = insn1->op2;
1803 off1 = insn1->op1;
1804 } else {
1805 base1 = insn1->op1;
1806 off1 = insn1->op2;
1807 }
1808 if (insn2->op != IR_ADD) {
1809 base2 = addr2;
1810 off2 = IR_UNUSED;
1811 } else if (ctx->ir_base[insn2->op2].op == IR_SYM) {
1812 base2 = insn2->op2;
1813 off2 = insn2->op1;
1814 } else {
1815 base2 = insn2->op1;
1816 off2 = insn2->op2;
1817 }
1818 if (base1 == base2) {
1819 uintptr_t offset1, offset2;
1820
1821 if (!off1) {
1822 offset1 = 0;
1823 } else if (IR_IS_CONST_REF(off1) && !IR_IS_SYM_CONST(ctx->ir_base[off1].op)) {
1824 offset1 = ctx->ir_base[off1].val.addr;
1825 } else {
1826 return IR_MAY_ALIAS;
1827 }
1828 if (!off2) {
1829 offset2 = 0;
1830 } else if (IR_IS_CONST_REF(off2) && !IR_IS_SYM_CONST(ctx->ir_base[off2].op)) {
1831 offset2 = ctx->ir_base[off2].val.addr;
1832 } else {
1833 return IR_MAY_ALIAS;
1834 }
1835 if (offset1 == offset2) {
1836 return IR_MUST_ALIAS;
1837 } else if (offset1 < offset2) {
1838 return offset1 + ir_type_size[type1] <= offset2 ? IR_NO_ALIAS : IR_MUST_ALIAS;
1839 } else {
1840 return offset2 + ir_type_size[type2] <= offset1 ? IR_NO_ALIAS : IR_MUST_ALIAS;
1841 }
1842 } else {
1843 insn1 = &ctx->ir_base[base1];
1844 insn2 = &ctx->ir_base[base2];
1845 if ((insn1->op == IR_ALLOCA && (insn2->op == IR_ALLOCA || insn2->op == IR_SYM || insn2->op == IR_PARAM))
1846 || (insn1->op == IR_SYM && (insn2->op == IR_ALLOCA || insn2->op == IR_SYM))
1847 || (insn1->op == IR_PARAM && insn2->op == IR_ALLOCA)) {
1848 return IR_NO_ALIAS;
1849 }
1850 }
1851 return IR_MAY_ALIAS;
1852 }
1853
1854 static ir_ref ir_find_aliasing_load(ir_ctx *ctx, ir_ref ref, ir_type type, ir_ref addr)
1855 {
1856 ir_ref limit = (addr > 0) ? addr : 1;
1857 ir_insn *insn;
1858 uint32_t modified_regset = 0;
1859
1860 while (ref > limit) {
1861 insn = &ctx->ir_base[ref];
1862 if (insn->op == IR_LOAD) {
1863 if (insn->op2 == addr) {
1864 if (insn->type == type) {
1865 return ref; /* load forwarding (L2L) */
1866 } else if (ir_type_size[insn->type] == ir_type_size[type]) {
1867 return ir_fold1(ctx, IR_OPT(IR_BITCAST, type), ref); /* load forwarding with bitcast (L2L) */
1868 } else if (ir_type_size[insn->type] > ir_type_size[type]
1869 && IR_IS_TYPE_INT(type) && IR_IS_TYPE_INT(insn->type)) {
1870 return ir_fold1(ctx, IR_OPT(IR_TRUNC, type), ref); /* partial load forwarding (L2L) */
1871 }
1872 }
1873 } else if (insn->op == IR_STORE) {
1874 ir_type type2 = ctx->ir_base[insn->op3].type;
1875
1876 if (insn->op2 == addr) {
1877 if (ctx->ir_base[insn->op3].op == IR_RLOAD
1878 && (modified_regset & (1 << ctx->ir_base[insn->op3].op2))) {
1879 /* anti-dependency */
1880 return IR_UNUSED;
1881 } else if (type2 == type) {
1882 return insn->op3; /* store forwarding (S2L) */
1883 } else if (ir_type_size[type2] == ir_type_size[type]) {
1884 return ir_fold1(ctx, IR_OPT(IR_BITCAST, type), insn->op3); /* store forwarding with bitcast (S2L) */
1885 } else if (ir_type_size[type2] > ir_type_size[type]
1886 && IR_IS_TYPE_INT(type) && IR_IS_TYPE_INT(type2)) {
1887 return ir_fold1(ctx, IR_OPT(IR_TRUNC, type), insn->op3); /* partial store forwarding (S2L) */
1888 } else {
1889 return IR_UNUSED;
1890 }
1891 } else if (ir_check_partial_aliasing(ctx, addr, insn->op2, type, type2) != IR_NO_ALIAS) {
1892 return IR_UNUSED;
1893 }
1894 } else if (insn->op == IR_RSTORE) {
1895 modified_regset |= (1 << insn->op3);
1896 } else if (insn->op == IR_MERGE || insn->op == IR_LOOP_BEGIN || insn->op == IR_CALL || insn->op == IR_VSTORE) {
1897 return IR_UNUSED;
1898 }
1899 ref = insn->op1;
1900 }
1901 return IR_UNUSED;
1902 }
1903
1904 /* IR Construction API */
1905
1906 ir_ref _ir_PARAM(ir_ctx *ctx, ir_type type, const char* name, ir_ref num)
1907 {
1908 IR_ASSERT(ctx->control);
1909 IR_ASSERT(ctx->ir_base[ctx->control].op == IR_START);
1910 IR_ASSERT(ctx->insns_count == num + 1);
1911 return ir_param(ctx, type, ctx->control, name, num);
1912 }
1913
1914 ir_ref _ir_VAR(ir_ctx *ctx, ir_type type, const char* name)
1915 {
1916 // IR_ASSERT(ctx->control);
1917 // IR_ASSERT(IR_IS_BB_START(ctx->ir_base[ctx->control].op));
1918 // TODO: VAR may be insterted after some "memory" instruction
1919 ir_ref ref = ctx->control;
1920
1921 while (1) {
1922 IR_ASSERT(ctx->control);
1923 if (IR_IS_BB_START(ctx->ir_base[ref].op)) {
1924 break;
1925 }
1926 ref = ctx->ir_base[ref].op1;
1927 }
1928 return ir_var(ctx, type, ref, name);
1929 }
1930
1931 ir_ref _ir_PHI_2(ir_ctx *ctx, ir_type type, ir_ref src1, ir_ref src2)
1932 {
1933 IR_ASSERT(ctx->control);
1934 IR_ASSERT(ctx->ir_base[ctx->control].op == IR_MERGE || ctx->ir_base[ctx->control].op == IR_LOOP_BEGIN);
1935 if (src1 == src2 && src1 != IR_UNUSED) {
1936 return src1;
1937 }
1938 return ir_emit3(ctx, IR_OPTX(IR_PHI, type, 3), ctx->control, src1, src2);
1939 }
1940
1941 ir_ref _ir_PHI_N(ir_ctx *ctx, ir_type type, ir_ref n, ir_ref *inputs)
1942 {
1943 IR_ASSERT(ctx->control);
1944 IR_ASSERT(n > 0);
1945 if (n == 1) {
1946 return inputs[0];
1947 } else {
1948 ir_ref i;
1949 ir_ref ref = inputs[0];
1950
1951 IR_ASSERT(ctx->ir_base[ctx->control].op == IR_MERGE || ctx->ir_base[ctx->control].op == IR_LOOP_BEGIN);
1952 if (ref != IR_UNUSED) {
1953 for (i = 1; i < n; i++) {
1954 if (inputs[i] != ref) {
1955 break;
1956 }
1957 }
1958 if (i == n) {
1959 /* all the same */
1960 return ref;
1961 }
1962 }
1963
1964 ref = ir_emit_N(ctx, IR_OPT(IR_PHI, type), n + 1);
1965 ir_set_op(ctx, ref, 1, ctx->control);
1966 for (i = 0; i < n; i++) {
1967 ir_set_op(ctx, ref, i + 2, inputs[i]);
1968 }
1969 return ref;
1970 }
1971 }
1972
1973 void _ir_PHI_SET_OP(ir_ctx *ctx, ir_ref phi, ir_ref pos, ir_ref src)
1974 {
1975 ir_insn *insn = &ctx->ir_base[phi];
1976 ir_ref *ops = insn->ops;
1977
1978 IR_ASSERT(insn->op == IR_PHI);
1979 IR_ASSERT(ctx->ir_base[insn->op1].op == IR_MERGE || ctx->ir_base[insn->op1].op == IR_LOOP_BEGIN);
1980 IR_ASSERT(pos > 0 && pos < insn->inputs_count);
1981 pos++; /* op1 is used for control */
1982 ops[pos] = src;
1983 }
1984
1985 void _ir_START(ir_ctx *ctx)
1986 {
1987 IR_ASSERT(!ctx->control);
1988 IR_ASSERT(ctx->insns_count == 1);
1989 ctx->control = ir_emit0(ctx, IR_START);
1990 }
1991
1992 void _ir_ENTRY(ir_ctx *ctx, ir_ref src, ir_ref num)
1993 {
1994 IR_ASSERT(!ctx->control);
1995 /* fake control edge */
1996 IR_ASSERT((ir_op_flags[ctx->ir_base[src].op] & IR_OP_FLAG_TERMINATOR)
1997 || ctx->ir_base[src].op == IR_END
1998 || ctx->ir_base[src].op == IR_LOOP_END); /* return from a recursive call */
1999 ctx->control = ir_emit2(ctx, IR_ENTRY, src, num);
2000 }
2001
2002 void _ir_BEGIN(ir_ctx *ctx, ir_ref src)
2003 {
2004 IR_ASSERT(!ctx->control);
2005 if (src
2006 && src + 1 == ctx->insns_count
2007 && ctx->ir_base[src].op == IR_END) {
2008 /* merge with the last END */
2009 ctx->control = ctx->ir_base[src].op1;
2010 ctx->insns_count--;
2011 } else {
2012 ctx->control = ir_emit1(ctx, IR_BEGIN, src);
2013 }
2014 }
2015
2016 ir_ref _ir_fold_condition(ir_ctx *ctx, ir_ref ref)
2017 {
2018 ir_insn *insn = &ctx->ir_base[ref];
2019
2020 if (insn->op == IR_NE && IR_IS_CONST_REF(insn->op2)) {
2021 ir_insn *op2_insn = &ctx->ir_base[insn->op2];
2022
2023 if (IR_IS_TYPE_INT(op2_insn->type) && op2_insn->val.u64 == 0) {
2024 return insn->op1;
2025 }
2026 }
2027 return ref;
2028 }
2029
2030 ir_ref _ir_IF(ir_ctx *ctx, ir_ref condition)
2031 {
2032 ir_ref if_ref;
2033
2034 condition = _ir_fold_condition(ctx, condition);
2035 IR_ASSERT(ctx->control);
2036 if (IR_IS_CONST_REF(condition)) {
2037 condition = ir_ref_is_true(ctx, condition) ? IR_TRUE : IR_FALSE;
2038 } else {
2039 ir_insn *prev = NULL;
2040 ir_ref ref = ctx->control;
2041 ir_insn *insn;
2042
2043 while (ref > condition) {
2044 insn = &ctx->ir_base[ref];
2045 if (insn->op == IR_GUARD_NOT) {
2046 if (insn->op2 == condition) {
2047 condition = IR_FALSE;
2048 break;
2049 }
2050 } else if (insn->op == IR_GUARD) {
2051 if (insn->op2 == condition) {
2052 condition = IR_TRUE;
2053 break;
2054 }
2055 } else if (insn->op == IR_IF) {
2056 if (insn->op2 == condition) {
2057 if (prev->op == IR_IF_TRUE) {
2058 condition = IR_TRUE;
2059 break;
2060 } else if (prev->op == IR_IF_FALSE) {
2061 condition = IR_FALSE;
2062 break;
2063 }
2064 }
2065 } else if (insn->op == IR_START || insn->op == IR_MERGE || insn->op == IR_LOOP_BEGIN) {
2066 break;
2067 }
2068 prev = insn;
2069 ref = insn->op1;
2070 }
2071 }
2072 if_ref = ir_emit2(ctx, IR_IF, ctx->control, condition);
2073 ctx->control = IR_UNUSED;
2074 return if_ref;
2075 }
2076
2077 void _ir_IF_TRUE(ir_ctx *ctx, ir_ref if_ref)
2078 {
2079 IR_ASSERT(!ctx->control);
2080 IR_ASSERT(if_ref);
2081 IR_ASSERT(ctx->ir_base[if_ref].op == IR_IF);
2082 ctx->control = ir_emit1(ctx, IR_IF_TRUE, if_ref);
2083 }
2084
2085 void _ir_IF_TRUE_cold(ir_ctx *ctx, ir_ref if_ref)
2086 {
2087 IR_ASSERT(!ctx->control);
2088 IR_ASSERT(if_ref);
2089 IR_ASSERT(ctx->ir_base[if_ref].op == IR_IF);
2090 /* op2 is used as an indicator of low-probability branch */
2091 ctx->control = ir_emit2(ctx, IR_IF_TRUE, if_ref, 1);
2092 }
2093
2094 void _ir_IF_FALSE(ir_ctx *ctx, ir_ref if_ref)
2095 {
2096 IR_ASSERT(!ctx->control);
2097 IR_ASSERT(if_ref);
2098 IR_ASSERT(ctx->ir_base[if_ref].op == IR_IF);
2099 ctx->control = ir_emit1(ctx, IR_IF_FALSE, if_ref);
2100 }
2101
2102 void _ir_IF_FALSE_cold(ir_ctx *ctx, ir_ref if_ref)
2103 {
2104 IR_ASSERT(!ctx->control);
2105 IR_ASSERT(if_ref);
2106 IR_ASSERT(ctx->ir_base[if_ref].op == IR_IF);
2107 /* op2 is used as an indicator of low-probability branch */
2108 ctx->control = ir_emit2(ctx, IR_IF_FALSE, if_ref, 1);
2109 }
2110
2111 ir_ref _ir_END(ir_ctx *ctx)
2112 {
2113 ir_ref ref;
2114
2115 IR_ASSERT(ctx->control);
2116 ref = ir_emit1(ctx, IR_END, ctx->control);
2117 ctx->control = IR_UNUSED;
2118 return ref;
2119 }
2120
2121 void _ir_MERGE_2(ir_ctx *ctx, ir_ref src1, ir_ref src2)
2122 {
2123 IR_ASSERT(!ctx->control);
2124 ctx->control = ir_emit2(ctx, IR_OPTX(IR_MERGE, IR_VOID, 2), src1, src2);
2125 }
2126
2127 void _ir_MERGE_N(ir_ctx *ctx, ir_ref n, ir_ref *inputs)
2128 {
2129 IR_ASSERT(!ctx->control);
2130 IR_ASSERT(n > 0);
2131 if (n == 1) {
2132 _ir_BEGIN(ctx, inputs[0]);
2133 } else {
2134 ir_ref *ops;
2135
2136 ctx->control = ir_emit_N(ctx, IR_MERGE, n);
2137 ops = ctx->ir_base[ctx->control].ops;
2138 while (n) {
2139 n--;
2140 ops[n + 1] = inputs[n];
2141 }
2142 }
2143 }
2144
2145 void _ir_MERGE_SET_OP(ir_ctx *ctx, ir_ref merge, ir_ref pos, ir_ref src)
2146 {
2147 ir_insn *insn = &ctx->ir_base[merge];
2148 ir_ref *ops = insn->ops;
2149
2150 IR_ASSERT(insn->op == IR_MERGE || insn->op == IR_LOOP_BEGIN);
2151 IR_ASSERT(pos > 0 && pos <= insn->inputs_count);
2152 ops[pos] = src;
2153 }
2154
2155 ir_ref _ir_END_LIST(ir_ctx *ctx, ir_ref list)
2156 {
2157 ir_ref ref;
2158
2159 IR_ASSERT(ctx->control);
2160 IR_ASSERT(!list || ctx->ir_base[list].op == IR_END);
2161 /* create a liked list of END nodes with the same destination through END.op2 */
2162 ref = ir_emit2(ctx, IR_END, ctx->control, list);
2163 ctx->control = IR_UNUSED;
2164 return ref;
2165 }
2166
2167 ir_ref _ir_END_PHI_LIST(ir_ctx *ctx, ir_ref list, ir_ref val)
2168 {
2169 ir_ref ref;
2170
2171 IR_ASSERT(ctx->control);
2172 IR_ASSERT(!list || ctx->ir_base[list].op == IR_END);
2173 /* create a liked list of END nodes with the same destination through END.op2 */
2174 ref = ir_emit3(ctx, IR_END, ctx->control, list, val);
2175 ctx->control = IR_UNUSED;
2176 return ref;
2177 }
2178
2179 void _ir_MERGE_LIST(ir_ctx *ctx, ir_ref list)
2180 {
2181 ir_ref ref = list;
2182
2183 if (list != IR_UNUSED) {
2184 uint32_t n = 0;
2185
2186 IR_ASSERT(!ctx->control);
2187
2188 /* count inputs count */
2189 do {
2190 ir_insn *insn = &ctx->ir_base[ref];
2191
2192 IR_ASSERT(insn->op == IR_END);
2193 ref = insn->op2;
2194 n++;
2195 } while (ref != IR_UNUSED);
2196
2197
2198 /* create MERGE node */
2199 IR_ASSERT(n > 0);
2200 if (n == 1) {
2201 ctx->ir_base[list].op2 = IR_UNUSED;
2202 _ir_BEGIN(ctx, list);
2203 } else {
2204 ctx->control = ir_emit_N(ctx, IR_MERGE, n);
2205 ref = list;
2206 while (n) {
2207 ir_insn *insn = &ctx->ir_base[ref];
2208
2209 ir_set_op(ctx, ctx->control, n, ref);
2210 ref = insn->op2;
2211 insn->op2 = IR_UNUSED;
2212 n--;
2213 }
2214 }
2215 }
2216 }
2217
2218 ir_ref _ir_PHI_LIST(ir_ctx *ctx, ir_ref list)
2219 {
2220 ir_insn *merge, *end;
2221 ir_ref phi, *ops, i;
2222 ir_type type;
2223
2224 if (list == IR_UNUSED) {
2225 return IR_UNUSED;
2226 }
2227 end = &ctx->ir_base[list];
2228 if (!end->op2) {
2229 phi = end->op3;
2230 end->op3 = IR_UNUSED;
2231 _ir_BEGIN(ctx, list);
2232 } else if (!end->op3) {
2233 _ir_MERGE_LIST(ctx, list);
2234 phi = IR_UNUSED;
2235 } else {
2236 type = ctx->ir_base[end->op3].type;
2237 _ir_MERGE_LIST(ctx, list);
2238 merge = &ctx->ir_base[ctx->control];
2239 IR_ASSERT(merge->op == IR_MERGE);
2240 phi = ir_emit_N(ctx, IR_OPT(IR_PHI, type), merge->inputs_count + 1);
2241 merge = &ctx->ir_base[ctx->control];
2242 ops = merge->ops;
2243 ir_set_op(ctx, phi, 1, ctx->control);
2244 for (i = 0; i < merge->inputs_count; i++) {
2245 end = &ctx->ir_base[ops[i + 1]];
2246 ir_set_op(ctx, phi, i + 2, end->op3);
2247 end->op3 = IR_END;
2248 }
2249 }
2250 return phi;
2251 }
2252
2253 ir_ref _ir_LOOP_BEGIN(ir_ctx *ctx, ir_ref src1)
2254 {
2255 IR_ASSERT(!ctx->control);
2256 ctx->control = ir_emit2(ctx, IR_OPTX(IR_LOOP_BEGIN, IR_VOID, 2), src1, IR_UNUSED);
2257 return ctx->control;
2258 }
2259
2260 ir_ref _ir_LOOP_END(ir_ctx *ctx)
2261 {
2262 ir_ref ref;
2263
2264 IR_ASSERT(ctx->control);
2265 ref = ir_emit1(ctx, IR_LOOP_END, ctx->control);
2266 ctx->control = IR_UNUSED;
2267 return ref;
2268 }
2269
2270 ir_ref _ir_CALL(ir_ctx *ctx, ir_type type, ir_ref func)
2271 {
2272 IR_ASSERT(ctx->control);
2273 return ctx->control = ir_emit2(ctx, IR_OPTX(IR_CALL, type, 2), ctx->control, func);
2274 }
2275
2276 ir_ref _ir_CALL_1(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1)
2277 {
2278 IR_ASSERT(ctx->control);
2279 return ctx->control = ir_emit3(ctx, IR_OPTX(IR_CALL, type, 3), ctx->control, func, arg1);
2280 }
2281
2282 ir_ref _ir_CALL_2(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2)
2283 {
2284 ir_ref call;
2285
2286 IR_ASSERT(ctx->control);
2287 call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), 4);
2288 ir_set_op(ctx, call, 1, ctx->control);
2289 ir_set_op(ctx, call, 2, func);
2290 ir_set_op(ctx, call, 3, arg1);
2291 ir_set_op(ctx, call, 4, arg2);
2292 ctx->control = call;
2293 return call;
2294 }
2295
2296 ir_ref _ir_CALL_3(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3)
2297 {
2298 ir_ref call;
2299
2300 IR_ASSERT(ctx->control);
2301 call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), 5);
2302 ir_set_op(ctx, call, 1, ctx->control);
2303 ir_set_op(ctx, call, 2, func);
2304 ir_set_op(ctx, call, 3, arg1);
2305 ir_set_op(ctx, call, 4, arg2);
2306 ir_set_op(ctx, call, 5, arg3);
2307 ctx->control = call;
2308 return call;
2309 }
2310
2311 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)
2312 {
2313 ir_ref call;
2314
2315 IR_ASSERT(ctx->control);
2316 call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), 6);
2317 ir_set_op(ctx, call, 1, ctx->control);
2318 ir_set_op(ctx, call, 2, func);
2319 ir_set_op(ctx, call, 3, arg1);
2320 ir_set_op(ctx, call, 4, arg2);
2321 ir_set_op(ctx, call, 5, arg3);
2322 ir_set_op(ctx, call, 6, arg4);
2323 ctx->control = call;
2324 return call;
2325 }
2326
2327 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)
2328 {
2329 ir_ref call;
2330
2331 IR_ASSERT(ctx->control);
2332 call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), 7);
2333 ir_set_op(ctx, call, 1, ctx->control);
2334 ir_set_op(ctx, call, 2, func);
2335 ir_set_op(ctx, call, 3, arg1);
2336 ir_set_op(ctx, call, 4, arg2);
2337 ir_set_op(ctx, call, 5, arg3);
2338 ir_set_op(ctx, call, 6, arg4);
2339 ir_set_op(ctx, call, 7, arg5);
2340 ctx->control = call;
2341 return call;
2342 }
2343
2344 ir_ref _ir_CALL_N(ir_ctx *ctx, ir_type type, ir_ref func, uint32_t count, ir_ref *args)
2345 {
2346 ir_ref call;
2347 uint32_t i;
2348
2349 IR_ASSERT(ctx->control);
2350 call = ir_emit_N(ctx, IR_OPT(IR_CALL, type), count + 2);
2351 ir_set_op(ctx, call, 1, ctx->control);
2352 ir_set_op(ctx, call, 2, func);
2353 for (i = 0; i < count; i++) {
2354 ir_set_op(ctx, call, i + 3, args[i]);
2355 }
2356 ctx->control = call;
2357 return call;
2358 }
2359
2360 void _ir_UNREACHABLE(ir_ctx *ctx)
2361 {
2362 IR_ASSERT(ctx->control);
2363 ctx->control = ir_emit3(ctx, IR_UNREACHABLE, ctx->control, IR_UNUSED, ctx->ir_base[1].op1);
2364 ctx->ir_base[1].op1 = ctx->control;
2365 ctx->control = IR_UNUSED;
2366 }
2367
2368 void _ir_TAILCALL(ir_ctx *ctx, ir_type type, ir_ref func)
2369 {
2370 IR_ASSERT(ctx->control);
2371 if (ctx->ret_type == (ir_type)-1) {
2372 ctx->ret_type = type;
2373 }
2374 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2375 ctx->control = ir_emit2(ctx, IR_OPTX(IR_TAILCALL, type, 2), ctx->control, func);
2376 _ir_UNREACHABLE(ctx);
2377 }
2378
2379 void _ir_TAILCALL_1(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1)
2380 {
2381 IR_ASSERT(ctx->control);
2382 if (ctx->ret_type == (ir_type)-1) {
2383 ctx->ret_type = type;
2384 }
2385 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2386 ctx->control = ir_emit3(ctx, IR_OPTX(IR_TAILCALL, type, 3), ctx->control, func, arg1);
2387 _ir_UNREACHABLE(ctx);
2388 }
2389
2390 void _ir_TAILCALL_2(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2)
2391 {
2392 ir_ref call;
2393
2394 IR_ASSERT(ctx->control);
2395 if (ctx->ret_type == (ir_type)-1) {
2396 ctx->ret_type = type;
2397 }
2398 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2399 call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), 4);
2400 ir_set_op(ctx, call, 1, ctx->control);
2401 ir_set_op(ctx, call, 2, func);
2402 ir_set_op(ctx, call, 3, arg1);
2403 ir_set_op(ctx, call, 4, arg2);
2404 ctx->control = call;
2405 _ir_UNREACHABLE(ctx);
2406 }
2407
2408 void _ir_TAILCALL_3(ir_ctx *ctx, ir_type type, ir_ref func, ir_ref arg1, ir_ref arg2, ir_ref arg3)
2409 {
2410 ir_ref call;
2411
2412 IR_ASSERT(ctx->control);
2413 if (ctx->ret_type == (ir_type)-1) {
2414 ctx->ret_type = type;
2415 }
2416 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2417 call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), 5);
2418 ir_set_op(ctx, call, 1, ctx->control);
2419 ir_set_op(ctx, call, 2, func);
2420 ir_set_op(ctx, call, 3, arg1);
2421 ir_set_op(ctx, call, 4, arg2);
2422 ir_set_op(ctx, call, 5, arg3);
2423 ctx->control = call;
2424 _ir_UNREACHABLE(ctx);
2425 }
2426
2427 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)
2428 {
2429 ir_ref call;
2430
2431 IR_ASSERT(ctx->control);
2432 if (ctx->ret_type == (ir_type)-1) {
2433 ctx->ret_type = type;
2434 }
2435 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2436 call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), 6);
2437 ir_set_op(ctx, call, 1, ctx->control);
2438 ir_set_op(ctx, call, 2, func);
2439 ir_set_op(ctx, call, 3, arg1);
2440 ir_set_op(ctx, call, 4, arg2);
2441 ir_set_op(ctx, call, 5, arg3);
2442 ir_set_op(ctx, call, 6, arg4);
2443 ctx->control = call;
2444 _ir_UNREACHABLE(ctx);
2445 }
2446
2447 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)
2448 {
2449 ir_ref call;
2450
2451 IR_ASSERT(ctx->control);
2452 if (ctx->ret_type == (ir_type)-1) {
2453 ctx->ret_type = type;
2454 }
2455 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2456 call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), 7);
2457 ir_set_op(ctx, call, 1, ctx->control);
2458 ir_set_op(ctx, call, 2, func);
2459 ir_set_op(ctx, call, 3, arg1);
2460 ir_set_op(ctx, call, 4, arg2);
2461 ir_set_op(ctx, call, 5, arg3);
2462 ir_set_op(ctx, call, 6, arg4);
2463 ir_set_op(ctx, call, 7, arg5);
2464 ctx->control = call;
2465 _ir_UNREACHABLE(ctx);
2466 }
2467
2468 void _ir_TAILCALL_N(ir_ctx *ctx, ir_type type, ir_ref func, uint32_t count, ir_ref *args)
2469 {
2470 ir_ref call;
2471 uint32_t i;
2472
2473 IR_ASSERT(ctx->control);
2474 if (ctx->ret_type == (ir_type)-1) {
2475 ctx->ret_type = type;
2476 }
2477 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2478 call = ir_emit_N(ctx, IR_OPT(IR_TAILCALL, type), count + 2);
2479 ir_set_op(ctx, call, 1, ctx->control);
2480 ir_set_op(ctx, call, 2, func);
2481 for (i = 0; i < count; i++) {
2482 ir_set_op(ctx, call, i + 3, args[i]);
2483 }
2484 ctx->control = call;
2485 _ir_UNREACHABLE(ctx);
2486 }
2487
2488 ir_ref _ir_SWITCH(ir_ctx *ctx, ir_ref val)
2489 {
2490 ir_ref ref;
2491
2492 IR_ASSERT(ctx->control);
2493 ref = ir_emit2(ctx, IR_SWITCH, ctx->control, val);
2494 ctx->control = IR_UNUSED;
2495 return ref;
2496 }
2497
2498 void _ir_CASE_VAL(ir_ctx *ctx, ir_ref switch_ref, ir_ref val)
2499 {
2500 IR_ASSERT(!ctx->control);
2501 ctx->control = ir_emit2(ctx, IR_CASE_VAL, switch_ref, val);
2502 }
2503
2504 void _ir_CASE_DEFAULT(ir_ctx *ctx, ir_ref switch_ref)
2505 {
2506 IR_ASSERT(!ctx->control);
2507 ctx->control = ir_emit1(ctx, IR_CASE_DEFAULT, switch_ref);
2508 }
2509
2510 void _ir_RETURN(ir_ctx *ctx, ir_ref val)
2511 {
2512 ir_type type = (val != IR_UNUSED) ? ctx->ir_base[val].type : IR_VOID;
2513
2514 IR_ASSERT(ctx->control);
2515 if (ctx->ret_type == (ir_type)-1) {
2516 ctx->ret_type = type;
2517 }
2518 IR_ASSERT(ctx->ret_type == type && "conflicting return type");
2519 ctx->control = ir_emit3(ctx, IR_RETURN, ctx->control, val, ctx->ir_base[1].op1);
2520 ctx->ir_base[1].op1 = ctx->control;
2521 ctx->control = IR_UNUSED;
2522 }
2523
2524 void _ir_IJMP(ir_ctx *ctx, ir_ref addr)
2525 {
2526 IR_ASSERT(ctx->control);
2527 ctx->control = ir_emit3(ctx, IR_IJMP, ctx->control, addr, ctx->ir_base[1].op1);
2528 ctx->ir_base[1].op1 = ctx->control;
2529 ctx->control = IR_UNUSED;
2530 }
2531
2532 ir_ref _ir_ADD_OFFSET(ir_ctx *ctx, ir_ref addr, uintptr_t offset)
2533 {
2534 if (offset) {
2535 addr = ir_fold2(ctx, IR_OPT(IR_ADD, IR_ADDR), addr, ir_const_addr(ctx, offset));
2536 }
2537 return addr;
2538 }
2539
2540 void _ir_GUARD(ir_ctx *ctx, ir_ref condition, ir_ref addr)
2541 {
2542 IR_ASSERT(ctx->control);
2543 if (IR_IS_CONST_REF(condition)) {
2544 if (ir_ref_is_true(ctx, condition)) {
2545 return;
2546 }
2547 condition = IR_FALSE;
2548 } else {
2549 ir_insn *prev = NULL;
2550 ir_ref ref = ctx->control;
2551 ir_insn *insn;
2552
2553 while (ref > condition) {
2554 insn = &ctx->ir_base[ref];
2555 if (insn->op == IR_GUARD) {
2556 if (insn->op2 == condition) {
2557 return;
2558 }
2559 } else if (insn->op == IR_GUARD_NOT) {
2560 if (insn->op2 == condition) {
2561 condition = IR_FALSE;
2562 break;
2563 }
2564 } else if (insn->op == IR_IF) {
2565 if (insn->op2 == condition) {
2566 if (prev->op == IR_IF_TRUE) {
2567 return;
2568 } else if (prev->op == IR_IF_FALSE) {
2569 condition = IR_FALSE;
2570 break;
2571 }
2572 }
2573 } else if (insn->op == IR_START || insn->op == IR_MERGE || insn->op == IR_LOOP_BEGIN) {
2574 break;
2575 }
2576 prev = insn;
2577 ref = insn->op1;
2578 }
2579 }
2580 if (ctx->snapshot_create) {
2581 ctx->snapshot_create(ctx, addr);
2582 }
2583 ctx->control = ir_emit3(ctx, IR_GUARD, ctx->control, condition, addr);
2584 }
2585
2586 void _ir_GUARD_NOT(ir_ctx *ctx, ir_ref condition, ir_ref addr)
2587 {
2588 IR_ASSERT(ctx->control);
2589 if (IR_IS_CONST_REF(condition)) {
2590 if (!ir_ref_is_true(ctx, condition)) {
2591 return;
2592 }
2593 condition = IR_TRUE;
2594 } else {
2595 ir_insn *prev = NULL;
2596 ir_ref ref = ctx->control;
2597 ir_insn *insn;
2598
2599 while (ref > condition) {
2600 insn = &ctx->ir_base[ref];
2601 if (insn->op == IR_GUARD_NOT) {
2602 if (insn->op2 == condition) {
2603 return;
2604 }
2605 } else if (insn->op == IR_GUARD) {
2606 if (insn->op2 == condition) {
2607 condition = IR_TRUE;
2608 break;
2609 }
2610 } else if (insn->op == IR_IF) {
2611 if (insn->op2 == condition) {
2612 if (prev->op == IR_IF_TRUE) {
2613 condition = IR_TRUE;
2614 break;
2615 } else if (prev->op == IR_IF_FALSE) {
2616 return;
2617 }
2618 }
2619 } else if (insn->op == IR_START || insn->op == IR_MERGE || insn->op == IR_LOOP_BEGIN) {
2620 break;
2621 }
2622 prev = insn;
2623 ref = insn->op1;
2624 }
2625 }
2626 if (ctx->snapshot_create) {
2627 ctx->snapshot_create(ctx, addr);
2628 }
2629 ctx->control = ir_emit3(ctx, IR_GUARD_NOT, ctx->control, condition, addr);
2630 }
2631
2632 ir_ref _ir_SNAPSHOT(ir_ctx *ctx, ir_ref n)
2633 {
2634 ir_ref snapshot;
2635
2636 IR_ASSERT(ctx->control);
2637 snapshot = ir_emit_N(ctx, IR_SNAPSHOT, 1 + n); /* op1 is used for control */
2638 ctx->ir_base[snapshot].op1 = ctx->control;
2639 ctx->control = snapshot;
2640 return snapshot;
2641 }
2642
2643 void _ir_SNAPSHOT_SET_OP(ir_ctx *ctx, ir_ref snapshot, ir_ref pos, ir_ref val)
2644 {
2645 ir_insn *insn = &ctx->ir_base[snapshot];
2646 ir_ref *ops = insn->ops;
2647
2648 IR_ASSERT(val < snapshot);
2649 IR_ASSERT(insn->op == IR_SNAPSHOT);
2650 pos++; /* op1 is used for control */
2651 IR_ASSERT(pos > 1 && pos <= insn->inputs_count);
2652 ops[pos] = val;
2653 }
2654
2655 ir_ref _ir_EXITCALL(ir_ctx *ctx, ir_ref func)
2656 {
2657 IR_ASSERT(ctx->control);
2658 return ctx->control = ir_emit2(ctx, IR_OPT(IR_EXITCALL, IR_I32), ctx->control, func);
2659 }
2660
2661 ir_ref _ir_ALLOCA(ir_ctx *ctx, ir_ref size)
2662 {
2663 IR_ASSERT(ctx->control);
2664 return ctx->control = ir_emit2(ctx, IR_OPT(IR_ALLOCA, IR_ADDR), ctx->control, size);
2665 }
2666
2667 void _ir_AFREE(ir_ctx *ctx, ir_ref size)
2668 {
2669 IR_ASSERT(ctx->control);
2670 ctx->control = ir_emit2(ctx, IR_AFREE, ctx->control, size);
2671 }
2672
2673 ir_ref _ir_VLOAD(ir_ctx *ctx, ir_type type, ir_ref var)
2674 {
2675 ir_ref ref = ctx->control;
2676 ir_insn *insn;
2677
2678 while (ref > var) {
2679 insn = &ctx->ir_base[ref];
2680 if (insn->op == IR_VLOAD) {
2681 if (insn->op2 == var) {
2682 if (insn->type == type) {
2683 return ref; /* load forwarding (L2L) */
2684 } else if (ir_type_size[insn->type] == ir_type_size[type]) {
2685 return ir_fold1(ctx, IR_OPT(IR_BITCAST, type), ref); /* load forwarding with bitcast (L2L) */
2686 } else if (ir_type_size[insn->type] > ir_type_size[type]
2687 && IR_IS_TYPE_INT(type) && IR_IS_TYPE_INT(insn->type)) {
2688 return ir_fold1(ctx, IR_OPT(IR_TRUNC, type), ref); /* partial load forwarding (L2L) */
2689 }
2690 }
2691 } else if (insn->op == IR_VSTORE) {
2692 ir_type type2 = ctx->ir_base[insn->op3].type;
2693
2694 if (insn->op2 == var) {
2695 if (type2 == type) {
2696 return insn->op3; /* store forwarding (S2L) */
2697 } else if (ir_type_size[type2] == ir_type_size[type]) {
2698 return ir_fold1(ctx, IR_OPT(IR_BITCAST, type), insn->op3); /* store forwarding with bitcast (S2L) */
2699 } else if (ir_type_size[type2] > ir_type_size[type]
2700 && IR_IS_TYPE_INT(type) && IR_IS_TYPE_INT(type2)) {
2701 return ir_fold1(ctx, IR_OPT(IR_TRUNC, type), insn->op3); /* partial store forwarding (S2L) */
2702 } else {
2703 break;
2704 }
2705 }
2706 } else if (insn->op == IR_MERGE || insn->op == IR_LOOP_BEGIN || insn->op == IR_CALL || insn->op == IR_STORE) {
2707 break;
2708 }
2709 ref = insn->op1;
2710 }
2711
2712 IR_ASSERT(ctx->control);
2713 return ctx->control = ir_emit2(ctx, IR_OPT(IR_VLOAD, type), ctx->control, var);
2714 }
2715
2716 void _ir_VSTORE(ir_ctx *ctx, ir_ref var, ir_ref val)
2717 {
2718 IR_ASSERT(ctx->control);
2719 ctx->control = ir_emit3(ctx, IR_VSTORE, ctx->control, var, val);
2720 }
2721
2722 ir_ref _ir_TLS(ir_ctx *ctx, ir_ref index, ir_ref offset)
2723 {
2724 IR_ASSERT(ctx->control);
2725 return ctx->control = ir_emit3(ctx, IR_OPT(IR_TLS, IR_ADDR), ctx->control, index, offset);
2726 }
2727
2728 ir_ref _ir_RLOAD(ir_ctx *ctx, ir_type type, ir_ref reg)
2729 {
2730 IR_ASSERT(ctx->control);
2731 return ctx->control = ir_emit2(ctx, IR_OPT(IR_RLOAD, type), ctx->control, reg);
2732 }
2733
2734 void _ir_RSTORE(ir_ctx *ctx, ir_ref reg, ir_ref val)
2735 {
2736 IR_ASSERT(ctx->control);
2737 ctx->control = ir_emit3(ctx, IR_RSTORE, ctx->control, val, reg);
2738 }
2739
2740 ir_ref _ir_LOAD(ir_ctx *ctx, ir_type type, ir_ref addr)
2741 {
2742 ir_ref ref = ir_find_aliasing_load(ctx, ctx->control, type, addr);
2743
2744 IR_ASSERT(ctx->control);
2745 if (!ref) {
2746 ctx->control = ref = ir_emit2(ctx, IR_OPT(IR_LOAD, type), ctx->control, addr);
2747 }
2748 return ref;
2749 }
2750
2751 void _ir_STORE(ir_ctx *ctx, ir_ref addr, ir_ref val)
2752 {
2753 ir_ref limit = (addr > 0) ? addr : 1;
2754 ir_ref ref = ctx->control;
2755 ir_ref prev = IR_UNUSED;
2756 ir_insn *insn;
2757 ir_type type = ctx->ir_base[val].type;
2758 ir_type type2;
2759 bool guarded = 0;
2760
2761 if (!IR_IS_CONST_REF(val)) {
2762 insn = &ctx->ir_base[val];
2763 if (insn->op == IR_BITCAST
2764 && !IR_IS_CONST_REF(insn->op1)
2765 && ir_type_size[insn->type] == ir_type_size[ctx->ir_base[insn->op1].type]) {
2766 /* skip BITCAST */
2767 val = insn->op1;
2768 }
2769 }
2770
2771 IR_ASSERT(ctx->control);
2772 while (ref > limit) {
2773 insn = &ctx->ir_base[ref];
2774 if (insn->op == IR_STORE) {
2775 if (insn->op2 == addr) {
2776 if (ctx->ir_base[insn->op3].type == type) {
2777 if (insn->op3 == val) {
2778 return;
2779 } else {
2780 if (!guarded) {
2781 if (prev) {
2782 ctx->ir_base[prev].op1 = insn->op1;
2783 } else {
2784 ctx->control = insn->op1;
2785 }
2786 MAKE_NOP(insn);
2787 }
2788 break;
2789 }
2790 } else {
2791 break;
2792 }
2793 } else {
2794 type2 = ctx->ir_base[insn->op3].type;
2795 goto check_aliasing;
2796 }
2797 } else if (insn->op == IR_LOAD) {
2798 if (insn->op2 == addr) {
2799 break;
2800 }
2801 type2 = insn->type;
2802 check_aliasing:
2803 if (ir_check_partial_aliasing(ctx, addr, insn->op2, type, type2) != IR_NO_ALIAS) {
2804 break;
2805 }
2806 } else if (insn->op == IR_GUARD || insn->op == IR_GUARD_NOT) {
2807 guarded = 1;
2808 } else if (insn->op >= IR_START || insn->op == IR_CALL) {
2809 break;
2810 }
2811 prev = ref;
2812 ref = insn->op1;
2813 }
2814 ctx->control = ir_emit3(ctx, IR_STORE, ctx->control, addr, val);
2815 }
2816
2817 void _ir_VA_START(ir_ctx *ctx, ir_ref list)
2818 {
2819 IR_ASSERT(ctx->control);
2820 ctx->control = ir_emit2(ctx, IR_VA_START, ctx->control, list);
2821 }
2822
2823 void _ir_VA_END(ir_ctx *ctx, ir_ref list)
2824 {
2825 IR_ASSERT(ctx->control);
2826 ctx->control = ir_emit2(ctx, IR_VA_END, ctx->control, list);
2827 }
2828
2829 void _ir_VA_COPY(ir_ctx *ctx, ir_ref dst, ir_ref src)
2830 {
2831 IR_ASSERT(ctx->control);
2832 ctx->control = ir_emit3(ctx, IR_VA_COPY, ctx->control, dst, src);
2833 }
2834
2835 ir_ref _ir_VA_ARG(ir_ctx *ctx, ir_type type, ir_ref list)
2836 {
2837 IR_ASSERT(ctx->control);
2838 return ctx->control = ir_emit2(ctx, IR_OPT(IR_VA_ARG, type), ctx->control, list);
2839 }
2840
2841 ir_ref _ir_BLOCK_BEGIN(ir_ctx *ctx)
2842 {
2843 IR_ASSERT(ctx->control);
2844 return ctx->control = ir_emit1(ctx, IR_OPT(IR_BLOCK_BEGIN, IR_ADDR), ctx->control);
2845 }
2846
