[IRSim] Check largest sections first when analyzing similarity

[AndrewLitteken]

Summary

When we check for similarity, right now there is no order to how it is checked, except for via the suffix tree ordering.

We can reduce how much structural analysis we perform by checking the the regions in decreasing size. In doing so, we know that if two large sections match, each of their contained regions also match. This allows us to skip the structural checking for each smaller section. IT does require that we use the large regions as a "bridge" to create the canonical mapping between the two regions.

This reduces compile time significantly for some benchmarks. It will not perform as well for programs with many small items.

[AndrewLitteken]

exclude parent patch code

[paquette]

Can we add a statistic which calculates the average size of an outlinable region?

[AndrewLitteken]

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

1177

Oops, I missed these. I'll be sure to remove this.

[paquette]

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

859

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

1126

is there a call to empty() or something you could use here?

1148

does this need to be a copy? or could you use a reference?

1178

remove debug dumping code?

1254

Could this just be auto IdxIt = ...?

Also IdxIt could probably use a more descriptive name?

1259

I think CandA.getStartIdx() and CandA.getEndIdx() can be hoisted out of the loop into variables.

1273

The start index + end index for CandB can be hoisted out of this loop too.

1292

These could probably both be declared with auto too?

[paquette]

LGTM

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

public:
   /// \param ToSourceMapping - The mapping of value numbers from this candidate
   /// to \p SourceCand.
   /// \param FromSourceMapping - The mapping of value numbers from \p SoureCand
   /// to this candidate.
   void createCanonicalRelationFrom(
       IRSimilarityCandidate &SourceCand,
       DenseMap<unsigned, DenseSet<unsigned>> &ToSourceMapping,
       DenseMap<unsigned, DenseSet<unsigned>> &FromSourceMapping);
   
+  /// Create a mapping for the value numbering of the calling
+  /// IRSimilarityCandidate, to a different separate set of numbers, based on
+  /// the canonical ordering in \p SourceCand. These are defined based on the
+  /// found mappings in \p ToSourceMapping and \p FromSourceMapping.  Both of
+  /// these relationships should have the same information, just in opposite
+  /// directions.  Uses the \p OneToOne mapping from target candidate to \p
+  /// SourceCand GVNs to determine the mapping first for values with multiple
+  /// mappings.  This mapping is created by the ordering of operands in the
+  /// instruction they are first seen in the candidates.
+  ///
+  /// \param [in, out] SourceCand - The IRSimilarityCandidate to create a
+  /// canonical numbering from.
+  /// \param [in,out] OneToOne - A mapping of value numbers from candidate
+  /// \p A to candidate \B using the structure of the original instructions.
+  /// \param ToSourceMapping - The mapping of value numbers from this candidate
+  /// to \p SourceCand.
+  /// \param FromSourceMapping - The mapping of value numbers from \p SoureCand
+  /// to this candidate.
+  void createCanonicalRelationFrom(
+      IRSimilarityCandidate &SourceCand,
+      DenseMap<unsigned, unsigned> &OneToOne,
+      DenseMap<unsigned, DenseSet<unsigned>> &ToSourceMapping,
+      DenseMap<unsigned, DenseSet<unsigned>> &FromSourceMapping);
+  
+  /// Create a mapping for the value numbering of the calling
+  /// IRSimilarityCandidate, to a different separate set of numbers, based on
+  /// the canonical ordering in \p SourceCand. These are defined based on the
+  /// canonical mapping defined between \p SoureCandLarge and
+  /// \p TargetCandLarge.  These IRSimilarityCandidates are already structurally
+  /// similar, and fully encapsulate the IRSimilarityCandidates in question.
+  /// These are used as a "bridge" from the \p SourceCand to the target.
+  ///
+  /// \param [in, out] SourceCand - The IRSimilarityCandidate to create a
+  /// canonical numbering from.
+  /// \param SoureCandLarge - The IRSimilarityCandidate fully containing
+  /// \p SourceCand.
+  /// \param TargetCandLarge -  The IRSimilarityCandidate fully containing
+  /// this Candidate.
+  void createCanonicalRelationFrom(
+      IRSimilarityCandidate &SourceCand,
+      IRSimilarityCandidate &SourceCandLarge,
+      IRSimilarityCandidate &TargetCandLarge);
+
   /// \param [in,out] BBSet - The set to track the basic blocks.
   void getBasicBlocks(DenseSet<BasicBlock *> &BBSet) const {
     for (IRInstructionData &ID : *this) {
       BasicBlock *BB = ID.Inst->getParent();
       BBSet.insert(BB);
     }
   }
 

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

for (BasicBlock *BB : BBSet) {
     BasicBlock *SourceBB = cast<Instruction>(SourceV)->getParent();
     unsigned SourceBBGVN = *SourceCand.getGVN(SourceBB);
     unsigned SourceCanonBBGVN = *SourceCand.getCanonicalNum(SourceBBGVN);
     CanonNumToNumber.insert(std::make_pair(SourceCanonBBGVN, BBGVNForCurrCand));
     NumberToCanonNum.insert(std::make_pair(BBGVNForCurrCand, SourceCanonBBGVN));
   }
 }
 
+void IRSimilarityCandidate::createCanonicalRelationFrom(
+    IRSimilarityCandidate &SourceCand, IRSimilarityCandidate &SourceCandLarge,
+    IRSimilarityCandidate &TargetCandLarge) {
+  assert(!SourceCand.CanonNumToNumber.empty() &&
+         "Canonical Relationship is non-empty");
+  assert(!SourceCand.NumberToCanonNum.empty() &&
+         "Canonical Relationship is non-empty");
+
+  assert(!SourceCandLarge.CanonNumToNumber.empty() &&
+         "Canonical Relationship is non-empty");
+  assert(!SourceCandLarge.NumberToCanonNum.empty() &&
+         "Canonical Relationship is non-empty");
+  
+  assert(!TargetCandLarge.CanonNumToNumber.empty() &&
+         "Canonical Relationship is non-empty");
+  assert(!TargetCandLarge.NumberToCanonNum.empty() &&
+         "Canonical Relationship is non-empty");
+
+  assert(CanonNumToNumber.empty() && "Canonical Relationship is non-empty");
+  assert(NumberToCanonNum.empty() && "Canonical Relationship is non-empty");
+
+  // We're going to use the larger candidates as a "bridge" to create the
+  // canonical number for the target candidate since we have idetified two
+  // candidates as subsequences of larger sequences, and therefore must be
+  // structurally similar.
+  for (std::pair<Value *, unsigned> &ValueNumPair : ValueToNumber) {
+    Value *CurrVal = ValueNumPair.first;
+    unsigned TargetCandGVN = ValueNumPair.second;
+
+    // Find the numbering in the large candidate that surrounds the 
+    // current candidate.
+    std::optional<unsigned> OLargeTargetGVN = TargetCandLarge.getGVN(CurrVal);
+    assert(OLargeTargetGVN.has_value() && "GVN not found for Value");
+
+    // Get the canonical numbering in the large target candidate.
+    std::optional<unsigned> OTargetCandCanon =
+        TargetCandLarge.getCanonicalNum(OLargeTargetGVN.value());
+    assert(OTargetCandCanon.has_value() &&
+           "Canononical Number not found for GVN");
+    
+    // Get the GVN in the large source candidate from the canonical numbering.
+    std::optional<unsigned> OLargeSourceGVN =
+        SourceCandLarge.fromCanonicalNum(OTargetCandCanon.value());
+    assert(OLargeSourceGVN.has_value() &&
+           "GVN Number not found for Canonical Number");
+    
+    // Get the Value from the GVN in the large source candidate.
+    std::optional<Value *> OLargeSourceV =
+        SourceCandLarge.fromGVN(OLargeSourceGVN.value());
+    assert(OLargeSourceV.has_value() && "Value not found for GVN");
+
+    // Get the GVN number for the Value in the source candidate.
+    std::optional<unsigned> OSourceGVN =
+        SourceCand.getGVN(OLargeSourceV.value());
+    assert(OSourceGVN.has_value() && "GVN Number not found for Value");
+
+    // Get the canonical numbering from the GVN/
+    std::optional<unsigned> OSourceCanon =
+        SourceCand.getCanonicalNum(OSourceGVN.value());
+    assert(OSourceCanon.has_value() && "Canon Number not found for GVN");
+
+    // Insert the canonical numbering and GVN pair into their respective
+    // mappings.
+    CanonNumToNumber.insert(
+        std::make_pair(OSourceCanon.value(), TargetCandGVN));
+    NumberToCanonNum.insert(
+        std::make_pair(TargetCandGVN, OSourceCanon.value()));
+  }
+}
+
 void IRSimilarityCandidate::createCanonicalMappingFor(
     IRSimilarityCandidate &CurrCand) {
   assert(CurrCand.CanonNumToNumber.size() == 0 &&
          "Canonical Relationship is non-empty");
   assert(CurrCand.NumberToCanonNum.size() == 0 &&
          "Canonical Relationship is non-empty");
 
   unsigned CanonNum = 0;
   // Iterate over the value numbers found, the order does not matter in this
   // case.
   for (std::pair<unsigned, Value *> &NumToVal : CurrCand.NumberToValue) {
     CurrCand.NumberToCanonNum.insert(std::make_pair(NumToVal.first, CanonNum));
     CurrCand.CanonNumToNumber.insert(std::make_pair(CanonNum, NumToVal.first));
     CanonNum++;
   }
 }
 
+/// Look for larger IRSimilarityCandidates From the previously matched
+/// IRSimilarityCandidates that fully contain \p CandA or \p CandB.  If there is
+/// an overlap, return a pair of structurally similar, larger
+/// IRSimilarityCandidates.
+///
+/// \param [in] CandA - The first candidate we are trying to determine the
+/// structure of.
+/// \param [in] CandB - The second candidate we are trying to determine the
+/// structure of.
+/// \param [in] IndexToIncludedCand - Mapping of index of the an instruction in
+/// a circuit to the IRSimilarityCandidates that include this instruction.
+/// \param [in] CandToOverallGroup - Mapping of IRSimilarityCandidate to a
+/// number representing the structural group assigned to it.
+static std::optional<
+    std::pair<IRSimilarityCandidate *, IRSimilarityCandidate *>>
+CheckLargerCands(
+    IRSimilarityCandidate &CandA, IRSimilarityCandidate &CandB,
+    DenseMap<unsigned, DenseSet<IRSimilarityCandidate *>> &IndexToIncludedCand,
+    DenseMap<IRSimilarityCandidate *, unsigned> &CandToGroup) {
+  DenseMap<unsigned, IRSimilarityCandidate *> IncludedGroupAndCandA;
+  DenseMap<unsigned, IRSimilarityCandidate *> IncludedGroupAndCandB;
+  DenseSet<unsigned> IncludedGroupsA;
+  DenseSet<unsigned> IncludedGroupsB;
+
+  // Find the overall similarity group numbers that fully contain the candidate,
+  // and record the larger candidate for each group.
+  auto IdxToCandidateIt = IndexToIncludedCand.find(CandA.getStartIdx());
+  std::optional<std::pair<IRSimilarityCandidate *, IRSimilarityCandidate *>>
+      Result;
+
+  unsigned CandAStart = CandA.getStartIdx();
+  unsigned CandAEnd = CandA.getEndIdx();
+  unsigned CandBStart = CandB.getStartIdx();
+  unsigned CandBEnd = CandB.getEndIdx();
+  if (IdxToCandidateIt == IndexToIncludedCand.end())
+    return Result;
+  for (IRSimilarityCandidate *MatchedCand : IdxToCandidateIt->second) {
+    if (MatchedCand->getStartIdx() > CandAStart ||
+        (MatchedCand->getEndIdx() < CandAEnd))
+      continue;
+    unsigned GroupNum = CandToGroup.find(MatchedCand)->second;
+    IncludedGroupAndCandA.insert(std::make_pair(GroupNum, MatchedCand));
+    IncludedGroupsA.insert(GroupNum);
+  }
+
+  // Find the overall similarity group numbers that fully contain the next
+  // candidate, and record the larger candidate for each group.
+  IdxToCandidateIt = IndexToIncludedCand.find(CandBStart);
+  if (IdxToCandidateIt == IndexToIncludedCand.end())
+    return Result;
+  for (IRSimilarityCandidate *MatchedCand : IdxToCandidateIt->second) {
+    if (MatchedCand->getStartIdx() > CandBStart ||
+        MatchedCand->getEndIdx() < CandBEnd)
+      continue;
+    unsigned GroupNum = CandToGroup.find(MatchedCand)->second;
+    IncludedGroupAndCandB.insert(std::make_pair(GroupNum, MatchedCand));
+    IncludedGroupsB.insert(GroupNum);
+  }
+
+  // Find the intersection between the two groups, these are the groups where
+  // the larger candidates exist.
+  set_intersect(IncludedGroupsA, IncludedGroupsB);
+
+  // If there is no intersection between the sets, then we cannot determine
+  // whether or not there is a match.
+  if (IncludedGroupsA.empty())
+    return Result;
+  
+  // Create a pair that contains the larger candidates.
+  auto ItA = IncludedGroupAndCandA.find(*IncludedGroupsA.begin());
+  auto ItB = IncludedGroupAndCandB.find(*IncludedGroupsA.begin());
+  Result = std::make_pair(ItA->second, ItB->second);
+  return Result;
+}
+
 /// From the list of IRSimilarityCandidates, perform a comparison between each
 /// IRSimilarityCandidate to determine if there are overlapping
 /// IRInstructionData, or if they do not have the same structure.
 ///
 /// \param [in] CandsForRepSubstring - The vector containing the
 /// IRSimilarityCandidates.
 /// \param [out] StructuralGroups - the mapping of unsigned integers to vector
 /// of IRSimilarityCandidates where each of the IRSimilarityCandidates in the
 /// vector are structurally similar to one another.
+/// \param [in] IndexToIncludedCand - Mapping of index of the an instruction in
+/// a circuit to the IRSimilarityCandidates that include this instruction.
+/// \param [in] CandToOverallGroup - Mapping of IRSimilarityCandidate to a
+/// number representing the structural group assigned to it.
 static void findCandidateStructures(
     std::vector<IRSimilarityCandidate> &CandsForRepSubstring,
-    DenseMap<unsigned, SimilarityGroup> &StructuralGroups) {
+    DenseMap<unsigned, SimilarityGroup> &StructuralGroups,
+    DenseMap<unsigned,  DenseSet<IRSimilarityCandidate *>> &IndexToIncludedCand,
+    DenseMap<IRSimilarityCandidate *, unsigned> &CandToOverallGroup
+    ) {
   std::vector<IRSimilarityCandidate>::iterator CandIt, CandEndIt, InnerCandIt,
       InnerCandEndIt;
 
   // IRSimilarityCandidates each have a structure for operand use.  It is
   // possible that two instances of the same subsequences have different
   // structure. Each type of structure found is assigned a number.  This
   // DenseMap maps an IRSimilarityCandidate to which type of similarity
   // discovered it fits within.
   DenseMap<IRSimilarityCandidate *, unsigned> CandToGroup;
 
   // Find the compatibility from each candidate to the others to determine
   // which candidates overlap and which have the same structure by mapping
   // each structure to a different group.
   bool SameStructure;
   bool Inserted;
   unsigned CurrentGroupNum = 0;
for (InnerCandIt = std::next(CandIt),
         InnerCandEndIt = CandsForRepSubstring.end();
          InnerCandIt != InnerCandEndIt; InnerCandIt++) {
 
       // We check if the inner item has a group already, if it does, we skip it.
       CandToGroupItInner = CandToGroup.find(&*InnerCandIt);
       if (CandToGroupItInner != CandToGroup.end())
         continue;
 
+      // Check if we have found structural similarity between two candidates
+      // that fully contains the first and second candidates.
+      std::optional<std::pair<IRSimilarityCandidate *, IRSimilarityCandidate *>>
+          LargerPair = CheckLargerCands(
+              *CandIt, *InnerCandIt, IndexToIncludedCand, CandToOverallGroup);
+
+      // If a pair was found, it means that we can assume that these smaller
+      // substrings are also structurally similar.  Use the larger candidates to
+      // determine the canonical mapping between the two sections.
+      if (LargerPair.has_value()) {
+        SameStructure = true;
+        InnerCandIt->createCanonicalRelationFrom(
+            *CandIt, *LargerPair.value().first, *LargerPair.value().second);
+        CandToGroup.insert(std::make_pair(&*InnerCandIt, OuterGroupNum));
+        CurrentGroupPair->second.push_back(*InnerCandIt);
+        continue;
+      }
+
       // Otherwise we determine if they have the same structure and add it to
       // vector if they match.
       ValueNumberMappingA.clear();
       ValueNumberMappingB.clear();
       SameStructure = IRSimilarityCandidate::compareStructure(
           *CandIt, *InnerCandIt, ValueNumberMappingA, ValueNumberMappingB);
       if (!SameStructure)
         continue;
void IRSimilarityIdentifier::findCandidates(
     std::vector<IRInstructionData *> &InstrList,
     std::vector<unsigned> &IntegerMapping) {
   SuffixTree ST(IntegerMapping);
 
   std::vector<IRSimilarityCandidate> CandsForRepSubstring;
   std::vector<SimilarityGroup> NewCandidateGroups;
 
   DenseMap<unsigned, SimilarityGroup> StructuralGroups;
+  DenseMap<unsigned, DenseSet<IRSimilarityCandidate *>> IndexToIncludedCand;
+  DenseMap<IRSimilarityCandidate *, unsigned> CandToGroup; 
 
   // Iterate over the subsequences found by the Suffix Tree to create
   // IRSimilarityCandidates for each repeated subsequence and determine which
   // instances are structurally similar to one another.
-  for (SuffixTree::RepeatedSubstring &RS : ST) {
+
+  // Sort the suffix tree from longest substring to shortest.
+  std::vector<SuffixTree::RepeatedSubstring> RSes;
+  for (SuffixTree::RepeatedSubstring &RS : ST)
+    RSes.push_back(RS);
+
+  llvm::stable_sort(RSes, [](const SuffixTree::RepeatedSubstring &LHS,
+                             const SuffixTree::RepeatedSubstring &RHS) {
+    return LHS.Length > RHS.Length;
+  });
+  for (SuffixTree::RepeatedSubstring &RS : RSes) {
     createCandidatesFromSuffixTree(Mapper, InstrList, IntegerMapping, RS,
                                    CandsForRepSubstring);
 
     if (CandsForRepSubstring.size() < 2)
       continue;
 
-    findCandidateStructures(CandsForRepSubstring, StructuralGroups);
-    for (std::pair<unsigned, SimilarityGroup> &Group : StructuralGroups)
+    findCandidateStructures(CandsForRepSubstring, StructuralGroups,
+                            IndexToIncludedCand, CandToGroup);
+    for (std::pair<unsigned, SimilarityGroup> &Group : StructuralGroups) {
       // We only add the group if it contains more than one
       // IRSimilarityCandidate.  If there is only one, that means there is no
       // other repeated subsequence with the same structure.
-      if (Group.second.size() > 1)
+      if (Group.second.size() > 1) {
         SimilarityCandidates->push_back(Group.second);
+        // Iterate over each candidate in the group, and add an entry for each
+        // instruction included with a mapping to a set of
+        // IRSimilarityCandidates that include that instruction.
+        for (IRSimilarityCandidate &IRCand : SimilarityCandidates->back()) {
+          for (unsigned Idx = IRCand.getStartIdx(), Edx = IRCand.getEndIdx();
+               Idx <= Edx; ++Idx) {
+            DenseMap<unsigned, DenseSet<IRSimilarityCandidate *>>::iterator
+                IdIt;
+            IdIt = IndexToIncludedCand.find(Idx);
+            bool Inserted = false;
+            if (IdIt == IndexToIncludedCand.end())
+              std::tie(IdIt, Inserted) = IndexToIncludedCand.insert(
+                  std::make_pair(Idx, DenseSet<IRSimilarityCandidate *>()));
+            IdIt->second.insert(&IRCand);
+          }
+          // Add mapping of candidate to the overall similarity group number.
+          CandToGroup.insert(
+              std::make_pair(&IRCand, SimilarityCandidates->size() - 1));
+        }
+      }
+    }
 
     CandsForRepSubstring.clear();
     StructuralGroups.clear();
     NewCandidateGroups.clear();
   }
 }
 
 SimilarityGroupList &IRSimilarityIdentifier::findSimilarity(

llvm/test/Transforms/IROutliner/illegal-assumes.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S -passes=verify,iroutliner -ir-outlining-no-cost < %s | FileCheck %s
+; RUN: opt -S -p iroutliner,verify -ir-outlining-no-cost < %s | FileCheck %s
 
 ; This test ensures that we do not include llvm.assumes.  There are exceptions
 ; in the CodeExtractor's algorithm for llvm.assumes, so we ignore it for now.
 
 define void @outline_assumes() {
 ; CHECK-LABEL: @outline_assumes(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[DL_LOC:%.*]] = alloca i1, align 1
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[C:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[D:%.*]] = alloca i1, align 4
 ; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 -1, ptr [[DL_LOC]])
-; CHECK-NEXT:    call void @outlined_ir_func_3(i1 true, ptr [[D]], ptr [[DL_LOC]])
+; CHECK-NEXT:    call void @outlined_ir_func_4(i1 true, ptr [[D]], ptr [[DL_LOC]])
 ; CHECK-NEXT:    [[DL_RELOAD:%.*]] = load i1, ptr [[DL_LOC]], align 1
 ; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 -1, ptr [[DL_LOC]])
 ; CHECK-NEXT:    [[SPLIT_INST:%.*]] = sub i1 [[DL_RELOAD]], [[DL_RELOAD]]
-; CHECK-NEXT:    call void @outlined_ir_func_0(ptr [[A]], ptr [[B]], ptr [[C]])
-; CHECK-NEXT:    call void @llvm.assume(i1 [[DL_RELOAD]])
 ; CHECK-NEXT:    call void @outlined_ir_func_1(ptr [[A]], ptr [[B]], ptr [[C]])
+; CHECK-NEXT:    call void @llvm.assume(i1 [[DL_RELOAD]])
+; CHECK-NEXT:    call void @outlined_ir_func_2(ptr [[A]], ptr [[B]], ptr [[C]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a = alloca i32, align 4
   %b = alloca i32, align 4
   %c = alloca i32, align 4
   %d = alloca i1, align 4
   store i1 1, ptr %d, align 4

 ; CHECK-LABEL: @outline_assumes2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[DL_LOC:%.*]] = alloca i1, align 1
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[C:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[D:%.*]] = alloca i1, align 4
 ; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 -1, ptr [[DL_LOC]])
-; CHECK-NEXT:    call void @outlined_ir_func_3(i1 false, ptr [[D]], ptr [[DL_LOC]])
+; CHECK-NEXT:    call void @outlined_ir_func_4(i1 false, ptr [[D]], ptr [[DL_LOC]])
 ; CHECK-NEXT:    [[DL_RELOAD:%.*]] = load i1, ptr [[DL_LOC]], align 1
 ; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 -1, ptr [[DL_LOC]])
-; CHECK-NEXT:    call void @outlined_ir_func_0(ptr [[A]], ptr [[B]], ptr [[C]])
-; CHECK-NEXT:    call void @llvm.assume(i1 [[DL_RELOAD]])
 ; CHECK-NEXT:    call void @outlined_ir_func_1(ptr [[A]], ptr [[B]], ptr [[C]])
+; CHECK-NEXT:    call void @llvm.assume(i1 [[DL_RELOAD]])
+; CHECK-NEXT:    call void @outlined_ir_func_2(ptr [[A]], ptr [[B]], ptr [[C]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a = alloca i32, align 4
   %b = alloca i32, align 4
   %c = alloca i32, align 4
   %d = alloca i1, align 4
   store i1 0, ptr %d, align 4
   %dl = load i1, ptr %d
   store i32 2, ptr %a, align 4
   store i32 3, ptr %b, align 4
   store i32 4, ptr %c, align 4
   call void @llvm.assume(i1 %dl)
   %al = load i32, ptr %a
   %bl = load i32, ptr %b
   %cl = load i32, ptr %c
   ret void
 }
 
 define void @outline_assumes3() {
 ; CHECK-LABEL: @outline_assumes3(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[DL_LOC:%.*]] = alloca i1, align 1
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[C:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[D:%.*]] = alloca i1, align 4
-; CHECK-NEXT:    store i1 true, ptr [[D]], align 4
-; CHECK-NEXT:    [[DL:%.*]] = load i1, ptr [[D]], align 1
-; CHECK-NEXT:    [[SPLIT_INST:%.*]] = add i1 [[DL]], [[DL]]
-; CHECK-NEXT:    call void @outlined_ir_func_0(ptr [[A]], ptr [[B]], ptr [[C]])
-; CHECK-NEXT:    call void @llvm.assume(i1 [[DL]])
-; CHECK-NEXT:    call void @outlined_ir_func_2(ptr [[A]])
+; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 -1, ptr [[DL_LOC]])
+; CHECK-NEXT:    call void @outlined_ir_func_0(i1 true, ptr [[D]], ptr [[A]], ptr [[B]], ptr [[C]], ptr [[DL_LOC]])
+; CHECK-NEXT:    [[DL_RELOAD:%.*]] = load i1, ptr [[DL_LOC]], align 1
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 -1, ptr [[DL_LOC]])
+; CHECK-NEXT:    call void @llvm.assume(i1 [[DL_RELOAD]])
+; CHECK-NEXT:    call void @outlined_ir_func_3(ptr [[A]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a = alloca i32, align 4
   %b = alloca i32, align 4
   %c = alloca i32, align 4
   %d = alloca i1, align 4
   store i1 1, ptr %d, align 4
   %dl = load i1, ptr %d
   %split_inst = add i1 %dl, %dl
   store i32 2, ptr %a, align 4
   store i32 3, ptr %b, align 4
   store i32 4, ptr %c, align 4
   call void @llvm.assume(i1 %dl)
   %al = load i32, ptr %a
   %bl = add i32 %al, %al
   ret void
 }
 
 define void @outline_assumes4() {
 ; CHECK-LABEL: @outline_assumes4(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[DL_LOC:%.*]] = alloca i1, align 1
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[C:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[D:%.*]] = alloca i1, align 4
-; CHECK-NEXT:    store i1 false, ptr [[D]], align 4
-; CHECK-NEXT:    [[DL:%.*]] = load i1, ptr [[D]], align 1
-; CHECK-NEXT:    [[SPLIT_INST:%.*]] = add i1 [[DL]], [[DL]]
-; CHECK-NEXT:    call void @outlined_ir_func_0(ptr [[A]], ptr [[B]], ptr [[C]])
-; CHECK-NEXT:    call void @llvm.assume(i1 [[DL]])
-; CHECK-NEXT:    call void @outlined_ir_func_2(ptr [[A]])
+; CHECK-NEXT:    call void @llvm.lifetime.start.p0(i64 -1, ptr [[DL_LOC]])
+; CHECK-NEXT:    call void @outlined_ir_func_0(i1 false, ptr [[D]], ptr [[A]], ptr [[B]], ptr [[C]], ptr [[DL_LOC]])
+; CHECK-NEXT:    [[DL_RELOAD:%.*]] = load i1, ptr [[DL_LOC]], align 1
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0(i64 -1, ptr [[DL_LOC]])
+; CHECK-NEXT:    call void @llvm.assume(i1 [[DL_RELOAD]])
+; CHECK-NEXT:    call void @outlined_ir_func_3(ptr [[A]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a = alloca i32, align 4
   %b = alloca i32, align 4
   %c = alloca i32, align 4
   %d = alloca i1, align 4
   store i1 0, ptr %d, align 4