Page MenuHomePhabricator

[LAA] Collect pointers with unknown bounds
Needs ReviewPublic

Authored by eastig on Oct 13 2016, 6:40 AM.

Details

Summary

This is an enhancement to LoopAccessAnalysis which enables collecting pointers with unknown bounds. Users of LAA can be interested in them.
The pointers are stored in RuntimePointerChecking. To have them and pointers with known bounds available after analysis, resetting of RuntimePointerChecking is removed from AccessAnalysis::canCheckPtrAtRT.

Event Timeline

eastig updated this revision to Diff 74505.Oct 13 2016, 6:40 AM
eastig retitled this revision from to [LAA] Collect pointers with unknown bounds.
eastig updated this object.
eastig added reviewers: anemet, sbaranga, ashutosh.nema.
eastig added a subscriber: llvm-commits.
ashutosh.nema added inline comments.Oct 17 2016, 12:19 AM
include/llvm/Analysis/LoopAccessAnalysis.h
478

Its good to assert with some message (i.e. unexpected null pointer).

lib/Analysis/LoopAccessAnalysis.cpp
718

Earlier when “NeedRTCheck” is true & LAA can’t find the bounds of pointer it used to reset the “Need” field of RuntimePointerChecking, but with this change it can remains set. Is this expected change ?

eastig added inline comments.Oct 17 2016, 2:36 PM
include/llvm/Analysis/LoopAccessAnalysis.h
478

Not a problem.
I'll do.

lib/Analysis/LoopAccessAnalysis.cpp
718

The old behaviour is to reset RtCheck if we can not do RT checks when they are needed. Resetting means to make RtCheck Pointers and Checks empty. When they are empty it doesn't matter what a value Need has. We can do nothing with such RtCheck. But when Pointers is not empty the value of Need is important. According its documentation Need indicates if we need to add the runtime check. So when it's true RT checks might be created. They are not created if there are pointers with unknown bounds. In such case it's a user responsibility to create checks. The user can analyze Pointers and PtrsWithUnknownBounds and create needed checks.
I hope this explains why Need must be preserved.

ashutosh.nema added inline comments.Oct 18 2016, 4:25 AM
lib/Analysis/LoopAccessAnalysis.cpp
718

I’m worried about cases where decisions are made based on “Need” flag, for example vectorizer. Earlier when this flag is true, vectorizer expects complete runtime check from LAA but with this change it may not be the same case, rather it will be expected from vectorizer to generate the complete check.

eastig added inline comments.Oct 18 2016, 9:19 AM
lib/Analysis/LoopAccessAnalysis.cpp
718

I've looked how "Need" is used. It is used according to its meaning: RT checks need to be added. The vectorizer uses LAI->canVectorizeMemory() to check if a loop can be vectorized. canVectorizeMemory() returns the value of CanVecMem which is set to false if CanDoRTIfNeeded is false (Need is true but CanDoRT is false). So in places where the vectorizer expects complete runtime checks they are complete because CanVecMem guarantees this.

I can update documentation of "Need" to mention that when it is true it does not mean it can do RT check. This is what it's written in comments to AccessAnalysis::canCheckPtrAtRT. Also when "Need" is calculated both pointers with known bounds and pointers with unknown bounds are taken into account.

anemet edited edge metadata.Oct 18 2016, 4:38 PM

This is an enhancement to LoopAccessAnalysis which enables collecting pointers with unknown bounds. Users of LAA can be interested in them.

Please describe the actual use case. We're complicating the interface and we need to know if this is worthwhile.

Please also describe how this work with LoopVersioning (Transform/Util/). Does it pick up the unknown bounds pointers and generate some some sort of run-time checks for them?

On PtrsWithUnknownBounds, you need to expose this in LAA::print and also write tests for directly using -loop-accesses -analyzes (see tests/Analysis/LoopAccessAnalysis).

include/llvm/Analysis/LoopAccessAnalysis.h
495–497

Please split out formatting changes to a separate commit and rebase this patch on top.

lib/Analysis/LoopAccessAnalysis.cpp
661

pointer is not a verb, you need to use add or something

718

For the record, I've looked at the other clients as well (LLE, LDist). They don't check Need. They look for specific type of dependences but the set of dependences is empty unless we were also able to correctly populate the set of memchecks (CanDoRTIfNeeded).

Also you shouldn't add a new feature (PtrsWithUnknownBounds) and changing the semantics of an existing API (whether RtChecks is clear or not) in the same patch.

You should probably do the latter first and explain how it effects existing clients (LV, LLE, LDist).

Moving on to PtrsWithUnknownBounds, right now the generic client code to LAA is something like this:

LAI = LAA->getInfo(L);
Deps = LAI->getDepChecker()->getDependences();
if (!Deps)
  return; // couldn't analyze the loop

// we have a set of dependences that are true if the all the run-time checks pass
RTC = LAI->getRuntimePointerChecking();
Checks = RTC->getChecks();
if (RTC.Need && Checks.empty()
  return; // couldn't generate RT checks

(For this latter check, I would actually prefer if getChecks would return null if we could't generate the checks.)

It would be good if you could describe how this would change with PtrsWithUnknownBounds if at all.

This is an enhancement to LoopAccessAnalysis which enables collecting pointers with unknown bounds. Users of LAA can be interested in them.

Please describe the actual use case. We're complicating the interface and we need to know if this is worthwhile.

The use case is provided here: https://reviews.llvm.org/D24934
I am splitting it into a set of patches.
I want to reuse the results of LAA. Of course I can copy the code from LAA into the "Loop versioning for LICM" pass but I don't want to do this.

Please also describe how this work with LoopVersioning (Transform/Util/). Does it pick up the unknown bounds pointers and generate some some sort of run-time checks for them?

LoopVersioning uses checks either from LAI or user provided ones:

/// \brief Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
/// It uses runtime check provided by the user. If \p UseLAIChecks is true,
/// we will retain the default checks made by LAI. Otherwise, construct an
/// object having no checks and we expect the user to add them.
LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
               DominatorTree *DT, ScalarEvolution *SE,
               bool UseLAIChecks = true);

/// \brief Sets the runtime alias checks for versioning the loop.
void setAliasChecks(
    SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks);

When there are pointers with unknown bounds RT checks are not created because CanDoRT is false.
My understanding is that it's a user responsibility to guarantee RT checks are not empty. It's based on the following and current use cases where checks are tested not to be empty:

BasicBlock* LoopVersioning::versionLoop(
    const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
...
  std::tie(FirstCheckInst, MemRuntimeCheck) =
      LAI.addRuntimeChecks(RuntimeCheckBB->getTerminator(), AliasChecks);
...
  if (MemRuntimeCheck && SCEVRuntimeCheck) {
    RuntimeCheck = BinaryOperator::Create(Instruction::Or, MemRuntimeCheck,
                                          SCEVRuntimeCheck, "lver.safe");
    if (auto *I = dyn_cast<Instruction>(RuntimeCheck))
      I->insertBefore(RuntimeCheckBB->getTerminator());
  } else
    RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;

  assert(RuntimeCheck && "called even though we don't need "
                         "any runtime checks");
...

When LAI.addRuntimeChecks is called for empty checks MemRuntimeCheck is nullptr. So if a user correctly uses LoopVersioning nothing will happen in case of pointers with unknown bounds. There should not be any call of versionLoop. Incorrect uses will cause the assertion failure.

There is also a separate review request regarding to LoopVersioning changes: https://reviews.llvm.org/D25559

On PtrsWithUnknownBounds, you need to expose this in LAA::print and also write tests for directly using -loop-accesses -analyzes (see tests/Analysis/LoopAccessAnalysis).

I'll do this.

eastig added inline comments.Oct 19 2016, 5:30 AM
include/llvm/Analysis/LoopAccessAnalysis.h
506

I think this should be changed to

SmallVector<TrackingVH<Value>, 4> PtrsWithUnknownBounds;

because PtrsWithUnknownBounds will live after the pass.

lib/Analysis/LoopAccessAnalysis.cpp
661

I'll change

718

Also you shouldn't add a new feature (PtrsWithUnknownBounds) and changing the semantics of an existing API (whether RtChecks is clear or
not) in the same patch.

Do you suggest to split the patch into:

  1. Remove the call of reset.
  2. Add PtrsWithUnknownBounds.

It would be good if you could describe how this would change with PtrsWithUnknownBounds if at all.

I think the current use cases won't be affected. They don't make a decision based only on "Need". They use flags which are based on Need and CanDoRt.