1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2  * vim: set ts=8 sts=2 et sw=2 tw=80:
3  */
4 /* This Source Code Form is subject to the terms of the Mozilla Public
5  * License, v. 2.0. If a copy of the MPL was not distributed with this
6  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 
8 #include "jit/IonAnalysis.h"
9 #include "jit/MIRGenerator.h"
10 #include "jit/MIRGraph.h"
11 #include "jit/RangeAnalysis.h"
12 
13 #include "jsapi-tests/testJitMinimalFunc.h"
14 #include "jsapi-tests/tests.h"
15 
16 using namespace js;
17 using namespace js::jit;
18 
EquivalentRanges(const Range * a,const Range * b)19 static bool EquivalentRanges(const Range* a, const Range* b) {
20   if (a->hasInt32UpperBound() != b->hasInt32UpperBound()) {
21     return false;
22   }
23   if (a->hasInt32LowerBound() != b->hasInt32LowerBound()) {
24     return false;
25   }
26   if (a->hasInt32UpperBound() && (a->upper() != b->upper())) {
27     return false;
28   }
29   if (a->hasInt32LowerBound() && (a->lower() != b->lower())) {
30     return false;
31   }
32   if (a->canHaveFractionalPart() != b->canHaveFractionalPart()) {
33     return false;
34   }
35   if (a->canBeNegativeZero() != b->canBeNegativeZero()) {
36     return false;
37   }
38   if (a->canBeNaN() != b->canBeNaN()) {
39     return false;
40   }
41   if (a->canBeInfiniteOrNaN() != b->canBeInfiniteOrNaN()) {
42     return false;
43   }
44   if (!a->canBeInfiniteOrNaN() && (a->exponent() != b->exponent())) {
45     return false;
46   }
47   return true;
48 }
49 
BEGIN_TEST(testJitRangeAnalysis_MathSign)50 BEGIN_TEST(testJitRangeAnalysis_MathSign) {
51   MinimalAlloc func;
52 
53   Range* xnan = new (func.alloc) Range();
54 
55   Range* ninf = Range::NewDoubleSingletonRange(
56       func.alloc, mozilla::NegativeInfinity<double>());
57   Range* n1_5 = Range::NewDoubleSingletonRange(func.alloc, -1.5);
58   Range* n1_0 = Range::NewDoubleSingletonRange(func.alloc, -1);
59   Range* n0_5 = Range::NewDoubleSingletonRange(func.alloc, -0.5);
60   Range* n0_0 = Range::NewDoubleSingletonRange(func.alloc, -0.0);
61 
62   Range* p0_0 = Range::NewDoubleSingletonRange(func.alloc, 0.0);
63   Range* p0_5 = Range::NewDoubleSingletonRange(func.alloc, 0.5);
64   Range* p1_0 = Range::NewDoubleSingletonRange(func.alloc, 1.0);
65   Range* p1_5 = Range::NewDoubleSingletonRange(func.alloc, 1.5);
66   Range* pinf = Range::NewDoubleSingletonRange(
67       func.alloc, mozilla::PositiveInfinity<double>());
68 
69   Range* xnanSign = Range::sign(func.alloc, xnan);
70 
71   Range* ninfSign = Range::sign(func.alloc, ninf);
72   Range* n1_5Sign = Range::sign(func.alloc, n1_5);
73   Range* n1_0Sign = Range::sign(func.alloc, n1_0);
74   Range* n0_5Sign = Range::sign(func.alloc, n0_5);
75   Range* n0_0Sign = Range::sign(func.alloc, n0_0);
76 
77   Range* p0_0Sign = Range::sign(func.alloc, p0_0);
78   Range* p0_5Sign = Range::sign(func.alloc, p0_5);
79   Range* p1_0Sign = Range::sign(func.alloc, p1_0);
80   Range* p1_5Sign = Range::sign(func.alloc, p1_5);
81   Range* pinfSign = Range::sign(func.alloc, pinf);
82 
83   CHECK(!xnanSign);
84   CHECK(EquivalentRanges(ninfSign,
85                          Range::NewInt32SingletonRange(func.alloc, -1)));
86   CHECK(EquivalentRanges(n1_5Sign,
87                          Range::NewInt32SingletonRange(func.alloc, -1)));
88   CHECK(EquivalentRanges(n1_0Sign,
89                          Range::NewInt32SingletonRange(func.alloc, -1)));
90 
91   // This should ideally be just -1, but range analysis can't represent the
92   // specific fractional range of the constant.
93   CHECK(EquivalentRanges(n0_5Sign, Range::NewInt32Range(func.alloc, -1, 0)));
94 
95   CHECK(EquivalentRanges(n0_0Sign,
96                          Range::NewDoubleSingletonRange(func.alloc, -0.0)));
97 
98   CHECK(!n0_0Sign->canHaveFractionalPart());
99   CHECK(n0_0Sign->canBeNegativeZero());
100   CHECK(n0_0Sign->lower() == 0);
101   CHECK(n0_0Sign->upper() == 0);
102 
103   CHECK(
104       EquivalentRanges(p0_0Sign, Range::NewInt32SingletonRange(func.alloc, 0)));
105 
106   CHECK(!p0_0Sign->canHaveFractionalPart());
107   CHECK(!p0_0Sign->canBeNegativeZero());
108   CHECK(p0_0Sign->lower() == 0);
109   CHECK(p0_0Sign->upper() == 0);
110 
111   // This should ideally be just 1, but range analysis can't represent the
112   // specific fractional range of the constant.
113   CHECK(EquivalentRanges(p0_5Sign, Range::NewInt32Range(func.alloc, 0, 1)));
114 
115   CHECK(
116       EquivalentRanges(p1_0Sign, Range::NewInt32SingletonRange(func.alloc, 1)));
117   CHECK(
118       EquivalentRanges(p1_5Sign, Range::NewInt32SingletonRange(func.alloc, 1)));
119   CHECK(
120       EquivalentRanges(pinfSign, Range::NewInt32SingletonRange(func.alloc, 1)));
121 
122   return true;
123 }
124 END_TEST(testJitRangeAnalysis_MathSign)
125 
BEGIN_TEST(testJitRangeAnalysis_MathSignBeta)126 BEGIN_TEST(testJitRangeAnalysis_MathSignBeta) {
127   MinimalFunc func;
128 
129   MBasicBlock* entry = func.createEntryBlock();
130   MBasicBlock* thenBlock = func.createBlock(entry);
131   MBasicBlock* elseBlock = func.createBlock(entry);
132   MBasicBlock* elseThenBlock = func.createBlock(elseBlock);
133   MBasicBlock* elseElseBlock = func.createBlock(elseBlock);
134 
135   // if (p < 0)
136   MParameter* p = func.createParameter();
137   entry->add(p);
138   MConstant* c0 = MConstant::New(func.alloc, DoubleValue(0.0));
139   entry->add(c0);
140   MConstant* cm0 = MConstant::New(func.alloc, DoubleValue(-0.0));
141   entry->add(cm0);
142   MCompare* cmp =
143       MCompare::New(func.alloc, p, c0, JSOp::Lt, MCompare::Compare_Double);
144   entry->add(cmp);
145   entry->end(MTest::New(func.alloc, cmp, thenBlock, elseBlock));
146 
147   // {
148   //   return Math.sign(p + -0);
149   // }
150   MAdd* thenAdd = MAdd::New(func.alloc, p, cm0, MIRType::Double);
151   thenBlock->add(thenAdd);
152   MSign* thenSign = MSign::New(func.alloc, thenAdd, MIRType::Double);
153   thenBlock->add(thenSign);
154   MReturn* thenRet = MReturn::New(func.alloc, thenSign);
155   thenBlock->end(thenRet);
156 
157   // else
158   // {
159   //   if (p >= 0)
160   MCompare* elseCmp =
161       MCompare::New(func.alloc, p, c0, JSOp::Ge, MCompare::Compare_Double);
162   elseBlock->add(elseCmp);
163   elseBlock->end(MTest::New(func.alloc, elseCmp, elseThenBlock, elseElseBlock));
164 
165   //   {
166   //     return Math.sign(p + -0);
167   //   }
168   MAdd* elseThenAdd = MAdd::New(func.alloc, p, cm0, MIRType::Double);
169   elseThenBlock->add(elseThenAdd);
170   MSign* elseThenSign = MSign::New(func.alloc, elseThenAdd, MIRType::Double);
171   elseThenBlock->add(elseThenSign);
172   MReturn* elseThenRet = MReturn::New(func.alloc, elseThenSign);
173   elseThenBlock->end(elseThenRet);
174 
175   //   else
176   //   {
177   //     return Math.sign(p + -0);
178   //   }
179   // }
180   MAdd* elseElseAdd = MAdd::New(func.alloc, p, cm0, MIRType::Double);
181   elseElseBlock->add(elseElseAdd);
182   MSign* elseElseSign = MSign::New(func.alloc, elseElseAdd, MIRType::Double);
183   elseElseBlock->add(elseElseSign);
184   MReturn* elseElseRet = MReturn::New(func.alloc, elseElseSign);
185   elseElseBlock->end(elseElseRet);
186 
187   if (!func.runRangeAnalysis()) {
188     return false;
189   }
190 
191   CHECK(!p->range());
192   CHECK(EquivalentRanges(c0->range(),
193                          Range::NewDoubleSingletonRange(func.alloc, 0.0)));
194   CHECK(EquivalentRanges(cm0->range(),
195                          Range::NewDoubleSingletonRange(func.alloc, -0.0)));
196 
197   // On the (p < 0) side, p is negative and not -0 (surprise!)
198   CHECK(EquivalentRanges(
199       thenAdd->range(),
200       new (func.alloc)
201           Range(Range::NoInt32LowerBound, 0, Range::IncludesFractionalParts,
202                 Range::ExcludesNegativeZero, Range::IncludesInfinity)));
203 
204   // Consequently, its Math.sign value is not -0 either.
205   CHECK(EquivalentRanges(thenSign->range(),
206                          new (func.alloc)
207                              Range(-1, 0, Range::ExcludesFractionalParts,
208                                    Range::ExcludesNegativeZero, 0)));
209 
210   // On the (p >= 0) side, p is not negative and may be -0 (surprise!)
211   CHECK(EquivalentRanges(
212       elseThenAdd->range(),
213       new (func.alloc)
214           Range(0, Range::NoInt32UpperBound, Range::IncludesFractionalParts,
215                 Range::IncludesNegativeZero, Range::IncludesInfinity)));
216 
217   // Consequently, its Math.sign value may be -0 too.
218   CHECK(EquivalentRanges(elseThenSign->range(),
219                          new (func.alloc)
220                              Range(0, 1, Range::ExcludesFractionalParts,
221                                    Range::IncludesNegativeZero, 0)));
222 
223   // Otherwise, p may be NaN.
224   CHECK(elseElseAdd->range()->isUnknown());
225   CHECK(!elseElseSign->range());
226 
227   return true;
228 }
229 END_TEST(testJitRangeAnalysis_MathSignBeta)
230 
BEGIN_TEST(testJitRangeAnalysis_StrictCompareBeta)231 BEGIN_TEST(testJitRangeAnalysis_StrictCompareBeta) {
232   MinimalFunc func;
233 
234   MBasicBlock* entry = func.createEntryBlock();
235   MBasicBlock* thenBlock = func.createBlock(entry);
236   MBasicBlock* elseBlock = func.createBlock(entry);
237 
238   // if (p === 0)
239   MParameter* p = func.createParameter();
240   entry->add(p);
241   MConstant* c0 = MConstant::New(func.alloc, DoubleValue(0.0));
242   entry->add(c0);
243   MCompare* cmp = MCompare::New(func.alloc, p, c0, JSOp::StrictEq,
244                                 MCompare::Compare_Double);
245   entry->add(cmp);
246   auto* test = MTest::New(func.alloc, cmp, thenBlock, elseBlock);
247   entry->end(test);
248 
249   // {
250   //   return p + -0;
251   // }
252   MConstant* cm0 = MConstant::New(func.alloc, DoubleValue(-0.0));
253   thenBlock->add(cm0);
254   MAdd* thenAdd = MAdd::New(func.alloc, p, cm0, MIRType::Double);
255   thenBlock->add(thenAdd);
256   MReturn* thenRet = MReturn::New(func.alloc, thenAdd);
257   thenBlock->end(thenRet);
258 
259   // else
260   // {
261   //   return 0;
262   // }
263   MReturn* elseRet = MReturn::New(func.alloc, c0);
264   elseBlock->end(elseRet);
265 
266   // If range analysis inserts a beta node for p, it will be able to compute
267   // a meaningful range for p + -0.
268 
269   auto replaceCompare = [&](auto compareType) {
270     auto* newCmp =
271         MCompare::New(func.alloc, p, c0, JSOp::StrictEq, compareType);
272     entry->insertBefore(cmp, newCmp);
273     test->replaceOperand(0, newCmp);
274     cmp = newCmp;
275   };
276 
277   // We can't do beta node insertion with StrictEq and a non-numeric
278   // comparison though.
279   for (auto compareType :
280        {MCompare::Compare_Object, MCompare::Compare_String}) {
281     replaceCompare(compareType);
282 
283     if (!func.runRangeAnalysis()) {
284       return false;
285     }
286     CHECK(!thenAdd->range() || thenAdd->range()->isUnknown());
287     ClearDominatorTree(func.graph);
288   }
289 
290   // We can do it with a numeric comparison.
291   replaceCompare(MCompare::Compare_Double);
292   if (!func.runRangeAnalysis()) {
293     return false;
294   }
295   CHECK(EquivalentRanges(thenAdd->range(),
296                          Range::NewDoubleRange(func.alloc, 0.0, 0.0)));
297 
298   return true;
299 }
END_TEST(testJitRangeAnalysis_StrictCompareBeta)300 END_TEST(testJitRangeAnalysis_StrictCompareBeta)
301 
302 static void deriveShiftRightRange(int32_t lhsLower, int32_t lhsUpper,
303                                   int32_t rhsLower, int32_t rhsUpper,
304                                   int32_t* min, int32_t* max) {
305   // This is the reference algorithm and should be verifiable by inspection.
306   int64_t i, j;
307   *min = INT32_MAX;
308   *max = INT32_MIN;
309   for (i = lhsLower; i <= lhsUpper; i++) {
310     for (j = rhsLower; j <= rhsUpper; j++) {
311       int32_t r = int32_t(i) >> (int32_t(j) & 0x1f);
312       if (r > *max) *max = r;
313       if (r < *min) *min = r;
314     }
315   }
316 }
317 
checkShiftRightRange(int32_t lhsLow,int32_t lhsHigh,int32_t lhsInc,int32_t rhsLow,int32_t rhsHigh,int32_t rhsInc)318 static bool checkShiftRightRange(int32_t lhsLow, int32_t lhsHigh,
319                                  int32_t lhsInc, int32_t rhsLow,
320                                  int32_t rhsHigh, int32_t rhsInc) {
321   MinimalAlloc func;
322   int64_t lhsLower, lhsUpper, rhsLower, rhsUpper;
323 
324   for (lhsLower = lhsLow; lhsLower <= lhsHigh; lhsLower += lhsInc) {
325     for (lhsUpper = lhsLower; lhsUpper <= lhsHigh; lhsUpper += lhsInc) {
326       Range* lhsRange = Range::NewInt32Range(func.alloc, lhsLower, lhsUpper);
327       for (rhsLower = rhsLow; rhsLower <= rhsHigh; rhsLower += rhsInc) {
328         for (rhsUpper = rhsLower; rhsUpper <= rhsHigh; rhsUpper += rhsInc) {
329           if (!func.alloc.ensureBallast()) {
330             return false;
331           }
332 
333           Range* rhsRange =
334               Range::NewInt32Range(func.alloc, rhsLower, rhsUpper);
335           Range* result = Range::rsh(func.alloc, lhsRange, rhsRange);
336           int32_t min, max;
337           deriveShiftRightRange(lhsLower, lhsUpper, rhsLower, rhsUpper, &min,
338                                 &max);
339           if (!result->isInt32() || result->lower() != min ||
340               result->upper() != max) {
341             return false;
342           }
343         }
344       }
345     }
346   }
347   return true;
348 }
349 
BEGIN_TEST(testJitRangeAnalysis_shiftRight)350 BEGIN_TEST(testJitRangeAnalysis_shiftRight) {
351   CHECK(checkShiftRightRange(-16, 15, 1, 0, 31, 1));
352   CHECK(checkShiftRightRange(-8, 7, 1, -64, 63, 1));
353   return true;
354 }
355 END_TEST(testJitRangeAnalysis_shiftRight)
356 
BEGIN_TEST(testJitRangeAnalysis_MathCeil)357 BEGIN_TEST(testJitRangeAnalysis_MathCeil) {
358   MinimalAlloc func;
359 
360   Range* n0_5 = Range::NewDoubleSingletonRange(func.alloc, -0.5);
361   Range* n0_5Ceil = Range::ceil(func.alloc, n0_5);
362 
363   CHECK(n0_5Ceil);
364   CHECK(n0_5Ceil->canBeNegativeZero());
365 
366   return true;
367 }
368 END_TEST(testJitRangeAnalysis_MathCeil)
369