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