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

[fhahn]

Summary

This patch prepares ValueLatticeElement to be used by SCCP, by:

• making the mark* functions public
• make the mark* functions return a bool indicating if the value has changed.

[davide]

I'm not necessarily sure I like this. It's simply spreading in a general framework a concept that shouldn't exist to begin with. I'd rather remove forced constant from SCCP, even though it might result in us losing some optimization power.

[fhahn]

In D60581#1463363, @davide wrote:

I'm not necessarily sure I like this. It's simply spreading in a general framework a concept that shouldn't exist to begin with. I'd rather remove forced constant from SCCP, even though it might result in us losing some optimization power.

Right, I am happy to go in that direction as well.

[fhahn]

I've put up a commit removing forcedconstant on top of the integer range support: D61314. This is mostly to have an easy way to compare the impact of forcedconstant and could be folded in the integer range support. But maybe it is easier to review/commit/test as separate steps.

[fhahn]

Rebased

[merge_guards_bot]

Unit tests: pass. 61085 tests passed, 0 failed and 728 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[fhahn]

Strip forcedconstant changes.

[nikic]

llvm/include/llvm/Analysis/ValueLattice.h

288

I'm confused -- how can this method ever return non-null? Isn't ConstantInt canonicalized to ranges?

304

And related to the previous comment: Why are these changes needed? This shouldn't happen.

[fhahn]

Remove getConstantInt changes, removed in D74329.

[fhahn]

llvm/include/llvm/Analysis/ValueLattice.h

288

Right, it looks like getConstantInt was an unused left-over. I've put up a patch to remove it: D74329

[nikic]

llvm/include/llvm/Analysis/ValueLattice.h

184–185

I believe this assert is useless after the isa<>. Can either be dropped or the previous order restored (not sure why it was changed?)

310

Looks like this can now be reverted to the previous code (which avoids the awkward empty initializations...)

[fhahn]

Address comments: remove unnecessary assert, undo unnnecessary changes in getCompare.

[nikic]

LGTM

[fhahn]

Thanks for taking a look. I plan to land this, once D60582 has been accepted as well.

llvm/include/llvm/Analysis/ValueLattice.h

public:
   }
   static ValueLatticeElement getOverdefined() {
     ValueLatticeElement Res;
     Res.markOverdefined();
     return Res;
   }
 
   bool isUndefined() const { return Tag == undefined; }
+  bool isUnknown() const { return Tag == undefined; }
   bool isConstant() const { return Tag == constant; }
   bool isNotConstant() const { return Tag == notconstant; }
   bool isConstantRange() const { return Tag == constantrange; }
   bool isOverdefined() const { return Tag == overdefined; }
 
   Constant *getConstant() const {
     assert(isConstant() && "Cannot get the constant of a non-constant!");
     return ConstVal;
Optional<APInt> asConstantInteger() const {
     if (isConstant() && isa<ConstantInt>(getConstant())) {
       return cast<ConstantInt>(getConstant())->getValue();
     } else if (isConstantRange() && getConstantRange().isSingleElement()) {
       return *getConstantRange().getSingleElement();
     }
     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 markConstant(Constant *V) {
     if (isa<UndefValue>(V))
-      return;
+      return false;
+
+    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((!isConstant() || getConstant() == V) &&
-           "Marking constant with different value");
     assert(isUndefined());
     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(isUndefined());
     Tag = notconstant;
     ConstVal = V;
+    return true;
   }
 
-  void markConstantRange(ConstantRange NewR) {
+  bool markConstantRange(ConstantRange NewR) {
     if (isConstantRange()) {
       if (NewR.isEmptySet())
         markOverdefined();
       else {
+        assert(NewR.contains(getConstantRange()) && "Existing range must be a subset of NewR");
         Range = std::move(NewR);
       }
-      return;
+      return true;
     }
 
     assert(isUndefined());
     if (NewR.isEmptySet())
-      markOverdefined();
-    else {
-      Tag = constantrange;
-      new (&Range) ConstantRange(std::move(NewR));
-    }
+      return markOverdefined();
+
+    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())
       return false;
     if (RHS.isOverdefined()) {
       markOverdefined();
       return true;
bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
     if (!RHS.isConstantRange()) {
       // We can get here if we've encountered a constantexpr of integer type
       // and merge it with a constantrange.
       markOverdefined();
       return true;
     }
     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;
+      return markConstantRange(std::move(NewR));
   }
 
   /// Compares this symbolic value with Other using Pred and returns either
   /// true, false or undef constants, or nullptr if the comparison cannot be
   /// evaluated.
   Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
                        const ValueLatticeElement &Other) const {
     if (isUndefined() || Other.isUndefined())
       return UndefValue::get(Ty);
 
     if (isConstant() && Other.isConstant())
       return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
 
     // Integer constants are represented as ConstantRanges with single
     // elements.
     if (!isConstantRange() || !Other.isConstantRange())
       return nullptr;
 
     const auto &CR = getConstantRange();
     const auto &OtherCR = Other.getConstantRange();
     if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR))
       return ConstantInt::getTrue(Ty);
     if (ConstantRange::makeSatisfyingICmpRegion(
             CmpInst::getInversePredicate(Pred), OtherCR)
             .contains(CR))
       return ConstantInt::getFalse(Ty);
 
     return nullptr;
   }
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
 
 } // end namespace llvm
 #endif