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