This is an archive of the discontinued LLVM Phabricator instance.

Use type sizes when determining dependence
ClosedPublic

Authored by jolanta.jensen on Aug 26 2021, 7:12 AM.

Details

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.

Diff Detail

Event Timeline

jolanta.jensen created this revision.Aug 26 2021, 7:12 AM
jolanta.jensen requested review of this revision.Aug 26 2021, 7:12 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 26 2021, 7:12 AM
fhahn requested changes to this revision.Aug 26 2021, 7:18 AM
fhahn added a subscriber: 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.

This revision now requires changes to proceed.Aug 26 2021, 7:18 AM
malharJ added inline comments.
llvm/lib/Analysis/LoopAccessAnalysis.cpp
1616

Should this now be

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

malharJ added inline comments.Sep 3 2021, 9:20 AM
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 updated this revision to Diff 372777.EditedSep 15 2021, 12:42 PM

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

Hi,

I would be grateful for re-review.

Cheers,
Jolanta

jolanta.jensen marked an inline comment as done.Sep 27 2021, 4:02 AM
jolanta.jensen added inline comments.
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.

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

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

jolanta.jensen marked 2 inline comments as done.Nov 4 2021, 8:55 AM
jolanta.jensen added inline comments.
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.

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

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.

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

jolanta.jensen marked 5 inline comments as done.Nov 25 2021, 3:10 AM
sdesmalen accepted this revision.Nov 25 2021, 3:14 AM

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 added inline comments.Nov 26 2021, 1:16 AM
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/

mgabka added a subscriber: mgabka.Nov 29 2021, 1:56 AM

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 marked 2 inline comments as done.Nov 30 2021, 4:36 AM
jolanta.jensen added inline comments.
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 accepted this revision.Dec 5 2021, 2:30 PM

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.

This revision is now accepted and ready to land.Dec 5 2021, 2:30 PM

@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 added inline comments.Dec 6 2021, 8:04 AM
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 updated this revision to Diff 392396.Dec 7 2021, 7:27 AM

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

sdesmalen added inline comments.Dec 7 2021, 7:28 AM
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 accepted this revision.Dec 8 2021, 12:51 AM

LGTM, thanks!

fhahn added inline comments.Dec 8 2021, 12:54 AM
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

This revision was automatically updated to reflect the committed changes.

Thanks for the feedback @fhahn!

llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll
74

Done.