VarargsForwardingPhase should use bytecode liveness in addition to other uses to...
[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* tryAt(size_t i) const
65     {
66         if (i >= size())
67             return nullptr;
68         return at(i);
69     }
70     Node*& operator[](size_t i) { return at(i); }
71     Node* operator[](size_t i) const { return at(i); }
72     
73     // Use this to find both the index of the terminal and the terminal itself in one go. May
74     // return a clear NodeAndIndex if the basic block currently lacks a terminal. That may happen
75     // in the middle of IR transformations within a phase but should never be the case in between
76     // phases.
77     //
78     // The reason why this is more than just "at(size() - 1)" is that we may place non-terminal
79     // liveness marking instructions after the terminal. This is supposed to happen infrequently
80     // but some basic blocks - most notably return blocks - will have liveness markers for all of
81     // the flushed variables right after the return.
82     //
83     // It turns out that doing this linear search is basically perf-neutral, so long as we force
84     // the method to be inlined. Hence the ALWAYS_INLINE.
85     ALWAYS_INLINE NodeAndIndex findTerminal() const
86     {
87         size_t i = size();
88         while (i--) {
89             Node* node = at(i);
90             switch (node->op()) {
91             case Jump:
92             case Branch:
93             case Switch:
94             case Return:
95             case Unreachable:
96                 return NodeAndIndex(node, i);
97             // The bitter end can contain Phantoms and the like. There will probably only be one or two nodes after the terminal.
98             case Phantom:
99             case PhantomLocal:
100             case Flush:
101                 break;
102             default:
103                 return NodeAndIndex();
104             }
105         }
106         return NodeAndIndex();
107     }
108     
109     ALWAYS_INLINE Node* terminal() const
110     {
111         return findTerminal().node;
112     }
113     
114     void resize(size_t size) { m_nodes.resize(size); }
115     void grow(size_t size) { m_nodes.grow(size); }
116     
117     void append(Node* node) { m_nodes.append(node); }
118     void insertBeforeTerminal(Node* node)
119     {
120         NodeAndIndex result = findTerminal();
121         if (!result)
122             append(node);
123         else
124             m_nodes.insert(result.index, node);
125     }
126     
127     void replaceTerminal(Node*);
128     
129     size_t numNodes() const { return phis.size() + size(); }
130     Node* node(size_t i) const
131     {
132         if (i < phis.size())
133             return phis[i];
134         return at(i - phis.size());
135     }
136     bool isPhiIndex(size_t i) const { return i < phis.size(); }
137     
138     bool isInPhis(Node* node) const;
139     bool isInBlock(Node* myNode) const;
140     
141     BlockNodeList::iterator begin() { return m_nodes.begin(); }
142     BlockNodeList::iterator end() { return m_nodes.end(); }
143     
144     Node* firstOriginNode();
145     NodeOrigin firstOrigin();
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*, NodePointerTraits> variablesAtHead;
207     Operands<Node*, NodePointerTraits> 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         AvailabilityMap availabilityAtHead;
240         AvailabilityMap availabilityAtTail;
241         
242         HashSet<Node*> liveAtHead;
243         HashSet<Node*> liveAtTail;
244         HashMap<Node*, AbstractValue> valuesAtHead;
245         HashMap<Node*, AbstractValue> valuesAtTail;
246         
247         SSAData(BasicBlock*);
248         ~SSAData();
249     };
250     std::unique_ptr<SSAData> ssa;
251     
252 private:
253     friend class InsertionSet;
254     BlockNodeList m_nodes;
255 };
256
257 typedef Vector<BasicBlock*, 5> BlockList;
258
259 struct UnlinkedBlock {
260     BasicBlock* m_block;
261     bool m_needsNormalLinking;
262     bool m_needsEarlyReturnLinking;
263     
264     UnlinkedBlock() { }
265     
266     explicit UnlinkedBlock(BasicBlock* block)
267         : m_block(block)
268         , m_needsNormalLinking(true)
269         , m_needsEarlyReturnLinking(false)
270     {
271     }
272 };
273     
274 static inline unsigned getBytecodeBeginForBlock(BasicBlock** basicBlock)
275 {
276     return (*basicBlock)->bytecodeBegin;
277 }
278
279 static inline BasicBlock* blockForBytecodeOffset(Vector<BasicBlock*>& linkingTargets, unsigned bytecodeBegin)
280 {
281     return *binarySearch<BasicBlock*, unsigned>(linkingTargets, linkingTargets.size(), bytecodeBegin, getBytecodeBeginForBlock);
282 }
283
284 } } // namespace JSC::DFG
285
286 #endif // ENABLE(DFG_JIT)
287
288 #endif // DFGBasicBlock_h
289