2 * Linearize - walk the statement tree (but _not_ the expressions)
3 * to generate a linear version of it and the basic blocks.
4 *
5 * NOTE! We're not interested in the actual sub-expressions yet,
6 * even though they can generate conditional branches and
7 * subroutine calls. That's all "local" behaviour.
8 *
9 * Copyright (C) 2004 Linus Torvalds
10 * Copyright (C) 2004 Christopher Li
11 */
12
13 #include <string.h>
14 #include <stdarg.h>
15 #include <stdlib.h>
16 #include <stdio.h>
17 #include <assert.h>
18
19 #include "parse.h"
20 #include "expression.h"
21 #include "linearize.h"
22 #include "flow.h"
23 #include "target.h"
24
25 pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt);
26 pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr);
27
28 static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right);
29 static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val);
30 static pseudo_t linearize_one_symbol(struct entrypoint *ep, struct symbol *sym);
31
32 struct access_data;
33 static pseudo_t add_load(struct entrypoint *ep, struct access_data *);
34 static pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *);
35 static pseudo_t cast_pseudo(struct entrypoint *ep, pseudo_t src, struct symbol *from, struct symbol *to);
36
37 struct pseudo void_pseudo = {};
38
39 static struct position current_pos;
40
41 ALLOCATOR(pseudo_user, "pseudo_user");
42
43 static struct instruction *alloc_instruction(int opcode, int size)
44 {
45 struct instruction * insn = __alloc_instruction(0);
46 insn->opcode = opcode;
47 insn->size = size;
53 {
54 return type ? type->bit_size > 0 ? type->bit_size : 0 : 0;
55 }
56
57 static struct instruction *alloc_typed_instruction(int opcode, struct symbol *type)
58 {
59 struct instruction *insn = alloc_instruction(opcode, type_size(type));
60 insn->type = type;
61 return insn;
62 }
63
64 static struct entrypoint *alloc_entrypoint(void)
65 {
66 return __alloc_entrypoint(0);
67 }
68
69 static struct basic_block *alloc_basic_block(struct entrypoint *ep, struct position pos)
70 {
71 static int nr;
72 struct basic_block *bb = __alloc_basic_block(0);
73 bb->context = -1;
74 bb->pos = pos;
75 bb->ep = ep;
76 bb->nr = nr++;
77 return bb;
78 }
79
80 static struct multijmp *alloc_multijmp(struct basic_block *target, int begin, int end)
81 {
82 struct multijmp *multijmp = __alloc_multijmp(0);
83 multijmp->target = target;
84 multijmp->begin = begin;
85 multijmp->end = end;
86 return multijmp;
87 }
88
89 static inline int regno(pseudo_t n)
90 {
91 int retval = -1;
92 if (n && n->type == PSEUDO_REG)
93 retval = n->nr;
94 return retval;
95 }
96
97 const char *show_pseudo(pseudo_t pseudo)
98 {
99 static int n;
100 static char buffer[4][64];
101 char *buf;
102 int i;
103
104 if (!pseudo)
105 return "no pseudo";
106 if (pseudo == VOID)
107 return "VOID";
108 buf = buffer[3 & ++n];
109 switch(pseudo->type) {
110 case PSEUDO_SYM: {
111 struct symbol *sym = pseudo->sym;
112 struct expression *expr;
113
114 if (sym->bb_target) {
115 snprintf(buf, 64, ".L%u", sym->bb_target->nr);
116 break;
117 }
118 if (sym->ident) {
119 snprintf(buf, 64, "%s", show_ident(sym->ident));
120 break;
121 }
122 expr = sym->initializer;
123 snprintf(buf, 64, "<anon symbol:%p>", sym);
124 if (expr) {
125 switch (expr->type) {
126 case EXPR_VALUE:
127 snprintf(buf, 64, "<symbol value: %lld>", expr->value);
128 break;
129 case EXPR_STRING:
130 return show_string(expr->string);
131 default:
132 break;
133 }
134 }
135 break;
136 }
137 case PSEUDO_REG:
138 i = snprintf(buf, 64, "%%r%d", pseudo->nr);
139 if (pseudo->ident)
140 sprintf(buf+i, "(%s)", show_ident(pseudo->ident));
141 break;
142 case PSEUDO_VAL: {
143 long long value = pseudo->value;
144 if (value > 1000 || value < -1000)
145 snprintf(buf, 64, "$%#llx", value);
146 else
147 snprintf(buf, 64, "$%lld", value);
148 break;
149 }
150 case PSEUDO_ARG:
151 snprintf(buf, 64, "%%arg%d", pseudo->nr);
152 break;
153 case PSEUDO_PHI:
154 i = snprintf(buf, 64, "%%phi%d", pseudo->nr);
155 if (pseudo->ident)
156 sprintf(buf+i, "(%s)", show_ident(pseudo->ident));
157 break;
158 default:
159 snprintf(buf, 64, "<bad pseudo type %d>", pseudo->type);
160 }
161 return buf;
162 }
163
164 static const char *opcodes[] = {
165 [OP_BADOP] = "bad_op",
166
167 /* Fn entrypoint */
168 [OP_ENTRY] = "<entry-point>",
169
170 /* Terminator */
171 [OP_RET] = "ret",
172 [OP_BR] = "br",
173 [OP_CBR] = "cbr",
174 [OP_SWITCH] = "switch",
175 [OP_INVOKE] = "invoke",
176 [OP_COMPUTEDGOTO] = "jmp *",
177 [OP_UNWIND] = "unwind",
178
179 /* Binary */
180 [OP_ADD] = "add",
181 [OP_SUB] = "sub",
182 [OP_MULU] = "mulu",
183 [OP_MULS] = "muls",
184 [OP_DIVU] = "divu",
185 [OP_DIVS] = "divs",
186 [OP_MODU] = "modu",
187 [OP_MODS] = "mods",
188 [OP_SHL] = "shl",
189 [OP_LSR] = "lsr",
190 [OP_ASR] = "asr",
191
192 /* Logical */
193 [OP_AND] = "and",
194 [OP_OR] = "or",
195 [OP_XOR] = "xor",
196 [OP_AND_BOOL] = "and-bool",
197 [OP_OR_BOOL] = "or-bool",
198
199 /* Binary comparison */
200 [OP_SET_EQ] = "seteq",
201 [OP_SET_NE] = "setne",
202 [OP_SET_LE] = "setle",
203 [OP_SET_GE] = "setge",
204 [OP_SET_LT] = "setlt",
205 [OP_SET_GT] = "setgt",
206 [OP_SET_B] = "setb",
207 [OP_SET_A] = "seta",
208 [OP_SET_BE] = "setbe",
209 [OP_SET_AE] = "setae",
210
211 /* Uni */
212 [OP_NOT] = "not",
213 [OP_NEG] = "neg",
214
215 /* Special three-input */
216 [OP_SEL] = "select",
217
218 /* Memory */
219 [OP_MALLOC] = "malloc",
220 [OP_FREE] = "free",
221 [OP_ALLOCA] = "alloca",
222 [OP_LOAD] = "load",
223 [OP_STORE] = "store",
224 [OP_SETVAL] = "set",
225 [OP_SYMADDR] = "symaddr",
226 [OP_GET_ELEMENT_PTR] = "getelem",
227
228 /* Other */
229 [OP_PHI] = "phi",
230 [OP_PHISOURCE] = "phisrc",
231 [OP_CAST] = "cast",
232 [OP_SCAST] = "scast",
233 [OP_FPCAST] = "fpcast",
234 [OP_PTRCAST] = "ptrcast",
235 [OP_INLINED_CALL] = "# call",
236 [OP_CALL] = "call",
237 [OP_VANEXT] = "va_next",
238 [OP_VAARG] = "va_arg",
239 [OP_SLICE] = "slice",
240 [OP_SNOP] = "snop",
241 [OP_LNOP] = "lnop",
242 [OP_NOP] = "nop",
243 [OP_DEATHNOTE] = "dead",
244 [OP_ASM] = "asm",
245
246 /* Sparse tagging (line numbers, context, whatever) */
247 [OP_CONTEXT] = "context",
248 [OP_RANGE] = "range-check",
249
250 [OP_COPY] = "copy",
251 };
252
253 static char *show_asm_constraints(char *buf, const char *sep, struct asm_constraint_list *list)
254 {
255 struct asm_constraint *entry;
256
257 FOR_EACH_PTR(list, entry) {
258 buf += sprintf(buf, "%s\"%s\"", sep, entry->constraint);
259 if (entry->pseudo)
260 buf += sprintf(buf, " (%s)", show_pseudo(entry->pseudo));
261 if (entry->ident)
290 const char *op = opcodes[opcode];
291 if (!op)
292 buf += sprintf(buf, "opcode:%d", opcode);
293 else
294 buf += sprintf(buf, "%s", op);
295 if (insn->size)
296 buf += sprintf(buf, ".%d", insn->size);
297 memset(buf, ' ', 20);
298 buf++;
299 }
300
301 if (buf < buffer + 12)
302 buf = buffer + 12;
303 switch (opcode) {
304 case OP_RET:
305 if (insn->src && insn->src != VOID)
306 buf += sprintf(buf, "%s", show_pseudo(insn->src));
307 break;
308
309 case OP_CBR:
310 buf += sprintf(buf, "%s, .L%u, .L%u", show_pseudo(insn->cond), insn->bb_true->nr, insn->bb_false->nr);
311 break;
312
313 case OP_BR:
314 buf += sprintf(buf, ".L%u", insn->bb_true->nr);
315 break;
316
317 case OP_SYMADDR: {
318 struct symbol *sym = insn->symbol->sym;
319 buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
320
321 if (!insn->bb && !sym)
322 break;
323 if (sym->bb_target) {
324 buf += sprintf(buf, ".L%u", sym->bb_target->nr);
325 break;
326 }
327 if (sym->ident) {
328 buf += sprintf(buf, "%s", show_ident(sym->ident));
329 break;
330 }
331 buf += sprintf(buf, "<anon symbol:%p>", sym);
332 break;
333 }
334
335 case OP_SETVAL: {
336 struct expression *expr = insn->val;
337 struct symbol *sym;
338 buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
339
340 if (!expr) {
341 buf += sprintf(buf, "%s", "<none>");
342 break;
343 }
344
345 switch (expr->type) {
346 case EXPR_VALUE:
347 buf += sprintf(buf, "%lld", expr->value);
348 break;
349 case EXPR_FVALUE:
350 buf += sprintf(buf, "%Lf", expr->fvalue);
351 break;
352 case EXPR_STRING:
353 buf += sprintf(buf, "%.40s", show_string(expr->string));
354 break;
355 case EXPR_SYMBOL:
356 buf += sprintf(buf, "%s", show_ident(expr->symbol->ident));
357 break;
358 case EXPR_LABEL:
359 sym = expr->symbol;
360 if (sym->bb_target)
361 buf += sprintf(buf, ".L%u", sym->bb_target->nr);
362 break;
363 default:
364 buf += sprintf(buf, "SETVAL EXPR TYPE %d", expr->type);
365 }
366 break;
367 }
368 case OP_SWITCH: {
369 struct multijmp *jmp;
370 buf += sprintf(buf, "%s", show_pseudo(insn->cond));
371 FOR_EACH_PTR(insn->multijmp_list, jmp) {
372 if (jmp->begin == jmp->end)
373 buf += sprintf(buf, ", %d -> .L%u", jmp->begin, jmp->target->nr);
374 else if (jmp->begin < jmp->end)
375 buf += sprintf(buf, ", %d ... %d -> .L%u", jmp->begin, jmp->end, jmp->target->nr);
376 else
377 buf += sprintf(buf, ", default -> .L%u", jmp->target->nr);
378 } END_FOR_EACH_PTR(jmp);
379 break;
380 }
381 case OP_COMPUTEDGOTO: {
382 struct multijmp *jmp;
383 buf += sprintf(buf, "%s", show_pseudo(insn->target));
384 FOR_EACH_PTR(insn->multijmp_list, jmp) {
385 buf += sprintf(buf, ", .L%u", jmp->target->nr);
386 } END_FOR_EACH_PTR(jmp);
387 break;
388 }
389
390 case OP_PHISOURCE: {
391 struct instruction *phi;
392 buf += sprintf(buf, "%s <- %s ", show_pseudo(insn->target), show_pseudo(insn->phi_src));
393 FOR_EACH_PTR(insn->phi_users, phi) {
394 buf += sprintf(buf, " (%s)", show_pseudo(phi->target));
395 } END_FOR_EACH_PTR(phi);
396 break;
397 }
398
399 case OP_PHI: {
400 pseudo_t phi;
401 const char *s = " <-";
402 buf += sprintf(buf, "%s", show_pseudo(insn->target));
403 FOR_EACH_PTR(insn->phi_list, phi) {
404 buf += sprintf(buf, "%s %s", s, show_pseudo(phi));
405 s = ",";
406 } END_FOR_EACH_PTR(phi);
407 break;
408 }
409 case OP_LOAD: case OP_LNOP:
410 buf += sprintf(buf, "%s <- %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
411 break;
412 case OP_STORE: case OP_SNOP:
413 buf += sprintf(buf, "%s -> %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
414 break;
415 case OP_INLINED_CALL:
416 case OP_CALL: {
417 struct pseudo *arg;
418 if (insn->target && insn->target != VOID)
419 buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
420 buf += sprintf(buf, "%s", show_pseudo(insn->func));
421 FOR_EACH_PTR(insn->arguments, arg) {
422 buf += sprintf(buf, ", %s", show_pseudo(arg));
423 } END_FOR_EACH_PTR(arg);
424 break;
425 }
426 case OP_CAST:
427 case OP_SCAST:
428 case OP_FPCAST:
429 case OP_PTRCAST:
430 buf += sprintf(buf, "%s <- (%d) %s",
431 show_pseudo(insn->target),
432 type_size(insn->orig_type),
433 show_pseudo(insn->src));
434 break;
435 case OP_BINARY ... OP_BINARY_END:
436 case OP_BINCMP ... OP_BINCMP_END:
437 buf += sprintf(buf, "%s <- %s, %s", show_pseudo(insn->target), show_pseudo(insn->src1), show_pseudo(insn->src2));
438 break;
439
440 case OP_SEL:
441 buf += sprintf(buf, "%s <- %s, %s, %s", show_pseudo(insn->target),
442 show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3));
443 break;
444
445 case OP_SLICE:
446 buf += sprintf(buf, "%s <- %s, %d, %d", show_pseudo(insn->target), show_pseudo(insn->base), insn->from, insn->len);
447 break;
448
449 case OP_NOT: case OP_NEG:
450 buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1));
451 break;
452
453 case OP_CONTEXT:
454 buf += sprintf(buf, "%s%d", insn->check ? "check: " : "", insn->increment);
455 break;
456 case OP_RANGE:
457 buf += sprintf(buf, "%s between %s..%s", show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3));
458 break;
459 case OP_NOP:
460 buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1));
461 break;
462 case OP_DEATHNOTE:
463 buf += sprintf(buf, "%s", show_pseudo(insn->target));
464 break;
465 case OP_ASM:
466 buf = show_asm(buf, insn);
467 break;
468 case OP_COPY:
469 buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src));
470 break;
471 default:
472 break;
473 }
474
475 if (buf >= buffer + sizeof(buffer))
476 die("instruction buffer overflowed %td\n", buf - buffer);
477 do { --buf; } while (*buf == ' ');
478 *++buf = 0;
479 return buffer;
480 }
481
482 void show_bb(struct basic_block *bb)
483 {
484 struct instruction *insn;
485
486 printf(".L%u:\n", bb->nr);
487 if (verbose) {
488 pseudo_t needs, defines;
489 printf("%s:%d\n", stream_name(bb->pos.stream), bb->pos.line);
490
491 FOR_EACH_PTR(bb->needs, needs) {
492 struct instruction *def = needs->def;
493 if (def->opcode != OP_PHI) {
494 printf(" **uses %s (from .L%u)**\n", show_pseudo(needs), def->bb->nr);
495 } else {
496 pseudo_t phi;
497 const char *sep = " ";
498 printf(" **uses %s (from", show_pseudo(needs));
499 FOR_EACH_PTR(def->phi_list, phi) {
500 if (phi == VOID)
501 continue;
502 printf("%s(%s:.L%u)", sep, show_pseudo(phi), phi->def->bb->nr);
503 sep = ", ";
504 } END_FOR_EACH_PTR(phi);
505 printf(")**\n");
506 }
507 } END_FOR_EACH_PTR(needs);
508
509 FOR_EACH_PTR(bb->defines, defines) {
510 printf(" **defines %s **\n", show_pseudo(defines));
511 } END_FOR_EACH_PTR(defines);
512
513 if (bb->parents) {
514 struct basic_block *from;
515 FOR_EACH_PTR(bb->parents, from) {
516 printf(" **from .L%u (%s:%d:%d)**\n", from->nr,
517 stream_name(from->pos.stream), from->pos.line, from->pos.pos);
518 } END_FOR_EACH_PTR(from);
519 }
520
521 if (bb->children) {
522 struct basic_block *to;
523 FOR_EACH_PTR(bb->children, to) {
524 printf(" **to .L%u (%s:%d:%d)**\n", to->nr,
525 stream_name(to->pos.stream), to->pos.line, to->pos.pos);
526 } END_FOR_EACH_PTR(to);
527 }
528 }
529
530 FOR_EACH_PTR(bb->insns, insn) {
531 if (!insn->bb && verbose < 2)
532 continue;
533 printf("\t%s\n", show_instruction(insn));
534 } END_FOR_EACH_PTR(insn);
535 if (!bb_terminated(bb))
536 printf("\tEND\n");
537 }
538
539 static void show_symbol_usage(pseudo_t pseudo)
540 {
541 struct pseudo_user *pu;
542
543 if (pseudo) {
544 FOR_EACH_PTR(pseudo->users, pu) {
668 FOR_EACH_PTR(bb->children, child) {
669 if (child == target) {
670 target = NULL; /* Trigger just once */
671 continue;
672 }
673 DELETE_CURRENT_PTR(child);
674 remove_parent(child, bb);
675 } END_FOR_EACH_PTR(child);
676 PACK_PTR_LIST(&bb->children);
677 }
678
679
680 void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi_node, pseudo_t if_true, pseudo_t if_false)
681 {
682 pseudo_t target;
683 struct instruction *select;
684
685 /* Remove the 'br' */
686 delete_last_instruction(&bb->insns);
687
688 select = alloc_instruction(OP_SEL, phi_node->size);
689 select->bb = bb;
690
691 assert(br->cond);
692 use_pseudo(select, br->cond, &select->src1);
693
694 target = phi_node->target;
695 assert(target->def == phi_node);
696 select->target = target;
697 target->def = select;
698
699 use_pseudo(select, if_true, &select->src2);
700 use_pseudo(select, if_false, &select->src3);
701
702 add_instruction(&bb->insns, select);
703 add_instruction(&bb->insns, br);
704 }
705
706 static inline int bb_empty(struct basic_block *bb)
707 {
708 return !bb->insns;
709 }
710
711 /* Add a label to the currently active block, return new active block */
712 static struct basic_block * add_label(struct entrypoint *ep, struct symbol *label)
713 {
714 struct basic_block *bb = label->bb_target;
715
716 if (bb) {
717 set_activeblock(ep, bb);
718 return bb;
719 }
720 bb = ep->active;
721 if (!bb_reachable(bb) || !bb_empty(bb)) {
722 bb = alloc_basic_block(ep, label->pos);
723 set_activeblock(ep, bb);
724 }
725 label->bb_target = bb;
726 return bb;
727 }
728
729 static void add_branch(struct entrypoint *ep, struct expression *expr, pseudo_t cond, struct basic_block *bb_true, struct basic_block *bb_false)
730 {
731 struct basic_block *bb = ep->active;
732 struct instruction *br;
733
734 if (bb_reachable(bb)) {
735 br = alloc_instruction(OP_CBR, 0);
736 use_pseudo(br, cond, &br->cond);
737 br->bb_true = bb_true;
738 br->bb_false = bb_false;
739 add_bb(&bb_true->parents, bb);
740 add_bb(&bb_false->parents, bb);
741 add_bb(&bb->children, bb_true);
742 add_bb(&bb->children, bb_false);
743 add_one_insn(ep, br);
744 }
745 }
746
747 /* Dummy pseudo allocator */
748 pseudo_t alloc_pseudo(struct instruction *def)
749 {
750 static int nr = 0;
751 struct pseudo * pseudo = __alloc_pseudo(0);
752 pseudo->type = PSEUDO_REG;
753 pseudo->nr = ++nr;
754 pseudo->def = def;
755 return pseudo;
756 }
757
758 static void clear_symbol_pseudos(struct entrypoint *ep)
759 {
760 pseudo_t pseudo;
761
762 FOR_EACH_PTR(ep->accesses, pseudo) {
763 pseudo->sym->pseudo = NULL;
764 } END_FOR_EACH_PTR(pseudo);
765 }
766
767 static pseudo_t symbol_pseudo(struct entrypoint *ep, struct symbol *sym)
768 {
769 pseudo_t pseudo;
770
771 if (!sym)
772 return VOID;
773
774 pseudo = sym->pseudo;
775 if (!pseudo) {
776 pseudo = __alloc_pseudo(0);
777 pseudo->nr = -1;
778 pseudo->type = PSEUDO_SYM;
779 pseudo->sym = sym;
780 pseudo->ident = sym->ident;
781 sym->pseudo = pseudo;
782 add_pseudo(&ep->accesses, pseudo);
783 }
784 /* Symbol pseudos have neither nr, usage nor def */
785 return pseudo;
786 }
787
788 pseudo_t value_pseudo(struct symbol *type, long long val)
789 {
790 #define MAX_VAL_HASH 64
791 static struct pseudo_list *prev[MAX_VAL_HASH];
792 int hash = val & (MAX_VAL_HASH-1);
793 struct pseudo_list **list = prev + hash;
794 int size = type ? type->bit_size : value_size(val);
795 pseudo_t pseudo;
796
797
798 FOR_EACH_PTR(*list, pseudo) {
799 if (pseudo->value == val && pseudo->size == size)
800 return pseudo;
801 } END_FOR_EACH_PTR(pseudo);
802
803 pseudo = __alloc_pseudo(0);
804 pseudo->type = PSEUDO_VAL;
805 pseudo->value = val;
806 pseudo->size = size;
807 add_pseudo(list, pseudo);
808
809 /* Value pseudos have neither nr, usage nor def */
810 return pseudo;
811 }
812
813 static pseudo_t argument_pseudo(struct entrypoint *ep, int nr)
814 {
815 pseudo_t pseudo = __alloc_pseudo(0);
816 struct instruction *entry = ep->entry;
817
818 pseudo->type = PSEUDO_ARG;
819 pseudo->nr = nr;
820 pseudo->def = entry;
821 add_pseudo(&entry->arg_list, pseudo);
822
823 /* Argument pseudos have neither usage nor def */
824 return pseudo;
825 }
826
827 pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size)
828 {
829 struct instruction *insn;
830 pseudo_t phi;
831 static int nr = 0;
832
833 if (!source)
834 return VOID;
835
836 insn = alloc_instruction(OP_PHISOURCE, size);
837 phi = __alloc_pseudo(0);
838 phi->type = PSEUDO_PHI;
839 phi->nr = ++nr;
840 phi->def = insn;
841
842 use_pseudo(insn, pseudo, &insn->phi_src);
843 insn->bb = source;
844 insn->target = phi;
845 add_instruction(&source->insns, insn);
846 return phi;
847 }
848
849 /*
850 * We carry the "access_data" structure around for any accesses,
851 * which simplifies things a lot. It contains all the access
852 * information in one place.
853 */
854 struct access_data {
855 struct symbol *result_type; // result ctype
856 struct symbol *source_type; // source ctype
857 pseudo_t address; // pseudo containing address ..
858 unsigned int offset; // byte offset
859 struct position pos;
860 };
861
862 static void finish_address_gen(struct entrypoint *ep, struct access_data *ad)
863 {
864 }
865
866 static int linearize_simple_address(struct entrypoint *ep,
867 struct expression *addr,
868 struct access_data *ad)
869 {
870 if (addr->type == EXPR_SYMBOL) {
871 linearize_one_symbol(ep, addr->symbol);
872 ad->address = symbol_pseudo(ep, addr->symbol);
873 return 1;
874 }
875 if (addr->type == EXPR_BINOP) {
876 if (addr->right->type == EXPR_VALUE) {
877 if (addr->op == '+') {
878 ad->offset += get_expression_value(addr->right);
879 return linearize_simple_address(ep, addr->left, ad);
880 }
881 }
882 }
883 ad->address = linearize_expression(ep, addr);
884 return 1;
885 }
886
887 static struct symbol *base_type(struct symbol *sym)
888 {
889 struct symbol *base = sym;
890
891 if (sym) {
892 if (sym->type == SYM_NODE)
893 base = base->ctype.base_type;
894 if (base->type == SYM_BITFIELD)
895 return base->ctype.base_type;
896 }
897 return sym;
898 }
899
900 static int linearize_address_gen(struct entrypoint *ep,
901 struct expression *expr,
902 struct access_data *ad)
903 {
904 struct symbol *ctype = expr->ctype;
905
906 if (!ctype)
907 return 0;
908 ad->pos = expr->pos;
909 ad->result_type = ctype;
910 ad->source_type = base_type(ctype);
911 if (expr->type == EXPR_PREOP && expr->op == '*')
912 return linearize_simple_address(ep, expr->unop, ad);
913
914 warning(expr->pos, "generating address of non-lvalue (%d)", expr->type);
915 return 0;
916 }
917
918 static pseudo_t add_load(struct entrypoint *ep, struct access_data *ad)
919 {
920 struct instruction *insn;
921 pseudo_t new;
922
923 insn = alloc_typed_instruction(OP_LOAD, ad->source_type);
924 new = alloc_pseudo(insn);
925
926 insn->target = new;
927 insn->offset = ad->offset;
928 use_pseudo(insn, ad->address, &insn->src);
929 add_one_insn(ep, insn);
930 return new;
931 }
932
933 static void add_store(struct entrypoint *ep, struct access_data *ad, pseudo_t value)
934 {
935 struct basic_block *bb = ep->active;
936
937 if (bb_reachable(bb)) {
938 struct instruction *store = alloc_typed_instruction(OP_STORE, ad->source_type);
939 store->offset = ad->offset;
940 use_pseudo(store, value, &store->target);
941 use_pseudo(store, ad->address, &store->src);
942 add_one_insn(ep, store);
943 }
944 }
945
946 static pseudo_t linearize_store_gen(struct entrypoint *ep,
947 pseudo_t value,
948 struct access_data *ad)
949 {
950 pseudo_t store = value;
951
952 if (type_size(ad->source_type) != type_size(ad->result_type)) {
953 struct symbol *ctype = ad->result_type;
954 unsigned int shift = ctype->bit_offset;
955 unsigned int size = ctype->bit_size;
956 pseudo_t orig = add_load(ep, ad);
957 unsigned long long mask = (1ULL << size) - 1;
958
959 if (shift) {
960 store = add_binary_op(ep, ad->source_type, OP_SHL, value, value_pseudo(ctype, shift));
961 mask <<= shift;
962 }
963 orig = add_binary_op(ep, ad->source_type, OP_AND, orig, value_pseudo(ctype, ~mask));
964 store = add_binary_op(ep, ad->source_type, OP_OR, orig, store);
965 }
966 add_store(ep, ad, store);
967 return value;
968 }
969
970 static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right)
971 {
972 struct instruction *insn = alloc_typed_instruction(op, ctype);
973 pseudo_t target = alloc_pseudo(insn);
974 insn->target = target;
975 use_pseudo(insn, left, &insn->src1);
976 use_pseudo(insn, right, &insn->src2);
977 add_one_insn(ep, insn);
978 return target;
979 }
980
981 static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val)
982 {
983 struct instruction *insn = alloc_typed_instruction(OP_SETVAL, ctype);
984 pseudo_t target = alloc_pseudo(insn);
985 insn->target = target;
986 insn->val = val;
987 add_one_insn(ep, insn);
988 return target;
989 }
990
991 static pseudo_t add_symbol_address(struct entrypoint *ep, struct symbol *sym)
992 {
993 struct instruction *insn = alloc_instruction(OP_SYMADDR, bits_in_pointer);
994 pseudo_t target = alloc_pseudo(insn);
995
996 insn->target = target;
997 use_pseudo(insn, symbol_pseudo(ep, sym), &insn->symbol);
998 add_one_insn(ep, insn);
999 return target;
1000 }
1001
1002 static pseudo_t linearize_load_gen(struct entrypoint *ep, struct access_data *ad)
1003 {
1004 struct symbol *ctype = ad->result_type;
1005 pseudo_t new = add_load(ep, ad);
1006
1007 if (ctype->bit_offset) {
1008 pseudo_t shift = value_pseudo(ctype, ctype->bit_offset);
1009 pseudo_t newval = add_binary_op(ep, ad->source_type, OP_LSR, new, shift);
1010 new = newval;
1011 }
1012 if (ctype->bit_size != type_size(ad->source_type))
1013 new = cast_pseudo(ep, new, ad->source_type, ad->result_type);
1014 return new;
1015 }
1016
1017 static pseudo_t linearize_access(struct entrypoint *ep, struct expression *expr)
1018 {
1019 struct access_data ad = { NULL, };
1020 pseudo_t value;
1021
1022 if (!linearize_address_gen(ep, expr, &ad))
1023 return VOID;
1024 value = linearize_load_gen(ep, &ad);
1025 finish_address_gen(ep, &ad);
1026 return value;
1027 }
1028
1029 /* FIXME: FP */
1030 static pseudo_t linearize_inc_dec(struct entrypoint *ep, struct expression *expr, int postop)
1031 {
1032 struct access_data ad = { NULL, };
1033 pseudo_t old, new, one;
1034 int op = expr->op == SPECIAL_INCREMENT ? OP_ADD : OP_SUB;
1035
1036 if (!linearize_address_gen(ep, expr->unop, &ad))
1037 return VOID;
1038
1039 old = linearize_load_gen(ep, &ad);
1040 one = value_pseudo(expr->ctype, expr->op_value);
1041 new = add_binary_op(ep, expr->ctype, op, old, one);
1042 linearize_store_gen(ep, new, &ad);
1043 finish_address_gen(ep, &ad);
1044 return postop ? old : new;
1045 }
1046
1047 static pseudo_t add_uniop(struct entrypoint *ep, struct expression *expr, int op, pseudo_t src)
1048 {
1049 struct instruction *insn = alloc_typed_instruction(op, expr->ctype);
1050 pseudo_t new = alloc_pseudo(insn);
1051
1052 insn->target = new;
1053 use_pseudo(insn, src, &insn->src1);
1054 add_one_insn(ep, insn);
1055 return new;
1056 }
1057
1058 static pseudo_t linearize_slice(struct entrypoint *ep, struct expression *expr)
1059 {
1060 pseudo_t pre = linearize_expression(ep, expr->base);
1061 struct instruction *insn = alloc_typed_instruction(OP_SLICE, expr->ctype);
1062 pseudo_t new = alloc_pseudo(insn);
1063
1064 insn->target = new;
1065 insn->from = expr->r_bitpos;
1066 insn->len = expr->r_nrbits;
1067 use_pseudo(insn, pre, &insn->base);
1068 add_one_insn(ep, insn);
1069 return new;
1070 }
1071
1072 static pseudo_t linearize_regular_preop(struct entrypoint *ep, struct expression *expr)
1073 {
1074 pseudo_t pre = linearize_expression(ep, expr->unop);
1075 switch (expr->op) {
1076 case '+':
1077 return pre;
1078 case '!': {
1079 pseudo_t zero = value_pseudo(expr->ctype, 0);
1080 return add_binary_op(ep, expr->ctype, OP_SET_EQ, pre, zero);
1081 }
1082 case '~':
1083 return add_uniop(ep, expr, OP_NOT, pre);
1084 case '-':
1085 return add_uniop(ep, expr, OP_NEG, pre);
1086 }
1087 return VOID;
1088 }
1089
1090 static pseudo_t linearize_preop(struct entrypoint *ep, struct expression *expr)
1091 {
1092 /*
1093 * '*' is an lvalue access, and is fundamentally different
1094 * from an arithmetic operation. Maybe it should have an
1095 * expression type of its own..
1096 */
1097 if (expr->op == '*')
1098 return linearize_access(ep, expr);
1099 if (expr->op == SPECIAL_INCREMENT || expr->op == SPECIAL_DECREMENT)
1100 return linearize_inc_dec(ep, expr, 0);
1101 return linearize_regular_preop(ep, expr);
1102 }
1103
1104 static pseudo_t linearize_postop(struct entrypoint *ep, struct expression *expr)
1105 {
1106 return linearize_inc_dec(ep, expr, 1);
1107 }
1108
1109 /*
1110 * Casts to pointers are "less safe" than other casts, since
1111 * they imply type-unsafe accesses. "void *" is a special
1112 * case, since you can't access through it anyway without another
1113 * cast.
1114 */
1115 static struct instruction *alloc_cast_instruction(struct symbol *src, struct symbol *ctype)
1116 {
1117 int opcode = OP_CAST;
1118 struct symbol *base = ctype;
1119
1120 if (src->ctype.modifiers & MOD_SIGNED)
1121 opcode = OP_SCAST;
1122 if (base->type == SYM_NODE)
1123 base = base->ctype.base_type;
1124 if (base->type == SYM_PTR) {
1125 base = base->ctype.base_type;
1126 if (base != &void_ctype)
1127 opcode = OP_PTRCAST;
1128 } else if (base->ctype.base_type == &fp_type)
1129 opcode = OP_FPCAST;
1130 return alloc_typed_instruction(opcode, ctype);
1131 }
1132
1133 static pseudo_t cast_pseudo(struct entrypoint *ep, pseudo_t src, struct symbol *from, struct symbol *to)
1134 {
1135 pseudo_t result;
1136 struct instruction *insn;
1137
1138 if (src == VOID)
1139 return VOID;
1140 if (!from || !to)
1141 return VOID;
1142 if (from->bit_size < 0 || to->bit_size < 0)
1143 return VOID;
1144 insn = alloc_cast_instruction(from, to);
1145 result = alloc_pseudo(insn);
1146 insn->target = result;
1147 insn->orig_type = from;
1148 use_pseudo(insn, src, &insn->src);
1149 add_one_insn(ep, insn);
1150 return result;
1151 }
1152
1153 static int opcode_sign(int opcode, struct symbol *ctype)
1154 {
1155 if (ctype && (ctype->ctype.modifiers & MOD_SIGNED)) {
1156 switch(opcode) {
1157 case OP_MULU: case OP_DIVU: case OP_MODU: case OP_LSR:
1158 opcode++;
1159 }
1160 }
1161 return opcode;
1162 }
1163
1164 static inline pseudo_t add_convert_to_bool(struct entrypoint *ep, pseudo_t src, struct symbol *type)
1165 {
1166 pseudo_t zero;
1167 int op;
1168
1169 if (is_bool_type(type))
1170 return src;
1171 zero = value_pseudo(type, 0);
1172 op = OP_SET_NE;
1173 return add_binary_op(ep, &bool_ctype, op, src, zero);
1174 }
1175
1176 static pseudo_t linearize_expression_to_bool(struct entrypoint *ep, struct expression *expr)
1177 {
1178 pseudo_t dst;
1179 dst = linearize_expression(ep, expr);
1180 dst = add_convert_to_bool(ep, dst, expr->ctype);
1181 return dst;
1182 }
1183
1184 static pseudo_t linearize_assignment(struct entrypoint *ep, struct expression *expr)
1185 {
1186 struct access_data ad = { NULL, };
1187 struct expression *target = expr->left;
1188 struct expression *src = expr->right;
1189 struct symbol *ctype;
1190 pseudo_t value;
1191
1192 value = linearize_expression(ep, src);
1193 if (!target || !linearize_address_gen(ep, target, &ad))
1194 return value;
1195 if (expr->op != '=') {
1196 pseudo_t oldvalue = linearize_load_gen(ep, &ad);
1197 pseudo_t dst;
1198 static const int op_trans[] = {
1199 [SPECIAL_ADD_ASSIGN - SPECIAL_BASE] = OP_ADD,
1200 [SPECIAL_SUB_ASSIGN - SPECIAL_BASE] = OP_SUB,
1201 [SPECIAL_MUL_ASSIGN - SPECIAL_BASE] = OP_MULU,
1202 [SPECIAL_DIV_ASSIGN - SPECIAL_BASE] = OP_DIVU,
1203 [SPECIAL_MOD_ASSIGN - SPECIAL_BASE] = OP_MODU,
1204 [SPECIAL_SHL_ASSIGN - SPECIAL_BASE] = OP_SHL,
1205 [SPECIAL_SHR_ASSIGN - SPECIAL_BASE] = OP_LSR,
1206 [SPECIAL_AND_ASSIGN - SPECIAL_BASE] = OP_AND,
1207 [SPECIAL_OR_ASSIGN - SPECIAL_BASE] = OP_OR,
1208 [SPECIAL_XOR_ASSIGN - SPECIAL_BASE] = OP_XOR
1209 };
1210 int opcode;
1211
1212 if (!src)
1213 return VOID;
1214
1215 ctype = src->ctype;
1216 oldvalue = cast_pseudo(ep, oldvalue, target->ctype, ctype);
1217 opcode = opcode_sign(op_trans[expr->op - SPECIAL_BASE], ctype);
1218 dst = add_binary_op(ep, ctype, opcode, oldvalue, value);
1219 value = cast_pseudo(ep, dst, ctype, expr->ctype);
1220 }
1221 value = linearize_store_gen(ep, value, &ad);
1222 finish_address_gen(ep, &ad);
1223 return value;
1224 }
1225
1226 static pseudo_t linearize_call_expression(struct entrypoint *ep, struct expression *expr)
1227 {
1228 struct expression *arg, *fn;
1229 struct instruction *insn = alloc_typed_instruction(OP_CALL, expr->ctype);
1230 pseudo_t retval, call;
1231 struct ctype *ctype = NULL;
1232 struct symbol *fntype;
1233 struct context *context;
1234
1235 if (!expr->ctype) {
1236 warning(expr->pos, "call with no type!");
1237 return VOID;
1238 }
1239
1240 FOR_EACH_PTR(expr->args, arg) {
1241 pseudo_t new = linearize_expression(ep, arg);
1242 use_pseudo(insn, new, add_pseudo(&insn->arguments, new));
1243 } END_FOR_EACH_PTR(arg);
1244
1245 fn = expr->fn;
1246
1247 if (fn->ctype)
1248 ctype = &fn->ctype->ctype;
1249
1250 fntype = fn->ctype;
1251 if (fntype) {
1252 if (fntype->type == SYM_NODE)
1253 fntype = fntype->ctype.base_type;
1254 }
1255 insn->fntype = fntype;
1256
1257 if (fn->type == EXPR_PREOP) {
1258 if (fn->unop->type == EXPR_SYMBOL) {
1259 struct symbol *sym = fn->unop->symbol;
1260 if (sym->ctype.base_type->type == SYM_FN)
1261 fn = fn->unop;
1262 }
1263 }
1264 if (fn->type == EXPR_SYMBOL) {
1265 call = symbol_pseudo(ep, fn->symbol);
1266 } else {
1267 call = linearize_expression(ep, fn);
1268 }
1269 use_pseudo(insn, call, &insn->func);
1270 retval = VOID;
1271 if (expr->ctype != &void_ctype)
1272 retval = alloc_pseudo(insn);
1273 insn->target = retval;
1274 add_one_insn(ep, insn);
1275
1276 if (ctype) {
1277 FOR_EACH_PTR(ctype->contexts, context) {
1278 int in = context->in;
1279 int out = context->out;
1280 int check = 0;
1281 int context_diff;
1282 if (in < 0) {
1283 check = 1;
1287 check = 0;
1288 out = 0;
1289 }
1290 context_diff = out - in;
1291 if (check || context_diff) {
1292 insn = alloc_instruction(OP_CONTEXT, 0);
1293 insn->increment = context_diff;
1294 insn->check = check;
1295 insn->context_expr = context->context;
1296 add_one_insn(ep, insn);
1297 }
1298 } END_FOR_EACH_PTR(context);
1299 }
1300
1301 return retval;
1302 }
1303
1304 static pseudo_t linearize_binop_bool(struct entrypoint *ep, struct expression *expr)
1305 {
1306 pseudo_t src1, src2, dst;
1307 int op = (expr->op == SPECIAL_LOGICAL_OR) ? OP_OR_BOOL : OP_AND_BOOL;
1308
1309 src1 = linearize_expression_to_bool(ep, expr->left);
1310 src2 = linearize_expression_to_bool(ep, expr->right);
1311 dst = add_binary_op(ep, &bool_ctype, op, src1, src2);
1312 if (expr->ctype != &bool_ctype)
1313 dst = cast_pseudo(ep, dst, &bool_ctype, expr->ctype);
1314 return dst;
1315 }
1316
1317 static pseudo_t linearize_binop(struct entrypoint *ep, struct expression *expr)
1318 {
1319 pseudo_t src1, src2, dst;
1320 static const int opcode[] = {
1321 ['+'] = OP_ADD, ['-'] = OP_SUB,
1322 ['*'] = OP_MULU, ['/'] = OP_DIVU,
1323 ['%'] = OP_MODU, ['&'] = OP_AND,
1324 ['|'] = OP_OR, ['^'] = OP_XOR,
1325 [SPECIAL_LEFTSHIFT] = OP_SHL,
1326 [SPECIAL_RIGHTSHIFT] = OP_LSR,
1327 };
1328 int op;
1329
1330 src1 = linearize_expression(ep, expr->left);
1331 src2 = linearize_expression(ep, expr->right);
1332 op = opcode_sign(opcode[expr->op], expr->ctype);
1333 dst = add_binary_op(ep, expr->ctype, op, src1, src2);
1334 return dst;
1335 }
1336
1337 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
1338
1339 pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
1340
1341 static pseudo_t linearize_select(struct entrypoint *ep, struct expression *expr)
1342 {
1343 pseudo_t cond, true, false, res;
1344 struct instruction *insn;
1345
1346 true = linearize_expression(ep, expr->cond_true);
1347 false = linearize_expression(ep, expr->cond_false);
1348 cond = linearize_expression(ep, expr->conditional);
1349
1350 insn = alloc_typed_instruction(OP_SEL, expr->ctype);
1351 if (!expr->cond_true)
1352 true = cond;
1353 use_pseudo(insn, cond, &insn->src1);
1354 use_pseudo(insn, true, &insn->src2);
1355 use_pseudo(insn, false, &insn->src3);
1356
1357 res = alloc_pseudo(insn);
1358 insn->target = res;
1359 add_one_insn(ep, insn);
1360 return res;
1361 }
1362
1363 static pseudo_t add_join_conditional(struct entrypoint *ep, struct expression *expr,
1364 pseudo_t phi1, pseudo_t phi2)
1365 {
1366 pseudo_t target;
1367 struct instruction *phi_node;
1368
1369 if (phi1 == VOID)
1370 return phi2;
1371 if (phi2 == VOID)
1372 return phi1;
1373
1374 phi_node = alloc_typed_instruction(OP_PHI, expr->ctype);
1375 use_pseudo(phi_node, phi1, add_pseudo(&phi_node->phi_list, phi1));
1376 use_pseudo(phi_node, phi2, add_pseudo(&phi_node->phi_list, phi2));
1377 phi_node->target = target = alloc_pseudo(phi_node);
1378 add_one_insn(ep, phi_node);
1379 return target;
1380 }
1381
1382 static pseudo_t linearize_short_conditional(struct entrypoint *ep, struct expression *expr,
1383 struct expression *cond,
1384 struct expression *expr_false)
1385 {
1386 pseudo_t src1, src2;
1387 struct basic_block *bb_false;
1388 struct basic_block *merge = alloc_basic_block(ep, expr->pos);
1389 pseudo_t phi1, phi2;
1390 int size = type_size(expr->ctype);
1391
1392 if (!expr_false || !ep->active)
1393 return VOID;
1394
1395 bb_false = alloc_basic_block(ep, expr_false->pos);
1396 src1 = linearize_expression(ep, cond);
1397 phi1 = alloc_phi(ep->active, src1, size);
1398 add_branch(ep, expr, src1, merge, bb_false);
1399
1400 set_activeblock(ep, bb_false);
1401 src2 = linearize_expression(ep, expr_false);
1402 phi2 = alloc_phi(ep->active, src2, size);
1403 set_activeblock(ep, merge);
1404
1405 return add_join_conditional(ep, expr, phi1, phi2);
1406 }
1407
1408 static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *expr,
1409 struct expression *cond,
1410 struct expression *expr_true,
1411 struct expression *expr_false)
1412 {
1413 pseudo_t src1, src2;
1414 pseudo_t phi1, phi2;
1415 struct basic_block *bb_true, *bb_false, *merge;
1416 int size = type_size(expr->ctype);
1417
1418 if (!cond || !expr_true || !expr_false || !ep->active)
1419 return VOID;
1420 bb_true = alloc_basic_block(ep, expr_true->pos);
1421 bb_false = alloc_basic_block(ep, expr_false->pos);
1422 merge = alloc_basic_block(ep, expr->pos);
1423
1424 linearize_cond_branch(ep, cond, bb_true, bb_false);
1425
1426 set_activeblock(ep, bb_true);
1427 src1 = linearize_expression(ep, expr_true);
1428 phi1 = alloc_phi(ep->active, src1, size);
1429 add_goto(ep, merge);
1430
1431 set_activeblock(ep, bb_false);
1432 src2 = linearize_expression(ep, expr_false);
1433 phi2 = alloc_phi(ep->active, src2, size);
1434 set_activeblock(ep, merge);
1435
1436 return add_join_conditional(ep, expr, phi1, phi2);
1437 }
1438
1439 static pseudo_t linearize_logical(struct entrypoint *ep, struct expression *expr)
1440 {
1441 struct expression *shortcut;
1442
1443 shortcut = alloc_const_expression(expr->pos, expr->op == SPECIAL_LOGICAL_OR);
1444 shortcut->ctype = expr->ctype;
1445 if (expr->op == SPECIAL_LOGICAL_OR)
1446 return linearize_conditional(ep, expr, expr->left, shortcut, expr->right);
1447 return linearize_conditional(ep, expr, expr->left, expr->right, shortcut);
1448 }
1449
1450 static pseudo_t linearize_compare(struct entrypoint *ep, struct expression *expr)
1451 {
1452 static const int cmpop[] = {
1453 ['>'] = OP_SET_GT, ['<'] = OP_SET_LT,
1454 [SPECIAL_EQUAL] = OP_SET_EQ,
1455 [SPECIAL_NOTEQUAL] = OP_SET_NE,
1456 [SPECIAL_GTE] = OP_SET_GE,
1457 [SPECIAL_LTE] = OP_SET_LE,
1458 [SPECIAL_UNSIGNED_LT] = OP_SET_B,
1459 [SPECIAL_UNSIGNED_GT] = OP_SET_A,
1460 [SPECIAL_UNSIGNED_LTE] = OP_SET_BE,
1461 [SPECIAL_UNSIGNED_GTE] = OP_SET_AE,
1462 };
1463
1464 pseudo_t src1 = linearize_expression(ep, expr->left);
1465 pseudo_t src2 = linearize_expression(ep, expr->right);
1466 pseudo_t dst = add_binary_op(ep, expr->ctype, cmpop[expr->op], src1, src2);
1467 return dst;
1468 }
1469
1470
1471 pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
1472 {
1473 pseudo_t cond;
1474
1475 if (!expr || !bb_reachable(ep->active))
1476 return VOID;
1477
1478 switch (expr->type) {
1479
1480 case EXPR_STRING:
1481 case EXPR_VALUE:
1482 add_goto(ep, expr->value ? bb_true : bb_false);
1483 return VOID;
1484
1485 case EXPR_FVALUE:
1486 add_goto(ep, expr->fvalue ? bb_true : bb_false);
1487 return VOID;
1488
1489 case EXPR_LOGICAL:
1490 linearize_logical_branch(ep, expr, bb_true, bb_false);
1491 return VOID;
1492
1493 case EXPR_COMPARE:
1494 cond = linearize_compare(ep, expr);
1495 add_branch(ep, expr, cond, bb_true, bb_false);
1496 break;
1497
1498 case EXPR_PREOP:
1499 if (expr->op == '!')
1500 return linearize_cond_branch(ep, expr->unop, bb_false, bb_true);
1501 /* fall through */
1502 default: {
1503 cond = linearize_expression(ep, expr);
1504 add_branch(ep, expr, cond, bb_true, bb_false);
1505
1506 return VOID;
1507 }
1508 }
1509 return VOID;
1510 }
1511
1512
1513
1514 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
1515 {
1516 struct basic_block *next = alloc_basic_block(ep, expr->pos);
1517
1518 if (expr->op == SPECIAL_LOGICAL_OR)
1519 linearize_cond_branch(ep, expr->left, bb_true, next);
1520 else
1521 linearize_cond_branch(ep, expr->left, next, bb_false);
1522 set_activeblock(ep, next);
1523 linearize_cond_branch(ep, expr->right, bb_true, bb_false);
1524 return VOID;
1525 }
1526
1527 static pseudo_t linearize_cast(struct entrypoint *ep, struct expression *expr)
1528 {
1529 pseudo_t src;
1530 struct expression *orig = expr->cast_expression;
1531
1532 if (!orig)
1533 return VOID;
1534
1535 src = linearize_expression(ep, orig);
1536 return cast_pseudo(ep, src, orig->ctype, expr->ctype);
1537 }
1538
1539 static pseudo_t linearize_position(struct entrypoint *ep, struct expression *pos, struct access_data *ad)
1540 {
1541 struct expression *init_expr = pos->init_expr;
1542
1543 ad->offset = pos->init_offset;
1544 ad->source_type = base_type(init_expr->ctype);
1545 ad->result_type = init_expr->ctype;
1546 return linearize_initializer(ep, init_expr, ad);
1547 }
1548
1549 static pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *ad)
1550 {
1551 switch (initializer->type) {
1552 case EXPR_INITIALIZER: {
1553 struct expression *expr;
1554 FOR_EACH_PTR(initializer->expr_list, expr) {
1555 linearize_initializer(ep, expr, ad);
1556 } END_FOR_EACH_PTR(expr);
1557 break;
1558 }
1559 case EXPR_POS:
1560 linearize_position(ep, initializer, ad);
1561 break;
1562 default: {
1563 pseudo_t value = linearize_expression(ep, initializer);
1564 ad->source_type = base_type(initializer->ctype);
1565 ad->result_type = initializer->ctype;
1566 linearize_store_gen(ep, value, ad);
1567 return value;
1568 }
1569 }
1570
1571 return VOID;
1572 }
1573
1574 static void linearize_argument(struct entrypoint *ep, struct symbol *arg, int nr)
1575 {
1576 struct access_data ad = { NULL, };
1577
1578 ad.source_type = arg;
1579 ad.result_type = arg;
1580 ad.address = symbol_pseudo(ep, arg);
1581 linearize_store_gen(ep, argument_pseudo(ep, nr), &ad);
1582 finish_address_gen(ep, &ad);
1583 }
1584
1585 pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr)
1586 {
1587 if (!expr)
1588 return VOID;
1589
1590 current_pos = expr->pos;
1591 switch (expr->type) {
1592 case EXPR_SYMBOL:
1593 linearize_one_symbol(ep, expr->symbol);
1594 return add_symbol_address(ep, expr->symbol);
1595
1596 case EXPR_VALUE:
1597 return value_pseudo(expr->ctype, expr->value);
1598
1599 case EXPR_STRING: case EXPR_FVALUE: case EXPR_LABEL:
1600 return add_setval(ep, expr->ctype, expr);
1601
1602 case EXPR_STATEMENT:
1603 return linearize_statement(ep, expr->statement);
1604
1605 case EXPR_CALL:
1606 return linearize_call_expression(ep, expr);
1607
1608 case EXPR_BINOP:
1609 if (expr->op == SPECIAL_LOGICAL_AND || expr->op == SPECIAL_LOGICAL_OR)
1610 return linearize_binop_bool(ep, expr);
1611 return linearize_binop(ep, expr);
1612
1613 case EXPR_LOGICAL:
1614 return linearize_logical(ep, expr);
1615
1616 case EXPR_COMPARE:
1617 return linearize_compare(ep, expr);
1618
1619 case EXPR_SELECT:
1620 return linearize_select(ep, expr);
1621
1662 {
1663 struct access_data ad = { NULL, };
1664 pseudo_t value;
1665
1666 if (!sym || !sym->initializer || sym->initialized)
1667 return VOID;
1668
1669 /* We need to output these puppies some day too.. */
1670 if (sym->ctype.modifiers & (MOD_STATIC | MOD_TOPLEVEL))
1671 return VOID;
1672
1673 sym->initialized = 1;
1674 ad.address = symbol_pseudo(ep, sym);
1675
1676 if (sym->initializer && !is_scalar_type(sym)) {
1677 // default zero initialization [6.7.9.21]
1678 // FIXME: this init the whole aggregate while
1679 // only the existing fields need to be initialized.
1680 // FIXME: this init the whole aggregate even if
1681 // all fields arelater explicitely initialized.
1682 struct expression *expr = sym->initializer;
1683 ad.pos = expr->pos;
1684 ad.result_type = sym;
1685 ad.source_type = base_type(sym);
1686 ad.address = symbol_pseudo(ep, sym);
1687 linearize_store_gen(ep, value_pseudo(sym, 0), &ad);
1688 }
1689
1690 value = linearize_initializer(ep, sym->initializer, &ad);
1691 finish_address_gen(ep, &ad);
1692 return value;
1693 }
1694
1695 static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct statement *stmt)
1696 {
1697 pseudo_t pseudo;
1698 struct statement *s;
1699 struct symbol *ret = stmt->ret;
1700
1701 pseudo = VOID;
1702 FOR_EACH_PTR(stmt->stmts, s) {
1703 pseudo = linearize_statement(ep, s);
1704 } END_FOR_EACH_PTR(s);
1705
1706 if (ret) {
1707 struct basic_block *bb = add_label(ep, ret);
1708 struct instruction *phi_node = first_instruction(bb->insns);
1709
1710 if (!phi_node)
1711 return pseudo;
1712
1713 if (pseudo_list_size(phi_node->phi_list)==1) {
1714 pseudo = first_pseudo(phi_node->phi_list);
1715 assert(pseudo->type == PSEUDO_PHI);
1716 return pseudo->def->src1;
1717 }
1718 return phi_node->target;
1719 }
1720
1721 return pseudo;
1722 }
1723
1724 static pseudo_t linearize_inlined_call(struct entrypoint *ep, struct statement *stmt)
1725 {
1726 struct instruction *insn = alloc_instruction(OP_INLINED_CALL, 0);
1727 struct statement *args = stmt->args;
1728 struct basic_block *bb;
1729 pseudo_t pseudo;
1730
1731 if (args) {
1732 struct symbol *sym;
1733
1734 concat_symbol_list(args->declaration, &ep->syms);
1735 FOR_EACH_PTR(args->declaration, sym) {
1736 pseudo_t value = linearize_one_symbol(ep, sym);
1737 use_pseudo(insn, value, add_pseudo(&insn->arguments, value));
1738 } END_FOR_EACH_PTR(sym);
1739 }
1740
1741 insn->target = pseudo = linearize_compound_statement(ep, stmt);
1742 use_pseudo(insn, symbol_pseudo(ep, stmt->inline_fn), &insn->func);
1743 bb = ep->active;
1744 if (bb && !bb->insns)
1745 bb->pos = stmt->pos;
1746 add_one_insn(ep, insn);
1747 return pseudo;
1748 }
1749
1750 static pseudo_t linearize_context(struct entrypoint *ep, struct statement *stmt)
1751 {
1752 struct instruction *insn = alloc_instruction(OP_CONTEXT, 0);
1753 struct expression *expr = stmt->expression;
1754 int value = 0;
1755
1756 if (expr->type == EXPR_VALUE)
1757 value = expr->value;
1758
1759 insn->increment = value;
1760 insn->context_expr = stmt->context;
1761 add_one_insn(ep, insn);
1762 return VOID;
1763 }
1764
1765 static pseudo_t linearize_range(struct entrypoint *ep, struct statement *stmt)
1766 {
1767 struct instruction *insn = alloc_instruction(OP_RANGE, 0);
1768
1769 use_pseudo(insn, linearize_expression(ep, stmt->range_expression), &insn->src1);
1770 use_pseudo(insn, linearize_expression(ep, stmt->range_low), &insn->src2);
1771 use_pseudo(insn, linearize_expression(ep, stmt->range_high), &insn->src3);
1772 add_one_insn(ep, insn);
1773 return VOID;
1774 }
1775
1776 ALLOCATOR(asm_rules, "asm rules");
1777 ALLOCATOR(asm_constraint, "asm constraints");
1778
1779 static void add_asm_input(struct entrypoint *ep, struct instruction *insn, struct expression *expr,
1781 {
1782 pseudo_t pseudo = linearize_expression(ep, expr);
1783 struct asm_constraint *rule = __alloc_asm_constraint(0);
1784
1785 rule->ident = ident;
1786 rule->constraint = constraint;
1787 use_pseudo(insn, pseudo, &rule->pseudo);
1788 add_ptr_list(&insn->asm_rules->inputs, rule);
1789 }
1790
1791 static void add_asm_output(struct entrypoint *ep, struct instruction *insn, struct expression *expr,
1792 const char *constraint, const struct ident *ident)
1793 {
1794 struct access_data ad = { NULL, };
1795 pseudo_t pseudo = alloc_pseudo(insn);
1796 struct asm_constraint *rule;
1797
1798 if (!expr || !linearize_address_gen(ep, expr, &ad))
1799 return;
1800 linearize_store_gen(ep, pseudo, &ad);
1801 finish_address_gen(ep, &ad);
1802 rule = __alloc_asm_constraint(0);
1803 rule->ident = ident;
1804 rule->constraint = constraint;
1805 use_pseudo(insn, pseudo, &rule->pseudo);
1806 add_ptr_list(&insn->asm_rules->outputs, rule);
1807 }
1808
1809 static pseudo_t linearize_asm_statement(struct entrypoint *ep, struct statement *stmt)
1810 {
1811 int state;
1812 struct expression *expr;
1813 struct instruction *insn;
1814 struct asm_rules *rules;
1815 const char *constraint;
1816 struct ident *ident;
1817
1818 insn = alloc_instruction(OP_ASM, 0);
1819 expr = stmt->asm_string;
1820 if (!expr || expr->type != EXPR_STRING) {
1821 warning(stmt->pos, "expected string in inline asm");
1822 return VOID;
1823 }
1824 insn->string = expr->string->data;
1825
1826 rules = __alloc_asm_rules(0);
1827 insn->asm_rules = rules;
1828
1829 /* Gather the inputs.. */
1830 state = 0;
1831 ident = NULL;
1832 constraint = NULL;
1833 FOR_EACH_PTR(stmt->asm_inputs, expr) {
1834 switch (state) {
1835 case 0: /* Identifier */
1836 state = 1;
1837 ident = (struct ident *)expr;
1838 continue;
1839
1840 case 1: /* Constraint */
1841 state = 2;
1842 constraint = expr ? expr->string->data : "";
1843 continue;
1844
1845 case 2: /* Expression */
1846 state = 0;
1847 add_asm_input(ep, insn, expr, constraint, ident);
1848 }
1849 } END_FOR_EACH_PTR(expr);
1850
1851 add_one_insn(ep, insn);
1852
1853 /* Assign the outputs */
1854 state = 0;
1855 ident = NULL;
1856 constraint = NULL;
1857 FOR_EACH_PTR(stmt->asm_outputs, expr) {
1858 switch (state) {
1859 case 0: /* Identifier */
1860 state = 1;
1861 ident = (struct ident *)expr;
1862 continue;
1863
1864 case 1: /* Constraint */
1865 state = 2;
1866 constraint = expr ? expr->string->data : "";
1867 continue;
1868
1869 case 2:
1870 state = 0;
1871 add_asm_output(ep, insn, expr, constraint, ident);
1872 }
1873 } END_FOR_EACH_PTR(expr);
1874
1875 return VOID;
1876 }
1877
1878 static int multijmp_cmp(const void *_a, const void *_b)
1879 {
1880 const struct multijmp *a = _a;
1881 const struct multijmp *b = _b;
1882
1883 // "default" case?
1884 if (a->begin > a->end) {
1885 if (b->begin > b->end)
1886 return 0;
1887 return 1;
1888 }
1889 if (b->begin > b->end)
1890 return -1;
1891 if (a->begin == b->begin) {
1892 if (a->end == b->end)
1899 static void sort_switch_cases(struct instruction *insn)
1900 {
1901 sort_list((struct ptr_list **)&insn->multijmp_list, multijmp_cmp);
1902 }
1903
1904 static pseudo_t linearize_declaration(struct entrypoint *ep, struct statement *stmt)
1905 {
1906 struct symbol *sym;
1907
1908 concat_symbol_list(stmt->declaration, &ep->syms);
1909
1910 FOR_EACH_PTR(stmt->declaration, sym) {
1911 linearize_one_symbol(ep, sym);
1912 } END_FOR_EACH_PTR(sym);
1913 return VOID;
1914 }
1915
1916 static pseudo_t linearize_return(struct entrypoint *ep, struct statement *stmt)
1917 {
1918 struct expression *expr = stmt->expression;
1919 struct basic_block *bb_return = get_bound_block(ep, stmt->ret_target);
1920 struct basic_block *active;
1921 pseudo_t src = linearize_expression(ep, expr);
1922 active = ep->active;
1923 if (active && src != VOID) {
1924 struct instruction *phi_node = first_instruction(bb_return->insns);
1925 pseudo_t phi;
1926 if (!phi_node) {
1927 phi_node = alloc_typed_instruction(OP_PHI, expr->ctype);
1928 phi_node->target = alloc_pseudo(phi_node);
1929 phi_node->bb = bb_return;
1930 add_instruction(&bb_return->insns, phi_node);
1931 }
1932 phi = alloc_phi(active, src, type_size(expr->ctype));
1933 phi->ident = &return_ident;
1934 use_pseudo(phi_node, phi, add_pseudo(&phi_node->phi_list, phi));
1935 }
1936 add_goto(ep, bb_return);
1937 return VOID;
1938 }
1939
1940 static pseudo_t linearize_switch(struct entrypoint *ep, struct statement *stmt)
1941 {
1942 struct symbol *sym;
1943 struct instruction *switch_ins;
1944 struct basic_block *switch_end = alloc_basic_block(ep, stmt->pos);
1945 struct basic_block *active, *default_case;
1946 struct multijmp *jmp;
1947 pseudo_t pseudo;
1948
1949 pseudo = linearize_expression(ep, stmt->switch_expression);
1950
1951 active = ep->active;
1952 if (!bb_reachable(active))
1953 return VOID;
1954
1955 switch_ins = alloc_instruction(OP_SWITCH, 0);
1956 use_pseudo(switch_ins, pseudo, &switch_ins->cond);
1957 add_one_insn(ep, switch_ins);
1958 finish_block(ep);
1959
1960 default_case = NULL;
1961 FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) {
1962 struct statement *case_stmt = sym->stmt;
1963 struct basic_block *bb_case = get_bound_block(ep, sym);
1964
1965 if (!case_stmt->case_expression) {
1966 default_case = bb_case;
1967 continue;
1968 } else {
1969 int begin, end;
1970
1971 begin = end = case_stmt->case_expression->value;
1972 if (case_stmt->case_to)
1973 end = case_stmt->case_to->value;
1974 if (begin > end)
1975 jmp = alloc_multijmp(bb_case, end, begin);
1976 else
1977 jmp = alloc_multijmp(bb_case, begin, end);
1978
1979 }
1980 add_multijmp(&switch_ins->multijmp_list, jmp);
1981 add_bb(&bb_case->parents, active);
1982 add_bb(&active->children, bb_case);
1983 } END_FOR_EACH_PTR(sym);
1984
1985 bind_label(stmt->switch_break, switch_end, stmt->pos);
1986
1987 /* And linearize the actual statement */
1988 linearize_statement(ep, stmt->switch_statement);
1989 set_activeblock(ep, switch_end);
1990
1991 if (!default_case)
1992 default_case = switch_end;
1993
2030 linearize_cond_branch(ep, pre_condition, loop_body, loop_end);
2031
2032 bind_label(stmt->iterator_continue, loop_continue, stmt->pos);
2033 bind_label(stmt->iterator_break, loop_end, stmt->pos);
2034
2035 set_activeblock(ep, loop_body);
2036 linearize_statement(ep, statement);
2037 add_goto(ep, loop_continue);
2038
2039 set_activeblock(ep, loop_continue);
2040 linearize_statement(ep, post_statement);
2041 if (!post_condition)
2042 add_goto(ep, loop_top);
2043 else
2044 linearize_cond_branch(ep, post_condition, loop_top, loop_end);
2045 set_activeblock(ep, loop_end);
2046
2047 return VOID;
2048 }
2049
2050 pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
2051 {
2052 struct basic_block *bb;
2053
2054 if (!stmt)
2055 return VOID;
2056
2057 bb = ep->active;
2058 if (bb && !bb->insns)
2059 bb->pos = stmt->pos;
2060 current_pos = stmt->pos;
2061
2062 switch (stmt->type) {
2063 case STMT_NONE:
2064 break;
2065
2066 case STMT_DECLARATION:
2067 return linearize_declaration(ep, stmt);
2068
2069 case STMT_CONTEXT:
2070 return linearize_context(ep, stmt);
2107 if (!bb_reachable(active))
2108 break;
2109
2110 if (stmt->goto_label) {
2111 add_goto(ep, get_bound_block(ep, stmt->goto_label));
2112 break;
2113 }
2114
2115 expr = stmt->goto_expression;
2116 if (!expr)
2117 break;
2118
2119 /* This can happen as part of simplification */
2120 if (expr->type == EXPR_LABEL) {
2121 add_goto(ep, get_bound_block(ep, expr->label_symbol));
2122 break;
2123 }
2124
2125 pseudo = linearize_expression(ep, expr);
2126 goto_ins = alloc_instruction(OP_COMPUTEDGOTO, 0);
2127 use_pseudo(goto_ins, pseudo, &goto_ins->target);
2128 add_one_insn(ep, goto_ins);
2129
2130 FOR_EACH_PTR(stmt->target_list, sym) {
2131 struct basic_block *bb_computed = get_bound_block(ep, sym);
2132 struct multijmp *jmp = alloc_multijmp(bb_computed, 1, 0);
2133 add_multijmp(&goto_ins->multijmp_list, jmp);
2134 add_bb(&bb_computed->parents, ep->active);
2135 add_bb(&active->children, bb_computed);
2136 } END_FOR_EACH_PTR(sym);
2137
2138 finish_block(ep);
2139 break;
2140 }
2141
2142 case STMT_COMPOUND:
2143 if (stmt->inline_fn)
2144 return linearize_inlined_call(ep, stmt);
2145 return linearize_compound_statement(ep, stmt);
2146
2147 /*
2167 linearize_statement(ep, stmt->if_false);
2168 }
2169 set_activeblock(ep, endif);
2170 break;
2171 }
2172
2173 case STMT_SWITCH:
2174 return linearize_switch(ep, stmt);
2175
2176 case STMT_ITERATOR:
2177 return linearize_iterator(ep, stmt);
2178
2179 default:
2180 break;
2181 }
2182 return VOID;
2183 }
2184
2185 static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_type)
2186 {
2187 struct entrypoint *ep;
2188 struct basic_block *bb;
2189 struct symbol *arg;
2190 struct instruction *entry;
2191 pseudo_t result;
2192 int i;
2193
2194 if (!base_type->stmt)
2195 return NULL;
2196
2197 ep = alloc_entrypoint();
2198 bb = alloc_basic_block(ep, sym->pos);
2199
2200 ep->name = sym;
2201 sym->ep = ep;
2202 set_activeblock(ep, bb);
2203
2204 entry = alloc_instruction(OP_ENTRY, 0);
2205 add_one_insn(ep, entry);
2206 ep->entry = entry;
2207
2208 concat_symbol_list(base_type->arguments, &ep->syms);
2209
2210 /* FIXME!! We should do something else about varargs.. */
2211 i = 0;
2212 FOR_EACH_PTR(base_type->arguments, arg) {
2213 linearize_argument(ep, arg, ++i);
2214 } END_FOR_EACH_PTR(arg);
2215
2216 result = linearize_statement(ep, base_type->stmt);
2217 if (bb_reachable(ep->active) && !bb_terminated(ep->active)) {
2218 struct symbol *ret_type = base_type->ctype.base_type;
2219 struct instruction *insn = alloc_typed_instruction(OP_RET, ret_type);
2220
2221 if (type_size(ret_type) > 0)
2222 use_pseudo(insn, result, &insn->src);
2223 add_one_insn(ep, insn);
2224 }
2225
2226 if (fdump_linearize) {
2227 if (fdump_linearize == 2)
2228 return ep;
2229 show_entry(ep);
2230 }
2231
2232 /*
2233 * Do trivial flow simplification - branches to
2234 * branches, kill dead basicblocks etc
2235 */
2236 kill_unreachable_bbs(ep);
2237
2238 /*
2239 * Turn symbols into pseudos
2240 */
2241 simplify_symbol_usage(ep);
2242
2243 repeat:
2244 /*
2245 * Remove trivial instructions, and try to CSE
2246 * the rest.
2247 */
2248 do {
2249 cleanup_and_cse(ep);
2250 pack_basic_blocks(ep);
2251 } while (repeat_phase & REPEAT_CSE);
2252
2253 kill_unreachable_bbs(ep);
2254 vrfy_flow(ep);
2255
2256 /* Cleanup */
2257 clear_symbol_pseudos(ep);
2258
2259 /* And track pseudo register usage */
2260 track_pseudo_liveness(ep);
2261
2262 /*
2263 * Some flow optimizations can only effectively
2264 * be done when we've done liveness analysis. But
2265 * if they trigger, we need to start all over
2266 * again
2267 */
2268 if (simplify_flow(ep)) {
2269 clear_liveness(ep);
2270 goto repeat;
2271 }
2272
2273 /* Finally, add deathnotes to pseudos now that we have them */
2274 if (dbg_dead)
2275 track_pseudo_death(ep);
2276
2277 return ep;
2278 }
2279
2280 struct entrypoint *linearize_symbol(struct symbol *sym)
2281 {
2282 struct symbol *base_type;
2283
2284 if (!sym)
2285 return NULL;
2286 current_pos = sym->pos;
2287 base_type = sym->ctype.base_type;
2288 if (!base_type)
2289 return NULL;
2290 if (base_type->type == SYM_FN)
2291 return linearize_fn(sym, base_type);
2292 return NULL;
2293 }
|
2 * Linearize - walk the statement tree (but _not_ the expressions)
3 * to generate a linear version of it and the basic blocks.
4 *
5 * NOTE! We're not interested in the actual sub-expressions yet,
6 * even though they can generate conditional branches and
7 * subroutine calls. That's all "local" behaviour.
8 *
9 * Copyright (C) 2004 Linus Torvalds
10 * Copyright (C) 2004 Christopher Li
11 */
12
13 #include <string.h>
14 #include <stdarg.h>
15 #include <stdlib.h>
16 #include <stdio.h>
17 #include <assert.h>
18
19 #include "parse.h"
20 #include "expression.h"
21 #include "linearize.h"
22 #include "optimize.h"
23 #include "flow.h"
24 #include "target.h"
25
26 static pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt);
27 static pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr);
28
29 static pseudo_t add_cast(struct entrypoint *ep, struct symbol *to, struct symbol *from, int op, pseudo_t src);
30 static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right);
31 static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val);
32 static pseudo_t linearize_one_symbol(struct entrypoint *ep, struct symbol *sym);
33
34 struct access_data;
35 static pseudo_t add_load(struct entrypoint *ep, struct access_data *);
36 static pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *);
37 static pseudo_t cast_pseudo(struct entrypoint *ep, pseudo_t src, struct symbol *from, struct symbol *to);
38
39 struct pseudo void_pseudo = {};
40
41 static struct position current_pos;
42
43 ALLOCATOR(pseudo_user, "pseudo_user");
44
45 static struct instruction *alloc_instruction(int opcode, int size)
46 {
47 struct instruction * insn = __alloc_instruction(0);
48 insn->opcode = opcode;
49 insn->size = size;
55 {
56 return type ? type->bit_size > 0 ? type->bit_size : 0 : 0;
57 }
58
59 static struct instruction *alloc_typed_instruction(int opcode, struct symbol *type)
60 {
61 struct instruction *insn = alloc_instruction(opcode, type_size(type));
62 insn->type = type;
63 return insn;
64 }
65
66 static struct entrypoint *alloc_entrypoint(void)
67 {
68 return __alloc_entrypoint(0);
69 }
70
71 static struct basic_block *alloc_basic_block(struct entrypoint *ep, struct position pos)
72 {
73 static int nr;
74 struct basic_block *bb = __alloc_basic_block(0);
75 bb->pos = pos;
76 bb->ep = ep;
77 bb->nr = nr++;
78 return bb;
79 }
80
81 static struct multijmp *alloc_multijmp(struct basic_block *target, long long begin, long long end)
82 {
83 struct multijmp *multijmp = __alloc_multijmp(0);
84 multijmp->target = target;
85 multijmp->begin = begin;
86 multijmp->end = end;
87 return multijmp;
88 }
89
90 const char *show_label(struct basic_block *bb)
91 {
92 static int n;
93 static char buffer[4][16];
94 char *buf = buffer[3 & ++n];
95
96 if (!bb)
97 return ".L???";
98 snprintf(buf, 64, ".L%u", bb->nr);
99 return buf;
100 }
101
102 const char *show_pseudo(pseudo_t pseudo)
103 {
104 static int n;
105 static char buffer[4][64];
106 char *buf;
107 int i;
108
109 if (!pseudo)
110 return "no pseudo";
111 if (pseudo == VOID)
112 return "VOID";
113 buf = buffer[3 & ++n];
114 switch(pseudo->type) {
115 case PSEUDO_SYM: {
116 struct symbol *sym = pseudo->sym;
117 struct expression *expr;
118
119 if (!sym) {
120 snprintf(buf, 64, "<bad symbol>");
121 break;
122 }
123 if (sym->bb_target) {
124 snprintf(buf, 64, "%s", show_label(sym->bb_target));
125 break;
126 }
127 if (sym->ident) {
128 snprintf(buf, 64, "%s", show_ident(sym->ident));
129 break;
130 }
131 expr = sym->initializer;
132 snprintf(buf, 64, "<anon symbol:%p>", verbose ? sym : NULL);
133 if (expr) {
134 switch (expr->type) {
135 case EXPR_VALUE:
136 snprintf(buf, 64, "<symbol value: %lld>", expr->value);
137 break;
138 case EXPR_STRING:
139 return show_string(expr->string);
140 default:
141 break;
142 }
143 }
144 break;
145 }
146 case PSEUDO_REG:
147 i = snprintf(buf, 64, "%%r%d", pseudo->nr);
148 if (pseudo->ident)
149 sprintf(buf+i, "(%s)", show_ident(pseudo->ident));
150 break;
151 case PSEUDO_VAL: {
152 long long value = pseudo->value;
153 if (value > 1000 || value < -1000)
154 snprintf(buf, 64, "$%#llx", value);
155 else
156 snprintf(buf, 64, "$%lld", value);
157 break;
158 }
159 case PSEUDO_ARG:
160 snprintf(buf, 64, "%%arg%d", pseudo->nr);
161 break;
162 case PSEUDO_PHI:
163 i = snprintf(buf, 64, "%%phi%d", pseudo->nr);
164 if (pseudo->ident)
165 sprintf(buf+i, "(%s)", show_ident(pseudo->ident));
166 break;
167 case PSEUDO_UNDEF:
168 return "UNDEF";
169 default:
170 snprintf(buf, 64, "<bad pseudo type %d>", pseudo->type);
171 }
172 return buf;
173 }
174
175 static const char *opcodes[] = {
176 [OP_BADOP] = "bad_op",
177
178 /* Fn entrypoint */
179 [OP_ENTRY] = "<entry-point>",
180
181 /* Terminator */
182 [OP_RET] = "ret",
183 [OP_BR] = "br",
184 [OP_CBR] = "cbr",
185 [OP_SWITCH] = "switch",
186 [OP_COMPUTEDGOTO] = "jmp *",
187
188 /* Binary */
189 [OP_ADD] = "add",
190 [OP_SUB] = "sub",
191 [OP_MUL] = "mul",
192 [OP_DIVU] = "divu",
193 [OP_DIVS] = "divs",
194 [OP_MODU] = "modu",
195 [OP_MODS] = "mods",
196 [OP_SHL] = "shl",
197 [OP_LSR] = "lsr",
198 [OP_ASR] = "asr",
199
200 /* Floating-point Binary */
201 [OP_FADD] = "fadd",
202 [OP_FSUB] = "fsub",
203 [OP_FMUL] = "fmul",
204 [OP_FDIV] = "fdiv",
205
206 /* Logical */
207 [OP_AND] = "and",
208 [OP_OR] = "or",
209 [OP_XOR] = "xor",
210
211 /* Binary comparison */
212 [OP_SET_EQ] = "seteq",
213 [OP_SET_NE] = "setne",
214 [OP_SET_LE] = "setle",
215 [OP_SET_GE] = "setge",
216 [OP_SET_LT] = "setlt",
217 [OP_SET_GT] = "setgt",
218 [OP_SET_B] = "setb",
219 [OP_SET_A] = "seta",
220 [OP_SET_BE] = "setbe",
221 [OP_SET_AE] = "setae",
222
223 /* floating-point comparison */
224 [OP_FCMP_ORD] = "fcmpord",
225 [OP_FCMP_OEQ] = "fcmpoeq",
226 [OP_FCMP_ONE] = "fcmpone",
227 [OP_FCMP_OLE] = "fcmpole",
228 [OP_FCMP_OGE] = "fcmpoge",
229 [OP_FCMP_OLT] = "fcmpolt",
230 [OP_FCMP_OGT] = "fcmpogt",
231 [OP_FCMP_UEQ] = "fcmpueq",
232 [OP_FCMP_UNE] = "fcmpune",
233 [OP_FCMP_ULE] = "fcmpule",
234 [OP_FCMP_UGE] = "fcmpuge",
235 [OP_FCMP_ULT] = "fcmpult",
236 [OP_FCMP_UGT] = "fcmpugt",
237 [OP_FCMP_UNO] = "fcmpuno",
238
239 /* Uni */
240 [OP_NOT] = "not",
241 [OP_NEG] = "neg",
242 [OP_FNEG] = "fneg",
243
244 /* Special three-input */
245 [OP_SEL] = "select",
246
247 /* Memory */
248 [OP_LOAD] = "load",
249 [OP_STORE] = "store",
250 [OP_SETVAL] = "set",
251 [OP_SETFVAL] = "setfval",
252 [OP_SYMADDR] = "symaddr",
253
254 /* Other */
255 [OP_PHI] = "phi",
256 [OP_PHISOURCE] = "phisrc",
257 [OP_SEXT] = "sext",
258 [OP_ZEXT] = "zext",
259 [OP_TRUNC] = "trunc",
260 [OP_FCVTU] = "fcvtu",
261 [OP_FCVTS] = "fcvts",
262 [OP_UCVTF] = "ucvtf",
263 [OP_SCVTF] = "scvtf",
264 [OP_FCVTF] = "fcvtf",
265 [OP_UTPTR] = "utptr",
266 [OP_PTRTU] = "ptrtu",
267 [OP_PTRCAST] = "ptrcast",
268 [OP_INLINED_CALL] = "# call",
269 [OP_CALL] = "call",
270 [OP_SLICE] = "slice",
271 [OP_NOP] = "nop",
272 [OP_DEATHNOTE] = "dead",
273 [OP_ASM] = "asm",
274
275 /* Sparse tagging (line numbers, context, whatever) */
276 [OP_CONTEXT] = "context",
277 [OP_RANGE] = "range-check",
278
279 [OP_COPY] = "copy",
280 };
281
282 static char *show_asm_constraints(char *buf, const char *sep, struct asm_constraint_list *list)
283 {
284 struct asm_constraint *entry;
285
286 FOR_EACH_PTR(list, entry) {
287 buf += sprintf(buf, "%s\"%s\"", sep, entry->constraint);
288 if (entry->pseudo)
289 buf += sprintf(buf, " (%s)", show_pseudo(entry->pseudo));
290 if (entry->ident)
319 const char *op = opcodes[opcode];
320 if (!op)
321 buf += sprintf(buf, "opcode:%d", opcode);
322 else
323 buf += sprintf(buf, "%s", op);
324 if (insn->size)
325 buf += sprintf(buf, ".%d", insn->size);
326 memset(buf, ' ', 20);
327 buf++;
328 }
329
330 if (buf < buffer + 12)
331 buf = buffer + 12;
332 switch (opcode) {
333 case OP_RET:
334 if (insn->src && insn->src != VOID)
335 buf += sprintf(buf, "%s", show_pseudo(insn->src));
336 break;
337
338 case OP_CBR:
339 buf += sprintf(buf, "%s, %s, %s", show_pseudo(insn->cond), show_label(insn->bb_true), show_label(insn->bb_false));
340 break;
341
342 case OP_BR:
343 buf += sprintf(buf, "%s", show_label(insn->bb_true));
344 break;
345
346 case OP_SETVAL: {
347 struct expression *expr = insn->val;
348 buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
349
350 if (!expr) {
351 buf += sprintf(buf, "%s", "<none>");
352 break;
353 }
354
355 switch (expr->type) {
356 case EXPR_VALUE:
357 buf += sprintf(buf, "%lld", expr->value);
358 break;
359 case EXPR_FVALUE:
360 buf += sprintf(buf, "%Le", expr->fvalue);
361 break;
362 case EXPR_STRING:
363 buf += sprintf(buf, "%.40s", show_string(expr->string));
364 break;
365 case EXPR_SYMBOL:
366 buf += sprintf(buf, "%s", show_ident(expr->symbol->ident));
367 break;
368 case EXPR_LABEL:
369 buf += sprintf(buf, "%s", show_label(expr->symbol->bb_target));
370 break;
371 default:
372 buf += sprintf(buf, "SETVAL EXPR TYPE %d", expr->type);
373 }
374 break;
375 }
376 case OP_SETFVAL:
377 buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
378 buf += sprintf(buf, "%Le", insn->fvalue);
379 break;
380
381 case OP_SWITCH: {
382 struct multijmp *jmp;
383 buf += sprintf(buf, "%s", show_pseudo(insn->cond));
384 FOR_EACH_PTR(insn->multijmp_list, jmp) {
385 if (jmp->begin == jmp->end)
386 buf += sprintf(buf, ", %lld -> %s", jmp->begin, show_label(jmp->target));
387 else if (jmp->begin < jmp->end)
388 buf += sprintf(buf, ", %lld ... %lld -> %s", jmp->begin, jmp->end, show_label(jmp->target));
389 else
390 buf += sprintf(buf, ", default -> %s", show_label(jmp->target));
391 } END_FOR_EACH_PTR(jmp);
392 break;
393 }
394 case OP_COMPUTEDGOTO: {
395 struct multijmp *jmp;
396 buf += sprintf(buf, "%s", show_pseudo(insn->src));
397 FOR_EACH_PTR(insn->multijmp_list, jmp) {
398 buf += sprintf(buf, ", %s", show_label(jmp->target));
399 } END_FOR_EACH_PTR(jmp);
400 break;
401 }
402
403 case OP_PHISOURCE: {
404 struct instruction *phi;
405 buf += sprintf(buf, "%s <- %s ", show_pseudo(insn->target), show_pseudo(insn->phi_src));
406 FOR_EACH_PTR(insn->phi_users, phi) {
407 buf += sprintf(buf, " (%s)", show_pseudo(phi->target));
408 } END_FOR_EACH_PTR(phi);
409 break;
410 }
411
412 case OP_PHI: {
413 pseudo_t phi;
414 const char *s = " <-";
415 buf += sprintf(buf, "%s", show_pseudo(insn->target));
416 FOR_EACH_PTR(insn->phi_list, phi) {
417 if (phi == VOID && !verbose)
418 continue;
419 buf += sprintf(buf, "%s %s", s, show_pseudo(phi));
420 s = ",";
421 } END_FOR_EACH_PTR(phi);
422 break;
423 }
424 case OP_LOAD:
425 buf += sprintf(buf, "%s <- %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
426 break;
427 case OP_STORE:
428 buf += sprintf(buf, "%s -> %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
429 break;
430 case OP_INLINED_CALL:
431 case OP_CALL: {
432 struct pseudo *arg;
433 if (insn->target && insn->target != VOID)
434 buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
435 buf += sprintf(buf, "%s", show_pseudo(insn->func));
436 FOR_EACH_PTR(insn->arguments, arg) {
437 buf += sprintf(buf, ", %s", show_pseudo(arg));
438 } END_FOR_EACH_PTR(arg);
439 break;
440 }
441 case OP_SEXT: case OP_ZEXT:
442 case OP_TRUNC:
443 case OP_FCVTU: case OP_FCVTS:
444 case OP_UCVTF: case OP_SCVTF:
445 case OP_FCVTF:
446 case OP_UTPTR:
447 case OP_PTRTU:
448 case OP_PTRCAST:
449 buf += sprintf(buf, "%s <- (%d) %s",
450 show_pseudo(insn->target),
451 type_size(insn->orig_type),
452 show_pseudo(insn->src));
453 break;
454 case OP_BINARY ... OP_BINARY_END:
455 case OP_FPCMP ... OP_FPCMP_END:
456 case OP_BINCMP ... OP_BINCMP_END:
457 buf += sprintf(buf, "%s <- %s, %s", show_pseudo(insn->target), show_pseudo(insn->src1), show_pseudo(insn->src2));
458 break;
459
460 case OP_SEL:
461 buf += sprintf(buf, "%s <- %s, %s, %s", show_pseudo(insn->target),
462 show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3));
463 break;
464
465 case OP_SLICE:
466 buf += sprintf(buf, "%s <- %s, %d, %d", show_pseudo(insn->target), show_pseudo(insn->base), insn->from, insn->len);
467 break;
468
469 case OP_NOT: case OP_NEG:
470 case OP_FNEG:
471 case OP_SYMADDR:
472 buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1));
473 break;
474
475 case OP_CONTEXT:
476 buf += sprintf(buf, "%s%d", insn->check ? "check: " : "", insn->increment);
477 break;
478 case OP_RANGE:
479 buf += sprintf(buf, "%s between %s..%s", show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3));
480 break;
481 case OP_NOP:
482 buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1));
483 break;
484 case OP_DEATHNOTE:
485 buf += sprintf(buf, "%s", show_pseudo(insn->target));
486 break;
487 case OP_ASM:
488 buf = show_asm(buf, insn);
489 break;
490 case OP_COPY:
491 buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src));
492 break;
493 default:
494 break;
495 }
496
497 if (buf >= buffer + sizeof(buffer))
498 die("instruction buffer overflowed %td\n", buf - buffer);
499 do { --buf; } while (*buf == ' ');
500 *++buf = 0;
501 return buffer;
502 }
503
504 void show_bb(struct basic_block *bb)
505 {
506 struct instruction *insn;
507
508 printf("%s:\n", show_label(bb));
509 if (verbose) {
510 pseudo_t needs, defines;
511 printf("%s:%d\n", stream_name(bb->pos.stream), bb->pos.line);
512
513 FOR_EACH_PTR(bb->needs, needs) {
514 struct instruction *def = needs->def;
515 if (def->opcode != OP_PHI) {
516 printf(" **uses %s (from %s)**\n", show_pseudo(needs), show_label(def->bb));
517 } else {
518 pseudo_t phi;
519 const char *sep = " ";
520 printf(" **uses %s (from", show_pseudo(needs));
521 FOR_EACH_PTR(def->phi_list, phi) {
522 if (phi == VOID)
523 continue;
524 printf("%s(%s:%s)", sep, show_pseudo(phi), show_label(phi->def->bb));
525 sep = ", ";
526 } END_FOR_EACH_PTR(phi);
527 printf(")**\n");
528 }
529 } END_FOR_EACH_PTR(needs);
530
531 FOR_EACH_PTR(bb->defines, defines) {
532 printf(" **defines %s **\n", show_pseudo(defines));
533 } END_FOR_EACH_PTR(defines);
534
535 if (bb->parents) {
536 struct basic_block *from;
537 FOR_EACH_PTR(bb->parents, from) {
538 printf(" **from %s (%s:%d:%d)**\n", show_label(from),
539 stream_name(from->pos.stream), from->pos.line, from->pos.pos);
540 } END_FOR_EACH_PTR(from);
541 }
542
543 if (bb->children) {
544 struct basic_block *to;
545 FOR_EACH_PTR(bb->children, to) {
546 printf(" **to %s (%s:%d:%d)**\n", show_label(to),
547 stream_name(to->pos.stream), to->pos.line, to->pos.pos);
548 } END_FOR_EACH_PTR(to);
549 }
550 }
551
552 FOR_EACH_PTR(bb->insns, insn) {
553 if (!insn->bb && verbose < 2)
554 continue;
555 printf("\t%s\n", show_instruction(insn));
556 } END_FOR_EACH_PTR(insn);
557 if (!bb_terminated(bb))
558 printf("\tEND\n");
559 }
560
561 static void show_symbol_usage(pseudo_t pseudo)
562 {
563 struct pseudo_user *pu;
564
565 if (pseudo) {
566 FOR_EACH_PTR(pseudo->users, pu) {
690 FOR_EACH_PTR(bb->children, child) {
691 if (child == target) {
692 target = NULL; /* Trigger just once */
693 continue;
694 }
695 DELETE_CURRENT_PTR(child);
696 remove_parent(child, bb);
697 } END_FOR_EACH_PTR(child);
698 PACK_PTR_LIST(&bb->children);
699 }
700
701
702 void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi_node, pseudo_t if_true, pseudo_t if_false)
703 {
704 pseudo_t target;
705 struct instruction *select;
706
707 /* Remove the 'br' */
708 delete_last_instruction(&bb->insns);
709
710 select = alloc_typed_instruction(OP_SEL, phi_node->type);
711 select->bb = bb;
712
713 assert(br->cond);
714 use_pseudo(select, br->cond, &select->src1);
715
716 target = phi_node->target;
717 assert(target->def == phi_node);
718 select->target = target;
719 target->def = select;
720
721 use_pseudo(select, if_true, &select->src2);
722 use_pseudo(select, if_false, &select->src3);
723
724 add_instruction(&bb->insns, select);
725 add_instruction(&bb->insns, br);
726 }
727
728 static inline int bb_empty(struct basic_block *bb)
729 {
730 return !bb->insns;
731 }
732
733 /* Add a label to the currently active block, return new active block */
734 static struct basic_block * add_label(struct entrypoint *ep, struct symbol *label)
735 {
736 struct basic_block *bb = label->bb_target;
737
738 if (bb) {
739 set_activeblock(ep, bb);
740 return bb;
741 }
742 bb = ep->active;
743 if (!bb_reachable(bb) || !bb_empty(bb)) {
744 bb = alloc_basic_block(ep, label->pos);
745 set_activeblock(ep, bb);
746 }
747 label->bb_target = bb;
748 return bb;
749 }
750
751 static void add_branch(struct entrypoint *ep, pseudo_t cond, struct basic_block *bb_true, struct basic_block *bb_false)
752 {
753 struct basic_block *bb = ep->active;
754 struct instruction *br;
755
756 if (bb_reachable(bb)) {
757 br = alloc_instruction(OP_CBR, 0);
758 use_pseudo(br, cond, &br->cond);
759 br->bb_true = bb_true;
760 br->bb_false = bb_false;
761 add_bb(&bb_true->parents, bb);
762 add_bb(&bb_false->parents, bb);
763 add_bb(&bb->children, bb_true);
764 add_bb(&bb->children, bb_false);
765 add_one_insn(ep, br);
766 }
767 }
768
769 pseudo_t alloc_pseudo(struct instruction *def)
770 {
771 static int nr = 0;
772 struct pseudo * pseudo = __alloc_pseudo(0);
773 pseudo->type = PSEUDO_REG;
774 pseudo->nr = ++nr;
775 pseudo->def = def;
776 return pseudo;
777 }
778
779 static pseudo_t symbol_pseudo(struct entrypoint *ep, struct symbol *sym)
780 {
781 pseudo_t pseudo;
782
783 if (!sym)
784 return VOID;
785
786 pseudo = sym->pseudo;
787 if (!pseudo) {
788 pseudo = __alloc_pseudo(0);
789 pseudo->nr = -1;
790 pseudo->type = PSEUDO_SYM;
791 pseudo->sym = sym;
792 pseudo->ident = sym->ident;
793 sym->pseudo = pseudo;
794 add_pseudo(&ep->accesses, pseudo);
795 }
796 /* Symbol pseudos have neither nr nor def */
797 return pseudo;
798 }
799
800 pseudo_t value_pseudo(long long val)
801 {
802 #define MAX_VAL_HASH 64
803 static struct pseudo_list *prev[MAX_VAL_HASH];
804 int hash = val & (MAX_VAL_HASH-1);
805 struct pseudo_list **list = prev + hash;
806 pseudo_t pseudo;
807
808 FOR_EACH_PTR(*list, pseudo) {
809 if (pseudo->value == val)
810 return pseudo;
811 } END_FOR_EACH_PTR(pseudo);
812
813 pseudo = __alloc_pseudo(0);
814 pseudo->type = PSEUDO_VAL;
815 pseudo->value = val;
816 add_pseudo(list, pseudo);
817
818 /* Value pseudos have neither nr, usage nor def */
819 return pseudo;
820 }
821
822 pseudo_t undef_pseudo(void)
823 {
824 pseudo_t pseudo = __alloc_pseudo(0);
825 pseudo->type = PSEUDO_UNDEF;
826 return pseudo;
827 }
828
829 static pseudo_t argument_pseudo(struct entrypoint *ep, int nr)
830 {
831 pseudo_t pseudo = __alloc_pseudo(0);
832 struct instruction *entry = ep->entry;
833
834 pseudo->type = PSEUDO_ARG;
835 pseudo->nr = nr;
836 pseudo->def = entry;
837 add_pseudo(&entry->arg_list, pseudo);
838
839 /* Argument pseudos have neither usage nor def */
840 return pseudo;
841 }
842
843 struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type)
844 {
845 struct instruction *insn = alloc_typed_instruction(OP_PHISOURCE, type);
846 pseudo_t phi = __alloc_pseudo(0);
847 static int nr = 0;
848
849 phi->type = PSEUDO_PHI;
850 phi->nr = ++nr;
851 phi->def = insn;
852
853 use_pseudo(insn, pseudo, &insn->phi_src);
854 insn->target = phi;
855 return insn;
856 }
857
858 pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, struct symbol *type)
859 {
860 struct instruction *insn;
861
862 if (!source)
863 return VOID;
864
865 insn = alloc_phisrc(pseudo, type);
866 insn->bb = source;
867 add_instruction(&source->insns, insn);
868 return insn->target;
869 }
870
871 struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident)
872 {
873 struct instruction *phi_node = alloc_typed_instruction(OP_PHI, type);
874 pseudo_t phi;
875
876 phi = alloc_pseudo(phi_node);
877 phi->ident = ident;
878 phi->def = phi_node;
879 phi_node->target = phi;
880 phi_node->bb = bb;
881 return phi_node;
882 }
883
884 void add_phi_node(struct basic_block *bb, struct instruction *phi_node)
885 {
886 struct instruction *insn;
887
888 FOR_EACH_PTR(bb->insns, insn) {
889 enum opcode op = insn->opcode;
890 if (op == OP_PHI)
891 continue;
892 INSERT_CURRENT(phi_node, insn);
893 return;
894 } END_FOR_EACH_PTR(insn);
895
896 // FIXME
897 add_instruction(&bb->insns, phi_node);
898 }
899
900 struct instruction *insert_phi_node(struct basic_block *bb, struct symbol *var)
901 {
902 struct instruction *phi_node = alloc_phi_node(bb, var, var->ident);
903 add_phi_node(bb, phi_node);
904 return phi_node;
905 }
906
907 /*
908 * We carry the "access_data" structure around for any accesses,
909 * which simplifies things a lot. It contains all the access
910 * information in one place.
911 */
912 struct access_data {
913 struct symbol *type; // ctype
914 struct symbol *btype; // base type of bitfields
915 pseudo_t address; // pseudo containing address ..
916 unsigned int offset; // byte offset
917 };
918
919 static int linearize_simple_address(struct entrypoint *ep,
920 struct expression *addr,
921 struct access_data *ad)
922 {
923 if (addr->type == EXPR_SYMBOL) {
924 linearize_one_symbol(ep, addr->symbol);
925 ad->address = symbol_pseudo(ep, addr->symbol);
926 return 1;
927 }
928 if (addr->type == EXPR_BINOP) {
929 if (addr->right->type == EXPR_VALUE) {
930 if (addr->op == '+') {
931 ad->offset += get_expression_value(addr->right);
932 return linearize_simple_address(ep, addr->left, ad);
933 }
934 }
935 }
936 ad->address = linearize_expression(ep, addr);
937 return 1;
938 }
939
940 static struct symbol *bitfield_base_type(struct symbol *sym)
941 {
942 struct symbol *base = sym;
943
944 if (sym) {
945 if (sym->type == SYM_NODE)
946 base = base->ctype.base_type;
947 if (base->type == SYM_BITFIELD)
948 return base->ctype.base_type;
949 }
950 return sym;
951 }
952
953 static int linearize_address_gen(struct entrypoint *ep,
954 struct expression *expr,
955 struct access_data *ad)
956 {
957 struct symbol *ctype = expr->ctype;
958
959 if (!ctype)
960 return 0;
961 ad->type = ctype;
962 if (expr->type == EXPR_PREOP && expr->op == '*')
963 return linearize_simple_address(ep, expr->unop, ad);
964
965 warning(expr->pos, "generating address of non-lvalue (%d)", expr->type);
966 return 0;
967 }
968
969 static pseudo_t add_load(struct entrypoint *ep, struct access_data *ad)
970 {
971 struct instruction *insn;
972 pseudo_t new;
973
974 if (!ep->active)
975 return VOID;
976
977 insn = alloc_typed_instruction(OP_LOAD, ad->btype);
978 new = alloc_pseudo(insn);
979
980 insn->target = new;
981 insn->offset = ad->offset;
982 insn->is_volatile = ad->type && (ad->type->ctype.modifiers & MOD_VOLATILE);
983 use_pseudo(insn, ad->address, &insn->src);
984 add_one_insn(ep, insn);
985 return new;
986 }
987
988 static void add_store(struct entrypoint *ep, struct access_data *ad, pseudo_t value)
989 {
990 struct basic_block *bb = ep->active;
991 struct instruction *store;
992
993 if (!bb)
994 return;
995
996 store = alloc_typed_instruction(OP_STORE, ad->btype);
997 store->offset = ad->offset;
998 store->is_volatile = ad->type && (ad->type->ctype.modifiers & MOD_VOLATILE);
999 use_pseudo(store, value, &store->target);
1000 use_pseudo(store, ad->address, &store->src);
1001 add_one_insn(ep, store);
1002 }
1003
1004 static pseudo_t linearize_bitfield_insert(struct entrypoint *ep,
1005 pseudo_t ori, pseudo_t val, struct symbol *ctype, struct symbol *btype)
1006 {
1007 unsigned int shift = ctype->bit_offset;
1008 unsigned int size = ctype->bit_size;
1009 unsigned long long mask = ((1ULL << size) - 1);
1010 unsigned long long smask= bits_mask(btype->bit_size);
1011
1012 val = add_cast(ep, btype, ctype, OP_ZEXT, val);
1013 if (shift) {
1014 val = add_binary_op(ep, btype, OP_SHL, val, value_pseudo(shift));
1015 mask <<= shift;
1016 }
1017 ori = add_binary_op(ep, btype, OP_AND, ori, value_pseudo(~mask & smask));
1018 val = add_binary_op(ep, btype, OP_OR, ori, val);
1019
1020 return val;
1021 }
1022
1023 static pseudo_t linearize_store_gen(struct entrypoint *ep,
1024 pseudo_t value,
1025 struct access_data *ad)
1026 {
1027 struct symbol *ctype = ad->type;
1028 struct symbol *btype;
1029 pseudo_t store = value;
1030
1031 if (!ep->active)
1032 return VOID;
1033
1034 btype = ad->btype = bitfield_base_type(ctype);
1035 if (type_size(btype) != type_size(ctype)) {
1036 pseudo_t orig = add_load(ep, ad);
1037 store = linearize_bitfield_insert(ep, orig, value, ctype, btype);
1038 }
1039 add_store(ep, ad, store);
1040 return value;
1041 }
1042
1043 static void taint_undefined_behaviour(struct instruction *insn)
1044 {
1045 pseudo_t src2;
1046
1047 switch (insn->opcode) {
1048 case OP_LSR:
1049 case OP_ASR:
1050 case OP_SHL:
1051 src2 = insn->src2;
1052 if (src2->type != PSEUDO_VAL)
1053 break;
1054 if ((unsigned long long)src2->value >= insn->size)
1055 insn->tainted = 1;
1056 break;
1057 }
1058 }
1059
1060 static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right)
1061 {
1062 struct instruction *insn = alloc_typed_instruction(op, ctype);
1063 pseudo_t target = alloc_pseudo(insn);
1064 insn->target = target;
1065 use_pseudo(insn, left, &insn->src1);
1066 use_pseudo(insn, right, &insn->src2);
1067 add_one_insn(ep, insn);
1068 return target;
1069 }
1070
1071 static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val)
1072 {
1073 struct instruction *insn = alloc_typed_instruction(OP_SETVAL, ctype);
1074 pseudo_t target = alloc_pseudo(insn);
1075 insn->target = target;
1076 insn->val = val;
1077 add_one_insn(ep, insn);
1078 return target;
1079 }
1080
1081 static pseudo_t add_setfval(struct entrypoint *ep, struct symbol *ctype, long double fval)
1082 {
1083 struct instruction *insn = alloc_typed_instruction(OP_SETFVAL, ctype);
1084 pseudo_t target = alloc_pseudo(insn);
1085 insn->target = target;
1086 insn->fvalue = fval;
1087 add_one_insn(ep, insn);
1088 return target;
1089 }
1090
1091 static pseudo_t add_symbol_address(struct entrypoint *ep, struct symbol *sym)
1092 {
1093 struct instruction *insn = alloc_instruction(OP_SYMADDR, bits_in_pointer);
1094 pseudo_t target = alloc_pseudo(insn);
1095
1096 insn->target = target;
1097 use_pseudo(insn, symbol_pseudo(ep, sym), &insn->src);
1098 add_one_insn(ep, insn);
1099 return target;
1100 }
1101
1102 static pseudo_t linearize_bitfield_extract(struct entrypoint *ep,
1103 pseudo_t val, struct symbol *ctype, struct symbol *btype)
1104 {
1105 unsigned int off = ctype->bit_offset;
1106
1107 if (off) {
1108 pseudo_t shift = value_pseudo(off);
1109 val = add_binary_op(ep, btype, OP_LSR, val, shift);
1110 }
1111 val = cast_pseudo(ep, val, btype, ctype);
1112 return val;
1113 }
1114
1115 static pseudo_t linearize_load_gen(struct entrypoint *ep, struct access_data *ad)
1116 {
1117 struct symbol *ctype = ad->type;
1118 struct symbol *btype;
1119 pseudo_t new;
1120
1121 if (!ep->active)
1122 return VOID;
1123
1124 btype = ad->btype = bitfield_base_type(ctype);
1125 new = add_load(ep, ad);
1126 if (ctype->bit_size != type_size(btype))
1127 new = linearize_bitfield_extract(ep, new, ctype, btype);
1128 return new;
1129 }
1130
1131 static pseudo_t linearize_access(struct entrypoint *ep, struct expression *expr)
1132 {
1133 struct access_data ad = { NULL, };
1134 pseudo_t value;
1135
1136 if (!linearize_address_gen(ep, expr, &ad))
1137 return VOID;
1138 value = linearize_load_gen(ep, &ad);
1139 return value;
1140 }
1141
1142 static pseudo_t linearize_inc_dec(struct entrypoint *ep, struct expression *expr, int postop)
1143 {
1144 struct access_data ad = { NULL, };
1145 pseudo_t old, new, one;
1146 int op = expr->op == SPECIAL_INCREMENT ? OP_ADD : OP_SUB;
1147
1148 if (!linearize_address_gen(ep, expr->unop, &ad))
1149 return VOID;
1150
1151 old = linearize_load_gen(ep, &ad);
1152 op = opcode_float(op, expr->ctype);
1153 if (is_float_type(expr->ctype))
1154 one = add_setfval(ep, expr->ctype, expr->op_value);
1155 else
1156 one = value_pseudo(expr->op_value);
1157 if (ad.btype != ad.type)
1158 old = cast_pseudo(ep, old, ad.type, ad.btype);
1159 new = add_binary_op(ep, ad.btype, op, old, one);
1160 if (ad.btype != ad.type)
1161 new = cast_pseudo(ep, new, ad.btype, ad.type);
1162 linearize_store_gen(ep, new, &ad);
1163 return postop ? old : new;
1164 }
1165
1166 static pseudo_t add_unop(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t src)
1167 {
1168 struct instruction *insn = alloc_typed_instruction(op, ctype);
1169 pseudo_t new = alloc_pseudo(insn);
1170
1171 insn->target = new;
1172 use_pseudo(insn, src, &insn->src1);
1173 add_one_insn(ep, insn);
1174 return new;
1175 }
1176
1177 static pseudo_t add_cast(struct entrypoint *ep, struct symbol *to,
1178 struct symbol *from, int op, pseudo_t src)
1179 {
1180 pseudo_t new = add_unop(ep, to, op, src);
1181 new->def->orig_type = from;
1182 return new;
1183 }
1184
1185 static pseudo_t linearize_slice(struct entrypoint *ep, struct expression *expr)
1186 {
1187 pseudo_t pre = linearize_expression(ep, expr->base);
1188 struct instruction *insn = alloc_typed_instruction(OP_SLICE, expr->ctype);
1189 pseudo_t new = alloc_pseudo(insn);
1190
1191 insn->target = new;
1192 insn->from = expr->r_bitpos;
1193 insn->len = expr->r_nrbits;
1194 use_pseudo(insn, pre, &insn->base);
1195 add_one_insn(ep, insn);
1196 return new;
1197 }
1198
1199 static pseudo_t linearize_regular_preop(struct entrypoint *ep, struct expression *expr)
1200 {
1201 pseudo_t pre = linearize_expression(ep, expr->unop);
1202 struct symbol *ctype = expr->ctype;
1203 switch (expr->op) {
1204 case '+':
1205 return pre;
1206 case '!': {
1207 pseudo_t zero = value_pseudo(0);
1208 return add_binary_op(ep, ctype, OP_SET_EQ, pre, zero);
1209 }
1210 case '~':
1211 return add_unop(ep, ctype, OP_NOT, pre);
1212 case '-':
1213 return add_unop(ep, ctype, opcode_float(OP_NEG, ctype), pre);
1214 }
1215 return VOID;
1216 }
1217
1218 static pseudo_t linearize_preop(struct entrypoint *ep, struct expression *expr)
1219 {
1220 /*
1221 * '*' is an lvalue access, and is fundamentally different
1222 * from an arithmetic operation. Maybe it should have an
1223 * expression type of its own..
1224 */
1225 if (expr->op == '*')
1226 return linearize_access(ep, expr);
1227 if (expr->op == SPECIAL_INCREMENT || expr->op == SPECIAL_DECREMENT)
1228 return linearize_inc_dec(ep, expr, 0);
1229 return linearize_regular_preop(ep, expr);
1230 }
1231
1232 static pseudo_t linearize_postop(struct entrypoint *ep, struct expression *expr)
1233 {
1234 return linearize_inc_dec(ep, expr, 1);
1235 }
1236
1237 /*
1238 * Casts to pointers are "less safe" than other casts, since
1239 * they imply type-unsafe accesses. "void *" is a special
1240 * case, since you can't access through it anyway without another
1241 * cast.
1242 */
1243 enum mtype {
1244 MTYPE_UINT,
1245 MTYPE_SINT,
1246 MTYPE_PTR,
1247 MTYPE_VPTR, // TODO: must be removed ?
1248 MTYPE_FLOAT,
1249 MTYPE_BAD,
1250 };
1251
1252 static enum mtype get_mtype(struct symbol *s)
1253 {
1254 int sign = (s->ctype.modifiers & MOD_SIGNED) ? 1 : 0;
1255
1256 retry: switch (s->type) {
1257 case SYM_NODE:
1258 s = s->ctype.base_type;
1259 goto retry;
1260 case SYM_PTR:
1261 if (s->ctype.base_type == &void_ctype)
1262 return MTYPE_VPTR;
1263 return MTYPE_PTR;
1264 case SYM_BITFIELD:
1265 case SYM_RESTRICT:
1266 case SYM_FOULED:
1267 case SYM_ENUM:
1268 s = s->ctype.base_type;
1269 /* fall-through */
1270 case_int:
1271 return sign ? MTYPE_SINT : MTYPE_UINT;
1272 case SYM_BASETYPE:
1273 if (s->ctype.base_type == &fp_type)
1274 return MTYPE_FLOAT;
1275 if (s->ctype.base_type == &int_type)
1276 goto case_int;
1277 /* fall-through */
1278 default:
1279 return MTYPE_BAD;
1280 }
1281 }
1282
1283 static int get_cast_opcode(struct symbol *dst, struct symbol *src)
1284 {
1285 enum mtype stype = get_mtype(src);
1286 enum mtype dtype = get_mtype(dst);
1287
1288 switch (dtype) {
1289 case MTYPE_FLOAT:
1290 switch (stype) {
1291 case MTYPE_FLOAT:
1292 if (dst->bit_size == src->bit_size)
1293 return OP_NOP;
1294 return OP_FCVTF;
1295 case MTYPE_UINT:
1296 return OP_UCVTF;
1297 case MTYPE_SINT:
1298 return OP_SCVTF;
1299 default:
1300 return OP_BADOP;
1301 }
1302 case MTYPE_PTR:
1303 switch (stype) {
1304 case MTYPE_UINT:
1305 case MTYPE_SINT:
1306 return OP_UTPTR;
1307 case MTYPE_PTR:
1308 case MTYPE_VPTR:
1309 return OP_PTRCAST;
1310 default:
1311 return OP_BADOP;
1312 }
1313 case MTYPE_VPTR:
1314 switch (stype) {
1315 case MTYPE_PTR:
1316 case MTYPE_VPTR:
1317 case MTYPE_UINT:
1318 stype = MTYPE_UINT;
1319 /* fall through */
1320 case MTYPE_SINT:
1321 break;
1322 default:
1323 return OP_BADOP;
1324 }
1325 /* fall through */
1326 case MTYPE_UINT:
1327 case MTYPE_SINT:
1328 switch (stype) {
1329 case MTYPE_FLOAT:
1330 return dtype == MTYPE_UINT ? OP_FCVTU : OP_FCVTS;
1331 case MTYPE_PTR:
1332 return OP_PTRTU;
1333 case MTYPE_VPTR:
1334 case MTYPE_UINT:
1335 case MTYPE_SINT:
1336 if (dst->bit_size ==src->bit_size)
1337 return OP_NOP;
1338 if (dst->bit_size < src->bit_size)
1339 return OP_TRUNC;
1340 return stype == MTYPE_SINT ? OP_SEXT : OP_ZEXT;
1341 default:
1342 return OP_BADOP;
1343 }
1344 /* fall through */
1345 default:
1346 if (src->type == SYM_NODE)
1347 src = src->ctype.base_type;
1348 if (dst->type == SYM_NODE)
1349 dst = dst->ctype.base_type;
1350 if (src == dst)
1351 return OP_NOP;
1352 return OP_BADOP;
1353 }
1354 }
1355
1356 static pseudo_t cast_pseudo(struct entrypoint *ep, pseudo_t src, struct symbol *from, struct symbol *to)
1357 {
1358 const struct position pos = current_pos;
1359 pseudo_t result;
1360 struct instruction *insn;
1361 int opcode;
1362
1363 if (src == VOID)
1364 return VOID;
1365 if (!from || !to)
1366 return VOID;
1367 if (from->bit_size < 0 || to->bit_size < 0)
1368 return VOID;
1369 opcode = get_cast_opcode(to, from);
1370 switch (opcode) {
1371 case OP_NOP:
1372 return src;
1373 case OP_UTPTR:
1374 if (from->bit_size == to->bit_size)
1375 break;
1376 if (src == value_pseudo(0))
1377 break;
1378 if (Wint_to_pointer_cast)
1379 warning(pos, "non size-preserving integer to pointer cast");
1380 src = cast_pseudo(ep, src, from, size_t_ctype);
1381 from = size_t_ctype;
1382 break;
1383 case OP_PTRTU:
1384 if (from->bit_size == to->bit_size)
1385 break;
1386 if (Wpointer_to_int_cast)
1387 warning(pos, "non size-preserving pointer to integer cast");
1388 src = cast_pseudo(ep, src, from, size_t_ctype);
1389 return cast_pseudo(ep, src, size_t_ctype, to);
1390 case OP_BADOP:
1391 return VOID;
1392 default:
1393 break;
1394 }
1395 insn = alloc_typed_instruction(opcode, to);
1396 result = alloc_pseudo(insn);
1397 insn->target = result;
1398 insn->orig_type = from;
1399 use_pseudo(insn, src, &insn->src);
1400 add_one_insn(ep, insn);
1401 return result;
1402 }
1403
1404 static int map_opcode(int opcode, struct symbol *ctype)
1405 {
1406 if (ctype && is_float_type(ctype))
1407 return opcode_table[opcode].to_float;
1408 if (ctype && (ctype->ctype.modifiers & MOD_SIGNED)) {
1409 switch(opcode) {
1410 case OP_DIVU: case OP_MODU: case OP_LSR:
1411 opcode++;
1412 }
1413 }
1414 return opcode;
1415 }
1416
1417 static inline pseudo_t add_convert_to_bool(struct entrypoint *ep, pseudo_t src, struct symbol *type)
1418 {
1419 pseudo_t zero;
1420 int op;
1421
1422 if (!type || src == VOID)
1423 return VOID;
1424 if (is_bool_type(type))
1425 return src;
1426 if (src->type == PSEUDO_VAL && (src->value == 0 || src->value == 1))
1427 return src;
1428 if (is_float_type(type)) {
1429 zero = add_setfval(ep, type, 0.0);
1430 op = map_opcode(OP_SET_NE, type);
1431 } else {
1432 zero = value_pseudo(0);
1433 op = OP_SET_NE;
1434 }
1435 return add_binary_op(ep, &bool_ctype, op, src, zero);
1436 }
1437
1438 static pseudo_t linearize_expression_to_bool(struct entrypoint *ep, struct expression *expr)
1439 {
1440 pseudo_t dst;
1441 dst = linearize_expression(ep, expr);
1442 dst = add_convert_to_bool(ep, dst, expr->ctype);
1443 return dst;
1444 }
1445
1446 static pseudo_t linearize_assignment(struct entrypoint *ep, struct expression *expr)
1447 {
1448 struct access_data ad = { NULL, };
1449 struct expression *target = expr->left;
1450 struct expression *src = expr->right;
1451 struct symbol *ctype;
1452 pseudo_t value;
1453
1454 value = linearize_expression(ep, src);
1455 if (!target || !linearize_address_gen(ep, target, &ad))
1456 return value;
1457 if (expr->op != '=') {
1458 pseudo_t oldvalue = linearize_load_gen(ep, &ad);
1459 pseudo_t dst;
1460 static const int op_trans[] = {
1461 [SPECIAL_ADD_ASSIGN - SPECIAL_BASE] = OP_ADD,
1462 [SPECIAL_SUB_ASSIGN - SPECIAL_BASE] = OP_SUB,
1463 [SPECIAL_MUL_ASSIGN - SPECIAL_BASE] = OP_MUL,
1464 [SPECIAL_DIV_ASSIGN - SPECIAL_BASE] = OP_DIVU,
1465 [SPECIAL_MOD_ASSIGN - SPECIAL_BASE] = OP_MODU,
1466 [SPECIAL_SHL_ASSIGN - SPECIAL_BASE] = OP_SHL,
1467 [SPECIAL_SHR_ASSIGN - SPECIAL_BASE] = OP_LSR,
1468 [SPECIAL_AND_ASSIGN - SPECIAL_BASE] = OP_AND,
1469 [SPECIAL_OR_ASSIGN - SPECIAL_BASE] = OP_OR,
1470 [SPECIAL_XOR_ASSIGN - SPECIAL_BASE] = OP_XOR
1471 };
1472 int opcode;
1473
1474 if (!src)
1475 return VOID;
1476
1477 ctype = src->ctype;
1478 oldvalue = cast_pseudo(ep, oldvalue, target->ctype, ctype);
1479 opcode = map_opcode(op_trans[expr->op - SPECIAL_BASE], ctype);
1480 dst = add_binary_op(ep, ctype, opcode, oldvalue, value);
1481 taint_undefined_behaviour(dst->def);
1482 value = cast_pseudo(ep, dst, ctype, expr->ctype);
1483 }
1484 value = linearize_store_gen(ep, value, &ad);
1485 return value;
1486 }
1487
1488 static pseudo_t linearize_call_expression(struct entrypoint *ep, struct expression *expr)
1489 {
1490 struct expression *arg, *fn;
1491 struct instruction *insn = alloc_typed_instruction(OP_CALL, expr->ctype);
1492 pseudo_t retval, call;
1493 struct ctype *ctype = NULL;
1494 struct symbol *fntype;
1495 struct context *context;
1496
1497 if (!expr->ctype)
1498 return VOID;
1499
1500 fn = expr->fn;
1501 fntype = fn->ctype;
1502 ctype = &fntype->ctype;
1503 if (fntype->type == SYM_NODE)
1504 fntype = fntype->ctype.base_type;
1505
1506 add_symbol(&insn->fntypes, fntype);
1507 FOR_EACH_PTR(expr->args, arg) {
1508 pseudo_t new = linearize_expression(ep, arg);
1509 use_pseudo(insn, new, add_pseudo(&insn->arguments, new));
1510 add_symbol(&insn->fntypes, arg->ctype);
1511 } END_FOR_EACH_PTR(arg);
1512
1513 if (fn->type == EXPR_PREOP && fn->op == '*' && is_func_type(fn->ctype))
1514 fn = fn->unop;
1515
1516 if (fn->type == EXPR_SYMBOL) {
1517 call = symbol_pseudo(ep, fn->symbol);
1518 } else {
1519 call = linearize_expression(ep, fn);
1520 }
1521 use_pseudo(insn, call, &insn->func);
1522 retval = VOID;
1523 if (expr->ctype != &void_ctype)
1524 retval = alloc_pseudo(insn);
1525 insn->target = retval;
1526 add_one_insn(ep, insn);
1527
1528 if (ctype) {
1529 FOR_EACH_PTR(ctype->contexts, context) {
1530 int in = context->in;
1531 int out = context->out;
1532 int check = 0;
1533 int context_diff;
1534 if (in < 0) {
1535 check = 1;
1539 check = 0;
1540 out = 0;
1541 }
1542 context_diff = out - in;
1543 if (check || context_diff) {
1544 insn = alloc_instruction(OP_CONTEXT, 0);
1545 insn->increment = context_diff;
1546 insn->check = check;
1547 insn->context_expr = context->context;
1548 add_one_insn(ep, insn);
1549 }
1550 } END_FOR_EACH_PTR(context);
1551 }
1552
1553 return retval;
1554 }
1555
1556 static pseudo_t linearize_binop_bool(struct entrypoint *ep, struct expression *expr)
1557 {
1558 pseudo_t src1, src2, dst;
1559 int op = (expr->op == SPECIAL_LOGICAL_OR) ? OP_OR : OP_AND;
1560
1561 src1 = linearize_expression_to_bool(ep, expr->left);
1562 src2 = linearize_expression_to_bool(ep, expr->right);
1563 dst = add_binary_op(ep, &bool_ctype, op, src1, src2);
1564 if (expr->ctype != &bool_ctype)
1565 dst = cast_pseudo(ep, dst, &bool_ctype, expr->ctype);
1566 return dst;
1567 }
1568
1569 static pseudo_t linearize_binop(struct entrypoint *ep, struct expression *expr)
1570 {
1571 pseudo_t src1, src2, dst;
1572 static const int opcode[] = {
1573 ['+'] = OP_ADD, ['-'] = OP_SUB,
1574 ['*'] = OP_MUL, ['/'] = OP_DIVU,
1575 ['%'] = OP_MODU, ['&'] = OP_AND,
1576 ['|'] = OP_OR, ['^'] = OP_XOR,
1577 [SPECIAL_LEFTSHIFT] = OP_SHL,
1578 [SPECIAL_RIGHTSHIFT] = OP_LSR,
1579 };
1580 int op;
1581
1582 src1 = linearize_expression(ep, expr->left);
1583 src2 = linearize_expression(ep, expr->right);
1584 op = map_opcode(opcode[expr->op], expr->ctype);
1585 dst = add_binary_op(ep, expr->ctype, op, src1, src2);
1586 taint_undefined_behaviour(dst->def);
1587 return dst;
1588 }
1589
1590 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
1591
1592 static pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
1593
1594 static pseudo_t linearize_select(struct entrypoint *ep, struct expression *expr)
1595 {
1596 pseudo_t cond, valt, valf, res;
1597 struct instruction *insn;
1598
1599 valt = linearize_expression(ep, expr->cond_true);
1600 valf = linearize_expression(ep, expr->cond_false);
1601 cond = linearize_expression(ep, expr->conditional);
1602
1603 insn = alloc_typed_instruction(OP_SEL, expr->ctype);
1604 if (!expr->cond_true)
1605 valt = cond;
1606 use_pseudo(insn, cond, &insn->src1);
1607 use_pseudo(insn, valt, &insn->src2);
1608 use_pseudo(insn, valf, &insn->src3);
1609
1610 res = alloc_pseudo(insn);
1611 insn->target = res;
1612 add_one_insn(ep, insn);
1613 return res;
1614 }
1615
1616 static pseudo_t add_join_conditional(struct entrypoint *ep, struct expression *expr,
1617 pseudo_t phi1, pseudo_t phi2)
1618 {
1619 pseudo_t target;
1620 struct instruction *phi_node;
1621
1622 if (phi1 == VOID)
1623 return phi2;
1624 if (phi2 == VOID)
1625 return phi1;
1626
1627 phi_node = alloc_typed_instruction(OP_PHI, expr->ctype);
1628 use_pseudo(phi_node, phi1, add_pseudo(&phi_node->phi_list, phi1));
1629 use_pseudo(phi_node, phi2, add_pseudo(&phi_node->phi_list, phi2));
1630 phi_node->target = target = alloc_pseudo(phi_node);
1631 add_one_insn(ep, phi_node);
1632 return target;
1633 }
1634
1635 static pseudo_t linearize_short_conditional(struct entrypoint *ep, struct expression *expr,
1636 struct expression *cond,
1637 struct expression *expr_false)
1638 {
1639 pseudo_t src1, src2;
1640 struct basic_block *bb_false;
1641 struct basic_block *merge;
1642 pseudo_t phi1, phi2;
1643
1644 if (!expr_false || !ep->active)
1645 return VOID;
1646
1647 bb_false = alloc_basic_block(ep, expr_false->pos);
1648 merge = alloc_basic_block(ep, expr->pos);
1649
1650 src1 = linearize_expression(ep, cond);
1651 phi1 = alloc_phi(ep->active, src1, expr->ctype);
1652 add_branch(ep, src1, merge, bb_false);
1653
1654 set_activeblock(ep, bb_false);
1655 src2 = linearize_expression(ep, expr_false);
1656 phi2 = alloc_phi(ep->active, src2, expr->ctype);
1657 set_activeblock(ep, merge);
1658
1659 return add_join_conditional(ep, expr, phi1, phi2);
1660 }
1661
1662 static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *expr,
1663 struct expression *cond,
1664 struct expression *expr_true,
1665 struct expression *expr_false)
1666 {
1667 pseudo_t src1, src2;
1668 pseudo_t phi1, phi2;
1669 struct basic_block *bb_true, *bb_false, *merge;
1670
1671 if (!cond || !expr_true || !expr_false || !ep->active)
1672 return VOID;
1673 bb_true = alloc_basic_block(ep, expr_true->pos);
1674 bb_false = alloc_basic_block(ep, expr_false->pos);
1675 merge = alloc_basic_block(ep, expr->pos);
1676
1677 linearize_cond_branch(ep, cond, bb_true, bb_false);
1678
1679 set_activeblock(ep, bb_true);
1680 src1 = linearize_expression(ep, expr_true);
1681 phi1 = alloc_phi(ep->active, src1, expr->ctype);
1682 add_goto(ep, merge);
1683
1684 set_activeblock(ep, bb_false);
1685 src2 = linearize_expression(ep, expr_false);
1686 phi2 = alloc_phi(ep->active, src2, expr->ctype);
1687 set_activeblock(ep, merge);
1688
1689 return add_join_conditional(ep, expr, phi1, phi2);
1690 }
1691
1692 static void insert_phis(struct basic_block *bb, pseudo_t src, struct symbol *ctype,
1693 struct instruction *node)
1694 {
1695 struct basic_block *parent;
1696
1697 FOR_EACH_PTR(bb->parents, parent) {
1698 struct instruction *br = delete_last_instruction(&parent->insns);
1699 pseudo_t phi = alloc_phi(parent, src, ctype);
1700 add_instruction(&parent->insns, br);
1701 use_pseudo(node, phi, add_pseudo(&node->phi_list, phi));
1702 } END_FOR_EACH_PTR(parent);
1703 }
1704
1705 static pseudo_t linearize_logical(struct entrypoint *ep, struct expression *expr)
1706 {
1707 struct symbol *ctype = expr->ctype;
1708 struct basic_block *other, *merge;
1709 struct instruction *node;
1710 pseudo_t src1, src2, phi2;
1711
1712 if (!ep->active || !expr->left || !expr->right)
1713 return VOID;
1714
1715 other = alloc_basic_block(ep, expr->right->pos);
1716 merge = alloc_basic_block(ep, expr->pos);
1717 node = alloc_phi_node(merge, ctype, NULL);
1718
1719 // LHS and its shortcut
1720 if (expr->op == SPECIAL_LOGICAL_OR) {
1721 linearize_cond_branch(ep, expr->left, merge, other);
1722 src1 = value_pseudo(1);
1723 } else {
1724 linearize_cond_branch(ep, expr->left, other, merge);
1725 src1 = value_pseudo(0);
1726 }
1727 insert_phis(merge, src1, ctype, node);
1728
1729 // RHS
1730 set_activeblock(ep, other);
1731 src2 = linearize_expression_to_bool(ep, expr->right);
1732 src2 = cast_pseudo(ep, src2, &bool_ctype, ctype);
1733 phi2 = alloc_phi(ep->active, src2, ctype);
1734 use_pseudo(node, phi2, add_pseudo(&node->phi_list, phi2));
1735
1736 // join
1737 set_activeblock(ep, merge);
1738 add_instruction(&merge->insns, node);
1739 return node->target;
1740 }
1741
1742 static pseudo_t linearize_compare(struct entrypoint *ep, struct expression *expr)
1743 {
1744 static const int cmpop[] = {
1745 ['>'] = OP_SET_GT, ['<'] = OP_SET_LT,
1746 [SPECIAL_EQUAL] = OP_SET_EQ,
1747 [SPECIAL_NOTEQUAL] = OP_SET_NE,
1748 [SPECIAL_GTE] = OP_SET_GE,
1749 [SPECIAL_LTE] = OP_SET_LE,
1750 [SPECIAL_UNSIGNED_LT] = OP_SET_B,
1751 [SPECIAL_UNSIGNED_GT] = OP_SET_A,
1752 [SPECIAL_UNSIGNED_LTE] = OP_SET_BE,
1753 [SPECIAL_UNSIGNED_GTE] = OP_SET_AE,
1754 };
1755 int op = opcode_float(cmpop[expr->op], expr->right->ctype);
1756 pseudo_t src1 = linearize_expression(ep, expr->left);
1757 pseudo_t src2 = linearize_expression(ep, expr->right);
1758 pseudo_t dst = add_binary_op(ep, expr->ctype, op, src1, src2);
1759 return dst;
1760 }
1761
1762
1763 static pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
1764 {
1765 pseudo_t cond;
1766
1767 if (!expr || !bb_reachable(ep->active))
1768 return VOID;
1769
1770 switch (expr->type) {
1771
1772 case EXPR_STRING:
1773 case EXPR_VALUE:
1774 add_goto(ep, expr->value ? bb_true : bb_false);
1775 return VOID;
1776
1777 case EXPR_FVALUE:
1778 add_goto(ep, expr->fvalue ? bb_true : bb_false);
1779 return VOID;
1780
1781 case EXPR_LOGICAL:
1782 linearize_logical_branch(ep, expr, bb_true, bb_false);
1783 return VOID;
1784
1785 case EXPR_COMPARE:
1786 cond = linearize_compare(ep, expr);
1787 add_branch(ep, cond, bb_true, bb_false);
1788 break;
1789
1790 case EXPR_PREOP:
1791 if (expr->op == '!')
1792 return linearize_cond_branch(ep, expr->unop, bb_false, bb_true);
1793 /* fall through */
1794 default: {
1795 cond = linearize_expression_to_bool(ep, expr);
1796 add_branch(ep, cond, bb_true, bb_false);
1797
1798 return VOID;
1799 }
1800 }
1801 return VOID;
1802 }
1803
1804
1805
1806 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
1807 {
1808 struct basic_block *next = alloc_basic_block(ep, expr->pos);
1809
1810 if (expr->op == SPECIAL_LOGICAL_OR)
1811 linearize_cond_branch(ep, expr->left, bb_true, next);
1812 else
1813 linearize_cond_branch(ep, expr->left, next, bb_false);
1814 set_activeblock(ep, next);
1815 linearize_cond_branch(ep, expr->right, bb_true, bb_false);
1816 return VOID;
1817 }
1818
1819 static pseudo_t linearize_cast(struct entrypoint *ep, struct expression *expr)
1820 {
1821 pseudo_t src;
1822 struct expression *orig = expr->cast_expression;
1823
1824 if (!orig)
1825 return VOID;
1826
1827 src = linearize_expression(ep, orig);
1828 return cast_pseudo(ep, src, orig->ctype, expr->ctype);
1829 }
1830
1831 static pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *ad)
1832 {
1833 switch (initializer->type) {
1834 case EXPR_INITIALIZER: {
1835 struct expression *expr;
1836 FOR_EACH_PTR(initializer->expr_list, expr) {
1837 linearize_initializer(ep, expr, ad);
1838 } END_FOR_EACH_PTR(expr);
1839 break;
1840 }
1841 case EXPR_POS:
1842 ad->offset = initializer->init_offset;
1843 linearize_initializer(ep, initializer->init_expr, ad);
1844 break;
1845 default: {
1846 pseudo_t value = linearize_expression(ep, initializer);
1847 ad->type = initializer->ctype;
1848 linearize_store_gen(ep, value, ad);
1849 return value;
1850 }
1851 }
1852
1853 return VOID;
1854 }
1855
1856 static void linearize_argument(struct entrypoint *ep, struct symbol *arg, int nr)
1857 {
1858 struct access_data ad = { NULL, };
1859
1860 ad.type = arg;
1861 ad.address = symbol_pseudo(ep, arg);
1862 linearize_store_gen(ep, argument_pseudo(ep, nr), &ad);
1863 }
1864
1865 static pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr)
1866 {
1867 if (!expr)
1868 return VOID;
1869
1870 current_pos = expr->pos;
1871 switch (expr->type) {
1872 case EXPR_SYMBOL:
1873 linearize_one_symbol(ep, expr->symbol);
1874 return add_symbol_address(ep, expr->symbol);
1875
1876 case EXPR_VALUE:
1877 return value_pseudo(expr->value);
1878
1879 case EXPR_STRING:
1880 case EXPR_LABEL:
1881 return add_setval(ep, expr->ctype, expr);
1882
1883 case EXPR_FVALUE:
1884 return add_setfval(ep, expr->ctype, expr->fvalue);
1885
1886 case EXPR_STATEMENT:
1887 return linearize_statement(ep, expr->statement);
1888
1889 case EXPR_CALL:
1890 return linearize_call_expression(ep, expr);
1891
1892 case EXPR_BINOP:
1893 if (expr->op == SPECIAL_LOGICAL_AND || expr->op == SPECIAL_LOGICAL_OR)
1894 return linearize_binop_bool(ep, expr);
1895 return linearize_binop(ep, expr);
1896
1897 case EXPR_LOGICAL:
1898 return linearize_logical(ep, expr);
1899
1900 case EXPR_COMPARE:
1901 return linearize_compare(ep, expr);
1902
1903 case EXPR_SELECT:
1904 return linearize_select(ep, expr);
1905
1946 {
1947 struct access_data ad = { NULL, };
1948 pseudo_t value;
1949
1950 if (!sym || !sym->initializer || sym->initialized)
1951 return VOID;
1952
1953 /* We need to output these puppies some day too.. */
1954 if (sym->ctype.modifiers & (MOD_STATIC | MOD_TOPLEVEL))
1955 return VOID;
1956
1957 sym->initialized = 1;
1958 ad.address = symbol_pseudo(ep, sym);
1959
1960 if (sym->initializer && !is_scalar_type(sym)) {
1961 // default zero initialization [6.7.9.21]
1962 // FIXME: this init the whole aggregate while
1963 // only the existing fields need to be initialized.
1964 // FIXME: this init the whole aggregate even if
1965 // all fields arelater explicitely initialized.
1966 ad.type = sym;
1967 ad.address = symbol_pseudo(ep, sym);
1968 linearize_store_gen(ep, value_pseudo(0), &ad);
1969 }
1970
1971 value = linearize_initializer(ep, sym->initializer, &ad);
1972 return value;
1973 }
1974
1975 static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct statement *stmt)
1976 {
1977 pseudo_t pseudo;
1978 struct statement *s;
1979
1980 pseudo = VOID;
1981 FOR_EACH_PTR(stmt->stmts, s) {
1982 pseudo = linearize_statement(ep, s);
1983 } END_FOR_EACH_PTR(s);
1984
1985 return pseudo;
1986 }
1987
1988 static void add_return(struct entrypoint *ep, struct basic_block *bb, struct symbol *ctype, pseudo_t src)
1989 {
1990 struct instruction *phi_node = first_instruction(bb->insns);
1991 pseudo_t phi;
1992 if (!phi_node) {
1993 phi_node = alloc_typed_instruction(OP_PHI, ctype);
1994 phi_node->target = alloc_pseudo(phi_node);
1995 phi_node->bb = bb;
1996 add_instruction(&bb->insns, phi_node);
1997 }
1998 phi = alloc_phi(ep->active, src, ctype);
1999 phi->ident = &return_ident;
2000 use_pseudo(phi_node, phi, add_pseudo(&phi_node->phi_list, phi));
2001 }
2002
2003 static pseudo_t linearize_fn_statement(struct entrypoint *ep, struct statement *stmt)
2004 {
2005 struct instruction *phi_node;
2006 struct basic_block *bb;
2007 pseudo_t pseudo;
2008
2009 pseudo = linearize_compound_statement(ep, stmt);
2010 if (!is_void_type(stmt->ret)) { // non-void function
2011 struct basic_block *active = ep->active;
2012 if (active && !bb_terminated(active)) { // missing return
2013 struct basic_block *bb_ret;
2014 bb_ret = get_bound_block(ep, stmt->ret);
2015 add_return(ep, bb_ret, stmt->ret, undef_pseudo());
2016 }
2017 }
2018 bb = add_label(ep, stmt->ret);
2019 phi_node = first_instruction(bb->insns);
2020 if (phi_node)
2021 pseudo = phi_node->target;
2022 return pseudo;
2023 }
2024
2025 static pseudo_t linearize_inlined_call(struct entrypoint *ep, struct statement *stmt)
2026 {
2027 struct instruction *insn = alloc_instruction(OP_INLINED_CALL, 0);
2028 struct statement *args = stmt->args;
2029 struct basic_block *bb;
2030 pseudo_t pseudo;
2031
2032 if (args) {
2033 struct symbol *sym;
2034
2035 concat_symbol_list(args->declaration, &ep->syms);
2036 FOR_EACH_PTR(args->declaration, sym) {
2037 pseudo_t value = linearize_one_symbol(ep, sym);
2038 add_pseudo(&insn->arguments, value);
2039 } END_FOR_EACH_PTR(sym);
2040 }
2041
2042 pseudo = linearize_fn_statement(ep, stmt);
2043 insn->target = pseudo;
2044
2045 use_pseudo(insn, symbol_pseudo(ep, stmt->inline_fn), &insn->func);
2046 bb = ep->active;
2047 if (!bb->insns)
2048 bb->pos = stmt->pos;
2049 add_one_insn(ep, insn);
2050 return pseudo;
2051 }
2052
2053 static pseudo_t linearize_context(struct entrypoint *ep, struct statement *stmt)
2054 {
2055 struct instruction *insn = alloc_instruction(OP_CONTEXT, 0);
2056 struct expression *expr = stmt->expression;
2057
2058 insn->increment = get_expression_value(expr);
2059 insn->context_expr = stmt->context;
2060 add_one_insn(ep, insn);
2061 return VOID;
2062 }
2063
2064 static pseudo_t linearize_range(struct entrypoint *ep, struct statement *stmt)
2065 {
2066 struct instruction *insn = alloc_instruction(OP_RANGE, 0);
2067
2068 use_pseudo(insn, linearize_expression(ep, stmt->range_expression), &insn->src1);
2069 use_pseudo(insn, linearize_expression(ep, stmt->range_low), &insn->src2);
2070 use_pseudo(insn, linearize_expression(ep, stmt->range_high), &insn->src3);
2071 add_one_insn(ep, insn);
2072 return VOID;
2073 }
2074
2075 ALLOCATOR(asm_rules, "asm rules");
2076 ALLOCATOR(asm_constraint, "asm constraints");
2077
2078 static void add_asm_input(struct entrypoint *ep, struct instruction *insn, struct expression *expr,
2080 {
2081 pseudo_t pseudo = linearize_expression(ep, expr);
2082 struct asm_constraint *rule = __alloc_asm_constraint(0);
2083
2084 rule->ident = ident;
2085 rule->constraint = constraint;
2086 use_pseudo(insn, pseudo, &rule->pseudo);
2087 add_ptr_list(&insn->asm_rules->inputs, rule);
2088 }
2089
2090 static void add_asm_output(struct entrypoint *ep, struct instruction *insn, struct expression *expr,
2091 const char *constraint, const struct ident *ident)
2092 {
2093 struct access_data ad = { NULL, };
2094 pseudo_t pseudo = alloc_pseudo(insn);
2095 struct asm_constraint *rule;
2096
2097 if (!expr || !linearize_address_gen(ep, expr, &ad))
2098 return;
2099 linearize_store_gen(ep, pseudo, &ad);
2100 rule = __alloc_asm_constraint(0);
2101 rule->ident = ident;
2102 rule->constraint = constraint;
2103 use_pseudo(insn, pseudo, &rule->pseudo);
2104 add_ptr_list(&insn->asm_rules->outputs, rule);
2105 }
2106
2107 static pseudo_t linearize_asm_statement(struct entrypoint *ep, struct statement *stmt)
2108 {
2109 struct expression *expr;
2110 struct instruction *insn;
2111 struct asm_rules *rules;
2112 const char *constraint;
2113
2114 insn = alloc_instruction(OP_ASM, 0);
2115 expr = stmt->asm_string;
2116 if (!expr || expr->type != EXPR_STRING) {
2117 warning(stmt->pos, "expected string in inline asm");
2118 return VOID;
2119 }
2120 insn->string = expr->string->data;
2121
2122 rules = __alloc_asm_rules(0);
2123 insn->asm_rules = rules;
2124
2125 /* Gather the inputs.. */
2126 FOR_EACH_PTR(stmt->asm_inputs, expr) {
2127 constraint = expr->constraint ? expr->constraint->string->data : "";
2128 add_asm_input(ep, insn, expr->expr, constraint, expr->name);
2129 } END_FOR_EACH_PTR(expr);
2130
2131 add_one_insn(ep, insn);
2132
2133 /* Assign the outputs */
2134 FOR_EACH_PTR(stmt->asm_outputs, expr) {
2135 constraint = expr->constraint ? expr->constraint->string->data : "";
2136 add_asm_output(ep, insn, expr->expr, constraint, expr->name);
2137 } END_FOR_EACH_PTR(expr);
2138
2139 return VOID;
2140 }
2141
2142 static int multijmp_cmp(const void *_a, const void *_b)
2143 {
2144 const struct multijmp *a = _a;
2145 const struct multijmp *b = _b;
2146
2147 // "default" case?
2148 if (a->begin > a->end) {
2149 if (b->begin > b->end)
2150 return 0;
2151 return 1;
2152 }
2153 if (b->begin > b->end)
2154 return -1;
2155 if (a->begin == b->begin) {
2156 if (a->end == b->end)
2163 static void sort_switch_cases(struct instruction *insn)
2164 {
2165 sort_list((struct ptr_list **)&insn->multijmp_list, multijmp_cmp);
2166 }
2167
2168 static pseudo_t linearize_declaration(struct entrypoint *ep, struct statement *stmt)
2169 {
2170 struct symbol *sym;
2171
2172 concat_symbol_list(stmt->declaration, &ep->syms);
2173
2174 FOR_EACH_PTR(stmt->declaration, sym) {
2175 linearize_one_symbol(ep, sym);
2176 } END_FOR_EACH_PTR(sym);
2177 return VOID;
2178 }
2179
2180 static pseudo_t linearize_return(struct entrypoint *ep, struct statement *stmt)
2181 {
2182 struct expression *expr = stmt->expression;
2183 struct symbol *ret = stmt->ret_target;
2184 struct basic_block *bb_return = get_bound_block(ep, ret);
2185 struct basic_block *active;
2186 pseudo_t src = linearize_expression(ep, expr);
2187 active = ep->active;
2188 if (active && !is_void_type(ret)) {
2189 add_return(ep, bb_return, ret, src);
2190 }
2191 add_goto(ep, bb_return);
2192 return VOID;
2193 }
2194
2195 static pseudo_t linearize_switch(struct entrypoint *ep, struct statement *stmt)
2196 {
2197 struct symbol *sym;
2198 struct instruction *switch_ins;
2199 struct basic_block *switch_end = alloc_basic_block(ep, stmt->pos);
2200 struct basic_block *active, *default_case;
2201 struct expression *expr = stmt->switch_expression;
2202 struct multijmp *jmp;
2203 pseudo_t pseudo;
2204
2205 if (!expr || !expr->ctype)
2206 return VOID;
2207 pseudo = linearize_expression(ep, expr);
2208 active = ep->active;
2209 if (!active) {
2210 active = alloc_basic_block(ep, stmt->pos);
2211 set_activeblock(ep, active);
2212 }
2213
2214 switch_ins = alloc_typed_instruction(OP_SWITCH, expr->ctype);
2215 use_pseudo(switch_ins, pseudo, &switch_ins->cond);
2216 add_one_insn(ep, switch_ins);
2217 finish_block(ep);
2218
2219 default_case = NULL;
2220 FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) {
2221 struct statement *case_stmt = sym->stmt;
2222 struct basic_block *bb_case = get_bound_block(ep, sym);
2223
2224 if (!case_stmt->case_expression) {
2225 default_case = bb_case;
2226 continue;
2227 } else if (case_stmt->case_expression->type != EXPR_VALUE) {
2228 continue;
2229 } else {
2230 struct expression *case_to = case_stmt->case_to;
2231 long long begin, end;
2232
2233 begin = end = case_stmt->case_expression->value;
2234 if (case_to && case_to->type == EXPR_VALUE)
2235 end = case_to->value;
2236 if (begin > end)
2237 jmp = alloc_multijmp(bb_case, end, begin);
2238 else
2239 jmp = alloc_multijmp(bb_case, begin, end);
2240
2241 }
2242 add_multijmp(&switch_ins->multijmp_list, jmp);
2243 add_bb(&bb_case->parents, active);
2244 add_bb(&active->children, bb_case);
2245 } END_FOR_EACH_PTR(sym);
2246
2247 bind_label(stmt->switch_break, switch_end, stmt->pos);
2248
2249 /* And linearize the actual statement */
2250 linearize_statement(ep, stmt->switch_statement);
2251 set_activeblock(ep, switch_end);
2252
2253 if (!default_case)
2254 default_case = switch_end;
2255
2292 linearize_cond_branch(ep, pre_condition, loop_body, loop_end);
2293
2294 bind_label(stmt->iterator_continue, loop_continue, stmt->pos);
2295 bind_label(stmt->iterator_break, loop_end, stmt->pos);
2296
2297 set_activeblock(ep, loop_body);
2298 linearize_statement(ep, statement);
2299 add_goto(ep, loop_continue);
2300
2301 set_activeblock(ep, loop_continue);
2302 linearize_statement(ep, post_statement);
2303 if (!post_condition)
2304 add_goto(ep, loop_top);
2305 else
2306 linearize_cond_branch(ep, post_condition, loop_top, loop_end);
2307 set_activeblock(ep, loop_end);
2308
2309 return VOID;
2310 }
2311
2312 static pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
2313 {
2314 struct basic_block *bb;
2315
2316 if (!stmt)
2317 return VOID;
2318
2319 bb = ep->active;
2320 if (bb && !bb->insns)
2321 bb->pos = stmt->pos;
2322 current_pos = stmt->pos;
2323
2324 switch (stmt->type) {
2325 case STMT_NONE:
2326 break;
2327
2328 case STMT_DECLARATION:
2329 return linearize_declaration(ep, stmt);
2330
2331 case STMT_CONTEXT:
2332 return linearize_context(ep, stmt);
2369 if (!bb_reachable(active))
2370 break;
2371
2372 if (stmt->goto_label) {
2373 add_goto(ep, get_bound_block(ep, stmt->goto_label));
2374 break;
2375 }
2376
2377 expr = stmt->goto_expression;
2378 if (!expr)
2379 break;
2380
2381 /* This can happen as part of simplification */
2382 if (expr->type == EXPR_LABEL) {
2383 add_goto(ep, get_bound_block(ep, expr->label_symbol));
2384 break;
2385 }
2386
2387 pseudo = linearize_expression(ep, expr);
2388 goto_ins = alloc_instruction(OP_COMPUTEDGOTO, 0);
2389 use_pseudo(goto_ins, pseudo, &goto_ins->src);
2390 add_one_insn(ep, goto_ins);
2391
2392 FOR_EACH_PTR(stmt->target_list, sym) {
2393 struct basic_block *bb_computed = get_bound_block(ep, sym);
2394 struct multijmp *jmp = alloc_multijmp(bb_computed, 1, 0);
2395 add_multijmp(&goto_ins->multijmp_list, jmp);
2396 add_bb(&bb_computed->parents, ep->active);
2397 add_bb(&active->children, bb_computed);
2398 } END_FOR_EACH_PTR(sym);
2399
2400 finish_block(ep);
2401 break;
2402 }
2403
2404 case STMT_COMPOUND:
2405 if (stmt->inline_fn)
2406 return linearize_inlined_call(ep, stmt);
2407 return linearize_compound_statement(ep, stmt);
2408
2409 /*
2429 linearize_statement(ep, stmt->if_false);
2430 }
2431 set_activeblock(ep, endif);
2432 break;
2433 }
2434
2435 case STMT_SWITCH:
2436 return linearize_switch(ep, stmt);
2437
2438 case STMT_ITERATOR:
2439 return linearize_iterator(ep, stmt);
2440
2441 default:
2442 break;
2443 }
2444 return VOID;
2445 }
2446
2447 static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_type)
2448 {
2449 struct statement *stmt = base_type->stmt;
2450 struct entrypoint *ep;
2451 struct basic_block *bb;
2452 struct symbol *ret_type;
2453 struct symbol *arg;
2454 struct instruction *entry;
2455 struct instruction *ret;
2456 pseudo_t result;
2457 int i;
2458
2459 if (!stmt)
2460 return NULL;
2461
2462 ep = alloc_entrypoint();
2463 ep->name = sym;
2464 sym->ep = ep;
2465 bb = alloc_basic_block(ep, sym->pos);
2466 set_activeblock(ep, bb);
2467
2468 if (stmt->type == STMT_ASM) { // top-level asm
2469 linearize_asm_statement(ep, stmt);
2470 return ep;
2471 }
2472
2473 entry = alloc_instruction(OP_ENTRY, 0);
2474 add_one_insn(ep, entry);
2475 ep->entry = entry;
2476
2477 concat_symbol_list(base_type->arguments, &ep->syms);
2478
2479 /* FIXME!! We should do something else about varargs.. */
2480 i = 0;
2481 FOR_EACH_PTR(base_type->arguments, arg) {
2482 linearize_argument(ep, arg, ++i);
2483 } END_FOR_EACH_PTR(arg);
2484
2485 result = linearize_fn_statement(ep, stmt);
2486 ret_type = base_type->ctype.base_type;
2487 ret = alloc_typed_instruction(OP_RET, ret_type);
2488 if (type_size(ret_type) > 0)
2489 use_pseudo(ret, result, &ret->src);
2490 add_one_insn(ep, ret);
2491
2492 optimize(ep);
2493 return ep;
2494 }
2495
2496 struct entrypoint *linearize_symbol(struct symbol *sym)
2497 {
2498 struct symbol *base_type;
2499
2500 if (!sym)
2501 return NULL;
2502 current_pos = sym->pos;
2503 base_type = sym->ctype.base_type;
2504 if (!base_type)
2505 return NULL;
2506 if (base_type->type == SYM_FN)
2507 return linearize_fn(sym, base_type);
2508 return NULL;
2509 }
|