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