X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FLoopInfo.h;h=29781b2185db08e6762db8a3de1e981827a9a5d2;hb=529de8a45702cd34968d79d13f95ed1e5d5fa250;hp=21051ad61c67f5fb2cbec85b2a78c6db75e18d5c;hpb=b670a1737bae5c3ecc65042d3a1b10d774ecd252;p=oota-llvm.git diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index 21051ad61c6..29781b2185d 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -57,19 +57,25 @@ class LoopInfo; class PHINode; class Instruction; template class LoopInfoBase; +template class LoopBase; + +typedef LoopBase Loop; //===----------------------------------------------------------------------===// -/// LoopBase class - Instances of this class are used to represent loops that are -/// detected in the flow graph +/// LoopBase class - Instances of this class are used to represent loops that +/// are detected in the flow graph /// template class LoopBase { LoopBase *ParentLoop; - std::vector*> SubLoops; // Loops contained entirely within this one - std::vector Blocks; // First entry is the header node + // SubLoops - Loops contained entirely within this one. + std::vector*> SubLoops; + + // Blocks - The list of blocks in this loop. First entry is the header node. + std::vector Blocks; LoopBase(const LoopBase &); // DO NOT IMPLEMENT - const LoopBase &operator=(const LoopBase &); // DO NOT IMPLEMENT + const LoopBase&operator=(const LoopBase &);// DO NOT IMPLEMENT public: /// Loop ctor - This creates an empty loop. LoopBase() : ParentLoop(0) {} @@ -78,9 +84,12 @@ public: delete SubLoops[i]; } + /// getLoopDepth - Return the nesting level of this loop. An outer-most + /// loop has depth 1, for consistency with loop depth values used for basic + /// blocks, where depth 0 is used for blocks not inside any loops. unsigned getLoopDepth() const { - unsigned D = 0; - for (const LoopBase *CurLoop = this; CurLoop; + unsigned D = 1; + for (const LoopBase *CurLoop = ParentLoop; CurLoop; CurLoop = CurLoop->ParentLoop) ++D; return D; @@ -109,8 +118,8 @@ public: block_iterator block_begin() const { return Blocks.begin(); } block_iterator block_end() const { return Blocks.end(); } - /// isLoopExit - True if terminator in the block can branch to another block - /// that is outside of the current loop. + /// isLoopExit - True if this block can branch to another block that is + /// outside of the current loop. /// bool isLoopExit(const BlockT *BB) const { typedef GraphTraits BlockTraits; @@ -288,8 +297,8 @@ public: if (SI != BlockTraits::child_end(Out)) return 0; // Multiple exits from the block, must not be a preheader. - // If there is exactly one preheader, return it. If there was zero, then Out - // is still null. + // If there is exactly one preheader, return it. If there was zero, then + // Out is still null. return Out; } @@ -351,12 +360,16 @@ public: // Loop over all of the PHI nodes, looking for a canonical indvar. for (typename BlockT::iterator I = H->begin(); isa(I); ++I) { PHINode *PN = cast(I); - if (Instruction *Inc = - dyn_cast(PN->getIncomingValueForBlock(Backedge))) - if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN) - if (ConstantInt *CI = dyn_cast(Inc->getOperand(1))) - if (CI->equalsInt(1)) - return PN; + if (ConstantInt *CI = + dyn_cast(PN->getIncomingValueForBlock(Incoming))) + if (CI->isNullValue()) + if (Instruction *Inc = + dyn_cast(PN->getIncomingValueForBlock(Backedge))) + if (Inc->getOpcode() == Instruction::Add && + Inc->getOperand(0) == PN) + if (ConstantInt *CI = dyn_cast(Inc->getOperand(1))) + if (CI->equalsInt(1)) + return PN; } return 0; } @@ -391,13 +404,14 @@ public: if (BranchInst *BI = dyn_cast(BackedgeBlock->getTerminator())) if (BI->isConditional()) { if (ICmpInst *ICI = dyn_cast(BI->getCondition())) { - if (ICI->getOperand(0) == Inc) + if (ICI->getOperand(0) == Inc) { if (BI->getSuccessor(0) == getHeader()) { if (ICI->getPredicate() == ICmpInst::ICMP_NE) return ICI->getOperand(1); } else if (ICI->getPredicate() == ICmpInst::ICMP_EQ) { return ICI->getOperand(1); } + } } } @@ -412,7 +426,7 @@ public: for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { BlockT *BB = *BI; - for (typename BlockT::iterator I = BB->begin(), E = BB->end(); I != E; ++I) + for (typename BlockT::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) { BlockT *UserBB = cast(*UI)->getParent(); @@ -421,8 +435,8 @@ public: UserBB = P->getIncomingBlock(OperandNo/2); } - // Check the current block, as a fast-path. Most values are used in the - // same block they are defined in. + // 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)) return false; } @@ -549,8 +563,6 @@ private: } }; -typedef LoopBase Loop; - //===----------------------------------------------------------------------===// /// LoopInfo - This class builds and contains all of the top level loop @@ -573,7 +585,7 @@ public: TopLevelLoops.begin(), E = TopLevelLoops.end(); I != E; ++I) delete *I; // Delete all of the loops... - BBMap.clear(); // Reset internal state of analysis + BBMap.clear(); // Reset internal state of analysis TopLevelLoops.clear(); } @@ -599,7 +611,8 @@ public: return getLoopFor(BB); } - /// getLoopDepth - Return the loop nesting level of the specified block... + /// getLoopDepth - Return the loop nesting level of the specified block. A + /// depth of 0 means the block is not inside any loop. /// unsigned getLoopDepth(const BlockT *BB) const { const LoopBase *L = getLoopFor(BB); @@ -711,19 +724,20 @@ public: if (!L->contains(X) && // As of yet unprocessed?? DT.dominates(EntryBlock, X)) { // X is reachable from entry block? // Check to see if this block already belongs to a loop. If this occurs - // then we have a case where a loop that is supposed to be a child of the - // current loop was processed before the current loop. When this occurs, - // this child loop gets added to a part of the current loop, making it a - // sibling to the current loop. We have to reparent this loop. + // then we have a case where a loop that is supposed to be a child of + // the current loop was processed before the current loop. When this + // occurs, this child loop gets added to a part of the current loop, + // making it a sibling to the current loop. We have to reparent this + // loop. if (LoopBase *SubLoop = const_cast*>(getLoopFor(X))) - if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)) { + if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)){ // Remove the subloop from it's current parent... assert(SubLoop->ParentLoop && SubLoop->ParentLoop != L); LoopBase *SLP = SubLoop->ParentLoop; // SubLoopParent typename std::vector*>::iterator I = std::find(SLP->SubLoops.begin(), SLP->SubLoops.end(), SubLoop); - assert(I != SLP->SubLoops.end() && "SubLoop not a child of parent?"); + assert(I != SLP->SubLoops.end() &&"SubLoop not a child of parent?"); SLP->SubLoops.erase(I); // Remove from parent... // Add the subloop to THIS loop... @@ -762,8 +776,8 @@ public: } // Now that we have a list of all of the child loops of this loop, check to - // see if any of them should actually be nested inside of each other. We can - // accidentally pull loops our of their parents, so we must make sure to + // see if any of them should actually be nested inside of each other. We + // can accidentally pull loops our of their parents, so we must make sure to // organize the loop nests correctly now. { std::map*> ContainingLoops; @@ -778,9 +792,9 @@ public: MoveSiblingLoopInto(Child, ContainingLoop); --i; // The loop got removed from the SubLoops list. } else { - // This is currently considered to be a top-level loop. Check to see if - // any of the contained blocks are loop headers for subloops we have - // already processed. + // This is currently considered to be a top-level loop. Check to see + // if any of the contained blocks are loop headers for subloops we + // have already processed. for (unsigned b = 0, e = Child->Blocks.size(); b != e; ++b) { LoopBase *&BlockLoop = ContainingLoops[Child->Blocks[b]]; if (BlockLoop == 0) { // Child block not processed yet... @@ -805,8 +819,8 @@ public: return L; } - /// MoveSiblingLoopInto - This method moves the NewChild loop to live inside of - /// the NewParent Loop, instead of being a sibling of it. + /// MoveSiblingLoopInto - This method moves the NewChild loop to live inside + /// of the NewParent Loop, instead of being a sibling of it. void MoveSiblingLoopInto(LoopBase *NewChild, LoopBase *NewParent) { LoopBase *OldParent = NewChild->getParentLoop(); @@ -815,7 +829,8 @@ public: // Remove NewChild from being a child of OldParent typename std::vector*>::iterator I = - std::find(OldParent->SubLoops.begin(), OldParent->SubLoops.end(), NewChild); + std::find(OldParent->SubLoops.begin(), OldParent->SubLoops.end(), + NewChild); assert(I != OldParent->SubLoops.end() && "Parent fields incorrect??"); OldParent->SubLoops.erase(I); // Remove from parent's subloops list NewChild->ParentLoop = 0; @@ -823,12 +838,13 @@ public: InsertLoopInto(NewChild, NewParent); } - /// InsertLoopInto - This inserts loop L into the specified parent loop. If the - /// parent loop contains a loop which should contain L, the loop gets inserted - /// into L instead. + /// InsertLoopInto - This inserts loop L into the specified parent loop. If + /// the parent loop contains a loop which should contain L, the loop gets + /// inserted into L instead. void InsertLoopInto(LoopBase *L, LoopBase *Parent) { BlockT *LHeader = L->getHeader(); - assert(Parent->contains(LHeader) && "This loop should not be inserted here!"); + assert(Parent->contains(LHeader) && + "This loop should not be inserted here!"); // Check to see if it belongs in a child loop... for (unsigned i = 0, e = Parent->SubLoops.size(); i != e; ++i) @@ -891,7 +907,8 @@ public: return LI->getLoopFor(BB); } - /// getLoopDepth - Return the loop nesting level of the specified block... + /// getLoopDepth - Return the loop nesting level of the specified block. A + /// depth of 0 means the block is not inside any loop. /// inline unsigned getLoopDepth(const BasicBlock *BB) const { return LI->getLoopDepth(BB);