Index: llvm/include/llvm/Analysis/LoopAllocationInfo.h =================================================================== --- /dev/null +++ llvm/include/llvm/Analysis/LoopAllocationInfo.h @@ -0,0 +1,104 @@ +//===- 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. Its design is tighly coupled +/// to the internal implementation of LICM, but is exposed in a public API +/// because the hoistRegion and sinkRegion functions in LICM are also exposed. +/// +/// 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 &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 &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 Allocations; + SmallVector, 4> Deallocations; + SmallVector, 4> ExitBlocksToAddDeallocationsTo; + + // Look up the index into the above vector given a call. + DenseMap AllocationLookup; + DenseMap DeallocationLookup; + + DenseSet SafeToSink; +}; + +} // namespace llvm + +#endif Index: llvm/include/llvm/IR/Instruction.h =================================================================== --- llvm/include/llvm/IR/Instruction.h +++ llvm/include/llvm/IR/Instruction.h @@ -536,6 +536,12 @@ 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; Index: llvm/include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -39,6 +39,7 @@ class BasicBlock; class DataLayout; class Loop; +class LoopAllocationInfo; class LoopInfo; class MemoryAccess; class MemorySSAUpdater; @@ -112,7 +113,7 @@ 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 @@ -124,8 +125,8 @@ /// 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. Index: llvm/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/lib/Analysis/CMakeLists.txt +++ llvm/lib/Analysis/CMakeLists.txt @@ -50,6 +50,7 @@ Lint.cpp Loads.cpp LoopAccessAnalysis.cpp + LoopAllocationInfo.cpp LoopAnalysisManager.cpp LoopUnrollAnalyzer.cpp LoopInfo.cpp Index: llvm/lib/Analysis/LoopAllocationInfo.cpp =================================================================== --- /dev/null +++ llvm/lib/Analysis/LoopAllocationInfo.cpp @@ -0,0 +1,235 @@ +//===- 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 LatchBlocks; + CurLoop->getLoopLatches(LatchBlocks); + if (LatchBlocks.empty()) + return; + + SmallVector 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 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(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 FreeCalls; + constexpr size_t UseVisitThreshold = 20; + SmallVector Worklist; + SmallPtrSet Visited; + auto Enqueue = [&](const Instruction *I) { + for (const Use &U : I->uses()) { + Instruction *User = cast(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(I)) { + Enqueue(I); + } else if (auto *GEP = dyn_cast(I)) { + if (GEP->hasAllZeroIndices()) + Enqueue(GEP); + } else if (auto *PN = dyn_cast(I)) { + if (PN->hasConstantOrUndefValue()) + Enqueue(I); + } else if (llvm::isFreeCall(I, TLI)) { + FreeCalls.push_back(cast(I)); + } + } while (!Worklist.empty() && Visited.size() < UseVisitThreshold); + + if (FreeCalls.empty() || Visited.size() >= UseVisitThreshold) + continue; + + SmallPtrSet 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 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 InsertDeallocation; + for (auto ExitBB : ExitBlocks) { + SmallVector 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 & +LoopAllocationInfo::toSink(const CallInst *CI) { + assert(AllocationLookup.find(CI) != AllocationLookup.end()); + return Deallocations[AllocationLookup[CI]]; +} + +const SmallVector & +LoopAllocationInfo::addDeallocations(const CallInst *CI) { + assert(AllocationLookup.find(CI) != AllocationLookup.end()); + return ExitBlocksToAddDeallocationsTo[AllocationLookup[CI]]; +} + +} // namespace llvm Index: llvm/lib/IR/Instruction.cpp =================================================================== --- llvm/lib/IR/Instruction.cpp +++ llvm/lib/IR/Instruction.cpp @@ -548,6 +548,46 @@ } } +bool Instruction::mayAllocateMemory() const { + switch (getOpcode()) { + default: + return false; + case Instruction::CallBr: + return true; + case Instruction::Call: { + auto II = dyn_cast(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(this); + if (!II) + return true; + switch (II->getIntrinsicID()) { + default: + return false; + case Intrinsic::objc_autoreleasePoolPop: + return true; + } + } + } +} + bool Instruction::isAtomic() const { switch (getOpcode()) { default: Index: llvm/lib/Transforms/Scalar/LICM.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LICM.cpp +++ llvm/lib/Transforms/Scalar/LICM.cpp @@ -40,6 +40,7 @@ #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" @@ -56,6 +57,7 @@ #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" @@ -342,6 +344,11 @@ 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 @@ -354,11 +361,11 @@ // 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 @@ -463,12 +470,13 @@ 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."); @@ -486,6 +494,7 @@ if (inSubLoop(BB, CurLoop, LI)) continue; + bool PassedOpaqueFunction = LAI->empty(); for (BasicBlock::iterator II = BB->end(); II != BB->begin();) { Instruction &I = *--II; @@ -518,6 +527,14 @@ Changed = true; } } + + if (!PassedOpaqueFunction) { + if (llvm::isFreeCall(&I, TLI)) { + LAI->addSafeToSink(cast(&I)); + } else if (I.mayAllocateMemory()) { + PassedOpaqueFunction = true; + } + } } } if (MSSAU && VerifyMemorySSA) @@ -762,12 +779,12 @@ 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."); @@ -828,6 +845,32 @@ 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(&I))) { + IRBuilder<>(&I).CreateLifetimeStart(&I); + hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo, + MSSAU, ORE); + HoistedInstructions.push_back(&I); + Instruction *Pattern = LAI->toSink(cast(&I))[0]; + for (auto ExitBlock : LAI->addDeallocations(cast(&I))) { + Instruction *Clone = Pattern->clone(); + Clone->dropUnknownNonDebugMetadata(); + ExitBlock->getInstList().insert(ExitBlock->getFirstInsertionPt(), + Clone); + } + + for (auto FreeCall : LAI->toSink(cast(&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 && Index: llvm/test/Transforms/LICM/allocs.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/LICM/allocs.ll @@ -0,0 +1,347 @@ +; RUN: opt -S -licm < %s | FileCheck %s +; RUN: opt -S -enable-mssa-loop-dependency -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 +} + +declare void @usei64(i64) + +define void @test9(i32 %loop_invariant) { +; CHECK-LABEL: @test9 +header: +; CHECK-LABEL: header: +; CHECK: add +; CHECK: @malloc +; CHECK: ptrtoint +; CHECK: and +; CHECK-NOT: usei64 +; CHECK: br label %loop + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK-NOT: @malloc +; CHECK: @llvm.lifetime.start +; CHECK-NOT: @malloc +; CHECK: usei64 + %size = add i32 %loop_invariant, 1 + %ptr = call i8* @malloc(i32 %size) + %ptrbits = ptrtoint i8* %ptr to i64 + %aligncheck = and i64 %ptrbits, 4 + call void @usei64(i64%aligncheck) + %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 +}