?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Teach register "allocator" about preferred register targets.
[smatch.git] / example.c
blobf589610467e86b43386a0a4950625db7ad0a5fc3
1 /*
2 * Example of how to write a compiler with sparse
3 */
4 #include <stdio.h>
5 #include <stdlib.h>
6 #include <assert.h>
7
8 #include "symbol.h"
9 #include "expression.h"
10 #include "linearize.h"
11 #include "flow.h"
12 #include "storage.h"
13
14 struct hardreg {
15 const char *name;
16 pseudo_t contains;
17 unsigned busy:1,
18 dirty:1,
19 used:1;
20 };
21
22 static void output_bb(struct basic_block *bb, unsigned long generation);
23
24 /*
25 * We only know about the caller-clobbered registers
26 * right now.
27 */
28 static struct hardreg hardregs[] = {
29 { .name = "eax" },
30 { .name = "edx" },
31 { .name = "ecx" },
32 { .name = "ebx" },
33 { .name = "esi" },
34 { .name = "edi" },
35 };
36 #define REGNO (sizeof(hardregs)/sizeof(struct hardreg))
37
38 struct bb_state {
39 struct basic_block *bb;
40 unsigned long stack_offset;
41 struct storage_hash_list *inputs;
42 struct storage_hash_list *outputs;
43 struct storage_hash_list *internal;
44 };
45
46 static struct storage_hash *find_storage_hash(pseudo_t pseudo, struct storage_hash_list *list)
47 {
48 struct storage_hash *entry;
49 FOR_EACH_PTR(list, entry) {
50 if (entry->pseudo == pseudo)
51 return entry;
52 } END_FOR_EACH_PTR(entry);
53 return NULL;
54 }
55
56 static struct storage_hash *find_or_create_hash(pseudo_t pseudo, struct storage_hash_list **listp)
57 {
58 struct storage_hash *entry;
59
60 entry = find_storage_hash(pseudo, *listp);
61 if (!entry) {
62 entry = alloc_storage_hash(alloc_storage());
63 entry->pseudo = pseudo;
64 add_ptr_list(listp, entry);
65 }
66 return entry;
67 }
68
69 static const char *show_memop(struct storage *storage)
70 {
71 static char buffer[1000];
72 switch (storage->type) {
73 case REG_ARG:
74 sprintf(buffer, "%d(FP)", storage->regno * 4);
75 break;
76 case REG_STACK:
77 sprintf(buffer, "%d(SP)", storage->offset);
78 break;
79 case REG_REG:
80 return hardregs[storage->regno].name;
81 default:
82 return show_storage(storage);
83 }
84 return buffer;
85 }
86
87 static void alloc_stack(struct bb_state *state, struct storage *storage)
88 {
89 storage->type = REG_STACK;
90 storage->offset = state->stack_offset;
91 state->stack_offset += 4;
92 }
93
94 /* Flush a hardreg out to the storage it has.. */
95 static void flush_reg(struct bb_state *state, struct hardreg *hardreg)
96 {
97 pseudo_t pseudo;
98 struct storage_hash *out;
99 struct storage *storage;
100
101 if (!hardreg->busy || !hardreg->dirty)
102 return;
103 hardreg->busy = 0;
104 hardreg->dirty = 0;
105 hardreg->used = 1;
106 pseudo = hardreg->contains;
107 if (!pseudo)
108 return;
109 if (pseudo->type != PSEUDO_REG && pseudo->type != PSEUDO_ARG)
110 return;
111
112 out = find_storage_hash(pseudo, state->internal);
113 if (!out) {
114 out = find_storage_hash(pseudo, state->outputs);
115 if (!out)
116 out = find_or_create_hash(pseudo, &state->internal);
117 }
118 storage = out->storage;
119 switch (storage->type) {
120 default:
121 /*
122 * Aieee - the next user wants it in a register, but we
123 * need to flush it to memory in between. Which means that
124 * we need to allocate an internal one, dammit..
125 */
126 out = find_or_create_hash(pseudo, &state->internal);
127 storage = out->storage;
128 /* Fall through */
129 case REG_UDEF:
130 alloc_stack(state, storage);
131 /* Fall through */
132 case REG_STACK:
133 printf("\tmovl %s,%s\n", hardreg->name, show_memop(storage));
134 break;
135 }
136 }
137
138 /* Fill a hardreg with the pseudo it has */
139 static struct hardreg *fill_reg(struct bb_state *state, struct hardreg *hardreg, pseudo_t pseudo)
140 {
141 struct storage_hash *src;
142 struct instruction *def;
143
144 switch (pseudo->type) {
145 case PSEUDO_VAL:
146 printf("\tmovl $%lld,%s\n", pseudo->value, hardreg->name);
147 break;
148 case PSEUDO_SYM:
149 printf("\tmovl $<%s>,%s\n", show_pseudo(pseudo), hardreg->name);
150 break;
151 case PSEUDO_ARG:
152 case PSEUDO_REG:
153 def = pseudo->def;
154 if (def->opcode == OP_SETVAL) {
155 printf("\tmovl $<%s>,%s\n", show_pseudo(def->symbol), hardreg->name);
156 break;
157 }
158 src = find_storage_hash(pseudo, state->internal);
159 if (!src) {
160 src = find_storage_hash(pseudo, state->inputs);
161 if (!src) {
162 src = find_storage_hash(pseudo, state->outputs);
163 /* Undefined? Screw it! */
164 if (!src) {
165 printf("\tundef %s ??\n", show_pseudo(pseudo));
166 break;
167 }
168 }
169 }
170 if (src->storage->type == REG_UDEF) {
171 if (!hardreg->used) {
172 src->storage->type = REG_REG;
173 src->storage->regno = hardreg - hardregs;
174 break;
175 }
176 alloc_stack(state, src->storage);
177 }
178 printf("\tmov.%d %s,%s\n", 32, show_memop(src->storage), hardreg->name);
179 break;
180 default:
181 printf("\treload %s from %s\n", hardreg->name, show_pseudo(pseudo));
182 break;
183 }
184 return hardreg;
185 }
186
187 static int last_reg;
188
189 static struct hardreg *target_reg(struct bb_state *state, pseudo_t pseudo, pseudo_t target)
190 {
191 int i;
192 struct hardreg *reg;
193 struct storage_hash *dst;
194
195 /* First, see if we have a preferred target register.. */
196 dst = find_storage_hash(target, state->outputs);
197 if (dst) {
198 struct storage *storage = dst->storage;
199 if (storage->type == REG_REG) {
200 reg = hardregs + storage->regno;
201 if (!reg->busy)
202 goto found;
203 }
204 }
205
206 i = last_reg+1;
207 if (i >= REGNO)
208 i = 0;
209 last_reg = i;
210 reg = hardregs + i;
211 flush_reg(state, reg);
212
213 found:
214 reg->contains = pseudo;
215 reg->busy = 1;
216 reg->dirty = 0;
217 return reg;
218 }
219
220 static struct hardreg *getreg(struct bb_state *state, pseudo_t pseudo, pseudo_t target)
221 {
222 int i;
223 struct hardreg *reg;
224
225 for (i = 0; i < REGNO; i++) {
226 if (hardregs[i].contains == pseudo) {
227 last_reg = i;
228 return hardregs+i;
229 }
230 }
231 reg = target_reg(state, pseudo, target);
232 return fill_reg(state, reg, pseudo);
233 }
234
235 static const char *address(struct bb_state *state, struct instruction *memop)
236 {
237 struct symbol *sym;
238 struct hardreg *base;
239 static char buffer[100];
240 pseudo_t addr = memop->src;
241
242 switch(addr->type) {
243 case PSEUDO_SYM:
244 sym = addr->sym;
245 if (sym->ctype.modifiers & MOD_NONLOCAL) {
246 sprintf(buffer, "%s+%d", show_ident(sym->ident), memop->offset);
247 return buffer;
248 }
249 sprintf(buffer, "%d+%s(SP)", memop->offset, show_ident(sym->ident));
250 return buffer;
251 default:
252 base = getreg(state, addr, NULL);
253 sprintf(buffer, "%d(%s)", memop->offset, base->name);
254 return buffer;
255 }
256 }
257
258 static const char *reg_or_imm(struct bb_state *state, pseudo_t pseudo)
259 {
260 switch(pseudo->type) {
261 case PSEUDO_VAL:
262 return show_pseudo(pseudo);
263 default:
264 return getreg(state, pseudo, NULL)->name;
265 }
266 }
267
268 static void generate_store(struct instruction *insn, struct bb_state *state)
269 {
270 printf("\tmov.%d %s,%s\n", insn->size, reg_or_imm(state, insn->target), address(state, insn));
271 }
272
273 static void generate_load(struct instruction *insn, struct bb_state *state)
274 {
275 const char *input = address(state, insn);
276 printf("\tmov.%d %s,%s\n", insn->size, input, target_reg(state, insn->target, NULL)->name);
277 }
278
279 static const char* opcodes[] = {
280 [OP_BADOP] = "bad_op",
281
282 /* Fn entrypoint */
283 [OP_ENTRY] = "<entry-point>",
284
285 /* Terminator */
286 [OP_RET] = "ret",
287 [OP_BR] = "br",
288 [OP_SWITCH] = "switch",
289 [OP_INVOKE] = "invoke",
290 [OP_COMPUTEDGOTO] = "jmp *",
291 [OP_UNWIND] = "unwind",
292
293 /* Binary */
294 [OP_ADD] = "add",
295 [OP_SUB] = "sub",
296 [OP_MUL] = "mul",
297 [OP_DIV] = "div",
298 [OP_MOD] = "mod",
299 [OP_SHL] = "shl",
300 [OP_SHR] = "shr",
301
302 /* Logical */
303 [OP_AND] = "and",
304 [OP_OR] = "or",
305 [OP_XOR] = "xor",
306 [OP_AND_BOOL] = "and-bool",
307 [OP_OR_BOOL] = "or-bool",
308
309 /* Binary comparison */
310 [OP_SET_EQ] = "seteq",
311 [OP_SET_NE] = "setne",
312 [OP_SET_LE] = "setle",
313 [OP_SET_GE] = "setge",
314 [OP_SET_LT] = "setlt",
315 [OP_SET_GT] = "setgt",
316 [OP_SET_B] = "setb",
317 [OP_SET_A] = "seta",
318 [OP_SET_BE] = "setbe",
319 [OP_SET_AE] = "setae",
320
321 /* Uni */
322 [OP_NOT] = "not",
323 [OP_NEG] = "neg",
324
325 /* Special three-input */
326 [OP_SEL] = "select",
327
328 /* Memory */
329 [OP_MALLOC] = "malloc",
330 [OP_FREE] = "free",
331 [OP_ALLOCA] = "alloca",
332 [OP_LOAD] = "load",
333 [OP_STORE] = "store",
334 [OP_SETVAL] = "set",
335 [OP_GET_ELEMENT_PTR] = "getelem",
336
337 /* Other */
338 [OP_PHI] = "phi",
339 [OP_PHISOURCE] = "phisrc",
340 [OP_CAST] = "cast",
341 [OP_PTRCAST] = "ptrcast",
342 [OP_CALL] = "call",
343 [OP_VANEXT] = "va_next",
344 [OP_VAARG] = "va_arg",
345 [OP_SLICE] = "slice",
346 [OP_SNOP] = "snop",
347 [OP_LNOP] = "lnop",
348 [OP_NOP] = "nop",
349 [OP_DEATHNOTE] = "dead",
350 [OP_ASM] = "asm",
351
352 /* Sparse tagging (line numbers, context, whatever) */
353 [OP_CONTEXT] = "context",
354 };
355
356
357 static struct hardreg *copy_reg(struct bb_state *state, struct hardreg *src)
358 {
359 int i;
360
361 if (!src->busy)
362 return src;
363
364 for (i = 0; i < REGNO; i++) {
365 struct hardreg *reg = hardregs + i;
366 if (!reg->busy) {
367 printf("\tmovl %s,%s\n", src->name, reg->name);
368 return reg;
369 }
370 }
371
372 flush_reg(state, src);
373 return src;
374 }
375
376 static void generate_binop(struct bb_state *state, struct instruction *insn)
377 {
378 const char *op = opcodes[insn->opcode];
379 struct hardreg *src = getreg(state, insn->src1, NULL);
380 struct hardreg *dst = copy_reg(state, src);
381
382 printf("\t%s.%d %s,%s\n", op, insn->size, reg_or_imm(state, insn->src2), dst->name);
383 dst->contains = insn->target;
384 dst->busy = 1;
385 dst->dirty = 1;
386 }
387
388 static void mark_pseudo_dead(pseudo_t pseudo)
389 {
390 int i;
391
392 for (i = 0; i < REGNO; i++) {
393 if (hardregs[i].contains == pseudo) {
394 hardregs[i].busy = 0;
395 hardregs[i].dirty = 0;
396 }
397 }
398 }
399
400 static void generate_phisource(struct instruction *insn, struct bb_state *state)
401 {
402 struct instruction *user = first_instruction(insn->phi_users);
403 struct hardreg *reg;
404
405 if (!user)
406 return;
407 reg = getreg(state, insn->phi_src, user->target);
408
409 flush_reg(state, reg);
410 reg->contains = user->target;
411 reg->busy = 1;
412 reg->dirty = 1;
413 }
414
415 static void generate_output_storage(struct bb_state *state);
416
417 static void generate_branch(struct bb_state *state, struct instruction *br)
418 {
419 if (br->cond) {
420 struct hardreg *reg = getreg(state, br->cond, NULL);
421 printf("\ttestl %s,%s\n", reg->name, reg->name);
422 }
423 generate_output_storage(state);
424 if (br->cond)
425 printf("\tje .L%p\n", br->bb_false);
426 printf("\tjmp .L%p\n", br->bb_true);
427 }
428
429 static void generate_one_insn(struct instruction *insn, struct bb_state *state)
430 {
431 switch (insn->opcode) {
432 case OP_ENTRY: {
433 struct symbol *sym = insn->bb->ep->name;
434 const char *name = show_ident(sym->ident);
435 if (sym->ctype.modifiers & MOD_STATIC)
436 printf("\n\n%s:\n", name);
437 else
438 printf("\n\n.globl %s\n%s:\n", name, name);
439 break;
440 }
441
442 /*
443 * OP_PHI doesn't actually generate any code. It has been
444 * done by the storage allocator and the OP_PHISOURCE.
445 */
446 case OP_PHI:
447 break;
448
449 case OP_PHISOURCE:
450 generate_phisource(insn, state);
451 break;
452
453 /*
454 * OP_SETVAL likewise doesn't actually generate any
455 * code. On use, the "def" of the pseudo will be
456 * looked up.
457 */
458 case OP_SETVAL:
459 break;
460
461 case OP_STORE:
462 generate_store(insn, state);
463 break;
464
465 case OP_LOAD:
466 generate_load(insn, state);
467 break;
468
469 case OP_DEATHNOTE:
470 mark_pseudo_dead(insn->target);
471 break;
472
473 case OP_BINARY ... OP_BINARY_END:
474 case OP_BINCMP ... OP_BINCMP_END:
475 generate_binop(state, insn);
476 break;
477
478 case OP_BR:
479 generate_branch(state, insn);
480 break;
481
482 default:
483 show_instruction(insn);
484 break;
485 }
486 }
487
488 static void write_reg_to_storage(struct bb_state *state, struct hardreg *reg, struct storage *storage)
489 {
490 struct hardreg *out;
491
492 switch (storage->type) {
493 case REG_UDEF:
494 storage->type = REG_REG;
495 storage->regno = reg - hardregs;
496 return;
497 case REG_REG:
498 out = hardregs + storage->regno;
499 if (reg == out)
500 return;
501 assert(!out->contains);
502 printf("\tmovl %s,%s\n", reg->name, out->name);
503 return;
504 default:
505 printf("\tmovl %s,%s\n", reg->name, show_memop(storage));
506 return;
507 }
508 }
509
510 static void write_val_to_storage(struct bb_state *state, pseudo_t src, struct storage *storage)
511 {
512 struct hardreg *out;
513
514 switch (storage->type) {
515 case REG_UDEF:
516 alloc_stack(state, storage);
517 default:
518 printf("\tmovl %s,%s\n", show_pseudo(src), show_memop(storage));
519 break;
520 case REG_REG:
521 out = hardregs + storage->regno;
522 printf("\tmovl %s,%s\n", show_pseudo(src), out->name);
523 }
524 }
525
526 static void fill_output(struct bb_state *state, pseudo_t pseudo, struct storage *out)
527 {
528 int i;
529 struct storage_hash *in;
530 struct instruction *def;
531
532 /* Is that pseudo a constant value? */
533 switch (pseudo->type) {
534 case PSEUDO_VAL:
535 write_val_to_storage(state, pseudo, out);
536 return;
537 case PSEUDO_REG:
538 def = pseudo->def;
539 if (def->opcode == OP_SETVAL) {
540 write_val_to_storage(state, def->symbol, out);
541 return;
542 }
543 default:
544 break;
545 }
546
547 /* See if we have that pseudo in a register.. */
548 for (i = 0; i < REGNO; i++) {
549 struct hardreg *reg = hardregs + i;
550 if (reg->contains != pseudo)
551 continue;
552 write_reg_to_storage(state, reg, out);
553 return;
554 }
555
556 /* Do we have it in another storage? */
557 in = find_storage_hash(pseudo, state->internal);
558 if (!in) {
559 in = find_storage_hash(pseudo, state->inputs);
560 /* Undefined? */
561 if (!in)
562 return;
563 }
564 switch (out->type) {
565 case REG_UDEF:
566 *out = *in->storage;
567 break;
568 case REG_REG:
569 printf("\tmovl %s,%s\n", show_memop(in->storage), hardregs[out->regno].name);
570 break;
571 default:
572 printf("\tmovl %s,tmp\n", show_memop(in->storage));
573 printf("\tmovl tmp,%s\n", show_memop(out));
574 break;
575 }
576 return;
577 }
578
579 /*
580 * This tries to make sure that we put all the pseudos that are
581 * live on exit into the proper storage
582 */
583 static void generate_output_storage(struct bb_state *state)
584 {
585 struct storage_hash *entry;
586
587 /* Go through the fixed outputs, making sure we have those regs free */
588 FOR_EACH_PTR(state->outputs, entry) {
589 struct storage *out = entry->storage;
590 if (out->type == REG_REG) {
591 struct hardreg *reg = hardregs + out->regno;
592 if (reg->contains != entry->pseudo) {
593 flush_reg(state, reg);
594 reg->contains = NULL;
595 }
596 }
597 } END_FOR_EACH_PTR(entry);
598
599 FOR_EACH_PTR(state->outputs, entry) {
600 fill_output(state, entry->pseudo, entry->storage);
601 } END_FOR_EACH_PTR(entry);
602 }
603
604 static void generate(struct basic_block *bb, struct bb_state *state)
605 {
606 int i;
607 struct storage_hash *entry;
608 struct instruction *insn;
609
610 for (i = 0; i < REGNO; i++) {
611 hardregs[i].contains = NULL;
612 hardregs[i].busy = 0;
613 hardregs[i].dirty = 0;
614 hardregs[i].used = 0;
615 }
616
617 FOR_EACH_PTR(state->inputs, entry) {
618 struct storage *storage = entry->storage;
619 const char *name = show_storage(storage);
620 if (storage->type == REG_REG) {
621 int regno = storage->regno;
622 hardregs[regno].contains = entry->pseudo;
623 hardregs[regno].busy = 1;
624 hardregs[regno].dirty = 1;
625 name = hardregs[regno].name;
626 }
627 } END_FOR_EACH_PTR(entry);
628
629 printf(".L%p:\n", bb);
630 FOR_EACH_PTR(bb->insns, insn) {
631 if (!insn->bb)
632 continue;
633 generate_one_insn(insn, state);
634 } END_FOR_EACH_PTR(insn);
635
636 if (verbose) {
637 printf("\t---\n");
638 FOR_EACH_PTR(state->inputs, entry) {
639 printf("\t%s <- %s\n", show_pseudo(entry->pseudo), show_storage(entry->storage));
640 } END_FOR_EACH_PTR(entry);
641 printf("\t---\n");
642 FOR_EACH_PTR(state->internal, entry) {
643 printf("\t%s <-> %s\n", show_pseudo(entry->pseudo), show_storage(entry->storage));
644 } END_FOR_EACH_PTR(entry);
645 printf("\t---\n");
646 FOR_EACH_PTR(state->outputs, entry) {
647 printf("\t%s -> %s\n", show_pseudo(entry->pseudo), show_storage(entry->storage));
648 } END_FOR_EACH_PTR(entry);
649 }
650 printf("\n");
651 }
652
653 static void generate_list(struct basic_block_list *list, unsigned long generation)
654 {
655 struct basic_block *bb;
656 FOR_EACH_PTR(list, bb) {
657 if (bb->generation == generation)
658 continue;
659 output_bb(bb, generation);
660 } END_FOR_EACH_PTR(bb);
661 }
662
663 static void output_bb(struct basic_block *bb, unsigned long generation)
664 {
665 struct bb_state state;
666
667 bb->generation = generation;
668
669 /* Make sure all parents have been generated first */
670 generate_list(bb->parents, generation);
671
672 state.inputs = gather_storage(bb, STOR_IN);
673 state.outputs = gather_storage(bb, STOR_OUT);
674 state.internal = NULL;
675 state.stack_offset = 0;
676
677 generate(bb, &state);
678
679 free_ptr_list(&state.inputs);
680 free_ptr_list(&state.outputs);
681
682 /* Generate all children... */
683 generate_list(bb->children, generation);
684 }
685
686 static void output(struct entrypoint *ep)
687 {
688 unsigned long generation = ++bb_generation;
689
690 last_reg = -1;
691
692 /* Set up initial inter-bb storage links */
693 set_up_storage(ep);
694
695 /* Show the results ... */
696 output_bb(ep->entry->bb, generation);
697
698 /* Clear the storage hashes for the next function.. */
699 free_storage();
700 }
701
702 static int compile(struct symbol_list *list)
703 {
704 struct symbol *sym;
705 FOR_EACH_PTR(list, sym) {
706 struct entrypoint *ep;
707 expand_symbol(sym);
708 ep = linearize_symbol(sym);
709 if (ep)
710 output(ep);
711 } END_FOR_EACH_PTR(sym);
712
713 return 0;
714 }
715
716 int main(int argc, char **argv)
717 {
718 return compile(sparse(argc, argv));
719 }
720
Static analysis for C