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