//===----------------------------------------------------------------------===//
#include "llvm/Analysis/LoopInfo.h"
-#include "llvm/Constants.h"
-#include "llvm/Instructions.h"
-#include "llvm/Analysis/Dominators.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Analysis/LoopInfoImpl.h"
#include "llvm/Analysis/LoopIterator.h"
-#include "llvm/Assembly/Writer.h"
-#include "llvm/Support/CFG.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Metadata.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
-#include "llvm/ADT/DepthFirstIterator.h"
-#include "llvm/ADT/SmallPtrSet.h"
#include <algorithm>
using namespace llvm;
+// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
+template class llvm::LoopBase<BasicBlock, Loop>;
+template class llvm::LoopInfoBase<BasicBlock, Loop>;
+
// Always verify loopinfo if expensive checking is enabled.
#ifdef XDEBUG
static bool VerifyLoopInfo = true;
char LoopInfo::ID = 0;
INITIALIZE_PASS_BEGIN(LoopInfo, "loops", "Natural Loop Information", true, true)
-INITIALIZE_PASS_DEPENDENCY(DominatorTree)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_END(LoopInfo, "loops", "Natural Loop Information", true, true)
+// Loop identifier metadata name.
+static const char *const LoopMDName = "llvm.loop";
+
//===----------------------------------------------------------------------===//
// Loop implementation
//
// 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;
PHINode *Loop::getCanonicalInductionVariable() const {
BasicBlock *H = getHeader();
- BasicBlock *Incoming = 0, *Backedge = 0;
+ BasicBlock *Incoming = nullptr, *Backedge = nullptr;
pred_iterator PI = pred_begin(H);
assert(PI != pred_end(H) &&
"Loop must have at least one backedge!");
Backedge = *PI++;
- if (PI == pred_end(H)) return 0; // dead loop
+ if (PI == pred_end(H)) return nullptr; // dead loop
Incoming = *PI++;
- if (PI != pred_end(H)) return 0; // multiple backedges?
+ if (PI != pred_end(H)) return nullptr; // multiple backedges?
if (contains(Incoming)) {
if (contains(Backedge))
- return 0;
+ return nullptr;
std::swap(Incoming, Backedge);
} else if (!contains(Backedge))
- return 0;
+ return nullptr;
// Loop over all of the PHI nodes, looking for a canonical indvar.
for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
if (CI->equalsInt(1))
return PN;
}
- 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;
- }
+ return nullptr;
}
/// 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
- // lookups.
- SmallPtrSet<BasicBlock*, 16> 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)
- for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;
- ++UI) {
- User *U = *UI;
- BasicBlock *UserBB = cast<Instruction>(U)->getParent();
- if (PHINode *P = dyn_cast<PHINode>(U))
- UserBB = P->getIncomingBlock(UI);
+ for (Use &U : I->uses()) {
+ Instruction *UI = cast<Instruction>(U.getUser());
+ BasicBlock *UserBB = UI->getParent();
+ if (PHINode *P = dyn_cast<PHINode>(UI))
+ UserBB = P->getIncomingBlock(U);
// 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) &&
+ !contains(UserBB) &&
DT.isReachableFromEntry(UserBB))
return false;
}
return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
}
+/// isSafeToClone - Return true if the loop body is safe to clone in practice.
+/// Routines that reform the loop CFG and split edges often fail on indirectbr.
+bool Loop::isSafeToClone() const {
+ // Return false if any loop blocks contain indirectbrs, or there are any calls
+ // to noduplicate functions.
+ for (Loop::block_iterator I = block_begin(), E = block_end(); I != E; ++I) {
+ if (isa<IndirectBrInst>((*I)->getTerminator()))
+ return false;
+
+ if (const InvokeInst *II = dyn_cast<InvokeInst>((*I)->getTerminator()))
+ if (II->cannotDuplicate())
+ return false;
+
+ for (BasicBlock::iterator BI = (*I)->begin(), BE = (*I)->end(); BI != BE; ++BI) {
+ if (const CallInst *CI = dyn_cast<CallInst>(BI)) {
+ if (CI->cannotDuplicate())
+ return false;
+ }
+ }
+ }
+ return true;
+}
+
+MDNode *Loop::getLoopID() const {
+ MDNode *LoopID = nullptr;
+ if (isLoopSimplifyForm()) {
+ LoopID = getLoopLatch()->getTerminator()->getMetadata(LoopMDName);
+ } else {
+ // Go through each predecessor of the loop header and check the
+ // terminator for the metadata.
+ BasicBlock *H = getHeader();
+ for (block_iterator I = block_begin(), IE = block_end(); I != IE; ++I) {
+ TerminatorInst *TI = (*I)->getTerminator();
+ MDNode *MD = nullptr;
+
+ // Check if this terminator branches to the loop header.
+ for (unsigned i = 0, ie = TI->getNumSuccessors(); i != ie; ++i) {
+ if (TI->getSuccessor(i) == H) {
+ MD = TI->getMetadata(LoopMDName);
+ break;
+ }
+ }
+ if (!MD)
+ return nullptr;
+
+ if (!LoopID)
+ LoopID = MD;
+ else if (MD != LoopID)
+ return nullptr;
+ }
+ }
+ if (!LoopID || LoopID->getNumOperands() == 0 ||
+ LoopID->getOperand(0) != LoopID)
+ return nullptr;
+ return LoopID;
+}
+
+void Loop::setLoopID(MDNode *LoopID) const {
+ assert(LoopID && "Loop ID should not be null");
+ assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand");
+ assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself");
+
+ if (isLoopSimplifyForm()) {
+ getLoopLatch()->getTerminator()->setMetadata(LoopMDName, LoopID);
+ return;
+ }
+
+ BasicBlock *H = getHeader();
+ for (block_iterator I = block_begin(), IE = block_end(); I != IE; ++I) {
+ TerminatorInst *TI = (*I)->getTerminator();
+ for (unsigned i = 0, ie = TI->getNumSuccessors(); i != ie; ++i) {
+ if (TI->getSuccessor(i) == H)
+ TI->setMetadata(LoopMDName, LoopID);
+ }
+ }
+}
+
+bool Loop::isAnnotatedParallel() const {
+ MDNode *desiredLoopIdMetadata = getLoopID();
+
+ if (!desiredLoopIdMetadata)
+ return false;
+
+ // The loop branch contains the parallel loop metadata. In order to ensure
+ // that any parallel-loop-unaware optimization pass hasn't added loop-carried
+ // dependencies (thus converted the loop back to a sequential loop), check
+ // that all the memory instructions in the loop contain parallelism metadata
+ // that point to the same unique "loop id metadata" the loop branch does.
+ for (block_iterator BB = block_begin(), BE = block_end(); BB != BE; ++BB) {
+ for (BasicBlock::iterator II = (*BB)->begin(), EE = (*BB)->end();
+ II != EE; II++) {
+
+ if (!II->mayReadOrWriteMemory())
+ continue;
+
+ // The memory instruction can refer to the loop identifier metadata
+ // directly or indirectly through another list metadata (in case of
+ // nested parallel loops). The loop identifier metadata refers to
+ // itself so we can check both cases with the same routine.
+ MDNode *loopIdMD = II->getMetadata("llvm.mem.parallel_loop_access");
+
+ if (!loopIdMD)
+ return false;
+
+ bool loopIdMDFound = false;
+ for (unsigned i = 0, e = loopIdMD->getNumOperands(); i < e; ++i) {
+ if (loopIdMD->getOperand(i) == desiredLoopIdMetadata) {
+ loopIdMDFound = true;
+ break;
+ }
+ }
+
+ if (!loopIdMDFound)
+ return false;
+ }
+ }
+ return true;
+}
+
+
/// 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<BasicBlock *, 16> LoopBBs(block_begin(), block_end());
// Each predecessor of each exit block of a normal loop is contained
// within the loop.
SmallVector<BasicBlock *, 4> 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))
+ if (!contains(*PI))
return false;
// All the requirements are met.
return true;
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<BasicBlock *, 128> LoopBBs(block_begin(), block_end());
- std::sort(LoopBBs.begin(), LoopBBs.end());
-
SmallVector<BasicBlock *, 32> switchExitBlocks;
for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) {
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))
+ if (contains(*I))
continue;
pred_iterator PI = pred_begin(*I);
getUniqueExitBlocks(UniqueExitBlocks);
if (UniqueExitBlocks.size() == 1)
return UniqueExitBlocks[0];
- return 0;
+ return nullptr;
}
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void Loop::dump() const {
print(dbgs());
}
+#endif
//===----------------------------------------------------------------------===//
// UnloopUpdater implementation
//
+namespace {
/// Find the new parent loop for all blocks within the "unloop" whose last
/// backedges has just been removed.
class UnloopUpdater {
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".
/// removeBlocksFromAncestors - Remove unloop's blocks from all ancestors below
/// their new parents.
void UnloopUpdater::removeBlocksFromAncestors() {
- // Remove unloop's blocks from all ancestors below their new parents.
+ // 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 *NewParent = LI->getLoopFor(*BI);
- // If this block is an immediate subloop, remove all blocks (including
- // nested subloops) from ancestors below the new parent loop.
- // Otherwise, if this block is in a nested subloop, skip it.
- if (SubloopParents.count(NewParent))
- NewParent = SubloopParents[NewParent];
- else if (Unloop->contains(NewParent))
- continue;
-
+ 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 != NewParent;
+ for (Loop *OldParent = Unloop->getParentLoop(); OldParent != OuterParent;
OldParent = OldParent->getParentLoop()) {
assert(OldParent && "new loop is not an ancestor of the original");
OldParent->removeBlockFromLoop(*BI);
/// nested within unloop.
void UnloopUpdater::updateSubloopParents() {
while (!Unloop->empty()) {
- Loop *Subloop = *llvm::prior(Unloop->end());
- Unloop->removeChildLoop(llvm::prior(Unloop->end()));
+ Loop *Subloop = *std::prev(Unloop->end());
+ Unloop->removeChildLoop(std::prev(Unloop->end()));
assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
- if (SubloopParents[Subloop])
- SubloopParents[Subloop]->addChildLoop(Subloop);
+ if (Loop *Parent = SubloopParents[Subloop])
+ Parent->addChildLoop(Subloop);
+ else
+ LI->addTopLevelLoop(Subloop);
}
}
// is considered uninitialized.
Loop *NearLoop = BBLoop;
- Loop *Subloop = 0;
+ Loop *Subloop = nullptr;
if (NearLoop != Unloop && Unloop->contains(NearLoop)) {
Subloop = NearLoop;
// Find the subloop ancestor that is directly contained within Unloop.
assert(Subloop && "subloop is not an ancestor of the original loop");
}
// Get the current nearest parent of the Subloop exits, initially Unloop.
- if (!SubloopParents.count(Subloop))
- SubloopParents[Subloop] = Unloop;
- NearLoop = SubloopParents[Subloop];
+ NearLoop =
+ SubloopParents.insert(std::make_pair(Subloop, Unloop)).first->second;
}
succ_iterator I = succ_begin(BB), E = succ_end(BB);
if (I == E) {
assert(!Subloop && "subloop blocks must have a successor");
- NearLoop = 0; // unloop blocks may now exit the function.
+ NearLoop = nullptr; // unloop blocks may now exit the function.
}
for (; I != E; ++I) {
if (*I == BB)
//
bool LoopInfo::runOnFunction(Function &) {
releaseMemory();
- LI.Calculate(getAnalysis<DominatorTree>().getBase()); // Update
+ LI.Analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
return false;
}
// Blocks no longer have a parent but are still referenced by Unloop until
// the Unloop object is deleted.
- LI.changeLoopFor(*I, 0);
+ LI.changeLoopFor(*I, nullptr);
}
// Remove the loop from the top-level LoopInfo object.
// Move all of the subloops to the top-level.
while (!Unloop->empty())
- LI.addTopLevelLoop(Unloop->removeChildLoop(llvm::prior(Unloop->end())));
+ LI.addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
return;
}
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.
+ 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 {
AU.setPreservesAll();
- AU.addRequired<DominatorTree>();
+ AU.addRequired<DominatorTreeWrapperPass>();
}
void LoopInfo::print(raw_ostream &OS, const Module*) const {
projects / oota-llvm.git / blobdiff