--- old/src/share/vm/runtime/advancedThresholdPolicy.hpp
          +++ new/src/share/vm/runtime/advancedThresholdPolicy.hpp
   1    1  /*
   2      -* Copyright (c) 2010, 2011 Oracle and/or its affiliates. All rights reserved.
   3      -* ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
   4      -*/
        2 + * Copyright (c) 2010, 2011, Oracle and/or its affiliates. All rights reserved.
        3 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
        4 + *
        5 + * This code is free software; you can redistribute it and/or modify it
        6 + * under the terms of the GNU General Public License version 2 only, as
        7 + * published by the Free Software Foundation.
        8 + *
        9 + * This code is distributed in the hope that it will be useful, but WITHOUT
       10 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
       11 + * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
       12 + * version 2 for more details (a copy is included in the LICENSE file that
       13 + * accompanied this code).
       14 + *
       15 + * You should have received a copy of the GNU General Public License version
       16 + * 2 along with this work; if not, write to the Free Software Foundation,
       17 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
       18 + *
       19 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
       20 + * or visit www.oracle.com if you need additional information or have any
       21 + * questions.
       22 + *
       23 + */
   5   24  
   6   25  #ifndef SHARE_VM_RUNTIME_ADVANCEDTHRESHOLDPOLICY_HPP
   7   26  #define SHARE_VM_RUNTIME_ADVANCEDTHRESHOLDPOLICY_HPP
   8   27  
   9   28  #include "runtime/simpleThresholdPolicy.hpp"
  10   29  
  11   30  #ifdef TIERED
  12   31  class CompileTask;
  13   32  class CompileQueue;
  14   33  

  15   34  /*
  16   35   *  The system supports 5 execution levels:
  17   36   *  * level 0 - interpreter
  18   37   *  * level 1 - C1 with full optimization (no profiling)
  19   38   *  * level 2 - C1 with invocation and backedge counters
  20   39   *  * level 3 - C1 with full profiling (level 2 + MDO)
  21   40   *  * level 4 - C2
  22   41   *
  23   42   * Levels 0, 2 and 3 periodically notify the runtime about the current value of the counters
  24   43   * (invocation counters and backedge counters). The frequency of these notifications is
  25   44   * different at each level. These notifications are used by the policy to decide what transition
  26   45   * to make.
  27   46   *
  28   47   * Execution starts at level 0 (interpreter), then the policy can decide either to compile the
  29   48   * method at level 3 or level 2. The decision is based on the following factors:
  30   49   *    1. The length of the C2 queue determines the next level. The observation is that level 2
  31   50   * is generally faster than level 3 by about 30%, therefore we would want to minimize the time
  32   51   * a method spends at level 3. We should only spend the time at level 3 that is necessary to get
  33   52   * adequate profiling. So, if the C2 queue is long enough it is more beneficial to go first to
  34   53   * level 2, because if we transitioned to level 3 we would be stuck there until our C2 compile
  35   54   * request makes its way through the long queue. When the load on C2 recedes we are going to
  36   55   * recompile at level 3 and start gathering profiling information.
  37   56   *    2. The length of C1 queue is used to dynamically adjust the thresholds, so as to introduce
  38   57   * additional filtering if the compiler is overloaded. The rationale is that by the time a
  39   58   * method gets compiled it can become unused, so it doesn't make sense to put too much onto the
  40   59   * queue.
  41   60   *
  42   61   * After profiling is completed at level 3 the transition is made to level 4. Again, the length
  43   62   * of the C2 queue is used as a feedback to adjust the thresholds.
  44   63   *
  45   64   * After the first C1 compile some basic information is determined about the code like the number
  46   65   * of the blocks and the number of the loops. Based on that it can be decided that a method
  47   66   * is trivial and compiling it with C1 will yield the same code. In this case the method is
  48   67   * compiled at level 1 instead of 4.
  49   68   *
  50   69   * We also support profiling at level 0. If C1 is slow enough to produce the level 3 version of
  51   70   * the code and the C2 queue is sufficiently small we can decide to start profiling in the
  52   71   * interpreter (and continue profiling in the compiled code once the level 3 version arrives).
  53   72   * If the profiling at level 0 is fully completed before level 3 version is produced, a level 2
  54   73   * version is compiled instead in order to run faster waiting for a level 4 version.
  55   74   *
  56   75   * Compile queues are implemented as priority queues - for each method in the queue we compute
  57   76   * the event rate (the number of invocation and backedge counter increments per unit of time).
  58   77   * When getting an element off the queue we pick the one with the largest rate. Maintaining the
  59   78   * rate also allows us to remove stale methods (the ones that got on the queue but stopped
  60   79   * being used shortly after that).
  61   80  */
  62   81  
  63   82  /* Command line options:
  64   83   * - Tier?InvokeNotifyFreqLog and Tier?BackedgeNotifyFreqLog control the frequency of method
  65   84   *   invocation and backedge notifications. Basically every n-th invocation or backedge a mutator thread
  66   85   *   makes a call into the runtime.
  67   86   *
  68   87   * - Tier?CompileThreshold, Tier?BackEdgeThreshold, Tier?MinInvocationThreshold control
  69   88   *   compilation thresholds.
  70   89   *   Level 2 thresholds are not used and are provided for option-compatibility and potential future use.
  71   90   *   Other thresholds work as follows:
  72   91   *
  73   92   *   Transition from interpreter (level 0) to C1 with full profiling (level 3) happens when
  74   93   *   the following predicate is true (X is the level):
  75   94   *
  76   95   *   i > TierXInvocationThreshold * s || (i > TierXMinInvocationThreshold * s  && i + b > TierXCompileThreshold * s),
  77   96   *
  78   97   *   where $i$ is the number of method invocations, $b$ number of backedges and $s$ is the scaling
  79   98   *   coefficient that will be discussed further.
  80   99   *   The intuition is to equalize the time that is spend profiling each method.
  81  100   *   The same predicate is used to control the transition from level 3 to level 4 (C2). It should be
  82  101   *   noted though that the thresholds are relative. Moreover i and b for the 0->3 transition come
  83  102   *   from methodOop and for 3->4 transition they come from MDO (since profiled invocations are
  84  103   *   counted separately).
  85  104   *
  86  105   *   OSR transitions are controlled simply with b > TierXBackEdgeThreshold * s predicates.
  87  106   *
  88  107   * - Tier?LoadFeedback options are used to automatically scale the predicates described above depending
  89  108   *   on the compiler load. The scaling coefficients are computed as follows:
  90  109   *
  91  110   *   s = queue_size_X / (TierXLoadFeedback * compiler_count_X) + 1,
  92  111   *
  93  112   *   where queue_size_X is the current size of the compiler queue of level X, and compiler_count_X
  94  113   *   is the number of level X compiler threads.
  95  114   *
  96  115   *   Basically these parameters describe how many methods should be in the compile queue
  97  116   *   per compiler thread before the scaling coefficient increases by one.
  98  117   *
  99  118   *   This feedback provides the mechanism to automatically control the flow of compilation requests
 100  119   *   depending on the machine speed, mutator load and other external factors.
 101  120   *
 102  121   * - Tier3DelayOn and Tier3DelayOff parameters control another important feedback loop.
 103  122   *   Consider the following observation: a method compiled with full profiling (level 3)
 104  123   *   is about 30% slower than a method at level 2 (just invocation and backedge counters, no MDO).
 105  124   *   Normally, the following transitions will occur: 0->3->4. The problem arises when the C2 queue
 106  125   *   gets congested and the 3->4 transition is delayed. While the method is the C2 queue it continues
 107  126   *   executing at level 3 for much longer time than is required by the predicate and at suboptimal speed.
 108  127   *   The idea is to dynamically change the behavior of the system in such a way that if a substantial
 109  128   *   load on C2 is detected we would first do the 0->2 transition allowing a method to run faster.
 110  129   *   And then when the load decreases to allow 2->3 transitions.
 111  130   *
 112  131   *   Tier3Delay* parameters control this switching mechanism.
 113  132   *   Tier3DelayOn is the number of methods in the C2 queue per compiler thread after which the policy
 114  133   *   no longer does 0->3 transitions but does 0->2 transitions instead.
 115  134   *   Tier3DelayOff switches the original behavior back when the number of methods in the C2 queue
 116  135   *   per compiler thread falls below the specified amount.
 117  136   *   The hysteresis is necessary to avoid jitter.
 118  137   *
 119  138   * - TieredCompileTaskTimeout is the amount of time an idle method can spend in the compile queue.
 120  139   *   Basically, since we use the event rate d(i + b)/dt as a value of priority when selecting a method to
 121  140   *   compile from the compile queue, we also can detect stale methods for which the rate has been
 122  141   *   0 for some time in the same iteration. Stale methods can appear in the queue when an application
 123  142   *   abruptly changes its behavior.
 124  143   *
 125  144   * - TieredStopAtLevel, is used mostly for testing. It allows to bypass the policy logic and stick
 126  145   *   to a given level. For example it's useful to set TieredStopAtLevel = 1 in order to compile everything
 127  146   *   with pure c1.
 128  147   *
 129  148   * - Tier0ProfilingStartPercentage allows the interpreter to start profiling when the inequalities in the
 130  149   *   0->3 predicate are already exceeded by the given percentage but the level 3 version of the
 131  150   *   method is still not ready. We can even go directly from level 0 to 4 if c1 doesn't produce a compiled
 132  151   *   version in time. This reduces the overall transition to level 4 and decreases the startup time.
 133  152   *   Note that this behavior is also guarded by the Tier3Delay mechanism: when the c2 queue is too long
 134  153   *   these is not reason to start profiling prematurely.
 135  154   *
 136  155   * - TieredRateUpdateMinTime and TieredRateUpdateMaxTime are parameters of the rate computation.
 137  156   *   Basically, the rate is not computed more frequently than TieredRateUpdateMinTime and is considered
 138  157   *   to be zero if no events occurred in TieredRateUpdateMaxTime.
 139  158   */
 140  159  
 141  160  
 142  161  class AdvancedThresholdPolicy : public SimpleThresholdPolicy {
 143  162    jlong _start_time;
 144  163  
 145  164    // Call and loop predicates determine whether a transition to a higher compilation
 146  165    // level should be performed (pointers to predicate functions are passed to common().
 147  166    // Predicates also take compiler load into account.
 148  167    typedef bool (AdvancedThresholdPolicy::*Predicate)(int i, int b, CompLevel cur_level);
 149  168    bool call_predicate(int i, int b, CompLevel cur_level);
 150  169    bool loop_predicate(int i, int b, CompLevel cur_level);
 151  170    // Common transition function. Given a predicate determines if a method should transition to another level.
 152  171    CompLevel common(Predicate p, methodOop method, CompLevel cur_level);
 153  172    // Transition functions.
 154  173    // call_event determines if a method should be compiled at a different
 155  174    // level with a regular invocation entry.
 156  175    CompLevel call_event(methodOop method, CompLevel cur_level);
 157  176    // loop_event checks if a method should be OSR compiled at a different
 158  177    // level.
 159  178    CompLevel loop_event(methodOop method, CompLevel cur_level);
 160  179    // Has a method been long around?
 161  180    // We don't remove old methods from the compile queue even if they have
 162  181    // very low activity (see select_task()).
 163  182    inline bool is_old(methodOop method);
 164  183    // Was a given method inactive for a given number of milliseconds.
 165  184    // If it is, we would remove it from the queue (see select_task()).
 166  185    inline bool is_stale(jlong t, jlong timeout, methodOop m);
 167  186    // Compute the weight of the method for the compilation scheduling
 168  187    inline double weight(methodOop method);
 169  188    // Apply heuristics and return true if x should be compiled before y
 170  189    inline bool compare_methods(methodOop x, methodOop y);
 171  190    // Compute event rate for a given method. The rate is the number of event (invocations + backedges)
 172  191    // per millisecond.
 173  192    inline void update_rate(jlong t, methodOop m);
 174  193    // Compute threshold scaling coefficient
 175  194    inline double threshold_scale(CompLevel level, int feedback_k);
 176  195    // If a method is old enough and is still in the interpreter we would want to
 177  196    // start profiling without waiting for the compiled method to arrive. This function
 178  197    // determines whether we should do that.
 179  198    inline bool should_create_mdo(methodOop method, CompLevel cur_level);
 180  199    // Create MDO if necessary.
 181  200    void create_mdo(methodHandle mh, TRAPS);
 182  201    // Is method profiled enough?
 183  202    bool is_method_profiled(methodOop method);
 184  203  
 185  204  protected:
 186  205    void print_specific(EventType type, methodHandle mh, methodHandle imh, int bci, CompLevel level);
 187  206  
 188  207    void set_start_time(jlong t) { _start_time = t;    }
 189  208    jlong start_time() const     { return _start_time; }
 190  209  
 191  210    // Submit a given method for compilation (and update the rate).
 192  211    virtual void submit_compile(methodHandle mh, int bci, CompLevel level, TRAPS);
 193  212    // event() from SimpleThresholdPolicy would call these.
 194  213    virtual void method_invocation_event(methodHandle method, methodHandle inlinee,
 195  214                                         CompLevel level, TRAPS);
 196  215    virtual void method_back_branch_event(methodHandle method, methodHandle inlinee,
 197  216                                          int bci, CompLevel level, TRAPS);
 198  217  public:
 199  218    AdvancedThresholdPolicy() : _start_time(0) { }
 200  219    // Select task is called by CompileBroker. We should return a task or NULL.
 201  220    virtual CompileTask* select_task(CompileQueue* compile_queue);
 202  221    virtual void initialize();
 203  222  };
 204  223  
 205  224  #endif // TIERED
 206  225  
 207  226  #endif // SHARE_VM_RUNTIME_ADVANCEDTHRESHOLDPOLICY_HPP

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX