* 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

2 files changed, 219 insertions, 0 deletions

diff --git a/lib/Analysis/InductionVariable.cpp b/lib/Analysis/InductionVariable.cpp
new file mode 100644
index 0000000000..706c778a4d
--- /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 0000000000..a240ec8b8b
--- /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;
+}