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