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