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