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