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 import static org.jikesrvm.compilers.opt.ir.Operators.YIELDPOINT_OSR;
017
018 import org.jikesrvm.VM;
019 import org.jikesrvm.compilers.opt.OptOptions;
020 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
021 import org.jikesrvm.compilers.opt.ir.BasicBlock;
022 import org.jikesrvm.compilers.opt.ir.BasicBlockEnumeration;
023 import org.jikesrvm.compilers.opt.ir.Goto;
024 import org.jikesrvm.compilers.opt.ir.IR;
025 import org.jikesrvm.compilers.opt.ir.InlineGuard;
026 import org.jikesrvm.compilers.opt.ir.Instruction;
027 import org.jikesrvm.compilers.opt.ir.InstructionEnumeration;
028
029 /**
030 * Static splitting based on very simple hints left by
031 * guarded inlining (off blocks marked as infrequent)
032 * and semantic knowledge of tests.
033 * The goal of this pass is to create 'common-case' traces.
034 * This is done by eliminating merge points where
035 * uncommon-case code merges back into common case code
036 * by code duplication. We rely on a later pass to
037 * eliminate redundant tests on the common-case trace.
038 * <p>
039 * We use semantic knowledge of the tests to reduce the
040 * code replicated. The key idea is that for a guarded
041 * inlining, it is correct to take the 'off' branch even
042 * if test would select the on-branch. Therefore we can
043 * avoid replicating the on-branch code downstream of the
044 * replicated test, at the possible cost of trapping an
045 * execution in the uncommon-case trace that might have
046 * been able to use a subset of to common-case trace.
047 * <p>
048 */
049 public class StaticSplitting extends CompilerPhase {
050
051 private static final boolean DEBUG = false;
052 private final BranchOptimizations branchOpts;
053
054 public StaticSplitting() {
055 branchOpts = new BranchOptimizations(-1, false, false);
056 }
057
058 /**
059 * Return this instance of this phase. This phase contains no
060 * per-compilation instance fields.
061 * @param ir not used
062 * @return this
063 */
064 public CompilerPhase newExecution(IR ir) {
065 return this;
066 }
067
068 public String getName() { return "Static Splitting"; }
069
070 public boolean shouldPerform(OptOptions options) {
071 return options.CONTROL_STATIC_SPLITTING;
072 }
073
074 public boolean printingEnabled(OptOptions options, boolean before) {
075 return DEBUG;
076 }
077
078 /**
079 * Do simplistic static splitting to create hot traces
080 * with that do not have incoming edges from
081 * blocks that are statically predicted to be cold.
082 *
083 * @param ir The IR on which to apply the phase
084 */
085 public void perform(IR ir) {
086 // (1) Find candidates to split
087 simpleCandidateSearch(ir);
088
089 // (2) Split them
090 boolean needCleanup = haveCandidates();
091 while (haveCandidates()) {
092 splitCandidate(nextCandidate(), ir);
093 }
094
095 // (3) If something was split optimize the CFG
096 if (needCleanup) {
097 branchOpts.perform(ir);
098 }
099 }
100
101 /**
102 * Identify candidate blocks by using a very
103 * simplistic algorithm.
104 * <ul>
105 * <li> Find all blocks that end in a test that
106 * is statically known to be likely to
107 * create a common case trace. For example,
108 * blocks that end in IG_METHOD_TEST, IG_CLASS_TEST
109 * and IG_PATCH_POINT. Note that these tests also
110 * have the property that it is correct
111 * (but less desirable) to execute the off branch
112 * when the test would have selected the on branch.
113 * <li> If such a block has a control flow predecessor
114 * that is marked as infrequent, and if the block
115 * is relatively small, then it is almost certainly
116 * profitable to duplicate the block and transfer
117 * the infrequent predecessor to go to
118 * the cloned block. This has the effect of freeing
119 * the common-case path from the pollution of the
120 * infrequently executed block. Therefore we identify
121 * the block as a splitting candidate.
122 * </ul>
123 */
124 private void simpleCandidateSearch(IR ir) {
125 for (BasicBlockEnumeration e = ir.getBasicBlocks(); e.hasMoreElements();) {
126 BasicBlock cand = e.next();
127 if (cand.isExceptionHandlerBasicBlock()) continue;
128 Instruction candTest = getCandidateTest(cand);
129 if (candTest == null) continue;
130 BasicBlock coldPrev = findColdPrev(cand);
131 if (coldPrev == null) continue;
132 if (tooBig(cand, ir.options.CONTROL_STATIC_SPLITTING_MAX_COST)) continue;
133 BasicBlock coldSucc = findColdSucc(cand, candTest);
134 if (containsOSRPoint(coldSucc)) continue;
135 if (DEBUG) {
136 VM.sysWrite("Found candidate \n");
137 VM.sysWrite("\tTest is " + candTest + "\n");
138 VM.sysWrite("\tcoldPrev is " + coldPrev + "\n");
139 VM.sysWrite("\tcoldSucc is " + coldSucc + "\n");
140 cand.printExtended();
141 }
142 pushCandidate(cand, coldPrev, coldSucc, candTest);
143 }
144 }
145
146 /**
147 * Split a node where we can safely not
148 * replicate the on-branch in the cloned node.
149 * @param ci description of the split candidate.
150 */
151 private void splitCandidate(CandInfo ci, IR ir) {
152 BasicBlock cand = ci.candBB;
153 BasicBlock prev = ci.prevBB;
154 BasicBlock succ = ci.succBB;
155 BasicBlock clone = cand.copyWithoutLinks(ir);
156
157 // Redirect clone to always stay on cold path.
158 Instruction s = clone.lastRealInstruction();
159 while (s.isBranch()) {
160 s = s.remove();
161 }
162 clone.appendInstruction(Goto.create(GOTO, succ.makeJumpTarget()));
163
164 // inject clone in code order;
165 // force prev to go to clone instead of cand.
166 prev.redirectOuts(cand, clone, ir);
167 clone.recomputeNormalOut(ir);
168 ir.cfg.addLastInCodeOrder(clone);
169 clone.setInfrequent();
170 }
171
172 /**
173 * Return the candidate test in b, or <code>null</code> if
174 * b does not have one.
175 */
176 private Instruction getCandidateTest(BasicBlock bb) {
177 Instruction test = null;
178 for (InstructionEnumeration e = bb.enumerateBranchInstructions(); e.hasMoreElements();) {
179 Instruction branch = e.next();
180 if (InlineGuard.conforms(branch)) {
181 if (test != null) return null; // found multiple tests!
182 test = branch;
183 } else if (branch.operator() != GOTO) {
184 return null;
185 }
186 }
187 return test;
188 }
189
190 /**
191 * Return the cold predecessor to the argument block.
192 * If there is not exactly 1, return null.
193 */
194 private BasicBlock findColdPrev(BasicBlock bb) {
195 BasicBlock cold = null;
196 for (java.util.Enumeration<BasicBlock> e = bb.getInNodes(); e.hasMoreElements();) {
197 BasicBlock p = e.nextElement();
198 if (p.getInfrequent()) {
199 if (cold != null) return null;
200 cold = p;
201 }
202 }
203 return cold;
204 }
205
206 /**
207 * Return the off-trace successor of b
208 * (on and off relative to the argument test)
209 */
210 private BasicBlock findColdSucc(BasicBlock bb, Instruction test) {
211 return test.getBranchTarget();
212 }
213
214 /**
215 * Simplistic cost estimate; since we
216 * are doing the splitting based on
217 * static hints, we are only willing to
218 * copy a very small amount of code.
219 */
220 private boolean tooBig(BasicBlock bb, int maxCost) {
221 int cost = 0;
222 for (InstructionEnumeration e = bb.forwardRealInstrEnumerator(); e.hasMoreElements();) {
223 Instruction s = e.next();
224 if (s.isCall()) {
225 cost += 3;
226 } else if (s.isAllocation()) {
227 cost += 6;
228 } else {
229 cost++;
230 }
231 if (cost > maxCost) return true;
232 }
233 return false;
234 }
235
236 private boolean containsOSRPoint(BasicBlock bb) {
237 for (InstructionEnumeration e = bb.forwardRealInstrEnumerator(); e.hasMoreElements();) {
238 Instruction s = e.next();
239 if (s.operator() == YIELDPOINT_OSR) {
240 return true;
241 }
242 }
243 return false;
244 }
245
246 /*
247 * Support for remembering candidates
248 */
249 private CandInfo cands;
250
251 private static final class CandInfo {
252 final BasicBlock candBB;
253 final BasicBlock prevBB;
254 final BasicBlock succBB;
255 final Instruction test;
256 final CandInfo next;
257
258 CandInfo(BasicBlock c, BasicBlock p, BasicBlock s, Instruction t, CandInfo n) {
259 candBB = c;
260 prevBB = p;
261 succBB = s;
262 test = t;
263 next = n;
264 }
265 }
266
267 private void pushCandidate(BasicBlock cand, BasicBlock prev, BasicBlock succ, Instruction test) {
268 cands = new CandInfo(cand, prev, succ, test, cands);
269 }
270
271 private boolean haveCandidates() {
272 return cands != null;
273 }
274
275 private CandInfo nextCandidate() {
276 CandInfo res = cands;
277 cands = cands.next;
278 return res;
279 }
280 }