Changeset 153282 in webkit for trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h
- Timestamp:
- Jul 24, 2013, 9:05:03 PM (12 years ago)
- File:
-
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h
r153281 r153282 1 1 /* 2 * Copyright (C) 201 1, 2012, 2013 Apple Inc. All rights reserved.2 * Copyright (C) 2013 Apple Inc. All rights reserved. 3 3 * 4 4 * Redistribution and use in source and binary forms, with or without … … 24 24 */ 25 25 26 #ifndef DFGAbstract State_h27 #define DFGAbstract State_h26 #ifndef DFGAbstractInterpreter_h 27 #define DFGAbstractInterpreter_h 28 28 29 29 #include <wtf/Platform.h> … … 35 35 #include "DFGGraph.h" 36 36 #include "DFGNode.h" 37 #include <wtf/Vector.h> 38 39 namespace JSC { 40 41 class CodeBlock; 42 43 namespace DFG { 44 45 struct 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 81 class AbstractState { 37 38 namespace JSC { namespace DFG { 39 40 template<typename AbstractStateType> 41 class AbstractInterpreter { 82 42 public: 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(); 43 AbstractInterpreter(Graph&, AbstractStateType& state); 44 ~AbstractInterpreter(); 99 45 100 46 AbstractValue& forNode(Node* node) 101 47 { 102 return node->value;48 return m_state.forNode(node); 103 49 } 104 50 … … 110 56 Operands<AbstractValue>& variables() 111 57 { 112 return m_ variables;58 return m_state.variables(); 113 59 } 114 60 … … 127 73 return needsTypeCheck(edge, typeFilterFor(edge.useKind())); 128 74 } 129 130 // Call this before beginning CFA to initialize the abstract values of131 // arguments, and to indicate which blocks should be listed for CFA132 // execution.133 void initialize();134 135 // Start abstractly executing the given basic block. Initializes the136 // notion of abstract state to what we believe it to be at the head137 // of the basic block, according to the basic block's data structures.138 // This method also sets cfaShouldRevisit to false.139 void beginBasicBlock(BasicBlock*);140 141 // Finish abstractly executing a basic block. If MergeToTail or142 // MergeToSuccessors is passed, then this merges everything we have143 // learned about how the state changes during this block's execution into144 // the block's data structures. There are three return modes, depending145 // on the value of mergeMode:146 //147 // DontMerge:148 // Always returns false.149 //150 // MergeToTail:151 // Returns true if the state of the block at the tail was changed.152 // This means that you must call mergeToSuccessors(), and if that153 // returns true, then you must revisit (at least) the successor154 // blocks. False will always be returned if the block is terminal155 // (i.e. ends in Throw or Return, or has a ForceOSRExit inside it).156 //157 // MergeToSuccessors:158 // Returns true if the state of the block at the tail was changed,159 // and, if the state at the heads of successors was changed.160 // A true return means that you must revisit (at least) the successor161 // blocks. This also sets cfaShouldRevisit to true for basic blocks162 // that must be visited next.163 bool endBasicBlock(MergeMode);164 165 // Reset the AbstractState. This throws away any results, and at this point166 // you can safely call beginBasicBlock() on any basic block.167 void reset();168 75 169 76 // Abstractly executes the given node. The new abstract state is stored into an … … 210 117 bool executeEffects(unsigned indexInBlock, Node*); 211 118 212 // Did the last executed node clobber the world?213 bool didClobber() const { return m_didClobber; }214 215 // Is the execution state still valid? This will be false if execute() has216 // returned false previously.217 bool isValid() const { return m_isValid; }218 219 // Merge the abstract state stored at the first block's tail into the second220 // block's head. Returns true if the second block's state changed. If so,221 // that block must be abstractly interpreted again. This also sets222 // to->cfaShouldRevisit to true, if it returns true, or if to has not been223 // visited yet.224 bool merge(BasicBlock* from, BasicBlock* to);225 226 // Merge the abstract state stored at the block's tail into all of its227 // successors. Returns true if any of the successors' states changed. Note228 // that this is automatically called in endBasicBlock() if MergeMode is229 // MergeToSuccessors.230 bool mergeToSuccessors(BasicBlock*);231 232 119 void dump(PrintStream& out); 233 120 … … 265 152 void clobberCapturedVars(const CodeOrigin&); 266 153 void clobberStructures(unsigned indexInBlock); 267 268 bool mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node*);269 270 static bool mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode);271 154 272 155 enum BooleanResult { … … 311 194 CodeBlock* m_codeBlock; 312 195 Graph& m_graph; 313 314 Operands<AbstractValue> m_variables; 315 BasicBlock* m_block; 316 317 bool m_haveStructures; 318 bool m_foundConstants; 319 320 bool m_isValid; 321 bool m_didClobber; 322 323 BranchDirection m_branchDirection; // This is only set for blocks that end in Branch and that execute to completion (i.e. m_isValid == true). 196 AbstractStateType& m_state; 324 197 }; 325 198 … … 328 201 #endif // ENABLE(DFG_JIT) 329 202 330 #endif // DFGAbstract State_h331 203 #endif // DFGAbstractInterpreter_h 204
Note:
See TracChangeset
for help on using the changeset viewer.
