Use type sizes when determining dependence

[jolanta.jensen]

Summary

In the isDependence function the code does not try hard enough
to determine the dependence between types. If the types are
different it simply gives up, whereas in fact what we really
care about are the type sizes. I've changed the code to compare
sizes instead of types.

[fhahn]

The test should be moved to`llvm/test/Analysis/LoopAccessAnalysis/` and please simplify the input IR to only the required loop + memory operations.

llvm/test/Transforms/LoopVectorize/depend_diff_types.ll

11 ↗

(On Diff #368870)

Please try to simplify the input IR and try to motivate/explain the problem only based on the input IR.

[malharJ]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1616

Should this now be

"LAA: Zero dependence difference but different type sizes" ?

[malharJ]

llvm/test/Transforms/LoopVectorize/depend_diff_types.ll

40 ↗

(On Diff #368870)

Looks like this isn't being used anywhere and can be removed ?

If so, can also remove line 65

%25 = add nsw i32 %.dY0001_321.0, -1

Then also change

%26 = icmp sgt i32 %.dY0001_321.0, 1

to something like

%26 = icmp slt i32 %indvars.iv.next, M

58–63 ↗

(On Diff #368870)

perhaps this can be removed ?

It looks like the IR corresponds to

1) v3[i+31] = (v1[1903+i] * v3[1023+i]);   // ---> all accesses are double*

2) v3[i+1007] =  v1[i+47];   // ---> all accesses are i64*

3) v3[i+16319] = v1[i+79];   // ---> all accesses are i64* (could remove ?)

Perhaps we are only concerned with the lines 1 and 2, as they are of different types ?

[jolanta.jensen]

The test is rewritten. Also updated the comments about type sizes.

[jolanta.jensen]

Hi,

I would be grateful for re-review.

Cheers,
Jolanta

[jolanta.jensen]

llvm/test/Transforms/LoopVectorize/depend_diff_types.ll

11 ↗

(On Diff #368870)

The whole test is rewritten.

58–63 ↗

(On Diff #368870)

The whole test is rewritten.

[sdesmalen]

Hi @jolanta.jensen thanks for this change!

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1571

nit: s/SizesAreSame/HasSameSize/
(this may be personal preference, so feel free to ignore).

1576

Is it worth also having a negative and positive test for this case, one where the sizes are not the same (guaranteed dependence) and one where the sizes are the same (no dependence). I think we at least need a positive test (i.e. proving no dependence when the types are different, but the same size, because I don't think your current tests covers the case of an unknown dependence distance).

1591

same question for this case.

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll

44

nit: s/backwards/backward

[jolanta.jensen]

The code and the test have been updated after the review comments.

[jolanta.jensen]

llvm/lib/Analysis/LoopAccessAnalysis.cpp

1576

The test case has been extended to cover the positive case for unknown distance and the same sizes.

1591

The test case has been extended to cover this case.

[jolanta.jensen]

Corrected line 1556 in LoopAccessAnalysis.cpp where we were still comparing types.
Extended the test to cover the change to line 1556.

[sdesmalen]

Thanks for the changes, looks mostly fine to me. I just had a few more nits on the test.

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll

4

nit: can you move this after the -passes='...', that way it's easier to see the difference between the two RUN lines.

18

Can you use CHECK-SAFE-NEXT: for all these? That way there are no other dependences that aren't caught by the CHECK lines. (same for the CHECK lines below).

nit: Can you move the CHECK lines just above define void @backdep_type_size_equivalence(..) {?

36

nit: strange indentation.

36

nit: odd indentation

101

nit: strange indentation.

[jolanta.jensen]

Adjusted indentation and changed CHECK to CHECK-NEXT in depend_diff_types.ll

[sdesmalen]

Thanks for addressing all the comments @jolanta.jensen, the patch looks good to me now!

@fhahn are you happy to remove your request for changes?

[fhahn]

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll

2

I think there's an effort to remove remove the legacy opt invocations from opt and this already happened for the tests in this directory. Could you remove the line?

3

does the test need require<tbaa>? It looks like there's no !tbaa metadata in the test.

9

All tests here have types where TypeSize == StoreSize == AllocaSize. Could you add a test with a type where TypeSize != StoreSize != AllocaSize, e.g. using something like i19.

26

Why are there no check lines for CHECK-UNSAFE for this function? Same for CHECK-SAFE for the function below/

[jolanta.jensen]

Removed legacy invocation and require<tbaa>.
Removed -store-to-load-forwarding-conflict-detection flag
as it is set by default and simplified check labels.
Added test where TypeSize != StoreSize != AllocaSize.

[jolanta.jensen]

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll

3

Removed.

26

Only using CHECK now as the -store-to-load-forwarding-conflict-detection flag is set by default.

[fhahn]

LGTM with additional comments for the tests addressed. Please also add something like [LAA] to the beginning of the title, so it is easier to categorise the change when reading the commit log.

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll

93

nit: formatting is off here and for other stores in this test.

135

can you also throw in a read or write to a 32 bit type? Might be good to move those into a separate test.

[sdesmalen]

@fhahn can you help me understand your comment on the test so that I can address it before I land the patch? (@jolanta.jensen is OoO and I was asked to land the patch on her behalf)

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll

135

Can you be a bit more specific about what you'd like to see? I can't quickly see what added value a read/write to 32bit type would add here. Or see which part needs moving to a separate test.

[fhahn]

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll

135

I was thinking about a test that explicitly checks that the alloc types are compared in the HasSameSize check. Having a test with i19 and double accesses doesn't really ensure this, as DL.getTypeAllocSize(double) != all the different sizes (store, alloc) for i19,( i19 and double will never have the same size, except in very weird data layouts)

In a test that has accesses with i19 and i32, we should get different results for the HasSameSize check, if we use a different size in the compare (e.g. if we compare the type size directly), like below

(btw the use of unnamed IR values makes it a bit harder to play with the test cases)

define void @neg_dist_dep_type_size_equivalence(i64* nocapture %vec, i64 %n) {
entry:
  br label %loop

loop:
  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %loop ]

  ;; Load from vec[indvars.iv] as double
  %0 = getelementptr i64, i64* %vec, i64 %indvars.iv
  %1 = bitcast i64* %0 to i32*
  %2 = load i32, i32* %1, align 8
  %3 = mul i32 %2, 5

  ;; Different sizes
  %v8 = add nuw nsw i64 %indvars.iv, %n
  %v9 = getelementptr inbounds i64, i64* %vec, i64 %v8
  %v10 = bitcast i64* %v9 to i19*
  %v11 = trunc i32 %3 to i19
  store i19 %v11, i19* %v10, align 8

  ;; Loop condition.
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %cond = icmp eq i64 %indvars.iv.next, %n
  br i1 %cond, label %exit, label %loop

exit:
  ret void
}

[sdesmalen]

Added new test-case (i32 vs float, and i32 vs i19) and gave some more meaningful names to the variables in the test.

[sdesmalen]

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll

135

Thanks, that makes sense! I've added a new test. Please have a look to see if that's what you were expecting.

[fhahn]

LGTM, thanks!

[fhahn]

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll

74

the patch checks the alloc size, which may be different to the store size, would be good to fix before committing

[sdesmalen]

Thanks for the feedback @fhahn!

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll

74

Done.

llvm/lib/Analysis/LoopAccessAnalysis.cpp

MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   // the address space.
   if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){
     LLVM_DEBUG(dbgs() << "Pointer access with non-constant stride\n");
     return Dependence::Unknown;
   }
 
   auto &DL = InnermostLoop->getHeader()->getModule()->getDataLayout();
   uint64_t TypeByteSize = DL.getTypeAllocSize(ATy);
+  bool HasSameSize =
+      DL.getTypeStoreSizeInBits(ATy) == DL.getTypeStoreSizeInBits(BTy);
   uint64_t Stride = std::abs(StrideAPtr);
   const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist);
   if (!C) {
-    if (!isa<SCEVCouldNotCompute>(Dist) &&
-        TypeByteSize == DL.getTypeAllocSize(BTy) &&
+    if (!isa<SCEVCouldNotCompute>(Dist) && HasSameSize &&
         isSafeDependenceDistance(DL, *(PSE.getSE()),
                                  *(PSE.getBackedgeTakenCount()), *Dist, Stride,
                                  TypeByteSize))
       return Dependence::NoDep;
 
     LLVM_DEBUG(dbgs() << "LAA: Dependence because of non-constant distance\n");
     FoundNonConstantDistanceDependence = true;
     return Dependence::Unknown;
   }
 
   const APInt &Val = C->getAPInt();
   int64_t Distance = Val.getSExtValue();
 
   // Attempt to prove strided accesses independent.
-  if (std::abs(Distance) > 0 && Stride > 1 && ATy == BTy &&
+  if (std::abs(Distance) > 0 && Stride > 1 && HasSameSize &&
       areStridedAccessesIndependent(std::abs(Distance), Stride, TypeByteSize)) {
     LLVM_DEBUG(dbgs() << "LAA: Strided accesses are independent\n");
     return Dependence::NoDep;
   }
 
   // Negative distances are not plausible dependencies.
   if (Val.isNegative()) {
     bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
     if (IsTrueDataDependence && EnableForwardingConflictDetection &&
         (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize) ||
-         ATy != BTy)) {
+         !HasSameSize)) {
       LLVM_DEBUG(dbgs() << "LAA: Forward but may prevent st->ld forwarding\n");
       return Dependence::ForwardButPreventsForwarding;
     }
 
     LLVM_DEBUG(dbgs() << "LAA: Dependence is negative\n");
     return Dependence::Forward;
   }
 
   // Write to the same location with the same size.
-  // Could be improved to assert type sizes are the same (i32 == float, etc).
   if (Val == 0) {
-    if (ATy == BTy)
+    if (HasSameSize)
       return Dependence::Forward;
     LLVM_DEBUG(
-        dbgs() << "LAA: Zero dependence difference but different types\n");
+        dbgs() << "LAA: Zero dependence difference but different type sizes\n");
     return Dependence::Unknown;
   }
 
   assert(Val.isStrictlyPositive() && "Expect a positive value");
 
-  if (ATy != BTy) {
-    LLVM_DEBUG(
-        dbgs()
-        << "LAA: ReadWrite-Write positive dependency with different types\n");
+  if (!HasSameSize) {
+    LLVM_DEBUG(dbgs() << "LAA: ReadWrite-Write positive dependency with "
+                         "different type sizes\n");
     return Dependence::Unknown;
   }
 
   // Bail out early if passed-in parameters make vectorization not feasible.
   unsigned ForcedFactor = (VectorizerParams::VectorizationFactor ?
                            VectorizerParams::VectorizationFactor : 1);
   unsigned ForcedUnroll = (VectorizerParams::VectorizationInterleave ?
                            VectorizerParams::VectorizationInterleave : 1);

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll

+; RUN: opt -S -disable-output -passes='require<scalar-evolution>,require<aa>,loop(print-access-info)' < %s 2>&1 | FileCheck %s
+
+
+; In the function below some of the accesses are done as float types and some
+; are done as i32 types. When doing dependence analysis the type should not
+; matter if it can be determined that they are the same size.
+
+%int_pair = type { i32, i32 }
+
+; CHECK-LABEL: function 'backdep_type_size_equivalence':
+; CHECK-NEXT:    loop:
+; CHECK-NEXT:      Memory dependences are safe with a maximum dependence distance of 800 bytes
+; CHECK-NEXT:      Dependences:
+; CHECK-NEXT:        Forward:
+; CHECK-NEXT:            %ld.f32 = load float, float* %gep.iv.f32, align 8 ->
+; CHECK-NEXT:            store i32 %indvars.iv.i32, i32* %gep.iv, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        Forward:
+; CHECK-NEXT:            %ld.f32 = load float, float* %gep.iv.f32, align 8 ->
+; CHECK-NEXT:            store float %val, float* %gep.iv.min.100.f32, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        BackwardVectorizable:
+; CHECK-NEXT:            store float %val, float* %gep.iv.min.100.f32, align 8 ->
+; CHECK-NEXT:            store i32 %indvars.iv.i32, i32* %gep.iv, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        Run-time memory checks:
+; CHECK-NEXT:        Grouped accesses:
+
+define void @backdep_type_size_equivalence(%int_pair* nocapture %vec, i64 %n) {
+entry:
+  br label %loop
+
+loop:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %loop ]
+
+  ;; Load from vec[indvars.iv].x as float
+  %gep.iv = getelementptr inbounds %int_pair, %int_pair* %vec, i64 %indvars.iv, i32 0
+  %gep.iv.f32 = bitcast i32* %gep.iv to float*
+  %ld.f32 = load float, float* %gep.iv.f32, align 8
+  %val = fmul fast float %ld.f32, 5.0
+
+  ;; Store to vec[indvars.iv - 100].x as float
+  %indvars.iv.min.100 = add nsw i64 %indvars.iv, -100
+  %gep.iv.min.100 = getelementptr inbounds %int_pair, %int_pair* %vec, i64 %indvars.iv.min.100, i32 0
+  %gep.iv.min.100.f32 = bitcast i32* %gep.iv.min.100 to float*
+  store float %val, float* %gep.iv.min.100.f32, align 8
+
+  ;; Store to vec[indvars.iv].x as i32, creating a backward dependency between
+  ;; the two stores with different element types but the same element size.
+  %indvars.iv.i32 = trunc i64 %indvars.iv to i32
+  store i32 %indvars.iv.i32, i32* %gep.iv, align 8
+
+  ;; Store to vec[indvars.iv].y as i32, strided accesses should be independent
+  ;; between the two stores with different element types but the same element size.
+  %gep.iv.1 = getelementptr inbounds %int_pair, %int_pair* %vec, i64 %indvars.iv, i32 1
+  store i32 %indvars.iv.i32, i32* %gep.iv.1, align 8
+
+  ;; Store to vec[indvars.iv + n].y as i32, to verify no dependence in the case
+  ;; of unknown dependence distance.
+  %indvars.iv.n = add nuw nsw i64 %indvars.iv, %n
+  %gep.iv.n = getelementptr inbounds %int_pair, %int_pair* %vec, i64 %indvars.iv.n, i32 1
+  store i32 %indvars.iv.i32, i32* %gep.iv.n, align 8
+
+  ;; Loop condition.
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %cond = icmp eq i64 %indvars.iv.next, %n
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+; In the function below one of the accesses is done as i19 type, which has a
+; different store size than the i32 type, even though their alloc sizes are
+; equivalent. This is a negative test to ensure that they are not analyzed as
+; in the tests above.
+;
+; CHECK-LABEL: function 'backdep_type_store_size_equivalence':
+; CHECK-NEXT:    loop:
+; CHECK-NEXT:      Report: unsafe dependent memory operations in loop.
+; CHECK-NEXT:      Dependences:
+; CHECK-NEXT:        Unknown:
+; CHECK-NEXT:            %ld.f32 = load float, float* %gep.iv.f32, align 8 ->
+; CHECK-NEXT:            store i19 %indvars.iv.i19, i19* %gep.iv.i19, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        Run-time memory checks:
+; CHECK-NEXT:        Grouped accesses:
+
+define void @backdep_type_store_size_equivalence(%int_pair* nocapture %vec, i64 %n) {
+entry:
+  br label %loop
+
+loop:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %loop ]
+
+  ;; Load from vec[indvars.iv].x as float
+  %gep.iv = getelementptr inbounds %int_pair, %int_pair* %vec, i64 %indvars.iv, i32 0
+  %gep.iv.f32 = bitcast i32* %gep.iv to float*
+  %ld.f32 = load float, float* %gep.iv.f32, align 8
+  %val = fmul fast float %ld.f32, 5.0
+
+  ;; Store to vec[indvars.iv].x as i19.
+  %indvars.iv.i19 = trunc i64 %indvars.iv to i19
+  %gep.iv.i19 = bitcast i32* %gep.iv to i19*
+  store i19 %indvars.iv.i19, i19* %gep.iv.i19, align 8
+
+  ;; Loop condition.
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %cond = icmp eq i64 %indvars.iv.next, %n
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+; In the function below some of the accesses are done as double types and some
+; are done as i64 and i32 types. This is a negative test to ensure that they
+; are not analyzed as in the tests above.
+
+; CHECK-LABEL: function 'neg_dist_dep_type_size_equivalence':
+; CHECK-NEXT:    loop:
+; CHECK-NEXT:      Report: unsafe dependent memory operations in loop.
+; CHECK-NEXT:      Dependences:
+; CHECK-NEXT:        Unknown:
+; CHECK-NEXT:            %ld.i64 = load i64, i64* %gep.iv, align 8 ->
+; CHECK-NEXT:            store i32 %ld.i64.i32, i32* %gep.iv.n.i32, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        ForwardButPreventsForwarding:
+; CHECK-NEXT:            store double %val, double* %gep.iv.101.f64, align 8 ->
+; CHECK-NEXT:            %ld.i64 = load i64, i64* %gep.iv, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        Unknown:
+; CHECK-NEXT:            %ld.f64 = load double, double* %gep.iv.f64, align 8 ->
+; CHECK-NEXT:            store i32 %ld.i64.i32, i32* %gep.iv.n.i32, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        BackwardVectorizableButPreventsForwarding:
+; CHECK-NEXT:            %ld.f64 = load double, double* %gep.iv.f64, align 8 ->
+; CHECK-NEXT:            store double %val, double* %gep.iv.101.f64, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:        Unknown:
+; CHECK-NEXT:            store double %val, double* %gep.iv.101.f64, align 8 ->
+; CHECK-NEXT:            store i32 %ld.i64.i32, i32* %gep.iv.n.i32, align 8
+; CHECK-EMPTY:
+; CHECK-NEXT:      Run-time memory checks:
+; CHECK-NEXT:      Grouped accesses:
+
+define void @neg_dist_dep_type_size_equivalence(i64* nocapture %vec, i64 %n) {
+entry:
+  br label %loop
+
+loop:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %loop ]
+
+  ;; Load from vec[indvars.iv] as double
+  %gep.iv = getelementptr i64, i64* %vec, i64 %indvars.iv
+  %gep.iv.f64 = bitcast i64* %gep.iv to double*
+  %ld.f64 = load double, double* %gep.iv.f64, align 8
+  %val = fmul fast double %ld.f64, 5.0
+
+  ;; Store to vec[indvars.iv + 101] as double
+  %indvars.iv.101 = add nsw i64 %indvars.iv, 101
+  %gep.iv.101.i64 = getelementptr i64, i64* %vec, i64 %indvars.iv.101
+  %gep.iv.101.f64 = bitcast i64* %gep.iv.101.i64 to double*
+  store double %val, double* %gep.iv.101.f64, align 8
+
+  ;; Read from vec[indvars.iv] as i64 creating
+  ;; a forward but prevents forwarding dependence
+  ;; with different types but same sizes.
+  %ld.i64 = load i64, i64* %gep.iv, align 8
+
+  ;; Different sizes
+  %indvars.iv.n = add nuw nsw i64 %indvars.iv, %n
+  %gep.iv.n.i64 = getelementptr inbounds i64, i64* %vec, i64 %indvars.iv.n
+  %gep.iv.n.i32 = bitcast i64* %gep.iv.n.i64 to i32*
+  %ld.i64.i32 = trunc i64 %ld.i64 to i32
+  store i32 %ld.i64.i32, i32* %gep.iv.n.i32, align 8
+
+  ;; Loop condition.
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %cond = icmp eq i64 %indvars.iv.next, %n
+  br i1 %cond, label %exit, label %loop
+
+exit:
+  ret void
+}