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