diff --git a/llvm/include/llvm/Analysis/ValueLattice.h b/llvm/include/llvm/Analysis/ValueLattice.h --- a/llvm/include/llvm/Analysis/ValueLattice.h +++ b/llvm/include/llvm/Analysis/ValueLattice.h @@ -29,27 +29,53 @@ /// 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 }; @@ -75,6 +101,7 @@ case unknown: case undef: case constant: + case singlecrfromundef: case notconstant: break; case constantrange: @@ -105,6 +132,7 @@ switch (Other.Tag) { case constantrange: + case singlecrfromundef: if (!isConstantRange()) new (&Range) ConstantRange(Other.Range); else @@ -158,8 +186,11 @@ 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 { @@ -254,6 +285,8 @@ if (getConstantRange() == NewR) return false; + assert(!isSingleCRFromUndef()); + if (NewR.isEmptySet()) return markOverdefined(); @@ -263,11 +296,11 @@ 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; } @@ -325,7 +358,17 @@ 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()) diff --git a/llvm/lib/Analysis/ValueLattice.cpp b/llvm/lib/Analysis/ValueLattice.cpp --- a/llvm/lib/Analysis/ValueLattice.cpp +++ b/llvm/lib/Analysis/ValueLattice.cpp @@ -19,6 +19,12 @@ 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() << ">"; diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/merge-range-and-undef.ll b/llvm/test/Transforms/CorrelatedValuePropagation/merge-range-and-undef.ll --- a/llvm/test/Transforms/CorrelatedValuePropagation/merge-range-and-undef.ll +++ b/llvm/test/Transforms/CorrelatedValuePropagation/merge-range-and-undef.ll @@ -199,7 +199,8 @@ ; 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 diff --git a/llvm/test/Transforms/SCCP/range-and-ip.ll b/llvm/test/Transforms/SCCP/range-and-ip.ll --- a/llvm/test/Transforms/SCCP/range-and-ip.ll +++ b/llvm/test/Transforms/SCCP/range-and-ip.ll @@ -1,8 +1,8 @@ ; 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( @@ -14,7 +14,9 @@ ; 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 @@ -35,8 +37,9 @@ 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)