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 /* cfg_add_exceptional_edges ***************************************************
507 Edges from basicblocks to their exception handlers and from exception
508 handlers to the blocks they handle exceptions for are added. Further
509 the number of potentially throwing instructions in the basicblocks are
512 We don't consider nor do we determine the types of exceptions thrown. Edges
513 are added from every block to every potential handler.
515 *******************************************************************************/
517 void cfg_add_exceptional_edges(jitdata *jd) {
522 /* Count the number of exceptional exits for every block.
523 * Every PEI is an exceptional out.
526 FOR_EACH_BASICBLOCK(jd, bptr) {
528 if (bptr->flags == BBUNDEF) {
532 FOR_EACH_INSTRUCTION(bptr, iptr) {
533 if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
539 /* Count the number of exception handlers for every block. */
541 for (ee = jd->exceptiontable; ee; ee = ee->down) {
542 for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
543 /* Linking a block with a handler, even if there are no exceptional exits
544 breaks stuff in other passes. */
545 if (bptr->exouts > 0) {
546 bptr->exhandlercount += 1;
547 ee->handler->expredecessorcount += 1;
552 /* Allocate and fill exception handler arrays. */
554 for (ee = jd->exceptiontable; ee; ee = ee->down) {
555 for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
556 if (bptr->exouts > 0) {
558 if (bptr->exhandlers == NULL) {
559 bptr->exhandlers = DMNEW(basicblock *, bptr->exhandlercount);
560 /* Move pointer past the end of the array,
561 * It will be filled in the reverse order.
563 bptr->exhandlers += bptr->exhandlercount;
566 bptr->exhandlers -= 1;
567 *(bptr->exhandlers) = ee->handler;
569 if (ee->handler->expredecessors == NULL) {
570 ee->handler->expredecessors = DMNEW(basicblock *, ee->handler->expredecessorcount);
571 ee->handler->expredecessors += ee->handler->expredecessorcount;
574 ee->handler->expredecessors -= 1;
575 *(ee->handler->expredecessors) = bptr;
584 * These are local overrides for various environment variables in Emacs.
585 * Please do not remove this and leave it at the end of the file, where
586 * Emacs will automagically detect them.
587 * ---------------------------------------------------------------------
590 * indent-tabs-mode: t
594 * vim:noexpandtab:sw=4:ts=4: