Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h

   1 /*
   2  * Copyright (C) 2013-2016 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     void executeKnownEdgeTypes(Node*);
 101
 102     ALWAYS_INLINE void filterEdgeByUse(Edge& edge)
 103     {
 104         filterByType(edge, typeFilterFor(edge.useKind()));
 105     }
 106
 107     // Abstractly execute the effects of the given node. This changes the abstract
 108     // state assuming that edges have already been filtered.
 109     bool executeEffects(unsigned indexInBlock);
 110     bool executeEffects(unsigned clobberLimit, Node*);
 111
 112     void dump(PrintStream& out) const;
 113     void dump(PrintStream& out);
 114
 115     template<typename T>
 116     FiltrationResult filter(T node, const StructureSet& set, SpeculatedType admittedTypes = SpecNone)
 117     {
 118         return filter(forNode(node), set, admittedTypes);
 119     }
 120
 121     template<typename T>
 122     FiltrationResult filterArrayModes(T node, ArrayModes arrayModes)
 123     {
 124         return filterArrayModes(forNode(node), arrayModes);
 125     }
 126
 127     template<typename T>
 128     FiltrationResult filter(T node, SpeculatedType type)
 129     {
 130         return filter(forNode(node), type);
 131     }
 132
 133     template<typename T>
 134     FiltrationResult filterByValue(T node, FrozenValue value)
 135     {
 136         return filterByValue(forNode(node), value);
 137     }
 138
 139     FiltrationResult filter(AbstractValue&, const StructureSet&, SpeculatedType admittedTypes = SpecNone);
 140     FiltrationResult filterArrayModes(AbstractValue&, ArrayModes);
 141     FiltrationResult filter(AbstractValue&, SpeculatedType);
 142     FiltrationResult filterByValue(AbstractValue&, FrozenValue);
 143
 144     PhiChildren* phiChildren() { return m_phiChildren.get(); }
 145
 146 private:
 147     void clobberWorld(const CodeOrigin&, unsigned indexInBlock);
 148
 149     template<typename Functor>
 150     void forAllValues(unsigned indexInBlock, Functor&);
 151
 152     void clobberStructures(unsigned indexInBlock);
 153     void observeTransition(unsigned indexInBlock, Structure* from, Structure* to);
 154     void observeTransitions(unsigned indexInBlock, const TransitionVector&);
 155     void setDidClobber();
 156
 157     enum BooleanResult {
 158         UnknownBooleanResult,
 159         DefinitelyFalse,
 160         DefinitelyTrue
 161     };
 162     BooleanResult booleanResult(Node*, AbstractValue&);
 163
 164     void setBuiltInConstant(Node* node, FrozenValue value)
 165     {
 166         AbstractValue& abstractValue = forNode(node);
 167         abstractValue.set(m_graph, value, m_state.structureClobberState());
 168         abstractValue.fixTypeForRepresentation(m_graph, node);
 169     }
 170
 171     void setConstant(Node* node, FrozenValue value)
 172     {
 173         setBuiltInConstant(node, value);
 174         m_state.setFoundConstants(true);
 175     }
 176
 177     ALWAYS_INLINE void filterByType(Edge& edge, SpeculatedType type)
 178     {
 179         AbstractValue& value = forNode(edge);
 180         if (!value.isType(type))
 181             edge.setProofStatus(NeedsCheck);
 182         else
 183             edge.setProofStatus(IsProved);
 184
 185         filter(value, type);
 186     }
 187
 188     void verifyEdge(Node*, Edge);
 189     void verifyEdges(Node*);
 190
 191     CodeBlock* m_codeBlock;
 192     Graph& m_graph;
 193     AbstractStateType& m_state;
 194     std::unique_ptr<PhiChildren> m_phiChildren;
 195 };
 196
 197 } } // namespace JSC::DFG
 198
 199 #endif // ENABLE(DFG_JIT)
 200
 201 #endif // DFGAbstractInterpreter_h
 202