#define DEBUG_TYPE "loopsimplify"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/Function.h"
#include "llvm/Type.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/DepthFirstIterator.h"
using namespace llvm;
STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted");
STATISTIC(NumNested , "Number of nested loops split out");
namespace {
struct VISIBILITY_HIDDEN LoopSimplify : public FunctionPass {
static char ID; LoopSimplify() : FunctionPass(&ID) {}
AliasAnalysis *AA;
LoopInfo *LI;
DominatorTree *DT;
virtual bool runOnFunction(Function &F);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<LoopInfo>();
AU.addRequired<DominatorTree>();
AU.addPreserved<LoopInfo>();
AU.addPreserved<DominatorTree>();
AU.addPreserved<DominanceFrontier>();
AU.addPreserved<AliasAnalysis>();
AU.addPreservedID(BreakCriticalEdgesID); }
void verifyAnalysis() const {
#ifndef NDEBUG
LoopInfo *NLI = &getAnalysis<LoopInfo>();
for (LoopInfo::iterator I = NLI->begin(), E = NLI->end(); I != E; ++I)
(*I)->verifyLoop();
#endif
}
private:
bool ProcessLoop(Loop *L);
BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit);
void InsertPreheaderForLoop(Loop *L);
Loop *SeparateNestedLoop(Loop *L);
void InsertUniqueBackedgeBlock(Loop *L);
void PlaceSplitBlockCarefully(BasicBlock *NewBB,
SmallVectorImpl<BasicBlock*> &SplitPreds,
Loop *L);
};
}
char LoopSimplify::ID = 0;
static RegisterPass<LoopSimplify>
X("loopsimplify", "Canonicalize natural loops", true);
const PassInfo *const llvm::LoopSimplifyID = &X;
FunctionPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); }
bool LoopSimplify::runOnFunction(Function &F) {
bool Changed = false;
LI = &getAnalysis<LoopInfo>();
AA = getAnalysisIfAvailable<AliasAnalysis>();
DT = &getAnalysis<DominatorTree>();
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
if (LI->getLoopFor(BB)) continue;
bool BlockUnreachable = false;
TerminatorInst *TI = BB->getTerminator();
for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
Loop *L = LI->getLoopFor(TI->getSuccessor(i));
if (!L) continue;
if (L->getHeader() == TI->getSuccessor(i) && L->getParentLoop() == 0)
continue;
BlockUnreachable = true;
break;
}
if (!BlockUnreachable) continue;
for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
TI->getSuccessor(i)->removePredecessor(BB);
new UnreachableInst(TI);
if (AA) AA->deleteValue(TI);
if (!TI->use_empty())
TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
TI->eraseFromParent();
Changed |= true;
}
for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
Changed |= ProcessLoop(*I);
return Changed;
}
bool LoopSimplify::ProcessLoop(Loop *L) {
bool Changed = false;
ReprocessLoop:
for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
Changed |= ProcessLoop(*I);
assert(L->getBlocks()[0] == L->getHeader() &&
"Header isn't first block in loop?");
if (L->getLoopPreheader() == 0) {
InsertPreheaderForLoop(L);
NumInserted++;
Changed = true;
}
SmallVector<BasicBlock*, 8> ExitBlocks;
L->getExitBlocks(ExitBlocks);
SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end());
for (SetVector<BasicBlock*>::iterator I = ExitBlockSet.begin(),
E = ExitBlockSet.end(); I != E; ++I) {
BasicBlock *ExitBlock = *I;
for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock);
PI != PE; ++PI)
if (!L->contains(*PI)) {
RewriteLoopExitBlock(L, ExitBlock);
NumInserted++;
Changed = true;
break;
}
}
unsigned NumBackedges = L->getNumBackEdges();
if (NumBackedges != 1) {
if (NumBackedges < 8) {
if (Loop *NL = SeparateNestedLoop(L)) {
++NumNested;
ProcessLoop(NL);
Changed = true;
goto ReprocessLoop;
}
}
InsertUniqueBackedgeBlock(L);
NumInserted++;
Changed = true;
}
PHINode *PN;
for (BasicBlock::iterator I = L->getHeader()->begin();
(PN = dyn_cast<PHINode>(I++)); )
if (Value *V = PN->hasConstantValue()) {
if (AA) AA->deleteValue(PN);
PN->replaceAllUsesWith(V);
PN->eraseFromParent();
}
return Changed;
}
void LoopSimplify::InsertPreheaderForLoop(Loop *L) {
BasicBlock *Header = L->getHeader();
SmallVector<BasicBlock*, 8> OutsideBlocks;
for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
PI != PE; ++PI)
if (!L->contains(*PI)) OutsideBlocks.push_back(*PI);
BasicBlock *NewBB =
SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(),
".preheader", this);
if (Loop *Parent = L->getParentLoop())
Parent->addBasicBlockToLoop(NewBB, LI->getBase());
PlaceSplitBlockCarefully(NewBB, OutsideBlocks, L);
}
BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) {
SmallVector<BasicBlock*, 8> LoopBlocks;
for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I)
if (L->contains(*I))
LoopBlocks.push_back(*I);
assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?");
BasicBlock *NewBB = SplitBlockPredecessors(Exit, &LoopBlocks[0],
LoopBlocks.size(), ".loopexit",
this);
Loop *SuccLoop = LI->getLoopFor(Exit);
while (SuccLoop && !SuccLoop->contains(L->getHeader()))
SuccLoop = SuccLoop->getParentLoop();
if (SuccLoop)
SuccLoop->addBasicBlockToLoop(NewBB, LI->getBase());
return NewBB;
}
static void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock,
std::set<BasicBlock*> &Blocks) {
std::vector<BasicBlock *> WorkList;
WorkList.push_back(InputBB);
do {
BasicBlock *BB = WorkList.back(); WorkList.pop_back();
if (Blocks.insert(BB).second && BB != StopBlock)
for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
BasicBlock *WBB = *I;
WorkList.push_back(WBB);
}
} while(!WorkList.empty());
}
static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT,
AliasAnalysis *AA) {
for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
PHINode *PN = cast<PHINode>(I);
++I;
if (Value *V = PN->hasConstantValue())
if (!isa<Instruction>(V) || DT->dominates(cast<Instruction>(V), PN)) {
PN->replaceAllUsesWith(V);
if (AA) AA->deleteValue(PN);
PN->eraseFromParent();
continue;
}
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
if (PN->getIncomingValue(i) == PN &&
L->contains(PN->getIncomingBlock(i)))
return PN;
}
return 0;
}
void LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB,
SmallVectorImpl<BasicBlock*> &SplitPreds,
Loop *L) {
Function::iterator BBI = NewBB; --BBI;
for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) {
if (&*BBI == SplitPreds[i])
return;
}
BasicBlock *FoundBB = 0;
for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) {
Function::iterator BBI = SplitPreds[i];
if (++BBI != NewBB->getParent()->end() &&
L->contains(BBI)) {
FoundBB = SplitPreds[i];
break;
}
}
if (!FoundBB)
FoundBB = SplitPreds[0];
NewBB->moveAfter(FoundBB);
}
Loop *LoopSimplify::SeparateNestedLoop(Loop *L) {
PHINode *PN = FindPHIToPartitionLoops(L, DT, AA);
if (PN == 0) return 0;
SmallVector<BasicBlock*, 8> OuterLoopPreds;
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
if (PN->getIncomingValue(i) != PN ||
!L->contains(PN->getIncomingBlock(i)))
OuterLoopPreds.push_back(PN->getIncomingBlock(i));
BasicBlock *Header = L->getHeader();
BasicBlock *NewBB = SplitBlockPredecessors(Header, &OuterLoopPreds[0],
OuterLoopPreds.size(),
".outer", this);
PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L);
Loop *NewOuter = new Loop();
if (Loop *Parent = L->getParentLoop())
Parent->replaceChildLoopWith(L, NewOuter);
else
LI->changeTopLevelLoop(L, NewOuter);
NewOuter->addBasicBlockToLoop(NewBB, LI->getBase());
NewOuter->addChildLoop(L);
for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
I != E; ++I)
NewOuter->addBlockEntry(*I);
std::set<BasicBlock*> BlocksInL;
for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI)
if (DT->dominates(Header, *PI))
AddBlockAndPredsToSet(*PI, Header, BlocksInL);
const std::vector<Loop*> &SubLoops = L->getSubLoops();
for (size_t I = 0; I != SubLoops.size(); )
if (BlocksInL.count(SubLoops[I]->getHeader()))
++I; else
NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I));
for (unsigned i = 0; i != L->getBlocks().size(); ++i) {
BasicBlock *BB = L->getBlocks()[i];
if (!BlocksInL.count(BB)) {
L->removeBlockFromLoop(BB);
if ((*LI)[BB] == L)
LI->changeLoopFor(BB, NewOuter);
--i;
}
}
return NewOuter;
}
void LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) {
assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!");
BasicBlock *Preheader = L->getLoopPreheader();
BasicBlock *Header = L->getHeader();
Function *F = Header->getParent();
std::vector<BasicBlock*> BackedgeBlocks;
for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I)
if (*I != Preheader) BackedgeBlocks.push_back(*I);
BasicBlock *BEBlock = BasicBlock::Create(Header->getName()+".backedge", F);
BranchInst *BETerminator = BranchInst::Create(Header, BEBlock);
Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos;
F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock);
for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
PHINode *PN = cast<PHINode>(I);
PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName()+".be",
BETerminator);
NewPN->reserveOperandSpace(BackedgeBlocks.size());
if (AA) AA->copyValue(PN, NewPN);
unsigned PreheaderIdx = ~0U;
bool HasUniqueIncomingValue = true;
Value *UniqueValue = 0;
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
BasicBlock *IBB = PN->getIncomingBlock(i);
Value *IV = PN->getIncomingValue(i);
if (IBB == Preheader) {
PreheaderIdx = i;
} else {
NewPN->addIncoming(IV, IBB);
if (HasUniqueIncomingValue) {
if (UniqueValue == 0)
UniqueValue = IV;
else if (UniqueValue != IV)
HasUniqueIncomingValue = false;
}
}
}
assert(PreheaderIdx != ~0U && "PHI has no preheader entry??");
if (PreheaderIdx != 0) {
PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx));
PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx));
}
for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i)
PN->removeIncomingValue(e-i, false);
PN->addIncoming(NewPN, BEBlock);
if (HasUniqueIncomingValue) {
NewPN->replaceAllUsesWith(UniqueValue);
if (AA) AA->deleteValue(NewPN);
BEBlock->getInstList().erase(NewPN);
}
}
for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) {
TerminatorInst *TI = BackedgeBlocks[i]->getTerminator();
for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op)
if (TI->getSuccessor(Op) == Header)
TI->setSuccessor(Op, BEBlock);
}
L->addBasicBlockToLoop(BEBlock, LI->getBase());
DT->splitBlock(BEBlock);
if (DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>())
DF->splitBlock(BEBlock);
}