dfg/DFGAbstractInterpreter.h

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