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