//===----------------------------------------------------------------------===//
#include "llvm/Analysis/LoopInfo.h"
-#include "llvm/Constants.h"
-#include "llvm/Instructions.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfoImpl.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Assembly/Writer.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Metadata.h"
#include "llvm/Support/CFG.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;
INITIALIZE_PASS_DEPENDENCY(DominatorTree)
INITIALIZE_PASS_END(LoopInfo, "loops", "Natural Loop Information", true, true)
+// Loop identifier metadata name.
+static const char *const LoopMDName = "llvm.loop";
+
//===----------------------------------------------------------------------===//
// Loop implementation
//
/// 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)
// 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;
}
/// 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.
+ // 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->hasFnAttr(Attribute::NoDuplicate))
+ return false;
+
+ for (BasicBlock::iterator BI = (*I)->begin(), BE = (*I)->end(); BI != BE; ++BI) {
+ if (const CallInst *CI = dyn_cast<CallInst>(BI)) {
+ if (CI->hasFnAttr(Attribute::NoDuplicate))
+ return false;
+ }
+ }
}
return true;
}
+MDNode *Loop::getLoopID() const {
+ MDNode *LoopID = 0;
+ 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 = 0;
+
+ // 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 0;
+
+ if (!LoopID)
+ LoopID = MD;
+ else if (MD != LoopID)
+ return 0;
+ }
+ }
+ if (!LoopID || LoopID->getNumOperands() == 0 ||
+ LoopID->getOperand(0) != LoopID)
+ return 0;
+ 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);
projects / oota-llvm.git / blobdiff