Index: include/llvm/Transforms/Utils/LoopUtils.h
===================================================================
--- include/llvm/Transforms/Utils/LoopUtils.h
+++ include/llvm/Transforms/Utils/LoopUtils.h
@@ -28,6 +28,7 @@
#include "llvm/IR/Operator.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Casting.h"
+#include "llvm/Transforms/Utils/OrderedInstructions.h"
namespace llvm {
@@ -51,10 +52,28 @@
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.
+ DenseSet<AssertingVH<Instruction>> EarlyExits;
+
+ // Utility to check for dominance information with caching.
+ OrderedInstructions OI;
+
// Used to update funclet bundle operands.
DenseMap<BasicBlock *, ColorVector> BlockColors;
- LoopSafetyInfo() = default;
+ // Delete the specified early exit. This can happen if the early exit
+ // is removed from the loop.
+ void deleteExit(Instruction *E) { EarlyExits.erase(E); }
+
+ // Return true if this instruction is an early exit, false otherwise.
+ bool isExit(Instruction *E) { return EarlyExits.count(E); }
+
+ // Constructor.
+ LoopSafetyInfo(DominatorTree *DT) : OI(DT) {}
};
/// The RecurrenceDescriptor is used to identify recurrences variables in a
@@ -444,13 +463,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<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);
Index: include/llvm/Transforms/Utils/OrderedInstructions.h
===================================================================
--- include/llvm/Transforms/Utils/OrderedInstructions.h
+++ include/llvm/Transforms/Utils/OrderedInstructions.h
@@ -10,11 +10,6 @@
// This file defines an efficient way to check for dominance relation between 2
// instructions.
//
-// This interface dispatches to appropriate dominance check given 2
-// instructions, i.e. in case the instructions are in the same basic block,
-// OrderedBasicBlock (with instruction numbering and caching) are used.
-// Otherwise, dominator tree is used.
-//
//===----------------------------------------------------------------------===//
#ifndef LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H
@@ -27,6 +22,12 @@
namespace llvm {
+/// This interface dispatches to appropriate dominance check given 2
+/// instructions, i.e. in case the instructions are in the same basic block,
+/// OrderedBasicBlock (with instruction numbering and caching) are used.
+/// Otherwise, dominator tree is used. This interface relies on the
+/// transformations to invalidate the basic blocks in case instructions in it
+/// are changed.
class OrderedInstructions {
/// Used to check dominance for instructions in same basic block.
mutable DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>>
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,
@@ -243,9 +241,9 @@
// Get the preheader block to move instructions into...
BasicBlock *Preheader = L->getLoopPreheader();
- // Compute loop safety information.
- LoopSafetyInfo SafetyInfo;
- computeLoopSafetyInfo(&SafetyInfo, L);
+ // Compute loop safety information. Along with all the early exits.
+ LoopSafetyInfo SafetyInfo(DT);
+ 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
@@ -370,6 +368,11 @@
DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
++II;
CurAST->deleteValue(&I);
+ // We could have treated this instruction as an early exit, update the
+ // early exit list.
+ SafetyInfo->deleteExit(&I);
+ // The ordered instruction list for this block is no longer valid.
+ SafetyInfo->OI.invalidateBlock(I.getParent());
I.eraseFromParent();
Changed = true;
continue;
@@ -425,6 +428,11 @@
I.replaceAllUsesWith(C);
if (isInstructionTriviallyDead(&I, TLI)) {
CurAST->deleteValue(&I);
+ // We could have treated this instruction as an early exit, update the
+ // early exit list.
+ SafetyInfo->deleteExit(&I);
+ // The ordered instruction list for this block is no longer valid.
+ SafetyInfo->OI.invalidateBlock(I.getParent());
I.eraseFromParent();
}
Changed = true;
@@ -447,6 +455,11 @@
Product->setFastMathFlags(I.getFastMathFlags());
Product->insertAfter(&I);
I.replaceAllUsesWith(Product);
+ // The ordered instruction list for this block is no longer valid.
+ SafetyInfo->OI.invalidateBlock(I.getParent());
+ // We do not update the early exit list here, i.e. how can we treat this
+ // instruction as an early exit ?
+ assert(SafetyInfo->isExit(&I) && "Invalid early exit");
I.eraseFromParent();
hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE);
@@ -476,17 +489,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.insert(&*I);
+ }
SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow;
// Iterate over loop instructions and compute safety info.
@@ -495,10 +518,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.insert(&*I);
+ }
// Compute funclet colors if we might sink/hoist in a function with a funclet
// personality routine.
@@ -794,8 +825,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));
@@ -856,6 +886,12 @@
PN->eraseFromParent();
}
+
+ // We could have treated this instruction as an early exit, update the
+ // early exit list.
+ SafetyInfo->deleteExit(&I);
+ // The ordered instruction list for this block is no longer valid.
+ SafetyInfo->OI.invalidateBlock(I.getParent());
CurAST->deleteValue(&I);
I.eraseFromParent();
return Changed;
@@ -865,8 +901,7 @@
/// 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");
@@ -884,6 +919,11 @@
!isGuaranteedToExecute(I, DT, CurLoop, SafetyInfo))
I.dropUnknownNonDebugMetadata();
+ // We could have treated this instruction as an early exit, update the
+ // early exit list.
+ SafetyInfo->deleteExit(&I);
+ // The ordered instruction list for this block is no longer valid.
+ SafetyInfo->OI.invalidateBlock(I.getParent());
// Move the new node to the Preheader, before its terminator.
I.moveBefore(Preheader->getTerminator());
@@ -909,7 +949,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/Scalar/LoopIdiomRecognize.cpp
===================================================================
--- lib/Transforms/Scalar/LoopIdiomRecognize.cpp
+++ lib/Transforms/Scalar/LoopIdiomRecognize.cpp
@@ -283,7 +283,7 @@
// The following transforms hoist stores/memsets into the loop pre-header.
// Give up if the loop has instructions may throw.
- LoopSafetyInfo SafetyInfo;
+ LoopSafetyInfo SafetyInfo(DT);
computeLoopSafetyInfo(&SafetyInfo, CurLoop);
if (SafetyInfo.MayThrow)
return MadeChange;
Index: lib/Transforms/Scalar/LoopUnswitch.cpp
===================================================================
--- lib/Transforms/Scalar/LoopUnswitch.cpp
+++ lib/Transforms/Scalar/LoopUnswitch.cpp
@@ -172,7 +172,6 @@
BasicBlock *loopPreheader;
bool SanitizeMemory;
- LoopSafetyInfo SafetyInfo;
// LoopBlocks contains all of the basic blocks of the loop, including the
// preheader of the loop, the body of the loop, and the exit blocks of the
@@ -193,7 +192,7 @@
}
bool runOnLoop(Loop *L, LPPassManager &LPM) override;
- bool processCurrentLoop();
+ bool processCurrentLoop(LoopSafetyInfo *SafetyInfo);
bool isUnreachableDueToPreviousUnswitching(BasicBlock *);
/// This transformation requires natural loop information & requires that
/// loop preheaders be inserted into the CFG.
@@ -508,6 +507,7 @@
Function *F = currentLoop->getHeader()->getParent();
SanitizeMemory = F->hasFnAttribute(Attribute::SanitizeMemory);
+ LoopSafetyInfo SafetyInfo(DT);
if (SanitizeMemory)
computeLoopSafetyInfo(&SafetyInfo, L);
@@ -515,7 +515,7 @@
do {
assert(currentLoop->isLCSSAForm(*DT));
redoLoop = false;
- Changed |= processCurrentLoop();
+ Changed |= processCurrentLoop(&SafetyInfo);
} while(redoLoop);
// FIXME: Reconstruct dom info, because it is not preserved properly.
@@ -554,7 +554,7 @@
}
/// Do actual work and unswitch loop if possible and profitable.
-bool LoopUnswitch::processCurrentLoop() {
+bool LoopUnswitch::processCurrentLoop(LoopSafetyInfo *SafetyInfo) {
bool Changed = false;
initLoopData();
@@ -649,7 +649,7 @@
// This is a workaround for the discrepancy between LLVM IR and MSan
// semantics. See PR28054 for more details.
if (SanitizeMemory &&
- !isGuaranteedToExecute(*TI, DT, currentLoop, &SafetyInfo))
+ !isGuaranteedToExecute(*TI, DT, currentLoop, SafetyInfo))
continue;
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
Index: lib/Transforms/Utils/LoopUtils.cpp
===================================================================
--- lib/Transforms/Utils/LoopUtils.cpp
+++ lib/Transforms/Utils/LoopUtils.cpp
@@ -17,6 +17,7 @@
#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 +1043,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))
+ 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;
-
+ // which does not execute this instruction.
// Get the exit blocks for the current loop.
SmallVector<BasicBlock *, 8> ExitBlocks;
CurLoop->getExitBlocks(ExitBlocks);
@@ -1071,7 +1081,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
===================================================================
--- lib/Transforms/Utils/OrderedInstructions.cpp
+++ lib/Transforms/Utils/OrderedInstructions.cpp
@@ -19,6 +19,7 @@
/// tree.
bool OrderedInstructions::dominates(const Instruction *InstA,
const Instruction *InstB) const {
+ assert(DT && "Uninitialized dominator tree");
const BasicBlock *IBB = InstA->getParent();
// Use ordered basic block to do dominance check in case the 2 instructions
// are in the same basic block.
Index: test/Transforms/LICM/loop-early-exits.ll
===================================================================
--- /dev/null
+++ test/Transforms/LICM/loop-early-exits.ll
@@ -0,0 +1,107 @@
+; RUN: opt -S -licm < %s | FileCheck %s
+
+declare void @use(i64 %a)
+declare void @use_nothing()
+declare void @call_nothrow() nounwind
+
+; 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(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(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 not transfer execution to successor, even
+; though it does not throw.
+define void @throw_body3(i64 %x, i64 %y, i1* %cond) {
+; CHECK-LABEL: throw_body3
+; CHECK-LABEL: body
+; CHECK: call void @call_nothrow()
+; CHECK: %div = udiv i64 %x, %y
+entry:
+ br label %loop
+
+loop: ; preds = %entry, %for.inc
+ br label %body
+
+body:
+ call void @call_nothrow()
+ %div = udiv i64 %x, %y
+ call void @use(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.