dfg/DFGGraph.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 DFGGraph_h
  27 #define DFGGraph_h
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include <RegisterFile.h>
  32 #include <dfg/DFGNode.h>
  33 #include <wtf/Vector.h>
  34 #include <wtf/StdLibExtras.h>
  35
  36 namespace JSC {
  37
  38 class CodeBlock;
  39
  40 namespace DFG {
  41
  42 // helper function to distinguish vars & temporaries from arguments.
  43 inline bool operandIsArgument(int operand) { return operand < 0; }
  44
  45 typedef uint8_t PredictedType;
  46 static const PredictedType PredictNone  = 0;
  47 static const PredictedType PredictCell  = 0x01;
  48 static const PredictedType PredictArray = 0x03;
  49 static const PredictedType PredictInt32 = 0x04;
  50
  51 struct PredictionSlot {
  52 public:
  53     PredictionSlot()
  54         : m_value(PredictNone)
  55     {
  56     }
  57     PredictedType m_value;
  58 };
  59
  60 typedef uint32_t BlockIndex;
  61
  62 // For every local variable we track any existing get or set of the value.
  63 // We track the get so that these may be shared, and we track the set to
  64 // retrieve the current value, and to reference the final definition.
  65 struct VariableRecord {
  66     VariableRecord()
  67         : value(NoNode)
  68     {
  69     }
  70
  71     NodeIndex value;
  72 };
  73
  74 typedef Vector <BlockIndex, 2> PredecessorList;
  75
  76 struct BasicBlock {
  77     BasicBlock(unsigned bytecodeBegin, NodeIndex begin, unsigned numArguments, unsigned numLocals)
  78         : bytecodeBegin(bytecodeBegin)
  79         , begin(begin)
  80         , end(NoNode)
  81         , m_arguments(numArguments)
  82         , m_locals(numLocals)
  83     {
  84     }
  85
  86     static inline BlockIndex getBytecodeBegin(OwnPtr<BasicBlock>* block)
  87     {
  88         return (*block)->bytecodeBegin;
  89     }
  90
  91     unsigned bytecodeBegin;
  92     NodeIndex begin;
  93     NodeIndex end;
  94
  95     PredecessorList m_predecessors;
  96     Vector <VariableRecord, 8> m_arguments;
  97     Vector <VariableRecord, 16> m_locals;
  98 };
  99
 100 //
 101 // === Graph ===
 102 //
 103 // The dataflow graph is an ordered vector of nodes.
 104 // The order may be significant for nodes with side-effects (property accesses, value conversions).
 105 // Nodes that are 'dead' remain in the vector with refCount 0.
 106 class Graph : public Vector<Node, 64> {
 107 public:
 108     Graph(unsigned numArguments, unsigned numVariables)
 109         : m_argumentPredictions(numArguments)
 110         , m_variablePredictions(numVariables)
 111     {
 112     }
 113
 114     // Mark a node as being referenced.
 115     void ref(NodeIndex nodeIndex)
 116     {
 117         Node& node = at(nodeIndex);
 118         // If the value (before incrementing) was at refCount zero then we need to ref its children.
 119         if (node.ref())
 120             refChildren(nodeIndex);
 121     }
 122
 123 #ifndef NDEBUG
 124     // CodeBlock is optional, but may allow additional information to be dumped (e.g. Identifier names).
 125     void dump(CodeBlock* = 0);
 126     void dump(NodeIndex, CodeBlock* = 0);
 127 #endif
 128
 129     BlockIndex blockIndexForBytecodeOffset(unsigned bytecodeBegin)
 130     {
 131         OwnPtr<BasicBlock>* begin = m_blocks.begin();
 132         OwnPtr<BasicBlock>* block = binarySearch<OwnPtr<BasicBlock>, unsigned, BasicBlock::getBytecodeBegin>(begin, m_blocks.size(), bytecodeBegin);
 133         ASSERT(block >= m_blocks.begin() && block < m_blocks.end());
 134         return static_cast<BlockIndex>(block - begin);
 135     }
 136
 137     BasicBlock& blockForBytecodeOffset(unsigned bytecodeBegin)
 138     {
 139         return *m_blocks[blockIndexForBytecodeOffset(bytecodeBegin)];
 140     }
 141
 142     void predict(int operand, PredictedType prediction)
 143     {
 144         if (operandIsArgument(operand)) {
 145             unsigned argument = operand + m_argumentPredictions.size() + RegisterFile::CallFrameHeaderSize;
 146             m_argumentPredictions[argument].m_value |= prediction;
 147         } else if ((unsigned)operand < m_variablePredictions.size())
 148             m_variablePredictions[operand].m_value |= prediction;
 149
 150     }
 151
 152     PredictedType getPrediction(int operand)
 153     {
 154         if (operandIsArgument(operand)) {
 155             unsigned argument = operand + m_argumentPredictions.size() + RegisterFile::CallFrameHeaderSize;
 156             return m_argumentPredictions[argument].m_value;
 157         }
 158         if ((unsigned)operand < m_variablePredictions.size())
 159             return m_variablePredictions[operand].m_value;
 160         return PredictNone;
 161     }
 162
 163     Vector< OwnPtr<BasicBlock> , 8> m_blocks;
 164 private:
 165
 166     // When a node's refCount goes from 0 to 1, it must (logically) recursively ref all of its children, and vice versa.
 167     void refChildren(NodeIndex);
 168
 169     Vector<PredictionSlot, 16> m_argumentPredictions;
 170     Vector<PredictionSlot, 16> m_variablePredictions;
 171 };
 172
 173 } } // namespace JSC::DFG
 174
 175 #endif
 176 #endif