#include "llvm/Analysis/Dominators.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/CFG.h"
+#include "llvm/Support/CommandLine.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
#include <algorithm>
using namespace llvm;
+// Always verify loopinfo if expensive checking is enabled.
+#ifdef XDEBUG
+bool VerifyLoopInfo = true;
+#else
+bool VerifyLoopInfo = false;
+#endif
+static cl::opt<bool,true>
+VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
+ cl::desc("Verify loop info (time consuming)"));
+
char LoopInfo::ID = 0;
static RegisterPass<LoopInfo>
X("loops", "Natural Loop Information", true, true);
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;
}
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)
+ 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) {
BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
- if (PHINode *P = dyn_cast<PHINode>(*UI)) {
+ if (PHINode *P = dyn_cast<PHINode>(*UI))
UserBB = P->getIncomingBlock(UI);
- }
// Check the current block, as a fast-path. Most values are used in
// the same block they are defined in.
/// the LoopSimplify form transforms loops to, which is sometimes called
/// normal form.
bool Loop::isLoopSimplifyForm() const {
- // Normal-form loops have a preheader.
- if (!getLoopPreheader())
- return false;
- // Normal-form loops have a single backedge.
- if (!getLoopLatch())
- return false;
+ // Normal-form loops have a preheader, a single backedge, and all of their
+ // exits have all their predecessors inside the loop.
+ return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
+}
+
+/// 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 (!contains(*PI))
+ if (!LoopBBs.count(*PI))
return false;
// All the requirements are met.
return true;
}
void LoopInfo::verifyAnalysis() const {
+ // LoopInfo is a FunctionPass, but verifying every loop in the function
+ // each time verifyAnalysis is called is very expensive. The
+ // -verify-loop-info option can enable this. In order to perform some
+ // checking by default, LoopPass has been taught to call verifyLoop
+ // manually during loop pass sequences.
+
+ if (!VerifyLoopInfo) return;
+
for (iterator I = begin(), E = end(); I != E; ++I) {
assert(!(*I)->getParentLoop() && "Top-level loop has a parent!");
- (*I)->verifyLoop();
+ (*I)->verifyLoopNest();
}
+
+ // TODO: check BBMap consistency.
}
void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {