diff --git a/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp b/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp --- a/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp @@ -973,23 +973,51 @@ } /// Return true if this PHI node is only used by a PHI node cycle that is dead. -static bool isDeadPHICycle(PHINode *PN, - SmallPtrSetImpl &PotentiallyDeadPHIs) { - if (PN->use_empty()) return true; - if (!PN->hasOneUse()) return false; - +/// For example, in the following graph of instructions there is a cycle at ϕ.A +/// between ϕ.A and ϕ.B that isn't used by another instructions. +/// ┌─────┐ +/// │ a │ +/// └─────┘ +/// │ +/// │ +/// ▼ +/// ┌─────┐ +/// │ ϕ.A │ ◀┐ +/// └─────┘ │ +/// │ │ +/// │ │ +/// ▼ │ +/// ┌─────┐ │ +/// │ x │ ─┘ +/// └─────┘ +/// │ +/// │ +/// ▼ +/// ┌─────┐ +/// │ ϕ.B │ ◀┐ +/// └─────┘ │ +/// │ │ +/// │ │ +/// ▼ │ +/// ┌─────┐ │ +/// │ y │ ─┘ +/// └─────┘ +static bool isDeadPHICycle(Instruction *I, + SmallPtrSetImpl &PotentiallyDeadInstrs) { // Remember this node, and if we find the cycle, return. - if (!PotentiallyDeadPHIs.insert(PN).second) + if (!PotentiallyDeadInstrs.insert(I).second) return true; // Don't scan crazily complex things. - if (PotentiallyDeadPHIs.size() == 16) + if (PotentiallyDeadInstrs.size() == 16) return false; - if (PHINode *PU = dyn_cast(PN->user_back())) - return isDeadPHICycle(PU, PotentiallyDeadPHIs); - - return false; + if (I->mayHaveSideEffects() || !wouldInstructionBeTriviallyDead(I)) + return false; + + return all_of(I->users(), [&PotentiallyDeadInstrs](User *U) { + return isDeadPHICycle(cast(U), PotentiallyDeadInstrs); + }); } /// Return true if this phi node is always equal to NonPhiInVal. @@ -1415,32 +1443,17 @@ } } - // If this is a trivial cycle in the PHI node graph, remove it. Basically, if - // this PHI only has a single use (a PHI), and if that PHI only has one use (a - // PHI)... break the cycle. + // If there is a cycle in the PHI node graph which is a dead, remove it. + // I.e. if this PHI has a use that is another PHI, and that PHI uses the first + // phi, and there are no other uses outside of this cycle, then break it. + SmallPtrSet PotentiallyDeadInstrs; + if (isDeadPHICycle(&PN, PotentiallyDeadInstrs)) + return replaceInstUsesWith(PN, PoisonValue::get(PN.getType())); + if (PN.hasOneUse()) { if (foldIntegerTypedPHI(PN)) return nullptr; - Instruction *PHIUser = cast(PN.user_back()); - if (PHINode *PU = dyn_cast(PHIUser)) { - SmallPtrSet PotentiallyDeadPHIs; - PotentiallyDeadPHIs.insert(&PN); - if (isDeadPHICycle(PU, PotentiallyDeadPHIs)) - return replaceInstUsesWith(PN, PoisonValue::get(PN.getType())); - } - - // If this phi has a single use, and if that use just computes a value for - // the next iteration of a loop, delete the phi. This occurs with unused - // induction variables, e.g. "for (int j = 0; ; ++j);". Detecting this - // common case here is good because the only other things that catch this - // are induction variable analysis (sometimes) and ADCE, which is only run - // late. - if (PHIUser->hasOneUse() && - (isa(PHIUser) || isa(PHIUser)) && - PHIUser->user_back() == &PN) { - return replaceInstUsesWith(PN, PoisonValue::get(PN.getType())); - } // When a PHI is used only to be compared with zero, it is safe to replace // an incoming value proved as known nonzero with any non-zero constant. // For example, in the code below, the incoming value %v can be replaced @@ -1449,7 +1462,7 @@ // %v = select %cond, 1, 2 // %p = phi [%v, BB] ... // icmp eq, %p, 0 - auto *CmpInst = dyn_cast(PHIUser); + auto *CmpInst = dyn_cast(PN.user_back()); // FIXME: To be simple, handle only integer type for now. if (CmpInst && isa(PN.getType()) && CmpInst->isEquality() && match(CmpInst->getOperand(1), m_Zero())) { diff --git a/llvm/test/Transforms/InstCombine/fmul-inseltpoison.ll b/llvm/test/Transforms/InstCombine/fmul-inseltpoison.ll --- a/llvm/test/Transforms/InstCombine/fmul-inseltpoison.ll +++ b/llvm/test/Transforms/InstCombine/fmul-inseltpoison.ll @@ -10,10 +10,8 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[FOR_COND:%.*]] ; CHECK: for.cond: -; CHECK-NEXT: [[LOCAL_VAR_7_0:%.*]] = phi <4 x float> [ , [[ENTRY:%.*]] ], [ [[TMP0:%.*]], [[FOR_BODY:%.*]] ] -; CHECK-NEXT: br i1 [[C1:%.*]], label [[FOR_BODY]], label [[FOR_END:%.*]] +; CHECK-NEXT: br i1 [[C1:%.*]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]] ; CHECK: for.body: -; CHECK-NEXT: [[TMP0]] = insertelement <4 x float> [[LOCAL_VAR_7_0]], float 0.000000e+00, i64 2 ; CHECK-NEXT: br label [[FOR_COND]] ; CHECK: for.end: ; CHECK-NEXT: ret void diff --git a/llvm/test/Transforms/InstCombine/fmul.ll b/llvm/test/Transforms/InstCombine/fmul.ll --- a/llvm/test/Transforms/InstCombine/fmul.ll +++ b/llvm/test/Transforms/InstCombine/fmul.ll @@ -377,10 +377,8 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[FOR_COND:%.*]] ; CHECK: for.cond: -; CHECK-NEXT: [[LOCAL_VAR_7_0:%.*]] = phi <4 x float> [ , [[ENTRY:%.*]] ], [ [[TMP0:%.*]], [[FOR_BODY:%.*]] ] -; CHECK-NEXT: br i1 [[C1:%.*]], label [[FOR_BODY]], label [[FOR_END:%.*]] +; CHECK-NEXT: br i1 [[C1:%.*]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]] ; CHECK: for.body: -; CHECK-NEXT: [[TMP0]] = insertelement <4 x float> [[LOCAL_VAR_7_0]], float 0.000000e+00, i64 2 ; CHECK-NEXT: br label [[FOR_COND]] ; CHECK: for.end: ; CHECK-NEXT: ret void @@ -1069,8 +1067,8 @@ define float @negate_if_true(float %x, i1 %cond) { ; CHECK-LABEL: @negate_if_true( ; CHECK-NEXT: [[TMP1:%.*]] = fneg float [[X:%.*]] -; CHECK-NEXT: [[TMP2:%.*]] = select i1 [[COND:%.*]], float [[TMP1]], float [[X]] -; CHECK-NEXT: ret float [[TMP2]] +; CHECK-NEXT: [[R:%.*]] = select i1 [[COND:%.*]], float [[TMP1]], float [[X]] +; CHECK-NEXT: ret float [[R]] ; %sel = select i1 %cond, float -1.0, float 1.0 %r = fmul float %sel, %x @@ -1080,8 +1078,8 @@ define float @negate_if_false(float %x, i1 %cond) { ; CHECK-LABEL: @negate_if_false( ; CHECK-NEXT: [[TMP1:%.*]] = fneg arcp float [[X:%.*]] -; CHECK-NEXT: [[TMP2:%.*]] = select arcp i1 [[COND:%.*]], float [[X]], float [[TMP1]] -; CHECK-NEXT: ret float [[TMP2]] +; CHECK-NEXT: [[R:%.*]] = select arcp i1 [[COND:%.*]], float [[X]], float [[TMP1]] +; CHECK-NEXT: ret float [[R]] ; %sel = select i1 %cond, float 1.0, float -1.0 %r = fmul arcp float %sel, %x @@ -1092,8 +1090,8 @@ ; CHECK-LABEL: @negate_if_true_commute( ; CHECK-NEXT: [[X:%.*]] = fdiv <2 x double> , [[PX:%.*]] ; CHECK-NEXT: [[TMP1:%.*]] = fneg ninf <2 x double> [[X]] -; CHECK-NEXT: [[TMP2:%.*]] = select ninf i1 [[COND:%.*]], <2 x double> [[TMP1]], <2 x double> [[X]] -; CHECK-NEXT: ret <2 x double> [[TMP2]] +; CHECK-NEXT: [[R:%.*]] = select ninf i1 [[COND:%.*]], <2 x double> [[TMP1]], <2 x double> [[X]] +; CHECK-NEXT: ret <2 x double> [[R]] ; %x = fdiv <2 x double> , %px ; thwart complexity-based canonicalization %sel = select i1 %cond, <2 x double> , <2 x double> @@ -1105,8 +1103,8 @@ ; CHECK-LABEL: @negate_if_false_commute( ; CHECK-NEXT: [[X:%.*]] = fdiv <2 x double> , [[PX:%.*]] ; CHECK-NEXT: [[TMP1:%.*]] = fneg <2 x double> [[X]] -; CHECK-NEXT: [[TMP2:%.*]] = select <2 x i1> [[COND:%.*]], <2 x double> [[X]], <2 x double> [[TMP1]] -; CHECK-NEXT: ret <2 x double> [[TMP2]] +; CHECK-NEXT: [[R:%.*]] = select <2 x i1> [[COND:%.*]], <2 x double> [[X]], <2 x double> [[TMP1]] +; CHECK-NEXT: ret <2 x double> [[R]] ; %x = fdiv <2 x double> , %px ; thwart complexity-based canonicalization %sel = select <2 x i1> %cond, <2 x double> , <2 x double> @@ -1203,8 +1201,8 @@ define half @mul_zero_nnan(half %x) { ; CHECK-LABEL: @mul_zero_nnan( -; CHECK-NEXT: [[TMP1:%.*]] = call nnan half @llvm.copysign.f16(half 0xH0000, half [[X:%.*]]) -; CHECK-NEXT: ret half [[TMP1]] +; CHECK-NEXT: [[R:%.*]] = call nnan half @llvm.copysign.f16(half 0xH0000, half [[X:%.*]]) +; CHECK-NEXT: ret half [[R]] ; %r = fmul nnan half %x, 0.0 ret half %r @@ -1214,8 +1212,8 @@ define <2 x float> @mul_zero_nnan_vec_poison(<2 x float> %x) { ; CHECK-LABEL: @mul_zero_nnan_vec_poison( -; CHECK-NEXT: [[TMP1:%.*]] = call nnan <2 x float> @llvm.copysign.v2f32(<2 x float> , <2 x float> [[X:%.*]]) -; CHECK-NEXT: ret <2 x float> [[TMP1]] +; CHECK-NEXT: [[R:%.*]] = call nnan <2 x float> @llvm.copysign.v2f32(<2 x float> , <2 x float> [[X:%.*]]) +; CHECK-NEXT: ret <2 x float> [[R]] ; %r = fmul nnan <2 x float> %x, ret <2 x float> %r diff --git a/llvm/test/Transforms/InstCombine/phi-dead-cycle-iteration.ll b/llvm/test/Transforms/InstCombine/phi-dead-cycle-iteration.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/InstCombine/phi-dead-cycle-iteration.ll @@ -0,0 +1,49 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -passes=instcombine -S -instcombine-infinite-loop-threshold=2 | FileCheck %s + +; Ensure that dead PHI cycles are removed in the same iteration (hence why this +; test sets the loop threshold to 2) +define void @f() { +; CHECK-LABEL: @f( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[A:%.*]] +; CHECK: a: +; CHECK-NEXT: br i1 false, label [[A]], label [[B:%.*]] +; CHECK: b: +; CHECK-NEXT: br label [[B]] +; +entry: + br label %a +a: + %phi.a = phi i32 [ 0, %entry ], [ %x, %a ] + %x = add i32 %phi.a, 1 + br i1 false, label %a, label %b +b: + %phi.b = phi i32 [ %x, %a ], [ %y, %b ] + %y = add i32 %phi.b, 1 + br label %b +} + +; Ensure the dead cycle is still detected when a phi node has multiple uses +define void @multipleUses() { +; CHECK-LABEL: @multipleUses( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[A:%.*]] +; CHECK: a: +; CHECK-NEXT: br i1 false, label [[A]], label [[B:%.*]] +; CHECK: b: +; CHECK-NEXT: br label [[B]] +; +entry: + br label %a +a: + %phi.a = phi i32 [ 0, %entry ], [ %z, %a ] + %x = add i32 %phi.a, 1 + %y = add i32 %phi.a, 2 + %z = add i32 %x, %y + br i1 false, label %a, label %b +b: + %phi.b = phi i32 [ %x, %a ], [ %c, %b ] + %c = add i32 %phi.b, 1 + br label %b +} diff --git a/llvm/test/Transforms/InstCombine/phi-dead-cycle-side-effect.ll b/llvm/test/Transforms/InstCombine/phi-dead-cycle-side-effect.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/InstCombine/phi-dead-cycle-side-effect.ll @@ -0,0 +1,28 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -passes=instcombine -S | FileCheck %s +; Ensure that instructions with side effects don't cause the cycle to be removed +define void @sideEffect(ptr %p) { +; CHECK-LABEL: @sideEffect( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[A:%.*]] +; CHECK: a: +; CHECK-NEXT: [[PHI_A:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[X:%.*]], [[A]] ] +; CHECK-NEXT: [[TMP0:%.*]] = sext i32 [[PHI_A]] to i64 +; CHECK-NEXT: [[Q:%.*]] = getelementptr i32, ptr [[P:%.*]], i64 [[TMP0]] +; CHECK-NEXT: [[X]] = load volatile i32, ptr [[Q]], align 4 +; CHECK-NEXT: br i1 false, label [[A]], label [[B:%.*]] +; CHECK: b: +; CHECK-NEXT: br label [[B]] +; +entry: + br label %a +a: + %phi.a = phi i32 [ 0, %entry ], [ %x, %a ] + %q = getelementptr i32, ptr %p, i32 %phi.a + %x = load volatile i32, ptr %q + br i1 false, label %a, label %b +b: + %phi.b = phi i32 [ %x, %a ], [ %y, %b ] + %y = add i32 %phi.b, 1 + br label %b +} diff --git a/llvm/test/Transforms/InstCombine/pr27703.ll b/llvm/test/Transforms/InstCombine/pr27703.ll --- a/llvm/test/Transforms/InstCombine/pr27703.ll +++ b/llvm/test/Transforms/InstCombine/pr27703.ll @@ -1,6 +1,6 @@ ; RUN: opt < %s -passes=instcombine -S | FileCheck %s -define void @mem() { +define ptr @mem() { bb: br label %bb6 @@ -13,7 +13,7 @@ br label %bb6 bb206: - ret void + ret ptr %t2 ; CHECK: phi ; CHECK-NEXT: load ; CHECK-NEXT: load