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