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