X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLoopInfo.cpp;h=05831402f4092bcea8ccf670e5864f8fdab03f40;hb=12bf43bc4f86602a5677d5e1662cb4e40562351b;hp=94dc15411340f5e0bfe31b6eee3d3a634a6fbb9f;hpb=8fc5ad33691b2a0672a7487da1f56b6f7f675a1b;p=oota-llvm.git diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp index 94dc1541134..05831402f40 100644 --- a/lib/Analysis/LoopInfo.cpp +++ b/lib/Analysis/LoopInfo.cpp @@ -20,14 +20,27 @@ #include "llvm/Analysis/Dominators.h" #include "llvm/Assembly/Writer.h" #include "llvm/Support/CFG.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include using namespace llvm; +// Always verify loopinfo if expensive checking is enabled. +#ifdef XDEBUG +static bool VerifyLoopInfo = true; +#else +static bool VerifyLoopInfo = false; +#endif +static cl::opt +VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), + cl::desc("Verify loop info (time consuming)")); + char LoopInfo::ID = 0; -static RegisterPass -X("loops", "Natural Loop Information", true, true); +INITIALIZE_PASS_BEGIN(LoopInfo, "loops", "Natural Loop Information", true, true) +INITIALIZE_PASS_DEPENDENCY(DominatorTree) +INITIALIZE_PASS_END(LoopInfo, "loops", "Natural Loop Information", true, true) //===----------------------------------------------------------------------===// // Loop implementation @@ -37,15 +50,18 @@ X("loops", "Natural Loop Information", true, true); /// bool Loop::isLoopInvariant(Value *V) const { if (Instruction *I = dyn_cast(V)) - return isLoopInvariant(I); + return !contains(I); return true; // All non-instructions are loop invariant } -/// isLoopInvariant - Return true if the specified instruction is -/// loop-invariant. -/// -bool Loop::isLoopInvariant(Instruction *I) const { - return !contains(I->getParent()); +/// 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; } /// makeLoopInvariant - If the given value is an instruciton inside of the @@ -94,6 +110,7 @@ bool Loop::makeLoopInvariant(Instruction *I, bool &Changed, for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) if (!makeLoopInvariant(I->getOperand(i), Changed, InsertPt)) return false; + // Hoist. I->moveBefore(InsertPt); Changed = true; @@ -112,14 +129,13 @@ PHINode *Loop::getCanonicalInductionVariable() const { BasicBlock *H = getHeader(); BasicBlock *Incoming = 0, *Backedge = 0; - typedef GraphTraits > InvBlockTraits; - InvBlockTraits::ChildIteratorType PI = InvBlockTraits::child_begin(H); - assert(PI != InvBlockTraits::child_end(H) && + pred_iterator PI = pred_begin(H); + assert(PI != pred_end(H) && "Loop must have at least one backedge!"); Backedge = *PI++; - if (PI == InvBlockTraits::child_end(H)) return 0; // dead loop + if (PI == pred_end(H)) return 0; // dead loop Incoming = *PI++; - if (PI != InvBlockTraits::child_end(H)) return 0; // multiple backedges? + if (PI != pred_end(H)) return 0; // multiple backedges? if (contains(Incoming)) { if (contains(Backedge)) @@ -145,18 +161,6 @@ PHINode *Loop::getCanonicalInductionVariable() const { return 0; } -/// getCanonicalInductionVariableIncrement - Return the LLVM value that holds -/// the canonical induction variable value for the "next" iteration of the -/// loop. This always succeeds if getCanonicalInductionVariable succeeds. -/// -Instruction *Loop::getCanonicalInductionVariableIncrement() const { - if (PHINode *PN = getCanonicalInductionVariable()) { - bool P1InLoop = contains(PN->getIncomingBlock(1)); - return cast(PN->getIncomingValue(P1InLoop)); - } - return 0; -} - /// getTripCount - Return a loop-invariant LLVM value indicating the number of /// times the loop will be executed. Note that this means that the backedge /// of the loop executes N-1 times. If the trip-count cannot be determined, @@ -168,12 +172,12 @@ Instruction *Loop::getCanonicalInductionVariableIncrement() const { Value *Loop::getTripCount() const { // Canonical loops will end with a 'cmp ne I, V', where I is the incremented // canonical induction variable and V is the trip count of the loop. - Instruction *Inc = getCanonicalInductionVariableIncrement(); - if (Inc == 0) return 0; - PHINode *IV = cast(Inc->getOperand(0)); + PHINode *IV = getCanonicalInductionVariable(); + if (IV == 0 || IV->getNumIncomingValues() != 2) return 0; - BasicBlock *BackedgeBlock = - IV->getIncomingBlock(contains(IV->getIncomingBlock(1))); + bool P0InLoop = contains(IV->getIncomingBlock(0)); + Value *Inc = IV->getIncomingValue(!P0InLoop); + BasicBlock *BackedgeBlock = IV->getIncomingBlock(!P0InLoop); if (BranchInst *BI = dyn_cast(BackedgeBlock->getTerminator())) if (BI->isConditional()) { @@ -194,7 +198,7 @@ Value *Loop::getTripCount() const { /// getSmallConstantTripCount - Returns the trip count of this loop as a /// normal unsigned value, if possible. Returns 0 if the trip count is unknown -/// of not constant. Will also return 0 if the trip count is very large +/// or not constant. Will also return 0 if the trip count is very large /// (>= 2^32) unsigned Loop::getSmallConstantTripCount() const { Value* TripCount = this->getTripCount(); @@ -232,6 +236,11 @@ unsigned Loop::getSmallConstantTripMultiple() const { case BinaryOperator::Mul: Result = dyn_cast(BO->getOperand(1)); break; + case BinaryOperator::Shl: + if (ConstantInt *CI = dyn_cast(BO->getOperand(1))) + if (CI->getValue().getActiveBits() <= 5) + return 1u << CI->getZExtValue(); + break; default: break; } @@ -246,24 +255,28 @@ unsigned Loop::getSmallConstantTripMultiple() const { } /// isLCSSAForm - Return true if the Loop is in LCSSA form -bool Loop::isLCSSAForm() const { +bool Loop::isLCSSAForm(DominatorTree &DT) const { // Sort the blocks vector so that we can use binary search to do quick // lookups. - SmallPtrSet LoopBBs(block_begin(), block_end()); + SmallPtrSet LoopBBs(block_begin(), block_end()); 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) + BasicBlock *BB = *BI; + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;++I) for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI) { - BasicBlock *UserBB = cast(*UI)->getParent(); - if (PHINode *P = dyn_cast(*UI)) { + User *U = *UI; + BasicBlock *UserBB = cast(U)->getParent(); + if (PHINode *P = dyn_cast(U)) UserBB = P->getIncomingBlock(UI); - } - // Check the current block, as a fast-path. Most values are used in - // the same block they are defined in. - if (UserBB != BB && !LoopBBs.count(UserBB)) + // Check the current block, as a fast-path, before checking whether + // the use is anywhere in the loop. Most values are used in the same + // block they are defined in. Also, blocks not reachable from the + // entry are special; uses in them don't need to go through PHIs. + if (UserBB != BB && + !LoopBBs.count(UserBB) && + DT.isReachableFromEntry(UserBB)) return false; } } @@ -275,12 +288,17 @@ bool Loop::isLCSSAForm() const { /// the LoopSimplify form transforms loops to, which is sometimes called /// normal form. bool Loop::isLoopSimplifyForm() const { - // Normal-form loops have a preheader. - if (!getLoopPreheader()) - return false; - // Normal-form loops have a single backedge. - if (!getLoopLatch()) - return false; + // Normal-form loops have a preheader, a single backedge, and all of their + // exits have all their predecessors inside the loop. + return getLoopPreheader() && getLoopLatch() && hasDedicatedExits(); +} + +/// hasDedicatedExits - Return true if no exit block for the loop +/// has a predecessor that is outside the loop. +bool Loop::hasDedicatedExits() const { + // Sort the blocks vector so that we can use binary search to do quick + // lookups. + SmallPtrSet LoopBBs(block_begin(), block_end()); // Each predecessor of each exit block of a normal loop is contained // within the loop. SmallVector ExitBlocks; @@ -288,7 +306,7 @@ bool Loop::isLoopSimplifyForm() const { for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) for (pred_iterator PI = pred_begin(ExitBlocks[i]), PE = pred_end(ExitBlocks[i]); PI != PE; ++PI) - if (!contains(*PI)) + if (!LoopBBs.count(*PI)) return false; // All the requirements are met. return true; @@ -296,35 +314,31 @@ bool Loop::isLoopSimplifyForm() const { /// getUniqueExitBlocks - Return all unique successor blocks of this loop. /// These are the blocks _outside of the current loop_ which are branched to. -/// This assumes that loop is in canonical form. +/// This assumes that loop exits are in canonical form. /// void Loop::getUniqueExitBlocks(SmallVectorImpl &ExitBlocks) const { - assert(isLoopSimplifyForm() && - "getUniqueExitBlocks assumes the loop is in canonical form!"); + assert(hasDedicatedExits() && + "getUniqueExitBlocks assumes the loop has canonical form exits!"); // Sort the blocks vector so that we can use binary search to do quick // lookups. SmallVector LoopBBs(block_begin(), block_end()); std::sort(LoopBBs.begin(), LoopBBs.end()); - std::vector switchExitBlocks; + SmallVector switchExitBlocks; for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { BasicBlock *current = *BI; switchExitBlocks.clear(); - typedef GraphTraits BlockTraits; - typedef GraphTraits > InvBlockTraits; - for (BlockTraits::ChildIteratorType I = - BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); - I != E; ++I) { + for (succ_iterator I = succ_begin(*BI), E = succ_end(*BI); I != E; ++I) { // If block is inside the loop then it is not a exit block. if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) continue; - InvBlockTraits::ChildIteratorType PI = InvBlockTraits::child_begin(*I); + pred_iterator PI = pred_begin(*I); BasicBlock *firstPred = *PI; // If current basic block is this exit block's first predecessor @@ -337,8 +351,7 @@ Loop::getUniqueExitBlocks(SmallVectorImpl &ExitBlocks) const { // If a terminator has more then two successors, for example SwitchInst, // then it is possible that there are multiple edges from current block // to one exit block. - if (std::distance(BlockTraits::child_begin(current), - BlockTraits::child_end(current)) <= 2) { + if (std::distance(succ_begin(current), succ_end(current)) <= 2) { ExitBlocks.push_back(*I); continue; } @@ -365,6 +378,10 @@ BasicBlock *Loop::getUniqueExitBlock() const { return 0; } +void Loop::dump() const { + print(dbgs()); +} + //===----------------------------------------------------------------------===// // LoopInfo implementation // @@ -375,10 +392,20 @@ bool LoopInfo::runOnFunction(Function &) { } void LoopInfo::verifyAnalysis() const { + // LoopInfo is a FunctionPass, but verifying every loop in the function + // each time verifyAnalysis is called is very expensive. The + // -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; + for (iterator I = begin(), E = end(); I != E; ++I) { assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); - (*I)->verifyLoop(); + (*I)->verifyLoopNest(); } + + // TODO: check BBMap consistency. } void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {