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 DFG_ASSERT(m_graph, nullptr, m_graph.m_form == ThreadedCPS);
49
50 ScoreBoard scoreBoard(m_graph.m_nextMachineLocal);
51 scoreBoard.assertClear();
52 for (size_t blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
53 BasicBlock* block = m_graph.block(blockIndex);
54 if (!block)
55 continue;
56 if (!block->isReachable)
57 continue;
58 if (!ASSERT_DISABLED) {
59 // Force usage of highest-numbered virtual registers.
60 scoreBoard.sortFree();
61 }
62 for (auto* node : *block) {
63 if (!node->shouldGenerate())
64 continue;
65
66 switch (node->op()) {
67 case Phi:
68 case Flush:
69 case PhantomLocal:
70 continue;
71 case GetLocal:
72 ASSERT(!node->child1()->hasResult());
73 break;
74 default:
75 break;
76 }
77
78 // First, call use on all of the current node's children, then
79 // allocate a VirtualRegister for this node. We do so in this
80 // order so that if a child is on its last use, and a
81 // VirtualRegister is freed, then it may be reused for node.
82 if (node->flags() & NodeHasVarArgs) {
83 for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++)
84 scoreBoard.useIfHasResult(m_graph.m_varArgChildren[childIdx]);
85 } else {
86 scoreBoard.useIfHasResult(node->child1());
87 scoreBoard.useIfHasResult(node->child2());
88 scoreBoard.useIfHasResult(node->child3());
89 }
90
91 if (!node->hasResult())
92 continue;
93
94 VirtualRegister virtualRegister = scoreBoard.allocate();
95 node->setVirtualRegister(virtualRegister);
96 // 'mustGenerate' nodes have their useCount artificially elevated,
97 // call use now to account for this.
98 if (node->mustGenerate())
99 scoreBoard.use(node);
100 }
101 scoreBoard.assertClear();
102 }
103
104 // Record the number of virtual registers we're using. This is used by calls
105 // to figure out where to put the parameters.
106 m_graph.m_nextMachineLocal = scoreBoard.highWatermark();
107
108 return true;
109 }
110};
111
112bool performVirtualRegisterAllocation(Graph& graph)
113{
114 return runPhase<VirtualRegisterAllocationPhase>(graph);
115}
116
117} } // namespace JSC::DFG
118
119#endif // ENABLE(DFG_JIT)
120