?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Make "value_pseudo()" always return the same pseudo for
[smatch.git] / linearize.c
blobac4f8fa72e810fd4a0278c9a1bbe210d5f439f70
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 <stddef.h>
18
19 #include "parse.h"
20 #include "expression.h"
21 #include "linearize.h"
22
23 pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt);
24 pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr);
25
26 static void add_setcc(struct entrypoint *ep, struct expression *expr, pseudo_t val);
27 static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right);
28 static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val);
29
30 struct access_data;
31 static pseudo_t add_load(struct entrypoint *ep, struct access_data *);
32 pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *);
33
34 struct pseudo void_pseudo = {};
35
36 unsigned long bb_generation;
37
38 static struct instruction *alloc_instruction(int opcode, struct symbol *type)
39 {
40 struct instruction * insn = __alloc_instruction(0);
41 insn->type = type;
42 insn->opcode = opcode;
43 return insn;
44 }
45
46 static struct entrypoint *alloc_entrypoint(void)
47 {
48 bb_generation = 0;
49 return __alloc_entrypoint(0);
50 }
51
52 static struct basic_block *alloc_basic_block(struct position pos)
53 {
54 struct basic_block *bb = __alloc_basic_block(0);
55 bb->context = -1;
56 bb->pos = pos;
57 return bb;
58 }
59
60 static struct multijmp* alloc_multijmp(struct basic_block *target, int begin, int end)
61 {
62 struct multijmp *multijmp = __alloc_multijmp(0);
63 multijmp->target = target;
64 multijmp->begin = begin;
65 multijmp->end = end;
66 return multijmp;
67 }
68
69 static inline void add_pseudo_ptr(pseudo_t *ptr, struct pseudo_ptr_list **list)
70 {
71 add_ptr_list((struct ptr_list **)list, ptr);
72 }
73
74 static inline void use_pseudo(pseudo_t p, pseudo_t *pp)
75 {
76 *pp = p;
77 if (p && p->type != PSEUDO_VOID)
78 add_pseudo_ptr(pp, &p->users);
79 }
80
81 static struct phi* alloc_phi(struct basic_block *source, pseudo_t pseudo)
82 {
83 struct phi *phi = __alloc_phi(0);
84 phi->source = source;
85 add_phi(&source->phinodes, phi);
86 use_pseudo(pseudo, &phi->pseudo);
87 return phi;
88 }
89
90 static inline int regno(pseudo_t n)
91 {
92 int retval = -1;
93 if (n && n->type == PSEUDO_REG)
94 retval = n->nr;
95 return retval;
96 }
97
98 static const char *show_pseudo(pseudo_t pseudo)
99 {
100 static int n;
101 static char buffer[4][64];
102 char *buf;
103
104 if (!pseudo)
105 return "no pseudo";
106 if (pseudo == VOID)
107 return "VOID";
108 buf = buffer[3 & ++n];
109 switch(pseudo->type) {
110 case PSEUDO_SYM: {
111 struct symbol *sym = pseudo->sym;
112 struct expression *expr;
113
114 if (sym->bb_target) {
115 snprintf(buf, 64, ".L%p", sym->bb_target);
116 break;
117 }
118 if (sym->ident) {
119 snprintf(buf, 64, "%s:%p", show_ident(sym->ident), sym);
120 break;
121 }
122 expr = sym->initializer;
123 if (!expr) {
124 snprintf(buf, 64, "<anon sym: %d>", pseudo->nr);
125 break;
126 }
127 switch (expr->type) {
128 case EXPR_VALUE:
129 snprintf(buf, 64, "<symbol value: %lld>", expr->value);
130 break;
131 case EXPR_STRING:
132 return show_string(expr->string);
133 default:
134 snprintf(buf, 64, "<symbol expression: %d>", pseudo->nr);
135 break;
136 }
137 }
138 case PSEUDO_REG:
139 snprintf(buf, 64, "%%r%d", pseudo->nr);
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 default:
153 snprintf(buf, 64, "<bad pseudo type %d>", pseudo->type);
154 }
155 return buf;
156 }
157
158 static void show_instruction(struct instruction *insn)
159 {
160 int op = insn->opcode;
161
162 switch (op) {
163 case OP_BADOP:
164 printf("\tAIEEE! (%s <- %s)\n", show_pseudo(insn->target), show_pseudo(insn->src));
165 break;
166 case OP_RET:
167 if (insn->type && insn->type != &void_ctype)
168 printf("\tret %s\n", show_pseudo(insn->src));
169 else
170 printf("\tret\n");
171 break;
172 case OP_BR:
173 if (insn->bb_true && insn->bb_false) {
174 printf("\tbr\t%s, .L%p, .L%p\n", show_pseudo(insn->cond), insn->bb_true, insn->bb_false);
175 break;
176 }
177 printf("\tbr\t.L%p\n", insn->bb_true ? insn->bb_true : insn->bb_false);
178 break;
179
180 case OP_SETVAL: {
181 struct expression *expr = insn->val;
182 struct symbol *sym = insn->symbol;
183 int target = regno(insn->target);
184
185 if (sym) {
186 if (sym->bb_target) {
187 printf("\t%%r%d <- .L%p\n", target, sym->bb_target);
188 break;
189 }
190 if (sym->ident) {
191 printf("\t%%r%d <- %s\n", target, show_ident(sym->ident));
192 break;
193 }
194 expr = sym->initializer;
195 if (!expr) {
196 printf("\t%%r%d <- %s\n", target, "anon symbol");
197 break;
198 }
199 }
200
201 if (!expr) {
202 printf("\t%%r%d <- %s\n", target, "<none>");
203 break;
204 }
205
206 switch (expr->type) {
207 case EXPR_VALUE:
208 printf("\t%%r%d <- %lld\n", target, expr->value);
209 break;
210 case EXPR_FVALUE:
211 printf("\t%%r%d <- %Lf\n", target, expr->fvalue);
212 break;
213 case EXPR_STRING:
214 printf("\t%%r%d <- %s\n", target, show_string(expr->string));
215 break;
216 case EXPR_SYMBOL:
217 printf("\t%%r%d <- %s\n", target, show_ident(expr->symbol->ident));
218 break;
219 case EXPR_LABEL:
220 printf("\t%%r%d <- .L%p\n", target, expr->symbol->bb_target);
221 break;
222 default:
223 printf("\t%%r%d <- SETVAL EXPR TYPE %d\n", target, expr->type);
224 }
225 break;
226 }
227 case OP_SWITCH: {
228 struct multijmp *jmp;
229 printf("\tswitch %s", show_pseudo(insn->cond));
230 FOR_EACH_PTR(insn->multijmp_list, jmp) {
231 if (jmp->begin == jmp->end)
232 printf(", %d -> .L%p", jmp->begin, jmp->target);
233 else if (jmp->begin < jmp->end)
234 printf(", %d ... %d -> .L%p", jmp->begin, jmp->end, jmp->target);
235 else
236 printf(", default -> .L%p\n", jmp->target);
237 } END_FOR_EACH_PTR(jmp);
238 printf("\n");
239 break;
240 }
241 case OP_COMPUTEDGOTO: {
242 struct multijmp *jmp;
243 printf("\tjmp *%s", show_pseudo(insn->target));
244 FOR_EACH_PTR(insn->multijmp_list, jmp) {
245 printf(", .L%p", jmp->target);
246 } END_FOR_EACH_PTR(jmp);
247 printf("\n");
248 break;
249 }
250
251 case OP_PHI: {
252 struct phi *phi;
253 const char *s = " ";
254 printf("\t%s <- phi", show_pseudo(insn->target));
255 FOR_EACH_PTR(insn->phi_list, phi) {
256 printf("%s(%s, .L%p)", s, show_pseudo(phi->pseudo), phi->source);
257 s = ", ";
258 } END_FOR_EACH_PTR(phi);
259 printf("\n");
260 break;
261 }
262 case OP_LOAD:
263 printf("\tload %s <- %d.%d.%d[%s]\n", show_pseudo(insn->target), insn->offset,
264 insn->type->bit_offset, insn->type->bit_size, show_pseudo(insn->src));
265 break;
266 case OP_STORE:
267 printf("\tstore %s -> %d.%d.%d[%s]\n", show_pseudo(insn->target), insn->offset,
268 insn->type->bit_offset, insn->type->bit_size, show_pseudo(insn->src));
269 break;
270 case OP_CALL: {
271 struct pseudo *arg;
272 printf("\t%s <- CALL %s", show_pseudo(insn->target), show_pseudo(insn->func));
273 FOR_EACH_PTR(insn->arguments, arg) {
274 printf(", %s", show_pseudo(arg));
275 } END_FOR_EACH_PTR(arg);
276 printf("\n");
277 break;
278 }
279 case OP_CAST:
280 printf("\t%%r%d <- CAST(%d->%d) %s\n",
281 regno(insn->target),
282 insn->orig_type->bit_size, insn->type->bit_size,
283 show_pseudo(insn->src));
284 break;
285 case OP_BINARY ... OP_BINARY_END: {
286 static const char *opname[] = {
287 [OP_ADD - OP_BINARY] = "add", [OP_SUB - OP_BINARY] = "sub",
288 [OP_MUL - OP_BINARY] = "mul", [OP_DIV - OP_BINARY] = "div",
289 [OP_MOD - OP_BINARY] = "mod", [OP_AND - OP_BINARY] = "and",
290 [OP_OR - OP_BINARY] = "or", [OP_XOR - OP_BINARY] = "xor",
291 [OP_SHL - OP_BINARY] = "shl", [OP_SHR - OP_BINARY] = "shr",
292 [OP_AND_BOOL - OP_BINARY] = "and-bool",
293 [OP_OR_BOOL - OP_BINARY] = "or-bool",
294 [OP_SEL - OP_BINARY] = "select",
295 };
296 printf("\t%%r%d <- %s %s, %s\n",
297 regno(insn->target),
298 opname[op - OP_BINARY], show_pseudo(insn->src1), show_pseudo(insn->src2));
299 break;
300 }
301
302 case OP_SLICE:
303 printf("\t%%r%d <- slice %s, %d, %d\n",
304 regno(insn->target),
305 show_pseudo(insn->base), insn->from, insn->len);
306 break;
307
308 case OP_BINCMP ... OP_BINCMP_END: {
309 static const char *opname[] = {
310 [OP_SET_EQ - OP_BINCMP] = "seteq",
311 [OP_SET_NE - OP_BINCMP] = "setne",
312 [OP_SET_LE - OP_BINCMP] = "setle",
313 [OP_SET_GE - OP_BINCMP] = "setge",
314 [OP_SET_LT - OP_BINCMP] = "setlt",
315 [OP_SET_GT - OP_BINCMP] = "setgt",
316 [OP_SET_BE - OP_BINCMP] = "setbe",
317 [OP_SET_AE - OP_BINCMP] = "setae",
318 [OP_SET_A - OP_BINCMP] = "seta",
319 [OP_SET_B - OP_BINCMP] = "setb",
320 };
321 printf("\t%%r%d <- %s %s, %s\n",
322 regno(insn->target),
323 opname[op - OP_BINCMP], show_pseudo(insn->src1), show_pseudo(insn->src2));
324 break;
325 }
326
327 case OP_NOT: case OP_NEG:
328 printf("\t%%r%d <- %s %s\n",
329 regno(insn->target),
330 op == OP_NOT ? "not" : "neg", show_pseudo(insn->src1));
331 break;
332 case OP_SETCC:
333 printf("\tsetcc %s\n", show_pseudo(insn->src));
334 break;
335 case OP_CONTEXT:
336 printf("\tcontext %d\n", insn->increment);
337 break;
338 case OP_SNOP:
339 printf("\tnop (%s -> %d.%d.%d[%s])\n", show_pseudo(insn->target), insn->offset,
340 insn->type->bit_offset, insn->type->bit_size, show_pseudo(insn->src));
341 break;
342 case OP_LNOP:
343 printf("\tnop (%s <- %d.%d.%d[%s])\n", show_pseudo(insn->target), insn->offset,
344 insn->type->bit_offset, insn->type->bit_size, show_pseudo(insn->src));
345 break;
346 default:
347 printf("\top %d ???\n", op);
348 }
349 }
350
351 static void show_bb(struct basic_block *bb)
352 {
353 struct instruction *insn;
354
355 printf("bb: %p\n", bb);
356 printf(" %s:%d:%d\n", input_streams[bb->pos.stream].name, bb->pos.line,bb->pos.pos);
357
358 if (bb->parents) {
359 struct basic_block *from;
360 FOR_EACH_PTR(bb->parents, from) {
361 printf(" **from %p (%s:%d:%d)**\n", from,
362 input_streams[from->pos.stream].name, from->pos.line, from->pos.pos);
363 } END_FOR_EACH_PTR(from);
364 }
365
366 if (bb->children) {
367 struct basic_block *to;
368 FOR_EACH_PTR(bb->children, to) {
369 printf(" **to %p (%s:%d:%d)**\n", to,
370 input_streams[to->pos.stream].name, to->pos.line, to->pos.pos);
371 } END_FOR_EACH_PTR(to);
372 }
373
374 if (bb->phinodes) {
375 struct phi *phi;
376 FOR_EACH_PTR(bb->phinodes, phi) {
377 printf(" **phi source %s**\n", show_pseudo(phi->pseudo));
378 } END_FOR_EACH_PTR(phi);
379 }
380
381 FOR_EACH_PTR(bb->insns, insn) {
382 show_instruction(insn);
383 } END_FOR_EACH_PTR(insn);
384 if (!bb_terminated(bb))
385 printf("\tEND\n");
386 printf("\n");
387 }
388
389 #define container(ptr, type, member) \
390 (type *)((void *)(ptr) - offsetof(type, member))
391
392 static void show_symbol_usage(pseudo_t pseudo)
393 {
394 if (pseudo) {
395 pseudo_t *pp;
396 FOR_EACH_PTR(pseudo->users, pp) {
397 struct instruction *insn = container(pp, struct instruction, src);
398 show_instruction(insn);
399 } END_FOR_EACH_PTR(pp);
400 }
401 }
402
403 void show_entry(struct entrypoint *ep)
404 {
405 struct symbol *sym;
406 struct basic_block *bb;
407
408 printf("ep %p: %s\n", ep, show_ident(ep->name->ident));
409
410 FOR_EACH_PTR(ep->syms, sym) {
411 printf(" sym: %p %s\n", sym, show_ident(sym->ident));
412 if (sym->ctype.modifiers & (MOD_EXTERN | MOD_STATIC | MOD_ADDRESSABLE))
413 printf("\texternal visibility\n");
414 show_symbol_usage(sym->pseudo);
415 } END_FOR_EACH_PTR(sym);
416
417 printf("\n");
418
419 FOR_EACH_PTR(ep->bbs, bb) {
420 if (!bb)
421 continue;
422 if (bb == ep->entry)
423 printf("ENTRY:\n");
424 show_bb(bb);
425 } END_FOR_EACH_PTR(bb);
426
427 printf("\n");
428 }
429
430 static void bind_label(struct symbol *label, struct basic_block *bb, struct position pos)
431 {
432 if (label->bb_target)
433 warning(pos, "label '%s' already bound", show_ident(label->ident));
434 label->bb_target = bb;
435 }
436
437 static struct basic_block * get_bound_block(struct entrypoint *ep, struct symbol *label)
438 {
439 struct basic_block *bb = label->bb_target;
440
441 if (!bb) {
442 bb = alloc_basic_block(label->pos);
443 label->bb_target = bb;
444 }
445 return bb;
446 }
447
448 static void finish_block(struct entrypoint *ep)
449 {
450 struct basic_block *src = ep->active;
451 if (bb_reachable(src))
452 ep->active = NULL;
453 }
454
455 static void add_goto(struct entrypoint *ep, struct basic_block *dst)
456 {
457 struct basic_block *src = ep->active;
458 if (bb_reachable(src)) {
459 struct instruction *br = alloc_instruction(OP_BR, NULL);
460 br->bb_true = dst;
461 add_bb(&dst->parents, src);
462 add_bb(&src->children, dst);
463 br->bb = src;
464 add_instruction(&src->insns, br);
465 ep->active = NULL;
466 }
467 }
468
469 static void add_one_insn(struct entrypoint *ep, struct instruction *insn)
470 {
471 struct basic_block *bb = ep->active;
472
473 if (bb_reachable(bb)) {
474 insn->bb = bb;
475 add_instruction(&bb->insns, insn);
476 }
477 }
478
479 static void set_activeblock(struct entrypoint *ep, struct basic_block *bb)
480 {
481 if (!bb_terminated(ep->active))
482 add_goto(ep, bb);
483
484 ep->active = bb;
485 if (bb_reachable(bb))
486 add_bb(&ep->bbs, bb);
487 }
488
489 static inline int bb_empty(struct basic_block *bb)
490 {
491 return !bb->insns && !bb->phinodes;
492 }
493
494 /* Add a label to the currently active block, return new active block */
495 static struct basic_block * add_label(struct entrypoint *ep, struct symbol *label)
496 {
497 struct basic_block *bb = label->bb_target;
498
499 if (bb) {
500 set_activeblock(ep, bb);
501 return bb;
502 }
503 bb = ep->active;
504 if (!bb_reachable(bb) || !bb_empty(bb)) {
505 bb = alloc_basic_block(label->pos);
506 set_activeblock(ep, bb);
507 }
508 label->bb_target = bb;
509 return bb;
510 }
511
512 static void add_setcc(struct entrypoint *ep, struct expression *expr, pseudo_t val)
513 {
514 struct basic_block *bb = ep->active;
515
516 if (bb_reachable(bb)) {
517 struct instruction *cc = alloc_instruction(OP_SETCC, &bool_ctype);
518 use_pseudo(val, &cc->src);
519 add_one_insn(ep, cc);
520 }
521 }
522
523 static void add_branch(struct entrypoint *ep, struct expression *expr, pseudo_t cond, struct basic_block *bb_true, struct basic_block *bb_false)
524 {
525 struct basic_block *bb = ep->active;
526 struct instruction *br;
527
528 if (bb_reachable(bb)) {
529 br = alloc_instruction(OP_BR, expr->ctype);
530 use_pseudo(cond, &br->cond);
531 br->bb_true = bb_true;
532 br->bb_false = bb_false;
533 add_bb(&bb_true->parents, bb);
534 add_bb(&bb_false->parents, bb);
535 add_bb(&bb->children, bb_true);
536 add_bb(&bb->children, bb_false);
537 add_one_insn(ep, br);
538 }
539 }
540
541 /* Dummy pseudo allocator */
542 static pseudo_t alloc_pseudo(struct instruction *def)
543 {
544 static int nr = 0;
545 struct pseudo * pseudo = __alloc_pseudo(0);
546 pseudo->type = PSEUDO_REG;
547 pseudo->nr = ++nr;
548 pseudo->usage = 1;
549 pseudo->def = def;
550 return pseudo;
551 }
552
553 static pseudo_t symbol_pseudo(struct entrypoint *ep, struct symbol *sym)
554 {
555 pseudo_t pseudo = sym->pseudo;
556
557 if (!pseudo) {
558 pseudo = __alloc_pseudo(0);
559 pseudo->type = PSEUDO_SYM;
560 pseudo->sym = sym;
561 sym->pseudo = pseudo;
562 add_symbol(&ep->accesses, sym);
563 }
564 /* Symbol pseudos have neither nr, usage nor def */
565 return pseudo;
566 }
567
568 static pseudo_t value_pseudo(long long val)
569 {
570 #define MAX_VAL_HASH 64
571 static struct pseudo_list *prev[MAX_VAL_HASH];
572 int hash = val & (MAX_VAL_HASH-1);
573 struct pseudo_list **list = prev + hash;
574 pseudo_t pseudo;
575
576 FOR_EACH_PTR(*list, pseudo) {
577 if (pseudo->value == val)
578 return pseudo;
579 } END_FOR_EACH_PTR(pseudo);
580
581 pseudo = __alloc_pseudo(0);
582 pseudo->type = PSEUDO_VAL;
583 pseudo->value = val;
584 add_pseudo(list, pseudo);
585
586 /* Value pseudos have neither nr, usage nor def */
587 return pseudo;
588 }
589
590 static pseudo_t argument_pseudo(int nr)
591 {
592 pseudo_t pseudo = __alloc_pseudo(0);
593 pseudo->type = PSEUDO_ARG;
594 pseudo->nr = nr;
595 /* Argument pseudos have neither usage nor def */
596 return pseudo;
597 }
598
599 /*
600 * We carry the "access_data" structure around for any accesses,
601 * which simplifies things a lot. It contains all the access
602 * information in one place.
603 */
604 struct access_data {
605 struct symbol *ctype;
606 pseudo_t address; // pseudo containing address ..
607 pseudo_t origval; // pseudo for original value ..
608 unsigned int offset, alignment; // byte offset
609 unsigned int bit_size, bit_offset; // which bits
610 struct position pos;
611 };
612
613 static void finish_address_gen(struct entrypoint *ep, struct access_data *ad)
614 {
615 }
616
617 static int linearize_simple_address(struct entrypoint *ep,
618 struct expression *addr,
619 struct access_data *ad)
620 {
621 if (addr->type == EXPR_SYMBOL) {
622 ad->address = symbol_pseudo(ep, addr->symbol);
623 return 1;
624 }
625 if (addr->type == EXPR_BINOP) {
626 if (addr->right->type == EXPR_VALUE) {
627 if (addr->op == '+') {
628 ad->offset += get_expression_value(addr->right);
629 return linearize_simple_address(ep, addr->left, ad);
630 }
631 }
632 }
633 ad->address = linearize_expression(ep, addr);
634 return 1;
635 }
636
637 static int linearize_address_gen(struct entrypoint *ep,
638 struct expression *expr,
639 struct access_data *ad)
640 {
641 struct symbol *ctype = expr->ctype;
642
643 if (!ctype)
644 return 0;
645 ad->pos = expr->pos;
646 ad->ctype = ctype;
647 ad->bit_size = ctype->bit_size;
648 ad->alignment = ctype->ctype.alignment;
649 ad->bit_offset = ctype->bit_offset;
650 if (expr->type == EXPR_PREOP && expr->op == '*')
651 return linearize_simple_address(ep, expr->unop, ad);
652
653 warning(expr->pos, "generating address of non-lvalue (%d)", expr->type);
654 return 0;
655 }
656
657 static pseudo_t add_load(struct entrypoint *ep, struct access_data *ad)
658 {
659 struct instruction *insn;
660 pseudo_t new;
661
662 new = ad->origval;
663 if (new) {
664 new->usage++;
665 return new;
666 }
667
668 insn = alloc_instruction(OP_LOAD, ad->ctype);
669 new = alloc_pseudo(insn);
670 ad->origval = new;
671
672 insn->target = new;
673 insn->offset = ad->offset;
674 use_pseudo(ad->address, &insn->src);
675 add_one_insn(ep, insn);
676 return new;
677 }
678
679 static void add_store(struct entrypoint *ep, struct access_data *ad, pseudo_t value)
680 {
681 struct basic_block *bb = ep->active;
682
683 if (bb_reachable(bb)) {
684 struct instruction *store = alloc_instruction(OP_STORE, ad->ctype);
685 store->offset = ad->offset;
686 use_pseudo(value, &store->target);
687 use_pseudo(ad->address, &store->src);
688 add_one_insn(ep, store);
689 }
690 }
691
692 /* Target-dependent, really.. */
693 #define OFFSET_ALIGN 8
694 #define MUST_ALIGN 0
695
696 static struct symbol *base_type(struct symbol *s)
697 {
698 if (s->type == SYM_NODE)
699 s = s->ctype.base_type;
700 if (s->type == SYM_BITFIELD)
701 s = s->ctype.base_type;
702 return s;
703 }
704
705 static pseudo_t linearize_store_gen(struct entrypoint *ep,
706 pseudo_t value,
707 struct access_data *ad)
708 {
709 unsigned long mask;
710 pseudo_t shifted, ormask, orig, value_mask, newval;
711
712 /* Bogus tests, but you get the idea.. */
713 if (ad->bit_offset & (OFFSET_ALIGN-1))
714 goto unaligned;
715 if (ad->bit_size & (ad->bit_size-1))
716 goto unaligned;
717 if (ad->bit_size & (OFFSET_ALIGN-1))
718 goto unaligned;
719 if (MUST_ALIGN && ((ad->bit_size >> 3) & (ad->alignment-1)))
720 goto unaligned;
721
722 add_store(ep, ad, value);
723 return value;
724
725 unaligned:
726 mask = ((1<<ad->bit_size)-1) << ad->bit_offset;
727 shifted = value;
728 if (ad->bit_offset) {
729 pseudo_t shift;
730 shift = value_pseudo(ad->bit_offset);
731 shifted = add_binary_op(ep, ad->ctype, OP_SHL, value, shift);
732 }
733 ad->ctype = base_type(ad->ctype);
734 orig = add_load(ep, ad);
735 ormask = value_pseudo(~mask);
736 value_mask = add_binary_op(ep, ad->ctype, OP_AND, orig, ormask);
737 newval = add_binary_op(ep, ad->ctype, OP_OR, orig, value_mask);
738
739 add_store(ep, ad, newval);
740 return value;
741 }
742
743 static pseudo_t add_binary_op(struct entrypoint *ep, struct symbol *ctype, int op, pseudo_t left, pseudo_t right)
744 {
745 struct instruction *insn = alloc_instruction(op, ctype);
746 pseudo_t target = alloc_pseudo(insn);
747 insn->target = target;
748 use_pseudo(left, &insn->src1);
749 use_pseudo(right, &insn->src2);
750 add_one_insn(ep, insn);
751 return target;
752 }
753
754 static pseudo_t add_setval(struct entrypoint *ep, struct symbol *ctype, struct expression *val)
755 {
756 struct instruction *insn = alloc_instruction(OP_SETVAL, ctype);
757 pseudo_t target = alloc_pseudo(insn);
758 insn->target = target;
759 insn->val = val;
760 if (!val)
761 insn->symbol = ctype;
762 add_one_insn(ep, insn);
763 return target;
764 }
765
766 static pseudo_t linearize_load_gen(struct entrypoint *ep, struct access_data *ad)
767 {
768 pseudo_t new = add_load(ep, ad);
769
770 if (ad->bit_offset) {
771 pseudo_t shift = value_pseudo(ad->bit_offset);
772 pseudo_t newval = add_binary_op(ep, ad->ctype, OP_SHR, new, shift);
773 new = newval;
774 }
775
776 return new;
777 }
778
779 static pseudo_t linearize_access(struct entrypoint *ep, struct expression *expr)
780 {
781 struct access_data ad = { NULL, };
782 pseudo_t value;
783
784 if (!linearize_address_gen(ep, expr, &ad))
785 return VOID;
786 value = linearize_load_gen(ep, &ad);
787 finish_address_gen(ep, &ad);
788 return value;
789 }
790
791 /* FIXME: FP */
792 static pseudo_t linearize_inc_dec(struct entrypoint *ep, struct expression *expr, int postop)
793 {
794 struct access_data ad = { NULL, };
795 pseudo_t old, new, one;
796 int op = expr->op == SPECIAL_INCREMENT ? OP_ADD : OP_SUB;
797
798 if (!linearize_address_gen(ep, expr->unop, &ad))
799 return VOID;
800
801 old = linearize_load_gen(ep, &ad);
802 one = value_pseudo(1);
803 new = add_binary_op(ep, expr->ctype, op, old, one);
804 linearize_store_gen(ep, new, &ad);
805 finish_address_gen(ep, &ad);
806 return postop ? old : new;
807 }
808
809 static pseudo_t add_uniop(struct entrypoint *ep, struct expression *expr, int op, pseudo_t src)
810 {
811 struct instruction *insn = alloc_instruction(op, expr->ctype);
812 pseudo_t new = alloc_pseudo(insn);
813
814 insn->target = new;
815 use_pseudo(src, &insn->src1);
816 add_one_insn(ep, insn);
817 return new;
818 }
819
820 static pseudo_t linearize_slice(struct entrypoint *ep, struct expression *expr)
821 {
822 pseudo_t pre = linearize_expression(ep, expr->base);
823 struct instruction *insn = alloc_instruction(OP_SLICE, expr->ctype);
824 pseudo_t new = alloc_pseudo(insn);
825
826 insn->target = new;
827 insn->from = expr->r_bitpos;
828 insn->len = expr->r_nrbits;
829 use_pseudo(pre, &insn->base);
830 add_one_insn(ep, insn);
831 return new;
832 }
833
834 static pseudo_t linearize_regular_preop(struct entrypoint *ep, struct expression *expr)
835 {
836 pseudo_t pre = linearize_expression(ep, expr->unop);
837 switch (expr->op) {
838 case '+':
839 return pre;
840 case '!': {
841 pseudo_t zero = value_pseudo(0);
842 return add_binary_op(ep, expr->ctype, OP_SET_EQ, pre, zero);
843 }
844 case '~':
845 return add_uniop(ep, expr, OP_NOT, pre);
846 case '-':
847 return add_uniop(ep, expr, OP_NEG, pre);
848 }
849 return VOID;
850 }
851
852 static pseudo_t linearize_preop(struct entrypoint *ep, struct expression *expr)
853 {
854 /*
855 * '*' is an lvalue access, and is fundamentally different
856 * from an arithmetic operation. Maybe it should have an
857 * expression type of its own..
858 */
859 if (expr->op == '*')
860 return linearize_access(ep, expr);
861 if (expr->op == SPECIAL_INCREMENT || expr->op == SPECIAL_DECREMENT)
862 return linearize_inc_dec(ep, expr, 0);
863 return linearize_regular_preop(ep, expr);
864 }
865
866 static pseudo_t linearize_postop(struct entrypoint *ep, struct expression *expr)
867 {
868 return linearize_inc_dec(ep, expr, 1);
869 }
870
871 static pseudo_t linearize_assignment(struct entrypoint *ep, struct expression *expr)
872 {
873 struct access_data ad = { NULL, };
874 struct expression *target = expr->left;
875 pseudo_t value;
876
877 value = linearize_expression(ep, expr->right);
878 if (!linearize_address_gen(ep, target, &ad))
879 return VOID;
880 if (expr->op != '=') {
881 pseudo_t oldvalue = linearize_load_gen(ep, &ad);
882 pseudo_t dst;
883 static const int op_trans[] = {
884 [SPECIAL_ADD_ASSIGN - SPECIAL_BASE] = OP_ADD,
885 [SPECIAL_SUB_ASSIGN - SPECIAL_BASE] = OP_SUB,
886 [SPECIAL_MUL_ASSIGN - SPECIAL_BASE] = OP_MUL,
887 [SPECIAL_DIV_ASSIGN - SPECIAL_BASE] = OP_DIV,
888 [SPECIAL_MOD_ASSIGN - SPECIAL_BASE] = OP_MOD,
889 [SPECIAL_SHL_ASSIGN - SPECIAL_BASE] = OP_SHL,
890 [SPECIAL_SHR_ASSIGN - SPECIAL_BASE] = OP_SHR,
891 [SPECIAL_AND_ASSIGN - SPECIAL_BASE] = OP_AND,
892 [SPECIAL_OR_ASSIGN - SPECIAL_BASE] = OP_OR,
893 [SPECIAL_XOR_ASSIGN - SPECIAL_BASE] = OP_XOR
894 };
895 dst = add_binary_op(ep, expr->ctype, op_trans[expr->op - SPECIAL_BASE], oldvalue, value);
896 value = dst;
897 }
898 value = linearize_store_gen(ep, value, &ad);
899 finish_address_gen(ep, &ad);
900 return value;
901 }
902
903 static pseudo_t linearize_call_expression(struct entrypoint *ep, struct expression *expr)
904 {
905 struct expression *arg, *fn;
906 struct instruction *insn = alloc_instruction(OP_CALL, expr->ctype);
907 pseudo_t retval, call;
908 int context_diff;
909
910 if (!expr->ctype) {
911 warning(expr->pos, "call with no type!");
912 return VOID;
913 }
914
915 FOR_EACH_PTR(expr->args, arg) {
916 pseudo_t new = linearize_expression(ep, arg);
917 use_pseudo(new, add_pseudo(&insn->arguments, new));
918 } END_FOR_EACH_PTR(arg);
919
920 fn = expr->fn;
921
922 context_diff = 0;
923 if (fn->ctype) {
924 int in = fn->ctype->ctype.in_context;
925 int out = fn->ctype->ctype.out_context;
926 if (in < 0 || out < 0)
927 in = out = 0;
928 context_diff = out - in;
929 }
930
931 if (fn->type == EXPR_PREOP) {
932 if (fn->unop->type == EXPR_SYMBOL) {
933 struct symbol *sym = fn->unop->symbol;
934 if (sym->ctype.base_type->type == SYM_FN)
935 fn = fn->unop;
936 }
937 }
938 if (fn->type == EXPR_SYMBOL) {
939 call = symbol_pseudo(ep, fn->symbol);
940 } else {
941 call = linearize_expression(ep, fn);
942 }
943 use_pseudo(call, &insn->func);
944 retval = VOID;
945 if (expr->ctype != &void_ctype)
946 retval = alloc_pseudo(insn);
947 insn->target = retval;
948 add_one_insn(ep, insn);
949
950 if (context_diff) {
951 insn = alloc_instruction(OP_CONTEXT, &void_ctype);
952 insn->increment = context_diff;
953 add_one_insn(ep, insn);
954 }
955
956 return retval;
957 }
958
959 static pseudo_t linearize_binop(struct entrypoint *ep, struct expression *expr)
960 {
961 pseudo_t src1, src2, dst;
962 static const int opcode[] = {
963 ['+'] = OP_ADD, ['-'] = OP_SUB,
964 ['*'] = OP_MUL, ['/'] = OP_DIV,
965 ['%'] = OP_MOD, ['&'] = OP_AND,
966 ['|'] = OP_OR, ['^'] = OP_XOR,
967 [SPECIAL_LEFTSHIFT] = OP_SHL,
968 [SPECIAL_RIGHTSHIFT] = OP_SHR,
969 [SPECIAL_LOGICAL_AND] = OP_AND_BOOL,
970 [SPECIAL_LOGICAL_OR] = OP_OR_BOOL,
971 };
972
973 src1 = linearize_expression(ep, expr->left);
974 src2 = linearize_expression(ep, expr->right);
975 dst = add_binary_op(ep, expr->ctype, opcode[expr->op], src1, src2);
976 return dst;
977 }
978
979 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
980
981 pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false);
982
983 static pseudo_t linearize_select(struct entrypoint *ep, struct expression *expr)
984 {
985 pseudo_t cond, true, false, res;
986
987 true = linearize_expression(ep, expr->cond_true);
988 false = linearize_expression(ep, expr->cond_false);
989 cond = linearize_expression(ep, expr->conditional);
990
991 add_setcc(ep, expr, cond);
992 if (!expr->cond_true)
993 true = cond;
994 res = add_binary_op(ep, expr->ctype, OP_SEL, true, false);
995 return res;
996 }
997
998 static pseudo_t add_join_conditional(struct entrypoint *ep, struct expression *expr,
999 pseudo_t src1, struct basic_block *bb1,
1000 pseudo_t src2, struct basic_block *bb2)
1001 {
1002 pseudo_t target;
1003 struct instruction *phi_node;
1004 struct phi *phi1, *phi2;
1005
1006 if (src1 == VOID || !bb_reachable(bb1))
1007 return src2;
1008 if (src2 == VOID || !bb_reachable(bb2))
1009 return src1;
1010 phi_node = alloc_instruction(OP_PHI, expr->ctype);
1011 phi1 = alloc_phi(bb1, src1);
1012 phi2 = alloc_phi(bb2, src2);
1013 add_phi(&phi_node->phi_list, phi1);
1014 add_phi(&phi_node->phi_list, phi2);
1015 phi_node->target = target = alloc_pseudo(phi_node);
1016 add_one_insn(ep, phi_node);
1017 return target;
1018 }
1019
1020 static pseudo_t linearize_short_conditional(struct entrypoint *ep, struct expression *expr,
1021 struct expression *cond,
1022 struct expression *expr_false)
1023 {
1024 pseudo_t src1, src2;
1025 struct basic_block *bb_true;
1026 struct basic_block *bb_false = alloc_basic_block(expr_false->pos);
1027 struct basic_block *merge = alloc_basic_block(expr->pos);
1028
1029 src1 = linearize_expression(ep, cond);
1030 bb_true = ep->active;
1031 add_branch(ep, expr, src1, merge, bb_false);
1032
1033 set_activeblock(ep, bb_false);
1034 src2 = linearize_expression(ep, expr_false);
1035 bb_false = ep->active;
1036 set_activeblock(ep, merge);
1037
1038 return add_join_conditional(ep, expr, src1, bb_true, src2, bb_false);
1039 }
1040
1041 static pseudo_t linearize_conditional(struct entrypoint *ep, struct expression *expr,
1042 struct expression *cond,
1043 struct expression *expr_true,
1044 struct expression *expr_false)
1045 {
1046 pseudo_t src1, src2;
1047 struct basic_block *bb_true = alloc_basic_block(expr_true->pos);
1048 struct basic_block *bb_false = alloc_basic_block(expr_false->pos);
1049 struct basic_block *merge = alloc_basic_block(expr->pos);
1050
1051 linearize_cond_branch(ep, cond, bb_true, bb_false);
1052
1053 set_activeblock(ep, bb_true);
1054 src1 = linearize_expression(ep, expr_true);
1055 bb_true = ep->active;
1056 add_goto(ep, merge);
1057
1058 set_activeblock(ep, bb_false);
1059 src2 = linearize_expression(ep, expr_false);
1060 bb_false = ep->active;
1061 set_activeblock(ep, merge);
1062
1063 return add_join_conditional(ep, expr, src1, bb_true, src2, bb_false);
1064 }
1065
1066 static pseudo_t linearize_logical(struct entrypoint *ep, struct expression *expr)
1067 {
1068 struct expression *shortcut;
1069
1070 shortcut = alloc_const_expression(expr->pos, expr->op == SPECIAL_LOGICAL_OR);
1071 shortcut->ctype = expr->ctype;
1072 return linearize_conditional(ep, expr, expr->left, shortcut, expr->right);
1073 }
1074
1075 static pseudo_t linearize_compare(struct entrypoint *ep, struct expression *expr)
1076 {
1077 static const int cmpop[] = {
1078 ['>'] = OP_SET_GT, ['<'] = OP_SET_LT,
1079 [SPECIAL_EQUAL] = OP_SET_EQ,
1080 [SPECIAL_NOTEQUAL] = OP_SET_NE,
1081 [SPECIAL_GTE] = OP_SET_GE,
1082 [SPECIAL_LTE] = OP_SET_LE,
1083 [SPECIAL_UNSIGNED_LT] = OP_SET_B,
1084 [SPECIAL_UNSIGNED_GT] = OP_SET_A,
1085 [SPECIAL_UNSIGNED_LTE] = OP_SET_BE,
1086 [SPECIAL_UNSIGNED_GTE] = OP_SET_AE,
1087 };
1088
1089 pseudo_t src1 = linearize_expression(ep, expr->left);
1090 pseudo_t src2 = linearize_expression(ep, expr->right);
1091 pseudo_t dst = add_binary_op(ep, expr->ctype, cmpop[expr->op], src1, src2);
1092 return dst;
1093 }
1094
1095
1096 pseudo_t linearize_cond_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
1097 {
1098 pseudo_t cond;
1099
1100 if (!expr || !bb_reachable(ep->active))
1101 return VOID;
1102
1103 switch (expr->type) {
1104
1105 case EXPR_STRING:
1106 case EXPR_VALUE:
1107 add_goto(ep, expr->value ? bb_true : bb_false);
1108 return VOID;
1109
1110 case EXPR_FVALUE:
1111 add_goto(ep, expr->fvalue ? bb_true : bb_false);
1112 return VOID;
1113
1114 case EXPR_LOGICAL:
1115 linearize_logical_branch(ep, expr, bb_true, bb_false);
1116 return VOID;
1117
1118 case EXPR_COMPARE:
1119 cond = linearize_compare(ep, expr);
1120 add_branch(ep, expr, cond, bb_true, bb_false);
1121 break;
1122
1123 case EXPR_PREOP:
1124 if (expr->op == '!')
1125 return linearize_cond_branch(ep, expr->unop, bb_false, bb_true);
1126 /* fall through */
1127 default: {
1128 cond = linearize_expression(ep, expr);
1129 add_branch(ep, expr, cond, bb_true, bb_false);
1130
1131 return VOID;
1132 }
1133 }
1134 return VOID;
1135 }
1136
1137
1138
1139 static pseudo_t linearize_logical_branch(struct entrypoint *ep, struct expression *expr, struct basic_block *bb_true, struct basic_block *bb_false)
1140 {
1141 struct basic_block *next = alloc_basic_block(expr->pos);
1142
1143 if (expr->op == SPECIAL_LOGICAL_OR)
1144 linearize_cond_branch(ep, expr->left, bb_true, next);
1145 else
1146 linearize_cond_branch(ep, expr->left, next, bb_false);
1147 set_activeblock(ep, next);
1148 linearize_cond_branch(ep, expr->right, bb_true, bb_false);
1149 return VOID;
1150 }
1151
1152 pseudo_t linearize_cast(struct entrypoint *ep, struct expression *expr)
1153 {
1154 pseudo_t src, result;
1155 struct instruction *insn;
1156
1157 src = linearize_expression(ep, expr->cast_expression);
1158 if (src == VOID)
1159 return VOID;
1160 if (expr->ctype->bit_size < 0)
1161 return VOID;
1162 insn = alloc_instruction(OP_CAST, expr->ctype);
1163 result = alloc_pseudo(insn);
1164 insn->target = result;
1165 insn->orig_type = expr->cast_expression->ctype;
1166 use_pseudo(src, &insn->src);
1167 add_one_insn(ep, insn);
1168 return result;
1169 }
1170
1171 pseudo_t linearize_position(struct entrypoint *ep, struct expression *pos, struct access_data *ad)
1172 {
1173 struct expression *init_expr = pos->init_expr;
1174 pseudo_t value = linearize_expression(ep, init_expr);
1175
1176 ad->offset = pos->init_offset;
1177 ad->ctype = init_expr->ctype;
1178 linearize_store_gen(ep, value, ad);
1179 return VOID;
1180 }
1181
1182 pseudo_t linearize_initializer(struct entrypoint *ep, struct expression *initializer, struct access_data *ad)
1183 {
1184 switch (initializer->type) {
1185 case EXPR_INITIALIZER: {
1186 struct expression *expr;
1187 FOR_EACH_PTR(initializer->expr_list, expr) {
1188 linearize_initializer(ep, expr, ad);
1189 } END_FOR_EACH_PTR(expr);
1190 break;
1191 }
1192 case EXPR_POS:
1193 linearize_position(ep, initializer, ad);
1194 break;
1195 default: {
1196 pseudo_t value = linearize_expression(ep, initializer);
1197 ad->ctype = initializer->ctype;
1198 linearize_store_gen(ep, value, ad);
1199 }
1200 }
1201
1202 return VOID;
1203 }
1204
1205 void linearize_argument(struct entrypoint *ep, struct symbol *arg, int nr)
1206 {
1207 struct access_data ad = { NULL, };
1208
1209 ad.ctype = arg;
1210 ad.address = symbol_pseudo(ep, arg);
1211 linearize_store_gen(ep, argument_pseudo(nr), &ad);
1212 finish_address_gen(ep, &ad);
1213 }
1214
1215 pseudo_t linearize_expression(struct entrypoint *ep, struct expression *expr)
1216 {
1217 if (!expr)
1218 return VOID;
1219
1220 switch (expr->type) {
1221 case EXPR_SYMBOL:
1222 return add_setval(ep, expr->symbol, NULL);
1223
1224 case EXPR_VALUE:
1225 return value_pseudo(expr->value);
1226
1227 case EXPR_STRING: case EXPR_FVALUE: case EXPR_LABEL:
1228 return add_setval(ep, expr->ctype, expr);
1229
1230 case EXPR_STATEMENT:
1231 return linearize_statement(ep, expr->statement);
1232
1233 case EXPR_CALL:
1234 return linearize_call_expression(ep, expr);
1235
1236 case EXPR_BINOP:
1237 return linearize_binop(ep, expr);
1238
1239 case EXPR_LOGICAL:
1240 return linearize_logical(ep, expr);
1241
1242 case EXPR_COMPARE:
1243 return linearize_compare(ep, expr);
1244
1245 case EXPR_SELECT:
1246 return linearize_select(ep, expr);
1247
1248 case EXPR_CONDITIONAL:
1249 if (!expr->cond_true)
1250 return linearize_short_conditional(ep, expr, expr->conditional, expr->cond_false);
1251
1252 return linearize_conditional(ep, expr, expr->conditional,
1253 expr->cond_true, expr->cond_false);
1254
1255 case EXPR_COMMA:
1256 linearize_expression(ep, expr->left);
1257 return linearize_expression(ep, expr->right);
1258
1259 case EXPR_ASSIGNMENT:
1260 return linearize_assignment(ep, expr);
1261
1262 case EXPR_PREOP:
1263 return linearize_preop(ep, expr);
1264
1265 case EXPR_POSTOP:
1266 return linearize_postop(ep, expr);
1267
1268 case EXPR_CAST:
1269 case EXPR_IMPLIED_CAST:
1270 return linearize_cast(ep, expr);
1271
1272 case EXPR_SLICE:
1273 return linearize_slice(ep, expr);
1274
1275 case EXPR_INITIALIZER:
1276 case EXPR_POS:
1277 warning(expr->pos, "unexpected initializer expression (%d %d)", expr->type, expr->op);
1278 return VOID;
1279 default:
1280 warning(expr->pos, "unknown expression (%d %d)", expr->type, expr->op);
1281 return VOID;
1282 }
1283 return VOID;
1284 }
1285
1286 static void linearize_one_symbol(struct entrypoint *ep, struct symbol *sym)
1287 {
1288 struct access_data ad = { NULL, };
1289
1290 if (!sym->initializer)
1291 return;
1292
1293 ad.address = symbol_pseudo(ep, sym);
1294 linearize_initializer(ep, sym->initializer, &ad);
1295 finish_address_gen(ep, &ad);
1296 }
1297
1298 static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct statement *stmt)
1299 {
1300 pseudo_t pseudo;
1301 struct statement *s;
1302 struct symbol *sym;
1303 struct symbol *ret = stmt->ret;
1304
1305 concat_symbol_list(stmt->syms, &ep->syms);
1306
1307 FOR_EACH_PTR(stmt->syms, sym) {
1308 linearize_one_symbol(ep, sym);
1309 } END_FOR_EACH_PTR(sym);
1310
1311 pseudo = VOID;
1312 FOR_EACH_PTR(stmt->stmts, s) {
1313 pseudo = linearize_statement(ep, s);
1314 } END_FOR_EACH_PTR(s);
1315
1316 if (ret) {
1317 struct basic_block *bb = add_label(ep, ret);
1318 struct instruction *phi = first_instruction(bb->insns);
1319
1320 if (!phi)
1321 return pseudo;
1322
1323 if (phi_list_size(phi->phi_list)==1) {
1324 pseudo = first_phi(phi->phi_list)->pseudo;
1325 delete_last_instruction(&bb->insns);
1326 return pseudo;
1327 }
1328 return phi->target;
1329 }
1330 return pseudo;
1331 }
1332
1333
1334 pseudo_t linearize_internal(struct entrypoint *ep, struct statement *stmt)
1335 {
1336 struct instruction *insn = alloc_instruction(OP_CONTEXT, &void_ctype);
1337 struct expression *expr = stmt->expression;
1338 int value = 0;
1339
1340 if (expr->type == EXPR_VALUE)
1341 value = expr->value;
1342
1343 insn->increment = value;
1344 add_one_insn(ep, insn);
1345 return VOID;
1346 }
1347
1348 pseudo_t linearize_statement(struct entrypoint *ep, struct statement *stmt)
1349 {
1350 if (!stmt)
1351 return VOID;
1352
1353 switch (stmt->type) {
1354 case STMT_NONE:
1355 break;
1356
1357 case STMT_INTERNAL:
1358 return linearize_internal(ep, stmt);
1359
1360 case STMT_EXPRESSION:
1361 return linearize_expression(ep, stmt->expression);
1362
1363 case STMT_ASM:
1364 /* FIXME */
1365 break;
1366
1367 case STMT_RETURN: {
1368 struct expression *expr = stmt->expression;
1369 struct basic_block *bb_return = get_bound_block(ep, stmt->ret_target);
1370 struct basic_block *active;
1371 pseudo_t src = linearize_expression(ep, expr);
1372 active = ep->active;
1373 add_goto(ep, bb_return);
1374 if (active && src != &void_pseudo) {
1375 struct instruction *phi_node = first_instruction(bb_return->insns);
1376 struct phi *phi;
1377 if (!phi_node) {
1378 phi_node = alloc_instruction(OP_PHI, expr->ctype);
1379 phi_node->target = alloc_pseudo(phi_node);
1380 phi_node->bb = bb_return;
1381 add_instruction(&bb_return->insns, phi_node);
1382 }
1383 phi = alloc_phi(active, src);
1384 add_phi(&phi_node->phi_list, phi);
1385 }
1386 return VOID;
1387 }
1388
1389 case STMT_CASE: {
1390 add_label(ep, stmt->case_label);
1391 linearize_statement(ep, stmt->case_statement);
1392 break;
1393 }
1394
1395 case STMT_LABEL: {
1396 struct symbol *label = stmt->label_identifier;
1397
1398 if (label->used) {
1399 add_label(ep, label);
1400 linearize_statement(ep, stmt->label_statement);
1401 }
1402 break;
1403 }
1404
1405 case STMT_GOTO: {
1406 struct symbol *sym;
1407 struct expression *expr;
1408 struct instruction *goto_ins;
1409 struct basic_block *active;
1410 pseudo_t pseudo;
1411
1412 active = ep->active;
1413 if (!bb_reachable(active))
1414 break;
1415
1416 if (stmt->goto_label) {
1417 add_goto(ep, get_bound_block(ep, stmt->goto_label));
1418 break;
1419 }
1420
1421 expr = stmt->goto_expression;
1422 if (!expr)
1423 break;
1424
1425 /* This can happen as part of simplification */
1426 if (expr->type == EXPR_LABEL) {
1427 add_goto(ep, get_bound_block(ep, expr->label_symbol));
1428 break;
1429 }
1430
1431 pseudo = linearize_expression(ep, expr);
1432 goto_ins = alloc_instruction(OP_COMPUTEDGOTO, NULL);
1433 use_pseudo(pseudo, &goto_ins->target);
1434 add_one_insn(ep, goto_ins);
1435
1436 FOR_EACH_PTR(stmt->target_list, sym) {
1437 struct basic_block *bb_computed = get_bound_block(ep, sym);
1438 struct multijmp *jmp = alloc_multijmp(bb_computed, 1, 0);
1439 add_multijmp(&goto_ins->multijmp_list, jmp);
1440 add_bb(&bb_computed->parents, ep->active);
1441 add_bb(&active->children, bb_computed);
1442 } END_FOR_EACH_PTR(sym);
1443
1444 finish_block(ep);
1445 break;
1446 }
1447
1448 case STMT_COMPOUND:
1449 return linearize_compound_statement(ep, stmt);
1450
1451 /*
1452 * This could take 'likely/unlikely' into account, and
1453 * switch the arms around appropriately..
1454 */
1455 case STMT_IF: {
1456 struct basic_block *bb_true, *bb_false, *endif;
1457 struct expression *cond = stmt->if_conditional;
1458
1459 bb_true = alloc_basic_block(stmt->pos);
1460 bb_false = endif = alloc_basic_block(stmt->pos);
1461
1462 linearize_cond_branch(ep, cond, bb_true, bb_false);
1463
1464 set_activeblock(ep, bb_true);
1465 linearize_statement(ep, stmt->if_true);
1466
1467 if (stmt->if_false) {
1468 endif = alloc_basic_block(stmt->pos);
1469 add_goto(ep, endif);
1470 set_activeblock(ep, bb_false);
1471 linearize_statement(ep, stmt->if_false);
1472 }
1473 set_activeblock(ep, endif);
1474 break;
1475 }
1476
1477 case STMT_SWITCH: {
1478 struct symbol *sym;
1479 struct instruction *switch_ins;
1480 struct basic_block *switch_end = alloc_basic_block(stmt->pos);
1481 struct basic_block *active, *default_case;
1482 struct multijmp *jmp;
1483 pseudo_t pseudo;
1484
1485 pseudo = linearize_expression(ep, stmt->switch_expression);
1486
1487 active = ep->active;
1488 if (!bb_reachable(active))
1489 break;
1490
1491 switch_ins = alloc_instruction(OP_SWITCH, NULL);
1492 add_instruction(&ep->switches, switch_ins);
1493 use_pseudo(pseudo, &switch_ins->cond);
1494 add_one_insn(ep, switch_ins);
1495 finish_block(ep);
1496
1497 default_case = NULL;
1498 FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) {
1499 struct statement *case_stmt = sym->stmt;
1500 struct basic_block *bb_case = get_bound_block(ep, sym);
1501
1502 if (!case_stmt->case_expression) {
1503 default_case = bb_case;
1504 continue;
1505 } else {
1506 int begin, end;
1507
1508 begin = end = case_stmt->case_expression->value;
1509 if (case_stmt->case_to)
1510 end = case_stmt->case_to->value;
1511 if (begin > end)
1512 jmp = alloc_multijmp(bb_case, end, begin);
1513 else
1514 jmp = alloc_multijmp(bb_case, begin, end);
1515
1516 }
1517 add_multijmp(&switch_ins->multijmp_list, jmp);
1518 add_bb(&bb_case->parents, active);
1519 add_bb(&active->children, bb_case);
1520 } END_FOR_EACH_PTR(sym);
1521
1522 bind_label(stmt->switch_break, switch_end, stmt->pos);
1523
1524 /* And linearize the actual statement */
1525 linearize_statement(ep, stmt->switch_statement);
1526 set_activeblock(ep, switch_end);
1527
1528 if (!default_case)
1529 default_case = switch_end;
1530
1531 jmp = alloc_multijmp(default_case, 1, 0);
1532 add_multijmp(&switch_ins->multijmp_list, jmp);
1533 add_bb(&default_case->parents, active);
1534 add_bb(&active->children, default_case);
1535
1536 break;
1537 }
1538
1539 case STMT_ITERATOR: {
1540 struct statement *pre_statement = stmt->iterator_pre_statement;
1541 struct expression *pre_condition = stmt->iterator_pre_condition;
1542 struct statement *statement = stmt->iterator_statement;
1543 struct statement *post_statement = stmt->iterator_post_statement;
1544 struct expression *post_condition = stmt->iterator_post_condition;
1545 struct basic_block *loop_top, *loop_body, *loop_continue, *loop_end;
1546
1547 concat_symbol_list(stmt->iterator_syms, &ep->syms);
1548 linearize_statement(ep, pre_statement);
1549
1550 loop_body = loop_top = alloc_basic_block(stmt->pos);
1551 loop_continue = alloc_basic_block(stmt->pos);
1552 loop_end = alloc_basic_block(stmt->pos);
1553
1554 if (pre_condition == post_condition) {
1555 loop_top = alloc_basic_block(stmt->pos);
1556 set_activeblock(ep, loop_top);
1557 }
1558
1559 if (pre_condition)
1560 linearize_cond_branch(ep, pre_condition, loop_body, loop_end);
1561
1562 bind_label(stmt->iterator_continue, loop_continue, stmt->pos);
1563 bind_label(stmt->iterator_break, loop_end, stmt->pos);
1564
1565 set_activeblock(ep, loop_body);
1566 linearize_statement(ep, statement);
1567 add_goto(ep, loop_continue);
1568
1569 if (post_condition) {
1570 set_activeblock(ep, loop_continue);
1571 linearize_statement(ep, post_statement);
1572 if (pre_condition == post_condition)
1573 add_goto(ep, loop_top);
1574 else
1575 linearize_cond_branch(ep, post_condition, loop_top, loop_end);
1576 }
1577
1578 set_activeblock(ep, loop_end);
1579 break;
1580 }
1581
1582 default:
1583 break;
1584 }
1585 return VOID;
1586 }
1587
1588 /*
1589 * Dammit, if we have a phi-node followed by a conditional
1590 * branch on that phi-node, we should damn well be able to
1591 * do something about the source. Maybe.
1592 */
1593 static void rewrite_branch(struct basic_block *bb,
1594 struct basic_block **ptr,
1595 struct basic_block *old,
1596 struct basic_block *new)
1597 {
1598 struct basic_block *tmp;
1599
1600 if (*ptr != old)
1601 return;
1602
1603 *ptr = new;
1604 FOR_EACH_PTR(new->parents, tmp) {
1605 if (tmp == old)
1606 *THIS_ADDRESS(tmp) = bb;
1607 } END_FOR_EACH_PTR(tmp);
1608
1609 FOR_EACH_PTR(bb->children, tmp) {
1610 if (tmp == old)
1611 *THIS_ADDRESS(tmp) = new;
1612 } END_FOR_EACH_PTR(tmp);
1613 }
1614
1615 /*
1616 * Return the known truth value of a pseudo, or -1 if
1617 * it's not known.
1618 */
1619 static int pseudo_truth_value(pseudo_t pseudo)
1620 {
1621 switch (pseudo->type) {
1622 case PSEUDO_VAL:
1623 return !!pseudo->value;
1624
1625 case PSEUDO_REG: {
1626 struct instruction *insn = pseudo->def;
1627 if (insn->opcode == OP_SETVAL && insn->target == pseudo) {
1628 struct expression *expr = insn->val;
1629
1630 /* A symbol address is always considered true.. */
1631 if (!expr)
1632 return 1;
1633 if (expr->type == EXPR_VALUE)
1634 return !!expr->value;
1635 }
1636 }
1637 /* Fall through */
1638 default:
1639 return -1;
1640 }
1641 }
1642
1643
1644 static void try_to_simplify_bb(struct entrypoint *ep, struct basic_block *bb,
1645 struct instruction *first, struct instruction *second)
1646 {
1647 struct phi *phi;
1648
1649 FOR_EACH_PTR(first->phi_list, phi) {
1650 struct basic_block *source = phi->source, *target;
1651 pseudo_t pseudo = phi->pseudo;
1652 struct instruction *br;
1653 int true;
1654
1655 if (!pseudo || !source)
1656 continue;
1657 br = last_instruction(source->insns);
1658 if (!br)
1659 continue;
1660 if (br->opcode != OP_BR)
1661 continue;
1662
1663 true = pseudo_truth_value(pseudo);
1664 if (true < 0)
1665 continue;
1666 target = true ? second->bb_true : second->bb_false;
1667 rewrite_branch(source, &br->bb_true, bb, target);
1668 rewrite_branch(source, &br->bb_false, bb, target);
1669 } END_FOR_EACH_PTR(phi);
1670 }
1671
1672 static inline int linearize_insn_list(struct instruction_list *list, struct instruction **arr, int nr)
1673 {
1674 return linearize_ptr_list((struct ptr_list *)list, (void **)arr, nr);
1675 }
1676
1677 static void simplify_phi_nodes(struct entrypoint *ep)
1678 {
1679 struct basic_block *bb;
1680
1681 FOR_EACH_PTR(ep->bbs, bb) {
1682 struct instruction *insns[2], *first, *second;
1683
1684 if (linearize_insn_list(bb->insns, insns, 2) < 2)
1685 continue;
1686
1687 first = insns[0];
1688 second = insns[1];
1689
1690 if (first->opcode != OP_PHI)
1691 continue;
1692 if (second->opcode != OP_BR)
1693 continue;
1694 if (first->target != second->cond)
1695 continue;
1696 try_to_simplify_bb(ep, bb, first, second);
1697 } END_FOR_EACH_PTR(bb);
1698 }
1699
1700 static inline void concat_user_list(struct pseudo_ptr_list *src, struct pseudo_ptr_list **dst)
1701 {
1702 concat_ptr_list((struct ptr_list *)src, (struct ptr_list **)dst);
1703 }
1704
1705 static void convert_load_insn(struct instruction *insn, pseudo_t src)
1706 {
1707 pseudo_t target, *usep;
1708
1709 /*
1710 * Go through the "insn->users" list and replace them all..
1711 */
1712 target = insn->target;
1713 FOR_EACH_PTR(target->users, usep) {
1714 *usep = src;
1715 } END_FOR_EACH_PTR(usep);
1716 concat_user_list(target->users, &src->users);
1717
1718 /* Turn the load into a no-op */
1719 insn->opcode = OP_LNOP;
1720 }
1721
1722 static int overlapping_memop(struct instruction *a, struct instruction *b)
1723 {
1724 unsigned int a_start = (a->offset << 3) + a->type->bit_offset;
1725 unsigned int b_start = (b->offset << 3) + b->type->bit_offset;
1726 unsigned int a_size = a->type->bit_size;
1727 unsigned int b_size = b->type->bit_size;
1728
1729 if (a_size + a_start <= b_start)
1730 return 0;
1731 if (b_size + b_start <= a_start)
1732 return 0;
1733 return 1;
1734 }
1735
1736 static inline int same_memop(struct instruction *a, struct instruction *b)
1737 {
1738 return a->offset == b->offset &&
1739 a->type->bit_size == b->type->bit_size &&
1740 a->type->bit_offset == b->type->bit_offset;
1741 }
1742
1743 /*
1744 * Return 1 if "one" dominates the access to 'pseudo'
1745 * in insn.
1746 *
1747 * Return 0 if it doesn't, and -1 if you don't know.
1748 */
1749 static int dominates(pseudo_t pseudo, struct instruction *insn,
1750 struct instruction *one, int local)
1751 {
1752 int opcode = one->opcode;
1753
1754 if (opcode == OP_CALL)
1755 return local ? 0 : -1;
1756 if (opcode != OP_LOAD && opcode != OP_STORE)
1757 return 0;
1758 if (one->src != pseudo) {
1759 if (local)
1760 return 0;
1761 /* We don't think two explicitly different symbols ever alias */
1762 if (one->src->type == PSEUDO_SYM)
1763 return 0;
1764 /* We could try to do some alias analysis here */
1765 return -1;
1766 }
1767 if (!same_memop(insn, one)) {
1768 if (one->opcode == OP_LOAD)
1769 return 0;
1770 if (!overlapping_memop(insn, one))
1771 return 0;
1772 return -1;
1773 }
1774 return 1;
1775 }
1776
1777 static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
1778 struct basic_block *bb, unsigned long generation, struct phi_list **dominators,
1779 int local, int loads)
1780 {
1781 struct basic_block *parent;
1782
1783 if (bb_list_size(bb->parents) > 1)
1784 loads = 0;
1785 FOR_EACH_PTR(bb->parents, parent) {
1786 struct instruction *one;
1787 struct phi *phi;
1788
1789 FOR_EACH_PTR_REVERSE(parent->insns, one) {
1790 int dominance;
1791 if (one == insn)
1792 goto no_dominance;
1793 dominance = dominates(pseudo, insn, one, local);
1794 if (dominance < 0) {
1795 if (one->opcode == OP_LOAD)
1796 continue;
1797 return 0;
1798 }
1799 if (!dominance)
1800 continue;
1801 if (one->opcode == OP_LOAD && !loads)
1802 continue;
1803 goto found_dominator;
1804 } END_FOR_EACH_PTR_REVERSE(one);
1805 no_dominance:
1806 if (parent->generation == generation)
1807 continue;
1808 parent->generation = generation;
1809
1810 if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local, loads))
1811 return 0;
1812 continue;
1813
1814 found_dominator:
1815 phi = alloc_phi(parent, one->target);
1816 add_phi(dominators, phi);
1817 } END_FOR_EACH_PTR(parent);
1818 return 1;
1819 }
1820
1821 /*
1822 * We should probably sort the phi list just to make it easier to compare
1823 * later for equality.
1824 */
1825 static void rewrite_load_instruction(struct instruction *insn, struct phi_list *dominators)
1826 {
1827 struct phi *phi, *first;
1828 pseudo_t new;
1829
1830 first = NULL;
1831 FOR_EACH_PTR(dominators, phi) {
1832 if (!first) {
1833 first = phi;
1834 continue;
1835 }
1836 if (first->pseudo == phi->pseudo &&
1837 first->source == phi->source) {
1838 phi->source = NULL;
1839 continue;
1840 }
1841 goto complex_phi;
1842 } END_FOR_EACH_PTR(phi);
1843
1844 first->source = NULL; /* Mark it as not used */
1845 convert_load_insn(insn, first->pseudo);
1846 return;
1847
1848 complex_phi:
1849 new = alloc_pseudo(insn);
1850 convert_load_insn(insn, new);
1851
1852 /*
1853 * FIXME! This is dubious. We should probably allocate a new
1854 * instruction instead of re-using the OP_LOAD instruction.
1855 * Re-use of the instruction makes the usage list suspect.
1856 *
1857 * It should be ok, because the only usage of the OP_LOAD
1858 * is the symbol pseudo, and we should never follow that
1859 * list _except_ for exactly the dominant instruction list
1860 * generation (and then we always check the opcode).
1861 */
1862 insn->opcode = OP_PHI;
1863 insn->target = new;
1864 insn->phi_list = dominators;
1865 new->def = insn;
1866 }
1867
1868 static int find_dominating_stores(pseudo_t pseudo, struct instruction *insn,
1869 unsigned long generation, int local)
1870 {
1871 struct basic_block *bb = insn->bb;
1872 struct instruction *one, *dom = NULL;
1873 struct phi_list *dominators;
1874 int partial;
1875
1876 /* Unreachable load? Undo it */
1877 if (!bb) {
1878 insn->opcode = OP_LNOP;
1879 return 1;
1880 }
1881
1882 partial = 0;
1883 FOR_EACH_PTR(bb->insns, one) {
1884 int dominance;
1885 if (one == insn)
1886 goto found;
1887 dominance = dominates(pseudo, insn, one, local);
1888 if (dominance < 0) {
1889 /* Ignore partial load dominators */
1890 if (one->opcode == OP_LOAD)
1891 continue;
1892 dom = NULL;
1893 partial = 1;
1894 continue;
1895 }
1896 if (!dominance)
1897 continue;
1898 dom = one;
1899 partial = 0;
1900 } END_FOR_EACH_PTR(one);
1901 /* Whaa? */
1902 warning(pseudo->sym->pos, "unable to find symbol read");
1903 return 0;
1904 found:
1905 if (partial)
1906 return 0;
1907
1908 if (dom) {
1909 if (dom->opcode == OP_LOAD)
1910 find_dominating_stores(pseudo, dom, ++bb_generation, local);
1911 convert_load_insn(insn, dom->target);
1912 return 1;
1913 }
1914
1915 /* Ok, go find the parents */
1916 bb->generation = generation;
1917
1918 dominators = NULL;
1919 if (!find_dominating_parents(pseudo, insn, bb, generation, &dominators, local, 1))
1920 return 0;
1921
1922 /* This happens with initial assignments to structures etc.. */
1923 if (!dominators) {
1924 if (!local)
1925 return 0;
1926 convert_load_insn(insn, value_pseudo(0));
1927 return 1;
1928 }
1929
1930 /*
1931 * If we find just one dominating instruction, we
1932 * can turn it into a direct thing. Otherwise we'll
1933 * have to turn the load into a phi-node of the
1934 * dominators.
1935 */
1936 rewrite_load_instruction(insn, dominators);
1937 return 1;
1938 }
1939
1940 /* Kill a pseudo that is dead on exit from the bb */
1941 static void kill_dead_stores(pseudo_t pseudo, unsigned long generation, struct basic_block *bb, int local)
1942 {
1943 struct instruction *insn;
1944 struct basic_block *parent;
1945
1946 if (bb->generation == generation)
1947 return;
1948 bb->generation = generation;
1949 FOR_EACH_PTR_REVERSE(bb->insns, insn) {
1950 int opcode = insn->opcode;
1951
1952 if (opcode != OP_LOAD && opcode != OP_STORE) {
1953 if (local)
1954 continue;
1955 if (opcode == OP_CALL)
1956 return;
1957 continue;
1958 }
1959 if (insn->src == pseudo) {
1960 if (opcode == OP_LOAD)
1961 return;
1962 insn->opcode = OP_SNOP;
1963 continue;
1964 }
1965 if (local)
1966 continue;
1967 if (insn->src->type != PSEUDO_SYM)
1968 return;
1969 } END_FOR_EACH_PTR_REVERSE(insn);
1970
1971 FOR_EACH_PTR(bb->parents, parent) {
1972 struct basic_block *child;
1973 FOR_EACH_PTR(parent->children, child) {
1974 if (child && child != bb)
1975 return;
1976 } END_FOR_EACH_PTR(child);
1977 kill_dead_stores(pseudo, generation, parent, local);
1978 } END_FOR_EACH_PTR(parent);
1979 }
1980
1981 /*
1982 * This should see if the "insn" trivially dominates some previous store, and kill the
1983 * store if unnecessary.
1984 */
1985 static void kill_dominated_stores(pseudo_t pseudo, struct instruction *insn,
1986 unsigned long generation, struct basic_block *bb, int local, int found)
1987 {
1988 struct instruction *one;
1989 struct basic_block *parent;
1990
1991 if (bb->generation == generation)
1992 return;
1993 bb->generation = generation;
1994 FOR_EACH_PTR_REVERSE(bb->insns, one) {
1995 int dominance;
1996 if (!found) {
1997 if (one != insn)
1998 continue;
1999 found = 1;
2000 continue;
2001 }
2002 dominance = dominates(pseudo, insn, one, local);
2003 if (!dominance)
2004 continue;
2005 if (dominance < 0)
2006 return;
2007 if (one->opcode == OP_LOAD)
2008 return;
2009 one->opcode = OP_SNOP;
2010 } END_FOR_EACH_PTR_REVERSE(one);
2011
2012 if (!found) {
2013 warning(bb->pos, "Unable to find instruction");
2014 return;
2015 }
2016
2017 FOR_EACH_PTR(bb->parents, parent) {
2018 struct basic_block *child;
2019 FOR_EACH_PTR(parent->children, child) {
2020 if (child && child != bb)
2021 return;
2022 } END_FOR_EACH_PTR(child);
2023 kill_dominated_stores(pseudo, insn, generation, parent, local, found);
2024 } END_FOR_EACH_PTR(parent);
2025 }
2026
2027 static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
2028 {
2029 pseudo_t pseudo, src, *pp;
2030 struct instruction *def;
2031 unsigned long mod;
2032 int all;
2033
2034 /* Never used as a symbol? */
2035 pseudo = sym->pseudo;
2036 if (!pseudo)
2037 return;
2038
2039 /* We don't do coverage analysis of volatiles.. */
2040 if (sym->ctype.modifiers & MOD_VOLATILE)
2041 return;
2042
2043 /* ..and symbols with external visibility need more care */
2044 mod = sym->ctype.modifiers & (MOD_EXTERN | MOD_STATIC | MOD_ADDRESSABLE);
2045 if (mod)
2046 goto external_visibility;
2047
2048 def = NULL;
2049 FOR_EACH_PTR(pseudo->users, pp) {
2050 /* We know that the symbol-pseudo use is the "src" in the instruction */
2051 struct instruction *insn = container(pp, struct instruction, src);
2052
2053 switch (insn->opcode) {
2054 case OP_STORE:
2055 if (def)
2056 goto multi_def;
2057 def = insn;
2058 break;
2059 case OP_LOAD:
2060 break;
2061 default:
2062 warning(sym->pos, "symbol '%s' pseudo used in unexpected way", show_ident(sym->ident));
2063 }
2064 if (insn->offset)
2065 goto complex_def;
2066 } END_FOR_EACH_PTR(pp);
2067
2068 /*
2069 * Goodie, we have a single store (if even that) in the whole
2070 * thing. Replace all loads with moves from the pseudo,
2071 * replace the store with a def.
2072 */
2073 src = VOID;
2074 if (def) {
2075 src = def->target;
2076
2077 /* Turn the store into a no-op */
2078 def->opcode = OP_SNOP;
2079 }
2080 FOR_EACH_PTR(pseudo->users, pp) {
2081 struct instruction *insn = container(pp, struct instruction, src);
2082 if (insn->opcode == OP_LOAD)
2083 convert_load_insn(insn, src);
2084 } END_FOR_EACH_PTR(pp);
2085 return;
2086
2087 multi_def:
2088 complex_def:
2089 external_visibility:
2090 all = 1;
2091 FOR_EACH_PTR_REVERSE(pseudo->users, pp) {
2092 struct instruction *insn = container(pp, struct instruction, src);
2093 if (insn->opcode == OP_LOAD)
2094 all &= find_dominating_stores(pseudo, insn, ++bb_generation, !mod);
2095 } END_FOR_EACH_PTR_REVERSE(pp);
2096
2097 /* If we converted all the loads, remove the stores. They are dead */
2098 if (all && !mod) {
2099 FOR_EACH_PTR(pseudo->users, pp) {
2100 struct instruction *insn = container(pp, struct instruction, src);
2101 if (insn->opcode == OP_STORE)
2102 insn->opcode = OP_SNOP;
2103 } END_FOR_EACH_PTR(pp);
2104 } else {
2105 /*
2106 * If we couldn't take the shortcut, see if we can at least kill some
2107 * of them..
2108 */
2109 FOR_EACH_PTR(pseudo->users, pp) {
2110 struct instruction *insn = container(pp, struct instruction, src);
2111 if (insn->opcode == OP_STORE)
2112 kill_dominated_stores(pseudo, insn, ++bb_generation, insn->bb, !mod, 0);
2113 } END_FOR_EACH_PTR(pp);
2114
2115 if (!(mod & (MOD_EXTERN | MOD_STATIC))) {
2116 struct basic_block *bb;
2117 FOR_EACH_PTR(ep->bbs, bb) {
2118 if (!bb->children)
2119 kill_dead_stores(pseudo, ++bb_generation, bb, !mod);
2120 } END_FOR_EACH_PTR(bb);
2121 }
2122 }
2123
2124 return;
2125 }
2126
2127 static void simplify_symbol_usage(struct entrypoint *ep)
2128 {
2129 struct symbol *sym;
2130 FOR_EACH_PTR(ep->accesses, sym) {
2131 simplify_one_symbol(ep, sym);
2132 sym->pseudo = NULL;
2133 } END_FOR_EACH_PTR(sym);
2134 }
2135
2136 static void mark_bb_reachable(struct basic_block *bb, unsigned long generation)
2137 {
2138 struct basic_block *child;
2139
2140 if (bb->generation == generation)
2141 return;
2142 bb->generation = generation;
2143 FOR_EACH_PTR(bb->children, child) {
2144 mark_bb_reachable(child, generation);
2145 } END_FOR_EACH_PTR(child);
2146 }
2147
2148 static void kill_bb(struct basic_block *bb)
2149 {
2150 bb->insns = NULL;
2151 bb->children = NULL;
2152 bb->parents = NULL;
2153 }
2154
2155 static void kill_unreachable_bbs(struct entrypoint *ep)
2156 {
2157 struct basic_block *bb;
2158 unsigned long generation = ++bb_generation;
2159
2160 mark_bb_reachable(ep->entry, generation);
2161 FOR_EACH_PTR(ep->bbs, bb) {
2162 struct phi *phi;
2163 if (bb->generation == generation)
2164 continue;
2165 FOR_EACH_PTR(bb->phinodes, phi) {
2166 phi->pseudo = VOID;
2167 phi->source = NULL;
2168 } END_FOR_EACH_PTR(phi);
2169
2170 /* Mark it as being dead */
2171 kill_bb(bb);
2172 } END_FOR_EACH_PTR(bb);
2173 }
2174
2175 static void try_to_replace(struct basic_block *bb, struct basic_block **target,
2176 struct basic_block *old, struct basic_block *new)
2177 {
2178 if (*target == old) {
2179 *target = new;
2180 /* FIXME!! Fix child information */
2181 warning(bb->pos, "changed child from %p to %p", old, new);
2182 }
2183 }
2184
2185 static int rewrite_parent_branch(struct basic_block *bb, struct basic_block *old, struct basic_block *new)
2186 {
2187 struct instruction *insn = last_instruction(bb->insns);
2188
2189 if (!insn)
2190 return 0;
2191 switch (insn->opcode) {
2192 case OP_BR:
2193 rewrite_branch(bb, &insn->bb_true, old, new);
2194 rewrite_branch(bb, &insn->bb_false, old, new);
2195 return 1;
2196 case OP_SWITCH: {
2197 struct multijmp *jmp;
2198 FOR_EACH_PTR(insn->multijmp_list, jmp) {
2199 rewrite_branch(bb, &jmp->target, old, new);
2200 } END_FOR_EACH_PTR(jmp);
2201 return 1;
2202 }
2203 default:
2204 return 0;
2205 }
2206 }
2207
2208 static int rewrite_branch_bb(struct basic_block *bb, struct instruction *br)
2209 {
2210 int success;
2211 struct basic_block *parent;
2212 struct basic_block *target = br->bb_true;
2213 struct basic_block *false = br->bb_false;
2214
2215 if (target && false) {
2216 pseudo_t cond = br->cond;
2217 if (cond->type != PSEUDO_VAL)
2218 return 0;
2219 target = cond->value ? target : false;
2220 }
2221
2222 success = 1;
2223 target = target ? : false;
2224 FOR_EACH_PTR(bb->parents, parent) {
2225 if (!rewrite_parent_branch(parent, bb, target))
2226 success = 0;
2227 } END_FOR_EACH_PTR(parent);
2228 return success;
2229 }
2230
2231 /*
2232 * FIXME! This knows _way_ too much about list internals
2233 */
2234 static void set_list(struct basic_block_list *p, struct basic_block *child)
2235 {
2236 struct ptr_list *list = (void *)p;
2237 list->prev = list;
2238 list->next = list;
2239 list->nr = 1;
2240 list->list[0] = child;
2241 }
2242
2243 static void simplify_one_switch(struct basic_block *bb,
2244 long long val,
2245 struct multijmp_list *list,
2246 struct instruction *p)
2247 {
2248 struct multijmp *jmp;
2249
2250 FOR_EACH_PTR(list, jmp) {
2251 /* Default case */
2252 if (jmp->begin > jmp->end)
2253 goto found;
2254 if (val >= jmp->begin && val <= jmp->end)
2255 goto found;
2256 } END_FOR_EACH_PTR(jmp);
2257 warning(bb->pos, "Impossible case statement");
2258 return;
2259
2260 found:
2261 p->opcode = OP_BR;
2262 p->cond = NULL;
2263 p->bb_false = NULL;
2264 p->bb_true = jmp->target;
2265 set_list(bb->children, jmp->target);
2266 }
2267
2268 static void simplify_switch(struct entrypoint *ep)
2269 {
2270 struct instruction *insn;
2271
2272 FOR_EACH_PTR(ep->switches, insn) {
2273 pseudo_t pseudo = insn->target;
2274 if (pseudo->type == PSEUDO_VAL)
2275 simplify_one_switch(insn->bb, pseudo->value, insn->multijmp_list, insn);
2276 } END_FOR_EACH_PTR(insn);
2277 }
2278
2279 static void pack_basic_blocks(struct entrypoint *ep)
2280 {
2281 struct basic_block *bb;
2282
2283 simplify_switch(ep);
2284
2285 kill_unreachable_bbs(ep);
2286
2287 /* See if we can merge a bb into another one.. */
2288 FOR_EACH_PTR(ep->bbs, bb) {
2289 struct instruction *first;
2290 struct basic_block *parent, *child;
2291
2292 if (!bb_reachable(bb))
2293 continue;
2294 /*
2295 * If this block has a phi-node associated with it,
2296 */
2297 if (bb->phinodes)
2298 continue;
2299
2300 /*
2301 * Just a branch?
2302 */
2303 first = first_instruction(bb->insns);
2304 if (first && first->opcode == OP_BR) {
2305 if (rewrite_branch_bb(bb, first)) {
2306 kill_bb(bb);
2307 continue;
2308 }
2309 }
2310
2311 if (ep->entry == bb)
2312 continue;
2313
2314 /*
2315 * See if we only have one parent..
2316 */
2317 if (bb_list_size(bb->parents) != 1)
2318 continue;
2319 parent = first_basic_block(bb->parents);
2320 if (parent == bb)
2321 continue;
2322
2323 /*
2324 * Goodie. See if the parent can merge..
2325 */
2326 FOR_EACH_PTR(parent->children, child) {
2327 if (child != bb)
2328 goto no_merge;
2329 } END_FOR_EACH_PTR(child);
2330
2331 parent->children = bb->children;
2332 FOR_EACH_PTR(bb->children, child) {
2333 struct basic_block *p;
2334 FOR_EACH_PTR(child->parents, p) {
2335 if (p != bb)
2336 continue;
2337 *THIS_ADDRESS(p) = parent;
2338 } END_FOR_EACH_PTR(p);
2339 } END_FOR_EACH_PTR(child);
2340
2341 delete_last_instruction(&parent->insns);
2342 concat_instruction_list(bb->insns, &parent->insns);
2343 kill_bb(bb);
2344
2345 no_merge:
2346 /* nothing to do */;
2347 } END_FOR_EACH_PTR(bb);
2348 }
2349
2350 struct entrypoint *linearize_symbol(struct symbol *sym)
2351 {
2352 struct symbol *base_type;
2353 struct entrypoint *ret_ep = NULL;
2354
2355 if (!sym)
2356 return NULL;
2357 base_type = sym->ctype.base_type;
2358 if (!base_type)
2359 return NULL;
2360 if (base_type->type == SYM_FN) {
2361 if (base_type->stmt) {
2362 struct entrypoint *ep = alloc_entrypoint();
2363 struct basic_block *bb = alloc_basic_block(sym->pos);
2364 struct symbol *arg;
2365 pseudo_t result;
2366 int i;
2367
2368 ep->name = sym;
2369 ep->entry = bb;
2370 set_activeblock(ep, bb);
2371 concat_symbol_list(base_type->arguments, &ep->syms);
2372
2373 /* FIXME!! We should do something else about varargs.. */
2374 i = 0;
2375 FOR_EACH_PTR(base_type->arguments, arg) {
2376 linearize_argument(ep, arg, ++i);
2377 } END_FOR_EACH_PTR(arg);
2378
2379 result = linearize_statement(ep, base_type->stmt);
2380 if (bb_reachable(ep->active) && !bb_terminated(ep->active)) {
2381 struct symbol *ret_type = base_type->ctype.base_type;
2382 struct instruction *insn = alloc_instruction(OP_RET, ret_type);
2383
2384 use_pseudo(result, &insn->src);
2385 add_one_insn(ep, insn);
2386 }
2387
2388 simplify_symbol_usage(ep);
2389
2390 /*
2391 * Questionable conditional branch simplification.
2392 * This short-circuits branches to conditional branches,
2393 * and leaves the phi-nodes "dangling" in the old
2394 * basic block - the nodes are no longer attached to
2395 * where the uses are. But it can still be considered
2396 * SSA if you just look at it sideways..
2397 */
2398 simplify_phi_nodes(ep);
2399
2400 /*
2401 * Remove or merge basic blocks.
2402 */
2403 pack_basic_blocks(ep);
2404
2405 ret_ep = ep;
2406 }
2407 }
2408
2409 return ret_ep;
2410 }
Static analysis for C