From 5c4c262b3c97bfa740d30122aa8d68be4a244d36 Mon Sep 17 00:00:00 2001
From: Adam Nemet <anemet@apple.com>
Date: Thu, 19 Feb 2015 19:15:10 +0000
Subject: [PATCH] [LoopAccesses] Add canAnalyzeLoop

This allows the analysis to be attempted with any loop.  This feature
will be used with -analysis.  (LV only requests the analysis on loops
that have already satisfied these tests.)

This is part of the patchset that converts LoopAccessAnalysis into an
actual analysis pass.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@229895 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Analysis/LoopAccessAnalysis.h |  4 ++
 lib/Analysis/LoopAccessAnalysis.cpp        | 52 +++++++++++++++++++++-
 2 files changed, 55 insertions(+), 1 deletion(-)

diff --git a/include/llvm/Analysis/LoopAccessAnalysis.h b/include/llvm/Analysis/LoopAccessAnalysis.h
index 75838d26faf..936783e53b0 100644
--- a/include/llvm/Analysis/LoopAccessAnalysis.h
+++ b/include/llvm/Analysis/LoopAccessAnalysis.h
@@ -181,6 +181,10 @@ private:
   /// \brief Analyze the loop.  Substitute symbolic strides using Strides.
   void analyzeLoop(ValueToValueMap &Strides);
 
+  /// \brief Check if the structure of the loop allows it to be analyzed by this
+  /// pass.
+  bool canAnalyzeLoop();
+
   void emitAnalysis(VectorizationReport &Message);
 
   /// We need to check that all of the pointers in this list are disjoint
diff --git a/lib/Analysis/LoopAccessAnalysis.cpp b/lib/Analysis/LoopAccessAnalysis.cpp
index 05917036404..40b70ef30d4 100644
--- a/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/lib/Analysis/LoopAccessAnalysis.cpp
@@ -855,6 +855,55 @@ bool MemoryDepChecker::areDepsSafe(AccessAnalysis::DepCandidates &AccessSets,
   return true;
 }
 
+bool LoopAccessInfo::canAnalyzeLoop() {
+    // We can only analyze innermost loops.
+  if (!TheLoop->empty()) {
+    emitAnalysis(VectorizationReport() << "loop is not the innermost loop");
+    return false;
+  }
+
+  // We must have a single backedge.
+  if (TheLoop->getNumBackEdges() != 1) {
+    emitAnalysis(
+        VectorizationReport() <<
+        "loop control flow is not understood by analyzer");
+    return false;
+  }
+
+  // We must have a single exiting block.
+  if (!TheLoop->getExitingBlock()) {
+    emitAnalysis(
+        VectorizationReport() <<
+        "loop control flow is not understood by analyzer");
+    return false;
+  }
+
+  // We only handle bottom-tested loops, i.e. loop in which the condition is
+  // checked at the end of each iteration. With that we can assume that all
+  // instructions in the loop are executed the same number of times.
+  if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) {
+    emitAnalysis(
+        VectorizationReport() <<
+        "loop control flow is not understood by analyzer");
+    return false;
+  }
+
+  // We need to have a loop header.
+  DEBUG(dbgs() << "LAA: Found a loop: " <<
+        TheLoop->getHeader()->getName() << '\n');
+
+  // ScalarEvolution needs to be able to find the exit count.
+  const SCEV *ExitCount = SE->getBackedgeTakenCount(TheLoop);
+  if (ExitCount == SE->getCouldNotCompute()) {
+    emitAnalysis(VectorizationReport() <<
+                 "could not determine number of loop iterations");
+    DEBUG(dbgs() << "LAA: SCEV could not compute the loop exit count.\n");
+    return false;
+  }
+
+  return true;
+}
+
 void LoopAccessInfo::analyzeLoop(ValueToValueMap &Strides) {
 
   typedef SmallVector<Value*, 16> ValueVector;
@@ -1238,7 +1287,8 @@ LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
                                DominatorTree *DT, ValueToValueMap &Strides)
     : TheLoop(L), SE(SE), DL(DL), TLI(TLI), AA(AA), DT(DT), NumLoads(0),
       NumStores(0), MaxSafeDepDistBytes(-1U), CanVecMem(false) {
-  analyzeLoop(Strides);
+  if (canAnalyzeLoop())
+    analyzeLoop(Strides);
 }
 
 LoopAccessInfo &LoopAccessAnalysis::getInfo(Loop *L, ValueToValueMap &Strides) {
-- 
2.34.1