1/*
2 * Copyright (C) 2015-2019 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 constexpr 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 m_values.operand(reg) = nullptr;
157
158 // We only need to insert a Phantom if the node hasn't been used since the last
159 // exit, and was born before the last exit.
160 if (killedNode->epoch() == currentEpoch)
161 return;
162
163 if (DFGPhantomInsertionPhaseInternal::verbose) {
164 dataLog(
165 " Inserting Phantom on ", killedNode, " after ",
166 block->at(lastExitingIndex), "\n");
167 }
168
169 // We have exact ref counts, so creating a new use means that we have to
170 // increment the ref count.
171 killedNode->postfixRef();
172
173 Node* lastExitingNode = block->at(lastExitingIndex);
174
175 m_insertionSet.insertNode(
176 lastExitingIndex + 1, SpecNone, Phantom,
177 lastExitingNode->origin.forInsertingAfter(m_graph, lastExitingNode),
178 killedNode->defaultEdge());
179 };
180
181 if (node->op() == SetLocal) {
182 VirtualRegister local = node->local();
183 if (nodeMayExit) {
184 // If the SetLocal does exit, we need the MovHint of its local
185 // to be live until the SetLocal is done.
186 processKilledOperand(local);
187 alreadyKilled = local;
188 }
189 m_values.operand(local) = nullptr;
190 }
191
192 forAllKilledOperands(m_graph, node, block->tryAt(nodeIndex + 1), processKilledOperand);
193 }
194
195 m_insertionSet.execute(block);
196 }
197
198 InsertionSet m_insertionSet;
199 Operands<Node*> m_values;
200};
201
202} // anonymous namespace
203
204bool performPhantomInsertion(Graph& graph)
205{
206 return runPhase<PhantomInsertionPhase>(graph);
207}
208
209} } // namespace JSC::DFG
210
211#endif // ENABLE(DFG_JIT)
212
213