[ValueLattice] Add singlecrfromundef lattice value.

[fhahn]

Summary

This patch adds a new singlecrfromundef lattice value, indicating a
single element constant range which was merge with undef at some point.
Merging it with another constant range results in overdefined, as we
won't be able to replace all users with a single value.

This patch uses a ConstantRange instead of a Constant*, because regular
integer constants are represented as single element constant ranges as
well and this allows the existing code working without additional
changes.

[nikic]

Same comment as on D75055: For LVI we don't guarantee that all uses of the value will be replaced, so this does not seem like a completely fix. I'm generally not really clear on how this differs from the variant implemented in D75055 (is it is just a matter of style, i.e. making this explicit, or is there a functional difference here?)

[fhahn]

In D75845#1913226, @nikic wrote:

Same comment as on D75055: For LVI we don't guarantee that all uses of the value will be replaced, so this does not seem like a completely fix.

Yes that is an additional issue that needs to be addressed in LVI and/or its clients. This patch (and the preceding one) are a first step towards fixing the underlying issue in ValueLattice. Once those are addressed, we can fix the code in LVI.

I'm generally not really clear on how this differs from the variant implemented in D75120 (is it is just a matter of style, i.e. making this explicit, or is there a functional difference here?)

Sorry for the confusion. This patch and D75120 complement each other and both are needed. D75120 introduces a state for actual undef values and separates the notion of value we know nothing about yet and values we know are undef. This patch introduces a state for constants that started out as undef values or were merged with undef values. Such constants cannot safely be merged with other constant ranges.

[efriedma]

LGTM, with some updates to the comments.

llvm/include/llvm/Analysis/ValueLattice.h

31–37

I think it would make sense to list out the possible state transitions for each state here.

71

I would prefer to say something like "This Value contains a single element constant range that was merged with an Undef value".

[efriedma]

llvm/include/llvm/Analysis/ValueLattice.h

61

Sort of a side-question while I'm here, but how are we inferring notconstant? Is the inference safe in the presence of undef?

[fhahn]

Thank you very much for taking a look!

Update wording around singlecrfromundef as suggested, document allowed follow-on states.

[fhahn]

llvm/include/llvm/Analysis/ValueLattice.h

31–37

Done! Is the format along the lines you imagined? It does not list explicitly that we can stay in the existing state, if nothing changes.

[fhahn]

llvm/include/llvm/Analysis/ValueLattice.h

61

I've responded in D75120

[efriedma]

llvm/include/llvm/Analysis/ValueLattice.h

31–37

Yes, this format looks fine.

For unknown specifically, probably you could just say "transition allowed to any state".

44

Is there actually a transition from undef -> constant?

61

I guess my concern is really, does "notconstant" imply that we've proven the value isn't undef? It would probably be worth stating that explicitly.

[fhahn]

Rebase after recent changes landed.

[fhahn]

llvm/include/llvm/Analysis/ValueLattice.h

44

Yes it is allowed in mergeIn(), which also ensures going to overdefined if we merge a constant with a different constant.

61

Right, notconstant (undef) is not allowed. I'll state that explicitly.

[efriedma]

llvm/include/llvm/Analysis/ValueLattice.h

44

Oh, I see. It's probably worth calling out in the documentation for constant: it might actually come from an undef/constant merge, like singlecrfromundef. (I don't think it has any practical impact at the moment, but it could matter in the future.)

[fhahn]

llvm/include/llvm/Analysis/ValueLattice.h

44

Should be added in 873ab73db477

llvm/include/llvm/Analysis/ValueLattice.h

 ///
 
 namespace llvm {
 class ValueLatticeElement {
   enum ValueLatticeElementTy {
     /// This Value has no known value yet.  As a result, this implies the
     /// 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".
+    /// Transition allowed to the following states:
+    ///  undef
+    ///  constant
+    ///  constantrange
+    ///  notconstant
+    ///  constantrange
     unknown,
 
     /// 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.
+    /// Transition allowed to the following states:
+    ///  constant
+    ///  singlecrfromundef
+    ///  overdefined
     undef,
 
     /// This Value has a specific constant value.  (For constant integers,
     /// constantrange is used instead.  Integer typed constantexprs can appear
     /// as constant.)
+    /// Transition allowed to the following states:
+    ///  overdefined
     constant,
 
     /// This Value is known to not have the specified value.  (For constant
     /// integers, constantrange is used instead.  As above, integer typed
     /// constantexprs can appear here.)
+    /// Transition allowed to the following states:
+    ///  overdefined
     notconstant,
 
     /// The Value falls within this range. (Used only for integer typed values.)
+    /// Transition allowed to the following states:
+    ///  constantrange (new range must be a superset of the existing range)
+    ///  singlecrfromundef (range must stay a single element range)
+    ///  overdefined
     constantrange,
 
+    /// This Value contains a single element constant range that was merged with
+    /// an Undef value. Merging it with other constant ranges results in
+    /// overdefined, unless they match the single element constant range.
+    /// Transition allowed to the following states:
+    ///  overdefined
+    singlecrfromundef,
+
     /// We can not precisely model the dynamic values this value might take.
+    /// No transitions are allowed after reaching overdefined.
     overdefined
   };
 
   ValueLatticeElementTy Tag;
 
   /// The union either stores a pointer to a constant or a constant range,
   /// associated to the lattice element. We have to ensure that Range is
   /// initialized or destroyed when changing state to or from constantrange.
public:
   /// Custom destructor to ensure Range is properly destroyed, when the object
   /// is deallocated.
   ~ValueLatticeElement() {
     switch (Tag) {
     case overdefined:
     case unknown:
     case undef:
     case constant:
+    case singlecrfromundef:
     case notconstant:
       break;
     case constantrange:
       Range.~ConstantRange();
       break;
     };
   }
 
ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
     // If we change the state of this from a valid ConstVal to another a state
     // without a valid ConstVal, zero the pointer.
     if ((isConstant() || isNotConstant()) && !Other.isConstant() &&
         !Other.isNotConstant())
       ConstVal = nullptr;
 
     switch (Other.Tag) {
     case constantrange:
+    case singlecrfromundef:
       if (!isConstantRange())
         new (&Range) ConstantRange(Other.Range);
       else
         Range = Other.Range;
       break;
     case constant:
     case notconstant:
       ConstVal = Other.ConstVal;
static ValueLatticeElement getOverdefined() {
     Res.markOverdefined();
     return Res;
   }
 
   bool isUndef() const { return Tag == undef; }
   bool isUnknown() const { return Tag == unknown; }
   bool isUnknownOrUndef() const { return Tag == unknown || Tag == undef; }
   bool isConstant() const { return Tag == constant; }
+  bool isSingleCRFromUndef() const { return Tag == singlecrfromundef; }
   bool isNotConstant() const { return Tag == notconstant; }
-  bool isConstantRange() const { return Tag == constantrange; }
+  bool isConstantRange() const {
+    return Tag == constantrange || Tag == singlecrfromundef;
+  }
   bool isOverdefined() const { return Tag == overdefined; }
 
   Constant *getConstant() const {
     assert(isConstant() && "Cannot get the constant of a non-constant!");
     return ConstVal;
   }
 
   Constant *getNotConstant() const {
public:
   /// 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;
 
+      assert(!isSingleCRFromUndef());
+
       if (NewR.isEmptySet())
         return markOverdefined();
 
       assert(NewR.contains(getConstantRange()) &&
              "Existing range must be a subset of NewR");
       Range = std::move(NewR);
       return true;
     }
 
-    assert(isUnknown() || isUndef());
+    assert(isUnknown() || (isUndef() && NewR.isSingleElement()));
     if (NewR.isEmptySet())
       return markOverdefined();
 
-    Tag = constantrange;
+    Tag = isUnknown() ? constantrange : singlecrfromundef;
     new (&Range) ConstantRange(std::move(NewR));
     return true;
   }
 
   /// 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.isUnknown() || isOverdefined())
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.
       markOverdefined();
       return true;
     }
+
     ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
+
+    if (isSingleCRFromUndef() || RHS.isSingleCRFromUndef()) {
+      if (NewR.isSingleElement()) {
+        assert(getConstantRange() == NewR);
+        return false;
+      }
+      markOverdefined();
+      return true;
+    }
     if (NewR.isFullSet())
       return markOverdefined();
     else if (NewR == getConstantRange())
       return false;
     else
       return markConstantRange(std::move(NewR));
   }
 

llvm/lib/Analysis/ValueLattice.cpp

if (Val.isUnknown())
     return OS << "unknown";
   if (Val.isUndef())
     return OS << "undef";
   if (Val.isOverdefined())
     return OS << "overdefined";
 
   if (Val.isNotConstant())
     return OS << "notconstant<" << *Val.getNotConstant() << ">";
+
+  if (Val.isSingleCRFromUndef())
+    return OS << "constantrange (from undef)<"
+              << Val.getConstantRange().getLower() << ", "
+              << Val.getConstantRange().getUpper() << ">";
+
   if (Val.isConstantRange())
     return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
               << Val.getConstantRange().getUpper() << ">";
   return OS << "constant<" << *Val.getConstant() << ">";
 }
 } // end namespace llvm

llvm/test/Transforms/CorrelatedValuePropagation/merge-range-and-undef.ll

 ; CHECK-NEXT:    br label [[BB4:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], label [[BB4]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
 ; CHECK-NEXT:    br label [[BB4]]
 ; CHECK:       bb4:
 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ 10, [[BB2]] ], [ [[R]], [[BB3]] ]
-; CHECK-NEXT:    ret i64 [[P]]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
 ;
 entry:
   br i1 %c1, label %bb1, label %bb2
 
 bb1:
   br label %bb4
 
 bb2:

llvm/test/Transforms/SCCP/range-and-ip.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -ipsccp %s | FileCheck %s
 
-; FIXME: we cannot assume %r < 256 for @f1, because we pass undef at a call
-; site, which we won't eliminate.
+; Make sure we do not assume %r < 256 for @f1, because we pass undef
+; at a call site, which we won't eliminate.
 
 define i1 @constant_and_undef(i64 %a) {
 ; CHECK-LABEL: define {{.*}} @constant_and_undef(
 ; CHECK-NEXT:    [[C_1:%.*]] = call i1 @f1(i64 undef)
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[C_2:%.*]] = call i1 @f1(i64 10)
 ; CHECK-NEXT:    br label [[BB2:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[RANGE:%.*]] = and i64 [[A:%.*]], 255
 ; CHECK-NEXT:    [[C_3:%.*]] = call i1 @f1(i64 [[RANGE]])
-; CHECK-NEXT:    ret i1 true
+; CHECK-NEXT:    [[R_1:%.*]] = and i1 [[C_1]], [[C_2]]
+; CHECK-NEXT:    [[R_2:%.*]] = and i1 [[R_1]], [[C_3]]
+; CHECK-NEXT:    ret i1 [[R_2]]
 ;
   %c.1 = call i1 @f1(i64 undef)
   br label %bb1
 
 bb1:
   %c.2 = call i1 @f1(i64 10)
   br label %bb2
 
 bb2:
   %range = and i64 %a, 255
   %c.3 = call i1 @f1(i64 %range)
   %r.1 = and i1 %c.1, %c.2
   %r.2 = and i1 %r.1, %c.3
   ret i1 %r.2
 }
 
 declare void @sideeffect(i1, i64 %a)
 
 define internal i1 @f1(i64 %r) {
 ; CHECK-LABEL: define {{.*}} @f1(
-; CHECK-NEXT:    call void @sideeffect(i1 true, i64 [[R:%.*]])
-; CHECK-NEXT:    ret i1 undef
+; CHECK-NEXT:    [[C:%.*]] = icmp ult i64 [[R:%.*]], 256
+; CHECK-NEXT:    call void @sideeffect(i1 [[C]], i64 [[R]])
+; CHECK-NEXT:    ret i1 [[C]]
 ;
   %c = icmp ult i64 %r, 256
   call void @sideeffect(i1 %c, i64 %r)
   ret i1 %c
 }