[LoopAccesses] Cache the result of canVectorizeMemory

[anemet]

Summary

LAA will be an on-demand analysis pass, so we need to cache the result
of the analysis. canVectorizeMemory is renamed to analyzeLoop which
computes the result. canVectorizeMemory becomes the query function for
the cached result.

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

[hfinkel]

Why not do the analysis in the constructor, and remove the implicit ordering dependency between calling analyzeLoop and calling the other accessor functions?

[anemet]

In D7682#124581, @hfinkel wrote:

Why not do the analysis in the constructor, and remove the implicit ordering dependency between calling analyzeLoop and calling the other accessor functions?

I think that should work, let me give it a try.

[anemet]

In D7682#124591, @anemet wrote:

In D7682#124581, @hfinkel wrote:

Why not do the analysis in the constructor, and remove the implicit ordering dependency between calling analyzeLoop and calling the other accessor functions?

I think that should work, let me give it a try.

OK, I know now why we can't do it in *this* patch. LAI is constructed when LVLegality is constructed so we would effectively move running canVectorizeMemory much earlier than before.

On the other hand I can do this after we have the LAA-LAI separation later in D7684 (where the pass is actually created). There, LAI is only created from LVLegality::canVectorizeMem so there is no functional change. Are you OK with that?

[hfinkel]

In D7682#124926, @anemet wrote:

In D7682#124591, @anemet wrote:

In D7682#124581, @hfinkel wrote:

Why not do the analysis in the constructor, and remove the implicit ordering dependency between calling analyzeLoop and calling the other accessor functions?

I think that should work, let me give it a try.

OK, I know now why we can't do it in *this* patch. LAI is constructed when LVLegality is constructed so we would effectively move running canVectorizeMemory much earlier than before.

On the other hand I can do this after we have the LAA-LAI separation later in D7684 (where the pass is actually created). There, LAI is only created from LVLegality::canVectorizeMem so there is no functional change. Are you OK with that?

Yes, that's fine with me. Go ahead with this, it will last for a few minutes ;) LGTM.

[anemet]

r229892

include/llvm/Analysis/LoopAccessAnalysis.h

struct RuntimePointerCheck {
     /// Holds the id of the disjoint alias set to which this pointer belongs.
     SmallVector<unsigned, 2> AliasSetId;
   };
 
   LoopAccessInfo(Loop *L, ScalarEvolution *SE, const DataLayout *DL,
                  const TargetLibraryInfo *TLI, AliasAnalysis *AA,
                  DominatorTree *DT) :
       TheLoop(L), SE(SE), DL(DL), TLI(TLI), AA(AA), DT(DT), NumLoads(0),
-      NumStores(0), MaxSafeDepDistBytes(-1U) {}
+      NumStores(0), MaxSafeDepDistBytes(-1U), CanVecMem(false) {}
+
+  /// \brief Analyze the loop.  Replaces symbolic strides using Strides.
+  void analyzeLoop(ValueToValueMap &Strides);
 
   /// Return true we can analyze the memory accesses in the loop and there are
-  /// no memory dependence cycles.  Replaces symbolic strides using Strides.
-  bool canVectorizeMemory(ValueToValueMap &Strides);
+  /// no memory dependence cycles.
+  bool canVectorizeMemory() { return CanVecMem; }
 
   RuntimePointerCheck *getRuntimePointerCheck() { return &PtrRtCheck; }
 
   /// Return true if the block BB needs to be predicated in order for the loop
   /// to be vectorized.
   bool blockNeedsPredication(BasicBlock *BB);
 
   /// Returns true if the value V is uniform within the loop.
private:
   AliasAnalysis *AA;
   DominatorTree *DT;
 
   unsigned NumLoads;
   unsigned NumStores;
 
   unsigned MaxSafeDepDistBytes;
 
+  /// \brief Cache the result of analyzeLoop.
+  bool CanVecMem;
+
   /// \brief The diagnostics report generated for the analysis.  E.g. why we
   /// couldn't analyze the loop.
   Optional<VectorizationReport> Report;
 };
 
 Value *stripIntegerCast(Value *V);
 
 ///\brief Return the SCEV corresponding to a pointer with the symbolic stride

lib/Analysis/LoopAccessAnalysis.cpp

while (AI != AE) {
         ++OI;
       }
       AI++;
     }
   }
   return true;
 }
 
-bool LoopAccessInfo::canVectorizeMemory(ValueToValueMap &Strides) {
+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;
 
for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
         if (Call && getIntrinsicIDForCall(Call, TLI))
           continue;
 
         LoadInst *Ld = dyn_cast<LoadInst>(it);
         if (!Ld || (!Ld->isSimple() && !IsAnnotatedParallel)) {
           emitAnalysis(VectorizationReport(Ld)
                        << "read with atomic ordering or volatile read");
           DEBUG(dbgs() << "LV: Found a non-simple load.\n");
-          return false;
+          CanVecMem = false;
+          return;
         }
         NumLoads++;
         Loads.push_back(Ld);
         DepChecker.addAccess(Ld);
         continue;
       }
 
       // Save 'store' instructions. Abort if other instructions write to memory.
       if (it->mayWriteToMemory()) {
         StoreInst *St = dyn_cast<StoreInst>(it);
         if (!St) {
           emitAnalysis(VectorizationReport(it) <<
                        "instruction cannot be vectorized");
-          return false;
+          CanVecMem = false;
+          return;
         }
         if (!St->isSimple() && !IsAnnotatedParallel) {
           emitAnalysis(VectorizationReport(St)
                        << "write with atomic ordering or volatile write");
           DEBUG(dbgs() << "LV: Found a non-simple store.\n");
-          return false;
+          CanVecMem = false;
+          return;
         }
         NumStores++;
         Stores.push_back(St);
         DepChecker.addAccess(St);
       }
     } // Next instr.
   } // Next block.
 
   // Now we have two lists that hold the loads and the stores.
   // Next, we find the pointers that they use.
 
   // Check if we see any stores. If there are no stores, then we don't
   // care if the pointers are *restrict*.
   if (!Stores.size()) {
     DEBUG(dbgs() << "LV: Found a read-only loop!\n");
-    return true;
+    CanVecMem = true;
+    return;
   }
 
   AccessAnalysis::DepCandidates DependentAccesses;
   AccessAnalysis Accesses(DL, AA, DependentAccesses);
 
   // Holds the analyzed pointers. We don't want to call GetUnderlyingObjects
   // multiple times on the same object. If the ptr is accessed twice, once
   // for read and once for write, it will only appear once (on the write
   // list). This is okay, since we are going to check for conflicts between
   // writes and between reads and writes, but not between reads and reads.
   ValueSet Seen;
 
   ValueVector::iterator I, IE;
   for (I = Stores.begin(), IE = Stores.end(); I != IE; ++I) {
     StoreInst *ST = cast<StoreInst>(*I);
     Value* Ptr = ST->getPointerOperand();
 
     if (isUniform(Ptr)) {
       emitAnalysis(
           VectorizationReport(ST)
           << "write to a loop invariant address could not be vectorized");
       DEBUG(dbgs() << "LV: We don't allow storing to uniform addresses\n");
-      return false;
+      CanVecMem = false;
+      return;
     }
 
     // If we did *not* see this pointer before, insert it to  the read-write
     // list. At this phase it is only a 'write' list.
     if (Seen.insert(Ptr).second) {
       ++NumReadWrites;
 
       AliasAnalysis::Location Loc = AA->getLocation(ST);
       // The TBAA metadata could have a control dependency on the predication
       // condition, so we cannot rely on it when determining whether or not we
       // need runtime pointer checks.
       if (blockNeedsPredication(ST->getParent()))
         Loc.AATags.TBAA = nullptr;
 
       Accesses.addStore(Loc);
     }
   }
 
   if (IsAnnotatedParallel) {
     DEBUG(dbgs()
           << "LV: A loop annotated parallel, ignore memory dependency "
           << "checks.\n");
-    return true;
+    CanVecMem = true;
+    return;
   }
 
   for (I = Loads.begin(), IE = Loads.end(); I != IE; ++I) {
     LoadInst *LD = cast<LoadInst>(*I);
     Value* Ptr = LD->getPointerOperand();
     // If we did *not* see this pointer before, insert it to the
     // read list. If we *did* see it before, then it is already in
     // the read-write list. This allows us to vectorize expressions
for (I = Loads.begin(), IE = Loads.end(); I != IE; ++I) {
 
     Accesses.addLoad(Loc, IsReadOnlyPtr);
   }
 
   // If we write (or read-write) to a single destination and there are no
   // other reads in this loop then is it safe to vectorize.
   if (NumReadWrites == 1 && NumReads == 0) {
     DEBUG(dbgs() << "LV: Found a write-only loop!\n");
-    return true;
+    CanVecMem = true;
+    return;
   }
 
   // Build dependence sets and check whether we need a runtime pointer bounds
   // check.
   Accesses.buildDependenceSets();
   bool NeedRTCheck = Accesses.isRTCheckNeeded();
 
   // Find pointers with computable bounds. We are going to use this information
if (CanDoRT) {
     DEBUG(dbgs() << "LV: We can perform a memory runtime check if needed.\n");
   }
 
   if (NeedRTCheck && !CanDoRT) {
     emitAnalysis(VectorizationReport() << "cannot identify array bounds");
     DEBUG(dbgs() << "LV: We can't vectorize because we can't find " <<
           "the array bounds.\n");
     PtrRtCheck.reset();
-    return false;
+    CanVecMem = false;
+    return;
   }
 
   PtrRtCheck.Need = NeedRTCheck;
 
-  bool CanVecMem = true;
+  CanVecMem = true;
   if (Accesses.isDependencyCheckNeeded()) {
     DEBUG(dbgs() << "LV: Checking memory dependencies\n");
     CanVecMem = DepChecker.areDepsSafe(
         DependentAccesses, Accesses.getDependenciesToCheck(), Strides);
     MaxSafeDepDistBytes = DepChecker.getMaxSafeDepDistBytes();
 
     if (!CanVecMem && DepChecker.shouldRetryWithRuntimeCheck()) {
       DEBUG(dbgs() << "LV: Retrying with memory checks\n");
if (!CanVecMem && DepChecker.shouldRetryWithRuntimeCheck()) {
                        << "cannot check memory dependencies at runtime");
         else
           emitAnalysis(VectorizationReport()
                        << NumComparisons << " exceeds limit of "
                        << VectorizerParams::RuntimeMemoryCheckThreshold
                        << " dependent memory operations checked at runtime");
         DEBUG(dbgs() << "LV: Can't vectorize with memory checks\n");
         PtrRtCheck.reset();
-        return false;
+        CanVecMem = false;
+        return;
       }
 
       CanVecMem = true;
     }
   }
 
   if (!CanVecMem)
     emitAnalysis(VectorizationReport() <<
                  "unsafe dependent memory operations in loop");
 
   DEBUG(dbgs() << "LV: We" << (NeedRTCheck ? "" : " don't") <<
         " need a runtime memory check.\n");
-
-  return CanVecMem;
 }
 
 bool LoopAccessInfo::blockNeedsPredication(BasicBlock *BB)  {
   assert(TheLoop->contains(BB) && "Unknown block used");
 
   // Blocks that do not dominate the latch need predication.
   BasicBlock* Latch = TheLoop->getLoopLatch();
   return !DT->dominates(BB, Latch);

lib/Transforms/Vectorize/LoopVectorize.cpp

while (!Worklist.empty()) {
     Uniforms.insert(I);
 
     // Insert all operands.
     Worklist.insert(Worklist.end(), I->op_begin(), I->op_end());
   }
 }
 
 bool LoopVectorizationLegality::canVectorizeMemory() {
-  bool Success = LAI.canVectorizeMemory(Strides);
+  LAI.analyzeLoop(Strides);
   auto &OptionalReport = LAI.getReport();
   if (OptionalReport)
     emitAnalysis(*OptionalReport);
-  return Success;
+  return LAI.canVectorizeMemory();
 }
 
 static bool hasMultipleUsesOf(Instruction *I,
                               SmallPtrSetImpl<Instruction *> &Insts) {
   unsigned NumUses = 0;
   for(User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) {
     if (Insts.count(dyn_cast<Instruction>(*Use)))
       ++NumUses;