diff options
Diffstat (limited to 'Source/JavaScriptCore/dfg/DFGAbstractState.h')
| -rw-r--r-- | Source/JavaScriptCore/dfg/DFGAbstractState.h | 297 |
1 files changed, 0 insertions, 297 deletions
diff --git a/Source/JavaScriptCore/dfg/DFGAbstractState.h b/Source/JavaScriptCore/dfg/DFGAbstractState.h deleted file mode 100644 index cbb213a6f..000000000 --- a/Source/JavaScriptCore/dfg/DFGAbstractState.h +++ /dev/null @@ -1,297 +0,0 @@ -/* - * Copyright (C) 2011, 2012, 2013 Apple Inc. All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY - * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR - * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR - * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, - * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, - * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR - * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY - * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -#ifndef DFGAbstractState_h -#define DFGAbstractState_h - -#include <wtf/Platform.h> - -#if ENABLE(DFG_JIT) - -#include "DFGAbstractValue.h" -#include "DFGBranchDirection.h" -#include "DFGGraph.h" -#include "DFGNode.h" -#include <wtf/Vector.h> - -namespace JSC { - -class CodeBlock; - -namespace DFG { - -struct BasicBlock; - -// This implements the notion of an abstract state for flow-sensitive intraprocedural -// control flow analysis (CFA), with a focus on the elimination of redundant type checks. -// It also implements most of the mechanisms of abstract interpretation that such an -// analysis would use. This class should be used in two idioms: -// -// 1) Performing the CFA. In this case, AbstractState should be run over all basic -// blocks repeatedly until convergence is reached. Convergence is defined by -// endBasicBlock(AbstractState::MergeToSuccessors) returning false for all blocks. -// -// 2) Rematerializing the results of a previously executed CFA. In this case, -// AbstractState should be run over whatever basic block you're interested in up -// to the point of the node at which you'd like to interrogate the known type -// of all other nodes. At this point it's safe to discard the AbstractState entirely, -// call reset(), or to run it to the end of the basic block and call -// endBasicBlock(AbstractState::DontMerge). The latter option is safest because -// it performs some useful integrity checks. -// -// After the CFA is run, the inter-block state is saved at the heads and tails of all -// basic blocks. This allows the intra-block state to be rematerialized by just -// executing the CFA for that block. If you need to know inter-block state only, then -// you only need to examine the BasicBlock::m_valuesAtHead or m_valuesAtTail fields. -// -// Running this analysis involves the following, modulo the inter-block state -// merging and convergence fixpoint: -// -// AbstractState state(codeBlock, graph); -// state.beginBasicBlock(basicBlock); -// bool endReached = true; -// for (unsigned i = 0; i < basicBlock->size(); ++i) { -// if (!state.execute(i)) -// break; -// } -// bool result = state.endBasicBlock(<either Merge or DontMerge>); - -class AbstractState { -public: - enum MergeMode { - // Don't merge the state in AbstractState with basic blocks. - DontMerge, - - // Merge the state in AbstractState with the tail of the basic - // block being analyzed. - MergeToTail, - - // Merge the state in AbstractState with the tail of the basic - // block, and with the heads of successor blocks. - MergeToSuccessors - }; - - AbstractState(Graph&); - - ~AbstractState(); - - AbstractValue& forNode(Node* node) - { - return node->value; - } - - AbstractValue& forNode(Edge edge) - { - return forNode(edge.node()); - } - - Operands<AbstractValue>& variables() - { - return m_variables; - } - - // Call this before beginning CFA to initialize the abstract values of - // arguments, and to indicate which blocks should be listed for CFA - // execution. - static void initialize(Graph&); - - // Start abstractly executing the given basic block. Initializes the - // notion of abstract state to what we believe it to be at the head - // of the basic block, according to the basic block's data structures. - // This method also sets cfaShouldRevisit to false. - void beginBasicBlock(BasicBlock*); - - // Finish abstractly executing a basic block. If MergeToTail or - // MergeToSuccessors is passed, then this merges everything we have - // learned about how the state changes during this block's execution into - // the block's data structures. There are three return modes, depending - // on the value of mergeMode: - // - // DontMerge: - // Always returns false. - // - // MergeToTail: - // Returns true if the state of the block at the tail was changed. - // This means that you must call mergeToSuccessors(), and if that - // returns true, then you must revisit (at least) the successor - // blocks. False will always be returned if the block is terminal - // (i.e. ends in Throw or Return, or has a ForceOSRExit inside it). - // - // MergeToSuccessors: - // Returns true if the state of the block at the tail was changed, - // and, if the state at the heads of successors was changed. - // A true return means that you must revisit (at least) the successor - // blocks. This also sets cfaShouldRevisit to true for basic blocks - // that must be visited next. - bool endBasicBlock(MergeMode); - - // Reset the AbstractState. This throws away any results, and at this point - // you can safely call beginBasicBlock() on any basic block. - void reset(); - - // Abstractly executes the given node. The new abstract state is stored into an - // abstract stack stored in *this. Loads of local variables (that span - // basic blocks) interrogate the basic block's notion of the state at the head. - // Stores to local variables are handled in endBasicBlock(). This returns true - // if execution should continue past this node. Notably, it will return true - // for block terminals, so long as those terminals are not Return or Unreachable. - // - // This is guaranteed to be equivalent to doing: - // - // if (state.startExecuting(index)) { - // state.executeEdges(index); - // result = state.executeEffects(index); - // } else - // result = true; - bool execute(unsigned indexInBlock); - - // Indicate the start of execution of the node. It resets any state in the node, - // that is progressively built up by executeEdges() and executeEffects(). In - // particular, this resets canExit(), so if you want to "know" between calls of - // startExecuting() and executeEdges()/Effects() whether the last run of the - // analysis concluded that the node can exit, you should probably set that - // information aside prior to calling startExecuting(). - bool startExecuting(Node*); - bool startExecuting(unsigned indexInBlock); - - // Abstractly execute the edges of the given node. This runs filterEdgeByUse() - // on all edges of the node. You can skip this step, if you have already used - // filterEdgeByUse() (or some equivalent) on each edge. - void executeEdges(Node*); - void executeEdges(unsigned indexInBlock); - - ALWAYS_INLINE void filterEdgeByUse(Node* node, Edge& edge) - { -#if !ASSERT_DISABLED - switch (edge.useKind()) { - case KnownInt32Use: - case KnownNumberUse: - case KnownCellUse: - case KnownStringUse: - ASSERT(!(forNode(edge).m_type & ~typeFilterFor(edge.useKind()))); - break; - default: - break; - } -#endif // !ASSERT_DISABLED - - filterByType(node, edge, typeFilterFor(edge.useKind())); - } - - // Abstractly execute the effects of the given node. This changes the abstract - // state assuming that edges have already been filtered. - bool executeEffects(unsigned indexInBlock); - bool executeEffects(unsigned indexInBlock, Node*); - - // Did the last executed node clobber the world? - bool didClobber() const { return m_didClobber; } - - // Is the execution state still valid? This will be false if execute() has - // returned false previously. - bool isValid() const { return m_isValid; } - - // Merge the abstract state stored at the first block's tail into the second - // block's head. Returns true if the second block's state changed. If so, - // that block must be abstractly interpreted again. This also sets - // to->cfaShouldRevisit to true, if it returns true, or if to has not been - // visited yet. - bool merge(BasicBlock* from, BasicBlock* to); - - // Merge the abstract state stored at the block's tail into all of its - // successors. Returns true if any of the successors' states changed. Note - // that this is automatically called in endBasicBlock() if MergeMode is - // MergeToSuccessors. - bool mergeToSuccessors(Graph&, BasicBlock*); - - void dump(PrintStream& out); - -private: - void clobberWorld(const CodeOrigin&, unsigned indexInBlock); - void clobberCapturedVars(const CodeOrigin&); - void clobberStructures(unsigned indexInBlock); - - bool mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node*); - - static bool mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode); - - enum BooleanResult { - UnknownBooleanResult, - DefinitelyFalse, - DefinitelyTrue - }; - BooleanResult booleanResult(Node*, AbstractValue&); - - bool trySetConstant(Node* node, JSValue value) - { - // Make sure we don't constant fold something that will produce values that contravene - // predictions. If that happens then we know that the code will OSR exit, forcing - // recompilation. But if we tried to constant fold then we'll have a very degenerate - // IR: namely we'll have a JSConstant that contravenes its own prediction. There's a - // lot of subtle code that assumes that - // speculationFromValue(jsConstant) == jsConstant.prediction(). "Hardening" that code - // is probably less sane than just pulling back on constant folding. - SpeculatedType oldType = node->prediction(); - if (mergeSpeculations(speculationFromValue(value), oldType) != oldType) - return false; - - forNode(node).set(value); - return true; - } - - ALWAYS_INLINE void filterByType(Node* node, Edge& edge, SpeculatedType type) - { - AbstractValue& value = forNode(edge); - if (value.m_type & ~type) { - node->setCanExit(true); - edge.setProofStatus(NeedsCheck); - } else - edge.setProofStatus(IsProved); - - value.filter(type); - } - - void verifyEdge(Node*, Edge); - void verifyEdges(Node*); - - CodeBlock* m_codeBlock; - Graph& m_graph; - - Operands<AbstractValue> m_variables; - BasicBlock* m_block; - bool m_haveStructures; - bool m_foundConstants; - - bool m_isValid; - bool m_didClobber; - - BranchDirection m_branchDirection; // This is only set for blocks that end in Branch and that execute to completion (i.e. m_isValid == true). -}; - -} } // namespace JSC::DFG - -#endif // ENABLE(DFG_JIT) - -#endif // DFGAbstractState_h - |