[LoopVectorize] Split out LoopAccessAnalysis from LoopVectorizationLegality

[anemet]

Summary

Move the canVectorizeMemory functionality from LoopVectorizationLegality to a
new class LoopAccessAnalysis and forward users.

Currently the collection of the symbolic stride information is kept with
LoopVectorizationLegality and it becomes an input to LoopAccessAnalysis.

NFC. This is part of the patchset that splits out the memory dependence logic
from LoopVectorizationLegality into a new class LoopAccessAnalysis.
LoopAccessAnalysis will be used by the new Loop Distribution pass.

[hfinkel]

lib/Transforms/Vectorize/LoopVectorize.cpp

674

This class does not do anything "at run-time" ;)

1852

Can you please group together the implementations of the functions for each class? I can see some advantage to having these two near each other, but in the end, I think having the implementation spread out over different parts of the file is confusing.

5073

(here too, please group these with the others)

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

674

Sure, I'll reword it.

1852

Sure. I just kept the original order so that it's immediately apparent what changed in the diff. Sometime these things show up as code movement with modifications which are harder to figure out.

What do you think about adjusting the order in an additional step in the patchset?

[hfinkel]

• Original Message -----

From: "Adam Nemet" <[e-mail]>
To: [e-mail], [e-mail], [e-mail]
Cc: [e-mail]
Sent: Friday, January 30, 2015 12:16:00 PM
Subject: Re: [PATCH] [LoopVectorize] Split out LoopAccessAnalysis from LoopVectorizationLegality

Comment at: lib/Transforms/Vectorize/LoopVectorize.cpp:613
@@ +612,3 @@
+/ This class is responsible for analyzing the memory accesses of a
loop either
+/ at compile or at run-time. It collects the accesses and then
its main
+/// helper the AccessAnalysis class finds and categorizes the

dependences in

hfinkel wrote:

This class does not do anything "at run-time" ;)

Sure, I'll reword it.

Comment at: lib/Transforms/Vectorize/LoopVectorize.cpp:1800
@@ -1744,3 +1799,3 @@

-bool LoopVectorizationLegality::isUniform(Value *V) {
+bool LoopAccessAnalysis::isUniform(Value *V) {

return (SE->isLoopInvariant(SE->getSCEV(V), TheLoop));

---

hfinkel wrote:

Can you please group together the implementations of the functions
for each class? I can see some advantage to having these two near
each other, but in the end, I think having the implementation
spread out over different parts of the file is confusing.

Sure. I just kept the original order so that it's immediately
apparent what changed in the diff. Sometime these things show up as
code movement with modifications which are harder to figure out.

What do you think about adjusting the order in an additional step in
the patchset?

Sure. Just make sure you get them all when you move them into the new file (I think some of these out-of-order ones may have been missed in the later patchset).

-Hal

http://reviews.llvm.org/D7282

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

[anemet]

Rebased and fixed the silly comment noticed by Hal

[hfinkel]

Given that you'll be moving the aforementioned functions that are not grouped with the others to a different file anyway, LGTM.

[anemet]

r227751

lib/Transforms/Vectorize/LoopVectorize.cpp

struct RuntimePointerCheck {
   /// Holds the information if this pointer is used for writing to memory.
   SmallVector<bool, 2> IsWritePtr;
   /// Holds the id of the set of pointers that could be dependent because of a
   /// shared underlying object.
   SmallVector<unsigned, 2> DependencySetId;
   /// Holds the id of the disjoint alias set to which this pointer belongs.
   SmallVector<unsigned, 2> AliasSetId;
 };
+
+/// \brief Drive the analysis of memory accesses in the loop
+///
+/// This class is responsible for analyzing the memory accesses of a loop.  It
+/// collects the accesses and then its main helper the AccessAnalysis class
+/// finds and categorizes the dependences in buildDependenceSets.
+///
+/// For memory dependences that can be analyzed at compile time, it determines
+/// whether the dependence is part of cycle inhibiting vectorization.  This work
+/// is delegated to the MemoryDepChecker class.
+///
+/// For memory dependences that cannot be determined at compile time, it
+/// generates run-time checks to prove independence.  This is done by
+/// AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the
+/// RuntimePointerCheck class.
+class LoopAccessAnalysis {
+public:
+  LoopAccessAnalysis(Function *F, Loop *L, ScalarEvolution *SE,
+                     const DataLayout *DL, const TargetLibraryInfo *TLI,
+                     AliasAnalysis *AA, DominatorTree *DT) :
+      TheFunction(F), TheLoop(L), SE(SE), DL(DL), TLI(TLI), AA(AA), DT(DT),
+      NumLoads(0), NumStores(0), MaxSafeDepDistBytes(-1U) {
+  }
+
+  /// 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);
+
+  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.
+  bool isUniform(Value *V);
+
+  unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; }
+
+private:
+  void emitAnalysis(Report &Message) {
+    emitLoopAnalysis(Message, TheFunction, TheLoop);
+  }
+
+  /// We need to check that all of the pointers in this list are disjoint
+  /// at runtime.
+  RuntimePointerCheck PtrRtCheck;
+  Function *TheFunction;
+  Loop *TheLoop;
+  ScalarEvolution *SE;
+  const DataLayout *DL;
+  const TargetLibraryInfo *TLI;
+  AliasAnalysis *AA;
+  DominatorTree *DT;
+
+  unsigned NumLoads;
+  unsigned NumStores;
+
+  unsigned MaxSafeDepDistBytes;
+};
 } // end anonymous namespace
 
 /// LoopVectorizationLegality checks if it is legal to vectorize a loop, and
 /// to what vectorization factor.
 /// This class does not look at the profitability of vectorization, only the
 /// legality. This class has two main kinds of checks:
 /// * Memory checks - The code in canVectorizeMemory checks if vectorization
 ///   will change the order of memory accesses in a way that will change the
 ///   correctness of the program.
 /// * Scalars checks - The code in canVectorizeInstrs and canVectorizeMemory
 /// checks for a number of different conditions, such as the availability of a
 /// single induction variable, that all types are supported and vectorize-able,
 /// etc. This code reflects the capabilities of InnerLoopVectorizer.
 /// This class is also used by InnerLoopVectorizer for identifying
 /// induction variable and the different reduction variables.
 class LoopVectorizationLegality {
 public:
   LoopVectorizationLegality(Loop *L, ScalarEvolution *SE, const DataLayout *DL,
                             DominatorTree *DT, TargetLibraryInfo *TLI,
                             AliasAnalysis *AA, Function *F,
                             const TargetTransformInfo *TTI)
-      : NumLoads(0), NumStores(0), NumPredStores(0), TheLoop(L), SE(SE), DL(DL),
-        DT(DT), TLI(TLI), AA(AA), TheFunction(F), TTI(TTI), Induction(nullptr),
-        WidestIndTy(nullptr), HasFunNoNaNAttr(false), MaxSafeDepDistBytes(-1U) {
+      : NumPredStores(0), TheLoop(L), SE(SE), DL(DL), TLI(TLI), TheFunction(F),
+        TTI(TTI), Induction(nullptr), WidestIndTy(nullptr),
+        LAA(F, L, SE, DL, TLI, AA, DT), HasFunNoNaNAttr(false) {
   }
 
   /// This enum represents the kinds of reductions that we support.
   enum ReductionKind {
     RK_NoReduction, ///< Not a reduction.
     RK_IntegerAdd,  ///< Sum of integers.
     RK_IntegerMult, ///< Product of integers.
     RK_IntegerOr,   ///< Bitwise or logical OR of numbers.
public:
 
   /// Returns true if the value V is uniform within the loop.
   bool isUniform(Value *V);
 
   /// Returns true if this instruction will remain scalar after vectorization.
   bool isUniformAfterVectorization(Instruction* I) { return Uniforms.count(I); }
 
   /// Returns the information that we collected about runtime memory check.
-  RuntimePointerCheck *getRuntimePointerCheck() { return &PtrRtCheck; }
+  RuntimePointerCheck *getRuntimePointerCheck() {
+    return LAA.getRuntimePointerCheck();
+  }
 
   /// This function returns the identity element (or neutral element) for
   /// the operation K.
   static Constant *getReductionIdentity(ReductionKind K, Type *Tp);
 
-  unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; }
+  unsigned getMaxSafeDepDistBytes() { return LAA.getMaxSafeDepDistBytes(); }
 
   bool hasStride(Value *V) { return StrideSet.count(V); }
   bool mustCheckStrides() { return !StrideSet.empty(); }
   SmallPtrSet<Value *, 8>::iterator strides_begin() {
     return StrideSet.begin();
   }
   SmallPtrSet<Value *, 8>::iterator strides_end() { return StrideSet.end(); }
 
private:
   unsigned NumPredStores;
 
   /// The loop that we evaluate.
   Loop *TheLoop;
   /// Scev analysis.
   ScalarEvolution *SE;
   /// DataLayout analysis.
   const DataLayout *DL;
-  /// Dominators.
-  DominatorTree *DT;
   /// Target Library Info.
   TargetLibraryInfo *TLI;
-  /// Alias analysis.
-  AliasAnalysis *AA;
   /// Parent function
   Function *TheFunction;
   /// Target Transform Info
   const TargetTransformInfo *TTI;
 
   //  ---  vectorization state --- //
 
   /// Holds the integer induction variable. This is the counter of the
private:
   Type *WidestIndTy;
 
   /// Allowed outside users. This holds the reduction
   /// vars which can be accessed from outside the loop.
   SmallPtrSet<Value*, 4> AllowedExit;
   /// This set holds the variables which are known to be uniform after
   /// vectorization.
   SmallPtrSet<Instruction*, 4> Uniforms;
-  /// We need to check that all of the pointers in this list are disjoint
-  /// at runtime.
-  RuntimePointerCheck PtrRtCheck;
+  LoopAccessAnalysis LAA;
   /// Can we assume the absence of NaNs.
   bool HasFunNoNaNAttr;
 
-  unsigned MaxSafeDepDistBytes;
-
   ValueToValueMap Strides;
   SmallPtrSet<Value *, 8> StrideSet;
   
   /// While vectorizing these instructions we have to generate a
   /// call to the appropriate masked intrinsic
   SmallPtrSet<const Instruction*, 8> MaskedOp;
 };
 
if (Step->isOne())
       return 1;
     if (Step->isAllOnesValue())
       return -1;
   }
 
   return 0;
 }
 
-bool LoopVectorizationLegality::isUniform(Value *V) {
+bool LoopAccessAnalysis::isUniform(Value *V) {
   return (SE->isLoopInvariant(SE->getSCEV(V), TheLoop));
 }
 
+bool LoopVectorizationLegality::isUniform(Value *V) {
+  return LAA.isUniform(V);
+}
+
 InnerLoopVectorizer::VectorParts&
 InnerLoopVectorizer::getVectorValue(Value *V) {
   assert(V != Induction && "The new induction variable should not be used.");
   assert(!V->getType()->isVectorTy() && "Can't widen a vector");
 
   // If we have a stride that is replaced by one, do it here.
   if (Legal->hasStride(V))
     V = ConstantInt::get(V->getType(), 1);
if (!canVectorizeMemory()) {
     DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n");
     return false;
   }
 
   // Collect all of the variables that remain uniform after vectorization.
   collectLoopUniforms();
 
   DEBUG(dbgs() << "LV: We can vectorize this loop" <<
-        (PtrRtCheck.Need ? " (with a runtime bound check)" : "")
+        (LAA.getRuntimePointerCheck()->Need ? " (with a runtime bound check)" :
+         "")
         <<"!\n");
 
   // Okay! We can vectorize. At this point we don't have any other mem analysis
   // which may limit our maximum vectorization factor, so just return true with
   // no restrictions.
   return true;
 }
 
while (AI != AE) {
         ++OI;
       }
       AI++;
     }
   }
   return true;
 }
 
-bool LoopVectorizationLegality::canVectorizeMemory() {
+bool LoopAccessAnalysis::canVectorizeMemory(ValueToValueMap &Strides) {
 
   typedef SmallVector<Value*, 16> ValueVector;
   typedef SmallPtrSet<Value*, 16> ValueSet;
 
   // Holds the Load and Store *instructions*.
   ValueVector Loads;
   ValueVector Stores;
 
if (!CanVecMem)
     emitAnalysis(Report() << "unsafe dependent memory operations in loop");
 
   DEBUG(dbgs() << "LV: We" << (NeedRTCheck ? "" : " don't") <<
         " need a runtime memory check.\n");
 
   return CanVecMem;
 }
 
+bool LoopVectorizationLegality::canVectorizeMemory() {
+  return LAA.canVectorizeMemory(Strides);
+}
+
 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;
     if (NumUses > 1)
       return true;
bool LoopVectorizationLegality::isInductionVariable(const Value *V) {
   Value *In0 = const_cast<Value*>(V);
   PHINode *PN = dyn_cast_or_null<PHINode>(In0);
   if (!PN)
     return false;
 
   return Inductions.count(PN);
 }
 
-bool LoopVectorizationLegality::blockNeedsPredication(BasicBlock *BB)  {
+bool LoopAccessAnalysis::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);
 }
 
+bool LoopVectorizationLegality::blockNeedsPredication(BasicBlock *BB)  {
+  return LAA.blockNeedsPredication(BB);
+}
+
 bool LoopVectorizationLegality::blockCanBePredicated(BasicBlock *BB,
                                            SmallPtrSetImpl<Value *> &SafePtrs) {
   
   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
     // Check that we don't have a constant expression that can trap as operand.
     for (Instruction::op_iterator OI = it->op_begin(), OE = it->op_end();
          OI != OE; ++OI) {
       if (Constant *C = dyn_cast<Constant>(*OI))