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