?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Make switch/case statements check type compatibility
[smatch.git] / example.c
blob7d0a037589c4b259a3fe5b9fb67918d7a24016d6
1 /*
2 * Example of how to write a compiler with sparse
3 */
4 #include <stdio.h>
5 #include <stdlib.h>
6 #include <stdarg.h>
7 #include <string.h>
8 #include <assert.h>
9
10 #include "symbol.h"
11 #include "expression.h"
12 #include "linearize.h"
13 #include "flow.h"
14 #include "storage.h"
15 #include "target.h"
16
17 static const char* opcodes[] = {
18 [OP_BADOP] = "bad_op",
19
20 /* Fn entrypoint */
21 [OP_ENTRY] = "<entry-point>",
22
23 /* Terminator */
24 [OP_RET] = "ret",
25 [OP_BR] = "br",
26 [OP_SWITCH] = "switch",
27 [OP_INVOKE] = "invoke",
28 [OP_COMPUTEDGOTO] = "jmp *",
29 [OP_UNWIND] = "unwind",
30
31 /* Binary */
32 [OP_ADD] = "add",
33 [OP_SUB] = "sub",
34 [OP_MULU] = "mulu",
35 [OP_MULS] = "muls",
36 [OP_DIVU] = "divu",
37 [OP_DIVS] = "divs",
38 [OP_MODU] = "modu",
39 [OP_MODS] = "mods",
40 [OP_SHL] = "shl",
41 [OP_LSR] = "lsr",
42 [OP_ASR] = "asr",
43
44 /* Logical */
45 [OP_AND] = "and",
46 [OP_OR] = "or",
47 [OP_XOR] = "xor",
48 [OP_AND_BOOL] = "and-bool",
49 [OP_OR_BOOL] = "or-bool",
50
51 /* Binary comparison */
52 [OP_SET_EQ] = "seteq",
53 [OP_SET_NE] = "setne",
54 [OP_SET_LE] = "setle",
55 [OP_SET_GE] = "setge",
56 [OP_SET_LT] = "setlt",
57 [OP_SET_GT] = "setgt",
58 [OP_SET_B] = "setb",
59 [OP_SET_A] = "seta",
60 [OP_SET_BE] = "setbe",
61 [OP_SET_AE] = "setae",
62
63 /* Uni */
64 [OP_NOT] = "not",
65 [OP_NEG] = "neg",
66
67 /* Special three-input */
68 [OP_SEL] = "select",
69
70 /* Memory */
71 [OP_MALLOC] = "malloc",
72 [OP_FREE] = "free",
73 [OP_ALLOCA] = "alloca",
74 [OP_LOAD] = "load",
75 [OP_STORE] = "store",
76 [OP_SETVAL] = "set",
77 [OP_GET_ELEMENT_PTR] = "getelem",
78
79 /* Other */
80 [OP_PHI] = "phi",
81 [OP_PHISOURCE] = "phisrc",
82 [OP_CAST] = "cast",
83 [OP_SCAST] = "scast",
84 [OP_FPCAST] = "fpcast",
85 [OP_PTRCAST] = "ptrcast",
86 [OP_CALL] = "call",
87 [OP_VANEXT] = "va_next",
88 [OP_VAARG] = "va_arg",
89 [OP_SLICE] = "slice",
90 [OP_SNOP] = "snop",
91 [OP_LNOP] = "lnop",
92 [OP_NOP] = "nop",
93 [OP_DEATHNOTE] = "dead",
94 [OP_ASM] = "asm",
95
96 /* Sparse tagging (line numbers, context, whatever) */
97 [OP_CONTEXT] = "context",
98 };
99
100 static int last_reg, stack_offset;
101
102 struct hardreg {
103 const char *name;
104 struct pseudo_list *contains;
105 unsigned busy:16,
106 dead:8,
107 used:1;
108 };
109
110 #define TAG_DEAD 1
111 #define TAG_DIRTY 2
112
113 /* Our "switch" generation is very very stupid. */
114 #define SWITCH_REG (1)
115
116 static void output_bb(struct basic_block *bb, unsigned long generation);
117
118 /*
119 * We only know about the caller-clobbered registers
120 * right now.
121 */
122 static struct hardreg hardregs[] = {
123 { .name = "%eax" },
124 { .name = "%edx" },
125 { .name = "%ecx" },
126 { .name = "%ebx" },
127 { .name = "%esi" },
128 { .name = "%edi" },
129
130 { .name = "%ebp" },
131 { .name = "%esp" },
132 };
133 #define REGNO 6
134 #define REG_EBP 6
135 #define REG_ESP 7
136
137 struct bb_state {
138 struct position pos;
139 struct storage_hash_list *inputs;
140 struct storage_hash_list *outputs;
141 struct storage_hash_list *internal;
142
143 /* CC cache.. */
144 int cc_opcode, cc_dead;
145 pseudo_t cc_target;
146 };
147
148 enum optype {
149 OP_UNDEF,
150 OP_REG,
151 OP_VAL,
152 OP_MEM,
153 OP_ADDR,
154 };
155
156 struct operand {
157 enum optype type;
158 int size;
159 union {
160 struct hardreg *reg;
161 long long value;
162 struct /* OP_MEM and OP_ADDR */ {
163 unsigned int offset;
164 unsigned int scale;
165 struct symbol *sym;
166 struct hardreg *base;
167 struct hardreg *index;
168 };
169 };
170 };
171
172 static const char *show_op(struct bb_state *state, struct operand *op)
173 {
174 static char buf[256][4];
175 static int bufnr;
176 char *p, *ret;
177 int nr;
178
179 nr = (bufnr + 1) & 3;
180 bufnr = nr;
181 ret = p = buf[nr];
182
183 switch (op->type) {
184 case OP_UNDEF:
185 return "undef";
186 case OP_REG:
187 return op->reg->name;
188 case OP_VAL:
189 sprintf(p, "$%lld", op->value);
190 break;
191 case OP_MEM:
192 case OP_ADDR:
193 if (op->offset)
194 p += sprintf(p, "%d", op->offset);
195 if (op->sym)
196 p += sprintf(p, "%s%s",
197 op->offset ? "+" : "",
198 show_ident(op->sym->ident));
199 if (op->base || op->index) {
200 p += sprintf(p, "(%s%s%s",
201 op->base ? op->base->name : "",
202 (op->base && op->index) ? "," : "",
203 op->index ? op->index->name : "");
204 if (op->scale > 1)
205 p += sprintf(p, ",%d", op->scale);
206 *p++ = ')';
207 *p = '\0';
208 }
209 break;
210 }
211 return ret;
212 }
213
214 static struct storage_hash *find_storage_hash(pseudo_t pseudo, struct storage_hash_list *list)
215 {
216 struct storage_hash *entry;
217 FOR_EACH_PTR(list, entry) {
218 if (entry->pseudo == pseudo)
219 return entry;
220 } END_FOR_EACH_PTR(entry);
221 return NULL;
222 }
223
224 static struct storage_hash *find_or_create_hash(pseudo_t pseudo, struct storage_hash_list **listp)
225 {
226 struct storage_hash *entry;
227
228 entry = find_storage_hash(pseudo, *listp);
229 if (!entry) {
230 entry = alloc_storage_hash(alloc_storage());
231 entry->pseudo = pseudo;
232 add_ptr_list(listp, entry);
233 }
234 return entry;
235 }
236
237 /* Eventually we should just build it up in memory */
238 static void output_line(struct bb_state *state, const char *fmt, ...)
239 {
240 va_list args;
241
242 va_start(args, fmt);
243 vprintf(fmt, args);
244 va_end(args);
245 }
246
247 static void output_label(struct bb_state *state, const char *fmt, ...)
248 {
249 static char buffer[512];
250 va_list args;
251
252 va_start(args, fmt);
253 vsnprintf(buffer, sizeof(buffer), fmt, args);
254 va_end(args);
255
256 output_line(state, "%s:\n", buffer);
257 }
258
259 static void output_insn(struct bb_state *state, const char *fmt, ...)
260 {
261 static char buffer[512];
262 va_list args;
263
264 va_start(args, fmt);
265 vsnprintf(buffer, sizeof(buffer), fmt, args);
266 va_end(args);
267
268 output_line(state, "\t%s\n", buffer);
269 }
270
271 #define output_insn(state, fmt, arg...) \
272 output_insn(state, fmt "\t\t# %s" , ## arg , __FUNCTION__)
273
274 static void output_comment(struct bb_state *state, const char *fmt, ...)
275 {
276 static char buffer[512];
277 va_list args;
278
279 if (!verbose)
280 return;
281 va_start(args, fmt);
282 vsnprintf(buffer, sizeof(buffer), fmt, args);
283 va_end(args);
284
285 output_line(state, "\t# %s\n", buffer);
286 }
287
288 static const char *show_memop(struct storage *storage)
289 {
290 static char buffer[1000];
291
292 if (!storage)
293 return "undef";
294 switch (storage->type) {
295 case REG_FRAME:
296 sprintf(buffer, "%d(FP)", storage->offset);
297 break;
298 case REG_STACK:
299 sprintf(buffer, "%d(SP)", storage->offset);
300 break;
301 case REG_REG:
302 return hardregs[storage->regno].name;
303 default:
304 return show_storage(storage);
305 }
306 return buffer;
307 }
308
309 static int alloc_stack_offset(int size)
310 {
311 int ret = stack_offset;
312 stack_offset = ret + size;
313 return ret;
314 }
315
316 static void alloc_stack(struct bb_state *state, struct storage *storage)
317 {
318 storage->type = REG_STACK;
319 storage->offset = alloc_stack_offset(4);
320 }
321
322 /*
323 * Can we re-generate the pseudo, so that we don't need to
324 * flush it to memory? We can regenerate:
325 * - immediates and symbol addresses
326 * - pseudos we got as input in non-registers
327 * - pseudos we've already saved off earlier..
328 */
329 static int can_regenerate(struct bb_state *state, pseudo_t pseudo)
330 {
331 struct storage_hash *in;
332
333 switch (pseudo->type) {
334 case PSEUDO_VAL:
335 case PSEUDO_SYM:
336 return 1;
337
338 default:
339 in = find_storage_hash(pseudo, state->inputs);
340 if (in && in->storage->type != REG_REG)
341 return 1;
342 in = find_storage_hash(pseudo, state->internal);
343 if (in)
344 return 1;
345 }
346 return 0;
347 }
348
349 static void flush_one_pseudo(struct bb_state *state, struct hardreg *hardreg, pseudo_t pseudo)
350 {
351 struct storage_hash *out;
352 struct storage *storage;
353
354 if (can_regenerate(state, pseudo))
355 return;
356
357 output_comment(state, "flushing %s from %s", show_pseudo(pseudo), hardreg->name);
358 out = find_storage_hash(pseudo, state->internal);
359 if (!out) {
360 out = find_storage_hash(pseudo, state->outputs);
361 if (!out)
362 out = find_or_create_hash(pseudo, &state->internal);
363 }
364 storage = out->storage;
365 switch (storage->type) {
366 default:
367 /*
368 * Aieee - the next user wants it in a register, but we
369 * need to flush it to memory in between. Which means that
370 * we need to allocate an internal one, dammit..
371 */
372 out = find_or_create_hash(pseudo, &state->internal);
373 storage = out->storage;
374 /* Fall through */
375 case REG_UDEF:
376 alloc_stack(state, storage);
377 /* Fall through */
378 case REG_STACK:
379 output_insn(state, "movl %s,%s", hardreg->name, show_memop(storage));
380 break;
381 }
382 }
383
384 /* Flush a hardreg out to the storage it has.. */
385 static void flush_reg(struct bb_state *state, struct hardreg *reg)
386 {
387 pseudo_t pseudo;
388
389 if (reg->busy)
390 output_comment(state, "reg %s flushed while busy is %d!", reg->name, reg->busy);
391 if (!reg->contains)
392 return;
393 reg->dead = 0;
394 reg->used = 1;
395 FOR_EACH_PTR(reg->contains, pseudo) {
396 if (CURRENT_TAG(pseudo) & TAG_DEAD)
397 continue;
398 if (!(CURRENT_TAG(pseudo) & TAG_DIRTY))
399 continue;
400 flush_one_pseudo(state, reg, pseudo);
401 } END_FOR_EACH_PTR(pseudo);
402 free_ptr_list(&reg->contains);
403 }
404
405 static struct storage_hash *find_pseudo_storage(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
406 {
407 struct storage_hash *src;
408
409 src = find_storage_hash(pseudo, state->internal);
410 if (!src) {
411 src = find_storage_hash(pseudo, state->inputs);
412 if (!src) {
413 src = find_storage_hash(pseudo, state->outputs);
414 /* Undefined? Screw it! */
415 if (!src)
416 return NULL;
417
418 /*
419 * If we found output storage, it had better be local stack
420 * that we flushed to earlier..
421 */
422 if (src->storage->type != REG_STACK)
423 return NULL;
424 }
425 }
426
427 /*
428 * Incoming pseudo with out any pre-set storage allocation?
429 * We can make up our own, and obviously prefer to get it
430 * in the register we already selected (if it hasn't been
431 * used yet).
432 */
433 if (src->storage->type == REG_UDEF) {
434 if (reg && !reg->used) {
435 src->storage->type = REG_REG;
436 src->storage->regno = reg - hardregs;
437 return NULL;
438 }
439 alloc_stack(state, src->storage);
440 }
441 return src;
442 }
443
444 static void mark_reg_dead(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
445 {
446 pseudo_t p;
447
448 FOR_EACH_PTR(reg->contains, p) {
449 if (p != pseudo)
450 continue;
451 if (CURRENT_TAG(p) & TAG_DEAD)
452 continue;
453 output_comment(state, "marking pseudo %s in reg %s dead", show_pseudo(pseudo), reg->name);
454 TAG_CURRENT(p, TAG_DEAD);
455 reg->dead++;
456 } END_FOR_EACH_PTR(p);
457 }
458
459 static void add_pseudo_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
460 {
461 output_comment(state, "added pseudo %s to reg %s", show_pseudo(pseudo), reg->name);
462 add_ptr_list_tag(&reg->contains, pseudo, TAG_DIRTY);
463 }
464
465 static struct hardreg *preferred_reg(struct bb_state *state, pseudo_t target)
466 {
467 struct storage_hash *dst;
468
469 dst = find_storage_hash(target, state->outputs);
470 if (dst) {
471 struct storage *storage = dst->storage;
472 if (storage->type == REG_REG)
473 return hardregs + storage->regno;
474 }
475 return NULL;
476 }
477
478 static struct hardreg *empty_reg(struct bb_state *state)
479 {
480 int i;
481 struct hardreg *reg = hardregs;
482
483 for (i = 0; i < REGNO; i++, reg++) {
484 if (!reg->contains)
485 return reg;
486 }
487 return NULL;
488 }
489
490 static struct hardreg *target_reg(struct bb_state *state, pseudo_t pseudo, pseudo_t target)
491 {
492 int i;
493 int unable_to_find_reg = 0;
494 struct hardreg *reg;
495
496 /* First, see if we have a preferred target register.. */
497 reg = preferred_reg(state, target);
498 if (reg && !reg->contains)
499 goto found;
500
501 reg = empty_reg(state);
502 if (reg)
503 goto found;
504
505 i = last_reg;
506 do {
507 i++;
508 if (i >= REGNO)
509 i = 0;
510 reg = hardregs + i;
511 if (!reg->busy) {
512 flush_reg(state, reg);
513 last_reg = i;
514 goto found;
515 }
516 } while (i != last_reg);
517 assert(unable_to_find_reg);
518
519 found:
520 add_pseudo_reg(state, pseudo, reg);
521 return reg;
522 }
523
524 static struct hardreg *find_in_reg(struct bb_state *state, pseudo_t pseudo)
525 {
526 int i;
527 struct hardreg *reg;
528
529 for (i = 0; i < REGNO; i++) {
530 pseudo_t p;
531
532 reg = hardregs + i;
533 FOR_EACH_PTR(reg->contains, p) {
534 if (p == pseudo) {
535 last_reg = i;
536 output_comment(state, "found pseudo %s in reg %s (busy=%d)", show_pseudo(pseudo), reg->name, reg->busy);
537 return reg;
538 }
539 } END_FOR_EACH_PTR(p);
540 }
541 return NULL;
542 }
543
544 static void flush_pseudo(struct bb_state *state, pseudo_t pseudo, struct storage *storage)
545 {
546 struct hardreg *reg = find_in_reg(state, pseudo);
547
548 if (reg)
549 flush_reg(state, reg);
550 }
551
552 static void flush_cc_cache_to_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
553 {
554 int opcode = state->cc_opcode;
555
556 state->cc_opcode = 0;
557 state->cc_target = NULL;
558 output_insn(state, "%s %s", opcodes[opcode], reg->name);
559 }
560
561 static void flush_cc_cache(struct bb_state *state)
562 {
563 pseudo_t pseudo = state->cc_target;
564
565 if (pseudo) {
566 struct hardreg *dst;
567
568 state->cc_target = NULL;
569
570 if (!state->cc_dead) {
571 dst = target_reg(state, pseudo, pseudo);
572 flush_cc_cache_to_reg(state, pseudo, dst);
573 }
574 }
575 }
576
577 static void add_cc_cache(struct bb_state *state, int opcode, pseudo_t pseudo)
578 {
579 assert(!state->cc_target);
580 state->cc_target = pseudo;
581 state->cc_opcode = opcode;
582 state->cc_dead = 0;
583 output_comment(state, "caching %s", opcodes[opcode]);
584 }
585
586 /* Fill a hardreg with the pseudo it has */
587 static struct hardreg *fill_reg(struct bb_state *state, struct hardreg *hardreg, pseudo_t pseudo)
588 {
589 struct storage_hash *src;
590 struct instruction *def;
591
592 if (state->cc_target == pseudo) {
593 flush_cc_cache_to_reg(state, pseudo, hardreg);
594 return hardreg;
595 }
596
597 switch (pseudo->type) {
598 case PSEUDO_VAL:
599 output_insn(state, "movl $%lld,%s", pseudo->value, hardreg->name);
600 break;
601 case PSEUDO_SYM:
602 src = find_pseudo_storage(state, pseudo, NULL);
603 /* Static thing? */
604 if (!src) {
605 output_insn(state, "movl $<%s>,%s", show_pseudo(pseudo), hardreg->name);
606 break;
607 }
608 switch (src->storage->type) {
609 case REG_REG:
610 /* Aiaiaiaiaii! Need to flush it to temporary memory */
611 src = find_or_create_hash(pseudo, &state->internal);
612 /* Fallthrough */
613 default:
614 alloc_stack(state, src->storage);
615 /* Fallthrough */
616 case REG_STACK:
617 case REG_FRAME:
618 flush_pseudo(state, pseudo, src->storage);
619 output_insn(state, "leal %s,%s", show_memop(src->storage), hardreg->name);
620 break;
621 }
622 break;
623 case PSEUDO_ARG:
624 case PSEUDO_REG:
625 def = pseudo->def;
626 if (def->opcode == OP_SETVAL) {
627 output_insn(state, "movl $<%s>,%s", show_pseudo(def->target), hardreg->name);
628 break;
629 }
630 src = find_pseudo_storage(state, pseudo, hardreg);
631 if (!src)
632 break;
633 if (src->flags & TAG_DEAD)
634 mark_reg_dead(state, pseudo, hardreg);
635 output_insn(state, "mov.%d %s,%s", 32, show_memop(src->storage), hardreg->name);
636 break;
637 default:
638 output_insn(state, "reload %s from %s", hardreg->name, show_pseudo(pseudo));
639 break;
640 }
641 return hardreg;
642 }
643
644 static struct hardreg *getreg(struct bb_state *state, pseudo_t pseudo, pseudo_t target)
645 {
646 struct hardreg *reg;
647
648 reg = find_in_reg(state, pseudo);
649 if (reg)
650 return reg;
651 reg = target_reg(state, pseudo, target);
652 return fill_reg(state, reg, pseudo);
653 }
654
655 static void move_reg(struct bb_state *state, struct hardreg *src, struct hardreg *dst)
656 {
657 output_insn(state, "movl %s,%s", src->name, dst->name);
658 }
659
660 static struct hardreg *copy_reg(struct bb_state *state, struct hardreg *src, pseudo_t target)
661 {
662 int i;
663 struct hardreg *reg;
664
665 /* If the container has been killed off, just re-use it */
666 if (!src->contains)
667 return src;
668
669 /* If "src" only has one user, and the contents are dead, we can re-use it */
670 if (src->busy == 1 && src->dead == 1)
671 return src;
672
673 reg = preferred_reg(state, target);
674 if (reg && !reg->contains) {
675 output_comment(state, "copying %s to preferred target %s", show_pseudo(target), reg->name);
676 move_reg(state, src, reg);
677 return reg;
678 }
679
680 for (i = 0; i < REGNO; i++) {
681 struct hardreg *reg = hardregs + i;
682 if (!reg->contains) {
683 output_comment(state, "copying %s to %s", show_pseudo(target), reg->name);
684 output_insn(state, "movl %s,%s", src->name, reg->name);
685 return reg;
686 }
687 }
688
689 flush_reg(state, src);
690 return src;
691 }
692
693 static void put_operand(struct bb_state *state, struct operand *op)
694 {
695 switch (op->type) {
696 case OP_REG:
697 op->reg->busy--;
698 break;
699 case OP_ADDR:
700 case OP_MEM:
701 if (op->base)
702 op->base->busy--;
703 if (op->index)
704 op->index->busy--;
705 break;
706 default:
707 break;
708 }
709 }
710
711 static struct operand *alloc_op(void)
712 {
713 struct operand *op = malloc(sizeof(*op));
714 memset(op, 0, sizeof(*op));
715 return op;
716 }
717
718 static struct operand *get_register_operand(struct bb_state *state, pseudo_t pseudo, pseudo_t target)
719 {
720 struct operand *op = alloc_op();
721 op->type = OP_REG;
722 op->reg = getreg(state, pseudo, target);
723 op->reg->busy++;
724 return op;
725 }
726
727 static int get_sym_frame_offset(struct bb_state *state, pseudo_t pseudo)
728 {
729 int offset = pseudo->nr;
730 if (offset < 0) {
731 offset = alloc_stack_offset(4);
732 pseudo->nr = offset;
733 }
734 return offset;
735 }
736
737 static struct operand *get_generic_operand(struct bb_state *state, pseudo_t pseudo)
738 {
739 struct hardreg *reg;
740 struct storage *src;
741 struct storage_hash *hash;
742 struct operand *op = malloc(sizeof(*op));
743
744 memset(op, 0, sizeof(*op));
745 switch (pseudo->type) {
746 case PSEUDO_VAL:
747 op->type = OP_VAL;
748 op->value = pseudo->value;
749 break;
750
751 case PSEUDO_SYM: {
752 struct symbol *sym = pseudo->sym;
753 op->type = OP_ADDR;
754 if (sym->ctype.modifiers & MOD_NONLOCAL) {
755 op->sym = sym;
756 break;
757 }
758 op->base = hardregs + REG_EBP;
759 op->offset = get_sym_frame_offset(state, pseudo);
760 break;
761 }
762
763 default:
764 reg = find_in_reg(state, pseudo);
765 if (reg) {
766 op->type = OP_REG;
767 op->reg = reg;
768 reg->busy++;
769 break;
770 }
771 hash = find_pseudo_storage(state, pseudo, NULL);
772 if (!hash)
773 break;
774 src = hash->storage;
775 switch (src->type) {
776 case REG_REG:
777 op->type = OP_REG;
778 op->reg = hardregs + src->regno;
779 op->reg->busy++;
780 break;
781 case REG_FRAME:
782 op->type = OP_MEM;
783 op->offset = src->offset;
784 op->base = hardregs + REG_EBP;
785 break;
786 case REG_STACK:
787 op->type = OP_MEM;
788 op->offset = src->offset;
789 op->base = hardregs + REG_ESP;
790 break;
791 default:
792 break;
793 }
794 }
795 return op;
796 }
797
798 /* Callers should be made to use the proper "operand" formats */
799 static const char *generic(struct bb_state *state, pseudo_t pseudo)
800 {
801 struct hardreg *reg;
802 struct operand *op = get_generic_operand(state, pseudo);
803 static char buf[100];
804 const char *str;
805
806 switch (op->type) {
807 case OP_ADDR:
808 if (!op->offset && op->base && !op->sym)
809 return op->base->name;
810 if (op->sym && !op->base) {
811 int len = sprintf(buf, "$ %s", show_op(state, op));
812 if (op->offset)
813 sprintf(buf + len, " + %d", op->offset);
814 return buf;
815 }
816 str = show_op(state, op);
817 put_operand(state, op);
818 reg = target_reg(state, pseudo, NULL);
819 output_insn(state, "lea %s,%s", show_op(state, op), reg->name);
820 return reg->name;
821
822 default:
823 str = show_op(state, op);
824 }
825 put_operand(state, op);
826 return str;
827 }
828
829 static struct operand *get_address_operand(struct bb_state *state, struct instruction *memop)
830 {
831 struct hardreg *base;
832 struct operand *op = get_generic_operand(state, memop->src);
833
834 switch (op->type) {
835 case OP_ADDR:
836 op->offset += memop->offset;
837 break;
838 default:
839 put_operand(state, op);
840 base = getreg(state, memop->src, NULL);
841 op->type = OP_ADDR;
842 op->base = base;
843 base->busy++;
844 op->offset = memop->offset;
845 op->sym = NULL;
846 }
847 return op;
848 }
849
850 static const char *address(struct bb_state *state, struct instruction *memop)
851 {
852 struct operand *op = get_address_operand(state, memop);
853 const char *str = show_op(state, op);
854 put_operand(state, op);
855 return str;
856 }
857
858 static const char *reg_or_imm(struct bb_state *state, pseudo_t pseudo)
859 {
860 switch(pseudo->type) {
861 case PSEUDO_VAL:
862 return show_pseudo(pseudo);
863 default:
864 return getreg(state, pseudo, NULL)->name;
865 }
866 }
867
868 static void kill_dead_reg(struct hardreg *reg)
869 {
870 if (reg->dead) {
871 pseudo_t p;
872
873 FOR_EACH_PTR(reg->contains, p) {
874 if (CURRENT_TAG(p) & TAG_DEAD) {
875 DELETE_CURRENT_PTR(p);
876 reg->dead--;
877 }
878 } END_FOR_EACH_PTR(p);
879 PACK_PTR_LIST(&reg->contains);
880 assert(!reg->dead);
881 }
882 }
883
884 static struct hardreg *target_copy_reg(struct bb_state *state, struct hardreg *src, pseudo_t target)
885 {
886 kill_dead_reg(src);
887 return copy_reg(state, src, target);
888 }
889
890 static void do_binop(struct bb_state *state, struct instruction *insn, pseudo_t val1, pseudo_t val2)
891 {
892 const char *op = opcodes[insn->opcode];
893 struct operand *src = get_register_operand(state, val1, insn->target);
894 struct operand *src2 = get_generic_operand(state, val2);
895 struct hardreg *dst;
896
897 dst = target_copy_reg(state, src->reg, insn->target);
898 output_insn(state, "%s.%d %s,%s", op, insn->size, show_op(state, src2), dst->name);
899 put_operand(state, src);
900 put_operand(state, src2);
901 add_pseudo_reg(state, insn->target, dst);
902 }
903
904 static void generate_binop(struct bb_state *state, struct instruction *insn)
905 {
906 flush_cc_cache(state);
907 do_binop(state, insn, insn->src1, insn->src2);
908 }
909
910 static int is_dead_reg(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
911 {
912 pseudo_t p;
913 FOR_EACH_PTR(reg->contains, p) {
914 if (p == pseudo)
915 return CURRENT_TAG(p) & TAG_DEAD;
916 } END_FOR_EACH_PTR(p);
917 return 0;
918 }
919
920 /*
921 * Commutative binops are much more flexible, since we can switch the
922 * sources around to satisfy the target register, or to avoid having
923 * to load one of them into a register..
924 */
925 static void generate_commutative_binop(struct bb_state *state, struct instruction *insn)
926 {
927 pseudo_t src1, src2;
928 struct hardreg *reg1, *reg2;
929
930 flush_cc_cache(state);
931 src1 = insn->src1;
932 src2 = insn->src2;
933 reg2 = find_in_reg(state, src2);
934 if (!reg2)
935 goto dont_switch;
936 reg1 = find_in_reg(state, src1);
937 if (!reg1)
938 goto do_switch;
939 if (!is_dead_reg(state, src2, reg2))
940 goto dont_switch;
941 if (!is_dead_reg(state, src1, reg1))
942 goto do_switch;
943
944 /* Both are dead. Is one preferrable? */
945 if (reg2 != preferred_reg(state, insn->target))
946 goto dont_switch;
947
948 do_switch:
949 src1 = src2;
950 src2 = insn->src1;
951 dont_switch:
952 do_binop(state, insn, src1, src2);
953 }
954
955 /*
956 * This marks a pseudo dead. It still stays on the hardreg list (the hardreg
957 * still has its value), but it's scheduled to be killed after the next
958 * "sequence point" when we call "kill_read_pseudos()"
959 */
960 static void mark_pseudo_dead(struct bb_state *state, pseudo_t pseudo)
961 {
962 int i;
963 struct storage_hash *src;
964
965 if (state->cc_target == pseudo)
966 state->cc_dead = 1;
967 src = find_pseudo_storage(state, pseudo, NULL);
968 if (src)
969 src->flags |= TAG_DEAD;
970 for (i = 0; i < REGNO; i++)
971 mark_reg_dead(state, pseudo, hardregs + i);
972 }
973
974 static void kill_dead_pseudos(struct bb_state *state)
975 {
976 int i;
977
978 for (i = 0; i < REGNO; i++) {
979 kill_dead_reg(hardregs + i);
980 }
981 }
982
983 /*
984 * A PHI source can define a pseudo that we already
985 * have in another register. We need to invalidate the
986 * old register so that we don't end up with the same
987 * pseudo in "two places".
988 */
989 static void remove_pseudo_reg(struct bb_state *state, pseudo_t pseudo)
990 {
991 int i;
992
993 output_comment(state, "pseudo %s died", show_pseudo(pseudo));
994 for (i = 0; i < REGNO; i++) {
995 struct hardreg *reg = hardregs + i;
996 pseudo_t p;
997 FOR_EACH_PTR(reg->contains, p) {
998 if (p != pseudo)
999 continue;
1000 if (CURRENT_TAG(p) & TAG_DEAD)
1001 reg->dead--;
1002 DELETE_CURRENT_PTR(p);
1003 output_comment(state, "removed pseudo %s from reg %s", show_pseudo(pseudo), reg->name);
1004 } END_FOR_EACH_PTR(p);
1005 PACK_PTR_LIST(&reg->contains);
1006 }
1007 }
1008
1009 static void generate_store(struct instruction *insn, struct bb_state *state)
1010 {
1011 output_insn(state, "mov.%d %s,%s", insn->size, reg_or_imm(state, insn->target), address(state, insn));
1012 }
1013
1014 static void generate_load(struct instruction *insn, struct bb_state *state)
1015 {
1016 const char *input = address(state, insn);
1017 struct hardreg *dst;
1018
1019 kill_dead_pseudos(state);
1020 dst = target_reg(state, insn->target, NULL);
1021 output_insn(state, "mov.%d %s,%s", insn->size, input, dst->name);
1022 }
1023
1024 static void generate_phisource(struct instruction *insn, struct bb_state *state)
1025 {
1026 struct instruction *user;
1027 struct hardreg *reg;
1028
1029 /* Mark all the target pseudos dead first */
1030 FOR_EACH_PTR(insn->phi_users, user) {
1031 mark_pseudo_dead(state, user->target);
1032 } END_FOR_EACH_PTR(user);
1033
1034 reg = NULL;
1035 FOR_EACH_PTR(insn->phi_users, user) {
1036 if (!reg)
1037 reg = getreg(state, insn->phi_src, user->target);
1038 remove_pseudo_reg(state, user->target);
1039 add_pseudo_reg(state, user->target, reg);
1040 } END_FOR_EACH_PTR(user);
1041 }
1042
1043 static void generate_cast(struct bb_state *state, struct instruction *insn)
1044 {
1045 struct hardreg *src = getreg(state, insn->src, insn->target);
1046 struct hardreg *dst;
1047 unsigned int old = insn->orig_type ? insn->orig_type->bit_size : 0;
1048 unsigned int new = insn->size;
1049
1050 /*
1051 * Cast to smaller type? Ignore the high bits, we
1052 * just keep both pseudos in the same register.
1053 */
1054 if (old >= new) {
1055 add_pseudo_reg(state, insn->target, src);
1056 return;
1057 }
1058
1059 dst = target_copy_reg(state, src, insn->target);
1060
1061 if (insn->orig_type && (insn->orig_type->ctype.modifiers & MOD_SIGNED)) {
1062 output_insn(state, "sext.%d.%d %s", old, new, dst->name);
1063 } else {
1064 unsigned long long mask;
1065 mask = ~(~0ULL << old);
1066 mask &= ~(~0ULL << new);
1067 output_insn(state, "andl.%d $%#llx,%s", insn->size, mask, dst->name);
1068 }
1069 add_pseudo_reg(state, insn->target, dst);
1070 }
1071
1072 static void generate_output_storage(struct bb_state *state);
1073
1074 static const char *conditional[] = {
1075 [OP_SET_EQ] = "e",
1076 [OP_SET_NE] = "ne",
1077 [OP_SET_LE] = "le",
1078 [OP_SET_GE] = "ge",
1079 [OP_SET_LT] = "lt",
1080 [OP_SET_GT] = "gt",
1081 [OP_SET_B] = "b",
1082 [OP_SET_A] = "a",
1083 [OP_SET_BE] = "be",
1084 [OP_SET_AE] = "ae"
1085 };
1086
1087
1088 static void generate_branch(struct bb_state *state, struct instruction *br)
1089 {
1090 const char *cond = "XXX";
1091 struct basic_block *target;
1092
1093 if (br->cond) {
1094 if (state->cc_target == br->cond) {
1095 cond = conditional[state->cc_opcode];
1096 } else {
1097 struct hardreg *reg = getreg(state, br->cond, NULL);
1098 output_insn(state, "testl %s,%s", reg->name, reg->name);
1099 cond = "ne";
1100 }
1101 }
1102 generate_output_storage(state);
1103 target = br->bb_true;
1104 if (br->cond) {
1105 output_insn(state, "j%s .L%p", cond, target);
1106 target = br->bb_false;
1107 }
1108 output_insn(state, "jmp .L%p", target);
1109 }
1110
1111 /* We've made sure that there is a dummy reg live for the output */
1112 static void generate_switch(struct bb_state *state, struct instruction *insn)
1113 {
1114 struct hardreg *reg = hardregs + SWITCH_REG;
1115
1116 generate_output_storage(state);
1117 output_insn(state, "switch on %s", reg->name);
1118 output_insn(state, "unimplemented: %s", show_instruction(insn));
1119 }
1120
1121 static void generate_ret(struct bb_state *state, struct instruction *ret)
1122 {
1123 if (ret->src && ret->src != VOID) {
1124 struct hardreg *wants = hardregs+0;
1125 struct hardreg *reg = getreg(state, ret->src, NULL);
1126 if (reg != wants)
1127 output_insn(state, "movl %s,%s", reg->name, wants->name);
1128 }
1129 output_insn(state, "ret");
1130 }
1131
1132 /*
1133 * Fake "call" linearization just as a taster..
1134 */
1135 static void generate_call(struct bb_state *state, struct instruction *insn)
1136 {
1137 int offset = 0;
1138 pseudo_t arg;
1139
1140 FOR_EACH_PTR(insn->arguments, arg) {
1141 output_insn(state, "pushl %s", generic(state, arg));
1142 offset += 4;
1143 } END_FOR_EACH_PTR(arg);
1144 flush_reg(state, hardregs+0);
1145 flush_reg(state, hardregs+1);
1146 flush_reg(state, hardregs+2);
1147 output_insn(state, "call %s", show_pseudo(insn->func));
1148 if (offset)
1149 output_insn(state, "addl $%d,%%esp", offset);
1150 if (insn->target && insn->target != VOID)
1151 add_pseudo_reg(state, insn->target, hardregs+0);
1152 }
1153
1154 static void generate_select(struct bb_state *state, struct instruction *insn)
1155 {
1156 const char *cond;
1157 struct hardreg *src1, *src2, *dst;
1158
1159 src1 = getreg(state, insn->src2, NULL);
1160 dst = copy_reg(state, src1, insn->target);
1161 add_pseudo_reg(state, insn->target, dst);
1162 src2 = getreg(state, insn->src3, insn->target);
1163
1164 if (state->cc_target == insn->src1) {
1165 cond = conditional[state->cc_opcode];
1166 } else {
1167 struct hardreg *reg = getreg(state, insn->src1, NULL);
1168 output_insn(state, "testl %s,%s", reg->name, reg->name);
1169 cond = "ne";
1170 }
1171
1172 output_insn(state, "sel%s %s,%s", cond, src2->name, dst->name);
1173 }
1174
1175 struct asm_arg {
1176 const struct ident *name;
1177 const char *value;
1178 pseudo_t pseudo;
1179 struct hardreg *reg;
1180 };
1181
1182 static void replace_asm_arg(char **dst_p, struct asm_arg *arg)
1183 {
1184 char *dst = *dst_p;
1185 int len = strlen(arg->value);
1186
1187 memcpy(dst, arg->value, len);
1188 *dst_p = dst + len;
1189 }
1190
1191 static void replace_asm_percent(const char **src_p, char **dst_p, struct asm_arg *args, int nr)
1192 {
1193 const char *src = *src_p;
1194 char c;
1195 int index;
1196
1197 c = *src++;
1198 switch (c) {
1199 case '0' ... '9':
1200 index = c - '0';
1201 if (index < nr)
1202 replace_asm_arg(dst_p, args+index);
1203 break;
1204 }
1205 *src_p = src;
1206 return;
1207 }
1208
1209 static void replace_asm_named(const char **src_p, char **dst_p, struct asm_arg *args, int nr)
1210 {
1211 const char *src = *src_p;
1212 const char *end = src;
1213
1214 for(;;) {
1215 char c = *end++;
1216 if (!c)
1217 return;
1218 if (c == ']') {
1219 int i;
1220
1221 *src_p = end;
1222 for (i = 0; i < nr; i++) {
1223 const struct ident *ident = args[i].name;
1224 int len;
1225 if (!ident)
1226 continue;
1227 len = ident->len;
1228 if (memcmp(src, ident->name, len))
1229 continue;
1230 replace_asm_arg(dst_p, args+i);
1231 return;
1232 }
1233 }
1234 }
1235 }
1236
1237 static const char *replace_asm_args(const char *str, struct asm_arg *args, int nr)
1238 {
1239 static char buffer[1000];
1240 char *p = buffer;
1241
1242 for (;;) {
1243 char c = *str;
1244 *p = c;
1245 if (!c)
1246 return buffer;
1247 str++;
1248 switch (c) {
1249 case '%':
1250 if (*str == '%') {
1251 str++;
1252 p++;
1253 continue;
1254 }
1255 replace_asm_percent(&str, &p, args, nr);
1256 continue;
1257 case '[':
1258 replace_asm_named(&str, &p, args, nr);
1259 continue;
1260 default:
1261 break;
1262 }
1263 p++;
1264 }
1265 }
1266
1267 #define MAX_ASM_ARG (50)
1268 static struct asm_arg asm_arguments[MAX_ASM_ARG];
1269
1270 static struct asm_arg *generate_asm_inputs(struct bb_state *state, struct asm_constraint_list *list, struct asm_arg *arg)
1271 {
1272 struct asm_constraint *entry;
1273
1274 FOR_EACH_PTR(list, entry) {
1275 const char *constraint = entry->constraint;
1276 pseudo_t pseudo = entry->pseudo;
1277 struct hardreg *reg, *orig;
1278 const char *string;
1279 int index;
1280
1281 string = "undef";
1282 switch (*constraint) {
1283 case 'r':
1284 string = getreg(state, pseudo, NULL)->name;
1285 break;
1286 case '0' ... '9':
1287 index = *constraint - '0';
1288 reg = asm_arguments[index].reg;
1289 orig = find_in_reg(state, pseudo);
1290 if (orig)
1291 move_reg(state, orig, reg);
1292 else
1293 fill_reg(state, reg, pseudo);
1294 string = reg->name;
1295 break;
1296 default:
1297 string = generic(state, pseudo);
1298 break;
1299 }
1300
1301 output_insn(state, "# asm input \"%s\": %s : %s", constraint, show_pseudo(pseudo), string);
1302
1303 arg->name = entry->ident;
1304 arg->value = string;
1305 arg->pseudo = NULL;
1306 arg->reg = NULL;
1307 arg++;
1308 } END_FOR_EACH_PTR(entry);
1309 return arg;
1310 }
1311
1312 static struct asm_arg *generate_asm_outputs(struct bb_state *state, struct asm_constraint_list *list, struct asm_arg *arg)
1313 {
1314 struct asm_constraint *entry;
1315
1316 FOR_EACH_PTR(list, entry) {
1317 const char *constraint = entry->constraint;
1318 pseudo_t pseudo = entry->pseudo;
1319 struct hardreg *reg;
1320 const char *string;
1321
1322 while (*constraint == '=' || *constraint == '+')
1323 constraint++;
1324
1325 string = "undef";
1326 switch (*constraint) {
1327 case 'r':
1328 default:
1329 reg = target_reg(state, pseudo, NULL);
1330 arg->pseudo = pseudo;
1331 arg->reg = reg;
1332 string = reg->name;
1333 break;
1334 }
1335
1336 output_insn(state, "# asm output \"%s\": %s : %s", constraint, show_pseudo(pseudo), string);
1337
1338 arg->name = entry->ident;
1339 arg->value = string;
1340 arg++;
1341 } END_FOR_EACH_PTR(entry);
1342 return arg;
1343 }
1344
1345 static void generate_asm(struct bb_state *state, struct instruction *insn)
1346 {
1347 const char *str = insn->string;
1348
1349 if (insn->asm_rules->outputs || insn->asm_rules->inputs) {
1350 struct asm_arg *arg;
1351
1352 arg = generate_asm_outputs(state, insn->asm_rules->outputs, asm_arguments);
1353 arg = generate_asm_inputs(state, insn->asm_rules->inputs, arg);
1354 str = replace_asm_args(str, asm_arguments, arg - asm_arguments);
1355 }
1356 output_insn(state, "%s", str);
1357 }
1358
1359 static void generate_compare(struct bb_state *state, struct instruction *insn)
1360 {
1361 struct hardreg *src;
1362 const char *src2;
1363 int opcode;
1364
1365 flush_cc_cache(state);
1366 opcode = insn->opcode;
1367
1368 /*
1369 * We should try to switch these around if necessary,
1370 * and update the opcode to match..
1371 */
1372 src = getreg(state, insn->src1, insn->target);
1373 src2 = generic(state, insn->src2);
1374
1375 output_insn(state, "cmp.%d %s,%s", insn->size, src2, src->name);
1376
1377 add_cc_cache(state, opcode, insn->target);
1378 }
1379
1380 static void generate_one_insn(struct instruction *insn, struct bb_state *state)
1381 {
1382 if (verbose)
1383 output_comment(state, "%s", show_instruction(insn));
1384
1385 switch (insn->opcode) {
1386 case OP_ENTRY: {
1387 struct symbol *sym = insn->bb->ep->name;
1388 const char *name = show_ident(sym->ident);
1389 if (sym->ctype.modifiers & MOD_STATIC)
1390 printf("\n\n%s:\n", name);
1391 else
1392 printf("\n\n.globl %s\n%s:\n", name, name);
1393 break;
1394 }
1395
1396 /*
1397 * OP_PHI doesn't actually generate any code. It has been
1398 * done by the storage allocator and the OP_PHISOURCE.
1399 */
1400 case OP_PHI:
1401 break;
1402
1403 case OP_PHISOURCE:
1404 generate_phisource(insn, state);
1405 break;
1406
1407 /*
1408 * OP_SETVAL likewise doesn't actually generate any
1409 * code. On use, the "def" of the pseudo will be
1410 * looked up.
1411 */
1412 case OP_SETVAL:
1413 break;
1414
1415 case OP_STORE:
1416 generate_store(insn, state);
1417 break;
1418
1419 case OP_LOAD:
1420 generate_load(insn, state);
1421 break;
1422
1423 case OP_DEATHNOTE:
1424 mark_pseudo_dead(state, insn->target);
1425 return;
1426
1427 case OP_ADD: case OP_MULU: case OP_MULS:
1428 case OP_AND: case OP_OR: case OP_XOR:
1429 case OP_AND_BOOL: case OP_OR_BOOL:
1430 generate_commutative_binop(state, insn);
1431 break;
1432
1433 case OP_SUB: case OP_DIVU: case OP_DIVS:
1434 case OP_MODU: case OP_MODS:
1435 case OP_SHL: case OP_LSR: case OP_ASR:
1436 generate_binop(state, insn);
1437 break;
1438
1439 case OP_BINCMP ... OP_BINCMP_END:
1440 generate_compare(state, insn);
1441 break;
1442
1443 case OP_CAST: case OP_SCAST: case OP_FPCAST: case OP_PTRCAST:
1444 generate_cast(state, insn);
1445 break;
1446
1447 case OP_SEL:
1448 generate_select(state, insn);
1449 break;
1450
1451 case OP_BR:
1452 generate_branch(state, insn);
1453 break;
1454
1455 case OP_SWITCH:
1456 generate_switch(state, insn);
1457 break;
1458
1459 case OP_CALL:
1460 generate_call(state, insn);
1461 break;
1462
1463 case OP_RET:
1464 generate_ret(state, insn);
1465 break;
1466
1467 case OP_ASM:
1468 generate_asm(state, insn);
1469 break;
1470
1471 default:
1472 output_insn(state, "unimplemented: %s", show_instruction(insn));
1473 break;
1474 }
1475 kill_dead_pseudos(state);
1476 }
1477
1478 #define VERY_BUSY 1000
1479 #define REG_FIXED 2000
1480
1481 static void write_reg_to_storage(struct bb_state *state, struct hardreg *reg, pseudo_t pseudo, struct storage *storage)
1482 {
1483 int i;
1484 struct hardreg *out;
1485
1486 switch (storage->type) {
1487 case REG_REG:
1488 out = hardregs + storage->regno;
1489 if (reg == out)
1490 return;
1491 output_insn(state, "movl %s,%s", reg->name, out->name);
1492 return;
1493 case REG_UDEF:
1494 if (reg->busy < VERY_BUSY) {
1495 storage->type = REG_REG;
1496 storage->regno = reg - hardregs;
1497 reg->busy = REG_FIXED;
1498 return;
1499 }
1500
1501 /* Try to find a non-busy register.. */
1502 for (i = 0; i < REGNO; i++) {
1503 out = hardregs + i;
1504 if (out->contains)
1505 continue;
1506 output_insn(state, "movl %s,%s", reg->name, out->name);
1507 storage->type = REG_REG;
1508 storage->regno = i;
1509 out->busy = REG_FIXED;
1510 return;
1511 }
1512
1513 /* Fall back on stack allocation ... */
1514 alloc_stack(state, storage);
1515 /* Fallthroigh */
1516 default:
1517 output_insn(state, "movl %s,%s", reg->name, show_memop(storage));
1518 return;
1519 }
1520 }
1521
1522 static void write_val_to_storage(struct bb_state *state, pseudo_t src, struct storage *storage)
1523 {
1524 struct hardreg *out;
1525
1526 switch (storage->type) {
1527 case REG_UDEF:
1528 alloc_stack(state, storage);
1529 default:
1530 output_insn(state, "movl %s,%s", show_pseudo(src), show_memop(storage));
1531 break;
1532 case REG_REG:
1533 out = hardregs + storage->regno;
1534 output_insn(state, "movl %s,%s", show_pseudo(src), out->name);
1535 }
1536 }
1537
1538 static void fill_output(struct bb_state *state, pseudo_t pseudo, struct storage *out)
1539 {
1540 int i;
1541 struct storage_hash *in;
1542 struct instruction *def;
1543
1544 /* Is that pseudo a constant value? */
1545 switch (pseudo->type) {
1546 case PSEUDO_VAL:
1547 write_val_to_storage(state, pseudo, out);
1548 return;
1549 case PSEUDO_REG:
1550 def = pseudo->def;
1551 if (def->opcode == OP_SETVAL) {
1552 write_val_to_storage(state, pseudo, out);
1553 return;
1554 }
1555 default:
1556 break;
1557 }
1558
1559 /* See if we have that pseudo in a register.. */
1560 for (i = 0; i < REGNO; i++) {
1561 struct hardreg *reg = hardregs + i;
1562 pseudo_t p;
1563
1564 FOR_EACH_PTR(reg->contains, p) {
1565 if (p == pseudo) {
1566 write_reg_to_storage(state, reg, pseudo, out);
1567 return;
1568 }
1569 } END_FOR_EACH_PTR(p);
1570 }
1571
1572 /* Do we have it in another storage? */
1573 in = find_storage_hash(pseudo, state->internal);
1574 if (!in) {
1575 in = find_storage_hash(pseudo, state->inputs);
1576 /* Undefined? */
1577 if (!in)
1578 return;
1579 }
1580 switch (out->type) {
1581 case REG_UDEF:
1582 *out = *in->storage;
1583 break;
1584 case REG_REG:
1585 output_insn(state, "movl %s,%s", show_memop(in->storage), hardregs[out->regno].name);
1586 break;
1587 default:
1588 if (out == in->storage)
1589 break;
1590 if ((out->type == in->storage->type) && (out->regno == in->storage->regno))
1591 break;
1592 output_insn(state, "movl %s,%s", show_memop(in->storage), show_memop(out));
1593 break;
1594 }
1595 return;
1596 }
1597
1598 static int final_pseudo_flush(struct bb_state *state, pseudo_t pseudo, struct hardreg *reg)
1599 {
1600 struct storage_hash *hash;
1601 struct storage *out;
1602 struct hardreg *dst;
1603
1604 /*
1605 * Since this pseudo is live at exit, we'd better have output
1606 * storage for it..
1607 */
1608 hash = find_storage_hash(pseudo, state->outputs);
1609 if (!hash)
1610 return 1;
1611 out = hash->storage;
1612
1613 /* If the output is in a register, try to get it there.. */
1614 if (out->type == REG_REG) {
1615 dst = hardregs + out->regno;
1616 /*
1617 * Two good cases: nobody is using the right register,
1618 * or we've already set it aside for output..
1619 */
1620 if (!dst->contains || dst->busy > VERY_BUSY)
1621 goto copy_to_dst;
1622
1623 /* Aiee. Try to keep it in a register.. */
1624 dst = empty_reg(state);
1625 if (dst)
1626 goto copy_to_dst;
1627
1628 return 0;
1629 }
1630
1631 /* If the output is undefined, let's see if we can put it in a register.. */
1632 if (out->type == REG_UDEF) {
1633 dst = empty_reg(state);
1634 if (dst) {
1635 out->type = REG_REG;
1636 out->regno = dst - hardregs;
1637 goto copy_to_dst;
1638 }
1639 /* Uhhuh. Not so good. No empty registers right now */
1640 return 0;
1641 }
1642
1643 /* If we know we need to flush it, just do so already .. */
1644 output_insn(state, "movl %s,%s", reg->name, show_memop(out));
1645 return 1;
1646
1647 copy_to_dst:
1648 if (reg == dst)
1649 return 1;
1650 output_insn(state, "movl %s,%s", reg->name, dst->name);
1651 add_pseudo_reg(state, pseudo, dst);
1652 return 1;
1653 }
1654
1655 /*
1656 * This tries to make sure that we put all the pseudos that are
1657 * live on exit into the proper storage
1658 */
1659 static void generate_output_storage(struct bb_state *state)
1660 {
1661 struct storage_hash *entry;
1662
1663 /* Go through the fixed outputs, making sure we have those regs free */
1664 FOR_EACH_PTR(state->outputs, entry) {
1665 struct storage *out = entry->storage;
1666 if (out->type == REG_REG) {
1667 struct hardreg *reg = hardregs + out->regno;
1668 pseudo_t p;
1669 int flushme = 0;
1670
1671 reg->busy = REG_FIXED;
1672 FOR_EACH_PTR(reg->contains, p) {
1673 if (p == entry->pseudo) {
1674 flushme = -100;
1675 continue;
1676 }
1677 if (CURRENT_TAG(p) & TAG_DEAD)
1678 continue;
1679
1680 /* Try to write back the pseudo to where it should go ... */
1681 if (final_pseudo_flush(state, p, reg)) {
1682 DELETE_CURRENT_PTR(p);
1683 continue;
1684 }
1685 flushme++;
1686 } END_FOR_EACH_PTR(p);
1687 PACK_PTR_LIST(&reg->contains);
1688 if (flushme > 0)
1689 flush_reg(state, reg);
1690 }
1691 } END_FOR_EACH_PTR(entry);
1692
1693 FOR_EACH_PTR(state->outputs, entry) {
1694 fill_output(state, entry->pseudo, entry->storage);
1695 } END_FOR_EACH_PTR(entry);
1696 }
1697
1698 static void generate(struct basic_block *bb, struct bb_state *state)
1699 {
1700 int i;
1701 struct storage_hash *entry;
1702 struct instruction *insn;
1703
1704 for (i = 0; i < REGNO; i++) {
1705 free_ptr_list(&hardregs[i].contains);
1706 hardregs[i].busy = 0;
1707 hardregs[i].dead = 0;
1708 hardregs[i].used = 0;
1709 }
1710
1711 FOR_EACH_PTR(state->inputs, entry) {
1712 struct storage *storage = entry->storage;
1713 const char *name = show_storage(storage);
1714 output_comment(state, "incoming %s in %s", show_pseudo(entry->pseudo), name);
1715 if (storage->type == REG_REG) {
1716 int regno = storage->regno;
1717 add_pseudo_reg(state, entry->pseudo, hardregs + regno);
1718 name = hardregs[regno].name;
1719 }
1720 } END_FOR_EACH_PTR(entry);
1721
1722 output_label(state, ".L%p", bb);
1723 FOR_EACH_PTR(bb->insns, insn) {
1724 if (!insn->bb)
1725 continue;
1726 generate_one_insn(insn, state);
1727 } END_FOR_EACH_PTR(insn);
1728
1729 if (verbose) {
1730 output_comment(state, "--- in ---");
1731 FOR_EACH_PTR(state->inputs, entry) {
1732 output_comment(state, "%s <- %s", show_pseudo(entry->pseudo), show_storage(entry->storage));
1733 } END_FOR_EACH_PTR(entry);
1734 output_comment(state, "--- spill ---");
1735 FOR_EACH_PTR(state->internal, entry) {
1736 output_comment(state, "%s <-> %s", show_pseudo(entry->pseudo), show_storage(entry->storage));
1737 } END_FOR_EACH_PTR(entry);
1738 output_comment(state, "--- out ---");
1739 FOR_EACH_PTR(state->outputs, entry) {
1740 output_comment(state, "%s -> %s", show_pseudo(entry->pseudo), show_storage(entry->storage));
1741 } END_FOR_EACH_PTR(entry);
1742 }
1743 printf("\n");
1744 }
1745
1746 static void generate_list(struct basic_block_list *list, unsigned long generation)
1747 {
1748 struct basic_block *bb;
1749 FOR_EACH_PTR(list, bb) {
1750 if (bb->generation == generation)
1751 continue;
1752 output_bb(bb, generation);
1753 } END_FOR_EACH_PTR(bb);
1754 }
1755
1756 /*
1757 * Mark all the output registers of all the parents
1758 * as being "used" - this does not mean that we cannot
1759 * re-use them, but it means that we cannot ask the
1760 * parents to pass in another pseudo in one of those
1761 * registers that it already uses for another child.
1762 */
1763 static void mark_used_registers(struct basic_block *bb, struct bb_state *state)
1764 {
1765 struct basic_block *parent;
1766
1767 FOR_EACH_PTR(bb->parents, parent) {
1768 struct storage_hash_list *outputs = gather_storage(parent, STOR_OUT);
1769 struct storage_hash *entry;
1770
1771 FOR_EACH_PTR(outputs, entry) {
1772 struct storage *s = entry->storage;
1773 if (s->type == REG_REG) {
1774 struct hardreg *reg = hardregs + s->regno;
1775 reg->used = 1;
1776 }
1777 } END_FOR_EACH_PTR(entry);
1778 } END_FOR_EACH_PTR(parent);
1779 }
1780
1781 static void output_bb(struct basic_block *bb, unsigned long generation)
1782 {
1783 struct bb_state state;
1784
1785 bb->generation = generation;
1786
1787 /* Make sure all parents have been generated first */
1788 generate_list(bb->parents, generation);
1789
1790 state.pos = bb->pos;
1791 state.inputs = gather_storage(bb, STOR_IN);
1792 state.outputs = gather_storage(bb, STOR_OUT);
1793 state.internal = NULL;
1794 state.cc_opcode = 0;
1795 state.cc_target = NULL;
1796
1797 /* Mark incoming registers used */
1798 mark_used_registers(bb, &state);
1799
1800 generate(bb, &state);
1801
1802 free_ptr_list(&state.inputs);
1803 free_ptr_list(&state.outputs);
1804
1805 /* Generate all children... */
1806 generate_list(bb->children, generation);
1807 }
1808
1809 /*
1810 * We should set up argument sources here..
1811 *
1812 * Things like "first three arguments in registers" etc
1813 * are all for this place.
1814 *
1815 * On x86, we default to stack, unless it's a static
1816 * function that doesn't have its address taken.
1817 *
1818 * I should implement the -mregparm=X cmd line option.
1819 */
1820 static void set_up_arch_entry(struct entrypoint *ep, struct instruction *entry)
1821 {
1822 pseudo_t arg;
1823 struct symbol *sym, *argtype;
1824 int i, offset, regparm;
1825
1826 sym = ep->name;
1827 regparm = 0;
1828 if (!(sym->ctype.modifiers & MOD_ADDRESSABLE))
1829 regparm = 3;
1830 sym = sym->ctype.base_type;
1831 i = 0;
1832 offset = 0;
1833 PREPARE_PTR_LIST(sym->arguments, argtype);
1834 FOR_EACH_PTR(entry->arg_list, arg) {
1835 struct storage *in = lookup_storage(entry->bb, arg, STOR_IN);
1836 if (!in) {
1837 in = alloc_storage();
1838 add_storage(in, entry->bb, arg, STOR_IN);
1839 }
1840 if (i < regparm) {
1841 in->type = REG_REG;
1842 in->regno = i;
1843 } else {
1844 int bits = argtype ? argtype->bit_size : 0;
1845
1846 if (bits < bits_in_int)
1847 bits = bits_in_int;
1848
1849 in->type = REG_FRAME;
1850 in->offset = offset;
1851
1852 offset += bits >> 3;
1853 }
1854 i++;
1855 NEXT_PTR_LIST(argtype);
1856 } END_FOR_EACH_PTR(arg);
1857 FINISH_PTR_LIST(argtype);
1858 }
1859
1860 /*
1861 * Set up storage information for "return"
1862 *
1863 * Not strictly necessary, since the code generator will
1864 * certainly move the return value to the right register,
1865 * but it can help register allocation if the allocator
1866 * sees that the target register is going to return in %eax.
1867 */
1868 static void set_up_arch_exit(struct basic_block *bb, struct instruction *ret)
1869 {
1870 pseudo_t pseudo = ret->src;
1871
1872 if (pseudo && pseudo != VOID) {
1873 struct storage *out = lookup_storage(bb, pseudo, STOR_OUT);
1874 if (!out) {
1875 out = alloc_storage();
1876 add_storage(out, bb, pseudo, STOR_OUT);
1877 }
1878 out->type = REG_REG;
1879 out->regno = 0;
1880 }
1881 }
1882
1883 /*
1884 * Set up dummy/silly output storage information for a switch
1885 * instruction. We need to make sure that a register is available
1886 * when we generate code for switch, so force that by creating
1887 * a dummy output rule.
1888 */
1889 static void set_up_arch_switch(struct basic_block *bb, struct instruction *insn)
1890 {
1891 pseudo_t pseudo = insn->cond;
1892 struct storage *out = lookup_storage(bb, pseudo, STOR_OUT);
1893 if (!out) {
1894 out = alloc_storage();
1895 add_storage(out, bb, pseudo, STOR_OUT);
1896 }
1897 out->type = REG_REG;
1898 out->regno = SWITCH_REG;
1899 }
1900
1901 static void arch_set_up_storage(struct entrypoint *ep)
1902 {
1903 struct basic_block *bb;
1904
1905 /* Argument storage etc.. */
1906 set_up_arch_entry(ep, ep->entry);
1907
1908 FOR_EACH_PTR(ep->bbs, bb) {
1909 struct instruction *insn = last_instruction(bb->insns);
1910 if (!insn)
1911 continue;
1912 switch (insn->opcode) {
1913 case OP_RET:
1914 set_up_arch_exit(bb, insn);
1915 break;
1916 case OP_SWITCH:
1917 set_up_arch_switch(bb, insn);
1918 break;
1919 default:
1920 /* nothing */;
1921 }
1922 } END_FOR_EACH_PTR(bb);
1923 }
1924
1925 static void output(struct entrypoint *ep)
1926 {
1927 unsigned long generation = ++bb_generation;
1928
1929 last_reg = -1;
1930 stack_offset = 0;
1931
1932 /* Set up initial inter-bb storage links */
1933 set_up_storage(ep);
1934
1935 /* Architecture-specific storage rules.. */
1936 arch_set_up_storage(ep);
1937
1938 /* Show the results ... */
1939 output_bb(ep->entry->bb, generation);
1940
1941 /* Clear the storage hashes for the next function.. */
1942 free_storage();
1943 }
1944
1945 static int compile(struct symbol_list *list)
1946 {
1947 struct symbol *sym;
1948 FOR_EACH_PTR(list, sym) {
1949 struct entrypoint *ep;
1950 expand_symbol(sym);
1951 ep = linearize_symbol(sym);
1952 if (ep)
1953 output(ep);
1954 } END_FOR_EACH_PTR(sym);
1955
1956 return 0;
1957 }
1958
1959 int main(int argc, char **argv)
1960 {
1961 compile(sparse_initialize(argc, argv));
1962 while (*argv)
1963 compile(sparse(argv));
1964 return 0;
1965 }
1966
Static analysis for C