-
Notifications
You must be signed in to change notification settings - Fork 1.4k
/
DFGBasicBlock.h
282 lines (235 loc) · 9.6 KB
/
DFGBasicBlock.h
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
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
/*
* Copyright (C) 2011, 2013-2016 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.
*/
#pragma once
#if ENABLE(DFG_JIT)
#include "DFGAbstractValue.h"
#include "DFGAvailabilityMap.h"
#include "DFGBranchDirection.h"
#include "DFGNode.h"
#include "DFGNodeAbstractValuePair.h"
#include "DFGStructureClobberState.h"
#include "Operands.h"
#include <wtf/Vector.h>
namespace JSC { namespace DFG {
class Graph;
class InsertionSet;
typedef Vector<BasicBlock*, 2> PredecessorList;
typedef Vector<Node*, 8> BlockNodeList;
DECLARE_ALLOCATOR_WITH_HEAP_IDENTIFIER(BasicBlock);
struct BasicBlock : RefCounted<BasicBlock> {
WTF_MAKE_STRUCT_FAST_ALLOCATED_WITH_HEAP_IDENTIFIER(BasicBlock);
BasicBlock(
BytecodeIndex bytecodeBegin, unsigned numArguments, unsigned numLocals, unsigned numTmps,
float executionCount);
~BasicBlock();
void ensureLocals(unsigned newNumLocals);
void ensureTmps(unsigned newNumTmps);
size_t size() const { return m_nodes.size(); }
bool isEmpty() const { return !size(); }
Node*& at(size_t i) { return m_nodes[i]; }
Node* at(size_t i) const { return m_nodes[i]; }
Node* tryAt(size_t i) const
{
if (i >= size())
return nullptr;
return at(i);
}
Node*& operator[](size_t i) { return at(i); }
Node* operator[](size_t i) const { return at(i); }
Node* last() const
{
RELEASE_ASSERT(!!size());
return at(size() - 1);
}
// Use this to find both the index of the terminal and the terminal itself in one go. May
// return a clear NodeAndIndex if the basic block currently lacks a terminal. That may happen
// in the middle of IR transformations within a phase but should never be the case in between
// phases.
//
// The reason why this is more than just "at(size() - 1)" is that we may place non-terminal
// liveness marking instructions after the terminal. This is supposed to happen infrequently
// but some basic blocks - most notably return blocks - will have liveness markers for all of
// the flushed variables right after the return.
//
// It turns out that doing this linear search is basically perf-neutral, so long as we force
// the method to be inlined. Hence the ALWAYS_INLINE.
ALWAYS_INLINE NodeAndIndex findTerminal() const
{
size_t i = size();
while (i--) {
Node* node = at(i);
if (node->isTerminal())
return NodeAndIndex(node, i);
switch (node->op()) {
// The bitter end can contain Phantoms and the like. There will probably only be one or two nodes after the terminal. They are all no-ops and will not have any checked children.
case Check: // This is here because it's our universal no-op.
case CheckVarargs:
case Phantom:
case PhantomLocal:
case Flush:
break;
default:
return NodeAndIndex();
}
}
return NodeAndIndex();
}
ALWAYS_INLINE Node* terminal() const
{
return findTerminal().node;
}
void resize(size_t size) { m_nodes.resize(size); }
void grow(size_t size) { m_nodes.grow(size); }
void append(Node* node) { m_nodes.append(node); }
void insertBeforeTerminal(Node* node)
{
NodeAndIndex result = findTerminal();
if (!result)
append(node);
else
m_nodes.insert(result.index, node);
}
void replaceTerminal(Graph&, Node*);
size_t numNodes() const { return phis.size() + size(); }
Node* node(size_t i) const
{
if (i < phis.size())
return phis[i];
return at(i - phis.size());
}
bool isPhiIndex(size_t i) const { return i < phis.size(); }
bool isInPhis(Node* node) const;
bool isInBlock(Node* myNode) const;
BlockNodeList::iterator begin() { return m_nodes.begin(); }
BlockNodeList::iterator end() { return m_nodes.end(); }
unsigned numSuccessors() { return terminal()->numSuccessors(); }
BasicBlock*& successor(unsigned index)
{
return terminal()->successor(index);
}
BasicBlock*& successorForCondition(bool condition)
{
return terminal()->successorForCondition(condition);
}
Node::SuccessorsIterable successors()
{
return terminal()->successors();
}
void removePredecessor(BasicBlock* block);
void replacePredecessor(BasicBlock* from, BasicBlock* to);
template<typename... Params>
Node* appendNode(Graph&, SpeculatedType, Params...);
template<typename... Params>
Node* appendNonTerminal(Graph&, SpeculatedType, Params...);
template<typename... Params>
Node* replaceTerminal(Graph&, SpeculatedType, Params...);
void dump(PrintStream& out) const;
void didLink()
{
#if ASSERT_ENABLED
isLinked = true;
#endif
}
// This value is used internally for block linking and OSR entry. It is mostly meaningless
// for other purposes due to inlining.
BytecodeIndex bytecodeBegin;
BlockIndex index;
StructureClobberState cfaStructureClobberStateAtHead;
StructureClobberState cfaStructureClobberStateAtTail;
BranchDirection cfaBranchDirection;
bool cfaHasVisited;
bool cfaShouldRevisit;
bool cfaThinksShouldTryConstantFolding { false };
bool cfaDidFinish;
bool intersectionOfCFAHasVisited;
bool isOSRTarget;
bool isCatchEntrypoint;
#if ASSERT_ENABLED
bool isLinked;
#endif
bool isReachable;
Vector<Node*> phis;
PredecessorList predecessors;
Operands<Node*> variablesAtHead;
Operands<Node*> variablesAtTail;
Operands<AbstractValue> valuesAtHead;
Operands<AbstractValue> valuesAtTail;
// The intersection of assumptions we have made previously at the head of this block. Note
// that under normal circumstances, each time we run the CFA, we will get strictly more precise
// results. But we don't actually require this to be the case. It's fine for the CFA to loosen
// up for any odd reason. It's fine when this happens, because anything that the CFA proves
// must be true from that point forward, except if some registered watchpoint fires, in which
// case the code won't ever run. So, the CFA proving something less precise later on is just an
// outcome of the CFA being imperfect; the more precise thing that it had proved earlier is no
// less true.
//
// But for the purpose of OSR entry, we need to make sure that we remember what assumptions we
// had used for optimizing any given basic block. That's what this is for.
//
// It's interesting that we could use this to make the CFA more precise: all future CFAs could
// filter their results with this thing to sort of maintain maximal precision. Because we
// expect CFA to usually be monotonically more precise each time we run it to fixpoint, this
// would not be a productive optimization: it would make setting up a basic block more
// expensive and would only benefit bizarre pathological cases.
Operands<AbstractValue> intersectionOfPastValuesAtHead;
float executionCount;
struct SSAData {
WTF_MAKE_FAST_ALLOCATED;
public:
void invalidate()
{
liveAtTail.clear();
liveAtHead.clear();
valuesAtHead.clear();
valuesAtTail.clear();
}
AvailabilityMap availabilityAtHead;
AvailabilityMap availabilityAtTail;
Vector<NodeFlowProjection> liveAtHead;
Vector<NodeFlowProjection> liveAtTail;
Vector<NodeAbstractValuePair> valuesAtHead;
Vector<NodeAbstractValuePair> valuesAtTail;
SSAData(BasicBlock*);
~SSAData();
};
std::unique_ptr<SSAData> ssa;
private:
friend class InsertionSet;
BlockNodeList m_nodes;
};
typedef Vector<BasicBlock*> BlockList;
static inline BytecodeIndex getBytecodeBeginForBlock(BasicBlock** basicBlock)
{
return (*basicBlock)->bytecodeBegin;
}
static inline BasicBlock* blockForBytecodeIndex(Vector<BasicBlock*>& linkingTargets, BytecodeIndex bytecodeBegin)
{
return *binarySearch<BasicBlock*, BytecodeIndex>(linkingTargets, linkingTargets.size(), bytecodeBegin, getBytecodeBeginForBlock);
}
} } // namespace JSC::DFG
namespace WTF {
void printInternal(PrintStream&, JSC::DFG::BasicBlock*);
}
#endif // ENABLE(DFG_JIT)