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