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, null
156 */
157 @SuppressWarnings("unchecked")
158 // until HashMapRVM becomes generic
159 private static synchronized LinkedList<ControllerPlan> findPlan(RVMMethod method) {
160 return table.get(method);
161 }
162
163 /**
164 * Find the plan for the compiled method that is passed
165 * @param cmpMethod the compiled method of interest
166 * @return the matching plan or null if none exists.
167 */
168 public static synchronized ControllerPlan findMatchingPlan(CompiledMethod cmpMethod) {
169 RVMMethod method = cmpMethod.getMethod();
170
171 LinkedList<ControllerPlan> planList = findPlan(method);
172 if (planList == null) {
173 return null;
174 } else {
175 // iterate over the planList until we get to this item
176 synchronized (planList) {
177 for (ControllerPlan plan : planList) {
178 // exit when we find ourselves
179 if (plan.getCMID() == cmpMethod.getId()) {
180 return plan;
181 }
182 } // more to process
183 }
184 return null;
185 }
186 }
187
188 /**
189 * Determine if the passed method should be considered as a candidate
190 * for _initial_ AOS recompilation.
191 * A method should not be reconsider for initial AOS recompilation if
192 * a plan already exists for the method whose status is IN_PROGRESS,
193 * COMPLETED, OUTDATED, or ABORTED because of compilation error.
194 *
195 * @param method the method of interest
196 * @return whether the method should be considered or not
197 */
198 static synchronized boolean shouldConsiderForInitialRecompilation(RVMMethod method) {
199 LinkedList<ControllerPlan> planList = findPlan(method);
200 if (planList == null) {
201 return true;
202 } else {
203 // iterate over the planList until we find a plan whose status is
204 // inprogress, completed,
205 synchronized (planList) {
206 for (ControllerPlan curPlan : planList) {
207 // exit when we find ourselves
208 byte status = curPlan.getStatus();
209 if (status == ControllerPlan.COMPLETED ||
210 status == ControllerPlan.IN_PROGRESS ||
211 status == ControllerPlan.ABORTED_COMPILATION_ERROR ||
212 status == ControllerPlan.OUTDATED) {
213 return false;
214 }
215 }
216 }
217 return true; // we didn't find any, so return true
218 }
219 }
220
221 /**
222 * Return true if there is a plan with the given status for the given method
223 *
224 * @param method the method of interest
225 * @param status the status of interest
226 * @return whether or not there is plan with that status for the method
227 */
228 static synchronized boolean planWithStatus(RVMMethod method, byte status) {
229 LinkedList<ControllerPlan> planList = findPlan(method);
230 if (planList != null) {
231 // iterate over the planList until we find a plan with status 'status'
232 synchronized (planList) {
233 for (ControllerPlan curPlan : planList) {
234 if (curPlan.getStatus() == status) {
235 return true;
236 }
237 }
238 }
239 }
240 return false;
241 }
242
243 /**
244 * Return true iff there is a plan to transition from Base to Opt for a
245 * given CMID.
246 */
247 public static synchronized boolean requestedOSR(int cmid) {
248 CompiledMethod cm = CompiledMethods.getCompiledMethod(cmid);
249
250 // make sure that the cm in question is baseline-compiled
251 if (cm.getCompilerType() != CompiledMethod.BASELINE) return false;
252
253 // OK; now check for an OSR plan
254 RVMMethod m = cm.getMethod();
255 if (m == null) return false;
256 return planWithStatus(m, ControllerPlan.OSR_BASE_2_OPT);
257 }
258
259 /**
260 * Return true if there is a completed plan with the given opt level for
261 * the given method
262 *
263 * @param method the method of interest
264 * @param optLevel the opt level of interest
265 * @return whether or not there is completed plan with that level
266 * for the method
267 */
268 static synchronized boolean completedPlanWithOptLevel(RVMMethod method, int optLevel) {
269 LinkedList<ControllerPlan> planList = findPlan(method);
270 if (planList != null) {
271 // iterate over the planList until we find a completed plan with the
272 // opt level passed
273 synchronized (planList) {
274 for (ControllerPlan curPlan : planList) {
275 if (curPlan.getStatus() == ControllerPlan.COMPLETED &&
276 curPlan.getCompPlan().options.getOptLevel() == optLevel) {
277 return true;
278 }
279 }
280 }
281 }
282 return false;
283 }
284
285 /**
286 * Looks for the last controller plan for the passed method
287 *
288 * @param method The method to look for
289 * @return The last controller plan for this method if it exists,
290 * otherwise, null
291 */
292 public static synchronized ControllerPlan findLatestPlan(RVMMethod method) {
293 LinkedList<ControllerPlan> planList = findPlan(method);
294 if (planList == null) {
295 return null;
296 } else {
297 return planList.getLast();
298 }
299 }
300
301 /**
302 * This method summarizes the recompilation actions taken for all methods
303 * in this object and produces a report to the passed PrintStream.
304 * @param log the stream to print to
305 */
306 public static synchronized void printFinalMethodStats(PrintStream log) {
307 // We will traverse the hash table and for each method record its status as
308 // one of the following
309 // B -> 0 -> 1 -> 2
310 // B -> 0 -> 1
311 // B -> 0
312 // B -> 1 -> 2
313 // B -> 0 -> 2
314 // B -> 2
315 // B -> 1
316 //
317 // We encode these possibilities by turning on 1 of three bits for 0, 1, 2
318 // Also, for all methods that eventually get to level 2, they can be
319 // recompiled an arbitrary amount of times. We record this in in a counter.
320
321 final int MAX_BIT_PATTERN = 7;
322 int[] summaryArray = new int[MAX_BIT_PATTERN + 1];
323 int[] recompsAtLevel2Array = new int[MAX_BIT_PATTERN + 1];
324 int totalRecompsAtLevel2 = 0;
325
326 // traverse table and give a summary of all actions that have occurred
327 for (RVMMethod meth : table.keys()) {
328 LinkedList<ControllerPlan> planList = table.get(meth);
329
330 int bitPattern = 0;
331 int recompsAtLevel2 = 0;
332
333 for (ControllerPlan plan : planList) {
334
335 // only process plans that were completed or completed and outdated
336 // by subsequent plans for this method
337 byte status = plan.getStatus();
338 if (status == ControllerPlan.COMPLETED || status == ControllerPlan.OUTDATED) {
339 int optLevel = plan.getCompPlan().options.getOptLevel();
340
341 // check for recomps at level 2
342 if (optLevel == 2 && bitIsSet(bitPattern, 2)) {
343 recompsAtLevel2++;
344 }
345
346 bitPattern = setBitPattern(bitPattern, optLevel);
347 } // if
348 } // while
349
350 if (Controller.options.LOGGING_LEVEL >= 2) {
351 log.println("Method: " + meth + ", bitPattern: " + bitPattern + ", recompsAtLevel2: " + recompsAtLevel2);
352 }
353
354 summaryArray[bitPattern]++;
355 // track level 2 recomps per pattern
356 recompsAtLevel2Array[bitPattern] += recompsAtLevel2;
357 }
358
359 // Print the summary
360 int totalUniqueMethods = 0;
361 for (int i = 1; i <= MAX_BIT_PATTERN; i++) {
362 log.print(" Base");
363 for (int optLevel = 0; optLevel <= 2; optLevel++) {
364 if (bitIsSet(i, optLevel)) {
365 log.print(" -> " + optLevel);
366 }
367 }
368 log.print(": " + summaryArray[i]);
369 // print any level 2 recomps for this pattern
370 if (recompsAtLevel2Array[i] > 0) {
371 totalRecompsAtLevel2 += recompsAtLevel2Array[i];
372 log.println(" (" + recompsAtLevel2Array[i] + " opt level 2 recomps)");
373 } else {
374 log.println();
375 }
376 totalUniqueMethods = totalUniqueMethods + summaryArray[i];
377 }
378 log.println(" Num recompilations At level 2: " + totalRecompsAtLevel2);
379 log.println(" Num unique methods recompiled: " + totalUniqueMethods + "\n");
380 }
381
382 /**
383 * set the optLevel bit in the passed bitPattern and return the result
384 * @param bitPattern
385 * @param optLevel
386 */
387 static int setBitPattern(int bitPattern, int optLevel) {
388 int newPattern = 1;
389 newPattern = newPattern << optLevel;
390 return newPattern | bitPattern;
391 }
392
393 /**
394 * check if the bit position defined by the 2nd parm is set in the first parm
395 * @param bitPattern
396 * @param optLevel
397 * @return whether the passed bit is set
398 */
399 static boolean bitIsSet(int bitPattern, int optLevel) {
400 int newPattern = 1;
401 newPattern = newPattern << optLevel;
402 return (newPattern & bitPattern) > 0;
403 }
404
405 static synchronized String asString() {
406 return table.toString();
407 }
408 }
409