* Implement dominator based loop identification
* Implement cleaner induction variable identification
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@1359 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/InductionVariable.cpp b/lib/Analysis/InductionVariable.cpp
new file mode 100644
index 0000000..706c778
--- /dev/null
+++ b/lib/Analysis/InductionVariable.cpp
@@ -0,0 +1,138 @@
+//===- llvm/Analysis/InductionVariable.h - Induction variable ----*- C++ -*--=//
+//
+// This interface is used to identify and classify induction variables that
+// exist in the program. Induction variables must contain a PHI node that
+// exists in a loop header. Because of this, they are identified an managed by
+// this PHI node.
+//
+// Induction variables are classified into a type. Knowing that an induction
+// variable is of a specific type can constrain the values of the start and
+// step. For example, a SimpleLinear induction variable must have a start and
+// step values that are constants.
+//
+// Induction variables can be created with or without loop information. If no
+// loop information is available, induction variables cannot be recognized to be
+// more than SimpleLinear variables.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/InductionVariable.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/Expressions.h"
+#include "llvm/iOther.h"
+#include "llvm/Type.h"
+#include "llvm/ConstPoolVals.h"
+
+using analysis::ExprType;
+
+
+static bool isLoopInvariant(const Value *V, const cfg::Loop *L) {
+ if (isa<ConstPoolVal>(V) || isa<MethodArgument>(V) || isa<GlobalValue>(V))
+ return true;
+
+ const Instruction *I = cast<Instruction>(V);
+ const BasicBlock *BB = I->getParent();
+
+ return !L->contains(BB);
+}
+
+enum InductionVariable::iType
+InductionVariable::Classify(const Value *Start, const Value *Step,
+ const cfg::Loop *L = 0) {
+ // Check for cannonical and simple linear expressions now...
+ if (ConstPoolInt *CStart = dyn_cast<ConstPoolInt>(Start))
+ if (ConstPoolInt *CStep = dyn_cast<ConstPoolInt>(Step)) {
+ if (CStart->equalsInt(0) && CStep->equalsInt(1))
+ return Cannonical;
+ else
+ return SimpleLinear;
+ }
+
+ // Without loop information, we cannot do any better, so bail now...
+ if (L == 0) return Unknown;
+
+ if (isLoopInvariant(Start, L) && isLoopInvariant(Step, L))
+ return Linear;
+ return Unknown;
+}
+
+// Create an induction variable for the specified value. If it is a PHI, and
+// if it's recognizable, classify it and fill in instance variables.
+//
+InductionVariable::InductionVariable(Instruction *V, cfg::LoopInfo *LoopInfo) {
+ InductionType = Unknown; // Assume the worst
+
+ // If this instruction is not a PHINode, it can't be an induction variable.
+ // Also, if the PHI node has more than two predecessors, we don't know how to
+ // handle it.
+ //
+ Phi = dyn_cast<PHINode>(V);
+ if (!Phi || Phi->getNumIncomingValues() != 2) return;
+
+ // If we have loop information, make sure that this PHI node is in the header
+ // of a loop...
+ //
+ const cfg::Loop *L = LoopInfo ? LoopInfo->getLoopFor(Phi->getParent()) : 0;
+ if (L && L->getHeader() != Phi->getParent())
+ return;
+
+ Value *V1 = Phi->getIncomingValue(0);
+ Value *V2 = Phi->getIncomingValue(1);
+
+ if (L == 0) { // No loop information? Base everything on expression analysis
+ ExprType E1 = analysis::ClassifyExpression(V1);
+ ExprType E2 = analysis::ClassifyExpression(V2);
+
+ if (E1.ExprTy > E2.ExprTy) // Make E1 be the simpler expression
+ swap(E1, E2);
+
+ // E1 must be a constant incoming value, and E2 must be a linear expression
+ // with respect to the PHI node.
+ //
+ if (E1.ExprTy > ExprType::Constant || E2.ExprTy != ExprType::Linear ||
+ E2.Var != Phi)
+ return;
+
+ // Okay, we have found an induction variable. Save the start and step values
+ const Type *ETy = Phi->getType();
+ if (ETy->isPointerType()) ETy = Type::ULongTy;
+
+ Start = (Value*)(E1.Offset ? E1.Offset : ConstPoolInt::get(ETy, 0));
+ Step = (Value*)(E2.Offset ? E2.Offset : ConstPoolInt::get(ETy, 0));
+ } else {
+ // Okay, at this point, we know that we have loop information...
+
+ // Make sure that V1 is the incoming value, and V2 is from the backedge of
+ // the loop.
+ if (L->contains(Phi->getIncomingBlock(0))) // Wrong order. Swap now.
+ swap(V1, V2);
+
+ Start = V1; // We know that Start has to be loop invariant...
+ Step = 0;
+
+ if (V2 == Phi) { // referencing the PHI directly? Must have zero step
+ Step = ConstPoolVal::getNullConstant(Phi->getType());
+ } else if (BinaryOperator *I = dyn_cast<BinaryOperator>(V2)) {
+ // TODO: This could be much better...
+ if (I->getOpcode() == Instruction::Add) {
+ if (I->getOperand(0) == Phi)
+ Step = I->getOperand(1);
+ else if (I->getOperand(1) == Phi)
+ Step = I->getOperand(0);
+ }
+ }
+
+ if (Step == 0) { // Unrecognized step value...
+ ExprType StepE = analysis::ClassifyExpression(V2);
+ if (StepE.ExprTy != ExprType::Linear ||
+ StepE.Var != Phi) return;
+
+ const Type *ETy = Phi->getType();
+ if (ETy->isPointerType()) ETy = Type::ULongTy;
+ Step = (Value*)(StepE.Offset ? StepE.Offset : ConstPoolInt::get(ETy, 0));
+ }
+ }
+
+ // Classify the induction variable type now...
+ InductionType = InductionVariable::Classify(Start, Step, L);
+}
diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp
new file mode 100644
index 0000000..a240ec8
--- /dev/null
+++ b/lib/Analysis/LoopInfo.cpp
@@ -0,0 +1,81 @@
+//===- LoopInfo.cpp - Natural Loop Calculator -------------------------------=//
+//
+// This file defines the LoopInfo class that is used to identify natural loops
+// and determine the loop depth of various nodes of the CFG. Note that the
+// loops identified may actually be several natural loops that share the same
+// header node... not just a single natural loop.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Support/DepthFirstIterator.h"
+#include "llvm/BasicBlock.h"
+#include <algorithm>
+
+bool cfg::Loop::contains(const BasicBlock *BB) const {
+ return find(Blocks.begin(), Blocks.end(), BB) != Blocks.end();
+}
+
+cfg::LoopInfo::LoopInfo(const DominatorSet &DS) {
+ const BasicBlock *RootNode = DS.getRoot();
+
+ for (df_iterator<const BasicBlock*> NI = df_begin(RootNode),
+ NE = df_end(RootNode); NI != NE; ++NI)
+ if (Loop *L = ConsiderForLoop(*NI, DS))
+ TopLevelLoops.push_back(L);
+
+ for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
+ TopLevelLoops[i]->setLoopDepth(1);
+}
+
+cfg::Loop *cfg::LoopInfo::ConsiderForLoop(const BasicBlock *BB,
+ const DominatorSet &DS) {
+ if (BBMap.find(BB) != BBMap.end()) return 0; // Havn't processed this node?
+
+ vector<const BasicBlock *> TodoStack;
+
+ // Scan the predecessors of BB, checking to see if BB dominates any of
+ // them.
+ for (BasicBlock::pred_const_iterator I = BB->pred_begin(),
+ E = BB->pred_end(); I != E; ++I)
+ if (DS.dominates(BB, *I)) // If BB dominates it's predecessor...
+ TodoStack.push_back(*I);
+
+ if (TodoStack.empty()) return 0; // Doesn't dominate any predecessors...
+
+ // Create a new loop to represent this basic block...
+ Loop *L = new Loop(BB);
+ BBMap[BB] = L;
+
+ while (!TodoStack.empty()) { // Process all the nodes in the loop
+ const BasicBlock *X = TodoStack.back();
+ TodoStack.pop_back();
+
+ if (!L->contains(X)) { // As of yet unprocessed??
+ L->Blocks.push_back(X);
+
+ // Add all of the predecessors of X to the end of the work stack...
+ TodoStack.insert(TodoStack.end(), X->pred_begin(), X->pred_end());
+ }
+ }
+
+ // Add the basic blocks that comprise this loop to the BBMap so that this
+ // loop can be found for them. Also check subsidary basic blocks to see if
+ // they start subloops of their own.
+ //
+ for (vector<const BasicBlock*>::reverse_iterator I = L->Blocks.rbegin(),
+ E = L->Blocks.rend(); I != E; ++I) {
+
+ // Check to see if this block starts a new loop
+ if (Loop *NewLoop = ConsiderForLoop(*I, DS)) {
+ L->SubLoops.push_back(NewLoop);
+ NewLoop->ParentLoop = L;
+ }
+
+ if (BBMap.find(*I) == BBMap.end())
+ BBMap.insert(make_pair(*I, L));
+ }
+
+ return L;
+}