Backport 4878aa36d4a [ValueLattice] Add new state for undef constants.

Summary:
NOTE: I mostly put it on Phabricator to make it easy for other people to fetch & check if that fixes a bug.

This patch backports 4878aa36d4a and required earlier patches onto
the release/10.x branch.

It includes the following patches:

aa5ebfdf205de6d599c1fed3161da3b63b6f0bef [ValueLattice] Make mark* functions public, return if value changed.

c1943b42c5b7feff5d0e0c1358d02889e2be165f [ValueLattice] Update markConstantRange to return false equal ranges.

e30c257811f62fea21704caa961c61e4559de202 [CVP,SCCP] Precommit test for D75055.

4878aa36d4aa27df644430139fab2734fde4a000 [ValueLattice] Add new state for undef constants.

All patches except the last one apply cleanly. For the last one, the
changes to SCCP.cpp were stripped, because SCCP does not yet use
ValueLattice on release/10.x. Otherwise we would have to pull in more
additional changes.

Subscribers: tstellar, hiraditya, llvm-commits

Tags: #llvm

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

1 files changed, 102 insertions, 60 deletions

diff --git a/llvm/include/llvm/Analysis/ValueLattice.h b/llvm/include/llvm/Analysis/ValueLattice.h
index 56519d7d085..415c32e7c23 100644
--- a/llvm/include/llvm/Analysis/ValueLattice.h
+++ b/llvm/include/llvm/Analysis/ValueLattice.h
@@ -29,7 +29,7 @@ class ValueLatticeElement {
     /// producing instruction is dead.  Caution: We use this as the starting
     /// state in our local meet rules.  In this usage, it's taken to mean
     /// "nothing known yet".
-    undefined,
+    unknown,
 
     /// This Value has a specific constant value.  (For constant integers,
     /// constantrange is used instead.  Integer typed constantexprs can appear
@@ -45,7 +45,12 @@ class ValueLatticeElement {
     constantrange,
 
     /// We can not precisely model the dynamic values this value might take.
-    overdefined
+    overdefined,
+
+    /// This Value is an UndefValue constant or produces undef. Undefined values
+    /// can be merged with constants (or single element constant ranges),
+    /// assuming all uses of the result will be replaced.
+    undef
   };
 
   ValueLatticeElementTy Tag;
@@ -60,14 +65,15 @@ class ValueLatticeElement {
 
 public:
   // Const and Range are initialized on-demand.
-  ValueLatticeElement() : Tag(undefined) {}
+  ValueLatticeElement() : Tag(unknown) {}
 
   /// Custom destructor to ensure Range is properly destroyed, when the object
   /// is deallocated.
   ~ValueLatticeElement() {
     switch (Tag) {
     case overdefined:
-    case undefined:
+    case unknown:
+    case undef:
     case constant:
     case notconstant:
       break;
@@ -79,7 +85,7 @@ public:
 
   /// Custom copy constructor, to ensure Range gets initialized when
   /// copying a constant range lattice element.
-  ValueLatticeElement(const ValueLatticeElement &Other) : Tag(undefined) {
+  ValueLatticeElement(const ValueLatticeElement &Other) : Tag(unknown) {
     *this = Other;
   }
 
@@ -109,7 +115,8 @@ public:
       ConstVal = Other.ConstVal;
       break;
     case overdefined:
-    case undefined:
+    case unknown:
+    case undef:
       break;
     }
     Tag = Other.Tag;
@@ -118,14 +125,16 @@ public:
 
   static ValueLatticeElement get(Constant *C) {
     ValueLatticeElement Res;
-    if (!isa<UndefValue>(C))
+    if (isa<UndefValue>(C))
+      Res.markUndef();
+    else
       Res.markConstant(C);
     return Res;
   }
   static ValueLatticeElement getNot(Constant *C) {
     ValueLatticeElement Res;
-    if (!isa<UndefValue>(C))
-      Res.markNotConstant(C);
+    assert(!isa<UndefValue>(C) && "!= undef is not supported");
+    Res.markNotConstant(C);
     return Res;
   }
   static ValueLatticeElement getRange(ConstantRange CR) {
@@ -139,7 +148,10 @@ public:
     return Res;
   }
 
-  bool isUndefined() const { return Tag == undefined; }
+  bool isUndef() const { return Tag == undef; }
+  bool isUnknown() const { return Tag == unknown; }
+  bool isUnknownOrUndef() const { return Tag == unknown || Tag == undef; }
+  bool isUndefined() const { return isUnknownOrUndef(); }
   bool isConstant() const { return Tag == constant; }
   bool isNotConstant() const { return Tag == notconstant; }
   bool isConstantRange() const { return Tag == constantrange; }
@@ -170,89 +182,123 @@ public:
     return None;
   }
 
-private:
-  void markOverdefined() {
+  bool markOverdefined() {
     if (isOverdefined())
-      return;
+      return false;
     if (isConstant() || isNotConstant())
       ConstVal = nullptr;
     if (isConstantRange())
       Range.~ConstantRange();
     Tag = overdefined;
+    return true;
   }
 
-  void markConstant(Constant *V) {
-    assert(V && "Marking constant with NULL");
-    if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
-      markConstantRange(ConstantRange(CI->getValue()));
-      return;
-    }
+  bool markUndef() {
+    if (isUndef())
+      return false;
+
+    assert(isUnknown());
+    Tag = undef;
+    return true;
+  }
+
+  bool markConstant(Constant *V) {
     if (isa<UndefValue>(V))
-      return;
+      return markUndef();
 
-    assert((!isConstant() || getConstant() == V) &&
-           "Marking constant with different value");
-    assert(isUndefined());
+    if (isConstant()) {
+      assert(getConstant() == V && "Marking constant with different value");
+      return false;
+    }
+
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
+      return markConstantRange(ConstantRange(CI->getValue()));
+
+    assert(isUnknown() || isUndef());
     Tag = constant;
     ConstVal = V;
+    return true;
   }
 
-  void markNotConstant(Constant *V) {
+  bool markNotConstant(Constant *V) {
     assert(V && "Marking constant with NULL");
-    if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
-      markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
-      return;
-    }
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
+      return markConstantRange(
+          ConstantRange(CI->getValue() + 1, CI->getValue()));
+
     if (isa<UndefValue>(V))
-      return;
+      return false;
 
-    assert((!isConstant() || getConstant() != V) &&
-           "Marking constant !constant with same value");
-    assert((!isNotConstant() || getNotConstant() == V) &&
-           "Marking !constant with different value");
-    assert(isUndefined() || isConstant());
+    if (isNotConstant()) {
+      assert(getNotConstant() == V && "Marking !constant with different value");
+      return false;
+    }
+
+    assert(isUnknown());
     Tag = notconstant;
     ConstVal = V;
+    return true;
   }
 
-  void markConstantRange(ConstantRange NewR) {
+  /// Mark the object as constant range with \p NewR. If the object is already a
+  /// constant range, nothing changes if the existing range is equal to \p
+  /// NewR. Otherwise \p NewR must be a superset of the existing range or the
+  /// object must be undef.
+  bool markConstantRange(ConstantRange NewR) {
     if (isConstantRange()) {
+      if (getConstantRange() == NewR)
+        return false;
+
       if (NewR.isEmptySet())
-        markOverdefined();
-      else {
-        Range = std::move(NewR);
-      }
-      return;
+        return markOverdefined();
+
+      assert(NewR.contains(getConstantRange()) &&
+             "Existing range must be a subset of NewR");
+      Range = std::move(NewR);
+      return true;
     }
 
-    assert(isUndefined());
+    assert(isUnknown() || isUndef());
     if (NewR.isEmptySet())
-      markOverdefined();
-    else {
-      Tag = constantrange;
-      new (&Range) ConstantRange(std::move(NewR));
-    }
+      return markOverdefined();
+
+    Tag = constantrange;
+    new (&Range) ConstantRange(std::move(NewR));
+    return true;
   }
 
-public:
   /// Updates this object to approximate both this object and RHS. Returns
   /// true if this object has been changed.
   bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
-    if (RHS.isUndefined() || isOverdefined())
+    if (RHS.isUnknown() || isOverdefined())
       return false;
     if (RHS.isOverdefined()) {
       markOverdefined();
       return true;
     }
 
-    if (isUndefined()) {
+    if (isUndef()) {
+      assert(!RHS.isUnknown());
+      if (RHS.isUndef())
+        return false;
+      if (RHS.isConstant())
+        return markConstant(RHS.getConstant());
+      if (RHS.isConstantRange() && RHS.getConstantRange().isSingleElement())
+        return markConstantRange(RHS.getConstantRange());
+      return markOverdefined();
+    }
+
+    if (isUnknown()) {
+      assert(!RHS.isUnknown() && "Unknow RHS should be handled earlier");
       *this = RHS;
-      return !RHS.isUndefined();
+      return true;
     }
 
     if (isConstant()) {
       if (RHS.isConstant() && getConstant() == RHS.getConstant())
         return false;
+      if (RHS.isUndef())
+        return false;
       markOverdefined();
       return true;
     }
@@ -265,6 +311,9 @@ public:
     }
 
     assert(isConstantRange() && "New ValueLattice type?");
+    if (RHS.isUndef() && getConstantRange().isSingleElement())
+      return false;
+
     if (!RHS.isConstantRange()) {
       // We can get here if we've encountered a constantexpr of integer type
       // and merge it with a constantrange.
@@ -273,18 +322,11 @@ public:
     }
     ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
     if (NewR.isFullSet())
-      markOverdefined();
+      return markOverdefined();
     else if (NewR == getConstantRange())
       return false;
     else
-      markConstantRange(std::move(NewR));
-    return true;
-  }
-
-  ConstantInt *getConstantInt() const {
-    assert(isConstant() && isa<ConstantInt>(getConstant()) &&
-           "No integer constant");
-    return cast<ConstantInt>(getConstant());
+      return markConstantRange(std::move(NewR));
   }
 
   /// Compares this symbolic value with Other using Pred and returns either
@@ -292,7 +334,7 @@ public:
   /// evaluated.
   Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
                        const ValueLatticeElement &Other) const {
-    if (isUndefined() || Other.isUndefined())
+    if (isUnknownOrUndef() || Other.isUnknownOrUndef())
       return UndefValue::get(Ty);
 
     if (isConstant() && Other.isConstant())