Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -27,6 +27,7 @@ #include "llvm/IR/Operator.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Support/Casting.h" +#include "llvm/Transforms/Utils/OrderedInstructions.h" namespace llvm { @@ -49,6 +50,16 @@ bool MayThrow = false; // The current loop contains an instruction which // may throw. bool HeaderMayThrow = false; // Same as previous, but specific to loop header + + // Whether we have computed all the early exits. + bool ComputedEarlyExits = false; + // The early exits in the loop, excluding loop exits. + // These are calls that might throw, infinite loop, etc. + SmallVector EarlyExits; + + // Utility to check for dominance information with caching. + OrderedInstructions OI; + // Used to update funclet bundle operands. DenseMap BlockColors; @@ -442,13 +453,14 @@ /// checks loop body & header for the possibility of may throw /// exception, it takes LoopSafetyInfo and loop as argument. /// Updates safety information in LoopSafetyInfo argument. -void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *); +/// In case ComputeEarlyExits is true, all the early exit points are recorded. +void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *, + bool ComputeEarlyExits = false); /// Returns true if the instruction in a loop is guaranteed to execute at least /// once. bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, - const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo); + const Loop *CurLoop, LoopSafetyInfo *SafetyInfo); /// \brief Returns the instructions that use values defined in the loop. SmallVector findDefsUsedOutsideOfLoop(Loop *L); Index: include/llvm/Transforms/Utils/OrderedInstructions.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Utils/OrderedInstructions.h @@ -0,0 +1,41 @@ +//===- llvm/Transforms/Utils/OrderedInstructions.h ---------------*- C++ +//-*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines an efficient way to check for dominance between 2 +// instructions. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H +#define LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/Analysis/OrderedBasicBlock.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Operator.h" + +namespace llvm { + +class OrderedInstructions { + /// Used to check dominance for instructions in same basic block. + DenseMap> OBBMap; + +public: + /// Return true if first instruction dominates the second. + bool dominates(const Instruction *, const Instruction *, + const DominatorTree *DT); + + /// Invalidate the OrderedBasicBlock cache when its basic block changes. + void invalidateBlock(BasicBlock *BB) { OBBMap.erase(BB); } +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -91,16 +91,14 @@ static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo); static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo, - OptimizationRemarkEmitter *ORE); + LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE); static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT, const Loop *CurLoop, AliasSetTracker *CurAST, - const LoopSafetyInfo *SafetyInfo, - OptimizationRemarkEmitter *ORE); + LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE); static bool isSafeToExecuteUnconditionally(Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo, + LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE, const Instruction *CtxI = nullptr); static bool pointerInvalidatedByLoop(Value *V, uint64_t Size, @@ -245,7 +243,7 @@ // Compute loop safety information. LoopSafetyInfo SafetyInfo; - computeLoopSafetyInfo(&SafetyInfo, L); + computeLoopSafetyInfo(&SafetyInfo, L, true); // 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 @@ -476,17 +474,27 @@ /// Computes loop safety information, checks loop body & header /// for the possibility of may throw exception. /// -void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) { +void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop, + bool ComputeEarlyExits) { assert(CurLoop != nullptr && "CurLoop cant be null"); BasicBlock *Header = CurLoop->getHeader(); // Setting default safety values. SafetyInfo->MayThrow = false; SafetyInfo->HeaderMayThrow = false; + SafetyInfo->EarlyExits.clear(); + SafetyInfo->ComputedEarlyExits = ComputeEarlyExits; // Iterate over header and compute safety info. - for (BasicBlock::iterator I = Header->begin(), E = Header->end(); - (I != E) && !SafetyInfo->HeaderMayThrow; ++I) - SafetyInfo->HeaderMayThrow |= - !isGuaranteedToTransferExecutionToSuccessor(&*I); + for (BasicBlock::iterator I = Header->begin(), E = Header->end(); I != E; + ++I) { + bool MayThrow = !isGuaranteedToTransferExecutionToSuccessor(&*I); + SafetyInfo->HeaderMayThrow |= MayThrow; + // Exit as soon as we find an instruction that may throw in case we are + // not computing early exits. + if (!ComputeEarlyExits && SafetyInfo->HeaderMayThrow) + break; + if (MayThrow) + SafetyInfo->EarlyExits.push_back(&*I); + } SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow; // Iterate over loop instructions and compute safety info. @@ -495,10 +503,18 @@ assert(Header == *CurLoop->getBlocks().begin() && "First block must be header"); for (Loop::block_iterator BB = std::next(CurLoop->block_begin()), BBE = CurLoop->block_end(); - (BB != BBE) && !SafetyInfo->MayThrow; ++BB) - for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); - (I != E) && !SafetyInfo->MayThrow; ++I) - SafetyInfo->MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(&*I); + BB != BBE; ++BB) + for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; + ++I) { + bool MayThrow = !isGuaranteedToTransferExecutionToSuccessor(&*I); + SafetyInfo->MayThrow |= MayThrow; + // Exit as soon as we find an instruction that may throw in case we are + // not computing early exits. + if (!ComputeEarlyExits && SafetyInfo->MayThrow) + break; + if (MayThrow) + SafetyInfo->EarlyExits.push_back(&*I); + } // Compute funclet colors if we might sink/hoist in a function with a funclet // personality routine. @@ -794,8 +810,7 @@ /// static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT, const Loop *CurLoop, AliasSetTracker *CurAST, - const LoopSafetyInfo *SafetyInfo, - OptimizationRemarkEmitter *ORE) { + LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) { DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n"); ORE->emit(OptimizationRemark(DEBUG_TYPE, "InstSunk", &I) << "sinking " << ore::NV("Inst", &I)); @@ -814,6 +829,9 @@ ExitBlocks.end()); #endif + // The OBB for this basic block is no longer valid. + SafetyInfo->OI.invalidateBlock(I.getParent()); + // Clones of this instruction. Don't create more than one per exit block! SmallDenseMap SunkCopies; @@ -865,14 +883,16 @@ /// is safe to hoist, this instruction is called to do the dirty work. /// static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo, - OptimizationRemarkEmitter *ORE) { + LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) { auto *Preheader = CurLoop->getLoopPreheader(); DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I << "\n"); ORE->emit(OptimizationRemark(DEBUG_TYPE, "Hoisted", &I) << "hoisting " << ore::NV("Inst", &I)); + // The OBB for this basic block is no longer valid. + SafetyInfo->OI.invalidateBlock(I.getParent()); + // Metadata can be dependent on conditions we are hoisting above. // Conservatively strip all metadata on the instruction unless we were // guaranteed to execute I if we entered the loop, in which case the metadata @@ -909,7 +929,7 @@ static bool isSafeToExecuteUnconditionally(Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo, + LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE, const Instruction *CtxI) { if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT)) Index: lib/Transforms/Utils/CMakeLists.txt =================================================================== --- lib/Transforms/Utils/CMakeLists.txt +++ lib/Transforms/Utils/CMakeLists.txt @@ -37,6 +37,7 @@ MetaRenamer.cpp ModuleUtils.cpp NameAnonGlobals.cpp + OrderedInstructions.cpp PredicateInfo.cpp PromoteMemoryToRegister.cpp StripGCRelocates.cpp Index: lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- lib/Transforms/Utils/LoopUtils.cpp +++ lib/Transforms/Utils/LoopUtils.cpp @@ -15,9 +15,9 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/GlobalsModRef.h" -#include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/OrderedBasicBlock.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" #include "llvm/Analysis/ScalarEvolutionExpander.h" @@ -1042,24 +1042,33 @@ /// once. bool llvm::isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, - const LoopSafetyInfo *SafetyInfo) { + LoopSafetyInfo *SafetyInfo) { + // If we have computed early exits, use it. + if (SafetyInfo->ComputedEarlyExits) { + // Check wehther the instruction dominates all early exits. If it doesn't, + // then there is a path out of the loop which does not execute this + // instruction and its not guaranteed to execute. + for (Instruction *ExitInst : SafetyInfo->EarlyExits) + if (!SafetyInfo->OI.dominates(&Inst, ExitInst, DT)) + return false; + } else { + // If the instruction is in the header block for the loop (which is very + // common), it is always guaranteed to dominate the exit blocks. Since this + // is a common case, and can save some work, check it now. + if (Inst.getParent() == CurLoop->getHeader()) + // If there's a throw in the header block, we can't guarantee we'll reach + // Inst. + return !SafetyInfo->HeaderMayThrow; + + // Somewhere in this loop there is an instruction which may throw and make + // us exit the loop. + if (SafetyInfo->MayThrow) + return false; + } + // We have to check to make sure that the instruction dominates all // of the exit blocks. If it doesn't, then there is a path out of the loop // which does not execute this instruction, so we can't hoist it. - - // If the instruction is in the header block for the loop (which is very - // common), it is always guaranteed to dominate the exit blocks. Since this - // is a common case, and can save some work, check it now. - if (Inst.getParent() == CurLoop->getHeader()) - // If there's a throw in the header block, we can't guarantee we'll reach - // Inst. - return !SafetyInfo->HeaderMayThrow; - - // Somewhere in this loop there is an instruction which may throw and make us - // exit the loop. - if (SafetyInfo->MayThrow) - return false; - // Get the exit blocks for the current loop. SmallVector ExitBlocks; CurLoop->getExitBlocks(ExitBlocks); @@ -1071,7 +1080,9 @@ // As a degenerate case, if the loop is statically infinite then we haven't // proven anything since there are no exit blocks. - if (ExitBlocks.empty()) + // However, we also special case instruction from the header as the header + // is always guaranteed to execute. + if (ExitBlocks.empty() && Inst.getParent() != CurLoop->getHeader()) return false; // FIXME: In general, we have to prove that the loop isn't an infinite loop. Index: lib/Transforms/Utils/OrderedInstructions.cpp =================================================================== --- /dev/null +++ lib/Transforms/Utils/OrderedInstructions.cpp @@ -0,0 +1,32 @@ +//===-- OrderedInstructions.cpp - Instruction dominance function +//-----------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines utility to check dominance information for 2 instructions. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Utils/OrderedInstructions.h" + +using namespace llvm; + +#define DEBUG_TYPE "ordered-insts" + +bool OrderedInstructions::dominates(const Instruction *InstA, + const Instruction *InstB, + const DominatorTree *DT) { + const BasicBlock *IBB = InstA->getParent(); + if (IBB == InstB->getParent()) { + auto OBB = OBBMap.find(IBB); + if (OBB == OBBMap.end()) + OBB = OBBMap.insert({IBB, make_unique(IBB)}).first; + return OBB->second->dominates(InstA, InstB); + } else + return DT->dominates(InstA->getParent(), InstB->getParent()); +} Index: test/Transforms/LICM/loop-early-exits.ll =================================================================== --- /dev/null +++ test/Transforms/LICM/loop-early-exits.ll @@ -0,0 +1,82 @@ +; RUN: opt -S -licm < %s | FileCheck %s + +declare void @use(i64 %a) +declare void @use_nothrow(i64 %a) nounwind +declare void @use_nothing() + +; We can move this udiv out of the loop as it comes before +; the call instruction that may throw. +define void @throw_header1(i64 %x, i64 %y, i1* %cond) { +; CHECK-LABEL: throw_header1 +; CHECK: %div = udiv i64 %x, %y +; CHECK-LABEL: loop +; CHECK: call void @use(i64 %div) +entry: + br label %loop + +loop: ; preds = %entry, %for.inc + %div = udiv i64 %x, %y + call void @use(i64 %div) + br label %loop +} + +; We can not move this udiv out of the loop as it comes after +; the call instruction that may throw. +define void @throw_header2(i64 %x, i64 %y, i1* %cond) { +; CHECK-LABEL: throw_header2 +; CHECK-LABEL: loop +; CHECK: call void @use_nothing() +; CHECK: %div = udiv i64 %x, %y +entry: + br label %loop + +loop: ; preds = %entry, %for.inc + call void @use_nothing() + %div = udiv i64 %x, %y + call void @use_nothrow(i64 %div) + br label %loop +} + +; We can move this udiv out of the loop as it comes before +; the call instruction that may throw. +define void @throw_body1(i64 %x, i64 %y, i1* %cond) { +; CHECK-LABEL: throw_body1 +; CHECK: %div = udiv i64 %x, %y +; CHECK-LABEL: loop +entry: + br label %loop + +loop: ; preds = %entry, %for.inc + br label %body + +body: + %div = udiv i64 %x, %y + call void @use(i64 %div) + br i1 undef, label %loop, label %exit + +exit: + ret void +} + +; We can not move this udiv out of the loop as it comes after +; the call instruction that may throw. +define void @throw_body2(i64 %x, i64 %y, i1* %cond) { +; CHECK-LABEL: throw_body2 +; CHECK-LABEL: loop +; CHECK: call void @use_nothing() +; CHECK: %div = udiv i64 %x, %y +entry: + br label %loop + +loop: ; preds = %entry, %for.inc + br label %body + +body: + call void @use_nothing() + %div = udiv i64 %x, %y + call void @use_nothrow(i64 %div) + br i1 undef, label %loop, label %exit + +exit: + ret void +} Index: test/Transforms/LICM/preheader-safe.ll =================================================================== --- test/Transforms/LICM/preheader-safe.ll +++ test/Transforms/LICM/preheader-safe.ll @@ -21,20 +21,6 @@ call void @use_nothrow(i64 %div) br label %loop } -; Negative test -define void @throw_header(i64 %x, i64 %y, i1* %cond) { -; CHECK-LABEL: throw_header -; CHECK-LABEL: loop -; CHECK: %div = udiv i64 %x, %y -; CHECK: call void @use(i64 %div) -entry: - br label %loop - -loop: ; preds = %entry, %for.inc - %div = udiv i64 %x, %y - call void @use(i64 %div) - br label %loop -} ; The header is known no throw, but the loop is not. We can ; still lift out of the header.