js/src/jsapi-tests/testJitRangeAnalysis.cpp

   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::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
 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 }
 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
 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
 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
 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)