[JSC] Add Div/Mod and fix Mul for B3 ARM64
[WebKit-https.git] / Source / JavaScriptCore / b3 / B3LowerMacros.cpp
1 /*
2  * Copyright (C) 2015 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 "B3BasicBlockInlines.h"
32 #include "B3BlockInsertionSet.h"
33 #include "B3CCallValue.h"
34 #include "B3ConstPtrValue.h"
35 #include "B3ControlValue.h"
36 #include "B3InsertionSetInlines.h"
37 #include "B3PhaseScope.h"
38 #include "B3ProcedureInlines.h"
39 #include "B3SwitchValue.h"
40 #include "B3UpsilonValue.h"
41 #include "B3ValueInlines.h"
42 #include <cmath>
43
44 namespace JSC { namespace B3 {
45
46 namespace {
47
48 class LowerMacros {
49 public:
50     LowerMacros(Procedure& proc)
51         : m_proc(proc)
52         , m_blockInsertionSet(proc)
53         , m_insertionSet(proc)
54     {
55     }
56
57     bool run()
58     {
59         for (BasicBlock* block : m_proc) {
60             m_block = block;
61             processCurrentBlock();
62         }
63         m_changed |= m_blockInsertionSet.execute();
64         if (m_changed) {
65             m_proc.resetReachability();
66             m_proc.invalidateCFG();
67         }
68         return m_changed;
69     }
70     
71 private:
72     void processCurrentBlock()
73     {
74         for (m_index = 0; m_index < m_block->size(); ++m_index) {
75             m_value = m_block->at(m_index);
76             m_origin = m_value->origin();
77             switch (m_value->opcode()) {
78             case Mod: {
79                 if (m_value->type() == Double) {
80                     Value* functionAddress = m_insertionSet.insert<ConstPtrValue>(m_index, m_origin, fmod);
81                     Value* result = m_insertionSet.insert<CCallValue>(m_index, Double, m_origin,
82                         Effects::none(),
83                         functionAddress,
84                         m_value->child(0),
85                         m_value->child(1));
86                     m_value->replaceWithIdentity(result);
87                     m_changed = true;
88                 } else if (m_value->type() == Float) {
89                     Value* numeratorAsDouble = m_insertionSet.insert<Value>(m_index, FloatToDouble, m_origin, m_value->child(0));
90                     Value* denominatorAsDouble = m_insertionSet.insert<Value>(m_index, FloatToDouble, m_origin, m_value->child(1));
91                     Value* functionAddress = m_insertionSet.insert<ConstPtrValue>(m_index, m_origin, fmod);
92                     Value* doubleMod = m_insertionSet.insert<CCallValue>(m_index, Double, m_origin,
93                         Effects::none(),
94                         functionAddress,
95                         numeratorAsDouble,
96                         denominatorAsDouble);
97                     Value* result = m_insertionSet.insert<Value>(m_index, DoubleToFloat, m_origin, doubleMod);
98                     m_value->replaceWithIdentity(result);
99                     m_changed = true;
100                 } else if (isARM64()) {
101                     Value* divResult = m_insertionSet.insert<Value>(m_index, ChillDiv, m_origin, m_value->child(0), m_value->child(1));
102                     Value* multipliedBack = m_insertionSet.insert<Value>(m_index, Mul, m_origin, divResult, m_value->child(1));
103                     Value* result = m_insertionSet.insert<Value>(m_index, Sub, m_origin, m_value->child(0), multipliedBack);
104                     m_value->replaceWithIdentity(result);
105                     m_changed = true;
106                 }
107                 break;
108             }
109             case ChillDiv: {
110                 makeDivisionChill(Div);
111                 break;
112             }
113
114             case ChillMod: {
115                 if (isARM64()) {
116                     BasicBlock* before = m_blockInsertionSet.splitForward(m_block, m_index, &m_insertionSet);
117                     BasicBlock* zeroDenCase = m_blockInsertionSet.insertBefore(m_block);
118                     BasicBlock* normalModCase = m_blockInsertionSet.insertBefore(m_block);
119
120                     before->replaceLastWithNew<ControlValue>(
121                         m_proc, Branch, m_origin, m_value->child(1),
122                         FrequentedBlock(normalModCase, FrequencyClass::Normal),
123                         FrequentedBlock(zeroDenCase, FrequencyClass::Rare));
124
125                     Value* divResult = normalModCase->appendNew<Value>(m_proc, ChillDiv, m_origin, m_value->child(0), m_value->child(1));
126                     Value* multipliedBack = normalModCase->appendNew<Value>(m_proc, Mul, m_origin, divResult, m_value->child(1));
127                     Value* result = normalModCase->appendNew<Value>(m_proc, Sub, m_origin, m_value->child(0), multipliedBack);
128                     UpsilonValue* normalResult = normalModCase->appendNew<UpsilonValue>(m_proc, m_origin, result);
129                     normalModCase->appendNew<ControlValue>(m_proc, Jump, m_origin, FrequentedBlock(m_block));
130
131                     UpsilonValue* zeroResult = zeroDenCase->appendNew<UpsilonValue>(
132                         m_proc, m_origin,
133                         zeroDenCase->appendIntConstant(m_proc, m_value, 0));
134                     zeroDenCase->appendNew<ControlValue>(m_proc, Jump, m_origin, FrequentedBlock(m_block));
135
136                     Value* phi = m_insertionSet.insert<Value>(m_index, Phi, m_value->type(), m_origin);
137                     normalResult->setPhi(phi);
138                     zeroResult->setPhi(phi);
139                     m_value->replaceWithIdentity(phi);
140                     m_changed = true;
141                 } else
142                     makeDivisionChill(Mod);
143                 break;
144             }
145
146             case Switch: {
147                 SwitchValue* switchValue = m_value->as<SwitchValue>();
148                 Vector<SwitchCase> cases;
149                 for (const SwitchCase& switchCase : *switchValue)
150                     cases.append(switchCase);
151                 std::sort(
152                     cases.begin(), cases.end(),
153                     [] (const SwitchCase& left, const SwitchCase& right) {
154                         return left.caseValue() < right.caseValue();
155                     });
156                 m_block->values().removeLast();
157                 recursivelyBuildSwitch(cases, 0, false, cases.size(), m_block);
158                 m_proc.deleteValue(switchValue);
159                 m_block->updatePredecessorsAfter();
160                 m_changed = true;
161                 break;
162             }
163
164             default:
165                 break;
166             }
167         }
168         m_insertionSet.execute(m_block);
169     }
170
171     void makeDivisionChill(Opcode nonChillOpcode)
172     {
173         ASSERT(nonChillOpcode == Div || nonChillOpcode == Mod);
174
175         // ARM supports this instruction natively.
176         if (isARM64())
177             return;
178
179         // We implement "res = ChillDiv/ChillMod(num, den)" as follows:
180         //
181         //     if (den + 1 <=_unsigned 1) {
182         //         if (!den) {
183         //             res = 0;
184         //             goto done;
185         //         }
186         //         if (num == -2147483648) {
187         //             res = isDiv ? num : 0;
188         //             goto done;
189         //         }
190         //     }
191         //     res = num (/ or %) dev;
192         // done:
193         m_changed = true;
194
195         Value* num = m_value->child(0);
196         Value* den = m_value->child(1);
197
198         Value* one = m_insertionSet.insertIntConstant(m_index, m_value, 1);
199         Value* isDenOK = m_insertionSet.insert<Value>(
200             m_index, Above, m_origin,
201             m_insertionSet.insert<Value>(m_index, Add, m_origin, den, one),
202             one);
203
204         BasicBlock* before = m_blockInsertionSet.splitForward(m_block, m_index, &m_insertionSet);
205
206         BasicBlock* normalDivCase = m_blockInsertionSet.insertBefore(m_block);
207         BasicBlock* shadyDenCase = m_blockInsertionSet.insertBefore(m_block);
208         BasicBlock* zeroDenCase = m_blockInsertionSet.insertBefore(m_block);
209         BasicBlock* neg1DenCase = m_blockInsertionSet.insertBefore(m_block);
210         BasicBlock* intMinCase = m_blockInsertionSet.insertBefore(m_block);
211
212         before->replaceLastWithNew<ControlValue>(
213             m_proc, Branch, m_origin, isDenOK,
214             FrequentedBlock(normalDivCase, FrequencyClass::Normal),
215             FrequentedBlock(shadyDenCase, FrequencyClass::Rare));
216
217         UpsilonValue* normalResult = normalDivCase->appendNew<UpsilonValue>(
218             m_proc, m_origin,
219             normalDivCase->appendNew<Value>(m_proc, nonChillOpcode, m_origin, num, den));
220         normalDivCase->appendNew<ControlValue>(
221             m_proc, Jump, m_origin, FrequentedBlock(m_block));
222
223         shadyDenCase->appendNew<ControlValue>(
224             m_proc, Branch, m_origin, den,
225             FrequentedBlock(neg1DenCase, FrequencyClass::Normal),
226             FrequentedBlock(zeroDenCase, FrequencyClass::Rare));
227
228         UpsilonValue* zeroResult = zeroDenCase->appendNew<UpsilonValue>(
229             m_proc, m_origin,
230             zeroDenCase->appendIntConstant(m_proc, m_value, 0));
231         zeroDenCase->appendNew<ControlValue>(
232             m_proc, Jump, m_origin, FrequentedBlock(m_block));
233
234         int64_t badNumeratorConst = 0;
235         switch (m_value->type()) {
236         case Int32:
237             badNumeratorConst = std::numeric_limits<int32_t>::min();
238             break;
239         case Int64:
240             badNumeratorConst = std::numeric_limits<int64_t>::min();
241             break;
242         default:
243             ASSERT_NOT_REACHED();
244             badNumeratorConst = 0;
245         }
246
247         Value* badNumerator =
248             neg1DenCase->appendIntConstant(m_proc, m_value, badNumeratorConst);
249
250         neg1DenCase->appendNew<ControlValue>(
251             m_proc, Branch, m_origin,
252             neg1DenCase->appendNew<Value>(
253                 m_proc, Equal, m_origin, num, badNumerator),
254             FrequentedBlock(intMinCase, FrequencyClass::Rare),
255             FrequentedBlock(normalDivCase, FrequencyClass::Normal));
256
257         Value* intMinResult = nonChillOpcode == Div ? badNumerator : intMinCase->appendIntConstant(m_proc, m_value, 0);
258         UpsilonValue* intMinResultUpsilon = intMinCase->appendNew<UpsilonValue>(
259             m_proc, m_origin, intMinResult);
260         intMinCase->appendNew<ControlValue>(
261             m_proc, Jump, m_origin, FrequentedBlock(m_block));
262
263         Value* phi = m_insertionSet.insert<Value>(
264             m_index, Phi, m_value->type(), m_origin);
265         normalResult->setPhi(phi);
266         zeroResult->setPhi(phi);
267         intMinResultUpsilon->setPhi(phi);
268
269         m_value->replaceWithIdentity(phi);
270         before->updatePredecessorsAfter();
271     }
272
273     void recursivelyBuildSwitch(
274         const Vector<SwitchCase>& cases, unsigned start, bool hardStart, unsigned end,
275         BasicBlock* before)
276     {
277         // FIXME: Add table-based switch lowering.
278         // https://bugs.webkit.org/show_bug.cgi?id=151141
279         
280         // See comments in jit/BinarySwitch.cpp for a justification of this algorithm. The only
281         // thing we do differently is that we don't use randomness.
282
283         const unsigned leafThreshold = 3;
284
285         unsigned size = end - start;
286
287         if (size <= leafThreshold) {
288             bool allConsecutive = false;
289
290             if ((hardStart || (start && cases[start - 1].caseValue() == cases[start].caseValue() - 1))
291                 && end < cases.size()
292                 && cases[end - 1].caseValue() == cases[end].caseValue() - 1) {
293                 allConsecutive = true;
294                 for (unsigned i = 0; i < size - 1; ++i) {
295                     if (cases[start + i].caseValue() + 1 != cases[start + i + 1].caseValue()) {
296                         allConsecutive = false;
297                         break;
298                     }
299                 }
300             }
301
302             unsigned limit = allConsecutive ? size - 1 : size;
303             
304             for (unsigned i = 0; i < limit; ++i) {
305                 BasicBlock* nextCheck = m_blockInsertionSet.insertAfter(m_block);
306                 before->appendNew<ControlValue>(
307                     m_proc, Branch, m_origin,
308                     before->appendNew<Value>(
309                         m_proc, Equal, m_origin, m_value->child(0),
310                         before->appendIntConstant(
311                             m_proc, m_origin, m_value->child(0)->type(),
312                             cases[start + i].caseValue())),
313                     cases[start + i].target(), FrequentedBlock(nextCheck));
314
315                 before = nextCheck;
316             }
317
318             if (allConsecutive) {
319                 before->appendNew<ControlValue>(
320                     m_proc, Jump, m_origin, cases[end - 1].target());
321             } else {
322                 before->appendNew<ControlValue>(
323                     m_proc, Jump, m_origin, m_value->as<SwitchValue>()->fallThrough());
324             }
325             return;
326         }
327
328         unsigned medianIndex = (start + end) / 2;
329
330         BasicBlock* left = m_blockInsertionSet.insertAfter(m_block);
331         BasicBlock* right = m_blockInsertionSet.insertAfter(m_block);
332
333         before->appendNew<ControlValue>(
334             m_proc, Branch, m_origin,
335             before->appendNew<Value>(
336                 m_proc, LessThan, m_origin, m_value->child(0),
337                 before->appendIntConstant(
338                     m_proc, m_origin, m_value->child(0)->type(),
339                     cases[medianIndex].caseValue())),
340             FrequentedBlock(left), FrequentedBlock(right));
341
342         recursivelyBuildSwitch(cases, start, hardStart, medianIndex, left);
343         recursivelyBuildSwitch(cases, medianIndex, true, end, right);
344     }
345     
346     Procedure& m_proc;
347     BlockInsertionSet m_blockInsertionSet;
348     InsertionSet m_insertionSet;
349     BasicBlock* m_block;
350     unsigned m_index;
351     Value* m_value;
352     Origin m_origin;
353     bool m_changed { false };
354 };
355
356 bool lowerMacrosImpl(Procedure& proc)
357 {
358     LowerMacros lowerMacros(proc);
359     return lowerMacros.run();
360 }
361
362 } // anonymous namespace
363
364 bool lowerMacros(Procedure& proc)
365 {
366     PhaseScope phaseScope(proc, "lowerMacros");
367     bool result = lowerMacrosImpl(proc);
368     if (shouldValidateIR())
369         RELEASE_ASSERT(!lowerMacrosImpl(proc));
370     return result;
371 }
372
373 } } // namespace JSC::B3
374
375 #endif // ENABLE(B3_JIT)
376