1/*
2 * Copyright (C) 2014 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#pragma once
27
28#if ENABLE(DFG_JIT)
29
30#include "DFGDominators.h"
31#include "DFGGraph.h"
32
33namespace JSC { namespace DFG {
34
35// SSACalculator provides a reusable tool for using the Cytron, Ferrante, Rosen, Wegman, and
36// Zadeck "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph"
37// (TOPLAS'91) algorithm for computing SSA. SSACalculator doesn't magically do everything for you
38// but it maintains the major data structures and handles most of the non-local reasoning. Here's
39// the workflow of using SSACalculator to execute this algorithm:
40//
41// 0) Create a fresh SSACalculator instance. You will need this instance only for as long as
42// you're not yet done computing SSA.
43//
44// 1) Create an SSACalculator::Variable for every variable that you want to do Phi insertion
45// on. SSACalculator::Variable::index() is a dense indexing of the Variables that you
46// created, so you can easily use a Vector to map the SSACalculator::Variables to your
47// variables.
48//
49// 2) Create a SSACalculator::Def for every assignment to those variables. A Def knows about the
50// variable, the block, and the DFG::Node* that has the value being put into the variable.
51// Note that creating a Def in block B for variable V if block B already has a def for variable
52// V will overwrite the previous Def's DFG::Node* value. This enables you to create Defs by
53// processing basic blocks in forward order. If a block has multiple Defs of a variable, this
54// "just works" because each block will then remember the last Def of each variable.
55//
56// 3) Call SSACalculator::computePhis(). This takes a functor that will create the Phi nodes. The
57// functor returns either the Phi node it created, or nullptr, if it chooses to prune. (As an
58// aside, it's always sound not to prune, and the safest reason for pruning is liveness.) The
59// computePhis() code will record the created Phi nodes as Defs, and it will separately record
60// the list of Phis inserted at each block. It's OK for the functor you pass here to modify the
61// DFG::Graph on the fly, but the easiest way to write this is to just create the Phi nodes by
62// doing Graph::addNode() and return them. It's then best to insert all Phi nodes for a block
63// in bulk as part of the pass you do below, in step (4).
64//
65// 4) Modify the graph to create the SSA data flow. For each block, this should:
66//
67// 4.0) Compute the set of reaching defs (aka available values) for each variable by calling
68// SSACalculator::reachingDefAtHead() for each variable. Record this in a local table that
69// will be incrementally updated as you proceed through the block in forward order in the
70// next steps:
71//
72// FIXME: It might be better to compute reaching defs for all live variables in one go, to
73// avoid doing repeated dom tree traversals.
74// https://bugs.webkit.org/show_bug.cgi?id=136610
75//
76// 4.1) Insert all of the Phi nodes for the block by using SSACalculator::phisForBlock(), and
77// record those Phi nodes as being available values.
78//
79// 4.2) Process the block in forward order. For each load from a variable, replace it with the
80// available SSA value for that variable. For each store, delete it and record the stored
81// value as being available.
82//
83// Note that you have two options of how to replace loads with SSA values. You can replace
84// the load with an Identity node; this will end up working fairly naturally so long as
85// you run GCSE after your phase. Or, you can replace all uses of the load with the SSA
86// value yourself (using the Graph::performSubstitution() idiom), but that requires that
87// your loop over basic blocks proceeds in the appropriate graph order, for example
88// preorder.
89//
90// FIXME: Make it easier to do this, that doesn't involve rerunning GCSE.
91// https://bugs.webkit.org/show_bug.cgi?id=136639
92//
93// 4.3) Insert Upsilons at the end of the current block for the corresponding Phis in each successor block.
94// Use the available values table to decide the source value for each Phi's variable. Note that
95// you could also use SSACalculator::reachingDefAtTail() instead of the available values table,
96// though your local available values table is likely to be more efficient.
97//
98// The most obvious use of SSACalculator is for the CPS->SSA conversion itself, but it's meant to
99// also be used for SSA update and for things like the promotion of heap fields to local SSA
100// variables.
101
102class SSACalculator {
103public:
104 SSACalculator(Graph&);
105 ~SSACalculator();
106
107 void reset();
108
109 class Variable {
110 public:
111 unsigned index() const { return m_index; }
112
113 void dump(PrintStream&) const;
114 void dumpVerbose(PrintStream&) const;
115
116 private:
117 friend class SSACalculator;
118
119 Variable()
120 : m_index(UINT_MAX)
121 {
122 }
123
124 Variable(unsigned index)
125 : m_index(index)
126 {
127 }
128
129 BlockList m_blocksWithDefs;
130 unsigned m_index;
131 };
132
133 class Def {
134 public:
135 Variable* variable() const { return m_variable; }
136 BasicBlock* block() const { return m_block; }
137
138 Node* value() const { return m_value; }
139
140 void dump(PrintStream&) const;
141
142 private:
143 friend class SSACalculator;
144
145 Def()
146 : m_variable(nullptr)
147 , m_block(nullptr)
148 , m_value(nullptr)
149 {
150 }
151
152 Def(Variable* variable, BasicBlock* block, Node* value)
153 : m_variable(variable)
154 , m_block(block)
155 , m_value(value)
156 {
157 }
158
159 Variable* m_variable;
160 BasicBlock* m_block;
161 Node* m_value;
162 };
163
164 Variable* newVariable();
165 Def* newDef(Variable*, BasicBlock*, Node*);
166
167 Variable* variable(unsigned index) { return &m_variables[index]; }
168
169 // The PhiInsertionFunctor takes a Variable and a BasicBlock and either inserts a Phi and
170 // returns the Node for that Phi, or it decides that it's not worth it to insert a Phi at that
171 // block because of some additional pruning condition (typically liveness) and returns
172 // nullptr. If a non-null Node* is returned, a new Def is created, so that
173 // nonLocalReachingDef() will find it later. Note that it is generally always sound to not
174 // prune any Phis (that is, to always have the functor insert a Phi and never return nullptr).
175 template<typename PhiInsertionFunctor>
176 void computePhis(const PhiInsertionFunctor& functor)
177 {
178 DFG_ASSERT(m_graph, nullptr, m_graph.m_ssaDominators);
179
180 for (Variable& variable : m_variables) {
181 m_graph.m_ssaDominators->forAllBlocksInPrunedIteratedDominanceFrontierOf(
182 variable.m_blocksWithDefs,
183 [&] (BasicBlock* block) -> bool {
184 Node* phiNode = functor(&variable, block);
185 if (!phiNode)
186 return false;
187
188 BlockData& data = m_data[block];
189 Def* phiDef = m_phis.add(Def(&variable, block, phiNode));
190 data.m_phis.append(phiDef);
191
192 // Note that it's possible to have a block that looks like this before SSA
193 // conversion:
194 //
195 // label:
196 // print(x);
197 // ...
198 // x = 42;
199 // goto label;
200 //
201 // And it may look like this after SSA conversion:
202 //
203 // label:
204 // x1: Phi()
205 // ...
206 // Upsilon(42, ^x1)
207 // goto label;
208 //
209 // In this case, we will want to insert a Phi in this block, and the block
210 // will already have a Def for the variable. When this happens, we don't want
211 // the Phi to override the original Def, since the Phi is at the top, the
212 // original Def in the m_defs table would have been at the bottom, and we want
213 // m_defs to tell us about defs at tail.
214 //
215 // So, we rely on the fact that HashMap::add() does nothing if the key was
216 // already present.
217 data.m_defs.add(&variable, phiDef);
218 return true;
219 });
220 }
221 }
222
223 const Vector<Def*>& phisForBlock(BasicBlock* block)
224 {
225 return m_data[block].m_phis;
226 }
227
228 // Ignores defs within the given block; it assumes that you've taken care of those
229 // yourself.
230 Def* nonLocalReachingDef(BasicBlock*, Variable*);
231 Def* reachingDefAtHead(BasicBlock* block, Variable* variable)
232 {
233 return nonLocalReachingDef(block, variable);
234 }
235
236 // Considers the def within the given block, but only works at the tail of the block.
237 Def* reachingDefAtTail(BasicBlock*, Variable*);
238
239 void dump(PrintStream&) const;
240
241private:
242 SegmentedVector<Variable> m_variables;
243 Bag<Def> m_defs;
244
245 Bag<Def> m_phis;
246
247 struct BlockData {
248 HashMap<Variable*, Def*> m_defs;
249 Vector<Def*> m_phis;
250 };
251
252 BlockMap<BlockData> m_data;
253
254 Graph& m_graph;
255};
256
257} } // namespace JSC::DFG
258
259#endif // ENABLE(DFG_JIT)
260