1/* 2 * Copyright (C) 2011, 2013 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 "JSCInlines.h" 34#include "StackAlignment.h" 35#include <wtf/StdLibExtras.h> 36 37namespace JSC { namespace DFG { 38 39class VirtualRegisterAllocationPhase : public Phase { 40public: 41 VirtualRegisterAllocationPhase(Graph& graph) 42 : Phase(graph, "virtual register allocation") 43 { 44 } 45 46 bool run() 47 { 48 ScoreBoard scoreBoard(m_graph.m_nextMachineLocal); 49 scoreBoard.assertClear(); 50 for (size_t blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) { 51 BasicBlock* block = m_graph.block(blockIndex); 52 if (!block) 53 continue; 54 if (!block->isReachable) 55 continue; 56 for (size_t indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) { 57 Node* node = block->at(indexInBlock); 58 59 if (!node->shouldGenerate()) 60 continue; 61 62 switch (node->op()) { 63 case Phi: 64 case Flush: 65 case PhantomLocal: 66 continue; 67 case GetLocal: 68 ASSERT(!node->child1()->hasResult()); 69 break; 70 default: 71 break; 72 } 73 74 // First, call use on all of the current node's children, then 75 // allocate a VirtualRegister for this node. We do so in this 76 // order so that if a child is on its last use, and a 77 // VirtualRegister is freed, then it may be reused for node. 78 if (node->flags() & NodeHasVarArgs) { 79 for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) 80 scoreBoard.useIfHasResult(m_graph.m_varArgChildren[childIdx]); 81 } else { 82 scoreBoard.useIfHasResult(node->child1()); 83 scoreBoard.useIfHasResult(node->child2()); 84 scoreBoard.useIfHasResult(node->child3()); 85 } 86 87 if (!node->hasResult()) 88 continue; 89 90 VirtualRegister virtualRegister = scoreBoard.allocate(); 91 node->setVirtualRegister(virtualRegister); 92 // 'mustGenerate' nodes have their useCount artificially elevated, 93 // call use now to account for this. 94 if (node->mustGenerate()) 95 scoreBoard.use(node); 96 } 97 scoreBoard.assertClear(); 98 } 99 100 // Record the number of virtual registers we're using. This is used by calls 101 // to figure out where to put the parameters. 102 m_graph.m_nextMachineLocal = scoreBoard.highWatermark(); 103 104 return true; 105 } 106}; 107 108bool performVirtualRegisterAllocation(Graph& graph) 109{ 110 SamplingRegion samplingRegion("DFG Virtual Register Allocation Phase"); 111 return runPhase<VirtualRegisterAllocationPhase>(graph); 112} 113 114} } // namespace JSC::DFG 115 116#endif // ENABLE(DFG_JIT) 117