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