Hoist/sink malloc/free's in LICM.

[nicholas]

Summary

Hoist/sink malloc/free's in LICM.

Adds a new method on Instruction that answers the query of whether the given Instruction might allocate or free memory. Unlike builtin info which answers whether they are an allocation/deallocation call, this method indicates whether allocation behaviour is possible.

Adds a new analysis on loops called LoopAllocationInfo. This is tightly tied to the internal implementation of LICM, but is exposed in a public API because the relevant parts of LICM's externals, hoistRegion and sinkRegion, are also a public API.

One potentially surprising aspect of this optimization is that it is correct even if the loop exits in the middle, after the malloc and before the free. As long as there is only one live malloc at a time, there is no visible difference in behaviour. It is sufficient to show that we've found free() calls which cover all possible access to the loop backedge (the other option is that the code had a pre-existing double-free, which is undefined behaviour). The loop may thus exit with the malloc either allocated or freed, and we track which loop exits blocks should have frees added to them and which ones should not.

[asbirlea]

A couple of quick comments.
Would you mind splitting the cleanups and bug fix (which will be straightforward to approve) and rebase this on top of that?

llvm/include/llvm/Analysis/LoopAllocationInfo.h

29

Could you include the comment from the description here? "This analysis is tightly coupled to the internal implementation of the LICM transform."

llvm/test/Transforms/LICM/allocs.ll

2

Could you also add a RUN line with -enable-mssa-loop-dependency?

[reames]

I've only skimmed through the high level comments so far, so if if any of this is addressed inline, just say so.

I was wondering why you phrased this as a combination of hoisting and sinking as opposed to promotion. We have the scalar promotion path, and the basic transform you're doing feels a lot like promotion. I suspect that many of the legality aspects will be common.

llvm/include/llvm/IR/Instruction.h

539

These feel like they need a bit more specification. In particular, are there any expectations around how new memory is returned? Is a deallocation routine allowed to free a random pointer read from a global?

(i.e. which set of locations are we talking about freeing and allocating?)

llvm/lib/IR/Instruction.cpp

562

Err, using a blacklist here feels *really* dangerous.

[nicholas]

I've only skimmed through the high level comments so far, so if if any of this is addressed inline, just say so.

I was wondering why you phrased this as a combination of hoisting and sinking as opposed to promotion. We have the scalar promotion path, and the basic transform you're doing feels a lot like promotion. I suspect that many of the legality aspects will be common.

I didn't frame it as promotion simply because I view promotion as a transform from one thing to another (such as heap to stack, stack to scalar) whereas this optimization was just hoisting out the allocation and sinking the matching deallocations.

The safety checks we need are "is there a path from this malloc back to this malloc without passing through one of the frees we identified?" and "for each exit block, can we see that all paths either pass through one-or-more frees or that all paths do not pass through any frees?". We have no need of MemorySSA or AliasSets like the memory-to-scalar promotion does.

Comparing this code with LICM's promotion does reveal one bug. We might try to insert into catchswitch blocks.

Should I pull it out of hoisting and sinking and into a post-pass like LICM's scalar promotion? Initially I had imagined that it would participate in hoist and sink's queries of whether "are all arguments to this instruction loop invariant (outside the loop)" as hoists instructions iterately, it would hoist malloc like any other instruction. In practice that couldn't happen because the hoist is deferred until sink time. We do need the malloc hoist to occur after hoistRegion in order to make the malloc size argument invariant. So, maybe there's no reason not to place it after hoist and sink? We currently piggy-back on hoist and sink's linear scans, but doing them again is merely a constant factor. It would eliminate the need to expose LoopAllocationInfo as a public interface, which is a benefit.

llvm/include/llvm/IR/Instruction.h

539

Acknowledged.

These exist to help us maintain a C++-language invariant that we may not increase the total amount of heap memory in use, so, malloc+free+malloc may not be transformed into malloc+malloc+free. We simply need to avoid moving memory allocations around each other (though we can sort a continuous block of memory allocations if there's no frees in between). As such, there's no consideration of how the allocated memory would be returned or which memory gets deallocated (similar to how mayReadOrWriteMemory doesn't). We also don't really talk about what happens when an intrinsic allocates and deallocates internally, I think ultimately whether the intrinsic wants to be treated as something we can move other allocation/deallocation operations around should be left to the intrinsic author. It may not matter to the Objective-C runtime for instance. (But what about Objective-C++?)

I think this will end up getting resolved when we address your comments on llvm/lib/IR/Instruction.cpp:562.

llvm/lib/IR/Instruction.cpp

562

Uhh, you aren't suggesting that I actually list them all, right?

The reason I put it here in Instruction instead of hidden away in LICM/LoopAllocationInfo is to make it somewhat clearer that this is a global property that you'll need to update when adding an instruction or intrinsic.

How about if we update Intrinsics.td to include a Mallocs and Frees (similar to Throws) IntrinsicProperty? That makes it opt-in when declaring the intrinsic? (Speaking of which, why Throws and not IntrThrows? Should mine be IntrMallocs/IntrFrees or Mallocs/Frees?)

Also, can a readnone function malloc? Is there any way we could make this stricter?

[nicholas]

In D60056#1450884, @nicholas wrote:

Should I pull it out of hoisting and sinking and into a post-pass like LICM's scalar promotion? Initially I had imagined that it would participate in hoist and sink's queries of whether "are all arguments to this instruction loop invariant (outside the loop)" as hoists instructions iterately, it would hoist malloc like any other instruction. In practice that couldn't happen because the hoist is deferred until sink time.

Er, I'm mistaken. It does, because sinkRegion happens first and doesn't call isLoopInvariant, then hoistRegion happens second and that uses isLoopInvariant. So in theory if you have something like ptrtoint of the malloc (maybe an alignment check?), we could hoist that out of the loop too. So it does interlace with the rest of hoistRegion, and that's important for optimization power. I'll add a test to that effect shortly.

[nicholas]

Fixed creation of invalid IR when the loop exit block we need to insert a free call in, is a catchswitch block.

[reames]

llvm/lib/Analysis/LoopAllocationInfo.cpp

93

As discussed offline, bug example:
for (int i = 0; i < N; i++) {

throw_if(requested_size > TOO_BIG);
a = malloc(requested_size);
free(a);

}

[reames]

Other items discussed offline:

• the instruction usage feels to generic with too few uses. I suggested (but will not require) either making them computed properties of an intrinsic, or finding other uses.
• my comment about using a blacklist is clearly wrong. You'd suggested using an attribute in Instrinsics.td. I was fine with that, but it felt like possible overkill.

llvm/include/llvm/Analysis/LoopAllocationInfo.h

92

It really looks like you have a named tuple hidding here.

AllocationInfoEntry?

llvm/lib/Transforms/Scalar/LICM.cpp

857

As debated offline, naming here is problematic.

• addDeallocations -> locationsNeedingFrees? newAllocPlacement?
• toSink -> freesForMalloc

(key piece: avoid action names)

A comment would be help as well.

Pull out the cast to CallInst

860

You might wish to either a) union the source locations, or b) restrict this to non -g

See applyMergedLocation on Instruction.

[reames]

minor comments on interface, LICM part, and tests. I got interrupted and need to come back and finish reviewing the analysis implementation.

llvm/include/llvm/Analysis/LoopAllocationInfo.h

78

either "may ... ?" or "return true if ...". (i.e make a question a question)

83

Should we assert that CI is a malloc within the specified loop?

107

Not sure what the last part of the comment means. Reword?

llvm/lib/Transforms/Scalar/LICM.cpp

535

What about invokes? (Use callbase)

llvm/test/Transforms/LICM/allocs.ll

568

This test is odd. I don't see anything preventing us from reordering the volatile load and malloc. Was this an attempt to test for a side exit? If so, simply using an unknown call before the malloc would be preferred.

[nicholas]

llvm/include/llvm/Analysis/LoopAllocationInfo.h

78

Done, used "return true iff".

83

We don't presently store the right member variables to assert that, and I don't really want to add DEBUG-only member variables. The condition on this function is that mayHoist(CI) must be true. I've added an assert that CI is in entries, which is the condition under which this function would have UB.

llvm/lib/Analysis/LoopAllocationInfo.cpp

93

I've updated this to use isGuaranteedToTransferExecutionToSuccessor on the instructions leading up to the allocation. The "throw_if" example couldn't happen because any opaque function might also malloc or free, so the test @test16 uses a volatile load instead.

llvm/lib/Transforms/Scalar/LICM.cpp

497

Rename this to something clearer, such as "ScanForFrees".

535

Done.

This loop skips the terminator, so it can't be an invoke.

Which is, indeed, a miscompile bug. Fixed above where we initialize ScanForFrees and added @test19.

Changed it to CallBase here anyways.

857

Is picking the first one out of toSink/freesForMalloc a problem? The order depends on the use-list ordering. I don't know what LLVM's current rules on that are, I know that there's https://llvm.org/docs/LangRef.html#use-list-order-directives . Is it considered a bug to have an optimization whose result depends on use list order?

857

Is it possible for a free call to have an operand bundle on a malloc or free call? In CloneInstructionInExitBlock, LICM updates the funclet operand bundle for the new location in the CFG.

llvm/test/Transforms/LICM/allocs.ll

568

This test shows the difference from using isGuaranteedToTranferExecution in analyzeLoop. Before that change, we would have hoisted the malloc above the volatile load. The same test written with a function would not have shown any difference simply because there is no way to create a function that might-throw but can't-malloc/free (without adding new attributes to LLVM). It would also just be @test3 again.

I think the new behaviour tested for here is correct. Suppose you have a system where out of memory terminates the program, and the volatile store is triggering some external action (moves the robot arm). Suppose the programmer is using volatile to make sure the external system is in the safe state before doing the malloc that may terminate, and wants the malloc to complete before beginning any more operations. The compiler should not reorder these actions.

[nicholas]

This update adds a failing test @test21 which demonstrates a miscompile. While we check the block with the free in it for potentially-malloc'ing instructions, we don't examine all the possible paths from where that free was pre-transform to the new location of the free post-transform.

It's not immediately clear to me how to fix that efficiently. It's possible to label each loop block with whether it contains a potentially-malloc'ing instruction, then find all paths from frees to exit blocks which will have frees added to them and do not pass through any backedge or back through the header. We can simplify this path scan, knowing that all exits reachable after the free call are exits where we will insert a free.

[reames]

Assumed inactive, cleaning out review list, please readd if needed.

llvm/include/llvm/Analysis/CFG.h

 
 /// Return true if the specified edge is a critical edge. Critical edges are
 /// edges from a block with multiple successors to a block with multiple
 /// predecessors.
 ///
 bool isCriticalEdge(const Instruction *TI, unsigned SuccNum,
                     bool AllowIdenticalEdges = false);
 
-/// Determine whether instruction 'To' is reachable from 'From',
-/// returning true if uncertain.
+/// Determine whether instruction 'To' is reachable from 'From', without passing
+/// through any blocks in ExclusionSet, returning true if uncertain.
 ///
 /// Determine whether there is a path from From to To within a single function.
 /// Returns false only if we can prove that once 'From' has been executed then
 /// 'To' can not be executed. Conservatively returns true.
 ///
 /// This function is linear with respect to the number of blocks in the CFG,
 /// walking down successors from From to reach To, with a fixed threshold.
 /// Using DT or LI allows us to answer more quickly. LI reduces the cost of
 /// an entire loop of any number of blocks to be the same as the cost of a
 /// single block. DT reduces the cost by allowing the search to terminate when
 /// we find a block that dominates the block containing 'To'. DT is most useful
 /// on branchy code but not loops, and LI is most useful on code with loops but
 /// does not help on branchy code outside loops.
-bool isPotentiallyReachable(const Instruction *From, const Instruction *To,
-                            const DominatorTree *DT = nullptr,
-                            const LoopInfo *LI = nullptr);
+bool isPotentiallyReachable(
+    const Instruction *From, const Instruction *To,
+    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet = nullptr,
+    const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
 
 /// Determine whether block 'To' is reachable from 'From', returning
 /// true if uncertain.
 ///
 /// Determine whether there is a path from From to To within a single function.
 /// Returns false only if we can prove that once 'From' has been reached then
 /// 'To' can not be executed. Conservatively returns true.
 bool isPotentiallyReachable(const BasicBlock *From, const BasicBlock *To,
                             const DominatorTree *DT = nullptr,
                             const LoopInfo *LI = nullptr);
 
 /// Determine whether there is at least one path from a block in
 /// 'Worklist' to 'StopBB', returning true if uncertain.
 ///
 /// Determine whether there is a path from at least one block in Worklist to
 /// StopBB within a single function. Returns false only if we can prove that
 /// once any block in 'Worklist' has been reached then 'StopBB' can not be
 /// executed. Conservatively returns true.
 bool isPotentiallyReachableFromMany(SmallVectorImpl<BasicBlock *> &Worklist,
                                     BasicBlock *StopBB,
                                     const DominatorTree *DT = nullptr,
                                     const LoopInfo *LI = nullptr);
 
+/// Determine whether there is at least one path from a block in
+/// 'Worklist' to 'StopBB' without passing through any blocks in
+/// 'ExclusionSet', returning true if uncertain.
+///
+/// Determine whether there is a path from at least one block in Worklist to
+/// StopBB within a single function without passing through any of the blocks
+/// in 'ExclusionSet'. Returns false only if we can prove that once any block
+/// in 'Worklist' has been reached then 'StopBB' can not be executed.
+/// Conservatively returns true.
+bool isPotentiallyReachableFromMany(
+    SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
+    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet,
+    const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr);
+
 /// Return true if the control flow in \p RPOTraversal is irreducible.
 ///
 /// This is a generic implementation to detect CFG irreducibility based on loop
 /// info analysis. It can be used for any kind of CFG (Loop, MachineLoop,
 /// Function, MachineFunction, etc.) by providing an RPO traversal (\p
 /// RPOTraversal) and the loop info analysis (\p LI) of the CFG. This utility
 /// function is only recommended when loop info analysis is available. If loop
 /// info analysis isn't available, please, don't compute it explicitly for this

llvm/include/llvm/Analysis/LoopAllocationInfo.h

+//===- LoopAllocationInfo.h - memory allocations inside loops ---*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LOOPALLOCATIONINFO_H
+#define LLVM_ANALYSIS_LOOPALLOCATIONINFO_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SmallVector.h"
+
+namespace llvm {
+
+class BasicBlock;
+class CallInst;
+class DominatorTree;
+class Loop;
+class LoopInfo;
+class TargetLibraryInfo;
+
+/// Track ptr = allocfn to one or more freefn(ptr) relationships within the
+/// loop.
+///
+/// This analysis stores information about allocation and deallocation calls
+/// where the pointer is only live within the loop.
+///
+/// An allocation must be both hoisted and sunk, or neither. LICM performs
+/// sinking first, then hoisting. As sinking and hoisting is performed, more
+/// instructions will appear to be loop invariant, making more opportunities.
+/// For this reason we split the analysis into two pieces:
+///   1. for a given pointer that is only live in the loop, retain a list its
+///      matching deallocating instructions.
+///   2. during sinking, if we would sink the deallocation, don't, but inform
+///      the LoopAllocationInfo. If all deallocations would have been sunk, and
+///      hoistSink would hoist the allocation, perform both the hoist and sink
+///      the various deallocation instructions.
+///
+/// We don't need guaranteed execution of any deallocation function during
+/// unwinding. Before this transformation, an unwind mid-loop would leak one
+/// pointer that was allocated at the start of the loop. After this
+/// transformation, it would leak the one pointer allocated before the loop
+/// began. There is no difference visible to the caller.
+///
+/// We do have to ensure that the maximum amount of allocated memory is not
+/// raised by this transformation. To ensure this, we stop looking for
+/// allocations after seeing an opaque function call. For example:
+///   loop_top:
+///     %ptr1 = call i8* @malloc(i32 %loop_invariant1)  ;; candidate
+///     %ptr2 = call i8* @malloc(i32 %loop_variant2)    ;; not candidate
+///     %ptr3 = call i8* @malloc(i32 %loop_invariant3)  ;; candidate
+///     call void @opaque()                             ;; stop scanning
+///     %ptr5 = call i8* @malloc(i32 %loop_invariant5)  ;; not candidate
+///
+/// The same idea applies in reverse order to @free calls at the loop exits:
+///   loop_exiting:
+///      call void @free(%ptr1)  ;; not candidate
+///      call void @opaque()     ;; stop scanning
+///      call void @free(%ptr2)  ;; %ptr2 is candidate
+///                              ;; start here and scan upwards
+class LoopAllocationInfo {
+public:
+  void analyzeLoop(LoopInfo *LI, DominatorTree *DT, TargetLibraryInfo *TLI,
+                   Loop *CurLoop);
+
+  // sinkRegion has determined that this deallocation call may be sunk.
+  void addSafeToSink(const CallInst *CI);
+
+  // hoistRegion would like to know whether the given allocation call may be
+  // hoisted.
+  bool mayHoist(const CallInst *CI) const;
+
+  // Retrieve the list of free calls that should be removed from the loop.
+  const SmallVector<CallInst *, 16> &toSink(const CallInst *CI);
+
+  // Retrieve the list of loop exit blocks which must have a free inserted.
+  // This is a subset or equal to the loops exit blocks.
+  const SmallVector<BasicBlock *, 16> &addDeallocations(const CallInst *CI);
+
+  // Returns whether the loop has any potentially-hoistable allocations.
+  bool empty() const { return Allocations.empty(); }
+
+private:
+  // The n-th index into these vectors finds the matching allocation and
+  // deallocations.
+  SmallVector<const CallInst *, 4> Allocations;
+  SmallVector<SmallVector<CallInst *, 16>, 4> Deallocations;
+  SmallVector<SmallVector<BasicBlock *, 16>, 4> ExitBlocksToAddDeallocationsTo;
+
+  // Look up the index into the above vector given a call.
+  DenseMap<const CallInst *, size_t> AllocationLookup;
+  DenseMap<const CallInst *, size_t> DeallocationLookup;
+
+  DenseSet<const CallInst *> SafeToSink;
+};
+
+} // namespace llvm
+
+#endif

llvm/include/llvm/IR/Instruction.h

public:
   /// Return true if this instruction may read memory.
   bool mayReadFromMemory() const;
 
   /// Return true if this instruction may read or write memory.
   bool mayReadOrWriteMemory() const {
     return mayReadFromMemory() || mayWriteToMemory();
   }
 
+  /// Return true if this instruction may allocate heap memory.
+  bool mayAllocateMemory() const;
+
+  /// Return true if this instruction may deallocate heap memory.
+  bool mayDeallocateMemory() const;
+
   /// Return true if this instruction has an AtomicOrdering of unordered or
   /// higher.
   bool isAtomic() const;
 
   /// Return true if this atomic instruction loads from memory.
   bool hasAtomicLoad() const;
 
   /// Return true if this atomic instruction stores to memory.

llvm/include/llvm/Transforms/Utils/LoopUtils.h

 
 namespace llvm {
 
 class AliasSet;
 class AliasSetTracker;
 class BasicBlock;
 class DataLayout;
 class Loop;
+class LoopAllocationInfo;
 class LoopInfo;
 class MemoryAccess;
 class MemorySSAUpdater;
 class OptimizationRemarkEmitter;
 class PredicatedScalarEvolution;
 class PredIteratorCache;
 class ScalarEvolution;
 class SCEV;

 /// uses before definitions, allowing us to sink a loop body in one pass without
 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
 /// instructions of the loop and loop safety information as
 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                 TargetLibraryInfo *, TargetTransformInfo *, Loop *,
                 AliasSetTracker *, MemorySSAUpdater *, ICFLoopSafetyInfo *,
-                bool, int &, OptimizationRemarkEmitter *);
+                LoopAllocationInfo *, bool, int &, OptimizationRemarkEmitter *);
 
 /// Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in depth
 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
 /// loop and loop safety information as arguments. Diagnostics is emitted via \p
 /// ORE. It returns changed status.
 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
-                 MemorySSAUpdater *, ICFLoopSafetyInfo *, bool, int &,
-                 OptimizationRemarkEmitter *);
+                 MemorySSAUpdater *, ICFLoopSafetyInfo *, LoopAllocationInfo *,
+                 bool, int &, OptimizationRemarkEmitter *);
 
 /// This function deletes dead loops. The caller of this function needs to
 /// guarantee that the loop is infact dead.
 /// The function requires a bunch or prerequisites to be present:
 ///   - The loop needs to be in LCSSA form
 ///   - The loop needs to have a Preheader
 ///   - A unique dedicated exit block must exist
 ///

llvm/lib/Analysis/BasicAliasAnalysis.cpp

bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
 
   if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck)
     return false;
 
   // Make sure that the visited phis cannot reach the Value. This ensures that
   // the Values cannot come from different iterations of a potential cycle the
   // phi nodes could be involved in.
   for (auto *P : VisitedPhiBBs)
-    if (isPotentiallyReachable(&P->front(), Inst, DT, LI))
+    if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT, LI))
       return false;
 
   return true;
 }
 
 /// Computes the symbolic difference between two de-composed GEPs.
 ///
 /// Dest and Src are the variable indices from two decomposed GetElementPtr

llvm/lib/Analysis/CFG.cpp

 //===-- CFG.cpp - BasicBlock analysis --------------------------------------==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This family of functions performs analyses on basic blocks, and instructions
 // contained within basic blocks.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/CFG.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/Dominators.h"
 
 using namespace llvm;
 
 /// FindFunctionBackedges - Analyze the specified function to find all of the
 /// loop backedges in the function and return them.  This is a relatively cheap
static const Loop *getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB) {
   const Loop *L = LI->getLoopFor(BB);
   if (L) {
     while (const Loop *Parent = L->getParentLoop())
       L = Parent;
   }
   return L;
 }
 
-// True if there is a loop which contains both BB1 and BB2.
-static bool loopContainsBoth(const LoopInfo *LI,
-                             const BasicBlock *BB1, const BasicBlock *BB2) {
-  const Loop *L1 = getOutermostLoop(LI, BB1);
-  const Loop *L2 = getOutermostLoop(LI, BB2);
-  return L1 != nullptr && L1 == L2;
-}
-
 bool llvm::isPotentiallyReachableFromMany(
     SmallVectorImpl<BasicBlock *> &Worklist, BasicBlock *StopBB,
-    const DominatorTree *DT, const LoopInfo *LI) {
+    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
+    const LoopInfo *LI) {
   // When the stop block is unreachable, it's dominated from everywhere,
   // regardless of whether there's a path between the two blocks.
   if (DT && !DT->isReachableFromEntry(StopBB))
     DT = nullptr;
 
+  // We can't skip directly from a block that dominates the stop block if the
+  // exclusion block is potentially in between.
+  if (ExclusionSet && !ExclusionSet->empty())
+    DT = nullptr;
+
+  // Normally any block in a loop is reachable from any other block in a loop,
+  // however excluded blocks might partition the body of a loop to make that
+  // untrue.
+  SmallPtrSet<const Loop *, 8> LoopsWithHoles;
+  if (LI && ExclusionSet) {
+    for (auto BB : *ExclusionSet) {
+      if (const Loop *L = getOutermostLoop(LI, BB))
+        LoopsWithHoles.insert(L);
+    }
+  }
+
+  const Loop *StopLoop = LI ? getOutermostLoop(LI, StopBB) : nullptr;
+
   // Limit the number of blocks we visit. The goal is to avoid run-away compile
   // times on large CFGs without hampering sensible code. Arbitrarily chosen.
   unsigned Limit = 32;
   SmallPtrSet<const BasicBlock*, 32> Visited;
   do {
     BasicBlock *BB = Worklist.pop_back_val();
     if (!Visited.insert(BB).second)
       continue;
     if (BB == StopBB)
       return true;
+    if (ExclusionSet && ExclusionSet->count(BB))
+      continue;
     if (DT && DT->dominates(BB, StopBB))
       return true;
-    if (LI && loopContainsBoth(LI, BB, StopBB))
+
+    const Loop *Outer = nullptr;
+    if (LI) {
+      Outer = getOutermostLoop(LI, BB);
+      if (LoopsWithHoles.count(Outer))
+        Outer = nullptr;
+      if (StopLoop && Outer == StopLoop)
         return true;
+    }
 
     if (!--Limit) {
       // We haven't been able to prove it one way or the other. Conservatively
       // answer true -- that there is potentially a path.
       return true;
     }
 
-    if (const Loop *Outer = LI ? getOutermostLoop(LI, BB) : nullptr) {
+    if (Outer) {
       // All blocks in a single loop are reachable from all other blocks. From
       // any of these blocks, we can skip directly to the exits of the loop,
       // ignoring any other blocks inside the loop body.
       Outer->getExitBlocks(Worklist);
     } else {
       Worklist.append(succ_begin(BB), succ_end(BB));
     }
   } while (!Worklist.empty());
 
   // We have exhausted all possible paths and are certain that 'To' can not be
   // reached from 'From'.
   return false;
 }
 
 bool llvm::isPotentiallyReachable(const BasicBlock *A, const BasicBlock *B,
                                   const DominatorTree *DT, const LoopInfo *LI) {
   assert(A->getParent() == B->getParent() &&
          "This analysis is function-local!");
 
   SmallVector<BasicBlock*, 32> Worklist;
   Worklist.push_back(const_cast<BasicBlock*>(A));
 
   return isPotentiallyReachableFromMany(Worklist, const_cast<BasicBlock *>(B),
-                                        DT, LI);
+                                        nullptr, DT, LI);
 }
 
-bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B,
-                                  const DominatorTree *DT, const LoopInfo *LI) {
+bool llvm::isPotentiallyReachable(
+    const Instruction *A, const Instruction *B,
+    const SmallPtrSetImpl<BasicBlock *> *ExclusionSet, const DominatorTree *DT,
+    const LoopInfo *LI) {
   assert(A->getParent()->getParent() == B->getParent()->getParent() &&
          "This analysis is function-local!");
 
   SmallVector<BasicBlock*, 32> Worklist;
 
   if (A->getParent() == B->getParent()) {
     // The same block case is special because it's the only time we're looking
     // within a single block to see which instruction comes first. Once we
if (A->getParent() == B->getParent()) {
     if (Worklist.empty()) {
       // We've proven that there's no path!
       return false;
     }
   } else {
     Worklist.push_back(const_cast<BasicBlock*>(A->getParent()));
   }
 
-  if (A->getParent() == &A->getParent()->getParent()->getEntryBlock())
+  if (DT) {
+    if (DT->isReachableFromEntry(A->getParent()) !=
+        DT->isReachableFromEntry(B->getParent()))
+      return false;
+    if (!ExclusionSet || ExclusionSet->empty()) {
+      if (A->getParent() == &A->getParent()->getParent()->getEntryBlock() &&
+          DT->isReachableFromEntry(B->getParent()))
         return true;
-  if (B->getParent() == &A->getParent()->getParent()->getEntryBlock())
+      if (B->getParent() == &A->getParent()->getParent()->getEntryBlock() &&
+          DT->isReachableFromEntry(A->getParent()))
         return false;
+    }
+  }
 
   return isPotentiallyReachableFromMany(
-      Worklist, const_cast<BasicBlock *>(B->getParent()), DT, LI);
+      Worklist, const_cast<BasicBlock *>(B->getParent()), ExclusionSet, DT, LI);
 }

llvm/lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   LazyBranchProbabilityInfo.cpp
   LazyBlockFrequencyInfo.cpp
   LazyCallGraph.cpp
   LazyValueInfo.cpp
   LegacyDivergenceAnalysis.cpp
   Lint.cpp
   Loads.cpp
   LoopAccessAnalysis.cpp
+  LoopAllocationInfo.cpp
   LoopAnalysisManager.cpp
   LoopUnrollAnalyzer.cpp
   LoopInfo.cpp
   LoopPass.cpp
   MemDepPrinter.cpp
   MemDerefPrinter.cpp
   MemoryBuiltins.cpp
   MemoryDependenceAnalysis.cpp

llvm/lib/Analysis/CaptureTracking.cpp

bool isSafeToPrune(Instruction *I) {
         //  (1) BB is an entry block or have no successors.
         //  (2) There's no path coming back through BB successors.
         if (BB == &BB->getParent()->getEntryBlock() ||
             !BB->getTerminator()->getNumSuccessors())
           return true;
 
         SmallVector<BasicBlock*, 32> Worklist;
         Worklist.append(succ_begin(BB), succ_end(BB));
-        return !isPotentiallyReachableFromMany(Worklist, BB, DT);
+        return !isPotentiallyReachableFromMany(Worklist, BB, nullptr, DT);
       }
 
       // If the value is defined in the same basic block as use and BeforeHere,
       // there is no need to explore the use if BeforeHere dominates use.
       // Check whether there is a path from I to BeforeHere.
       if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
-          !isPotentiallyReachable(I, BeforeHere, DT))
+          !isPotentiallyReachable(I, BeforeHere, nullptr, DT))
         return true;
 
       return false;
     }
 
     bool shouldExplore(const Use *U) override {
       Instruction *I = cast<Instruction>(U->getUser());
 

llvm/lib/Analysis/LoopAllocationInfo.cpp

+//===- LoopAllocationInfo.cpp - memory allocations inside loops -----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/LoopAllocationInfo.h"
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Analysis/CFG.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/Support/Casting.h"
+
+namespace llvm {
+
+/// Track ptr = allocfn to one or more freefn(ptr) relationships within the
+/// loop.
+///
+/// This analysis stores information about allocation and deallocation calls
+/// where the pointer is only live within the loop.
+///
+/// An allocation must be both hoisted and sunk, or neither. LICM performs
+/// sinking first, then hoisting. As sinking and hoisting is performed, more
+/// instructions will appear to be loop invariant, making more opportunities.
+/// For this reason we split the analysis into two pieces:
+///   1. for a given pointer that is only live in the loop, retain a list its
+///      matching deallocating instructions.
+///   2. during sinking, if we would sink the deallocation, don't, but inform
+///      the LoopAllocationInfo. If all deallocations would have been sunk, and
+///      hoistSink would hoist the allocation, perform both the hoist and sink
+///      the various deallocation instructions.
+///
+/// We don't need guaranteed execution of any deallocation function during
+/// unwinding. Before this transformation, an unwind mid-loop would leak one
+/// pointer that was allocated at the start of the loop. After this
+/// transformation, it would leak the one pointer allocated before the loop
+/// began. There is no difference visible to the caller.
+///
+/// We do have to ensure that the maximum amount of allocated memory is not
+/// raised by this transformation. To ensure this, we stop looking for
+/// allocations after seeing an opaque function call. For example:
+///   loop_top:
+///     %ptr1 = call i8* @malloc(i32 %loop_invariant1)  ;; candidate
+///     %ptr2 = call i8* @malloc(i32 %loop_variant2)    ;; not candidate
+///     %ptr3 = call i8* @malloc(i32 %loop_invariant3)  ;; candidate
+///     call void @opaque()                             ;; stop scanning
+///     %ptr5 = call i8* @malloc(i32 %loop_invariant5)  ;; not candidate
+///
+/// The same idea applies in reverse order to @free calls at the loop exits:
+///   loop_exiting:
+///      call void @free(%ptr1)  ;; not candidate
+///      call void @opaque()     ;; stop scanning
+///      call void @free(%ptr2)  ;; %ptr2 is candidate
+///                              ;; start here and scan upwards
+void LoopAllocationInfo::analyzeLoop(LoopInfo *LI, DominatorTree *DT,
+                                     TargetLibraryInfo *TLI, Loop *CurLoop) {
+  assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&
+         "Unexpected input to LoopAllocationInfo::analyzeLoop.");
+  if (!TLI)
+    return;
+
+  SmallVector<BasicBlock *, 32> LatchBlocks;
+  CurLoop->getLoopLatches(LatchBlocks);
+  if (LatchBlocks.empty())
+    return;
+
+  SmallVector<BasicBlock *, 32> ExitBlocks;
+  CurLoop->getExitBlocks(ExitBlocks);
+  if (ExitBlocks.empty())
+    return;
+
+  // Unlike hoistRegion, we only scan the header block. If the allocation is in
+  // a later block, it must be behind some sort of branch which implies that
+  // it's conditional on something or else another optimization would've removed
+  // the unconditional branch earlier).
+  BasicBlock *HeaderBB = CurLoop->getHeader();
+  SmallPtrSet<BasicBlock *, 1> HeaderBlock;
+  HeaderBlock.insert(HeaderBB);
+  for (BasicBlock::iterator II = HeaderBB->begin(), E = HeaderBB->end();
+       II != E; ++II) {
+    if (!II->mayDeallocateMemory() && !II->mayAllocateMemory())
+      continue;
+    if (!llvm::isAllocationFn(&*II, TLI))
+      break;
+    auto CI = cast<CallInst>(II);
+
+    // Find places in the loop where the pointer is certainly freed. The places
+    // we identify must free this allocation, but there may be any number of
+    // other places that could free our pointer which we miss.
+    //
+    // We use this to ensure that the allocation is freed before we go around
+    // any loop latch.
+    SmallVector<CallInst *, 16> FreeCalls;
+    constexpr size_t UseVisitThreshold = 20;
+    SmallVector<Instruction *, UseVisitThreshold> Worklist;
+    SmallPtrSet<Instruction *, UseVisitThreshold> Visited;
+    auto Enqueue = [&](const Instruction *I) {
+      for (const Use &U : I->uses()) {
+        Instruction *User = cast<Instruction>(U.getUser());
+        if (!CurLoop->contains(User))
+          continue;
+        if (!Visited.insert(User).second)
+          continue;
+        if (Visited.size() == UseVisitThreshold)
+          return;
+        Worklist.push_back(User);
+      }
+    };
+    Enqueue(CI);
+    do {
+      Instruction *I = Worklist.pop_back_val();
+      if (isa<BitCastInst>(I)) {
+        Enqueue(I);
+      } else if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
+        if (GEP->hasAllZeroIndices())
+          Enqueue(GEP);
+      } else if (auto *PN = dyn_cast<PHINode>(I)) {
+        if (PN->hasConstantOrUndefValue())
+          Enqueue(I);
+      } else if (llvm::isFreeCall(I, TLI)) {
+        FreeCalls.push_back(cast<CallInst>(I));
+      }
+    } while (!Worklist.empty() && Visited.size() < UseVisitThreshold);
+
+    if (FreeCalls.empty() || Visited.size() >= UseVisitThreshold)
+      continue;
+
+    SmallPtrSet<BasicBlock *, 32> FreeCallBBs;
+    for (auto FreeCall : FreeCalls)
+      FreeCallBBs.insert(FreeCall->getParent());
+
+    bool DoNotTransform = false;
+
+    // Check that the frees we found cover all the latches.
+    for (BasicBlock *LatchBB : LatchBlocks) {
+      if (FreeCallBBs.count(LatchBB))
+        continue;
+      SmallVector<BasicBlock *, 32> HeaderWorklist;
+      HeaderWorklist.push_back(HeaderBB);
+      if (llvm::isPotentiallyReachableFromMany(HeaderWorklist, LatchBB,
+                                               &FreeCallBBs, DT, LI)) {
+        DoNotTransform = true;
+        break;
+      }
+    }
+    if (DoNotTransform)
+      continue;
+
+    // Examine each exit block and determine whether was a free which is
+    // unconditionally executed on the way to the exit block.
+    //
+    // We use two queries, is there a path from any free to this exit without
+    // going back to the header (if not, do not insert a free), and is there a
+    // path from the path from the header to this exit without going through any
+    // frees (if not, we must insert a free). Both of these queries can return
+    // true, in which case the deallocation is conditional or there are other
+    // deallocations we can not see, and we do not perform the transform.
+    SmallVector<BasicBlock *, 16> InsertDeallocation;
+    for (auto ExitBB : ExitBlocks) {
+      SmallVector<BasicBlock *, 32> HeaderWorklist, FreeCallWorklist;
+      HeaderWorklist.push_back(HeaderBB);
+      FreeCallWorklist.insert(FreeCallWorklist.end(), FreeCallBBs.begin(),
+                              FreeCallBBs.end());
+      bool A = llvm::isPotentiallyReachableFromMany(HeaderWorklist, ExitBB,
+                                                    &FreeCallBBs, DT, LI);
+      bool B = FreeCallBBs.count(HeaderBB) ||
+               llvm::isPotentiallyReachableFromMany(FreeCallWorklist, ExitBB,
+                                                    &HeaderBlock, DT, LI);
+      assert((A || B) && "loop exit blocks not reachable from loop");
+      if (A && B) {
+        // We can't tell whether we pass through a free on the way to this exit
+        // block.
+        DoNotTransform = true;
+        break;
+      }
+      if (B)
+        InsertDeallocation.push_back(ExitBB);
+    }
+    if (DoNotTransform)
+      continue;
+
+    AllocationLookup[CI] = Allocations.size();
+    for (const CallInst *FreeCall : FreeCalls)
+      DeallocationLookup[FreeCall] = Allocations.size();
+    Allocations.push_back(CI);
+    Deallocations.emplace_back(std::move(FreeCalls));
+    ExitBlocksToAddDeallocationsTo.emplace_back(std::move(InsertDeallocation));
+  }
+}
+
+// sinkRegion has determined that this deallocation call may be sunk.
+void LoopAllocationInfo::addSafeToSink(const CallInst *CI) {
+  if (DeallocationLookup.count(CI))
+    SafeToSink.insert(CI);
+}
+
+// hoistRegion would like to know whether the given allocation call may be
+// hoisted.
+bool LoopAllocationInfo::mayHoist(const CallInst *CI) const {
+  auto it = AllocationLookup.find(CI);
+  if (it == AllocationLookup.end())
+    return false;
+  size_t index = it->second;
+  assert(index < Deallocations.size());
+  for (const CallInst *FreeCall : Deallocations[index]) {
+    if (!SafeToSink.count(FreeCall))
+      return false;
+  }
+  return true;
+}
+
+const SmallVector<CallInst *, 16> &
+LoopAllocationInfo::toSink(const CallInst *CI) {
+  assert(AllocationLookup.find(CI) != AllocationLookup.end());
+  return Deallocations[AllocationLookup[CI]];
+}
+
+const SmallVector<BasicBlock *, 16> &
+LoopAllocationInfo::addDeallocations(const CallInst *CI) {
+  assert(AllocationLookup.find(CI) != AllocationLookup.end());
+  return ExitBlocksToAddDeallocationsTo[AllocationLookup[CI]];
+}
+
+} // namespace llvm

llvm/lib/CodeGen/DwarfEHPrepare.cpp

 /// unreachable and then simplify those blocks.
 size_t DwarfEHPrepare::pruneUnreachableResumes(
     Function &Fn, SmallVectorImpl<ResumeInst *> &Resumes,
     SmallVectorImpl<LandingPadInst *> &CleanupLPads) {
   BitVector ResumeReachable(Resumes.size());
   size_t ResumeIndex = 0;
   for (auto *RI : Resumes) {
     for (auto *LP : CleanupLPads) {
-      if (isPotentiallyReachable(LP, RI, DT)) {
+      if (isPotentiallyReachable(LP, RI, nullptr, DT)) {
         ResumeReachable.set(ResumeIndex);
         break;
       }
     }
     ++ResumeIndex;
   }
 
   // If everything is reachable, there is no change.

llvm/lib/IR/Instruction.cpp

bool Instruction::mayWriteToMemory() const {
   case Instruction::Invoke:
   case Instruction::CallBr:
     return !cast<CallBase>(this)->onlyReadsMemory();
   case Instruction::Load:
     return !cast<LoadInst>(this)->isUnordered();
   }
 }
 
+bool Instruction::mayAllocateMemory() const {
+  switch (getOpcode()) {
+  default:
+    return false;
+  case Instruction::CallBr:
+    return true;
+  case Instruction::Call: {
+    auto II = dyn_cast<IntrinsicInst>(this);
+    if (!II)
+      return true;
+    switch (II->getIntrinsicID()) {
+    default:
+      return false;
+    case Intrinsic::objc_autoreleasePoolPush:
+      return true;
+    }
+  }
+  }
+}
+
+bool Instruction::mayDeallocateMemory() const {
+  switch (getOpcode()) {
+  default:
+    return false;
+  case Instruction::CallBr:
+    return true;
+  case Instruction::Call: {
+    auto II = dyn_cast<IntrinsicInst>(this);
+    if (!II)
+      return true;
+    switch (II->getIntrinsicID()) {
+    default:
+      return false;
+    case Intrinsic::objc_autoreleasePoolPop:
+      return true;
+    }
+  }
+  }
+}
+
 bool Instruction::isAtomic() const {
   switch (getOpcode()) {
   default:
     return false;
   case Instruction::AtomicCmpXchg:
   case Instruction::AtomicRMW:
   case Instruction::Fence:
     return true;

llvm/lib/Transforms/Scalar/LICM.cpp

 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/Loads.h"
+#include "llvm/Analysis/LoopAllocationInfo.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/PredIteratorCache.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"

 static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
                                   const LoopSafetyInfo *SafetyInfo,
                                   TargetTransformInfo *TTI, bool &FreeInLoop);
 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
                   BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
                   MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE);
 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
                  const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
-                 MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE,
-                 bool FreeInLoop);
+                 MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE);
 static bool isSafeToExecuteUnconditionally(Instruction &Inst,
                                            const DominatorTree *DT,
                                            const Loop *CurLoop,
                                            const LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,
                                            const Instruction *CtxI = nullptr);
 static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
                                      AliasSetTracker *CurAST, Loop *CurLoop,
bool LoopInvariantCodeMotion::runOnLoop(
 
   // Get the preheader block to move instructions into...
   BasicBlock *Preheader = L->getLoopPreheader();
 
   // Compute loop safety information.
   ICFLoopSafetyInfo SafetyInfo(DT);
   SafetyInfo.computeLoopSafetyInfo(L);
 
+  // Scan for matching malloc/free pairs.
+  LoopAllocationInfo LAI;
+  if (L->hasDedicatedExits() && Preheader)
+    LAI.analyzeLoop(LI, DT, TLI, L);
+
   // We want to visit all of the instructions in this loop... that are not parts
   // of our subloops (they have already had their invariants hoisted out of
   // their loop, into this loop, so there is no need to process the BODIES of
   // the subloops).
   //
   // Traverse the body of the loop in depth first order on the dominator tree so
   // that we are guaranteed to see definitions before we see uses.  This allows
   // us to sink instructions in one pass, without iteration.  After sinking
   // instructions, we perform another pass to hoist them out of the loop.
   //
   if (L->hasDedicatedExits())
     Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, TTI, L,
-                          CurAST.get(), MSSAU.get(), &SafetyInfo,
+                          CurAST.get(), MSSAU.get(), &SafetyInfo, &LAI,
                           NoOfMemAccTooLarge, LicmMssaOptCounter, ORE);
   if (Preheader)
     Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
-                           CurAST.get(), MSSAU.get(), &SafetyInfo,
+                           CurAST.get(), MSSAU.get(), &SafetyInfo, &LAI,
                            NoOfMemAccTooLarge, LicmMssaOptCounter, ORE);
 
   // Now that all loop invariants have been removed from the loop, promote any
   // memory references to scalars that we can.
   // Don't sink stores from loops without dedicated block exits. Exits
   // containing indirect branches are not transformed by loop simplify,
   // make sure we catch that. An additional load may be generated in the
   // preheader for SSA updater, so also avoid sinking when no preheader

 /// the specified block, and that are in the current loop) in reverse depth
 /// first order w.r.t the DominatorTree.  This allows us to visit uses before
 /// definitions, allowing us to sink a loop body in one pass without iteration.
 ///
 bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
                       DominatorTree *DT, TargetLibraryInfo *TLI,
                       TargetTransformInfo *TTI, Loop *CurLoop,
                       AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
-                      ICFLoopSafetyInfo *SafetyInfo, bool NoOfMemAccTooLarge,
-                      int &LicmMssaOptCounter, OptimizationRemarkEmitter *ORE) {
+                      ICFLoopSafetyInfo *SafetyInfo, LoopAllocationInfo *LAI,
+                      bool NoOfMemAccTooLarge, int &LicmMssaOptCounter,
+                      OptimizationRemarkEmitter *ORE) {
 
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
-         CurLoop != nullptr && SafetyInfo != nullptr &&
+         CurLoop != nullptr && SafetyInfo != nullptr && LAI != nullptr &&
          "Unexpected input to sinkRegion.");
   assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&
          "Either AliasSetTracker or MemorySSA should be initialized.");
 
   // We want to visit children before parents. We will enque all the parents
   // before their children in the worklist and process the worklist in reverse
   // order.
   SmallVector<DomTreeNode *, 16> Worklist = collectChildrenInLoop(N, CurLoop);
 
   bool Changed = false;
   for (DomTreeNode *DTN : reverse(Worklist)) {
     BasicBlock *BB = DTN->getBlock();
     // Only need to process the contents of this block if it is not part of a
     // subloop (which would already have been processed).
     if (inSubLoop(BB, CurLoop, LI))
       continue;
 
+    bool PassedOpaqueFunction = LAI->empty();
     for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
       Instruction &I = *--II;
 
       // If the instruction is dead, we would try to sink it because it isn't
       // used in the loop, instead, just delete it.
       if (isInstructionTriviallyDead(&I, TLI)) {
         LLVM_DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
         salvageDebugInfo(I);
         ++II;
         eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
         Changed = true;
         continue;
       }
 
       // Check to see if we can sink this instruction to the exit blocks
       // of the loop.  We can do this if the all users of the instruction are
       // outside of the loop.  In this case, it doesn't even matter if the
       // operands of the instruction are loop invariant.
       //
       bool FreeInLoop = false;
       if (isNotUsedOrFreeInLoop(I, CurLoop, SafetyInfo, TTI, FreeInLoop) &&
           canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true,
                              NoOfMemAccTooLarge, &LicmMssaOptCounter, ORE) &&
           !I.mayHaveSideEffects()) {
-        if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE, FreeInLoop)) {
+        if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE)) {
           if (!FreeInLoop) {
             ++II;
             eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
           }
           Changed = true;
         }
       }
+
+      if (!PassedOpaqueFunction) {
+        if (llvm::isFreeCall(&I, TLI)) {
+          LAI->addSafeToSink(cast<CallInst>(&I));
+        } else if (I.mayAllocateMemory()) {
+          PassedOpaqueFunction = true;
+        }
+      }
     }
   }
   if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
   return Changed;
 }
 
 namespace {

 /// Walk the specified region of the CFG (defined by all blocks dominated by
 /// the specified block, and that are in the current loop) in depth first
 /// order w.r.t the DominatorTree.  This allows us to visit definitions before
 /// uses, allowing us to hoist a loop body in one pass without iteration.
 ///
 bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
                        DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
                        AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
-                       ICFLoopSafetyInfo *SafetyInfo, bool NoOfMemAccTooLarge,
-                       int &LicmMssaOptCounter,
+                       ICFLoopSafetyInfo *SafetyInfo, LoopAllocationInfo *LAI,
+                       bool NoOfMemAccTooLarge, int &LicmMssaOptCounter,
                        OptimizationRemarkEmitter *ORE) {
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
-         CurLoop != nullptr && SafetyInfo != nullptr &&
+         CurLoop != nullptr && SafetyInfo != nullptr && LAI != nullptr &&
          "Unexpected input to hoistRegion.");
   assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&
          "Either AliasSetTracker or MemorySSA should be initialized.");
 
   ControlFlowHoister CFH(LI, DT, CurLoop, MSSAU);
 
   // Keep track of instructions that have been hoisted, as they may need to be
   // re-hoisted if they end up not dominating all of their uses.
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
               CurLoop->getLoopPreheader()->getTerminator())) {
         hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
               MSSAU, ORE);
         HoistedInstructions.push_back(&I);
         Changed = true;
         continue;
       }
 
+      // If it's a malloc/free pair, try hoisting it out to the preheader. We
+      // don't need to worry about intervening unwinding function calls in this
+      // case, so we can be more aggressive than for generic instructions.
+      if (CurLoop->hasLoopInvariantOperands(&I) &&
+          llvm::isAllocationFn(&I, TLI) && LAI->mayHoist(cast<CallInst>(&I))) {
+        IRBuilder<>(&I).CreateLifetimeStart(&I);
+        hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
+              MSSAU, ORE);
+        HoistedInstructions.push_back(&I);
+        Instruction *Pattern = LAI->toSink(cast<CallInst>(&I))[0];
+        for (auto ExitBlock : LAI->addDeallocations(cast<CallInst>(&I))) {
+          Instruction *Clone = Pattern->clone();
+          Clone->dropUnknownNonDebugMetadata();
+          ExitBlock->getInstList().insert(ExitBlock->getFirstInsertionPt(),
+                                          Clone);
+        }
+
+        for (auto FreeCall : LAI->toSink(cast<CallInst>(&I))) {
+          IRBuilder<>(FreeCall).CreateLifetimeEnd(&I);
+          eraseInstruction(*FreeCall, *SafetyInfo, CurAST, MSSAU);
+        }
+
+        Changed = true;
+        continue;
+      }
+
       // Attempt to remove floating point division out of the loop by
       // converting it to a reciprocal multiplication.
       if (I.getOpcode() == Instruction::FDiv &&
           CurLoop->isLoopInvariant(I.getOperand(1)) &&
           I.hasAllowReciprocal()) {
         auto Divisor = I.getOperand(1);
         auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0);
         auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
static bool isLoadInvariantInLoop(LoadInst *LI, DominatorTree *DT,
   }
 
   return false;
 }
 
 namespace {
 /// Return true if-and-only-if we know how to (mechanically) both hoist and
 /// sink a given instruction out of a loop.  Does not address legality
-/// concerns such as aliasing or speculation safety.  
+/// concerns such as aliasing or speculation safety.
 bool isHoistableAndSinkableInst(Instruction &I) {
   // Only these instructions are hoistable/sinkable.
-  return (isa<LoadInst>(I) || isa<StoreInst>(I) ||
-          isa<CallInst>(I) || isa<FenceInst>(I) || 
-          isa<BinaryOperator>(I) || isa<CastInst>(I) ||
-          isa<SelectInst>(I) || isa<GetElementPtrInst>(I) ||
-          isa<CmpInst>(I) || isa<InsertElementInst>(I) ||
-          isa<ExtractElementInst>(I) || isa<ShuffleVectorInst>(I) ||
-          isa<ExtractValueInst>(I) || isa<InsertValueInst>(I));
+  return (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<CallInst>(I) ||
+          isa<FenceInst>(I) || isa<BinaryOperator>(I) || isa<CastInst>(I) ||
+          isa<SelectInst>(I) || isa<GetElementPtrInst>(I) || isa<CmpInst>(I) ||
+          isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) ||
+          isa<ShuffleVectorInst>(I) || isa<ExtractValueInst>(I) ||
+          isa<InsertValueInst>(I));
 }
 /// Return true if all of the alias sets within this AST are known not to
 /// contain a Mod, or if MSSA knows thare are no MemoryDefs in the loop.
 bool isReadOnly(AliasSetTracker *CurAST, const MemorySSAUpdater *MSSAU,
                 const Loop *L) {
   if (CurAST) {
     for (AliasSet &AS : *CurAST) {
       if (!AS.isForwardingAliasSet() && AS.isMod()) {
static Instruction *CloneInstructionInExitBlock(
     Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
     const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU) {
   Instruction *New;
   if (auto *CI = dyn_cast<CallInst>(&I)) {
     const auto &BlockColors = SafetyInfo->getBlockColors();
 
     // Sinking call-sites need to be handled differently from other
     // instructions.  The cloned call-site needs a funclet bundle operand
-    // appropriate for it's location in the CFG.
+    // appropriate for its location in the CFG.
     SmallVector<OperandBundleDef, 1> OpBundles;
     for (unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
          BundleIdx != BundleEnd; ++BundleIdx) {
       OperandBundleUse Bundle = CI->getOperandBundleAt(BundleIdx);
       if (Bundle.getTagID() == LLVMContext::OB_funclet)
         continue;
 
       OpBundles.emplace_back(Bundle);

 
 /// When an instruction is found to only be used outside of the loop, this
 /// function moves it to the exit blocks and patches up SSA form as needed.
 /// This method is guaranteed to remove the original instruction from its
 /// position, and may either delete it or move it to outside of the loop.
 ///
 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
                  const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
-                 MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE,
-                 bool FreeInLoop) {
+                 MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE) {
   LLVM_DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
   ORE->emit([&]() {
     return OptimizationRemark(DEBUG_TYPE, "InstSunk", &I)
            << "sinking " << ore::NV("Inst", &I);
   });
   bool Changed = false;
   if (isa<LoadInst>(I))
     ++NumMovedLoads;
   else if (isa<CallInst>(I))
     ++NumMovedCalls;
   ++NumSunk;
 
   // Iterate over users to be ready for actual sinking. Replace users via
-  // unrechable blocks with undef and make all user PHIs trivially replcable.
+  // unreachable blocks with undef and make all user PHIs trivially replaceable.
   SmallPtrSet<Instruction *, 8> VisitedUsers;
   for (Value::user_iterator UI = I.user_begin(), UE = I.user_end(); UI != UE;) {
     auto *User = cast<Instruction>(*UI);
     Use &U = UI.getUse();
     ++UI;
 
     if (VisitedUsers.count(User) || CurLoop->contains(User))
       continue;

llvm/test/Transforms/LICM/allocs.ll

+; RUN: opt -S -licm < %s | FileCheck %s
+
+declare i8* @malloc(i32)
+declare void @free(i8* nocapture)
+
+declare void @use(i8*)
+declare i1 @expr()
+
+define void @test1(i32 %loop_invariant) {
+; CHECK-LABEL: @test1
+header:
+; CHECK-LABEL: header:
+; CHECK: @malloc
+; CHECK: br label %loop
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK-NOT: @malloc
+; CHECK: @llvm.lifetime.start
+; CHECK-NOT: @malloc
+; CHECK: @use
+; CHECK-NOT: @free
+; CHECK: @llvm.lifetime.end
+; CHECK-NOT: @free
+  %ptr = call i8* @malloc(i32 %loop_invariant)
+  call void @use(i8* %ptr)
+  call void @free(i8* %ptr)
+  br i1 undef, label %loop, label %loopexit
+
+loopexit:
+; CHECK-LABEL: loopexit:
+; CHECK: @free
+  ret void
+}
+
+declare void @mightmalloc()
+
+define void @test2(i32 %loop_invariant) {
+; CHECK-LABEL: @test2
+header:
+; CHECK-LABEL: header:
+; CHECK-NOT: @malloc
+; CHECK: br label %loop
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK: @malloc
+; CHECK: @use
+; CHECK: @free
+; CHECK: @mightmalloc
+  %ptr = call i8* @malloc(i32 %loop_invariant)
+  call void @use(i8* %ptr)
+  call void @free(i8* %ptr)
+  call void @mightmalloc()
+  br i1 undef, label %loop, label %loopexit
+
+loopexit:
+; CHECK-LABEL: loopexit:
+; CHECK-NOT: @free
+  ret void
+}
+
+define void @test3(i32 %loop_invariant) {
+; CHECK-LABEL: @test3
+header:
+; CHECK-LABEL: header:
+; CHECK-NOT: @malloc
+; CHECK: br label %loop
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK: @mightmalloc
+; CHECK: @malloc
+; CHECK: @use
+; CHECK: @free
+  call void @mightmalloc()
+  %ptr = call i8* @malloc(i32 %loop_invariant)
+  call void @use(i8* %ptr)
+  call void @free(i8* %ptr)
+  br i1 undef, label %loop, label %loopexit
+
+loopexit:
+; CHECK-LABEL: loopexit:
+; CHECK-NOT: @free
+  ret void
+}
+
+define void @test4(i32 %loop_invariant) {
+; CHECK-LABEL: @test4
+header:
+; CHECK-LABEL: header:
+; CHECK: @malloc
+; CHECK: @malloc
+; CHECK: @malloc
+; CHECK: br label %loop
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK-NOT: @malloc
+; CHECK: @llvm.lifetime.start
+; CHECK: @llvm.lifetime.start
+; CHECK: @llvm.lifetime.start
+; CHECK: @use
+; CHECK: @use
+; CHECK: @use
+; CHECK: @llvm.lifetime.end
+; CHECK: @llvm.lifetime.end
+; CHECK: @llvm.lifetime.end
+; CHECK-NOT: @free
+  %ptr1 = call i8* @malloc(i32 %loop_invariant)
+  %ptr2 = call i8* @malloc(i32 %loop_invariant)
+  %ptr3 = call i8* @malloc(i32 %loop_invariant)
+  call void @use(i8* %ptr1)
+  call void @use(i8* %ptr2)
+  call void @use(i8* %ptr3)
+  call void @free(i8* %ptr1)
+  call void @free(i8* %ptr2)
+  call void @free(i8* %ptr3)
+  br i1 undef, label %loop, label %loopexit
+
+loopexit:
+; CHECK-LABEL: loopexit:
+; CHECK: @free
+; CHECK: @free
+; CHECK: @free
+  ret void
+}
+
+define void @test5(i32 %loop_invariant) {
+; CHECK-LABEL: @test5
+header:
+; CHECK-LABEL: header:
+; CHECK: @malloc
+; CHECK: @malloc
+; CHECK: @malloc
+; CHECK: br label %loop
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK-NOT: @malloc
+; CHECK: @llvm.lifetime.start
+; CHECK: @llvm.lifetime.start
+; CHECK: @llvm.lifetime.start
+; CHECK: @use
+; CHECK: @use
+; CHECK: @use
+; CHECK: @llvm.lifetime.end
+; CHECK: @llvm.lifetime.end
+; CHECK: @llvm.lifetime.end
+; CHECK-NOT: @free
+  %ptr3 = call i8* @malloc(i32 %loop_invariant)
+  %ptr2 = call i8* @malloc(i32 %loop_invariant)
+  %ptr1 = call i8* @malloc(i32 %loop_invariant)
+  call void @use(i8* %ptr1)
+  call void @use(i8* %ptr2)
+  call void @use(i8* %ptr3)
+  call void @free(i8* %ptr1)
+  call void @free(i8* %ptr2)
+  call void @free(i8* %ptr3)
+  br i1 undef, label %loop, label %loopexit
+
+loopexit:
+; CHECK-LABEL: loopexit:
+; CHECK: @free
+; CHECK: @free
+; CHECK: @free
+  ret void
+}
+
+define void @test6(i32 %loop_invariant) {
+; CHECK-LABEL: @test6
+header:
+; CHECK-LABEL: header:
+; CHECK: @malloc
+; CHECK: @malloc
+; CHECK-NOT: @malloc
+; CHECK: br label %loop
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK: @llvm.lifetime.start
+; CHECK: @malloc
+; CHECK: @llvm.lifetime.start
+; CHECK: @use
+; CHECK: @use
+; CHECK: @use
+; CHECK: @llvm.lifetime.end
+; CHECK: @free
+; CHECK: @llvm.lifetime.end
+  %i = phi i32 [%loop_invariant, %header], [%i.1, %loop]
+  %ptr1 = call i8* @malloc(i32 %loop_invariant)
+  %ptr2 = call i8* @malloc(i32 %i)
+  %ptr3 = call i8* @malloc(i32 %loop_invariant)
+  call void @use(i8* %ptr1)
+  call void @use(i8* %ptr2)
+  call void @use(i8* %ptr3)
+  call void @free(i8* %ptr1)
+  call void @free(i8* %ptr2)
+  call void @free(i8* %ptr3)
+  %i.1 = add i32 %i, 1
+  br i1 undef, label %loop, label %loopexit
+
+loopexit:
+; CHECK-LABEL: loopexit:
+; CHECK: @free
+; CHECK: @free
+; CHECK-NOT: @free
+; CHECK: ret void
+  ret void
+}
+
+define void @test7(i32 %loop_invariant) {
+; CHECK-LABEL: @test7
+header:
+; CHECK-LABEL: header:
+; CHECK: @malloc
+; CHECK: br label %loop
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK-NOT: @malloc
+; CHECK: @llvm.lifetime.start
+; CHECK-NOT: @malloc
+; CHECK: @use
+; CHECK-NOT: @free
+; CHECK-NOT: @llvm.lifetime.end
+  %i = phi i32 [%loop_invariant, %header], [%i.1, %loop.2], [%i.1, %loop.3]
+  %ptr = call i8* @malloc(i32 %loop_invariant)
+  call void @use(i8* %ptr)
+  %i.1 = add i32 %i, 1
+  %cmp = icmp eq i32 %i.1, 123
+  br i1 %cmp, label %loop.2, label %loop.3
+
+loop.2:
+; CHECK-LABEL: loop.2:
+; CHECK-NOT: @free
+; CHECK: @llvm.lifetime.end
+; CHECK-NOT: @free
+  %continue.1 = call i1 @expr()
+  call void @free(i8* %ptr)
+  br i1 %continue.1, label %loop, label %loopexit
+
+loop.3:
+; CHECK-LABEL: loop.3:
+; CHECK-NOT: @free
+; CHECK: @llvm.lifetime.end
+; CHECK-NOT: @free
+  %continue.2 = call i1 @expr()
+  call void @free(i8* %ptr)
+  br i1 %continue.2, label %loop, label %loopexit
+
+loopexit:
+; CHECK-LABEL: loopexit:
+; CHECK: @free
+  ret void
+}
+
+declare void @assert_fail()
+
+define void @test8(i32 %loop_invariant) {
+; CHECK-LABEL: @test8
+header:
+; CHECK-LABEL: header:
+; CHECK: @malloc
+; CHECK: br label %loop
+  br label %loop
+
+loop:
+; CHECK-LABEL: loop:
+; CHECK-NOT: @malloc
+; CHECK: @llvm.lifetime.start
+; CHECK-NOT: @malloc
+  %ptr = call i8* @malloc(i32 %loop_invariant)
+  %fail = call i1 @expr()
+  br i1 %fail, label %assert_fail, label %assert_pass
+
+assert_fail:
+  call void @assert_fail()
+  unreachable
+
+assert_pass:
+; CHECK-LABEL: assert_pass:
+; CHECK-NOT: @free
+; CHECK: @llvm.lifetime.end
+; CHECK-NOT: @free
+  call void @free(i8* %ptr)
+  br i1 undef, label %loop, label %loopexit
+
+loopexit:
+; CHECK-LABEL: loopexit:
+; CHECK: @free
+  ret void
+}

llvm/unittests/Analysis/CFGTest.cpp

 //===- CFGTest.cpp - CFG tests --------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/CFG.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/IR/Module.h"
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
         else if (I->getName() == "B")
           B = &*I;
       }
     }
     if (A == nullptr)
       report_fatal_error("@test must have an instruction %A");
     if (B == nullptr)
       report_fatal_error("@test must have an instruction %B");
+
+    assert(ExclusionSet.empty());
+    for (auto I = F->begin(), E = F->end(); I != E; ++I) {
+      if (I->hasName() && I->getName().startswith("excluded"))
+        ExclusionSet.insert(&*I);
+    }
   }
 
   void ExpectPath(bool ExpectedResult) {
     static char ID;
     class IsPotentiallyReachableTestPass : public FunctionPass {
      public:
-      IsPotentiallyReachableTestPass(bool ExpectedResult,
-                                     Instruction *A, Instruction *B)
-          : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B) {}
+       IsPotentiallyReachableTestPass(bool ExpectedResult, Instruction *A,
+                                      Instruction *B,
+                                      SmallPtrSet<BasicBlock *, 4> ExclusionSet)
+           : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B),
+             ExclusionSet(ExclusionSet) {}
 
        static int initialize() {
-        PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass",
-                                    "", &ID, nullptr, true, true);
+         PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass", "",
+                                     &ID, nullptr, true, true);
          PassRegistry::getPassRegistry()->registerPass(*PI, false);
          initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
          initializeDominatorTreeWrapperPassPass(
              *PassRegistry::getPassRegistry());
          return 0;
       }
 
       void getAnalysisUsage(AnalysisUsage &AU) const override {
         AU.setPreservesAll();
         AU.addRequired<LoopInfoWrapperPass>();
         AU.addRequired<DominatorTreeWrapperPass>();
       }
 
       bool runOnFunction(Function &F) override {
         if (!F.hasName() || F.getName() != "test")
           return false;
 
         LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
         DominatorTree *DT =
             &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-        EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, nullptr),
+        EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, nullptr),
+                  ExpectedResult);
+        EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, nullptr),
+                  ExpectedResult);
+        EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, LI),
+                  ExpectedResult);
+        EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, LI),
                   ExpectedResult);
-        EXPECT_EQ(isPotentiallyReachable(A, B, DT, nullptr), ExpectedResult);
-        EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, LI), ExpectedResult);
-        EXPECT_EQ(isPotentiallyReachable(A, B, DT, LI), ExpectedResult);
         return false;
       }
       bool ExpectedResult;
       Instruction *A, *B;
+      SmallPtrSet<BasicBlock *, 4> ExclusionSet;
     };
 
     static int initialize = IsPotentiallyReachableTestPass::initialize();
     (void)initialize;
 
     IsPotentiallyReachableTestPass *P =
-        new IsPotentiallyReachableTestPass(ExpectedResult, A, B);
+        new IsPotentiallyReachableTestPass(ExpectedResult, A, B, ExclusionSet);
     legacy::PassManager PM;
     PM.add(P);
     PM.run(*M);
   }
 
   LLVMContext Context;
   std::unique_ptr<Module> M;
   Instruction *A, *B;
+  SmallPtrSet<BasicBlock *, 4> ExclusionSet;
 };
 
 }
 
 TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) {
   ParseAssembly(
       "define void @test() {\n"
       "entry:\n"
TEST_F(IsPotentiallyReachableTest, ModifyTest) {
 
   succ_iterator S = succ_begin(&*++M->getFunction("test")->begin());
   BasicBlock *OldBB = S[0];
   S[0] = S[1];
   ExpectPath(false);
   S[0] = OldBB;
   ExpectPath(true);
 }
+
+TEST_F(IsPotentiallyReachableTest, UnreachableFromEntryTest) {
+  ParseAssembly("define void @test() {\n"
+                "entry:\n"
+                "  %A = bitcast i8 undef to i8\n"
+                "  ret void\n"
+                "not.reachable:\n"
+                "  %B = bitcast i8 undef to i8\n"
+                "  ret void\n"
+                "}");
+  ExpectPath(false);
+}
+
+TEST_F(IsPotentiallyReachableTest, UnreachableBlocksTest1) {
+  ParseAssembly("define void @test() {\n"
+                "entry:\n"
+                "  ret void\n"
+                "not.reachable.1:\n"
+                "  %A = bitcast i8 undef to i8\n"
+                "  br label %not.reachable.2\n"
+                "not.reachable.2:\n"
+                "  %B = bitcast i8 undef to i8\n"
+                "  ret void\n"
+                "}");
+  ExpectPath(true);
+}
+
+TEST_F(IsPotentiallyReachableTest, UnreachableBlocksTest2) {
+  ParseAssembly("define void @test() {\n"
+                "entry:\n"
+                "  ret void\n"
+                "not.reachable.1:\n"
+                "  %B = bitcast i8 undef to i8\n"
+                "  br label %not.reachable.2\n"
+                "not.reachable.2:\n"
+                "  %A = bitcast i8 undef to i8\n"
+                "  ret void\n"
+                "}");
+  ExpectPath(false);
+}
+
+TEST_F(IsPotentiallyReachableTest, SimpleExclusionTest) {
+  ParseAssembly("define void @test() {\n"
+                "entry:\n"
+                "  %A = bitcast i8 undef to i8\n"
+                "  br label %excluded\n"
+                "excluded:\n"
+                "  br label %exit\n"
+                "exit:\n"
+                "  %B = bitcast i8 undef to i8\n"
+                "  ret void\n"
+                "}");
+  ExpectPath(false);
+}
+
+TEST_F(IsPotentiallyReachableTest, DiamondExcludedTest) {
+  ParseAssembly("declare i1 @switch()\n"
+                "\n"
+                "define void @test() {\n"
+                "entry:\n"
+                "  %x = call i1 @switch()\n"
+                "  %A = bitcast i8 undef to i8\n"
+                "  br i1 %x, label %excluded.1, label %excluded.2\n"
+                "excluded.1:\n"
+                "  br label %exit\n"
+                "excluded.2:\n"
+                "  br label %exit\n"
+                "exit:\n"
+                "  %B = bitcast i8 undef to i8\n"
+                "  ret void\n"
+                "}");
+  ExpectPath(false);
+}
+
+TEST_F(IsPotentiallyReachableTest, DiamondOneSideExcludedTest) {
+  ParseAssembly("declare i1 @switch()\n"
+                "\n"
+                "define void @test() {\n"
+                "entry:\n"
+                "  %x = call i1 @switch()\n"
+                "  %A = bitcast i8 undef to i8\n"
+                "  br i1 %x, label %excluded, label %diamond\n"
+                "excluded:\n"
+                "  br label %exit\n"
+                "diamond:\n"
+                "  br label %exit\n"
+                "exit:\n"
+                "  %B = bitcast i8 undef to i8\n"
+                "  ret void\n"
+                "}");
+  ExpectPath(true);
+}