[CallSiteSplitting] Only record conditions up to the IDom(call site).

[fhahn]

Summary

We can stop recording conditions once we reached the immediate dominator
for the block containing the call site. Conditions in predecessors of the
that node will be the same for all paths to the call site and splitting
is not beneficial.

This patch makes CallSiteSplitting dependent on the DT anlysis. because
the immediate dominators seem to be the easiest way of finding the node
to stop at.

I had to update some exiting tests, because they were checking for
conditions that were true/false on all paths to the call site.

[fhahn]

Update test/Other/new-pm-lto-defaults.ll to account for running the dominator tree analysis earlier.

[fhahn]

ping

[junbuml]

test/Transforms/CallSiteSplitting/callsite-split-or-phi.ll

46 ↗

(On Diff #138946)

We may want to keep this test as it is. With this patch, the call sites split will take %a, instead of null. null value might be propagated to the callsite later in the pipeline, but there is no reason not to pass the known null value early in the pipeline. If the callee has early exit condition with null check. Inliner may have better opportunity to get this callee inlined by passing null.

[fhahn]

test/Transforms/CallSiteSplitting/callsite-split-or-phi.ll

46 ↗

(On Diff #138946)

Ah yes, if we split anyways, we could also propagate other known constraints.

[junbuml]

test/Transforms/CallSiteSplitting/callsite-split-or-phi.ll

46 ↗

(On Diff #138946)

This may show that inliner fail to inline the callee with this change.

define i32 @test_eq_eq_eq(i32* %a, i32 %v, i32 %p) {
Header:
  %tobool1 = icmp eq i32* %a, null
  br i1 %tobool1, label %Header2, label %End

Header2:
  %tobool2 = icmp eq i32 %p, 10
  call void @dummy()
  br i1 %tobool2, label %Tail, label %TBB

TBB:
  %cmp = icmp eq i32 %v, 1
  call void @dummy()
  br i1 %cmp, label %Tail, label %End

Tail:
  %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
  ret i32 %r

End:
  ret i32 %v
}


define i32 @callee(i32* %a, i32 %v, i32 %p) {
entry:
  %c = icmp eq i32* %a, null
  br i1 %c, label %BB1, label %BB2

BB1:
  ret i32 0

BB2:
  call void @dummy2(i32 %v, i32 %p)
  call void @dummy2(i32 %v, i32 %p)
  call void @dummy2(i32 %v, i32 %p)
  call void @dummy2(i32 %v, i32 %p)
  call void @dummy2(i32 %v, i32 %p)
  call void @dummy2(i32 %v, i32 %p)
  call void @dummy2(i32 %v, i32 %p)
  call void @dummy2(i32 %v, i32 %p)
  call void @dummy2(i32 %v, i32 %p)
  call void @dummy2(i32 %v, i32 %p)
  call void @dummy2(i32 %v, i32 %p)
  call void @dummy2(i32 %v, i32 %p)
  call void @dummy2(i32 %v, i32 %p)
  call void @dummy2(i32 %v, i32 %p)
  br label %End

End:
  ret i32 %p
}

declare void @dummy()
declare void @dummy2(i32, i32)

[fhahn]

I moved code around a bit and updated it to explicitly gather common conditions starting from IDom(CS). While I do think that we ideally handle that somewhere else before inlining, it is quite easy to do it here for now.

[junbuml]

Thanks for doing this. Now, you intended it to be a NFC, right? If then, it will be good to keep the original test cases as it is. Adding more tests is definitely good.

lib/Transforms/Scalar/CallSiteSplitting.cpp

468–479 ↗

(On Diff #140212)

I think we should move this to line 461. Otherwise, we wont be able to handle the case where a known value is not detected in immediate predecessors, but there is a known value after IDom.

Looks like test_cond_no_effect() shows the case.

test/Transforms/CallSiteSplitting/callsite-split-or-phi.ll

133 ↗

(On Diff #140212)

We should keep this test to check that nonnull is passed to both call-sites.

133 ↗

(On Diff #140212)

We can add this test, but I don't think there is any change in this test with/without this patch.

185 ↗

(On Diff #140212)

We should keep this test to check that nonnull is passed to both call-sites.

[junbuml]

lib/Transforms/Scalar/CallSiteSplitting.cpp

468–479 ↗

(On Diff #140212)

In this case (test_cond_no_effect), we should just pass the known value without splitting. Looks like I tried thing similar before in https://reviews.llvm.org/D41782.

[fhahn]

lib/Transforms/Scalar/CallSiteSplitting.cpp

468–479 ↗

(On Diff #140212)

As this patch is at the moment, it is not a NFC, as it prevents splitting in case there are no suitable conditions along any path between the IDom and the call site.

In this case (test_cond_no_effect), we should just pass the known value without splitting. Looks like I tried thing similar before in https://reviews.llvm.org/D41782.

I just thought the same thing :) With my change, it should be quite straight forward to handle that case. But I would prefer to do that in a different patch

[junbuml]

Sounds good to me.

[fhahn]

I thought

lib/Transforms/Scalar/CallSiteSplitting.cpp

468–479 ↗

(On Diff #140212)

In this case (test_cond_no_effect), we should just pass the known value without splitting. Looks like I tried thing similar before in https://reviews.llvm.org/D41782.

I thought a bit more about how to best handle propagating common facts that do not require splitting. I do not think we can do it properly here without making things to complicated. I've shared a WIP patch that is a first step towards enabling IPSCCP to propagate facts from compare instructions : D45330

[fhahn]

Resurrecting the patch. The cases we loose (propagating %a == null in test_cond_no_effect) is now handled by ipsccp, which is a better place IMO. @junbuml what do you think?

This patch makes CallSiteSplitting stop backtracking once it is not necessary any more and avoid splitting unnecessarily.

[junbuml]

Thanks for revisiting this.
LGTM.

lib/Transforms/Scalar/CallSiteSplitting.cpp

159–160 ↗

(On Diff #173155)

It seems better to place "To != StopAt" first :

while (To != StopAt && !Visited.count(From->getSinglePredecessor()) &&
         (From = From->getSinglePredecessor()))

llvm/trunk/lib/Transforms/Scalar/CallSiteSplitting.cpp

if (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)
     if (isCondRelevantToAnyCallArgument(Cmp, CS))
       Conditions.push_back({Cmp, From->getTerminator()->getSuccessor(0) == To
                                      ? Pred
                                      : Cmp->getInversePredicate()});
 }
 
 /// Record ICmp conditions relevant to any argument in CS following Pred's
 /// single predecessors. If there are conflicting conditions along a path, like
-/// x == 1 and x == 0, the first condition will be used.
+/// x == 1 and x == 0, the first condition will be used. We stop once we reach
+/// an edge to StopAt.
 static void recordConditions(CallSite CS, BasicBlock *Pred,
-                             ConditionsTy &Conditions) {
-  recordCondition(CS, Pred, CS.getInstruction()->getParent(), Conditions);
+                             ConditionsTy &Conditions, BasicBlock *StopAt) {
   BasicBlock *From = Pred;
   BasicBlock *To = Pred;
   SmallPtrSet<BasicBlock *, 4> Visited;
-  while (!Visited.count(From->getSinglePredecessor()) &&
+  while (To != StopAt && !Visited.count(From->getSinglePredecessor()) &&
          (From = From->getSinglePredecessor())) {
     recordCondition(CS, From, To, Conditions);
     Visited.insert(From);
     To = From;
   }
 }
 
 static void addConditions(CallSite CS, const ConditionsTy &Conditions) {

 ///    %p = phi i1 [%ca1, %Tail-split1],[%ca2, %Tail-split2]
 ///
 /// Note that in case any arguments at the call-site are constrained by its
 /// predecessors, new call-sites with more constrained arguments will be
 /// created in createCallSitesOnPredicatedArgument().
 static void splitCallSite(
     CallSite CS,
     const SmallVectorImpl<std::pair<BasicBlock *, ConditionsTy>> &Preds,
-    DominatorTree *DT) {
+    DominatorTree &DT) {
   Instruction *Instr = CS.getInstruction();
   BasicBlock *TailBB = Instr->getParent();
   bool IsMustTailCall = CS.isMustTailCall();
 
   PHINode *CallPN = nullptr;
 
   // `musttail` calls must be followed by optional `bitcast`, and `ret`. The
   // split blocks will be terminated right after that so there're no users for
   // this phi in a `TailBB`.
   if (!IsMustTailCall && !Instr->use_empty()) {
     CallPN = PHINode::Create(Instr->getType(), Preds.size(), "phi.call");
     CallPN->setDebugLoc(Instr->getDebugLoc());
   }
 
   LLVM_DEBUG(dbgs() << "split call-site : " << *Instr << " into \n");
 
   assert(Preds.size() == 2 && "The ValueToValueMaps array has size 2.");
   // ValueToValueMapTy is neither copy nor moveable, so we use a simple array
   // here.
   ValueToValueMapTy ValueToValueMaps[2];
   for (unsigned i = 0; i < Preds.size(); i++) {
     BasicBlock *PredBB = Preds[i].first;
     BasicBlock *SplitBlock = DuplicateInstructionsInSplitBetween(
         TailBB, PredBB, &*std::next(Instr->getIterator()), ValueToValueMaps[i],
-        DT);
+        &DT);
     assert(SplitBlock && "Unexpected new basic block split.");
 
     Instruction *NewCI =
         &*std::prev(SplitBlock->getTerminator()->getIterator());
     CallSite NewCS(NewCI);
     addConditions(NewCS, Preds[i].second);
 
     // Handle PHIs used as arguments in the call-site.
if (PHINode *PN = dyn_cast<PHINode>(&BI)) {
             return true;
         }
     }
     break;
   }
   return false;
 }
 
-static bool tryToSplitOnPHIPredicatedArgument(CallSite CS, DominatorTree *DT) {
+static bool tryToSplitOnPHIPredicatedArgument(CallSite CS, DominatorTree &DT) {
   if (!isPredicatedOnPHI(CS))
     return false;
 
   auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
   SmallVector<std::pair<BasicBlock *, ConditionsTy>, 2> PredsCS = {
       {Preds[0], {}}, {Preds[1], {}}};
   splitCallSite(CS, PredsCS, DT);
   return true;
 }
 
-static bool tryToSplitOnPredicatedArgument(CallSite CS, DominatorTree *DT) {
+static bool tryToSplitOnPredicatedArgument(CallSite CS, DominatorTree &DT) {
   auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
   if (Preds[0] == Preds[1])
     return false;
 
+  // We can stop recording conditions once we reached the immediate dominator
+  // for the block containing the call site. Conditions in predecessors of the
+  // that node will be the same for all paths to the call site and splitting
+  // is not beneficial.
+  auto *CSDTNode = DT.getNode(CS.getInstruction()->getParent());
+  BasicBlock *StopAt = CSDTNode ? CSDTNode->getIDom()->getBlock() : nullptr;
+
   SmallVector<std::pair<BasicBlock *, ConditionsTy>, 2> PredsCS;
   for (auto *Pred : make_range(Preds.rbegin(), Preds.rend())) {
     ConditionsTy Conditions;
-    recordConditions(CS, Pred, Conditions);
+    // Record condition on edge BB(CS) <- Pred
+    recordCondition(CS, Pred, CS.getInstruction()->getParent(), Conditions);
+    // Record conditions followng Pred's single predecessors.
+    recordConditions(CS, Pred, Conditions, StopAt);
     PredsCS.push_back({Pred, Conditions});
   }
 
   if (all_of(PredsCS, [](const std::pair<BasicBlock *, ConditionsTy> &P) {
         return P.second.empty();
       }))
     return false;
 
+  // Record common conditions starting from StopAt. Those conditions hold for
+  // all paths to CS. Adding them gives the inliner a better chance at inlining
+  // CS.
+  ConditionsTy CommonConditions;
+  if (StopAt)
+    recordConditions(CS, StopAt, CommonConditions, nullptr);
+  if (!CommonConditions.empty())
+    for (auto &Pred : PredsCS) {
+      Pred.second.insert(Pred.second.end(), CommonConditions.begin(),
+                         CommonConditions.end());
+    }
+
   splitCallSite(CS, PredsCS, DT);
   return true;
 }
 
 static bool tryToSplitCallSite(CallSite CS, TargetTransformInfo &TTI,
-                               DominatorTree *DT) {
+                               DominatorTree &DT) {
   if (!CS.arg_size() || !canSplitCallSite(CS, TTI))
     return false;
   return tryToSplitOnPredicatedArgument(CS, DT) ||
          tryToSplitOnPHIPredicatedArgument(CS, DT);
 }
 
 static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI,
-                                TargetTransformInfo &TTI, DominatorTree *DT) {
+                                TargetTransformInfo &TTI, DominatorTree &DT) {
   bool Changed = false;
   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE;) {
     BasicBlock &BB = *BI++;
     auto II = BB.getFirstNonPHIOrDbg()->getIterator();
     auto IE = BB.getTerminator()->getIterator();
     // Iterate until we reach the terminator instruction. tryToSplitCallSite
     // can replace BB's terminator in case BB is a successor of itself. In that
     // case, IE will be invalidated and we also have to check the current
struct CallSiteSplittingLegacyPass : public FunctionPass {
   static char ID;
   CallSiteSplittingLegacyPass() : FunctionPass(ID) {
     initializeCallSiteSplittingLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
+    AU.addRequired<DominatorTreeWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
     FunctionPass::getAnalysisUsage(AU);
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
 
     auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
     auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
-    auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
-    return doCallSiteSplitting(F, TLI, TTI,
-                               DTWP ? &DTWP->getDomTree() : nullptr);
+    auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    return doCallSiteSplitting(F, TLI, TTI, DT);
   }
 };
 } // namespace
 
 char CallSiteSplittingLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(CallSiteSplittingLegacyPass, "callsite-splitting",
                       "Call-site splitting", false, false)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_END(CallSiteSplittingLegacyPass, "callsite-splitting",
                     "Call-site splitting", false, false)
 FunctionPass *llvm::createCallSiteSplittingPass() {
   return new CallSiteSplittingLegacyPass();
 }
 
 PreservedAnalyses CallSiteSplittingPass::run(Function &F,
                                              FunctionAnalysisManager &AM) {
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
-  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
+  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 
   if (!doCallSiteSplitting(F, TLI, TTI, DT))
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   return PA;
 }

llvm/trunk/test/Other/new-pm-lto-defaults.ll

 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O2-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O2-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}Module
 ; CHECK-O2-NEXT: Running analysis: PassInstrumentationAnalysis
 ; CHECK-O2-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O2-NEXT: Running pass: CallSiteSplittingPass on foo
 ; CHECK-O2-NEXT: Running analysis: TargetLibraryAnalysis on foo
 ; CHECK-O2-NEXT: Running analysis: TargetIRAnalysis on foo
+; CHECK-O2-NEXT: Running analysis: DominatorTreeAnalysis on foo
 ; CHECK-O2-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-O2-NEXT: PGOIndirectCallPromotion
 ; CHECK-O2-NEXT: Running analysis: ProfileSummaryAnalysis
 ; CHECK-O2-NEXT: Running analysis: OptimizationRemarkEmitterAnalysis
 ; CHECK-O2-NEXT: Running pass: IPSCCPPass
-; CHECK-O2-DAG: Running analysis: AssumptionAnalysis on foo
-; CHECK-O2-DAG: Running analysis: DominatorTreeAnalysis on foo
+; CHECK-O2-NEXT: Running analysis: AssumptionAnalysis on foo
 ; CHECK-O2-NEXT: Running pass: CalledValuePropagationPass
 ; CHECK-O-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor<{{.*}}PostOrderFunctionAttrsPass>
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}SCC
 ; CHECK-O1-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}Function
 ; CHECK-O-NEXT: Running analysis: LazyCallGraphAnalysis
 ; CHECK-O-NEXT: Running analysis: FunctionAnalysisManagerCGSCCProxy
 ; CHECK-O-NEXT: Running analysis: PassInstrumentationAnalysis
 ; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}LazyCallGraph{{.*}}>

llvm/trunk/test/Other/opt-O3-pipeline.ll

 ; CHECK:      Type-Based Alias Analysis
 ; CHECK-NEXT: Scoped NoAlias Alias Analysis
 ; CHECK-NEXT: Assumption Cache Tracker
 ; CHECK-NEXT: Profile summary info
 ; CHECK-NEXT:   ModulePass Manager
 ; CHECK-NEXT:     Force set function attributes
 ; CHECK-NEXT:     Infer set function attributes
 ; CHECK-NEXT:     FunctionPass Manager
+; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Call-site splitting
 ; CHECK-NEXT:     Interprocedural Sparse Conditional Constant Propagation
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Called Value Propagation
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction

llvm/trunk/test/Transforms/CallSiteSplitting/callsite-split-or-phi.ll

 End:
   ret i32 %v
 }
 
 ;CHECK-LABEL: @test_ne_eq_ne
 ;CHECK-LABEL: Header2.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 10)
 ;CHECK-LABEL: TBB.split:
-;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 %p)
+;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* %a, i32 %v, i32 %p)
 ;CHECK-LABEL: Tail
 ;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header2.split ], [ %[[CALL2]], %TBB.split ]
 ;CHECK: ret i32 %[[MERGED]]
 define i32 @test_ne_eq_ne(i32* %a, i32 %v, i32 %p) {
 Header:
   %tobool1 = icmp ne i32* %a, null
-  br i1 %tobool1, label %Header2, label %End
+  br i1 %tobool1, label %Header2, label %TBB
 
 Header2:
   %tobool2 = icmp eq i32 %p, 10
   br i1 %tobool2, label %Tail, label %TBB
 
 TBB:
   %cmp = icmp ne i32 %v, 1
   br i1 %cmp, label %Tail, label %End

 End:
   ret i32 %v
 }
 
 ;CHECK-LABEL: @test_ne_ne_ne_constrain_same_pointer_arg
 ;CHECK-LABEL: Header2.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 %p)
 ;CHECK-LABEL: TBB.split:
-;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 %p)
+;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* %a, i32 %v, i32 %p)
 ;CHECK-LABEL: Tail
 ;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header2.split ], [ %[[CALL2]], %TBB.split ]
 ;CHECK: ret i32 %[[MERGED]]
 define i32 @test_ne_ne_ne_constrain_same_pointer_arg(i32* %a, i32 %v, i32 %p, i32* %a2, i32* %a3) {
 Header:
   %tobool1 = icmp ne i32* %a, null
-  br i1 %tobool1, label %Header2, label %End
+  br i1 %tobool1, label %Header2, label %TBB
 
 Header2:
   %tobool2 = icmp ne i32* %a, %a2
   br i1 %tobool2, label %Tail, label %TBB
 
 TBB:
   %cmp = icmp ne i32* %a, %a3
   br i1 %cmp, label %Tail, label %End

 End:
   ret i32 %v
 }
 
 ;CHECK-LABEL: @test_eq_eq_eq_untaken
 ;CHECK-LABEL: Header2.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 10)
 ;CHECK-LABEL: TBB.split:
-;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* nonnull %a, i32 1, i32 %p)
+;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* %a, i32 1, i32 %p)
 ;CHECK-LABEL: Tail
 ;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header2.split ], [ %[[CALL2]], %TBB.split ]
 ;CHECK: ret i32 %[[MERGED]]
 define i32 @test_eq_eq_eq_untaken(i32* %a, i32 %v, i32 %p) {
 Header:
   %tobool1 = icmp eq i32* %a, null
-  br i1 %tobool1, label %End, label %Header2
+  br i1 %tobool1, label %TBB, label %Header2
 
 Header2:
   %tobool2 = icmp eq i32 %p, 10
   br i1 %tobool2, label %Tail, label %TBB
 
 TBB:
   %cmp = icmp eq i32 %v, 1
   br i1 %cmp, label %Tail, label %End

 End:
   ret i32 %v
 }
 
 ;CHECK-LABEL: @test_ne_eq_ne_untaken
 ;CHECK-LABEL: Header2.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* null, i32 %v, i32 10)
 ;CHECK-LABEL: TBB.split:
-;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* null, i32 %v, i32 %p)
+;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* %a, i32 %v, i32 %p)
 ;CHECK-LABEL: Tail
 ;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header2.split ], [ %[[CALL2]], %TBB.split ]
 ;CHECK: ret i32 %[[MERGED]]
 define i32 @test_ne_eq_ne_untaken(i32* %a, i32 %v, i32 %p) {
 Header:
   %tobool1 = icmp ne i32* %a, null
-  br i1 %tobool1, label %End, label %Header2
+  br i1 %tobool1, label %TBB, label %Header2
 
 Header2:
   %tobool2 = icmp eq i32 %p, 10
   br i1 %tobool2, label %Tail, label %TBB
 
 TBB:
   %cmp = icmp ne i32 %v, 1
   br i1 %cmp, label %Tail, label %End
Tail:
   %p = phi i32[1,%Header], [2, %TBB]
   %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
   ret i32 %r
 
 End:
   ret i32 %v
 }
 
+;CHECK-LABEL: @test_cond_no_effect
+;CHECK-NOT: Header.split:
+;CHECK-NOT: TBB.split:
+;CHECK-LABEL: Tail:
+;CHECK: %r = call i32 @callee(i32* %a, i32 %v, i32 0)
+;CHECK: ret i32 %r
+define i32 @test_cond_no_effect(i32* %a, i32 %v) {
+Entry:
+  %tobool1 = icmp eq i32* %a, null
+  br i1 %tobool1, label %Header, label %End
+
+Header:
+  br i1 undef, label %Tail, label %TBB
+
+TBB:
+  br i1 undef, label %Tail, label %End
+
+Tail:
+  %r = call i32 @callee(i32* %a, i32 %v, i32 0)
+  ret i32 %r
+
+End:
+  ret i32 %v
+}
+
 ;CHECK-LABEL: @test_unreachable
 ;CHECK-LABEL: Header.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* %a, i32 %v, i32 10)
 ;CHECK-LABEL: TBB.split:
 ;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* %a, i32 1, i32 %p)
 ;CHECK-LABEL: Tail
 ;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB.split ]
 ;CHECK: ret i32 %[[MERGED]]