dfg/DFGBasicBlock.h

   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
  42 namespace JSC { namespace DFG {
  43
  44 class Graph;
  45 class InsertionSet;
  46
  47 typedef Vector<BasicBlock*, 2> PredecessorList;
  48
  49 struct 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
 153 private:
 154     friend class InsertionSet;
 155     Vector<Node*, 8> m_nodes;
 156 };
 157
 158 struct 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
 173 static inline unsigned getBytecodeBeginForBlock(BasicBlock** basicBlock)
 174 {
 175     return (*basicBlock)->bytecodeBegin;
 176 }
 177
 178 static 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