X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLoopInfo.cpp;h=0c725fcadff74316d40d3c91be5ebacfbe5b2603;hb=HEAD;hp=c200f9f36841030102218eefe0466535035fd15c;hpb=de5df29556542ad6a73d6bf0296a7c6b86afc760;p=oota-llvm.git diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp index c200f9f3684..0c725fcadff 100644 --- a/lib/Analysis/LoopInfo.cpp +++ b/lib/Analysis/LoopInfo.cpp @@ -26,8 +26,10 @@ #include "llvm/IR/Instructions.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Metadata.h" +#include "llvm/IR/PassManager.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" #include using namespace llvm; @@ -54,20 +56,16 @@ static const char *const LoopMDName = "llvm.loop"; /// isLoopInvariant - Return true if the specified value is loop invariant /// -bool Loop::isLoopInvariant(Value *V) const { - if (Instruction *I = dyn_cast(V)) +bool Loop::isLoopInvariant(const Value *V) const { + if (const Instruction *I = dyn_cast(V)) return !contains(I); return true; // All non-instructions are loop invariant } /// hasLoopInvariantOperands - Return true if all the operands of the /// specified instruction are loop invariant. -bool Loop::hasLoopInvariantOperands(Instruction *I) const { - for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) - if (!isLoopInvariant(I->getOperand(i))) - return false; - - return true; +bool Loop::hasLoopInvariantOperands(const Instruction *I) const { + return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); }); } /// makeLoopInvariant - If the given value is an instruciton inside of the @@ -104,8 +102,8 @@ bool Loop::makeLoopInvariant(Instruction *I, bool &Changed, return false; if (I->mayReadFromMemory()) return false; - // The landingpad instruction is immobile. - if (isa(I)) + // EH block instructions are immobile. + if (I->isEHPad()) return false; // Determine the insertion point, unless one was given. if (!InsertPt) { @@ -122,6 +120,13 @@ bool Loop::makeLoopInvariant(Instruction *I, bool &Changed, // Hoist. I->moveBefore(InsertPt); + + // There is possibility of hoisting this instruction above some arbitrary + // condition. Any metadata defined on it can be control dependent on this + // condition. Conservatively strip it here so that we don't give any wrong + // information to the optimizer. + I->dropUnknownNonDebugMetadata(); + Changed = true; return true; } @@ -174,7 +179,13 @@ PHINode *Loop::getCanonicalInductionVariable() const { bool Loop::isLCSSAForm(DominatorTree &DT) const { for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { BasicBlock *BB = *BI; - for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I) + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I) { + // Tokens can't be used in PHI nodes and live-out tokens prevent loop + // optimizations, so for the purposes of considered LCSSA form, we + // can ignore them. + if (I->getType()->isTokenTy()) + continue; + for (Use &U : I->uses()) { Instruction *UI = cast(U.getUser()); BasicBlock *UserBB = UI->getParent(); @@ -190,11 +201,21 @@ bool Loop::isLCSSAForm(DominatorTree &DT) const { DT.isReachableFromEntry(UserBB)) return false; } + } } return true; } +bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT) const { + if (!isLCSSAForm(DT)) + return false; + + return std::all_of(begin(), end(), [&](const Loop *L) { + return L->isRecursivelyLCSSAForm(DT); + }); +} + /// isLoopSimplifyForm - Return true if the Loop is in the form that /// the LoopSimplify form transforms loops to, which is sometimes called /// normal form. @@ -213,15 +234,23 @@ bool Loop::isSafeToClone() const { if (isa((*I)->getTerminator())) return false; - if (const InvokeInst *II = dyn_cast((*I)->getTerminator())) + if (const InvokeInst *II = dyn_cast((*I)->getTerminator())) { if (II->cannotDuplicate()) return false; + // Return false if any loop blocks contain invokes to EH-pads other than + // landingpads; we don't know how to split those edges yet. + auto *FirstNonPHI = II->getUnwindDest()->getFirstNonPHI(); + if (FirstNonPHI->isEHPad() && !isa(FirstNonPHI)) + return false; + } for (BasicBlock::iterator BI = (*I)->begin(), BE = (*I)->end(); BI != BE; ++BI) { if (const CallInst *CI = dyn_cast(BI)) { if (CI->cannotDuplicate()) return false; } + if (BI->getType()->isTokenTy() && BI->isUsedOutsideOfBlock(*I)) + return false; } } return true; @@ -604,20 +633,21 @@ Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { return NearLoop; } -/// updateUnloop - The last backedge has been removed from a loop--now the -/// "unloop". Find a new parent for the blocks contained within unloop and -/// update the loop tree. We don't necessarily have valid dominators at this -/// point, but LoopInfo is still valid except for the removal of this loop. -/// -/// Note that Unloop may now be an empty loop. Calling Loop::getHeader without -/// checking first is illegal. -void LoopInfo::updateUnloop(Loop *Unloop) { +LoopInfo::LoopInfo(const DominatorTreeBase &DomTree) { + analyze(DomTree); +} + +void LoopInfo::markAsRemoved(Loop *Unloop) { + assert(!Unloop->isInvalid() && "Loop has already been removed"); + Unloop->invalidate(); + RemovedLoops.push_back(Unloop); // First handle the special case of no parent loop to simplify the algorithm. if (!Unloop->getParentLoop()) { // Since BBLoop had no parent, Unloop blocks are no longer in a loop. for (Loop::block_iterator I = Unloop->block_begin(), - E = Unloop->block_end(); I != E; ++I) { + E = Unloop->block_end(); + I != E; ++I) { // Don't reparent blocks in subloops. if (getLoopFor(*I) != Unloop) @@ -625,21 +655,21 @@ void LoopInfo::updateUnloop(Loop *Unloop) { // Blocks no longer have a parent but are still referenced by Unloop until // the Unloop object is deleted. - LI.changeLoopFor(*I, nullptr); + changeLoopFor(*I, nullptr); } // Remove the loop from the top-level LoopInfo object. - for (LoopInfo::iterator I = LI.begin();; ++I) { - assert(I != LI.end() && "Couldn't find loop"); + for (iterator I = begin();; ++I) { + assert(I != end() && "Couldn't find loop"); if (*I == Unloop) { - LI.removeLoop(I); + removeLoop(I); break; } } // Move all of the subloops to the top-level. while (!Unloop->empty()) - LI.addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end()))); + addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end()))); return; } @@ -666,6 +696,40 @@ void LoopInfo::updateUnloop(Loop *Unloop) { } } +char LoopAnalysis::PassID; + +LoopInfo LoopAnalysis::run(Function &F, AnalysisManager *AM) { + // FIXME: Currently we create a LoopInfo from scratch for every function. + // This may prove to be too wasteful due to deallocating and re-allocating + // memory each time for the underlying map and vector datastructures. At some + // point it may prove worthwhile to use a freelist and recycle LoopInfo + // objects. I don't want to add that kind of complexity until the scope of + // the problem is better understood. + LoopInfo LI; + LI.analyze(AM->getResult(F)); + return LI; +} + +PreservedAnalyses LoopPrinterPass::run(Function &F, + AnalysisManager *AM) { + AM->getResult(F).print(OS); + return PreservedAnalyses::all(); +} + +PrintLoopPass::PrintLoopPass() : OS(dbgs()) {} +PrintLoopPass::PrintLoopPass(raw_ostream &OS, const std::string &Banner) + : OS(OS), Banner(Banner) {} + +PreservedAnalyses PrintLoopPass::run(Loop &L) { + OS << Banner; + for (auto *Block : L.blocks()) + if (Block) + Block->print(OS); + else + OS << "Printing block"; + return PreservedAnalyses::all(); +} + //===----------------------------------------------------------------------===// // LoopInfo implementation // @@ -679,7 +743,7 @@ INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information", bool LoopInfoWrapperPass::runOnFunction(Function &) { releaseMemory(); - LI.getBase().Analyze(getAnalysis().getDomTree()); + LI.analyze(getAnalysis().getDomTree()); return false; } @@ -689,22 +753,8 @@ void LoopInfoWrapperPass::verifyAnalysis() const { // -verify-loop-info option can enable this. In order to perform some // checking by default, LoopPass has been taught to call verifyLoop manually // during loop pass sequences. - - if (!VerifyLoopInfo) return; - - DenseSet Loops; - for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I) { - assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); - (*I)->verifyLoopNest(&Loops); - } - - // Verify that blocks are mapped to valid loops. - for (auto &Entry : LI.LI.BBMap) { - BasicBlock *BB = Entry.first; - Loop *L = Entry.second; - assert(Loops.count(L) && "orphaned loop"); - assert(L->contains(BB) && "orphaned block"); - } + if (VerifyLoopInfo) + LI.verify(); } void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { @@ -713,7 +763,7 @@ void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { } void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const { - LI.LI.print(OS); + LI.print(OS); } //===----------------------------------------------------------------------===//