1/* 2 * Copyright (C) 2011, 2012, 2013 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 DFGAbstractState_h 27#define DFGAbstractState_h 28 29#include <wtf/Platform.h> 30 31#if ENABLE(DFG_JIT) 32 33#include "DFGAbstractValue.h" 34#include "DFGBranchDirection.h" 35#include "DFGGraph.h" 36#include "DFGNode.h" 37#include <wtf/Vector.h> 38 39namespace JSC { 40 41class CodeBlock; 42 43namespace DFG { 44 45struct BasicBlock; 46 47// This implements the notion of an abstract state for flow-sensitive intraprocedural 48// control flow analysis (CFA), with a focus on the elimination of redundant type checks. 49// It also implements most of the mechanisms of abstract interpretation that such an 50// analysis would use. This class should be used in two idioms: 51// 52// 1) Performing the CFA. In this case, AbstractState should be run over all basic 53// blocks repeatedly until convergence is reached. Convergence is defined by 54// endBasicBlock(AbstractState::MergeToSuccessors) returning false for all blocks. 55// 56// 2) Rematerializing the results of a previously executed CFA. In this case, 57// AbstractState should be run over whatever basic block you're interested in up 58// to the point of the node at which you'd like to interrogate the known type 59// of all other nodes. At this point it's safe to discard the AbstractState entirely, 60// call reset(), or to run it to the end of the basic block and call 61// endBasicBlock(AbstractState::DontMerge). The latter option is safest because 62// it performs some useful integrity checks. 63// 64// After the CFA is run, the inter-block state is saved at the heads and tails of all 65// basic blocks. This allows the intra-block state to be rematerialized by just 66// executing the CFA for that block. If you need to know inter-block state only, then 67// you only need to examine the BasicBlock::m_valuesAtHead or m_valuesAtTail fields. 68// 69// Running this analysis involves the following, modulo the inter-block state 70// merging and convergence fixpoint: 71// 72// AbstractState state(codeBlock, graph); 73// state.beginBasicBlock(basicBlock); 74// bool endReached = true; 75// for (unsigned i = 0; i < basicBlock->size(); ++i) { 76// if (!state.execute(i)) 77// break; 78// } 79// bool result = state.endBasicBlock(<either Merge or DontMerge>); 80 81class AbstractState { 82public: 83 enum MergeMode { 84 // Don't merge the state in AbstractState with basic blocks. 85 DontMerge, 86 87 // Merge the state in AbstractState with the tail of the basic 88 // block being analyzed. 89 MergeToTail, 90 91 // Merge the state in AbstractState with the tail of the basic 92 // block, and with the heads of successor blocks. 93 MergeToSuccessors 94 }; 95 96 AbstractState(Graph&); 97 98 ~AbstractState(); 99 100 AbstractValue& forNode(Node* node) 101 { 102 return node->value; 103 } 104 105 AbstractValue& forNode(Edge edge) 106 { 107 return forNode(edge.node()); 108 } 109 110 Operands<AbstractValue>& variables() 111 { 112 return m_variables; 113 } 114 115 // Call this before beginning CFA to initialize the abstract values of 116 // arguments, and to indicate which blocks should be listed for CFA 117 // execution. 118 static void initialize(Graph&); 119 120 // Start abstractly executing the given basic block. Initializes the 121 // notion of abstract state to what we believe it to be at the head 122 // of the basic block, according to the basic block's data structures. 123 // This method also sets cfaShouldRevisit to false. 124 void beginBasicBlock(BasicBlock*); 125 126 // Finish abstractly executing a basic block. If MergeToTail or 127 // MergeToSuccessors is passed, then this merges everything we have 128 // learned about how the state changes during this block's execution into 129 // the block's data structures. There are three return modes, depending 130 // on the value of mergeMode: 131 // 132 // DontMerge: 133 // Always returns false. 134 // 135 // MergeToTail: 136 // Returns true if the state of the block at the tail was changed. 137 // This means that you must call mergeToSuccessors(), and if that 138 // returns true, then you must revisit (at least) the successor 139 // blocks. False will always be returned if the block is terminal 140 // (i.e. ends in Throw or Return, or has a ForceOSRExit inside it). 141 // 142 // MergeToSuccessors: 143 // Returns true if the state of the block at the tail was changed, 144 // and, if the state at the heads of successors was changed. 145 // A true return means that you must revisit (at least) the successor 146 // blocks. This also sets cfaShouldRevisit to true for basic blocks 147 // that must be visited next. 148 bool endBasicBlock(MergeMode); 149 150 // Reset the AbstractState. This throws away any results, and at this point 151 // you can safely call beginBasicBlock() on any basic block. 152 void reset(); 153 154 // Abstractly executes the given node. The new abstract state is stored into an 155 // abstract stack stored in *this. Loads of local variables (that span 156 // basic blocks) interrogate the basic block's notion of the state at the head. 157 // Stores to local variables are handled in endBasicBlock(). This returns true 158 // if execution should continue past this node. Notably, it will return true 159 // for block terminals, so long as those terminals are not Return or variants 160 // of Throw. 161 // 162 // This is guaranteed to be equivalent to doing: 163 // 164 // if (state.startExecuting(index)) { 165 // state.executeEdges(index); 166 // result = state.executeEffects(index); 167 // } else 168 // result = true; 169 bool execute(unsigned indexInBlock); 170 171 // Indicate the start of execution of the node. It resets any state in the node, 172 // that is progressively built up by executeEdges() and executeEffects(). In 173 // particular, this resets canExit(), so if you want to "know" between calls of 174 // startExecuting() and executeEdges()/Effects() whether the last run of the 175 // analysis concluded that the node can exit, you should probably set that 176 // information aside prior to calling startExecuting(). 177 bool startExecuting(Node*); 178 bool startExecuting(unsigned indexInBlock); 179 180 // Abstractly execute the edges of the given node. This runs filterEdgeByUse() 181 // on all edges of the node. You can skip this step, if you have already used 182 // filterEdgeByUse() (or some equivalent) on each edge. 183 void executeEdges(Node*); 184 void executeEdges(unsigned indexInBlock); 185 186 ALWAYS_INLINE void filterEdgeByUse(Node* node, Edge& edge) 187 { 188#if !ASSERT_DISABLED 189 switch (edge.useKind()) { 190 case KnownInt32Use: 191 case KnownNumberUse: 192 case KnownCellUse: 193 case KnownStringUse: 194 ASSERT(!(forNode(edge).m_type & ~typeFilterFor(edge.useKind()))); 195 break; 196 default: 197 break; 198 } 199#endif // !ASSERT_DISABLED 200 201 filterByType(node, edge, typeFilterFor(edge.useKind())); 202 } 203 204 // Abstractly execute the effects of the given node. This changes the abstract 205 // state assuming that edges have already been filtered. 206 bool executeEffects(unsigned indexInBlock); 207 bool executeEffects(unsigned indexInBlock, Node*); 208 209 // Did the last executed node clobber the world? 210 bool didClobber() const { return m_didClobber; } 211 212 // Is the execution state still valid? This will be false if execute() has 213 // returned false previously. 214 bool isValid() const { return m_isValid; } 215 216 // Merge the abstract state stored at the first block's tail into the second 217 // block's head. Returns true if the second block's state changed. If so, 218 // that block must be abstractly interpreted again. This also sets 219 // to->cfaShouldRevisit to true, if it returns true, or if to has not been 220 // visited yet. 221 bool merge(BasicBlock* from, BasicBlock* to); 222 223 // Merge the abstract state stored at the block's tail into all of its 224 // successors. Returns true if any of the successors' states changed. Note 225 // that this is automatically called in endBasicBlock() if MergeMode is 226 // MergeToSuccessors. 227 bool mergeToSuccessors(Graph&, BasicBlock*); 228 229 void dump(PrintStream& out); 230 231private: 232 void clobberWorld(const CodeOrigin&, unsigned indexInBlock); 233 void clobberCapturedVars(const CodeOrigin&); 234 void clobberStructures(unsigned indexInBlock); 235 236 bool mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node*); 237 238 static bool mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode); 239 240 enum BooleanResult { 241 UnknownBooleanResult, 242 DefinitelyFalse, 243 DefinitelyTrue 244 }; 245 BooleanResult booleanResult(Node*, AbstractValue&); 246 247 bool trySetConstant(Node* node, JSValue value) 248 { 249 // Make sure we don't constant fold something that will produce values that contravene 250 // predictions. If that happens then we know that the code will OSR exit, forcing 251 // recompilation. But if we tried to constant fold then we'll have a very degenerate 252 // IR: namely we'll have a JSConstant that contravenes its own prediction. There's a 253 // lot of subtle code that assumes that 254 // speculationFromValue(jsConstant) == jsConstant.prediction(). "Hardening" that code 255 // is probably less sane than just pulling back on constant folding. 256 SpeculatedType oldType = node->prediction(); 257 if (mergeSpeculations(speculationFromValue(value), oldType) != oldType) 258 return false; 259 260 forNode(node).set(value); 261 return true; 262 } 263 264 ALWAYS_INLINE void filterByType(Node* node, Edge& edge, SpeculatedType type) 265 { 266 AbstractValue& value = forNode(edge); 267 if (value.m_type & ~type) { 268 node->setCanExit(true); 269 edge.setProofStatus(NeedsCheck); 270 } else 271 edge.setProofStatus(IsProved); 272 273 value.filter(type); 274 } 275 276 void verifyEdge(Node*, Edge); 277 void verifyEdges(Node*); 278 279 CodeBlock* m_codeBlock; 280 Graph& m_graph; 281 282 Operands<AbstractValue> m_variables; 283 BasicBlock* m_block; 284 bool m_haveStructures; 285 bool m_foundConstants; 286 287 bool m_isValid; 288 bool m_didClobber; 289 290 BranchDirection m_branchDirection; // This is only set for blocks that end in Branch and that execute to completion (i.e. m_isValid == true). 291}; 292 293} } // namespace JSC::DFG 294 295#endif // ENABLE(DFG_JIT) 296 297#endif // DFGAbstractState_h 298 299