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