Page MenuHomePhabricator

Use type sizes when determining dependence
Needs ReviewPublic

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



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.

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.

Should this now be

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

malharJ added inline comments.Sep 3 2021, 9:20 AM
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, 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.


I would be grateful for re-review.


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


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


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).


same question for this case.


nit: s/backwards/backward

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

jolanta.jensen marked 2 inline comments as done.Thu, Nov 4, 8:55 AM
jolanta.jensen added inline comments.

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


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.


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


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(..) {?


nit: strange indentation.


nit: odd indentation


nit: strange indentation.

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

jolanta.jensen marked 5 inline comments as done.Thu, Nov 25, 3:10 AM
sdesmalen accepted this revision.Thu, Nov 25, 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.Fri, Nov 26, 1:16 AM

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?


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


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.


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.Mon, Nov 29, 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.Tue, Nov 30, 4:36 AM
jolanta.jensen added inline comments.



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