dfg/DFGStaticExecutionCountEstimationPhase.cpp

   1 /*
   2  * Copyright (C) 2014 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "DFGStaticExecutionCountEstimationPhase.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGBasicBlockInlines.h"
  32 #include "DFGGraph.h"
  33 #include "DFGPhase.h"
  34 #include "JSCInlines.h"
  35
  36 namespace JSC { namespace DFG {
  37
  38 class StaticExecutionCountEstimationPhase : public Phase {
  39 public:
  40     StaticExecutionCountEstimationPhase(Graph& graph)
  41         : Phase(graph, "static execution count estimation")
  42     {
  43     }
  44
  45     bool run()
  46     {
  47         m_graph.m_naturalLoops.computeIfNecessary(m_graph);
  48
  49         // Estimate basic block execution counts based on loop depth.
  50         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
  51             BasicBlock* block = m_graph.block(blockIndex);
  52             if (!block)
  53                 continue;
  54
  55             block->executionCount = pow(10, m_graph.m_naturalLoops.loopDepth(block));
  56         }
  57
  58         // Estimate branch weights based on execution counts. This isn't quite correct. It'll
  59         // assume that each block's conditional successor only has that block as its
  60         // predecessor.
  61         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
  62             BasicBlock* block = m_graph.block(blockIndex);
  63             if (!block)
  64                 continue;
  65
  66             switch (block->last()->op()) {
  67             case Branch: {
  68                 BranchData* data = block->last()->branchData();
  69                 applyCounts(data->taken);
  70                 applyCounts(data->notTaken);
  71                 break;
  72             }
  73
  74             case Switch: {
  75                 SwitchData* data = block->last()->switchData();
  76                 for (unsigned i = data->cases.size(); i--;)
  77                     applyCounts(data->cases[i].target);
  78                 applyCounts(data->fallThrough);
  79                 break;
  80             }
  81
  82             default:
  83                 break;
  84             }
  85         }
  86
  87         return true;
  88     }
  89
  90 private:
  91     void applyCounts(BranchTarget& target)
  92     {
  93         target.count = target.block->executionCount;
  94     }
  95 };
  96
  97 bool performStaticExecutionCountEstimation(Graph& graph)
  98 {
  99     SamplingRegion samplingRegion("DFG Static Execution Count Estimation");
 100     return runPhase<StaticExecutionCountEstimationPhase>(graph);
 101 }
 102
 103 } } // namespace JSC::DFG
 104
 105 #endif // ENABLE(DFG_JIT)
 106
 107