Mercurial > hg > graal-compiler
comparison graal/GraalCompiler/src/com/sun/c1x/opt/CEEliminator.java @ 2509:16b9a8b5ad39
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/CEEliminator.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 import com.sun.cri.ci.*; | |
31 | |
32 /** | |
33 * This class implements conditional-expression elimination, which replaces some | |
34 * simple branching constructs with conditional moves. | |
35 * | |
36 * @author Ben L. Titzer | |
37 */ | |
38 public class CEEliminator implements BlockClosure { | |
39 | |
40 final IR ir; | |
41 final InstructionSubstituter subst; | |
42 | |
43 public CEEliminator(IR ir) { | |
44 this.ir = ir; | |
45 this.subst = new InstructionSubstituter(ir); | |
46 ir.startBlock.iteratePreOrder(this); | |
47 subst.finish(); | |
48 } | |
49 | |
50 void adjustExceptionEdges(BlockBegin block, BlockBegin sux) { | |
51 int e = sux.numberOfExceptionHandlers(); | |
52 for (int i = 0; i < e; i++) { | |
53 BlockBegin xhandler = sux.exceptionHandlerAt(i); | |
54 block.addExceptionHandler(xhandler); | |
55 | |
56 assert xhandler.isPredecessor(sux) : "missing predecessor"; | |
57 if (sux.numberOfPreds() == 0) { | |
58 // sux is disconnected from graph so disconnect from exception handlers | |
59 xhandler.removePredecessor(sux); | |
60 } | |
61 if (!xhandler.isPredecessor(block)) { | |
62 xhandler.addPredecessor(block); | |
63 } | |
64 } | |
65 } | |
66 | |
67 public void apply(BlockBegin block) { | |
68 // 1) check that block ends with an If | |
69 if (!(block.end() instanceof If)) { | |
70 return; | |
71 } | |
72 If curIf = (If) block.end(); | |
73 | |
74 // check that the if's operands are of int or object type | |
75 CiKind ifType = curIf.x().kind; | |
76 if (!ifType.isInt() && !ifType.isObject()) { | |
77 return; | |
78 } | |
79 | |
80 BlockBegin tBlock = curIf.trueSuccessor(); | |
81 BlockBegin fBlock = curIf.falseSuccessor(); | |
82 Instruction tCur = tBlock.next(); | |
83 Instruction fCur = fBlock.next(); | |
84 | |
85 // one Constant may be present between BlockBegin and BlockEnd | |
86 Instruction tConst = null; | |
87 Instruction fConst = null; | |
88 if (tCur instanceof Constant) { | |
89 tConst = tCur; | |
90 tCur = tCur.next(); | |
91 } | |
92 if (fCur instanceof Constant) { | |
93 fConst = fCur; | |
94 fCur = fCur.next(); | |
95 } | |
96 | |
97 // check that both branches end with a goto | |
98 if (!(tCur instanceof Goto) || !(fCur instanceof Goto)) { | |
99 return; | |
100 } | |
101 Goto tGoto = (Goto) tCur; | |
102 Goto fGoto = (Goto) fCur; | |
103 | |
104 // check that both gotos merge into the same block | |
105 BlockBegin sux = tGoto.defaultSuccessor(); | |
106 if (sux != fGoto.defaultSuccessor()) { | |
107 return; | |
108 } | |
109 | |
110 // check that at least one word was pushed on suxState | |
111 FrameState suxState = sux.stateBefore(); | |
112 if (suxState.stackSize() <= curIf.stateAfter().stackSize()) { | |
113 return; | |
114 } | |
115 | |
116 // check that phi function is present at end of successor stack and that | |
117 // only this phi was pushed on the stack | |
118 final Value suxPhi = suxState.stackAt(curIf.stateAfter().stackSize()); | |
119 if (suxPhi == null || !(suxPhi instanceof Phi) || ((Phi) suxPhi).block() != sux) { | |
120 return; | |
121 } | |
122 if (suxPhi.kind.sizeInSlots() != suxState.stackSize() - curIf.stateAfter().stackSize()) { | |
123 return; | |
124 } | |
125 | |
126 // get the values that were pushed in the true- and false-branch | |
127 Value tValue = tGoto.stateAfter().stackAt(curIf.stateAfter().stackSize()); | |
128 Value fValue = fGoto.stateAfter().stackAt(curIf.stateAfter().stackSize()); | |
129 | |
130 assert tValue.kind == fValue.kind : "incompatible types"; | |
131 | |
132 if (tValue.kind.isFloat() || tValue.kind.isDouble()) { | |
133 // backend does not support conditional moves on floats | |
134 return; | |
135 } | |
136 | |
137 // check that successor has no other phi functions but suxPhi | |
138 // this can happen when tBlock or fBlock contained additional stores to local variables | |
139 // that are no longer represented by explicit instructions | |
140 boolean suxHasOtherPhi = sux.stateBefore().forEachPhi(sux, new PhiProcedure() { | |
141 public boolean doPhi(Phi phi) { | |
142 return phi == suxPhi; | |
143 } | |
144 }); | |
145 if (suxHasOtherPhi) { | |
146 return; | |
147 } | |
148 | |
149 // check that true and false blocks don't have phis | |
150 if (tBlock.stateBefore().hasPhis() || fBlock.stateBefore().hasPhis()) { | |
151 return; | |
152 } | |
153 | |
154 // 2) cut off the original if and replace with constants and a Goto | |
155 // cut curIf away and get node before | |
156 Instruction ifPrev = curIf.prev(block); | |
157 int bci = curIf.bci(); | |
158 | |
159 // append constants of true- and false-block if necessary | |
160 // clone constants because original block must not be destroyed | |
161 assert (tValue != fConst && fValue != tConst) || tConst == fConst : "mismatch"; | |
162 if (tValue == tConst) { | |
163 Constant tc = new Constant(tConst.asConstant()); | |
164 tValue = tc; | |
165 ifPrev = ifPrev.setNext(tc, bci); | |
166 } | |
167 if (fValue == fConst) { | |
168 Constant fc = new Constant(fConst.asConstant()); | |
169 fValue = fc; | |
170 ifPrev = ifPrev.setNext(fc, bci); | |
171 } | |
172 | |
173 Value result; | |
174 if (tValue == fValue) { | |
175 // conditional chooses the same value regardless | |
176 result = tValue; | |
177 C1XMetrics.RedundantConditionals++; | |
178 } else { | |
179 // it is very unlikely that the condition can be statically decided | |
180 // (this was checked previously by the Canonicalizer), so always | |
181 // append IfOp | |
182 result = new IfOp(curIf.x(), curIf.condition(), curIf.y(), tValue, fValue); | |
183 ifPrev = ifPrev.setNext((Instruction) result, bci); | |
184 } | |
185 | |
186 // append Goto to successor | |
187 FrameState stateBefore = curIf.isSafepoint() ? curIf.stateAfter() : null; | |
188 Goto newGoto = new Goto(sux, stateBefore, curIf.isSafepoint() || tGoto.isSafepoint() || fGoto.isSafepoint()); | |
189 | |
190 // prepare state for Goto | |
191 FrameState tempGotoState = curIf.stateAfter(); | |
192 while (suxState.scope() != tempGotoState.scope()) { | |
193 tempGotoState = tempGotoState.popScope(); | |
194 assert tempGotoState != null : "states do not match up"; | |
195 } | |
196 MutableFrameState gotoState = tempGotoState.copy(); | |
197 gotoState.push(result.kind, result); | |
198 assert gotoState.isSameAcrossScopes(suxState) : "states must match now"; | |
199 // ATTN: assumption: last use of gotoState, else add .immutableCopy() | |
200 newGoto.setStateAfter(gotoState); | |
201 | |
202 // Steal the bci for the goto from the sux | |
203 ifPrev = ifPrev.setNext(newGoto, sux.bci()); | |
204 | |
205 // update block end (will remove this block from tBlock and fBlock predecessors) | |
206 block.setEnd(newGoto); | |
207 | |
208 // remove blocks if they became unreachable | |
209 tryRemove(tBlock); | |
210 tryRemove(fBlock); | |
211 | |
212 // substitute the phi if possible | |
213 Phi suxAsPhi = (Phi) suxPhi; | |
214 if (suxAsPhi.inputCount() == 1) { | |
215 // if the successor block now has only one predecessor | |
216 assert suxAsPhi.inputAt(0) == result : "screwed up phi"; | |
217 subst.setSubst(suxPhi, result); | |
218 | |
219 // 3) successfully eliminated a conditional expression | |
220 C1XMetrics.ConditionalEliminations++; | |
221 } | |
222 } | |
223 | |
224 private void tryRemove(BlockBegin succ) { | |
225 if (succ.numberOfPreds() == 0) { | |
226 // block just became unreachable | |
227 for (BlockBegin s : succ.end().successors()) { | |
228 s.predecessors().remove(succ); | |
229 } | |
230 } | |
231 } | |
232 } |