[CallSiteSplitting] Support splitting of blocks with instrs before call.

[fhahn]

Summary

For basic blocks with instructions between the beginning of the block
and a call we have to duplicate the instructions before the call in all
split blocks and add PHI nodes for uses of the duplicated instructions
after the call.

Currently, the threshold for the number of instructions before a call
is quite low, to keep the impact on binary size low.

[fhahn]

Added test case test/Transforms/CallSiteSplitting/callsite-instructions-before-call.ll

[fhahn]

Rebased after committing rL322599

[fhahn]

ping

[junbuml]

Do you have any result for performance and size ?

lib/Transforms/Scalar/CallSiteSplitting.cpp

80

Why don't we make it a command line option? It will be good to run a correctness test without being limited in the current default value.

315

CurrentI might point a new PHI created below (line 309) during the iteration as it iterate reversely.

test/Transforms/CallSiteSplitting/callsite-instructions-before-call.ll

105

We need more test to see if PHIs are created properly for cloned instructions used after callsite split.

[fhahn]

Update code to insert new PHIs at the beginning of TailBB and delete instructions up to the original first instruction. This way, remove unnecessary existing PHI nodes, while not deleting newly created ones.

I hope I can post benchmark numbers with the new version of the patch tomorrow.

[fhahn]

I've run spec2006, spec2000 and the test-suite on Cortex-A57. Slight improvement in the geomean speedup, no perf regressions, not size regressions.

[fhahn]

ping

[junbuml]

Overall LGTM, but I want someone else also look at this.

lib/Transforms/Scalar/CallSiteSplitting.cpp

303

Isn't it possible to hold space for ValueToValueMapTy for each predecessor and pass its reference to DuplicateInstructionsInSplitBetween.

For example, as we only support 2 predecessors for now, we can define Remaps as a fixed size array which has ValueToValueMapTy as its element, and then we can pass the reference of each array element to DuplicateInstructionsInSplitBetween for each predecessor.

317

Instead of '2', it will be good to use the number of pred of TailBB. Or at least we need assert before using '2' directly here.

test/Transforms/CallSiteSplitting/callsite-instructions-before-call.ll

159

I think it should be %i, instead of %0. Or did you intend [[V1]] ?

[fhahn]

Thanks for having a look! I've updated the patch to use a fixed size array for ValueToValueMapTys, used Preds.size() when creating the PHI node and updated the remaining tests.

[fhahn]

lib/Transforms/Scalar/CallSiteSplitting.cpp

303

I've changed it to use a fixed size array. I am not entirely happy with it, but it's definitely nicer than the duplication :)

[junbuml]

lib/Transforms/Scalar/CallSiteSplitting.cpp

189–201

Here we assume that the duplication costs of instructions are all same. However, I believe this assumption is not always true because each instruction here will end up differently after lowering. For example, if there is another call before the call we are trying to split, the cost for such call should be more expensive than other simple instructions (e.g., add or trunc ). If such call duplicated is inlined, the code size could be significantly impacted. I think we should consider using getUserCost(), instead of number of instructions ?

320

If CurrnetI is PHI, "Mapping[CurrentI])->getParent()" may not point the new SplitBlock becasue DuplicateInstructionsInSplitBetween map a PHI with its original incoming value. Isn't it okay to skip doing this if CurrnetI is PHI?

Based on your test_remove_unused_phi(), we should add a test case something like this :

define void @test_no_remove_used_phi(i32* %ptrarg, i32* %ptrarg2, i32 %i, i32 %i2) {
Header:
  %l1 = load i32, i32* undef, align 16
  %tobool = icmp ne i32* %ptrarg, null
  br i1 %tobool, label %TBB, label %CallSite

TBB:                                    ; preds = %Header
  %arrayidx = getelementptr inbounds i32, i32* %ptrarg, i64 42
  %0 = load i32, i32* %arrayidx, align 4
  %l2 = load i32, i32* undef, align 16
  %tobool1 = icmp ne i32 %0, 0
  br i1 %tobool1, label %CallSite, label %End

CallSite:                                          ; preds = %TBB, %Header
  %l = phi i32 [ %l1, %Header ], [ %l2, %TBB ]
  call void @bar(i32* %ptrarg, i32 %l)
  call void @bari(i32 %l)                   <------------ %l is used here, so it will hit the case I mentioned.
  br label %End

End:                                           ; preds = %CallSite, %TBB
  ret void
}

[fhahn]

Thanks Jun!
Update the patch to use getInstructionCost(i, TCK_CodeSize) to decide whether it is worth to perform call site splitting. Also avoid creating PHI nodes for existing PHI nodes unnecessarily.

[fhahn]

lib/Transforms/Scalar/CallSiteSplitting.cpp

189–201

I've updated the code to use getInstructionCost with TCK_CodeSize. Per default it uses getUserCost, which seems OK, although in some cases, the cost it returns might be too high for our case (e.g. sdiv has a high cost although it might be lowered to a single instruction)

320

Thanks, there is indeed no need to re-create the PHI node there. I've added your test case. The incoming basic blocks in the PHI node are updated to use the split blocks. I assume this is done when splitting. Not sure if it would be better to use the original basic blocks. But I think that should be follow up patch if we want to change it ;)

[junbuml]

lib/Transforms/Scalar/CallSiteSplitting.cpp

85

Considering that TCC_Basic is 1, don't you think 50 is too aggressive? For me, the conservative enough default should be TCC_Expensive.

[junbuml]

I've updated the code to use getInstructionCost with TCK_CodeSize. Per default it uses getUserCost, which seems OK, although in some cases,
the cost it returns might be too high for our case (e.g. sdiv has a high cost although it might be lowered to a single instruction)

If getUserCost is supposed to represent only the code size (I believe so), then we may need to introduce a new target hook to handle sdiv properly in getOperationCost(). @hfinkel might have better idea about it.

[fhahn]

Fix default threshold.

[fhahn]

If getUserCost is supposed to represent only the code size (I believe so), then we may need to introduce a new target hook to handle sdiv properly in getOperationCost(). @hfinkel might have better idea about it.

I am not entirely sure, but it looks like for most instructions, getUserCost delegates to getOperationCost, which per default marks sdiv & co as expensive. In any case, the patch uses

TTI.getInstructionCost(&InstBeforeCall,
                                   TargetTransformInfo::TCK_CodeSize);

so in case the code size cost becomes more accurate, we should pick it up.

lib/Transforms/Scalar/CallSiteSplitting.cpp

85

Yeah, that was left over from testing, sorry about that!

[junbuml]

LGTM, but I may want to hold it for sometime to let other reviewers take a chance to look at this as well.

lib/Transforms/Scalar/CallSiteSplitting.cpp

190–201

when there the CodeSize -> when the CodeSize

[fhahn]

Thanks @junbuml ! I'll wait with committing until the middle of next week or so

[fhahn]

Reverted again in rL325009, as memsan was not happy with the array of the ValueToValueMaps. I'll look into how to resolve this.

lib/Transforms/Scalar/CallSiteSplitting.cpp

 //   Tail:
 //    %p = phi i32 [ 0, %Tail-split0 ], [ 1, %Tail-split1 ]
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/CallSiteSplitting.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/Local.h"
 
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "callsite-splitting"
 
 STATISTIC(NumCallSiteSplit, "Number of call-site split");
 
+/// Only allow instructions before a call, if their CodeSize cost is below
+/// DuplicationThreshold. Those instructions need to be duplicated in all
+/// split blocks.
+static cl::opt<unsigned>
+    DuplicationThreshold("callsite-splitting-duplication-threshold", cl::Hidden,
+                         cl::desc("Only allow instructions before a call, if "
+                                  "their cost is below DuplicationThreshold"),
+                         cl::init(50));
+
 static void addNonNullAttribute(CallSite CS, Value *Op) {
   unsigned ArgNo = 0;
   for (auto &I : CS.args()) {
     if (&*I == Op)
       CS.addParamAttr(ArgNo, Attribute::NonNull);
     ++ArgNo;
   }
 }

 }
 
 static SmallVector<BasicBlock *, 2> getTwoPredecessors(BasicBlock *BB) {
   SmallVector<BasicBlock *, 2> Preds(predecessors((BB)));
   assert(Preds.size() == 2 && "Expected exactly 2 predecessors!");
   return Preds;
 }
 
-static bool canSplitCallSite(CallSite CS) {
+static bool canSplitCallSite(CallSite CS, TargetTransformInfo &TTI) {
   // FIXME: As of now we handle only CallInst. InvokeInst could be handled
   // without too much effort.
   Instruction *Instr = CS.getInstruction();
   if (!isa<CallInst>(Instr))
     return false;
 
-  // Allow splitting a call-site only when there is no instruction before the
-  // call-site in the basic block. Based on this constraint, we only clone the
-  // call instruction, and we do not move a call-site across any other
-  // instruction.
   BasicBlock *CallSiteBB = Instr->getParent();
-  if (Instr != CallSiteBB->getFirstNonPHIOrDbg())
+  // Allow splitting a call-site only when there the CodeSize cost of the
+  // instructions before the call is less then DuplicationThreshold. The
+  // instructions before the call will be duplicated in the split blocks and
+  // corresponding uses will be updated.
+  unsigned Cost = 0;
+  for (auto &InstBeforeCall :
+       llvm::make_range(CallSiteBB->begin(), Instr->getIterator())) {
+    Cost += TTI.getInstructionCost(&InstBeforeCall,
+                                   TargetTransformInfo::TCK_CodeSize);
+    if (Cost >= DuplicationThreshold)
       return false;
+  }
 
   // Need 2 predecessors and cannot split an edge from an IndirectBrInst.
   SmallVector<BasicBlock *, 2> Preds(predecessors(CallSiteBB));
   if (Preds.size() != 2 || isa<IndirectBrInst>(Preds[0]->getTerminator()) ||
       isa<IndirectBrInst>(Preds[1]->getTerminator()))
     return false;
 
   return CallSiteBB->canSplitPredecessors();
static void splitCallSite(
   Instruction *Instr = CS.getInstruction();
   BasicBlock *TailBB = Instr->getParent();
 
   PHINode *CallPN = nullptr;
   if (Instr->getNumUses())
     CallPN = PHINode::Create(Instr->getType(), Preds.size(), "phi.call");
 
   DEBUG(dbgs() << "split call-site : " << *Instr << " into \n");
-  for (const auto &P : Preds) {
-    BasicBlock *PredBB = P.first;
-    BasicBlock *SplitBlock =
-        SplitBlockPredecessors(TailBB, PredBB, ".predBB.split");
+
+  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++) {
+    new (&ValueToValueMaps[i]) ValueToValueMapTy;
+    BasicBlock *PredBB = Preds[i].first;
+    BasicBlock *SplitBlock = DuplicateInstructionsInSplitBetween(
+        TailBB, PredBB, &*std::next(Instr->getIterator()), ValueToValueMaps[i]);
     assert(SplitBlock && "Unexpected new basic block split.");
 
-    Instruction *NewCI = Instr->clone();
+    Instruction *NewCI =
+        &*std::prev(SplitBlock->getTerminator()->getIterator());
     CallSite NewCS(NewCI);
-    addConditions(NewCS, P.second);
-    NewCI->insertBefore(&*SplitBlock->getFirstInsertionPt());
+    addConditions(NewCS, Preds[i].second);
 
     // Handle PHIs used as arguments in the call-site.
     for (PHINode &PN : TailBB->phis()) {
       unsigned ArgNo = 0;
       for (auto &CI : CS.args()) {
         if (&*CI == &PN) {
           NewCS.setArgument(ArgNo, PN.getIncomingValueForBlock(SplitBlock));
         }
         ++ArgNo;
       }
     }
     DEBUG(dbgs() << "    " << *NewCI << " in " << SplitBlock->getName()
                  << "\n");
     if (CallPN)
       CallPN->addIncoming(NewCI, SplitBlock);
   }
 
+  auto OriginalBegin = TailBB->begin();
   // Replace users of the original call with a PHI mering call-sites split.
   if (CallPN) {
-    CallPN->insertBefore(TailBB->getFirstNonPHI());
+    CallPN->insertBefore(&*OriginalBegin);
     Instr->replaceAllUsesWith(CallPN);
   }
 
-  Instr->eraseFromParent();
+  // Remove instructions moved to split blocks from TailBB, from the duplicated
+  // call instruction to the beginning of the basic block. If an instruction
+  // has any uses, add a new PHI node to combine the values coming from the
+  // split blocks. The new PHI nodes are placed before the first original
+  // instruction, so we do not end up deleting them. By using reverse-order, we
+  // do not introduce unnecessary PHI nodes for def-use chains from the call
+  // instruction to the beginning of the block.
+  auto I = Instr->getReverseIterator();
+  while (I != TailBB->rend()) {
+    Instruction *CurrentI = &*I++;
+    if (!CurrentI->use_empty()) {
+      // If an existing PHI has users after the call, there is no need to create
+      // a new one.
+      if (isa<PHINode>(CurrentI))
+        continue;
+      PHINode *NewPN = PHINode::Create(CurrentI->getType(), Preds.size());
+      for (auto &Mapping : ValueToValueMaps)
+        NewPN->addIncoming(Mapping[CurrentI],
+                           cast<Instruction>(Mapping[CurrentI])->getParent());
+      NewPN->insertBefore(&*TailBB->begin());
+      CurrentI->replaceAllUsesWith(NewPN);
+    }
+    CurrentI->eraseFromParent();
+    // We are done once we handled the first original instruction in TailBB.
+    if (CurrentI == &*OriginalBegin)
+      break;
+  }
   NumCallSiteSplit++;
 }
 
 // Return true if the call-site has an argument which is a PHI with only
 // constant incoming values.
 static bool isPredicatedOnPHI(CallSite CS) {
   Instruction *Instr = CS.getInstruction();
   BasicBlock *Parent = Instr->getParent();
if (std::all_of(PredsCS.begin(), PredsCS.end(),
                     return P.second.empty();
                   }))
     return false;
 
   splitCallSite(CS, PredsCS);
   return true;
 }
 
-static bool tryToSplitCallSite(CallSite CS) {
-  if (!CS.arg_size() || !canSplitCallSite(CS))
+static bool tryToSplitCallSite(CallSite CS, TargetTransformInfo &TTI) {
+  if (!CS.arg_size() || !canSplitCallSite(CS, TTI))
     return false;
   return tryToSplitOnPredicatedArgument(CS) ||
          tryToSplitOnPHIPredicatedArgument(CS);
 }
 
-static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI) {
+static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI,
+                                TargetTransformInfo &TTI) {
   bool Changed = false;
   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE;) {
     BasicBlock &BB = *BI++;
     for (BasicBlock::iterator II = BB.begin(), IE = BB.end(); II != IE;) {
       Instruction *I = &*II++;
       CallSite CS(cast<Value>(I));
       if (!CS || isa<IntrinsicInst>(I) || isInstructionTriviallyDead(I, &TLI))
         continue;
 
       Function *Callee = CS.getCalledFunction();
       if (!Callee || Callee->isDeclaration())
         continue;
-      Changed |= tryToSplitCallSite(CS);
+      Changed |= tryToSplitCallSite(CS, TTI);
     }
   }
   return Changed;
 }
 
 namespace {
 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>();
     FunctionPass::getAnalysisUsage(AU);
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
 
     auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
-    return doCallSiteSplitting(F, TLI);
+    auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
+    return doCallSiteSplitting(F, TLI, TTI);
   }
 };
 } // 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_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);
 
-  if (!doCallSiteSplitting(F, TLI))
+  if (!doCallSiteSplitting(F, TLI, TTI))
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   return PA;
 }

test/Transforms/CallSiteSplitting/callsite-instructions-before-call.ll

+; RUN: opt -S -callsite-splitting < %s | FileCheck --check-prefix=CHECK %s
+; RUN: opt -S -callsite-splitting -callsite-splitting-duplication-threshold=0 < %s | FileCheck --check-prefix=NODUP %s
+
+; Instructions before a call that will be pushed to its predecessors
+; with uses after the callsite, must be patched up as PHI nodes in
+; the join block.
+define i32* @test_split_branch_phi(i32* %ptrarg, i32 %i) {
+Header:
+  %tobool = icmp ne i32* %ptrarg, null
+  br i1 %tobool, label %TBB, label %CallSite
+
+TBB:                                    ; preds = %Header
+  %arrayidx = getelementptr inbounds i32, i32* %ptrarg, i64 42
+  %0 = load i32, i32* %arrayidx, align 4
+  %tobool1 = icmp ne i32 %0, 0
+  br i1 %tobool1, label %CallSite, label %End
+
+CallSite:                                          ; preds = %TBB, %Header
+  %somepointer = getelementptr i32, i32* %ptrarg, i64 18
+  call void @bar(i32* %ptrarg, i32 %i)
+  br label %End
+
+End:                                           ; preds = %CallSite, %TBB
+  %somepointerphi = phi i32* [ %somepointer, %CallSite ], [ null, %TBB ]
+  ret i32* %somepointerphi
+}
+; NODUP-LABEL: test_split_branch_phi
+; NODUP-NOT: split
+; CHECK-LABEL: Header.split
+; CHECK: %[[V1:somepointer[0-9]+]] = getelementptr i32, i32* %ptrarg, i64 18
+; CHECK: call void @bar(i32* null, i32 %i)
+; CHECK: br label %CallSite
+; CHECK-LABEL: TBB.split:
+; CHECK: %[[V2:somepointer[0-9]+]] = getelementptr i32, i32* %ptrarg, i64 18
+; CHECK: call void @bar(i32* nonnull %ptrarg, i32 %i)
+; CHECK: br label %CallSite
+; CHECK: CallSite:
+; CHECK: phi i32* [ %[[V1]], %Header.split ], [ %[[V2]], %TBB.split ]
+
+
+define void @split_branch_no_extra_phi(i32* %ptrarg, i32 %i) {
+Header:
+  %tobool = icmp ne i32* %ptrarg, null
+  br i1 %tobool, label %TBB, label %CallSite
+
+TBB:                                    ; preds = %Header
+  %arrayidx = getelementptr inbounds i32, i32* %ptrarg, i64 42
+  %0 = load i32, i32* %arrayidx, align 4
+  %tobool1 = icmp ne i32 %0, 0
+  br i1 %tobool1, label %CallSite, label %End
+
+CallSite:                                          ; preds = %TBB, %Header
+  %i.add = add i32 %i, 99
+  call void @bar(i32* %ptrarg, i32 %i.add)
+  br label %End
+
+End:                                           ; preds = %CallSite, %TBB
+  ret void
+}
+; NODUP-LABEL: split_branch_no_extra_phi
+; NODUP-NOT: split
+; CHECK-LABEL: split_branch_no_extra_phi
+; CHECK-LABEL: Header.split
+; CHECK: %[[V1:.+]] = add i32 %i, 99
+; CHECK: call void @bar(i32* null, i32 %[[V1]])
+; CHECK: br label %CallSite
+; CHECK-LABEL: TBB.split:
+; CHECK: %[[V2:.+]] = add i32 %i, 99
+; CHECK: call void @bar(i32* nonnull %ptrarg, i32 %[[V2]])
+; CHECK: br label %CallSite
+; CHECK: CallSite:
+; CHECK-NOT: phi
+
+
+; In this test case, the codesize cost of the instructions before the call to
+; bar() is equal to the default DuplicationThreshold of 5, because calls are
+; more expensive.
+define void @test_no_split_threshold(i32* %ptrarg, i32 %i) {
+Header:
+  %tobool = icmp ne i32* %ptrarg, null
+  br i1 %tobool, label %TBB, label %CallSite
+
+TBB:                                    ; preds = %Header
+  %arrayidx = getelementptr inbounds i32, i32* %ptrarg, i64 42
+  %0 = load i32, i32* %arrayidx, align 4
+  %tobool1 = icmp ne i32 %0, 0
+  br i1 %tobool1, label %CallSite, label %End
+
+CallSite:                                          ; preds = %TBB, %Header
+  %i2 = add i32 %i, 10
+  call void @bari(i32 %i2)
+  call void @bari(i32 %i2)
+  call void @bar(i32* %ptrarg, i32 %i2)
+  br label %End
+
+End:                                           ; preds = %CallSite, %TBB
+  ret void
+}
+; NODUP-LABEL: test_no_split_threshold
+; NODUP-NOT: split
+; CHECK-LABEL: test_no_split_threshold
+; CHECK-NOT: split
+; CHECK-LABEL: CallSite:
+; CHECK: call void @bar(i32* %ptrarg, i32 %i2)
+
+; In this test case, the phi node %l in CallSite should be removed, as after
+; moving the call to the split blocks we can use the values directly.
+define void @test_remove_unused_phi(i32* %ptrarg, i32 %i) {
+Header:
+  %l1 = load i32, i32* undef, align 16
+  %tobool = icmp ne i32* %ptrarg, null
+  br i1 %tobool, label %TBB, label %CallSite
+
+TBB:                                    ; preds = %Header
+  %arrayidx = getelementptr inbounds i32, i32* %ptrarg, i64 42
+  %0 = load i32, i32* %arrayidx, align 4
+  %l2 = load i32, i32* undef, align 16
+  %tobool1 = icmp ne i32 %0, 0
+  br i1 %tobool1, label %CallSite, label %End
+
+CallSite:                                          ; preds = %TBB, %Header
+  %l = phi i32 [ %l1, %Header ], [ %l2, %TBB ]
+  call void @bar(i32* %ptrarg, i32 %l)
+  br label %End
+
+End:                                           ; preds = %CallSite, %TBB
+  ret void
+}
+; NODUP-LABEL: test_remove_unused_phi
+; NODUP-NOT: split
+; CHECK-LABEL: test_remove_unused_phi
+; CHECK-LABEL: Header.split
+; CHECK: call void @bar(i32* null, i32 %l1)
+; CHECK: br label %CallSite
+; CHECK-LABEL: TBB.split:
+; CHECK: call void @bar(i32* nonnull %ptrarg, i32 %l2)
+; CHECK: br label %CallSite
+; CHECK-LABEL: CallSite:
+; CHECK-NOT: phi
+
+; In this test case, we need to insert a new PHI node in TailBB to combine
+; the loads we moved to the predecessors.
+define void @test_add_new_phi(i32* %ptrarg, i32 %i) {
+Header:
+  %tobool = icmp ne i32* %ptrarg, null
+  br i1 %tobool, label %TBB, label %CallSite
+
+TBB:
+  br i1 undef, label %CallSite, label %End
+
+CallSite:
+  %arrayidx112 = getelementptr inbounds i32, i32* undef, i64 1
+  %0 = load i32, i32* %arrayidx112, align 4
+  call void @bar(i32* %ptrarg, i32 %i)
+  %sub = sub nsw i32 %0, undef
+  br label %End
+
+End:                                           ; preds = %CallSite, %TBB
+  ret void
+}
+; NODUP-LABEL: test_add_new_phi
+; NODUP-NOT: split
+; CHECK-LABEL: test_add_new_phi
+; CHECK-LABEL: Header.split
+; CHECK: %[[V1:.+]] = load i32, i32*
+; CHECK: call void @bar(i32* null, i32 %i)
+; CHECK: br label %CallSite
+; CHECK-LABEL: TBB.split:
+; CHECK: %[[V2:.+]] = load i32, i32*
+; CHECK: call void @bar(i32* nonnull %ptrarg, i32 %i)
+; CHECK: br label %CallSite
+; CHECK-LABEL: CallSite:
+; CHECK-NEXT: %[[V3:.+]] = phi i32 [ %[[V1]], %Header.split ], [ %[[V2]], %TBB.split ]
+; CHECK: %sub = sub nsw i32 %[[V3]], undef
+
+define i32 @test_firstnophi(i32* %a, i32 %v) {
+Header:
+  %tobool1 = icmp eq i32* %a, null
+  br i1 %tobool1, label %Tail, label %TBB
+
+TBB:
+  %cmp = icmp eq i32 %v, 1
+  br i1 %cmp, label %Tail, label %End
+
+Tail:
+  %p = phi i32[1,%Header], [2, %TBB]
+  store i32 %v, i32* %a
+  %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
+  ret i32 %r
+
+End:
+  ret i32 %v
+}
+; NODUP-LABEL: @test_firstnophi
+; NODUP-NOT: split:
+; CHECK-LABEL: @test_firstnophi
+; CHECK-LABEL: Header.split:
+; CHECK-NEXT: store i32 %v, i32* %a
+; CHECK-NEXT: %[[CALL1:.*]] = call i32 @callee(i32* null, i32 %v, i32 1)
+; CHECK-NEXT: br label %Tail
+; CHECK-LABEL: TBB.split:
+; CHECK-NEXT: store i32 %v, i32* %a
+; CHECK-NEXT: %[[CALL2:.*]] = call i32 @callee(i32* nonnull %a, i32 1, i32 2)
+; CHECK-NEXT br label %Tail
+; CHECK-LABEL: Tail:
+; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB.split ]
+; CHECK: ret i32 %[[MERGED]]
+define i32 @callee(i32* %a, i32 %v, i32 %p) {
+    ret i32 0
+}
+
+define void @test_no_remove_used_phi(i32* %ptrarg, i32 %i) {
+Header:
+  %l1 = load i32, i32* undef, align 16
+  %tobool = icmp ne i32* %ptrarg, null
+  br i1 %tobool, label %TBB, label %CallSite
+
+TBB:                                    ; preds = %Header
+  %arrayidx = getelementptr inbounds i32, i32* %ptrarg, i64 42
+  %0 = load i32, i32* %arrayidx, align 4
+  %l2 = load i32, i32* undef, align 16
+  %tobool1 = icmp ne i32 %0, 0
+  br i1 %tobool1, label %CallSite, label %End
+
+CallSite:                                          ; preds = %TBB, %Header
+  %l = phi i32 [ %l1, %Header ], [ %l2, %TBB ]
+  call void @bar(i32* %ptrarg, i32 %l)
+  call void @bari(i32 %l)
+  br label %End
+
+End:                                           ; preds = %CallSite, %TBB
+  ret void
+}
+; NODUP-LABEL: @test_no_remove_used_phi
+; NODUP-NOT: split
+; CHECK-LABEL: @test_no_remove_used_phi
+; CHECK-LABEL: Header.split:
+; CHECK: call void @bar(i32* null, i32 %l1)
+; CHECK-NEXT: br label %CallSite
+; CHECK-LABEL: TBB.split:
+; CHECK: call void @bar(i32* nonnull %ptrarg, i32 %l2)
+; CHECK-NEXT br label %CallSite
+; CHECK-LABEL: CallSite:
+; CHECK-NEXT:  %l = phi i32 [ %l1, %Header.split ], [ %l2, %TBB.split ]
+; CHECK: call void @bari(i32 %l)
+
+define void @bar(i32*, i32) {
+    ret void
+}
+
+define  void @bari(i32) {
+    ret void
+}

test/Transforms/CallSiteSplitting/callsite-no-or-structure.ll

 ; RUN: opt < %s -callsite-splitting -S | FileCheck %s
 ; RUN: opt < %s  -passes='function(callsite-splitting)' -S | FileCheck %s
 
 ; CHECK-LABEL: @test_simple
 ; CHECK-LABEL: Header:
-; CHECK-NEXT: br i1 undef, label %Tail.predBB.split
-; CHECK-LABEL: TBB:
-; CHECK: br i1 %cmp, label %Tail.predBB.split1
-; CHECK-LABEL: Tail.predBB.split:
+; CHECK-NEXT: br i1 undef, label %Header.split
+; CHECK-LABEL: Header.split:
 ; CHECK: %[[CALL1:.*]] = call i32 @callee(i32* %a, i32 %v, i32 %p)
-; CHECK-LABEL: Tail.predBB.split1:
+; CHECK-LABEL: TBB:
+; CHECK: br i1 %cmp, label %TBB.split
+; CHECK-LABEL: TBB.split:
 ; CHECK: %[[CALL2:.*]] = call i32 @callee(i32* null, i32 %v, i32 %p)
 ; CHECK-LABEL: Tail
-; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB.split ]
 ; CHECK: ret i32 %[[MERGED]]
 define i32 @test_simple(i32* %a, i32 %v, i32 %p) {
 Header:
   br i1 undef, label %Tail, label %End
 
 TBB:
   %cmp = icmp eq i32* %a, null
   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
 }
 
 ; CHECK-LABEL: @test_eq_eq_eq_untaken
 ; CHECK-LABEL: Header:
-; CHECK: br i1 %tobool1, label %TBB1, label %Tail.predBB.split
-; CHECK-LABEL: TBB2:
-; CHECK: br i1 %cmp2, label %Tail.predBB.split1, label %End
-; CHECK-LABEL: Tail.predBB.split:
+; CHECK: br i1 %tobool1, label %TBB1, label %Header.split
+; CHECK-LABEL: Header.split:
 ; CHECK: %[[CALL1:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 %p)
-; CHECK-LABEL: Tail.predBB.split1:
+; CHECK-LABEL: TBB2:
+; CHECK: br i1 %cmp2, label %TBB2.split, label %End
+; CHECK-LABEL: TBB2.split:
 ; CHECK: %[[CALL2:.*]] = call i32 @callee(i32* null, i32 1, i32 99)
 ; CHECK-LABEL: Tail
-; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB2.split ]
 ; CHECK: ret i32 %[[MERGED]]
 define i32 @test_eq_eq_eq_untaken2(i32* %a, i32 %v, i32 %p) {
 Header:
   %tobool1 = icmp eq i32* %a, null
   br i1 %tobool1, label %TBB1, label %Tail
 
 TBB1:
   %cmp1 = icmp eq i32 %v, 1
   br i1 %cmp1, label %TBB2, label %End
 
 TBB2:
   %cmp2 = icmp eq i32 %p, 99
   br i1 %cmp2, label %Tail, label %End
 
 Tail:
   %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
   ret i32 %r
 
 End:
   ret i32 %v
 }
 
 ; CHECK-LABEL: @test_eq_ne_eq_untaken
 ; CHECK-LABEL: Header:
-; CHECK: br i1 %tobool1, label %TBB1, label %Tail.predBB.split
-; CHECK-LABEL: TBB2:
-; CHECK: br i1 %cmp2, label %Tail.predBB.split1, label %End
-; CHECK-LABEL: Tail.predBB.split:
+; CHECK: br i1 %tobool1, label %TBB1, label %Header.split
+; CHECK-LABEL: Header.split:
 ; CHECK: %[[CALL1:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 %p)
-; CHECK-LABEL: Tail.predBB.split1:
+; CHECK-LABEL: TBB2:
+; CHECK: br i1 %cmp2, label %TBB2.split, label %End
+; CHECK-LABEL: TBB2.split:
 ; CHECK: %[[CALL2:.*]] = call i32 @callee(i32* null, i32 %v, i32 99)
 ; CHECK-LABEL: Tail
-; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB2.split ]
 ; CHECK: ret i32 %[[MERGED]]
 define i32 @test_eq_ne_eq_untaken(i32* %a, i32 %v, i32 %p) {
 Header:
   %tobool1 = icmp eq i32* %a, null
   br i1 %tobool1, label %TBB1, label %Tail
 
 TBB1:
   %cmp1 = icmp ne i32 %v, 1
   br i1 %cmp1, label %TBB2, label %End
 
 TBB2:
   %cmp2 = icmp eq i32 %p, 99
   br i1 %cmp2, label %Tail, label %End
 
 Tail:
   %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
   ret i32 %r
 
 End:
   ret i32 %v
 }
 
 ; CHECK-LABEL: @test_header_header2_tbb
 ; CHECK: Header2:
-; CHECK:br i1 %tobool2, label %Tail.predBB.split, label %TBB1
-; CHECK-LABEL: TBB2:
-; CHECK: br i1 %cmp2, label %Tail.predBB.split1, label %End
-; CHECK-LABEL: Tail.predBB.split:
+; CHECK:br i1 %tobool2, label %Header2.split, label %TBB1
+; CHECK-LABEL: Header2.split:
 ; CHECK: %[[CALL1:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 10)
-; CHECK-LABEL: Tail.predBB.split1:
+; CHECK-LABEL: TBB2:
+; CHECK: br i1 %cmp2, label %TBB2.split, label %End
+; CHECK-LABEL: TBB2.split:
 ; NOTE: CallSiteSplitting cannot infer that %a is null here, as it currently
 ;       only supports recording conditions along a single predecessor path.
 ; CHECK: %[[CALL2:.*]] = call i32 @callee(i32* %a, i32 1, i32 99)
 ; CHECK-LABEL: Tail
-; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+; CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header2.split ], [ %[[CALL2]], %TBB2.split ]
 ; CHECK: ret i32 %[[MERGED]]
 define i32 @test_header_header2_tbb(i32* %a, i32 %v, i32 %p) {
 Header:
   %tobool1 = icmp eq i32* %a, null
   br i1 %tobool1, label %TBB1, label %Header2
 
 Header2:
   %tobool2 = icmp eq i32 %p, 10

test/Transforms/CallSiteSplitting/callsite-split-debug.ll

 !6 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 4, unit: !0)
 !7 = !DILocalVariable(name: "c", scope: !6, line: 5, type: !5)
 !8 = !DILocation(line: 5, column: 7, scope: !6)
 
 ; The optimization should trigger even in the presence of the dbg.value in
 ; CallSiteBB.
 
 ; CHECK-LABEL: @foo
-; CHECK-LABEL: CallsiteBB.predBB.split:
-; CHECK: [[TMP1:%[0-9]+]] = call i16 @bar(i16 1, i16 5)
-; CHECK-LABEL: CallsiteBB.predBB.split1:
-; CHECK: [[TMP2:%[0-9]+]] = call i16 @bar(i16 0, i16 5)
+; CHECK-LABEL: bb1.split:
+; CHECK: [[TMP1:%[0-9]+]] = call i16 @bar(i16 0, i16 5)
+; CHECK-LABEL: bb2.split:
+; CHECK: [[TMP2:%[0-9]+]] = call i16 @bar(i16 1, i16 5)
 ; CHECK-LABEL: CallsiteBB
-; CHECK: %phi.call = phi i16 [ [[TMP1]], %CallsiteBB.predBB.split ], [ [[TMP2]], %CallsiteBB.predBB.split1
-
+; CHECK: %phi.call = phi i16 [ [[TMP2]], %bb2.split ], [ [[TMP1]], %bb1.split

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

 ; RUN: opt < %s -callsite-splitting -S | FileCheck %s
 ; RUN: opt < %s  -passes='function(callsite-splitting)' -S | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64-linaro-linux-gnueabi"
 
 ;CHECK-LABEL: @test_eq_eq
-;CHECK-LABEL: Tail.predBB.split:
+
+;CHECK-LABEL: Header:
+;CHECK: br i1 %tobool1, label %Header.split, label %TBB
+;CHECK-LABEL: Header.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* null, i32 %v, i32 1)
-;CHECK-LABEL: Tail.predBB.split1:
+;CHECK-LABEL: TBB:
+;CHECK: br i1 %cmp, label %TBB.split, label %End
+;CHECK-LABEL: TBB.split:
 ;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* nonnull %a, i32 1, i32 2)
 ;CHECK-LABEL: Tail
-;CHECK: %p = phi i32 [ 1, %Tail.predBB.split ], [ 2, %Tail.predBB.split1 ]
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB.split ]
 ;CHECK: ret i32 %[[MERGED]]
 define i32 @test_eq_eq(i32* %a, i32 %v) {
 Header:
   %tobool1 = icmp eq i32* %a, null
   br i1 %tobool1, label %Tail, label %TBB
 
 TBB:
   %cmp = icmp eq 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_eq_eq_eq
-;CHECK-LABEL: Tail.predBB.split:
+;CHECK-LABEL: Header2.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* null, i32 %v, i32 10)
-;CHECK-LABEL: Tail.predBB.split1:
+;CHECK-LABEL: TBB.split:
 ;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* null, i32 1, i32 %p)
 ;CHECK-LABEL: Tail
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header2.split ], [ %[[CALL2]], %TBB.split ]
 ;CHECK: ret i32 %[[MERGED]]
 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
   br i1 %tobool2, label %Tail, label %TBB
 
 TBB:
   %cmp = icmp eq i32 %v, 1
   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
 }
 
 ;CHECK-LABEL: @test_eq_eq_eq_constrain_same_i32_arg
-;CHECK-LABEL: Tail.predBB.split:
+;CHECK-LABEL: Header2.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* %a, i32 222, i32 %p)
-;CHECK-LABEL: Tail.predBB.split1:
+;CHECK-LABEL: TBB.split:
 ;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* %a, i32 333, i32 %p)
 ;CHECK-LABEL: Tail
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header2.split ], [ %[[CALL2]], %TBB.split ]
 ;CHECK: ret i32 %[[MERGED]]
 define i32 @test_eq_eq_eq_constrain_same_i32_arg(i32* %a, i32 %v, i32 %p) {
 Header:
   %tobool1 = icmp eq i32 %v, 111
   br i1 %tobool1, label %Header2, label %End
 
 Header2:
   %tobool2 = icmp eq i32 %v, 222
   br i1 %tobool2, label %Tail, label %TBB
 
 TBB:
   %cmp = icmp eq i32 %v, 333
   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
 }
 
 ;CHECK-LABEL: @test_ne_eq
-;CHECK-LABEL: Tail.predBB.split:
+;CHECK-LABEL: Header.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 1)
-;CHECK-LABEL: Tail.predBB.split1:
+;CHECK-LABEL: TBB.split:
 ;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* null, i32 1, i32 2)
 ;CHECK-LABEL: Tail
-;CHECK: %p = phi i32 [ 1, %Tail.predBB.split ], [ 2, %Tail.predBB.split1 ]
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB.split ]
 ;CHECK: ret i32 %[[MERGED]]
 define i32 @test_ne_eq(i32* %a, i32 %v) {
 Header:
   %tobool1 = icmp ne i32* %a, null
   br i1 %tobool1, label %Tail, label %TBB
 
 TBB:
   %cmp = icmp eq 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_ne_eq_ne
-;CHECK-LABEL: Tail.predBB.split:
+;CHECK-LABEL: Header2.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 10)
-;CHECK-LABEL: Tail.predBB.split1:
+;CHECK-LABEL: TBB.split:
 ;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 %p)
 ;CHECK-LABEL: Tail
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;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
 
 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:
   %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
   ret i32 %r
 
 End:
   ret i32 %v
 }
 
 ;CHECK-LABEL: @test_ne_ne
-;CHECK-LABEL: Tail.predBB.split:
+;CHECK-LABEL: Header.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 1)
-;CHECK-LABEL: Tail.predBB.split1:
+;CHECK-LABEL: TBB.split:
 ;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* null, i32 %v, i32 2)
 ;CHECK-LABEL: Tail
-;CHECK: %p = phi i32 [ 1, %Tail.predBB.split ], [ 2, %Tail.predBB.split1 ]
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB.split ]
 ;CHECK: ret i32 %[[MERGED]]
 define i32 @test_ne_ne(i32* %a, i32 %v) {
 Header:
   %tobool1 = icmp ne i32* %a, null
   br i1 %tobool1, 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_ne_ne_ne_constrain_same_pointer_arg
-;CHECK-LABEL: Tail.predBB.split:
+;CHECK-LABEL: Header2.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 %p)
-;CHECK-LABEL: Tail.predBB.split1:
+;CHECK-LABEL: TBB.split:
 ;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 %p)
 ;CHECK-LABEL: Tail
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;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
 
 Header2:
   %tobool2 = icmp ne i32* %a, %a2

 
 End:
   ret i32 %v
 }
 
 
 
 ;CHECK-LABEL: @test_eq_eq_untaken
-;CHECK-LABEL: Tail.predBB.split:
+;CHECK-LABEL: Header.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 1)
-;CHECK-LABEL: Tail.predBB.split1:
+;CHECK-LABEL: TBB.split:
 ;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* null, i32 1, i32 2)
 ;CHECK-LABEL: Tail
-;CHECK: %p = phi i32 [ 1, %Tail.predBB.split ], [ 2, %Tail.predBB.split1 ]
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB.split ]
 ;CHECK: ret i32 %[[MERGED]]
 define i32 @test_eq_eq_untaken(i32* %a, i32 %v) {
 Header:
   %tobool1 = icmp eq i32* %a, null
   br i1 %tobool1, label %TBB, label %Tail
 
 TBB:
   %cmp = icmp eq 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_eq_eq_eq_untaken
-;CHECK-LABEL: Tail.predBB.split:
+;CHECK-LABEL: Header2.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* nonnull %a, i32 %v, i32 10)
-;CHECK-LABEL: Tail.predBB.split1:
+;CHECK-LABEL: TBB.split:
 ;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* nonnull %a, i32 1, i32 %p)
 ;CHECK-LABEL: Tail
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;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
 
 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
 
 Tail:
   %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
   ret i32 %r
 
 End:
   ret i32 %v
 }
 
 ;CHECK-LABEL: @test_ne_eq_untaken
-;CHECK-LABEL: Tail.predBB.split:
+;CHECK-LABEL: Header.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* null, i32 %v, i32 1)
-;CHECK-LABEL: Tail.predBB.split1:
+;CHECK-LABEL: TBB.split:
 ;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* nonnull %a, i32 1, i32 2)
 ;CHECK-LABEL: Tail
-;CHECK: %p = phi i32 [ 1, %Tail.predBB.split ], [ 2, %Tail.predBB.split1 ]
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB.split ]
 ;CHECK: ret i32 %[[MERGED]]
 define i32 @test_ne_eq_untaken(i32* %a, i32 %v) {
 Header:
   %tobool1 = icmp ne i32* %a, null
   br i1 %tobool1, label %TBB, label %Tail
 
 TBB:
   %cmp = icmp eq 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_ne_eq_ne_untaken
-;CHECK-LABEL: Tail.predBB.split:
+;CHECK-LABEL: Header2.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* null, i32 %v, i32 10)
-;CHECK-LABEL: Tail.predBB.split1:
+;CHECK-LABEL: TBB.split:
 ;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* null, i32 %v, i32 %p)
 ;CHECK-LABEL: Tail
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;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
 
 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:
   %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
   ret i32 %r
 
 End:
   ret i32 %v
 }
 
 ;CHECK-LABEL: @test_ne_ne_untaken
-;CHECK-LABEL: Tail.predBB.split:
+;CHECK-LABEL: Header.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* null, i32 %v, i32 1)
-;CHECK-LABEL: Tail.predBB.split1:
+;CHECK-LABEL: TBB.split:
 ;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* nonnull %a, i32 1, i32 2)
 ;CHECK-LABEL: Tail
-;CHECK: %p = phi i32 [ 1, %Tail.predBB.split ], [ 2, %Tail.predBB.split1 ]
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB.split ]
 ;CHECK: ret i32 %[[MERGED]]
 define i32 @test_ne_ne_untaken(i32* %a, i32 %v) {
 Header:
   %tobool1 = icmp ne i32* %a, null
   br i1 %tobool1, label %TBB, label %Tail
 
 TBB:
   %cmp = icmp ne i32 %v, 1
   br i1 %cmp, label %End, label %Tail
 
 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_nonconst_const_phi
-;CHECK-LABEL: Tail.predBB.split:
+;CHECK-LABEL: Header.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* %a, i32 %v, i32 1)
-;CHECK-LABEL: Tail.predBB.split1:
+;CHECK-LABEL: TBB.split:
 ;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* %a, i32 1, i32 2)
 ;CHECK-LABEL: Tail
-;CHECK: %p = phi i32 [ 1, %Tail.predBB.split ], [ 2, %Tail.predBB.split1 ]
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB.split ]
 ;CHECK: ret i32 %[[MERGED]]
 define i32 @test_nonconst_const_phi(i32* %a, i32* %b, i32 %v) {
 Header:
   %tobool1 = icmp eq i32* %a, %b
   br i1 %tobool1, label %Tail, label %TBB
 
 TBB:
   %cmp = icmp eq 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_nonconst_nonconst_phi
-;CHECK-LABEL: Tail.predBB.split:
-;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* %a, i32 %v, i32 2)
-;CHECK-LABEL: Tail.predBB.split1:
-;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* %a, i32 %v, i32 1)
+;CHECK-LABEL: Header.split:
+;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* %a, i32 %v, i32 1)
+;CHECK-LABEL: TBB.split:
+;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* %a, i32 %v, i32 2)
 ;CHECK-LABEL: Tail
-;CHECK: %p = phi i32 [ 2, %Tail.predBB.split ], [ 1, %Tail.predBB.split1 ]
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL2]], %TBB.split ], [ %[[CALL1]], %Header.split ]
 ;CHECK: ret i32 %[[MERGED]]
 define i32 @test_nonconst_nonconst_phi(i32* %a, i32* %b, i32 %v, i32 %v2) {
 Header:
   %tobool1 = icmp eq i32* %a, %b
   br i1 %tobool1, label %Tail, label %TBB
 
 TBB:
   %cmp = icmp eq i32 %v, %v2 
   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_cfg_no_or_phi
-;CHECK-LABEL: Tail.predBB.split
-;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* %a, i32 %v, i32 2)
-;CHECK-LABEL: Tail.predBB.split1:
-;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* %a, i32 %v, i32 1)
+;CHECK-LABEL: TBB0.split
+;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* %a, i32 %v, i32 1)
+;CHECK-LABEL: TBB1.split:
+;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* %a, i32 %v, i32 2)
 ;CHECK-LABEL: Tail
-;CHECK: %p = phi i32 [ 2, %Tail.predBB.split ], [ 1, %Tail.predBB.split1 ]
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL2]], %TBB1.split ], [ %[[CALL1]], %TBB0.split ]
 ;CHECK: ret i32 %[[MERGED]]
 define i32 @test_cfg_no_or_phi(i32* %a,  i32 %v) {
 entry:
   br i1 undef, label %TBB0, label %TBB1
 TBB0:
   br i1 undef, label %Tail, label %End
 TBB1:
   br i1 undef, label %Tail, label %End
 Tail:
   %p = phi i32[1,%TBB0], [2, %TBB1]
   %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
   ret i32 %r
 End:
   ret i32 %v
 }
 
 ;CHECK-LABEL: @test_nonconst_nonconst_phi_noncost
-;CHECK-NOT: Tail.predBB.split:
-;CHECK-NOT: Tail.predBB.split1:
+;CHECK-NOT: Header.split:
+;CHECK-NOT: TBB.split:
 ;CHECK-LABEL: Tail:
 ;CHECK: %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
 ;CHECK: ret i32 %r
 define i32 @test_nonconst_nonconst_phi_noncost(i32* %a, i32* %b, i32 %v, i32 %v2) {
 Header:
   %tobool1 = icmp eq i32* %a, %b
   br i1 %tobool1, label %Tail, label %TBB
 
 TBB:
   %cmp = icmp eq i32 %v, %v2 
   br i1 %cmp, label %Tail, label %End
 
 Tail:
   %p = phi i32[%v,%Header], [%v2, %TBB]
   %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
   ret i32 %r
 
 End:
   ret i32 %v
 }
 
-;CHECK-LABEL: @test_fisrtnonphi
-;CHECK-NOT: Tail.predBB.split:
-;CHECK-NOT: Tail.predBB.split1:
-;CHECK-LABEL: Tail:
-;CHECK: %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
-;CHECK: ret i32 %r
-define i32 @test_fisrtnonphi(i32* %a, i32 %v) {
-Header:
-  %tobool1 = icmp eq i32* %a, null
-  br i1 %tobool1, label %Tail, label %TBB
-
-TBB:
-  %cmp = icmp eq i32 %v, 1
-  br i1 %cmp, label %Tail, label %End
-
-Tail:
-  %p = phi i32[1,%Header], [2, %TBB]
-  store i32 %v, i32* %a
-  %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
-  ret i32 %r
-
-End:
-  ret i32 %v
-}
-
 ;CHECK-LABEL: @test_3preds_constphi
-;CHECK-NOT: Tail.predBB.split:
-;CHECK-NOT: Tail.predBB.split1:
+;CHECK-NOT: Header.split:
+;CHECK-NOT: TBB.split:
 ;CHECK-LABEL: Tail:
 ;CHECK: %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
 ;CHECK: ret i32 %r
 define i32 @test_3preds_constphi(i32* %a, i32 %v, i1 %c1, i1 %c2, i1 %c3) {
 Header:
   br i1 %c1, label %Tail, label %TBB1
 
 TBB1:
   br i1 %c2, label %Tail, label %TBB2
 
 TBB2:
   br i1 %c3, label %Tail, label %End
 
 Tail:
   %p = phi i32[1,%Header], [2, %TBB1], [3, %TBB2]
   %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
   ret i32 %r
 
 End:
   ret i32 %v
 }
 
 ;CHECK-LABEL: @test_indirectbr_phi
-;CHECK-NOT: Tail.predBB.split:
-;CHECK-NOT: Tail.predBB.split1:
+;CHECK-NOT: Header.split:
+;CHECK-NOT: TBB.split:
 ;CHECK-LABEL: Tail:
 ;CHECK: %r = call i32 @callee(i32* %a, i32 %v, i32 %p)
 ;CHECK: ret i32 %r
 define i32 @test_indirectbr_phi(i8* %address, i32* %a, i32* %b, i32 %v) {
 Header:
    %indirect.goto.dest = select i1 undef, i8* blockaddress(@test_indirectbr_phi, %End), i8* %address
    indirectbr i8* %indirect.goto.dest, [label %TBB, label %Tail]
 
 TBB:
   %indirect.goto.dest2 = select i1 undef, i8* blockaddress(@test_indirectbr_phi, %End), i8* %address
   indirectbr i8* %indirect.goto.dest2, [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_unreachable
-;CHECK-LABEL: Tail.predBB.split:
+;CHECK-LABEL: Header.split:
 ;CHECK: %[[CALL1:.*]] = call i32 @callee(i32* %a, i32 %v, i32 10)
-;CHECK-LABEL: Tail.predBB.split1:
+;CHECK-LABEL: TBB.split:
 ;CHECK: %[[CALL2:.*]] = call i32 @callee(i32* %a, i32 1, i32 %p)
 ;CHECK-LABEL: Tail
-;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Tail.predBB.split ], [ %[[CALL2]], %Tail.predBB.split1 ]
+;CHECK: %[[MERGED:.*]] = phi i32 [ %[[CALL1]], %Header.split ], [ %[[CALL2]], %TBB.split ]
 ;CHECK: ret i32 %[[MERGED]]
 define i32 @test_unreachable(i32* %a, i32 %v, i32 %p) {
 Entry:
   br label %End
 Header:
   %tobool2 = icmp eq i32 %p, 10
   br i1 %tobool2, label %Tail, label %TBB
 TBB:

test/Transforms/CallSiteSplitting/callsite-split.ll

 ; RUN: opt < %s -callsite-splitting -inline -instcombine -jump-threading -S | FileCheck %s
 ; RUN: opt < %s  -passes='function(callsite-splitting),cgscc(inline),function(instcombine,jump-threading)' -S | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64-linaro-linux-gnueabi"
 
 %struct.bitmap = type { i32, %struct.bitmap* }
 
 ;CHECK-LABEL: @caller
+;CHECK-LABEL: Top.split:
+;CHECK: call void @callee(%struct.bitmap* null, %struct.bitmap* null, %struct.bitmap* %b_elt, i1 false)
 ;CHECK-LABEL: NextCond:
 ;CHECK: br {{.*}} label %callee.exit
-;CHECK-LABEL: CallSiteBB.predBB.split:
-;CHECK: call void @callee(%struct.bitmap* null, %struct.bitmap* null, %struct.bitmap* %b_elt, i1 false)
 ;CHECK-LABEL: callee.exit:
 ;CHECK: call void @dummy2(%struct.bitmap* %a_elt)
 
 define void @caller(i1 %c, %struct.bitmap* %a_elt, %struct.bitmap* %b_elt) {
 entry:
   br label %Top
 
 Top:
End:
   ret void
 }
 
 declare void @dummy2(%struct.bitmap*)
 declare void @dummy1(%struct.bitmap*, %struct.bitmap*, %struct.bitmap*, %struct.bitmap*, %struct.bitmap*, %struct.bitmap*)
 
 
 ;CHECK-LABEL: @caller2
-;CHECK-LABEL: CallSiteBB.predBB.split:
-;CHECK: call void @dummy3()
-;CHECK-LABEL: CallSiteBB.predBB.split1:
+;CHECK-LABEL: Top.split:
 ;CHECK: call void @dummy4()
+;CHECK-LABEL: NextCond.split:
+;CHECK: call void @dummy3()
 ;CheCK-LABEL: CallSiteBB:
-;CHECK: %phi.call = phi i1 [ true, %CallSiteBB.predBB.split ], [ false, %CallSiteBB.predBB.split1 ]
+;CHECK: %phi.call = phi i1 [ true, %NextCond.split ], [ false, %Top.split ]
 ;CHECK: call void @foo(i1 %phi.call)
 define void @caller2(i1 %c, %struct.bitmap* %a_elt, %struct.bitmap* %b_elt, %struct.bitmap* %c_elt) {
 entry:
   br label %Top
 
 Top:
   %tobool1 = icmp eq %struct.bitmap* %a_elt, %b_elt
   br i1 %tobool1, label %CallSiteBB, label %NextCond