[LoopAccesses] Add canAnalyzeLoop

[anemet]

Summary

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.

[anemet]

lib/Analysis/LoopAccessAnalysis.cpp

1280–1282

Based on Hal's comment to an earlier patch in the set, I will try to fold both of these into the constructor.

[hfinkel]

lib/Analysis/LoopAccessAnalysis.cpp

835

These should say LoopAccessReport(), not VectorizationReport(), right? Or do we have a special subclass for the analysis itslef? If not, maybe we should?

[anemet]

lib/Analysis/LoopAccessAnalysis.cpp

835

Yes, these should be LoopAccessReport, thanks for noticing!

Also I just notices that the comment should be adjust not to mention vectorization in this context.

Why do you think that we'd need a subclass for the analysis? The base class (LoopAccessReport) seems to be sufficient for now.

[hfinkel]

lib/Analysis/LoopAccessAnalysis.cpp

835

The vectorizer's subclass says something like "could not vectorize", should the analysis one say something like, "could not analyze for memory dependencies"? (just a though)

[anemet]

lib/Analysis/LoopAccessAnalysis.cpp

835

The way I see it is that LoopAccessReport gives you the report on the analysis and then the transform passes extended it with their interpretation of the analysis (e.g. could not vectorize).

For the analysis pass itself I don't think there is much to add but we'll have to see if the reports makes sense on their own...

[anemet]

Turns out that LoopAccessReport is only introduced at a later patch (D7690) so
I was correct using VectorizationReport at this point.

I did change a few comments and messages in canAnalyzeLoop to say analyzer
rather than vectorizer.

[hfinkel]

LGTM.

[anemet]

r229895

include/llvm/Analysis/LoopAccessAnalysis.h

public:
   LoopAccessInfo(Loop *L, ScalarEvolution *SE, const DataLayout *DL,
                  const TargetLibraryInfo *TLI, AliasAnalysis *AA,
                  DominatorTree *DT, ValueToValueMap &Strides);
 
   /// Return true we can analyze the memory accesses in the loop and there are
   /// no memory dependence cycles.
   bool canVectorizeMemory() { return CanVecMem; }
 
+  /// \brief Check if the structure of the loop allows it to be analyzed by this
+  /// pass.
+  bool canAnalyzeLoop();
+
   RuntimePointerCheck *getRuntimePointerCheck() { return &PtrRtCheck; }
 
   /// Return true if the block BB needs to be predicated in order for the loop
   /// to be vectorized.
   static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
                                     DominatorTree *DT);
   bool blockNeedsPredication(BasicBlock *BB);
 

lib/Analysis/LoopAccessAnalysis.cpp

while (AI != AE) {
         ++OI;
       }
       AI++;
     }
   }
   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;
   typedef SmallPtrSet<Value*, 16> ValueSet;
 
   // Holds the Load and Store *instructions*.
   ValueVector Loads;
   ValueVector Stores;

 }
 
 LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
                                const DataLayout *DL,
                                const TargetLibraryInfo *TLI, AliasAnalysis *AA,
                                DominatorTree *DT, ValueToValueMap &Strides)
     : TheLoop(L), SE(SE), DL(DL), TLI(TLI), AA(AA), DT(DT), NumLoads(0),
       NumStores(0), MaxSafeDepDistBytes(-1U), CanVecMem(false) {
+  if (canAnalyzeLoop())
     analyzeLoop(Strides);
 }
 
 LoopAccessInfo &LoopAccessAnalysis::getInfo(Loop *L, ValueToValueMap &Strides) {
   auto &LAI = LoopAccessInfoMap[L];
 
 #ifndef NDEBUG
   assert((!LAI || LAI->NumSymbolicStrides == Strides.size()) &&
          "Symbolic strides changed for loop");
 #endif
 
   if (!LAI) {
     LAI = make_unique<LoopAccessInfo>(L, SE, DL, TLI, AA, DT, Strides);
 #ifndef NDEBUG
     LAI->NumSymbolicStrides = Strides.size();
 #endif
   }
   return *LAI.get();
 }
 
 bool LoopAccessAnalysis::runOnFunction(Function &F) {
   SE = &getAnalysis<ScalarEvolution>();