[JSC] Add a Modulo operator to B3, and a chill variant
[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                 } else if (m_value->type() == Float) {
88                     Value* numeratorAsDouble = m_insertionSet.insert<Value>(m_index, FloatToDouble, m_origin, m_value->child(0));
89                     Value* denominatorAsDouble = m_insertionSet.insert<Value>(m_index, FloatToDouble, m_origin, m_value->child(1));
90                     Value* functionAddress = m_insertionSet.insert<ConstPtrValue>(m_index, m_origin, fmod);
91                     Value* doubleMod = m_insertionSet.insert<CCallValue>(m_index, Double, m_origin,
92                         Effects::none(),
93                         functionAddress,
94                         numeratorAsDouble,
95                         denominatorAsDouble);
96                     Value* result = m_insertionSet.insert<Value>(m_index, DoubleToFloat, m_origin, doubleMod);
97                     m_value->replaceWithIdentity(result);
98                 }
99                 break;
100             }
101             case ChillDiv: {
102                 makeDivisionChill(Div);
103                 break;
104             }
105
106             case ChillMod: {
107                 makeDivisionChill(Mod);
108                 break;
109             }
110
111             case Switch: {
112                 SwitchValue* switchValue = m_value->as<SwitchValue>();
113                 Vector<SwitchCase> cases;
114                 for (const SwitchCase& switchCase : *switchValue)
115                     cases.append(switchCase);
116                 std::sort(
117                     cases.begin(), cases.end(),
118                     [] (const SwitchCase& left, const SwitchCase& right) {
119                         return left.caseValue() < right.caseValue();
120                     });
121                 m_block->values().removeLast();
122                 recursivelyBuildSwitch(cases, 0, false, cases.size(), m_block);
123                 m_proc.deleteValue(switchValue);
124                 m_block->updatePredecessorsAfter();
125                 m_changed = true;
126                 break;
127             }
128
129             default:
130                 break;
131             }
132         }
133         m_insertionSet.execute(m_block);
134     }
135
136     void makeDivisionChill(Opcode nonChillOpcode)
137     {
138         ASSERT(nonChillOpcode == Div || nonChillOpcode == Mod);
139
140         // ARM supports this instruction natively.
141         if (isARM64())
142             return;
143
144         // We implement "res = ChillDiv/ChillMod(num, den)" as follows:
145         //
146         //     if (den + 1 <=_unsigned 1) {
147         //         if (!den) {
148         //             res = 0;
149         //             goto done;
150         //         }
151         //         if (num == -2147483648) {
152         //             res = isDiv ? num : 0;
153         //             goto done;
154         //         }
155         //     }
156         //     res = num (/ or %) dev;
157         // done:
158         m_changed = true;
159
160         Value* num = m_value->child(0);
161         Value* den = m_value->child(1);
162
163         Value* one = m_insertionSet.insertIntConstant(m_index, m_value, 1);
164         Value* isDenOK = m_insertionSet.insert<Value>(
165             m_index, Above, m_origin,
166             m_insertionSet.insert<Value>(m_index, Add, m_origin, den, one),
167             one);
168
169         BasicBlock* before = m_blockInsertionSet.splitForward(m_block, m_index, &m_insertionSet);
170
171         BasicBlock* normalDivCase = m_blockInsertionSet.insertBefore(m_block);
172         BasicBlock* shadyDenCase = m_blockInsertionSet.insertBefore(m_block);
173         BasicBlock* zeroDenCase = m_blockInsertionSet.insertBefore(m_block);
174         BasicBlock* neg1DenCase = m_blockInsertionSet.insertBefore(m_block);
175         BasicBlock* intMinCase = m_blockInsertionSet.insertBefore(m_block);
176
177         before->replaceLastWithNew<ControlValue>(
178             m_proc, Branch, m_origin, isDenOK,
179             FrequentedBlock(normalDivCase, FrequencyClass::Normal),
180             FrequentedBlock(shadyDenCase, FrequencyClass::Rare));
181
182         UpsilonValue* normalResult = normalDivCase->appendNew<UpsilonValue>(
183             m_proc, m_origin,
184             normalDivCase->appendNew<Value>(m_proc, nonChillOpcode, m_origin, num, den));
185         normalDivCase->appendNew<ControlValue>(
186             m_proc, Jump, m_origin, FrequentedBlock(m_block));
187
188         shadyDenCase->appendNew<ControlValue>(
189             m_proc, Branch, m_origin, den,
190             FrequentedBlock(neg1DenCase, FrequencyClass::Normal),
191             FrequentedBlock(zeroDenCase, FrequencyClass::Rare));
192
193         UpsilonValue* zeroResult = zeroDenCase->appendNew<UpsilonValue>(
194             m_proc, m_origin,
195             zeroDenCase->appendIntConstant(m_proc, m_value, 0));
196         zeroDenCase->appendNew<ControlValue>(
197             m_proc, Jump, m_origin, FrequentedBlock(m_block));
198
199         int64_t badNumeratorConst = 0;
200         switch (m_value->type()) {
201         case Int32:
202             badNumeratorConst = std::numeric_limits<int32_t>::min();
203             break;
204         case Int64:
205             badNumeratorConst = std::numeric_limits<int64_t>::min();
206             break;
207         default:
208             ASSERT_NOT_REACHED();
209             badNumeratorConst = 0;
210         }
211
212         Value* badNumerator =
213             neg1DenCase->appendIntConstant(m_proc, m_value, badNumeratorConst);
214
215         neg1DenCase->appendNew<ControlValue>(
216             m_proc, Branch, m_origin,
217             neg1DenCase->appendNew<Value>(
218                 m_proc, Equal, m_origin, num, badNumerator),
219             FrequentedBlock(intMinCase, FrequencyClass::Rare),
220             FrequentedBlock(normalDivCase, FrequencyClass::Normal));
221
222         Value* intMinResult = nonChillOpcode == Div ? badNumerator : intMinCase->appendIntConstant(m_proc, m_value, 0);
223         UpsilonValue* intMinResultUpsilon = intMinCase->appendNew<UpsilonValue>(
224             m_proc, m_origin, intMinResult);
225         intMinCase->appendNew<ControlValue>(
226             m_proc, Jump, m_origin, FrequentedBlock(m_block));
227
228         Value* phi = m_insertionSet.insert<Value>(
229             m_index, Phi, m_value->type(), m_origin);
230         normalResult->setPhi(phi);
231         zeroResult->setPhi(phi);
232         intMinResultUpsilon->setPhi(phi);
233
234         m_value->replaceWithIdentity(phi);
235         before->updatePredecessorsAfter();
236     }
237
238     void recursivelyBuildSwitch(
239         const Vector<SwitchCase>& cases, unsigned start, bool hardStart, unsigned end,
240         BasicBlock* before)
241     {
242         // FIXME: Add table-based switch lowering.
243         // https://bugs.webkit.org/show_bug.cgi?id=151141
244         
245         // See comments in jit/BinarySwitch.cpp for a justification of this algorithm. The only
246         // thing we do differently is that we don't use randomness.
247
248         const unsigned leafThreshold = 3;
249
250         unsigned size = end - start;
251
252         if (size <= leafThreshold) {
253             bool allConsecutive = false;
254
255             if ((hardStart || (start && cases[start - 1].caseValue() == cases[start].caseValue() - 1))
256                 && end < cases.size()
257                 && cases[end - 1].caseValue() == cases[end].caseValue() - 1) {
258                 allConsecutive = true;
259                 for (unsigned i = 0; i < size - 1; ++i) {
260                     if (cases[start + i].caseValue() + 1 != cases[start + i + 1].caseValue()) {
261                         allConsecutive = false;
262                         break;
263                     }
264                 }
265             }
266
267             unsigned limit = allConsecutive ? size - 1 : size;
268             
269             for (unsigned i = 0; i < limit; ++i) {
270                 BasicBlock* nextCheck = m_blockInsertionSet.insertAfter(m_block);
271                 before->appendNew<ControlValue>(
272                     m_proc, Branch, m_origin,
273                     before->appendNew<Value>(
274                         m_proc, Equal, m_origin, m_value->child(0),
275                         before->appendIntConstant(
276                             m_proc, m_origin, m_value->child(0)->type(),
277                             cases[start + i].caseValue())),
278                     cases[start + i].target(), FrequentedBlock(nextCheck));
279
280                 before = nextCheck;
281             }
282
283             if (allConsecutive) {
284                 before->appendNew<ControlValue>(
285                     m_proc, Jump, m_origin, cases[end - 1].target());
286             } else {
287                 before->appendNew<ControlValue>(
288                     m_proc, Jump, m_origin, m_value->as<SwitchValue>()->fallThrough());
289             }
290             return;
291         }
292
293         unsigned medianIndex = (start + end) / 2;
294
295         BasicBlock* left = m_blockInsertionSet.insertAfter(m_block);
296         BasicBlock* right = m_blockInsertionSet.insertAfter(m_block);
297
298         before->appendNew<ControlValue>(
299             m_proc, Branch, m_origin,
300             before->appendNew<Value>(
301                 m_proc, LessThan, m_origin, m_value->child(0),
302                 before->appendIntConstant(
303                     m_proc, m_origin, m_value->child(0)->type(),
304                     cases[medianIndex].caseValue())),
305             FrequentedBlock(left), FrequentedBlock(right));
306
307         recursivelyBuildSwitch(cases, start, hardStart, medianIndex, left);
308         recursivelyBuildSwitch(cases, medianIndex, true, end, right);
309     }
310     
311     Procedure& m_proc;
312     BlockInsertionSet m_blockInsertionSet;
313     InsertionSet m_insertionSet;
314     BasicBlock* m_block;
315     unsigned m_index;
316     Value* m_value;
317     Origin m_origin;
318     bool m_changed { false };
319 };
320
321 bool lowerMacrosImpl(Procedure& proc)
322 {
323     LowerMacros lowerMacros(proc);
324     return lowerMacros.run();
325 }
326
327 } // anonymous namespace
328
329 bool lowerMacros(Procedure& proc)
330 {
331     PhaseScope phaseScope(proc, "lowerMacros");
332     bool result = lowerMacrosImpl(proc);
333     if (shouldValidateIR())
334         RELEASE_ASSERT(!lowerMacrosImpl(proc));
335     return result;
336 }
337
338 } } // namespace JSC::B3
339
340 #endif // ENABLE(B3_JIT)
341