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 "DFGNaturalLoops.h"
34#include "DFGPhase.h"
35#include "JSCInlines.h"
36
37namespace JSC { namespace DFG {
38
39class StaticExecutionCountEstimationPhase : public Phase {
40public:
41 StaticExecutionCountEstimationPhase(Graph& graph)
42 : Phase(graph, "static execution count estimation")
43 {
44 }
45
46 bool run()
47 {
48 m_graph.ensureCPSNaturalLoops();
49
50 // Estimate basic block execution counts based on loop depth.
51 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
52 BasicBlock* block = m_graph.block(blockIndex);
53 if (!block)
54 continue;
55
56 block->executionCount = pow(10, m_graph.m_cpsNaturalLoops->loopDepth(block));
57 }
58
59 // Estimate branch weights based on execution counts. This isn't quite correct. It'll
60 // assume that each block's conditional successor only has that block as its
61 // predecessor.
62 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
63 BasicBlock* block = m_graph.block(blockIndex);
64 if (!block)
65 continue;
66
67 Node* terminal = block->terminal();
68 switch (terminal->op()) {
69 case Branch: {
70 BranchData* data = terminal->branchData();
71 applyCounts(data->taken);
72 applyCounts(data->notTaken);
73 break;
74 }
75
76 case Switch: {
77 SwitchData* data = terminal->switchData();
78 for (unsigned i = data->cases.size(); i--;)
79 applyCounts(data->cases[i].target);
80 applyCounts(data->fallThrough);
81 break;
82 }
83
84 case EntrySwitch: {
85 DFG_CRASH(m_graph, terminal, "Unexpected EntrySwitch in CPS form.");
86 break;
87 }
88
89 default:
90 break;
91 }
92 }
93
94 return true;
95 }
96
97private:
98 void applyCounts(BranchTarget& target)
99 {
100 target.count = target.block->executionCount;
101 }
102};
103
104bool performStaticExecutionCountEstimation(Graph& graph)
105{
106 return runPhase<StaticExecutionCountEstimationPhase>(graph);
107}
108
109} } // namespace JSC::DFG
110
111#endif // ENABLE(DFG_JIT)
112
113
114