1/*
2 * Copyright (C) 2015 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 "DFGPhantomInsertionPhase.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "BytecodeLivenessAnalysisInlines.h"
32#include "DFGForAllKills.h"
33#include "DFGGraph.h"
34#include "DFGInsertionSet.h"
35#include "DFGMayExit.h"
36#include "DFGPhase.h"
37#include "DFGPredictionPropagationPhase.h"
38#include "DFGVariableAccessDataDump.h"
39#include "JSCInlines.h"
40#include "OperandsInlines.h"
41
42namespace JSC { namespace DFG {
43
44namespace {
45
46namespace DFGPhantomInsertionPhaseInternal {
47static const bool verbose = false;
48}
49
50class PhantomInsertionPhase : public Phase {
51public:
52 PhantomInsertionPhase(Graph& graph)
53 : Phase(graph, "phantom insertion")
54 , m_insertionSet(graph)
55 , m_values(OperandsLike, graph.block(0)->variablesAtHead)
56 {
57 }
58
59 bool run()
60 {
61 // We assume that DCE has already run. If we run before DCE then we think that all
62 // SetLocals execute, which is inaccurate. That causes us to insert too few Phantoms.
63 DFG_ASSERT(m_graph, nullptr, m_graph.m_refCountState == ExactRefCount);
64
65 if (DFGPhantomInsertionPhaseInternal::verbose) {
66 dataLog("Graph before Phantom insertion:\n");
67 m_graph.dump();
68 }
69
70 m_graph.clearEpochs();
71
72 for (BasicBlock* block : m_graph.blocksInNaturalOrder())
73 handleBlock(block);
74
75 if (DFGPhantomInsertionPhaseInternal::verbose) {
76 dataLog("Graph after Phantom insertion:\n");
77 m_graph.dump();
78 }
79
80 return true;
81 }
82
83private:
84 void handleBlock(BasicBlock* block)
85 {
86 // FIXME: For blocks that have low register pressure, it would make the most sense to
87 // simply insert Phantoms at the last point possible since that would obviate the need to
88 // query bytecode liveness:
89 //
90 // - If we MovHint @x into loc42 then put a Phantom on the last MovHinted value in loc42.
91 // - At the end of the block put Phantoms for each MovHinted value.
92 //
93 // This will definitely not work if there are any phantom allocations. For those blocks
94 // where this would be legal, it remains to be seen how profitable it would be even if there
95 // was high register pressure. After all, a Phantom would cause a spill but it wouldn't
96 // cause a fill.
97 //
98 // https://bugs.webkit.org/show_bug.cgi?id=144524
99
100 m_values.fill(nullptr);
101
102 Epoch currentEpoch = Epoch::first();
103 unsigned lastExitingIndex = 0;
104 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
105 Node* node = block->at(nodeIndex);
106 if (DFGPhantomInsertionPhaseInternal::verbose)
107 dataLog("Considering ", node, "\n");
108
109 switch (node->op()) {
110 case MovHint:
111 m_values.operand(node->unlinkedLocal()) = node->child1().node();
112 break;
113
114 case ZombieHint:
115 m_values.operand(node->unlinkedLocal()) = nullptr;
116 break;
117
118 case GetLocal:
119 case SetArgumentDefinitely:
120 case SetArgumentMaybe:
121 m_values.operand(node->local()) = nullptr;
122 break;
123
124 default:
125 break;
126 }
127
128 bool nodeMayExit = mayExit(m_graph, node) != DoesNotExit;
129 if (nodeMayExit) {
130 currentEpoch.bump();
131 lastExitingIndex = nodeIndex;
132 }
133
134 m_graph.doToChildren(
135 node,
136 [&] (Edge edge) {
137 edge->setEpoch(currentEpoch);
138 });
139
140 node->setEpoch(currentEpoch);
141
142 VirtualRegister alreadyKilled;
143
144 auto processKilledOperand = [&] (VirtualRegister reg) {
145 if (DFGPhantomInsertionPhaseInternal::verbose)
146 dataLog(" Killed operand: ", reg, "\n");
147
148 // Already handled from SetLocal.
149 if (reg == alreadyKilled)
150 return;
151
152 Node* killedNode = m_values.operand(reg);
153 if (!killedNode)
154 return;
155
156 // We only need to insert a Phantom if the node hasn't been used since the last
157 // exit, and was born before the last exit.
158 if (killedNode->epoch() == currentEpoch)
159 return;
160
161 if (DFGPhantomInsertionPhaseInternal::verbose) {
162 dataLog(
163 " Inserting Phantom on ", killedNode, " after ",
164 block->at(lastExitingIndex), "\n");
165 }
166
167 // We have exact ref counts, so creating a new use means that we have to
168 // increment the ref count.
169 killedNode->postfixRef();
170
171 Node* lastExitingNode = block->at(lastExitingIndex);
172
173 m_insertionSet.insertNode(
174 lastExitingIndex + 1, SpecNone, Phantom,
175 lastExitingNode->origin.forInsertingAfter(m_graph, lastExitingNode),
176 killedNode->defaultEdge());
177 };
178
179 if (node->op() == SetLocal) {
180 VirtualRegister local = node->local();
181 if (nodeMayExit) {
182 // If the SetLocal does exit, we need the MovHint of its local
183 // to be live until the SetLocal is done.
184 processKilledOperand(local);
185 alreadyKilled = local;
186 }
187 m_values.operand(local) = nullptr;
188 }
189
190 forAllKilledOperands(m_graph, node, block->tryAt(nodeIndex + 1), processKilledOperand);
191 }
192
193 m_insertionSet.execute(block);
194 }
195
196 InsertionSet m_insertionSet;
197 Operands<Node*> m_values;
198};
199
200} // anonymous namespace
201
202bool performPhantomInsertion(Graph& graph)
203{
204 return runPhase<PhantomInsertionPhase>(graph);
205}
206
207} } // namespace JSC::DFG
208
209#endif // ENABLE(DFG_JIT)
210
211