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