Page MenuHomePhabricator

[LAA] Introduce enum for vectorization safety status (NFC).
ClosedPublic

Authored by fhahn on Nov 26 2018, 3:05 AM.

Details

Summary

This patch adds a VectorizationSafetyStatus enum, which will be extended
in a follow up patch to distinguish between 'safe with runtime checks'
and 'known unsafe' dependences.

Diff Detail

Repository
rL LLVM

Event Timeline

fhahn created this revision.Nov 26 2018, 3:05 AM

Hi Florian, are you saying that in this case (known unsafe dep) we would still vectorize the loop (and always fail at run-time)?

fhahn added a comment.Nov 26 2018, 9:27 AM

Hi Florian, are you saying that in this case (known unsafe dep) we would still vectorize the loop (and always fail at run-time)?

Without this patch, yes if the loop has at least one unknown dependence and a non-vectorizable dependence, as in the test case: %l2 - store %ad is unknown, as the they have non constant offsets, %lc - store %vc is known non vectorizable.

anemet added inline comments.Nov 26 2018, 9:51 PM
include/llvm/Analysis/LoopAccessAnalysis.h
212 ↗(On Diff #175220)

What is the actual semantical difference between RuntimeChecksFeasible and ShouldRetryWithRuntimeCheck?

In other words, can't we just clear ShouldRetryWithRuntimeCheck when we see an unsafe known dep?

Ayal added inline comments.Nov 26 2018, 11:28 PM
lib/Analysis/LoopAccessAnalysis.cpp
1620 ↗(On Diff #175220)

Right, but comment best be placed elsewhere.

1661 ↗(On Diff #175220)

Suggest to add and call Dependence::isUnsafeForVectorization(Type) which will determine if there's a dependence that cannot be overcome by runtime checks. Perhaps find a better name - it implies but is not equivalent to !isSafeForVectorization(Type).

Then bail-out as soon as such a dependence is encountered; there's no point in continuing to RecordDependences.

This could alternatively be done here as follows, by leveraging ShouldRetryWithRuntimeCheck, which essentially already indicates if runtime checks may be useful (but then early bail-out is necessary):

if (!DepSafe && Type != Dependence::Unknown) {
  ShouldRetryWithRuntimeCheck = false;
  RecordDependences = false;
  Dependences.clear();
  LLVM_DEBUG(dbgs() << "Found unsafe dependence\n");
  return false;
}
fhahn marked an inline comment as done.Nov 27 2018, 7:01 AM

Thanks Adam and Ayal, responses inline. I would be happy to update the patch to do an early bailout, but I am not sure if that is desirable, as it might have a negative impact on the reports generated.

include/llvm/Analysis/LoopAccessAnalysis.h
212 ↗(On Diff #175220)

At the moment, they refer to slightly different things: RuntimeChecksFeasible is true iff we did not find any dependences making RT ineffective, ShouldRetryWithRuntimeChecks is true iff we encountered an unknown dependence where RT checks might help. Additionally we only set ShouldRetryWithRuntimeChecks for some Unknown dependences. The reason I went with an additional flag was that it seemed easier to see what is going on.

Currently clearing ShouldRetryWithRuntimeCheck would not be enough I think, because we keep checking dependences and we could set ShouldRetryWithRuntimeChecks again for later dependences. Changing the code to bail out early would help (see discussion below)

lib/Analysis/LoopAccessAnalysis.cpp
1661 ↗(On Diff #175220)

Suggest to add and call Dependence::isUnsafeForVectorization(Type) which will determine if there's a dependence that cannot be overcome by runtime checks. Perhaps find a better name - it implies but is not equivalent to !isSafeForVectorization(Type).

Thanks, I'll add a special function. One thing I just realized is that we only should do RT checks for some Unknown dependences. It might be worth adding a new type UnknownRTCheckable or something, to even better distinguish when RT checks are profitable.

Then bail-out as soon as such a dependence is encountered; there's no point in continuing to RecordDependences.

The reason I did not go for an early bailout is that we keep recording dependences even if we found some unsafe ones, I suppose for better reporting. If we go for an early bailout in this patch, this seems slightly inconsistent and it might be worth changing to an early bailout in case of unsafe deps too first?

anemet added inline comments.Nov 27 2018, 9:00 AM
include/llvm/Analysis/LoopAccessAnalysis.h
212 ↗(On Diff #175220)

Even then I would prefer a single three-state value rather than a two booleans, e.g. something like: true, false and unfeasible/failed or some such.

Ayal added inline comments.Nov 27 2018, 1:11 PM
include/llvm/Analysis/LoopAccessAnalysis.h
212 ↗(On Diff #175220)

Agreed it sounds like RetryWithRuntimeChecks could be enum'd to indicate

  1. Should: unknown dependencies exist where RT checks might help;
  2. Don't - Won'tHelpTo: dependencies exists which even RT checks cannot help; or
  3. Don't - NoNeedTo: all's well w/o RT checks.

OTOH, if we encounter a dependence that prevents vectorization and can't bail out on the spot (see below), we could raise an UnsafeForVectorization flag instead. Or perhaps SafeForVectorization/areDepsSafe() should be/return the single three-state value, e.g., something like: Safe, Unsafe, SafeWithRT which correspond to (3), (2), (1) respectively? Start optimistically Safe, move to SafeWithRT only from Safe mode, keep Unsafe is sticky.

(BTW, isSafeForVectorization() seems to be dead and should be removed. The return value of areDepsSafe() is used instead.)

lib/Analysis/LoopAccessAnalysis.cpp
1661 ↗(On Diff #175220)

Then bail-out as soon as such a dependence is encountered; there's no point in continuing to RecordDependences.

Ahh, that's true for LV, but not for LoopDistributor which would like to obtain all the dependencies in order to separate the unsafe ones...

fhahn planned changes to this revision.Dec 4 2018, 7:46 AM

Thanks, I'll update the patch in a bit to use a 3 value enum as suggested.

fhahn updated this revision to Diff 178179.Dec 13 2018, 10:09 PM

Updated to add a StatusTy enum class with 3 values: Safe, SafeWithRTChecks and Unsafe. Please let me know if that is along the lines you were thinking. I am not sure about the naming in the patch and would appreciate any suggestions.

fhahn marked 2 inline comments as done.Dec 13 2018, 10:10 PM

I'll address the unused functions in a separate commit.

Ayal added inline comments.Dec 17 2018, 3:45 PM
include/llvm/Analysis/LoopAccessAnalysis.h
102 ↗(On Diff #178179)

// Can vectorize safely without RT checks. All dependences are known to be safe.

104 ↗(On Diff #178179)

// Can vectorize with RT checks to overcome unknown dependencies.

106 ↗(On Diff #178179)

// Cannot vectorize due to known unsafe dependencies.
, "unknown" is considered SafeWithRtChecks, right?

206 ↗(On Diff #178179)

Use this isSafeForVectorization() getter method where the SafeForVectorization flag was read before, below, instead of replacing it with (inlined) comparisons of Status == StatusTy::Safe.

This will also make it useful (though it could be made protected/private).

287 ↗(On Diff #178179)

Perhaps use a more specific name; e.g., VectorizationSafetyStatus?

lib/Analysis/LoopAccessAnalysis.cpp
1233 ↗(On Diff #178179)

Consider splitting into an NFC patch which has only Safe and Unsafe states, with the test showing it currently vectorizes; plus a separate patch adding SafeWithRtChecks state with updated test.

1323 ↗(On Diff #178179)

Could this be done as follows, based on the numerical values of the enum, properly sorted as now?

if (Status < S)
  Status = S;
fhahn updated this revision to Diff 178567.Dec 17 2018, 5:18 PM
fhahn marked 9 inline comments as done.
fhahn retitled this revision from [LAA] Avoid generating RT checks for known deps preventing vectorization. to [LAA] Introduce enum for vectorization safety status (NFC)..
fhahn edited the summary of this revision. (Show Details)

Thanks, Ayal, I've addressed the comments and stripped the SafeWithRtChecks from this patch.

fhahn added inline comments.
include/llvm/Analysis/LoopAccessAnalysis.h
206 ↗(On Diff #178179)

I'll address visibility and unused functions as follow up commits.

lib/Analysis/LoopAccessAnalysis.cpp
1323 ↗(On Diff #178179)

Nice, I didn't know enum classes provide a default implementation for that.

Ayal added inline comments.Dec 18 2018, 11:24 AM
include/llvm/Analysis/LoopAccessAnalysis.h
100 ↗(On Diff #178567)

Nice, I didn't know enum classes provide a default implementation for that.

Yeah, they have numerical values, which btw could also be specified.
Would be good to note that the order of elements in the enum is important.

221 ↗(On Diff #178567)

This is redundant, as ShouldRetryWithRuntimeCheck implies Unsafe. I.e., can assert !(Should && Safe).
When SafeWithRtChecks is added, in next patch, consider renaming the flag or method (slightly), as they will no longer mean exactly the same thing.

lib/Analysis/LoopAccessAnalysis.cpp
1679 ↗(On Diff #178567)

!isSafeForVectorization() ?

fhahn updated this revision to Diff 178762.Dec 18 2018, 12:35 PM
fhahn marked 4 inline comments as done.

Addressed comments, thanks!

include/llvm/Analysis/LoopAccessAnalysis.h
221 ↗(On Diff #178567)

Yep, I dropped all changes to this function from this patch.

Ayal accepted this revision.Dec 18 2018, 12:41 PM

LGTM, thanks.

include/llvm/Analysis/LoopAccessAnalysis.h
107 ↗(On Diff #178762)

This comment is accurate once SafeWithRtChecks is added, in upcoming patch.

This revision is now accepted and ready to land.Dec 18 2018, 12:41 PM
fhahn marked an inline comment as done.Dec 18 2018, 1:59 PM
fhahn added inline comments.
include/llvm/Analysis/LoopAccessAnalysis.h
107 ↗(On Diff #178762)

Thanks, I'll slightly tweak the comment before committing.

This revision was automatically updated to reflect the committed changes.