B3 should be able to compile a program with Switch
[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 "B3ControlValue.h"
34 #include "B3InsertionSetInlines.h"
35 #include "B3PhaseScope.h"
36 #include "B3ProcedureInlines.h"
37 #include "B3SwitchValue.h"
38 #include "B3UpsilonValue.h"
39 #include "B3ValueInlines.h"
40
41 namespace JSC { namespace B3 {
42
43 namespace {
44
45 class LowerMacros {
46 public:
47     LowerMacros(Procedure& proc)
48         : m_proc(proc)
49         , m_blockInsertionSet(proc)
50         , m_insertionSet(proc)
51     {
52     }
53
54     bool run()
55     {
56         for (BasicBlock* block : m_proc) {
57             m_block = block;
58             processCurrentBlock();
59         }
60         m_changed |= m_blockInsertionSet.execute();
61         if (m_changed)
62             m_proc.resetReachability();
63         return m_changed;
64     }
65     
66 private:
67     void processCurrentBlock()
68     {
69         for (m_index = 0; m_index < m_block->size(); ++m_index) {
70             m_value = m_block->at(m_index);
71             m_origin = m_value->origin();
72             switch (m_value->opcode()) {
73             case ChillDiv: {
74                 // ARM supports this instruction natively.
75                 if (isARM64())
76                     break;
77
78                 m_changed = true;
79
80                 // We implement "res = ChillDiv(num, den)" as follows:
81                 //
82                 //     if (den + 1 <=_unsigned 1) {
83                 //         if (!den) {
84                 //             res = 0;
85                 //             goto done;
86                 //         }
87                 //         if (num == -2147483648) {
88                 //             res = num;
89                 //             goto done;
90                 //         }
91                 //     }
92                 //     res = num / dev;
93                 // done:
94
95                 Value* num = m_value->child(0);
96                 Value* den = m_value->child(1);
97
98                 Value* one =
99                     m_insertionSet.insertIntConstant(m_index, m_value, 1);
100                 Value* isDenOK = m_insertionSet.insert<Value>(
101                     m_index, Above, m_origin,
102                     m_insertionSet.insert<Value>(m_index, Add, m_origin, den, one),
103                     one);
104
105                 BasicBlock* before =
106                     m_blockInsertionSet.splitForward(m_block, m_index, &m_insertionSet);
107
108                 BasicBlock* normalDivCase = m_blockInsertionSet.insertBefore(m_block);
109                 BasicBlock* shadyDenCase = m_blockInsertionSet.insertBefore(m_block);
110                 BasicBlock* zeroDenCase = m_blockInsertionSet.insertBefore(m_block);
111                 BasicBlock* neg1DenCase = m_blockInsertionSet.insertBefore(m_block);
112                 BasicBlock* intMinCase = m_blockInsertionSet.insertBefore(m_block);
113
114                 before->replaceLastWithNew<ControlValue>(
115                     m_proc, Branch, m_origin, isDenOK,
116                     FrequentedBlock(normalDivCase, FrequencyClass::Normal),
117                     FrequentedBlock(shadyDenCase, FrequencyClass::Rare));
118
119                 UpsilonValue* normalResult = normalDivCase->appendNew<UpsilonValue>(
120                     m_proc, m_origin,
121                     normalDivCase->appendNew<Value>(m_proc, Div, m_origin, num, den));
122                 normalDivCase->appendNew<ControlValue>(
123                     m_proc, Jump, m_origin, FrequentedBlock(m_block));
124
125                 shadyDenCase->appendNew<ControlValue>(
126                     m_proc, Branch, m_origin, den,
127                     FrequentedBlock(neg1DenCase, FrequencyClass::Normal),
128                     FrequentedBlock(zeroDenCase, FrequencyClass::Rare));
129
130                 UpsilonValue* zeroResult = zeroDenCase->appendNew<UpsilonValue>(
131                     m_proc, m_origin,
132                     zeroDenCase->appendIntConstant(m_proc, m_value, 0));
133                 zeroDenCase->appendNew<ControlValue>(
134                     m_proc, Jump, m_origin, FrequentedBlock(m_block));
135
136                 int64_t badNumeratorConst;
137                 switch (m_value->type()) {
138                 case Int32:
139                     badNumeratorConst = std::numeric_limits<int32_t>::min();
140                     break;
141                 case Int64:
142                     badNumeratorConst = std::numeric_limits<int64_t>::min();
143                     break;
144                 default:
145                     ASSERT_NOT_REACHED();
146                     badNumeratorConst = 0;
147                 }
148
149                 Value* badNumerator =
150                     neg1DenCase->appendIntConstant(m_proc, m_value, badNumeratorConst);
151
152                 neg1DenCase->appendNew<ControlValue>(
153                     m_proc, Branch, m_origin,
154                     neg1DenCase->appendNew<Value>(
155                         m_proc, Equal, m_origin, num, badNumerator),
156                     FrequentedBlock(intMinCase, FrequencyClass::Rare),
157                     FrequentedBlock(normalDivCase, FrequencyClass::Normal));
158
159                 UpsilonValue* intMinResult = intMinCase->appendNew<UpsilonValue>(
160                     m_proc, m_origin, badNumerator);
161                 intMinCase->appendNew<ControlValue>(
162                     m_proc, Jump, m_origin, FrequentedBlock(m_block));
163
164                 Value* phi = m_insertionSet.insert<Value>(
165                     m_index, Phi, m_value->type(), m_origin);
166                 normalResult->setPhi(phi);
167                 zeroResult->setPhi(phi);
168                 intMinResult->setPhi(phi);
169
170                 m_value->replaceWithIdentity(phi);
171                 before->updatePredecessorsAfter();
172                 break;
173             }
174
175             case Switch: {
176                 SwitchValue* switchValue = m_value->as<SwitchValue>();
177                 Vector<SwitchCase> cases;
178                 for (const SwitchCase& switchCase : *switchValue)
179                     cases.append(switchCase);
180                 std::sort(
181                     cases.begin(), cases.end(),
182                     [] (const SwitchCase& left, const SwitchCase& right) {
183                         return left.caseValue() < right.caseValue();
184                     });
185                 m_block->values().removeLast();
186                 recursivelyBuildSwitch(cases, 0, false, cases.size(), m_block);
187                 m_proc.deleteValue(switchValue);
188                 m_block->updatePredecessorsAfter();
189                 m_changed = true;
190                 break;
191             }
192
193             default:
194                 break;
195             }
196         }
197         m_insertionSet.execute(m_block);
198     }
199
200     void recursivelyBuildSwitch(
201         const Vector<SwitchCase>& cases, unsigned start, bool hardStart, unsigned end,
202         BasicBlock* before)
203     {
204         // FIXME: Add table-based switch lowering.
205         // https://bugs.webkit.org/show_bug.cgi?id=151141
206         
207         // See comments in jit/BinarySwitch.cpp for a justification of this algorithm. The only
208         // thing we do differently is that we don't use randomness.
209
210         const unsigned leafThreshold = 3;
211
212         unsigned size = end - start;
213
214         if (size <= leafThreshold) {
215             bool allConsecutive = false;
216
217             if ((hardStart || (start && cases[start - 1].caseValue() == cases[start].caseValue() - 1))
218                 && end < cases.size()
219                 && cases[end - 1].caseValue() == cases[end].caseValue() - 1) {
220                 allConsecutive = true;
221                 for (unsigned i = 0; i < size - 1; ++i) {
222                     if (cases[start + i].caseValue() + 1 != cases[start + i + 1].caseValue()) {
223                         allConsecutive = false;
224                         break;
225                     }
226                 }
227             }
228
229             unsigned limit = allConsecutive ? size - 1 : size;
230             
231             for (unsigned i = 0; i < limit; ++i) {
232                 BasicBlock* nextCheck = m_blockInsertionSet.insertAfter(m_block);
233                 before->appendNew<ControlValue>(
234                     m_proc, Branch, m_origin,
235                     before->appendNew<Value>(
236                         m_proc, Equal, m_origin, m_value->child(0),
237                         before->appendIntConstant(
238                             m_proc, m_origin, m_value->child(0)->type(),
239                             cases[start + i].caseValue())),
240                     cases[start + i].target(), FrequentedBlock(nextCheck));
241
242                 before = nextCheck;
243             }
244
245             if (allConsecutive) {
246                 before->appendNew<ControlValue>(
247                     m_proc, Jump, m_origin, cases[end - 1].target());
248             } else {
249                 before->appendNew<ControlValue>(
250                     m_proc, Jump, m_origin, m_value->as<SwitchValue>()->fallThrough());
251             }
252             return;
253         }
254
255         unsigned medianIndex = (start + end) / 2;
256
257         BasicBlock* left = m_blockInsertionSet.insertAfter(m_block);
258         BasicBlock* right = m_blockInsertionSet.insertAfter(m_block);
259
260         before->appendNew<ControlValue>(
261             m_proc, Branch, m_origin,
262             before->appendNew<Value>(
263                 m_proc, LessThan, m_origin, m_value->child(0),
264                 before->appendIntConstant(
265                     m_proc, m_origin, m_value->child(0)->type(),
266                     cases[medianIndex].caseValue())),
267             FrequentedBlock(left), FrequentedBlock(right));
268
269         recursivelyBuildSwitch(cases, start, hardStart, medianIndex, left);
270         recursivelyBuildSwitch(cases, medianIndex, true, end, right);
271     }
272     
273     Procedure& m_proc;
274     BlockInsertionSet m_blockInsertionSet;
275     InsertionSet m_insertionSet;
276     BasicBlock* m_block;
277     unsigned m_index;
278     Value* m_value;
279     Origin m_origin;
280     bool m_changed { false };
281 };
282
283 bool lowerMacrosImpl(Procedure& proc)
284 {
285     LowerMacros lowerMacros(proc);
286     return lowerMacros.run();
287 }
288
289 } // anonymous namespace
290
291 bool lowerMacros(Procedure& proc)
292 {
293     PhaseScope phaseScope(proc, "lowerMacros");
294     bool result = lowerMacrosImpl(proc);
295     if (shouldValidateIR())
296         RELEASE_ASSERT(!lowerMacrosImpl(proc));
297     return result;
298 }
299
300 } } // namespace JSC::B3
301
302 #endif // ENABLE(B3_JIT)
303