561b9540ab84189f9af145ef037738a1bacb07b8
[WebKit-https.git] / Source / JavaScriptCore / b3 / B3LowerMacros.cpp
1 /*
2  * Copyright (C) 2015-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 "B3LowerMacros.h"
28
29 #if ENABLE(B3_JIT)
30
31 #include "AllowMacroScratchRegisterUsage.h"
32 #include "B3BasicBlockInlines.h"
33 #include "B3BlockInsertionSet.h"
34 #include "B3CCallValue.h"
35 #include "B3CaseCollectionInlines.h"
36 #include "B3ConstPtrValue.h"
37 #include "B3InsertionSetInlines.h"
38 #include "B3MemoryValue.h"
39 #include "B3PatchpointValue.h"
40 #include "B3PhaseScope.h"
41 #include "B3ProcedureInlines.h"
42 #include "B3StackmapGenerationParams.h"
43 #include "B3SwitchValue.h"
44 #include "B3UpsilonValue.h"
45 #include "B3ValueInlines.h"
46 #include "CCallHelpers.h"
47 #include "LinkBuffer.h"
48 #include <cmath>
49 #include <wtf/BitVector.h>
50
51 namespace JSC { namespace B3 {
52
53 namespace {
54
55 class LowerMacros {
56 public:
57     LowerMacros(Procedure& proc)
58         : m_proc(proc)
59         , m_blockInsertionSet(proc)
60         , m_insertionSet(proc)
61     {
62     }
63
64     bool run()
65     {
66         for (BasicBlock* block : m_proc) {
67             m_block = block;
68             processCurrentBlock();
69         }
70         m_changed |= m_blockInsertionSet.execute();
71         if (m_changed) {
72             m_proc.resetReachability();
73             m_proc.invalidateCFG();
74         }
75         return m_changed;
76     }
77     
78 private:
79     void processCurrentBlock()
80     {
81         for (m_index = 0; m_index < m_block->size(); ++m_index) {
82             m_value = m_block->at(m_index);
83             m_origin = m_value->origin();
84             switch (m_value->opcode()) {
85             case Mod: {
86                 double (*fmodDouble)(double, double) = fmod;
87                 if (m_value->type() == Double) {
88                     Value* functionAddress = m_insertionSet.insert<ConstPtrValue>(m_index, m_origin, fmodDouble);
89                     Value* result = m_insertionSet.insert<CCallValue>(m_index, Double, m_origin,
90                         Effects::none(),
91                         functionAddress,
92                         m_value->child(0),
93                         m_value->child(1));
94                     m_value->replaceWithIdentity(result);
95                     m_changed = true;
96                 } else if (m_value->type() == Float) {
97                     Value* numeratorAsDouble = m_insertionSet.insert<Value>(m_index, FloatToDouble, m_origin, m_value->child(0));
98                     Value* denominatorAsDouble = m_insertionSet.insert<Value>(m_index, FloatToDouble, m_origin, m_value->child(1));
99                     Value* functionAddress = m_insertionSet.insert<ConstPtrValue>(m_index, m_origin, fmodDouble);
100                     Value* doubleMod = m_insertionSet.insert<CCallValue>(m_index, Double, m_origin,
101                         Effects::none(),
102                         functionAddress,
103                         numeratorAsDouble,
104                         denominatorAsDouble);
105                     Value* result = m_insertionSet.insert<Value>(m_index, DoubleToFloat, m_origin, doubleMod);
106                     m_value->replaceWithIdentity(result);
107                     m_changed = true;
108                 } else if (isARM64()) {
109                     Value* divResult = m_insertionSet.insert<Value>(m_index, ChillDiv, m_origin, m_value->child(0), m_value->child(1));
110                     Value* multipliedBack = m_insertionSet.insert<Value>(m_index, Mul, m_origin, divResult, m_value->child(1));
111                     Value* result = m_insertionSet.insert<Value>(m_index, Sub, m_origin, m_value->child(0), multipliedBack);
112                     m_value->replaceWithIdentity(result);
113                     m_changed = true;
114                 }
115                 break;
116             }
117             case ChillDiv: {
118                 makeDivisionChill(Div);
119                 break;
120             }
121
122             case ChillMod: {
123                 if (isARM64()) {
124                     BasicBlock* before = m_blockInsertionSet.splitForward(m_block, m_index, &m_insertionSet);
125                     BasicBlock* zeroDenCase = m_blockInsertionSet.insertBefore(m_block);
126                     BasicBlock* normalModCase = m_blockInsertionSet.insertBefore(m_block);
127
128                     before->replaceLastWithNew<Value>(m_proc, Branch, m_origin, m_value->child(1));
129                     before->setSuccessors(
130                         FrequentedBlock(normalModCase, FrequencyClass::Normal),
131                         FrequentedBlock(zeroDenCase, FrequencyClass::Rare));
132
133                     Value* divResult = normalModCase->appendNew<Value>(m_proc, ChillDiv, m_origin, m_value->child(0), m_value->child(1));
134                     Value* multipliedBack = normalModCase->appendNew<Value>(m_proc, Mul, m_origin, divResult, m_value->child(1));
135                     Value* result = normalModCase->appendNew<Value>(m_proc, Sub, m_origin, m_value->child(0), multipliedBack);
136                     UpsilonValue* normalResult = normalModCase->appendNew<UpsilonValue>(m_proc, m_origin, result);
137                     normalModCase->appendNew<Value>(m_proc, Jump, m_origin);
138                     normalModCase->setSuccessors(FrequentedBlock(m_block));
139
140                     UpsilonValue* zeroResult = zeroDenCase->appendNew<UpsilonValue>(
141                         m_proc, m_origin,
142                         zeroDenCase->appendIntConstant(m_proc, m_value, 0));
143                     zeroDenCase->appendNew<Value>(m_proc, Jump, m_origin);
144                     zeroDenCase->setSuccessors(FrequentedBlock(m_block));
145
146                     Value* phi = m_insertionSet.insert<Value>(m_index, Phi, m_value->type(), m_origin);
147                     normalResult->setPhi(phi);
148                     zeroResult->setPhi(phi);
149                     m_value->replaceWithIdentity(phi);
150                     m_changed = true;
151                 } else
152                     makeDivisionChill(Mod);
153                 break;
154             }
155
156             case Switch: {
157                 SwitchValue* switchValue = m_value->as<SwitchValue>();
158                 Vector<SwitchCase> cases;
159                 for (const SwitchCase& switchCase : switchValue->cases(m_block))
160                     cases.append(switchCase);
161                 std::sort(
162                     cases.begin(), cases.end(),
163                     [] (const SwitchCase& left, const SwitchCase& right) {
164                         return left.caseValue() < right.caseValue();
165                     });
166                 FrequentedBlock fallThrough = m_block->fallThrough();
167                 m_block->values().removeLast();
168                 recursivelyBuildSwitch(cases, fallThrough, 0, false, cases.size(), m_block);
169                 m_proc.deleteValue(switchValue);
170                 m_block->updatePredecessorsAfter();
171                 m_changed = true;
172                 break;
173             }
174
175             default:
176                 break;
177             }
178         }
179         m_insertionSet.execute(m_block);
180     }
181
182     void makeDivisionChill(Opcode nonChillOpcode)
183     {
184         ASSERT(nonChillOpcode == Div || nonChillOpcode == Mod);
185
186         // ARM supports this instruction natively.
187         if (isARM64())
188             return;
189
190         // We implement "res = ChillDiv/ChillMod(num, den)" as follows:
191         //
192         //     if (den + 1 <=_unsigned 1) {
193         //         if (!den) {
194         //             res = 0;
195         //             goto done;
196         //         }
197         //         if (num == -2147483648) {
198         //             res = isDiv ? num : 0;
199         //             goto done;
200         //         }
201         //     }
202         //     res = num (/ or %) dev;
203         // done:
204         m_changed = true;
205
206         Value* num = m_value->child(0);
207         Value* den = m_value->child(1);
208
209         Value* one = m_insertionSet.insertIntConstant(m_index, m_value, 1);
210         Value* isDenOK = m_insertionSet.insert<Value>(
211             m_index, Above, m_origin,
212             m_insertionSet.insert<Value>(m_index, Add, m_origin, den, one),
213             one);
214
215         BasicBlock* before = m_blockInsertionSet.splitForward(m_block, m_index, &m_insertionSet);
216
217         BasicBlock* normalDivCase = m_blockInsertionSet.insertBefore(m_block);
218         BasicBlock* shadyDenCase = m_blockInsertionSet.insertBefore(m_block);
219         BasicBlock* zeroDenCase = m_blockInsertionSet.insertBefore(m_block);
220         BasicBlock* neg1DenCase = m_blockInsertionSet.insertBefore(m_block);
221         BasicBlock* intMinCase = m_blockInsertionSet.insertBefore(m_block);
222
223         before->replaceLastWithNew<Value>(m_proc, Branch, m_origin, isDenOK);
224         before->setSuccessors(
225             FrequentedBlock(normalDivCase, FrequencyClass::Normal),
226             FrequentedBlock(shadyDenCase, FrequencyClass::Rare));
227
228         UpsilonValue* normalResult = normalDivCase->appendNew<UpsilonValue>(
229             m_proc, m_origin,
230             normalDivCase->appendNew<Value>(m_proc, nonChillOpcode, m_origin, num, den));
231         normalDivCase->appendNew<Value>(m_proc, Jump, m_origin);
232         normalDivCase->setSuccessors(FrequentedBlock(m_block));
233
234         shadyDenCase->appendNew<Value>(m_proc, Branch, m_origin, den);
235         shadyDenCase->setSuccessors(
236             FrequentedBlock(neg1DenCase, FrequencyClass::Normal),
237             FrequentedBlock(zeroDenCase, FrequencyClass::Rare));
238
239         UpsilonValue* zeroResult = zeroDenCase->appendNew<UpsilonValue>(
240             m_proc, m_origin,
241             zeroDenCase->appendIntConstant(m_proc, m_value, 0));
242         zeroDenCase->appendNew<Value>(m_proc, Jump, m_origin);
243         zeroDenCase->setSuccessors(FrequentedBlock(m_block));
244
245         int64_t badNumeratorConst = 0;
246         switch (m_value->type()) {
247         case Int32:
248             badNumeratorConst = std::numeric_limits<int32_t>::min();
249             break;
250         case Int64:
251             badNumeratorConst = std::numeric_limits<int64_t>::min();
252             break;
253         default:
254             ASSERT_NOT_REACHED();
255             badNumeratorConst = 0;
256         }
257
258         Value* badNumerator =
259             neg1DenCase->appendIntConstant(m_proc, m_value, badNumeratorConst);
260
261         neg1DenCase->appendNew<Value>(
262             m_proc, Branch, m_origin,
263             neg1DenCase->appendNew<Value>(
264                 m_proc, Equal, m_origin, num, badNumerator));
265         neg1DenCase->setSuccessors(
266             FrequentedBlock(intMinCase, FrequencyClass::Rare),
267             FrequentedBlock(normalDivCase, FrequencyClass::Normal));
268
269         Value* intMinResult = nonChillOpcode == Div ? badNumerator : intMinCase->appendIntConstant(m_proc, m_value, 0);
270         UpsilonValue* intMinResultUpsilon = intMinCase->appendNew<UpsilonValue>(
271             m_proc, m_origin, intMinResult);
272         intMinCase->appendNew<Value>(m_proc, Jump, m_origin);
273         intMinCase->setSuccessors(FrequentedBlock(m_block));
274
275         Value* phi = m_insertionSet.insert<Value>(
276             m_index, Phi, m_value->type(), m_origin);
277         normalResult->setPhi(phi);
278         zeroResult->setPhi(phi);
279         intMinResultUpsilon->setPhi(phi);
280
281         m_value->replaceWithIdentity(phi);
282         before->updatePredecessorsAfter();
283     }
284
285     void recursivelyBuildSwitch(
286         const Vector<SwitchCase>& cases, FrequentedBlock fallThrough, unsigned start, bool hardStart,
287         unsigned end, BasicBlock* before)
288     {
289         Value* child = m_value->child(0);
290         Type type = child->type();
291         
292         // It's a good idea to use a table-based switch in some cases: the number of cases has to be
293         // large enough and they have to be dense enough. This could probably be improved a lot. For
294         // example, we could still use a jump table in cases where the inputs are sparse so long as we
295         // shift off the uninteresting bits. On the other hand, it's not clear that this would
296         // actually be any better than what we have done here and it's not clear that it would be
297         // better than a binary switch.
298         const unsigned minCasesForTable = 7;
299         const unsigned densityLimit = 4;
300         if (end - start >= minCasesForTable) {
301             int64_t firstValue = cases[start].caseValue();
302             int64_t lastValue = cases[end - 1].caseValue();
303             if ((lastValue - firstValue + 1) / (end - start) < densityLimit) {
304                 BasicBlock* switchBlock = m_blockInsertionSet.insertAfter(m_block);
305                 Value* index = before->appendNew<Value>(
306                     m_proc, Sub, m_origin, child,
307                     before->appendIntConstant(m_proc, m_origin, type, firstValue));
308                 before->appendNew<Value>(
309                     m_proc, Branch, m_origin,
310                     before->appendNew<Value>(
311                         m_proc, Above, m_origin, index,
312                         before->appendIntConstant(m_proc, m_origin, type, lastValue - firstValue)));
313                 before->setSuccessors(fallThrough, FrequentedBlock(switchBlock));
314                 
315                 size_t tableSize = lastValue - firstValue + 1;
316                 
317                 if (index->type() != pointerType() && index->type() == Int32)
318                     index = switchBlock->appendNew<Value>(m_proc, ZExt32, m_origin, index);
319                 
320                 PatchpointValue* patchpoint =
321                     switchBlock->appendNew<PatchpointValue>(m_proc, Void, m_origin);
322
323                 // Even though this loads from the jump table, the jump table is immutable. For the
324                 // purpose of alias analysis, reading something immutable is like reading nothing.
325                 patchpoint->effects = Effects();
326                 patchpoint->effects.terminal = true;
327                 
328                 patchpoint->appendSomeRegister(index);
329                 patchpoint->numGPScratchRegisters++;
330                 // Technically, we don't have to clobber macro registers on X86_64. This is probably
331                 // OK though.
332                 patchpoint->clobber(RegisterSet::macroScratchRegisters());
333                 
334                 BitVector handledIndices;
335                 for (unsigned i = start; i < end; ++i) {
336                     FrequentedBlock block = cases[i].target();
337                     int64_t value = cases[i].caseValue();
338                     switchBlock->appendSuccessor(block);
339                     size_t index = value - firstValue;
340                     ASSERT(!handledIndices.get(index));
341                     handledIndices.set(index);
342                 }
343                 
344                 bool hasUnhandledIndex = false;
345                 for (unsigned i = 0; i < tableSize; ++i) {
346                     if (!handledIndices.get(i)) {
347                         hasUnhandledIndex = true;
348                         break;
349                     }
350                 }
351                 
352                 if (hasUnhandledIndex)
353                     switchBlock->appendSuccessor(fallThrough);
354
355                 patchpoint->setGenerator(
356                     [=] (CCallHelpers& jit, const StackmapGenerationParams& params) {
357                         AllowMacroScratchRegisterUsage allowScratch(jit);
358                         
359                         MacroAssemblerCodePtr* jumpTable = static_cast<MacroAssemblerCodePtr*>(
360                             params.proc().addDataSection(sizeof(MacroAssemblerCodePtr) * tableSize));
361                         
362                         GPRReg index = params[0].gpr();
363                         GPRReg scratch = params.gpScratch(0);
364                         
365                         jit.move(CCallHelpers::TrustedImmPtr(jumpTable), scratch);
366                         jit.jump(CCallHelpers::BaseIndex(scratch, index, CCallHelpers::timesPtr()));
367                         
368                         // These labels are guaranteed to be populated before either late paths or
369                         // link tasks run.
370                         Vector<Box<CCallHelpers::Label>> labels = params.successorLabels();
371                         
372                         jit.addLinkTask(
373                             [=] (LinkBuffer& linkBuffer) {
374                                 if (hasUnhandledIndex) {
375                                     MacroAssemblerCodePtr fallThrough =
376                                         linkBuffer.locationOf(*labels.last());
377                                     for (unsigned i = tableSize; i--;)
378                                         jumpTable[i] = fallThrough;
379                                 }
380                                 
381                                 unsigned labelIndex = 0;
382                                 for (unsigned tableIndex : handledIndices) {
383                                     jumpTable[tableIndex] =
384                                         linkBuffer.locationOf(*labels[labelIndex++]);
385                                 }
386                             });
387                     });
388                 return;
389             }
390         }
391         
392         // See comments in jit/BinarySwitch.cpp for a justification of this algorithm. The only
393         // thing we do differently is that we don't use randomness.
394
395         const unsigned leafThreshold = 3;
396
397         unsigned size = end - start;
398
399         if (size <= leafThreshold) {
400             bool allConsecutive = false;
401
402             if ((hardStart || (start && cases[start - 1].caseValue() == cases[start].caseValue() - 1))
403                 && end < cases.size()
404                 && cases[end - 1].caseValue() == cases[end].caseValue() - 1) {
405                 allConsecutive = true;
406                 for (unsigned i = 0; i < size - 1; ++i) {
407                     if (cases[start + i].caseValue() + 1 != cases[start + i + 1].caseValue()) {
408                         allConsecutive = false;
409                         break;
410                     }
411                 }
412             }
413
414             unsigned limit = allConsecutive ? size - 1 : size;
415             
416             for (unsigned i = 0; i < limit; ++i) {
417                 BasicBlock* nextCheck = m_blockInsertionSet.insertAfter(m_block);
418                 before->appendNew<Value>(
419                     m_proc, Branch, m_origin,
420                     before->appendNew<Value>(
421                         m_proc, Equal, m_origin, child,
422                         before->appendIntConstant(
423                             m_proc, m_origin, type,
424                             cases[start + i].caseValue())));
425                 before->setSuccessors(cases[start + i].target(), FrequentedBlock(nextCheck));
426
427                 before = nextCheck;
428             }
429
430             before->appendNew<Value>(m_proc, Jump, m_origin);
431             if (allConsecutive)
432                 before->setSuccessors(cases[end - 1].target());
433             else
434                 before->setSuccessors(fallThrough);
435             return;
436         }
437
438         unsigned medianIndex = (start + end) / 2;
439
440         BasicBlock* left = m_blockInsertionSet.insertAfter(m_block);
441         BasicBlock* right = m_blockInsertionSet.insertAfter(m_block);
442
443         before->appendNew<Value>(
444             m_proc, Branch, m_origin,
445             before->appendNew<Value>(
446                 m_proc, LessThan, m_origin, child,
447                 before->appendIntConstant(
448                     m_proc, m_origin, type,
449                     cases[medianIndex].caseValue())));
450         before->setSuccessors(FrequentedBlock(left), FrequentedBlock(right));
451
452         recursivelyBuildSwitch(cases, fallThrough, start, hardStart, medianIndex, left);
453         recursivelyBuildSwitch(cases, fallThrough, medianIndex, true, end, right);
454     }
455     
456     Procedure& m_proc;
457     BlockInsertionSet m_blockInsertionSet;
458     InsertionSet m_insertionSet;
459     BasicBlock* m_block;
460     unsigned m_index;
461     Value* m_value;
462     Origin m_origin;
463     bool m_changed { false };
464 };
465
466 bool lowerMacrosImpl(Procedure& proc)
467 {
468     LowerMacros lowerMacros(proc);
469     return lowerMacros.run();
470 }
471
472 } // anonymous namespace
473
474 bool lowerMacros(Procedure& proc)
475 {
476     PhaseScope phaseScope(proc, "lowerMacros");
477     bool result = lowerMacrosImpl(proc);
478     if (shouldValidateIR())
479         RELEASE_ASSERT(!lowerMacrosImpl(proc));
480     return result;
481 }
482
483 } } // namespace JSC::B3
484
485 #endif // ENABLE(B3_JIT)
486