#define DEBUG_TYPE "loop-delete"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/SmallVector.h"
using namespace llvm;
STATISTIC(NumDeleted, "Number of loops deleted");
namespace {
class LoopDeletion : public LoopPass {
public:
static char ID; LoopDeletion() : LoopPass(ID) {
initializeLoopDeletionPass(*PassRegistry::getPassRegistry());
}
bool runOnLoop(Loop* L, LPPassManager& LPM);
bool IsLoopDead(Loop* L, SmallVector<BasicBlock*, 4>& exitingBlocks,
SmallVector<BasicBlock*, 4>& exitBlocks,
bool &Changed, BasicBlock *Preheader);
virtual void getAnalysisUsage(AnalysisUsage& AU) const {
AU.addRequired<DominatorTree>();
AU.addRequired<LoopInfo>();
AU.addRequired<ScalarEvolution>();
AU.addRequiredID(LoopSimplifyID);
AU.addRequiredID(LCSSAID);
AU.addPreserved<ScalarEvolution>();
AU.addPreserved<DominatorTree>();
AU.addPreserved<LoopInfo>();
AU.addPreservedID(LoopSimplifyID);
AU.addPreservedID(LCSSAID);
}
};
}
char LoopDeletion::ID = 0;
INITIALIZE_PASS_BEGIN(LoopDeletion, "loop-deletion",
"Delete dead loops", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTree)
INITIALIZE_PASS_DEPENDENCY(LoopInfo)
INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
INITIALIZE_PASS_DEPENDENCY(LCSSA)
INITIALIZE_PASS_END(LoopDeletion, "loop-deletion",
"Delete dead loops", false, false)
Pass* llvm::createLoopDeletionPass() {
return new LoopDeletion();
}
bool LoopDeletion::IsLoopDead(Loop* L,
SmallVector<BasicBlock*, 4>& exitingBlocks,
SmallVector<BasicBlock*, 4>& exitBlocks,
bool &Changed, BasicBlock *Preheader) {
BasicBlock* exitBlock = exitBlocks[0];
BasicBlock::iterator BI = exitBlock->begin();
while (PHINode* P = dyn_cast<PHINode>(BI)) {
Value* incoming = P->getIncomingValueForBlock(exitingBlocks[0]);
for (unsigned i = 1; i < exitingBlocks.size(); ++i) {
if (incoming != P->getIncomingValueForBlock(exitingBlocks[i]))
return false;
}
if (Instruction* I = dyn_cast<Instruction>(incoming))
if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator()))
return false;
++BI;
}
for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
LI != LE; ++LI) {
for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end();
BI != BE; ++BI) {
if (BI->mayHaveSideEffects())
return false;
}
}
return true;
}
bool LoopDeletion::runOnLoop(Loop* L, LPPassManager& LPM) {
BasicBlock* preheader = L->getLoopPreheader();
if (!preheader)
return false;
if (!L->hasDedicatedExits())
return false;
if (L->begin() != L->end())
return false;
SmallVector<BasicBlock*, 4> exitingBlocks;
L->getExitingBlocks(exitingBlocks);
SmallVector<BasicBlock*, 4> exitBlocks;
L->getUniqueExitBlocks(exitBlocks);
if (exitBlocks.size() != 1)
return false;
bool Changed = false;
if (!IsLoopDead(L, exitingBlocks, exitBlocks, Changed, preheader))
return Changed;
ScalarEvolution& SE = getAnalysis<ScalarEvolution>();
const SCEV *S = SE.getMaxBackedgeTakenCount(L);
if (isa<SCEVCouldNotCompute>(S))
return Changed;
BasicBlock* exitBlock = exitBlocks[0];
SE.forgetLoop(L);
TerminatorInst* TI = preheader->getTerminator();
TI->replaceUsesOfWith(L->getHeader(), exitBlock);
BasicBlock* exitingBlock = exitingBlocks[0];
BasicBlock::iterator BI = exitBlock->begin();
while (PHINode* P = dyn_cast<PHINode>(BI)) {
int j = P->getBasicBlockIndex(exitingBlock);
assert(j >= 0 && "Can't find exiting block in exit block's phi node!");
P->setIncomingBlock(j, preheader);
for (unsigned i = 1; i < exitingBlocks.size(); ++i)
P->removeIncomingValue(exitingBlocks[i]);
++BI;
}
DominatorTree& DT = getAnalysis<DominatorTree>();
SmallVector<DomTreeNode*, 8> ChildNodes;
for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
LI != LE; ++LI) {
ChildNodes.insert(ChildNodes.begin(), DT[*LI]->begin(), DT[*LI]->end());
for (SmallVector<DomTreeNode*, 8>::iterator DI = ChildNodes.begin(),
DE = ChildNodes.end(); DI != DE; ++DI) {
DT.changeImmediateDominator(*DI, DT[preheader]);
}
ChildNodes.clear();
DT.eraseNode(*LI);
(*LI)->dropAllReferences();
}
for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
LI != LE; ++LI)
(*LI)->eraseFromParent();
LoopInfo& loopInfo = getAnalysis<LoopInfo>();
SmallPtrSet<BasicBlock*, 8> blocks;
blocks.insert(L->block_begin(), L->block_end());
for (SmallPtrSet<BasicBlock*,8>::iterator I = blocks.begin(),
E = blocks.end(); I != E; ++I)
loopInfo.removeBlock(*I);
LPM.deleteLoopFromQueue(L);
Changed = true;
++NumDeleted;
return Changed;
}