From c77c186a647b385c291ddabecd70a2b4f84ae342 Mon Sep 17 00:00:00 2001 From: Dmitry Makogon Date: Fri, 10 Feb 2023 16:00:16 +0700 Subject: [PATCH] [LVI] Don't traverse uses when calculating range at use This effectively reverts 5c38c6a and 4f772b0. A recently introduced LazyValueInfo::getConstantRangeAtUse returns incorrect ranges for values in certain cases. One such example is described in PR60629. The issue has something to do with traversing PHI uses of a value transitively. As nikic pointed out, we're effectively reasoning about values from different loop iterations. In the faulting test case, CVP made a miscompilation because the calculated range for a shift argument was incorrect. It returned empty-set, however it is clearly not a dead code. CVP then erased the shift instruction because of empty range. --- llvm/lib/Analysis/LazyValueInfo.cpp | 2 +- llvm/test/Analysis/LazyValueAnalysis/pr60629.ll | 2 - .../CorrelatedValuePropagation/cond-at-use.ll | 72 ++++++++++------------ 3 files changed, 33 insertions(+), 43 deletions(-) diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp index 16d9ad7..efe878d 100644 --- a/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/llvm/lib/Analysis/LazyValueInfo.cpp @@ -1662,7 +1662,7 @@ ConstantRange LazyValueInfo::getConstantRangeAtUse(const Use &U, // position where V can be constrained by a select or branch condition. const Use *CurrU = &U; // TODO: Increase limit? - const unsigned MaxUsesToInspect = 3; + const unsigned MaxUsesToInspect = 0; for (unsigned I = 0; I < MaxUsesToInspect; ++I) { std::optional CondVal; auto *CurrI = cast(CurrU->getUser()); diff --git a/llvm/test/Analysis/LazyValueAnalysis/pr60629.ll b/llvm/test/Analysis/LazyValueAnalysis/pr60629.ll index feae45b..7cc314e 100644 --- a/llvm/test/Analysis/LazyValueAnalysis/pr60629.ll +++ b/llvm/test/Analysis/LazyValueAnalysis/pr60629.ll @@ -1,8 +1,6 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt -passes=correlated-propagation -S %s | FileCheck %s -; XFAIL: * - ; Check that shift is not removed by CVP because of incorrect range returned by LVI::getConstantRangeAtUse. ; https://github.com/llvm/llvm-project/issues/60629 diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/cond-at-use.ll b/llvm/test/Transforms/CorrelatedValuePropagation/cond-at-use.ll index 6270ca8..1b09ca0 100644 --- a/llvm/test/Transforms/CorrelatedValuePropagation/cond-at-use.ll +++ b/llvm/test/Transforms/CorrelatedValuePropagation/cond-at-use.ll @@ -9,9 +9,9 @@ declare i16 @llvm.abs.i16(i16, i1) define i16 @sel_true_cond(i16 %x) { ; CHECK-LABEL: @sel_true_cond( -; CHECK-NEXT: [[SUB1:%.*]] = sub nuw i16 [[X:%.*]], 10 +; CHECK-NEXT: [[SUB:%.*]] = call i16 @llvm.usub.sat.i16(i16 [[X:%.*]], i16 10) ; CHECK-NEXT: [[CMP:%.*]] = icmp uge i16 [[X]], 10 -; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 [[SUB1]], i16 42 +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 [[SUB]], i16 42 ; CHECK-NEXT: ret i16 [[SEL]] ; %sub = call i16 @llvm.usub.sat.i16(i16 %x, i16 10) @@ -76,8 +76,8 @@ define i16 @sel_true_cond_extra_use(i16 %x) { define i16 @sel_true_cond_chain_speculatable(i16 %x) { ; CHECK-LABEL: @sel_true_cond_chain_speculatable( -; CHECK-NEXT: [[SUB1:%.*]] = add nuw i16 [[X:%.*]], 1 -; CHECK-NEXT: [[EXTRA:%.*]] = mul i16 [[SUB1]], 3 +; CHECK-NEXT: [[SUB:%.*]] = call i16 @llvm.uadd.sat.i16(i16 [[X:%.*]], i16 1) +; CHECK-NEXT: [[EXTRA:%.*]] = mul i16 [[SUB]], 3 ; CHECK-NEXT: [[CMP:%.*]] = icmp ne i16 [[X]], -1 ; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 [[EXTRA]], i16 42 ; CHECK-NEXT: ret i16 [[SEL]] @@ -125,9 +125,9 @@ define i16 @sel_true_cond_longer_chain(i16 %x) { define i16 @sel_false_cond(i16 %x) { ; CHECK-LABEL: @sel_false_cond( -; CHECK-NEXT: [[SUB1:%.*]] = sub nuw i16 [[X:%.*]], 10 +; CHECK-NEXT: [[SUB:%.*]] = call i16 @llvm.usub.sat.i16(i16 [[X:%.*]], i16 10) ; CHECK-NEXT: [[CMP:%.*]] = icmp ult i16 [[X]], 10 -; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 42, i16 [[SUB1]] +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 42, i16 [[SUB]] ; CHECK-NEXT: ret i16 [[SEL]] ; %sub = call i16 @llvm.usub.sat.i16(i16 %x, i16 10) @@ -152,13 +152,13 @@ define i16 @sel_false_cond_insufficient(i16 %x) { define i16 @phi_true_cond(i16 %x) { ; CHECK-LABEL: @phi_true_cond( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[SUB1:%.*]] = sub nuw i16 [[X:%.*]], 10 +; CHECK-NEXT: [[SUB:%.*]] = call i16 @llvm.usub.sat.i16(i16 [[X:%.*]], i16 10) ; CHECK-NEXT: [[CMP:%.*]] = icmp uge i16 [[X]], 10 ; CHECK-NEXT: br i1 [[CMP]], label [[JOIN:%.*]], label [[SPLIT:%.*]] ; CHECK: split: ; CHECK-NEXT: br label [[JOIN]] ; CHECK: join: -; CHECK-NEXT: [[PHI:%.*]] = phi i16 [ [[SUB1]], [[ENTRY:%.*]] ], [ 42, [[SPLIT]] ] +; CHECK-NEXT: [[PHI:%.*]] = phi i16 [ [[SUB]], [[ENTRY:%.*]] ], [ 42, [[SPLIT]] ] ; CHECK-NEXT: ret i16 [[PHI]] ; entry: @@ -229,13 +229,13 @@ join: define i16 @phi_false_cond(i16 %x) { ; CHECK-LABEL: @phi_false_cond( ; CHECK-NEXT: entry: -; CHECK-NEXT: [[SUB1:%.*]] = sub nuw i16 [[X:%.*]], 10 +; CHECK-NEXT: [[SUB:%.*]] = call i16 @llvm.usub.sat.i16(i16 [[X:%.*]], i16 10) ; CHECK-NEXT: [[CMP:%.*]] = icmp ult i16 [[X]], 10 ; CHECK-NEXT: br i1 [[CMP]], label [[SPLIT:%.*]], label [[JOIN:%.*]] ; CHECK: split: ; CHECK-NEXT: br label [[JOIN]] ; CHECK: join: -; CHECK-NEXT: [[PHI:%.*]] = phi i16 [ [[SUB1]], [[ENTRY:%.*]] ], [ 42, [[SPLIT]] ] +; CHECK-NEXT: [[PHI:%.*]] = phi i16 [ [[SUB]], [[ENTRY:%.*]] ], [ 42, [[SPLIT]] ] ; CHECK-NEXT: ret i16 [[PHI]] ; entry: @@ -308,10 +308,10 @@ define i16 @loop_cond() { ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[IV:%.*]] = phi i16 [ 1000, [[ENTRY:%.*]] ], [ [[IV_NEXT1:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[IV:%.*]] = phi i16 [ 1000, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ] ; CHECK-NEXT: [[COUNT:%.*]] = phi i16 [ 0, [[ENTRY]] ], [ [[COUNT_NEXT:%.*]], [[LOOP]] ] ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i16 [[IV]], 0 -; CHECK-NEXT: [[IV_NEXT1]] = sub nuw i16 [[IV]], 1 +; CHECK-NEXT: [[IV_NEXT]] = call i16 @llvm.usub.sat.i16(i16 [[IV]], i16 1) ; CHECK-NEXT: [[COUNT_NEXT]] = add i16 [[COUNT]], 1 ; CHECK-NEXT: br i1 [[CMP]], label [[EXIT:%.*]], label [[LOOP]] ; CHECK: exit: @@ -334,8 +334,9 @@ exit: define i16 @urem_elide(i16 %x) { ; CHECK-LABEL: @urem_elide( -; CHECK-NEXT: [[CMP:%.*]] = icmp ult i16 [[X:%.*]], 42 -; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 [[X]], i16 24 +; CHECK-NEXT: [[UREM:%.*]] = urem i16 [[X:%.*]], 42 +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i16 [[X]], 42 +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 [[UREM]], i16 24 ; CHECK-NEXT: ret i16 [[SEL]] ; %urem = urem i16 %x, 42 @@ -346,10 +347,7 @@ define i16 @urem_elide(i16 %x) { define i16 @urem_expand(i16 %x) { ; CHECK-LABEL: @urem_expand( -; CHECK-NEXT: [[X_FROZEN:%.*]] = freeze i16 [[X:%.*]] -; CHECK-NEXT: [[UREM_UREM:%.*]] = sub nuw i16 [[X_FROZEN]], 42 -; CHECK-NEXT: [[UREM_CMP:%.*]] = icmp ult i16 [[X_FROZEN]], 42 -; CHECK-NEXT: [[UREM:%.*]] = select i1 [[UREM_CMP]], i16 [[X_FROZEN]], i16 [[UREM_UREM]] +; CHECK-NEXT: [[UREM:%.*]] = urem i16 [[X:%.*]], 42 ; CHECK-NEXT: [[CMP:%.*]] = icmp ult i16 [[X]], 84 ; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 [[UREM]], i16 24 ; CHECK-NEXT: ret i16 [[SEL]] @@ -362,11 +360,9 @@ define i16 @urem_expand(i16 %x) { define i16 @urem_narrow(i16 %x) { ; CHECK-LABEL: @urem_narrow( -; CHECK-NEXT: [[UREM_LHS_TRUNC:%.*]] = trunc i16 [[X:%.*]] to i8 -; CHECK-NEXT: [[UREM1:%.*]] = urem i8 [[UREM_LHS_TRUNC]], 42 -; CHECK-NEXT: [[UREM_ZEXT:%.*]] = zext i8 [[UREM1]] to i16 +; CHECK-NEXT: [[UREM:%.*]] = urem i16 [[X:%.*]], 42 ; CHECK-NEXT: [[CMP:%.*]] = icmp ult i16 [[X]], 85 -; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 [[UREM_ZEXT]], i16 24 +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 [[UREM]], i16 24 ; CHECK-NEXT: ret i16 [[SEL]] ; %urem = urem i16 %x, 42 @@ -390,10 +386,11 @@ define i16 @urem_insufficient(i16 %x) { define i16 @srem_elide(i16 %x) { ; CHECK-LABEL: @srem_elide( -; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i16 [[X:%.*]], 42 +; CHECK-NEXT: [[SREM:%.*]] = srem i16 [[X:%.*]], 42 +; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i16 [[X]], 42 ; CHECK-NEXT: [[CMP2:%.*]] = icmp sgt i16 [[X]], -42 ; CHECK-NEXT: [[AND:%.*]] = and i1 [[CMP1]], [[CMP2]] -; CHECK-NEXT: [[SEL:%.*]] = select i1 [[AND]], i16 [[X]], i16 24 +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[AND]], i16 [[SREM]], i16 24 ; CHECK-NEXT: ret i16 [[SEL]] ; %srem = srem i16 %x, 42 @@ -406,13 +403,11 @@ define i16 @srem_elide(i16 %x) { define i16 @srem_narrow(i16 %x) { ; CHECK-LABEL: @srem_narrow( -; CHECK-NEXT: [[SREM_LHS_TRUNC:%.*]] = trunc i16 [[X:%.*]] to i8 -; CHECK-NEXT: [[SREM1:%.*]] = srem i8 [[SREM_LHS_TRUNC]], 42 -; CHECK-NEXT: [[SREM_SEXT:%.*]] = sext i8 [[SREM1]] to i16 +; CHECK-NEXT: [[SREM:%.*]] = srem i16 [[X:%.*]], 42 ; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i16 [[X]], 43 ; CHECK-NEXT: [[CMP2:%.*]] = icmp sgt i16 [[X]], -43 ; CHECK-NEXT: [[AND:%.*]] = and i1 [[CMP1]], [[CMP2]] -; CHECK-NEXT: [[SEL:%.*]] = select i1 [[AND]], i16 [[SREM_SEXT]], i16 24 +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[AND]], i16 [[SREM]], i16 24 ; CHECK-NEXT: ret i16 [[SEL]] ; %srem = srem i16 %x, 42 @@ -425,11 +420,9 @@ define i16 @srem_narrow(i16 %x) { define i16 @srem_convert(i16 %x) { ; CHECK-LABEL: @srem_convert( -; CHECK-NEXT: [[X_NONNEG:%.*]] = sub i16 0, [[X:%.*]] -; CHECK-NEXT: [[SREM1:%.*]] = urem i16 [[X_NONNEG]], 42 -; CHECK-NEXT: [[SREM1_NEG:%.*]] = sub i16 0, [[SREM1]] +; CHECK-NEXT: [[SREM:%.*]] = srem i16 [[X:%.*]], 42 ; CHECK-NEXT: [[CMP:%.*]] = icmp slt i16 [[X]], 0 -; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 [[SREM1_NEG]], i16 24 +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 [[SREM]], i16 24 ; CHECK-NEXT: ret i16 [[SEL]] ; %srem = srem i16 %x, 42 @@ -440,11 +433,9 @@ define i16 @srem_convert(i16 %x) { define i16 @sdiv_convert(i16 %x) { ; CHECK-LABEL: @sdiv_convert( -; CHECK-NEXT: [[X_NONNEG:%.*]] = sub i16 0, [[X:%.*]] -; CHECK-NEXT: [[SREM1:%.*]] = udiv i16 [[X_NONNEG]], 42 -; CHECK-NEXT: [[SREM1_NEG:%.*]] = sub i16 0, [[SREM1]] +; CHECK-NEXT: [[SREM:%.*]] = sdiv i16 [[X:%.*]], 42 ; CHECK-NEXT: [[CMP:%.*]] = icmp slt i16 [[X]], 0 -; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 [[SREM1_NEG]], i16 24 +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 [[SREM]], i16 24 ; CHECK-NEXT: ret i16 [[SEL]] ; %srem = sdiv i16 %x, 42 @@ -507,7 +498,7 @@ define i16 @umin_elide(i16 %x) { define i16 @ashr_convert(i16 %x, i16 %y) { ; CHECK-LABEL: @ashr_convert( -; CHECK-NEXT: [[ASHR:%.*]] = lshr i16 [[X:%.*]], [[Y:%.*]] +; CHECK-NEXT: [[ASHR:%.*]] = ashr i16 [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: [[CMP:%.*]] = icmp sge i16 [[X]], 0 ; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 [[ASHR]], i16 24 ; CHECK-NEXT: ret i16 [[SEL]] @@ -520,7 +511,7 @@ define i16 @ashr_convert(i16 %x, i16 %y) { define i32 @sext_convert(i16 %x) { ; CHECK-LABEL: @sext_convert( -; CHECK-NEXT: [[EXT:%.*]] = zext i16 [[X:%.*]] to i32 +; CHECK-NEXT: [[EXT:%.*]] = sext i16 [[X:%.*]] to i32 ; CHECK-NEXT: [[CMP:%.*]] = icmp sge i16 [[X]], 0 ; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i32 [[EXT]], i32 24 ; CHECK-NEXT: ret i32 [[SEL]] @@ -546,8 +537,9 @@ define i16 @infer_flags(i16 %x) { define i16 @and_elide(i16 %x) { ; CHECK-LABEL: @and_elide( -; CHECK-NEXT: [[CMP:%.*]] = icmp ult i16 [[X:%.*]], 8 -; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 [[X]], i16 24 +; CHECK-NEXT: [[AND:%.*]] = and i16 [[X:%.*]], 7 +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i16 [[X]], 8 +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[CMP]], i16 [[AND]], i16 24 ; CHECK-NEXT: ret i16 [[SEL]] ; %and = and i16 %x, 7 -- 2.7.4