Add ability to use DependenceAnalysis from LoopAccessAnalysis

[hfinkel]

Summary

LoopAccessAnalysis performs dependence analysis for our loop vectorization and other loop transformation passes. Its builtin dependence analysis is fairly simple, and ends up missing a number of common cases. As a result, we end up inserting runtime checks where they're not really needed (or perhaps not vectorizing at all).

LLVM has a more-sophisticated DependenceAnalysis implementation which does catch more of these cases. This patch adds a mode, disabled by default, under which we can use DependenceAnalysis from LoopAccessAnalysis. I've included an example test case in which the use of DependenceAnalysis allows us to elide unnecessary runtime checks.

We should discuss whether we should have, as a general refactoring goal, having LoopAccessAnalysis use DependenceAnalysis for all of its dependence-analysis needs. And if not, why not.

[anemet]

This is great! I will look at this but quickly, did you see any performance gains with this?

[hfinkel]

In D19886#420408, @anemet wrote:

This is great! I will look at this but quickly, did you see any performance gains with this?

Thanks! I've not run the test suite, etc. yet. I was looking at the performance of a loop that follows the pattern in the test case (reading from one part of an array and writing to another part), and this patch definitely helps that case.

[sbaranga]

Overall, this looks like a very good goal.

The only problem that I can see would be that the Dependence Analysis won't be able to use the extra run-time information from loop versioning. In these cases, the current built-in logic might get a NoDep (there probably is a way to fix this).

[etherzhhb]

lib/Analysis/LoopAccessAnalysis.cpp

1245

In order to address @sbaranga's comment, perhaps we can rewrite Dist with SCEVPredicateRewriter using the existing Predicate from PSE to incorporate the existing runtime checks.

[sbaranga]

lib/Analysis/LoopAccessAnalysis.cpp

1227

DA is independent of the loop versioning. Therefore if we have NoDep here then the versioning performed by replaceSymbolicStrideSCEV/isStridedPtr wouldn't help. So by moving this above the replaceSymbolicStrideSCEV calls, we could reduce the number of run-time checks needed.

1245

Yes, something like that can be used to keep the existing features of the LAA dependece analysis, but it wouldn't help if we wanted to refactor and replace this logic entirely with DependenceAnalysis.

What are we getting by using the Dep->getDistance? It might be better to just keep the old distance calculation (which should be equivalent and avoid additional SCEV rewritting).

[etherzhhb]

lib/Analysis/LoopAccessAnalysis.cpp

1227

Yes, we can call DA early to get the distance SCEV early and avoid the later replaceSymbolicStrideSCEV.

If the result provided by DA is more precise, it is also useful in this stage. See below.

1245

If DependenceAnalysis (and later the analysis from Polly, see one of this year's GSoC mentored by @jdoerfert) provide more precise result, and we can rewirte the SCEV returned by DependenceAnalysis with the predicates introduced by LoopAccessAnalysis to provide even more precise results, we may have some gain here.

[sbaranga]

lib/Analysis/LoopAccessAnalysis.cpp

1245

That should be fine in the long run (and looks like it will have to be touched in the GSoC work), my only concern was that it might not make sense to do this it in the current change if it doesn't bring any gain (it would be over-engineering?).

Anyway, if we do want to use the distance returned by the DependenceAnalysis, we would have to do two things:

• we would need to record this distance in the dependences produced by LLA, since other passes consume this (see isDependenceDistanceOfOne in LLE) and are currently assuming that the distance is computed by subtracting the SCEVs. There might be other examples that I'm not aware of.
• add the boilerplate to PSE to version the SCEV directly (should be simple).

It would also be really nice if we could figure out a good (and common) interface for the dependence result (which would be part of the refactoring goal anyway).

[hfinkel]

Rebased (no other changes yet)

include/llvm/Analysis/LoopAccessAnalysis.h

 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace llvm {
 
 class Value;
 class DataLayout;
+class DependenceInfo;
 class ScalarEvolution;
 class Loop;
 class SCEV;
 class SCEVUnionPredicate;
 class LoopAccessInfo;
 
 /// Optimization analysis message produced during vectorization. Messages inform
 /// the user why vectorization did not occur.
struct Dependence {
     bool isPossiblyBackward() const;
 
     /// \brief Print the dependence.  \p Instr is used to map the instruction
     /// indices to instructions.
     void print(raw_ostream &OS, unsigned Depth,
                const SmallVectorImpl<Instruction *> &Instrs) const;
   };
 
-  MemoryDepChecker(PredicatedScalarEvolution &PSE, const Loop *L)
-      : PSE(PSE), InnermostLoop(L), AccessIdx(0),
+  MemoryDepChecker(PredicatedScalarEvolution &PSE, DependenceInfo *DI,
+                   const Loop *L)
+      : PSE(PSE), DI(DI), InnermostLoop(L), AccessIdx(0),
         ShouldRetryWithRuntimeCheck(false), SafeForVectorization(true),
         RecordDependences(true) {}
 
   /// \brief Register the location (instructions are given increasing numbers)
   /// of a write access.
   void addAccess(StoreInst *SI) {
     Value *Ptr = SI->getPointerOperand();
     Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);

 private:
   /// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and
   /// applies dynamic knowledge to simplify SCEV expressions and convert them
   /// to a more usable form. We need this in case assumptions about SCEV
   /// expressions need to be made in order to avoid unknown dependences. For
   /// example we might assume a unit stride for a pointer in order to prove
   /// that a memory access is strided and doesn't wrap.
   PredicatedScalarEvolution &PSE;
+  DependenceInfo *DI;
   const Loop *InnermostLoop;
 
   /// \brief Maps access locations (ptr, read/write) to program order.
   DenseMap<MemAccessInfo, std::vector<unsigned> > Accesses;
 
   /// \brief Memory access instructions in program order.
   SmallVector<Instruction *, 16> InstMap;
 

 /// If pointers can wrap or can't be expressed as affine AddRec expressions by
 /// ScalarEvolution, we will generate run-time checks by emitting a
 /// SCEVUnionPredicate.
 ///
 /// Checks for both memory dependences and the SCEV predicates contained in the
 /// PSE must be emitted in order for the results of this analysis to be valid.
 class LoopAccessInfo {
 public:
-  LoopAccessInfo(Loop *L, ScalarEvolution *SE, const DataLayout &DL,
+  LoopAccessInfo(Loop *L, ScalarEvolution *SE, DependenceInfo *DI,
+                 const DataLayout &DL,
                  const TargetLibraryInfo *TLI, AliasAnalysis *AA,
                  DominatorTree *DT, LoopInfo *LI);
 
   // FIXME:
   // Hack for MSVC 2013 which sems like it can't synthesize this even 
   // with default keyword:
   // LoopAccessInfo(LoopAccessInfo &&LAI) = default;
   LoopAccessInfo(LoopAccessInfo &&LAI)
private:
   DenseMap<Loop *, std::unique_ptr<LoopAccessInfo>> LoopAccessInfoMap;
 
   // The used analysis passes.
   ScalarEvolution *SE;
   const TargetLibraryInfo *TLI;
   AliasAnalysis *AA;
   DominatorTree *DT;
   LoopInfo *LI;
+  DependenceInfo *DI;
 };
 
 /// \brief LoopAccessInfoAnalysis
 class LoopAccessInfoAnalysis
     : public AnalysisInfoMixin<LoopAccessInfoAnalysis> {
   friend AnalysisInfoMixin<LoopAccessInfoAnalysis>;
   static char PassID;
 

lib/Analysis/LoopAccessAnalysis.cpp

 //===- LoopAccessAnalysis.cpp - Loop Access Analysis Implementation --------==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // The implementation for the loop memory dependence that was originally
 // developed for the loop vectorizer.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPassManager.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/DiagnosticInfo.h"

 
 /// \brief Enable store-to-load forwarding conflict detection. This option can
 /// be disabled for correctness testing.
 static cl::opt<bool> EnableForwardingConflictDetection(
     "store-to-load-forwarding-conflict-detection", cl::Hidden,
     cl::desc("Enable conflict detection in loop-access analysis"),
     cl::init(true));
 
+static cl::opt<bool>
+    UseDA("use-da-for-loop-accesses", cl::Hidden, cl::init(false),
+          cl::desc("Use da in loop-accesses"));
+
 bool VectorizerParams::isInterleaveForced() {
   return ::VectorizationInterleave.getNumOccurrences() > 0;
 }
 
 void LoopAccessReport::emitAnalysis(const LoopAccessReport &Message,
                                     const Function *TheFunction,
                                     const Loop *TheLoop,
                                     const char *PassName) {
MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   if (StrideAPtr < 0) {
     std::swap(APtr, BPtr);
     std::swap(Src, Sink);
     std::swap(AIsWrite, BIsWrite);
     std::swap(AIdx, BIdx);
     std::swap(StrideAPtr, StrideBPtr);
   }
 
-  const SCEV *Dist = PSE.getSE()->getMinusSCEV(Sink, Src);
+  const SCEV *Dist = nullptr;
+  if (UseDA) {
+    DEBUG(dbgs() << "LAA: DA checking " << *InstMap[AIdx] <<
+                    " vs. " << *InstMap[BIdx] << "\n");
+    auto Dep = DI->depends(InstMap[AIdx], InstMap[BIdx], false);
+    if (!Dep) {
+      DEBUG(dbgs() << "LAA: DA returned no dependence!\n");
+      return Dependence::NoDep;
+    }
+
+    DEBUG(dbgs() << "LAA: DA returned dependence: "; Dep->dump(dbgs());
+          dbgs() << "\n");
+    if (Dep->getLevels() > 0) {
+      Dist = Dep->getDistance(Dep->getLevels());
+      if (Dist) {
+        Type *ATy = APtr->getType()->getPointerElementType();
+        Dist = PSE.getSE()->getMulExpr(Dist,
+          PSE.getSE()->getSizeOfExpr(Dist->getType(), ATy));
+
+        DEBUG(dbgs() << "LAA: DA distance after sizeof adjustment: " <<
+                        *Dist << "\n");
+
+        // The code below assumes that we've computed a distance as
+        // (Sink - Src), but DependenceAnalysis returns a distance as
+        // (Src - Sink).
+        Dist = PSE.getSE()->getNegativeSCEV(Dist);
+      }
+    }
+  }
+
+  if (!Dist)
+    Dist = PSE.getSE()->getMinusSCEV(Sink, Src);
 
   DEBUG(dbgs() << "LAA: Src Scev: " << *Src << "Sink Scev: " << *Sink
                << "(Induction step: " << StrideAPtr << ")\n");
   DEBUG(dbgs() << "LAA: Distance for " << *InstMap[AIdx] << " to "
                << *InstMap[BIdx] << ": " << *Dist << "\n");
 
   // Need accesses with constant stride. We don't want to vectorize
   // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in
void LoopAccessInfo::collectStridedAccess(Value *MemAccess) {
 
   DEBUG(dbgs() << "LAA: Found a strided access that we can version");
   DEBUG(dbgs() << "  Ptr: " << *Ptr << " Stride: " << *Stride << "\n");
   SymbolicStrides[Ptr] = Stride;
   StrideSet.insert(Stride);
 }
 
 LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
+                               DependenceInfo *DI,
                                const DataLayout &DL,
                                const TargetLibraryInfo *TLI, AliasAnalysis *AA,
                                DominatorTree *DT, LoopInfo *LI)
     : PSE(llvm::make_unique<PredicatedScalarEvolution>(*SE, *L)),
       PtrRtChecking(llvm::make_unique<RuntimePointerChecking>(SE)),
-      DepChecker(llvm::make_unique<MemoryDepChecker>(*PSE, L)), TheLoop(L),
+      DepChecker(llvm::make_unique<MemoryDepChecker>(*PSE, DI, L)), TheLoop(L),
       DL(&DL), TLI(TLI), AA(AA), DT(DT), LI(LI), NumLoads(0), NumStores(0),
       MaxSafeDepDistBytes(-1U), CanVecMem(false),
       StoreToLoopInvariantAddress(false) {
   if (canAnalyzeLoop())
     analyzeLoop();
 }
 
 void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
   PSE->print(OS, Depth);
 }
 
 const LoopAccessInfo &LoopAccessAnalysis::getInfo(Loop *L) {
   auto &LAI = LoopAccessInfoMap[L];
 
   if (!LAI) {
     const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
-    LAI = llvm::make_unique<LoopAccessInfo>(L, SE, DL, TLI, AA, DT, LI);
+    LAI = llvm::make_unique<LoopAccessInfo>(L, SE, DI, DL, TLI, AA, DT, LI);
   }
   return *LAI.get();
 }
 
 void LoopAccessAnalysis::print(raw_ostream &OS, const Module *M) const {
   LoopAccessAnalysis &LAA = *const_cast<LoopAccessAnalysis *>(this);
 
   for (Loop *TopLevelLoop : *LI)
     for (Loop *L : depth_first(TopLevelLoop)) {
       OS.indent(2) << L->getHeader()->getName() << ":\n";
       auto &LAI = LAA.getInfo(L);
       LAI.print(OS, 4);
     }
 }
 
 bool LoopAccessAnalysis::runOnFunction(Function &F) {
   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
   TLI = TLIP ? &TLIP->getTLI() : nullptr;
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  if (UseDA)
+    DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI();
 
   return false;
 }
 
 void LoopAccessAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
     AU.addRequired<ScalarEvolutionWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
+    if (UseDA)
+      AU.addRequired<DependenceAnalysisWrapperPass>();
 
     AU.setPreservesAll();
 }
 
 char LoopAccessAnalysis::ID = 0;
 static const char laa_name[] = "Loop Access Analysis";
 #define LAA_NAME "loop-accesses"
 
 INITIALIZE_PASS_BEGIN(LoopAccessAnalysis, LAA_NAME, laa_name, false, true)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(DependenceAnalysisWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_END(LoopAccessAnalysis, LAA_NAME, laa_name, false, true)
 
 char LoopAccessInfoAnalysis::PassID;
 
 LoopAccessInfo LoopAccessInfoAnalysis::run(Loop &L, AnalysisManager<Loop> &AM) {
   // FIXME: ugly const cast
   AnalysisManager<Function> &FAM = const_cast<FunctionAnalysisManager &>(
       AM.getResult<FunctionAnalysisManagerLoopProxy>(L).getManager());
   Function &F = *L.getHeader()->getParent();
   auto *SE = &FAM.getResult<ScalarEvolutionAnalysis>(F);
   auto *TLI = FAM.getCachedResult<TargetLibraryAnalysis>(F);
   auto *AA = &FAM.getResult<AAManager>(F);
   auto *DT = &FAM.getResult<DominatorTreeAnalysis>(F);
   auto *LI = &FAM.getResult<LoopAnalysis>(F);
   const DataLayout &DL = F.getParent()->getDataLayout();
-  return LoopAccessInfo(&L, SE, DL, TLI, AA, DT, LI);
+  auto *DI = UseDA ? &FAM.getResult<DependenceAnalysis>(F) : nullptr;
+  return LoopAccessInfo(&L, SE, DI, DL, TLI, AA, DT, LI);
 }
 
 PreservedAnalyses LoopAccessInfoPrinterPass::run(Loop &L,
                                                  AnalysisManager<Loop> &AM) {
   Function &F = *L.getHeader()->getParent();
   auto &LAI = AM.getResult<LoopAccessInfoAnalysis>(L);
   OS << "Loop access info in function '" << F.getName() << "':\n";
   OS.indent(2) << L.getHeader()->getName() << ":\n";

test/Analysis/LoopAccessAnalysis/use-da.ll

+; RUN: opt -loop-accesses -analyze -use-da-for-loop-accesses < %s | FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; void test(int * restrict a, int * restrict b, long n) {
+;   for (long i = 0; i < n; ++i) {
+;     a[i + n] = i;
+;     b[i] = a[i + 2*n];
+;   }
+; }
+
+; Function Attrs: norecurse nounwind uwtable
+define void @test(i32* noalias nocapture %a, i32* noalias nocapture %b, i64 %n) #0 {
+entry:
+  %cmp11 = icmp sgt i64 %n, 0
+  br i1 %cmp11, label %for.body.lr.ph, label %for.cond.cleanup
+
+; CHECK-LABEL: for function 'test'
+; CHECK-NOT: Memory dependences are safe with run-time checks
+; CHECK: Memory dependences are safe
+; CHECK: Dependences:
+; CHECK-NEXT: Run-time memory checks:
+
+for.body.lr.ph:                                   ; preds = %entry
+  %mul = shl i64 %n, 1
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %for.body, %for.body.lr.ph
+  %i.014 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
+  %conv = trunc i64 %i.014 to i32
+  %add = add nsw i64 %i.014, %n
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %add
+  store i32 %conv, i32* %arrayidx, align 4
+  %add1 = add nsw i64 %i.014, %mul
+  %arrayidx2 = getelementptr inbounds i32, i32* %a, i64 %add1
+  %0 = load i32, i32* %arrayidx2, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %b, i64 %i.014
+  store i32 %0, i32* %arrayidx3, align 4
+  %inc = add nuw nsw i64 %i.014, 1
+  %exitcond = icmp eq i64 %inc, %n
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+attributes #0 = { norecurse nounwind uwtable "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" }
+