From 456497450482153afe86838ac2e2be395206d377 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Tue, 7 Jul 2020 22:50:12 +0200 Subject: [PATCH] [SCCP] Propagate inequalities Teach SCCP to create notconstant lattice values from inequality assumes and nonnull metadata, and update getConstant() to make use of them. Additionally isOverdefined() needs to be changed to consider notconstant an overdefined value. Handling inequality branches is delayed until our branch on undef story in other passes has been improved. Differential Revision: https://reviews.llvm.org/D83643 --- llvm/include/llvm/Analysis/ValueLattice.h | 11 ++++++++++ llvm/lib/Transforms/Scalar/SCCP.cpp | 36 ++++++++++++++++++++----------- llvm/test/Transforms/SCCP/assume.ll | 12 ++++------- llvm/test/Transforms/SCCP/metadata.ll | 12 ++++------- 4 files changed, 42 insertions(+), 29 deletions(-) diff --git a/llvm/include/llvm/Analysis/ValueLattice.h b/llvm/include/llvm/Analysis/ValueLattice.h index bf5bab9..108d080 100644 --- a/llvm/include/llvm/Analysis/ValueLattice.h +++ b/llvm/include/llvm/Analysis/ValueLattice.h @@ -11,6 +11,7 @@ #include "llvm/IR/ConstantRange.h" #include "llvm/IR/Constants.h" +#include "llvm/IR/Instructions.h" // //===----------------------------------------------------------------------===// // ValueLatticeElement @@ -456,6 +457,16 @@ public: if (isConstant() && Other.isConstant()) return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant()); + if (ICmpInst::isEquality(Pred)) { + // not(C) != C => true, not(C) == C => false. + if ((isNotConstant() && Other.isConstant() && + getNotConstant() == Other.getConstant()) || + (isConstant() && Other.isNotConstant() && + getConstant() == Other.getNotConstant())) + return Pred == ICmpInst::ICMP_NE + ? ConstantInt::getTrue(Ty) : ConstantInt::getFalse(Ty); + } + // Integer constants are represented as ConstantRanges with single // elements. if (!isConstantRange() || !Other.isConstantRange()) diff --git a/llvm/lib/Transforms/Scalar/SCCP.cpp b/llvm/lib/Transforms/Scalar/SCCP.cpp index 9c9f483..bd0968b 100644 --- a/llvm/lib/Transforms/Scalar/SCCP.cpp +++ b/llvm/lib/Transforms/Scalar/SCCP.cpp @@ -104,8 +104,7 @@ bool isConstant(const ValueLatticeElement &LV) { // ValueLatticeElement::isOverdefined() and is intended to be used in the // transition to ValueLatticeElement. bool isOverdefined(const ValueLatticeElement &LV) { - return LV.isOverdefined() || - (LV.isConstantRange() && !LV.getConstantRange().isSingleElement()); + return !LV.isUnknownOrUndef() && !isConstant(LV); } //===----------------------------------------------------------------------===// @@ -1123,7 +1122,9 @@ static ValueLatticeElement getValueFromMetadata(const Instruction *I) { if (I->getType()->isIntegerTy()) return ValueLatticeElement::getRange( getConstantRangeFromMetadata(*Ranges)); - // TODO: Also handle MD_nonnull. + if (I->hasMetadata(LLVMContext::MD_nonnull)) + return ValueLatticeElement::getNot( + ConstantPointerNull::get(cast(I->getType()))); return ValueLatticeElement::getOverdefined(); } @@ -1291,6 +1292,17 @@ void SCCPSolver::handleCallResult(CallBase &CB) { return; } + // TODO: Actually filp MayIncludeUndef for the created range to false, + // once most places in the optimizer respect the branches on + // undef/poison are UB rule. The reason why the new range cannot be + // undef is as follows below: + // The new range is based on a branch condition. That guarantees that + // neither of the compare operands can be undef in the branch targets, + // unless we have conditions that are always true/false (e.g. icmp ule + // i32, %a, i32_max). For the latter overdefined/empty range will be + // inferred, but the branch will get folded accordingly anyways. + bool MayIncludeUndef = !isa(PI); + ValueLatticeElement CondVal = getValueState(OtherOp); ValueLatticeElement &IV = ValueState[&CB]; if (CondVal.isConstantRange() || CopyOfVal.isConstantRange()) { @@ -1316,18 +1328,9 @@ void SCCPSolver::handleCallResult(CallBase &CB) { NewCR = CopyOfCR; addAdditionalUser(OtherOp, &CB); - // TODO: Actually filp MayIncludeUndef for the created range to false, - // once most places in the optimizer respect the branches on - // undef/poison are UB rule. The reason why the new range cannot be - // undef is as follows below: - // The new range is based on a branch condition. That guarantees that - // neither of the compare operands can be undef in the branch targets, - // unless we have conditions that are always true/false (e.g. icmp ule - // i32, %a, i32_max). For the latter overdefined/empty range will be - // inferred, but the branch will get folded accordingly anyways. mergeInValue( IV, &CB, - ValueLatticeElement::getRange(NewCR, /*MayIncludeUndef=*/true)); + ValueLatticeElement::getRange(NewCR, MayIncludeUndef)); return; } else if (Pred == CmpInst::ICMP_EQ && CondVal.isConstant()) { // For non-integer values or integer constant expressions, only @@ -1335,6 +1338,13 @@ void SCCPSolver::handleCallResult(CallBase &CB) { addAdditionalUser(OtherOp, &CB); mergeInValue(IV, &CB, CondVal); return; + } else if (Pred == CmpInst::ICMP_NE && CondVal.isConstant() && + !MayIncludeUndef) { + // Propagate inequalities. + addAdditionalUser(OtherOp, &CB); + mergeInValue(IV, &CB, + ValueLatticeElement::getNot(CondVal.getConstant())); + return; } return (void)mergeInValue(IV, &CB, CopyOfVal); diff --git a/llvm/test/Transforms/SCCP/assume.ll b/llvm/test/Transforms/SCCP/assume.ll index dc827f0..ce47877 100644 --- a/llvm/test/Transforms/SCCP/assume.ll +++ b/llvm/test/Transforms/SCCP/assume.ll @@ -51,14 +51,10 @@ define void @nonnull(i32* %v) { ; CHECK-LABEL: @nonnull( ; CHECK-NEXT: [[A:%.*]] = icmp ne i32* [[V:%.*]], null ; CHECK-NEXT: call void @llvm.assume(i1 [[A]]) -; CHECK-NEXT: [[C1:%.*]] = icmp eq i32* [[V]], null -; CHECK-NEXT: call void @use(i1 [[C1]]) -; CHECK-NEXT: [[C2:%.*]] = icmp ne i32* [[V]], null -; CHECK-NEXT: call void @use(i1 [[C2]]) -; CHECK-NEXT: [[C3:%.*]] = icmp eq i32* null, [[V]] -; CHECK-NEXT: call void @use(i1 [[C3]]) -; CHECK-NEXT: [[C4:%.*]] = icmp ne i32* null, [[V]] -; CHECK-NEXT: call void @use(i1 [[C4]]) +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: call void @use(i1 true) ; CHECK-NEXT: ret void ; %a = icmp ne i32* %v, null diff --git a/llvm/test/Transforms/SCCP/metadata.ll b/llvm/test/Transforms/SCCP/metadata.ll index 844e210..f32dca2 100644 --- a/llvm/test/Transforms/SCCP/metadata.ll +++ b/llvm/test/Transforms/SCCP/metadata.ll @@ -48,14 +48,10 @@ define void @load_nonnull(i32** %p, i32** %p2) { ; CHECK-LABEL: @load_nonnull( ; CHECK-NEXT: [[V:%.*]] = load i32*, i32** [[P:%.*]], align 8, !nonnull !2 ; CHECK-NEXT: [[V2:%.*]] = load i32*, i32** [[P2:%.*]], align 8, !nonnull !2 -; CHECK-NEXT: [[C1:%.*]] = icmp ne i32* [[V]], null -; CHECK-NEXT: call void @use(i1 [[C1]]) -; CHECK-NEXT: [[C2:%.*]] = icmp eq i32* [[V]], null -; CHECK-NEXT: call void @use(i1 [[C2]]) -; CHECK-NEXT: [[C3:%.*]] = icmp ne i32* null, [[V]] -; CHECK-NEXT: call void @use(i1 [[C3]]) -; CHECK-NEXT: [[C4:%.*]] = icmp eq i32* null, [[V]] -; CHECK-NEXT: call void @use(i1 [[C4]]) +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: call void @use(i1 false) ; CHECK-NEXT: [[C5:%.*]] = icmp eq i32* [[V]], [[V2]] ; CHECK-NEXT: call void @use(i1 [[C5]]) ; CHECK-NEXT: [[C6:%.*]] = icmp ne i32* [[V]], [[V2]] -- 2.7.4