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.adaptive.controller;
014
015 import org.jikesrvm.VM;
016 import org.jikesrvm.adaptive.recompilation.CompilerDNA;
017 import org.jikesrvm.adaptive.util.AOSLogging;
018 import org.jikesrvm.classloader.NormalMethod;
019 import org.jikesrvm.compilers.common.CompiledMethod;
020
021 /**
022 * This class encapsulates the analytic model used by the controller
023 * to guide multi-level recompilation decisions. An early version of
024 * this model is described in the OOPSLA'2000 paper, but we've made
025 * some improvements since then...
026 *
027 * @see MultiLevelAdaptiveModel
028 */
029 abstract class AnalyticModel extends RecompilationStrategy {
030
031 //---- Interface ------
032 // Code that inherits from AnalyticModel must define the
033 // following behavior
034
035 /**
036 * Initialize the set of "optimization choices" that the
037 * cost-benefit model will consider when using will consider when
038 * using adaptive compilation.
039 */
040 abstract void populateRecompilationChoices();
041
042 /**
043 * Compute the set of optimization choices that should be
044 * considered by the cost-benefit model, given the previous compiler.
045 *
046 * @param prevCompiler The compiler compiler that was used to
047 * compile cmpMethod
048 * @param cmpMethod The compiled method being considered
049 */
050 abstract RecompilationChoice[] getViableRecompilationChoices(int prevCompiler, CompiledMethod cmpMethod);
051
052 // -----------------------------------------------------
053 // Below code that is (currently) common to all recompilation
054 // strategies that use the analytic model.
055
056 /**
057 * Initialize the analytic model:
058 *
059 * NOTE: The call to super.init() uses the command line options to
060 * set up the optimization plans, so this must be run after the
061 * command line options are available.
062 */
063 @Override
064 void init() {
065 // Do the common initialization first
066 super.init();
067
068 // setup the recompilation choices that are available to the
069 // analytic model
070 populateRecompilationChoices();
071 }
072
073 /**
074 * This method is the main decision making loop for all
075 * recompilation strategies that use the analytic model.
076 * <p>
077 * Given a HotMethodRecompilationEvent, this code will determine
078 * IF the method should be recompiled, and if so, HOW to perform
079 * the recompilation, i.e., what compilation plan should be used.
080 * The method returns a controller plan, which contains the compilation
081 * plan and other goodies.
082 *
083 * @param cmpMethod the compiled method of interest
084 * @param hme the HotMethodRecompilationEvent
085 * @return the controller plan to be used or NULL, if no
086 * compilation is to be performed. */
087 @Override
088 ControllerPlan considerHotMethod(CompiledMethod cmpMethod, HotMethodEvent hme) {
089 // Compiler used for the previous compilation
090 int prevCompiler = getPreviousCompiler(cmpMethod);
091 if (prevCompiler == -1) {
092 return null; // Not a method that we can recompile (trap, JNI).
093 }
094
095 ControllerPlan plan = ControllerMemory.findMatchingPlan(cmpMethod);
096
097 // for a outdated hot method from baseline, we consider OSR,
098 // and execute plan in the routine, no more action here
099 if (considerOSRRecompilation(cmpMethod, hme, plan)) return null;
100
101 if (!considerForRecompilation(hme, plan)) return null;
102
103 // Now we know the compiler that generated the method (prevCompiler) and
104 // that the method is a potential candidate for additional recompilation.
105 // So, next decide what, if anything, should be done now.
106 // We consider doing nothing (ie leaving the method at the current
107 // opt level, which incurs no compilation cost), and recompiling the
108 // method at each greater compilation level.
109 double futureTimeForMethod = futureTimeForMethod(hme);
110
111 // initialize bestAction as doing nothing, which means we'll
112 // spend just as much time in the method in the future as we have so far.
113 RecompilationChoice bestActionChoice = null;
114 double bestActionTime = futureTimeForMethod;
115 double bestCost = 0.0;
116
117 AOSLogging.logger.recordControllerEstimateCostDoNothing(cmpMethod.getMethod(),
118 CompilerDNA.getOptLevel(prevCompiler),
119 bestActionTime);
120
121 // Get a vector of optimization choices to consider
122 RecompilationChoice[] recompilationChoices = getViableRecompilationChoices(prevCompiler, cmpMethod);
123
124 // Consider all choices in the vector of possibilities
125 NormalMethod meth = (NormalMethod) hme.getMethod();
126 for (RecompilationChoice choice : recompilationChoices) {
127 // Get the cost and benefit of this choice
128 double cost = choice.getCost(meth);
129 double futureExecutionTime = choice.getFutureExecutionTime(prevCompiler, futureTimeForMethod);
130
131 double curActionTime = cost + futureExecutionTime;
132
133 AOSLogging.logger.recordControllerEstimateCostOpt(cmpMethod.getMethod(), choice.toString(), cost, curActionTime);
134
135 if (curActionTime < bestActionTime) {
136 bestActionTime = curActionTime;
137 bestActionChoice = choice;
138 bestCost = cost;
139 }
140 }
141
142 // if the best action is the previous than we don't need to recompile
143 if (bestActionChoice == null) {
144 plan = null;
145 } else {
146 plan =
147 bestActionChoice.makeControllerPlan(cmpMethod, prevCompiler, futureTimeForMethod, bestActionTime, bestCost);
148 }
149 return plan;
150 }
151
152 /* check if a compiled method is outdated, then decide if it needs OSR from BASE to OPT
153 */
154 boolean considerOSRRecompilation(CompiledMethod cmpMethod, HotMethodEvent hme, ControllerPlan plan) {
155 boolean outdatedBaseline = false;
156 if (plan == null) {
157 // if plan is null, this method was not compiled by AOS; it was
158 // either in the boot image or compiled by the initial baseline
159 // compiler. In either case, if we've completed any recompilation
160 // then the compiled method is outdated.
161 outdatedBaseline =
162 ControllerMemory.planWithStatus(cmpMethod.getMethod(), ControllerPlan.COMPLETED) &&
163 cmpMethod.getCompilerType() == CompiledMethod.BASELINE;
164 if (outdatedBaseline) {
165 AOSLogging.logger.debug("outdated Baseline " + cmpMethod.getMethod() + "(" + cmpMethod.getId() + ")");
166 }
167 }
168
169 // consider OSR option for old baseline-compiled activation
170 if (outdatedBaseline) {
171 if (!hme.getCompiledMethod().getSamplesReset()) {
172 // the first time we see an outdated event, we clear the samples
173 // associated with the cmid.
174 hme.getCompiledMethod().setSamplesReset();
175 Controller.methodSamples.reset(hme.getCMID());
176 AOSLogging.logger.debug(" Resetting method samples " + hme);
177 return true;
178 } else {
179 plan = chooseOSRRecompilation(hme);
180 // insert the plan to memory, which sets up state in the system to trigger
181 // the OSR promotion
182 if (plan != null) {
183 ControllerMemory.insert(plan);
184 // to coordinate with OSRListener, it marks cmpMethod as outdated
185 if (VM.VerifyAssertions) {
186 VM._assert(cmpMethod.getCompilerType() == CompiledMethod.BASELINE);
187 }
188 cmpMethod.setOutdated();
189 }
190 // we don't do any more action on the controller side.
191 return true;
192 }
193 }
194 return false;
195 }
196
197 /**
198 * @param hme sample data for an outdated cmid
199 * @return a plan representing recompilation with OSR, null if OSR not
200 * justified.
201 */
202 private ControllerPlan chooseOSRRecompilation(HotMethodEvent hme) {
203 if (!Controller.options.OSR_PROMOTION) return null;
204
205 AOSLogging.logger.debug(" Consider OSR for " + hme);
206
207 ControllerPlan prev = ControllerMemory.findLatestPlan(hme.getMethod());
208
209 if (prev.getStatus() == ControllerPlan.OSR_BASE_2_OPT) {
210 AOSLogging.logger.debug(" Already have an OSR promotion plan for this method");
211 return null;
212 }
213
214 double millis = prev.getTimeCompleted() - prev.getTimeInitiated();
215 double speedup = prev.getExpectedSpeedup();
216 double futureTimeForMethod = futureTimeForMethod(hme);
217
218 double futureTimeOptimized = futureTimeForMethod / speedup;
219
220 AOSLogging.logger.debug(" Estimated future time for method " + hme + " is " + futureTimeForMethod);
221 AOSLogging.logger.debug(" Estimated future time optimized " + hme + " is " + (futureTimeOptimized + millis));
222
223 if (futureTimeForMethod > futureTimeOptimized + millis) {
224 AOSLogging.logger.recordOSRRecompilationDecision(prev);
225 ControllerPlan p =
226 new ControllerPlan(prev.getCompPlan(),
227 prev.getTimeCreated(),
228 hme.getCMID(),
229 prev.getExpectedSpeedup(),
230 millis,
231 prev.getPriority());
232 // set up state to trigger osr
233 p.setStatus(ControllerPlan.OSR_BASE_2_OPT);
234 return p;
235 } else {
236 return null;
237 }
238 }
239
240 /**
241 * This function defines how the analytic model handles a
242 * AINewHotEdgeEvent. The basic idea is to use the model to
243 * evaluate whether it would be better to do nothing or to recompile
244 * at the same opt level, assuming there would be some "boost" after
245 * performing inlining.
246 */
247 @Override
248 void considerHotCallEdge(CompiledMethod cmpMethod, AINewHotEdgeEvent event) {
249
250 // Compiler used for the previous compilation
251 int prevCompiler = getPreviousCompiler(cmpMethod);
252 if (prevCompiler == -1) {
253 return; // Not a method we can recompile (trap, JNI).
254 }
255
256 ControllerPlan plan = ControllerMemory.findMatchingPlan(cmpMethod);
257 if (!considerForRecompilation(event, plan)) return;
258 double prevCompileTime = cmpMethod.getCompilationTime();
259
260 // Use the model to calculate expected cost of (1) doing nothing
261 // and (2) recompiling at the same opt level with the FDO boost
262 double futureTimeForMethod = futureTimeForMethod(event);
263 double futureTimeForFDOMethod = prevCompileTime + (futureTimeForMethod / event.getBoostFactor());
264
265 int prevOptLevel = CompilerDNA.getOptLevel(prevCompiler);
266 AOSLogging.logger.recordControllerEstimateCostDoNothing(cmpMethod.getMethod(), prevOptLevel, futureTimeForMethod);
267 AOSLogging.logger.recordControllerEstimateCostOpt(cmpMethod.getMethod(),
268 "O" + prevOptLevel + "AI",
269 prevCompileTime,
270 futureTimeForFDOMethod);
271
272 if (futureTimeForFDOMethod < futureTimeForMethod) {
273 // Profitable to recompile with FDO, so do it.
274 int optLevel = CompilerDNA.getOptLevel(prevCompiler);
275 double priority = futureTimeForMethod - futureTimeForFDOMethod;
276 plan =
277 createControllerPlan(cmpMethod.getMethod(),
278 optLevel,
279 null,
280 cmpMethod.getId(),
281 event.getBoostFactor(),
282 futureTimeForFDOMethod,
283 priority);
284 plan.execute();
285 }
286 }
287
288 /**
289 * How much time do we expect to spend in the method in the future if
290 * we take no recompilation action?
291 * The key assumption is that we'll spend just as much time
292 * executing in the the method in the future as we have done so far
293 * in the past.
294 *
295 * @param hme The HotMethodEvent in question
296 * @return estimate of future execution time to be spent in this method
297 */
298 double futureTimeForMethod(HotMethodEvent hme) {
299 double numSamples = hme.getNumSamples();
300 double timePerSample = VM.interruptQuantum;
301 if (!VM.UseEpilogueYieldPoints) {
302 // NOTE: we take two samples per timer interrupt, so we have to
303 // adjust here (otherwise we'd give the method twice as much time
304 // as it actually deserves).
305 timePerSample /= 2.0;
306 }
307 if (Controller.options.mlCBS()) {
308 // multiple method samples per timer interrupt. Divide accordingly.
309 timePerSample /= VM.CBSMethodSamplesPerTick;
310 }
311 double timeInMethodSoFar = numSamples * timePerSample;
312 return timeInMethodSoFar;
313 }
314 }