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 java.io.PrintStream;
016 import java.util.LinkedList;
017 import org.jikesrvm.VM;
018 import org.jikesrvm.Constants;
019 import org.jikesrvm.classloader.RVMMethod;
020 import org.jikesrvm.compilers.common.CompiledMethod;
021 import org.jikesrvm.compilers.common.CompiledMethods;
022 import org.jikesrvm.util.ImmutableEntryHashMapRVM;
023
024 /**
025 * This class records decisions taken by the controller. It will remember
026 * controller plans, which contain compilation plans and other goodies,
027 * and allows searching for previous decisions
028 */
029 public final class ControllerMemory implements Constants {
030
031 /**
032 * This is a hashtable of controller plans indexed by RVMMethod.
033 * Each method can have a list of such plans associated with.
034 */
035 private static final ImmutableEntryHashMapRVM<RVMMethod, LinkedList<ControllerPlan>> table =
036 new ImmutableEntryHashMapRVM<RVMMethod, LinkedList<ControllerPlan>>();
037
038 /**
039 * Number of times controller is awoken and did nothing.
040 */
041 private static int didNothing = 0;
042
043 /**
044 * Number of times controller is awoken
045 */
046 private static int awoken = 0;
047
048 // counters for chosen opt levels
049 private static int numMethodsConsidered = 0;
050 private static int numMethodsScheduledForRecomp = 0;
051 private static int numBase = 0;
052 private static int numOpt0 = 0;
053 private static int numOpt1 = 0;
054 private static int numOpt2 = 0;
055 private static int numOpt3 = 0;
056 private static int numOpt4 = 0;
057
058 public static int getNumAwoken() { return awoken; }
059
060 public static int getNumDidNothing() { return didNothing; }
061
062 public static int getNumMethodsConsidered() { return numMethodsConsidered; }
063
064 public static int getNumMethodsScheduledForRecomp() { return numMethodsScheduledForRecomp; }
065
066 public static int getNumBase() { return numBase; }
067
068 public static int getNumOpt0() { return numOpt0; }
069
070 public static int getNumOpt1() { return numOpt1; }
071
072 public static int getNumOpt2() { return numOpt2; }
073
074 public static int getNumOpt3() { return numOpt3; }
075
076 static int getNumOpt4() { return numOpt4; }
077
078 static void incrementNumAwoken() { awoken++; }
079
080 static void incrementNumDidNothing() { didNothing++; }
081
082 static void incrementNumMethodsConsidered() { numMethodsConsidered++; }
083
084 static void incrementNumMethodsScheduledForRecomp() { numMethodsScheduledForRecomp++; }
085
086 public static void incrementNumBase() { numBase++; }
087
088 static void incrementNumOpt0() { numOpt0++; }
089
090 static void incrementNumOpt1() { numOpt1++; }
091
092 static void incrementNumOpt2() { numOpt2++; }
093
094 static void incrementNumOpt3() { numOpt3++; }
095
096 static void incrementNumOpt4() { numOpt4++; }
097
098 /**
099 * Inserts a controller plan keyed on the underlying method
100 *
101 * @param plan the controller plan to insert
102 */
103 static synchronized void insert(ControllerPlan plan) {
104
105 numMethodsScheduledForRecomp++;
106 int optLevel = plan.getCompPlan().options.getOptLevel();
107 switch (optLevel) {
108 case 0:
109 numOpt0++;
110 break;
111 case 1:
112 numOpt1++;
113 break;
114 case 2:
115 numOpt2++;
116 break;
117 case 3:
118 numOpt3++;
119 break;
120 case 4:
121 numOpt4++;
122 break;
123 default:
124 if (VM.VerifyAssertions) VM._assert(NOT_REACHED, "Unknown Opt Level");
125 }
126
127 // first check to see if there is a plan list for this method
128 LinkedList<ControllerPlan> planList = findPlan(plan.getCompPlan().method);
129
130 if (planList == null) {
131 // create a plan list, with the single element being this plan
132 planList = new LinkedList<ControllerPlan>();
133
134 // no synch needed here because the planList is not in the table yet
135 planList.addLast(plan);
136
137 // insert in the hashtable using the method as the hash value
138 table.put(plan.getCompPlan().method, planList);
139 } else {
140 // add the current plan to the end of the list
141 synchronized (planList) {
142 planList.addLast(plan);
143 }
144 }
145
146 // tell the plan what list it is on
147 plan.setPlanList(planList);
148 }
149
150 /**
151 * Looks for a controller plan for the passed method
152 *
153 * @param method The method to look for
154 * @return the list of controller plans for this method if one exists,
155 * otherwise, {@code null}
156 */
157 private static synchronized LinkedList<ControllerPlan> findPlan(RVMMethod method) {
158 return table.get(method);
159 }
160
161 /**
162 * Find the plan for the compiled method that is passed
163 * @param cmpMethod the compiled method of interest
164 * @return the matching plan or {@code null} if none exists.
165 */
166 public static synchronized ControllerPlan findMatchingPlan(CompiledMethod cmpMethod) {
167 RVMMethod method = cmpMethod.getMethod();
168
169 LinkedList<ControllerPlan> planList = findPlan(method);
170 if (planList == null) {
171 return null;
172 } else {
173 // iterate over the planList until we get to this item
174 synchronized (planList) {
175 for (ControllerPlan plan : planList) {
176 // exit when we find ourselves
177 if (plan.getCMID() == cmpMethod.getId()) {
178 return plan;
179 }
180 } // more to process
181 }
182 return null;
183 }
184 }
185
186 /**
187 * Determine if the passed method should be considered as a candidate
188 * for _initial_ AOS recompilation.
189 * A method should not be reconsider for initial AOS recompilation if
190 * a plan already exists for the method whose status is {@link ControllerPlan#IN_PROGRESS},
191 * {@link ControllerPlan#COMPLETED}, {@link ControllerPlan#OUTDATED},
192 * or {@link ControllerPlan#ABORTED_COMPILATION_ERROR} because of compilation error.
193 *
194 * @param method the method of interest
195 * @return whether the method should be considered or not
196 */
197 static synchronized boolean shouldConsiderForInitialRecompilation(RVMMethod method) {
198 LinkedList<ControllerPlan> planList = findPlan(method);
199 if (planList == null) {
200 return true;
201 } else {
202 // iterate over the planList until we find a plan whose status is
203 // inprogress, completed,
204 synchronized (planList) {
205 for (ControllerPlan curPlan : planList) {
206 // exit when we find ourselves
207 byte status = curPlan.getStatus();
208 if (status == ControllerPlan.COMPLETED ||
209 status == ControllerPlan.IN_PROGRESS ||
210 status == ControllerPlan.ABORTED_COMPILATION_ERROR ||
211 status == ControllerPlan.OUTDATED) {
212 return false;
213 }
214 }
215 }
216 return true; // we didn't find any, so return true
217 }
218 }
219
220 /**
221 * Return {@code true} if there is a plan with the given status for the given method
222 *
223 * @param method the method of interest
224 * @param status the status of interest
225 * @return whether or not there is plan with that status for the method
226 */
227 static synchronized boolean planWithStatus(RVMMethod method, byte status) {
228 LinkedList<ControllerPlan> planList = findPlan(method);
229 if (planList != null) {
230 // iterate over the planList until we find a plan with status 'status'
231 synchronized (planList) {
232 for (ControllerPlan curPlan : planList) {
233 if (curPlan.getStatus() == status) {
234 return true;
235 }
236 }
237 }
238 }
239 return false;
240 }
241
242 /**
243 * Return {@code true} iff there is a plan to transition from Base to Opt for a
244 * given CMID.
245 */
246 public static synchronized boolean requestedOSR(int cmid) {
247 CompiledMethod cm = CompiledMethods.getCompiledMethod(cmid);
248
249 // make sure that the cm in question is baseline-compiled
250 if (cm.getCompilerType() != CompiledMethod.BASELINE) return false;
251
252 // OK; now check for an OSR plan
253 RVMMethod m = cm.getMethod();
254 if (m == null) return false;
255 return planWithStatus(m, ControllerPlan.OSR_BASE_2_OPT);
256 }
257
258 /**
259 * Return {@code true} if there is a completed plan with the given opt level for
260 * the given method
261 *
262 * @param method the method of interest
263 * @param optLevel the opt level of interest
264 * @return whether or not there is completed plan with that level
265 * for the method
266 */
267 static synchronized boolean completedPlanWithOptLevel(RVMMethod method, int optLevel) {
268 LinkedList<ControllerPlan> planList = findPlan(method);
269 if (planList != null) {
270 // iterate over the planList until we find a completed plan with the
271 // opt level passed
272 synchronized (planList) {
273 for (ControllerPlan curPlan : planList) {
274 if (curPlan.getStatus() == ControllerPlan.COMPLETED &&
275 curPlan.getCompPlan().options.getOptLevel() == optLevel) {
276 return true;
277 }
278 }
279 }
280 }
281 return false;
282 }
283
284 /**
285 * Looks for the last controller plan for the passed method
286 *
287 * @param method The method to look for
288 * @return The last controller plan for this method if it exists,
289 * otherwise, {@code null}
290 */
291 public static synchronized ControllerPlan findLatestPlan(RVMMethod method) {
292 LinkedList<ControllerPlan> planList = findPlan(method);
293 if (planList == null) {
294 return null;
295 } else {
296 return planList.getLast();
297 }
298 }
299
300 /**
301 * This method summarizes the recompilation actions taken for all methods
302 * in this object and produces a report to the passed PrintStream.
303 * @param log the stream to print to
304 */
305 public static synchronized void printFinalMethodStats(PrintStream log) {
306 // We will traverse the hash table and for each method record its status as
307 // one of the following
308 // B -> 0 -> 1 -> 2
309 // B -> 0 -> 1
310 // B -> 0
311 // B -> 1 -> 2
312 // B -> 0 -> 2
313 // B -> 2
314 // B -> 1
315 //
316 // We encode these possibilities by turning on 1 of three bits for 0, 1, 2
317 // Also, for all methods that eventually get to level 2, they can be
318 // recompiled an arbitrary amount of times. We record this in in a counter.
319
320 final int MAX_BIT_PATTERN = 7;
321 int[] summaryArray = new int[MAX_BIT_PATTERN + 1];
322 int[] recompsAtLevel2Array = new int[MAX_BIT_PATTERN + 1];
323 int totalRecompsAtLevel2 = 0;
324
325 // traverse table and give a summary of all actions that have occurred
326 for (RVMMethod meth : table.keys()) {
327 LinkedList<ControllerPlan> planList = table.get(meth);
328
329 int bitPattern = 0;
330 int recompsAtLevel2 = 0;
331
332 for (ControllerPlan plan : planList) {
333
334 // only process plans that were completed or completed and outdated
335 // by subsequent plans for this method
336 byte status = plan.getStatus();
337 if (status == ControllerPlan.COMPLETED || status == ControllerPlan.OUTDATED) {
338 int optLevel = plan.getCompPlan().options.getOptLevel();
339
340 // check for recomps at level 2
341 if (optLevel == 2 && bitIsSet(bitPattern, 2)) {
342 recompsAtLevel2++;
343 }
344
345 bitPattern = setBitPattern(bitPattern, optLevel);
346 } // if
347 } // while
348
349 if (Controller.options.LOGGING_LEVEL >= 2) {
350 log.println("Method: " + meth + ", bitPattern: " + bitPattern + ", recompsAtLevel2: " + recompsAtLevel2);
351 }
352
353 summaryArray[bitPattern]++;
354 // track level 2 recomps per pattern
355 recompsAtLevel2Array[bitPattern] += recompsAtLevel2;
356 }
357
358 // Print the summary
359 int totalUniqueMethods = 0;
360 for (int i = 1; i <= MAX_BIT_PATTERN; i++) {
361 log.print(" Base");
362 for (int optLevel = 0; optLevel <= 2; optLevel++) {
363 if (bitIsSet(i, optLevel)) {
364 log.print(" -> " + optLevel);
365 }
366 }
367 log.print(": " + summaryArray[i]);
368 // print any level 2 recomps for this pattern
369 if (recompsAtLevel2Array[i] > 0) {
370 totalRecompsAtLevel2 += recompsAtLevel2Array[i];
371 log.println(" (" + recompsAtLevel2Array[i] + " opt level 2 recomps)");
372 } else {
373 log.println();
374 }
375 totalUniqueMethods = totalUniqueMethods + summaryArray[i];
376 }
377 log.println(" Num recompilations At level 2: " + totalRecompsAtLevel2);
378 log.println(" Num unique methods recompiled: " + totalUniqueMethods + "\n");
379 }
380
381 /**
382 * set the optLevel bit in the passed bitPattern and return the result
383 * @param bitPattern
384 * @param optLevel
385 */
386 static int setBitPattern(int bitPattern, int optLevel) {
387 int newPattern = 1;
388 newPattern = newPattern << optLevel;
389 return newPattern | bitPattern;
390 }
391
392 /**
393 * check if the bit position defined by the 2nd parm is set in the first parm
394 * @param bitPattern
395 * @param optLevel
396 * @return whether the passed bit is set
397 */
398 static boolean bitIsSet(int bitPattern, int optLevel) {
399 int newPattern = 1;
400 newPattern = newPattern << optLevel;
401 return (newPattern & bitPattern) > 0;
402 }
403
404 static synchronized String asString() {
405 return table.toString();
406 }
407 }
408