From 7e7dc45eb15d3739564f2a63ab1c468c57d94ff8 Mon Sep 17 00:00:00 2001
From: Nick Lewycky <nicholas@mxc.ca>
Date: Sun, 19 Jul 2009 03:44:35 +0000
Subject: [PATCH] Fix ConstantRange::unionWith. Also make it work a little hard
 in some cases to return the smallest union of two ranges instead of just any
 range that happens to contain the union.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@76360 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Support/ConstantRange.cpp           | 95 +++++++++++++++++----------------
 unittests/Support/ConstantRangeTest.cpp | 11 ++++
 2 files changed, 61 insertions(+), 45 deletions(-)

diff --git a/lib/Support/ConstantRange.cpp b/lib/Support/ConstantRange.cpp
index 5f3d6f8db24..2a3da453712 100644
--- a/lib/Support/ConstantRange.cpp
+++ b/lib/Support/ConstantRange.cpp
@@ -371,69 +371,74 @@ ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
 
   if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
 
-  APInt L = Lower, U = Upper;
-
   if (!isWrappedSet() && !CR.isWrappedSet()) {
+    if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
+      // If the two ranges are disjoint, find the smaller gap and bridge it.
+      APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
+      if (d1.ult(d2))
+        return ConstantRange(Lower, CR.Upper);
+      else
+        return ConstantRange(CR.Lower, Upper);
+    }
+
+    APInt L = Lower, U = Upper;
     if (CR.Lower.ult(L))
       L = CR.Lower;
-
-    if (CR.Upper.ugt(U))
+    if ((CR.Upper - 1).ugt(U - 1))
       U = CR.Upper;
+
+    if (L == 0 && U == 0)
+      return ConstantRange(getBitWidth());
+
+    return ConstantRange(L, U);
   }
 
-  if (isWrappedSet() && !CR.isWrappedSet()) {
-    if ((CR.Lower.ult(Upper) && CR.Upper.ult(Upper)) ||
-        (CR.Lower.ugt(Lower) && CR.Upper.ugt(Lower))) {
+  if (!CR.isWrappedSet()) {
+    // ------U   L-----  and  ------U   L----- : this
+    //   L--U                            L--U  : CR
+    if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
       return *this;
-    }
 
-    if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) {
+    // ------U   L----- : this
+    //    L---------U   : CR
+    if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
       return ConstantRange(getBitWidth());
-    }
 
-    if (CR.Lower.ule(Upper) && CR.Upper.ule(Lower)) {
-      APInt d1 = CR.Upper - Upper, d2 = Lower - CR.Upper;
-      if (d1.ult(d2)) {
-        U = CR.Upper;
-      } else {
-        L = CR.Upper;
-      }
-    }
-
-    if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower)) {
+    // ----U       L---- : this
+    //       L---U       : CR
+    //    <d1>  <d2>
+    if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
-      if (d1.ult(d2)) {
-        U = CR.Lower + 1;
-      } else {
-        L = CR.Upper - 1;
-      }
+      if (d1.ult(d2))
+        return ConstantRange(Lower, CR.Upper);
+      else
+        return ConstantRange(CR.Lower, Upper);
     }
 
-    if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) {
-      APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Lower;
+    // ----U     L----- : this
+    //        L----U    : CR
+    if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
+      return ConstantRange(CR.Lower, Upper);
 
-      if (d1.ult(d2)) {
-        U = CR.Lower + 1;
-      } else {
-        L = CR.Lower;
-      }
-    }
+    // ------U    L---- : this
+    //    L-----U       : CR
+    if (CR.Lower.ult(Upper) && CR.Upper.ult(Lower))
+      return ConstantRange(Lower, CR.Upper);
   }
 
-  if (isWrappedSet() && CR.isWrappedSet()) {
-    if (Lower.ult(CR.Upper) || CR.Lower.ult(Upper))
-      return ConstantRange(getBitWidth());
+  assert(isWrappedSet() && CR.isWrappedSet() &&
+         "ConstantRange::unionWith missed wrapped union unwrapped case");
 
-    if (CR.Upper.ugt(U)) {
-      U = CR.Upper;
-    }
+  // ------U    L----  and  ------U    L---- : this
+  // -U  L-----------  and  ------------U  L : CR
+  if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
+    return ConstantRange(getBitWidth());
 
-    if (CR.Lower.ult(L)) {
-      L = CR.Lower;
-    }
-
-    if (L == U) return ConstantRange(getBitWidth());
-  }
+  APInt L = Lower, U = Upper;
+  if (CR.Upper.ugt(U))
+    U = CR.Upper;
+  if (CR.Lower.ult(L))
+    L = CR.Lower;
 
   return ConstantRange(L, U);
 }
diff --git a/unittests/Support/ConstantRangeTest.cpp b/unittests/Support/ConstantRangeTest.cpp
index b77ac6aece0..b1b82a99273 100644
--- a/unittests/Support/ConstantRangeTest.cpp
+++ b/unittests/Support/ConstantRangeTest.cpp
@@ -219,6 +219,17 @@ TEST_F(ConstantRangeTest, UnionWith) {
   EXPECT_TRUE(Empty.unionWith(Empty).isEmptySet());
   EXPECT_TRUE(Full.unionWith(Full).isFullSet());
   EXPECT_TRUE(Some.unionWith(Wrap).isFullSet());
+
+  // PR4545
+  EXPECT_EQ(ConstantRange(APInt(16, 14), APInt(16, 1)).unionWith(
+            ConstantRange(APInt(16, 0), APInt(16, 8))),
+            ConstantRange(APInt(16, 14), APInt(16, 8)));
+  EXPECT_EQ(ConstantRange(APInt(16, 6), APInt(16, 4)).unionWith(
+            ConstantRange(APInt(16, 4), APInt(16, 0))),
+            ConstantRange(16));
+  EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 0)).unionWith(
+            ConstantRange(APInt(16, 2), APInt(16, 1))),
+            ConstantRange(16));
 }
 
 TEST_F(ConstantRangeTest, SubtractAPInt) {
-- 
2.11.0