?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
fix: try_to_simplify_bb eargerness
[smatch.git] / linearize.c
blob7313e72d8e01426e3bfe0b80bae2a49fff60e159
1 /*
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;
48 insn->pos = current_pos;
49 return insn;
50 }
51
52 static inline int type_size(struct symbol *type)
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)
262 buf += sprintf(buf, " [%s]", show_ident(entry->ident));
263 sep = ", ";
264 } END_FOR_EACH_PTR(entry);
265 return buf;
266 }
267
268 static char *show_asm(char *buf, struct instruction *insn)
269 {
270 struct asm_rules *rules = insn->asm_rules;
271
272 buf += sprintf(buf, "\"%s\"", insn->string);
273 buf = show_asm_constraints(buf, "\n\t\tout: ", rules->outputs);
274 buf = show_asm_constraints(buf, "\n\t\tin: ", rules->inputs);
275 buf = show_asm_constraints(buf, "\n\t\tclobber: ", rules->clobbers);
276 return buf;
277 }
278
279 const char *show_instruction(struct instruction *insn)
280 {
281 int opcode = insn->opcode;
282 static char buffer[4096];
283 char *buf;
284
285 buf = buffer;
286 if (!insn->bb)
287 buf += sprintf(buf, "# ");
288
289 if (opcode < ARRAY_SIZE(opcodes)) {
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 buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
338
339 if (!expr) {
340 buf += sprintf(buf, "%s", "<none>");
341 break;
342 }
343
344 switch (expr->type) {
345 case EXPR_VALUE:
346 buf += sprintf(buf, "%lld", expr->value);
347 break;
348 case EXPR_FVALUE:
349 buf += sprintf(buf, "%Lf", expr->fvalue);
350 break;
351 case EXPR_STRING:
352 buf += sprintf(buf, "%.40s", show_string(expr->string));
353 break;
354 case EXPR_SYMBOL:
355 buf += sprintf(buf, "%s", show_ident(expr->symbol->ident));
356 break;
357 case EXPR_LABEL:
358 buf += sprintf(buf, ".L%u", expr->symbol->bb_target->nr);
359 break;
360 default:
361 buf += sprintf(buf, "SETVAL EXPR TYPE %d", expr->type);
362 }
363 break;
364 }
365 case OP_SWITCH: {
366 struct multijmp *jmp;
367 buf += sprintf(buf, "%s", show_pseudo(insn->cond));
368 FOR_EACH_PTR(insn->multijmp_list, jmp) {
369 if (jmp->begin == jmp->end)
370 buf += sprintf(buf, ", %d -> .L%u", jmp->begin, jmp->target->nr);
371 else if (jmp->begin < jmp->end)
372 buf += sprintf(buf, ", %d ... %d -> .L%u", jmp->begin, jmp->end, jmp->target->nr);
373 else
374 buf += sprintf(buf, ", default -> .L%u", jmp->target->nr);
375 } END_FOR_EACH_PTR(jmp);
376 break;
377 }
378 case OP_COMPUTEDGOTO: {
379 struct multijmp *jmp;
380 buf += sprintf(buf, "%s", show_pseudo(insn->target));
381 FOR_EACH_PTR(insn->multijmp_list, jmp) {
382 buf += sprintf(buf, ", .L%u", jmp->target->nr);
383 } END_FOR_EACH_PTR(jmp);
384 break;
385 }
386
387 case OP_PHISOURCE: {
388 struct instruction *phi;
389 buf += sprintf(buf, "%s <- %s ", show_pseudo(insn->target), show_pseudo(insn->phi_src));
390 FOR_EACH_PTR(insn->phi_users, phi) {
391 buf += sprintf(buf, " (%s)", show_pseudo(phi->target));
392 } END_FOR_EACH_PTR(phi);
393 break;
394 }
395
396 case OP_PHI: {
397 pseudo_t phi;
398 const char *s = " <-";
399 buf += sprintf(buf, "%s", show_pseudo(insn->target));
400 FOR_EACH_PTR(insn->phi_list, phi) {
401 buf += sprintf(buf, "%s %s", s, show_pseudo(phi));
402 s = ",";
403 } END_FOR_EACH_PTR(phi);
404 break;
405 }
406 case OP_LOAD: case OP_LNOP:
407 buf += sprintf(buf, "%s <- %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
408 break;
409 case OP_STORE: case OP_SNOP:
410 buf += sprintf(buf, "%s -> %d[%s]", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
411 break;
412 case OP_INLINED_CALL:
413 case OP_CALL: {
414 struct pseudo *arg;
415 if (insn->target && insn->target != VOID)
416 buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
417 buf += sprintf(buf, "%s", show_pseudo(insn->func));
418 FOR_EACH_PTR(insn->arguments, arg) {
419 buf += sprintf(buf, ", %s", show_pseudo(arg));
420 } END_FOR_EACH_PTR(arg);
421 break;
422 }
423 case OP_CAST:
424 case OP_SCAST:
425 case OP_FPCAST:
426 case OP_PTRCAST:
427 buf += sprintf(buf, "%s <- (%d) %s",
428 show_pseudo(insn->target),
429 type_size(insn->orig_type),
430 show_pseudo(insn->src));
431 break;
432 case OP_BINARY ... OP_BINARY_END:
433 case OP_BINCMP ... OP_BINCMP_END:
434 buf += sprintf(buf, "%s <- %s, %s", show_pseudo(insn->target), show_pseudo(insn->src1), show_pseudo(insn->src2));
435 break;
436
437 case OP_SEL:
438 buf += sprintf(buf, "%s <- %s, %s, %s", show_pseudo(insn->target),
439 show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3));
440 break;
441
442 case OP_SLICE:
443 buf += sprintf(buf, "%s <- %s, %d, %d", show_pseudo(insn->target), show_pseudo(insn->base), insn->from, insn->len);
444 break;
445
446 case OP_NOT: case OP_NEG:
447 buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1));
448 break;
449
450 case OP_CONTEXT:
451 buf += sprintf(buf, "%s%d", insn->check ? "check: " : "", insn->increment);
452 break;
453 case OP_RANGE:
454 buf += sprintf(buf, "%s between %s..%s", show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3));
455 break;
456 case OP_NOP:
457 buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1));
458 break;
459 case OP_DEATHNOTE:
460 buf += sprintf(buf, "%s", show_pseudo(insn->target));
461 break;
462 case OP_ASM:
463 buf = show_asm(buf, insn);
464 break;
465 case OP_COPY:
466 buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src));
467 break;
468 default:
469 break;
470 }
471
472 if (buf >= buffer + sizeof(buffer))
473 die("instruction buffer overflowed %td\n", buf - buffer);
474 do { --buf; } while (*buf == ' ');
475 *++buf = 0;
476 return buffer;
477 }
478
479 void show_bb(struct basic_block *bb)
480 {
481 struct instruction *insn;
482
483 printf(".L%u:\n", bb->nr);
484 if (verbose) {
485 pseudo_t needs, defines;
486 printf("%s:%d\n", stream_name(bb->pos.stream), bb->pos.line);
487
488 FOR_EACH_PTR(bb->needs, needs) {
489 struct instruction *def = needs->def;
490 if (def->opcode != OP_PHI) {
491 printf(" **uses %s (from .L%u)**\n", show_pseudo(needs), def->bb->nr);
492 } else {
493 pseudo_t phi;
494 const char *sep = " ";
495 printf(" **uses %s (from", show_pseudo(needs));
496 FOR_EACH_PTR(def->phi_list, phi) {
497 if (phi == VOID)
498 continue;
499 printf("%s(%s:.L%u)", sep, show_pseudo(phi), phi->def->bb->nr);
500 sep = ", ";
501 } END_FOR_EACH_PTR(phi);
502 printf(")**\n");
503 }
504 } END_FOR_EACH_PTR(needs);
505
506 FOR_EACH_PTR(bb->defines, defines) {
507 printf(" **defines %s **\n", show_pseudo(defines));
508 } END_FOR_EACH_PTR(defines);
509
510 if (bb->parents) {
511 struct basic_block *from;
512 FOR_EACH_PTR(bb->parents, from) {
513 printf(" **from .L%u (%s:%d:%d)**\n", from->nr,
514 stream_name(from->pos.stream), from->pos.line, from->pos.pos);
515 } END_FOR_EACH_PTR(from);
516 }
517
518 if (bb->children) {
519 struct basic_block *to;
520 FOR_EACH_PTR(bb->children, to) {
521 printf(" **to .L%u (%s:%d:%d)**\n", to->nr,
522 stream_name(to->pos.stream), to->pos.line, to->pos.pos);
523 } END_FOR_EACH_PTR(to);
524 }
525 }
526
527 FOR_EACH_PTR(bb->insns, insn) {
528 if (!insn->bb && verbose < 2)
529 continue;
530 printf("\t%s\n", show_instruction(insn));
531 } END_FOR_EACH_PTR(insn);
532 if (!bb_terminated(bb))
533 printf("\tEND\n");
534 }
535
536 static void show_symbol_usage(pseudo_t pseudo)
537 {
538 struct pseudo_user *pu;
539
540 if (pseudo) {
541 FOR_EACH_PTR(pseudo->users, pu) {
542 printf("\t%s\n", show_instruction(pu->insn));
543 } END_FOR_EACH_PTR(pu);
544 }
545 }
546
547 void show_entry(struct entrypoint *ep)
548 {
549 struct symbol *sym;
550 struct basic_block *bb;
551
552 printf("%s:\n", show_ident(ep->name->ident));
553
554 if (verbose) {
555 printf("ep %p: %s\n", ep, show_ident(ep->name->ident));
556
557 FOR_EACH_PTR(ep->syms, sym) {
558 if (!sym->pseudo)
559 continue;
560 if (!sym->pseudo->users)
561 continue;
562 printf(" sym: %p %s\n", sym, show_ident(sym->ident));
563 if (sym->ctype.modifiers & (MOD_EXTERN | MOD_STATIC | MOD_ADDRESSABLE))
564 printf("\texternal visibility\n");
565 show_symbol_usage(sym->pseudo);
566 } END_FOR_EACH_PTR(sym);
567
568 printf("\n");
569 }
570
571 FOR_EACH_PTR(ep->bbs, bb) {
572 if (!bb)
573 continue;
574 if (!bb->parents && !bb->children && !bb->insns && verbose < 2)
575 continue;
576 show_bb(bb);
577 printf("\n");
578 } END_FOR_EACH_PTR(bb);
579
580 printf("\n");
581 }
582
583 static void bind_label(struct symbol *label, struct basic_block *bb, struct position pos)
584 {
585 if (label->bb_target)
586 warning(pos, "label '%s' already bound", show_ident(label->ident));
587 label->bb_target = bb;
588 }
589
590 static struct basic_block * get_bound_block(struct entrypoint *ep, struct symbol *label)
591 {
592 struct basic_block *bb = label->bb_target;
593
594 if (!bb) {
595 bb = alloc_basic_block(ep, label->pos);
596 label->bb_target = bb;
597 }
598 return bb;
599 }
600
601 static void finish_block(struct entrypoint *ep)
602 {
603 struct basic_block *src = ep->active;
604 if (bb_reachable(src))
605 ep->active = NULL;
606 }
607
608 static void add_goto(struct entrypoint *ep, struct basic_block *dst)
609 {
610 struct basic_block *src = ep->active;
611 if (bb_reachable(src)) {
612 struct instruction *br = alloc_instruction(OP_BR, 0);
613 br->bb_true = dst;
614 add_bb(&dst->parents, src);
615 add_bb(&src->children, dst);
616 br->bb = src;
617 add_instruction(&src->insns, br);
618 ep->active = NULL;
619 }
620 }
621
622 static void add_one_insn(struct entrypoint *ep, struct instruction *insn)
623 {
624 struct basic_block *bb = ep->active;
625
626 if (bb_reachable(bb)) {
627 insn->bb = bb;
628 add_instruction(&bb->insns, insn);
629 }
630 }
631
632 static void set_activeblock(struct entrypoint *ep, struct basic_block *bb)
633 {
634 if (!bb_terminated(ep->active))
635 add_goto(ep, bb);
636
637 ep->active = bb;
638 if (bb_reachable(bb))
639 add_bb(&ep->bbs, bb);
640 }
641
642 static void remove_parent(struct basic_block *child, struct basic_block *parent)
643 {
644 remove_bb_from_list(&child->parents, parent, 1);
645 if (!child->parents)
646 repeat_phase |= REPEAT_CFG_CLEANUP;
647 }
648
649 /* Change a "switch" or a conditional branch into a branch */
650 void insert_branch(struct basic_block *bb, struct instruction *jmp, struct basic_block *target)
651 {
652 struct instruction *br, *old;
653 struct basic_block *child;
654
655 /* Remove the switch */
656 old = delete_last_instruction(&bb->insns);
657 assert(old == jmp);
658 kill_instruction(old);
659
660 br = alloc_instruction(OP_BR, 0);
661 br->bb = bb;
662 br->bb_true = target;
663 add_instruction(&bb->insns, br);
664
665 FOR_EACH_PTR(bb->children, child) {
666 if (child == target) {
667 target = NULL; /* Trigger just once */
668 continue;
669 }
670 DELETE_CURRENT_PTR(child);
671 remove_parent(child, bb);
672 } END_FOR_EACH_PTR(child);
673 PACK_PTR_LIST(&bb->children);
674
675 if (repeat_phase & REPEAT_CFG_CLEANUP)
676 kill_unreachable_bbs(bb->ep);
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(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 pseudo_t pseudo;
795
796 FOR_EACH_PTR(*list, pseudo) {
797 if (pseudo->value == val)
798 return pseudo;
799 } END_FOR_EACH_PTR(pseudo);
800
801 pseudo = __alloc_pseudo(0);
802 pseudo->type = PSEUDO_VAL;
803 pseudo->value = val;
804 add_pseudo(list, pseudo);
805
806 /* Value pseudos have neither nr, usage nor def */
807 return pseudo;
808 }
809
810 static pseudo_t argument_pseudo(struct entrypoint *ep, int nr)
811 {
812 pseudo_t pseudo = __alloc_pseudo(0);
813 struct instruction *entry = ep->entry;
814
815 pseudo->type = PSEUDO_ARG;
816 pseudo->nr = nr;
817 pseudo->def = entry;
818 add_pseudo(&entry->arg_list, pseudo);
819
820 /* Argument pseudos have neither usage nor def */
821 return pseudo;
822 }
823
824 pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size)
825 {
826 struct instruction *insn = alloc_instruction(OP_PHISOURCE, size);
827 pseudo_t phi = __alloc_pseudo(0);
828 static int nr = 0;
829
830 phi->type = PSEUDO_PHI;
831 phi->nr = ++nr;
832 phi->def = insn;
833
834 use_pseudo(insn, pseudo, &insn->phi_src);
835 insn->bb = source;
836 insn->target = phi;
837 add_instruction(&source->insns, insn);
838 return phi;
839 }
840
841 /*
842 * We carry the "access_data" structure around for any accesses,
843 * which simplifies things a lot. It contains all the access
844 * information in one place.
845 */
846 struct access_data {
847 struct symbol *result_type; // result ctype
848 struct symbol *source_type; // source ctype
849 pseudo_t address; // pseudo containing address ..
850 unsigned int offset; // byte offset
851 struct position pos;
852 };
853
854 static void finish_address_gen(struct entrypoint *ep, struct access_data *ad)
855 {
856 }
857
858 static int linearize_simple_address(struct entrypoint *ep,
859 struct expression *addr,
860 struct access_data *ad)
861 {
862 if (addr->type == EXPR_SYMBOL) {
863 linearize_one_symbol(ep, addr->symbol);
864 ad->address = symbol_pseudo(ep, addr->symbol);
865 return 1;
866 }
867 if (addr->type == EXPR_BINOP) {
868 if (addr->right->type == EXPR_VALUE) {
869 if (addr->op == '+') {
870 ad->offset += get_expression_value(addr->right);
871 return linearize_simple_address(ep, addr->left, ad);
872 }
873 }
874 }
875 ad->address = linearize_expression(ep, addr);
876 return 1;
877 }
878
879 static struct symbol *base_type(struct symbol *sym)
880 {
881 struct symbol *base = sym;
882
883 if (sym) {
884 if (sym->type == SYM_NODE)
885 base = base->ctype.base_type;
886 if (base->type == SYM_BITFIELD)
887 return base->ctype.base_type;
888 }
889 return sym;
890 }
891
892 static int linearize_address_gen(struct entrypoint *ep,
893 struct expression *expr,
894 struct access_data *ad)
895 {
896 struct symbol *ctype = expr->ctype;
897
898 if (!ctype)
899 return 0;
900 ad->pos = expr->pos;
901 ad->result_type = ctype;
902 ad->source_type = base_type(ctype);
903 if (expr->type == EXPR_PREOP && expr->op == '*')
904 return linearize_simple_address(ep, expr->unop, ad);
905
906 warning(expr->pos, "generating address of non-lvalue (%d)", expr->type);
907 return 0;
908 }
909
910 static pseudo_t add_load(struct entrypoint *ep, struct access_data *ad)
911 {
912 struct instruction *insn;
913 pseudo_t new;
914
915 insn = alloc_typed_instruction(OP_LOAD, ad->source_type);
916 new = alloc_pseudo(insn);
917
918 insn->target = new;
919 insn->offset = ad->offset;
920 use_pseudo(insn, ad->address, &insn->src);
921 add_one_insn(ep, insn);
922 return new;
923 }
924
925 static void add_store(struct entrypoint *ep, struct access_data *ad, pseudo_t value)
926 {
927 struct basic_block *bb = ep->active;
928
929 if (bb_reachable(bb)) {
930 struct instruction *store = alloc_typed_instruction(OP_STORE, ad->source_type);
931 store->offset = ad->offset;
932 use_pseudo(store, value, &store->target);
933 use_pseudo(store, ad->address, &store->src);
934 add_one_insn(ep, store);
935 }
936 }
937
938 static pseudo_t linearize_store_gen(struct entrypoint *ep,
939 pseudo_t value,
940 struct access_data *ad)
941 {
942 pseudo_t store = value;
943
944 if (type_size(ad->source_type) != type_size(ad->result_type)) {
945 struct symbol *ctype = ad->result_type;
946 unsigned int shift = ctype->bit_offset;
947 unsigned int size = ctype->bit_size;
948 pseudo_t orig = add_load(ep, ad);
949 unsigned long long mask = (1ULL << size) - 1;
950
951 if (shift) {
952 store = add_binary_op(ep, ad->source_type, OP_SHL, value, value_pseudo(shift));
953 mask <<= shift;
954 }
955 orig = add_binary_op(ep, ad->source_type, OP_AND, orig, value_pseudo(~mask));
956 store = add_binary_op(ep, ad->source_type, OP_OR, orig, store);
957 }
958 add_store(ep, ad, store);
959 return value;
960 }
961
962 static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right)
963 {
964 struct instruction *insn = alloc_typed_instruction(op, ctype);
965 pseudo_t target = alloc_pseudo(insn);
966 insn->target = target;
967 use_pseudo(insn, left, &insn->src1);
968 use_pseudo(insn, right, &insn->src2);
969 add_one_insn(ep, insn);
970 return target;
971 }
972
973 static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val)
974 {
975 struct instruction *insn = alloc_typed_instruction(OP_SETVAL, ctype);
976 pseudo_t target = alloc_pseudo(insn);
977 insn->target = target;
978 insn->val = val;
979 add_one_insn(ep, insn);
980 return target;
981 }
982
983 static pseudo_t add_symbol_address(struct entrypoint *ep, struct symbol *sym)
984 {
985 struct instruction *insn = alloc_instruction(OP_SYMADDR, bits_in_pointer);
986 pseudo_t target = alloc_pseudo(insn);
987
988 insn->target = target;
989 use_pseudo(insn, symbol_pseudo(ep, sym), &insn->symbol);
990 add_one_insn(ep, insn);
991 return target;
992 }
993
994 static pseudo_t linearize_load_gen(struct entrypoint *ep, struct access_data *ad)
995 {
996 struct symbol *ctype = ad->result_type;
997 pseudo_t new = add_load(ep, ad);
998
999 if (ctype->bit_offset) {
1000 pseudo_t shift = value_pseudo(ctype->bit_offset);
1001 pseudo_t newval = add_binary_op(ep, ad->source_type, OP_LSR, new, shift);
1002 new = newval;
1003 }
1004 if (ctype->bit_size != type_size(ad->source_type))
1005 new = cast_pseudo(ep, new, ad->source_type, ad->result_type);
1006 return new;
1007 }
1008
1009 static pseudo_t linearize_access(struct entrypoint *ep, struct expression *expr)
1010 {
1011 struct access_data ad = { NULL, };
1012 pseudo_t value;
1013
1014 if (!linearize_address_gen(ep, expr, &ad))
1015 return VOID;
1016 value = linearize_load_gen(ep, &ad);
1017 finish_address_gen(ep, &ad);
1018 return value;
1019 }
1020
1021 /* FIXME: FP */
1022 static pseudo_t linearize_inc_dec(struct entrypoint *ep, struct expression *expr, int postop)
1023 {
1024 struct access_data ad = { NULL, };
1025 pseudo_t old, new, one;
1026 int op = expr->op == SPECIAL_INCREMENT ? OP_ADD : OP_SUB;
1027
1028 if (!linearize_address_gen(ep, expr->unop, &ad))
1029 return VOID;
1030
1031 old = linearize_load_gen(ep, &ad);
1032 one = value_pseudo(expr->op_value);
1033 new = add_binary_op(ep, expr->ctype, op, old, one);
1034 linearize_store_gen(ep, new, &ad);
1035 finish_address_gen(ep, &ad);
1036 return postop ? old : new;
1037 }
1038
1039 static pseudo_t add_uniop(struct entrypoint *ep, struct expression *expr, int op, pseudo_t src)
1040 {
1041 struct instruction *insn = alloc_typed_instruction(op, expr->ctype);
1042 pseudo_t new = alloc_pseudo(insn);
1043
1044 insn->target = new;
1045 use_pseudo(insn, src, &insn->src1);
1046 add_one_insn(ep, insn);
1047 return new;
1048 }
1049
1050 static pseudo_t linearize_slice(struct entrypoint *ep, struct expression *expr)
1051 {
1052 pseudo_t pre = linearize_expression(ep, expr->base);
1053 struct instruction *insn = alloc_typed_instruction(OP_SLICE, expr->ctype);
1054 pseudo_t new = alloc_pseudo(insn);
1055
1056 insn->target = new;
1057 insn->from = expr->r_bitpos;
1058 insn->len = expr->r_nrbits;
1059 use_pseudo(insn, pre, &insn->base);
1060 add_one_insn(ep, insn);
1061 return new;
1062 }
1063
1064 static pseudo_t linearize_regular_preop(struct entrypoint *ep, struct expression *expr)
1065 {
1066 pseudo_t pre = linearize_expression(ep, expr->unop);
1067 switch (expr->op) {
1068 case '+':
1069 return pre;
1070 case '!': {
1071 pseudo_t zero = value_pseudo(0);
1072 return add_binary_op(ep, expr->ctype, OP_SET_EQ, pre, zero);
1073 }
1074 case '~':
1075 return add_uniop(ep, expr, OP_NOT, pre);
1076 case '-':
1077 return add_uniop(ep, expr, OP_NEG, pre);
1078 }
1079 return VOID;
1080 }
1081
1082 static pseudo_t linearize_preop(struct entrypoint *ep, struct expression *expr)
1083 {
1084 /*
1085 * '*' is an lvalue access, and is fundamentally different
1086 * from an arithmetic operation. Maybe it should have an
1087 * expression type of its own..
1088 */
1089 if (expr->op == '*')
1090 return linearize_access(ep, expr);
1091 if (expr->op == SPECIAL_INCREMENT || expr->op == SPECIAL_DECREMENT)
1092 return linearize_inc_dec(ep, expr, 0);
1093 return linearize_regular_preop(ep, expr);
1094 }
1095
1096 static pseudo_t linearize_postop(struct entrypoint *ep, struct expression *expr)
1097 {
1098 return linearize_inc_dec(ep, expr, 1);
1099 }
1100
1101 /*
1102 * Casts to pointers are "less safe" than other casts, since
1103 * they imply type-unsafe accesses. "void *" is a special
1104 * case, since you can't access through it anyway without another
1105 * cast.
1106 */
1107 static struct instruction *alloc_cast_instruction(struct symbol *src, struct symbol *ctype)
1108 {
1109 int opcode = OP_CAST;
1110 struct symbol *base = ctype;
1111
1112 if (src->ctype.modifiers & MOD_SIGNED)
1113 opcode = OP_SCAST;
1114 if (base->type == SYM_NODE)
1115 base = base->ctype.base_type;
1116 if (base->type == SYM_PTR) {
1117 base = base->ctype.base_type;
1118 if (base != &void_ctype)
1119 opcode = OP_PTRCAST;
1120 } else if (base->ctype.base_type == &fp_type)
1121 opcode = OP_FPCAST;
1122 return alloc_typed_instruction(opcode, ctype);
1123 }
1124
1125 static pseudo_t cast_pseudo(struct entrypoint *ep, pseudo_t src, struct symbol *from, struct symbol *to)
1126 {
1127 pseudo_t result;
1128 struct instruction *insn;
1129
1130 if (src == VOID)
1131 return VOID;
1132 if (!from || !to)
1133 return VOID;
1134 if (from->bit_size < 0 || to->bit_size < 0)
1135 return VOID;
1136 insn = alloc_cast_instruction(from, to);
1137 result = alloc_pseudo(insn);
1138 insn->target = result;
1139 insn->orig_type = from;
1140 use_pseudo(insn, src, &insn->src);
1141 add_one_insn(ep, insn);
1142 return result;
1143 }
1144
1145 static int opcode_sign(int opcode, struct symbol *ctype)
1146 {
1147 if (ctype && (ctype->ctype.modifiers & MOD_SIGNED)) {
1148 switch(opcode) {
1149 case OP_MULU: case OP_DIVU: case OP_MODU: case OP_LSR:
1150 opcode++;
1151 }
1152 }
1153 return opcode;
1154 }
1155
1156 static inline pseudo_t add_convert_to_bool(struct entrypoint *ep, pseudo_t src, struct symbol *type)
1157 {
1158 pseudo_t zero;
1159 int op;
1160
1161 if (is_bool_type(type))
1162 return src;
1163 zero = value_pseudo(0);
1164 op = OP_SET_NE;
1165 return add_binary_op(ep, &bool_ctype, op, src, zero);
1166 }
1167
1168 static pseudo_t linearize_expression_to_bool(struct entrypoint *ep, struct expression *expr)
1169 {
1170 pseudo_t dst;
1171 dst = linearize_expression(ep, expr);
1172 dst = add_convert_to_bool(ep, dst, expr->ctype);
1173 return dst;
1174 }
1175
1176 static pseudo_t linearize_assignment(struct entrypoint *ep, struct expression *expr)
1177 {
1178 struct access_data ad = { NULL, };
1179 struct expression *target = expr->left;
1180 struct expression *src = expr->right;
1181 struct symbol *ctype;
1182 pseudo_t value;
1183
1184 value = linearize_expression(ep, src);
1185 if (!target || !linearize_address_gen(ep, target, &ad))
1186 return value;
1187 if (expr->op != '=') {
1188 pseudo_t oldvalue = linearize_load_gen(ep, &ad);
1189 pseudo_t dst;
1190 static const int op_trans[] = {
1191 [SPECIAL_ADD_ASSIGN - SPECIAL_BASE] = OP_ADD,
1192 [SPECIAL_SUB_ASSIGN - SPECIAL_BASE] = OP_SUB,
1193 [SPECIAL_MUL_ASSIGN - SPECIAL_BASE] = OP_MULU,
1194 [SPECIAL_DIV_ASSIGN - SPECIAL_BASE] = OP_DIVU,
1195 [SPECIAL_MOD_ASSIGN - SPECIAL_BASE] = OP_MODU,
1196 [SPECIAL_SHL_ASSIGN - SPECIAL_BASE] = OP_SHL,
1197 [SPECIAL_SHR_ASSIGN - SPECIAL_BASE] = OP_LSR,
1198 [SPECIAL_AND_ASSIGN - SPECIAL_BASE] = OP_AND,
1199 [SPECIAL_OR_ASSIGN - SPECIAL_BASE] = OP_OR,
1200 [SPECIAL_XOR_ASSIGN - SPECIAL_BASE] = OP_XOR
1201 };
1202 int opcode;
1203
1204 if (!src)
1205 return VOID;
1206
1207 ctype = src->ctype;
1208 oldvalue = cast_pseudo(ep, oldvalue, target->ctype, ctype);
1209 opcode = opcode_sign(op_trans[expr->op - SPECIAL_BASE], ctype);
1210 dst = add_binary_op(ep, ctype, opcode, oldvalue, value);
1211 value = cast_pseudo(ep, dst, ctype, expr->ctype);
1212 }
1213 value = linearize_store_gen(ep, value, &ad);
1214 finish_address_gen(ep, &ad);
1215 return value;
1216 }
1217
1218 static pseudo_t linearize_call_expression(struct entrypoint *ep, struct expression *expr)
1219 {
1220 struct expression *arg, *fn;
1221 struct instruction *insn = alloc_typed_instruction(OP_CALL, expr->ctype);
1222 pseudo_t retval, call;
1223 struct ctype *ctype = NULL;
1224 struct symbol *fntype;
1225 struct context *context;
1226
1227 if (!expr->ctype) {
1228 warning(expr->pos, "call with no type!");
1229 return VOID;
1230 }
1231
1232 FOR_EACH_PTR(expr->args, arg) {
1233 pseudo_t new = linearize_expression(ep, arg);
1234 use_pseudo(insn, new, add_pseudo(&insn->arguments, new));
1235 } END_FOR_EACH_PTR(arg);
1236
1237 fn = expr->fn;
1238
1239 if (fn->ctype)
1240 ctype = &fn->ctype->ctype;
1241
1242 fntype = fn->ctype;
1243 if (fntype) {
1244 if (fntype->type == SYM_NODE)
1245 fntype = fntype->ctype.base_type;
1246 }
1247 insn->fntype = fntype;
1248
1249 if (fn->type == EXPR_PREOP) {
1250 if (fn->unop->type == EXPR_SYMBOL) {
1251 struct symbol *sym = fn->unop->symbol;
1252 if (sym->ctype.base_type->type == SYM_FN)
1253 fn = fn->unop;
1254 }
1255 }
1256 if (fn->type == EXPR_SYMBOL) {
1257 call = symbol_pseudo(ep, fn->symbol);
1258 } else {
1259 call = linearize_expression(ep, fn);
1260 }
1261 use_pseudo(insn, call, &insn->func);
1262 retval = VOID;
1263 if (expr->ctype != &void_ctype)
1264 retval = alloc_pseudo(insn);
1265 insn->target = retval;
1266 add_one_insn(ep, insn);
1267
1268 if (ctype) {
1269 FOR_EACH_PTR(ctype->contexts, context) {
1270 int in = context->in;
1271 int out = context->out;
1272 int check = 0;
1273 int context_diff;
1274 if (in < 0) {
1275 check = 1;
1276 in = 0;
1277 }
1278 if (out < 0) {
1279 check = 0;
1280 out = 0;
1281 }
1282 context_diff = out - in;
1283 if (check || context_diff) {
1284 insn = alloc_instruction(OP_CONTEXT, 0);
1285 insn->increment = context_diff;
1286 insn->check = check;
1287 insn->context_expr = context->context;
1288 add_one_insn(ep, insn);
1289 }
1290 } END_FOR_EACH_PTR(context);
1291 }
1292
1293 return retval;
1294 }
1295
1296 static pseudo_t linearize_binop_bool(struct entrypoint *ep, struct expression *expr)
1297 {
1298 pseudo_t src1, src2, dst;
1299 int op = (expr->op == SPECIAL_LOGICAL_OR) ? OP_OR_BOOL : OP_AND_BOOL;
1300
1301 src1 = linearize_expression_to_bool(ep, expr->left);
1302 src2 = linearize_expression_to_bool(ep, expr->right);
1303 dst = add_binary_op(ep, &bool_ctype, op, src1, src2);
1304 if (expr->ctype != &bool_ctype)
1305 dst = cast_pseudo(ep, dst, &bool_ctype, expr->ctype);
1306 return dst;
1307 }
1308
1309 static pseudo_t linearize_binop(struct entrypoint *ep, struct expression *expr)
1310 {
1311 pseudo_t src1, src2, dst;
1312 static const int opcode[] = {
1313 ['+'] = OP_ADD, ['-'] = OP_SUB,
1314 ['*'] = OP_MULU, ['/'] = OP_DIVU,
1315 ['%'] = OP_MODU, ['&'] = OP_AND,
1316 ['|'] = OP_OR, ['^'] = OP_XOR,
1317 [SPECIAL_LEFTSHIFT] = OP_SHL,
1318 [SPECIAL_RIGHTSHIFT] = OP_LSR,
1319 };
1320 int op;
1321
1322 src1 = linearize_expression(ep, expr->left);
1323 src2 = linearize_expression(ep, expr->right);
1324 op = opcode_sign(opcode[expr->op], expr->ctype);
1325 dst = add_binary_op(ep, expr->ctype, op, src1, src2);
1326 return dst;
1327 }
1328
1329 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
1330
1331 pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
1332
1333 static pseudo_t linearize_select(struct entrypoint *ep, struct expression *expr)
1334 {
1335 pseudo_t cond, true, false, res;
1336 struct instruction *insn;
1337
1338 true = linearize_expression(ep, expr->cond_true);
1339 false = linearize_expression(ep, expr->cond_false);
1340 cond = linearize_expression(ep, expr->conditional);
1341
1342 insn = alloc_typed_instruction(OP_SEL, expr->ctype);
1343 if (!expr->cond_true)
1344 true = cond;
1345 use_pseudo(insn, cond, &insn->src1);
1346 use_pseudo(insn, true, &insn->src2);
1347 use_pseudo(insn, false, &insn->src3);
1348
1349 res = alloc_pseudo(insn);
1350 insn->target = res;
1351 add_one_insn(ep, insn);
1352 return res;
1353 }
1354
1355 static pseudo_t add_join_conditional(struct entrypoint *ep, struct expression *expr,
1356 pseudo_t phi1, pseudo_t phi2)
1357 {
1358 pseudo_t target;
1359 struct instruction *phi_node;
1360
1361 if (phi1 == VOID)
1362 return phi2;
1363 if (phi2 == VOID)
1364 return phi1;
1365
1366 phi_node = alloc_typed_instruction(OP_PHI, expr->ctype);
1367 use_pseudo(phi_node, phi1, add_pseudo(&phi_node->phi_list, phi1));
1368 use_pseudo(phi_node, phi2, add_pseudo(&phi_node->phi_list, phi2));
1369 phi_node->target = target = alloc_pseudo(phi_node);
1370 add_one_insn(ep, phi_node);
1371 return target;
1372 }
1373
1374 static pseudo_t linearize_short_conditional(struct entrypoint *ep, struct expression *expr,
1375 struct expression *cond,
1376 struct expression *expr_false)
1377 {
1378 pseudo_t src1, src2;
1379 struct basic_block *bb_false;
1380 struct basic_block *merge = alloc_basic_block(ep, expr->pos);
1381 pseudo_t phi1, phi2;
1382 int size = type_size(expr->ctype);
1383
1384 if (!expr_false || !ep->active)
1385 return VOID;
1386
1387 bb_false = alloc_basic_block(ep, expr_false->pos);
1388 src1 = linearize_expression(ep, cond);
1389 phi1 = alloc_phi(ep->active, src1, size);
1390 add_branch(ep, expr, src1, merge, bb_false);
1391
1392 set_activeblock(ep, bb_false);
1393 src2 = linearize_expression(ep, expr_false);
1394 phi2 = alloc_phi(ep->active, src2, size);
1395 set_activeblock(ep, merge);
1396
1397 return add_join_conditional(ep, expr, phi1, phi2);
1398 }
1399
1400 static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *expr,
1401 struct expression *cond,
1402 struct expression *expr_true,
1403 struct expression *expr_false)
1404 {
1405 pseudo_t src1, src2;
1406 pseudo_t phi1, phi2;
1407 struct basic_block *bb_true, *bb_false, *merge;
1408 int size = type_size(expr->ctype);
1409
1410 if (!cond || !expr_true || !expr_false || !ep->active)
1411 return VOID;
1412 bb_true = alloc_basic_block(ep, expr_true->pos);
1413 bb_false = alloc_basic_block(ep, expr_false->pos);
1414 merge = alloc_basic_block(ep, expr->pos);
1415
1416 linearize_cond_branch(ep, cond, bb_true, bb_false);
1417
1418 set_activeblock(ep, bb_true);
1419 src1 = linearize_expression(ep, expr_true);
1420 phi1 = alloc_phi(ep->active, src1, size);
1421 add_goto(ep, merge);
1422
1423 set_activeblock(ep, bb_false);
1424 src2 = linearize_expression(ep, expr_false);
1425 phi2 = alloc_phi(ep->active, src2, size);
1426 set_activeblock(ep, merge);
1427
1428 return add_join_conditional(ep, expr, phi1, phi2);
1429 }
1430
1431 static pseudo_t linearize_logical(struct entrypoint *ep, struct expression *expr)
1432 {
1433 struct expression *shortcut;
1434
1435 shortcut = alloc_const_expression(expr->pos, expr->op == SPECIAL_LOGICAL_OR);
1436 shortcut->ctype = expr->ctype;
1437 if (expr->op == SPECIAL_LOGICAL_OR)
1438 return linearize_conditional(ep, expr, expr->left, shortcut, expr->right);
1439 return linearize_conditional(ep, expr, expr->left, expr->right, shortcut);
1440 }
1441
1442 static pseudo_t linearize_compare(struct entrypoint *ep, struct expression *expr)
1443 {
1444 static const int cmpop[] = {
1445 ['>'] = OP_SET_GT, ['<'] = OP_SET_LT,
1446 [SPECIAL_EQUAL] = OP_SET_EQ,
1447 [SPECIAL_NOTEQUAL] = OP_SET_NE,
1448 [SPECIAL_GTE] = OP_SET_GE,
1449 [SPECIAL_LTE] = OP_SET_LE,
1450 [SPECIAL_UNSIGNED_LT] = OP_SET_B,
1451 [SPECIAL_UNSIGNED_GT] = OP_SET_A,
1452 [SPECIAL_UNSIGNED_LTE] = OP_SET_BE,
1453 [SPECIAL_UNSIGNED_GTE] = OP_SET_AE,
1454 };
1455
1456 pseudo_t src1 = linearize_expression(ep, expr->left);
1457 pseudo_t src2 = linearize_expression(ep, expr->right);
1458 pseudo_t dst = add_binary_op(ep, expr->ctype, cmpop[expr->op], src1, src2);
1459 return dst;
1460 }
1461
1462
1463 pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
1464 {
1465 pseudo_t cond;
1466
1467 if (!expr || !bb_reachable(ep->active))
1468 return VOID;
1469
1470 switch (expr->type) {
1471
1472 case EXPR_STRING:
1473 case EXPR_VALUE:
1474 add_goto(ep, expr->value ? bb_true : bb_false);
1475 return VOID;
1476
1477 case EXPR_FVALUE:
1478 add_goto(ep, expr->fvalue ? bb_true : bb_false);
1479 return VOID;
1480
1481 case EXPR_LOGICAL:
1482 linearize_logical_branch(ep, expr, bb_true, bb_false);
1483 return VOID;
1484
1485 case EXPR_COMPARE:
1486 cond = linearize_compare(ep, expr);
1487 add_branch(ep, expr, cond, bb_true, bb_false);
1488 break;
1489
1490 case EXPR_PREOP:
1491 if (expr->op == '!')
1492 return linearize_cond_branch(ep, expr->unop, bb_false, bb_true);
1493 /* fall through */
1494 default: {
1495 cond = linearize_expression(ep, expr);
1496 add_branch(ep, expr, cond, bb_true, bb_false);
1497
1498 return VOID;
1499 }
1500 }
1501 return VOID;
1502 }
1503
1504
1505
1506 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
1507 {
1508 struct basic_block *next = alloc_basic_block(ep, expr->pos);
1509
1510 if (expr->op == SPECIAL_LOGICAL_OR)
1511 linearize_cond_branch(ep, expr->left, bb_true, next);
1512 else
1513 linearize_cond_branch(ep, expr->left, next, bb_false);
1514 set_activeblock(ep, next);
1515 linearize_cond_branch(ep, expr->right, bb_true, bb_false);
1516 return VOID;
1517 }
1518
1519 static pseudo_t linearize_cast(struct entrypoint *ep, struct expression *expr)
1520 {
1521 pseudo_t src;
1522 struct expression *orig = expr->cast_expression;
1523
1524 if (!orig)
1525 return VOID;
1526
1527 src = linearize_expression(ep, orig);
1528 return cast_pseudo(ep, src, orig->ctype, expr->ctype);
1529 }
1530
1531 static pseudo_t linearize_position(struct entrypoint *ep, struct expression *pos, struct access_data *ad)
1532 {
1533 struct expression *init_expr = pos->init_expr;
1534
1535 ad->offset = pos->init_offset;
1536 ad->source_type = base_type(init_expr->ctype);
1537 ad->result_type = init_expr->ctype;
1538 return linearize_initializer(ep, init_expr, ad);
1539 }
1540
1541 static pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *ad)
1542 {
1543 switch (initializer->type) {
1544 case EXPR_INITIALIZER: {
1545 struct expression *expr;
1546 FOR_EACH_PTR(initializer->expr_list, expr) {
1547 linearize_initializer(ep, expr, ad);
1548 } END_FOR_EACH_PTR(expr);
1549 break;
1550 }
1551 case EXPR_POS:
1552 linearize_position(ep, initializer, ad);
1553 break;
1554 default: {
1555 pseudo_t value = linearize_expression(ep, initializer);
1556 ad->source_type = base_type(initializer->ctype);
1557 ad->result_type = initializer->ctype;
1558 linearize_store_gen(ep, value, ad);
1559 return value;
1560 }
1561 }
1562
1563 return VOID;
1564 }
1565
1566 static void linearize_argument(struct entrypoint *ep, struct symbol *arg, int nr)
1567 {
1568 struct access_data ad = { NULL, };
1569
1570 ad.source_type = arg;
1571 ad.result_type = arg;
1572 ad.address = symbol_pseudo(ep, arg);
1573 linearize_store_gen(ep, argument_pseudo(ep, nr), &ad);
1574 finish_address_gen(ep, &ad);
1575 }
1576
1577 pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr)
1578 {
1579 if (!expr)
1580 return VOID;
1581
1582 current_pos = expr->pos;
1583 switch (expr->type) {
1584 case EXPR_SYMBOL:
1585 linearize_one_symbol(ep, expr->symbol);
1586 return add_symbol_address(ep, expr->symbol);
1587
1588 case EXPR_VALUE:
1589 return value_pseudo(expr->value);
1590
1591 case EXPR_STRING: case EXPR_FVALUE: case EXPR_LABEL:
1592 return add_setval(ep, expr->ctype, expr);
1593
1594 case EXPR_STATEMENT:
1595 return linearize_statement(ep, expr->statement);
1596
1597 case EXPR_CALL:
1598 return linearize_call_expression(ep, expr);
1599
1600 case EXPR_BINOP:
1601 if (expr->op == SPECIAL_LOGICAL_AND || expr->op == SPECIAL_LOGICAL_OR)
1602 return linearize_binop_bool(ep, expr);
1603 return linearize_binop(ep, expr);
1604
1605 case EXPR_LOGICAL:
1606 return linearize_logical(ep, expr);
1607
1608 case EXPR_COMPARE:
1609 return linearize_compare(ep, expr);
1610
1611 case EXPR_SELECT:
1612 return linearize_select(ep, expr);
1613
1614 case EXPR_CONDITIONAL:
1615 if (!expr->cond_true)
1616 return linearize_short_conditional(ep, expr, expr->conditional, expr->cond_false);
1617
1618 return linearize_conditional(ep, expr, expr->conditional,
1619 expr->cond_true, expr->cond_false);
1620
1621 case EXPR_COMMA:
1622 linearize_expression(ep, expr->left);
1623 return linearize_expression(ep, expr->right);
1624
1625 case EXPR_ASSIGNMENT:
1626 return linearize_assignment(ep, expr);
1627
1628 case EXPR_PREOP:
1629 return linearize_preop(ep, expr);
1630
1631 case EXPR_POSTOP:
1632 return linearize_postop(ep, expr);
1633
1634 case EXPR_CAST:
1635 case EXPR_FORCE_CAST:
1636 case EXPR_IMPLIED_CAST:
1637 return linearize_cast(ep, expr);
1638
1639 case EXPR_SLICE:
1640 return linearize_slice(ep, expr);
1641
1642 case EXPR_INITIALIZER:
1643 case EXPR_POS:
1644 warning(expr->pos, "unexpected initializer expression (%d %d)", expr->type, expr->op);
1645 return VOID;
1646 default:
1647 warning(expr->pos, "unknown expression (%d %d)", expr->type, expr->op);
1648 return VOID;
1649 }
1650 return VOID;
1651 }
1652
1653 static pseudo_t linearize_one_symbol(struct entrypoint *ep, struct symbol *sym)
1654 {
1655 struct access_data ad = { NULL, };
1656 pseudo_t value;
1657
1658 if (!sym || !sym->initializer || sym->initialized)
1659 return VOID;
1660
1661 /* We need to output these puppies some day too.. */
1662 if (sym->ctype.modifiers & (MOD_STATIC | MOD_TOPLEVEL))
1663 return VOID;
1664
1665 sym->initialized = 1;
1666 ad.address = symbol_pseudo(ep, sym);
1667
1668 if (sym->initializer && !is_scalar_type(sym)) {
1669 // default zero initialization [6.7.9.21]
1670 // FIXME: this init the whole aggregate while
1671 // only the existing fields need to be initialized.
1672 // FIXME: this init the whole aggregate even if
1673 // all fields arelater explicitely initialized.
1674 struct expression *expr = sym->initializer;
1675 ad.pos = expr->pos;
1676 ad.result_type = sym;
1677 ad.source_type = base_type(sym);
1678 ad.address = symbol_pseudo(ep, sym);
1679 linearize_store_gen(ep, value_pseudo(0), &ad);
1680 }
1681
1682 value = linearize_initializer(ep, sym->initializer, &ad);
1683 finish_address_gen(ep, &ad);
1684 return value;
1685 }
1686
1687 static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct statement *stmt)
1688 {
1689 pseudo_t pseudo;
1690 struct statement *s;
1691 struct symbol *ret = stmt->ret;
1692
1693 pseudo = VOID;
1694 FOR_EACH_PTR(stmt->stmts, s) {
1695 pseudo = linearize_statement(ep, s);
1696 } END_FOR_EACH_PTR(s);
1697
1698 if (ret) {
1699 struct basic_block *bb = add_label(ep, ret);
1700 struct instruction *phi_node = first_instruction(bb->insns);
1701
1702 if (!phi_node)
1703 return pseudo;
1704
1705 if (pseudo_list_size(phi_node->phi_list)==1) {
1706 pseudo = first_pseudo(phi_node->phi_list);
1707 assert(pseudo->type == PSEUDO_PHI);
1708 return pseudo->def->src1;
1709 }
1710 return phi_node->target;
1711 }
1712
1713 return pseudo;
1714 }
1715
1716 static pseudo_t linearize_inlined_call(struct entrypoint *ep, struct statement *stmt)
1717 {
1718 struct instruction *insn = alloc_instruction(OP_INLINED_CALL, 0);
1719 struct statement *args = stmt->args;
1720 struct basic_block *bb;
1721 pseudo_t pseudo;
1722
1723 if (args) {
1724 struct symbol *sym;
1725
1726 concat_symbol_list(args->declaration, &ep->syms);
1727 FOR_EACH_PTR(args->declaration, sym) {
1728 pseudo_t value = linearize_one_symbol(ep, sym);
1729 use_pseudo(insn, value, add_pseudo(&insn->arguments, value));
1730 } END_FOR_EACH_PTR(sym);
1731 }
1732
1733 insn->target = pseudo = linearize_compound_statement(ep, stmt);
1734 use_pseudo(insn, symbol_pseudo(ep, stmt->inline_fn), &insn->func);
1735 bb = ep->active;
1736 if (bb && !bb->insns)
1737 bb->pos = stmt->pos;
1738 add_one_insn(ep, insn);
1739 return pseudo;
1740 }
1741
1742 static pseudo_t linearize_context(struct entrypoint *ep, struct statement *stmt)
1743 {
1744 struct instruction *insn = alloc_instruction(OP_CONTEXT, 0);
1745 struct expression *expr = stmt->expression;
1746 int value = 0;
1747
1748 if (expr->type == EXPR_VALUE)
1749 value = expr->value;
1750
1751 insn->increment = value;
1752 insn->context_expr = stmt->context;
1753 add_one_insn(ep, insn);
1754 return VOID;
1755 }
1756
1757 static pseudo_t linearize_range(struct entrypoint *ep, struct statement *stmt)
1758 {
1759 struct instruction *insn = alloc_instruction(OP_RANGE, 0);
1760
1761 use_pseudo(insn, linearize_expression(ep, stmt->range_expression), &insn->src1);
1762 use_pseudo(insn, linearize_expression(ep, stmt->range_low), &insn->src2);
1763 use_pseudo(insn, linearize_expression(ep, stmt->range_high), &insn->src3);
1764 add_one_insn(ep, insn);
1765 return VOID;
1766 }
1767
1768 ALLOCATOR(asm_rules, "asm rules");
1769 ALLOCATOR(asm_constraint, "asm constraints");
1770
1771 static void add_asm_input(struct entrypoint *ep, struct instruction *insn, struct expression *expr,
1772 const char *constraint, const struct ident *ident)
1773 {
1774 pseudo_t pseudo = linearize_expression(ep, expr);
1775 struct asm_constraint *rule = __alloc_asm_constraint(0);
1776
1777 rule->ident = ident;
1778 rule->constraint = constraint;
1779 use_pseudo(insn, pseudo, &rule->pseudo);
1780 add_ptr_list(&insn->asm_rules->inputs, rule);
1781 }
1782
1783 static void add_asm_output(struct entrypoint *ep, struct instruction *insn, struct expression *expr,
1784 const char *constraint, const struct ident *ident)
1785 {
1786 struct access_data ad = { NULL, };
1787 pseudo_t pseudo = alloc_pseudo(insn);
1788 struct asm_constraint *rule;
1789
1790 if (!expr || !linearize_address_gen(ep, expr, &ad))
1791 return;
1792 linearize_store_gen(ep, pseudo, &ad);
1793 finish_address_gen(ep, &ad);
1794 rule = __alloc_asm_constraint(0);
1795 rule->ident = ident;
1796 rule->constraint = constraint;
1797 use_pseudo(insn, pseudo, &rule->pseudo);
1798 add_ptr_list(&insn->asm_rules->outputs, rule);
1799 }
1800
1801 static pseudo_t linearize_asm_statement(struct entrypoint *ep, struct statement *stmt)
1802 {
1803 int state;
1804 struct expression *expr;
1805 struct instruction *insn;
1806 struct asm_rules *rules;
1807 const char *constraint;
1808 struct ident *ident;
1809
1810 insn = alloc_instruction(OP_ASM, 0);
1811 expr = stmt->asm_string;
1812 if (!expr || expr->type != EXPR_STRING) {
1813 warning(stmt->pos, "expected string in inline asm");
1814 return VOID;
1815 }
1816 insn->string = expr->string->data;
1817
1818 rules = __alloc_asm_rules(0);
1819 insn->asm_rules = rules;
1820
1821 /* Gather the inputs.. */
1822 state = 0;
1823 ident = NULL;
1824 constraint = NULL;
1825 FOR_EACH_PTR(stmt->asm_inputs, expr) {
1826 switch (state) {
1827 case 0: /* Identifier */
1828 state = 1;
1829 ident = (struct ident *)expr;
1830 continue;
1831
1832 case 1: /* Constraint */
1833 state = 2;
1834 constraint = expr ? expr->string->data : "";
1835 continue;
1836
1837 case 2: /* Expression */
1838 state = 0;
1839 add_asm_input(ep, insn, expr, constraint, ident);
1840 }
1841 } END_FOR_EACH_PTR(expr);
1842
1843 add_one_insn(ep, insn);
1844
1845 /* Assign the outputs */
1846 state = 0;
1847 ident = NULL;
1848 constraint = NULL;
1849 FOR_EACH_PTR(stmt->asm_outputs, expr) {
1850 switch (state) {
1851 case 0: /* Identifier */
1852 state = 1;
1853 ident = (struct ident *)expr;
1854 continue;
1855
1856 case 1: /* Constraint */
1857 state = 2;
1858 constraint = expr ? expr->string->data : "";
1859 continue;
1860
1861 case 2:
1862 state = 0;
1863 add_asm_output(ep, insn, expr, constraint, ident);
1864 }
1865 } END_FOR_EACH_PTR(expr);
1866
1867 return VOID;
1868 }
1869
1870 static int multijmp_cmp(const void *_a, const void *_b)
1871 {
1872 const struct multijmp *a = _a;
1873 const struct multijmp *b = _b;
1874
1875 // "default" case?
1876 if (a->begin > a->end) {
1877 if (b->begin > b->end)
1878 return 0;
1879 return 1;
1880 }
1881 if (b->begin > b->end)
1882 return -1;
1883 if (a->begin == b->begin) {
1884 if (a->end == b->end)
1885 return 0;
1886 return (a->end < b->end) ? -1 : 1;
1887 }
1888 return a->begin < b->begin ? -1 : 1;
1889 }
1890
1891 static void sort_switch_cases(struct instruction *insn)
1892 {
1893 sort_list((struct ptr_list **)&insn->multijmp_list, multijmp_cmp);
1894 }
1895
1896 static pseudo_t linearize_declaration(struct entrypoint *ep, struct statement *stmt)
1897 {
1898 struct symbol *sym;
1899
1900 concat_symbol_list(stmt->declaration, &ep->syms);
1901
1902 FOR_EACH_PTR(stmt->declaration, sym) {
1903 linearize_one_symbol(ep, sym);
1904 } END_FOR_EACH_PTR(sym);
1905 return VOID;
1906 }
1907
1908 static pseudo_t linearize_return(struct entrypoint *ep, struct statement *stmt)
1909 {
1910 struct expression *expr = stmt->expression;
1911 struct basic_block *bb_return = get_bound_block(ep, stmt->ret_target);
1912 struct basic_block *active;
1913 pseudo_t src = linearize_expression(ep, expr);
1914 active = ep->active;
1915 if (active && src != VOID) {
1916 struct instruction *phi_node = first_instruction(bb_return->insns);
1917 pseudo_t phi;
1918 if (!phi_node) {
1919 phi_node = alloc_typed_instruction(OP_PHI, expr->ctype);
1920 phi_node->target = alloc_pseudo(phi_node);
1921 phi_node->bb = bb_return;
1922 add_instruction(&bb_return->insns, phi_node);
1923 }
1924 phi = alloc_phi(active, src, type_size(expr->ctype));
1925 phi->ident = &return_ident;
1926 use_pseudo(phi_node, phi, add_pseudo(&phi_node->phi_list, phi));
1927 }
1928 add_goto(ep, bb_return);
1929 return VOID;
1930 }
1931
1932 static pseudo_t linearize_switch(struct entrypoint *ep, struct statement *stmt)
1933 {
1934 struct symbol *sym;
1935 struct instruction *switch_ins;
1936 struct basic_block *switch_end = alloc_basic_block(ep, stmt->pos);
1937 struct basic_block *active, *default_case;
1938 struct multijmp *jmp;
1939 pseudo_t pseudo;
1940
1941 pseudo = linearize_expression(ep, stmt->switch_expression);
1942
1943 active = ep->active;
1944 if (!bb_reachable(active))
1945 return VOID;
1946
1947 switch_ins = alloc_instruction(OP_SWITCH, 0);
1948 use_pseudo(switch_ins, pseudo, &switch_ins->cond);
1949 add_one_insn(ep, switch_ins);
1950 finish_block(ep);
1951
1952 default_case = NULL;
1953 FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) {
1954 struct statement *case_stmt = sym->stmt;
1955 struct basic_block *bb_case = get_bound_block(ep, sym);
1956
1957 if (!case_stmt->case_expression) {
1958 default_case = bb_case;
1959 continue;
1960 } else {
1961 int begin, end;
1962
1963 begin = end = case_stmt->case_expression->value;
1964 if (case_stmt->case_to)
1965 end = case_stmt->case_to->value;
1966 if (begin > end)
1967 jmp = alloc_multijmp(bb_case, end, begin);
1968 else
1969 jmp = alloc_multijmp(bb_case, begin, end);
1970
1971 }
1972 add_multijmp(&switch_ins->multijmp_list, jmp);
1973 add_bb(&bb_case->parents, active);
1974 add_bb(&active->children, bb_case);
1975 } END_FOR_EACH_PTR(sym);
1976
1977 bind_label(stmt->switch_break, switch_end, stmt->pos);
1978
1979 /* And linearize the actual statement */
1980 linearize_statement(ep, stmt->switch_statement);
1981 set_activeblock(ep, switch_end);
1982
1983 if (!default_case)
1984 default_case = switch_end;
1985
1986 jmp = alloc_multijmp(default_case, 1, 0);
1987 add_multijmp(&switch_ins->multijmp_list, jmp);
1988 add_bb(&default_case->parents, active);
1989 add_bb(&active->children, default_case);
1990 sort_switch_cases(switch_ins);
1991
1992 return VOID;
1993 }
1994
1995 static pseudo_t linearize_iterator(struct entrypoint *ep, struct statement *stmt)
1996 {
1997 struct statement *pre_statement = stmt->iterator_pre_statement;
1998 struct expression *pre_condition = stmt->iterator_pre_condition;
1999 struct statement *statement = stmt->iterator_statement;
2000 struct statement *post_statement = stmt->iterator_post_statement;
2001 struct expression *post_condition = stmt->iterator_post_condition;
2002 struct basic_block *loop_top, *loop_body, *loop_continue, *loop_end;
2003 struct symbol *sym;
2004
2005 FOR_EACH_PTR(stmt->iterator_syms, sym) {
2006 linearize_one_symbol(ep, sym);
2007 } END_FOR_EACH_PTR(sym);
2008 concat_symbol_list(stmt->iterator_syms, &ep->syms);
2009 linearize_statement(ep, pre_statement);
2010
2011 loop_body = loop_top = alloc_basic_block(ep, stmt->pos);
2012 loop_continue = alloc_basic_block(ep, stmt->pos);
2013 loop_end = alloc_basic_block(ep, stmt->pos);
2014
2015 /* An empty post-condition means that it's the same as the pre-condition */
2016 if (!post_condition) {
2017 loop_top = alloc_basic_block(ep, stmt->pos);
2018 set_activeblock(ep, loop_top);
2019 }
2020
2021 if (pre_condition)
2022 linearize_cond_branch(ep, pre_condition, loop_body, loop_end);
2023
2024 bind_label(stmt->iterator_continue, loop_continue, stmt->pos);
2025 bind_label(stmt->iterator_break, loop_end, stmt->pos);
2026
2027 set_activeblock(ep, loop_body);
2028 linearize_statement(ep, statement);
2029 add_goto(ep, loop_continue);
2030
2031 set_activeblock(ep, loop_continue);
2032 linearize_statement(ep, post_statement);
2033 if (!post_condition)
2034 add_goto(ep, loop_top);
2035 else
2036 linearize_cond_branch(ep, post_condition, loop_top, loop_end);
2037 set_activeblock(ep, loop_end);
2038
2039 return VOID;
2040 }
2041
2042 pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
2043 {
2044 struct basic_block *bb;
2045
2046 if (!stmt)
2047 return VOID;
2048
2049 bb = ep->active;
2050 if (bb && !bb->insns)
2051 bb->pos = stmt->pos;
2052 current_pos = stmt->pos;
2053
2054 switch (stmt->type) {
2055 case STMT_NONE:
2056 break;
2057
2058 case STMT_DECLARATION:
2059 return linearize_declaration(ep, stmt);
2060
2061 case STMT_CONTEXT:
2062 return linearize_context(ep, stmt);
2063
2064 case STMT_RANGE:
2065 return linearize_range(ep, stmt);
2066
2067 case STMT_EXPRESSION:
2068 return linearize_expression(ep, stmt->expression);
2069
2070 case STMT_ASM:
2071 return linearize_asm_statement(ep, stmt);
2072
2073 case STMT_RETURN:
2074 return linearize_return(ep, stmt);
2075
2076 case STMT_CASE: {
2077 add_label(ep, stmt->case_label);
2078 linearize_statement(ep, stmt->case_statement);
2079 break;
2080 }
2081
2082 case STMT_LABEL: {
2083 struct symbol *label = stmt->label_identifier;
2084
2085 if (label->used) {
2086 add_label(ep, label);
2087 }
2088 return linearize_statement(ep, stmt->label_statement);
2089 }
2090
2091 case STMT_GOTO: {
2092 struct symbol *sym;
2093 struct expression *expr;
2094 struct instruction *goto_ins;
2095 struct basic_block *active;
2096 pseudo_t pseudo;
2097
2098 active = ep->active;
2099 if (!bb_reachable(active))
2100 break;
2101
2102 if (stmt->goto_label) {
2103 add_goto(ep, get_bound_block(ep, stmt->goto_label));
2104 break;
2105 }
2106
2107 expr = stmt->goto_expression;
2108 if (!expr)
2109 break;
2110
2111 /* This can happen as part of simplification */
2112 if (expr->type == EXPR_LABEL) {
2113 add_goto(ep, get_bound_block(ep, expr->label_symbol));
2114 break;
2115 }
2116
2117 pseudo = linearize_expression(ep, expr);
2118 goto_ins = alloc_instruction(OP_COMPUTEDGOTO, 0);
2119 use_pseudo(goto_ins, pseudo, &goto_ins->target);
2120 add_one_insn(ep, goto_ins);
2121
2122 FOR_EACH_PTR(stmt->target_list, sym) {
2123 struct basic_block *bb_computed = get_bound_block(ep, sym);
2124 struct multijmp *jmp = alloc_multijmp(bb_computed, 1, 0);
2125 add_multijmp(&goto_ins->multijmp_list, jmp);
2126 add_bb(&bb_computed->parents, ep->active);
2127 add_bb(&active->children, bb_computed);
2128 } END_FOR_EACH_PTR(sym);
2129
2130 finish_block(ep);
2131 break;
2132 }
2133
2134 case STMT_COMPOUND:
2135 if (stmt->inline_fn)
2136 return linearize_inlined_call(ep, stmt);
2137 return linearize_compound_statement(ep, stmt);
2138
2139 /*
2140 * This could take 'likely/unlikely' into account, and
2141 * switch the arms around appropriately..
2142 */
2143 case STMT_IF: {
2144 struct basic_block *bb_true, *bb_false, *endif;
2145 struct expression *cond = stmt->if_conditional;
2146
2147 bb_true = alloc_basic_block(ep, stmt->pos);
2148 bb_false = endif = alloc_basic_block(ep, stmt->pos);
2149
2150 linearize_cond_branch(ep, cond, bb_true, bb_false);
2151
2152 set_activeblock(ep, bb_true);
2153 linearize_statement(ep, stmt->if_true);
2154
2155 if (stmt->if_false) {
2156 endif = alloc_basic_block(ep, stmt->pos);
2157 add_goto(ep, endif);
2158 set_activeblock(ep, bb_false);
2159 linearize_statement(ep, stmt->if_false);
2160 }
2161 set_activeblock(ep, endif);
2162 break;
2163 }
2164
2165 case STMT_SWITCH:
2166 return linearize_switch(ep, stmt);
2167
2168 case STMT_ITERATOR:
2169 return linearize_iterator(ep, stmt);
2170
2171 default:
2172 break;
2173 }
2174 return VOID;
2175 }
2176
2177 static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_type)
2178 {
2179 struct entrypoint *ep;
2180 struct basic_block *bb;
2181 struct symbol *arg;
2182 struct instruction *entry;
2183 pseudo_t result;
2184 int i;
2185
2186 if (!base_type->stmt)
2187 return NULL;
2188
2189 ep = alloc_entrypoint();
2190 bb = alloc_basic_block(ep, sym->pos);
2191
2192 ep->name = sym;
2193 sym->ep = ep;
2194 set_activeblock(ep, bb);
2195
2196 entry = alloc_instruction(OP_ENTRY, 0);
2197 add_one_insn(ep, entry);
2198 ep->entry = entry;
2199
2200 concat_symbol_list(base_type->arguments, &ep->syms);
2201
2202 /* FIXME!! We should do something else about varargs.. */
2203 i = 0;
2204 FOR_EACH_PTR(base_type->arguments, arg) {
2205 linearize_argument(ep, arg, ++i);
2206 } END_FOR_EACH_PTR(arg);
2207
2208 result = linearize_statement(ep, base_type->stmt);
2209 if (bb_reachable(ep->active) && !bb_terminated(ep->active)) {
2210 struct symbol *ret_type = base_type->ctype.base_type;
2211 struct instruction *insn = alloc_typed_instruction(OP_RET, ret_type);
2212
2213 if (type_size(ret_type) > 0)
2214 use_pseudo(insn, result, &insn->src);
2215 add_one_insn(ep, insn);
2216 }
2217
2218 if (fdump_linearize) {
2219 if (fdump_linearize == 2)
2220 return ep;
2221 show_entry(ep);
2222 }
2223
2224 /*
2225 * Do trivial flow simplification - branches to
2226 * branches, kill dead basicblocks etc
2227 */
2228 kill_unreachable_bbs(ep);
2229
2230 /*
2231 * Turn symbols into pseudos
2232 */
2233 simplify_symbol_usage(ep);
2234
2235 repeat:
2236 /*
2237 * Remove trivial instructions, and try to CSE
2238 * the rest.
2239 */
2240 do {
2241 cleanup_and_cse(ep);
2242 pack_basic_blocks(ep);
2243 } while (repeat_phase & REPEAT_CSE);
2244
2245 kill_unreachable_bbs(ep);
2246 vrfy_flow(ep);
2247
2248 /* Cleanup */
2249 clear_symbol_pseudos(ep);
2250
2251 /* And track pseudo register usage */
2252 track_pseudo_liveness(ep);
2253
2254 /*
2255 * Some flow optimizations can only effectively
2256 * be done when we've done liveness analysis. But
2257 * if they trigger, we need to start all over
2258 * again
2259 */
2260 if (simplify_flow(ep)) {
2261 clear_liveness(ep);
2262 goto repeat;
2263 }
2264
2265 /* Finally, add deathnotes to pseudos now that we have them */
2266 if (dbg_dead)
2267 track_pseudo_death(ep);
2268
2269 return ep;
2270 }
2271
2272 struct entrypoint *linearize_symbol(struct symbol *sym)
2273 {
2274 struct symbol *base_type;
2275
2276 if (!sym)
2277 return NULL;
2278 current_pos = sym->pos;
2279 base_type = sym->ctype.base_type;
2280 if (!base_type)
2281 return NULL;
2282 if (base_type->type == SYM_FN)
2283 return linearize_fn(sym, base_type);
2284 return NULL;
2285 }
Static analysis for C