001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.compilers.opt.controlflow;
014
015 import static org.jikesrvm.compilers.opt.ir.Operators.GOTO;
016
017 import java.util.Enumeration;
018
019 import org.jikesrvm.VM;
020 import org.jikesrvm.compilers.opt.OptOptions;
021 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
022 import org.jikesrvm.compilers.opt.ir.BasicBlock;
023 import org.jikesrvm.compilers.opt.ir.Goto;
024 import org.jikesrvm.compilers.opt.ir.IR;
025 import org.jikesrvm.compilers.opt.ir.Instruction;
026 import org.jikesrvm.compilers.opt.ir.WeightedBranchTargets;
027 import org.jikesrvm.compilers.opt.util.GraphNode;
028 import org.jikesrvm.util.BitVector;
029
030 /**
031 * This Phase supports
032 * <ul>
033 * <li>transforming while into until loops,
034 * <li>elimination of critical edges,
035 * </ul>
036 */
037 public class CFGTransformations extends CompilerPhase {
038
039 private static final boolean DEBUG = false;
040
041 /**
042 * Return this instance of this phase. This phase contains no
043 * per-compilation instance fields.
044 * @param ir not used
045 * @return this
046 */
047 @Override
048 public CompilerPhase newExecution(IR ir) {
049 return this;
050 }
051
052 @Override
053 public void perform(IR ir) {
054 staticPerform(ir);
055 }
056
057 /**
058 * static version of perform
059 * @param ir
060 */
061 static void staticPerform(IR ir) {
062 if (ir.hasReachableExceptionHandlers()) return;
063
064 // Note: the following unfactors the CFG.
065 DominatorsPhase dom = new DominatorsPhase(true);
066 boolean moreToCome = true;
067 while (moreToCome) {
068 dom.perform(ir);
069 moreToCome = turnWhilesIntoUntils(ir);
070 }
071
072 ensureLandingPads(ir);
073
074 dom.perform(ir);
075 ir.cfg.compactNodeNumbering();
076 ir.HIRInfo.dominatorsAreComputed = false; // compacting the node numbering destroys the dominator info
077 }
078
079 /**
080 * Should this phase be performed?
081 * @return <code>true</code> if the opt level is at least 2 and whiles should be turned into untils
082 */
083 @Override
084 public boolean shouldPerform(OptOptions options) {
085 if (options.getOptLevel() < 2) {
086 return false;
087 }
088 return options.CONTROL_TURN_WHILES_INTO_UNTILS;
089 }
090
091 /**
092 * Returns the name of the phase.
093 */
094 @Override
095 public String getName() {
096 return "Loop Normalization";
097 }
098
099 /**
100 * Returns {@code true} if the phase wants the IR dumped before and/or after it runs.
101 */
102 @Override
103 public boolean printingEnabled(OptOptions options, boolean before) {
104 return false;
105 }
106
107 //Implementation
108 /**
109 * treat all loops of the ir
110 */
111 private static boolean turnWhilesIntoUntils(IR ir) {
112 LSTGraph lstg = ir.HIRInfo.loopStructureTree;
113 if (lstg != null) {
114 return turnLoopTreeIntoUntils((LSTNode) lstg.firstNode(), ir);
115 }
116 return false;
117 }
118
119 /**
120 * deal with a sub tree of the loop structure tree
121 */
122 private static boolean turnLoopTreeIntoUntils(LSTNode t, IR ir) {
123 Enumeration<GraphNode> e = t.outNodes();
124 while (e.hasMoreElements()) {
125 LSTNode n = (LSTNode) e.nextElement();
126 if (turnLoopTreeIntoUntils(n, ir)) {
127 return true;
128 }
129 if (turnLoopIntoUntil(n, ir)) {
130 return true;
131 }
132 }
133 return false;
134 }
135
136 /**
137 * treat all loops of the ir
138 */
139 private static void ensureLandingPads(IR ir) {
140 LSTGraph lstg = ir.HIRInfo.loopStructureTree;
141 if (lstg != null) {
142 ensureLandingPads((LSTNode) lstg.firstNode(), ir);
143 }
144 }
145
146 /**
147 * deal with a sub tree of the loop structure tree
148 */
149 private static void ensureLandingPads(LSTNode t, IR ir) {
150 Enumeration<GraphNode> e = t.outNodes();
151 while (e.hasMoreElements()) {
152 LSTNode n = (LSTNode) e.nextElement();
153 ensureLandingPads(n, ir);
154 ensureLandingPad(n, ir);
155 }
156 }
157
158 private static float edgeFrequency(BasicBlock a, BasicBlock b) {
159 float prop = 0f;
160 WeightedBranchTargets ws = new WeightedBranchTargets(a);
161 while (ws.hasMoreElements()) {
162 if (ws.curBlock() == b) prop += ws.curWeight();
163 ws.advance();
164 }
165 return a.getExecutionFrequency() * prop;
166 }
167
168 private static void ensureLandingPad(LSTNode n, IR ir) {
169 BasicBlock[] ps = loopPredecessors(n);
170 if (ps.length == 1 && ps[0].getNumberOfOut() == 1) return;
171
172 float frequency = 0f;
173 for (BasicBlock bb : ps) {
174 frequency += edgeFrequency(bb, n.header);
175 }
176 BasicBlock newPred;
177 newPred = n.header.createSubBlock(n.header.firstInstruction().bcIndex, ir, 1f);
178 newPred.setLandingPad();
179 newPred.setExecutionFrequency(frequency);
180
181 BasicBlock p = n.header.prevBasicBlockInCodeOrder();
182 if (VM.VerifyAssertions) VM._assert(p != null);
183 p.killFallThrough();
184 ir.cfg.breakCodeOrder(p, n.header);
185 ir.cfg.linkInCodeOrder(p, newPred);
186 ir.cfg.linkInCodeOrder(newPred, n.header);
187
188 newPred.lastInstruction().insertBefore(Goto.create(GOTO, n.header.makeJumpTarget()));
189 newPred.recomputeNormalOut(ir);
190
191 for (BasicBlock bb : ps) {
192 bb.redirectOuts(n.header, newPred, ir);
193 }
194 }
195
196 /**
197 * Transform a given loop
198 *
199 * <p> Look for the set S of in-loop predecessors of the loop header h.
200 * Make a copy h' of the loop header and redirect all edges going from
201 * nodes in S to h. Make them point to h' instead.
202 *
203 * <p> As an effect of this transformation, the old header is now not anymore
204 * part of the loop, but guards it.
205 */
206 private static boolean turnLoopIntoUntil(LSTNode n, IR ir) {
207 BasicBlock header = n.header;
208 BasicBlock newLoopTest = null;
209
210 int i = 0;
211 int exiters = 0;
212
213 Enumeration<BasicBlock> e = ir.getBasicBlocks(n.loop);
214 while (e.hasMoreElements()) {
215 BasicBlock b = e.nextElement();
216 if (!exitsLoop(b, n.loop)) {
217 // header doesn't exit: nothing to do
218 if (b == n.header) return false;
219 } else {
220 exiters++;
221 }
222 i++;
223 }
224 // all blocks exit: can't improve
225 if (i == exiters) return false;
226
227 // rewriting loops where the header has more than one in-loop
228 // successor will lead to irreducible control flow.
229 BasicBlock[] succ = inLoopSuccessors(n);
230 if (succ.length > 1) {
231 if (DEBUG) VM.sysWrite("unwhiling would lead to irreducible CFG\n");
232 return false;
233 }
234
235 BasicBlock[] pred = inLoopPredecessors(n);
236 float frequency = 0f;
237
238 if (pred.length > 0) {
239 frequency += edgeFrequency(pred[0], header);
240 // replicate the header as successor of pred[0]
241 BasicBlock p = header.prevBasicBlockInCodeOrder();
242 p.killFallThrough();
243 newLoopTest = pred[0].replicateThisOut(ir, header, p);
244 }
245 for (i = 1; i < pred.length; ++i) { // check for aditional back edges
246 frequency += edgeFrequency(pred[i], header);
247 pred[i].redirectOuts(header, newLoopTest, ir);
248 }
249 newLoopTest.setExecutionFrequency(frequency);
250 header.setExecutionFrequency(header.getExecutionFrequency() - frequency);
251 return true;
252 }
253
254 /**
255 * the predecessors of the loop header that are not part of the loop
256 */
257 private static BasicBlock[] loopPredecessors(LSTNode n) {
258 BasicBlock header = n.header;
259 BitVector loop = n.loop;
260
261 int i = 0;
262 Enumeration<BasicBlock> be = header.getIn();
263 while (be.hasMoreElements()) if (!inLoop(be.nextElement(), loop)) i++;
264
265 BasicBlock[] res = new BasicBlock[i];
266
267 i = 0;
268 be = header.getIn();
269 while (be.hasMoreElements()) {
270 BasicBlock in = be.nextElement();
271 if (!inLoop(in, loop)) res[i++] = in;
272 }
273 return res;
274 }
275
276 /**
277 * the predecessors of the loop header that are part of the loop.
278 */
279 private static BasicBlock[] inLoopPredecessors(LSTNode n) {
280 BasicBlock header = n.header;
281 BitVector loop = n.loop;
282
283 int i = 0;
284 Enumeration<BasicBlock> be = header.getIn();
285 while (be.hasMoreElements()) if (inLoop(be.nextElement(), loop)) i++;
286
287 BasicBlock[] res = new BasicBlock[i];
288
289 i = 0;
290 be = header.getIn();
291 while (be.hasMoreElements()) {
292 BasicBlock in = be.nextElement();
293 if (inLoop(in, loop)) res[i++] = in;
294 }
295 return res;
296 }
297
298 /**
299 * the successors of the loop header that are part of the loop.
300 */
301 private static BasicBlock[] inLoopSuccessors(LSTNode n) {
302 BasicBlock header = n.header;
303 BitVector loop = n.loop;
304
305 int i = 0;
306 Enumeration<BasicBlock> be = header.getOut();
307 while (be.hasMoreElements()) if (inLoop(be.nextElement(), loop)) i++;
308
309 BasicBlock[] res = new BasicBlock[i];
310
311 i = 0;
312 be = header.getOut();
313 while (be.hasMoreElements()) {
314 BasicBlock in = be.nextElement();
315 if (inLoop(in, loop)) res[i++] = in;
316 }
317 return res;
318 }
319
320 static void killFallThroughs(IR ir, BitVector nloop) {
321 Enumeration<BasicBlock> bs = ir.getBasicBlocks(nloop);
322 while (bs.hasMoreElements()) {
323 BasicBlock block = bs.nextElement();
324 Enumeration<BasicBlock> bi = block.getIn();
325 while (bi.hasMoreElements()) {
326 BasicBlock in = bi.nextElement();
327 if (inLoop(in, nloop)) continue;
328 in.killFallThrough();
329 }
330 block.killFallThrough();
331 }
332 }
333
334 static boolean inLoop(BasicBlock b, BitVector nloop) {
335 int idx = b.getNumber();
336 if (idx >= nloop.length()) return false;
337 return nloop.get(idx);
338 }
339
340 private static boolean exitsLoop(BasicBlock b, BitVector loop) {
341 Enumeration<BasicBlock> be = b.getOut();
342 while (be.hasMoreElements()) {
343 if (!inLoop(be.nextElement(), loop)) return true;
344 }
345 return false;
346 }
347
348 /**
349 * Critical edge removal: if (a,b) is an edge in the cfg where `a' has more
350 * than one out-going edge and `b' has more than one in-coming edge,
351 * insert a new empty block `c' on the edge between `a' and `b'.
352 *
353 * <p> We do this to provide landing pads for loop-invariant code motion.
354 * So we split only edges, where `a' has a lower loop nesting depth than `b'.
355 */
356 public static void splitCriticalEdges(IR ir) {
357 Enumeration<BasicBlock> e = ir.getBasicBlocks();
358 while (e.hasMoreElements()) {
359 BasicBlock b = e.nextElement();
360 int numberOfIns = b.getNumberOfIn();
361 //Exception handlers and blocks with less than two inputs
362 // are no candidates for `b'.
363 if (b.isExceptionHandlerBasicBlock() || numberOfIns <= 1) {
364 continue;
365 }
366 // copy the predecessors, since we will alter the incoming edges.
367 BasicBlock[] ins = new BasicBlock[numberOfIns];
368 Enumeration<BasicBlock> ie = b.getIn();
369 for (int i = 0; i < numberOfIns; ++i) {
370 ins[i] = ie.nextElement();
371 }
372 // skip blocks, that do not fulfill our requirements for `a'
373 for (int i = 0; i < numberOfIns; ++i) {
374 BasicBlock a = ins[i];
375 if (a.getNumberOfOut() <= 1) {
376 continue;
377 }
378 // insert pads only for moving code up to the start of the method
379 //if (a.getExecutionFrequency() >= b.getExecutionFrequency()) continue;
380
381 // create a new block as landing pad
382 BasicBlock landingPad;
383 Instruction firstInB = b.firstInstruction();
384 int bcIndex = firstInB != null ? firstInB.bcIndex : -1;
385 landingPad = b.createSubBlock(bcIndex, ir);
386 landingPad.setLandingPad();
387 landingPad.setExecutionFrequency(edgeFrequency(a, b));
388
389 // make the landing pad jump to `b'
390 Instruction g;
391 g = Goto.create(GOTO, b.makeJumpTarget());
392 landingPad.appendInstruction(g);
393 landingPad.recomputeNormalOut(ir);
394 // redirect a's outputs from b to the landing pad
395 a.redirectOuts(b, landingPad, ir);
396
397 a.killFallThrough();
398 BasicBlock aNext = a.nextBasicBlockInCodeOrder();
399 if (aNext != null) {
400 ir.cfg.breakCodeOrder(a, aNext);
401 ir.cfg.linkInCodeOrder(landingPad, aNext);
402 }
403 ir.cfg.linkInCodeOrder(a, landingPad);
404 }
405 }
406 }
407 }