1 /* src/vm/optimizing/ssa2.c
4 CACAOVM - Verein zu Foerderung der freien virtuellen Machine CACAO
6 This file is part of CACAO.
8 This program is free software; you can redistribute it and/or
9 modify it under the terms of the GNU General Public License as
10 published by the Free Software Foundation; either version 2, or (at
11 your option) any later version.
13 This program is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
23 Reimplementation of code in ssa.c.
24 Uses the new dominator tree and the new CFG.
29 #include "mm/memory.h"
31 #include "toolbox/bitvector.h"
32 #include "toolbox/set.h"
33 #include "toolbox/worklist.h"
35 #include "vm/global.h"
36 #include "vm/jit/jit.hpp"
39 #define printf(...) do { if (getenv("VERB")) printf(__VA_ARGS__); } while (0)
40 #define show_method(...) do { if (getenv("VERB")) show_method(__VA_ARGS__); } while (0)
43 typedef struct phi_function {
48 typedef struct basicblock_info {
52 phi_function *phi_functions;
55 typedef struct var_info {
67 typedef struct ssa_info {
71 unsigned total_local_count;
74 static inline basicblock_info *bb_info(basicblock *bb) {
75 return (basicblock_info *)(bb->vp);
78 static ssa_info *ssa_init(jitdata *jd) {
84 ssa->vars_count = jd->localcount;
86 ssa->vars = DMNEW(var_info, ssa->vars_count);
87 MZERO(ssa->vars, var_info, ssa->vars_count);
88 for (i = 0; i < ssa->vars_count; ++i) {
89 ssa->vars[i].work = set_new(jd->basicblockcount);
95 static void ssa_place_phi_functions(ssa_info *ssa) {
97 basicblock *bptr, *Y, *n, **itdf;
103 for (bptr = ssa->jd->basicblocks; bptr; bptr = bptr->next) {
105 bbi = DNEW(basicblock_info);
106 bbi->defines = bv_new(ssa->vars_count);
107 bbi->phi = bv_new(ssa->vars_count);
112 for (iptr = bptr->iinstr; iptr != bptr->iinstr + bptr->icount; ++iptr) {
113 if (instruction_has_dst(iptr)) {
115 var_is_local(ssa->jd, iptr->dst.varindex)
118 bv_set_bit(bbi->defines, iptr->dst.varindex);
120 set_insert(ssa->vars[iptr->dst.varindex].work, bptr);
121 /* Accout definition */
122 ssa->vars[iptr->dst.varindex].num_defs += 1;
128 bptr = ssa->jd->basicblocks;
130 for (a = 0; a < ssa->vars_count; ++a) {
131 bv_set_bit(bbi->defines, a);
132 set_insert(ssa->vars[a].work, bptr);
133 ssa->vars[a].num_defs += 1;
136 for (a = 0; a < ssa->vars_count; ++a) {
137 work = ssa->vars[a].work;
138 while (! set_empty(work)) {
139 n = (basicblock *)set_pop(work);
141 itdf = n->domfrontier;
142 itdf != n->domfrontier + n->domfrontiercount;
146 if (! bv_get_bit(bb_info(Y)->phi, a)) {
147 bv_set_bit(bb_info(Y)->phi, a);
148 printf(" *** BB %d: phi for var %d\n", Y->nr, a);
149 bb_info(Y)->phi_count += 1;
150 ssa->vars[a].num_defs += 1;
151 if (! bv_get_bit(bb_info(Y)->defines, a)) {
160 static void ssa_create_phi_functions(ssa_info *ssa) {
162 basicblock_info *bbi;
166 for (bptr = ssa->jd->basicblocks; bptr; bptr = bptr->next) {
169 bbi->phi_functions = DMNEW(phi_function, bbi->phi_count);
170 itph = bbi->phi_functions;
172 for (i = 0; i < ssa->vars_count; ++i) {
173 if (bv_get_bit(bbi->phi, i)) {
175 itph->args = DMNEW(s4, bptr->predecessorcount);
176 for (j = 0; j < bptr->predecessorcount; ++j) {
185 static void ssa_calculate_offsets(ssa_info *ssa) {
187 unsigned cur_offset = ssa->jd->localcount;
189 ssa->total_local_count = 0;
191 for (i = 0; i < ssa->vars_count; ++i) {
193 ssa->vars[i].offset = cur_offset;
195 ssa->total_local_count += ssa->vars[i].num_defs;
197 if (ssa->vars[i].num_defs > 1) {
198 cur_offset += (ssa->vars[i].num_defs - 1);
204 static s4 ssa_rename_var(ssa_info *ssa, s4 var, unsigned index) {
207 if (var_is_local(ssa->jd, var)) {
208 assert(0 < index && index <= ssa->vars[var].num_defs);
212 return ssa->vars[var].offset + (index - 2);
214 assert(ret < ssa->total_local_count);
216 return ssa->total_local_count + (var - ssa->vars_count);
219 printf(" *** rename %c %d vers %d => %d\n", var_is_local(ssa->jd, var) ? 'L' : 'O', var, index, ret);
223 static void ssa_rename_uses(ssa_info *ssa, s4 *uses, unsigned uses_count) {
224 while (uses_count > 0) {
225 if (var_is_local(ssa->jd, *uses)) {
226 *uses = ssa_rename_var(ssa, *uses, *(ssa->vars[*uses].stack_top));
228 *uses = ssa_rename_var(ssa, *uses, 0);
235 static void ssa_rename_definition(ssa_info *ssa, s4 *pdef) {
239 if (var_is_local(ssa->jd, def)) {
240 ssa->vars[def].count += 1;
241 i = ssa->vars[def].count;
242 ssa->vars[def].stack_top += 1;
243 *(ssa->vars[def].stack_top) = i;
246 *pdef = ssa_rename_var(ssa, def, i);
249 static void ssa_rename_block(ssa_info *ssa, basicblock *bptr) {
251 basicblock_info *bbi = bb_info(bptr);
256 basicblock **itsucc, **itpred, **itdsucc, *Y;
264 orig_stack_top = DMNEW(s4 *, ssa->vars_count);
265 for (a = 0; a < ssa->vars_count; ++a) orig_stack_top[a] = ssa->vars[a].stack_top;
269 printf(" *** === %d ===========\n", bptr->nr);
271 ssa_rename_uses(ssa, bptr->invars, bptr->indepth);
273 /* Phi functions are the first instructions in the block */
274 printf(" *** --- phis ---------\n");
276 itph = bbi->phi_functions;
277 itph != bbi->phi_functions + bbi->phi_count;
280 ssa_rename_definition(ssa, &(itph->dst));
283 printf(" *** --- vars ---------\n");
285 if (bptr == ssa->jd->basicblocks) {
286 for (i = 0; i < ssa->jd->localcount; ++i) {
288 ssa_rename_definition(ssa, &tmp);
292 for (iptr = bptr->iinstr; iptr != bptr->iinstr + bptr->icount; ++iptr) {
298 switch (icmd_table[iptr->opc].dataflow) {
301 s[2] = iptr->sx.s23.s3.varindex;
306 s[1] = iptr->sx.s23.s2.varindex;
313 s[0] = iptr->s1.varindex;
323 uses = iptr->sx.s23.s2.args;
324 uses_count = iptr->s1.argcount;
329 printf(" *** %s uses ", icmd_table[iptr->opc].name);
330 for (jj = 0; jj < uses_count; ++jj) printf("%d ",uses[jj]);
333 if (uses_count > 0) {
334 /* Update uses, if there are any */
336 ssa_rename_uses(ssa, uses, uses_count);
338 /* If uses were s, then we need to update the instruction */
341 switch (uses_count) {
343 iptr->sx.s23.s3.varindex = s[2];
345 iptr->sx.s23.s2.varindex = s[1];
347 iptr->s1.varindex = s[0];
352 /* Rename definitions */
354 if (instruction_has_dst(iptr)) {
355 printf(" *** %s defines %d\n", icmd_table[iptr->opc].name, iptr->dst.varindex);
356 ssa_rename_definition(ssa, &(iptr->dst.varindex));
361 for (i = 0; i < bptr->outdepth; ++i) {
362 ssa_rename_definition(ssa, bptr->outvars + i);
367 printf(" *** succs %d\n", bptr->successorcount);
370 itsucc = bptr->successors;
371 itsucc != bptr->successors + bptr->successorcount;
377 itpred = Y->predecessors, j = 0;
378 itpred != Y->predecessors + Y->predecessorcount;
381 if (*itpred == bptr) break;
384 assert(j != Y->predecessorcount);
387 itph = bb_info(Y)->phi_functions;
388 itph != bb_info(Y)->phi_functions + bb_info(Y)->phi_count;
391 ssa_rename_uses(ssa, itph->args + j, 1);
398 itdsucc = bptr->domsuccessors;
399 itdsucc != bptr->domsuccessors + bptr->domsuccessorcount;
402 ssa_rename_block(ssa, *itdsucc);
405 /* For each definition of some variable a in the original S, pop stack */
408 for (a = 0; a < ssa->vars_count; ++a) ssa->vars[a].stack_top = orig_stack_top[a];
411 static void ssa_rename(ssa_info *ssa) {
414 for (i = 0; i < ssa->vars_count; ++i) {
415 ssa->vars[i].stack = DMNEW(unsigned, ssa->vars[i].num_defs + 1);
416 ssa->vars[i].stack[0] = 0;
417 ssa->vars[i].stack_top = ssa->vars[i].stack;
420 ssa_rename_block(ssa, ssa->jd->basicblocks);
423 static void ssa_export(ssa_info *ssa) {
425 jitdata *jd = ssa->jd;
426 methoddesc *md = jd->m->parseddesc;
430 vartop = ssa->total_local_count + jd->vartop - jd->localcount;
431 vars = DMNEW(varinfo, vartop);
433 printf(" *** vartop(%d) = ssa->total_local_count(%d) + jd->vartop(%d) - jd->localcount(%d)\n",
434 vartop , ssa->total_local_count , jd->vartop , jd->localcount);
438 /* Version 1 of each local */
440 for (i = 0; i < jd->localcount; ++i) {
441 *(it++) = jd->var[i];
444 /* Other versions of each local */
446 for (i = 0; i < jd->localcount; ++i) {
447 for (j = 1; j < ssa->vars[i].num_defs; ++j) {
448 *(it++) = jd->var[i];
454 for (i = jd->localcount; i < jd->vartop; ++i) {
455 *(it++) = jd->var[i];
459 jd->vartop = jd->varcount = vartop;
461 jd->local_map = DMREALLOC(jd->local_map, s4, 5 * jd->maxlocals, 5 * (jd->maxlocals + ssa->total_local_count - jd->localcount));
463 for (i = 0; i < ssa->total_local_count - jd->localcount; ++i) {
464 for (j = 0; j < 5; ++j) {
465 varindex = jd->localcount + i;
466 if (jd->var[varindex].type != j) {
469 jd->local_map[((jd->maxlocals + i) * 5) + j] = varindex;
473 jd->maxlocals += (ssa->total_local_count - jd->localcount);
474 jd->localcount = ssa->total_local_count;
476 printf(" *** jd->localcount %d, jd->maxlocals %d\n", jd->localcount , jd->maxlocals);
479 static unsigned get_predecessor_index(basicblock *from, basicblock *to) {
483 for (itpred = to->predecessors; itpred != to->predecessors + to->predecessorcount; ++itpred) {
484 if (*itpred == from) break;
488 if (j == to->predecessorcount) {
489 printf(" *** %d => %d\n", from->nr, to->nr);
490 assert(j != to->predecessorcount);
496 static basicblock *create_block(ssa_info *ssa, basicblock *from, basicblock *to) {
498 basicblock_info *toi;
501 unsigned j = get_predecessor_index(from, to);
503 mid = DNEW(basicblock);
504 MZERO(mid, basicblock, 1);
509 mid->nr = ssa->jd->basicblockcount;
510 ssa->jd->basicblockcount += 1;
513 mid->icount = toi->phi_count + 1;
514 iptr = mid->iinstr = DMNEW(instruction, mid->icount);
515 MZERO(mid->iinstr, instruction, mid->icount);
517 for (itph = toi->phi_functions; itph != toi->phi_functions + toi->phi_count; ++itph) {
518 iptr->opc = ICMD_COPY;
519 iptr->dst.varindex = itph->dst;
520 iptr->s1.varindex = itph->args[j];
521 assert(itph->dst < ssa->total_local_count);
522 assert(itph->args[j] < ssa->total_local_count);
526 iptr->opc = ICMD_GOTO;
527 iptr->dst.block = to;
538 static void crate_fallthrough(ssa_info *ssa, basicblock *bptr) {
540 basicblock_info *toi;
544 if (bptr->next == NULL) return;
546 j = get_predecessor_index(bptr, bptr->next);
548 toi = bb_info(bptr->next);
551 bptr->iinstr = DMREALLOC(bptr->iinstr, instruction, bptr->icount, bptr->icount + toi->phi_count);
552 iptr = bptr->iinstr + bptr->icount;
553 bptr->icount += toi->phi_count;
555 for (itph = toi->phi_functions; itph != toi->phi_functions + toi->phi_count; ++itph) {
556 iptr->opc = ICMD_COPY;
557 iptr->dst.varindex = itph->dst;
558 iptr->s1.varindex = itph->args[j];
559 assert(itph->dst < ssa->total_local_count);
560 assert(itph->args[j] < ssa->total_local_count);
566 static void ssa_create_phi_moves(ssa_info *ssa) {
571 branch_target_t *table;
572 lookup_target_t *lookup;
575 for (bptr = ssa->jd->basicblocks; bptr; bptr = bptr->next) {
576 if (bptr->type == 666) {
577 bptr->type = BBTYPE_STD;
580 if (! bptr->vp) continue;
581 if (! (bptr->flags >= BBREACHED)) continue;
583 for (iptr = bptr->iinstr; iptr != bptr->iinstr + bptr->icount; ++iptr) {
584 switch (icmd_table[iptr->opc].controlflow) {
588 iptr->dst.block = create_block(ssa, bptr, iptr->dst.block);
591 table = iptr->dst.table;
592 l = iptr->sx.s23.s2.tablelow;
593 i = iptr->sx.s23.s3.tablehigh;
595 i += 1; /* default */
597 table->block = create_block(ssa, bptr, table->block);
602 lookup = iptr->dst.lookup;
603 i = iptr->sx.s23.s2.lookupcount;
605 lookup->target.block = create_block(ssa, bptr, lookup->target.block);
608 iptr->sx.s23.s3.lookupdefault.block = create_block(ssa, bptr, iptr->sx.s23.s3.lookupdefault.block);
611 iptr->sx.s23.s3.jsrtarget.block = create_block(ssa, bptr, iptr->sx.s23.s3.jsrtarget.block);
614 if ((iptr->opc == ICMD_GOTO) || icmd_table[iptr->opc].controlflow == CF_END)
616 else if (iptr->opc != ICMD_NOP)
619 if (! bptr->next) continue;
620 if (! (bptr->next->flags >= BBREACHED)) continue;
621 if (bptr->next->type == 666) continue;
622 if (!gt) crate_fallthrough(ssa, bptr);
626 void xssa(jitdata *jd) {
627 ssa_info *ssa = ssa_init(jd);
629 printf("=============== [ before %s ] =========================\n", jd->m->name->text);
631 printf("=============== [ /before ] =========================\n");
633 ssa_place_phi_functions(ssa);
634 ssa_create_phi_functions(ssa);
635 ssa_calculate_offsets(ssa);
638 ssa_create_phi_moves(ssa);
640 printf("=============== [ after ] =========================\n");
642 printf("=============== [ /after ] =========================\n");
646 * These are local overrides for various environment variables in Emacs.
647 * Please do not remove this and leave it at the end of the file, where
648 * Emacs will automagically detect them.
649 * ---------------------------------------------------------------------
652 * indent-tabs-mode: t
656 * vim:noexpandtab:sw=4:ts=4: