This is an archive of the discontinued LLVM Phabricator instance.

[LAA] Extend isConsecutiveAccess to determine if two accesses are consecutive, reverse consecutive, or non-consecutive.
AbandonedPublic

Authored by mcrosier on Sep 2 2016, 6:53 AM.

Details

Reviewers
mkuper
mssimpso
Summary

The current implementation of isConsecutiveAccess(A,B) checks to see if access A is consecutively followed by access B. With little additional work we can determine if B is followed by A (i.e., reverse consecutive) or if A and B are not known to be consecutive.

This patch modifies isConsecutiveAccess to:

  • return 1 if A and B are consecutive and B follows A,
  • return -1 if A and B are consecutive and A follows B (i.e., reverse consecutive) or,
  • return 0 if we can't prove and A and B to be consecutive.

This is very similar to the behavior of the isConsecutivePtr function in the loop vectorizer and IMO having isConsecutiveAccess follow suit makes sense.

This patch also uses this new functionality to reduce the number of calls to isConsecutiveAccesses in the SLP vectorizer.

Across SPEC2000 and SPEC2006 the total number of calls to isConsecutiveAccess is reduced by 4.31% or 18875 calls. There should be no functional change other than the reduction is calls.

All of the SPEC200X and llvm test-suite tests passed correctness tests and show no codegen changes as expected. I plan on kicking off the compile-time regression tests over the weekend.

Chad

Diff Detail

Event Timeline

mcrosier updated this revision to Diff 70153.Sep 2 2016, 6:53 AM
mcrosier retitled this revision from to [LAA] Extend isConsecutiveAccess to determine if two accesses are consecutive, reverse consecutive, or non-consecutive..
mcrosier updated this object.
mcrosier added reviewers: mkuper, mssimpso.
mcrosier added a subscriber: llvm-commits.
mcrosier updated this object.Sep 2 2016, 6:58 AM
mcrosier updated this object.Sep 2 2016, 7:02 AM
mkuper edited edge metadata.Sep 2 2016, 10:13 AM

I'm not sure this is a clear compile-time win. We'll get less calls to isConsecutiveAcess, but most of the clients - except for the Load case in buildTree_rec() - care only about one direction. We'll see what regression testing shows, I guess. My guess is "noise". :-)

include/llvm/Analysis/LoopAccessAnalysis.h
718

Any compelling reason not to make this an enum?

lib/Analysis/LoopAccessAnalysis.cpp
1083

Aren't these the same values BaseDelta and OffsetDeltaSCEV already have?

mcrosier abandoned this revision.Oct 26 2016, 5:53 AM

Abandoning for now..