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;
487 if (zero->predecessorcount == 0) {
488 zero->predecessors = DNEW(basicblock *);
490 zero->predecessors = DMREALLOC(zero->predecessors, basicblock *, zero->predecessorcount, zero->predecessorcount + 1);
492 zero->predecessors[zero->predecessorcount] = root;
493 zero->predecessorcount += 1;
495 jd->basicblocks = root;
496 jd->basicblockcount += 1;
498 for (it = zero; it; it = it->next) {
503 #if defined(ENABLE_SSA)
505 static void cfg_eliminate_edges_to_unreachable(jitdata *jd);
507 /* cfg_add_exceptional_edges ***************************************************
509 Edges from basicblocks to their exception handlers and from exception
510 handlers to the blocks they handle exceptions for are added. Further
511 the number of potentially throwing instructions in the basicblocks are
514 We don't consider nor do we determine the types of exceptions thrown. Edges
515 are added from every block to every potential handler.
517 *******************************************************************************/
519 void cfg_add_exceptional_edges(jitdata *jd) {
523 bool unreachable_exh = false;
525 /* Count the number of exceptional exits for every block.
526 * Every PEI is an exceptional out.
529 FOR_EACH_BASICBLOCK(jd, bptr) {
531 /* Prepare for reachability calculation. */
534 if (bptr->flags == BBUNDEF) {
538 FOR_EACH_INSTRUCTION(bptr, iptr) {
539 if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
545 /* Count the number of exception handlers for every block. */
547 for (ee = jd->exceptiontable; ee; ee = ee->down) {
548 for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
549 /* Linking a block with a handler, even if there are no exceptional exits
550 breaks stuff in other passes. */
551 if (bptr->exouts > 0) {
552 bptr->exhandlercount += 1;
553 ee->handler->expredecessorcount += 1;
558 /* Allocate and fill exception handler arrays. */
560 for (ee = jd->exceptiontable; ee; ee = ee->down) {
562 if (ee->handler->expredecessorcount == 0) {
563 /* An exception handler that is unreachable.
564 This is inconsistent with the semantics of the CFG,
565 we need to recalculate reachability. */
566 unreachable_exh = true;
569 for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
570 if (bptr->exouts > 0) {
572 if (bptr->exhandlers == NULL) {
573 bptr->exhandlers = DMNEW(basicblock *, bptr->exhandlercount);
574 /* Move pointer past the end of the array,
575 * It will be filled in the reverse order.
577 bptr->exhandlers += bptr->exhandlercount;
580 bptr->exhandlers -= 1;
581 *(bptr->exhandlers) = ee->handler;
583 if (ee->handler->expredecessors == NULL) {
584 ee->handler->expredecessors = DMNEW(basicblock *, ee->handler->expredecessorcount);
585 ee->handler->expredecessors += ee->handler->expredecessorcount;
588 ee->handler->expredecessors -= 1;
589 *(ee->handler->expredecessors) = bptr;
594 if (unreachable_exh) {
596 /* This is rare in ``normal'' compiler generated code.
598 The dead block [EXH] is a predecessor of [BB1],
599 but the edge [EXH] -> [BB1] will never be traversed.
601 [BB1] --[next]--> [BB2, no peis] ==[exhandler]==> [EXH] --[next]--+
603 +---------------------------------------------------------------+
606 fprintf(stderr, "Found unreachable exh, adjusting %s %s",
607 jd->m->class->name->text, jd->m->name->text);
608 fprintf(stderr, "<before>\n");
610 fprintf(stderr, "</before>\n");
611 cfg_eliminate_edges_to_unreachable(jd);
612 fprintf(stderr, "<after>\n");
614 fprintf(stderr, "</after>\n");
618 static void cfg_calculate_reachability(basicblock *bptr) {
621 /* Block not marked. */
622 assert(bptr->vp == NULL);
624 bptr->vp = bptr; /* Mark block */
626 FOR_EACH_SUCCESSOR(bptr, itsucc) {
627 if ((*itsucc)->vp == NULL) {
628 cfg_calculate_reachability(*itsucc);
632 if (bptr->exouts > 0) {
633 FOR_EACH_EXHANDLER(bptr, itsucc) {
634 if ((*itsucc)->vp == NULL) {
635 cfg_calculate_reachability(*itsucc);
641 static void cfg_remove_predecessors(basicblock *bptr, basicblock *pbptr) {
644 for (i = 0; i < bptr->predecessorcount; ++i) {
646 if (bptr->predecessors[i] == pbptr) {
647 if (i != (bptr->predecessorcount - 1)) {
648 /* If not last element, replace element with last element. */
649 bptr->predecessors[i] = bptr->predecessors[bptr->predecessorcount - 1];
652 /* Decrease element count. */
653 bptr->predecessorcount -= 1;
660 static void cfg_eliminate_edges_to_unreachable(jitdata *jd) {
664 cfg_calculate_reachability(jd->basicblocks);
666 FOR_EACH_BASICBLOCK(jd, it) {
667 if (it->vp == NULL) {
669 /* Mark as unreachable. */
673 /* As this block got unreachable, it is no more a predecessor
674 of its successors. */
676 FOR_EACH_SUCCESSOR(it, itsucc) {
677 cfg_remove_predecessors(*itsucc, it);
680 /* Eliminiate all CFG edges of this block. */
682 it->predecessorcount = 0;
683 it->successorcount = 0;
684 it->expredecessorcount = 0;
693 * These are local overrides for various environment variables in Emacs.
694 * Please do not remove this and leave it at the end of the file, where
695 * Emacs will automagically detect them.
696 * ---------------------------------------------------------------------
699 * indent-tabs-mode: t
703 * vim:noexpandtab:sw=4:ts=4: