diff --git a/llvm/include/llvm/Analysis/LazyValueInfo.h b/llvm/include/llvm/Analysis/LazyValueInfo.h --- a/llvm/include/llvm/Analysis/LazyValueInfo.h +++ b/llvm/include/llvm/Analysis/LazyValueInfo.h @@ -85,7 +85,9 @@ /// Return the ConstantRange constraint that is known to hold for the /// specified value at the end of the specified block. This may only be called /// on integer-typed Values. - ConstantRange getConstantRange(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr); + ConstantRange getConstantRange(Value *V, BasicBlock *BB, + Instruction *CxtI = nullptr, + bool UndefAllowed = true); /// Determine whether the specified value is known to be a /// constant on the specified edge. Return null if not. 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 @@ -37,7 +37,7 @@ /// assuming all uses of the result will be replaced. /// Transition allowed to the following states: /// constant - /// singlecrfromundef + /// constantrange_including_undef /// overdefined undef, @@ -59,20 +59,20 @@ /// 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) + /// constantrange_including_undef /// 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. + /// This Value falls within this range, but also may be undef. + /// Merging it with other constant ranges results in + /// constantrange_including_undef. /// Transition allowed to the following states: /// overdefined - singlecrfromundef, + constantrange_including_undef, /// We can not precisely model the dynamic values this value might take. /// No transitions are allowed after reaching overdefined. - overdefined + overdefined, }; ValueLatticeElementTy Tag; @@ -97,9 +97,9 @@ case unknown: case undef: case constant: - case singlecrfromundef: case notconstant: break; + case constantrange_including_undef: case constantrange: Range.~ConstantRange(); break; @@ -128,7 +128,7 @@ switch (Other.Tag) { case constantrange: - case singlecrfromundef: + case constantrange_including_undef: if (!isConstantRange()) new (&Range) ConstantRange(Other.Range); else @@ -161,12 +161,13 @@ Res.markNotConstant(C); return Res; } - static ValueLatticeElement getRange(ConstantRange CR) { + static ValueLatticeElement getRange(ConstantRange CR, + bool MayIncludeUndef = false) { if (CR.isFullSet()) return getOverdefined(); ValueLatticeElement Res; - Res.markConstantRange(std::move(CR)); + Res.markConstantRange(std::move(CR), MayIncludeUndef); return Res; } static ValueLatticeElement getOverdefined() { @@ -179,10 +180,17 @@ 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 || Tag == singlecrfromundef; + bool isConstantRangeIncludingUndef() const { + return Tag == constantrange_including_undef; + } + /// Returns true if this value is a constant range. Use \p UndefAllowed to + /// exclude non-singleton constant ranges that may also be undef. Note that + /// this function also returns true if the range may include undef, but only + /// contains a single element. In that case, it can be replaced by a constant. + bool isConstantRange(bool UndefAllowed = true) const { + return Tag == constantrange || (Tag == constantrange_including_undef && + (UndefAllowed || Range.isSingleElement())); } bool isOverdefined() const { return Tag == overdefined; } @@ -196,8 +204,12 @@ return ConstVal; } - const ConstantRange &getConstantRange() const { - assert(isConstantRange() && + /// Returns the constant range for this value. Use \p UndefAllowed to exclude + /// non-singleton constant ranges that may also be undef. Note that this + /// function also returns a range if the range may include undef, but only + /// contains a single element. In that case, it can be replaced by a constant. + const ConstantRange &getConstantRange(bool UndefAllowed = true) const { + assert(isConstantRange(UndefAllowed) && "Cannot get the constant-range of a non-constant-range!"); return Range; } @@ -231,7 +243,7 @@ return true; } - bool markConstant(Constant *V) { + bool markConstant(Constant *V, bool MayIncludeUndef = false) { if (isa(V)) return markUndef(); @@ -241,7 +253,7 @@ } if (ConstantInt *CI = dyn_cast(V)) - return markConstantRange(ConstantRange(CI->getValue())); + return markConstantRange(ConstantRange(CI->getValue()), MayIncludeUndef); assert(isUnknown() || isUndef()); Tag = constant; @@ -271,29 +283,38 @@ /// 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; - - assert(!isSingleCRFromUndef()); + /// NewR and the tag. Otherwise \p NewR must be a superset of the existing + /// range or the object must be undef. The tag is set to + /// constant_range_including_undef if either the existing value or the new + /// range may include undef. + bool markConstantRange(ConstantRange NewR, bool MayIncludeUndef = false) { + if (NewR.isFullSet()) + return markOverdefined(); + ValueLatticeElementTy OldTag = Tag; + ValueLatticeElementTy NewTag = + (isUndef() || isConstantRangeIncludingUndef() || MayIncludeUndef) + ? constantrange_including_undef + : constantrange; + if (isConstantRange()) { if (NewR.isEmptySet()) return markOverdefined(); + Tag = NewTag; + if (getConstantRange() == NewR) + return Tag != OldTag; + assert(NewR.contains(getConstantRange()) && "Existing range must be a subset of NewR"); Range = std::move(NewR); return true; } - assert(isUnknown() || (isUndef() && NewR.isSingleElement())); + assert(isUnknown() || isUndef()); if (NewR.isEmptySet()) return markOverdefined(); - Tag = isUnknown() ? constantrange : singlecrfromundef; + Tag = NewTag; new (&Range) ConstantRange(std::move(NewR)); return true; } @@ -313,9 +334,10 @@ if (RHS.isUndef()) return false; if (RHS.isConstant()) - return markConstant(RHS.getConstant()); - if (RHS.isConstantRange() && RHS.getConstantRange().isSingleElement()) - return markConstantRange(RHS.getConstantRange()); + return markConstant(RHS.getConstant(), /*MayIncludeUndef=*/true); + if (RHS.isConstantRange()) + return markConstantRange(RHS.getConstantRange(true), + /*MayIncludeUndef=*/true); return markOverdefined(); } @@ -341,9 +363,12 @@ return true; } + auto OldTag = Tag; assert(isConstantRange() && "New ValueLattice type?"); - if (RHS.isUndef() && getConstantRange().isSingleElement()) - return false; + if (RHS.isUndef()) { + Tag = constantrange_including_undef; + return OldTag != Tag; + } if (!RHS.isConstantRange()) { // We can get here if we've encountered a constantexpr of integer type @@ -353,21 +378,9 @@ } 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)); + return markConstantRange( + std::move(NewR), + /*MayIncludeUndef=*/RHS.isConstantRangeIncludingUndef()); } // Compares this symbolic value with Other using Pred and returns either diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp --- a/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/llvm/lib/Analysis/LazyValueInfo.cpp @@ -121,11 +121,13 @@ // Intersect two constant ranges ConstantRange Range = - A.getConstantRange().intersectWith(B.getConstantRange()); + A.getConstantRange().intersectWith(B.getConstantRange()); // Note: An empty range is implicitly converted to overdefined internally. // TODO: We could instead use Undefined here since we've proven a conflict // and thus know this path must be unreachable. - return ValueLatticeElement::getRange(std::move(Range)); + return ValueLatticeElement::getRange( + std::move(Range), /*MayIncludeUndef=*/A.isConstantRangeIncludingUndef() | + B.isConstantRangeIncludingUndef()); } //===----------------------------------------------------------------------===// @@ -901,17 +903,21 @@ return TrueCR.umax(FalseCR); }; }(); - BBLV = ValueLatticeElement::getRange(ResultCR); + BBLV = ValueLatticeElement::getRange( + ResultCR, TrueVal.isConstantRangeIncludingUndef() | + FalseVal.isConstantRangeIncludingUndef()); return true; } if (SPR.Flavor == SPF_ABS) { if (LHS == SI->getTrueValue()) { - BBLV = ValueLatticeElement::getRange(TrueCR.abs()); + BBLV = ValueLatticeElement::getRange( + TrueCR.abs(), TrueVal.isConstantRangeIncludingUndef()); return true; } if (LHS == SI->getFalseValue()) { - BBLV = ValueLatticeElement::getRange(FalseCR.abs()); + BBLV = ValueLatticeElement::getRange( + FalseCR.abs(), FalseVal.isConstantRangeIncludingUndef()); return true; } } @@ -919,11 +925,13 @@ if (SPR.Flavor == SPF_NABS) { ConstantRange Zero(APInt::getNullValue(TrueCR.getBitWidth())); if (LHS == SI->getTrueValue()) { - BBLV = ValueLatticeElement::getRange(Zero.sub(TrueCR.abs())); + BBLV = ValueLatticeElement::getRange( + Zero.sub(TrueCR.abs()), FalseVal.isConstantRangeIncludingUndef()); return true; } if (LHS == SI->getFalseValue()) { - BBLV = ValueLatticeElement::getRange(Zero.sub(FalseCR.abs())); + BBLV = ValueLatticeElement::getRange( + Zero.sub(FalseCR.abs()), FalseVal.isConstantRangeIncludingUndef()); return true; } } @@ -1706,7 +1714,8 @@ } ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB, - Instruction *CxtI) { + Instruction *CxtI, + bool UndefAllowed) { assert(V->getType()->isIntegerTy()); unsigned Width = V->getType()->getIntegerBitWidth(); const DataLayout &DL = BB->getModule()->getDataLayout(); @@ -1714,8 +1723,8 @@ getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); if (Result.isUnknown()) return ConstantRange::getEmpty(Width); - if (Result.isConstantRange()) - return Result.getConstantRange(); + if (Result.isConstantRange(UndefAllowed)) + return Result.getConstantRange(UndefAllowed); // We represent ConstantInt constants as constant ranges but other kinds // of integer constants, i.e. ConstantExpr will be tagged as constants assert(!(Result.isConstant() && isa(Result.getConstant())) && 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 @@ -20,10 +20,10 @@ if (Val.isNotConstant()) return OS << "notconstant<" << *Val.getNotConstant() << ">"; - if (Val.isSingleCRFromUndef()) - return OS << "constantrange (from undef)<" - << Val.getConstantRange().getLower() << ", " - << Val.getConstantRange().getUpper() << ">"; + if (Val.isConstantRangeIncludingUndef()) + return OS << "constantrange incl. undef <" + << Val.getConstantRange(true).getLower() << ", " + << Val.getConstantRange(true).getUpper() << ">"; if (Val.isConstantRange()) return OS << "constantrange<" << Val.getConstantRange().getLower() << ", " diff --git a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp --- a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -790,7 +790,10 @@ if (!RHS || !RHS->getValue().isMask()) return false; - ConstantRange LRange = LVI->getConstantRange(LHS, BB, BinOp); + // We can only replace the AND with LHS based on range info if the range does + // not include undef. + ConstantRange LRange = + LVI->getConstantRange(LHS, BB, BinOp, /*UndefAllowed=*/false); if (!LRange.getUnsignedMax().ule(RHS->getValue())) return false; 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 @@ -57,10 +57,8 @@ ; CHECK-NEXT: [[RES:%.*]] = and i64 [[P]], 255 ; CHECK-NEXT: br label [[EXIT:%.*]] ; CHECK: exit: -; CHECK-NEXT: [[F_1:%.*]] = icmp eq i64 [[P]], 256 -; CHECK-NEXT: call void @use(i1 [[F_1]]) -; CHECK-NEXT: [[T_1:%.*]] = icmp ne i64 [[P]], 256 -; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: ret i64 [[RES]] ; entry: @@ -163,12 +161,9 @@ ; CHECK-NEXT: [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ [[R]], [[BB2]] ] ; CHECK-NEXT: br label [[EXIT:%.*]] ; CHECK: exit: -; CHECK-NEXT: [[C:%.*]] = icmp ult i64 [[P]], 256 -; CHECK-NEXT: [[F_1:%.*]] = icmp eq i64 [[P]], 256 -; CHECK-NEXT: call void @use(i1 [[F_1]]) -; CHECK-NEXT: [[T_1:%.*]] = icmp ne i64 [[P]], 256 -; CHECK-NEXT: call void @use(i1 [[T_1]]) -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: ret i1 true ; entry: br i1 %cond, label %bb1, label %bb2 @@ -211,10 +206,8 @@ ; CHECK-NEXT: [[RES:%.*]] = and i64 [[P]], 255 ; CHECK-NEXT: br label [[EXIT:%.*]] ; CHECK: exit: -; CHECK-NEXT: [[F_1:%.*]] = icmp eq i64 [[P]], 256 -; CHECK-NEXT: call void @use(i1 [[F_1]]) -; CHECK-NEXT: [[T_1:%.*]] = icmp ne i64 [[P]], 256 -; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: ret i64 [[RES]] ; entry: @@ -261,10 +254,8 @@ ; CHECK-NEXT: [[RES:%.*]] = and i64 [[P]], 255 ; CHECK-NEXT: br label [[EXIT:%.*]] ; CHECK: exit: -; CHECK-NEXT: [[F_1:%.*]] = icmp eq i64 [[P]], 256 -; CHECK-NEXT: call void @use(i1 [[F_1]]) -; CHECK-NEXT: [[T_1:%.*]] = icmp ne i64 [[P]], 256 -; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: ret i64 [[RES]] ; entry: @@ -311,10 +302,8 @@ ; CHECK-NEXT: [[RES:%.*]] = and i64 [[P]], 255 ; CHECK-NEXT: br label [[EXIT:%.*]] ; CHECK: exit: -; CHECK-NEXT: [[F_1:%.*]] = icmp eq i64 [[P]], 256 -; CHECK-NEXT: call void @use(i1 [[F_1]]) -; CHECK-NEXT: [[T_1:%.*]] = icmp ne i64 [[P]], 256 -; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: ret i64 [[RES]] ; entry: diff --git a/llvm/test/Transforms/SCCP/phi-cycle.ll b/llvm/test/Transforms/SCCP/phi-cycle.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/SCCP/phi-cycle.ll @@ -0,0 +1,33 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -ipsccp -S %s | FileCheck %s + +declare i1 @cond() + +define i32 @test() { +; CHECK-LABEL: @test( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[C_1:%.*]] = call i1 @cond() +; CHECK-NEXT: br i1 [[C_1]], label [[LOOP]], label [[LATCH_2:%.*]] +; CHECK: latch.2: +; CHECK-NEXT: [[C_2:%.*]] = call i1 @cond() +; CHECK-NEXT: br i1 [[C_2]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret i32 0 +; +entry: + br label %loop + +loop: + %p = phi i32 [ undef, %entry ], [ 0, %latch.2 ], [ %p, %loop] + %c.1 = call i1 @cond() + br i1 %c.1, label %loop, label %latch.2 + +latch.2: + %c.2 = call i1 @cond() + br i1 %c.2, label %loop, label %exit + +exit: + ret i32 %p +} 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 @@ -14,9 +14,7 @@ ; CHECK: bb2: ; CHECK-NEXT: [[RANGE:%.*]] = and i64 [[A:%.*]], 255 ; CHECK-NEXT: [[C_3:%.*]] = call i1 @f1(i64 [[RANGE]]) -; 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]] +; CHECK-NEXT: ret i1 true ; %c.1 = call i1 @f1(i64 undef) br label %bb1 @@ -37,9 +35,8 @@ define internal i1 @f1(i64 %r) { ; CHECK-LABEL: define {{.*}} @f1( -; CHECK-NEXT: [[C:%.*]] = icmp ult i64 [[R:%.*]], 256 -; CHECK-NEXT: call void @sideeffect(i1 [[C]], i64 [[R]]) -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: call void @sideeffect(i1 true, i64 [[R:%.*]]) +; CHECK-NEXT: ret i1 undef ; %c = icmp ult i64 %r, 256 call void @sideeffect(i1 %c, i64 %r) diff --git a/llvm/test/Transforms/SCCP/range-and.ll b/llvm/test/Transforms/SCCP/range-and.ll --- a/llvm/test/Transforms/SCCP/range-and.ll +++ b/llvm/test/Transforms/SCCP/range-and.ll @@ -128,7 +128,7 @@ ret i64 %res } -define i1 @constant_range_and_255_100(i1 %cond, i64 %a) { +define i64 @constant_range_and_255_100(i1 %cond, i64 %a) { ; CHECK-LABEL: @constant_range_and_255_100( ; CHECK-NEXT: entry: ; CHECK-NEXT: br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]] @@ -141,7 +141,8 @@ ; CHECK: bb3: ; CHECK-NEXT: [[P:%.*]] = phi i64 [ [[R_1]], [[BB1]] ], [ [[R_2]], [[BB2]] ] ; CHECK-NEXT: [[P_AND:%.*]] = and i64 [[P]], 512 -; CHECK-NEXT: ret i1 true +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: ret i64 [[P_AND]] ; entry: br i1 %cond, label %bb1, label %bb2 @@ -158,7 +159,8 @@ %p = phi i64 [ %r.1, %bb1 ], [ %r.2, %bb2 ] %p.and = and i64 %p, 512 %c = icmp ult i64 %p.and, 256 - ret i1 %c + call void @use(i1 %c) + ret i64 %p.and } @@ -224,8 +226,7 @@ ; CHECK-NEXT: br label [[BB3]] ; CHECK: bb3: ; CHECK-NEXT: [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ [[R]], [[BB2]] ] -; CHECK-NEXT: [[C:%.*]] = icmp ult i64 [[P]], 256 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; entry: br i1 %cond, label %bb1, label %bb2 @@ -254,8 +255,7 @@ ; CHECK-NEXT: br label [[BB3]] ; CHECK: bb3: ; CHECK-NEXT: [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ undef, [[BB2]] ] -; CHECK-NEXT: [[C:%.*]] = icmp ult i64 [[P]], 256 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; entry: br i1 %cond, label %bb1, label %bb2