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 35namespace JSC { namespace DFG { 36 37class VirtualRegisterAllocationPhase : public Phase { 38public: 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 143bool 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) 152