8fc33c68bd6bb8c17a6bfa4099554b85ece158ec
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGBasicBlock.h
1 /*
2  * Copyright (C) 2011, 2013-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 #ifndef DFGBasicBlock_h
27 #define DFGBasicBlock_h
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGAbstractValue.h"
32 #include "DFGAvailability.h"
33 #include "DFGAvailabilityMap.h"
34 #include "DFGBranchDirection.h"
35 #include "DFGFlushedAt.h"
36 #include "DFGNode.h"
37 #include "DFGNodeOrigin.h"
38 #include "DFGStructureClobberState.h"
39 #include "Operands.h"
40 #include <wtf/HashMap.h>
41 #include <wtf/HashSet.h>
42 #include <wtf/Vector.h>
43
44 namespace JSC { namespace DFG {
45
46 class Graph;
47 class InsertionSet;
48
49 typedef Vector<BasicBlock*, 2> PredecessorList;
50 typedef Vector<Node*, 8> BlockNodeList;
51
52 struct BasicBlock : RefCounted<BasicBlock> {
53     BasicBlock(
54         unsigned bytecodeBegin, unsigned numArguments, unsigned numLocals,
55         float executionCount);
56     ~BasicBlock();
57     
58     void ensureLocals(unsigned newNumLocals);
59     
60     size_t size() const { return m_nodes.size(); }
61     bool isEmpty() const { return !size(); }
62     Node*& at(size_t i) { return m_nodes[i]; }
63     Node* at(size_t i) const { return m_nodes[i]; }
64     Node*& operator[](size_t i) { return at(i); }
65     Node* operator[](size_t i) const { return at(i); }
66     
67     // Use this to find both the index of the terminal and the terminal itself in one go. May
68     // return a clear NodeAndIndex if the basic block currently lacks a terminal. That may happen
69     // in the middle of IR transformations within a phase but should never be the case in between
70     // phases.
71     //
72     // The reason why this is more than just "at(size() - 1)" is that we may place non-terminal
73     // liveness marking instructions after the terminal. This is supposed to happen infrequently
74     // but some basic blocks - most notably return blocks - will have liveness markers for all of
75     // the flushed variables right after the return.
76     //
77     // It turns out that doing this linear search is basically perf-neutral, so long as we force
78     // the method to be inlined. Hence the ALWAYS_INLINE.
79     ALWAYS_INLINE NodeAndIndex findTerminal() const
80     {
81         size_t i = size();
82         while (i--) {
83             Node* node = at(i);
84             switch (node->op()) {
85             case Jump:
86             case Branch:
87             case Switch:
88             case Return:
89             case Unreachable:
90                 return NodeAndIndex(node, i);
91             // The bitter end can contain Phantoms and the like. There will probably only be one or two nodes after the terminal.
92             case Phantom:
93             case PhantomLocal:
94             case Flush:
95                 break;
96             default:
97                 return NodeAndIndex();
98             }
99         }
100         return NodeAndIndex();
101     }
102     
103     ALWAYS_INLINE Node* terminal() const
104     {
105         return findTerminal().node;
106     }
107     
108     void resize(size_t size) { m_nodes.resize(size); }
109     void grow(size_t size) { m_nodes.grow(size); }
110     
111     void append(Node* node) { m_nodes.append(node); }
112     void insertBeforeTerminal(Node* node)
113     {
114         NodeAndIndex result = findTerminal();
115         if (!result)
116             append(node);
117         else
118             m_nodes.insert(result.index, node);
119     }
120     
121     void replaceTerminal(Node*);
122     
123     size_t numNodes() const { return phis.size() + size(); }
124     Node* node(size_t i) const
125     {
126         if (i < phis.size())
127             return phis[i];
128         return at(i - phis.size());
129     }
130     bool isPhiIndex(size_t i) const { return i < phis.size(); }
131     
132     bool isInPhis(Node* node) const;
133     bool isInBlock(Node* myNode) const;
134     
135     BlockNodeList::iterator begin() { return m_nodes.begin(); }
136     BlockNodeList::iterator end() { return m_nodes.end(); }
137     
138     Node* firstOriginNode();
139     NodeOrigin firstOrigin();
140     
141     unsigned numSuccessors() { return terminal()->numSuccessors(); }
142     
143     BasicBlock*& successor(unsigned index)
144     {
145         return terminal()->successor(index);
146     }
147     BasicBlock*& successorForCondition(bool condition)
148     {
149         return terminal()->successorForCondition(condition);
150     }
151
152     Node::SuccessorsIterable successors()
153     {
154         return terminal()->successors();
155     }
156     
157     void removePredecessor(BasicBlock* block);
158     void replacePredecessor(BasicBlock* from, BasicBlock* to);
159
160     template<typename... Params>
161     Node* appendNode(Graph&, SpeculatedType, Params...);
162     
163     template<typename... Params>
164     Node* appendNonTerminal(Graph&, SpeculatedType, Params...);
165     
166     template<typename... Params>
167     Node* replaceTerminal(Graph&, SpeculatedType, Params...);
168     
169     void dump(PrintStream& out) const;
170     
171     void didLink()
172     {
173 #if !ASSERT_DISABLED
174         isLinked = true;
175 #endif
176     }
177     
178     // This value is used internally for block linking and OSR entry. It is mostly meaningless
179     // for other purposes due to inlining.
180     unsigned bytecodeBegin;
181     
182     BlockIndex index;
183     
184     bool isOSRTarget;
185     bool cfaHasVisited;
186     bool cfaShouldRevisit;
187     bool cfaFoundConstants;
188     bool cfaDidFinish;
189     StructureClobberState cfaStructureClobberStateAtHead;
190     StructureClobberState cfaStructureClobberStateAtTail;
191     BranchDirection cfaBranchDirection;
192 #if !ASSERT_DISABLED
193     bool isLinked;
194 #endif
195     bool isReachable;
196     
197     Vector<Node*> phis;
198     PredecessorList predecessors;
199     
200     Operands<Node*, NodePointerTraits> variablesAtHead;
201     Operands<Node*, NodePointerTraits> variablesAtTail;
202     
203     Operands<AbstractValue> valuesAtHead;
204     Operands<AbstractValue> valuesAtTail;
205     
206     // The intersection of assumptions we have made previously at the head of this block. Note
207     // that under normal circumstances, each time we run the CFA, we will get strictly more precise
208     // results. But we don't actually require this to be the case. It's fine for the CFA to loosen
209     // up for any odd reason. It's fine when this happens, because anything that the CFA proves
210     // must be true from that point forward, except if some registered watchpoint fires, in which
211     // case the code won't ever run. So, the CFA proving something less precise later on is just an
212     // outcome of the CFA being imperfect; the more precise thing that it had proved earlier is no
213     // less true.
214     //
215     // But for the purpose of OSR entry, we need to make sure that we remember what assumptions we
216     // had used for optimizing any given basic block. That's what this is for.
217     //
218     // It's interesting that we could use this to make the CFA more precise: all future CFAs could
219     // filter their results with this thing to sort of maintain maximal precision. Because we
220     // expect CFA to usually be monotonically more precise each time we run it to fixpoint, this
221     // would not be a productive optimization: it would make setting up a basic block more
222     // expensive and would only benefit bizarre pathological cases.
223     Operands<AbstractValue> intersectionOfPastValuesAtHead;
224     bool intersectionOfCFAHasVisited;
225     
226     float executionCount;
227     
228     // These fields are reserved for NaturalLoops.
229     static const unsigned numberOfInnerMostLoopIndices = 2;
230     unsigned innerMostLoopIndices[numberOfInnerMostLoopIndices];
231
232     struct SSAData {
233         AvailabilityMap availabilityAtHead;
234         AvailabilityMap availabilityAtTail;
235         
236         HashSet<Node*> liveAtHead;
237         HashSet<Node*> liveAtTail;
238         HashMap<Node*, AbstractValue> valuesAtHead;
239         HashMap<Node*, AbstractValue> valuesAtTail;
240         
241         SSAData(BasicBlock*);
242         ~SSAData();
243     };
244     std::unique_ptr<SSAData> ssa;
245     
246 private:
247     friend class InsertionSet;
248     BlockNodeList m_nodes;
249 };
250
251 typedef Vector<BasicBlock*, 5> BlockList;
252
253 struct UnlinkedBlock {
254     BasicBlock* m_block;
255     bool m_needsNormalLinking;
256     bool m_needsEarlyReturnLinking;
257     
258     UnlinkedBlock() { }
259     
260     explicit UnlinkedBlock(BasicBlock* block)
261         : m_block(block)
262         , m_needsNormalLinking(true)
263         , m_needsEarlyReturnLinking(false)
264     {
265     }
266 };
267     
268 static inline unsigned getBytecodeBeginForBlock(BasicBlock** basicBlock)
269 {
270     return (*basicBlock)->bytecodeBegin;
271 }
272
273 static inline BasicBlock* blockForBytecodeOffset(Vector<BasicBlock*>& linkingTargets, unsigned bytecodeBegin)
274 {
275     return *binarySearch<BasicBlock*, unsigned>(linkingTargets, linkingTargets.size(), bytecodeBegin, getBytecodeBeginForBlock);
276 }
277
278 } } // namespace JSC::DFG
279
280 #endif // ENABLE(DFG_JIT)
281
282 #endif // DFGBasicBlock_h
283