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