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 36namespace JSC { namespace DFG { 37 38template<typename AbstractStateType> 39class AbstractInterpreter { 40public: 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 148private: 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 199