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