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