fourthTier: DFG should do a high-level LICM before going to FTL
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGBasicBlock.h
1 /*
2  * Copyright (C) 2011, 2013 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 "DFGBranchDirection.h"
33 #include "DFGNode.h"
34 #include "DFGVariadicFunction.h"
35 #include "Operands.h"
36 #include <wtf/HashMap.h>
37 #include <wtf/HashSet.h>
38 #include <wtf/OwnPtr.h>
39 #include <wtf/Vector.h>
40
41 namespace JSC { namespace DFG {
42
43 class Graph;
44 class InsertionSet;
45
46 typedef Vector<BasicBlock*, 2> PredecessorList;
47
48 struct BasicBlock : RefCounted<BasicBlock> {
49     BasicBlock(unsigned bytecodeBegin, unsigned numArguments, unsigned numLocals);
50     ~BasicBlock();
51     
52     void ensureLocals(unsigned newNumLocals);
53     
54     size_t size() const { return m_nodes.size(); }
55     bool isEmpty() const { return !size(); }
56     Node*& at(size_t i) { return m_nodes[i]; }
57     Node* at(size_t i) const { return m_nodes[i]; }
58     Node*& operator[](size_t i) { return at(i); }
59     Node* operator[](size_t i) const { return at(i); }
60     Node* last() const { return at(size() - 1); }
61     void resize(size_t size) { m_nodes.resize(size); }
62     void grow(size_t size) { m_nodes.grow(size); }
63     
64     void append(Node* node) { m_nodes.append(node); }
65     void insertBeforeLast(Node* node)
66     {
67         append(last());
68         at(size() - 2) = node;
69     }
70     
71     size_t numNodes() const { return phis.size() + size(); }
72     Node* node(size_t i) const
73     {
74         if (i < phis.size())
75             return phis[i];
76         return at(i - phis.size());
77     }
78     bool isPhiIndex(size_t i) const { return i < phis.size(); }
79     
80     bool isInPhis(Node* node) const;
81     bool isInBlock(Node* myNode) const;
82     
83     unsigned numSuccessors() { return last()->numSuccessors(); }
84     
85     BasicBlock*& successor(unsigned index)
86     {
87         return last()->successor(index);
88     }
89     BasicBlock*& successorForCondition(bool condition)
90     {
91         return last()->successorForCondition(condition);
92     }
93     
94     void removePredecessor(BasicBlock* block);
95     void replacePredecessor(BasicBlock* from, BasicBlock* to);
96
97 #define DFG_DEFINE_APPEND_NODE(templatePre, templatePost, typeParams, valueParamsComma, valueParams, valueArgs) \
98     templatePre typeParams templatePost Node* appendNode(Graph&, SpeculatedType valueParamsComma valueParams);
99     DFG_VARIADIC_TEMPLATE_FUNCTION(DFG_DEFINE_APPEND_NODE)
100 #undef DFG_DEFINE_APPEND_NODE
101     
102 #define DFG_DEFINE_APPEND_NODE(templatePre, templatePost, typeParams, valueParamsComma, valueParams, valueArgs) \
103     templatePre typeParams templatePost Node* appendNonTerminal(Graph&, SpeculatedType valueParamsComma valueParams);
104     DFG_VARIADIC_TEMPLATE_FUNCTION(DFG_DEFINE_APPEND_NODE)
105 #undef DFG_DEFINE_APPEND_NODE
106     
107     void dump(PrintStream& out) const;
108     
109     // This value is used internally for block linking and OSR entry. It is mostly meaningless
110     // for other purposes due to inlining.
111     unsigned bytecodeBegin;
112     
113     BlockIndex index;
114     
115     bool isOSRTarget;
116     bool cfaHasVisited;
117     bool cfaShouldRevisit;
118     bool cfaFoundConstants;
119     bool cfaDidFinish;
120     BranchDirection cfaBranchDirection;
121 #if !ASSERT_DISABLED
122     bool isLinked;
123 #endif
124     bool isReachable;
125     
126     Vector<Node*> phis;
127     PredecessorList predecessors;
128     
129     Operands<Node*, NodePointerTraits> variablesAtHead;
130     Operands<Node*, NodePointerTraits> variablesAtTail;
131     
132     Operands<AbstractValue> valuesAtHead;
133     Operands<AbstractValue> valuesAtTail;
134     
135     // These fields are reserved for NaturalLoops.
136     static const unsigned numberOfInnerMostLoopIndices = 2;
137     unsigned innerMostLoopIndices[numberOfInnerMostLoopIndices];
138
139     struct SSAData {
140         Operands<FlushFormat> flushFormatAtHead;
141         Operands<FlushFormat> flushFormatAtTail;
142         Operands<Node*> availabilityAtHead;
143         Operands<Node*> availabilityAtTail;
144         HashSet<Node*> liveAtHead;
145         HashSet<Node*> liveAtTail;
146         HashMap<Node*, AbstractValue> valuesAtHead;
147         HashMap<Node*, AbstractValue> valuesAtTail;
148         
149         SSAData(BasicBlock*);
150         ~SSAData();
151     };
152     OwnPtr<SSAData> ssa;
153
154 private:
155     friend class InsertionSet;
156     Vector<Node*, 8> m_nodes;
157 };
158
159 struct UnlinkedBlock {
160     BasicBlock* m_block;
161     bool m_needsNormalLinking;
162     bool m_needsEarlyReturnLinking;
163     
164     UnlinkedBlock() { }
165     
166     explicit UnlinkedBlock(BasicBlock* block)
167         : m_block(block)
168         , m_needsNormalLinking(true)
169         , m_needsEarlyReturnLinking(false)
170     {
171     }
172 };
173     
174 static inline unsigned getBytecodeBeginForBlock(BasicBlock** basicBlock)
175 {
176     return (*basicBlock)->bytecodeBegin;
177 }
178
179 static inline BasicBlock* blockForBytecodeOffset(Vector<BasicBlock*>& linkingTargets, unsigned bytecodeBegin)
180 {
181     return *binarySearch<BasicBlock*, unsigned>(linkingTargets, linkingTargets.size(), bytecodeBegin, getBytecodeBeginForBlock);
182 }
183
184 } } // namespace JSC::DFG
185
186 #endif // ENABLE(DFG_JIT)
187
188 #endif // DFGBasicBlock_h
189