From f945429fed52bc7c182d5b38469a41ab5eea03a2 Mon Sep 17 00:00:00 2001
From: Nikita Popov <nikita.ppv@gmail.com>
Date: Tue, 23 Apr 2019 18:00:17 +0000
Subject: [ConstantRange] Add urem support

Add urem support to ConstantRange, so we can handle in in LVI. This
is an approximate implementation that tries to capture the most useful
conditions: If the LHS is always strictly smaller than the RHS, then
the urem is a no-op and the result is the same as the LHS range.
Otherwise the lower bound is zero and the upper bound is
min(LHSMax, RHSMax - 1).

Differential Revision: https://reviews.llvm.org/D60952

llvm-svn: 359019
---
 llvm/lib/IR/ConstantRange.cpp | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

(limited to 'llvm/lib/IR/ConstantRange.cpp')

diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp
index b2bdd0abd9c..7e2c6727703 100644
--- a/llvm/lib/IR/ConstantRange.cpp
+++ b/llvm/lib/IR/ConstantRange.cpp
@@ -794,6 +794,8 @@ ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
     return multiply(Other);
   case Instruction::UDiv:
     return udiv(Other);
+  case Instruction::URem:
+    return urem(Other);
   case Instruction::Shl:
     return shl(Other);
   case Instruction::LShr:
@@ -991,6 +993,19 @@ ConstantRange::udiv(const ConstantRange &RHS) const {
   return getNonEmpty(std::move(Lower), std::move(Upper));
 }
 
+ConstantRange ConstantRange::urem(const ConstantRange &RHS) const {
+  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
+    return getEmpty();
+
+  // L % R for L < R is L.
+  if (getUnsignedMax().ult(RHS.getUnsignedMin()))
+    return *this;
+
+  // L % R is <= L and < R.
+  APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1;
+  return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(Upper));
+}
+
 ConstantRange
 ConstantRange::binaryAnd(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
-- 
cgit v1.2.3