dfg/DFGAbstractState.h

   1 /*
   2  * Copyright (C) 2011 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 "DFGGraph.h"
  35 #include "DFGNode.h"
  36 #include <wtf/Vector.h>
  37
  38 namespace JSC {
  39
  40 class CodeBlock;
  41
  42 namespace DFG {
  43
  44 struct BasicBlock;
  45
  46 // This implements the notion of an abstract state for flow-sensitive intraprocedural
  47 // control flow analysis (CFA), with a focus on the elimination of redundant type checks.
  48 // It also implements most of the mechanisms of abstract interpretation that such an
  49 // analysis would use. This class should be used in two idioms:
  50 //
  51 // 1) Performing the CFA. In this case, AbstractState should be run over all basic
  52 //    blocks repeatedly until convergence is reached. Convergence is defined by
  53 //    endBasicBlock(AbstractState::MergeToSuccessors) returning false for all blocks.
  54 //
  55 // 2) Rematerializing the results of a previously executed CFA. In this case,
  56 //    AbstractState should be run over whatever basic block you're interested in up
  57 //    to the point of the node at which you'd like to interrogate the known type
  58 //    of all other nodes. At this point it's safe to discard the AbstractState entirely,
  59 //    call reset(), or to run it to the end of the basic block and call
  60 //    endBasicBlock(AbstractState::DontMerge). The latter option is safest because
  61 //    it performs some useful integrity checks.
  62 //
  63 // After the CFA is run, the inter-block state is saved at the heads and tails of all
  64 // basic blocks. This allows the intra-block state to be rematerialized by just
  65 // executing the CFA for that block. If you need to know inter-block state only, then
  66 // you only need to examine the BasicBlock::m_valuesAtHead or m_valuesAtTail fields.
  67 //
  68 // Running this analysis involves the following, modulo the inter-block state
  69 // merging and convergence fixpoint:
  70 //
  71 // AbstractState state(codeBlock, graph);
  72 // state.beginBasicBlock(basicBlock);
  73 // bool endReached = true;
  74 // for (NodeIndex idx = basicBlock.begin; idx < basicBlock.end; ++idx) {
  75 //     if (!state.execute(idx))
  76 //         break;
  77 // }
  78 // bool result = state.endBasicBlock(<either Merge or DontMerge>);
  79
  80 class AbstractState {
  81 public:
  82     enum MergeMode {
  83         // Don't merge the state in AbstractState with basic blocks.
  84         DontMerge,
  85
  86         // Merge the state in AbstractState with the tail of the basic
  87         // block being analyzed.
  88         MergeToTail,
  89
  90         // Merge the state in AbstractState with the tail of the basic
  91         // block, and with the heads of successor blocks.
  92         MergeToSuccessors
  93     };
  94
  95     AbstractState(Graph&);
  96
  97     ~AbstractState();
  98
  99     AbstractValue& forNode(NodeIndex nodeIndex)
 100     {
 101         return m_nodes[nodeIndex];
 102     }
 103
 104     AbstractValue& forNode(Edge nodeUse)
 105     {
 106         return forNode(nodeUse.index());
 107     }
 108
 109     // Call this before beginning CFA to initialize the abstract values of
 110     // arguments, and to indicate which blocks should be listed for CFA
 111     // execution.
 112     static void initialize(Graph&);
 113
 114     // Start abstractly executing the given basic block. Initializes the
 115     // notion of abstract state to what we believe it to be at the head
 116     // of the basic block, according to the basic block's data structures.
 117     // This method also sets cfaShouldRevisit to false.
 118     void beginBasicBlock(BasicBlock*);
 119
 120     // Finish abstractly executing a basic block. If MergeToTail or
 121     // MergeToSuccessors is passed, then this merges everything we have
 122     // learned about how the state changes during this block's execution into
 123     // the block's data structures. There are three return modes, depending
 124     // on the value of mergeMode:
 125     //
 126     // DontMerge:
 127     //    Always returns false.
 128     //
 129     // MergeToTail:
 130     //    Returns true if the state of the block at the tail was changed.
 131     //    This means that you must call mergeToSuccessors(), and if that
 132     //    returns true, then you must revisit (at least) the successor
 133     //    blocks. False will always be returned if the block is terminal
 134     //    (i.e. ends in Throw or Return, or has a ForceOSRExit inside it).
 135     //
 136     // MergeToSuccessors:
 137     //    Returns true if the state of the block at the tail was changed,
 138     //    and, if the state at the heads of successors was changed.
 139     //    A true return means that you must revisit (at least) the successor
 140     //    blocks. This also sets cfaShouldRevisit to true for basic blocks
 141     //    that must be visited next.
 142     bool endBasicBlock(MergeMode);
 143
 144     // Reset the AbstractState. This throws away any results, and at this point
 145     // you can safely call beginBasicBlock() on any basic block.
 146     void reset();
 147
 148     // Abstractly executes the given node. The new abstract state is stored into an
 149     // abstract register file stored in *this. Loads of local variables (that span
 150     // basic blocks) interrogate the basic block's notion of the state at the head.
 151     // Stores to local variables are handled in endBasicBlock(). This returns true
 152     // if execution should continue past this node. Notably, it will return true
 153     // for block terminals, so long as those terminals are not Return or variants
 154     // of Throw.
 155     bool execute(unsigned);
 156
 157     // Is the execution state still valid? This will be false if execute() has
 158     // returned false previously.
 159     bool isValid() const { return m_isValid; }
 160
 161     // Merge the abstract state stored at the first block's tail into the second
 162     // block's head. Returns true if the second block's state changed. If so,
 163     // that block must be abstractly interpreted again. This also sets
 164     // to->cfaShouldRevisit to true, if it returns true, or if to has not been
 165     // visited yet.
 166     bool merge(BasicBlock* from, BasicBlock* to);
 167
 168     // Merge the abstract state stored at the block's tail into all of its
 169     // successors. Returns true if any of the successors' states changed. Note
 170     // that this is automatically called in endBasicBlock() if MergeMode is
 171     // MergeToSuccessors.
 172     bool mergeToSuccessors(Graph&, BasicBlock*);
 173
 174 #ifndef NDEBUG
 175     void dump(FILE* out);
 176 #endif
 177
 178 private:
 179     void clobberStructures(unsigned);
 180
 181     bool mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, NodeIndex);
 182
 183     static bool mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, NodeIndex destinationNodeIndex, NodeIndex sourceNodeIndex);
 184
 185     CodeBlock* m_codeBlock;
 186     Graph& m_graph;
 187
 188     Vector<AbstractValue, 64> m_nodes;
 189     Operands<AbstractValue> m_variables;
 190     BasicBlock* m_block;
 191     bool m_haveStructures;
 192
 193     bool m_isValid;
 194 };
 195
 196 } } // namespace JSC::DFG
 197
 198 #endif // ENABLE(DFG_JIT)
 199
 200 #endif // DFGAbstractState_h
 201