1 /* src/vm/jit/optimizing/graph.c - CFG
3 Copyright (C) 2005, 2006 R. Grafl, A. Krall, C. Kruegel, C. Oates,
4 R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
5 C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
6 Institut f. Computersprachen - TU Wien
8 This file is part of CACAO.
10 This program is free software; you can redistribute it and/or
11 modify it under the terms of the GNU General Public License as
12 published by the Free Software Foundation; either version 2, or (at
13 your option) any later version.
15 This program is distributed in the hope that it will be useful, but
16 WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 General Public License for more details.
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
25 Contact: cacao@complang.tuwien.ac.at
27 Authors: Christian Ullrich
37 #include "mm/memory.h"
39 #include "toolbox/bitvector.h"
41 #include "vm/jit/jit.h"
43 #include "vm/jit/optimizing/lsra.h"
44 #include "vm/jit/optimizing/ssa.h"
45 #include "vm/jit/optimizing/graph.h"
47 #ifdef GRAPH_DEBUG_VERBOSE
48 #include "vmcore/options.h"
51 /* Helpers for graph_make_cfg */
52 void graph_add_cfg( jitdata *jd, graphdata *gd, basicblock *, basicblock *);
53 void graph_add_exceptions(jitdata *jd, graphdata *gd);
54 void graph_add_edge( graphdata *gd, int from, int to );
56 /* Helper for graph_get_first_* */
57 int graph_get_first_(graph_element *ge, graphiterator *i);
58 void transform_CFG(jitdata *, graphdata *);
60 #ifdef GRAPH_DEBUG_VERBOSE
61 void graph_print(lsradata *ls, graphdata *gd);
65 graphdata *graph_init(int basicblockcount) {
70 #ifdef GRAPH_DEBUG_CHECK
71 /* Remember basicblockcount, so Array Bound checks can be made */
72 gd->basicblockcount = basicblockcount;
75 gd->num_succ = DMNEW(int, basicblockcount);
76 gd->successor = DMNEW(graph_element *, basicblockcount);
78 gd->num_pred = DMNEW(int, basicblockcount);
79 gd->predecessor = DMNEW(graph_element *, basicblockcount);
81 for(i = 0; i < basicblockcount; i++) {
82 gd->num_succ[i] = gd->num_pred[i] = 0;
83 gd->successor[i] = NULL;
84 gd->predecessor[i] = NULL;
89 int graph_get_num_predecessor(graphdata *gd, int b_index) {
90 _GRAPH_CHECK_BOUNDS(b_index, 0, gd->basicblockcount);
91 return gd->num_pred[b_index];
94 int graph_get_num_successor(graphdata *gd, int b_index) {
95 _GRAPH_CHECK_BOUNDS(b_index, 0, gd->basicblockcount);
96 return gd->num_succ[b_index];
99 int graph_get_first_successor(graphdata *gd, int b_index, graphiterator *i) {
100 _GRAPH_CHECK_BOUNDS(b_index, 0, gd->basicblockcount);
101 return graph_get_first_(gd->successor[b_index], i);
104 int graph_get_first_predecessor(graphdata *gd, int b_index, graphiterator *i) {
105 _GRAPH_CHECK_BOUNDS(b_index, 0, gd->basicblockcount);
106 return graph_get_first_(gd->predecessor[b_index], i);
109 int graph_get_next(graphiterator *i) {
119 int graph_get_first_(graph_element *ge, graphiterator *i) {
120 if ( ((*i) = ge) == NULL)
126 bool graph_has_multiple_predecessors( graphdata *gd, int b_index) {
127 _GRAPH_CHECK_BOUNDS(b_index, 0, gd->basicblockcount);
128 return (gd->num_pred[b_index] > 1);
131 bool graph_has_multiple_successors( graphdata *gd, int b_index) {
132 _GRAPH_CHECK_BOUNDS(b_index, 0, gd->basicblockcount);
133 return (gd->num_succ[b_index] > 1);
136 void graph_add_edge( graphdata *gd, int from, int to ) {
141 /* prevent multiple similar edges from TABLESWITCH and */
143 b = graph_get_first_successor(gd, from, &i);
144 for( ; (b != -1) && ( b != to); b = graph_get_next(&i));
145 if (b != -1) /* edge from->to already existing */
148 /* We need two new graph_elements. One for successors and one for */
150 n = DMNEW(graph_element, 2);
153 n->next=gd->successor[from];
154 gd->successor[from]=n;
155 gd->num_succ[from]++;
157 n++; /* take next allocated graph_element */
159 n->next=gd->predecessor[to];
160 gd->predecessor[to]=n;
164 /* split the edge from BB from shown by iterator i with new_block */
165 void graph_split_edge(graphdata *gd, int from, graphiterator *i, int new_block) {
166 graphiterator i_pred;
170 /* i->value is the BB index of the "old" successor */
174 /* search for iterator showing predecessor edge from BB succ back to */
177 l = graph_get_first_predecessor(gd, succ, &i_pred);
178 for(; (l != -1) && (l != from); l = graph_get_next(&i_pred));
179 _GRAPH_ASSERT(l == from);
181 /* change CFG entries */
183 (*i)->value = new_block;
184 i_pred->value = new_block;
186 /* and insert the CFG successor and predecesser entries for new_block */
187 /* 2 entries needed */
189 n = DMNEW(graph_element, 2);
191 /* make the successor entry for new_block */
194 n->next = gd->successor[new_block];
195 gd->successor[new_block] = n;
196 gd->num_succ[new_block]++;
198 /* make the predecessor entry for new_block */
202 n->next = gd->predecessor[new_block];
203 gd->predecessor[new_block] = n;
204 gd->num_pred[new_block]++;
207 /***********************************************
208 Generate the Control Flow Graph
209 ( pred,succ,num_pred of lsradata structure)
210 ************************************************/
211 void graph_make_cfg(jitdata *jd,graphdata *gd) {
213 lookup_target_t *lookup;
214 branch_target_t *table;
227 /* Add edge from new Basic Block 0 (parameter initialization) */
228 graph_add_edge(gd, 0, 1);
230 for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
231 if (bptr->flags >= BBREACHED) {
232 if ((len = bptr->icount)) {
233 /* set iptr to last non NOP instruction */
234 iptr = bptr->iinstr + bptr->icount -1;
235 while ((len>0) && (iptr->opc == ICMD_NOP)) {
239 /* block contains instructions */
240 switch (iptr->opc) { /* check type of last instruction */
248 break; /* function returns -> end of graph */
277 case ICMD_IF_ACMPNE: /* branch -> add next block */
278 /* Add branch target */
279 graph_add_cfg(jd, gd, bptr, iptr->dst.block);
280 /* Add fall through path */
281 graph_add_cfg(jd, gd, bptr, bptr->next);
286 graph_add_cfg(jd, gd, bptr, iptr->dst.block);
287 break; /* visit branch (goto) target */
289 case ICMD_TABLESWITCH: /* switch statement */
290 table = iptr->dst.table;
291 l = iptr->sx.s23.s2.tablelow;
292 i = iptr->sx.s23.s3.tablehigh;
295 /* Add default target */
297 graph_add_cfg(jd, gd, bptr, table[0].block);
301 graph_add_cfg(jd, gd, bptr, table->block);
306 case ICMD_LOOKUPSWITCH: /* switch statement */
307 lookup = iptr->dst.lookup;
308 i = iptr->sx.s23.s2.lookupcount;
311 graph_add_cfg(jd, gd, bptr, lookup->target.block);
315 graph_add_cfg(jd, gd, bptr, iptr->sx.s23.s3.lookupdefault.block);
327 graph_add_cfg(jd, gd, bptr, bptr + 1 );
329 } /* switch (iptr->opc)*/
330 } /* if (bptr->icount) */
331 } /* if (bptr->flags >= BBREACHED) */
332 } /* for (bptr = ...; bptr != NULL; bptr = bptr->next) */
334 graph_add_exceptions(jd, gd);
335 transform_CFG(jd, gd);
337 #ifdef GRAPH_DEBUG_VERBOSE
343 /*****************************************************************
344 add Edges from guarded Areas to Exception handlers in the CFG
345 *****************************************************************/
346 void graph_add_exceptions(jitdata *jd, graphdata *gd) {
349 raw_exception_entry *ex;
354 /* add cfg edges from all bb of a try block to the start of the according */
355 /* exception handler to ensure the right order after depthfirst search */
357 ex=jd->exceptiontable;
359 #ifdef GRAPH_DEBUG_VERBOSE
361 printf("ExTable(%i): ", jd->exceptiontablelength);
364 for (; ex != NULL; ex = ex->down) {
366 #ifdef GRAPH_DEBUG_VERBOSE
368 printf("[%i-%i]->%i ",ex->start->nr, ex->end->nr,
372 _GRAPH_ASSERT(ex->handler->nr < jd->new_basicblockcount);
373 _GRAPH_ASSERT(ex->handler->flags >= BBREACHED);
374 _GRAPH_ASSERT(ex->start->nr <= ex->end->nr);
376 /* loop all valid Basic Blocks of the guarded area and add CFG edges */
377 /* to the appropriate handler */
378 for (bptr = ex->start; (bptr != NULL) && (bptr != ex->end); bptr = bptr->next)
379 if (bptr->flags >= BBREACHED)
380 graph_add_cfg(jd, gd, bptr, ex->handler);
382 _GRAPH_ASSERT((bptr != NULL)
383 && ((bptr->flags >=BBREACHED) || (bptr == ex->end)));
385 #ifdef GRAPH_DEBUG_VERBOSE
393 /******************************************************************
394 Add the CFG Edge into next und succ
395 ******************************************************************/
396 void graph_add_cfg( jitdata *jd, graphdata *gd, basicblock *from,
399 /* ignore Empty, Deleted,... Basic Blocks as target */
400 /* TODO: Setup BasicBlock array before to avoid this */
401 /* best together with using the basicblock list, so lsra works */
402 /* with opt_loops, too */
404 for (; (to != NULL) && (to->flags < BBREACHED); to = to->next);
406 _GRAPH_ASSERT(to != NULL);
409 /* add one to from and to, so the to be inserted Basic Block 0 is */
410 /* already regarded */
411 graph_add_edge( gd, from->nr + 1, to->nr + 1);
415 /*****************************************************************
416 Sort Basic Blocks using Depth First search in reverse post order
417 In: ls->basicblockcount, ls->basicblocks[], gd->
418 Out: ls->sorted, ls->sorted_rev
419 *****************************************************************/
421 void graph_DFS(lsradata *ls, graphdata *gd) {
429 ls->sorted = DMNEW(int, ls->basicblockcount);
430 ls->sorted_rev = DMNEW(int, ls->basicblockcount);
432 stack = DMNEW( int, ls->basicblockcount);
433 visited = (int *)DMNEW( bool, ls->basicblockcount);
434 for (i = 0; i < ls->basicblockcount; i++) {
437 ls->sorted_rev[i]=-1;
440 stack[0] = 0; /* start with Block 0 */
442 /* Start Block is handled right and can be put in sorted */
443 visited[0] = graph_get_num_predecessor(gd , 0);
446 while (not_finished) {
447 while (stack_top != 0) {
449 i = stack[stack_top];
452 s = graph_get_first_successor(gd, i, &iter);
453 for (; s != -1; s = graph_get_next(&iter)) {
455 if (visited[s] == graph_get_num_predecessor(gd, s)) {
456 /* push the node on the stack, only if all ancestors have */
458 stack[stack_top] = s;
463 not_finished = false;
464 for (i=1; i < ls->basicblockcount; i++) {
465 /* search for visited blocks, which have not reached the num_pre */
466 /* and put them on the stack -> happens with backedges */
467 num_pred = graph_get_num_predecessor(gd, i);
468 if ((visited[i] != 0) && (visited[i] < num_pred)) {
469 stack[stack_top] = i;
471 visited[i] = num_pred;
478 for(i = 0; i < ls->basicblockcount; i++)
479 if (ls->sorted[i] != -1)
480 ls->sorted_rev[ls->sorted[i]] = i;
484 void graph_init_basicblock(jitdata *jd, basicblock *bptr, int b_index) {
488 bptr->type = BBTYPE_STD;
489 bptr->flags = BBFINISHED;
491 bptr->outvars = NULL;
494 bptr->branchrefs = NULL;
497 bptr->method = jd->m;
500 /*********************************************************************+
501 After the "original" CFG has been created, it has to be adopted for
502 SSA. (inluding insertion of new Basic Blocks)
504 TODO: Do not insert blocks right now - just adopt the call graph!
505 After the phi moves are determined create only the needed Blocks
506 **********************************************************************/
507 void transform_CFG(jitdata *jd, graphdata *gd) {
508 int i, j, k, n, num_new_blocks;
510 basicblock *tmp, *bptr;
511 s4 *in, *out, *new_in_stack, *new_out_stack;
514 struct graph_element **successor;
516 struct graph_element **predecessor;
527 /* with SSA a new Basic Block 0 is inserted for parameter initialisation */
528 /* & look for nodes with multiple successors leading to nodes with */
529 /* multiple predecessor -> if found insert a new block between to split */
530 /* this edge. As first step count how many blocks have to be inserted. */
533 for(i = 0; i< jd->basicblockcount + 1; i++) {
534 if (graph_has_multiple_successors(gd, i)) {
535 k = graph_get_first_successor(gd, i, &iter);
536 for(; k != -1; k = graph_get_next(&iter)) {
537 /* check for successor blocks with more than one */
538 /* predecessor. For each found incremet num_new_blocks */
539 if (graph_has_multiple_predecessors(gd, k))
545 /* increase now basicblockcount accordingly. */
546 ls->basicblockcount = jd->basicblockcount + num_new_blocks;
548 ls->basicblocks = DMNEW(basicblock *, ls->basicblockcount);
549 for(i = 0; i< ls->basicblockcount; i++)
550 ls->basicblocks[i] = NULL;
552 /* copy Basic Block References to ls->basicblocks */
554 for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
555 /* if (bptr->flags >= BBREACHED) { */
556 _GRAPH_ASSERT(bptr->nr < jd->basicblockcount);
557 ls->basicblocks[bptr->nr + 1] = bptr;
558 bptr->nr = bptr->nr+1;
562 /* Create new Basic Blocks:
563 0, [jd->new_basicblockcount..ls->basicblockcount[ */
564 /* num_new_blocks have to be inserted*/
566 tmp = DMNEW( basicblock, num_new_blocks);
567 ls->basicblocks[0] = tmp;
568 graph_init_basicblock( jd, tmp, 0);
570 ls->basicblocks[0]->next = ls->basicblocks[1];
572 if (ls->basicblockcount > jd->basicblockcount + 1) {
573 /* new Blocks have to be inserted */
574 num_succ = DMNEW(int, ls->basicblockcount);
575 successor = DMNEW(graph_element *, ls->basicblockcount);
577 num_pred = DMNEW(int, ls->basicblockcount);
578 predecessor = DMNEW(graph_element *, ls->basicblockcount);
580 /* regard the + 1 for the already inserted new BB 0 */
581 /* So recreate ls->var_def */
582 var_def = DMNEW(int *, ls->basicblockcount);
583 for(i = 0; i < jd->basicblockcount + 1; i++) {
584 var_def[i] = ls->var_def[i];
585 num_succ[i] = gd->num_succ[i];
586 num_pred[i] = gd->num_pred[i];
587 successor[i] = gd->successor[i];
588 predecessor[i] = gd->predecessor[i];
590 for(i = jd->basicblockcount + 1; i < ls->basicblockcount; i++) {
591 var_def[i] = bv_new(jd->varcount);
592 graph_init_basicblock( jd, tmp, i);
593 ls->basicblocks[i] = tmp;
599 predecessor[i] = NULL;
601 ls->var_def = var_def;
602 gd->num_succ = num_succ;
603 gd->num_pred = num_pred;
604 gd->successor = successor;
605 gd->predecessor = predecessor;
606 #ifdef GRAPH_DEBUG_CHECK
607 /* Remember basicblockcount, so Array Bound checks can be made */
608 gd->basicblockcount = ls->basicblockcount;
612 /* Now Split the edges */
613 num_new_blocks = jd->basicblockcount + 1; /* first free new block index */
614 for(i = 0; i < jd->basicblockcount + 1; i++) {
615 if (graph_has_multiple_successors(gd, i)) {/* more than one successor */
616 j = graph_get_first_successor( gd, i, &iter);
617 for(; j != -1; j = graph_get_next(&iter)) {
618 if (graph_has_multiple_predecessors(gd, j)) {
619 /* and more than one predecessor -> split edge */
620 _GRAPH_ASSERT(num_new_blocks < ls->basicblockcount);
622 /* insert new Block num_new_blocks */
624 /* splite the edge from BB i to j with the new BB */
625 /* num_new_blocks ( i->j --> i->nnb->j)*/
626 /* iter_succ shows the edge from i to j */
627 graph_split_edge(gd, i, &iter, num_new_blocks);
629 ls->basicblocks[num_new_blocks]->indepth =
630 ls->basicblocks[i]->outdepth;
631 out = ls->basicblocks[i]->outvars;
632 ls->basicblocks[num_new_blocks]->invars = in = NULL;
634 if (ls->basicblocks[num_new_blocks]->indepth > 0)
635 new_in_stack = DMNEW( s4,
636 ls->basicblocks[num_new_blocks]->indepth);
637 new_out_stack = DMNEW( s4,
638 ls->basicblocks[num_new_blocks]->indepth);
640 for(n=0; n<ls->basicblocks[num_new_blocks]->indepth; n++) {
641 new_in_stack[n] = out[n];
642 new_out_stack[n] = out[n];
644 ls->basicblocks[num_new_blocks]->invars = new_in_stack;
646 /* Create Outstack */
647 ls->basicblocks[num_new_blocks]->outvars =
649 ls->basicblocks[num_new_blocks]->outdepth =
650 ls->basicblocks[num_new_blocks]->indepth;
652 _GRAPH_ASSERT(ls->basicblocks[num_new_blocks]->outdepth ==
653 ls->basicblocks[j]->indepth );
656 /* !!!! There can't be inoutvar definitions in one of these */
657 /* newly inserted basicblocks !!!! */
660 /* decrease nr temporarly, because ssa_set_interface*/
661 /* adds 1 since it is called from stack.c, where there is */
662 /* no new BB 0 inserted like now */
664 ls->basicblocks[num_new_blocks]->nr--;
665 ssa_set_interface(jd, ls->basicblocks[num_new_blocks]);
666 ls->basicblocks[num_new_blocks]->nr++;
675 void transform_BB(jitdata *jd, graphdata *gd) {
678 basicblock *last_block;
687 /* the "real" last Block is always an empty block */
688 /* so take the one before, to insert new blocks after it */
689 last_block = &(jd->basicblocks[jd->basicblockcount - 1]);
690 _GRAPH_ASSERT(last_block->next->next == NULL);
691 _GRAPH_ASSERT(last_block->next->flags <= BBREACHED);
692 last_block->next->nr = ls->basicblockcount;
694 /* look through new blocks */
695 for(n = jd->basicblockcount + 1; n < ls->basicblockcount ; n++) {
696 /* if a phi move happens at this block, we need this block */
697 /* if not, remove him from the CFG */
698 if (ls->num_phi_moves[n] > 0) {
699 /* i can only have one predecessor and one successor! */
700 _GRAPH_ASSERT( graph_has_multiple_predecessors(gd, n) == false);
701 _GRAPH_ASSERT( graph_has_multiple_successors(gd, n) == false);
703 succ = graph_get_first_successor(gd, n, &iter);
704 pred = graph_get_first_predecessor(gd, n, &iter);
706 /* set iptr to last instruction */
707 len = ls->basicblocks[pred]->icount;
708 iptr = ls->basicblocks[pred]->iinstr + len - 1;
709 while ((len>0) && (iptr->opc == ICMD_NOP)) {
715 /* with JSR there can not be multiple successors */
716 _GRAPH_ASSERT(iptr->opc != ICMD_JSR);
717 /* If the return Statment has more successors and */
718 /* one of these has more predecessor, we are in */
719 /* troubles - one would have to insert a new Block */
720 /* after the one which executes the ICMD_JSR */
721 /* !!TODO!! if subroutines will not be inlined */
722 _GRAPH_ASSERT(iptr->opc != ICMD_RET);
724 /* link new block into basicblocks list */
725 /* if edge to split is the "fallthrough" path of the */
726 /* conditional, then link the new block inbetween */
727 /* and generate no ICMD */
728 /* else if edge to split is the branch, generate a */
729 /* ICMD_GOTO and add new BB at the end of the BB List*/
730 if ((ls->basicblocks[pred]->next == ls->basicblocks[succ])
731 && (iptr->opc != ICMD_LOOKUPSWITCH)
732 && (iptr->opc != ICMD_TABLESWITCH)
733 && (iptr->opc != ICMD_GOTO)) {
734 /* GOTO, *SWITCH have no fallthrough path */
736 /* link into fallthrough path */
739 ls->basicblocks[n]->next =
740 ls->basicblocks[pred]->next;
741 ls->basicblocks[pred]->next =
743 /* generate no instructions */
744 ls->basicblocks[n]->icount = 1;
745 ls->basicblocks[n]->iinstr = NEW(instruction);
746 ls->basicblocks[n]->iinstr[0].opc = ICMD_NOP;
748 /* Block n is in the Branch path */
749 /* link Block at the end */
750 ls->basicblocks[n]->next =last_block->next;
751 last_block->next = ls->basicblocks[n];
752 last_block = ls->basicblocks[n];
754 /* change the Branch Target to BB i */
759 case ICMD_LOOKUPSWITCH:
762 lookup_target_t *lookup;
764 lookup = iptr->dst.lookup;
766 i = iptr->sx.s23.s2.lookupcount;
769 if (lookup->target.block == ls->basicblocks[succ])
770 /* target found -> change */
771 lookup->target.block = ls->basicblocks[n];
775 if (iptr->sx.s23.s3.lookupdefault.block == ls->basicblocks[succ])
776 /* target found -> change */
777 iptr->sx.s23.s3.lookupdefault.block = ls->basicblocks[n];
780 case ICMD_TABLESWITCH:
783 branch_target_t *table;
785 table = iptr->dst.table;
787 l = iptr->sx.s23.s2.tablelow;
788 i = iptr->sx.s23.s3.tablehigh;
792 if (table[0].block == ls->basicblocks[succ]) /* default target */
793 /* target found -> change*/
794 table[0].block = ls->basicblocks[n];
799 if (table->block == ls->basicblocks[succ])
800 /* target found -> change */
801 table->block = ls->basicblocks[n];
835 _GRAPH_ASSERT(iptr->dst.block == ls->basicblocks[succ]);
836 iptr->dst.block = ls->basicblocks[n];
839 /* Exception Edge to split */
840 /* not handled by now -> fallback to regalloc */
844 /* Generate the ICMD_GOTO */
845 ls->basicblocks[n]->icount = 1;
846 ls->basicblocks[n]->iinstr =
848 ls->basicblocks[n]->iinstr->opc =
850 ls->basicblocks[n]->iinstr->dst.block =
851 ls->basicblocks[succ];
857 #ifdef GRAPH_DEBUG_VERBOSE
858 void graph_print(lsradata *ls, graphdata *gd) {
861 printf("graph_print: basicblockcount %3i\n", ls->basicblockcount);
864 for(i = 0; i < ls->basicblockcount; i++) {
866 j = graph_get_first_successor(gd, i, &iter);
867 for(; j != -1; j = graph_get_next(&iter)) {
873 for(i = 0; i < ls->basicblockcount; i++) {
875 j = graph_get_first_predecessor(gd, i, &iter);
876 for(; j != -1; j = graph_get_next(&iter)) {
887 * These are local overrides for various environment variables in Emacs.
888 * Please do not remove this and leave it at the end of the file, where
889 * Emacs will automagically detect them.
890 * ---------------------------------------------------------------------
893 * indent-tabs-mode: t