This is an archive of the discontinued LLVM Phabricator instance.

[LAA] Avoid generating RT checks for known deps preventing vectorization.
ClosedPublic

Authored by fhahn on Dec 17 2018, 5:19 PM.

Details

Summary

If we found unsafe dependences other than 'unknown', we already know at
compile time that they are unsafe and the runtime checks should always
fail. So we can avoid generating them in those cases.

This should have no negative impact on performance as the runtime checks
that would be created previously should always fail. As a sanity check,
I measured the test-suite, spec2k and spec2k6 and there were no regressions.

Diff Detail

Repository
rL LLVM

Event Timeline

Ayal added inline comments.Dec 18 2018, 12:31 PM
include/llvm/Analysis/LoopAccessAnalysis.h
223 ↗(On Diff #178568)

When SafeWithRtChecks is added, in next patch, consider renaming the flag or method (slightly), as they will no longer mean exactly the same thing.

Consider renaming ShouldRetryWithRuntimeCheck to something like FoundDependenceForRuntimeCheck; or keep the original name but fold SafeWithRtChecks into the flag, i.e., when turning the flag on check if Status is not Unsafe, and when setting Status to Unsafe turn the flag off.

On second thought, now that Status includes SafeWithRtChecks, this flag seems redundant, and suffice to have

bool shouldRetryWithRuntimeCheck() const {
  return Status == VectorizationSafetyStatus::SafeWithRtChecks;
}

?

fhahn marked an inline comment as done.Dec 18 2018, 1:36 PM
fhahn added inline comments.
include/llvm/Analysis/LoopAccessAnalysis.h
223 ↗(On Diff #178568)

Currently, ShouldRetryWithRuntimeCheck is only set when we return Unknown for non-constant distances between dependences. There are other cases where we return Unknown, but do not set it.

By removing it, we would generate runtime checks in more cases. That might be beneficial, but I think should be done in a separate patch.

Ayal added inline comments.Dec 19 2018, 4:31 AM
include/llvm/Analysis/LoopAccessAnalysis.h
223 ↗(On Diff #178568)

Agreed, there's no intent to generate runtime checks in more cases, and the ShouldRetryWithRuntimeCheck flag is only set when a dependence having non constant distance is encountered, w/o being unset when any other (unknown) dependence is encountered. In other words, ShouldRetryWithRuntimeCheck means FoundNonConstantDistanceDependence.

Ideally, SafeWithRtChecks would indicate that only (Safe or) Unknown dependences which can be overcome by RT checks exist, as documented above. This however is not easily determined - "ShouldRetry" may fail. Furthermore, isSafeForVectorization(DepType Type) has only the Type to consider, which does not even distinguish between non constant distance dependences and other RT-un/friendly Unknowns; hence the method returns SafeWithRtChecks for all Unknowns. In other words, SafeWithRtChecks means PossiblySafeWithRtChecks.

So conceptually Status has four possible states of interest:

  1. Safe --> No need to Retry
  2. PossiblySafeWithRtChecks without having found a non constant distance --> Don't Retry, not worth it(?)
  3. PossiblySafeWithRtChecks having found a non constant distance --> Retry
  4. Unsafe --> Don't Retry, no point

In order to determine the current Status, isDependent() communicates to isSafeForVectorization(DepType Type) a DepType. One possible option is to introduce another 'NonConstantDistance' member to DepType, but that might be intrusive. Another option is to have isDependent() return both a DepType and an indication whether a non constant distance dependence was observed, and determine the Status according to both.

In any case, areDepsSafe() can return a Status instead of a boolean; this could simplify the if (!CanVecMem && DepChecker->shouldRetryWithRuntimeCheck()) (although this !CanVecMem seems redundant...).

fhahn marked an inline comment as done.Dec 19 2018, 1:08 PM
fhahn added inline comments.
include/llvm/Analysis/LoopAccessAnalysis.h
223 ↗(On Diff #178568)

Agreed. What do you think of proceeding in the following steps:

  1. change SafeWithRtChecks to PossiblySafeWithRtChecks in this patch
  2. in a follow up patch, add NonConstantDistance to DepType, drop the possibly from PossiblySafeWithRtChecks and return it for NonConstantDistance dependences and Unsafe otherwise
  3. in another follow up patch, make areDepsSafe return a Status

IMO splitting it up makes sense, as the follow ups are structural improvements not directly related to the aim of this patch and it makes it easier to pin point where things went wrong, if there are problems.

Ayal added inline comments.Dec 19 2018, 2:43 PM
include/llvm/Analysis/LoopAccessAnalysis.h
223 ↗(On Diff #178568)

Sure, this breakdown LGTM. Some comments:

  1. When introducing PossiblySafeWithRtChecks, suggest to rename ShouldRetryWithRuntimeCheck to FoundNonConstantDistanceDependence. Or keep the name but turn the flag off whenever Status becomes Unsafe. The original motivation is to avoid having discrepancy between a flag and a method of exactly the same name, where the method no longer simply retrieves the flag.
  2. When to introducing NonConstantDistance, if we return Unsafe for all other Unknown's we'll be restricting Retry only to cases where all dependences are (either Safe or) of non constant distance. Seems Retry may succeed for other Unknown dependences today, say of distinct types/strides (but not of distinct address spaces - consider these Unsafe?). Would be good btw to include tests for various Unknown combinations, and perhaps a TODO for cases that have only (Safe and) non-constant distance unknown dependences.
  3. Changing the return type of areDepsSafe is indeed orthogonal.
fhahn updated this revision to Diff 179005.Dec 19 2018, 6:35 PM

Rename to PossiblySafeWithRtChecks and FoundNonConstantDistanceDependence.

fhahn marked an inline comment as done.Dec 19 2018, 6:39 PM
fhahn added inline comments.
include/llvm/Analysis/LoopAccessAnalysis.h
223 ↗(On Diff #178568)

When to introducing NonConstantDistance, if we return Unsafe for all other Unknown's we'll be restricting Retry only to cases where all dependences are (either Safe or) of non constant distance. Seems Retry may succeed for other Unknown dependences today, say of distinct types/strides (but not of distinct address spaces - consider these Unsafe?). Would be good btw to include tests for various Unknown combinations, and perhaps a TODO for cases that have only (Safe and) non-constant distance unknown dependences.

Yep, before making that change, we have to make sure we do not miss any cases where runtime checks could be succeed. I'll put up a patch once I did that.

Ayal accepted this revision.Dec 19 2018, 11:39 PM

This LGTM, thanks.

This revision is now accepted and ready to land.Dec 19 2018, 11:39 PM
This revision was automatically updated to reflect the committed changes.