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