Line data Source code
1 : /* src/vm/jit/cfg.c - build a control-flow graph
2 :
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
7 :
8 : This file is part of CACAO.
9 :
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.
14 :
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.
19 :
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
23 : 02110-1301, USA.
24 :
25 : */
26 :
27 : #include "vm/jit/cfg.hpp"
28 : #include <assert.h> // for assert
29 : #include "config.h"
30 : #include "mm/dumpmemory.hpp" // for DMNEW
31 : #include "vm/jit/ir/icmd.hpp" // for ::ICMD_NOP, etc
32 : #include "vm/jit/ir/instruction.hpp" // for instruction, etc
33 : #include "vm/jit/jit.hpp" // for basicblock, jitdata, etc
34 : #include "vm/jit/stack.hpp"
35 :
36 :
37 : /* cfg_allocate_predecessors ***************************************************
38 :
39 : Allocates the predecessor array, if there is none, and resets the
40 : predecessor count.
41 :
42 : *******************************************************************************/
43 :
44 305136 : static void cfg_allocate_predecessors(basicblock *bptr)
45 : {
46 305136 : if (bptr->predecessors == NULL) {
47 222928 : bptr->predecessors = DMNEW(basicblock*, bptr->predecessorcount);
48 :
49 222928 : bptr->predecessorcount = 0;
50 : }
51 305136 : }
52 :
53 :
54 : /* cfg_allocate_successors *****************************************************
55 :
56 : Allocates the succecessor array, if there is none, and resets the
57 : predecessor count.
58 :
59 : *******************************************************************************/
60 :
61 197591 : static void cfg_allocate_successors(basicblock *bptr)
62 : {
63 197591 : if (bptr->successors == NULL) {
64 197590 : bptr->successors = DMNEW(basicblock*, bptr->successorcount);
65 :
66 197590 : bptr->successorcount = 0;
67 : }
68 197591 : }
69 :
70 :
71 : /* cfg_insert_predecessor ******************************************************
72 :
73 : Inserts a predecessor into the array, but checks for duplicate
74 : entries. This is used for TABLESWITCH and LOOKUPSWITCH.
75 :
76 : *******************************************************************************/
77 :
78 248565 : static void cfg_insert_predecessors(basicblock *bptr, basicblock *pbptr)
79 : {
80 : basicblock **tbptr;
81 : int i;
82 :
83 248565 : tbptr = bptr->predecessors;
84 :
85 : /* check if the predecessors is already stored in the array */
86 :
87 320030 : for (i = 0; i < bptr->predecessorcount; i++, tbptr++)
88 71924 : if (*tbptr == pbptr)
89 459 : return;
90 :
91 : /* not found, insert it */
92 :
93 248106 : bptr->predecessors[bptr->predecessorcount] = pbptr;
94 248106 : bptr->predecessorcount++;
95 : }
96 :
97 248565 : static void cfg_insert_successors(basicblock *bptr, basicblock *pbptr)
98 : {
99 : basicblock **tbptr;
100 : int i;
101 :
102 248565 : tbptr = bptr->successors;
103 :
104 : /* check if the successor is already stored in the array */
105 :
106 394762 : for (i = 0; i < bptr->successorcount; i++, tbptr++)
107 146656 : if (*tbptr == pbptr)
108 459 : return;
109 :
110 : /* not found, insert it */
111 :
112 248106 : bptr->successors[bptr->successorcount] = pbptr;
113 248106 : bptr->successorcount++;
114 : }
115 :
116 :
117 : /* cfg_build *******************************************************************
118 :
119 : Build a control-flow graph in finding all predecessors and
120 : successors for the basic blocks.
121 :
122 : *******************************************************************************/
123 :
124 86399 : bool cfg_build(jitdata *jd)
125 : {
126 : basicblock *bptr;
127 : basicblock *tbptr;
128 : basicblock *ntbptr;
129 : instruction *iptr;
130 : branch_target_t *table;
131 : lookup_target_t *lookup;
132 : int i;
133 : bool has_fallthrough;
134 :
135 : /* process all basic blocks to find the predecessor/successor counts */
136 :
137 86399 : bptr = jd->basicblocks;
138 :
139 492080 : for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
140 :
141 405681 : if (bptr->type == basicblock::TYPE_EXH) {
142 : /* predecessorcount for exception handlers is initialized to -1,
143 : so we need to fix it to 0. */
144 9964 : bptr->predecessorcount += 1;
145 : }
146 :
147 405681 : if ((bptr->icount == 0) || (bptr->state == basicblock::UNDEF))
148 86401 : continue;
149 :
150 319280 : iptr = bptr->iinstr + bptr->icount - 1;
151 :
152 : /* skip NOPs at the end of the block */
153 :
154 872662 : while (iptr->opc == ICMD_NOP) {
155 234102 : if (iptr == bptr->iinstr)
156 0 : break;
157 234102 : iptr--;
158 : }
159 :
160 319280 : if (iptr->opc == ICMD_GOTO) {
161 :
162 : /*
163 : This is needed for the following special case caused by
164 : stack_reach_next_block:
165 : I.e. there might be instructions causing control flow before
166 : a GOTO:
167 :
168 : ....
169 : 129: 192: IFEQ Ti102 0 (0x00000000) --> L052
170 : 131: 193: NOP
171 : 0: 0: GOTO --> L060
172 : */
173 :
174 34738 : bptr->successorcount++;
175 :
176 34738 : tbptr = iptr->dst.block;
177 34738 : tbptr->predecessorcount++;
178 :
179 34738 : if (iptr == bptr->iinstr) {
180 7451 : continue;
181 : }
182 :
183 27287 : iptr--;
184 :
185 56346 : while (iptr->opc == ICMD_NOP) {
186 1772 : if (iptr == bptr->iinstr) {
187 0 : break;
188 : }
189 1772 : iptr--;
190 : }
191 :
192 27287 : has_fallthrough = false;
193 : } else {
194 284542 : has_fallthrough = true;
195 : }
196 :
197 311829 : switch (icmd_table[iptr->opc].controlflow) {
198 :
199 : case CF_END:
200 121690 : break;
201 :
202 : case CF_IF:
203 :
204 106055 : bptr->successorcount += 2;
205 :
206 106055 : tbptr = iptr->dst.block;
207 106055 : tbptr->predecessorcount++;
208 :
209 106055 : if (has_fallthrough) {
210 106054 : ntbptr = bptr->next;
211 106054 : ntbptr->predecessorcount++;
212 : }
213 106055 : break;
214 :
215 : case CF_JSR:
216 17 : bptr->successorcount++;
217 :
218 17 : tbptr = iptr->sx.s23.s3.jsrtarget.block;
219 17 : tbptr->predecessorcount++;
220 17 : break;
221 :
222 : case CF_GOTO:
223 : case CF_RET:
224 15 : bptr->successorcount++;
225 :
226 15 : tbptr = iptr->dst.block;
227 15 : tbptr->predecessorcount++;
228 15 : break;
229 :
230 : case CF_TABLE:
231 72 : table = iptr->dst.table;
232 :
233 72 : bptr->successorcount++;
234 :
235 72 : tbptr = table->block;
236 72 : tbptr->predecessorcount++;
237 72 : table++;
238 :
239 72 : i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
240 :
241 1218 : while (--i >= 0) {
242 1074 : bptr->successorcount++;
243 :
244 1074 : tbptr = table->block;
245 1074 : tbptr->predecessorcount++;
246 1074 : table++;
247 : }
248 72 : break;
249 :
250 : case CF_LOOKUP:
251 60 : lookup = iptr->dst.lookup;
252 :
253 60 : bptr->successorcount++;
254 :
255 60 : tbptr = iptr->sx.s23.s3.lookupdefault.block;
256 60 : tbptr->predecessorcount++;
257 :
258 60 : i = iptr->sx.s23.s2.lookupcount;
259 :
260 600 : while (--i >= 0) {
261 480 : bptr->successorcount++;
262 :
263 480 : tbptr = lookup->target.block;
264 480 : tbptr->predecessorcount++;
265 480 : lookup++;
266 : }
267 60 : break;
268 :
269 : default:
270 83920 : if (has_fallthrough) {
271 56634 : bptr->successorcount++;
272 :
273 56634 : tbptr = bptr->next;
274 :
275 : /* An exception handler has no predecessors. */
276 :
277 56634 : if (tbptr->type != basicblock::TYPE_EXH)
278 56571 : tbptr->predecessorcount++;
279 : }
280 : break;
281 : }
282 : }
283 :
284 : /* Second iteration to allocate the arrays and insert the basic
285 : block pointers. */
286 :
287 86399 : bptr = jd->basicblocks;
288 :
289 492080 : for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
290 405681 : if ((bptr->icount == 0) || (bptr->state == basicblock::UNDEF))
291 86401 : continue;
292 :
293 319280 : iptr = bptr->iinstr + bptr->icount - 1;
294 :
295 : /* skip NOPs at the end of the block */
296 :
297 872662 : while (iptr->opc == ICMD_NOP) {
298 234102 : if (iptr == bptr->iinstr)
299 0 : break;
300 234102 : iptr--;
301 : }
302 :
303 319280 : if (iptr->opc == ICMD_GOTO) {
304 34738 : tbptr = iptr->dst.block;
305 :
306 34738 : cfg_allocate_successors(bptr);
307 :
308 34738 : cfg_insert_successors(bptr, tbptr);
309 :
310 34738 : cfg_allocate_predecessors(tbptr);
311 :
312 34738 : cfg_insert_predecessors(tbptr, bptr);
313 :
314 34738 : if (iptr == bptr->iinstr) {
315 7451 : continue;
316 : }
317 :
318 27287 : iptr--;
319 :
320 56346 : while (iptr->opc == ICMD_NOP) {
321 1772 : if (iptr == bptr->iinstr) {
322 0 : break;
323 : }
324 1772 : iptr--;
325 : }
326 :
327 27287 : has_fallthrough = false;
328 :
329 : } else {
330 284542 : has_fallthrough = true;
331 : }
332 :
333 311829 : switch (icmd_table[iptr->opc].controlflow) {
334 :
335 : case CF_END:
336 121690 : break;
337 :
338 : case CF_IF:
339 :
340 106055 : tbptr = iptr->dst.block;
341 106055 : ntbptr = bptr->next;
342 :
343 106055 : cfg_allocate_successors(bptr);
344 :
345 106055 : cfg_insert_successors(bptr, tbptr);
346 106055 : if (has_fallthrough) {
347 106054 : cfg_insert_successors(bptr, ntbptr);
348 : }
349 :
350 106055 : cfg_allocate_predecessors(tbptr);
351 106055 : if (has_fallthrough) {
352 106054 : cfg_allocate_predecessors(ntbptr);
353 : }
354 :
355 106055 : cfg_insert_predecessors(tbptr, bptr);
356 106055 : if (has_fallthrough) {
357 106054 : cfg_insert_predecessors(ntbptr, bptr);
358 : }
359 106055 : break;
360 :
361 : case CF_JSR:
362 17 : tbptr = iptr->sx.s23.s3.jsrtarget.block;
363 17 : goto goto_tail;
364 :
365 : case CF_GOTO:
366 : case CF_RET:
367 :
368 15 : tbptr = iptr->dst.block;
369 : goto_tail:
370 32 : cfg_allocate_successors(bptr);
371 :
372 32 : cfg_insert_successors(bptr, tbptr);
373 :
374 32 : cfg_allocate_predecessors(tbptr);
375 :
376 32 : cfg_insert_predecessors(tbptr, bptr);
377 32 : break;
378 :
379 : case CF_TABLE:
380 72 : table = iptr->dst.table;
381 :
382 72 : tbptr = table->block;
383 72 : table++;
384 :
385 72 : cfg_allocate_successors(bptr);
386 :
387 72 : cfg_insert_successors(bptr, tbptr);
388 :
389 72 : cfg_allocate_predecessors(tbptr);
390 :
391 72 : cfg_insert_predecessors(tbptr, bptr);
392 :
393 72 : i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
394 :
395 1218 : while (--i >= 0) {
396 1074 : tbptr = table->block;
397 1074 : table++;
398 :
399 1074 : cfg_insert_successors(bptr, tbptr);
400 :
401 1074 : cfg_allocate_predecessors(tbptr);
402 1074 : cfg_insert_predecessors(tbptr, bptr);
403 : }
404 72 : break;
405 :
406 : case CF_LOOKUP:
407 60 : lookup = iptr->dst.lookup;
408 :
409 60 : tbptr = iptr->sx.s23.s3.lookupdefault.block;
410 :
411 60 : cfg_allocate_successors(bptr);
412 :
413 60 : cfg_insert_successors(bptr, tbptr);
414 :
415 60 : cfg_allocate_predecessors(tbptr);
416 :
417 60 : cfg_insert_predecessors(tbptr, bptr);
418 :
419 60 : i = iptr->sx.s23.s2.lookupcount;
420 :
421 600 : while (--i >= 0) {
422 480 : tbptr = lookup->target.block;
423 480 : lookup++;
424 :
425 480 : cfg_insert_successors(bptr, tbptr);
426 :
427 480 : cfg_allocate_predecessors(tbptr);
428 480 : cfg_insert_predecessors(tbptr, bptr);
429 : }
430 60 : break;
431 :
432 : default:
433 83920 : if (has_fallthrough) {
434 56634 : tbptr = bptr->next;
435 :
436 56634 : cfg_allocate_successors(bptr);
437 :
438 56634 : bptr->successors[0] = tbptr;
439 56634 : bptr->successorcount++;
440 :
441 : /* An exception handler has no predecessors. */
442 :
443 56634 : if (tbptr->type != basicblock::TYPE_EXH) {
444 56571 : cfg_allocate_predecessors(tbptr);
445 :
446 56571 : tbptr->predecessors[tbptr->predecessorcount] = bptr;
447 56571 : tbptr->predecessorcount++;
448 : }
449 : }
450 : break;
451 : }
452 : }
453 :
454 : /* everything's ok */
455 :
456 86399 : return true;
457 : }
458 :
459 : /* cfg_add_root ****************************************************************
460 :
461 : Adds an empty root basicblock.
462 : The numbers of all other basicblocks are set off by one.
463 : Needed for some analyses that require the root basicblock to have no
464 : predecessors and to perform special initializations.
465 :
466 : *******************************************************************************/
467 :
468 0 : void cfg_add_root(jitdata *jd) {
469 : basicblock *root, *zero, *it;
470 :
471 0 : zero = jd->basicblocks;
472 :
473 0 : root = DNEW(basicblock);
474 0 : MZERO(root, basicblock, 1);
475 :
476 0 : root->successorcount = 1;
477 0 : root->successors = DMNEW(basicblock *, 1);
478 0 : root->successors[0] = zero;
479 0 : root->next = zero;
480 0 : root->nr = 0;
481 0 : root->type = basicblock::TYPE_STD;
482 0 : root->method = jd->m;
483 :
484 0 : if (zero->predecessorcount == 0) {
485 0 : zero->predecessors = DNEW(basicblock *);
486 : } else {
487 0 : zero->predecessors = DMREALLOC(zero->predecessors, basicblock *, zero->predecessorcount, zero->predecessorcount + 1);
488 : }
489 0 : zero->predecessors[zero->predecessorcount] = root;
490 0 : zero->predecessorcount += 1;
491 :
492 0 : jd->basicblocks = root;
493 0 : jd->basicblockcount += 1;
494 :
495 0 : for (it = zero; it; it = it->next) {
496 0 : it->nr += 1;
497 : }
498 0 : }
499 :
500 0 : void cfg_remove_root(jitdata *jd) {
501 : basicblock *root, *zero, *it;
502 :
503 0 : root = jd->basicblocks;
504 0 : zero = root->next;
505 :
506 0 : zero->predecessorcount -= 1;
507 :
508 0 : jd->basicblocks = zero;
509 :
510 0 : for (it = zero; it; it = it->next) {
511 0 : it->nr -= 1;
512 : }
513 0 : }
514 :
515 0 : void cfg_clear(jitdata *jd)
516 : {
517 :
518 0 : for (basicblock *b = jd->basicblocks; b != NULL; b = b->next)
519 : {
520 0 : b->predecessorcount = (b->type == basicblock::TYPE_EXH) ? -1 : 0;
521 0 : b->successorcount = 0;
522 0 : b->predecessors = NULL;
523 0 : b->successors = NULL;
524 : }
525 0 : }
526 :
527 : #if defined(ENABLE_SSA)
528 :
529 : static void cfg_eliminate_edges_to_unreachable(jitdata *jd);
530 :
531 : /* cfg_add_exceptional_edges ***************************************************
532 :
533 : Edges from basicblocks to their exception handlers and from exception
534 : handlers to the blocks they handle exceptions for are added. Further
535 : the number of potentially throwing instructions in the basicblocks are
536 : counted.
537 :
538 : We don't consider nor do we determine the types of exceptions thrown. Edges
539 : are added from every block to every potential handler.
540 :
541 : *******************************************************************************/
542 :
543 : void cfg_add_exceptional_edges(jitdata *jd) {
544 : basicblock *bptr;
545 : instruction *iptr;
546 : exception_entry *ee;
547 : bool unreachable_exh = false;
548 :
549 : /* Count the number of exceptional exits for every block.
550 : * Every PEI is an exceptional out.
551 : */
552 :
553 : FOR_EACH_BASICBLOCK(jd, bptr) {
554 :
555 : /* Prepare for reachability calculation. */
556 : bptr->vp = NULL;
557 :
558 : if (bptr->state == basicblock::UNDEF) {
559 : continue;
560 : }
561 :
562 : FOR_EACH_INSTRUCTION(bptr, iptr) {
563 : if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
564 : bptr->exouts += 1;
565 : }
566 : }
567 : }
568 :
569 : /* Count the number of exception handlers for every block. */
570 :
571 : for (ee = jd->exceptiontable; ee; ee = ee->down) {
572 : for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
573 : /* Linking a block with a handler, even if there are no exceptional exits
574 : breaks stuff in other passes. */
575 : if (bptr->exouts > 0) {
576 : bptr->exhandlercount += 1;
577 : ee->handler->expredecessorcount += 1;
578 : }
579 : }
580 : }
581 :
582 : /* Allocate and fill exception handler arrays. */
583 :
584 : for (ee = jd->exceptiontable; ee; ee = ee->down) {
585 :
586 : if (ee->handler->expredecessorcount == 0) {
587 : /* An exception handler that is unreachable.
588 : This is inconsistent with the semantics of the CFG,
589 : we need to recalculate reachability. */
590 : unreachable_exh = true;
591 : }
592 :
593 : for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
594 : if (bptr->exouts > 0) {
595 :
596 : if (bptr->exhandlers == NULL) {
597 : bptr->exhandlers = DMNEW(basicblock *, bptr->exhandlercount);
598 : /* Move pointer past the end of the array,
599 : * It will be filled in the reverse order.
600 : */
601 : bptr->exhandlers += bptr->exhandlercount;
602 : }
603 :
604 : bptr->exhandlers -= 1;
605 : *(bptr->exhandlers) = ee->handler;
606 :
607 : if (ee->handler->expredecessors == NULL) {
608 : ee->handler->expredecessors = DMNEW(basicblock *, ee->handler->expredecessorcount);
609 : ee->handler->expredecessors += ee->handler->expredecessorcount;
610 : }
611 :
612 : ee->handler->expredecessors -= 1;
613 : *(ee->handler->expredecessors) = bptr;
614 : }
615 : }
616 : }
617 :
618 : if (unreachable_exh) {
619 :
620 : /* This is rare in ``normal'' compiler generated code.
621 :
622 : The dead block [EXH] is a predecessor of [BB1],
623 : but the edge [EXH] -> [BB1] will never be traversed.
624 :
625 : [BB1] --[next]--> [BB2, no peis] ==[exhandler]==> [EXH] --[next]--+
626 : ^ |
627 : +---------------------------------------------------------------+
628 : */
629 :
630 : /*
631 : fprintf(stderr, "Found unreachable exh, adjusting %s %s",
632 : UTF_TEXT(jd->m->klazz->name), UTF_TEXT(jd->m->name));
633 : fprintf(stderr, "<before>\n");
634 : show_method(jd, 3);
635 : fprintf(stderr, "</before>\n");
636 : */
637 :
638 : cfg_eliminate_edges_to_unreachable(jd);
639 :
640 : /*
641 : fprintf(stderr, "<after>\n");
642 : show_method(jd, 3);
643 : fprintf(stderr, "</after>\n");
644 : */
645 : }
646 : }
647 :
648 : static void cfg_calculate_reachability(basicblock *bptr) {
649 : basicblock **itsucc;
650 :
651 : /* Block not marked. */
652 : assert(bptr->vp == NULL);
653 :
654 : bptr->vp = bptr; /* Mark block */
655 :
656 : FOR_EACH_SUCCESSOR(bptr, itsucc) {
657 : if ((*itsucc)->vp == NULL) {
658 : cfg_calculate_reachability(*itsucc);
659 : }
660 : }
661 :
662 : if (bptr->exouts > 0) {
663 : FOR_EACH_EXHANDLER(bptr, itsucc) {
664 : if ((*itsucc)->vp == NULL) {
665 : cfg_calculate_reachability(*itsucc);
666 : }
667 : }
668 : }
669 : }
670 :
671 : static void cfg_remove_predecessors(basicblock *bptr, basicblock *pbptr) {
672 : s4 i;
673 :
674 : for (i = 0; i < bptr->predecessorcount; ++i) {
675 : /* Search item. */
676 : if (bptr->predecessors[i] == pbptr) {
677 : if (i != (bptr->predecessorcount - 1)) {
678 : /* If not last element, replace element with last element. */
679 : bptr->predecessors[i] = bptr->predecessors[bptr->predecessorcount - 1];
680 : }
681 :
682 : /* Decrease element count. */
683 : bptr->predecessorcount -= 1;
684 :
685 : return;
686 : }
687 : }
688 : }
689 :
690 : static void cfg_eliminate_edges_to_unreachable(jitdata *jd) {
691 : basicblock *it;
692 : basicblock **itsucc;
693 :
694 : cfg_calculate_reachability(jd->basicblocks);
695 :
696 : FOR_EACH_BASICBLOCK(jd, it) {
697 : if (it->vp == NULL) {
698 :
699 : /* Mark as unreachable. */
700 :
701 : it->state = basicblock::UNDEF;
702 :
703 : /* As this block got unreachable, it is no more a predecessor
704 : of its successors. */
705 :
706 : FOR_EACH_SUCCESSOR(it, itsucc) {
707 : cfg_remove_predecessors(*itsucc, it);
708 : }
709 :
710 : /* Eliminiate all CFG edges of this block. */
711 :
712 : it->predecessorcount = 0;
713 : it->successorcount = 0;
714 : it->expredecessorcount = 0;
715 : }
716 : }
717 : }
718 :
719 : #endif
720 :
721 : /*
722 : * These are local overrides for various environment variables in Emacs.
723 : * Please do not remove this and leave it at the end of the file, where
724 : * Emacs will automagically detect them.
725 : * ---------------------------------------------------------------------
726 : * Local variables:
727 : * mode: c++
728 : * indent-tabs-mode: t
729 : * c-basic-offset: 4
730 : * tab-width: 4
731 : * End:
732 : * vim:noexpandtab:sw=4:ts=4:
733 : */
|
