Mercurial > hg > truffle

comparison graal/GraalCompiler/src/com/sun/c1x/opt/BlockMerger.java @ 2509:16b9a8b5ad39

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Renamings Runtime=>GraalRuntime and Compiler=>GraalCompiler
author Thomas Wuerthinger <thomas@wuerthinger.net>
date Wed, 27 Apr 2011 11:50:44 +0200
parents graal/Compiler/src/com/sun/c1x/opt/BlockMerger.java@9ec15d6914ca
children
comparison
equal deleted inserted replaced
2508:fea94949e0a2 2509:16b9a8b5ad39
1 /*
2 * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package com.sun.c1x.opt;
24
25 import com.sun.c1x.*;
26 import com.sun.c1x.graph.*;
27 import com.sun.c1x.ir.*;
28 import com.sun.c1x.value.*;
29 import com.sun.c1x.value.FrameState.*;
30
31 /**
32 * This class implements block merging, which combines adjacent basic blocks into a larger
33 * basic block, and block skipping, which removes empty blocks that end in a Goto with
34 * their target.
35 *
36 * @author Ben L. Titzer
37 */
38 public class BlockMerger implements BlockClosure {
39
40 private final BlockBegin startBlock;
41 private final IR ir;
42
43 public BlockMerger(IR ir) {
44 this.ir = ir;
45 startBlock = ir.startBlock;
46 startBlock.iteratePreOrder(this);
47 }
48
49 public void apply(BlockBegin block) {
50 while (block.end() instanceof Goto && block != startBlock) {
51 BlockEnd end = block.end();
52 BlockBegin sux = end.defaultSuccessor();
53
54 assert end.successors().size() == 1 : "end must have exactly one successor";
55 assert !sux.isExceptionEntry() : "should not have Goto to exception entry";
56
57 if (!end.isSafepoint()) {
58 if (sux.numberOfPreds() == 1) {
59 // the successor has only one predecessor, merge it into this block
60 mergeBlocks(block, sux, end);
61 C1XMetrics.BlocksMerged++;
62 continue;
63 } else if (C1XOptions.OptBlockSkipping && block.next() == end && !block.isExceptionEntry()) {
64 // the successor has multiple predecessors, but this block is empty
65 skipBlock(block, sux, end);
66 break;
67 }
68 }
69 break;
70 }
71 }
72
73 private void skipBlock(BlockBegin block, final BlockBegin sux, BlockEnd oldEnd) {
74 final FrameState oldState = oldEnd.stateAfter();
75 assert sux.stateBefore().scope() == oldState.scope();
76 boolean hasAtLeastOnePhi = block.stateBefore().forEachPhi(block, new PhiProcedure() {
77 public boolean doPhi(Phi phi) {
78 return false;
79 }
80 });
81
82 if (hasAtLeastOnePhi) {
83 // can't skip a block that has phis
84 return;
85 }
86 for (final BlockBegin pred : block.predecessors()) {
87 final FrameState predState = pred.end().stateAfter();
88 if (predState.scope() != oldState.scope() || predState.stackSize() != oldState.stackSize()) {
89 // scopes would not match after skipping this block
90 // XXX: if phi's were smarter about scopes, this would not be necessary
91 return;
92 }
93 boolean atLeastOneSuxPhiMergesFromAnotherBlock = !sux.stateBefore().forEachPhi(sux, new PhiProcedure() {
94 public boolean doPhi(Phi phi) {
95 if (phi.inputIn(sux.stateBefore()) != phi.inputIn(pred.end().stateAfter())) {
96 return false;
97 }
98 return true;
99 }
100 });
101
102 if (atLeastOneSuxPhiMergesFromAnotherBlock) {
103 return;
104 }
105 }
106 ir.replaceBlock(block, sux);
107 C1XMetrics.BlocksSkipped++;
108 }
109
110 private void mergeBlocks(BlockBegin block, BlockBegin sux, BlockEnd oldEnd) {
111 BlockEnd newEnd;
112 // find instruction before oldEnd & append first instruction of sux block
113 Instruction prev = oldEnd.prev(block);
114 Instruction next = sux.next();
115 assert !(prev instanceof BlockEnd) : "must not be a BlockEnd";
116 prev.setNext(next, next.bci());
117 BlockUtil.disconnectFromGraph(sux);
118 newEnd = sux.end();
119 block.setEnd(newEnd);
120 // add exception handlers of deleted block, if any
121 for (BlockBegin xhandler : sux.exceptionHandlerBlocks()) {
122 block.addExceptionHandler(xhandler);
123
124 // also substitute predecessor of exception handler
125 assert xhandler.isPredecessor(sux) : "missing predecessor";
126 xhandler.removePredecessor(sux);
127 if (!xhandler.isPredecessor(block)) {
128 xhandler.addPredecessor(block);
129 }
130 }
131 }
132 }