summaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/LICM.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Scalar/LICM.cpp')
-rw-r--r--lib/Transforms/Scalar/LICM.cpp233
1 files changed, 118 insertions, 115 deletions
diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp
index 4ea935793b80..ff66632f0391 100644
--- a/lib/Transforms/Scalar/LICM.cpp
+++ b/lib/Transforms/Scalar/LICM.cpp
@@ -47,6 +47,7 @@
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
@@ -64,7 +65,6 @@
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
-#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
#include <algorithm>
@@ -97,7 +97,7 @@ static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
const LoopSafetyInfo *SafetyInfo,
OptimizationRemarkEmitter *ORE);
static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
- const Loop *CurLoop, const LoopSafetyInfo *SafetyInfo,
+ const Loop *CurLoop, LoopSafetyInfo *SafetyInfo,
OptimizationRemarkEmitter *ORE, bool FreeInLoop);
static bool isSafeToExecuteUnconditionally(Instruction &Inst,
const DominatorTree *DT,
@@ -170,7 +170,8 @@ struct LegacyLICMPass : public LoopPass {
/// loop preheaders be inserted into the CFG...
///
void getAnalysisUsage(AnalysisUsage &AU) const override {
- AU.setPreservesCFG();
+ AU.addPreserved<DominatorTreeWrapperPass>();
+ AU.addPreserved<LoopInfoWrapperPass>();
AU.addRequired<TargetLibraryInfoWrapperPass>();
if (EnableMSSALoopDependency)
AU.addRequired<MemorySSAWrapperPass>();
@@ -220,7 +221,10 @@ PreservedAnalyses LICMPass::run(Loop &L, LoopAnalysisManager &AM,
return PreservedAnalyses::all();
auto PA = getLoopPassPreservedAnalyses();
- PA.preserveSet<CFGAnalyses>();
+
+ PA.preserve<DominatorTreeAnalysis>();
+ PA.preserve<LoopAnalysis>();
+
return PA;
}
@@ -392,7 +396,8 @@ bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
// 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)) {
- DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
+ LLVM_DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
+ salvageDebugInfo(I);
++II;
CurAST->deleteValue(&I);
I.eraseFromParent();
@@ -445,99 +450,76 @@ bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
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))
- for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
- Instruction &I = *II++;
- // Try constant folding this instruction. If all the operands are
- // constants, it is technically hoistable, but it would be better to
- // just fold it.
- if (Constant *C = ConstantFoldInstruction(
- &I, I.getModule()->getDataLayout(), TLI)) {
- DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C << '\n');
- CurAST->copyValue(&I, C);
- I.replaceAllUsesWith(C);
- if (isInstructionTriviallyDead(&I, TLI)) {
- CurAST->deleteValue(&I);
- I.eraseFromParent();
- }
- Changed = true;
- continue;
- }
+ if (inSubLoop(BB, CurLoop, LI))
+ 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);
- ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
- ReciprocalDivisor->insertBefore(&I);
+ // Keep track of whether the prefix of instructions visited so far are such
+ // that the next instruction visited is guaranteed to execute if the loop
+ // is entered.
+ bool IsMustExecute = CurLoop->getHeader() == BB;
- auto Product =
- BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
- Product->setFastMathFlags(I.getFastMathFlags());
- Product->insertAfter(&I);
- I.replaceAllUsesWith(Product);
+ for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
+ Instruction &I = *II++;
+ // Try constant folding this instruction. If all the operands are
+ // constants, it is technically hoistable, but it would be better to
+ // just fold it.
+ if (Constant *C = ConstantFoldInstruction(
+ &I, I.getModule()->getDataLayout(), TLI)) {
+ LLVM_DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C
+ << '\n');
+ CurAST->copyValue(&I, C);
+ I.replaceAllUsesWith(C);
+ if (isInstructionTriviallyDead(&I, TLI)) {
+ CurAST->deleteValue(&I);
I.eraseFromParent();
-
- hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE);
- Changed = true;
- continue;
}
+ Changed = true;
+ continue;
+ }
- // Try hoisting the instruction out to the preheader. We can only do
- // this if all of the operands of the instruction are loop invariant and
- // if it is safe to hoist the instruction.
- //
- if (CurLoop->hasLoopInvariantOperands(&I) &&
- canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo, ORE) &&
- isSafeToExecuteUnconditionally(
- I, DT, CurLoop, SafetyInfo, ORE,
- CurLoop->getLoopPreheader()->getTerminator()))
- Changed |= hoist(I, DT, CurLoop, SafetyInfo, ORE);
+ // Try hoisting the instruction out to the preheader. We can only do
+ // this if all of the operands of the instruction are loop invariant and
+ // if it is safe to hoist the instruction.
+ //
+ if (CurLoop->hasLoopInvariantOperands(&I) &&
+ canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo, ORE) &&
+ (IsMustExecute ||
+ isSafeToExecuteUnconditionally(
+ I, DT, CurLoop, SafetyInfo, ORE,
+ CurLoop->getLoopPreheader()->getTerminator()))) {
+ Changed |= hoist(I, DT, CurLoop, SafetyInfo, ORE);
+ continue;
}
- }
- return Changed;
-}
+ // 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);
+ ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
+ ReciprocalDivisor->insertBefore(&I);
-/// Computes loop safety information, checks loop body & header
-/// for the possibility of may throw exception.
-///
-void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) {
- assert(CurLoop != nullptr && "CurLoop cant be null");
- BasicBlock *Header = CurLoop->getHeader();
- // Setting default safety values.
- SafetyInfo->MayThrow = false;
- SafetyInfo->HeaderMayThrow = false;
- // 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);
+ auto Product =
+ BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
+ Product->setFastMathFlags(I.getFastMathFlags());
+ Product->insertAfter(&I);
+ I.replaceAllUsesWith(Product);
+ I.eraseFromParent();
- SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow;
- // Iterate over loop instructions and compute safety info.
- // Skip header as it has been computed and stored in HeaderMayThrow.
- // The first block in loopinfo.Blocks is guaranteed to be the header.
- 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);
+ hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE);
+ Changed = true;
+ continue;
+ }
+
+ if (IsMustExecute)
+ IsMustExecute = isGuaranteedToTransferExecutionToSuccessor(&I);
+ }
+ }
- // Compute funclet colors if we might sink/hoist in a function with a funclet
- // personality routine.
- Function *Fn = CurLoop->getHeader()->getParent();
- if (Fn->hasPersonalityFn())
- if (Constant *PersonalityFn = Fn->getPersonalityFn())
- if (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn)))
- SafetyInfo->BlockColors = colorEHFunclets(*Fn);
+ return Changed;
}
// Return true if LI is invariant within scope of the loop. LI is invariant if
@@ -708,7 +690,7 @@ bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
/// This is true when all incoming values are that instruction.
/// This pattern occurs most often with LCSSA PHI nodes.
///
-static bool isTriviallyReplacablePHI(const PHINode &PN, const Instruction &I) {
+static bool isTriviallyReplaceablePHI(const PHINode &PN, const Instruction &I) {
for (const Value *IncValue : PN.incoming_values())
if (IncValue != &I)
return false;
@@ -838,12 +820,12 @@ CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
return New;
}
-static Instruction *sinkThroughTriviallyReplacablePHI(
+static Instruction *sinkThroughTriviallyReplaceablePHI(
PHINode *TPN, Instruction *I, LoopInfo *LI,
SmallDenseMap<BasicBlock *, Instruction *, 32> &SunkCopies,
const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop) {
- assert(isTriviallyReplacablePHI(*TPN, *I) &&
- "Expect only trivially replacalbe PHI");
+ assert(isTriviallyReplaceablePHI(*TPN, *I) &&
+ "Expect only trivially replaceable PHI");
BasicBlock *ExitBlock = TPN->getParent();
Instruction *New;
auto It = SunkCopies.find(ExitBlock);
@@ -855,10 +837,16 @@ static Instruction *sinkThroughTriviallyReplacablePHI(
return New;
}
-static bool canSplitPredecessors(PHINode *PN) {
+static bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo) {
BasicBlock *BB = PN->getParent();
if (!BB->canSplitPredecessors())
return false;
+ // It's not impossible to split EHPad blocks, but if BlockColors already exist
+ // it require updating BlockColors for all offspring blocks accordingly. By
+ // skipping such corner case, we can make updating BlockColors after splitting
+ // predecessor fairly simple.
+ if (!SafetyInfo->BlockColors.empty() && BB->getFirstNonPHI()->isEHPad())
+ return false;
for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
BasicBlock *BBPred = *PI;
if (isa<IndirectBrInst>(BBPred->getTerminator()))
@@ -868,7 +856,8 @@ static bool canSplitPredecessors(PHINode *PN) {
}
static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT,
- LoopInfo *LI, const Loop *CurLoop) {
+ LoopInfo *LI, const Loop *CurLoop,
+ LoopSafetyInfo *SafetyInfo) {
#ifndef NDEBUG
SmallVector<BasicBlock *, 32> ExitBlocks;
CurLoop->getUniqueExitBlocks(ExitBlocks);
@@ -879,7 +868,7 @@ static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT,
assert(ExitBlockSet.count(ExitBB) && "Expect the PHI is in an exit block.");
// Split predecessors of the loop exit to make instructions in the loop are
- // exposed to exit blocks through trivially replacable PHIs while keeping the
+ // exposed to exit blocks through trivially replaceable PHIs while keeping the
// loop in the canonical form where each predecessor of each exit block should
// be contained within the loop. For example, this will convert the loop below
// from
@@ -891,7 +880,7 @@ static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT,
// %v2 =
// br %LE, %LB1
// LE:
- // %p = phi [%v1, %LB1], [%v2, %LB2] <-- non-trivially replacable
+ // %p = phi [%v1, %LB1], [%v2, %LB2] <-- non-trivially replaceable
//
// to
//
@@ -902,21 +891,35 @@ static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT,
// %v2 =
// br %LE.split2, %LB1
// LE.split:
- // %p1 = phi [%v1, %LB1] <-- trivially replacable
+ // %p1 = phi [%v1, %LB1] <-- trivially replaceable
// br %LE
// LE.split2:
- // %p2 = phi [%v2, %LB2] <-- trivially replacable
+ // %p2 = phi [%v2, %LB2] <-- trivially replaceable
// br %LE
// LE:
// %p = phi [%p1, %LE.split], [%p2, %LE.split2]
//
+ auto &BlockColors = SafetyInfo->BlockColors;
SmallSetVector<BasicBlock *, 8> PredBBs(pred_begin(ExitBB), pred_end(ExitBB));
while (!PredBBs.empty()) {
BasicBlock *PredBB = *PredBBs.begin();
assert(CurLoop->contains(PredBB) &&
"Expect all predecessors are in the loop");
- if (PN->getBasicBlockIndex(PredBB) >= 0)
- SplitBlockPredecessors(ExitBB, PredBB, ".split.loop.exit", DT, LI, true);
+ if (PN->getBasicBlockIndex(PredBB) >= 0) {
+ BasicBlock *NewPred = SplitBlockPredecessors(
+ ExitBB, PredBB, ".split.loop.exit", DT, LI, true);
+ // Since we do not allow splitting EH-block with BlockColors in
+ // canSplitPredecessors(), we can simply assign predecessor's color to
+ // the new block.
+ if (!BlockColors.empty()) {
+ // Grab a reference to the ColorVector to be inserted before getting the
+ // reference to the vector we are copying because inserting the new
+ // element in BlockColors might cause the map to be reallocated.
+ ColorVector &ColorsForNewBlock = BlockColors[NewPred];
+ ColorVector &ColorsForOldBlock = BlockColors[PredBB];
+ ColorsForNewBlock = ColorsForOldBlock;
+ }
+ }
PredBBs.remove(PredBB);
}
}
@@ -927,9 +930,9 @@ static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT,
/// 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, const LoopSafetyInfo *SafetyInfo,
+ const Loop *CurLoop, LoopSafetyInfo *SafetyInfo,
OptimizationRemarkEmitter *ORE, bool FreeInLoop) {
- DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
+ LLVM_DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
ORE->emit([&]() {
return OptimizationRemark(DEBUG_TYPE, "InstSunk", &I)
<< "sinking " << ore::NV("Inst", &I);
@@ -972,15 +975,15 @@ static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
}
VisitedUsers.insert(PN);
- if (isTriviallyReplacablePHI(*PN, I))
+ if (isTriviallyReplaceablePHI(*PN, I))
continue;
- if (!canSplitPredecessors(PN))
+ if (!canSplitPredecessors(PN, SafetyInfo))
return Changed;
// Split predecessors of the PHI so that we can make users trivially
- // replacable.
- splitPredecessorsOfLoopExit(PN, DT, LI, CurLoop);
+ // replaceable.
+ splitPredecessorsOfLoopExit(PN, DT, LI, CurLoop, SafetyInfo);
// Should rebuild the iterators, as they may be invalidated by
// splitPredecessorsOfLoopExit().
@@ -1014,9 +1017,9 @@ static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
PHINode *PN = cast<PHINode>(User);
assert(ExitBlockSet.count(PN->getParent()) &&
"The LCSSA PHI is not in an exit block!");
- // The PHI must be trivially replacable.
- Instruction *New = sinkThroughTriviallyReplacablePHI(PN, &I, LI, SunkCopies,
- SafetyInfo, CurLoop);
+ // The PHI must be trivially replaceable.
+ Instruction *New = sinkThroughTriviallyReplaceablePHI(PN, &I, LI, SunkCopies,
+ SafetyInfo, CurLoop);
PN->replaceAllUsesWith(New);
PN->eraseFromParent();
Changed = true;
@@ -1031,8 +1034,8 @@ static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
const LoopSafetyInfo *SafetyInfo,
OptimizationRemarkEmitter *ORE) {
auto *Preheader = CurLoop->getLoopPreheader();
- DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I
- << "\n");
+ LLVM_DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I
+ << "\n");
ORE->emit([&]() {
return OptimizationRemark(DEBUG_TYPE, "Hoisted", &I) << "hoisting "
<< ore::NV("Inst", &I);
@@ -1221,7 +1224,7 @@ bool llvm::promoteLoopAccessesToScalars(
Value *SomePtr = *PointerMustAliases.begin();
BasicBlock *Preheader = CurLoop->getLoopPreheader();
- // It isn't safe to promote a load/store from the loop if the load/store is
+ // It is not safe to promote a load/store from the loop if the load/store is
// conditional. For example, turning:
//
// for () { if (c) *P += 1; }
@@ -1350,7 +1353,7 @@ bool llvm::promoteLoopAccessesToScalars(
// If a store dominates all exit blocks, it is safe to sink.
// As explained above, if an exit block was executed, a dominating
- // store must have been been executed at least once, so we are not
+ // store must have been executed at least once, so we are not
// introducing stores on paths that did not have them.
// Note that this only looks at explicit exit blocks. If we ever
// start sinking stores into unwind edges (see above), this will break.
@@ -1412,8 +1415,8 @@ bool llvm::promoteLoopAccessesToScalars(
return false;
// Otherwise, this is safe to promote, lets do it!
- DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " << *SomePtr
- << '\n');
+ LLVM_DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " << *SomePtr
+ << '\n');
ORE->emit([&]() {
return OptimizationRemark(DEBUG_TYPE, "PromoteLoopAccessesToScalar",
LoopUses[0])
generated by cgit v1.3 (git 2.53.0) at 2026-07-30 08:24:28 +0000