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