?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Add "argument pseudo" for incoming arguments to a function.
[smatch.git] / linearize.c
blob14a1838a7fde3b3e211990197afe6b3b8fa23b47
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
18 #include "parse.h"
19 #include "expression.h"
20 #include "linearize.h"
21
22 pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt);
23 pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr);
24
25 static void add_setcc(struct entrypoint *ep, struct expression *expr, pseudo_t val);
26 static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right);
27 static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val);
28
29 struct access_data;
30 static pseudo_t add_load(struct entrypoint *ep, struct access_data *);
31 pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *);
32
33 struct pseudo void_pseudo = {};
34
35 static struct instruction *alloc_instruction(int opcode, struct symbol *type)
36 {
37 struct instruction * insn = __alloc_instruction(0);
38 insn->type = type;
39 insn->opcode = opcode;
40 return insn;
41 }
42
43 static struct entrypoint *alloc_entrypoint(void)
44 {
45 return __alloc_entrypoint(0);
46 }
47
48 static struct basic_block *alloc_basic_block(struct position pos)
49 {
50 struct basic_block *bb = __alloc_basic_block(0);
51 bb->context = -1;
52 bb->pos = pos;
53 return bb;
54 }
55
56 static struct multijmp* alloc_multijmp(struct basic_block *target, int begin, int end)
57 {
58 struct multijmp *multijmp = __alloc_multijmp(0);
59 multijmp->target = target;
60 multijmp->begin = begin;
61 multijmp->end = end;
62 return multijmp;
63 }
64
65 static struct phi* alloc_phi(struct basic_block *source, pseudo_t pseudo)
66 {
67 struct phi *phi = __alloc_phi(0);
68 phi->source = source;
69 phi->pseudo = pseudo;
70 return phi;
71 }
72
73 static inline int regno(pseudo_t n)
74 {
75 int retval = -1;
76 if (n && n->type == PSEUDO_REG)
77 retval = n->nr;
78 return retval;
79 }
80
81 static const char *show_pseudo(pseudo_t pseudo)
82 {
83 static int n;
84 static char buffer[4][64];
85 char *buf;
86
87 if (!pseudo)
88 return "no pseudo";
89 if (pseudo == VOID)
90 return "VOID";
91 buf = buffer[3 & ++n];
92 switch(pseudo->type) {
93 case PSEUDO_SYM: {
94 struct symbol *sym = pseudo->sym;
95 struct expression *expr;
96
97 if (sym->bb_target) {
98 snprintf(buf, 64, ".L%p", sym->bb_target);
99 break;
100 }
101 if (sym->ident) {
102 snprintf(buf, 64, "%s", show_ident(sym->ident));
103 break;
104 }
105 expr = sym->initializer;
106 if (!expr) {
107 snprintf(buf, 64, "<anon sym: %d>", pseudo->nr);
108 break;
109 }
110 switch (expr->type) {
111 case EXPR_VALUE:
112 snprintf(buf, 64, "<symbol value: %lld>", expr->value);
113 break;
114 case EXPR_STRING:
115 return show_string(expr->string);
116 default:
117 snprintf(buf, 64, "<symbol expression: %d>", pseudo->nr);
118 break;
119 }
120 }
121 case PSEUDO_REG:
122 snprintf(buf, 64, "%%r%d", pseudo->nr);
123 break;
124 case PSEUDO_VAL:
125 snprintf(buf, 64, "$%lld", pseudo->value);
126 break;
127 case PSEUDO_ARG:
128 snprintf(buf, 64, "%%arg%d", pseudo->nr);
129 break;
130 default:
131 snprintf(buf, 64, "<bad pseudo type %d>", pseudo->type);
132 }
133 return buf;
134 }
135
136 static void show_instruction(struct instruction *insn)
137 {
138 int op = insn->opcode;
139
140 switch (op) {
141 case OP_BADOP:
142 printf("\tAIEEE! (%s <- %s)\n", show_pseudo(insn->target), show_pseudo(insn->src));
143 break;
144 case OP_RET:
145 if (insn->type && insn->type != &void_ctype)
146 printf("\tret %s\n", show_pseudo(insn->src));
147 else
148 printf("\tret\n");
149 break;
150 case OP_BR:
151 if (insn->bb_true && insn->bb_false) {
152 printf("\tbr\t%s, .L%p, .L%p\n", show_pseudo(insn->cond), insn->bb_true, insn->bb_false);
153 break;
154 }
155 printf("\tbr\t.L%p\n", insn->bb_true ? insn->bb_true : insn->bb_false);
156 break;
157
158 case OP_SETVAL: {
159 struct expression *expr = insn->val;
160 struct symbol *sym = insn->symbol;
161 int target = regno(insn->target);
162
163 if (sym) {
164 if (sym->bb_target) {
165 printf("\t%%r%d <- .L%p\n", target, sym->bb_target);
166 break;
167 }
168 if (sym->ident) {
169 printf("\t%%r%d <- %s\n", target, show_ident(sym->ident));
170 break;
171 }
172 expr = sym->initializer;
173 if (!expr) {
174 printf("\t%%r%d <- %s\n", target, "anon symbol");
175 break;
176 }
177 }
178
179 if (!expr) {
180 printf("\t%%r%d <- %s\n", target, "<none>");
181 break;
182 }
183
184 switch (expr->type) {
185 case EXPR_VALUE:
186 printf("\t%%r%d <- %lld\n", target, expr->value);
187 break;
188 case EXPR_FVALUE:
189 printf("\t%%r%d <- %Lf\n", target, expr->fvalue);
190 break;
191 case EXPR_STRING:
192 printf("\t%%r%d <- %s\n", target, show_string(expr->string));
193 break;
194 case EXPR_SYMBOL:
195 printf("\t%%r%d <- %s\n", target, show_ident(expr->symbol->ident));
196 break;
197 case EXPR_LABEL:
198 printf("\t%%r%d <- .L%p\n", target, expr->symbol->bb_target);
199 break;
200 default:
201 printf("\t%%r%d <- SETVAL EXPR TYPE %d\n", target, expr->type);
202 }
203 break;
204 }
205 case OP_SWITCH: {
206 struct multijmp *jmp;
207 printf("\tswitch %s", show_pseudo(insn->cond));
208 FOR_EACH_PTR(insn->multijmp_list, jmp) {
209 if (jmp->begin == jmp->end)
210 printf(", %d -> .L%p", jmp->begin, jmp->target);
211 else if (jmp->begin < jmp->end)
212 printf(", %d ... %d -> .L%p", jmp->begin, jmp->end, jmp->target);
213 else
214 printf(", default -> .L%p\n", jmp->target);
215 } END_FOR_EACH_PTR(jmp);
216 printf("\n");
217 break;
218 }
219 case OP_COMPUTEDGOTO: {
220 struct multijmp *jmp;
221 printf("\tjmp *%s", show_pseudo(insn->target));
222 FOR_EACH_PTR(insn->multijmp_list, jmp) {
223 printf(", .L%p", jmp->target);
224 } END_FOR_EACH_PTR(jmp);
225 printf("\n");
226 break;
227 }
228
229 case OP_PHI: {
230 struct phi *phi;
231 const char *s = " ";
232 printf("\t%s <- phi", show_pseudo(insn->target));
233 FOR_EACH_PTR(insn->phi_list, phi) {
234 printf("%s(%s, .L%p)", s, show_pseudo(phi->pseudo), phi->source);
235 s = ", ";
236 } END_FOR_EACH_PTR(phi);
237 printf("\n");
238 break;
239 }
240 case OP_LOAD:
241 printf("\tload %s <- %d[%s]\n", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
242 break;
243 case OP_STORE:
244 printf("\tstore %s -> %d[%s]\n", show_pseudo(insn->target), insn->offset, show_pseudo(insn->src));
245 break;
246 case OP_CALL: {
247 struct pseudo *arg;
248 printf("\t%s <- CALL %s", show_pseudo(insn->target), show_pseudo(insn->func));
249 FOR_EACH_PTR(insn->arguments, arg) {
250 printf(", %s", show_pseudo(arg));
251 } END_FOR_EACH_PTR(arg);
252 printf("\n");
253 break;
254 }
255 case OP_CAST:
256 printf("\t%%r%d <- CAST(%d->%d) %s\n",
257 regno(insn->target),
258 insn->orig_type->bit_size, insn->type->bit_size,
259 show_pseudo(insn->src));
260 break;
261 case OP_BINARY ... OP_BINARY_END: {
262 static const char *opname[] = {
263 [OP_ADD - OP_BINARY] = "add", [OP_SUB - OP_BINARY] = "sub",
264 [OP_MUL - OP_BINARY] = "mul", [OP_DIV - OP_BINARY] = "div",
265 [OP_MOD - OP_BINARY] = "mod", [OP_AND - OP_BINARY] = "and",
266 [OP_OR - OP_BINARY] = "or", [OP_XOR - OP_BINARY] = "xor",
267 [OP_SHL - OP_BINARY] = "shl", [OP_SHR - OP_BINARY] = "shr",
268 [OP_AND_BOOL - OP_BINARY] = "and-bool",
269 [OP_OR_BOOL - OP_BINARY] = "or-bool",
270 [OP_SEL - OP_BINARY] = "select",
271 };
272 printf("\t%%r%d <- %s %s, %s\n",
273 regno(insn->target),
274 opname[op - OP_BINARY], show_pseudo(insn->src1), show_pseudo(insn->src2));
275 break;
276 }
277
278 case OP_SLICE:
279 printf("\t%%r%d <- slice %s, %d, %d\n",
280 regno(insn->target),
281 show_pseudo(insn->base), insn->from, insn->len);
282 break;
283
284 case OP_BINCMP ... OP_BINCMP_END: {
285 static const char *opname[] = {
286 [OP_SET_EQ - OP_BINCMP] = "seteq",
287 [OP_SET_NE - OP_BINCMP] = "setne",
288 [OP_SET_LE - OP_BINCMP] = "setle",
289 [OP_SET_GE - OP_BINCMP] = "setge",
290 [OP_SET_LT - OP_BINCMP] = "setlt",
291 [OP_SET_GT - OP_BINCMP] = "setgt",
292 [OP_SET_BE - OP_BINCMP] = "setbe",
293 [OP_SET_AE - OP_BINCMP] = "setae",
294 [OP_SET_A - OP_BINCMP] = "seta",
295 [OP_SET_B - OP_BINCMP] = "setb",
296 };
297 printf("\t%%r%d <- %s %s, %s\n",
298 regno(insn->target),
299 opname[op - OP_BINCMP], show_pseudo(insn->src1), show_pseudo(insn->src2));
300 break;
301 }
302
303 case OP_MOV:
304 printf("\t%%r%d <- %s\n",
305 regno(insn->target), show_pseudo(insn->src));
306 break;
307 case OP_NOT: case OP_NEG:
308 printf("\t%%r%d <- %s %s\n",
309 regno(insn->target),
310 op == OP_NOT ? "not" : "neg", show_pseudo(insn->src1));
311 break;
312 case OP_SETCC:
313 printf("\tsetcc %s\n", show_pseudo(insn->src));
314 break;
315 case OP_CONTEXT:
316 printf("\tcontext %d\n", insn->increment);
317 break;
318 case OP_DEAD:
319 printf("\tdeathnote %%r%d\n", regno(insn->target));
320 break;
321 default:
322 printf("\top %d ???\n", op);
323 }
324 }
325
326 static void show_bb(struct basic_block *bb)
327 {
328 struct instruction *insn;
329
330 printf("bb: %p\n", bb);
331 printf(" %s:%d:%d\n", input_streams[bb->pos.stream].name, bb->pos.line,bb->pos.pos);
332 if (bb->parents) {
333 struct basic_block *from;
334 FOR_EACH_PTR(bb->parents, from) {
335 printf(" **from %p (%s:%d:%d)**\n", from,
336 input_streams[from->pos.stream].name, from->pos.line, from->pos.pos);
337 } END_FOR_EACH_PTR(from);
338 }
339 FOR_EACH_PTR(bb->insns, insn) {
340 show_instruction(insn);
341 } END_FOR_EACH_PTR(insn);
342 if (!bb_terminated(bb))
343 printf("\tEND\n");
344 printf("\n");
345 }
346
347 static void show_uses(pseudo_t pseudo)
348 {
349 if (pseudo && pseudo->users) {
350 struct instruction *use;
351 FOR_EACH_PTR(pseudo->users, use) {
352 show_instruction(use);
353 } END_FOR_EACH_PTR(use);
354 }
355 }
356
357 void show_entry(struct entrypoint *ep)
358 {
359 struct symbol *sym;
360 struct basic_block *bb;
361
362 printf("ep %p: %s\n", ep, show_ident(ep->name->ident));
363
364 FOR_EACH_PTR(ep->syms, sym) {
365 printf(" sym: %p %s\n", sym, show_ident(sym->ident));
366 if (sym->ctype.modifiers & (MOD_EXTERN | MOD_STATIC | MOD_ADDRESSABLE))
367 printf("\texternal visibility\n");
368 show_uses(sym->pseudo);
369 } END_FOR_EACH_PTR(sym);
370
371 printf("\n");
372
373 FOR_EACH_PTR(ep->bbs, bb) {
374 if (bb == ep->entry)
375 printf("ENTRY:\n");
376 show_bb(bb);
377 } END_FOR_EACH_PTR(bb);
378
379 printf("\n");
380 }
381
382 static void bind_label(struct symbol *label, struct basic_block *bb, struct position pos)
383 {
384 if (label->bb_target)
385 warning(pos, "label '%s' already bound", show_ident(label->ident));
386 label->bb_target = bb;
387 }
388
389 static struct basic_block * get_bound_block(struct entrypoint *ep, struct symbol *label)
390 {
391 struct basic_block *bb = label->bb_target;
392
393 if (!bb) {
394 label->bb_target = bb = alloc_basic_block(label->pos);
395 bb->flags |= BB_REACHABLE;
396 }
397 return bb;
398 }
399
400 static void finish_block(struct entrypoint *ep)
401 {
402 struct basic_block *src = ep->active;
403 if (bb_reachable(src))
404 ep->active = NULL;
405 }
406
407 static void add_goto(struct entrypoint *ep, struct basic_block *dst)
408 {
409 struct basic_block *src = ep->active;
410 if (bb_reachable(src)) {
411 struct instruction *br = alloc_instruction(OP_BR, NULL);
412 br->bb_true = dst;
413 add_bb(&dst->parents, src);
414 add_instruction(&src->insns, br);
415 ep->active = NULL;
416 }
417 }
418
419 static inline void use_pseudo(struct instruction *insn, pseudo_t pseudo)
420 {
421 if (pseudo && pseudo->type != PSEUDO_VOID)
422 add_instruction(&pseudo->users, insn);
423 }
424
425 static void add_deathnote(struct entrypoint *ep, pseudo_t pseudo)
426 {
427 if (pseudo && pseudo->type == PSEUDO_REG) {
428 struct basic_block *bb = ep->active;
429 if (!--pseudo->usage && bb_reachable(bb)) {
430 struct instruction *dead = alloc_instruction(OP_DEAD, NULL);
431 dead->target = pseudo;
432 add_instruction(&bb->insns, dead);
433 }
434 }
435 }
436
437 static void add_one_insn(struct entrypoint *ep, struct instruction *insn)
438 {
439 struct basic_block *bb = ep->active;
440
441 if (bb_reachable(bb))
442 add_instruction(&bb->insns, insn);
443 }
444
445 static void set_activeblock(struct entrypoint *ep, struct basic_block *bb)
446 {
447 if (!bb_terminated(ep->active))
448 add_goto(ep, bb);
449
450 ep->active = bb;
451 if (bb_reachable(bb))
452 add_bb(&ep->bbs, bb);
453 }
454
455 static void add_setcc(struct entrypoint *ep, struct expression *expr, pseudo_t val)
456 {
457 struct basic_block *bb = ep->active;
458
459 if (bb_reachable(bb)) {
460 struct instruction *cc = alloc_instruction(OP_SETCC, &bool_ctype);
461 cc->src = val;
462 use_pseudo(cc, val);
463 add_one_insn(ep, cc);
464 }
465 }
466
467 static void add_branch(struct entrypoint *ep, struct expression *expr, pseudo_t cond, struct basic_block *bb_true, struct basic_block *bb_false)
468 {
469 struct basic_block *bb = ep->active;
470 struct instruction *br;
471
472 if (bb_reachable(bb)) {
473 br = alloc_instruction(OP_BR, expr->ctype);
474 br->cond = cond;
475 use_pseudo(br, cond);
476 br->bb_true = bb_true;
477 br->bb_false = bb_false;
478 add_bb(&bb_true->parents, bb);
479 add_bb(&bb_false->parents, bb);
480 add_one_insn(ep, br);
481 }
482 }
483
484 /* Dummy pseudo allocator */
485 static pseudo_t alloc_pseudo(struct instruction *def)
486 {
487 static int nr = 0;
488 struct pseudo * pseudo = __alloc_pseudo(0);
489 pseudo->type = PSEUDO_REG;
490 pseudo->nr = ++nr;
491 pseudo->usage = 1;
492 pseudo->def = def;
493 return pseudo;
494 }
495
496 static pseudo_t symbol_pseudo(struct symbol *sym)
497 {
498 pseudo_t pseudo = sym->pseudo;
499
500 if (!pseudo) {
501 pseudo = __alloc_pseudo(0);
502 pseudo->type = PSEUDO_SYM;
503 pseudo->sym = sym;
504 sym->pseudo = pseudo;
505 }
506 /* Symbol pseudos have neither nr, usage nor def */
507 return pseudo;
508 }
509
510 static pseudo_t value_pseudo(long long val)
511 {
512 pseudo_t pseudo = __alloc_pseudo(0);
513 pseudo->type = PSEUDO_VAL;
514 pseudo->value = val;
515 /* Value pseudos have neither nr, usage nor def */
516 return pseudo;
517 }
518
519 static pseudo_t argument_pseudo(int nr)
520 {
521 pseudo_t pseudo = __alloc_pseudo(0);
522 pseudo->type = PSEUDO_ARG;
523 pseudo->nr = nr;
524 /* Argument pseudos have neither usage nor def */
525 return pseudo;
526 }
527
528 /*
529 * We carry the "access_data" structure around for any accesses,
530 * which simplifies things a lot. It contains all the access
531 * information in one place.
532 */
533 struct access_data {
534 struct symbol *ctype;
535 pseudo_t address; // pseudo containing address ..
536 pseudo_t origval; // pseudo for original value ..
537 unsigned int offset, alignment; // byte offset
538 unsigned int bit_size, bit_offset; // which bits
539 struct position pos;
540 };
541
542 static void finish_address_gen(struct entrypoint *ep, struct access_data *ad)
543 {
544 if (ad->address && ad->address != VOID)
545 add_deathnote(ep, ad->address);
546 }
547
548 static int linearize_simple_address(struct entrypoint *ep,
549 struct expression *addr,
550 struct access_data *ad)
551 {
552 if (addr->type == EXPR_SYMBOL) {
553 ad->address = symbol_pseudo(addr->symbol);
554 return 1;
555 }
556 if (addr->type == EXPR_BINOP) {
557 if (addr->right->type == EXPR_VALUE) {
558 if (addr->op == '+') {
559 ad->offset += get_expression_value(addr->right);
560 return linearize_simple_address(ep, addr->left, ad);
561 }
562 }
563 }
564 ad->address = linearize_expression(ep, addr);
565 return 1;
566 }
567
568 static int linearize_address_gen(struct entrypoint *ep,
569 struct expression *expr,
570 struct access_data *ad)
571 {
572 struct symbol *ctype = expr->ctype;
573
574 if (!ctype)
575 return 0;
576 ad->pos = expr->pos;
577 ad->ctype = ctype;
578 ad->bit_size = ctype->bit_size;
579 ad->alignment = ctype->ctype.alignment;
580 ad->bit_offset = ctype->bit_offset;
581 if (expr->type == EXPR_PREOP && expr->op == '*')
582 return linearize_simple_address(ep, expr->unop, ad);
583
584 warning(expr->pos, "generating address of non-lvalue (%d)", expr->type);
585 return 0;
586 }
587
588 static pseudo_t add_load(struct entrypoint *ep, struct access_data *ad)
589 {
590 struct instruction *insn;
591 pseudo_t new;
592
593 new = ad->origval;
594 if (new) {
595 new->usage++;
596 return new;
597 }
598
599 insn = alloc_instruction(OP_LOAD, ad->ctype);
600 new = alloc_pseudo(insn);
601 ad->origval = new;
602
603 insn->target = new;
604 insn->src = ad->address;
605 insn->offset = ad->offset;
606 use_pseudo(insn, ad->address);
607 add_one_insn(ep, insn);
608 return new;
609 }
610
611 static void add_store(struct entrypoint *ep, struct access_data *ad, pseudo_t value)
612 {
613 struct basic_block *bb = ep->active;
614
615 if (bb_reachable(bb)) {
616 struct instruction *store = alloc_instruction(OP_STORE, ad->ctype);
617 store->target = value;
618 store->src = ad->address;
619 store->offset = ad->offset;
620 use_pseudo(store, value);
621 use_pseudo(store, ad->address);
622 add_one_insn(ep, store);
623 }
624 }
625
626 /* Target-dependent, really.. */
627 #define OFFSET_ALIGN 8
628 #define MUST_ALIGN 0
629
630 static pseudo_t linearize_store_gen(struct entrypoint *ep,
631 pseudo_t value,
632 struct access_data *ad)
633 {
634 unsigned long mask;
635 pseudo_t shifted, ormask, orig, value_mask, newval;
636
637 /* Bogus tests, but you get the idea.. */
638 if (ad->bit_offset & (OFFSET_ALIGN-1))
639 goto unaligned;
640 if (ad->bit_size & (OFFSET_ALIGN-1))
641 goto unaligned;
642 if (MUST_ALIGN && ((ad->bit_size >> 3) & (ad->alignment-1)))
643 goto unaligned;
644
645 add_store(ep, ad, value);
646 return value;
647
648 unaligned:
649 mask = ((1<<ad->bit_size)-1) << ad->bit_offset;
650 shifted = value;
651 if (ad->bit_offset) {
652 pseudo_t shift;
653 shift = value_pseudo(ad->bit_offset);
654 shifted = add_binary_op(ep, ad->ctype, OP_SHL, value, shift);
655 add_deathnote(ep, shift);
656 }
657 orig = add_load(ep, ad);
658 ormask = value_pseudo(mask);
659 value_mask = add_binary_op(ep, ad->ctype, OP_AND, shifted, ormask);
660 add_deathnote(ep, ormask);
661 if (shifted != value)
662 add_deathnote(ep, shifted);
663 newval = add_binary_op(ep, ad->ctype, OP_OR, orig, value_mask);
664 add_deathnote(ep, orig);
665 add_deathnote(ep, value_mask);
666
667 add_store(ep, ad, newval);
668 add_deathnote(ep, newval);
669 return value;
670 }
671
672 static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right)
673 {
674 struct instruction *insn = alloc_instruction(op, ctype);
675 pseudo_t target = alloc_pseudo(insn);
676 insn->target = target;
677 insn->src1 = left;
678 insn->src2 = right;
679 use_pseudo(insn, left);
680 use_pseudo(insn, right);
681 add_one_insn(ep, insn);
682 return target;
683 }
684
685 static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val)
686 {
687 struct instruction *insn = alloc_instruction(OP_SETVAL, ctype);
688 pseudo_t target = alloc_pseudo(insn);
689 insn->target = target;
690 insn->val = val;
691 if (!val)
692 insn->symbol = ctype;
693 add_one_insn(ep, insn);
694 return target;
695 }
696
697 static pseudo_t linearize_load_gen(struct entrypoint *ep, struct access_data *ad)
698 {
699 pseudo_t new = add_load(ep, ad);
700
701 if (ad->bit_offset) {
702 pseudo_t shift = value_pseudo(ad->bit_offset);
703 pseudo_t newval = add_binary_op(ep, ad->ctype, OP_SHR, new, shift);
704 add_deathnote(ep, new);
705 add_deathnote(ep, shift);
706 new = newval;
707 }
708
709 return new;
710 }
711
712 static pseudo_t linearize_access(struct entrypoint *ep, struct expression *expr)
713 {
714 struct access_data ad = { NULL, };
715 pseudo_t value;
716
717 if (!linearize_address_gen(ep, expr, &ad))
718 return VOID;
719 value = linearize_load_gen(ep, &ad);
720 finish_address_gen(ep, &ad);
721 return value;
722 }
723
724 /* FIXME: FP */
725 static pseudo_t linearize_inc_dec(struct entrypoint *ep, struct expression *expr, int postop)
726 {
727 struct access_data ad = { NULL, };
728 pseudo_t old, new, one;
729 int op = expr->op == SPECIAL_INCREMENT ? OP_ADD : OP_SUB;
730
731 if (!linearize_address_gen(ep, expr->unop, &ad))
732 return VOID;
733
734 old = linearize_load_gen(ep, &ad);
735 one = value_pseudo(1);
736 new = add_binary_op(ep, expr->ctype, op, old, one);
737 linearize_store_gen(ep, new, &ad);
738 finish_address_gen(ep, &ad);
739 if (postop) {
740 add_deathnote(ep, new);
741 return old;
742 }
743 add_deathnote(ep, old);
744 return new;
745 }
746
747 static pseudo_t add_uniop(struct entrypoint *ep, struct expression *expr, int op, pseudo_t src)
748 {
749 struct instruction *insn = alloc_instruction(op, expr->ctype);
750 pseudo_t new = alloc_pseudo(insn);
751
752 insn->target = new;
753 insn->src1 = src;
754 use_pseudo(insn, src);
755 add_one_insn(ep, insn);
756 add_deathnote(ep, src);
757 return new;
758 }
759
760 static pseudo_t linearize_slice(struct entrypoint *ep, struct expression *expr)
761 {
762 pseudo_t pre = linearize_expression(ep, expr->base);
763 struct instruction *insn = alloc_instruction(OP_SLICE, expr->ctype);
764 pseudo_t new = alloc_pseudo(insn);
765
766 insn->target = new;
767 insn->base = pre;
768 insn->from = expr->r_bitpos;
769 insn->len = expr->r_nrbits;
770 use_pseudo(insn, pre);
771 add_one_insn(ep, insn);
772 add_deathnote(ep, pre);
773 return new;
774 }
775
776 static pseudo_t linearize_regular_preop(struct entrypoint *ep, struct expression *expr)
777 {
778 pseudo_t pre = linearize_expression(ep, expr->unop);
779 switch (expr->op) {
780 case '+':
781 return pre;
782 case '!': {
783 pseudo_t zero = value_pseudo(0);
784 return add_binary_op(ep, expr->ctype, OP_SET_EQ, pre, zero);
785 }
786 case '~':
787 return add_uniop(ep, expr, OP_NOT, pre);
788 case '-':
789 return add_uniop(ep, expr, OP_NEG, pre);
790 }
791 return VOID;
792 }
793
794 static pseudo_t linearize_preop(struct entrypoint *ep, struct expression *expr)
795 {
796 /*
797 * '*' is an lvalue access, and is fundamentally different
798 * from an arithmetic operation. Maybe it should have an
799 * expression type of its own..
800 */
801 if (expr->op == '*')
802 return linearize_access(ep, expr);
803 if (expr->op == SPECIAL_INCREMENT || expr->op == SPECIAL_DECREMENT)
804 return linearize_inc_dec(ep, expr, 0);
805 return linearize_regular_preop(ep, expr);
806 }
807
808 static pseudo_t linearize_postop(struct entrypoint *ep, struct expression *expr)
809 {
810 return linearize_inc_dec(ep, expr, 1);
811 }
812
813 static pseudo_t linearize_assignment(struct entrypoint *ep, struct expression *expr)
814 {
815 struct access_data ad = { NULL, };
816 struct expression *target = expr->left;
817 pseudo_t value;
818
819 value = linearize_expression(ep, expr->right);
820 if (!linearize_address_gen(ep, target, &ad))
821 return VOID;
822 if (expr->op != '=') {
823 pseudo_t oldvalue = linearize_load_gen(ep, &ad);
824 pseudo_t dst;
825 static const int op_trans[] = {
826 [SPECIAL_ADD_ASSIGN - SPECIAL_BASE] = OP_ADD,
827 [SPECIAL_SUB_ASSIGN - SPECIAL_BASE] = OP_SUB,
828 [SPECIAL_MUL_ASSIGN - SPECIAL_BASE] = OP_MUL,
829 [SPECIAL_DIV_ASSIGN - SPECIAL_BASE] = OP_DIV,
830 [SPECIAL_MOD_ASSIGN - SPECIAL_BASE] = OP_MOD,
831 [SPECIAL_SHL_ASSIGN - SPECIAL_BASE] = OP_SHL,
832 [SPECIAL_SHR_ASSIGN - SPECIAL_BASE] = OP_SHR,
833 [SPECIAL_AND_ASSIGN - SPECIAL_BASE] = OP_AND,
834 [SPECIAL_OR_ASSIGN - SPECIAL_BASE] = OP_OR,
835 [SPECIAL_XOR_ASSIGN - SPECIAL_BASE] = OP_XOR
836 };
837 dst = add_binary_op(ep, expr->ctype, op_trans[expr->op - SPECIAL_BASE], oldvalue, value);
838 add_deathnote(ep, oldvalue);
839 add_deathnote(ep, value);
840 value = dst;
841 }
842 value = linearize_store_gen(ep, value, &ad);
843 finish_address_gen(ep, &ad);
844 return value;
845 }
846
847 static pseudo_t linearize_call_expression(struct entrypoint *ep, struct expression *expr)
848 {
849 struct expression *arg, *fn;
850 struct instruction *insn = alloc_instruction(OP_CALL, expr->ctype);
851 pseudo_t retval;
852 int context_diff;
853
854 if (!expr->ctype) {
855 warning(expr->pos, "call with no type!");
856 return VOID;
857 }
858
859 FOR_EACH_PTR(expr->args, arg) {
860 pseudo_t new = linearize_expression(ep, arg);
861 add_pseudo(&insn->arguments, new);
862 use_pseudo(insn, new);
863 } END_FOR_EACH_PTR(arg);
864
865 fn = expr->fn;
866
867 context_diff = 0;
868 if (fn->ctype) {
869 int in = fn->ctype->ctype.in_context;
870 int out = fn->ctype->ctype.out_context;
871 if (in < 0 || out < 0)
872 in = out = 0;
873 context_diff = out - in;
874 }
875
876 if (fn->type == EXPR_PREOP) {
877 if (fn->unop->type == EXPR_SYMBOL) {
878 struct symbol *sym = fn->unop->symbol;
879 if (sym->ctype.base_type->type == SYM_FN)
880 fn = fn->unop;
881 }
882 }
883 if (fn->type == EXPR_SYMBOL) {
884 insn->func = symbol_pseudo(fn->symbol);
885 } else {
886 insn->func = linearize_expression(ep, fn);
887 }
888 use_pseudo(insn, insn->func);
889 retval = VOID;
890 if (expr->ctype != &void_ctype)
891 retval = alloc_pseudo(insn);
892 insn->target = retval;
893 add_one_insn(ep, insn);
894
895 if (context_diff) {
896 insn = alloc_instruction(OP_CONTEXT, &void_ctype);
897 insn->increment = context_diff;
898 add_one_insn(ep, insn);
899 }
900
901 return retval;
902 }
903
904 static pseudo_t linearize_binop(struct entrypoint *ep, struct expression *expr)
905 {
906 pseudo_t src1, src2, dst;
907 static const int opcode[] = {
908 ['+'] = OP_ADD, ['-'] = OP_SUB,
909 ['*'] = OP_MUL, ['/'] = OP_DIV,
910 ['%'] = OP_MOD, ['&'] = OP_AND,
911 ['|'] = OP_OR, ['^'] = OP_XOR,
912 [SPECIAL_LEFTSHIFT] = OP_SHL,
913 [SPECIAL_RIGHTSHIFT] = OP_SHR,
914 [SPECIAL_LOGICAL_AND] = OP_AND_BOOL,
915 [SPECIAL_LOGICAL_OR] = OP_OR_BOOL,
916 };
917
918 src1 = linearize_expression(ep, expr->left);
919 src2 = linearize_expression(ep, expr->right);
920 dst = add_binary_op(ep, expr->ctype, opcode[expr->op], src1, src2);
921 add_deathnote(ep, src1);
922 add_deathnote(ep, src2);
923 return dst;
924 }
925
926 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
927
928 pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
929
930 static pseudo_t linearize_select(struct entrypoint *ep, struct expression *expr)
931 {
932 pseudo_t cond, true, false, res;
933
934 true = linearize_expression(ep, expr->cond_true);
935 false = linearize_expression(ep, expr->cond_false);
936 cond = linearize_expression(ep, expr->conditional);
937
938 add_setcc(ep, expr, cond);
939 if (expr->cond_true)
940 add_deathnote(ep, cond);
941 else
942 true = cond;
943 res = add_binary_op(ep, expr->ctype, OP_SEL, true, false);
944 add_deathnote(ep, true);
945 add_deathnote(ep, false);
946 return res;
947 }
948
949 static pseudo_t copy_pseudo(struct entrypoint *ep, struct expression *expr, pseudo_t src)
950 {
951 struct basic_block *bb = ep->active;
952
953 if (src->type != PSEUDO_REG)
954 return src;
955
956 if (bb_reachable(bb)) {
957 struct instruction *new = alloc_instruction(OP_MOV, expr->ctype);
958 pseudo_t dst = alloc_pseudo(src->def);
959 new->target = dst;
960 new->src = src;
961 use_pseudo(new, src);
962 add_instruction(&bb->insns, new);
963 return dst;
964 }
965 return VOID;
966 }
967
968 static pseudo_t add_join_conditional(struct entrypoint *ep, struct expression *expr,
969 pseudo_t src1, struct basic_block *bb1,
970 pseudo_t src2, struct basic_block *bb2)
971 {
972 pseudo_t target;
973 struct instruction *phi_node;
974
975 if (src1 == VOID || !bb_reachable(bb1))
976 return src2;
977 if (src2 == VOID || !bb_reachable(bb2))
978 return src1;
979 phi_node = alloc_instruction(OP_PHI, expr->ctype);
980 add_phi(&phi_node->phi_list, alloc_phi(bb1, src1));
981 add_phi(&phi_node->phi_list, alloc_phi(bb2, src2));
982 phi_node->target = target = alloc_pseudo(phi_node);
983 use_pseudo(phi_node, src1);
984 use_pseudo(phi_node, src2);
985 add_one_insn(ep, phi_node);
986 return target;
987 }
988
989 static pseudo_t linearize_short_conditional(struct entrypoint *ep, struct expression *expr,
990 struct expression *cond,
991 struct expression *expr_false)
992 {
993 pseudo_t tst, src1, src2;
994 struct basic_block *bb_true;
995 struct basic_block *bb_false = alloc_basic_block(expr_false->pos);
996 struct basic_block *merge = alloc_basic_block(expr->pos);
997
998 tst = linearize_expression(ep, cond);
999 src1 = copy_pseudo(ep, expr, tst);
1000 bb_true = ep->active;
1001 add_branch(ep, expr, tst, merge, bb_false);
1002
1003 set_activeblock(ep, bb_false);
1004 src2 = linearize_expression(ep, expr_false);
1005 bb_false = ep->active;
1006 set_activeblock(ep, merge);
1007
1008 return add_join_conditional(ep, expr, src1, bb_true, src2, bb_false);
1009 }
1010
1011 static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *expr,
1012 struct expression *cond,
1013 struct expression *expr_true,
1014 struct expression *expr_false)
1015 {
1016 pseudo_t src1, src2;
1017 struct basic_block *bb_true = alloc_basic_block(expr_true->pos);
1018 struct basic_block *bb_false = alloc_basic_block(expr_false->pos);
1019 struct basic_block *merge = alloc_basic_block(expr->pos);
1020
1021 linearize_cond_branch(ep, cond, bb_true, bb_false);
1022
1023 set_activeblock(ep, bb_true);
1024 src1 = linearize_expression(ep, expr_true);
1025 bb_true = ep->active;
1026 add_goto(ep, merge);
1027
1028 set_activeblock(ep, bb_false);
1029 src2 = linearize_expression(ep, expr_false);
1030 bb_false = ep->active;
1031 set_activeblock(ep, merge);
1032
1033 return add_join_conditional(ep, expr, src1, bb_true, src2, bb_false);
1034 }
1035
1036 static pseudo_t linearize_logical(struct entrypoint *ep, struct expression *expr)
1037 {
1038 struct expression *shortcut;
1039
1040 shortcut = alloc_const_expression(expr->pos, expr->op == SPECIAL_LOGICAL_OR);
1041 shortcut->ctype = expr->ctype;
1042 return linearize_conditional(ep, expr, expr->left, shortcut, expr->right);
1043 }
1044
1045 static pseudo_t linearize_compare(struct entrypoint *ep, struct expression *expr)
1046 {
1047 static const int cmpop[] = {
1048 ['>'] = OP_SET_GT, ['<'] = OP_SET_LT,
1049 [SPECIAL_EQUAL] = OP_SET_EQ,
1050 [SPECIAL_NOTEQUAL] = OP_SET_NE,
1051 [SPECIAL_GTE] = OP_SET_GE,
1052 [SPECIAL_LTE] = OP_SET_LE,
1053 [SPECIAL_UNSIGNED_LT] = OP_SET_B,
1054 [SPECIAL_UNSIGNED_GT] = OP_SET_A,
1055 [SPECIAL_UNSIGNED_LTE] = OP_SET_BE,
1056 [SPECIAL_UNSIGNED_GTE] = OP_SET_AE,
1057 };
1058
1059 pseudo_t src1 = linearize_expression(ep, expr->left);
1060 pseudo_t src2 = linearize_expression(ep, expr->right);
1061 pseudo_t dst = add_binary_op(ep, expr->ctype, cmpop[expr->op], src1, src2);
1062 add_deathnote(ep, src1);
1063 add_deathnote(ep, src2);
1064 return dst;
1065 }
1066
1067
1068 pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
1069 {
1070 pseudo_t cond;
1071
1072 if (!expr || !bb_reachable(ep->active))
1073 return VOID;
1074
1075 switch (expr->type) {
1076
1077 case EXPR_STRING:
1078 case EXPR_VALUE:
1079 add_goto(ep, expr->value ? bb_true : bb_false);
1080 return VOID;
1081
1082 case EXPR_FVALUE:
1083 add_goto(ep, expr->fvalue ? bb_true : bb_false);
1084 return VOID;
1085
1086 case EXPR_LOGICAL:
1087 linearize_logical_branch(ep, expr, bb_true, bb_false);
1088 return VOID;
1089
1090 case EXPR_COMPARE:
1091 cond = linearize_compare(ep, expr);
1092 add_branch(ep, expr, cond, bb_true, bb_false);
1093 break;
1094
1095 case EXPR_PREOP:
1096 if (expr->op == '!')
1097 return linearize_cond_branch(ep, expr->unop, bb_false, bb_true);
1098 /* fall through */
1099 default: {
1100 cond = linearize_expression(ep, expr);
1101 add_branch(ep, expr, cond, bb_true, bb_false);
1102
1103 return VOID;
1104 }
1105 }
1106 return VOID;
1107 }
1108
1109
1110
1111 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
1112 {
1113 struct basic_block *next = alloc_basic_block(expr->pos);
1114
1115 if (expr->op == SPECIAL_LOGICAL_OR)
1116 linearize_cond_branch(ep, expr->left, bb_true, next);
1117 else
1118 linearize_cond_branch(ep, expr->left, next, bb_false);
1119 set_activeblock(ep, next);
1120 linearize_cond_branch(ep, expr->right, bb_true, bb_false);
1121 return VOID;
1122 }
1123
1124 pseudo_t linearize_cast(struct entrypoint *ep, struct expression *expr)
1125 {
1126 pseudo_t src, result;
1127 struct instruction *insn;
1128
1129 src = linearize_expression(ep, expr->cast_expression);
1130 if (src == VOID)
1131 return VOID;
1132 if (expr->ctype->bit_size < 0) {
1133 add_deathnote(ep, src);
1134 return VOID;
1135 }
1136 insn = alloc_instruction(OP_CAST, expr->ctype);
1137 result = alloc_pseudo(insn);
1138 insn->target = result;
1139 insn->src = src;
1140 insn->orig_type = expr->cast_expression->ctype;
1141 use_pseudo(insn, src);
1142 add_one_insn(ep, insn);
1143 add_deathnote(ep, src);
1144 return result;
1145 }
1146
1147 pseudo_t linearize_position(struct entrypoint *ep, struct expression *pos, struct access_data *ad)
1148 {
1149 struct expression *init_expr = pos->init_expr;
1150 pseudo_t value = linearize_expression(ep, init_expr);
1151
1152 ad->offset = pos->init_offset;
1153 linearize_store_gen(ep, value, ad);
1154 add_deathnote(ep, value);
1155 return VOID;
1156 }
1157
1158 pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *ad)
1159 {
1160 switch (initializer->type) {
1161 case EXPR_INITIALIZER: {
1162 struct expression *expr;
1163 FOR_EACH_PTR(initializer->expr_list, expr) {
1164 linearize_initializer(ep, expr, ad);
1165 } END_FOR_EACH_PTR(expr);
1166 break;
1167 }
1168 case EXPR_POS:
1169 linearize_position(ep, initializer, ad);
1170 break;
1171 default: {
1172 pseudo_t value = linearize_expression(ep, initializer);
1173 linearize_store_gen(ep, value, ad);
1174 add_deathnote(ep, value);
1175 }
1176 }
1177
1178 return VOID;
1179 }
1180
1181 void linearize_argument(struct entrypoint *ep, struct symbol *arg, int nr)
1182 {
1183 struct access_data ad = { NULL, };
1184
1185 ad.address = symbol_pseudo(arg);
1186 linearize_store_gen(ep, argument_pseudo(nr), &ad);
1187 finish_address_gen(ep, &ad);
1188 }
1189
1190 pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr)
1191 {
1192 if (!expr)
1193 return VOID;
1194
1195 switch (expr->type) {
1196 case EXPR_SYMBOL:
1197 return add_setval(ep, expr->symbol, NULL);
1198
1199 case EXPR_VALUE:
1200 return value_pseudo(expr->value);
1201
1202 case EXPR_STRING: case EXPR_FVALUE: case EXPR_LABEL:
1203 return add_setval(ep, expr->ctype, expr);
1204
1205 case EXPR_STATEMENT:
1206 return linearize_statement(ep, expr->statement);
1207
1208 case EXPR_CALL:
1209 return linearize_call_expression(ep, expr);
1210
1211 case EXPR_BINOP:
1212 return linearize_binop(ep, expr);
1213
1214 case EXPR_LOGICAL:
1215 return linearize_logical(ep, expr);
1216
1217 case EXPR_COMPARE:
1218 return linearize_compare(ep, expr);
1219
1220 case EXPR_SELECT:
1221 return linearize_select(ep, expr);
1222
1223 case EXPR_CONDITIONAL:
1224 if (!expr->cond_true)
1225 return linearize_short_conditional(ep, expr, expr->conditional, expr->cond_false);
1226
1227 return linearize_conditional(ep, expr, expr->conditional,
1228 expr->cond_true, expr->cond_false);
1229
1230 case EXPR_COMMA: {
1231 pseudo_t left = linearize_expression(ep, expr->left);
1232 add_deathnote(ep, left);
1233 return linearize_expression(ep, expr->right);
1234 }
1235
1236 case EXPR_ASSIGNMENT:
1237 return linearize_assignment(ep, expr);
1238
1239 case EXPR_PREOP:
1240 return linearize_preop(ep, expr);
1241
1242 case EXPR_POSTOP:
1243 return linearize_postop(ep, expr);
1244
1245 case EXPR_CAST:
1246 case EXPR_IMPLIED_CAST:
1247 return linearize_cast(ep, expr);
1248
1249 case EXPR_SLICE:
1250 return linearize_slice(ep, expr);
1251
1252 case EXPR_INITIALIZER:
1253 case EXPR_POS:
1254 warning(expr->pos, "unexpected initializer expression (%d %d)", expr->type, expr->op);
1255 return VOID;
1256 default:
1257 warning(expr->pos, "unknown expression (%d %d)", expr->type, expr->op);
1258 return VOID;
1259 }
1260 return VOID;
1261 }
1262
1263 static void linearize_one_symbol(struct entrypoint *ep, struct symbol *sym)
1264 {
1265 struct access_data ad = { NULL, };
1266
1267 if (!sym->initializer)
1268 return;
1269
1270 ad.address = symbol_pseudo(sym);
1271 linearize_initializer(ep, sym->initializer, &ad);
1272 finish_address_gen(ep, &ad);
1273 }
1274
1275 static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct statement *stmt)
1276 {
1277 pseudo_t pseudo;
1278 struct statement *s;
1279 struct symbol *sym;
1280 struct symbol *ret = stmt->ret;
1281
1282 concat_symbol_list(stmt->syms, &ep->syms);
1283
1284 if (ret)
1285 ret->bb_target = alloc_basic_block(stmt->pos);
1286
1287 FOR_EACH_PTR(stmt->syms, sym) {
1288 linearize_one_symbol(ep, sym);
1289 } END_FOR_EACH_PTR(sym);
1290
1291 pseudo = VOID;
1292 FOR_EACH_PTR(stmt->stmts, s) {
1293 add_deathnote(ep, pseudo);
1294 pseudo = linearize_statement(ep, s);
1295 } END_FOR_EACH_PTR(s);
1296
1297 if (ret) {
1298 struct basic_block *bb = ret->bb_target;
1299 struct instruction *phi = first_instruction(bb->insns);
1300
1301 if (!phi)
1302 return pseudo;
1303
1304 set_activeblock(ep, bb);
1305 if (phi_list_size(phi->phi_list)==1) {
1306 pseudo = first_phi(phi->phi_list)->pseudo;
1307 delete_last_instruction(&bb->insns);
1308 return pseudo;
1309 }
1310 return phi->target;
1311 }
1312 return pseudo;
1313 }
1314
1315
1316 pseudo_t linearize_internal(struct entrypoint *ep, struct statement *stmt)
1317 {
1318 struct instruction *insn = alloc_instruction(OP_CONTEXT, &void_ctype);
1319 struct expression *expr = stmt->expression;
1320 int value = 0;
1321
1322 if (expr->type == EXPR_VALUE)
1323 value = expr->value;
1324
1325 insn->increment = value;
1326 add_one_insn(ep, insn);
1327 return VOID;
1328 }
1329
1330 pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
1331 {
1332 if (!stmt)
1333 return VOID;
1334
1335 switch (stmt->type) {
1336 case STMT_NONE:
1337 break;
1338
1339 case STMT_INTERNAL:
1340 return linearize_internal(ep, stmt);
1341
1342 case STMT_EXPRESSION:
1343 return linearize_expression(ep, stmt->expression);
1344
1345 case STMT_ASM:
1346 /* FIXME */
1347 break;
1348
1349 case STMT_RETURN: {
1350 struct expression *expr = stmt->expression;
1351 struct basic_block *bb_return = stmt->ret_target->bb_target;
1352 struct basic_block *active;
1353 pseudo_t src = linearize_expression(ep, expr);
1354 active = ep->active;
1355 add_goto(ep, bb_return);
1356 if (active && src != &void_pseudo) {
1357 struct instruction *phi_node = first_instruction(bb_return->insns);
1358 if (!phi_node) {
1359 phi_node = alloc_instruction(OP_PHI, expr->ctype);
1360 phi_node->target = alloc_pseudo(phi_node);
1361 add_instruction(&bb_return->insns, phi_node);
1362 }
1363 use_pseudo(phi_node, src);
1364 add_phi(&phi_node->phi_list, alloc_phi(active, src));
1365 }
1366 return VOID;
1367 }
1368
1369 case STMT_CASE: {
1370 struct basic_block *bb = get_bound_block(ep, stmt->case_label);
1371 set_activeblock(ep, bb);
1372 linearize_statement(ep, stmt->case_statement);
1373 break;
1374 }
1375
1376 case STMT_LABEL: {
1377 struct symbol *label = stmt->label_identifier;
1378 struct basic_block *bb;
1379
1380 if (label->used) {
1381 bb = get_bound_block(ep, stmt->label_identifier);
1382 set_activeblock(ep, bb);
1383 linearize_statement(ep, stmt->label_statement);
1384 }
1385 break;
1386 }
1387
1388 case STMT_GOTO: {
1389 struct symbol *sym;
1390 struct expression *expr;
1391 struct instruction *goto_ins;
1392 pseudo_t pseudo;
1393
1394 if (stmt->goto_label) {
1395 add_goto(ep, get_bound_block(ep, stmt->goto_label));
1396 break;
1397 }
1398
1399 expr = stmt->goto_expression;
1400 if (!expr)
1401 break;
1402
1403 /* This can happen as part of simplification */
1404 if (expr->type == EXPR_LABEL) {
1405 add_goto(ep, get_bound_block(ep, expr->label_symbol));
1406 break;
1407 }
1408
1409 pseudo = linearize_expression(ep, expr);
1410 goto_ins = alloc_instruction(OP_COMPUTEDGOTO, NULL);
1411 use_pseudo(goto_ins, pseudo);
1412 add_one_insn(ep, goto_ins);
1413 goto_ins->target = pseudo;
1414
1415 FOR_EACH_PTR(stmt->target_list, sym) {
1416 struct basic_block *bb_computed = get_bound_block(ep, sym);
1417 struct multijmp *jmp = alloc_multijmp(bb_computed, 1, 0);
1418 add_multijmp(&goto_ins->multijmp_list, jmp);
1419 add_bb(&bb_computed->parents, ep->active);
1420 } END_FOR_EACH_PTR(sym);
1421
1422 finish_block(ep);
1423 break;
1424 }
1425
1426 case STMT_COMPOUND:
1427 return linearize_compound_statement(ep, stmt);
1428
1429 /*
1430 * This could take 'likely/unlikely' into account, and
1431 * switch the arms around appropriately..
1432 */
1433 case STMT_IF: {
1434 struct basic_block *bb_true, *bb_false, *endif;
1435 struct expression *cond = stmt->if_conditional;
1436
1437 bb_true = alloc_basic_block(stmt->pos);
1438 bb_false = endif = alloc_basic_block(stmt->pos);
1439
1440 linearize_cond_branch(ep, cond, bb_true, bb_false);
1441
1442 set_activeblock(ep, bb_true);
1443 linearize_statement(ep, stmt->if_true);
1444
1445 if (stmt->if_false) {
1446 endif = alloc_basic_block(stmt->pos);
1447 add_goto(ep, endif);
1448 set_activeblock(ep, bb_false);
1449 linearize_statement(ep, stmt->if_false);
1450 }
1451 set_activeblock(ep, endif);
1452 break;
1453 }
1454
1455 case STMT_SWITCH: {
1456 struct symbol *sym;
1457 struct instruction *switch_ins;
1458 struct basic_block *switch_end = alloc_basic_block(stmt->pos);
1459 pseudo_t pseudo;
1460
1461 pseudo = linearize_expression(ep, stmt->switch_expression);
1462 switch_ins = alloc_instruction(OP_SWITCH, NULL);
1463 switch_ins->cond = pseudo;
1464 use_pseudo(switch_ins, pseudo);
1465 add_one_insn(ep, switch_ins);
1466
1467 FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) {
1468 struct statement *case_stmt = sym->stmt;
1469 struct basic_block *bb_case = get_bound_block(ep, sym);
1470 struct multijmp *jmp;
1471
1472 if (!case_stmt->case_expression) {
1473 jmp = alloc_multijmp(bb_case, 1, 0);
1474 } else {
1475 int begin, end;
1476
1477 begin = end = case_stmt->case_expression->value;
1478 if (case_stmt->case_to)
1479 end = case_stmt->case_to->value;
1480 if (begin > end)
1481 jmp = alloc_multijmp(bb_case, end, begin);
1482 else
1483 jmp = alloc_multijmp(bb_case, begin, end);
1484
1485 }
1486 add_multijmp(&switch_ins->multijmp_list, jmp);
1487 add_bb(&bb_case->parents, ep->active);
1488 } END_FOR_EACH_PTR(sym);
1489
1490 bind_label(stmt->switch_break, switch_end, stmt->pos);
1491
1492 /* And linearize the actual statement */
1493 linearize_statement(ep, stmt->switch_statement);
1494 set_activeblock(ep, switch_end);
1495
1496 break;
1497 }
1498
1499 case STMT_ITERATOR: {
1500 struct statement *pre_statement = stmt->iterator_pre_statement;
1501 struct expression *pre_condition = stmt->iterator_pre_condition;
1502 struct statement *statement = stmt->iterator_statement;
1503 struct statement *post_statement = stmt->iterator_post_statement;
1504 struct expression *post_condition = stmt->iterator_post_condition;
1505 struct basic_block *loop_top, *loop_body, *loop_continue, *loop_end;
1506
1507 concat_symbol_list(stmt->iterator_syms, &ep->syms);
1508 linearize_statement(ep, pre_statement);
1509
1510 loop_body = loop_top = alloc_basic_block(stmt->pos);
1511 loop_continue = alloc_basic_block(stmt->pos);
1512 loop_end = alloc_basic_block(stmt->pos);
1513
1514 if (pre_condition == post_condition) {
1515 loop_top = alloc_basic_block(stmt->pos);
1516 loop_top->flags |= BB_REACHABLE;
1517 set_activeblock(ep, loop_top);
1518 }
1519
1520 loop_top->flags |= BB_REACHABLE;
1521 if (pre_condition)
1522 linearize_cond_branch(ep, pre_condition, loop_body, loop_end);
1523
1524 bind_label(stmt->iterator_continue, loop_continue, stmt->pos);
1525 bind_label(stmt->iterator_break, loop_end, stmt->pos);
1526
1527 set_activeblock(ep, loop_body);
1528 linearize_statement(ep, statement);
1529 add_goto(ep, loop_continue);
1530
1531 if (post_condition) {
1532 set_activeblock(ep, loop_continue);
1533 linearize_statement(ep, post_statement);
1534 if (pre_condition == post_condition)
1535 add_goto(ep, loop_top);
1536 else
1537 linearize_cond_branch(ep, post_condition, loop_top, loop_end);
1538 }
1539
1540 set_activeblock(ep, loop_end);
1541 break;
1542 }
1543
1544 default:
1545 break;
1546 }
1547 return VOID;
1548 }
1549
1550 void mark_bb_reachable(struct basic_block *bb)
1551 {
1552 struct basic_block *child;
1553 struct terminator_iterator term;
1554 struct basic_block_list *bbstack = NULL;
1555
1556 if (!bb || bb->flags & BB_REACHABLE)
1557 return;
1558
1559 add_bb(&bbstack, bb);
1560 while (bbstack) {
1561 bb = delete_last_basic_block(&bbstack);
1562 if (bb->flags & BB_REACHABLE)
1563 continue;
1564 bb->flags |= BB_REACHABLE;
1565 init_terminator_iterator(last_instruction(bb->insns), &term);
1566 while ((child=next_terminator_bb(&term)) != NULL) {
1567 if (!(child->flags & BB_REACHABLE))
1568 add_bb(&bbstack, child);
1569 }
1570 }
1571 }
1572
1573 void remove_unreachable_bbs(struct entrypoint *ep)
1574 {
1575 struct basic_block *bb, *child;
1576 struct terminator_iterator term;
1577
1578 FOR_EACH_PTR(ep->bbs, bb) {
1579 bb->flags &= ~BB_REACHABLE;
1580 } END_FOR_EACH_PTR(bb);
1581
1582 mark_bb_reachable(ep->entry);
1583 FOR_EACH_PTR(ep->bbs, bb) {
1584 if (bb->flags & BB_REACHABLE)
1585 continue;
1586 init_terminator_iterator(last_instruction(bb->insns), &term);
1587 while ((child=next_terminator_bb(&term)) != NULL)
1588 replace_basic_block_list(child->parents, bb, NULL);
1589 DELETE_CURRENT_PTR(bb);
1590 }END_FOR_EACH_PTR(bb);
1591 }
1592
1593 void pack_basic_blocks(struct entrypoint *ep)
1594 {
1595 struct basic_block *bb;
1596
1597 remove_unreachable_bbs(ep);
1598 FOR_EACH_PTR(ep->bbs, bb) {
1599 struct terminator_iterator term;
1600 struct instruction *jmp;
1601 struct basic_block *target, *sibling, *parent;
1602 int parents;
1603
1604 if (!is_branch_goto(jmp=last_instruction(bb->insns)))
1605 continue;
1606
1607 target = jmp->bb_true ? jmp->bb_true : jmp->bb_false;
1608 if (target == bb)
1609 continue;
1610 parents = bb_list_size(target->parents);
1611 if (target == ep->entry)
1612 parents++;
1613 if (parents != 1 && jmp != first_instruction(bb->insns))
1614 continue;
1615
1616 /* Transfer the parents' terminator to target directly. */
1617 replace_basic_block_list(target->parents, bb, NULL);
1618 FOR_EACH_PTR(bb->parents, parent) {
1619 init_terminator_iterator(last_instruction(parent->insns), &term);
1620 while ((sibling=next_terminator_bb(&term)) != NULL) {
1621 if (sibling == bb) {
1622 replace_terminator_bb(&term, target);
1623 add_bb(&target->parents, parent);
1624 }
1625 }
1626 } END_FOR_EACH_PTR(parent);
1627
1628 /* Move the instructions to the target block. */
1629 delete_last_instruction(&bb->insns);
1630 if (bb->insns) {
1631 concat_instruction_list(target->insns, &bb->insns);
1632 free_instruction_list(&target->insns);
1633 target->insns = bb->insns;
1634 }
1635 if (bb == ep->entry)
1636 ep->entry = target;
1637 DELETE_CURRENT_PTR(bb);
1638 }END_FOR_EACH_PTR(bb);
1639 }
1640
1641 /*
1642 * Dammit, if we have a phi-node followed by a conditional
1643 * branch on that phi-node, we should damn well be able to
1644 * do something about the source. Maybe.
1645 */
1646 static void rewrite_branch(struct basic_block *bb,
1647 struct basic_block **ptr,
1648 struct basic_block *old,
1649 struct basic_block *new)
1650 {
1651 *ptr = new;
1652 add_bb(&new->parents, bb);
1653 /*
1654 * FIXME!!! We should probably also remove bb from "old->parents",
1655 * but we need to be careful that bb isn't a parent some other way.
1656 */
1657 }
1658
1659 /*
1660 * Return the known truth value of a pseudo, or -1 if
1661 * it's not known.
1662 */
1663 static int pseudo_truth_value(pseudo_t pseudo)
1664 {
1665 switch (pseudo->type) {
1666 case PSEUDO_VAL:
1667 return !!pseudo->value;
1668
1669 case PSEUDO_REG: {
1670 struct instruction *insn = pseudo->def;
1671 if (insn->opcode == OP_SETVAL && insn->target == pseudo) {
1672 struct expression *expr = insn->val;
1673
1674 /* A symbol address is always considered true.. */
1675 if (!expr)
1676 return 1;
1677 if (expr->type == EXPR_VALUE)
1678 return !!expr->value;
1679 }
1680 }
1681 /* Fall through */
1682 default:
1683 return -1;
1684 }
1685 }
1686
1687
1688 static void try_to_simplify_bb(struct entrypoint *ep, struct basic_block *bb,
1689 struct instruction *first, struct instruction *second)
1690 {
1691 struct phi *phi;
1692
1693 FOR_EACH_PTR(first->phi_list, phi) {
1694 struct basic_block *source = phi->source, *target;
1695 pseudo_t pseudo = phi->pseudo;
1696 struct instruction *br;
1697 int true;
1698
1699 br = last_instruction(source->insns);
1700 if (!br)
1701 continue;
1702 if (br->opcode != OP_BR)
1703 continue;
1704
1705 true = pseudo_truth_value(pseudo);
1706 if (true < 0)
1707 continue;
1708 target = true ? second->bb_true : second->bb_false;
1709 if (br->bb_true == bb)
1710 rewrite_branch(source, &br->bb_true, bb, target);
1711 if (br->bb_false == bb)
1712 rewrite_branch(source, &br->bb_false, bb, target);
1713 } END_FOR_EACH_PTR(phi);
1714 }
1715
1716 static inline int linearize_insn_list(struct instruction_list *list, struct instruction **arr, int nr)
1717 {
1718 return linearize_ptr_list((struct ptr_list *)list, (void **)arr, nr);
1719 }
1720
1721 static void simplify_phi_nodes(struct entrypoint *ep)
1722 {
1723 struct basic_block *bb;
1724
1725 FOR_EACH_PTR(ep->bbs, bb) {
1726 struct instruction *insns[2], *first, *second;
1727
1728 if (linearize_insn_list(bb->insns, insns, 2) < 2)
1729 continue;
1730
1731 first = insns[0];
1732 second = insns[1];
1733
1734 if (first->opcode != OP_PHI)
1735 continue;
1736 if (second->opcode != OP_BR)
1737 continue;
1738 if (first->target != second->cond)
1739 continue;
1740 try_to_simplify_bb(ep, bb, first, second);
1741 } END_FOR_EACH_PTR(bb);
1742 }
1743
1744 static void create_phi_copy(struct basic_block *bb, struct instruction *phi,
1745 pseudo_t src, pseudo_t dst)
1746 {
1747 struct instruction *insn = last_instruction(bb->insns);
1748 struct instruction *new = alloc_instruction(OP_MOV, phi->type);
1749
1750 delete_last_instruction(&bb->insns);
1751 new->target = dst;
1752 new->src = src;
1753 use_pseudo(new, src);
1754 add_instruction(&bb->insns, new);
1755
1756 if (src->type == PSEUDO_REG) {
1757 struct instruction *dead = alloc_instruction(OP_DEAD, NULL);
1758 dead->target = src;
1759 add_instruction(&bb->insns, dead);
1760 }
1761
1762 /* And add back the last instruction */
1763 add_instruction(&bb->insns, insn);
1764 }
1765
1766 static void remove_one_phi_node(struct entrypoint *ep,
1767 struct basic_block *bb,
1768 struct instruction *insn)
1769 {
1770 struct phi *node;
1771 pseudo_t target = insn->target;
1772
1773 FOR_EACH_PTR(insn->phi_list, node) {
1774 create_phi_copy(node->source, insn, node->pseudo, target);
1775 } END_FOR_EACH_PTR(node);
1776 }
1777
1778 static void remove_phi_nodes(struct entrypoint *ep)
1779 {
1780 struct basic_block *bb;
1781 FOR_EACH_PTR(ep->bbs, bb) {
1782 struct instruction *insn = first_instruction(bb->insns);
1783 if (insn && insn->opcode == OP_PHI)
1784 remove_one_phi_node(ep, bb, insn);
1785 } END_FOR_EACH_PTR(bb);
1786 }
1787
1788 struct entrypoint *linearize_symbol(struct symbol *sym)
1789 {
1790 struct symbol *base_type;
1791 struct entrypoint *ret_ep = NULL;
1792
1793 if (!sym)
1794 return NULL;
1795 base_type = sym->ctype.base_type;
1796 if (!base_type)
1797 return NULL;
1798 if (base_type->type == SYM_FN) {
1799 if (base_type->stmt) {
1800 struct entrypoint *ep = alloc_entrypoint();
1801 struct basic_block *bb = alloc_basic_block(sym->pos);
1802 struct symbol *arg;
1803 pseudo_t result;
1804 int i;
1805
1806 ep->name = sym;
1807 ep->entry = bb;
1808 bb->flags |= BB_REACHABLE;
1809 set_activeblock(ep, bb);
1810 concat_symbol_list(base_type->arguments, &ep->syms);
1811
1812 /* FIXME!! We should do something else about varargs.. */
1813 i = 0;
1814 FOR_EACH_PTR(base_type->arguments, arg) {
1815 linearize_argument(ep, arg, ++i);
1816 } END_FOR_EACH_PTR(arg);
1817
1818 result = linearize_statement(ep, base_type->stmt);
1819 if (bb_reachable(ep->active) && !bb_terminated(ep->active)) {
1820 struct symbol *ret_type = base_type->ctype.base_type;
1821 struct instruction *insn = alloc_instruction(OP_RET, ret_type);
1822
1823 insn->src = result;
1824 use_pseudo(insn, result);
1825 add_one_insn(ep, insn);
1826 }
1827
1828 /*
1829 * Questionable conditional branch simplification.
1830 * This short-circuits branches to conditional branches,
1831 * and leaves the phi-nodes "dangling" in the old
1832 * basic block - the nodes are no longer attached to
1833 * where the uses are. But it can still be considered
1834 * SSA if you just look at it sideways..
1835 */
1836 simplify_phi_nodes(ep);
1837
1838 /*
1839 * WARNING!! The removal of phi nodes will make the
1840 * tree no longer valid SSA format. We do it here
1841 * to make the linearized code look more like real
1842 * assembly code, but we should do all the SSA-based
1843 * optimizations (CSE etc) _before_ this point.
1844 */
1845 remove_phi_nodes(ep);
1846
1847 pack_basic_blocks(ep);
1848
1849 ret_ep = ep;
1850 }
1851 }
1852
1853 return ret_ep;
1854 }
Static analysis for C