[PartialInlining] Enhance code outliner to sink locals declared outside the outline region

[davidxl]

Summary

This is a follow up to the previous patch that shrinkwraps allocas of locals that are declared inside the outline region.

With this patch, the machinery is introduced to handle more general case when life time markers are outside the region. This is the first step which is not yet hooked up with AA yet.

[davidxl]

Fix bugs in tests.

[wmi]

lib/Transforms/Utils/CodeExtractor.cpp

166

Why we choose to skip BitCast, GetElementPtr, ..., Alloca, but treat other instructions like BinaryOp instruction conservatively. Why not just check memory access instructions like load/store/call and treat them conservatively, but skip all the other instructions?

187–197

Can store have similar logic as load here?

291–299

I think it is possible one alloca has multiple pairs of lifetime_start and lifetime_end. Like loop unrolling may create such case. It is also possible for one lifetime_start to have multiple lifetime_ends. But I guess the most common case in inlined blocks is one pair of lifetime_start and lifetime_end, so we may just add some check to avoid the other uncommon cases.

336–349

If AI have multiple bitcasts, we will only sink one of them and may cause problem?

[davidxl]

lib/Transforms/Utils/CodeExtractor.cpp

166

Done.

187–197

Done.

291–299

Added check to fail when this is detected.

336–349

I think it is already handled. If there are more than one bitcast uses outside the region, the getter will return null.

[davidxl]

Addressed Wei's feedback.

[wmi]

One comment about simplifying the test. Other than that, LGTM.

test/Transforms/CodeExtractor/live_shrink.ll

19–34

The target of the test is used to check whether alloca can be shrinked properly. Can we use -skip-partial-inlining-cost-analysis and simplify the test by keeping only one call @_ZN1A7memfuncEv?

[davidxl]

Simplify test cases.

[davide]

lib/Transforms/Utils/CodeExtractor.cpp

147–162

I think this is a case where two nested lambda expressions make the code hard to understand. I'd convert them to a for loop.

362

You can probably move this inside the NDEBUG block.

[davide]

include/llvm/Transforms/Utils/CodeExtractor.h

110

s/sinked/sunk/

lib/Transforms/Utils/CodeExtractor.cpp

288–289

Can you add a comment explaining why you skip ordered load/stores?

[davidxl]

Addressed Davide's comments.

[davidxl]

Any more comments?

lib/Transforms/Utils/CodeExtractor.cpp

288–289

not necessarily needed. Removed.

[davide]

No more comments from me.

include/llvm/Transforms/Utils/CodeExtractor.h

     /// These can be used either when performing the extraction or to evaluate
     /// the expected size of a call to the extracted function. Note that this
     /// work cannot be cached between the two as once we decide to extract
     /// a code sequence, that sequence is modified, including changing these
     /// sets, before extraction occurs. These modifications won't have any
     /// significant impact on the cost however.
     void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
                            const ValueSet &Allocas) const;
+
+    /// Check if life time marker nodes can be hoisted/sinked into the outline
+    /// region.
+    ///
+    /// Returns true if it is safe to do the code motion.
+    bool isLegalToShrinkwrapLifetimeMarkers(Instruction *AllocaAddr) const;
     /// Find the set of allocas whose life ranges are contained within the
     /// outlined region.
     ///
     /// Allocas which have life_time markers contained in the outlined region
     /// should be pushed to the outlined function. The address bitcasts that
     /// are used by the lifetime markers are also candidates for shrink-
     /// wrapping. The instructions that need to be sinked are collected in
     /// 'Allocas'.
-    void findAllocas(ValueSet &Allocas) const;
+    void findAllocas(ValueSet &SinkCands, ValueSet &HoistCands,
+                     BasicBlock *&ExitBlock) const;
+
+    /// Find or create a block within the outline region for placing hoisted
+    /// code.
+    ///
+    /// CommonExitBlock is block outside the outline region. It is the common
+    /// successor of blocks inside the region. If there exists a single block
+    /// inside the region that is the predecessor of CommonExitBlock, that block
+    /// will be returned. Otherwise CommonExitBlock will be split and the
+    /// original block will be added to the outline region.
+    BasicBlock *findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock);
 
   private:
     void severSplitPHINodes(BasicBlock *&Header);
     void splitReturnBlocks();
 
     Function *constructFunction(const ValueSet &inputs,
                                 const ValueSet &outputs,
                                 BasicBlock *header,

lib/Transforms/Utils/CodeExtractor.cpp

 static bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) {
   if (isa<Argument>(V)) return true;
   if (Instruction *I = dyn_cast<Instruction>(V))
     if (!Blocks.count(I->getParent()))
       return true;
   return false;
 }
 
-void CodeExtractor::findAllocas(ValueSet &SinkCands) const {
+static BasicBlock *getCommonExitBlock(const SetVector<BasicBlock *> &Blocks) {
+  BasicBlock *CommonExitBlock = nullptr;
+  if (any_of(Blocks, [&](BasicBlock *Block) {
+        if (any_of(successors(Block), [&](BasicBlock *Succ) {
+              // Internal edges, ok.
+              if (Blocks.count(Succ))
+                return false;
+              if (!CommonExitBlock) {
+                CommonExitBlock = Succ;
+                return false;
+              }
+              return CommonExitBlock != Succ;
+            }))
+          return true;
+        return false;
+      }))
+    return nullptr;
+
+  return CommonExitBlock;
+}
+
+bool CodeExtractor::isLegalToShrinkwrapLifetimeMarkers(Instruction *Addr) const {
+  AllocaInst *AI = cast<AllocaInst>(Addr->stripInBoundsConstantOffsets());
+  Function *Func = (*Blocks.begin())->getParent();
+  for (BasicBlock &BB : *Func) {
+    if (Blocks.count(&BB))
+      continue;
+    for (Instruction &II : BB) {
+
+      if (isa<DbgInfoIntrinsic>(II))
+        continue;
+
+      unsigned Opcode = II.getOpcode();
+      switch (Opcode) {
+      case Instruction::BitCast:
+      case Instruction::GetElementPtr:
+      case Instruction::ICmp:
+      case Instruction::Br:
+      case Instruction::Ret:
+      case Instruction::Alloca:
+        break;
+      case Instruction::Load: {
+        LoadInst *LI = dyn_cast<LoadInst>(&II);
+        Value *Mem = LI->getOperand(0);
+        // Global variable not can not be aliased with locals.
+        if (dyn_cast<Constant>(Mem))
+          break;
+        Value *Base = Mem->stripInBoundsConstantOffsets();
+        if (!dyn_cast<AllocaInst>(Base) || Base == AI)
+          return false;
+        break;
+      }
+      default: {
+        IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(&II);
+        if (IntrInst) {
+          if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start ||
+              IntrInst->getIntrinsicID() == Intrinsic::lifetime_end)
+            break;
+          return false;
+        }
+        // Treat all the other cases conservatively:
+        return false;
+      }
+      }
+    }
+  }
+
+  return true;
+}
+
+BasicBlock *
+CodeExtractor::findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock) {
+  BasicBlock *SinglePredFromOutlineRegion = nullptr;
+  assert(!Blocks.count(CommonExitBlock) &&
+         "Expect a block outside the region!");
+  for (auto *Pred : predecessors(CommonExitBlock)) {
+    if (!Blocks.count(Pred))
+      continue;
+    if (!SinglePredFromOutlineRegion) {
+      SinglePredFromOutlineRegion = Pred;
+    } else if (SinglePredFromOutlineRegion != Pred) {
+      SinglePredFromOutlineRegion = nullptr;
+      break;
+    }
+  }
+
+  if (SinglePredFromOutlineRegion)
+    return SinglePredFromOutlineRegion;
+
+#ifndef NDEBUG
+  auto getFirstPHI = [](BasicBlock *BB) {
+    BasicBlock::iterator I = BB->begin();
+    PHINode *FirstPhi = nullptr;
+    while (I != BB->end()) {
+      PHINode *Phi = dyn_cast<PHINode>(I);
+      if (!Phi)
+        break;
+      if (!FirstPhi) {
+        FirstPhi = Phi;
+        break;
+      }
+    }
+    return FirstPhi;
+  };
+#endif
+
+  // If there are any phi nodes, the single pred either exists or has already
+  // be created before code extraction.
+  assert(!getFirstPHI(CommonExitBlock) && "Phi not expected");
+
+  BasicBlock *NewExitBlock = CommonExitBlock->splitBasicBlock(
+      CommonExitBlock->getFirstNonPHI()->getIterator());
+
+  for (auto *Pred : predecessors(CommonExitBlock)) {
+    if (Blocks.count(Pred))
+      continue;
+    Pred->getTerminator()->replaceUsesOfWith(CommonExitBlock, NewExitBlock);
+  }
+  // Now add the old exit block to the outline region.
+  Blocks.insert(CommonExitBlock);
+  return CommonExitBlock;
+}
+
+void CodeExtractor::findAllocas(ValueSet &SinkCands, ValueSet &HoistCands,
+                                BasicBlock *&ExitBlock) const {
   Function *Func = (*Blocks.begin())->getParent();
+  ExitBlock = getCommonExitBlock(Blocks);
+
   for (BasicBlock &BB : *Func) {
     if (Blocks.count(&BB))
       continue;
     for (Instruction &II : BB) {
       auto *AI = dyn_cast<AllocaInst>(&II);
       if (!AI)
         continue;
 
-      // Returns true if matching life time markers are found within
-      // the outlined region.
-      auto GetLifeTimeMarkers = [&](Instruction *Addr) {
+      // Find the pair of life time markers for address 'Addr' that are either
+      // defined inside the outline region or can legally be shrinkwrapped into
+      // the outline region. If there are not other untracked uses of the
+      // address, return the pair of markers if found; otherwise return a pair
+      // of nullptr.
+      auto GetLifeTimeMarkers =
+          [&](Instruction *Addr, bool &SinkLifeStart,
+              bool &HoistLifeEnd) -> std::pair<Instruction *, Instruction *> {
         Instruction *LifeStart = nullptr, *LifeEnd = nullptr;
-        for (User *U : Addr->users()) {
-          if (!definedInRegion(Blocks, U))
-            return false;
 
+        for (User *U : Addr->users()) {
           IntrinsicInst *IntrInst = dyn_cast<IntrinsicInst>(U);
           if (IntrInst) {
             if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_start)
               LifeStart = IntrInst;
             if (IntrInst->getIntrinsicID() == Intrinsic::lifetime_end)
               LifeEnd = IntrInst;
+            continue;
           }
+          // Find untracked uses of the address, bail.
+          if (!definedInRegion(Blocks, U))
+            return std::make_pair<Instruction *>(nullptr, nullptr);
         }
-        return LifeStart && LifeEnd;
+
+        if (!LifeStart || !LifeEnd)
+          return std::make_pair<Instruction *>(nullptr, nullptr);
+
+        SinkLifeStart = !definedInRegion(Blocks, LifeStart);
+        HoistLifeEnd = !definedInRegion(Blocks, LifeEnd);
+        // Do legality Check.
+        if ((SinkLifeStart || HoistLifeEnd) &&
+            !isLegalToShrinkwrapLifetimeMarkers(Addr))
+          return std::make_pair<Instruction *>(nullptr, nullptr);
+
+        // Check to see if we have a place to do hoisting, if not, bail.
+        if (HoistLifeEnd && !ExitBlock)
+          return std::make_pair<Instruction *>(nullptr, nullptr);
+
+        return std::make_pair(LifeStart, LifeEnd);
       };
 
-      if (GetLifeTimeMarkers(AI)) {
+      bool SinkLifeStart = false, HoistLifeEnd = false;
+      auto Markers = GetLifeTimeMarkers(AI, SinkLifeStart, HoistLifeEnd);
+
+      if (Markers.first) {
+        if (SinkLifeStart)
+          SinkCands.insert(Markers.first);
         SinkCands.insert(AI);
+        if (HoistLifeEnd)
+          HoistCands.insert(Markers.second);
         continue;
       }
 
-      // Follow the bitcast:
+      // Follow the bitcast.
       Instruction *MarkerAddr = nullptr;
       for (User *U : AI->users()) {
-        if (U->stripPointerCasts() == AI) {
+
+        if (U->stripInBoundsConstantOffsets() == AI) {
+          SinkLifeStart = false;
+          HoistLifeEnd = false;
           Instruction *Bitcast = cast<Instruction>(U);
-          if (GetLifeTimeMarkers(Bitcast)) {
+          Markers = GetLifeTimeMarkers(Bitcast, SinkLifeStart, HoistLifeEnd);
+          if (Markers.first) {
             MarkerAddr = Bitcast;
             continue;
           }
         }
+
+        // Found unknown use of AI.
         if (!definedInRegion(Blocks, U)) {
           MarkerAddr = nullptr;
           break;
         }
       }
+
       if (MarkerAddr) {
+        if (SinkLifeStart)
+          SinkCands.insert(Markers.first);
         if (!definedInRegion(Blocks, MarkerAddr))
           SinkCands.insert(MarkerAddr);
         SinkCands.insert(AI);
+        if (HoistLifeEnd)
+          HoistCands.insert(Markers.second);
       }
     }
   }
 }
 
 void CodeExtractor::findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
                                       const ValueSet &SinkCands) const {
 

       LLVMContext::MD_prof,
       MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));
 }
 
 Function *CodeExtractor::extractCodeRegion() {
   if (!isEligible())
     return nullptr;
 
-  ValueSet inputs, outputs, SinkingCands;
+  ValueSet inputs, outputs, SinkingCands, HoistingCands;
+  BasicBlock *CommonExit = nullptr;
 
   // Assumption: this is a single-entry code region, and the header is the first
   // block in the region.
   BasicBlock *header = *Blocks.begin();
 
   // Calculate the entry frequency of the new function before we change the root
   //   block.
   BlockFrequency EntryFreq;

                                                 header);
 
   // The new function needs a root node because other nodes can branch to the
   // head of the region, but the entry node of a function cannot have preds.
   BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(), 
                                                "newFuncRoot");
   newFuncRoot->getInstList().push_back(BranchInst::Create(header));
 
-  findAllocas(SinkingCands);
+  findAllocas(SinkingCands, HoistingCands, CommonExit);
+  assert(HoistingCands.empty() || CommonExit);
 
   // Find inputs to, outputs from the code region.
   findInputsOutputs(inputs, outputs, SinkingCands);
 
   // Now sink all instructions which only have non-phi uses inside the region
   for (auto *II : SinkingCands)
     cast<Instruction>(II)->moveBefore(*newFuncRoot,
                                       newFuncRoot->getFirstInsertionPt());
 
+  if (!HoistingCands.empty()) {
+    auto *HoistToBlock = findOrCreateBlockForHoisting(CommonExit);
+    Instruction *TI = HoistToBlock->getTerminator();
+    for (auto *II : HoistingCands)
+      cast<Instruction>(II)->moveBefore(TI);
+  }
+
   // Calculate the exit blocks for the extracted region and the total exit
   //  weights for each of those blocks.
   DenseMap<BasicBlock *, BlockFrequency> ExitWeights;
   SmallPtrSet<BasicBlock *, 1> ExitBlocks;
   for (BasicBlock *Block : Blocks) {
     for (succ_iterator SI = succ_begin(Block), SE = succ_end(Block); SI != SE;
          ++SI) {
       if (!Blocks.count(*SI)) {

test/Transforms/CodeExtractor/live_shrink.ll

+; RUN: opt  -partial-inliner  < %s |  | FileCheck %s
+; RUN: opt  -pass=partial-inliner  < %s |  | FileCheck %s
+
+%class.A = type { i32 }
+@cond = local_unnamed_addr global i32 0, align 4
+
+; Function Attrs: uwtable
+define void @_Z3foov() local_unnamed_addr  {
+bb:
+  %tmp = alloca %class.A, align 4
+  %tmp1 = bitcast %class.A* %tmp to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %tmp1)
+  %tmp2 = load i32, i32* @cond, align 4, !tbaa !2
+  %tmp3 = icmp eq i32 %tmp2, 0
+  br i1 %tmp3, label %bb4, label %bb5
+
+bb4:                                              ; preds = %bb
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  br label %bb5
+
+bb5:                                              ; preds = %bb4, %bb
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %tmp1)
+  ret void
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) 
+
+declare void @_ZN1A7memfuncEv(%class.A*) local_unnamed_addr 
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) 
+
+; Function Attrs: uwtable
+define void @_Z3goov() local_unnamed_addr  {
+; CHECK-LABEL: @_Z3goov()
+bb:
+; CHECK: bb:
+; CHECK-NOT: alloca
+; CHECK-NOT: bitcast
+; CHECK-NOT: llvm.lifetime
+; CHECK: br i1
+; CHECK: codeRepl.i:
+; CHECK: call void @_Z3foov.1_
+
+  tail call void @_Z3foov()
+  ret void
+}
+
+; CHECK-LABEL: define internal void @_Z3foov.1_
+; CHECK: newFuncRoot:
+; CHECK-NEXT:  %tmp = alloca %class.A
+; CHECK-NEXT:  %tmp1 = bitcast %class.A* %tmp to i8*
+; CHECK-NEXT:  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %tmp1)
+; CHECK:  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %tmp1)
+; CHECK-NEXT:  br label %bb5.exitStub
+
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 5.0.0 (trunk 304489)"}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C++ TBAA"}

test/Transforms/CodeExtractor/live_shrink_gep.ll

+; RUN: opt  -partial-inliner  < %s |  | FileCheck %s
+; RUN: opt  -pass=partial-inliner  < %s |  | FileCheck %s
+
+%class.A = type { i8 }
+
+@cond = local_unnamed_addr global i32 0, align 4
+
+; Function Attrs: uwtable
+define void @_Z3foov() local_unnamed_addr  {
+bb:
+  %tmp = alloca %class.A, align 1
+  %tmp1 = getelementptr inbounds %class.A, %class.A* %tmp, i64 0, i32 0
+  call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull %tmp1) 
+  %tmp2 = load i32, i32* @cond, align 4, !tbaa !2
+  %tmp3 = icmp eq i32 %tmp2, 0
+  br i1 %tmp3, label %bb4, label %bb5
+
+bb4:                                              ; preds = %bb
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  br label %bb5
+
+bb5:                                              ; preds = %bb4, %bb
+  call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull %tmp1) 
+  ret void
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) 
+
+declare void @_ZN1A7memfuncEv(%class.A*) local_unnamed_addr 
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) 
+
+; Function Attrs: uwtable
+define void @_Z3goov() local_unnamed_addr  {
+; CHECK-LABEL: @_Z3goov()
+bb:
+; CHECK: bb:
+; CHECK-NOT: alloca
+; CHECK-NOT: getelementptr
+; CHECK-NOT: llvm.lifetime
+; CHECK: br i1
+; CHECK: codeRepl.i:
+; CHECK: call void @_Z3foov.1_
+  tail call void @_Z3foov()
+  ret void
+}
+
+; CHECK-LABEL: define internal void @_Z3foov.1_
+; CHECK: newFuncRoot:
+; CHECK-NEXT:  %tmp = alloca %class.A
+; CHECK-NEXT:  %tmp1 = getelementptr
+; CHECK-NEXT:  call void @llvm.lifetime.start.p0i8
+; CHECK:  call void @llvm.lifetime.end.p0i8
+; CHECK-NEXT:  br label %bb5.exitStub
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 5.0.0 (trunk 304489)"}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C++ TBAA"}

test/Transforms/CodeExtractor/live_shrink_hoist.ll

+; RUN: opt  -partial-inliner -max-num-inline-blocks=2  < %s |  | FileCheck %s
+; RUN: opt  -pass=partial-inliner -max-num-inline-blocks=2  < %s |  | FileCheck %s
+
+%class.A = type { i32 }
+
+@cond = local_unnamed_addr global i32 0, align 4
+
+; Function Attrs: uwtable
+define void @_Z3foov() local_unnamed_addr  {
+bb:
+  %tmp = alloca %class.A, align 4
+  %tmp1 = bitcast %class.A* %tmp to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %tmp1) 
+  %tmp2 = load i32, i32* @cond, align 4, !tbaa !2
+  %tmp3 = icmp eq i32 %tmp2, 0
+  br i1 %tmp3, label %bb4, label %bb9
+
+bb4:                                              ; preds = %bb
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  %tmp5 = getelementptr inbounds %class.A, %class.A* %tmp, i64 0, i32 0
+  %tmp6 = load i32, i32* %tmp5, align 4, !tbaa !6
+  %tmp7 = icmp sgt i32 %tmp6, 0
+  br i1 %tmp7, label %bb9, label %bb8
+
+bb8:                                              ; preds = %bb4
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  br label %bb9
+
+bb9:                                              ; preds = %bb8, %bb4, %bb
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %tmp1) 
+  ret void
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) 
+
+declare void @_ZN1A7memfuncEv(%class.A*) local_unnamed_addr 
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) 
+
+; Function Attrs: uwtable
+define void @_Z3goov() local_unnamed_addr  {
+bb:
+  tail call void @_Z3foov()
+  ret void
+}
+
+; CHECK-LABEL: define internal void @_Z3foov.1_
+; CHECK: bb9:
+; CHECK: call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %tmp1)
+; CHECK:  br label %.exitStub
+
+
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 5.0.0 (trunk 304489)"}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C++ TBAA"}
+!6 = !{!7, !3, i64 0}
+!7 = !{!"_ZTS1A", !3, i64 0}

test/Transforms/CodeExtractor/live_shrink_multiple.ll

+; RUN: opt  -partial-inliner  < %s |  | FileCheck %s
+; RUN: opt  -pass=partial-inliner  < %s |  | FileCheck %s
+
+%class.A = type { i32 }
+@cond = local_unnamed_addr global i32 0, align 4
+
+; Function Attrs: uwtable
+define void @_Z3foov() local_unnamed_addr  {
+bb:
+  %tmp = alloca %class.A, align 4
+  %tmp1 = alloca %class.A, align 4
+  %tmp2 = bitcast %class.A* %tmp to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %tmp2) 
+  %tmp3 = bitcast %class.A* %tmp1 to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %tmp3) 
+  %tmp4 = load i32, i32* @cond, align 4, !tbaa !2
+  %tmp5 = icmp eq i32 %tmp4, 0
+  br i1 %tmp5, label %bb6, label %bb7
+
+bb6:                                              ; preds = %bb
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp1)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp1)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp1)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp1)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp1)
+  br label %bb7
+
+bb7:                                              ; preds = %bb6, %bb
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %tmp3) 
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %tmp2) 
+  ret void
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) 
+
+declare void @_ZN1A7memfuncEv(%class.A*) local_unnamed_addr 
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) 
+
+; Function Attrs: uwtable
+define void @_Z3goov() local_unnamed_addr  {
+bb:
+  tail call void @_Z3foov()
+  ret void
+}
+
+; CHECK-LABEL: define internal void @_Z3foov.1_
+; CHECK: newFuncRoot:
+; CHECK-NEXT:  alloca 
+; CHECK-NEXT:  bitcast 
+; CHECK-NEXT:  call void @llvm.lifetime.start.p0i8
+; CHECK-NEXT:  alloca
+; CHECK-NEXT:  bitcast 
+; CHECK-NEXT:  call void @llvm.lifetime.start.p0i8
+; CHECK:  call void @llvm.lifetime.end.p0i8
+; CHECK-NEXT:  call void @llvm.lifetime.end.p0i8
+; CHECK-NEXT:  br label {{.*}}exitStub
+
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 5.0.0 (trunk 304489)"}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C++ TBAA"}

test/Transforms/CodeExtractor/live_shrink_unsafe.ll

+; The expected behavior of this file is expected to change when partial
+; inlining legality check is enhanced.
+
+; RUN: opt  -partial-inliner -skip-partial-inlining-cost-analysis  < %s |  | FileCheck %s
+; RUN: opt  -pass=partial-inliner skip-partial-inlining-cost-analysis < %s |  | FileCheck %s
+
+%class.A = type { i32 }
+
+@cond = local_unnamed_addr global i32 0, align 4
+@condptr = external local_unnamed_addr global i32*, align 8
+
+; Function Attrs: uwtable
+define void @_Z3foo_unknown_mem_accessv() local_unnamed_addr  {
+bb:
+  %tmp = alloca %class.A, align 4
+  %tmp1 = alloca %class.A, align 4
+  %tmp2 = bitcast %class.A* %tmp to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %tmp2) 
+  %tmp3 = bitcast %class.A* %tmp1 to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %tmp3) 
+  %tmp4 = load i32*, i32** @condptr, align 8, !tbaa !2
+  %tmp5 = load i32, i32* %tmp4, align 4, !tbaa !6
+  %tmp6 = icmp eq i32 %tmp5, 0
+  br i1 %tmp6, label %bb7, label %bb8
+
+bb7:                                              ; preds = %bb
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp1)
+  br label %bb8
+
+bb8:                                              ; preds = %bb7, %bb
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %tmp3) 
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %tmp2) 
+  ret void
+}
+
+declare void @_Z3barv() local_unnamed_addr
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) 
+declare void @_ZN1A7memfuncEv(%class.A*) local_unnamed_addr 
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) 
+
+define void @_Z3foo_unknown_calli(i32 %arg) local_unnamed_addr {
+bb:
+  %tmp = alloca %class.A, align 4
+  %tmp1 = bitcast %class.A* %tmp to i8*
+  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %tmp1) 
+  tail call void @_Z3barv()
+  %tmp2 = icmp eq i32 %arg, 0
+  br i1 %tmp2, label %bb3, label %bb4
+
+bb3:                                              ; preds = %bb
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  call void @_ZN1A7memfuncEv(%class.A* nonnull %tmp)
+  br label %bb4
+
+bb4:                                              ; preds = %bb3, %bb
+  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %tmp1) 
+  ret void
+}
+
+define void @_Z3goov() local_unnamed_addr  {
+; CHECK-LABEL: @_Z3goov
+; CHECK-NEXT: bb:
+; CHECK: alloca
+; CHECK: lifetime
+bb:
+  call void @_Z3foo_unknown_mem_accessv()
+  %tmp = load i32, i32* @cond, align 4, !tbaa !2
+  tail call void @_Z3foo_unknown_calli(i32 %tmp)
+  ret void
+}
+
+; CHECK-LABEL define internal void @_Z3foo_unknown_calli.1_bb3
+; CHECK: newFuncRoot:
+; CHECK-NEXT: br label %bb3
+
+; CHECK: bb4.exitStub:
+; CHECK-NEXT: ret void
+
+; CHECK: bb3:
+; CHECK-NOT: lifetime.ed
+; CHECK: br label %bb4.exitStub
+
+
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 5.0.0 (trunk 304489)"}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"any pointer", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C++ TBAA"}
+!6 = !{!7, !7, i64 0}
+!7 = !{!"int", !4, i64 0}