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