testJitRangeAnalysis.cpp (12865B)
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 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 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 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::NewDouble(func.alloc, 0.0); 139 entry->add(c0); 140 MConstant* cm0 = MConstant::NewDouble(func.alloc, -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 // As 0 == -0, checking for (p < 0) implies that negative zero is excluded as 198 // well. So normally we should exclude -0 from the output, except that 199 // denormals might introduce extra confusion. 200 // 201 // What appears as 0, could be non-zero when seen in Range Analysis, while 202 // being zero when executed. As such we have to be conservative and include 203 // every possible outcome. 204 CHECK(EquivalentRanges( 205 thenAdd->range(), 206 new (func.alloc) 207 Range(Range::NoInt32LowerBound, 0, Range::IncludesFractionalParts, 208 Range::IncludesNegativeZero, Range::IncludesInfinity))); 209 210 // Consequently, its Math.sign value is not -0 either, but as we are 211 // conservative, we should include it here too. 212 CHECK(EquivalentRanges(thenSign->range(), 213 new (func.alloc) 214 Range(-1, 0, Range::ExcludesFractionalParts, 215 Range::IncludesNegativeZero, 0))); 216 217 // On the (p >= 0) side, p is not negative and may be -0 (surprise!) 218 CHECK(EquivalentRanges( 219 elseThenAdd->range(), 220 new (func.alloc) 221 Range(0, Range::NoInt32UpperBound, Range::IncludesFractionalParts, 222 Range::IncludesNegativeZero, Range::IncludesInfinity))); 223 224 // Consequently, its Math.sign value may be -0 too. 225 CHECK(EquivalentRanges(elseThenSign->range(), 226 new (func.alloc) 227 Range(0, 1, Range::ExcludesFractionalParts, 228 Range::IncludesNegativeZero, 0))); 229 230 // Otherwise, p may be NaN. 231 CHECK(elseElseAdd->range()->isUnknown()); 232 CHECK(!elseElseSign->range()); 233 234 return true; 235 } 236 END_TEST(testJitRangeAnalysis_MathSignBeta) 237 238 BEGIN_TEST(testJitRangeAnalysis_StrictCompareBeta) { 239 MinimalFunc func; 240 241 MBasicBlock* entry = func.createEntryBlock(); 242 MBasicBlock* thenBlock = func.createBlock(entry); 243 MBasicBlock* elseBlock = func.createBlock(entry); 244 245 // if (p === 0) 246 MParameter* p = func.createParameter(); 247 entry->add(p); 248 MConstant* c0 = MConstant::NewDouble(func.alloc, 0.0); 249 entry->add(c0); 250 MCompare* cmp = MCompare::New(func.alloc, p, c0, JSOp::StrictEq, 251 MCompare::Compare_Double); 252 entry->add(cmp); 253 auto* test = MTest::New(func.alloc, cmp, thenBlock, elseBlock); 254 entry->end(test); 255 256 // { 257 // return p + -0; 258 // } 259 MConstant* cm0 = MConstant::NewDouble(func.alloc, -0.0); 260 thenBlock->add(cm0); 261 MAdd* thenAdd = MAdd::New(func.alloc, p, cm0, MIRType::Double); 262 thenBlock->add(thenAdd); 263 MReturn* thenRet = MReturn::New(func.alloc, thenAdd); 264 thenBlock->end(thenRet); 265 266 // else 267 // { 268 // return 0; 269 // } 270 MReturn* elseRet = MReturn::New(func.alloc, c0); 271 elseBlock->end(elseRet); 272 273 // If range analysis inserts a beta node for p, it will be able to compute 274 // a meaningful range for p + -0. 275 276 auto replaceCompare = [&](auto compareType) { 277 auto* newCmp = 278 MCompare::New(func.alloc, p, c0, JSOp::StrictEq, compareType); 279 entry->insertBefore(cmp, newCmp); 280 test->replaceOperand(0, newCmp); 281 cmp = newCmp; 282 }; 283 284 // We can't do beta node insertion with StrictEq and a non-numeric 285 // comparison though. 286 for (auto compareType : 287 {MCompare::Compare_Object, MCompare::Compare_String}) { 288 replaceCompare(compareType); 289 290 if (!func.runRangeAnalysis()) { 291 return false; 292 } 293 CHECK(!thenAdd->range() || thenAdd->range()->isUnknown()); 294 ClearDominatorTree(func.graph); 295 } 296 297 // We can do it with a numeric comparison. 298 replaceCompare(MCompare::Compare_Double); 299 if (!func.runRangeAnalysis()) { 300 return false; 301 } 302 CHECK(EquivalentRanges(thenAdd->range(), 303 Range::NewDoubleRange(func.alloc, -0.0, 0.0))); 304 305 return true; 306 } 307 END_TEST(testJitRangeAnalysis_StrictCompareBeta) 308 309 static void deriveShiftRightRange(int32_t lhsLower, int32_t lhsUpper, 310 int32_t rhsLower, int32_t rhsUpper, 311 int32_t* min, int32_t* max) { 312 // This is the reference algorithm and should be verifiable by inspection. 313 int64_t i, j; 314 *min = INT32_MAX; 315 *max = INT32_MIN; 316 for (i = lhsLower; i <= lhsUpper; i++) { 317 for (j = rhsLower; j <= rhsUpper; j++) { 318 int32_t r = int32_t(i) >> (int32_t(j) & 0x1f); 319 if (r > *max) *max = r; 320 if (r < *min) *min = r; 321 } 322 } 323 } 324 325 static bool checkShiftRightRange(int32_t lhsLow, int32_t lhsHigh, 326 int32_t lhsInc, int32_t rhsLow, 327 int32_t rhsHigh, int32_t rhsInc) { 328 MinimalAlloc func; 329 int64_t lhsLower, lhsUpper, rhsLower, rhsUpper; 330 331 for (lhsLower = lhsLow; lhsLower <= lhsHigh; lhsLower += lhsInc) { 332 for (lhsUpper = lhsLower; lhsUpper <= lhsHigh; lhsUpper += lhsInc) { 333 Range* lhsRange = Range::NewInt32Range(func.alloc, lhsLower, lhsUpper); 334 for (rhsLower = rhsLow; rhsLower <= rhsHigh; rhsLower += rhsInc) { 335 for (rhsUpper = rhsLower; rhsUpper <= rhsHigh; rhsUpper += rhsInc) { 336 if (!func.alloc.ensureBallast()) { 337 return false; 338 } 339 340 Range* rhsRange = 341 Range::NewInt32Range(func.alloc, rhsLower, rhsUpper); 342 Range* result = Range::rsh(func.alloc, lhsRange, rhsRange); 343 int32_t min, max; 344 deriveShiftRightRange(lhsLower, lhsUpper, rhsLower, rhsUpper, &min, 345 &max); 346 if (!result->isInt32() || result->lower() != min || 347 result->upper() != max) { 348 return false; 349 } 350 } 351 } 352 } 353 } 354 return true; 355 } 356 357 BEGIN_TEST(testJitRangeAnalysis_shiftRight) { 358 CHECK(checkShiftRightRange(-16, 15, 1, 0, 31, 1)); 359 CHECK(checkShiftRightRange(-8, 7, 1, -64, 63, 1)); 360 return true; 361 } 362 END_TEST(testJitRangeAnalysis_shiftRight) 363 364 BEGIN_TEST(testJitRangeAnalysis_MathCeil) { 365 MinimalAlloc func; 366 367 Range* n0_5 = Range::NewDoubleSingletonRange(func.alloc, -0.5); 368 Range* n0_5Ceil = Range::ceil(func.alloc, n0_5); 369 370 CHECK(n0_5Ceil); 371 CHECK(n0_5Ceil->canBeNegativeZero()); 372 373 return true; 374 } 375 END_TEST(testJitRangeAnalysis_MathCeil)