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