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 "B3FoldPathConstants.h"
28
29#if ENABLE(B3_JIT)
30
31#include "B3BasicBlockInlines.h"
32#include "B3CaseCollectionInlines.h"
33#include "B3Dominators.h"
34#include "B3InsertionSetInlines.h"
35#include "B3PhaseScope.h"
36#include "B3ProcedureInlines.h"
37#include "B3SwitchValue.h"
38#include "B3ValueInlines.h"
39
40namespace JSC { namespace B3 {
41
42namespace {
43
44namespace B3FoldPathConstantsInternal {
45static const bool verbose = false;
46}
47
48class FoldPathConstants {
49public:
50 FoldPathConstants(Procedure& proc)
51 : m_proc(proc)
52 , m_insertionSet(proc)
53 {
54 }
55
56 void run()
57 {
58 bool changed = false;
59
60 if (B3FoldPathConstantsInternal::verbose)
61 dataLog("B3 before folding path constants: \n", m_proc, "\n");
62
63 // Find all of the values that are the subject of a branch or switch. For any successor
64 // that we dominate, install a value override at that block.
65
66 HashMap<Value*, Vector<Override>> overrides;
67
68 Dominators& dominators = m_proc.dominators();
69
70 auto addOverride = [&] (
71 BasicBlock* from, Value* value, const Override& override) {
72
73 if (override.block->numPredecessors() != 1)
74 return;
75 ASSERT(override.block->predecessor(0) == from);
76
77 Vector<Override>& forValue =
78 overrides.add(value, Vector<Override>()).iterator->value;
79
80 if (!ASSERT_DISABLED) {
81 for (const Override& otherOverride : forValue)
82 ASSERT_UNUSED(otherOverride, otherOverride.block != override.block);
83 }
84
85 if (B3FoldPathConstantsInternal::verbose)
86 dataLog("Overriding ", *value, " from ", *from, ": ", override, "\n");
87
88 forValue.append(override);
89 };
90
91 for (BasicBlock* block : m_proc) {
92 Value* branch = block->last();
93 switch (branch->opcode()) {
94 case Branch:
95 if (block->successorBlock(0) == block->successorBlock(1))
96 continue;
97 addOverride(
98 block, branch->child(0),
99 Override::nonZero(block->successorBlock(0)));
100 addOverride(
101 block, branch->child(0),
102 Override::constant(block->successorBlock(1), 0));
103 break;
104 case Switch: {
105 SwitchValue* switchValue = branch->as<SwitchValue>();
106
107 HashMap<BasicBlock*, unsigned> targetUses;
108 for (SwitchCase switchCase : switchValue->cases(block))
109 targetUses.add(switchCase.targetBlock(), 0).iterator->value++;
110 targetUses.add(switchValue->fallThrough(block), 0).iterator->value++;
111
112 for (SwitchCase switchCase : switchValue->cases(block)) {
113 if (targetUses.find(switchCase.targetBlock())->value != 1)
114 continue;
115
116 addOverride(
117 block, branch->child(0),
118 Override::constant(switchCase.targetBlock(), switchCase.caseValue()));
119 }
120 break;
121 }
122 default:
123 break;
124 }
125 }
126
127 // Install the constants in the override blocks. We use one-shot insertion sets because
128 // each block will get at most one thing inserted into it anyway.
129 for (auto& entry : overrides) {
130 for (Override& override : entry.value) {
131 if (!override.hasValue)
132 continue;
133 override.valueNode =
134 m_insertionSet.insertIntConstant(0, entry.key, override.value);
135 m_insertionSet.execute(override.block);
136 }
137 }
138
139 // Replace all uses of a value that has an override with that override, if appropriate.
140 // Certain instructions get special treatment.
141 auto getOverride = [&] (BasicBlock* block, Value* value) -> Override {
142 auto iter = overrides.find(value);
143 if (iter == overrides.end())
144 return Override();
145
146 Vector<Override>& forValue = iter->value;
147 Override result;
148 for (Override& override : forValue) {
149 if (dominators.dominates(override.block, block)
150 && override.isBetterThan(result))
151 result = override;
152 }
153
154 if (B3FoldPathConstantsInternal::verbose)
155 dataLog("In block ", *block, " getting override for ", *value, ": ", result, "\n");
156
157 return result;
158 };
159
160 for (BasicBlock* block : m_proc) {
161 for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
162 Value* value = block->at(valueIndex);
163
164 switch (value->opcode()) {
165 case Branch: {
166 if (getOverride(block, value->child(0)).isNonZero) {
167 value->replaceWithJump(block, block->taken());
168 changed = true;
169 }
170 break;
171 }
172
173 case Equal: {
174 if (value->child(1)->isInt(0)
175 && getOverride(block, value->child(0)).isNonZero) {
176 value->replaceWithIdentity(
177 m_insertionSet.insertIntConstant(valueIndex, value, 0));
178 }
179 break;
180 }
181
182 case NotEqual: {
183 if (value->child(1)->isInt(0)
184 && getOverride(block, value->child(0)).isNonZero) {
185 value->replaceWithIdentity(
186 m_insertionSet.insertIntConstant(valueIndex, value, 1));
187 }
188 break;
189 }
190
191 default:
192 break;
193 }
194
195 for (Value*& child : value->children()) {
196 Override override = getOverride(block, child);
197 if (override.valueNode)
198 child = override.valueNode;
199 }
200 }
201 m_insertionSet.execute(block);
202 }
203
204 if (changed) {
205 m_proc.resetReachability();
206 m_proc.invalidateCFG();
207 }
208 }
209
210private:
211 struct Override {
212 Override()
213 {
214 }
215
216 static Override constant(BasicBlock* block, int64_t value)
217 {
218 Override result;
219 result.block = block;
220 result.hasValue = true;
221 result.value = value;
222 if (value)
223 result.isNonZero = true;
224 return result;
225 }
226
227 static Override nonZero(BasicBlock* block)
228 {
229 Override result;
230 result.block = block;
231 result.isNonZero = true;
232 return result;
233 }
234
235 bool isBetterThan(const Override& override)
236 {
237 if (hasValue && !override.hasValue)
238 return true;
239 if (isNonZero && !override.isNonZero)
240 return true;
241 return false;
242 }
243
244 void dump(PrintStream& out) const
245 {
246 out.print("{block = ", pointerDump(block), ", value = ");
247 if (hasValue)
248 out.print(value);
249 else
250 out.print("<none>");
251 out.print(", isNonZero = ", isNonZero);
252 if (valueNode)
253 out.print(", valueNode = ", *valueNode);
254 out.print("}");
255 }
256
257 BasicBlock* block { nullptr };
258 bool hasValue { false };
259 bool isNonZero { false };
260 int64_t value { 0 };
261 Value* valueNode { nullptr };
262 };
263
264 Procedure& m_proc;
265 InsertionSet m_insertionSet;
266};
267
268} // anonymous namespace
269
270void foldPathConstants(Procedure& proc)
271{
272 PhaseScope phaseScope(proc, "foldPathConstants");
273 FoldPathConstants foldPathConstants(proc);
274 foldPathConstants.run();
275}
276
277} } // namespace JSC::B3
278
279#endif // ENABLE(B3_JIT)
280
281