1/*
2 * Copyright (C) 2016 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 "B3InferSwitches.h"
28
29#if ENABLE(B3_JIT)
30
31#include "B3BasicBlockInlines.h"
32#include "B3CaseCollectionInlines.h"
33#include "B3InsertionSetInlines.h"
34#include "B3PhaseScope.h"
35#include "B3ProcedureInlines.h"
36#include "B3SwitchValue.h"
37#include "B3UseCounts.h"
38#include "B3ValueInlines.h"
39#include <wtf/ListDump.h>
40
41namespace JSC { namespace B3 {
42
43namespace {
44
45namespace B3InferSwitchesInternal {
46static const bool verbose = false;
47}
48
49class InferSwitches {
50public:
51 InferSwitches(Procedure& proc)
52 : m_proc(proc)
53 , m_insertionSet(proc)
54 , m_useCounts(proc)
55 {
56 }
57
58 bool run()
59 {
60 if (B3InferSwitchesInternal::verbose)
61 dataLog("B3 before inferSwitches:\n", m_proc);
62
63 bool changed = true;
64 bool everChanged = false;
65 while (changed) {
66 changed = false;
67
68 if (B3InferSwitchesInternal::verbose)
69 dataLog("Performing fixpoint iteration:\n");
70
71 for (BasicBlock* block : m_proc)
72 changed |= attemptToMergeWithPredecessor(block);
73
74 everChanged |= changed;
75 }
76
77 if (everChanged) {
78 m_proc.resetReachability();
79 m_proc.invalidateCFG();
80
81 m_proc.deleteOrphans();
82
83 if (B3InferSwitchesInternal::verbose)
84 dataLog("B3 after inferSwitches:\n", m_proc);
85 return true;
86 }
87
88 return false;
89 }
90
91private:
92 bool attemptToMergeWithPredecessor(BasicBlock* block)
93 {
94 // No point in considering the root block. We also don't consider blocks with multiple
95 // predecessors, but we could handle this if we made this code a bit more general and we were
96 // not afraid of code bloat.
97 if (block->numPredecessors() != 1)
98 return false;
99
100 SwitchDescription description = describe(block);
101 if (B3InferSwitchesInternal::verbose)
102 dataLog("Description of primary block ", *block, ": ", description, "\n");
103 if (!description) {
104 if (B3InferSwitchesInternal::verbose)
105 dataLog(" Bailing because not switch-like.\n");
106 return false;
107 }
108
109 // We know that this block behaves like a switch. But we need to verify that it doesn't also
110 // perform any effects or do expensive things. We don't want to create a switch if that will
111 // make expensive things execute unconditionally. We're very conservative about how we define
112 // "expensive".
113 for (Value* value : *block) {
114 if (value->isFree())
115 continue;
116 if (value == description.extra)
117 continue;
118 if (value == description.branch)
119 continue;
120 if (B3InferSwitchesInternal::verbose)
121 dataLog(" Bailing because of ", deepDump(m_proc, value), "\n");
122 return false;
123 }
124
125 BasicBlock* predecessor = block->predecessor(0);
126 SwitchDescription predecessorDescription = describe(predecessor);
127 if (B3InferSwitchesInternal::verbose)
128 dataLog(" Description of predecessor block ", *predecessor, ": ", predecessorDescription, "\n");
129 if (!predecessorDescription) {
130 if (B3InferSwitchesInternal::verbose)
131 dataLog(" Bailing because not switch-like.\n");
132 return false;
133 }
134
135 // Both us and the predecessor are switch-like, but that doesn't mean that we're compatible.
136 // We may be switching on different values!
137 if (description.source != predecessorDescription.source) {
138 if (B3InferSwitchesInternal::verbose)
139 dataLog(" Bailing because sources don't match.\n");
140 return false;
141 }
142
143 // We expect that we are the fall-through destination of the predecessor. This is a bit of a
144 // goofy condition. If we were not the fall-through destination then our switch is probably
145 // just totally redundant and we should be getting rid of it. But we don't handle that here,
146 // yet.
147 if (predecessorDescription.fallThrough.block() != block) {
148 if (B3InferSwitchesInternal::verbose)
149 dataLog(" Bailing because fall-through of predecessor is not the primary block.\n");
150 return false;
151 }
152
153 // Make sure that there ain't no loops.
154 if (description.fallThrough.block() == block
155 || description.fallThrough.block() == predecessor) {
156 if (B3InferSwitchesInternal::verbose)
157 dataLog(" Bailing because of fall-through loop.\n");
158 return false;
159 }
160 for (SwitchCase switchCase : description.cases) {
161 if (switchCase.targetBlock() == block
162 || switchCase.targetBlock() == predecessor) {
163 if (B3InferSwitchesInternal::verbose)
164 dataLog(" Bailing because of loop in primary cases.\n");
165 return false;
166 }
167 }
168 for (SwitchCase switchCase : predecessorDescription.cases) {
169 if (switchCase.targetBlock() == block
170 || switchCase.targetBlock() == predecessor) {
171 if (B3InferSwitchesInternal::verbose)
172 dataLog(" Bailing because of loop in predecessor cases.\n");
173 return false;
174 }
175 }
176
177 if (B3InferSwitchesInternal::verbose)
178 dataLog(" Doing it!\n");
179 // We're committed to doing the thing.
180
181 // Delete the extra value from the predecessor, since that would break downstream inference
182 // on the next fixpoint iteration. We would think that this block is too expensive to merge
183 // because of the Equal or NotEqual value even though that value is dead! We know it's dead
184 // so we kill it ourselves.
185 for (Value* value : *predecessor) {
186 if (value == predecessorDescription.extra)
187 value->replaceWithNopIgnoringType();
188 }
189
190 // Insert all non-terminal values from our block into our predecessor. We definitely need to
191 // do this for constants. We must not do it for the extra value, since that would break
192 // downstream inference on the next fixpoint iteration. As a bonus, we don't do it for nops,
193 // so that we limit how big blocks get in this phase.
194 for (unsigned i = 0; i < block->size() - 1; ++i) {
195 Value* value = block->at(i);
196 if (value != description.extra && value->opcode() != Nop)
197 m_insertionSet.insertValue(predecessor->size() - 1, value);
198 }
199 m_insertionSet.execute(predecessor);
200 block->values().shrink(0);
201 block->appendNew<Value>(m_proc, Oops, description.branch->origin());
202 block->removePredecessor(predecessor);
203
204 for (BasicBlock* successorBlock : description.block->successorBlocks())
205 successorBlock->replacePredecessor(block, predecessor);
206
207 block->clearSuccessors();
208
209 SwitchValue* switchValue = predecessor->replaceLastWithNew<SwitchValue>(
210 m_proc, predecessor->last()->origin(), description.source);
211 predecessor->clearSuccessors();
212 switchValue->setFallThrough(description.fallThrough);
213
214 Vector<int64_t> predecessorCases;
215 for (SwitchCase switchCase : predecessorDescription.cases) {
216 switchValue->appendCase(switchCase);
217 predecessorCases.append(switchCase.caseValue());
218 }
219 std::sort(predecessorCases.begin(), predecessorCases.end());
220 auto isPredecessorCase = [&] (int64_t value) -> bool {
221 return !!tryBinarySearch<int64_t>(
222 predecessorCases, predecessorCases.size(), value,
223 [] (int64_t* element) -> int64_t { return *element; });
224 };
225
226 for (SwitchCase switchCase : description.cases) {
227 if (!isPredecessorCase(switchCase.caseValue()))
228 switchValue->appendCase(switchCase);
229 }
230 return true;
231 }
232
233 struct SwitchDescription {
234 SwitchDescription()
235 {
236 }
237
238 explicit operator bool() { return !!block; }
239
240 void dump(PrintStream& out) const
241 {
242 out.print(
243 "{block = ", pointerDump(block),
244 ", branch = ", pointerDump(branch),
245 ", extra = ", pointerDump(extra),
246 ", source = ", pointerDump(source),
247 ", cases = ", listDump(cases),
248 ", fallThrough = ", fallThrough, "}");
249 }
250
251 BasicBlock* block { nullptr };
252 Value* branch { nullptr };
253 Value* extra { nullptr }; // This is the Equal or NotEqual value, if applicable.
254 Value* source { nullptr };
255 Vector<SwitchCase, 1> cases;
256 FrequentedBlock fallThrough;
257 };
258
259 SwitchDescription describe(BasicBlock* block)
260 {
261 SwitchDescription result;
262 result.block = block;
263 result.branch = block->last();
264
265 switch (result.branch->opcode()) {
266 case Branch: {
267 Value* predicate = result.branch->child(0);
268 FrequentedBlock taken = result.block->taken();
269 FrequentedBlock notTaken = result.block->notTaken();
270 bool handled = false;
271 // NOTE: This uses UseCounts that we computed before any transformation. This is fine
272 // because although we may have mutated the IR, we would not have added any new
273 // predicates.
274 if (predicate->numChildren() == 2
275 && predicate->child(1)->hasInt()
276 && m_useCounts.numUses(predicate) == 1) {
277 switch (predicate->opcode()) {
278 case Equal:
279 result.source = predicate->child(0);
280 result.extra = predicate;
281 result.cases.append(SwitchCase(predicate->child(1)->asInt(), taken));
282 result.fallThrough = notTaken;
283 handled = true;
284 break;
285 case NotEqual:
286 result.source = predicate->child(0);
287 result.extra = predicate;
288 result.cases.append(SwitchCase(predicate->child(1)->asInt(), notTaken));
289 result.fallThrough = taken;
290 handled = true;
291 break;
292 default:
293 break;
294 }
295 }
296 if (handled)
297 break;
298 result.source = predicate;
299 result.cases.append(SwitchCase(0, notTaken));
300 result.fallThrough = taken;
301 break;
302 }
303
304 case Switch: {
305 SwitchValue* switchValue = result.branch->as<SwitchValue>();
306 result.source = switchValue->child(0);
307 for (SwitchCase switchCase : switchValue->cases(result.block))
308 result.cases.append(switchCase);
309 result.fallThrough = result.block->fallThrough();
310 break;
311 }
312
313 default:
314 result.block = nullptr;
315 result.branch = nullptr;
316 break;
317 }
318
319 return result;
320 }
321
322 Procedure& m_proc;
323 InsertionSet m_insertionSet;
324 UseCounts m_useCounts;
325};
326
327} // anonymous namespace
328
329bool inferSwitches(Procedure& proc)
330{
331 PhaseScope phaseScope(proc, "inferSwitches");
332 InferSwitches inferSwitches(proc);
333 return inferSwitches.run();
334}
335
336} } // namespace JSC::B3
337
338#endif // ENABLE(B3_JIT)
339
340