dfg/DFGAbstractInterpreter.h

   1 /*
   2  * Copyright (C) 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 DFGAbstractInterpreter_h
  27 #define DFGAbstractInterpreter_h
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGAbstractValue.h"
  32 #include "DFGBranchDirection.h"
  33 #include "DFGGraph.h"
  34 #include "DFGNode.h"
  35 #include "DFGPhiChildren.h"
  36
  37 namespace JSC { namespace DFG {
  38
  39 template<typename AbstractStateType>
  40 class AbstractInterpreter {
  41 public:
  42     AbstractInterpreter(Graph&, AbstractStateType&);
  43     ~AbstractInterpreter();
  44
  45     AbstractValue& forNode(Node* node)
  46     {
  47         return m_state.forNode(node);
  48     }
  49
  50     AbstractValue& forNode(Edge edge)
  51     {
  52         return forNode(edge.node());
  53     }
  54
  55     Operands<AbstractValue>& variables()
  56     {
  57         return m_state.variables();
  58     }
  59
  60     bool needsTypeCheck(Node* node, SpeculatedType typesPassedThrough)
  61     {
  62         return !forNode(node).isType(typesPassedThrough);
  63     }
  64
  65     bool needsTypeCheck(Edge edge, SpeculatedType typesPassedThrough)
  66     {
  67         return needsTypeCheck(edge.node(), typesPassedThrough);
  68     }
  69
  70     bool needsTypeCheck(Edge edge)
  71     {
  72         return needsTypeCheck(edge, typeFilterFor(edge.useKind()));
  73     }
  74
  75     // Abstractly executes the given node. The new abstract state is stored into an
  76     // abstract stack stored in *this. Loads of local variables (that span
  77     // basic blocks) interrogate the basic block's notion of the state at the head.
  78     // Stores to local variables are handled in endBasicBlock(). This returns true
  79     // if execution should continue past this node. Notably, it will return true
  80     // for block terminals, so long as those terminals are not Return or Unreachable.
  81     //
  82     // This is guaranteed to be equivalent to doing:
  83     //
  84     // state.startExecuting()
  85     // state.executeEdges(index);
  86     // result = state.executeEffects(index);
  87     bool execute(unsigned indexInBlock);
  88     bool execute(Node*);
  89
  90     // Indicate the start of execution of a node. It resets any state in the node
  91     // that is progressively built up by executeEdges() and executeEffects().
  92     void startExecuting();
  93
  94     // Abstractly execute the edges of the given node. This runs filterEdgeByUse()
  95     // on all edges of the node. You can skip this step, if you have already used
  96     // filterEdgeByUse() (or some equivalent) on each edge.
  97     void executeEdges(Node*);
  98     void executeEdges(unsigned indexInBlock);
  99
 100     ALWAYS_INLINE void filterEdgeByUse(Edge& edge)
 101     {
 102         ASSERT(mayHaveTypeCheck(edge.useKind()) || !needsTypeCheck(edge));
 103         filterByType(edge, typeFilterFor(edge.useKind()));
 104     }
 105     ALWAYS_INLINE void filterEdgeByUse(Node*, Edge& edge)
 106     {
 107         filterEdgeByUse(edge);
 108     }
 109
 110     // Abstractly execute the effects of the given node. This changes the abstract
 111     // state assuming that edges have already been filtered.
 112     bool executeEffects(unsigned indexInBlock);
 113     bool executeEffects(unsigned clobberLimit, Node*);
 114
 115     void dump(PrintStream& out) const;
 116     void dump(PrintStream& out);
 117
 118     template<typename T>
 119     FiltrationResult filter(T node, const StructureSet& set)
 120     {
 121         return filter(forNode(node), set);
 122     }
 123
 124     template<typename T>
 125     FiltrationResult filterArrayModes(T node, ArrayModes arrayModes)
 126     {
 127         return filterArrayModes(forNode(node), arrayModes);
 128     }
 129
 130     template<typename T>
 131     FiltrationResult filter(T node, SpeculatedType type)
 132     {
 133         return filter(forNode(node), type);
 134     }
 135
 136     template<typename T>
 137     FiltrationResult filterByValue(T node, FrozenValue value)
 138     {
 139         return filterByValue(forNode(node), value);
 140     }
 141
 142     FiltrationResult filter(AbstractValue&, const StructureSet&);
 143     FiltrationResult filterArrayModes(AbstractValue&, ArrayModes);
 144     FiltrationResult filter(AbstractValue&, SpeculatedType);
 145     FiltrationResult filterByValue(AbstractValue&, FrozenValue);
 146
 147     PhiChildren* phiChildren() { return m_phiChildren.get(); }
 148
 149 private:
 150     void clobberWorld(const CodeOrigin&, unsigned indexInBlock);
 151
 152     template<typename Functor>
 153     void forAllValues(unsigned indexInBlock, Functor&);
 154
 155     void clobberStructures(unsigned indexInBlock);
 156     void observeTransition(unsigned indexInBlock, Structure* from, Structure* to);
 157     void observeTransitions(unsigned indexInBlock, const TransitionVector&);
 158     void setDidClobber();
 159
 160     enum BooleanResult {
 161         UnknownBooleanResult,
 162         DefinitelyFalse,
 163         DefinitelyTrue
 164     };
 165     BooleanResult booleanResult(Node*, AbstractValue&);
 166
 167     void setBuiltInConstant(Node* node, FrozenValue value)
 168     {
 169         AbstractValue& abstractValue = forNode(node);
 170         abstractValue.set(m_graph, value, m_state.structureClobberState());
 171         abstractValue.fixTypeForRepresentation(m_graph, node);
 172     }
 173
 174     void setConstant(Node* node, FrozenValue value)
 175     {
 176         setBuiltInConstant(node, value);
 177         m_state.setFoundConstants(true);
 178     }
 179
 180     ALWAYS_INLINE void filterByType(Edge& edge, SpeculatedType type)
 181     {
 182         AbstractValue& value = forNode(edge);
 183         if (!value.isType(type))
 184             edge.setProofStatus(NeedsCheck);
 185         else
 186             edge.setProofStatus(IsProved);
 187
 188         filter(value, type);
 189     }
 190
 191     void verifyEdge(Node*, Edge);
 192     void verifyEdges(Node*);
 193
 194     CodeBlock* m_codeBlock;
 195     Graph& m_graph;
 196     AbstractStateType& m_state;
 197     std::unique_ptr<PhiChildren> m_phiChildren;
 198 };
 199
 200 } } // namespace JSC::DFG
 201
 202 #endif // ENABLE(DFG_JIT)
 203
 204 #endif // DFGAbstractInterpreter_h
 205