[LAA] Collect pointers with unknown bounds

[eastig]

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.

[ashutosh.nema]

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]

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]

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]

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]

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.

[eastig]

In D25557#573719, @anemet wrote:

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]

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.

include/llvm/Analysis/LoopAccessAnalysis.h

public:
 
   RuntimePointerChecking(ScalarEvolution *SE) : Need(false), SE(SE) {}
 
   /// Reset the state of the pointer runtime information.
   void reset() {
     Need = false;
     Pointers.clear();
     Checks.clear();
+    PtrsWithUnknownBounds.clear();
   }
 
   /// Insert a pointer and calculate the start and end SCEVs.
   /// We need \p PSE in order to compute the SCEV expression of the pointer
   /// according to the assumptions that we've made during the analysis.
   /// The method might also version the pointer stride according to \p Strides,
   /// and add new predicates to \p PSE.
   void insert(Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId,
public:
   /// index \p I and \p J to prove their independence.
   bool needsChecking(unsigned I, unsigned J) const;
 
   /// \brief Return PointerInfo for pointer at index \p PtrIdx.
   const PointerInfo &getPointerInfo(unsigned PtrIdx) const {
     return Pointers[PtrIdx];
   }
 
+  /// \brief Notify RuntimePointerChecking that Ptr has unknown bounds.
+  void pointerWithUnknownBounds(Value *Ptr) {
+    assert(Ptr);
+    PtrsWithUnknownBounds.push_back(Ptr);
+  }
+
+  /// \brief Get a list of pointers which have unknonw bounds.
+  const SmallVectorImpl<Value *> &getPointersWithUnknownBounds() const {
+    return PtrsWithUnknownBounds;
+  }
+
 private:
   /// \brief Groups pointers such that a single memcheck is required
   /// between two different groups. This will clear the CheckingGroups vector
   /// and re-compute it. We will only group dependecies if \p UseDependencies
   /// is true, otherwise we will create a separate group for each pointer.
   void groupChecks(MemoryDepChecker::DepCandidates &DepCands,
                    bool UseDependencies);
 
   /// Generate the checks and return them.
-  SmallVector<PointerCheck, 4>
-  generateChecks() const;
+  SmallVector<PointerCheck, 4> generateChecks() const;
 
   /// Holds a pointer to the ScalarEvolution analysis.
   ScalarEvolution *SE;
 
   /// \brief Set of run-time checks required to establish independence of
   /// otherwise may-aliasing pointers in the loop.
   SmallVector<PointerCheck, 4> Checks;
+
+  /// \brief Set of pointers with unknown bounds.
+  SmallVector<Value *, 4> PtrsWithUnknownBounds;
 };
 
 /// \brief Drive the analysis of memory accesses in the loop
 ///
 /// This class is responsible for analyzing the memory accesses of a loop.  It
 /// collects the accesses and then its main helper the AccessAnalysis class
 /// finds and categorizes the dependences in buildDependenceSets.
 ///

lib/Analysis/LoopAccessAnalysis.cpp

for (auto A : AS) {
           // Each access has its own dependence set.
           DepId = RunningDepId++;
 
         RtCheck.insert(TheLoop, Ptr, IsWrite, DepId, ASId, StridesMap, PSE);
 
         DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
       } else {
         DEBUG(dbgs() << "LAA: Can't find bounds for ptr:" << *Ptr << '\n');
+        RtCheck.pointerWithUnknownBounds(Ptr);
         CanDoRT = false;
       }
     }
 
     // If we have at least two writes or one write and a read then we need to
     // check them.  But there is no need to checks if there is only one
     // dependence set for this alias set.
     //
bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
   if (NeedRTCheck && CanDoRT)
     RtCheck.generateChecks(DepCands, IsDepCheckNeeded);
 
   DEBUG(dbgs() << "LAA: We need to do " << RtCheck.getNumberOfChecks()
                << " pointer comparisons.\n");
 
   RtCheck.Need = NeedRTCheck;
 
-  bool CanDoRTIfNeeded = !NeedRTCheck || CanDoRT;
-  if (!CanDoRTIfNeeded)
-    RtCheck.reset();
-  return CanDoRTIfNeeded;
+  return !NeedRTCheck || CanDoRT;
 }
 
 void AccessAnalysis::processMemAccesses() {
   // We process the set twice: first we process read-write pointers, last we
   // process read-only pointers. This allows us to skip dependence tests for
   // read-only pointers.
 
   DEBUG(dbgs() << "LAA: Processing memory accesses...\n");
void LoopAccessInfo::analyzeLoop(AliasAnalysis *AA, LoopInfo *LI,
   // Holds the Load and Store instructions.
   SmallVector<LoadInst *, 16> Loads;
   SmallVector<StoreInst *, 16> Stores;
 
   // Holds all the different accesses in the loop.
   unsigned NumReads = 0;
   unsigned NumReadWrites = 0;
 
-  PtrRtChecking->Pointers.clear();
-  PtrRtChecking->Need = false;
+  PtrRtChecking->reset();
 
   const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel();
 
   // For each block.
   for (BasicBlock *BB : TheLoop->blocks()) {
     // Scan the BB and collect legal loads and stores.
     for (Instruction &I : *BB) {
       // If this is a load, save it. If this instruction can read from memory