1 /* src/vm/jit/cfg.c - build a control-flow graph
3 Copyright (C) 2006, 2007 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 J. Wenninger, 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., 51 Franklin Street, Fifth Floor, Boston, MA
33 #include "mm/memory.h"
35 #include "vm/global.h"
37 #include "vm/jit/jit.h"
38 #include "vm/jit/stack.h"
41 /* cfg_allocate_predecessors ***************************************************
43 Allocates the predecessor array, if there is none, and resets the
46 *******************************************************************************/
48 static void cfg_allocate_predecessors(basicblock *bptr)
50 if (bptr->predecessors == NULL) {
51 bptr->predecessors = DMNEW(basicblock*, bptr->predecessorcount);
53 bptr->predecessorcount = 0;
58 /* cfg_allocate_successors *****************************************************
60 Allocates the succecessor array, if there is none, and resets the
63 *******************************************************************************/
65 static void cfg_allocate_successors(basicblock *bptr)
67 if (bptr->successors == NULL) {
68 bptr->successors = DMNEW(basicblock*, bptr->successorcount);
70 bptr->successorcount = 0;
75 /* cfg_insert_predecessor ******************************************************
77 Inserts a predecessor into the array, but checks for duplicate
78 entries. This is used for TABLESWITCH and LOOKUPSWITCH.
80 *******************************************************************************/
82 static void cfg_insert_predecessors(basicblock *bptr, basicblock *pbptr)
87 tbptr = bptr->predecessors;
89 /* check if the predecessors is already stored in the array */
91 for (i = 0; i < bptr->predecessorcount; i++, tbptr++)
95 /* not found, insert it */
97 bptr->predecessors[bptr->predecessorcount] = pbptr;
98 bptr->predecessorcount++;
101 static void cfg_insert_successors(basicblock *bptr, basicblock *pbptr)
106 tbptr = bptr->successors;
108 /* check if the successor is already stored in the array */
110 for (i = 0; i < bptr->successorcount; i++, tbptr++)
114 /* not found, insert it */
116 bptr->successors[bptr->successorcount] = pbptr;
117 bptr->successorcount++;
121 /* cfg_build *******************************************************************
123 Build a control-flow graph in finding all predecessors and
124 successors for the basic blocks.
126 *******************************************************************************/
128 bool cfg_build(jitdata *jd)
134 branch_target_t *table;
135 lookup_target_t *lookup;
137 bool has_fallthrough;
139 /* process all basic blocks to find the predecessor/successor counts */
141 bptr = jd->basicblocks;
143 for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
145 if (bptr->type == BBTYPE_EXH) {
146 /* predecessorcount for exception handlers is initialized to -1,
147 so we need to fix it to 0. */
148 bptr->predecessorcount += 1;
151 if ((bptr->icount == 0) || (bptr->flags == BBUNDEF))
154 iptr = bptr->iinstr + bptr->icount - 1;
156 /* skip NOPs at the end of the block */
158 while (iptr->opc == ICMD_NOP) {
159 if (iptr == bptr->iinstr)
164 if (iptr->opc == ICMD_GOTO) {
167 This is needed for the following special case caused by
168 stack_reach_next_block:
169 I.e. there might be instructions causing control flow before
173 129: 192: IFEQ Ti102 0 (0x00000000) --> L052
178 bptr->successorcount++;
180 tbptr = iptr->dst.block;
181 tbptr->predecessorcount++;
183 if (iptr == bptr->iinstr) {
189 while (iptr->opc == ICMD_NOP) {
190 if (iptr == bptr->iinstr) {
196 has_fallthrough = false;
198 has_fallthrough = true;
201 switch (icmd_table[iptr->opc].controlflow) {
208 bptr->successorcount += 2;
210 tbptr = iptr->dst.block;
211 tbptr->predecessorcount++;
213 if (has_fallthrough) {
215 ntbptr->predecessorcount++;
220 bptr->successorcount++;
222 tbptr = iptr->sx.s23.s3.jsrtarget.block;
223 tbptr->predecessorcount++;
228 bptr->successorcount++;
230 tbptr = iptr->dst.block;
231 tbptr->predecessorcount++;
235 table = iptr->dst.table;
237 bptr->successorcount++;
239 tbptr = table->block;
240 tbptr->predecessorcount++;
243 i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
246 bptr->successorcount++;
248 tbptr = table->block;
249 tbptr->predecessorcount++;
255 lookup = iptr->dst.lookup;
257 bptr->successorcount++;
259 tbptr = iptr->sx.s23.s3.lookupdefault.block;
260 tbptr->predecessorcount++;
262 i = iptr->sx.s23.s2.lookupcount;
265 bptr->successorcount++;
267 tbptr = lookup->target.block;
268 tbptr->predecessorcount++;
274 if (has_fallthrough) {
275 bptr->successorcount++;
279 /* An exception handler has no predecessors. */
281 if (tbptr->type != BBTYPE_EXH)
282 tbptr->predecessorcount++;
288 /* Second iteration to allocate the arrays and insert the basic
291 bptr = jd->basicblocks;
293 for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
294 if ((bptr->icount == 0) || (bptr->flags == BBUNDEF))
297 iptr = bptr->iinstr + bptr->icount - 1;
299 /* skip NOPs at the end of the block */
301 while (iptr->opc == ICMD_NOP) {
302 if (iptr == bptr->iinstr)
307 if (iptr->opc == ICMD_GOTO) {
308 tbptr = iptr->dst.block;
310 cfg_allocate_successors(bptr);
312 cfg_insert_successors(bptr, tbptr);
314 cfg_allocate_predecessors(tbptr);
316 cfg_insert_predecessors(tbptr, bptr);
318 if (iptr == bptr->iinstr) {
324 while (iptr->opc == ICMD_NOP) {
325 if (iptr == bptr->iinstr) {
331 has_fallthrough = false;
334 has_fallthrough = true;
337 switch (icmd_table[iptr->opc].controlflow) {
344 tbptr = iptr->dst.block;
347 cfg_allocate_successors(bptr);
349 cfg_insert_successors(bptr, tbptr);
350 if (has_fallthrough) {
351 cfg_insert_successors(bptr, ntbptr);
354 cfg_allocate_predecessors(tbptr);
355 if (has_fallthrough) {
356 cfg_allocate_predecessors(ntbptr);
359 cfg_insert_predecessors(tbptr, bptr);
360 if (has_fallthrough) {
361 cfg_insert_predecessors(ntbptr, bptr);
366 tbptr = iptr->sx.s23.s3.jsrtarget.block;
372 tbptr = iptr->dst.block;
374 cfg_allocate_successors(bptr);
376 cfg_insert_successors(bptr, tbptr);
378 cfg_allocate_predecessors(tbptr);
380 cfg_insert_predecessors(tbptr, bptr);
384 table = iptr->dst.table;
386 tbptr = table->block;
389 cfg_allocate_successors(bptr);
391 cfg_insert_successors(bptr, tbptr);
393 cfg_allocate_predecessors(tbptr);
395 cfg_insert_predecessors(tbptr, bptr);
397 i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
400 tbptr = table->block;
403 cfg_insert_successors(bptr, tbptr);
405 cfg_allocate_predecessors(tbptr);
406 cfg_insert_predecessors(tbptr, bptr);
411 lookup = iptr->dst.lookup;
413 tbptr = iptr->sx.s23.s3.lookupdefault.block;
415 cfg_allocate_successors(bptr);
417 cfg_insert_successors(bptr, tbptr);
419 cfg_allocate_predecessors(tbptr);
421 cfg_insert_predecessors(tbptr, bptr);
423 i = iptr->sx.s23.s2.lookupcount;
426 tbptr = lookup->target.block;
429 cfg_insert_successors(bptr, tbptr);
431 cfg_allocate_predecessors(tbptr);
432 cfg_insert_predecessors(tbptr, bptr);
437 if (has_fallthrough) {
440 cfg_allocate_successors(bptr);
442 bptr->successors[0] = tbptr;
443 bptr->successorcount++;
445 /* An exception handler has no predecessors. */
447 if (tbptr->type != BBTYPE_EXH) {
448 cfg_allocate_predecessors(tbptr);
450 tbptr->predecessors[tbptr->predecessorcount] = bptr;
451 tbptr->predecessorcount++;
458 /* everything's ok */
463 /* cfg_add_root ****************************************************************
465 Adds an empty root basicblock.
466 The numbers of all other basicblocks are set off by one.
467 Needed for some analyses that require the root basicblock to have no
468 predecessors and to perform special initializations.
470 *******************************************************************************/
472 void cfg_add_root(jitdata *jd) {
473 basicblock *root, *zero, *it;
475 zero = jd->basicblocks;
477 root = DNEW(basicblock);
478 MZERO(root, basicblock, 1);
480 root->successorcount = 1;
481 root->successors = DMNEW(basicblock *, 1);
482 root->successors[0] = zero;
485 root->type = BBTYPE_STD;
486 root->method = jd->m;
488 if (zero->predecessorcount == 0) {
489 zero->predecessors = DNEW(basicblock *);
491 zero->predecessors = DMREALLOC(zero->predecessors, basicblock *, zero->predecessorcount, zero->predecessorcount + 1);
493 zero->predecessors[zero->predecessorcount] = root;
494 zero->predecessorcount += 1;
496 jd->basicblocks = root;
497 jd->basicblockcount += 1;
499 for (it = zero; it; it = it->next) {
504 #if defined(ENABLE_SSA)
506 static void cfg_eliminate_edges_to_unreachable(jitdata *jd);
508 /* cfg_add_exceptional_edges ***************************************************
510 Edges from basicblocks to their exception handlers and from exception
511 handlers to the blocks they handle exceptions for are added. Further
512 the number of potentially throwing instructions in the basicblocks are
515 We don't consider nor do we determine the types of exceptions thrown. Edges
516 are added from every block to every potential handler.
518 *******************************************************************************/
520 void cfg_add_exceptional_edges(jitdata *jd) {
524 bool unreachable_exh = false;
526 /* Count the number of exceptional exits for every block.
527 * Every PEI is an exceptional out.
530 FOR_EACH_BASICBLOCK(jd, bptr) {
532 /* Prepare for reachability calculation. */
535 if (bptr->flags == BBUNDEF) {
539 FOR_EACH_INSTRUCTION(bptr, iptr) {
540 if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
546 /* Count the number of exception handlers for every block. */
548 for (ee = jd->exceptiontable; ee; ee = ee->down) {
549 for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
550 /* Linking a block with a handler, even if there are no exceptional exits
551 breaks stuff in other passes. */
552 if (bptr->exouts > 0) {
553 bptr->exhandlercount += 1;
554 ee->handler->expredecessorcount += 1;
559 /* Allocate and fill exception handler arrays. */
561 for (ee = jd->exceptiontable; ee; ee = ee->down) {
563 if (ee->handler->expredecessorcount == 0) {
564 /* An exception handler that is unreachable.
565 This is inconsistent with the semantics of the CFG,
566 we need to recalculate reachability. */
567 unreachable_exh = true;
570 for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
571 if (bptr->exouts > 0) {
573 if (bptr->exhandlers == NULL) {
574 bptr->exhandlers = DMNEW(basicblock *, bptr->exhandlercount);
575 /* Move pointer past the end of the array,
576 * It will be filled in the reverse order.
578 bptr->exhandlers += bptr->exhandlercount;
581 bptr->exhandlers -= 1;
582 *(bptr->exhandlers) = ee->handler;
584 if (ee->handler->expredecessors == NULL) {
585 ee->handler->expredecessors = DMNEW(basicblock *, ee->handler->expredecessorcount);
586 ee->handler->expredecessors += ee->handler->expredecessorcount;
589 ee->handler->expredecessors -= 1;
590 *(ee->handler->expredecessors) = bptr;
595 if (unreachable_exh) {
597 /* This is rare in ``normal'' compiler generated code.
599 The dead block [EXH] is a predecessor of [BB1],
600 but the edge [EXH] -> [BB1] will never be traversed.
602 [BB1] --[next]--> [BB2, no peis] ==[exhandler]==> [EXH] --[next]--+
604 +---------------------------------------------------------------+
608 fprintf(stderr, "Found unreachable exh, adjusting %s %s",
609 jd->m->klazz->name->text, jd->m->name->text);
610 fprintf(stderr, "<before>\n");
612 fprintf(stderr, "</before>\n");
615 cfg_eliminate_edges_to_unreachable(jd);
618 fprintf(stderr, "<after>\n");
620 fprintf(stderr, "</after>\n");
625 static void cfg_calculate_reachability(basicblock *bptr) {
628 /* Block not marked. */
629 assert(bptr->vp == NULL);
631 bptr->vp = bptr; /* Mark block */
633 FOR_EACH_SUCCESSOR(bptr, itsucc) {
634 if ((*itsucc)->vp == NULL) {
635 cfg_calculate_reachability(*itsucc);
639 if (bptr->exouts > 0) {
640 FOR_EACH_EXHANDLER(bptr, itsucc) {
641 if ((*itsucc)->vp == NULL) {
642 cfg_calculate_reachability(*itsucc);
648 static void cfg_remove_predecessors(basicblock *bptr, basicblock *pbptr) {
651 for (i = 0; i < bptr->predecessorcount; ++i) {
653 if (bptr->predecessors[i] == pbptr) {
654 if (i != (bptr->predecessorcount - 1)) {
655 /* If not last element, replace element with last element. */
656 bptr->predecessors[i] = bptr->predecessors[bptr->predecessorcount - 1];
659 /* Decrease element count. */
660 bptr->predecessorcount -= 1;
667 static void cfg_eliminate_edges_to_unreachable(jitdata *jd) {
671 cfg_calculate_reachability(jd->basicblocks);
673 FOR_EACH_BASICBLOCK(jd, it) {
674 if (it->vp == NULL) {
676 /* Mark as unreachable. */
680 /* As this block got unreachable, it is no more a predecessor
681 of its successors. */
683 FOR_EACH_SUCCESSOR(it, itsucc) {
684 cfg_remove_predecessors(*itsucc, it);
687 /* Eliminiate all CFG edges of this block. */
689 it->predecessorcount = 0;
690 it->successorcount = 0;
691 it->expredecessorcount = 0;
700 * These are local overrides for various environment variables in Emacs.
701 * Please do not remove this and leave it at the end of the file, where
702 * Emacs will automagically detect them.
703 * ---------------------------------------------------------------------
706 * indent-tabs-mode: t
710 * vim:noexpandtab:sw=4:ts=4: