[LAA] LLE 1/6: Expose Forward dependences

[anemet]

Summary

Before this change, we didn't use to collect forward dependences since
none of the current clients (LV, LDist) required them.

The motivation to also collect forward dependences is a new pass
LoopLoadElimination (LLE) which discovers store-to-load forwarding
opportunities across the loop's backedge. The pass uses both lexically
forward or backward loop-carried dependences to detect these
opportunities.

The new pass also analyzes loop-independent (forward) dependences since
they can conflict with the loop-carried dependences in terms of how the
data flows through memory.

The newly added test only covers loop-carried forward dependences
because loop-independent ones are currently categorized as NoDep. The
next patch will fix this.

The two patches were tested together for compile-time regression. None
found in LNT/SPEC.

Note that with this change LAA provides all dependences rather than just
"interesting" ones. A subsequent NFC patch will remove the now trivial
isInterestingDependence and rename the APIs.

[rengolin]

Hi Adam,

I've just been referred to this set of reviews as a mean to fix the following problem:

for (k..N)
  a[k] = b[k] + b[k+1];

Currently, GVN is hoisting the [k] load and adding an extra PHI to the loop body, making it unvectorizeable.

By adding LLE after the vectorizer, we can cover the same case in LLE without breaking vectorization opportunities.

Ultimately, Hal should approve all those patches, but I'll give my own take on them, if you're still interested in pushing them through.

This first one, LGTM.

cheers,
--renato

[anemet]

Hi Renato,

Thanks very much for looking at the set! I sure am interested pushing these through but I wanted to see where the main LLE patch was going before pinging these ones.

Adam

[hfinkel]

LGTM too.

llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp

bool MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) {
   case Backward:
   case BackwardVectorizableButPreventsForwarding:
     return false;
   }
   llvm_unreachable("unexpected DepType!");
 }
 
 bool MemoryDepChecker::Dependence::isInterestingDependence(DepType Type) {
-  switch (Type) {
-  case NoDep:
-  case Forward:
-    return false;
-
-  case BackwardVectorizable:
-  case Unknown:
-  case ForwardButPreventsForwarding:
-  case Backward:
-  case BackwardVectorizableButPreventsForwarding:
-    return true;
-  }
-  llvm_unreachable("unexpected DepType!");
+  return Type != NoDep;
 }
 
 bool MemoryDepChecker::Dependence::isPossiblyBackward() const {
   switch (Type) {
   case NoDep:
   case Forward:
   case ForwardButPreventsForwarding:
     return false;

llvm/trunk/test/Analysis/LoopAccessAnalysis/forward-loop-carried.ll

+; RUN: opt -loop-accesses -analyze < %s | FileCheck %s
+
+;   for (unsigned i = 0; i < 100; i++) {
+;     A[i+8] = B[i] + 2;
+;     C[i] = A[i] * 2;
+;   }
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32* %B, i32* %C, i64 %N) {
+
+; CHECK: Interesting Dependences:
+; CHECK-NEXT: Forward:
+; CHECK-NEXT:   store i32 %a_p1, i32* %Aidx_ahead, align 4 ->
+; CHECK-NEXT:   %a = load i32, i32* %Aidx, align 4
+
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+
+  %idx = add nuw nsw i64 %indvars.iv, 8
+
+  %Aidx_ahead = getelementptr inbounds i32, i32* %A, i64 %idx
+  %Bidx = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  %Cidx = getelementptr inbounds i32, i32* %C, i64 %indvars.iv
+  %Aidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+
+  %b = load i32, i32* %Bidx, align 4
+  %a_p1 = add i32 %b, 2
+  store i32 %a_p1, i32* %Aidx_ahead, align 4
+
+  %a = load i32, i32* %Aidx, align 4
+  %c = mul i32 %a, 2
+  store i32 %c, i32* %Cidx, align 4
+
+  %exitcond = icmp eq i64 %indvars.iv.next, %N
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}

llvm/trunk/test/Analysis/LoopAccessAnalysis/safe-no-checks.ll

 ; RUN: opt -basicaa -loop-accesses -analyze < %s | FileCheck %s
 
 ; If the arrays don't alias this loop is safe with no memchecks:
 ;   for (i = 0; i < n; i++)
 ;    A[i] = A[i+1] * B[i] * C[i];
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.10.0"
 
+; Check the loop-carried forward anti-dep between the load of A[i+1] and the
+; store of A[i];
+
 ; CHECK: Memory dependences are safe{{$}}
+; CHECK-NEXT: Interesting Dependences:
+; CHECK-NEXT:   Forward:
+; CHECK-NEXT:     %loadA_plus_2 = load i16, i16* %arrayidxA_plus_2, align 2 ->
+; CHECK-NEXT:     store i16 %mul1, i16* %arrayidxA, align 2
+
 
 define void @f(i16* noalias %a,
                i16* noalias %b,
                i16* noalias %c) {
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry