dfg/DFGVirtualRegisterAllocationPhase.cpp

   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 #include "config.h"
  27 #include "DFGVirtualRegisterAllocationPhase.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGGraph.h"
  32 #include "DFGScoreBoard.h"
  33 #include "JSCellInlines.h"
  34
  35 namespace JSC { namespace DFG {
  36
  37 class VirtualRegisterAllocationPhase : public Phase {
  38 public:
  39     VirtualRegisterAllocationPhase(Graph& graph)
  40         : Phase(graph, "virtual register allocation")
  41     {
  42     }
  43
  44     bool run()
  45     {
  46 #if DFG_ENABLE(DEBUG_VERBOSE)
  47         dataLogF("Preserved vars: ");
  48         m_graph.m_preservedVars.dump(WTF::dataFile());
  49         dataLogF("\n");
  50 #endif
  51         ScoreBoard scoreBoard(m_graph.m_preservedVars);
  52         scoreBoard.assertClear();
  53 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
  54         bool needsNewLine = false;
  55 #endif
  56         for (size_t blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
  57             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
  58             if (!block)
  59                 continue;
  60             if (!block->isReachable)
  61                 continue;
  62             for (size_t indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
  63                 Node* node = block->at(indexInBlock);
  64 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
  65                 if (needsNewLine)
  66                     dataLogF("\n");
  67                 dataLogF("   @%u:", node->index());
  68                 needsNewLine = true;
  69 #endif
  70
  71                 if (!node->shouldGenerate())
  72                     continue;
  73
  74                 switch (node->op()) {
  75                 case Phi:
  76                 case Flush:
  77                 case PhantomLocal:
  78                     continue;
  79                 case GetLocal:
  80                     ASSERT(!node->child1()->hasResult());
  81                     break;
  82                 default:
  83                     break;
  84                 }
  85
  86                 // First, call use on all of the current node's children, then
  87                 // allocate a VirtualRegister for this node. We do so in this
  88                 // order so that if a child is on its last use, and a
  89                 // VirtualRegister is freed, then it may be reused for node.
  90                 if (node->flags() & NodeHasVarArgs) {
  91                     for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++)
  92                         scoreBoard.useIfHasResult(m_graph.m_varArgChildren[childIdx]);
  93                 } else {
  94                     scoreBoard.useIfHasResult(node->child1());
  95                     scoreBoard.useIfHasResult(node->child2());
  96                     scoreBoard.useIfHasResult(node->child3());
  97                 }
  98
  99                 if (!node->hasResult())
 100                     continue;
 101
 102                 VirtualRegister virtualRegister = scoreBoard.allocate();
 103 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 104                 dataLogF(
 105                     " Assigning virtual register %u to node %u.",
 106                     virtualRegister, node->index());
 107 #endif
 108                 node->setVirtualRegister(virtualRegister);
 109                 // 'mustGenerate' nodes have their useCount artificially elevated,
 110                 // call use now to account for this.
 111                 if (node->mustGenerate())
 112                     scoreBoard.use(node);
 113             }
 114             scoreBoard.assertClear();
 115         }
 116 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 117         if (needsNewLine)
 118             dataLogF("\n");
 119 #endif
 120
 121         // 'm_numCalleeRegisters' is the number of locals and temporaries allocated
 122         // for the function (and checked for on entry). Since we perform a new and
 123         // different allocation of temporaries, more registers may now be required.
 124         unsigned calleeRegisters = scoreBoard.highWatermark() + m_graph.m_parameterSlots;
 125         size_t inlineCallFrameCount = codeBlock()->inlineCallFrames().size();
 126         for (size_t i = 0; i < inlineCallFrameCount; i++) {
 127             InlineCallFrame& inlineCallFrame = codeBlock()->inlineCallFrames()[i];
 128             CodeBlock* codeBlock = baselineCodeBlockForInlineCallFrame(&inlineCallFrame);
 129             unsigned requiredCalleeRegisters = inlineCallFrame.stackOffset + codeBlock->m_numCalleeRegisters;
 130             if (requiredCalleeRegisters > calleeRegisters)
 131                 calleeRegisters = requiredCalleeRegisters;
 132         }
 133         if ((unsigned)codeBlock()->m_numCalleeRegisters < calleeRegisters)
 134             codeBlock()->m_numCalleeRegisters = calleeRegisters;
 135 #if DFG_ENABLE(DEBUG_VERBOSE)
 136         dataLogF("Num callee registers: %u\n", calleeRegisters);
 137 #endif
 138
 139         return true;
 140     }
 141 };
 142
 143 bool performVirtualRegisterAllocation(Graph& graph)
 144 {
 145     SamplingRegion samplingRegion("DFG Virtual Register Allocation Phase");
 146     return runPhase<VirtualRegisterAllocationPhase>(graph);
 147 }
 148
 149 } } // namespace JSC::DFG
 150
 151 #endif // ENABLE(DFG_JIT)