#include <algorithm>
#include <ostream>
+namespace llvm {
+
template<typename T>
static void RemoveFromVector(std::vector<T*> &V, T *N) {
typename std::vector<T*>::iterator I = std::find(V.begin(), V.end(), N);
V.erase(I);
}
-namespace llvm {
-
class DominatorTree;
class LoopInfo;
class PHINode;
class Instruction;
template<class N> class LoopInfoBase;
+template<class N> class LoopBase;
+
+typedef LoopBase<BasicBlock> Loop;
//===----------------------------------------------------------------------===//
/// LoopBase class - Instances of this class are used to represent loops that
/// Loop ctor - This creates an empty loop.
LoopBase() : ParentLoop(0) {}
~LoopBase() {
- for (unsigned i = 0, e = SubLoops.size(); i != e; ++i)
+ for (size_t i = 0, e = SubLoops.size(); i != e; ++i)
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<BlockT> *CurLoop = this; CurLoop;
+ unsigned D = 1;
+ for (const LoopBase<BlockT> *CurLoop = ParentLoop; CurLoop;
CurLoop = CurLoop->ParentLoop)
++D;
return D;
// Loop over all of the PHI nodes, looking for a canonical indvar.
for (typename BlockT::iterator I = H->begin(); isa<PHINode>(I); ++I) {
PHINode *PN = cast<PHINode>(I);
- if (Instruction *Inc =
- dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
- if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN)
- if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
- if (CI->equalsInt(1))
- return PN;
+ if (ConstantInt *CI =
+ dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
+ if (CI->isNullValue())
+ if (Instruction *Inc =
+ dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
+ if (Inc->getOpcode() == Instruction::Add &&
+ Inc->getOperand(0) == PN)
+ if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
+ if (CI->equalsInt(1))
+ return PN;
}
return 0;
}
if (BranchInst *BI = dyn_cast<BranchInst>(BackedgeBlock->getTerminator()))
if (BI->isConditional()) {
if (ICmpInst *ICI = dyn_cast<ICmpInst>(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);
}
+ }
}
}
return 0;
}
+ /// 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
+ /// (>= 2^32)
+ inline unsigned getSmallConstantTripCount() const {
+ Value* TripCount = this->getTripCount();
+ if (TripCount) {
+ if (ConstantInt *TripCountC = dyn_cast<ConstantInt>(TripCount)) {
+ // Guard against huge trip counts.
+ if (TripCountC->getValue().getActiveBits() <= 32) {
+ return (unsigned)TripCountC->getZExtValue();
+ }
+ }
+ }
+ return 0;
+ }
+
+ /// getSmallConstantTripMultiple - Returns the largest constant divisor of the
+ /// trip count of this loop as a normal unsigned value, if possible. This
+ /// means that the actual trip count is always a multiple of the returned
+ /// value (don't forget the trip count could very well be zero as well!).
+ ///
+ /// Returns 1 if the trip count is unknown or not guaranteed to be the
+ /// multiple of a constant (which is also the case if the trip count is simply
+ /// constant, use getSmallConstantTripCount for that case), Will also return 1
+ /// if the trip count is very large (>= 2^32).
+ inline unsigned getSmallConstantTripMultiple() const {
+ Value* TripCount = this->getTripCount();
+ // This will hold the ConstantInt result, if any
+ ConstantInt *Result = NULL;
+ if (TripCount) {
+ // See if the trip count is constant itself
+ Result = dyn_cast<ConstantInt>(TripCount);
+ // if not, see if it is a multiplication
+ if (!Result)
+ if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TripCount)) {
+ switch (BO->getOpcode()) {
+ case BinaryOperator::Mul:
+ Result = dyn_cast<ConstantInt>(BO->getOperand(1));
+ break;
+ default:
+ break;
+ }
+ }
+ }
+ // Guard against huge trip counts.
+ if (Result && Result->getValue().getActiveBits() <= 32) {
+ return (unsigned)Result->getZExtValue();
+ } else {
+ return 1;
+ }
+ }
+
/// isLCSSAForm - Return true if the Loop is in LCSSA form
inline bool isLCSSAForm() const {
// Sort the blocks vector so that we can use binary search to do quick
}
};
-typedef LoopBase<BasicBlock> Loop;
-
//===----------------------------------------------------------------------===//
/// LoopInfo - This class builds and contains all of the top level loop
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<BlockT> *L = getLoopFor(BB);
"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)
+ for (unsigned i = 0, e = static_cast<unsigned>(Parent->SubLoops.size());
+ i != e; ++i)
if (Parent->SubLoops[i]->contains(LHeader)) {
InsertLoopInto(L, Parent->SubLoops[i]);
return;
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);
} // End llvm namespace
-// Make sure that any clients of this file link in LoopInfo.cpp
-FORCE_DEFINING_FILE_TO_BE_LINKED(LoopInfo)
-
#endif