X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLoopInfo.cpp;h=05831402f4092bcea8ccf670e5864f8fdab03f40;hb=12bf43bc4f86602a5677d5e1662cb4e40562351b;hp=db5ce2118cb5c7979d9c8038bd9c79f603c8bf31;hpb=16a2c927e95c29a316d0271c93e0490ce3bc06ce;p=oota-llvm.git diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp index db5ce2118cb..05831402f40 100644 --- a/lib/Analysis/LoopInfo.cpp +++ b/lib/Analysis/LoopInfo.cpp @@ -20,15 +20,27 @@ #include "llvm/Analysis/Dominators.h" #include "llvm/Assembly/Writer.h" #include "llvm/Support/CFG.h" -#include "llvm/Support/Streams.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 @@ -38,10 +50,73 @@ X("loops", "Natural Loop Information", true, true); /// bool Loop::isLoopInvariant(Value *V) const { if (Instruction *I = dyn_cast(V)) - return !contains(I->getParent()); + 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; +} + +/// makeLoopInvariant - If the given value is an instruciton inside of the +/// loop and it can be hoisted, do so to make it trivially loop-invariant. +/// Return true if the value after any hoisting is loop invariant. This +/// function can be used as a slightly more aggressive replacement for +/// isLoopInvariant. +/// +/// If InsertPt is specified, it is the point to hoist instructions to. +/// If null, the terminator of the loop preheader is used. +/// +bool Loop::makeLoopInvariant(Value *V, bool &Changed, + Instruction *InsertPt) const { + if (Instruction *I = dyn_cast(V)) + return makeLoopInvariant(I, Changed, InsertPt); + return true; // All non-instructions are loop-invariant. +} + +/// makeLoopInvariant - If the given instruction is inside of the +/// loop and it can be hoisted, do so to make it trivially loop-invariant. +/// Return true if the instruction after any hoisting is loop invariant. This +/// function can be used as a slightly more aggressive replacement for +/// isLoopInvariant. +/// +/// If InsertPt is specified, it is the point to hoist instructions to. +/// If null, the terminator of the loop preheader is used. +/// +bool Loop::makeLoopInvariant(Instruction *I, bool &Changed, + Instruction *InsertPt) const { + // Test if the value is already loop-invariant. + if (isLoopInvariant(I)) + return true; + if (!I->isSafeToSpeculativelyExecute()) + return false; + if (I->mayReadFromMemory()) + return false; + // Determine the insertion point, unless one was given. + if (!InsertPt) { + BasicBlock *Preheader = getLoopPreheader(); + // Without a preheader, hoisting is not feasible. + if (!Preheader) + return false; + InsertPt = Preheader->getTerminator(); + } + // Don't hoist instructions with loop-variant operands. + 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; + return true; +} + /// getCanonicalInductionVariable - Check to see if the loop has a canonical /// induction variable: an integer recurrence that starts at 0 and increments /// by one each time through the loop. If so, return the phi node that @@ -54,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)) @@ -87,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, @@ -110,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()) { @@ -136,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(); @@ -174,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; } @@ -188,30 +255,133 @@ 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; } } return true; } + +/// isLoopSimplifyForm - Return true if the Loop is in the form that +/// the LoopSimplify form transforms loops to, which is sometimes called +/// normal form. +bool Loop::isLoopSimplifyForm() const { + // 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; + getExitBlocks(ExitBlocks); + 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 (!LoopBBs.count(*PI)) + return false; + // All the requirements are met. + return true; +} + +/// 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 exits are in canonical form. +/// +void +Loop::getUniqueExitBlocks(SmallVectorImpl &ExitBlocks) const { + 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()); + + SmallVector switchExitBlocks; + + for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { + + BasicBlock *current = *BI; + switchExitBlocks.clear(); + + 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; + + pred_iterator PI = pred_begin(*I); + BasicBlock *firstPred = *PI; + + // If current basic block is this exit block's first predecessor + // then only insert exit block in to the output ExitBlocks vector. + // This ensures that same exit block is not inserted twice into + // ExitBlocks vector. + if (current != firstPred) + continue; + + // 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(succ_begin(current), succ_end(current)) <= 2) { + ExitBlocks.push_back(*I); + continue; + } + + // In case of multiple edges from current block to exit block, collect + // only one edge in ExitBlocks. Use switchExitBlocks to keep track of + // duplicate edges. + if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I) + == switchExitBlocks.end()) { + switchExitBlocks.push_back(*I); + ExitBlocks.push_back(*I); + } + } + } +} + +/// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one +/// block, return that block. Otherwise return null. +BasicBlock *Loop::getUniqueExitBlock() const { + SmallVector UniqueExitBlocks; + getUniqueExitBlocks(UniqueExitBlocks); + if (UniqueExitBlocks.size() == 1) + return UniqueExitBlocks[0]; + return 0; +} + +void Loop::dump() const { + print(dbgs()); +} + //===----------------------------------------------------------------------===// // LoopInfo implementation // @@ -221,7 +391,29 @@ bool LoopInfo::runOnFunction(Function &) { return false; } +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)->verifyLoopNest(); + } + + // TODO: check BBMap consistency. +} + void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequired(); } + +void LoopInfo::print(raw_ostream &OS, const Module*) const { + LI.print(OS); +} +