[InstCombine] Teach isDeadPHICycle to look through multiple uses

[luke]

Summary

Instead of only detecting trivial cycles which must be a PHI with a single use that's a PHI, which in turn has a single use of the first PHI, generalize it to catch more complex cycles. This means making it look through all of its uses, as well as looking through arbitrary side-effect free instructions.

The motivation behind this is to enable InstCombiner to remove larger dead PHI cycles in one iteration, to prevent cascading iterations in some pathological cases with lots of dead PHI cycles.

Supersedes D142293
Fixes https://github.com/llvm/llvm-project/issues/50564

[luke]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

1443

This is now covered by isDeadPHICycle

llvm/test/Transforms/InstCombine/fmul.ll

396–400

Looks like a dead cycle to me. I presume it's now detected because it isDeadPHICycle can look through arbitrary instructions now

llvm/test/Transforms/InstCombine/pr27703.ll

16

Otherwise a dead phi cycle is detected here and the phi is removed

[luismarques]

It might be a good idea to see the compile-time impact of this with https://llvm-compile-time-tracker.com?

[luke]

In D142551#4080233, @luismarques wrote:

It might be a good idea to see the compile-time impact of this with https://llvm-compile-time-tracker.com?

Good idea, I don't have access to a remote on it though. Would someone be able to post a branch with this patch on it?

[luismarques]

In D142551#4080298, @luke wrote:

Good idea, I don't have access to a remote on it though. Would someone be able to post a branch with this patch on it?

I think I can do it.

[luismarques]

In D142551#4080298, @luke wrote:

Good idea, I don't have access to a remote on it though. Would someone be able to post a branch with this patch on it?

https://llvm-compile-time-tracker.com/compare.php?from=f84d3dd0fd4ec3be52488e4c29baebb0077b04d4&to=b79315a7071612621ac543cd7595cb487c437a64&stat=instructions:u

[luke]

In D142551#4080424, @luismarques wrote:

In D142551#4080298, @luke wrote:

Good idea, I don't have access to a remote on it though. Would someone be able to post a branch with this patch on it?

https://llvm-compile-time-tracker.com/compare.php?from=f84d3dd0fd4ec3be52488e4c29baebb0077b04d4&to=b79315a7071612621ac543cd7595cb487c437a64&stat=instructions:u

Thanks. That seems like a non-negligible increase. Would it be worthwhile then limiting the search depth for non-phi node instructions to maybe 1 or 2 at a time?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

975–976

This code should also run for non-phis, with PotentiallyDeadPHIs -> PotentiallyDeadInsts. We want to count non-phi instructions towards the limit as well. I expect this is why you're seeing such a large compile time impact, because as written we only limit the number of visited phis, not the number of visited instructions.

1016

Can cast<> here, all users of instructions are instructions.

1016

Returning false for I->use_empty() doesn't really make sense. I suspect that what you're trying to work around here is the something like br doesn't have side effects, but also can't just be removed. The correct predicate to check here is wouldInstructionBeTriviallyDead.

[luke]

Address comments

[luke]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

1016

That makes much more sense, thanks.
I've updated the diff but now isDeadPHICycle is really just isDeadCycle, which makes me wonder if there's another, more generic place for this.

[nikic]

Huh, this made compile-time impact even worse: https://llvm-compile-time-tracker.com/compare.php?from=051bcd4f310bbf97781b9ccc95ae2754224a75b2&to=bd36ced96eabd9b4e028778d058dcb56bb6d86ba&stat=instructions

Apparently wouldInstructionBeTriviallyDead is that expensive. Using !isa<PHINode>(I) && !isa<BinaryOperator>(I) && !isa<GetElementPtrInst>(I)) in keeping with the existing code brings it down to this: http://llvm-compile-time-tracker.com/compare.php?from=051bcd4f310bbf97781b9ccc95ae2754224a75b2&to=abae5ca4dc70078006e4e26095215a732be1f330&stat=instructions%3Au

This is still not as free as I had hoped :/

[luke]

In D142551#4083916, @nikic wrote:

Huh, this made compile-time impact even worse: https://llvm-compile-time-tracker.com/compare.php?from=051bcd4f310bbf97781b9ccc95ae2754224a75b2&to=bd36ced96eabd9b4e028778d058dcb56bb6d86ba&stat=instructions

Apparently wouldInstructionBeTriviallyDead is that expensive. Using !isa<PHINode>(I) && !isa<BinaryOperator>(I) && !isa<GetElementPtrInst>(I)) in keeping with the existing code brings it down to this: http://llvm-compile-time-tracker.com/compare.php?from=051bcd4f310bbf97781b9ccc95ae2754224a75b2&to=abae5ca4dc70078006e4e26095215a732be1f330&stat=instructions%3Au

This is still not as free as I had hoped :/

We could also try limiting it to phi nodes with one use. There’s a test case in there for a phi node with 2 uses, but the actual bug that this aims to fix only has single use phi nodes.

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

Instruction *InstCombinerImpl::foldPHIArgOpIntoPHI(PHINode &PN) {
 
   CmpInst *CIOp = cast<CmpInst>(FirstInst);
   CmpInst *NewCI = CmpInst::Create(CIOp->getOpcode(), CIOp->getPredicate(),
                                    PhiVal, ConstantOp);
   PHIArgMergedDebugLoc(NewCI, PN);
   return NewCI;
 }
 
 /// Return true if this PHI node is only used by a PHI node cycle that is dead.
-static bool isDeadPHICycle(PHINode *PN,
-                           SmallPtrSetImpl<PHINode *> &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<Instruction *> &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<PHINode>(PN->user_back()))
-    return isDeadPHICycle(PU, PotentiallyDeadPHIs);
-
+  if (I->mayHaveSideEffects() || !wouldInstructionBeTriviallyDead(I))
     return false;
+  
+  return all_of(I->users(), [&PotentiallyDeadInstrs](User *U) {
+    return isDeadPHICycle(cast<Instruction>(U), PotentiallyDeadInstrs);
+  });
 }
 
 /// Return true if this phi node is always equal to NonPhiInVal.
 /// This happens with mutually cyclic phi nodes like:
 ///   z = some value; x = phi (y, z); y = phi (x, z)
 static bool PHIsEqualValue(PHINode *PN, Value *NonPhiInVal,
                            SmallPtrSetImpl<PHINode*> &ValueEqualPHIs) {
   // See if we already saw this PHI node.
if (IV0 != IV0Stripped &&
         all_of(PN.incoming_values(), [&CheckedIVs, IV0Stripped](Value *IV) {
           return !CheckedIVs.insert(IV).second ||
                  IV0Stripped == IV->stripPointerCasts();
         })) {
       return CastInst::CreatePointerCast(IV0Stripped, PN.getType());
     }
   }
 
-  // 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<Instruction*, 16> PotentiallyDeadInstrs;
+  if (isDeadPHICycle(&PN, PotentiallyDeadInstrs))
+    return replaceInstUsesWith(PN, PoisonValue::get(PN.getType()));
+
   if (PN.hasOneUse()) {
     if (foldIntegerTypedPHI(PN))
       return nullptr;
 
-    Instruction *PHIUser = cast<Instruction>(PN.user_back());
-    if (PHINode *PU = dyn_cast<PHINode>(PHIUser)) {
-      SmallPtrSet<PHINode*, 16> 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<BinaryOperator>(PHIUser) || isa<GetElementPtrInst>(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
     // with any non-zero constant based on the fact that the PHI is only used to
     // be compared with zero and %v is a known non-zero value:
     // %v = select %cond, 1, 2
     // %p = phi [%v, BB] ...
     //      icmp eq, %p, 0
-    auto *CmpInst = dyn_cast<ICmpInst>(PHIUser);
+    auto *CmpInst = dyn_cast<ICmpInst>(PN.user_back());
     // FIXME: To be simple, handle only integer type for now.
     if (CmpInst && isa<IntegerType>(PN.getType()) && CmpInst->isEquality() &&
         match(CmpInst->getOperand(1), m_Zero())) {
       ConstantInt *NonZeroConst = nullptr;
       bool MadeChange = false;
       for (unsigned I = 0, E = PN.getNumIncomingValues(); I != E; ++I) {
         Instruction *CtxI = PN.getIncomingBlock(I)->getTerminator();
         Value *VA = PN.getIncomingValue(I);

llvm/test/Transforms/InstCombine/fmul-inseltpoison.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -passes=instcombine < %s | FileCheck %s
 
 ; A copy of fmul.ll, with undef at insertelement/shufflevector replaced with
 ; poison
 
 ; Don't crash when attempting to cast a constant FMul to an instruction.
 define void @test8(ptr %inout, i1 %c1) {
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_COND:%.*]]
 ; CHECK:       for.cond:
-; CHECK-NEXT:    [[LOCAL_VAR_7_0:%.*]] = phi <4 x float> [ <float -0.000000e+00, float -0.000000e+00, float -0.000000e+00, float -0.000000e+00>, [[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
 ;
 entry:
   %0 = load i32, ptr %inout, align 4
   %conv = uitofp i32 %0 to float
   %vecinit = insertelement <4 x float> <float 0.000000e+00, float 0.000000e+00, float 0.000000e+00, float poison>, float %conv, i32 3

llvm/test/Transforms/InstCombine/fmul.ll

 }
 
 ; Don't crash when attempting to cast a constant FMul to an instruction.
 define void @test8(ptr %inout, i1 %c1) {
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_COND:%.*]]
 ; CHECK:       for.cond:
-; CHECK-NEXT:    [[LOCAL_VAR_7_0:%.*]] = phi <4 x float> [ <float -0.000000e+00, float -0.000000e+00, float -0.000000e+00, float -0.000000e+00>, [[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
 ;
 entry:
   %0 = load i32, ptr %inout, align 4
   %conv = uitofp i32 %0 to float
   %vecinit = insertelement <4 x float> <float 0.000000e+00, float 0.000000e+00, float 0.000000e+00, float undef>, float %conv, i32 3
   %sub = fsub <4 x float> <float -0.000000e+00, float -0.000000e+00, float -0.000000e+00, float -0.000000e+00>, %vecinit
   %1 = shufflevector <4 x float> %sub, <4 x float> undef, <4 x i32> <i32 1, i32 1, i32 1, i32 1>
   %mul = fmul <4 x float> zeroinitializer, %1
   br label %for.cond
 
 for.cond:                                         ; preds = %for.body, %entry
   %local_var_7.0 = phi <4 x float> [ %mul, %entry ], [ %2, %for.body ]
   br i1 %c1, label %for.body, label %for.end
 
 for.body:                                         ; preds = %for.cond
   %2 = insertelement <4 x float> %local_var_7.0, float 0.000000e+00, i32 2
   br label %for.cond
 
 for.end:                                          ; preds = %for.cond
   ret void
 }
 
 ; X * -1.0 => -0.0 - X
 define float @test9(float %x) {
;
   %fsub = fsub double -0.000000e+00, bitcast (i64 ptrtoint (ptr getelementptr inbounds ({ [2 x ptr] }, ptr @g, i64 0, inrange i32 0, i64 2) to i64) to double)
   %r = fmul double %x, %fsub
   ret double %r
 }
 
 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
   ret float %r
 }
 
 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
   ret float %r
 }
 
 define <2 x double> @negate_if_true_commute(<2 x double> %px, i1 %cond) {
 ; CHECK-LABEL: @negate_if_true_commute(
 ; CHECK-NEXT:    [[X:%.*]] = fdiv <2 x double> <double 4.200000e+01, double 4.200000e+01>, [[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> <double 42.0, double 42.0>, %px  ; thwart complexity-based canonicalization
   %sel = select i1 %cond, <2 x double> <double -1.0, double -1.0>, <2 x double> <double 1.0, double 1.0>
   %r = fmul ninf <2 x double> %x, %sel
   ret <2 x double> %r
 }
 
 define <2 x double> @negate_if_false_commute(<2 x double> %px, <2 x i1> %cond) {
 ; CHECK-LABEL: @negate_if_false_commute(
 ; CHECK-NEXT:    [[X:%.*]] = fdiv <2 x double> <double 4.200000e+01, double 5.100000e+00>, [[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> <double 42.0, double 5.1>, %px  ; thwart complexity-based canonicalization
   %sel = select <2 x i1> %cond, <2 x double> <double 1.0, double 1.0>, <2 x double> <double -1.0, double -1.0>
   %r = fmul <2 x double> %x, %sel
   ret <2 x double> %r
 }
 
 ; Negative test

 ;
   %shuf = shufflevector <vscale x 2 x float> insertelement (<vscale x 2 x float> undef, float 0.0, i32 0), <vscale x 2 x float> undef, <vscale x 2 x i32> zeroinitializer
   %t3 = fmul fast <vscale x 2 x float> %shuf, %z
   ret <vscale x 2 x float> %t3
 }
 
 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
 }
 
 ; poison propagates through vector elements
 
 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> <float 0.000000e+00, float poison>, <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> <float 0.000000e+00, float poison>, <2 x float> [[X:%.*]])
+; CHECK-NEXT:    ret <2 x float> [[R]]
 ;
   %r = fmul nnan <2 x float> %x, <float 0.0, float poison>
   ret <2 x float> %r
 }
 
 ; negative test - must have nnan
 
 define half @mul_zero(half %x) {

llvm/test/Transforms/InstCombine/phi-dead-cycle-iteration.ll

+; 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
+}

llvm/test/Transforms/InstCombine/phi-dead-cycle-side-effect.ll

+; 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
+}

llvm/test/Transforms/InstCombine/pr27703.ll

 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
-define void @mem() {
+define ptr @mem() {
 bb:
   br label %bb6
 
 bb6:
   %.0 = phi ptr [ undef, %bb ], [ %t2, %bb6 ]
   %tmp = load ptr, ptr %.0, align 8
   %bc = bitcast ptr %tmp to ptr
   %t1 = load ptr, ptr %bc, align 8
   %t2 = bitcast ptr %t1 to ptr
   br label %bb6
 
 bb206:
-  ret void
+  ret ptr %t2
 ; CHECK: phi
 ; CHECK-NEXT: load
 ; CHECK-NEXT: load
 ; CHECK-NEXT: br
 
 }