test_simplify.cpp

#include <gtest/gtest.h>
#include <test/cpp/tensorexpr/test_base.h>

#include <test/cpp/tensorexpr/test_utils.h>
#include <torch/csrc/jit/tensorexpr/hash_provider.h>
#include <torch/csrc/jit/tensorexpr/ir_simplifier.h>
#include <torch/csrc/jit/tensorexpr/loopnest.h>

#include <cmath>

namespace torch {
namespace jit {
using namespace torch::jit::tensorexpr;
using SimpleIRExprEval = ExprEval<SimpleIREvaluator>;

#define IS_NODE(T, node)                        \
  {                                             \
    auto* node_ = dynamic_cast<const T*>(node); \
    ASSERT_NE(nullptr, node_);                  \
  }

#define IS_NODE_WITH_NAME(T, node, name)     \
  auto* name = dynamic_cast<const T*>(node); \
  ASSERT_NE(nullptr, name);

#define IS_NODE_WITH_NAME_AND_CAST(T, node, name, Type)        \
  const T* name = nullptr;                                     \
  {                                                            \
    auto* node_ = dynamic_cast<const Cast*>(node);             \
    ASSERT_NE(nullptr, node_);                                 \
    ASSERT_EQ(node_->dtype().scalar_type(), ScalarType::Type); \
    name = dynamic_cast<const T*>(node_->src_value());         \
  }                                                            \
  ASSERT_NE(nullptr, name);

#define IS_IMM_WITH_VAL(T, node, val)                \
  {                                                  \
    auto* node_ = dynamic_cast<const T##Imm*>(node); \
    ASSERT_NE(nullptr, node_);                       \
    ASSERT_EQ(node_->value(), val);                  \
  }

#define IS_VAR_WITH_NAME(node, name)              \
  {                                               \
    auto* node_ = dynamic_cast<const Var*>(node); \
    ASSERT_NE(nullptr, node_);                    \
    ASSERT_EQ(node_->name_hint(), name);          \
  }

#define IS_BINOP_W_VARS(T, node, name, v1, v2) \
  const T* name = nullptr;                     \
  {                                            \
    name = dynamic_cast<const T*>(node);       \
    ASSERT_NE(nullptr, name);                  \
    IS_VAR_WITH_NAME(name->lhs(), v1);         \
    IS_VAR_WITH_NAME(name->rhs(), v2);         \
  }

#define IS_BINOP_W_CONST(T, node, name, v, c) \
  const T* name = nullptr;                    \
  {                                           \
    name = dynamic_cast<const T*>(node);      \
    ASSERT_NE(nullptr, name);                 \
    IS_VAR_WITH_NAME(name->lhs(), v);         \
    IS_IMM_WITH_VAL(Int, name->rhs(), c);     \
  }

#define IS_RAND(node)                                    \
  {                                                      \
    auto* node_ = dynamic_cast<const Intrinsics*>(node); \
    ASSERT_NE(nullptr, node_);                           \
    ASSERT_EQ(node_->op_type(), kRand);                  \
  }

TEST(Simplify, ConstantFoldSimple) {
  KernelScope kernel_scope;
  ExprHandle a(2.0f);
  ExprHandle b(3.0f);
  ExprHandle f = (a + b);

  ExprHandle newF = IRSimplifier::simplify(f);
  ASSERT_NE(newF.AsNode<FloatImm>(), nullptr);
  ASSERT_EQ(newF.AsNode<FloatImm>()->value(), 5);

  SimpleIRExprEval eval(newF);
  ASSERT_EQ(eval.value<float>(), 5.f);
}

TEST(Simplify, ConstantFoldTwoLayer) {
  KernelScope kernel_scope;
  ExprHandle a(2.0f);
  ExprHandle b(3.0f);
  ExprHandle c(4.0f);
  ExprHandle d(5.0f);
  ExprHandle f = (a + b) - (c + d);

  ExprHandle newF = IRSimplifier::simplify(f);
  ASSERT_NE(newF.AsNode<FloatImm>(), nullptr);
  ASSERT_EQ(newF.AsNode<FloatImm>()->value(), -4);

  SimpleIRExprEval eval(newF);
  ASSERT_EQ(eval.value<float>(), -4.f);
}

TEST(Simplify, ConstantFoldShifts) {
  KernelScope kernel_scope;
  ExprHandle a(7);
  ExprHandle b(2);
  ExprHandle c(3);
  ExprHandle f = ((a << b) << b) >> c;

  ExprHandle newF = IRSimplifier::simplify(f);
  ASSERT_NE(newF.AsNode<IntImm>(), nullptr);
  ASSERT_EQ(newF.AsNode<IntImm>()->value(), 14);

  SimpleIRExprEval eval(newF);
  ASSERT_EQ(eval.value<int>(), 7 << (4 - 3));
}

TEST(Simplify, ConstantFoldBitwise) {
  KernelScope kernel_scope;
  ExprHandle a(59);
  ExprHandle b(22);
  ExprHandle c(101);
  ExprHandle f = (a ^ b) & c;

  ExprHandle newF = IRSimplifier::simplify(f);
  ASSERT_NE(newF.AsNode<IntImm>(), nullptr);
  ASSERT_EQ(newF.AsNode<IntImm>()->value(), 37);

  SimpleIRExprEval eval(newF);
  ASSERT_EQ(eval.value<int>(), (59 ^ 22) & 101);
}

TEST(Simplify, ConstantFoldMultiOp) {
  KernelScope kernel_scope;
  ExprHandle a(2.0f);
  ExprHandle b(3.0f);
  ExprHandle c(4.0f);
  ExprHandle d(5.0f);
  ExprHandle e(6.0f);
  ExprHandle f(7.0f);
  ExprHandle fn = ((a / e) - (c + d)) * (f / b);

  ExprHandle newF = IRSimplifier::simplify(fn);
  ASSERT_NE(newF.AsNode<FloatImm>(), nullptr);

  SimpleIRExprEval eval(newF);
  SimpleIRExprEval ref(fn);

  ASSERT_EQ(eval.value<float>(), ref.value<float>());
}

TEST(Simplify, ConstantFoldMinMax) {
  KernelScope kernel_scope;
  ExprHandle a(12.0f);
  ExprHandle b(15.0f);
  ExprHandle c(17.0f);

  // x = max(12, min(15, 17)).
  ExprHandle minHandle = Min::make(b, c, true);
  ExprHandle fn = Max::make(a, minHandle, false);

  ASSERT_EQ(fn.dtype().scalar_type(), ScalarType::Float);

  ExprHandle newF = IRSimplifier::simplify(fn);
  ASSERT_NE(newF.AsNode<FloatImm>(), nullptr);

  SimpleIRExprEval eval(newF);
  ASSERT_EQ(eval.value<float>(), 15.f);
}

TEST(Simplify, ConstantFoldIntrinsics) {
  KernelScope kernel_scope;
  ExprHandle a(2.0f);
  ExprHandle b(3.0f);
  ExprHandle c(4.0f);
  ExprHandle powHandle = Intrinsics::make(kPow, a, b);
  ExprHandle sinHandle = Intrinsics::make(kSin, powHandle);
  ExprHandle modHandle = Intrinsics::make(kFmod, c, sinHandle);
  ExprHandle logHandle = Intrinsics::make(kLog10, modHandle);
  ExprHandle rndHandle = Intrinsics::make(kRound, logHandle);
  ExprHandle fn = Intrinsics::make(kAbs, rndHandle);

  ExprHandle newF = IRSimplifier::simplify(fn);
  ASSERT_NE(newF.AsNode<FloatImm>(), nullptr);
  ASSERT_EQ(newF.AsNode<FloatImm>()->value(), 1);

  SimpleIRExprEval eval(newF);
  SimpleIRExprEval ref(fn);

  ASSERT_EQ(eval.value<float>(), ref.value<float>());
}

TEST(Simplify, ConstantFoldCastToBool) {
  KernelScope kernel_scope;
  ExprHandle f = Cast::make(kBool, IntImm::make(0));
  ExprHandle newF = IRSimplifier::simplify(f);
  SimpleIRExprEval eval(newF);
  ASSERT_EQ(eval.value<bool>(), false);
}

TEST(Simplify, ConstantFoldWithVar) {
  KernelScope kernel_scope;
  {
    VarHandle x("x", kInt);
    ExprHandle body = x * (ExprHandle(2) + ExprHandle(4));

    ExprHandle newF = IRSimplifier::simplify(body);
    const Mul* root = newF.AsNode<Mul>();
    ASSERT_NE(root, nullptr);
    ASSERT_NE(dynamic_cast<const IntImm*>(root->lhs()), nullptr);

    SimpleIRExprEval eval(newF);
    eval.bindVar(x, ExprHandle(3));
    ASSERT_EQ(eval.value<int>(), 3 * (2 + 4));
  }

  {
    VarHandle x("x", kFloat);
    ExprHandle body = x * (ExprHandle(2.f) + ExprHandle(4.f));

    ExprHandle newF = IRSimplifier::simplify(body);
    const Mul* root = newF.AsNode<Mul>();
    ASSERT_NE(root, nullptr);
    ASSERT_NE(dynamic_cast<const FloatImm*>(root->rhs()), nullptr);

    SimpleIRExprEval eval(newF);
    eval.bindVar(x, ExprHandle(3.f));
    ASSERT_EQ(eval.value<float>(), 3 * (2 + 4));
  }
}

TEST(Simplify, ConditionalSelectFoldSimple) {
  KernelScope kernel_scope;
  ExprHandle a(3.0f);
  ExprHandle b(4.0f);
  ExprHandle c(3.0f);
  {
    ExprHandle f = (a > b);

    ExprHandle newF = IRSimplifier::simplify(f);
    ASSERT_NE(newF.AsNode<IntImm>(), nullptr);
    ASSERT_EQ(newF.AsNode<IntImm>()->value(), 0);

    SimpleIRExprEval eval(newF);
    ASSERT_EQ(eval.value<int>(), 0);
  }
  {
    ExprHandle f = (a < b);

    ExprHandle newF = IRSimplifier::simplify(f);
    ASSERT_NE(newF.AsNode<IntImm>(), nullptr);
    ASSERT_EQ(newF.AsNode<IntImm>()->value(), 1);

    SimpleIRExprEval eval(newF);
    ASSERT_EQ(eval.value<int>(), 1);
  }
  {
    ExprHandle f = (a == c);

    ExprHandle newF = IRSimplifier::simplify(f);
    ASSERT_NE(newF.AsNode<IntImm>(), nullptr);
    ASSERT_EQ(newF.AsNode<IntImm>()->value(), 1);

    SimpleIRExprEval eval(newF);
    ASSERT_EQ(eval.value<int>(), 1);
  }
  {
    ExprHandle f = (a != c);

    ExprHandle newF = IRSimplifier::simplify(f);
    ASSERT_NE(newF.AsNode<IntImm>(), nullptr);
    ASSERT_EQ(newF.AsNode<IntImm>()->value(), 0);

    SimpleIRExprEval eval(newF);
    ASSERT_EQ(eval.value<int>(), 0);
  }
}

TEST(Simplify, ConditionalSelectFoldTwoLayer) {
  KernelScope kernel_scope;
  ExprHandle a(3.0f);
  ExprHandle b(2.0f);
  ExprHandle c(2.0f);
  ExprHandle d(1.0f);
  {
    ExprHandle f = (a + b < c + d);

    ExprHandle newF = IRSimplifier::simplify(f);
    ASSERT_NE(newF.AsNode<IntImm>(), nullptr);
    ASSERT_EQ(newF.AsNode<IntImm>()->value(), 0);

    SimpleIRExprEval eval(newF);
    ASSERT_EQ(eval.value<int>(), 0);
  }
  {
    ExprHandle f = (a + b > c + d);

    ExprHandle newF = IRSimplifier::simplify(f);
    ASSERT_NE(newF.AsNode<IntImm>(), nullptr);
    ASSERT_EQ(newF.AsNode<IntImm>()->value(), 1);

    SimpleIRExprEval eval(newF);
    ASSERT_EQ(eval.value<int>(), 1);
  }
  {
    ExprHandle f = (a + d == b + c);

    ExprHandle newF = IRSimplifier::simplify(f);
    ASSERT_NE(newF.AsNode<IntImm>(), nullptr);
    ASSERT_EQ(newF.AsNode<IntImm>()->value(), 1);

    SimpleIRExprEval eval(newF);
    ASSERT_EQ(eval.value<int>(), 1);
  }
  {
    ExprHandle f = (a + d != b + c);

    ExprHandle newF = IRSimplifier::simplify(f);
    ASSERT_NE(newF.AsNode<IntImm>(), nullptr);
    ASSERT_EQ(newF.AsNode<IntImm>()->value(), 0);

    SimpleIRExprEval eval(newF);
    ASSERT_EQ(eval.value<int>(), 0);
  }
}

TEST(Simplify, ConditionalSelectFoldWithVar) {
  KernelScope kernel_scope;
  VarHandle x("x", kFloat);
  ExprHandle f = x < 4.f;

  ExprHandle newF = IRSimplifier::simplify(f);
  const IntImm* folded = newF.AsNode<IntImm>();
  ASSERT_EQ(folded, nullptr);

  {
    SimpleIRExprEval eval(newF);
    eval.bindVar(x, ExprHandle(3.f));
    ASSERT_EQ(eval.value<int>(), 1);
  }
  {
    SimpleIRExprEval eval(newF);
    eval.bindVar(x, ExprHandle(5.f));
    ASSERT_EQ(eval.value<int>(), 0);
  }
}

TEST(Simplify, UnFoldableExpr) {
  KernelScope kernel_scope;
  VarHandle x("x", kFloat);
  VarHandle y("y", kFloat);
  ExprHandle body = (ExprHandle(3) * x) + (ExprHandle(5) * y);

  ExprHandle newF = IRSimplifier::simplify(body);
  const Add* root = newF.AsNode<Add>();
  ASSERT_NE(root, nullptr);
  ASSERT_EQ(dynamic_cast<const FloatImm*>(root->lhs()), nullptr);
  ASSERT_EQ(dynamic_cast<const FloatImm*>(root->rhs()), nullptr);

  SimpleIRExprEval eval(newF);
  eval.bindVar(x, ExprHandle(3.f));
  eval.bindVar(y, ExprHandle(2.f));
  ASSERT_EQ(eval.value<float>(), 9 + 10);
}

TEST(Simplify, HashSimple) {
  KernelScope kernel_scope;
  VarHandle x("x", kFloat);
  ExprHandle a(2.0f);
  ExprHandle b(3.0f);
  ExprHandle f = a + b * x;

  HashProvider hasher;

  auto hash_x = hasher.hash(x.node());
  auto hash_a = hasher.hash(a.node());
  auto hash_f = hasher.hash(f.node());

  ASSERT_NE(hash_x, (size_t)0);
  ASSERT_NE(hash_a, (size_t)0);
  ASSERT_NE(hash_f, (size_t)0);
  ASSERT_NE(hash_x, hash_a);
  ASSERT_NE(hash_x, hash_f);
  ASSERT_NE(hash_a, hash_f);
}

TEST(Simplify, HashEquivalence) {
  KernelScope kernel_scope;
  VarHandle x("x", kFloat);
  VarHandle y("y", kFloat);
  ExprHandle f = (x * y) + (x * y);

  const Add* root = f.AsNode<Add>();
  ASSERT_NE(root, nullptr);

  HashProvider hasher;
  auto hash_f = hasher.hash(f.node());
  auto hash_l = hasher.hash(root->lhs());
  auto hash_r = hasher.hash(root->rhs());

  // Root not equal to either branch.
  ASSERT_NE(hash_f, hash_l);
  ASSERT_NE(hash_f, hash_r);
  // but branches are equal.
  ASSERT_EQ(hash_l, hash_r);

  // Still equivalent if separate.
  ExprHandle a(2);
  ExprHandle f2 = x + a / y;
  ExprHandle b(2);
  ExprHandle f3 = x + b / y;
  ASSERT_EQ(hasher.hash(f2.node()), hasher.hash(f3.node()));

  // Not equivalent if different vars (even with same name).
  VarHandle z("x", kFloat);
  ExprHandle f4 = z + b / y;
  ASSERT_NE(hasher.hash(f2.node()), hasher.hash(f4.node()));

  // Intrinsics sanity check.
  ExprHandle f5 = Intrinsics::make(kSin, x) * Intrinsics::make(kCos, x);
  ASSERT_NE(hasher.hash(f5.node()), (size_t)0);
}

TEST(Simplify, HashEquivalenceRand) {
  KernelScope kernel_scope;
  ExprHandle f =
      Intrinsics::make(kRand, kFloat) + Intrinsics::make(kRand, kInt);

  const Add* root = f.AsNode<Add>();
  ASSERT_NE(root, nullptr);

  HashProvider hasher;
  auto hash_f = hasher.hash(f.node());
  auto hash_l = hasher.hash(root->lhs());
  auto hash_r = hasher.hash(root->rhs());

  // Root not equal to either branch.
  ASSERT_NE(hash_f, hash_l);
  ASSERT_NE(hash_f, hash_r);
  // and branches are NOT equal.
  ASSERT_NE(hash_l, hash_r);
}

TEST(Simplify, HashEquivalenceAfterFolding) {
  KernelScope kernel_scope;
  VarHandle x("x", kFloat);
  ExprHandle a(2.0f);
  ExprHandle b(3.0f);
  ExprHandle c(5.0f);

  ExprHandle f1 = ((a + b) * x);
  ExprHandle f2 = (c * x);

  HashProvider hasher;
  auto hash_l = hasher.hash(f1.node());
  auto hash_r = hasher.hash(f2.node());

  // Root not equal to either branch, and branches not equal.
  ASSERT_NE(hash_l, hash_r);

  ExprHandle ff1 = IRSimplifier::simplify(f1);
  ExprHandle ff2 = IRSimplifier::simplify(f2);

  auto hash_l_n = hasher.hash(ff1.node());
  auto hash_r_n = hasher.hash(ff2.node());
  // but branches are now equal.
  ASSERT_EQ(hash_l_n, hash_r_n);
}

TEST(Simplify, HashDifferenceTypes) {
  KernelScope kernel_scope;

  HashProvider hasher;
  std::vector<const Expr*> immediates;

  immediates.push_back(new DoubleImm(1));
  immediates.push_back(new FloatImm(1));
  immediates.push_back(new HalfImm(1));
  immediates.push_back(new BoolImm(1));
  immediates.push_back(new CharImm(1));
  immediates.push_back(new ByteImm(1));
  immediates.push_back(new ShortImm(1));
  immediates.push_back(new IntImm(1));
  immediates.push_back(new LongImm(1));

  // Immediates of different types are not equal.
  for (unsigned int i = 0; i < immediates.size(); ++i) {
    for (unsigned int j = i + 1; j < immediates.size(); ++j) {
      ASSERT_NE(hasher.hash(immediates[i]), hasher.hash(immediates[j]));
    }
  }

  // But coerced immediates are if they are the same type:
  ExprHandle f1 = ExprHandle(2.f) + CharImm::make(1);
  ExprHandle f2 = Cast::make(kFloat, IntImm::make(3));

  ExprHandle ff1 = IRSimplifier::simplify(f1);
  ExprHandle ff2 = IRSimplifier::simplify(f2);

  ASSERT_EQ(hasher.hash(ff1.node()), hasher.hash(ff2.node()));
}

TEST(Simplify, HashLargeExpression) {
  KernelScope kernel_scope;
  constexpr int N = 1024;
  BufHandle a("A", {N}, kInt);
  BufHandle b("B", {N}, kInt);
  BufHandle c("C", {N}, kInt);
  auto mask = IntImm::make(1);
  VarHandle i("i", kInt);
  auto memcpy_stmt = For::make(
      i,
      0,
      N,
      Store::make(
          c,
          {i},
          CompareSelect::make(
              Load::make(a, {i}, mask),
              Load::make(b, {i}, mask),
              CompareSelectOperation::kEQ),
          mask));

  BufHandle d("D", {1}, kInt);
  BufHandle e("E", {1}, kInt);
  auto store_ramp_stmt = Store::make(
      e,
      {Ramp::make(0, 1, 4)},
      Load::make(d, {Ramp::make(0, 1, 4)}, Broadcast::make(IntImm::make(1), 4)),
      Broadcast::make(Cast::make(kInt, DoubleImm::make(1)), 4));

  auto if_stmt = Cond::make(
      CompareSelect::make(
          Load::make(a, {i}, mask),
          Load::make(b, {i}, mask),
          CompareSelectOperation::kGE),
      memcpy_stmt,
      store_ramp_stmt);

  HashProvider hasher;
  auto hash_r = hasher.hash(if_stmt);
  // We should not have to do any more work.
  ASSERT_TRUE(hasher.cachedHash(memcpy_stmt));
  auto hash_t = hasher.hash(memcpy_stmt);
  ASSERT_TRUE(hasher.cachedHash(store_ramp_stmt));
  auto hash_f = hasher.hash(store_ramp_stmt);

  // Root not equal to either branch, and branches not equal.
  ASSERT_NE(hash_r, hash_t);
  ASSERT_NE(hash_r, hash_f);
  ASSERT_NE(hash_t, hash_f);
}

TEST(Simplify, HashForLoopOptions) {
  KernelScope kernel_scope;
  constexpr int N = 1024;
  BufHandle a("A", {N}, kInt);
  BufHandle b("B", {N}, kInt);
  BufHandle c("C", {N}, kInt);
  auto mask = IntImm::make(1);
  VarHandle i("i", kInt);
  auto for_stmt = For::make(
      i,
      0,
      N,
      Store::make(
          c,
          {i},
          CompareSelect::make(
              Load::make(a, {i}, mask),
              Load::make(b, {i}, mask),
              CompareSelectOperation::kEQ),
          mask));

  HashProvider hasher;
  auto hash_before = hasher.hash(for_stmt);
  hasher.clearCache();

  for_stmt->set_gpu_block_index(LoopOptions::IDX_X);
  auto hash_block_idx = hasher.hash(for_stmt);
  hasher.clearCache();

  ASSERT_NE(hash_before, hash_block_idx);

  for_stmt->set_gpu_block_index(LoopOptions::IDX_UNSET);
  auto hash_reset = hasher.hash(for_stmt);
  hasher.clearCache();

  ASSERT_EQ(hash_before, hash_reset);
  for_stmt->set_gpu_thread_index(LoopOptions::IDX_X);
  auto hash_thread_idx = hasher.hash(for_stmt);

  ASSERT_NE(hash_before, hash_thread_idx);
  ASSERT_NE(hash_block_idx, hash_thread_idx);
}

/// (2 + x) + 4 => x + 6
TEST(Simplify, SimplifyAdd) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);

  VarHandle m("m", kInt);
  VarHandle n("n", kInt);
  VarHandle n_1("n_1", kInt);
  ExprHandle body = (ExprHandle(2) + x) + ExprHandle(4);

  ExprHandle simplified = IRSimplifier::simplify(body);
  const Add* root = simplified.AsNode<Add>();
  ASSERT_NE(root, nullptr);
  const Var* lhs = dynamic_cast<const Var*>(root->lhs());
  ASSERT_NE(lhs, nullptr);
  ASSERT_EQ(lhs->name_hint(), "x");
  const IntImm* rhs = dynamic_cast<const IntImm*>(root->rhs());
  ASSERT_NE(rhs, nullptr);
  ASSERT_EQ(rhs->value(), 6.f);
}

/// (2 - x) - 4 => -2 - x
TEST(Simplify, SimplifySub) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  ExprHandle body = (ExprHandle(2) - x) - ExprHandle(4);

  ExprHandle simplified = IRSimplifier::simplify(body);
  const Sub* root = simplified.AsNode<Sub>();
  ASSERT_NE(root, nullptr);
  const IntImm* lhs = dynamic_cast<const IntImm*>(root->lhs());
  ASSERT_NE(lhs, nullptr);
  ASSERT_EQ(lhs->value(), -2.f);
  const Var* rhs = dynamic_cast<const Var*>(root->rhs());
  ASSERT_NE(rhs, nullptr);
  ASSERT_EQ(rhs->name_hint(), "x");
}

/// 2 * (1 - x) - 4 => 2 * (-3 - x)
TEST(Simplify, SimplifyMultiLayer) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  ExprHandle body = ExprHandle(2) * ((ExprHandle(1) - x) - ExprHandle(4));
  ExprHandle simplified = IRSimplifier::simplify(body);
  IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
  IS_IMM_WITH_VAL(Int, mul->lhs(), 2);
  IS_NODE_WITH_NAME(Sub, mul->rhs(), sub);
  IS_IMM_WITH_VAL(Int, sub->lhs(), -3);
  IS_VAR_WITH_NAME(sub->rhs(), "x");
}

/// 2 * (3 * x) - (x * 4) => 2 * x
TEST(Simplify, SimplifyMultiTerm) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  ExprHandle body =
      (ExprHandle(2) * ((ExprHandle(3) * x)) - (x * ExprHandle(4)));

  ExprHandle simplified = IRSimplifier::simplify(body);
  const Mul* root = simplified.AsNode<Mul>();
  ASSERT_NE(root, nullptr);
  const IntImm* lhs = dynamic_cast<const IntImm*>(root->lhs());
  ASSERT_NE(lhs, nullptr);
  ASSERT_EQ(lhs->value(), 2);
  const Var* rhs = dynamic_cast<const Var*>(root->rhs());
  ASSERT_NE(rhs, nullptr);
  ASSERT_EQ(rhs->name_hint(), "x");
}

/// 2 * (3 * (long)x) - (x * 4) => 2 * x
TEST(Simplify, SimplifyCasts) {
  KernelScope kernel_scope;
  VarHandle x("x", kLong);
  ExprHandle body =
      (ExprHandle(2) * ((ExprHandle(3) * x)) - (x * ExprHandle(4)));

  ExprHandle simplified = IRSimplifier::simplify(body);
  const Mul* root = simplified.AsNode<Mul>();
  ASSERT_NE(root, nullptr);
  const LongImm* lhs = dynamic_cast<const LongImm*>(root->lhs());
  ASSERT_NE(lhs, nullptr);
  ASSERT_EQ(lhs->value(), 2);
  const Var* rhs = dynamic_cast<const Var*>(root->rhs());
  ASSERT_NE(rhs, nullptr);
  ASSERT_EQ(rhs->name_hint(), "x");
}

/// (x + 0) * 1 => x
TEST(Simplify, SimplifyEliminatesNoOps) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  ExprHandle body = (x + ExprHandle(0)) * 1;

  ExprHandle simplified = IRSimplifier::simplify(body);
  const Var* root = simplified.AsNode<Var>();
  ASSERT_NE(root, nullptr);
  ASSERT_EQ(root->name_hint(), "x");
}

/// Cannot simplify this.
TEST(Simplify, SimplifyMultiVar) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);
  ExprHandle body = x * 24 + y * 34;

  ExprHandle simplified = IRSimplifier::simplify(body);

  const Add* root = simplified.AsNode<Add>();
  ASSERT_NE(root, nullptr);
  const Mul* lhs = dynamic_cast<const Mul*>(root->lhs());
  ASSERT_NE(lhs, nullptr);
  const Var* varX = dynamic_cast<const Var*>(lhs->rhs());
  ASSERT_NE(varX, nullptr);
  ASSERT_EQ(varX->name_hint(), "y");
  const Mul* rhs = dynamic_cast<const Mul*>(root->rhs());
  ASSERT_NE(rhs, nullptr);
  const Var* varY = dynamic_cast<const Var*>(rhs->rhs());
  ASSERT_NE(varY, nullptr);
  ASSERT_EQ(varY->name_hint(), "x");
}

// x + 2 + y => x + y + 2
TEST(Simplify, DISABLED_SimplifyReorderings) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);
  ExprHandle body = x + 2 + y;
  ExprHandle simplified = IRSimplifier::simplify(body);

  const Add* root = simplified.AsNode<Add>();
  ASSERT_NE(root, nullptr);

  IS_NODE_WITH_NAME(Add, root->lhs(), rhs);
  IS_VAR_WITH_NAME(rhs->lhs(), "x");
  IS_VAR_WITH_NAME(rhs->rhs(), "y");
  IS_IMM_WITH_VAL(Int, root->rhs(), 2);
}

/// y + x * 0 => y
TEST(Simplify, SimplifyEliminatesVar) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);
  ExprHandle body = y + x * ExprHandle(0);

  ExprHandle simplified = IRSimplifier::simplify(body);
  IS_VAR_WITH_NAME(simplified.node(), "y");
}

TEST(Simplify, SimplifyAdds) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);

  {
    // (x + y) + (x + y) => 2 * (x + y)
    ExprHandle body = (x + y) + (x + y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), root);
    IS_IMM_WITH_VAL(Int, root->lhs(), 2);
    IS_NODE_WITH_NAME(Add, root->rhs(), add);
    IS_VAR_WITH_NAME(add->lhs(), "y");
    IS_VAR_WITH_NAME(add->rhs(), "x");
  }

  {
    // (x * y) + (x * y) => 2 * (x * y)
    ExprHandle body = (x * y) + (x * y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), root);
    IS_IMM_WITH_VAL(Int, root->lhs(), 2);
    IS_NODE_WITH_NAME(Mul, root->rhs(), mul);
    IS_VAR_WITH_NAME(mul->lhs(), "x");
    IS_VAR_WITH_NAME(mul->rhs(), "y");
  }

  {
    // (x - y) + (x - y) => 2 * (x - y)
    ExprHandle body = (x - y) + (x - y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 2);

    IS_NODE_WITH_NAME(Sub, mul->rhs(), rhs);
    IS_VAR_WITH_NAME(rhs->lhs(), "x");
    IS_VAR_WITH_NAME(rhs->rhs(), "y");
  }

  {
    // (x + x + x + x) => 4 * x
    ExprHandle body = (x + x + x + x);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), root);
    IS_IMM_WITH_VAL(Int, root->lhs(), 4);
    IS_VAR_WITH_NAME(root->rhs(), "x");
  }

  {
    // (x + 0) => x.
    ExprHandle body = x + 0;
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_VAR_WITH_NAME(simplified.node(), "x");
  }

  {
    // (x + 0.f) => float(x).
    ExprHandle body = x + 0.f;
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Cast, simplified.node(), cast);
    ASSERT_EQ(cast->dtype().scalar_type(), ScalarType::Float);
    IS_VAR_WITH_NAME(cast->src_value(), "x");
  }
}

TEST(Simplify, SimplifyMuls) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);

  {
    // (x + y) * (x + y) => (x + y) * (x + y)
    // We don't attempt to simplify mulitplication of polynomials since the
    // result is only very rarely more efficient.
    ExprHandle body = (x + y) * (x + y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_NODE_WITH_NAME(Add, mul->lhs(), lhs);
    IS_VAR_WITH_NAME(lhs->lhs(), "y");
    IS_VAR_WITH_NAME(lhs->rhs(), "x");
    IS_NODE_WITH_NAME(Add, mul->rhs(), rhs);
    IS_VAR_WITH_NAME(rhs->lhs(), "y");
    IS_VAR_WITH_NAME(rhs->rhs(), "x");
  }

  {
    // x * y * x * y => x * x * y * y
    // These get reordered only.
    ExprHandle body = x * y * x * y;
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul1);
    IS_NODE_WITH_NAME(Mul, mul1->lhs(), mul2);
    IS_NODE_WITH_NAME(Mul, mul2->lhs(), mul3);
    IS_VAR_WITH_NAME(mul1->rhs(), "y");
    IS_VAR_WITH_NAME(mul2->rhs(), "y");
    IS_VAR_WITH_NAME(mul3->lhs(), "x");
    IS_VAR_WITH_NAME(mul3->rhs(), "x");
  }

  {
    // 1 * (x * 1) => x
    // Ones cancel cleanly.
    ExprHandle body = ExprHandle(1) * (x * ExprHandle(1));
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_VAR_WITH_NAME(simplified.node(), "x");
  }

  {
    // 1.f * (x * 1.f) => x
    // Even float ones cancel cleanly, but carry their type.
    ExprHandle body = ExprHandle(1.f) * (x * ExprHandle(1.f));
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Cast, simplified.node(), cast);
    ASSERT_EQ(cast->dtype().scalar_type(), ScalarType::Float);
    IS_VAR_WITH_NAME(cast->src_value(), "x");
  }

  {
    // 1 * (x * 1.f) => x
    // One float is enough to cast the expr.
    ExprHandle body = ExprHandle(1) * (x * ExprHandle(1.f));
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Cast, simplified.node(), cast);
    ASSERT_EQ(cast->dtype().scalar_type(), ScalarType::Float);
    IS_VAR_WITH_NAME(cast->src_value(), "x");
  }

  {
    // 1 * (x * 0) => 0
    // Zeroes are eliminated.
    ExprHandle body = ExprHandle(1) * (x * ExprHandle(0));
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_IMM_WITH_VAL(Int, simplified.node(), 0);
  }

  {
    // 1 * (x * 0) => 0
    // But not for Float since nan * 0 = nan.
    ExprHandle body = ExprHandle(1.f) * (x * ExprHandle(0.f));
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_NODE_WITH_NAME(Cast, mul->lhs(), cast);
    ASSERT_EQ(cast->dtype().scalar_type(), ScalarType::Float);
    IS_VAR_WITH_NAME(cast->src_value(), "x");
    IS_IMM_WITH_VAL(Float, mul->rhs(), 0.0);
  }

  {
    // (x - y) * (x - y) => (x - y) * (x - y)
    // As with Add we don't attempt simplification of this.
    ExprHandle body = (x - y) * (x - y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_NODE_WITH_NAME(Sub, mul->lhs(), lhs);
    IS_VAR_WITH_NAME(lhs->lhs(), "x");
    IS_VAR_WITH_NAME(lhs->rhs(), "y");
    IS_NODE_WITH_NAME(Sub, mul->rhs(), rhs);
    IS_VAR_WITH_NAME(rhs->lhs(), "x");
    IS_VAR_WITH_NAME(rhs->rhs(), "y");
  }

  {
    // (x + y) * (x - y) => (x - y) * (x - y)
    // Don't simplify with different ops on each side.
    ExprHandle body = (x + y) * (x - y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_NODE_WITH_NAME(Add, mul->lhs(), lhs);
    IS_VAR_WITH_NAME(lhs->lhs(), "y");
    IS_VAR_WITH_NAME(lhs->rhs(), "x");
    IS_NODE_WITH_NAME(Sub, mul->rhs(), rhs);
    IS_VAR_WITH_NAME(rhs->lhs(), "x");
    IS_VAR_WITH_NAME(rhs->rhs(), "y");
  }
}

// Sub an expr from itself will result in zero.
TEST(Simplify, SimplifySubs) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);

  {
    // (x + y) - (x + y) => 0
    ExprHandle body = (x + y) - (x + y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 0);
  }

  {
    // (x * y) - (x * y) => 0
    ExprHandle body = (x * y) - (x * y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 0);
  }

  {
    // (x - y) - (x - y) => 0
    ExprHandle body = (x - y) - (x - y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 0);
  }

  {
    // (x + y) - 2 * (x + y) => -1 * x - y
    ExprHandle body = (x + y) - ExprHandle(2) * (x + y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Sub, simplified.node(), sub);
    IS_NODE_WITH_NAME(Mul, sub->lhs(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), -1);
    IS_VAR_WITH_NAME(mul->rhs(), "x");
    IS_VAR_WITH_NAME(sub->rhs(), "y");
  }

  {
    // (x + y) - y => x
    ExprHandle body = (x + y) - y;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_VAR_WITH_NAME(simplified.node(), "x");
  }

  {
    // (x - 0) => x.
    ExprHandle body = x - 0;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_VAR_WITH_NAME(simplified.node(), "x");
  }

  {
    // (x - 0.f) => x.
    // Simple enough to cancel in float.
    ExprHandle body = x - ExprHandle(0.f);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Cast, simplified.node(), cast);
    ASSERT_EQ(cast->dtype().scalar_type(), ScalarType::Float);
    IS_VAR_WITH_NAME(cast->src_value(), "x");
  }

  {
    // (x - (float)(y - y)) => x.
    ExprHandle body = x - Cast::make(kFloat, y - y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Cast, simplified.node(), cast);
    ASSERT_EQ(cast->dtype().scalar_type(), ScalarType::Float);
    IS_VAR_WITH_NAME(cast->src_value(), "x");
  }

  {
    // (x - y) - y => x - 2 * y
    ExprHandle body = (x - y) - y;
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Sub, simplified.node(), sub);
    IS_VAR_WITH_NAME(sub->lhs(), "x");
    IS_NODE_WITH_NAME(Mul, sub->rhs(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 2);
    IS_VAR_WITH_NAME(mul->rhs(), "y");
  }

  {
    // 2 * x - x => x
    ExprHandle body = (ExprHandle(2) * x) - x;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_VAR_WITH_NAME(simplified.node(), "x");
  }

  {
    // x - 2 * x = -1 * x
    // We don't have a unary negate, but this could be 0 -x I guess?
    ExprHandle body = x - (ExprHandle(2) * x);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);

    IS_IMM_WITH_VAL(Int, mul->lhs(), -1);
    IS_VAR_WITH_NAME(mul->rhs(), "x");
  }

  {
    // (x + y + 5) * (x - x) => 0
    // Cancelling out one side of Mul cancels both.
    ExprHandle body = (x + y + 5) * (x - x);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_IMM_WITH_VAL(Int, simplified.node(), 0);
  }

  {
    // Cancel out opaque modulus.
    ExprHandle body = (x % y + 2) - (x % y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 2);
  }

  {
    // Cancel out opaque modulus with a bit more going on.
    ExprHandle body = (x % y + (x * 2 - x - y * 0) - x + 2) - (x % y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 2);
  }

  {
    // Sub where result is negative.
    ExprHandle body = x - (x + 1);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), -1);
  }

  {
    // Sub where result is positive due to negative scalar on RHS.
    ExprHandle body = x - (x - 1);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 1);
  }

  {
    // Term - Polynomial sub where RHS must be negated.
    ExprHandle body = (x * 2) - (x * 2 + 1);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), -1);
  }

  {
    // Term - Polynomial sub where the result is a Term.
    ExprHandle body = (y * x * 2) - (x * y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);

    IS_VAR_WITH_NAME(mul->lhs(), "x");
    IS_VAR_WITH_NAME(mul->rhs(), "y");
  }

  {
    // Term - Polynomial sub where the result is a Polynomial.
    ExprHandle body = (x * 2) - (x + 1);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Sub, simplified.node(), sub);

    IS_VAR_WITH_NAME(sub->lhs(), "x");
    IS_IMM_WITH_VAL(Int, sub->rhs(), 1);
  }
}

TEST(Simplify, SimplifyDiv) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);

  {
    ExprHandle body = ExprHandle(0) / x;
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_IMM_WITH_VAL(Int, simplified.node(), 0);
  }

  {
    ExprHandle body = x / 1;
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_VAR_WITH_NAME(simplified.node(), "x");
  }
}

TEST(Simplify, SimplifyMod) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);
  VarHandle z("z", kInt);

  {
    // Constant folding works.
    ExprHandle body = ExprHandle(10) % 8;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 2);
  }

  {
    // x % x => 0
    ExprHandle body = x % x;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 0);
  }

  {
    // 0 % x => 0
    ExprHandle body = ExprHandle(0) % x;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 0);
  }

  {
    // x % 1 => 0
    ExprHandle body = x % 1;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 0);
  }

  {
    // Doesn't change unknown mods.
    // x % y => x % y
    ExprHandle body = x % y;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Mod, simplified.node(), mod);
    IS_VAR_WITH_NAME(mod->lhs(), "x");
    IS_VAR_WITH_NAME(mod->rhs(), "y");
  }

  {
    // don't touch if RHS is unknown.
    // 4 % x => 4 % x
    ExprHandle body = ExprHandle(4) % x;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Mod, simplified.node(), mod);
    IS_IMM_WITH_VAL(Int, mod->lhs(), 4);
    IS_VAR_WITH_NAME(mod->rhs(), "x");
  }

  {
    // don't touch if LHS is unknown.
    // x % 4 => x % 4
    ExprHandle body = x % 4;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Mod, simplified.node(), mod);
    IS_VAR_WITH_NAME(mod->lhs(), "x");
    IS_IMM_WITH_VAL(Int, mod->rhs(), 4);
  }

  {
    // if LHS is a multiple of RHS, mod is zero.
    // 2 * x % x => 0
    ExprHandle body = (x * 2) % x;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 0);
  }

  {
    // true even if the multiple is not constant.
    // x * y % x => 0
    ExprHandle body = (x * y) % x;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 0);
  }

  {
    // true with multiple unknown values in LHS.
    // x * y * z % x => 0
    ExprHandle body = (x * y * z) % x;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 0);
  }

  {
    // true if the denom is compound.
    // x * y * z % y * z => 0
    ExprHandle body = (x * y * z) % (y * z);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 0);
  }

  {
    // Sanity check true with scalars that are multiples.
    // 12 * x % 4 => 0
    ExprHandle body = (x * 12) % 4;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 0);
  }

  {
    // Sanity check not true if the smaller scalar is on LHS.
    // 4 * x % 12 => 4 * x % 12
    ExprHandle body = (x * 4) % 12;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Mod, simplified.node(), mod);
    IS_NODE_WITH_NAME(Mul, mod->lhs(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 4);
    IS_VAR_WITH_NAME(mul->rhs(), "x");
    IS_IMM_WITH_VAL(Int, mod->rhs(), 12);
  }

  {
    // Both scalar and symbolic in multiple.
    // (6 * x * y) % (3 * x * y) => 0
    ExprHandle body = (ExprHandle(6) * x * y) % (x * y * 3);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_IMM_WITH_VAL(Int, simplified.node(), 0);
  }
}

// Test that mixing ops together simplifies as expected.
TEST(Simplify, SimplifyMultiOp) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);

  {
    // (x * y) + (x - y) => (x + x * y) - y
    ExprHandle body = (x * y) + (x - y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Sub, simplified.node(), sub);
    IS_NODE_WITH_NAME(Add, sub->lhs(), add);
    IS_VAR_WITH_NAME(add->lhs(), "x");
    IS_NODE_WITH_NAME(Mul, add->rhs(), mul);
    IS_VAR_WITH_NAME(mul->lhs(), "x");
    IS_VAR_WITH_NAME(mul->rhs(), "y");
    IS_VAR_WITH_NAME(sub->rhs(), "y");
  }

  {
    // (x + y) - (x * y) => x + y - (x * y)
    ExprHandle body = (x + y) - (x * y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Sub, simplified.node(), sub);
    IS_NODE_WITH_NAME(Add, sub->lhs(), add);
    IS_NODE_WITH_NAME(Mul, sub->rhs(), mul);
    IS_VAR_WITH_NAME(add->lhs(), "y");
    IS_VAR_WITH_NAME(add->rhs(), "x");
    IS_VAR_WITH_NAME(mul->lhs(), "x");
    IS_VAR_WITH_NAME(mul->rhs(), "y");
  }

  {
    // (x - y) - (x + y) => -2 * y
    ExprHandle body = (x - y) - (x + y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), -2);
    IS_VAR_WITH_NAME(mul->rhs(), "y");
  }

  {
    // (x - 0) + (x * 1) - (x + 0) => x
    ExprHandle body = (x - 0) + (x * 1) - (x + 0);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_VAR_WITH_NAME(simplified.node(), "x");
  }

  {
    // (x - 0.f) + (x * 1.f) - (x + 0.f) => float(x) + float(x) - float(x)
    // Even in Float simple terms cancel out, but the variable ones cannot.
    ExprHandle body =
        (x - ExprHandle(0.f)) + (x * ExprHandle(1.f)) - (x + ExprHandle(0.f));
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Sub, simplified.node(), sub);
    IS_NODE_WITH_NAME(Add, sub->lhs(), add);
    IS_NODE_WITH_NAME(Cast, add->lhs(), cast1);
    IS_VAR_WITH_NAME(cast1->src_value(), "x");
    IS_NODE_WITH_NAME(Cast, add->rhs(), cast2);
    IS_VAR_WITH_NAME(cast2->src_value(), "x");
    IS_NODE_WITH_NAME(Cast, sub->rhs(), cast3);
    IS_VAR_WITH_NAME(cast3->src_value(), "x");
  }
}

// Test that chaining many ops together works as expected.
TEST(Simplify, SimplifyManyOps) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);

  {
    // x + y + x + x + y + y + x + y + x = 5 * x + 4 * y
    ExprHandle body = x + y + x + x + y + y + x + y + x;
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Add, simplified.node(), add);

    IS_NODE_WITH_NAME(Mul, add->lhs(), lhs);
    IS_IMM_WITH_VAL(Int, lhs->lhs(), 5);
    IS_VAR_WITH_NAME(lhs->rhs(), "x");

    IS_NODE_WITH_NAME(Mul, add->rhs(), rhs);
    IS_IMM_WITH_VAL(Int, rhs->lhs(), 4);
    IS_VAR_WITH_NAME(rhs->rhs(), "y");
  }

  {
    // x - y + x + x - y - y + x - y + x = 5 * x - 4 * y
    ExprHandle body = x - y + x + x - y - y + x - y + x;
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Sub, simplified.node(), add);

    IS_NODE_WITH_NAME(Mul, add->lhs(), lhs);
    IS_IMM_WITH_VAL(Int, lhs->lhs(), 5);
    IS_VAR_WITH_NAME(lhs->rhs(), "x");

    IS_NODE_WITH_NAME(Mul, add->rhs(), rhs);
    IS_IMM_WITH_VAL(Int, rhs->lhs(), 4);
    IS_VAR_WITH_NAME(rhs->rhs(), "y");
  }

  {
    // x + y + x - x - y - y + x + y + x = 3 * x
    ExprHandle body = x + y + x - x - y - y + x + y + x;
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 3);
    IS_VAR_WITH_NAME(mul->rhs(), "x");
  }
}

TEST(Simplify, SimplifyFactorization) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);

  {
    // (2 * x) + (2 * y) => 2 * (x + y)
    ExprHandle body = (ExprHandle(2) * x + ExprHandle(2) * y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 2);

    IS_NODE_WITH_NAME(Add, mul->rhs(), add);
    IS_VAR_WITH_NAME(add->lhs(), "y");
    IS_VAR_WITH_NAME(add->rhs(), "x");
  }

  {
    // Factorization when scalars have common divider.
    // (2 * x) + (4 * y) => 2 * (2 * y + x)
    ExprHandle body = (ExprHandle(2) * x + ExprHandle(4) * y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 2);

    IS_NODE_WITH_NAME(Add, mul->rhs(), add);
    IS_VAR_WITH_NAME(add->lhs(), "x");
    IS_NODE_WITH_NAME(Mul, add->rhs(), mul2);
    IS_IMM_WITH_VAL(Int, mul2->lhs(), 2);
    IS_VAR_WITH_NAME(mul2->rhs(), "y");
  }

  {
    // Factorization attempt without a common divider.
    // (2 * x) + (5 * y) =>  (5 * y) + (2 * x)
    ExprHandle body = (ExprHandle(2) * x + ExprHandle(5) * y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Add, simplified.node(), add);

    IS_NODE_WITH_NAME(Mul, add->lhs(), lhs);
    IS_IMM_WITH_VAL(Int, lhs->lhs(), 5);
    IS_VAR_WITH_NAME(lhs->rhs(), "y");

    IS_NODE_WITH_NAME(Mul, add->rhs(), rhs);
    IS_IMM_WITH_VAL(Int, rhs->lhs(), 2);
    IS_VAR_WITH_NAME(rhs->rhs(), "x");
  }

  {
    // Factorization after merging.
    // (2 * x) + (4 * y) + (8 * x + 6 * y) => 10 * (x + y)
    ExprHandle body = (ExprHandle(2) * x + ExprHandle(4) * y) +
        (ExprHandle(8) * x + ExprHandle(6) * y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 10);

    IS_NODE_WITH_NAME(Add, mul->rhs(), add);
    IS_VAR_WITH_NAME(add->lhs(), "y");
    IS_VAR_WITH_NAME(add->rhs(), "x");
  }

  {
    // Factorization with common divider but different signs.
    // (2 * x) + (-4 * y) => 2 * (x - 2 * y)
    ExprHandle body = (ExprHandle(2) * x + ExprHandle(-4) * y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 2);

    IS_NODE_WITH_NAME(Sub, mul->rhs(), sub);
    IS_VAR_WITH_NAME(sub->lhs(), "x");
    IS_NODE_WITH_NAME(Mul, sub->rhs(), mul2);
    IS_IMM_WITH_VAL(Int, mul2->lhs(), 2);
    IS_VAR_WITH_NAME(mul2->rhs(), "y");
  }

  {
    // Factorization with all negative numbers.
    // (-2 * x) + (-4 * y) => 2 * (-1 * x - 2 * y)
    ExprHandle body = ExprHandle(-2) * x + ExprHandle(-4) * y;
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 2);

    IS_NODE_WITH_NAME(Sub, mul->rhs(), sub);
    IS_NODE_WITH_NAME(Mul, sub->lhs(), mul2);
    IS_IMM_WITH_VAL(Int, mul2->lhs(), -1);
    IS_VAR_WITH_NAME(mul2->rhs(), "x");
    IS_NODE_WITH_NAME(Mul, sub->rhs(), mul3);
    IS_IMM_WITH_VAL(Int, mul3->lhs(), 2);
    IS_VAR_WITH_NAME(mul3->rhs(), "y");
  }

  {
    // The following test ensures that there in no infinite recursion during
    // factorization when negative numbers are involved.
    VarHandle a("a", kInt);
    VarHandle b("b", kInt);
    VarHandle c("c", kInt);
    VarHandle d("d", kInt);
    VarHandle e("e", kInt);
    VarHandle f("f", kInt);
    VarHandle g("g", kInt);
    VarHandle h("h", kInt);

    ExprHandle body = ExprHandle(0) + (ExprHandle(1024) * a) +
        (ExprHandle(-1) * b) + (ExprHandle(-1) * c) + (ExprHandle(1) * d) +
        (ExprHandle(1) * e) + (ExprHandle(32) * f) + (ExprHandle(-1024) * g) +
        (ExprHandle(-32) * h);
    ExprHandle simplified = IRSimplifier::simplify(body);

    // We only check for the top level nodes here, since the main purpose
    // here is ensure that this simplification completes.
    IS_NODE_WITH_NAME(Sub, simplified.node(), sub);
    IS_NODE_WITH_NAME(Mul, sub->rhs(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 1024);
    IS_VAR_WITH_NAME(mul->rhs(), "g");
  }
}

// (4 * x + y + z * 2) + (4 * x + y + z * 4) => 2 * (y + 3 * z + 4 * x)
TEST(Simplify, SimplifyFactorizeUneven) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);
  VarHandle z("z", kInt);
  ExprHandle body =
      (ExprHandle(4) * x + y + z * 2) + (ExprHandle(4) * x + y + z * 4);
  ExprHandle simplified = IRSimplifier::simplify(body);

  IS_NODE_WITH_NAME(Mul, simplified.node(), root);
  IS_IMM_WITH_VAL(Int, root->lhs(), 2);
  IS_NODE_WITH_NAME(Add, root->rhs(), add1);
  IS_NODE_WITH_NAME(Add, add1->lhs(), add2);

  IS_VAR_WITH_NAME(add2->lhs(), "y");
  IS_NODE_WITH_NAME(Mul, add2->rhs(), zmul);
  IS_NODE_WITH_NAME(Mul, add1->rhs(), xmul);

  IS_IMM_WITH_VAL(Int, xmul->lhs(), 4);
  IS_VAR_WITH_NAME(xmul->rhs(), "x");

  IS_IMM_WITH_VAL(Int, zmul->lhs(), 3);
  IS_VAR_WITH_NAME(zmul->rhs(), "z");
}

// (x * y) + (2 * x) * (x + y) => 3 * (x * y) + 2 * (x * x)
// This is kind of a placeholder test for variable factorization.
TEST(Simplify, SimplifyDeeperTerms) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);
  ExprHandle body = (x * y) + (ExprHandle(2) * x) * (x + y);
  ExprHandle simplified = IRSimplifier::simplify(body);

  IS_NODE_WITH_NAME(Add, simplified.node(), add);

  IS_NODE_WITH_NAME(Mul, add->lhs(), lhs);
  IS_IMM_WITH_VAL(Int, lhs->lhs(), 3);
  IS_NODE_WITH_NAME(Mul, lhs->rhs(), xyTerm);
  IS_VAR_WITH_NAME(xyTerm->lhs(), "x");
  IS_VAR_WITH_NAME(xyTerm->rhs(), "y");

  IS_NODE_WITH_NAME(Mul, add->rhs(), rhs);
  IS_IMM_WITH_VAL(Int, rhs->lhs(), 2);
  IS_NODE_WITH_NAME(Mul, rhs->rhs(), xxTerm);
  IS_VAR_WITH_NAME(xxTerm->rhs(), "x");
  IS_VAR_WITH_NAME(xxTerm->rhs(), "x");
}

// Tests the difference between two less trivial expressions.
// (m * (1 * n_1) + (n  + 1)) - (m *  (1 * n_1) + n) => 1
TEST(Simplify, SimplifyDeeperDifference) {
  KernelScope kernel_scope;
  VarHandle n("n", kInt);
  VarHandle n_1("n_1", kInt);
  VarHandle m("m", kInt);
  ExprHandle body =
      (m * (ExprHandle(1) * n_1) + (n + 1)) - (m * (ExprHandle(1) * n_1) + n);
  ExprHandle simplified = IRSimplifier::simplify(body);

  IS_IMM_WITH_VAL(Int, simplified.node(), 1);
}

// Test constant folding into the difference between expressions.
// 2 + char((m * (1 * n_1) + (n  + 1)) - (m *  (1 * n_1) + n)) => 3
TEST(Simplify, SimplifyFoldComplexDifference) {
  KernelScope kernel_scope;
  VarHandle n("n", kInt);
  VarHandle n_1("n_1", kInt);
  VarHandle m("m", kInt);
  ExprHandle body =
      (IntImm::make(2) +
       (Cast::make(
           kChar,
           (m * (ExprHandle(1) * n_1) + (n + 1)) -
               (m * (ExprHandle(1) * n_1) + n))));
  ExprHandle simplified = IRSimplifier::simplify(body);
  IS_IMM_WITH_VAL(Int, simplified.node(), 3);
}

TEST(Simplify, SimplifyIfComponents) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);
  ExprHandle body = IfThenElse::make(
      ((ExprHandle(5) - ExprHandle(4)) * x) > y,
      ExprHandle(2) * x - x,
      ExprHandle(2) * y - y);

  ExprHandle simplified = IRSimplifier::simplify(body);

  IS_NODE_WITH_NAME(IfThenElse, simplified.node(), ifexpr);

  IS_NODE_WITH_NAME(CompareSelect, ifexpr->condition(), cmp);
  ASSERT_EQ(cmp->compare_select_op(), kGT);
  IS_VAR_WITH_NAME(cmp->lhs(), "x");
  IS_VAR_WITH_NAME(cmp->rhs(), "y");

  IS_VAR_WITH_NAME(ifexpr->true_value(), "x");
  IS_VAR_WITH_NAME(ifexpr->false_value(), "y");
}

TEST(Simplify, SimplifyOpaqueTerms) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);

  {
    // 2 * x/y * x - x/y * y => y * x/y
    ExprHandle body = ((ExprHandle(2)) * (x / y) * y) - ((x / y) * y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_VAR_WITH_NAME(mul->lhs(), "y");
    IS_NODE_WITH_NAME(Div, mul->rhs(), div);
    IS_VAR_WITH_NAME(div->lhs(), "x");
    IS_VAR_WITH_NAME(div->rhs(), "y");
  }

  {
    // x%y - (x%y - 1) => 1
    ExprHandle body = (x % y) - ((x % y) - 1);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_IMM_WITH_VAL(Int, simplified.node(), 1);
  }
}

TEST(Simplify, SimplifySymbolicMinMax) {
  KernelScope kernel_scope;

  {
    // Minimum with constant difference between terms.
    VarHandle x("x", kInt);
    ExprHandle body = Min::make(x + 3, x + 7, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Add, simplified.node(), add);
    IS_VAR_WITH_NAME(add->lhs(), "x");
    IS_IMM_WITH_VAL(Int, add->rhs(), 3);
  }

  {
    // Maximum with constant difference between terms.
    VarHandle x("x", kInt);
    ExprHandle body = Max::make(x + 3, x + 7, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Add, simplified.node(), add);
    IS_VAR_WITH_NAME(add->lhs(), "x");
    IS_IMM_WITH_VAL(Int, add->rhs(), 7);
  }

  {
    // Can't simplify multiples because of signedness of variable component.
    // TODO: maybe we could for unsigned types?
    VarHandle x("x", kInt);
    ExprHandle body = Max::make(x * 3, x * 7, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE(Max, simplified.node());
  }
}

TEST(Simplify, SimplifyNestedMax) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);
  VarHandle z("z", kInt);

  {
    // Max(x + y, x + y) => x + y
    ExprHandle body = Max::make(x + y, x + y, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_BINOP_W_VARS(Add, simplified.node(), add, "y", "x");
  }

  {
    // Max(x + y, Max(x + y, z)) => Max(y + x, z)
    ExprHandle body = Max::make(x + y, Max::make(x + y, z, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max);
    IS_BINOP_W_VARS(Add, max->lhs(), add, "y", "x");
    IS_VAR_WITH_NAME(max->rhs(), "z");
  }

  {
    // Max(x + y, Max(z, x + y)) => Max(y + x, z)
    ExprHandle body = Max::make(x + y, Max::make(z, x + y, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max);
    IS_BINOP_W_VARS(Add, max->lhs(), add, "y", "x");
    IS_VAR_WITH_NAME(max->rhs(), "z");
  }

  {
    // Max(Max(x + y, z), x + y) => Max(y + x, z)
    ExprHandle body = Max::make(Max::make(x + y, z, true), x + y, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max);
    IS_BINOP_W_VARS(Add, max->lhs(), add, "y", "x");
    IS_VAR_WITH_NAME(max->rhs(), "z");
  }

  {
    // Max(Max(z, x + y), x + y) => Max(y + x, z)
    ExprHandle body = Max::make(Max::make(z, x + y, true), x + y, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max);
    IS_BINOP_W_VARS(Add, max->lhs(), add, "y", "x");
    IS_VAR_WITH_NAME(max->rhs(), "z");
  }

  {
    // Max(Max(x, y), x) => Max(Max(x, y), x)
    // Nested Max ops with different propagate_nans should not be simplified.
    ExprHandle body = Max::make(Max::make(x, y, true), x, false);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max);
    IS_BINOP_W_VARS(Max, max->lhs(), max1, "x", "y");
    ASSERT_TRUE(max1->propagate_nans());
    IS_VAR_WITH_NAME(max->rhs(), "x");
    ASSERT_FALSE(max->propagate_nans());
  }

  {
    // Max(Min(x, y), Min(x, z)) => Min(x, Max(y, z))
    ExprHandle body =
        Max::make(Min::make(x, y, true), Min::make(x, z, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min);
    IS_VAR_WITH_NAME(min->lhs(), "x");
    IS_BINOP_W_VARS(Max, min->rhs(), max, "y", "z");
    ASSERT_TRUE(max->propagate_nans());
  }

  {
    // Max(Min(x, y), Min(z, x)) => Min(x, Max(y, z))
    ExprHandle body =
        Max::make(Min::make(x, y, true), Min::make(z, x, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min);
    IS_VAR_WITH_NAME(min->lhs(), "x");
    IS_BINOP_W_VARS(Max, min->rhs(), max, "y", "z");
    ASSERT_TRUE(max->propagate_nans());
  }

  {
    // Max(Min(y, x), Min(x, z)) => Min(x, Max(y, z))
    ExprHandle body =
        Max::make(Min::make(y, x, true), Min::make(x, z, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min);
    IS_VAR_WITH_NAME(min->lhs(), "x");
    IS_BINOP_W_VARS(Max, min->rhs(), max, "y", "z");
    ASSERT_TRUE(max->propagate_nans());
  }

  {
    // Max(Min(y, x), Min(z, x)) => Min(x, Max(y, z))
    ExprHandle body =
        Max::make(Min::make(y, x, true), Min::make(z, x, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min);
    IS_VAR_WITH_NAME(min->lhs(), "x");
    IS_BINOP_W_VARS(Max, min->rhs(), max, "y", "z");
    ASSERT_TRUE(max->propagate_nans());
  }

  {
    // Max(Min(y, x), Min(z, x)) => Max(Min(x, z), Min(x, y))
    // When all the ops in the pattern do not have the same propagate_nans,
    // it should not be simplified.
    ExprHandle body =
        Max::make(Min::make(y, x, true), Min::make(z, x, false), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max);
    IS_BINOP_W_VARS(Min, max->lhs(), min1, "x", "z");
    ASSERT_FALSE(min1->propagate_nans());
    IS_BINOP_W_VARS(Min, max->rhs(), min2, "x", "y");
    ASSERT_TRUE(min2->propagate_nans());
    ASSERT_TRUE(max->propagate_nans());
  }

  {
    // Max(5, Max(x, 8)) => Max(x, 8)
    ExprHandle body = Max::make(5, Max::make(x, 8, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_BINOP_W_CONST(Max, simplified.node(), max, "x", 8);
    ASSERT_TRUE(max->propagate_nans());
  }

  {
    // Max(8, Max(x, 5)) => Max(x, 8)
    ExprHandle body = Max::make(8, Max::make(x, 5, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_BINOP_W_CONST(Max, simplified.node(), max, "x", 8);
    ASSERT_TRUE(max->propagate_nans());
  }

  {
    // Max(Max(x, 8), 5) => Max(x, 8)
    ExprHandle body = Max::make(Max::make(x, 8, true), 5, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_BINOP_W_CONST(Max, simplified.node(), max, "x", 8);
    ASSERT_TRUE(max->propagate_nans());
  }

  {
    // Max(Max(x, 5), 8) => Max(x, 8)
    ExprHandle body = Max::make(Max::make(x, 5, true), 8, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_BINOP_W_CONST(Max, simplified.node(), max, "x", 8);
    ASSERT_TRUE(max->propagate_nans());
  }

  {
    // Max(5, Max(x, Max(y, Max(z, 8)))) => Max(Max(Max(x, 8), y), z)
    ExprHandle body = Max::make(
        5, Max::make(x, Max::make(y, Max::make(z, 8, true), true), true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max1);
    IS_NODE_WITH_NAME(Max, max1->lhs(), max2);
    IS_BINOP_W_CONST(Max, max2->lhs(), max3, "x", 8);
    ASSERT_TRUE(max3->propagate_nans());
    IS_VAR_WITH_NAME(max2->rhs(), "y");
    IS_VAR_WITH_NAME(max1->rhs(), "z");
  }

  {
    // Max(8, Max(Max(y, Max(z, 5)), x)) => Max(Max(Max(x, 8), y), z)
    ExprHandle body = Max::make(
        8, Max::make(Max::make(y, Max::make(z, 5, true), true), x, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max1);
    IS_NODE_WITH_NAME(Max, max1->lhs(), max2);
    IS_BINOP_W_CONST(Max, max2->lhs(), max3, "x", 8);
    ASSERT_TRUE(max3->propagate_nans());
    IS_VAR_WITH_NAME(max2->rhs(), "y");
    IS_VAR_WITH_NAME(max1->rhs(), "z");
  }

  {
    // Max(5, Max(Max(Max(z, 8), y), x)) => Max(Max(Max(x, 8), y), z)
    ExprHandle body = Max::make(
        5, Max::make(Max::make(Max::make(z, 8, true), y, true), x, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max1);
    IS_NODE_WITH_NAME(Max, max1->lhs(), max2);
    IS_BINOP_W_CONST(Max, max2->lhs(), max3, "x", 8);
    ASSERT_TRUE(max3->propagate_nans());
    IS_VAR_WITH_NAME(max2->rhs(), "y");
    IS_VAR_WITH_NAME(max1->rhs(), "z");
  }

  {
    // Max(Max(x, Max(y, Max(5, z))), 8) => Max(Max(Max(x, 8), y), z)
    ExprHandle body = Max::make(
        Max::make(x, Max::make(y, Max::make(5, z, true), true), true), 8, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max1);
    IS_NODE_WITH_NAME(Max, max1->lhs(), max2);
    IS_BINOP_W_CONST(Max, max2->lhs(), max3, "x", 8);
    ASSERT_TRUE(max3->propagate_nans());
    IS_VAR_WITH_NAME(max2->rhs(), "y");
    IS_VAR_WITH_NAME(max1->rhs(), "z");
  }

  {
    // Max(Max(Max(y, Max(8, z)), x), 5) => Max(Max(Max(x, 8), y), z)
    ExprHandle body = Max::make(
        Max::make(Max::make(y, Max::make(z, 8, true), true), x, true), 5, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max1);
    IS_NODE_WITH_NAME(Max, max1->lhs(), max2);
    IS_BINOP_W_CONST(Max, max2->lhs(), max3, "x", 8);
    ASSERT_TRUE(max3->propagate_nans());
    IS_VAR_WITH_NAME(max2->rhs(), "y");
    IS_VAR_WITH_NAME(max1->rhs(), "z");
  }

  {
    // Max(Max(Max(Max(5, z), y), x), 8) => Max(Max(Max(x, 8), y), z)
    ExprHandle body = Max::make(
        Max::make(Max::make(Max::make(z, 5, true), y, true), x, true), 8, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max1);
    IS_NODE_WITH_NAME(Max, max1->lhs(), max2);
    IS_BINOP_W_CONST(Max, max2->lhs(), max3, "x", 8);
    ASSERT_TRUE(max3->propagate_nans());
    IS_VAR_WITH_NAME(max2->rhs(), "y");
    IS_VAR_WITH_NAME(max1->rhs(), "z");
  }

  {
    // Max(Max(Max(Max(z, 5), y), x), 8) => Max(Max(x, Max(Max(z, 5), y)), 8)
    // Do not simplify when all the Max ops do not have the same
    // propagate_nans.
    ExprHandle body = Max::make(
        Max::make(Max::make(Max::make(z, 5, true), y, false), x, true),
        8,
        false);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max1);
    IS_NODE_WITH_NAME(Max, max1->lhs(), max2);
    IS_VAR_WITH_NAME(max2->lhs(), "x");
    IS_NODE_WITH_NAME(Max, max2->rhs(), max3);
    IS_BINOP_W_CONST(Max, max3->lhs(), max4, "z", 5);
    ASSERT_TRUE(max4->propagate_nans());
    IS_VAR_WITH_NAME(max3->rhs(), "y");
    ASSERT_FALSE(max3->propagate_nans());
    ASSERT_TRUE(max2->propagate_nans());
    IS_IMM_WITH_VAL(Int, max1->rhs(), 8);
    ASSERT_FALSE(max1->propagate_nans());
  }

  {
    // Max(8, Max(Max(x, 5), Max(y, z))) => Max(Max(Max(x, 8), y), z)
    ExprHandle body = Max::make(
        8, Max::make(Max::make(x, 5, true), Max::make(y, z, true), true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max1);
    IS_NODE_WITH_NAME(Max, max1->lhs(), max2);
    IS_BINOP_W_CONST(Max, max2->lhs(), max3, "x", 8);
    ASSERT_TRUE(max3->propagate_nans());
    IS_VAR_WITH_NAME(max2->rhs(), "y");
    IS_VAR_WITH_NAME(max1->rhs(), "z");
  }

  {
    // Max(Max(Max(x, 5), Max(y, z)), 8) => Max(Max(Max(x, 8), y), z)
    ExprHandle body = Max::make(
        Max::make(Max::make(x, 5, true), Max::make(y, z, true), true), 8, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max1);
    IS_NODE_WITH_NAME(Max, max1->lhs(), max2);
    IS_BINOP_W_CONST(Max, max2->lhs(), max3, "x", 8);
    ASSERT_TRUE(max3->propagate_nans());
    IS_VAR_WITH_NAME(max2->rhs(), "y");
    IS_VAR_WITH_NAME(max1->rhs(), "z");
  }
}

TEST(Simplify, SimplifyNestedMin) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);
  VarHandle z("z", kInt);

  {
    // Min(x + y, x + y) => x + y
    ExprHandle body = Min::make(x + y, x + y, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_BINOP_W_VARS(Add, simplified.node(), add, "y", "x");
  }

  {
    // Min(x + y, Min(x + y, z)) => Min(y + x, z)
    ExprHandle body = Min::make(x + y, Min::make(x + y, z, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min);
    IS_BINOP_W_VARS(Add, min->lhs(), add, "y", "x");
    IS_VAR_WITH_NAME(min->rhs(), "z");
  }

  {
    // Min(x + y, Min(z, x + y)) => Min(y + x, z)
    ExprHandle body = Min::make(x + y, Min::make(z, x + y, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min);
    IS_BINOP_W_VARS(Add, min->lhs(), add, "y", "x");
    IS_VAR_WITH_NAME(min->rhs(), "z");
  }

  {
    // Min(Min(x + y, z), x + y) => Min(y + x, z)
    ExprHandle body = Min::make(Min::make(x + y, z, true), x + y, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min);
    IS_BINOP_W_VARS(Add, min->lhs(), add, "y", "x");
    IS_VAR_WITH_NAME(min->rhs(), "z");
  }

  {
    // Min(Min(z, x + y), x + y) => Min(y + x, z)
    ExprHandle body = Min::make(Min::make(z, x + y, true), x + y, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min);
    IS_BINOP_W_VARS(Add, min->lhs(), add, "y", "x");
    IS_VAR_WITH_NAME(min->rhs(), "z");
  }

  {
    // Min(Min(x, y), x) => Min(Min(x, y), x)
    // Nested Min ops with different propagate_nans should not be simplified.
    ExprHandle body = Min::make(Min::make(x, y, true), x, false);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min1);
    IS_BINOP_W_VARS(Min, min1->lhs(), min2, "x", "y");
    ASSERT_TRUE(min2->propagate_nans());
    IS_VAR_WITH_NAME(min1->rhs(), "x");
    ASSERT_FALSE(min1->propagate_nans());
  }

  {
    // Min(Max(x, y), Max(x, z)) => Max(x, Min(y, z))
    ExprHandle body =
        Min::make(Max::make(x, y, true), Max::make(x, z, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max);
    IS_VAR_WITH_NAME(max->lhs(), "x");
    IS_BINOP_W_VARS(Min, max->rhs(), min, "y", "z");
    ASSERT_TRUE(min->propagate_nans());
  }

  {
    // Min(Max(x, y), Max(z, x)) => Max(x, Min(y, z))
    ExprHandle body =
        Min::make(Max::make(x, y, true), Max::make(z, x, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max);
    IS_VAR_WITH_NAME(max->lhs(), "x");
    IS_BINOP_W_VARS(Min, max->rhs(), min, "y", "z");
    ASSERT_TRUE(min->propagate_nans());
  }

  {
    // Min(Max(y, x), Max(x, z)) => Max(x, Min(y, z))
    ExprHandle body =
        Min::make(Max::make(y, x, true), Max::make(x, z, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max);
    IS_VAR_WITH_NAME(max->lhs(), "x");
    IS_BINOP_W_VARS(Min, max->rhs(), min, "y", "z");
    ASSERT_TRUE(min->propagate_nans());
  }

  {
    // Min(Max(y, x), Max(z, x)) => Max(x, Min(y, z))
    ExprHandle body =
        Min::make(Max::make(y, x, true), Max::make(z, x, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Max, simplified.node(), max);
    IS_VAR_WITH_NAME(max->lhs(), "x");
    IS_BINOP_W_VARS(Min, max->rhs(), min, "y", "z");
    ASSERT_TRUE(min->propagate_nans());
  }

  {
    // Min(Max(y, x), Max(z, x)) => Min(Max(x, z), Max(x, y))
    // When all the ops in the pattern do not have the same propagate_nans,
    // it should not be simplified.
    ExprHandle body =
        Min::make(Max::make(y, x, true), Max::make(z, x, false), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min);
    IS_BINOP_W_VARS(Max, min->lhs(), max1, "x", "z");
    ASSERT_FALSE(max1->propagate_nans());
    IS_BINOP_W_VARS(Max, min->rhs(), max2, "x", "y");
    ASSERT_TRUE(max2->propagate_nans());
    ASSERT_TRUE(min->propagate_nans());
  }

  {
    // Min(5, Min(x, 8)) => Min(x, 8)
    ExprHandle body = Min::make(5, Min::make(x, 8, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_BINOP_W_CONST(Min, simplified.node(), min, "x", 5);
    ASSERT_TRUE(min->propagate_nans());
  }

  {
    // Min(8, Min(x, 5)) => Min(x, 8)
    ExprHandle body = Min::make(8, Min::make(x, 5, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_BINOP_W_CONST(Min, simplified.node(), min, "x", 5);
    ASSERT_TRUE(min->propagate_nans());
  }

  {
    // Min(Min(x, 8), 5) => Min(x, 8)
    ExprHandle body = Min::make(Min::make(x, 8, true), 5, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_BINOP_W_CONST(Min, simplified.node(), min, "x", 5);
    ASSERT_TRUE(min->propagate_nans());
  }

  {
    // Min(Min(x, 5), 8) => Min(x, 8)
    ExprHandle body = Min::make(Min::make(x, 5, true), 8, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_BINOP_W_CONST(Min, simplified.node(), min, "x", 5);
    ASSERT_TRUE(min->propagate_nans());
  }

  {
    // Min(5, Min(x, Min(y, Min(z, 8)))) => Min(Min(Min(x, 5), y), z)
    ExprHandle body = Min::make(
        5, Min::make(x, Min::make(y, Min::make(z, 8, true), true), true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min1);
    IS_NODE_WITH_NAME(Min, min1->lhs(), min2);
    IS_BINOP_W_CONST(Min, min2->lhs(), min3, "x", 5);
    ASSERT_TRUE(min3->propagate_nans());
    IS_VAR_WITH_NAME(min2->rhs(), "y");
    IS_VAR_WITH_NAME(min1->rhs(), "z");
  }

  {
    // Min(5, Min(Min(y, Min(z, 8)), x)) => Min(Min(Min(x, 5), y), z)
    ExprHandle body = Min::make(
        5, Min::make(Min::make(y, Min::make(z, 8, true), true), x, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min1);
    IS_NODE_WITH_NAME(Min, min1->lhs(), min2);
    IS_BINOP_W_CONST(Min, min2->lhs(), min3, "x", 5);
    ASSERT_TRUE(min3->propagate_nans());
    IS_VAR_WITH_NAME(min2->rhs(), "y");
    IS_VAR_WITH_NAME(min1->rhs(), "z");
  }

  {
    // Min(5, Min(Min(Min(z, 8), y), x)) => Min(Min(Min(x, 5), y), z)
    ExprHandle body = Min::make(
        5, Min::make(Min::make(Min::make(z, 8, true), y, true), x, true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min1);
    IS_NODE_WITH_NAME(Min, min1->lhs(), min2);
    IS_BINOP_W_CONST(Min, min2->lhs(), min3, "x", 5);
    ASSERT_TRUE(min3->propagate_nans());
    IS_VAR_WITH_NAME(min2->rhs(), "y");
    IS_VAR_WITH_NAME(min1->rhs(), "z");
  }

  {
    // Min(Min(x, Min(y, Min(8, z))), 5) => Min(Min(Min(x, 5), y), z)
    ExprHandle body = Min::make(
        Min::make(x, Min::make(y, Min::make(8, z, true), true), true), 5, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min1);
    IS_NODE_WITH_NAME(Min, min1->lhs(), min2);
    IS_BINOP_W_CONST(Min, min2->lhs(), min3, "x", 5);
    ASSERT_TRUE(min3->propagate_nans());
    IS_VAR_WITH_NAME(min2->rhs(), "y");
    IS_VAR_WITH_NAME(min1->rhs(), "z");
  }

  {
    // Min(Min(Min(y, Min(8, z)), x), 5) => Min(Min(Min(x, 5), y), z)
    ExprHandle body = Min::make(
        Min::make(Min::make(y, Min::make(z, 8, true), true), x, true), 5, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min1);
    IS_NODE_WITH_NAME(Min, min1->lhs(), min2);
    IS_BINOP_W_CONST(Min, min2->lhs(), min3, "x", 5);
    ASSERT_TRUE(min3->propagate_nans());
    IS_VAR_WITH_NAME(min2->rhs(), "y");
    IS_VAR_WITH_NAME(min1->rhs(), "z");
  }

  {
    // Min(Min(Min(Min(8, z), y), x), 5) => Min(Min(Min(x, 5), y), z)
    ExprHandle body = Min::make(
        Min::make(Min::make(Min::make(z, 8, true), y, true), x, true), 5, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min1);
    IS_NODE_WITH_NAME(Min, min1->lhs(), min2);
    IS_BINOP_W_CONST(Min, min2->lhs(), min3, "x", 5);
    ASSERT_TRUE(min3->propagate_nans());
    IS_VAR_WITH_NAME(min2->rhs(), "y");
    IS_VAR_WITH_NAME(min1->rhs(), "z");
  }

  {
    // Min(Min(Min(Min(z, 5), y), x), 8) => Min(Min(x, Min(Min(z, 5), y)), 8)
    // Do not simplify when all the Min ops do not have the same
    // propagate_nans.
    ExprHandle body = Min::make(
        Min::make(Min::make(Min::make(z, 5, true), y, false), x, true),
        8,
        false);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min1);
    IS_NODE_WITH_NAME(Min, min1->lhs(), min2);
    IS_VAR_WITH_NAME(min2->lhs(), "x");
    IS_NODE_WITH_NAME(Min, min2->rhs(), min3);
    IS_BINOP_W_CONST(Min, min3->lhs(), min4, "z", 5);
    ASSERT_TRUE(min4->propagate_nans());
    IS_VAR_WITH_NAME(min3->rhs(), "y");
    ASSERT_FALSE(min3->propagate_nans());
    ASSERT_TRUE(min2->propagate_nans());
    IS_IMM_WITH_VAL(Int, min1->rhs(), 8);
    ASSERT_FALSE(min1->propagate_nans());
  }

  {
    // Min(8, Min(Min(x, 5), Min(y, z))) => Min(Min(Min(x, 5), y), z)
    ExprHandle body = Min::make(
        8, Min::make(Min::make(x, 5, true), Min::make(y, z, true), true), true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min1);
    IS_NODE_WITH_NAME(Min, min1->lhs(), min2);
    IS_BINOP_W_CONST(Min, min2->lhs(), min3, "x", 5);
    ASSERT_TRUE(min3->propagate_nans());
    IS_VAR_WITH_NAME(min2->rhs(), "y");
    IS_VAR_WITH_NAME(min1->rhs(), "z");
  }

  {
    // Min(Min(Min(x, 5), Min(y, z)), 8) => Min(Min(Min(x, 5), y), z)
    ExprHandle body = Min::make(
        Min::make(Min::make(x, 5, true), Min::make(y, z, true), true), 8, true);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Min, simplified.node(), min1);
    IS_NODE_WITH_NAME(Min, min1->lhs(), min2);
    IS_BINOP_W_CONST(Min, min2->lhs(), min3, "x", 5);
    ASSERT_TRUE(min3->propagate_nans());
    IS_VAR_WITH_NAME(min2->rhs(), "y");
    IS_VAR_WITH_NAME(min1->rhs(), "z");
  }
}

TEST(Simplify, SimplifyWontReorderFloat) {
  KernelScope kernel_scope;

  {
    // 3 * (3 * x) - 3 * (3 * y) => 9 * (x - y)
    // This is an expression we can simplify.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);

    ExprHandle body = ExprHandle(3) * (ExprHandle(3) * x) -
        ExprHandle(3) * (ExprHandle(3) * y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 9);
    IS_NODE_WITH_NAME(Sub, mul->rhs(), sub);
    IS_VAR_WITH_NAME(sub->lhs(), "x");
    IS_VAR_WITH_NAME(sub->rhs(), "y");
  }

  {
    // 3 * (3 * x) - 3 * (3 * y) => 3 * (3 * x) - 3 * (3 * y).
    // If the vars are floating point, ops are not associative and we can't
    // reorder.
    VarHandle x("x", kFloat);
    VarHandle y("y", kFloat);

    ExprHandle body = ExprHandle(3) * (ExprHandle(3) * x) -
        ExprHandle(3) * (ExprHandle(3) * y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Sub, simplified.node(), sub);
    IS_NODE_WITH_NAME(Mul, sub->lhs(), lhsMul);
    IS_IMM_WITH_VAL(Float, lhsMul->lhs(), 3);
    IS_NODE_WITH_NAME(Mul, lhsMul->rhs(), lhsVarMul);
    IS_IMM_WITH_VAL(Float, lhsVarMul->lhs(), 3);
    IS_VAR_WITH_NAME(lhsVarMul->rhs(), "x");

    IS_NODE_WITH_NAME(Mul, sub->rhs(), rhsMul);
    IS_IMM_WITH_VAL(Float, rhsMul->lhs(), 3);
    IS_NODE_WITH_NAME(Mul, rhsMul->rhs(), rhsVarMul);
    IS_IMM_WITH_VAL(Float, rhsVarMul->lhs(), 3);
    IS_VAR_WITH_NAME(rhsVarMul->rhs(), "y");
  }

  {
    // 3 * (3 * x) - 3 * (3 * y) => 3 * (3 * x) - (9 * y).
    // We will simplify subexprs if they dont reorder floating point ops.
    VarHandle x("x", kDouble);
    VarHandle y("y", kInt);

    ExprHandle body = ExprHandle(3) * (ExprHandle(3) * x) -
        ExprHandle(3) * (ExprHandle(3) * y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Sub, simplified.node(), sub);
    IS_NODE_WITH_NAME(Mul, sub->lhs(), lhsMul);
    IS_IMM_WITH_VAL(Double, lhsMul->lhs(), 3);
    IS_NODE_WITH_NAME(Mul, lhsMul->rhs(), lhsVarMul);
    IS_IMM_WITH_VAL(Double, lhsVarMul->lhs(), 3);
    IS_VAR_WITH_NAME(lhsVarMul->rhs(), "x");

    IS_NODE_WITH_NAME_AND_CAST(Mul, sub->rhs(), rhsMul, Double);
    IS_IMM_WITH_VAL(Int, rhsMul->lhs(), 9);
    IS_VAR_WITH_NAME(rhsMul->rhs(), "y");
  }

  {
    // Prevent reordering if FP propagated from dtypes.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);

    ExprHandle body = ExprHandle(3.f) * (ExprHandle(3) * x) -
        ExprHandle(3) * (ExprHandle(3.f) * y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Sub, simplified.node(), sub);
    IS_NODE_WITH_NAME(Mul, sub->lhs(), lhsMul);
    IS_IMM_WITH_VAL(Float, lhsMul->lhs(), 3);
    IS_NODE_WITH_NAME_AND_CAST(Mul, lhsMul->rhs(), lhsVarMul, Float);
    IS_IMM_WITH_VAL(Int, lhsVarMul->lhs(), 3);
    IS_VAR_WITH_NAME(lhsVarMul->rhs(), "x");

    IS_NODE_WITH_NAME(Mul, sub->rhs(), rhsMul);
    IS_IMM_WITH_VAL(Float, rhsMul->lhs(), 3);
    IS_NODE_WITH_NAME(Mul, rhsMul->rhs(), rhsVarMul);
    IS_IMM_WITH_VAL(Float, rhsVarMul->lhs(), 3);
    IS_NODE_WITH_NAME(Cast, rhsVarMul->rhs(), yCast);
    IS_VAR_WITH_NAME(yCast->src_value(), "y");
  }

  {
    VarHandle x("x", kFloat);
    VarHandle y("y", kFloat);
    // x%y - (x%y - 1) => x%y - (x%y - 1).
    // We wont reorder opaque ops if they are FP.
    ExprHandle body = (x % y) - ((x % y) - 1);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Sub, simplified.node(), sub);
    IS_NODE_WITH_NAME(Mod, sub->lhs(), lhsMod);
    IS_VAR_WITH_NAME(lhsMod->lhs(), "x");
    IS_VAR_WITH_NAME(lhsMod->rhs(), "y");

    IS_NODE_WITH_NAME(Sub, sub->rhs(), rhsSub);
    IS_NODE_WITH_NAME(Mod, rhsSub->lhs(), rhsMod);
    IS_VAR_WITH_NAME(rhsMod->lhs(), "x");
    IS_VAR_WITH_NAME(rhsMod->rhs(), "y");
    IS_IMM_WITH_VAL(Float, rhsSub->rhs(), 1);
  }
}

TEST(Simplify, SimplifyRoundModPattern) {
  KernelScope kernel_scope;

  {
    // (x/y)*y + x%y => x.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = ((x / y) * y) + (x % y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_VAR_WITH_NAME(simplified.node(), "x");
  }

  {
    // Reverse order.
    // x%y + (x/y)*y => x.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = (x % y) + ((x / y) * y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_VAR_WITH_NAME(simplified.node(), "x");
  }

  {
    // Non opaque denominator.
    // (x / (4+y)) * (4+y)) + (x % (y + 4)) => x.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = ((x / (ExprHandle(4) + y)) * (ExprHandle(4) + y)) +
        (x % (y + ExprHandle(4)));
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_VAR_WITH_NAME(simplified.node(), "x");
  }

  {
    // Reverse order.
    // (x % (y + 4)) + (x / (4+y)) * (4+y)) => x.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = (x % (y + ExprHandle(4))) +
        ((x / (ExprHandle(4) + y)) * (ExprHandle(4) + y));
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_VAR_WITH_NAME(simplified.node(), "x");
  }

  {
    // Opaque denominator.
    // (x / (2/y)) * (2/y)) + (x % (2/y)) => x.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = ((x / (ExprHandle(2) / y)) * (ExprHandle(2) / y)) +
        (x % (ExprHandle(2) / y));
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_VAR_WITH_NAME(simplified.node(), "x");
  }

  {
    // Non opaque numerator
    // ((2*x)/y * y) + ((2*x) % y) => 2 * x.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body =
        (((ExprHandle(2) * x) / y) * y) + ((ExprHandle(2) * x) % y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 2);
    IS_VAR_WITH_NAME(mul->rhs(), "x");
  }

  {
    // Opaque numerator.
    // ((x/2) / y * y) + (x/2 % y) => x / 2.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body =
        (((x / ExprHandle(2)) / y) * y) + ((x / ExprHandle(2)) % y);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Div, simplified.node(), div);
    IS_VAR_WITH_NAME(div->lhs(), "x");
    IS_IMM_WITH_VAL(Int, div->rhs(), 2);
  }

  {
    // Numerator and denominator.
    // ((2*x)/(2*y) * (2*y)) + ((2*x) % (2*y)) => 2 * x.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body =
        (((ExprHandle(2) * x) / (ExprHandle(2) * y)) * (ExprHandle(2) * y)) +
        ((ExprHandle(2) * x) % (ExprHandle(2) * y));
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 2);
    IS_VAR_WITH_NAME(mul->rhs(), "x");
  }

  {
    // Reverse order.
    // ((2*x) % (2*y)) + ((2*x)/(2*y) * (2*y)) => 2 * x.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = ((ExprHandle(2) * x) % (ExprHandle(2) * y)) +
        (((ExprHandle(2) * x) / (ExprHandle(2) * y)) * (ExprHandle(2) * y));
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 2);
    IS_VAR_WITH_NAME(mul->rhs(), "x");
  }

  {
    // Negated Subtraction of Round Mod.
    // (x/y) * y - (0 - x%y) => x.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = ((x / y) * y) - (ExprHandle(0) - (x % y));
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_VAR_WITH_NAME(simplified.node(), "x");
  }

  {
    // Other terms are preserved.
    // (x/y)*y + x%y + (y * x) => x + (y * x).
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = ((x / y) * y) + (x % y) + (y * x);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Add, simplified.node(), add);
    IS_VAR_WITH_NAME(add->lhs(), "x");
    IS_NODE_WITH_NAME(Mul, add->rhs(), mul);
    IS_VAR_WITH_NAME(mul->lhs(), "x");
    IS_VAR_WITH_NAME(mul->rhs(), "y");
  }

  {
    // Sanity checking we wont do the optimization on floats.
    VarHandle x("x", kFloat);
    VarHandle y("y", kFloat);
    ExprHandle body = ((x / y) * y) + (x % y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Add, simplified.node(), add);
    IS_NODE_WITH_NAME(Mul, add->lhs(), roundMul);
    IS_NODE_WITH_NAME(Div, roundMul->lhs(), roundDiv);
    IS_VAR_WITH_NAME(roundDiv->lhs(), "x");
    IS_VAR_WITH_NAME(roundDiv->rhs(), "y");
    IS_VAR_WITH_NAME(roundMul->rhs(), "y");
    IS_NODE_WITH_NAME(Mod, add->rhs(), mod);
    IS_VAR_WITH_NAME(mod->lhs(), "x");
    IS_VAR_WITH_NAME(mod->rhs(), "y");
  }

  {
    // Sanity check we wont do it if the mod term doesn't match.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    VarHandle z("z", kInt);
    ExprHandle body = ((x / y) * y) + (x % z);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Add, simplified.node(), add);
    IS_NODE_WITH_NAME(Mul, add->lhs(), roundMul);
    IS_VAR_WITH_NAME(roundMul->lhs(), "y");
    IS_NODE_WITH_NAME(Div, roundMul->rhs(), roundDiv);
    IS_VAR_WITH_NAME(roundDiv->lhs(), "x");
    IS_VAR_WITH_NAME(roundDiv->rhs(), "y");
    IS_NODE_WITH_NAME(Mod, add->rhs(), mod);
    IS_VAR_WITH_NAME(mod->lhs(), "x");
    IS_VAR_WITH_NAME(mod->rhs(), "z");
  }

  {
    // Sanity check we wont do it if the div term doesn't match.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    VarHandle z("z", kInt);
    ExprHandle body = (y * (x / z)) + (x % y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Add, simplified.node(), add);
    IS_NODE_WITH_NAME(Mul, add->lhs(), roundMul);
    IS_VAR_WITH_NAME(roundMul->lhs(), "y");
    IS_NODE_WITH_NAME(Div, roundMul->rhs(), roundDiv);
    IS_VAR_WITH_NAME(roundDiv->lhs(), "x");
    IS_VAR_WITH_NAME(roundDiv->rhs(), "z");
    IS_NODE_WITH_NAME(Mod, add->rhs(), mod);
    IS_VAR_WITH_NAME(mod->lhs(), "x");
    IS_VAR_WITH_NAME(mod->rhs(), "y");
  }

  {
    // Sanity check we wont do it if the mul term doesn't match.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    VarHandle z("z", kInt);
    ExprHandle body = ((x / y) * z) + (x % y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Add, simplified.node(), add);
    IS_NODE_WITH_NAME(Mul, add->lhs(), roundMul);
    IS_VAR_WITH_NAME(roundMul->lhs(), "z");
    IS_NODE_WITH_NAME(Div, roundMul->rhs(), roundDiv);
    IS_VAR_WITH_NAME(roundDiv->lhs(), "x");
    IS_VAR_WITH_NAME(roundDiv->rhs(), "y");
    IS_NODE_WITH_NAME(Mod, add->rhs(), mod);
    IS_VAR_WITH_NAME(mod->lhs(), "x");
    IS_VAR_WITH_NAME(mod->rhs(), "y");
  }
}

TEST(Simplify, SimplifyRoundModPatternFactorization) {
  KernelScope kernel_scope;

  {
    // Full factorization.
    // 2 * (x/y * y) + 2 * (x%y) => 2 * x.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = ExprHandle(2) * ((x / y) * y) + ExprHandle(2) * (x % y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 2);
    IS_VAR_WITH_NAME(mul->rhs(), "x");
  }

  {
    // Partial Factorization.
    // 32 * (x/y) + 4 * (x % y) => 4 * x.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = ExprHandle(32) * (x / 8) + ExprHandle(4) * (x % 8);
    ExprHandle simplified = IRSimplifier::simplify(body);

    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 4);
    IS_VAR_WITH_NAME(mul->rhs(), "x");
  }

  {
    // Factorization requiring constant folding.
    // 20 * (x  / (16 / 2)) * 2 + (11 % 6) * (x % (7+1)) => 5 * x.
    VarHandle x("x", kInt);
    ExprHandle body = ExprHandle(40) * (x / (ExprHandle(16) / 2)) +
        (ExprHandle(11) % 6) * (x % (ExprHandle(7) + 1));
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 5);
    IS_VAR_WITH_NAME(mul->rhs(), "x");
  }

  {
    VarHandle x("x", kInt);
    ExprHandle body = (x / 5) * 10 + ExprHandle(2) * (x % 5);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 2);
    IS_VAR_WITH_NAME(mul->rhs(), "x");
  }

  {
    VarHandle x("x", kInt);
    ExprHandle body = (x / 10) * 0 + x % 5;
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Mod, simplified.node(), mod);
    IS_VAR_WITH_NAME(mod->lhs(), "x");
    IS_IMM_WITH_VAL(Int, mod->rhs(), 5);
  }
}

TEST(Simplify, SimplifyRoundModPatternMultivar) {
  KernelScope kernel_scope;

  {
    // Multivar.
    // (x/8) * 8 + (y/5)*5 + x%8 + y%5 => y + x.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = (x / ExprHandle(8) * ExprHandle(8)) +
        (y / ExprHandle(5) * ExprHandle(5)) + (x % 8) + (y % 5);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Add, simplified.node(), add);
    IS_VAR_WITH_NAME(add->lhs(), "y");
    IS_VAR_WITH_NAME(add->rhs(), "x");
  }

  {
    // Find the right var.
    // (y/8) * 8  x%8 + y%8 + z%8 => z%8 + x%8 + y
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    VarHandle z("z", kInt);
    ExprHandle body =
        (y / ExprHandle(8) * ExprHandle(8)) + (x % 8) + (y % 8) + (z % 8);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Add, simplified.node(), add);
    IS_NODE_WITH_NAME(Add, add->lhs(), add2);
    IS_NODE_WITH_NAME(Mod, add2->lhs(), xMod);
    IS_VAR_WITH_NAME(xMod->lhs(), "x");
    IS_IMM_WITH_VAL(Int, xMod->rhs(), 8);
    IS_VAR_WITH_NAME(add2->rhs(), "y");
    IS_NODE_WITH_NAME(Mod, add->rhs(), zMod);
    IS_VAR_WITH_NAME(zMod->lhs(), "z");
    IS_IMM_WITH_VAL(Int, zMod->rhs(), 8);
  }

  {
    // Compound.
    // (x + (z + 512 * y) % 16) + 16 * ((z + 512 * y) / 16)  => x + (z + 512 *
    // y).
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    VarHandle z("z", kInt);

    ExprHandle body = x + (z + ExprHandle(512) * y) % ExprHandle(16) +
        ExprHandle(16) * ((z + ExprHandle(512) * y) / ExprHandle(16));
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Add, simplified.node(), add);
    IS_VAR_WITH_NAME(add->lhs(), "x");
    IS_NODE_WITH_NAME(Add, add->rhs(), add2);
    IS_VAR_WITH_NAME(add2->lhs(), "z");
    IS_NODE_WITH_NAME(Mul, add2->rhs(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 512);
    IS_VAR_WITH_NAME(mul->rhs(), "y");
  }
}

TEST(Simplify, SimplifyDivisionScalarFactorization) {
  KernelScope kernel_scope;

  {
    // Simple factorization of numerator and denominator.
    // 8x / 4y => 2x / y.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = (x * 8) / (y * 4);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Div, simplified.node(), div);
    IS_NODE_WITH_NAME(Mul, div->lhs(), lhs);
    IS_IMM_WITH_VAL(Int, lhs->lhs(), 2);
    IS_VAR_WITH_NAME(lhs->rhs(), "x");
    IS_VAR_WITH_NAME(div->rhs(), "y");
  }

  {
    // Don't change anything if we can't factorize.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = (x * 7) / (y * 4);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Div, simplified.node(), div);
    IS_NODE_WITH_NAME(Mul, div->lhs(), lhs);
    IS_IMM_WITH_VAL(Int, lhs->lhs(), 7);
    IS_VAR_WITH_NAME(lhs->rhs(), "x");
    IS_NODE_WITH_NAME(Mul, div->rhs(), rhs);
    IS_IMM_WITH_VAL(Int, rhs->lhs(), 4);
    IS_VAR_WITH_NAME(rhs->rhs(), "y");
  }

  {
    // Don't reorder floats.
    VarHandle x("x", kFloat);
    VarHandle y("y", kFloat);
    ExprHandle body = (x * 8) / (y * 4);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Div, simplified.node(), div);
    IS_NODE_WITH_NAME(Mul, div->lhs(), lhs);
    IS_VAR_WITH_NAME(lhs->lhs(), "x");
    IS_IMM_WITH_VAL(Float, lhs->rhs(), 8.f);
    IS_NODE_WITH_NAME(Mul, div->rhs(), rhs);
    IS_VAR_WITH_NAME(rhs->lhs(), "y");
    IS_IMM_WITH_VAL(Float, rhs->rhs(), 4.f);
  }

  {
    // Sanity check we do nothing if there are only scalar parts.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = (x * 1) / (y * 1);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Div, simplified.node(), div);
    IS_VAR_WITH_NAME(div->lhs(), "x");
    IS_VAR_WITH_NAME(div->rhs(), "y");
  }

  {
    // Can factorize amounts of variables.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = (x + x + x + x) / (y + y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Div, simplified.node(), div);
    IS_NODE_WITH_NAME(Mul, div->lhs(), lhs);
    IS_IMM_WITH_VAL(Int, lhs->lhs(), 2);
    IS_VAR_WITH_NAME(lhs->rhs(), "x");
    IS_VAR_WITH_NAME(div->rhs(), "y");
  }
}

TEST(Simplify, SimplifyConstantBranches) {
  KernelScope kernel_scope;

  {
    // If the condition is constant true then take the true_value.
    // 1 ? x : y => x
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle t(1);
    ExprHandle body = IfThenElse::make(t, x, y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_VAR_WITH_NAME(simplified.node(), "x");
  }

  {
    // If the condition is constant false then take the false_value.
    // 0 ? x : y => y
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle t(0);
    ExprHandle body = IfThenElse::make(t, x, y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_VAR_WITH_NAME(simplified.node(), "y");
  }

  {
    // condition is simplified before checking.
    // (x-x) ? x : y => y
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = IfThenElse::make(x - x, x, y);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_VAR_WITH_NAME(simplified.node(), "y");
  }

  {
    // If both branches are the same then don't do the condition.
    // y ? x : x => x
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = IfThenElse::make(y, x, x);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_VAR_WITH_NAME(simplified.node(), "x");
  }

  {
    // If both branches simplify to the same thing it still works.
    // y ? (x + x) : (2 * x) => x
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    ExprHandle body = IfThenElse::make(y, x + x, ExprHandle(2) * x);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_IMM_WITH_VAL(Int, mul->lhs(), 2);
    IS_VAR_WITH_NAME(mul->rhs(), "x");
  }
}

TEST(Simplify, SimplifyConstantCond) {
  KernelScope kernel_scope;

  {
    // If the condition is constant true then take the true_value.
    // 1 ? A[0] = 1 : B[0] = 1 => A[0] = 1
    BufHandle a("A", {1}, kInt);
    BufHandle b("B", {1}, kInt);
    ExprHandle condition(1);
    Stmt* true_val = Store::make(a, {0}, 1, 1);
    Stmt* false_val = Store::make(b, {0}, 1, 1);

    Cond* body = new Cond(condition.node(), true_val, false_val);
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    IS_NODE_WITH_NAME(Store, block->front(), store);
    IS_VAR_WITH_NAME(store->base_handle(), "A");
  }

  {
    // If the condition is constant false then take the false_value.
    // 0 ? A[0] = 1 : B[0] = 1 => B[0] = 1
    BufHandle a("A", {1}, kInt);
    BufHandle b("B", {1}, kInt);
    ExprHandle condition(0);
    Stmt* true_val = Store::make(a, {0}, 1, 1);
    Stmt* false_val = Store::make(b, {0}, 1, 1);

    Stmt* body = new Cond(condition.node(), true_val, false_val);
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    IS_NODE_WITH_NAME(Store, block->front(), store);
    IS_VAR_WITH_NAME(store->base_handle(), "B");
  }

  {
    // condition is simplified before checking.
    // (x-x) ? A[0] = 1 : B[0] = 1 => B[0] = 1
    VarHandle x("x", kInt);
    BufHandle a("A", {1}, kInt);
    BufHandle b("B", {1}, kInt);
    ExprHandle condition(x - x);
    Stmt* true_val = Store::make(a, {0}, 1, 1);
    Stmt* false_val = Store::make(b, {0}, 1, 1);

    Stmt* body = new Cond(condition.node(), true_val, false_val);
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    IS_NODE_WITH_NAME(Store, block->front(), store);
    IS_VAR_WITH_NAME(store->base_handle(), "B");
  }

  {
    // If both branches are the same then don't do the condition.
    // x ? A[0] = x : A[0] = x => A[0] = x
    VarHandle x("x", kInt);
    BufHandle a("A", {1}, kInt);
    ExprHandle condition(x - x);
    Stmt* true_val = Store::make(a, {0}, x, 1);
    Stmt* false_val = Store::make(a, {0}, x, 1);

    Stmt* body = new Cond(condition.node(), true_val, false_val);
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    IS_NODE_WITH_NAME(Store, block->front(), store);
    IS_VAR_WITH_NAME(store->base_handle(), "A");
  }

  {
    // If both branches simplify to the same thing it still works.
    // x ? (x + x) : (2 * x) => x
    VarHandle x("x", kInt);
    BufHandle a("A", {1}, kInt);
    ExprHandle condition(x - x);
    Stmt* true_val = Store::make(a, {0}, ExprHandle(2) * x, 1);
    Stmt* false_val = Store::make(a, {0}, x + x, 1);

    Stmt* body = new Cond(condition.node(), true_val, false_val);
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    IS_NODE_WITH_NAME(Store, block->front(), store);
    IS_VAR_WITH_NAME(store->base_handle(), "A");
  }

  {
    // But not if they dont
    // x ? x : (2 * x) => x ? x : (2 * x)
    VarHandle x("x", kInt);
    BufHandle a("A", {1}, kInt);
    ExprHandle condition(x);
    Stmt* true_val = Store::make(a, {0}, x, 1);
    Stmt* false_val = Store::make(a, {0}, ExprHandle(2) * x, 1);

    Stmt* body = new Cond(condition.node(), true_val, false_val);
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    ASSERT_EQ(block, nullptr);
  }

  {
    Stmt* cond = new Cond(ExprHandle(false).node(), new Block({}), nullptr);
    Stmt* simplified = IRSimplifier::simplify(cond);
    ASSERT_EQ(simplified, nullptr);
  }

  {
    Stmt* cond = new Cond(ExprHandle(true).node(), nullptr, new Block({}));
    Stmt* simplified = IRSimplifier::simplify(cond);
    ASSERT_EQ(simplified, nullptr);
  }
}

TEST(Simplify, SimplifyEliminateEmptyCond) {
  KernelScope kernel_scope;
  // If the branches are empty in different ways, eliminate.
  {
    VarHandle x("x", kInt);
    ExprHandle condition(x);
    Stmt* true_val = new Block({});

    Stmt* body = new Cond(condition.node(), true_val, nullptr);
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    ASSERT_NE(block, nullptr);
    ASSERT_EQ(block->nstmts(), 0);
  }

  {
    VarHandle x("x", kInt);
    ExprHandle condition(x);
    Stmt* false_val = new Block({});

    Stmt* body = new Cond(condition.node(), nullptr, false_val);
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    ASSERT_NE(block, nullptr);
    ASSERT_EQ(block->nstmts(), 0);
  }
}

TEST(Simplify, SimplifyConstantComparisons) {
  KernelScope kernel_scope;

  auto ComparisonTest =
      [](ExprHandle a, ExprHandle b, CompareSelectOperation op, int result) {
        ExprHandle body = CompareSelect::make(a, b, op);
        ExprHandle simplified = IRSimplifier::simplify(body);
        IS_IMM_WITH_VAL(Int, simplified.node(), result);
      };

  // Equals.
  ComparisonTest(2, 2, kEQ, 1);
  ComparisonTest(1, 2, kEQ, 0);
  ComparisonTest(2, 1, kEQ, 0);

  // Greater than.
  ComparisonTest(2, 2, kGT, 0);
  ComparisonTest(1, 2, kGT, 0);
  ComparisonTest(2, 1, kGT, 1);

  // Greater or Equal.
  ComparisonTest(2, 2, kGE, 1);
  ComparisonTest(1, 2, kGE, 0);
  ComparisonTest(2, 1, kGE, 1);

  // Less Than.
  ComparisonTest(2, 2, kLT, 0);
  ComparisonTest(1, 2, kLT, 1);
  ComparisonTest(2, 1, kLT, 0);

  // Less or Equal.
  ComparisonTest(2, 2, kLE, 1);
  ComparisonTest(1, 2, kLE, 1);
  ComparisonTest(2, 1, kLE, 0);

  // Not equal.
  ComparisonTest(2, 2, kNE, 0);
  ComparisonTest(1, 2, kNE, 1);
  ComparisonTest(2, 1, kNE, 1);

  // With specified results:
  ExprHandle body = CompareSelect::make(2, 2, 5, 42, kNE);
  ExprHandle simplified = IRSimplifier::simplify(body);
  IS_IMM_WITH_VAL(Int, simplified.node(), 42);
}

TEST(Simplify, SimplifySymbolicComparisons) {
  KernelScope kernel_scope;
  VarHandle x("x", kInt);
  VarHandle y("y", kInt);

  auto TookTrueBranch = [](ExprHandle a) { IS_IMM_WITH_VAL(Int, a.node(), 1); };
  auto TookFalseBranch = [](ExprHandle a) {
    IS_IMM_WITH_VAL(Int, a.node(), 0);
  };

  // EQ

  // x == x => 1
  ExprHandle body = CompareSelect::make(x, x, kEQ);
  TookTrueBranch(IRSimplifier::simplify(body));

  // x == x+1 => 0
  body = CompareSelect::make(x, x + 1, kEQ);
  TookFalseBranch(IRSimplifier::simplify(body));

  // x == x * 2 cannot simplify since we don't know x is nonzero.
  body = CompareSelect::make(x, x * 2, kEQ);
  IS_NODE(CompareSelect, IRSimplifier::simplify(body).node());

  // x == x * 1 => 1
  body = CompareSelect::make(x, x * 1, kEQ);
  TookTrueBranch(IRSimplifier::simplify(body));

  {
    // x == y => x == y
    body = CompareSelect::make(x, y, kEQ);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(CompareSelect, simplified.node(), cmp);
    ASSERT_EQ(cmp->compare_select_op(), kEQ);
    IS_VAR_WITH_NAME(cmp->lhs(), "x");
    IS_VAR_WITH_NAME(cmp->rhs(), "y");
  }

  {
    // x == 5 => x == 5
    body = CompareSelect::make(x, 5, kEQ);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(CompareSelect, simplified.node(), cmp);
    ASSERT_EQ(cmp->compare_select_op(), kEQ);
    IS_VAR_WITH_NAME(cmp->lhs(), "x");
    IS_IMM_WITH_VAL(Int, cmp->rhs(), 5);
  }

  // GT

  // x+1 > x => 1
  body = CompareSelect::make(x + 1, x, kGT);
  TookTrueBranch(IRSimplifier::simplify(body));

  // x > x + 1 => 0
  body = CompareSelect::make(x, x + 1, kGT);
  TookFalseBranch(IRSimplifier::simplify(body));

  // x > x - 1 => 1
  body = CompareSelect::make(x, x - 1, kGT);
  TookTrueBranch(IRSimplifier::simplify(body));

  // x - 1 > x => 0
  body = CompareSelect::make(x - 1, x, kGT);
  TookFalseBranch(IRSimplifier::simplify(body));

  // x > x => 0
  body = CompareSelect::make(x, x, kGT);
  TookFalseBranch(IRSimplifier::simplify(body));

  // x * 2 > x => x * 2 > x
  // since we don't know the sign of x.
  body = CompareSelect::make(x * 2, x, kGT);
  IS_NODE(CompareSelect, IRSimplifier::simplify(body).node());

  // GE

  // x+1 >= x => 1
  body = CompareSelect::make(x + 1, x, kGE);
  TookTrueBranch(IRSimplifier::simplify(body));

  // x >= x + 1 => 0
  body = CompareSelect::make(x, x + 1, kGE);
  TookFalseBranch(IRSimplifier::simplify(body));

  // x >= x => 1
  body = CompareSelect::make(x, x, kGE);
  TookTrueBranch(IRSimplifier::simplify(body));

  // x * 2 >= x => x * 2 >= x
  // since we don't know the sign of x.
  body = CompareSelect::make(x * 2, x, kGE);
  IS_NODE(CompareSelect, IRSimplifier::simplify(body).node());

  // LT

  // x+1 < x => 0
  body = CompareSelect::make(x + 1, x, kLT);
  TookFalseBranch(IRSimplifier::simplify(body));

  // x < x + 1 => 1
  body = CompareSelect::make(x, x + 1, kLT);
  TookTrueBranch(IRSimplifier::simplify(body));

  // x < x => 0
  body = CompareSelect::make(x, x, kLT);
  TookFalseBranch(IRSimplifier::simplify(body));

  // LE

  // x+1 <= x => 0
  body = CompareSelect::make(x + 1, x, kLE);
  TookFalseBranch(IRSimplifier::simplify(body));

  // x <= x + 1 => 1
  body = CompareSelect::make(x, x + 1, kLE);
  TookTrueBranch(IRSimplifier::simplify(body));

  // x <= x => 1
  body = CompareSelect::make(x, x, kLE);
  TookTrueBranch(IRSimplifier::simplify(body));

  // NE

  // x+1 != x => 1
  body = CompareSelect::make(x + 1, x, kNE);
  TookTrueBranch(IRSimplifier::simplify(body));

  // x != x + 1 => 1
  body = CompareSelect::make(x, x + 1, kNE);
  TookTrueBranch(IRSimplifier::simplify(body));

  // x != x => 0
  body = CompareSelect::make(x, x, kNE);
  TookFalseBranch(IRSimplifier::simplify(body));
}

TEST(Simplify, SimplifyEliminateZeroLengthFor) {
  KernelScope kernel_scope;

  {
    // Will eliminate zero loop For.
    BufHandle a("A", {4}, kInt);
    BufHandle c("C", {4}, kInt);
    auto mask = IntImm::make(1);
    VarHandle i("i", kInt);
    auto body =
        For::make(i, 0, 0, Store::make(c, {i}, Load::make(a, {i}, mask), mask));
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    ASSERT_EQ(block->nstmts(), 0);
  }

  {
    // still works if start is not zero.
    BufHandle a("A", {4}, kInt);
    BufHandle c("C", {4}, kInt);
    auto mask = IntImm::make(1);
    VarHandle i("i", kInt);
    auto body =
        For::make(i, 2, 2, Store::make(c, {i}, Load::make(a, {i}, mask), mask));
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    ASSERT_EQ(block->nstmts(), 0);
  }

  {
    // works if both terms are variable.
    VarHandle x("x", kInt);
    BufHandle a("A", {4}, kInt);
    BufHandle c("C", {4}, kInt);
    auto mask = IntImm::make(1);
    VarHandle i("i", kInt);
    auto body =
        For::make(i, x, x, Store::make(c, {i}, Load::make(a, {i}, mask), mask));
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    ASSERT_EQ(block->nstmts(), 0);
  }

  {
    // works if one term simplifies down.
    VarHandle x("x", kInt);
    BufHandle a("A", {4}, kInt);
    BufHandle c("C", {4}, kInt);
    auto mask = IntImm::make(1);
    VarHandle i("i", kInt);
    auto body = For::make(
        i, 0, x - x, Store::make(c, {i}, Load::make(a, {i}, mask), mask));
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    ASSERT_EQ(block->nstmts(), 0);
  }

  {
    // Sanity check does nothing if the condition is not met.
    BufHandle a("A", {4}, kInt);
    BufHandle c("C", {4}, kInt);
    auto mask = IntImm::make(1);
    VarHandle i("i", kInt);
    auto body =
        For::make(i, 0, 3, Store::make(c, {i}, Load::make(a, {i}, mask), mask));
    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE(For, simplified);
  }
}

TEST(Simplify, SimplifyOneLoopFor) {
  KernelScope kernel_scope;

  {
    // Will remove the loop if the body is run once.
    BufHandle a("A", {4}, kInt);
    BufHandle c("C", {4}, kInt);
    auto mask = IntImm::make(1);
    VarHandle i("i", kInt);
    auto body =
        For::make(i, 0, 1, Store::make(c, {i}, Load::make(a, {i}, mask), mask));
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    IS_NODE_WITH_NAME(Store, block->front(), store);
    IS_VAR_WITH_NAME(store->base_handle(), "C");
    IS_IMM_WITH_VAL(Int, store->flat_index(), 0);
  }

  {
    // still works if start is not zero.
    BufHandle a("A", {4}, kInt);
    BufHandle c("C", {4}, kInt);
    auto mask = IntImm::make(1);
    VarHandle i("i", kInt);
    auto body =
        For::make(i, 2, 3, Store::make(c, {i}, Load::make(a, {i}, mask), mask));
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    IS_NODE_WITH_NAME(Store, block->front(), store);
    IS_VAR_WITH_NAME(store->base_handle(), "C");
    IS_IMM_WITH_VAL(Int, store->flat_index(), 2);
  }

  {
    // works if both terms are variable.
    VarHandle x("x", kInt);
    BufHandle a("A", {4}, kInt);
    BufHandle c("C", {4}, kInt);
    auto mask = IntImm::make(1);
    VarHandle i("i", kInt);
    auto body = For::make(
        i, x, x + 1, Store::make(c, {i}, Load::make(a, {i}, mask), mask));
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    IS_NODE_WITH_NAME(Store, block->front(), store);
    IS_VAR_WITH_NAME(store->base_handle(), "C");
    IS_VAR_WITH_NAME(store->flat_index(), "x");
  }

  {
    // works if one term simplifies down.
    VarHandle x("x", kInt);
    BufHandle a("A", {4}, kInt);
    BufHandle c("C", {4}, kInt);
    auto mask = IntImm::make(1);
    VarHandle i("i", kInt);
    auto body = For::make(
        i, 0, x - x + 1, Store::make(c, {i}, Load::make(a, {i}, mask), mask));
    Stmt* simplified = IRSimplifier::simplify(body);
    Block* block = dynamic_cast<Block*>(simplified);
    IS_NODE_WITH_NAME(Store, block->front(), store);
    IS_VAR_WITH_NAME(store->base_handle(), "C");
    IS_IMM_WITH_VAL(Int, store->flat_index(), 0);
  }

  {
    // Sanity check does nothing if the condition is not met.
    BufHandle a("A", {4}, kInt);
    BufHandle c("C", {4}, kInt);
    auto mask = IntImm::make(1);
    VarHandle i("i", kInt);
    auto body =
        For::make(i, 0, 3, Store::make(c, {i}, Load::make(a, {i}, mask), mask));
    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE(For, simplified);
  }
}

TEST(Simplify, SimplifyForWontLoseLoopOptions) {
  KernelScope kernel_scope;

  {
    // Sanity check does nothing if the condition is not met.
    BufHandle a("A", {4}, kInt);
    BufHandle c("C", {4}, kInt);
    auto mask = IntImm::make(1);
    VarHandle i("i", kInt);
    LoopOptions options;
    options.set_gpu_block_index(12);
    auto body = For::make(
        i, 0, 1, Store::make(c, {i}, Load::make(a, {i}, mask), mask), options);
    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(For, simplified, for_);
    LoopOptions options2 = for_->loop_options();
    ASSERT_EQ(options.gpu_block_index(), options2.gpu_block_index());
  }
}

TEST(Simplify, SimplifyMultilevelFor) {
  KernelScope kernel_scope;

  {
    // Multiple layers of For will be simplified out.
    BufHandle a("A", {4}, kInt);
    BufHandle c("C", {4}, kInt);
    auto mask = IntImm::make(1);
    VarHandle i("i", kInt);
    VarHandle j("j", kInt);
    auto* body =
        For::make(i, 0, 1, Store::make(c, {i}, Load::make(a, {i}, mask), mask));
    auto outer = For::make(j, 0, 1, body);
    Stmt* simplified = IRSimplifier::simplify(outer);
    Block* block = dynamic_cast<Block*>(simplified);
    IS_NODE_WITH_NAME(Store, block->front(), store);
    IS_VAR_WITH_NAME(store->base_handle(), "C");
    IS_IMM_WITH_VAL(Int, store->flat_index(), 0);
  }

  {
    // Will maintain an outer loop if the inner loop is eliminated.
    BufHandle a("A", {4}, kInt);
    BufHandle c("C", {4}, kInt);
    auto mask = IntImm::make(1);
    VarHandle i("i", kInt);
    VarHandle j("j", kInt);
    auto* body =
        For::make(i, 0, 1, Store::make(c, {i}, Load::make(a, {i}, mask), mask));
    auto outer = For::make(j, 0, 2, body);
    Stmt* simplified = IRSimplifier::simplify(outer);
    For* for__ = static_cast<For*>(simplified);
    IS_NODE_WITH_NAME(For, for__, for_);
    IS_VAR_WITH_NAME(for_->var(), "j");
    IS_IMM_WITH_VAL(Int, for_->start(), 0);
    IS_IMM_WITH_VAL(Int, for_->stop(), 2);
    Block* block = dynamic_cast<Block*>(for_->body());
    ASSERT_NE(block, nullptr);
    IS_NODE_WITH_NAME(Store, block->front(), store);
    IS_VAR_WITH_NAME(store->base_handle(), "C");
    IS_IMM_WITH_VAL(Int, store->flat_index(), 0);
  }

  {
    // Will maintain inner loop if outer loops is eliminated.
    BufHandle a("A", {4}, kInt);
    BufHandle c("C", {4}, kInt);
    auto mask = IntImm::make(1);
    VarHandle i("i", kInt);
    VarHandle j("j", kInt);
    auto* body =
        For::make(i, 0, 2, Store::make(c, {i}, Load::make(a, {i}, mask), mask));
    auto outer = For::make(j, 0, 1, body);
    Stmt* simplified = IRSimplifier::simplify(outer);
    Block* block = dynamic_cast<Block*>(simplified);
    IS_NODE_WITH_NAME(For, block->front(), for_);
    IS_VAR_WITH_NAME(for_->var(), "i");
    IS_IMM_WITH_VAL(Int, for_->start(), 0);
    IS_IMM_WITH_VAL(Int, for_->stop(), 2);
    IS_NODE_WITH_NAME(Store, for_->body()->front(), store);
    IS_VAR_WITH_NAME(store->base_handle(), "C");
    IS_VAR_WITH_NAME(store->flat_index(), "i");
  }
}

TEST(Simplify, SimplifyForCleansUp) {
  KernelScope kernel_scope;

  {
    Placeholder a("a", kFloat, {1, 12, 1});
    VarHandle x("x", kInt);
    Tensor* b = Compute(
        "x",
        {{1, "i"}, {12, "m"}, {1, "n"}},
        [](const VarHandle& i, const VarHandle& m, const VarHandle& n) {
          return i + m + n;
        });
    LoopNest l({b});
    l.prepareForCodegen();

    Stmt* body = l.root_stmt();
    Stmt* simplified = IRSimplifier::simplify(body);

    Block* block = dynamic_cast<Block*>(simplified);
    IS_NODE_WITH_NAME(For, block->front(), for_);
    // for is over "m".
    IS_VAR_WITH_NAME(for_->var(), "m");
    // x[m] = m;
    IS_NODE_WITH_NAME(Store, for_->body()->front(), store);
    IS_VAR_WITH_NAME(store->flat_index(), "m");
    IS_VAR_WITH_NAME(store->value(), "m");
  }
}

TEST(Simplify, SimplifyEliminateEmptyFor) {
  KernelScope kernel_scope;

  {
    // Flatten many layers around an empty block to an empty block.
    Stmt* last = new Block({});
    for (int i = 0; i < 11; ++i) {
      VarHandle loopVar("loopVar", kInt);
      last = For::make(loopVar, 0, 10, last);
    }

    Stmt* simplified = IRSimplifier::simplify(last);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 0);
  }
}

TEST(Simplify, SimplifyFlattenBlock) {
  KernelScope kernel_scope;

  {
    // Flatten multiple blocks down to one.
    // { { { stmt1, stmt2 } } } =>  { stmt1, stmt2 }
    BufHandle a("A", {1}, kInt);
    Store* store1 = Store::make(a, {0}, 1, 1);
    Store* store2 = Store::make(a, {0}, 0, 1);

    Block* block1 = new Block({store1, store2});
    Block* block2 = new Block({block1});

    Block* enclosing = new Block({block2});
    Stmt* simplified = IRSimplifier::simplify(enclosing);

    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 2);

    IS_NODE_WITH_NAME(Store, block->front(), store1_);
    IS_NODE_WITH_NAME(Store, block->back(), store2_);

    ASSERT_EQ(store1->value(), store1_->value());
    ASSERT_EQ(store2->value(), store2_->value());
  }

  {
    // Flatten multiple sub blocks containing statements.
    // { { stmt1 }, { stmt2 } } =>  { stmt1, stmt2 }
    BufHandle a("A", {1}, kInt);
    Store* store1 = Store::make(a, {0}, 1, 1);
    Store* store2 = Store::make(a, {0}, 0, 1);

    Block* block1 = new Block({store1});
    Block* block2 = new Block({store2});

    Block* enclosing = new Block({block1, block2});
    Stmt* simplified = IRSimplifier::simplify(enclosing);

    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 2);

    IS_NODE_WITH_NAME(Store, block->front(), store1_);
    IS_NODE_WITH_NAME(Store, block->back(), store2_);

    ASSERT_EQ(store1->value(), store1_->value());
    ASSERT_EQ(store2->value(), store2_->value());
  }

  {
    // Flatten sub blocks with different depths.
    // { stmt1 , { { stmt2 } } } =>  { stmt1, stmt2 }
    BufHandle a("A", {1}, kInt);
    Store* store1 = Store::make(a, {0}, 1, 1);
    Store* store2 = Store::make(a, {0}, 0, 1);

    Block* block1 = new Block({store2});
    Block* block2 = new Block({block1});

    Block* enclosing = new Block({store1, block2});
    Stmt* simplified = IRSimplifier::simplify(enclosing);

    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 2);

    IS_NODE_WITH_NAME(Store, block->front(), store1_);
    IS_NODE_WITH_NAME(Store, block->back(), store2_);

    ASSERT_EQ(store1->value(), store1_->value());
    ASSERT_EQ(store2->value(), store2_->value());
  }

  {
    // Flatten many layers around an empty block to an empty block.
    Stmt* last = new Block({});
    for (int i = 0; i < 11; ++i) {
      last = new Block({last});
    }

    Stmt* simplified = IRSimplifier::simplify(last);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 0);
  }
}

TEST(Simplify, SimplifyEliminateZeroLengthAlloc) {
  KernelScope kernel_scope;

  {
    // Simple positive case.
    VarHandle x("x", kInt);

    Allocate* alloc = Allocate::make(x, kInt, {0});
    Free* free_ = Free::make(x);

    Block* block1 = new Block({alloc, free_});
    ASSERT_EQ(block1->nstmts(), 2);

    Stmt* simplified = IRSimplifier::simplify(block1);
    IS_NODE_WITH_NAME(Block, simplified, block2);
    ASSERT_EQ(block2->nstmts(), 0);
  }

  {
    // Simple negative case.
    VarHandle x("x", kInt);

    Allocate* alloc = Allocate::make(x, kInt, {2});
    Free* free_ = Free::make(x);

    Block* block1 = new Block({alloc, free_});
    ASSERT_EQ(block1->nstmts(), 2);

    Stmt* simplified = IRSimplifier::simplify(block1);
    IS_NODE_WITH_NAME(Block, simplified, block2);
    ASSERT_EQ(block2->nstmts(), 2);
  }

  {
    // Finds right Alloc/Free.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);

    Allocate* alloc1 = Allocate::make(x, kInt, {0});
    Allocate* alloc2 = Allocate::make(y, kInt, {2});
    Free* free2_ = Free::make(y);
    Free* free1_ = Free::make(x);

    Block* block1 = new Block({alloc1, alloc2, free2_, free1_});
    ASSERT_EQ(block1->nstmts(), 4);

    Stmt* simplified = IRSimplifier::simplify(block1);
    IS_NODE_WITH_NAME(Block, simplified, block2);
    ASSERT_EQ(block2->nstmts(), 2);
    IS_NODE_WITH_NAME(Allocate, block2->stmts().front(), simplified_alloc);
    IS_VAR_WITH_NAME(simplified_alloc->buffer_var(), "y");
    IS_NODE_WITH_NAME(Free, block2->stmts().back(), simplified_free);
    ASSERT_EQ(simplified_alloc->buffer_var(), simplified_free->buffer_var());
  }

  {
    // Dynamic shape.
    VarHandle x("x", kInt);
    VarHandle y("y", kInt);
    VarHandle z("z", kInt);

    Allocate* alloc1 = Allocate::make(x, kInt, {0});
    Allocate* alloc2 = Allocate::make(y, kInt, {z});
    Free* free2_ = Free::make(y);
    Free* free1_ = Free::make(x);

    Block* block1 = new Block({alloc1, alloc2, free2_, free1_});
    ASSERT_EQ(block1->nstmts(), 4);
    Stmt* simplified = IRSimplifier::simplify(block1);
    IS_NODE_WITH_NAME(Block, simplified, block2);
    ASSERT_EQ(block2->nstmts(), 2);
  }
}

TEST(Simplify, DontSimplifyRand) {
  KernelScope kernel_scope;

  {
    // rand() + rand() = rand() + rand() NOT 2 * rand().
    ExprHandle body =
        Intrinsics::make(kRand, kInt) + Intrinsics::make(kRand, kInt);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Add, simplified.node(), add);
    IS_RAND(add->lhs());
    IS_RAND(add->rhs());
  }

  {
    // rand() - rand() = rand() - rand() NOT 0.
    ExprHandle body =
        Intrinsics::make(kRand, kFloat) - Intrinsics::make(kRand, kFloat);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Sub, simplified.node(), sub);
    IS_RAND(sub->lhs());
    IS_RAND(sub->rhs());
  }

  {
    // rand() * rand() = rand() * rand().
    ExprHandle body =
        Intrinsics::make(kRand, kInt) * Intrinsics::make(kRand, kInt);
    ExprHandle simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Mul, simplified.node(), mul);
    IS_RAND(mul->lhs());
    IS_RAND(mul->rhs());
  }
}

TEST(Simplify, SimplifyReorderForCond) {
  KernelScope kernel_scope;
  BufHandle a("A", {4}, kInt);
  BufHandle b("B", {1}, kInt);
  BufHandle c("C", {4}, kInt);
  auto mask = IntImm::make(1);
  VarHandle i("i", kInt);
  VarHandle j("j", kInt);

  {
    // for ( if ( ... ) ) => if ( for ( ... ) ).
    auto body = For::make(
        i,
        0,
        4,
        Cond::make(
            CompareSelect::make(j, 10, CompareSelectOperation::kLT),
            Store::make(c, {i}, Load::make(a, {i}, mask), mask),
            nullptr));

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Cond, simplified, cond);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), true_block);
    IS_NODE_WITH_NAME(For, true_block->front(), loop);
  }

  {
    // Can't reorder if condition is dependent on the loop var.
    auto body = For::make(
        i,
        0,
        4,
        Cond::make(
            CompareSelect::make(i, 10, CompareSelectOperation::kLT),
            Store::make(c, {i}, Load::make(a, {i}, mask), mask),
            nullptr));

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(For, simplified, loop);
    IS_NODE_WITH_NAME(Cond, loop->body()->front(), cond);
  }

  {
    // Can't reorder if condition is dependent on a var that is modified inside
    // the loop.
    auto body = For::make(
        i,
        0,
        4,
        Cond::make(
            CompareSelect::make(
                Load::make(c, {0}, mask), 10, CompareSelectOperation::kLT),
            Store::make(c, {0}, Load::make(a, {i}, mask), mask),
            nullptr));

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(For, simplified, loop);
    IS_NODE_WITH_NAME(Cond, loop->body()->front(), cond);
  }

  {
    // Condition based on buffer not referenced in body. Can reorder here.
    auto body = For::make(
        i,
        0,
        4,
        Cond::make(
            CompareSelect::make(
                Load::make(b, {0}, mask), 10, CompareSelectOperation::kLT),
            Store::make(c, {0}, Load::make(a, {i}, mask), mask),
            nullptr));

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Cond, simplified, cond);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), true_block);
    IS_NODE_WITH_NAME(For, true_block->front(), loop);
  }

  {
    // Condition based on buffer read only in body. Can reorder here.
    auto body = For::make(
        i,
        0,
        4,
        Cond::make(
            CompareSelect::make(
                Load::make(a, {0}, mask), 10, CompareSelectOperation::kLT),
            Store::make(c, {0}, Load::make(a, {i}, mask), mask),
            nullptr));

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Cond, simplified, cond);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), true_block);
    IS_NODE_WITH_NAME(For, true_block->front(), loop);
  }

  {
    // Condition depends on Let in the loop. Cannot reorder.
    auto body = For::make(
        i,
        0,
        4,
        Block::make(
            {Let::make(j, 3),
             Cond::make(
                 CompareSelect::make(j, 10, CompareSelectOperation::kLT),
                 Store::make(c, {0}, Load::make(a, {i}, mask), mask),
                 nullptr)}));

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(For, simplified, loop);
    IS_NODE_WITH_NAME(Let, loop->body()->front(), let);
    IS_NODE_WITH_NAME(Cond, loop->body()->back(), cond);
  }

  {
    // Multi level Ifs where all conditions are distinct. Move BOTH Cond
    // statements outside the loop.
    auto body = For::make(
        i,
        0,
        4,
        Cond::make(
            CompareSelect::make(
                Load::make(a, {0}, mask), 10, CompareSelectOperation::kLT),
            Cond::make(
                CompareSelect::make(j, 10, CompareSelectOperation::kEQ),
                Store::make(c, {0}, Load::make(a, {i}, mask), mask),
                nullptr),
            nullptr));

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Cond, simplified, cond);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), true_block);
    IS_NODE_WITH_NAME(Cond, true_block->front(), cond2);
    IS_NODE_WITH_NAME(Block, cond2->true_stmt(), true_block2);
    IS_NODE_WITH_NAME(For, true_block2->front(), loop);
  }

  {
    // Multi level Ifs where the inner condition does depend on a loop var,
    // reorder only the first Cond.
    auto body = For::make(
        i,
        0,
        4,
        Cond::make(
            CompareSelect::make(
                Load::make(a, {0}, mask), 10, CompareSelectOperation::kLT),
            Cond::make(
                CompareSelect::make(i, 10, CompareSelectOperation::kEQ),
                Store::make(c, {0}, Load::make(a, {i}, mask), mask),
                nullptr),
            nullptr));

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Cond, simplified, cond);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), true_block);
    IS_NODE_WITH_NAME(For, true_block->front(), loop);
    IS_NODE_WITH_NAME(Block, loop->body(), loop_body);
    IS_NODE_WITH_NAME(Cond, loop_body->front(), cond2);
  }

  {
    // Don't reorder if there's an else block of the Cond.
    // We could, but is it much better?
    auto body = For::make(
        i,
        0,
        4,
        Cond::make(
            CompareSelect::make(j, 10, CompareSelectOperation::kLT),
            Store::make(c, {0}, Load::make(a, {i}, mask), mask),
            Store::make(c, {0}, 0, mask)));

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(For, simplified, loop);
    IS_NODE_WITH_NAME(Cond, loop->body()->front(), cond);
  }

  {
    // Condition uses distinct region of Tensor.
    // We could reorder here wih better analysis, but we don't. Included for
    // completeness.
    auto body = For::make(
        i,
        0,
        4,
        Cond::make(
            CompareSelect::make(
                Load::make(c, {0}, mask), 10, CompareSelectOperation::kLT),
            Store::make(c, {1}, Load::make(a, {i}, mask), mask),
            nullptr));

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(For, simplified, loop);
    IS_NODE_WITH_NAME(Cond, loop->body()->front(), cond);
  }
}

TEST(Simplify, SimplifyFuseConditions) {
  KernelScope kernel_scope;
  BufHandle a("A", {2}, kInt);
  BufHandle b("B", {2}, kInt);
  auto mask = IntImm::make(1);
  VarHandle i("i", kInt);
  VarHandle j("j", kInt);

  {
    // Can fuse since the conditions are identical.
    // if (A) { X }; if (A) { Y }; => if (A) { X; Y }
    auto body = Block::make(
        {Cond::make(
             CompareSelect::make(i, 10, CompareSelectOperation::kLT),
             Store::make(a, {0}, i, mask),
             nullptr),
         Cond::make(
             CompareSelect::make(i, 10, CompareSelectOperation::kLT),
             Store::make(a, {1}, i, mask),
             nullptr)});

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 1);
    IS_NODE_WITH_NAME(Cond, block->front(), cond);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), true_stmt);
    ASSERT_EQ(true_stmt->nstmts(), 2);
    ASSERT_EQ(cond->false_stmt(), nullptr);
  }

  {
    // Can't fuse, conditions are not identical in lhs (i != j).
    auto body = Block::make(
        {Cond::make(
             CompareSelect::make(i, 10, CompareSelectOperation::kLT),
             Store::make(a, {0}, i, mask),
             nullptr),
         Cond::make(
             CompareSelect::make(j, 10, CompareSelectOperation::kLT),
             Store::make(a, {1}, i, mask),
             nullptr)});

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 2);
    IS_NODE_WITH_NAME(Cond, block->front(), cond1);
    IS_NODE_WITH_NAME(Cond, block->back(), cond2);

    IS_NODE_WITH_NAME(Block, cond1->true_stmt(), true_stmt1);
    IS_NODE_WITH_NAME(Block, cond2->true_stmt(), true_stmt2);
    ASSERT_EQ(true_stmt1->nstmts(), 1);
    ASSERT_EQ(true_stmt2->nstmts(), 1);

    ASSERT_EQ(cond1->false_stmt(), nullptr);
    ASSERT_EQ(cond2->false_stmt(), nullptr);
  }
  {
    // Can't fuse, conditions are not identical in rhs (10 != 11).
    auto body = Block::make(
        {Cond::make(
             CompareSelect::make(i, 10, CompareSelectOperation::kLT),
             Store::make(a, {0}, i, mask),
             nullptr),
         Cond::make(
             CompareSelect::make(i, 11, CompareSelectOperation::kLT),
             Store::make(a, {1}, i, mask),
             nullptr)});

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 2);
    IS_NODE_WITH_NAME(Cond, block->front(), cond1);
    IS_NODE_WITH_NAME(Cond, block->back(), cond2);

    IS_NODE_WITH_NAME(Block, cond1->true_stmt(), true_stmt1);
    IS_NODE_WITH_NAME(Block, cond2->true_stmt(), true_stmt2);
    ASSERT_EQ(true_stmt1->nstmts(), 1);
    ASSERT_EQ(true_stmt2->nstmts(), 1);

    ASSERT_EQ(cond1->false_stmt(), nullptr);
    ASSERT_EQ(cond2->false_stmt(), nullptr);
  }

  {
    // Can't fuse, conditions are not identical in operation (LT vs GT).
    auto body = Block::make(
        {Cond::make(
             CompareSelect::make(i, 10, CompareSelectOperation::kLT),
             Store::make(a, {0}, i, mask),
             nullptr),
         Cond::make(
             CompareSelect::make(i, 10, CompareSelectOperation::kGT),
             Store::make(a, {1}, i, mask),
             nullptr)});

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 2);
    IS_NODE_WITH_NAME(Cond, block->front(), cond1);
    IS_NODE_WITH_NAME(Cond, block->back(), cond2);

    IS_NODE_WITH_NAME(Block, cond1->true_stmt(), true_stmt1);
    IS_NODE_WITH_NAME(Block, cond2->true_stmt(), true_stmt2);
    ASSERT_EQ(true_stmt1->nstmts(), 1);
    ASSERT_EQ(true_stmt2->nstmts(), 1);

    ASSERT_EQ(cond1->false_stmt(), nullptr);
    ASSERT_EQ(cond2->false_stmt(), nullptr);
  }

  {
    // Can't fuse, CompareSelect results are different.
    // Actually we totally could if we normalized CompareSelect results, but
    // TODO for later.
    auto body = Block::make(
        {Cond::make(
             CompareSelect::make(
                 i,
                 10,
                 new IntImm(1),
                 new IntImm(0),
                 CompareSelectOperation::kLT),
             Store::make(a, {0}, i, mask),
             nullptr),
         Cond::make(
             CompareSelect::make(
                 j,
                 10,
                 new IntImm(2),
                 new IntImm(0),
                 CompareSelectOperation::kLT),
             Store::make(a, {1}, i, mask),
             nullptr)});

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 2);
    IS_NODE_WITH_NAME(Cond, block->front(), cond1);
    IS_NODE_WITH_NAME(Cond, block->back(), cond2);

    IS_NODE_WITH_NAME(Block, cond1->true_stmt(), true_stmt1);
    IS_NODE_WITH_NAME(Block, cond2->true_stmt(), true_stmt2);
    ASSERT_EQ(true_stmt1->nstmts(), 1);
    ASSERT_EQ(true_stmt2->nstmts(), 1);

    ASSERT_EQ(cond1->false_stmt(), nullptr);
    ASSERT_EQ(cond2->false_stmt(), nullptr);
  }

  {
    // Can fuse with false stmt only.
    auto body = Block::make(
        {Cond::make(
             CompareSelect::make(i, 10, CompareSelectOperation::kLT),
             nullptr,
             Store::make(a, {0}, i, mask)),
         Cond::make(
             CompareSelect::make(i, 10, CompareSelectOperation::kLT),
             nullptr,
             Store::make(a, {1}, i, mask))});

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 1);
    IS_NODE_WITH_NAME(Cond, block->front(), cond);
    IS_NODE_WITH_NAME(Block, cond->false_stmt(), false_stmt);
    ASSERT_EQ(false_stmt->nstmts(), 2);
    ASSERT_EQ(cond->true_stmt(), nullptr);
  }

  {
    // Can fuse with both true and false stmt.
    auto body = Block::make(
        {Cond::make(
             CompareSelect::make(i, 10, CompareSelectOperation::kLT),
             Store::make(a, {0}, i, mask),
             Store::make(b, {0}, i, mask)),
         Cond::make(
             CompareSelect::make(i, 10, CompareSelectOperation::kLT),
             Store::make(a, {1}, i, mask),
             Store::make(b, {1}, i, mask))});

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 1);
    IS_NODE_WITH_NAME(Cond, block->front(), cond);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), true_stmt);
    ASSERT_EQ(true_stmt->nstmts(), 2);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), false_stmt);
    ASSERT_EQ(false_stmt->nstmts(), 2);
  }

  {
    // Can fuse with mismatched true / false stmt existing
    auto body = Block::make(
        {Cond::make(
             CompareSelect::make(i, 10, CompareSelectOperation::kLT),
             Store::make(a, {0}, i, mask),
             nullptr),
         Cond::make(
             CompareSelect::make(i, 10, CompareSelectOperation::kLT),
             nullptr,
             Store::make(b, {1}, i, mask))});

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 1);
    IS_NODE_WITH_NAME(Cond, block->front(), cond);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), true_stmt);
    ASSERT_EQ(true_stmt->nstmts(), 1);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), false_stmt);
    ASSERT_EQ(false_stmt->nstmts(), 1);
  }

  {
    // Can fuse partial block contents, ie when there are non fused stmts before
    // and after.
    // before:
    // if (j < 10) { A[0] = j; }
    // if (i < 10) { A[0] = i; }
    // if (i < 10) { A[1] = i; }
    // if (i < 11) { A[1] = j; }
    //
    // after:
    //
    // if (j < 10) { A[0] = j; }
    // if (i < 10) {
    //   A[0] = i;
    //   A[1] = i;
    // }
    // if (i < 11) { A[1] = j; }

    auto body = Block::make({
        Cond::make(
            CompareSelect::make(j, 10, CompareSelectOperation::kLT),
            Store::make(a, {0}, j, mask),
            nullptr),
        Cond::make(
            CompareSelect::make(i, 10, CompareSelectOperation::kLT),
            Store::make(a, {0}, i, mask),
            nullptr),
        Cond::make(
            CompareSelect::make(i, 10, CompareSelectOperation::kLT),
            Store::make(a, {1}, i, mask),
            nullptr),
        Cond::make(
            CompareSelect::make(i, 11, CompareSelectOperation::kLT),
            Store::make(a, {1}, j, mask),
            nullptr),
    });
    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 3);
    auto it = block->begin();
    it++;
    IS_NODE_WITH_NAME(Cond, *it, cond);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), true_stmt);
    ASSERT_EQ(true_stmt->nstmts(), 2);
    ASSERT_EQ(cond->false_stmt(), nullptr);
  }

  {
    // Can fuse longer sequences of identical conditions.
    auto body = Block::make({
        Cond::make(
            CompareSelect::make(i, 10, CompareSelectOperation::kLT),
            Store::make(a, {0}, j, mask),
            nullptr),
        Cond::make(
            CompareSelect::make(i, 10, CompareSelectOperation::kLT),
            Store::make(a, {0}, i, mask),
            nullptr),
        Cond::make(
            CompareSelect::make(i, 10, CompareSelectOperation::kLT),
            Store::make(a, {1}, i, mask),
            nullptr),
        Cond::make(
            CompareSelect::make(i, 10, CompareSelectOperation::kLT),
            Store::make(a, {1}, j, mask),
            nullptr),
    });
    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 1);
    IS_NODE_WITH_NAME(Cond, block->front(), cond);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), true_stmt);
    ASSERT_EQ(true_stmt->nstmts(), 4);
    ASSERT_EQ(cond->false_stmt(), nullptr);
  }

  {
    // Can't fuse through a non condition.
    auto body = Block::make({
        Cond::make(
            CompareSelect::make(i, 10, CompareSelectOperation::kLT),
            Store::make(a, {0}, j, mask),
            nullptr),
        Cond::make(
            CompareSelect::make(i, 10, CompareSelectOperation::kLT),
            Store::make(a, {0}, i, mask),
            nullptr),
        Store::make(b, {1}, i + j, mask),
        Cond::make(
            CompareSelect::make(i, 10, CompareSelectOperation::kLT),
            Store::make(a, {1}, i, mask),
            nullptr),
        Cond::make(
            CompareSelect::make(i, 10, CompareSelectOperation::kLT),
            Store::make(a, {1}, j, mask),
            nullptr),
    });
    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 3);
    IS_NODE_WITH_NAME(Cond, block->front(), cond);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), true_stmt);
    ASSERT_EQ(true_stmt->nstmts(), 2);
    ASSERT_EQ(cond->false_stmt(), nullptr);

    IS_NODE_WITH_NAME(Cond, block->back(), cond2);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), true_stmt2);
    ASSERT_EQ(true_stmt2->nstmts(), 2);
    ASSERT_EQ(cond2->false_stmt(), nullptr);

    auto it = block->begin();
    it++;
    IS_NODE_WITH_NAME(Store, *it, middle);
  }

  {
    // Can fuse if the conditions simplify to the same thing.
    auto body = Block::make(
        {Cond::make(
             CompareSelect::make(
                 i * 2,
                 ExprHandle(87) % ExprHandle(11),
                 CompareSelectOperation::kLT),
             Store::make(a, {0}, i, mask),
             nullptr),
         Cond::make(
             CompareSelect::make(
                 i * 2,
                 ExprHandle(300) / ExprHandle(30),
                 CompareSelectOperation::kLT),
             Store::make(a, {1}, i, mask),
             nullptr)});
    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 1);
    IS_NODE_WITH_NAME(Cond, block->front(), cond);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), true_stmt);
    ASSERT_EQ(true_stmt->nstmts(), 2);
    ASSERT_EQ(cond->false_stmt(), nullptr);
  }

  {
    // Can fuse non-CompareSelects.
    // if (i) { X } if (i) { Y } => if (i) { X; Y }
    auto body = Block::make(
        {Cond::make(i, Store::make(a, {0}, i, mask), nullptr),
         Cond::make(i, Store::make(a, {1}, i, mask), nullptr)});

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 1);
    IS_NODE_WITH_NAME(Cond, block->front(), cond);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), true_stmt);
    ASSERT_EQ(true_stmt->nstmts(), 2);
    ASSERT_EQ(cond->false_stmt(), nullptr);
  }

  {
    // Sanity check wont fuse different non-CompareSelects.
    auto body = Block::make(
        {Cond::make(i, Store::make(a, {0}, i, mask), nullptr),
         Cond::make(j, Store::make(a, {1}, i, mask), nullptr)});

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 2);
    IS_NODE_WITH_NAME(Cond, block->front(), cond1);
    IS_NODE_WITH_NAME(Cond, block->back(), cond2);
  }

  {
    // Sanity check constant condition elimination still occurs when merging is
    // possible.
    auto body = Block::make(
        {Cond::make(1, Store::make(a, {0}, i, mask), nullptr),
         Cond::make(1, Store::make(a, {1}, i, mask), nullptr)});
    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 2);
    IS_NODE_WITH_NAME(Store, block->front(), store1);
    IS_NODE_WITH_NAME(Store, block->back(), store2);
  }

  {
    // Sanity check for-cond reordering occurs after fusing.
    auto body = For::make(
        i,
        0,
        4,
        Block::make(
            {Cond::make(
                 CompareSelect::make(j, 10, CompareSelectOperation::kLT),
                 Store::make(a, {1}, Load::make(b, {0}, mask), mask),
                 nullptr),
             Cond::make(
                 CompareSelect::make(j, 10, CompareSelectOperation::kLT),
                 Store::make(a, {2}, Load::make(b, {0}, mask), mask),
                 nullptr)}));

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Cond, simplified, cond);
    IS_NODE_WITH_NAME(Block, cond->true_stmt(), true_block);
    IS_NODE_WITH_NAME(For, true_block->front(), loop);
  }
}

TEST(Simplify, SimplifySyncThreads) {
  KernelScope kernel_scope;
  BufHandle a("A", {4}, kInt);
  auto mask = IntImm::make(1);
  VarHandle i("i", kInt);

  {
    // Merge two inner SyncThreads.
    auto body = Block::make(
        {Store::make(a, {0}, 1, 1),
         new SyncThreads(),
         new SyncThreads(),
         Store::make(a, {1}, 0, 1)});
    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 3);
    auto it = block->begin();
    IS_NODE(Store, *it++);
    IS_NODE(SyncThreads, *it++);
    IS_NODE(Store, *it++);
  }

  {
    // Eliminate outer SyncThreads.
    auto body = Block::make(
        {new SyncThreads(), Store::make(a, {1}, 0, 1), new SyncThreads()});

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 1);
    auto it = block->begin();
    IS_NODE(Store, *it);
  }

  {
    // Merge many inner SyncThreads.
    auto body = Block::make(
        {Store::make(a, {0}, 1, 1),
         new SyncThreads(),
         new SyncThreads(),
         new SyncThreads(),
         new SyncThreads(),
         new SyncThreads(),
         Store::make(a, {1}, 0, 1)});

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 3);
    auto it = block->begin();
    IS_NODE(Store, *it++);
    IS_NODE(SyncThreads, *it++);
    IS_NODE(Store, *it++);
  }

  {
    // Merge multiple outer SyncThreads.
    auto body = Block::make(
        {new SyncThreads(),
         new SyncThreads(),
         Store::make(a, {1}, 0, 1),
         new SyncThreads(),
         new SyncThreads(),
         new SyncThreads(),
         new SyncThreads()});

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 1);
    auto it = block->begin();
    IS_NODE(Store, *it);
  }

  {
    // Merge multiple sections;
    auto body = Block::make(
        {Store::make(a, {0}, 1, 1),
         new SyncThreads(),
         new SyncThreads(),
         Store::make(a, {1}, 0, 1),
         Store::make(a, {2}, 0, 1),
         new SyncThreads(),
         new SyncThreads(),
         new SyncThreads(),
         Store::make(a, {3}, 0, 1)});

    Stmt* simplified = IRSimplifier::simplify(body);
    IS_NODE_WITH_NAME(Block, simplified, block);
    ASSERT_EQ(block->nstmts(), 6);
    auto it = block->begin();
    IS_NODE(Store, *it++);
    IS_NODE(SyncThreads, *it++);
    IS_NODE(Store, *it++);
    IS_NODE(Store, *it++);
    IS_NODE(SyncThreads, *it++);
    IS_NODE(Store, *it++);
  }
}

TEST(Simplify, SimplifyRampSubBroadcast) {
  KernelScope kernel_scope;
  int num_lanes = 4;
  ExprHandle ramp = Ramp::make(ExprHandle(0), ExprHandle(6), num_lanes);
  ExprHandle broadcast = Broadcast::make(ExprHandle(-5), num_lanes);
  ExprHandle simplified = IRSimplifier::simplify(ramp - broadcast);
  Ramp* newRamp = simplified.AsNode<Ramp>();
  IS_NODE_WITH_NAME(IntImm, newRamp->base(), base);
  ASSERT_EQ(base->value(), 5);
  IS_NODE_WITH_NAME(IntImm, newRamp->stride(), stride);
  ASSERT_EQ(stride->value(), 6);
  ASSERT_EQ(newRamp->lanes(), num_lanes);
}

TEST(Simplify, SimplifyBroadcastTermExpander) {
  KernelScope kernel_scope;
  int num_lanes = 8;
  ExprHandle bc0 = Broadcast::make(ExprHandle(0), num_lanes);
  ExprHandle bc1 = Broadcast::make(ExprHandle(1), num_lanes);
  ExprHandle bc2 = Broadcast::make(ExprHandle(2), num_lanes);
  // NB: We need a term in the middle which isn't simplified to trigger the
  // relevant path in TermExpander::mutate. The two bc1 terms are brought
  // together and simplified to 2 * bc1, which then needs to make 2 multi-lane.
  ExprHandle simplified = IRSimplifier::simplify(bc1 + (bc0 / bc2) + bc1);
  BufHandle buf("buf", {num_lanes}, kInt);
  // The result isn't fully simplified currently and thus would be brittle to
  // match. Observe its value instead.
  auto store = Store::make(
      buf,
      {Ramp::make(0, 1, num_lanes)},
      simplified,
      Broadcast::make(ExprHandle(1), num_lanes));
  SimpleIREvaluator eval(store, {buf});
  std::vector<int> output(num_lanes);
  eval(output);
  for (int i = 0; i < num_lanes; ++i) {
    ASSERT_EQ(output[i], 2);
  }
}

} // namespace jit
} // namespace torch