1/*
2 * Copyright (C) 2015-2017 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 "B3MoveConstants.h"
28
29#if ENABLE(B3_JIT)
30
31#include "AirArg.h"
32#include "B3BasicBlockInlines.h"
33#include "B3Dominators.h"
34#include "B3InsertionSetInlines.h"
35#include "B3MemoryValueInlines.h"
36#include "B3PhaseScope.h"
37#include "B3ProcedureInlines.h"
38#include "B3ValueInlines.h"
39#include "B3ValueKeyInlines.h"
40#include <wtf/HashMap.h>
41#include <wtf/Vector.h>
42
43namespace JSC { namespace B3 {
44
45namespace {
46
47class MoveConstants {
48public:
49 MoveConstants(Procedure& proc)
50 : m_proc(proc)
51 , m_insertionSet(proc)
52 {
53 }
54
55 void run()
56 {
57 hoistConstants(
58 [&] (const ValueKey& key) -> bool {
59 return key.opcode() == ConstFloat || key.opcode() == ConstDouble;
60 });
61
62 lowerFPConstants();
63
64 hoistConstants(
65 [&] (const ValueKey& key) -> bool {
66 return key.opcode() == Const32 || key.opcode() == Const64 || key.opcode() == ArgumentReg;
67 });
68 }
69
70private:
71 template<typename Filter>
72 void hoistConstants(const Filter& filter)
73 {
74 Dominators& dominators = m_proc.dominators();
75 HashMap<ValueKey, Value*> valueForConstant;
76 IndexMap<BasicBlock*, Vector<Value*>> materializations(m_proc.size());
77
78 // We determine where things get materialized based on where they are used.
79 for (BasicBlock* block : m_proc) {
80 for (Value* value : *block) {
81 for (Value*& child : value->children()) {
82 ValueKey key = child->key();
83 if (!filter(key))
84 continue;
85
86 auto result = valueForConstant.add(key, child);
87 if (result.isNewEntry) {
88 // Assume that this block is where we want to materialize the value.
89 child->owner = block;
90 continue;
91 }
92
93 // Make 'value' use the canonical constant rather than the one it was using.
94 child = result.iterator->value;
95
96 // Determine the least common dominator. That's the lowest place in the CFG where
97 // we could materialize the constant while still having only one materialization
98 // in the resulting code.
99 while (!dominators.dominates(child->owner, block))
100 child->owner = dominators.idom(child->owner);
101 }
102 }
103 }
104
105 // Make sure that each basic block knows what to materialize. This also refines the
106 // materialization block based on execution frequency. It finds the minimum block frequency
107 // of all of its dominators, and selects the closest block amongst those that are tied for
108 // lowest frequency.
109 for (auto& entry : valueForConstant) {
110 Value* value = entry.value;
111 for (BasicBlock* block = value->owner; block; block = dominators.idom(block)) {
112 if (block->frequency() < value->owner->frequency())
113 value->owner = block;
114 }
115 materializations[value->owner].append(value);
116 }
117
118 // Get rid of Value's that are fast constants but aren't canonical. Also remove the canonical
119 // ones from the CFG, since we're going to reinsert them elsewhere.
120 for (BasicBlock* block : m_proc) {
121 for (Value*& value : *block) {
122 ValueKey key = value->key();
123 if (!filter(key))
124 continue;
125
126 if (valueForConstant.get(key) == value)
127 value = m_proc.add<Value>(Nop, value->origin());
128 else
129 value->replaceWithNopIgnoringType();
130 }
131 }
132
133 // Now make sure that we move constants to where they are supposed to go. Again, we do this
134 // based on uses.
135 for (BasicBlock* block : m_proc) {
136 for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
137 Value* value = block->at(valueIndex);
138
139 // This finds the outermost (best) block last. So, the functor overrides the result
140 // each time it finds something acceptable.
141 auto findBestConstant = [&] (const auto& predicate) -> Value* {
142 Value* result = nullptr;
143 dominators.forAllDominatorsOf(
144 block,
145 [&] (BasicBlock* dominator) {
146 for (Value* value : materializations[dominator]) {
147 if (predicate(value)) {
148 result = value;
149 break;
150 }
151 }
152 });
153 return result;
154 };
155
156 // We call this when we have found a constant that we'd like to use. It's possible that
157 // we have computed that the constant should be materialized in this block, but we
158 // haven't inserted it yet. This inserts the constant if necessary.
159 auto materialize = [&] (Value* child) {
160 ValueKey key = child->key();
161 if (!filter(key))
162 return;
163
164 // If we encounter a fast constant, then it must be canonical, since we already
165 // got rid of the non-canonical ones.
166 ASSERT(valueForConstant.get(key) == child);
167
168 if (child->owner != block) {
169 // This constant isn't our problem. It's going to be materialized in another
170 // block.
171 return;
172 }
173
174 // We're supposed to materialize this constant in this block, and we haven't
175 // done it yet.
176 m_insertionSet.insertValue(valueIndex, child);
177 child->owner = nullptr;
178 };
179
180 if (MemoryValue* memoryValue = value->as<MemoryValue>()) {
181 Value* pointer = memoryValue->lastChild();
182 if (pointer->hasIntPtr() && filter(pointer->key())) {
183 auto desiredOffset = [&] (Value* otherPointer) -> intptr_t {
184 // We would turn this:
185 //
186 // Load(@p, offset = c)
187 //
188 // into this:
189 //
190 // Load(@q, offset = ?)
191 //
192 // The offset should be c + @p - @q, because then we're loading from:
193 //
194 // @q + c + @p - @q
195 uintptr_t c = static_cast<uintptr_t>(static_cast<intptr_t>(memoryValue->offset()));
196 uintptr_t p = pointer->asIntPtr();
197 uintptr_t q = otherPointer->asIntPtr();
198 return c + p - q;
199 };
200
201 Value* bestPointer = findBestConstant(
202 [&] (Value* candidatePointer) -> bool {
203 if (!candidatePointer->hasIntPtr())
204 return false;
205
206 int64_t offset = desiredOffset(candidatePointer);
207 return memoryValue->isLegalOffset(offset);
208 });
209
210 if (bestPointer) {
211 memoryValue->lastChild() = bestPointer;
212 memoryValue->setOffset(static_cast<int32_t>(desiredOffset(bestPointer)));
213 }
214 }
215 } else {
216 switch (value->opcode()) {
217 case Add:
218 case Sub: {
219 Value* addend = value->child(1);
220 if (!addend->hasInt() || !filter(addend->key()))
221 break;
222 int64_t addendConst = addend->asInt();
223 Value* bestAddend = findBestConstant(
224 [&] (Value* candidateAddend) -> bool {
225 if (candidateAddend->type() != addend->type())
226 return false;
227 if (!candidateAddend->hasInt())
228 return false;
229 return candidateAddend == addend
230 || candidateAddend->asInt() == -addendConst;
231 });
232 if (!bestAddend || bestAddend == addend)
233 break;
234 materialize(value->child(0));
235 materialize(bestAddend);
236 value->replaceWithIdentity(
237 m_insertionSet.insert<Value>(
238 valueIndex, value->opcode() == Add ? Sub : Add, value->origin(),
239 value->child(0), bestAddend));
240 break;
241 }
242 default:
243 break;
244 }
245 }
246
247 for (Value* child : value->children())
248 materialize(child);
249 }
250
251 // We may have some constants that need to be materialized right at the end of this
252 // block.
253 for (Value* value : materializations[block]) {
254 if (!value->owner) {
255 // It's already materialized in this block.
256 continue;
257 }
258
259 m_insertionSet.insertValue(block->size() - 1, value);
260 }
261 m_insertionSet.execute(block);
262 }
263 }
264
265 void lowerFPConstants()
266 {
267 for (Value* value : m_proc.values()) {
268 ValueKey key = value->key();
269 if (goesInTable(key))
270 m_constTable.add(key, m_constTable.size());
271 }
272
273 m_dataSection = static_cast<int64_t*>(m_proc.addDataSection(m_constTable.size() * sizeof(int64_t)));
274 for (auto& entry : m_constTable)
275 m_dataSection[entry.value] = entry.key.value();
276
277 IndexSet<Value*> offLimits;
278 for (BasicBlock* block : m_proc) {
279 for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
280 StackmapValue* value = block->at(valueIndex)->as<StackmapValue>();
281 if (!value)
282 continue;
283
284 for (unsigned childIndex = 0; childIndex < value->numChildren(); ++childIndex) {
285 if (!value->constrainedChild(childIndex).rep().isAny())
286 continue;
287
288 Value*& child = value->child(childIndex);
289 ValueKey key = child->key();
290 if (!goesInTable(key))
291 continue;
292
293 child = m_insertionSet.insertValue(
294 valueIndex, key.materialize(m_proc, value->origin()));
295 offLimits.add(child);
296 }
297 }
298
299 m_insertionSet.execute(block);
300 }
301
302 for (BasicBlock* block : m_proc) {
303 for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
304 Value* value = block->at(valueIndex);
305 ValueKey key = value->key();
306 if (!goesInTable(key))
307 continue;
308 if (offLimits.contains(value))
309 continue;
310
311 auto offset = sizeof(int64_t) * m_constTable.get(key);
312 if (!isRepresentableAs<Value::OffsetType>(offset))
313 continue;
314
315 Value* tableBase = m_insertionSet.insertIntConstant(
316 valueIndex, value->origin(), pointerType(),
317 bitwise_cast<intptr_t>(m_dataSection));
318 Value* result = m_insertionSet.insert<MemoryValue>(
319 valueIndex, Load, value->type(), value->origin(), tableBase,
320 static_cast<Value::OffsetType>(offset));
321 value->replaceWithIdentity(result);
322 }
323
324 m_insertionSet.execute(block);
325 }
326 }
327
328 bool goesInTable(const ValueKey& key)
329 {
330 return (key.opcode() == ConstDouble && key != doubleZero())
331 || (key.opcode() == ConstFloat && key != floatZero());
332 }
333
334 static ValueKey doubleZero()
335 {
336 return ValueKey(ConstDouble, Double, 0.0);
337 }
338
339 static ValueKey floatZero()
340 {
341 return ValueKey(ConstFloat, Float, 0.0);
342 }
343
344 Procedure& m_proc;
345 HashMap<ValueKey, unsigned> m_constTable;
346 int64_t* m_dataSection;
347 InsertionSet m_insertionSet;
348};
349
350} // anonymous namespace
351
352void moveConstants(Procedure& proc)
353{
354 PhaseScope phaseScope(proc, "moveConstants");
355 MoveConstants moveConstants(proc);
356 moveConstants.run();
357}
358
359} } // namespace JSC::B3
360
361#endif // ENABLE(B3_JIT)
362
363