Quelle testJitRangeAnalysis.cpp Sprache: C

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
*/
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "jit/IonAnalysis.h"
#include "jit/MIRGenerator.h"
#include "jit/MIRGraph.h"
#include "jit/RangeAnalysis.h"

#include "jsapi-tests/testJitMinimalFunc.h"
#include "jsapi-tests/tests.h"

using namespace js;
using namespace js::jit;

static bool EquivalentRanges(const Range* a, const Range* b) {
  if (a->hasInt32UpperBound() != b->hasInt32UpperBound()) {
    return false;
  }
  if (a->hasInt32LowerBound() != b->hasInt32LowerBound()) {
    return false;
  }
  if (a->hasInt32UpperBound() && (a->upper() != b->upper())) {
    return false;
  }
  if (a->hasInt32LowerBound() && (a->lower() != b->lower())) {
    return false;
  }
  if (a->canHaveFractionalPart() != b->canHaveFractionalPart()) {
    return false;
  }
  if (a->canBeNegativeZero() != b->canBeNegativeZero()) {
    return false;
  }
  if (a->canBeNaN() != b->canBeNaN()) {
    return false;
  }
  if (a->canBeInfiniteOrNaN() != b->canBeInfiniteOrNaN()) {
    return false;
  }
  if (!a->canBeInfiniteOrNaN() && (a->exponent() != b->exponent())) {
    return false;
  }
  return true;
}

BEGIN_TEST(testJitRangeAnalysis_MathSign) {
  MinimalAlloc func;

  Range* xnan = new (func.alloc) Range();

  Range* ninf = Range::NewDoubleSingletonRange(
      func.alloc, mozilla::NegativeInfinity<double>());
  Range* n1_5 = Range::NewDoubleSingletonRange(func.alloc, -1.5);
  Range* n1_0 = Range::NewDoubleSingletonRange(func.alloc, -1);
  Range* n0_5 = Range::NewDoubleSingletonRange(func.alloc, -0.5);
  Range* n0_0 = Range::NewDoubleSingletonRange(func.alloc, -0.0);

  Range* p0_0 = Range::NewDoubleSingletonRange(func.alloc, 0.0);
  Range* p0_5 = Range::NewDoubleSingletonRange(func.alloc, 0.5);
  Range* p1_0 = Range::NewDoubleSingletonRange(func.alloc, 1.0);
  Range* p1_5 = Range::NewDoubleSingletonRange(func.alloc, 1.5);
  Range* pinf = Range::NewDoubleSingletonRange(
      func.alloc, mozilla::PositiveInfinity<double>());

  Range* xnanSign = Range::sign(func.alloc, xnan);

  Range* ninfSign = Range::sign(func.alloc, ninf);
  Range* n1_5Sign = Range::sign(func.alloc, n1_5);
  Range* n1_0Sign = Range::sign(func.alloc, n1_0);
  Range* n0_5Sign = Range::sign(func.alloc, n0_5);
  Range* n0_0Sign = Range::sign(func.alloc, n0_0);

  Range* p0_0Sign = Range::sign(func.alloc, p0_0);
  Range* p0_5Sign = Range::sign(func.alloc, p0_5);
  Range* p1_0Sign = Range::sign(func.alloc, p1_0);
  Range* p1_5Sign = Range::sign(func.alloc, p1_5);
  Range* pinfSign = Range::sign(func.alloc, pinf);

  CHECK(!xnanSign);
  CHECK(EquivalentRanges(ninfSign,
                         Range::NewInt32SingletonRange(func.alloc, -1)));
  CHECK(EquivalentRanges(n1_5Sign,
                         Range::NewInt32SingletonRange(func.alloc, -1)));
  CHECK(EquivalentRanges(n1_0Sign,
                         Range::NewInt32SingletonRange(func.alloc, -1)));

  // This should ideally be just -1, but range analysis can't represent the
  // specific fractional range of the constant.
  CHECK(EquivalentRanges(n0_5Sign, Range::NewInt32Range(func.alloc, -1, 0)));

  CHECK(EquivalentRanges(n0_0Sign,
                         Range::NewDoubleSingletonRange(func.alloc, -0.0)));

  CHECK(!n0_0Sign->canHaveFractionalPart());
  CHECK(n0_0Sign->canBeNegativeZero());
  CHECK(n0_0Sign->lower() == 0);
  CHECK(n0_0Sign->upper() == 0);

  CHECK(
      EquivalentRanges(p0_0Sign, Range::NewInt32SingletonRange(func.alloc, 0)));

  CHECK(!p0_0Sign->canHaveFractionalPart());
  CHECK(!p0_0Sign->canBeNegativeZero());
  CHECK(p0_0Sign->lower() == 0);
  CHECK(p0_0Sign->upper() == 0);

  // This should ideally be just 1, but range analysis can't represent the
  // specific fractional range of the constant.
  CHECK(EquivalentRanges(p0_5Sign, Range::NewInt32Range(func.alloc, 0, 1)));

  CHECK(
      EquivalentRanges(p1_0Sign, Range::NewInt32SingletonRange(func.alloc, 1)));
  CHECK(
      EquivalentRanges(p1_5Sign, Range::NewInt32SingletonRange(func.alloc, 1)));
  CHECK(
      EquivalentRanges(pinfSign, Range::NewInt32SingletonRange(func.alloc, 1)));

  return true;
}
END_TEST(testJitRangeAnalysis_MathSign)

BEGIN_TEST(testJitRangeAnalysis_MathSignBeta) {
  MinimalFunc func;

  MBasicBlock* entry = func.createEntryBlock();
  MBasicBlock* thenBlock = func.createBlock(entry);
  MBasicBlock* elseBlock = func.createBlock(entry);
  MBasicBlock* elseThenBlock = func.createBlock(elseBlock);
  MBasicBlock* elseElseBlock = func.createBlock(elseBlock);

  // if (p < 0)
  MParameter* p = func.createParameter();
  entry->add(p);
  MConstant* c0 = MConstant::New(func.alloc, DoubleValue(0.0));
  entry->add(c0);
  MConstant* cm0 = MConstant::New(func.alloc, DoubleValue(-0.0));
  entry->add(cm0);
  MCompare* cmp =
      MCompare::New(func.alloc, p, c0, JSOp::Lt, MCompare::Compare_Double);
  entry->add(cmp);
  entry->end(MTest::New(func.alloc, cmp, thenBlock, elseBlock));

  // {
  //   return Math.sign(p + -0);
  // }
  MAdd* thenAdd = MAdd::New(func.alloc, p, cm0, MIRType::Double);
  thenBlock->add(thenAdd);
  MSign* thenSign = MSign::New(func.alloc, thenAdd, MIRType::Double);
  thenBlock->add(thenSign);
  MReturn* thenRet = MReturn::New(func.alloc, thenSign);
  thenBlock->end(thenRet);

  // else
  // {
  //   if (p >= 0)
  MCompare* elseCmp =
      MCompare::New(func.alloc, p, c0, JSOp::Ge, MCompare::Compare_Double);
  elseBlock->add(elseCmp);
  elseBlock->end(MTest::New(func.alloc, elseCmp, elseThenBlock, elseElseBlock));

  //   {
  //     return Math.sign(p + -0);
  //   }
  MAdd* elseThenAdd = MAdd::New(func.alloc, p, cm0, MIRType::Double);
  elseThenBlock->add(elseThenAdd);
  MSign* elseThenSign = MSign::New(func.alloc, elseThenAdd, MIRType::Double);
  elseThenBlock->add(elseThenSign);
  MReturn* elseThenRet = MReturn::New(func.alloc, elseThenSign);
  elseThenBlock->end(elseThenRet);

  //   else
  //   {
  //     return Math.sign(p + -0);
  //   }
  // }
  MAdd* elseElseAdd = MAdd::New(func.alloc, p, cm0, MIRType::Double);
  elseElseBlock->add(elseElseAdd);
  MSign* elseElseSign = MSign::New(func.alloc, elseElseAdd, MIRType::Double);
  elseElseBlock->add(elseElseSign);
  MReturn* elseElseRet = MReturn::New(func.alloc, elseElseSign);
  elseElseBlock->end(elseElseRet);

  if (!func.runRangeAnalysis()) {
    return false;
  }

  CHECK(!p->range());
  CHECK(EquivalentRanges(c0->range(),
                         Range::NewDoubleSingletonRange(func.alloc, 0.0)));
  CHECK(EquivalentRanges(cm0->range(),
                         Range::NewDoubleSingletonRange(func.alloc, -0.0)));

  // On the (p < 0) side, p is negative and not -0 (surprise!)
  CHECK(EquivalentRanges(
      thenAdd->range(),
      new (func.alloc)
          Range(Range::NoInt32LowerBound, 0, Range::IncludesFractionalParts,
                Range::ExcludesNegativeZero, Range::IncludesInfinity)));

  // Consequently, its Math.sign value is not -0 either.
  CHECK(EquivalentRanges(thenSign->range(),
                         new (func.alloc)
                             Range(-1, 0, Range::ExcludesFractionalParts,
                                   Range::ExcludesNegativeZero, 0)));

  // On the (p >= 0) side, p is not negative and may be -0 (surprise!)
  CHECK(EquivalentRanges(
      elseThenAdd->range(),
      new (func.alloc)
          Range(0, Range::NoInt32UpperBound, Range::IncludesFractionalParts,
                Range::IncludesNegativeZero, Range::IncludesInfinity)));

  // Consequently, its Math.sign value may be -0 too.
  CHECK(EquivalentRanges(elseThenSign->range(),
                         new (func.alloc)
                             Range(0, 1, Range::ExcludesFractionalParts,
                                   Range::IncludesNegativeZero, 0)));

  // Otherwise, p may be NaN.
  CHECK(elseElseAdd->range()->isUnknown());
  CHECK(!elseElseSign->range());

  return true;
}
END_TEST(testJitRangeAnalysis_MathSignBeta)

BEGIN_TEST(testJitRangeAnalysis_StrictCompareBeta) {
  MinimalFunc func;

  MBasicBlock* entry = func.createEntryBlock();
  MBasicBlock* thenBlock = func.createBlock(entry);
  MBasicBlock* elseBlock = func.createBlock(entry);

  // if (p === 0)
  MParameter* p = func.createParameter();
  entry->add(p);
  MConstant* c0 = MConstant::New(func.alloc, DoubleValue(0.0));
  entry->add(c0);
  MCompare* cmp = MCompare::New(func.alloc, p, c0, JSOp::StrictEq,
                                MCompare::Compare_Double);
  entry->add(cmp);
  auto* test = MTest::New(func.alloc, cmp, thenBlock, elseBlock);
  entry->end(test);

  // {
  //   return p + -0;
  // }
  MConstant* cm0 = MConstant::New(func.alloc, DoubleValue(-0.0));
  thenBlock->add(cm0);
  MAdd* thenAdd = MAdd::New(func.alloc, p, cm0, MIRType::Double);
  thenBlock->add(thenAdd);
  MReturn* thenRet = MReturn::New(func.alloc, thenAdd);
  thenBlock->end(thenRet);

  // else
  // {
  //   return 0;
  // }
  MReturn* elseRet = MReturn::New(func.alloc, c0);
  elseBlock->end(elseRet);

  // If range analysis inserts a beta node for p, it will be able to compute
  // a meaningful range for p + -0.

  auto replaceCompare = [&](auto compareType) {
    auto* newCmp =
        MCompare::New(func.alloc, p, c0, JSOp::StrictEq, compareType);
    entry->insertBefore(cmp, newCmp);
    test->replaceOperand(0, newCmp);
    cmp = newCmp;
  };

  // We can't do beta node insertion with StrictEq and a non-numeric
  // comparison though.
  for (auto compareType :
       {MCompare::Compare_Object, MCompare::Compare_String}) {
    replaceCompare(compareType);

    if (!func.runRangeAnalysis()) {
      return false;
    }
    CHECK(!thenAdd->range() || thenAdd->range()->isUnknown());
    ClearDominatorTree(func.graph);
  }

  // We can do it with a numeric comparison.
  replaceCompare(MCompare::Compare_Double);
  if (!func.runRangeAnalysis()) {
    return false;
  }
  CHECK(EquivalentRanges(thenAdd->range(),
                         Range::NewDoubleRange(func.alloc, 0.0, 0.0)));

  return true;
}
END_TEST(testJitRangeAnalysis_StrictCompareBeta)

static void deriveShiftRightRange(int32_t lhsLower, int32_t lhsUpper,
                                  int32_t rhsLower, int32_t rhsUpper,
                                  int32_t* min, int32_t* max) {
  // This is the reference algorithm and should be verifiable by inspection.
  int64_t i, j;
  *min = INT32_MAX;
  *max = INT32_MIN;
  for (i = lhsLower; i <= lhsUpper; i++) {
    for (j = rhsLower; j <= rhsUpper; j++) {
      int32_t r = int32_t(i) >> (int32_t(j) & 0x1f);
      if (r > *max) *max = r;
      if (r < *min) *min = r;
    }
  }
}

static bool checkShiftRightRange(int32_t lhsLow, int32_t lhsHigh,
                                 int32_t lhsInc, int32_t rhsLow,
                                 int32_t rhsHigh, int32_t rhsInc) {
  MinimalAlloc func;
  int64_t lhsLower, lhsUpper, rhsLower, rhsUpper;

  for (lhsLower = lhsLow; lhsLower <= lhsHigh; lhsLower += lhsInc) {
    for (lhsUpper = lhsLower; lhsUpper <= lhsHigh; lhsUpper += lhsInc) {
      Range* lhsRange = Range::NewInt32Range(func.alloc, lhsLower, lhsUpper);
      for (rhsLower = rhsLow; rhsLower <= rhsHigh; rhsLower += rhsInc) {
        for (rhsUpper = rhsLower; rhsUpper <= rhsHigh; rhsUpper += rhsInc) {
          if (!func.alloc.ensureBallast()) {
            return false;
          }

          Range* rhsRange =
              Range::NewInt32Range(func.alloc, rhsLower, rhsUpper);
          Range* result = Range::rsh(func.alloc, lhsRange, rhsRange);
          int32_t min, max;
          deriveShiftRightRange(lhsLower, lhsUpper, rhsLower, rhsUpper, &min,
                                &max);
          if (!result->isInt32() || result->lower() != min ||
              result->upper() != max) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

BEGIN_TEST(testJitRangeAnalysis_shiftRight) {
  CHECK(checkShiftRightRange(-16, 15, 1, 0, 31, 1));
  CHECK(checkShiftRightRange(-8, 7, 1, -64, 63, 1));
  return true;
}
END_TEST(testJitRangeAnalysis_shiftRight)

BEGIN_TEST(testJitRangeAnalysis_MathCeil) {
  MinimalAlloc func;

  Range* n0_5 = Range::NewDoubleSingletonRange(func.alloc, -0.5);
  Range* n0_5Ceil = Range::ceil(func.alloc, n0_5);

  CHECK(n0_5Ceil);
  CHECK(n0_5Ceil->canBeNegativeZero());

  return true;
}
END_TEST(testJitRangeAnalysis_MathCeil)

quality89%

¤ Dauer der Verarbeitung: 0.12 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.