dfg/DFGStaticExecutionCountEstimationPhase.cpp

   1 /*
   2  * Copyright (C) 2014, 2015 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             Node* terminal = block->terminal();
  67             switch (terminal->op()) {
  68             case Branch: {
  69                 BranchData* data = terminal->branchData();
  70                 applyCounts(data->taken);
  71                 applyCounts(data->notTaken);
  72                 break;
  73             }
  74
  75             case Switch: {
  76                 SwitchData* data = terminal->switchData();
  77                 for (unsigned i = data->cases.size(); i--;)
  78                     applyCounts(data->cases[i].target);
  79                 applyCounts(data->fallThrough);
  80                 break;
  81             }
  82
  83             default:
  84                 break;
  85             }
  86         }
  87
  88         return true;
  89     }
  90
  91 private:
  92     void applyCounts(BranchTarget& target)
  93     {
  94         target.count = target.block->executionCount;
  95     }
  96 };
  97
  98 bool performStaticExecutionCountEstimation(Graph& graph)
  99 {
 100     SamplingRegion samplingRegion("DFG Static Execution Count Estimation");
 101     return runPhase<StaticExecutionCountEstimationPhase>(graph);
 102 }
 103
 104 } } // namespace JSC::DFG
 105
 106 #endif // ENABLE(DFG_JIT)
 107
 108