#include "llvm/Instructions.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopIterator.h"
+#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/CommandLine.h"
// Test if the value is already loop-invariant.
if (isLoopInvariant(I))
return true;
- if (!I->isSafeToSpeculativelyExecute())
+ if (!isSafeToSpeculativelyExecute(I))
return false;
if (I->mayReadFromMemory())
return false;
+ // The landingpad instruction is immobile.
+ if (isa<LandingPadInst>(I))
+ return false;
// Determine the insertion point, unless one was given.
if (!InsertPt) {
BasicBlock *Preheader = getLoopPreheader();
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,
-/// this returns null.
-///
-/// The IndVarSimplify pass transforms loops to have a form that this
-/// function easily understands.
-///
-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.
- PHINode *IV = getCanonicalInductionVariable();
- if (IV == 0 || IV->getNumIncomingValues() != 2) return 0;
-
- bool P0InLoop = contains(IV->getIncomingBlock(0));
- Value *Inc = IV->getIncomingValue(!P0InLoop);
- BasicBlock *BackedgeBlock = IV->getIncomingBlock(!P0InLoop);
-
- 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 (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
-/// or not constant. Will also return 0 if the trip count is very large
-/// (>= 2^32)
-unsigned Loop::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).
-unsigned Loop::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;
- case BinaryOperator::Shl:
- if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1)))
- if (CI->getValue().getActiveBits() <= 5)
- return 1u << CI->getZExtValue();
- 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
bool Loop::isLCSSAForm(DominatorTree &DT) const {
// Sort the blocks vector so that we can use binary search to do quick
// UnloopUpdater implementation
//
+namespace {
/// Find the new parent loop for all blocks within the "unloop" whose last
/// backedges has just been removed.
class UnloopUpdater {
void updateBlockParents();
+ void removeBlocksFromAncestors();
+
void updateSubloopParents();
protected:
Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
};
+} // end anonymous namespace
/// updateBlockParents - Update the parent loop for all blocks that are directly
/// contained within the original "unloop".
void UnloopUpdater::updateBlockParents() {
- {
+ if (Unloop->getNumBlocks()) {
// Perform a post order CFG traversal of all blocks within this loop,
// propagating the nearest loop from sucessors to predecessors.
LoopBlocksTraversal Traversal(DFS, LI);
}
}
+/// removeBlocksFromAncestors - Remove unloop's blocks from all ancestors below
+/// their new parents.
+void UnloopUpdater::removeBlocksFromAncestors() {
+ // Remove all unloop's blocks (including those in nested subloops) from
+ // ancestors below the new parent loop.
+ for (Loop::block_iterator BI = Unloop->block_begin(),
+ BE = Unloop->block_end(); BI != BE; ++BI) {
+ Loop *OuterParent = LI->getLoopFor(*BI);
+ if (Unloop->contains(OuterParent)) {
+ while (OuterParent->getParentLoop() != Unloop)
+ OuterParent = OuterParent->getParentLoop();
+ OuterParent = SubloopParents[OuterParent];
+ }
+ // Remove blocks from former Ancestors except Unloop itself which will be
+ // deleted.
+ for (Loop *OldParent = Unloop->getParentLoop(); OldParent != OuterParent;
+ OldParent = OldParent->getParentLoop()) {
+ assert(OldParent && "new loop is not an ancestor of the original");
+ OldParent->removeBlockFromLoop(*BI);
+ }
+ }
+}
+
/// updateSubloopParents - Update the parent loop for all subloops directly
/// nested within unloop.
void UnloopUpdater::updateSubloopParents() {
while (!Unloop->empty()) {
- Loop *Subloop = *(Unloop->end()-1);
- Unloop->removeChildLoop(Unloop->end()-1);
+ Loop *Subloop = *llvm::prior(Unloop->end());
+ Unloop->removeChildLoop(llvm::prior(Unloop->end()));
assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
if (SubloopParents[Subloop])
SubloopParents[Subloop]->addChildLoop(Subloop);
+ else
+ LI->addTopLevelLoop(Subloop);
}
}
/// For subloop blocks, simply update SubloopParents and return NULL.
Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
- // Initialy for blocks directly contained by Unloop, NearLoop == Unloop and is
- // considered uninitialized.
+ // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
+ // is considered uninitialized.
Loop *NearLoop = BBLoop;
Loop *Subloop = 0;
/// 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 necessarilly have valid dominators at this
+/// 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) {
// First handle the special case of no parent loop to simplify the algorithm.
}
// Remove the loop from the top-level LoopInfo object.
- for (LoopInfo::iterator I = LI.begin(), E = LI.end();; ++I) {
- assert(I != E && "Couldn't find loop");
+ for (LoopInfo::iterator I = LI.begin();; ++I) {
+ assert(I != LI.end() && "Couldn't find loop");
if (*I == Unloop) {
LI.removeLoop(I);
break;
// Move all of the subloops to the top-level.
while (!Unloop->empty())
- LI.addTopLevelLoop(Unloop->removeChildLoop(Unloop->end()-1));
+ LI.addTopLevelLoop(Unloop->removeChildLoop(llvm::prior(Unloop->end())));
return;
}
UnloopUpdater Updater(Unloop, this);
Updater.updateBlockParents();
- // Remove unloop's blocks from all ancestors below their new parents.
- for (Loop::block_iterator BI = Unloop->block_begin(),
- BE = Unloop->block_end(); BI != BE; ++BI) {
- Loop *NewParent = getLoopFor(*BI);
- // If this block is in a subloop, skip it.
- if (Unloop->contains(NewParent))
- continue;
-
- // Remove blocks from former Ancestors except Unloop itself which will be
- // deleted.
- for (Loop *OldParent = Unloop->getParentLoop(); OldParent != NewParent;
- OldParent = OldParent->getParentLoop()) {
- assert(OldParent && "new loop is not an ancestor of the original");
- OldParent->removeBlockFromLoop(*BI);
- }
- }
+ // Remove blocks from former ancestor loops.
+ Updater.removeBlocksFromAncestors();
// Add direct subloops as children in their new parent loop.
Updater.updateSubloopParents();
// Remove unloop from its parent loop.
Loop *ParentLoop = Unloop->getParentLoop();
- for (Loop::iterator I = ParentLoop->begin(), E = ParentLoop->end();; ++I) {
- assert(I != E && "Couldn't find loop");
+ for (Loop::iterator I = ParentLoop->begin();; ++I) {
+ assert(I != ParentLoop->end() && "Couldn't find loop");
if (*I == Unloop) {
ParentLoop->removeChildLoop(I);
break;
if (!VerifyLoopInfo) return;
+ DenseSet<const Loop*> Loops;
for (iterator I = begin(), E = end(); I != E; ++I) {
assert(!(*I)->getParentLoop() && "Top-level loop has a parent!");
- (*I)->verifyLoopNest();
+ (*I)->verifyLoopNest(&Loops);
}
- // TODO: check BBMap consistency.
+ // Verify that blocks are mapped to valid loops.
+ //
+ // FIXME: With an up-to-date DFS (see LoopIterator.h) and DominatorTree, we
+ // could also verify that the blocks are still in the correct loops.
+ for (DenseMap<BasicBlock*, Loop*>::const_iterator I = LI.BBMap.begin(),
+ E = LI.BBMap.end(); I != E; ++I) {
+ assert(Loops.count(I->second) && "orphaned loop");
+ assert(I->second->contains(I->first) && "orphaned block");
+ }
}
void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
LI.print(OS);
}
+//===----------------------------------------------------------------------===//
+// LoopBlocksDFS implementation
+//
+
+/// Traverse the loop blocks and store the DFS result.
+/// Useful for clients that just want the final DFS result and don't need to
+/// visit blocks during the initial traversal.
+void LoopBlocksDFS::perform(LoopInfo *LI) {
+ LoopBlocksTraversal Traversal(*this, LI);
+ for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
+ POE = Traversal.end(); POI != POE; ++POI) ;
+}
projects / oota-llvm.git / blobdiff