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