46 cl::desc(
"Verify loop info (time consuming)"));
113 if (isa<LandingPadInst>(I))
148 "Loop must have at least one backedge!");
166 if (CI->isNullValue())
169 if (Inc->getOpcode() == Instruction::Add &&
170 Inc->getOperand(0) == PN)
171 if (
ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
172 if (CI->equalsInt(1))
187 if (
PHINode *
P = dyn_cast<PHINode>(U))
188 UserBB =
P->getIncomingBlock(UI);
219 if (isa<IndirectBrInst>((*I)->getTerminator()))
222 if (
const InvokeInst *II = dyn_cast<InvokeInst>((*I)->getTerminator()))
227 if (
const CallInst *CI = dyn_cast<CallInst>(BI)) {
260 else if (MD != LoopID)
271 assert(LoopID &&
"Loop ID should not be null");
272 assert(LoopID->
getNumOperands() > 0 &&
"Loop ID needs at least one operand");
273 assert(LoopID->
getOperand(0) == LoopID &&
"Loop ID should refer to itself");
293 if (!desiredLoopIdMetadata)
305 if (!II->mayReadOrWriteMemory())
312 MDNode *loopIdMD = II->getMetadata(
"llvm.mem.parallel_loop_access");
317 bool loopIdMDFound =
false;
318 for (
unsigned i = 0, e = loopIdMD->
getNumOperands(); i < e; ++i) {
319 if (loopIdMD->
getOperand(i) == desiredLoopIdMetadata) {
320 loopIdMDFound =
true;
340 for (
unsigned i = 0, e = ExitBlocks.
size(); i != e; ++i)
342 PE =
pred_end(ExitBlocks[i]); PI != PE; ++PI)
356 "getUniqueExitBlocks assumes the loop has canonical form exits!");
363 switchExitBlocks.
clear();
377 if (current != firstPred)
391 if (std::find(switchExitBlocks.
begin(), switchExitBlocks.
end(), *
I)
392 == switchExitBlocks.
end()) {
405 if (UniqueExitBlocks.
size() == 1)
406 return UniqueExitBlocks[0];
410 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
423 class UnloopUpdater {
441 Unloop(UL),
LI(LInfo), DFS(UL), FoundIB(
false) {}
443 void updateBlockParents();
445 void removeBlocksFromAncestors();
447 void updateSubloopParents();
456 void UnloopUpdater::updateBlockParents() {
457 if (Unloop->getNumBlocks()) {
462 POE = Traversal.
end(); POI != POE; ++POI) {
464 Loop *L =
LI->getLoopFor(*POI);
465 Loop *NL = getNearestLoop(*POI, L);
469 assert((NL != Unloop && (!NL || NL->
contains(Unloop))) &&
470 "uninitialized successor");
471 LI->changeLoopFor(*POI, NL);
476 assert((FoundIB || Unloop->contains(L)) &&
"uninitialized successor");
482 bool Changed = FoundIB;
483 for (
unsigned NIters = 0; Changed; ++NIters) {
484 assert(NIters < Unloop->getNumBlocks() &&
"runaway iterative algorithm");
490 POE = DFS.endPostorder(); POI != POE; ++POI) {
492 Loop *L =
LI->getLoopFor(*POI);
493 Loop *NL = getNearestLoop(*POI, L);
495 assert(NL != Unloop && (!NL || NL->
contains(Unloop)) &&
496 "uninitialized successor");
497 LI->changeLoopFor(*POI, NL);
506 void UnloopUpdater::removeBlocksFromAncestors() {
510 BE = Unloop->block_end(); BI != BE; ++BI) {
511 Loop *OuterParent =
LI->getLoopFor(*BI);
512 if (Unloop->contains(OuterParent)) {
515 OuterParent = SubloopParents[OuterParent];
521 assert(OldParent &&
"new loop is not an ancestor of the original");
522 OldParent->removeBlockFromLoop(*BI);
529 void UnloopUpdater::updateSubloopParents() {
530 while (!Unloop->empty()) {
532 Unloop->removeChildLoop(
llvm::prior(Unloop->end()));
534 assert(SubloopParents.count(Subloop) &&
"DFS failed to visit subloop");
535 if (
Loop *Parent = SubloopParents[Subloop])
536 Parent->addChildLoop(Subloop);
538 LI->addTopLevelLoop(Subloop);
551 Loop *NearLoop = BBLoop;
554 if (NearLoop != Unloop && Unloop->
contains(NearLoop)) {
559 assert(Subloop &&
"subloop is not an ancestor of the original loop");
563 SubloopParents.insert(std::make_pair(Subloop, Unloop)).first->second;
568 assert(!Subloop &&
"subloop blocks must have a successor");
571 for (; I != E; ++
I) {
575 Loop *L =
LI->getLoopFor(*I);
579 assert((FoundIB || !DFS.hasPostorder(*I)) &&
"should have seen IB");
582 if (L != Unloop && Unloop->
contains(L)) {
588 assert(L->
getParentLoop() == Unloop &&
"cannot skip into nested loops");
591 L = SubloopParents[L];
602 if (NearLoop == Unloop || !NearLoop || NearLoop->
contains(L))
606 SubloopParents[Subloop] = NearLoop;
617 LI.Analyze(getAnalysis<DominatorTree>().
getBase());
642 LI.changeLoopFor(*I, 0);
647 assert(I != LI.end() &&
"Couldn't find loop");
655 while (!Unloop->
empty())
663 UnloopUpdater Updater(Unloop,
this);
664 Updater.updateBlockParents();
667 Updater.removeBlocksFromAncestors();
670 Updater.updateSubloopParents();
675 assert(I != ParentLoop->
end() &&
"Couldn't find loop");
694 assert(!(*I)->getParentLoop() &&
"Top-level loop has a parent!");
695 (*I)->verifyLoopNest(&Loops);
700 E = LI.BBMap.end(); I != E; ++
I) {
701 assert(Loops.
count(I->second) &&
"orphaned loop");
702 assert(I->second->contains(I->first) &&
"orphaned block");
725 POE = Traversal.
end(); POI != POE; ++POI) ;
static const char *const LoopMDName
void push_back(const T &Elt)
BasicBlock * getUniqueExitBlock() const
virtual void releaseMemory()
static bool isLoopInvariant(Value *V, const Loop *L, const DominatorTree *DT)
static _Self begin(GraphT G)
virtual void verifyAnalysis() const
The main container class for the LLVM Intermediate Representation.
LoopInfoBase< BasicBlock, Loop >::iterator iterator
bool isReachableFromEntry(const BasicBlock *A) const
bool isAnnotatedParallel() const
unsigned getNumOperands() const
unsigned getNumOperands() const
getNumOperands - Return number of MDNode operands.
virtual void print(raw_ostream &O, const Module *M=0) const
LoopT * getParentLoop() const
void updateUnloop(Loop *Unloop)
MDNode - a tuple of other values.
BlockT * getHeader() const
LoopInfoBase< BlockT, LoopT > * LI
LoopT * removeChildLoop(iterator I)
BlockT * getLoopLatch() const
Value * getOperand(unsigned i) const LLVM_READONLY
getOperand - Return specified operand.
void print(raw_ostream &OS, unsigned Depth=0) const
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Traverse the blocks in a loop using a depth-first search.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
bool hasLoopInvariantOperands(Instruction *I) const
bool isLoopSimplifyForm() const
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Interval::succ_iterator succ_begin(Interval *I)
bool mayReadFromMemory() const
virtual bool runOnFunction(Function &F)
Loop * getLoopFor(const BasicBlock *BB) const
static cl::opt< bool, true > VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), cl::desc("Verify loop info (time consuming)"))
virtual void getAnalysisUsage(AnalysisUsage &AU) const
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Interval::succ_iterator succ_end(Interval *I)
unsigned getNumSuccessors() const
BlockT * getLoopPreheader() const
LLVM Basic Block Representation.
BasicBlock * getSuccessor(unsigned idx) const
static bool VerifyLoopInfo
Interval::pred_iterator pred_begin(Interval *I)
MDNode * getLoopID() const
bool contains(const LoopT *L) const
bool makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt=0) const
bool isSafeToClone() const
isSafeToClone - Return true if the loop body is safe to clone in practice.
Value * getOperand(unsigned i) const
Interval::pred_iterator pred_end(Interval *I)
bool hasDedicatedExits() const
void getUniqueExitBlocks(SmallVectorImpl< BasicBlock * > &ExitBlocks) const
Call cannot be duplicated.
void setMetadata(unsigned KindID, MDNode *Node)
bool isSafeToSpeculativelyExecute(const Value *V, const DataLayout *TD=0)
void setLoopID(MDNode *LoopID) const
bool count(const ValueT &V) const
Class for constant integers.
bool isLCSSAForm(DominatorTree &DT) const
isLCSSAForm - Return true if the Loop is in LCSSA form
MDNode * getMetadata(unsigned KindID) const
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
PHINode * getCanonicalInductionVariable() const
raw_ostream & dbgs()
dbgs - Return a circular-buffered debug stream.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
std::vector< BlockT * >::const_iterator block_iterator
block_iterator block_end() const
TerminatorInst * getTerminator()
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
std::vector< BasicBlock * >::const_iterator POIterator
Postorder list iterators.
LLVM Value Representation.
static const Function * getParent(const Value *V)
void moveBefore(Instruction *MovePos)
ItTy prior(ItTy it, Dist n)
block_iterator block_begin() const
static _Self end(GraphT G)
bool isLoopInvariant(Value *V) const
std::vector< LoopT * >::const_iterator iterator
LoopInfoBase< BasicBlock, Loop > & getBase()
LocationClass< Ty > location(Ty &L)