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