B3::lowerMacros forgets to before->updatePredecessorsAfter() when lowering ChillMod...
[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                     before->updatePredecessorsAfter();
151                     m_changed = true;
152                 } else
153                     makeDivisionChill(Mod);
154                 break;
155             }
156
157             case Switch: {
158                 SwitchValue* switchValue = m_value->as<SwitchValue>();
159                 Vector<SwitchCase> cases;
160                 for (const SwitchCase& switchCase : switchValue->cases(m_block))
161                     cases.append(switchCase);
162                 std::sort(
163                     cases.begin(), cases.end(),
164                     [] (const SwitchCase& left, const SwitchCase& right) {
165                         return left.caseValue() < right.caseValue();
166                     });
167                 FrequentedBlock fallThrough = m_block->fallThrough();
168                 m_block->values().removeLast();
169                 recursivelyBuildSwitch(cases, fallThrough, 0, false, cases.size(), m_block);
170                 m_proc.deleteValue(switchValue);
171                 m_block->updatePredecessorsAfter();
172                 m_changed = true;
173                 break;
174             }
175
176             default:
177                 break;
178             }
179         }
180         m_insertionSet.execute(m_block);
181     }
182
183     void makeDivisionChill(Opcode nonChillOpcode)
184     {
185         ASSERT(nonChillOpcode == Div || nonChillOpcode == Mod);
186
187         // ARM supports this instruction natively.
188         if (isARM64())
189             return;
190
191         // We implement "res = ChillDiv/ChillMod(num, den)" as follows:
192         //
193         //     if (den + 1 <=_unsigned 1) {
194         //         if (!den) {
195         //             res = 0;
196         //             goto done;
197         //         }
198         //         if (num == -2147483648) {
199         //             res = isDiv ? num : 0;
200         //             goto done;
201         //         }
202         //     }
203         //     res = num (/ or %) dev;
204         // done:
205         m_changed = true;
206
207         Value* num = m_value->child(0);
208         Value* den = m_value->child(1);
209
210         Value* one = m_insertionSet.insertIntConstant(m_index, m_value, 1);
211         Value* isDenOK = m_insertionSet.insert<Value>(
212             m_index, Above, m_origin,
213             m_insertionSet.insert<Value>(m_index, Add, m_origin, den, one),
214             one);
215
216         BasicBlock* before = m_blockInsertionSet.splitForward(m_block, m_index, &m_insertionSet);
217
218         BasicBlock* normalDivCase = m_blockInsertionSet.insertBefore(m_block);
219         BasicBlock* shadyDenCase = m_blockInsertionSet.insertBefore(m_block);
220         BasicBlock* zeroDenCase = m_blockInsertionSet.insertBefore(m_block);
221         BasicBlock* neg1DenCase = m_blockInsertionSet.insertBefore(m_block);
222         BasicBlock* intMinCase = m_blockInsertionSet.insertBefore(m_block);
223
224         before->replaceLastWithNew<Value>(m_proc, Branch, m_origin, isDenOK);
225         before->setSuccessors(
226             FrequentedBlock(normalDivCase, FrequencyClass::Normal),
227             FrequentedBlock(shadyDenCase, FrequencyClass::Rare));
228
229         UpsilonValue* normalResult = normalDivCase->appendNew<UpsilonValue>(
230             m_proc, m_origin,
231             normalDivCase->appendNew<Value>(m_proc, nonChillOpcode, m_origin, num, den));
232         normalDivCase->appendNew<Value>(m_proc, Jump, m_origin);
233         normalDivCase->setSuccessors(FrequentedBlock(m_block));
234
235         shadyDenCase->appendNew<Value>(m_proc, Branch, m_origin, den);
236         shadyDenCase->setSuccessors(
237             FrequentedBlock(neg1DenCase, FrequencyClass::Normal),
238             FrequentedBlock(zeroDenCase, FrequencyClass::Rare));
239
240         UpsilonValue* zeroResult = zeroDenCase->appendNew<UpsilonValue>(
241             m_proc, m_origin,
242             zeroDenCase->appendIntConstant(m_proc, m_value, 0));
243         zeroDenCase->appendNew<Value>(m_proc, Jump, m_origin);
244         zeroDenCase->setSuccessors(FrequentedBlock(m_block));
245
246         int64_t badNumeratorConst = 0;
247         switch (m_value->type()) {
248         case Int32:
249             badNumeratorConst = std::numeric_limits<int32_t>::min();
250             break;
251         case Int64:
252             badNumeratorConst = std::numeric_limits<int64_t>::min();
253             break;
254         default:
255             ASSERT_NOT_REACHED();
256             badNumeratorConst = 0;
257         }
258
259         Value* badNumerator =
260             neg1DenCase->appendIntConstant(m_proc, m_value, badNumeratorConst);
261
262         neg1DenCase->appendNew<Value>(
263             m_proc, Branch, m_origin,
264             neg1DenCase->appendNew<Value>(
265                 m_proc, Equal, m_origin, num, badNumerator));
266         neg1DenCase->setSuccessors(
267             FrequentedBlock(intMinCase, FrequencyClass::Rare),
268             FrequentedBlock(normalDivCase, FrequencyClass::Normal));
269
270         Value* intMinResult = nonChillOpcode == Div ? badNumerator : intMinCase->appendIntConstant(m_proc, m_value, 0);
271         UpsilonValue* intMinResultUpsilon = intMinCase->appendNew<UpsilonValue>(
272             m_proc, m_origin, intMinResult);
273         intMinCase->appendNew<Value>(m_proc, Jump, m_origin);
274         intMinCase->setSuccessors(FrequentedBlock(m_block));
275
276         Value* phi = m_insertionSet.insert<Value>(
277             m_index, Phi, m_value->type(), m_origin);
278         normalResult->setPhi(phi);
279         zeroResult->setPhi(phi);
280         intMinResultUpsilon->setPhi(phi);
281
282         m_value->replaceWithIdentity(phi);
283         before->updatePredecessorsAfter();
284     }
285
286     void recursivelyBuildSwitch(
287         const Vector<SwitchCase>& cases, FrequentedBlock fallThrough, unsigned start, bool hardStart,
288         unsigned end, BasicBlock* before)
289     {
290         Value* child = m_value->child(0);
291         Type type = child->type();
292         
293         // It's a good idea to use a table-based switch in some cases: the number of cases has to be
294         // large enough and they have to be dense enough. This could probably be improved a lot. For
295         // example, we could still use a jump table in cases where the inputs are sparse so long as we
296         // shift off the uninteresting bits. On the other hand, it's not clear that this would
297         // actually be any better than what we have done here and it's not clear that it would be
298         // better than a binary switch.
299         const unsigned minCasesForTable = 7;
300         const unsigned densityLimit = 4;
301         if (end - start >= minCasesForTable) {
302             int64_t firstValue = cases[start].caseValue();
303             int64_t lastValue = cases[end - 1].caseValue();
304             if ((lastValue - firstValue + 1) / (end - start) < densityLimit) {
305                 BasicBlock* switchBlock = m_blockInsertionSet.insertAfter(m_block);
306                 Value* index = before->appendNew<Value>(
307                     m_proc, Sub, m_origin, child,
308                     before->appendIntConstant(m_proc, m_origin, type, firstValue));
309                 before->appendNew<Value>(
310                     m_proc, Branch, m_origin,
311                     before->appendNew<Value>(
312                         m_proc, Above, m_origin, index,
313                         before->appendIntConstant(m_proc, m_origin, type, lastValue - firstValue)));
314                 before->setSuccessors(fallThrough, FrequentedBlock(switchBlock));
315                 
316                 size_t tableSize = lastValue - firstValue + 1;
317                 
318                 if (index->type() != pointerType() && index->type() == Int32)
319                     index = switchBlock->appendNew<Value>(m_proc, ZExt32, m_origin, index);
320                 
321                 PatchpointValue* patchpoint =
322                     switchBlock->appendNew<PatchpointValue>(m_proc, Void, m_origin);
323
324                 // Even though this loads from the jump table, the jump table is immutable. For the
325                 // purpose of alias analysis, reading something immutable is like reading nothing.
326                 patchpoint->effects = Effects();
327                 patchpoint->effects.terminal = true;
328                 
329                 patchpoint->appendSomeRegister(index);
330                 patchpoint->numGPScratchRegisters++;
331                 // Technically, we don't have to clobber macro registers on X86_64. This is probably
332                 // OK though.
333                 patchpoint->clobber(RegisterSet::macroScratchRegisters());
334                 
335                 BitVector handledIndices;
336                 for (unsigned i = start; i < end; ++i) {
337                     FrequentedBlock block = cases[i].target();
338                     int64_t value = cases[i].caseValue();
339                     switchBlock->appendSuccessor(block);
340                     size_t index = value - firstValue;
341                     ASSERT(!handledIndices.get(index));
342                     handledIndices.set(index);
343                 }
344                 
345                 bool hasUnhandledIndex = false;
346                 for (unsigned i = 0; i < tableSize; ++i) {
347                     if (!handledIndices.get(i)) {
348                         hasUnhandledIndex = true;
349                         break;
350                     }
351                 }
352                 
353                 if (hasUnhandledIndex)
354                     switchBlock->appendSuccessor(fallThrough);
355
356                 patchpoint->setGenerator(
357                     [=] (CCallHelpers& jit, const StackmapGenerationParams& params) {
358                         AllowMacroScratchRegisterUsage allowScratch(jit);
359                         
360                         MacroAssemblerCodePtr* jumpTable = static_cast<MacroAssemblerCodePtr*>(
361                             params.proc().addDataSection(sizeof(MacroAssemblerCodePtr) * tableSize));
362                         
363                         GPRReg index = params[0].gpr();
364                         GPRReg scratch = params.gpScratch(0);
365                         
366                         jit.move(CCallHelpers::TrustedImmPtr(jumpTable), scratch);
367                         jit.jump(CCallHelpers::BaseIndex(scratch, index, CCallHelpers::timesPtr()));
368                         
369                         // These labels are guaranteed to be populated before either late paths or
370                         // link tasks run.
371                         Vector<Box<CCallHelpers::Label>> labels = params.successorLabels();
372                         
373                         jit.addLinkTask(
374                             [=] (LinkBuffer& linkBuffer) {
375                                 if (hasUnhandledIndex) {
376                                     MacroAssemblerCodePtr fallThrough =
377                                         linkBuffer.locationOf(*labels.last());
378                                     for (unsigned i = tableSize; i--;)
379                                         jumpTable[i] = fallThrough;
380                                 }
381                                 
382                                 unsigned labelIndex = 0;
383                                 for (unsigned tableIndex : handledIndices) {
384                                     jumpTable[tableIndex] =
385                                         linkBuffer.locationOf(*labels[labelIndex++]);
386                                 }
387                             });
388                     });
389                 return;
390             }
391         }
392         
393         // See comments in jit/BinarySwitch.cpp for a justification of this algorithm. The only
394         // thing we do differently is that we don't use randomness.
395
396         const unsigned leafThreshold = 3;
397
398         unsigned size = end - start;
399
400         if (size <= leafThreshold) {
401             bool allConsecutive = false;
402
403             if ((hardStart || (start && cases[start - 1].caseValue() == cases[start].caseValue() - 1))
404                 && end < cases.size()
405                 && cases[end - 1].caseValue() == cases[end].caseValue() - 1) {
406                 allConsecutive = true;
407                 for (unsigned i = 0; i < size - 1; ++i) {
408                     if (cases[start + i].caseValue() + 1 != cases[start + i + 1].caseValue()) {
409                         allConsecutive = false;
410                         break;
411                     }
412                 }
413             }
414
415             unsigned limit = allConsecutive ? size - 1 : size;
416             
417             for (unsigned i = 0; i < limit; ++i) {
418                 BasicBlock* nextCheck = m_blockInsertionSet.insertAfter(m_block);
419                 before->appendNew<Value>(
420                     m_proc, Branch, m_origin,
421                     before->appendNew<Value>(
422                         m_proc, Equal, m_origin, child,
423                         before->appendIntConstant(
424                             m_proc, m_origin, type,
425                             cases[start + i].caseValue())));
426                 before->setSuccessors(cases[start + i].target(), FrequentedBlock(nextCheck));
427
428                 before = nextCheck;
429             }
430
431             before->appendNew<Value>(m_proc, Jump, m_origin);
432             if (allConsecutive)
433                 before->setSuccessors(cases[end - 1].target());
434             else
435                 before->setSuccessors(fallThrough);
436             return;
437         }
438
439         unsigned medianIndex = (start + end) / 2;
440
441         BasicBlock* left = m_blockInsertionSet.insertAfter(m_block);
442         BasicBlock* right = m_blockInsertionSet.insertAfter(m_block);
443
444         before->appendNew<Value>(
445             m_proc, Branch, m_origin,
446             before->appendNew<Value>(
447                 m_proc, LessThan, m_origin, child,
448                 before->appendIntConstant(
449                     m_proc, m_origin, type,
450                     cases[medianIndex].caseValue())));
451         before->setSuccessors(FrequentedBlock(left), FrequentedBlock(right));
452
453         recursivelyBuildSwitch(cases, fallThrough, start, hardStart, medianIndex, left);
454         recursivelyBuildSwitch(cases, fallThrough, medianIndex, true, end, right);
455     }
456     
457     Procedure& m_proc;
458     BlockInsertionSet m_blockInsertionSet;
459     InsertionSet m_insertionSet;
460     BasicBlock* m_block;
461     unsigned m_index;
462     Value* m_value;
463     Origin m_origin;
464     bool m_changed { false };
465 };
466
467 bool lowerMacrosImpl(Procedure& proc)
468 {
469     LowerMacros lowerMacros(proc);
470     return lowerMacros.run();
471 }
472
473 } // anonymous namespace
474
475 bool lowerMacros(Procedure& proc)
476 {
477     PhaseScope phaseScope(proc, "lowerMacros");
478     bool result = lowerMacrosImpl(proc);
479     if (shouldValidateIR())
480         RELEASE_ASSERT(!lowerMacrosImpl(proc));
481     return result;
482 }
483
484 } } // namespace JSC::B3
485
486 #endif // ENABLE(B3_JIT)
487