1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
/*
* Copyright (C) 2013, 2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "config.h"
#include "DFGLoopPreHeaderCreationPhase.h"
#if ENABLE(DFG_JIT)
#include "DFGBasicBlockInlines.h"
#include "DFGBlockInsertionSet.h"
#include "DFGDominators.h"
#include "DFGGraph.h"
#include "DFGNaturalLoops.h"
#include "DFGPhase.h"
#include "JSCInlines.h"
#include <wtf/HashMap.h>
namespace JSC { namespace DFG {
BasicBlock* createPreHeader(Graph& graph, BlockInsertionSet& insertionSet, BasicBlock* block)
{
// FIXME: If we run this utility on SSA IR, then we may end up with a bizarre arrangement of
// Upsilons and Phis, like:
//
// BB#1:
// Upsilon(@a, ^p)
// Jump(#3)
//
// BB#2:
// Upsilon(@b, ^p)
// Jump(#3)
//
// BB#3:
// Jump(#4)
//
// BB#4:
// p: Phi()
//
// Notice how the Upsilons are not in the predecessor of the Phi anymore. It's not clear if this
// would be bad. Probably not, but it's weird anyway. We should add a validation rule, and we
// should implement a Upsilon/Phi canonicalization that handles this by calling into the
// SSACalculator and treating the Upsilons as Defs and rebuilding the Phis from scratch.
//
// https://bugs.webkit.org/show_bug.cgi?id=148587
// Determine a good frequency for the pre-header. It's definitely not the frequency of the loop body.
// Instead, we use the max of the frequencies of the loop body's non-loop predecessors.
float frequency = 0;
for (BasicBlock* predecessor : block->predecessors) {
if (graph.m_dominators->dominates(block, predecessor))
continue;
frequency = std::max(frequency, predecessor->executionCount);
}
BasicBlock* preHeader = insertionSet.insertBefore(block, frequency);
// FIXME: It would be great if we put some effort into enabling exitOK at this origin, if it
// happens to be unset. It might not be set because the loop header (i.e. "block") has Phis in it.
// Phis have to have exitOK=false. There are a few ways to try to set exitOK:
//
// - Regenerate an exit origin by proving that we are at an exit origin boundary. If all of the
// predecessors' terminals have different exit origins than the exit origin of head of block,
// then we can leverage the assumption that exit origin boundaries can always exit. We could
// extend this further, and say that we will set exitOK even if a predecessor's terminal has the
// same exit origin, but so long it hadn't done anything that clobbers exit since the start of
// the origin.
//
// - Analyze the Phi's and MovHint's at the head of block. If prior to the ExitOK there are only
// Phi's and MovHint's, we could "roll them back" by proving that for each of the MovHints, the
// referenced Phi has a child that dominates the pre-header, and that child is the node that is
// OSR-available at the local being MovHinted.
//
// Note that there are some obviously wrong ways to try to set exitOK. For example, we cannot
// simply use the origin of our predecessors, since in bytecode that could be *any* kind of
// instruction. It may not even be a control flow construct, if we had lowered some non-control
// bytecode operation into DFG IR that has control flow. Hence, we really do need to try to use the
// origin of the head of the loop header.
//
// https://bugs.webkit.org/show_bug.cgi?id=148586
preHeader->appendNode(
graph, SpecNone, Jump, block->at(0)->origin, OpInfo(block));
for (unsigned predecessorIndex = 0; predecessorIndex < block->predecessors.size(); predecessorIndex++) {
BasicBlock* predecessor = block->predecessors[predecessorIndex];
if (graph.m_dominators->dominates(block, predecessor))
continue;
block->predecessors[predecessorIndex--] = block->predecessors.last();
block->predecessors.removeLast();
for (unsigned successorIndex = predecessor->numSuccessors(); successorIndex--;) {
BasicBlock*& successor = predecessor->successor(successorIndex);
if (successor != block)
continue;
successor = preHeader;
preHeader->predecessors.append(predecessor);
}
}
block->predecessors.append(preHeader);
return preHeader;
}
class LoopPreHeaderCreationPhase : public Phase {
public:
LoopPreHeaderCreationPhase(Graph& graph)
: Phase(graph, "loop pre-header creation")
, m_insertionSet(graph)
{
}
bool run()
{
m_graph.ensureDominators();
m_graph.ensureNaturalLoops();
for (unsigned loopIndex = m_graph.m_naturalLoops->numLoops(); loopIndex--;) {
const NaturalLoop& loop = m_graph.m_naturalLoops->loop(loopIndex);
BasicBlock* existingPreHeader = 0;
bool needsNewPreHeader = false;
for (unsigned predecessorIndex = loop.header()->predecessors.size(); predecessorIndex--;) {
BasicBlock* predecessor = loop.header()->predecessors[predecessorIndex];
if (m_graph.m_dominators->dominates(loop.header(), predecessor))
continue;
if (!existingPreHeader) {
existingPreHeader = predecessor;
continue;
}
// We won't have duplicate entries in the predecessors list.
DFG_ASSERT(m_graph, nullptr, existingPreHeader != predecessor);
needsNewPreHeader = true;
break;
}
// This phase should only be run on a DFG where unreachable blocks have been pruned.
// We also don't allow loops back to root. This means that every loop header has got
// to have a pre-header.
DFG_ASSERT(m_graph, nullptr, existingPreHeader);
// We are looking at the predecessors of a loop header. A loop header has to have
// some predecessor other than the pre-header. We must have broken critical edges
// because that is the DFG SSA convention. Therefore, each predecessor of the loop
// header must have only one successor.
DFG_ASSERT(m_graph, nullptr, existingPreHeader->terminal()->op() == Jump);
// A pre-header is most useful if it's possible to exit from its terminal. Hence
// if the terminal of the existing pre-header doesn't allow for exit, but the first
// origin of the loop header does, then we should create a new pre-header.
if (!needsNewPreHeader && loop.header()->at(0)->origin.exitOK
&& !existingPreHeader->terminal()->origin.exitOK)
needsNewPreHeader = true;
if (!needsNewPreHeader)
continue;
createPreHeader(m_graph, m_insertionSet, loop.header());
}
return m_insertionSet.execute();
}
BlockInsertionSet m_insertionSet;
};
bool performLoopPreHeaderCreation(Graph& graph)
{
SamplingRegion samplingRegion("DFG Loop Pre-Header Creation Phase");
return runPhase<LoopPreHeaderCreationPhase>(graph);
}
} } // namespace JSC::DFG
#endif // ENABLE(DFG_JIT)
|
