[Delinearization] Refactoring of fixed-size array delinearization

[congzhe]

Summary

This is a follow-up patch to D122857 where we added delinearization of fixed-size arrays to loop cache analysis, which resulted in some duplicate code ("tryDelinearizeFixedSize()") in LoopCacheCost.cpp and DependenceAnalysis.cpp. Refactoring is done in this patch.

This patch refactors IndexedReference::tryDelinearizeFixedSize() out as tryDelinearizeFixedSizeImpl() and moves it to Delinearization.cpp, such that clients can reuse llvm::tryDelinearizeFixedSizeImpl() wherever they would like to delinearize fixed-size arrays. Currently it has two users, i.e., DependenceAnalysis.cpp and LoopCacheCost.cpp.

In DependenceAnalysis.cpp, tryDelinearizeFixedSize(Src, Dst, SrcAccessFn, DstAccessFn, SrcSubscripts, DstSubscripts) now calls tryDelinearizeFixedSizeImpl(SE, Src, SrcAccessFn, SrcSubscripts, SrcSizes) and tryDelinearizeFixedSizeImpl(SE, Dst, DstAccessFn, DstSubscripts, DstSizes) to delinearize Src and Dst respectively, and does some clean-up work afterwards that is needed in dependence analysis. Similarly in LoopCacheCost.cpp, tryDelinearizeFixedSize() calls tryDelinearizeFixedSizeImpl() and does some clean-up work afterwards that is needed in loop cache analysis.

I'm looking forward to comments on this patch :)

[bmahjour]

llvm/lib/Analysis/DependenceAnalysis.cpp

3369–3373

[nit] '\p' is used to refer to function parameters when commenting on a function.
[nit] /// is not meant for comments inside a function.
[nit] SrcPtr -> Src
[nit] Src is mentioned but not Dst
[suggestion] assert that size of src and dst subscripts arrays are the same.
[comment] it would be better to assert that Src and Dst are GEP before casting, and SrcGEP and DstGEP should be typed as GEP instead of 'Value'. What do we gain by assuming that the Src and Dst are GEPs anyway?

llvm/lib/Analysis/LoopCacheAnalysis.cpp

358

[nit] use // for function internal comments

394

[nit] use // for function internal comments

[congzhe]

Thanks for the comments, I've updated this patch accordingly.

llvm/lib/Analysis/DependenceAnalysis.cpp

3369–3373

Thanks for the comments!

Size of src and dst subscripts arrays are supposed to be the same if we reach this point. And I totally agree that it is worth adding an assertion to check that. I've added the assert accordingly.

You are right that Src and Dst do not need to be cast to GEPs (we did not gain anything). Now I've removed the cast.

[Meinersbur]

llvm/include/llvm/Analysis/Delinearization.h

128–129

"can be reused wherever needed with the llvm namespace" does not need documentation.

128–131

Could you explain the relation between Inst and AccessFn? One of them seems redundant because of the SrcBasePtr != SrcBase->getValue() check, i.e. one can be derived from the other.

llvm/lib/Analysis/Delinearization.cpp

528

Cannot assume that getPointerBase returns a SCEVUnknown.

SrcBase is only used down below, consider moving it there.

540

Subscripts.clear() should not be necessary, the caller is supposed to throw it away if returning false. We actually know that it is empty because getIndexExpressionsFromGEP has an assert for it. At least it is consistent that Sizes is not cleared too.

549

See above

llvm/lib/Analysis/DependenceAnalysis.cpp

3338

[nit]

[congzhe]

Addressed reviewers' comments.

llvm/include/llvm/Analysis/Delinearization.h

128–129

Thanks, I've updated it accordingly.

128–131

Thanks, I've added some explanations about Inst and AccessFn here in the comment. Generally speaking AccessFn can indeed be derived from Inst, i.e., AccessFn = SE.getSCEVAtScope(getPointerOperand(Inst), LI->getLoopFor(Inst->getParent()));. It is not immediately doable to remove the arugment AccessFn though, because we would need LoopInfo *LI to be passed here in order to derive AccessFn from Inst, which brings another aspect of complexity. So I left the function declaration as it is for now.

llvm/lib/Analysis/Delinearization.cpp

528

Thanks, I've used SrcBase = dyn_cast<SCEVUnknown>(getPointerBase) instead, and made it bail out if SrcBase is NULL.

540

Thanks for the comment! I tried to remove Subscripts.clear(); but it failed a few lit tests:

LLVM :: Analysis/DDG/basic-loopnest.ll
LLVM :: Analysis/DependenceAnalysis/Coupled.ll
LLVM :: Analysis/DependenceAnalysis/DADelin.ll
LLVM :: Analysis/DependenceAnalysis/SimpleSIVNoValidityCheck.ll
LLVM :: Analysis/LoopCacheAnalysis/PowerPC/compute-cost.ll
LLVM :: Analysis/LoopCacheAnalysis/PowerPC/loads-store.ll
LLVM :: Analysis/LoopCacheAnalysis/PowerPC/matmul.ll
LLVM :: Analysis/LoopCacheAnalysis/PowerPC/single-store.ll
LLVM :: Analysis/LoopCacheAnalysis/PowerPC/stencil.ll

IMHO we may need to keep Subscripts.clear(). Different from Sizes which indeed gets cleared/thrown away by the caller (e.g., DependenceInfo::tryDelinearizeFixedSize()), Subscripts does not get cleared by tryDelinearizeFixedSize() (if it has only one element), and will be passed into DependenceInfo::tryDelinearizeParametricSize() and causes incorrect result.

There might be ways to further modify other places which would enable us to remove this Subscripts.clear();, but I thought we might keep it and avoid too much modification?

llvm/lib/Analysis/DependenceAnalysis.cpp

3338

Thanks, fixed it.

[congzhe]

@Meinersbur Hi Michael, I'm wondering if you have further comments? I'd appreciate it if you could let me know your thoughts on my most recent update.

[Meinersbur]

LGTM

llvm/lib/Analysis/Delinearization.cpp

540

It's something to be improved. I don't like the inconsistent handling when invalid. Either only return false and the caller is expected to handle this, or we unconditionally clear the array at the beginning so we know there is no junk data from a previous call.

Could you add a TODO?

[congzhe]

Updated to reflect Michael's final minor comment, will land it shortly.

llvm/include/llvm/Analysis/Delinearization.h

 /// either equal length or the size list is one element shorter in case there
 /// is no known size available for the outermost array dimension. Returns true
 /// if successful and false otherwise.
 bool getIndexExpressionsFromGEP(ScalarEvolution &SE,
                                 const GetElementPtrInst *GEP,
                                 SmallVectorImpl<const SCEV *> &Subscripts,
                                 SmallVectorImpl<int> &Sizes);
 
+/// Implementation of fixed size array delinearization. Try to delinearize
+/// access function for a fixed size multi-dimensional array, by deriving
+/// subscripts from GEP instructions. Returns true upon success and false
+/// otherwise. \p Inst is the load/store instruction whose pointer operand is
+/// the one we want to delinearize. \p AccessFn is its corresponding SCEV
+/// expression w.r.t. the surrounding loop.
+bool tryDelinearizeFixedSizeImpl(ScalarEvolution *SE, Instruction *Inst,
+                                 const SCEV *AccessFn,
+                                 SmallVectorImpl<const SCEV *> &Subscripts,
+                                 SmallVectorImpl<int> &Sizes);
+
 struct DelinearizationPrinterPass
     : public PassInfoMixin<DelinearizationPrinterPass> {
   explicit DelinearizationPrinterPass(raw_ostream &OS);
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
 private:
   raw_ostream &OS;
 };
 } // namespace llvm
 
 #endif // LLVM_ANALYSIS_DELINEARIZATION_H

llvm/include/llvm/Analysis/DependenceAnalysis.h

private:
     void updateDirection(Dependence::DVEntry &Level,
                          const Constraint &CurConstraint) const;
 
     /// Given a linear access function, tries to recover subscripts
     /// for each dimension of the array element access.
     bool tryDelinearize(Instruction *Src, Instruction *Dst,
                         SmallVectorImpl<Subscript> &Pair);
 
-    /// Tries to delinearize access function for a fixed size multi-dimensional
-    /// array, by deriving subscripts from GEP instructions. Returns true upon
-    /// success and false otherwise.
+    /// Tries to delinearize \p Src and \p Dst access functions for a fixed size
+    /// multi-dimensional array. Calls tryDelinearizeFixedSizeImpl() to
+    /// delinearize \p Src and \p Dst separately,
     bool tryDelinearizeFixedSize(Instruction *Src, Instruction *Dst,
                                  const SCEV *SrcAccessFn,
                                  const SCEV *DstAccessFn,
                                  SmallVectorImpl<const SCEV *> &SrcSubscripts,
                                  SmallVectorImpl<const SCEV *> &DstSubscripts);
 
     /// Tries to delinearize access function for a multi-dimensional array with
     /// symbolic runtime sizes.

llvm/include/llvm/Analysis/LoopCacheAnalysis.h

public:
   ///       subscripts is zero
   ///   - or otherwise equal to 'TripCount'.
   CacheCostTy computeRefCost(const Loop &L, unsigned CLS) const;
 
 private:
   /// Attempt to delinearize the indexed reference.
   bool delinearize(const LoopInfo &LI);
 
-  bool tryDelinearizeFixedSize(ScalarEvolution *SE, Instruction *Src,
-                               const SCEV *SrcAccessFn,
-                               SmallVectorImpl<const SCEV *> &SrcSubscripts);
+  /// Attempt to delinearize \p AccessFn for fixed-size arrays.
+  bool tryDelinearizeFixedSize(const SCEV *AccessFn,
+                               SmallVectorImpl<const SCEV *> &Subscripts);
 
   /// Return true if the index reference is invariant with respect to loop \p L.
   bool isLoopInvariant(const Loop &L) const;
 
   /// Return true if the indexed reference is 'consecutive' in loop \p L.
   /// An indexed reference is 'consecutive' if the only coefficient that uses
   /// the loop induction variable is the rightmost one, and the access stride is
   /// smaller than the cache line size \p CLS.

llvm/lib/Analysis/Delinearization.cpp

for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
     if (!(DroppedFirstDim && i == 2))
       Sizes.push_back(ArrayTy->getNumElements());
 
     Ty = ArrayTy->getElementType();
   }
   return !Subscripts.empty();
 }
 
+bool llvm::tryDelinearizeFixedSizeImpl(
+    ScalarEvolution *SE, Instruction *Inst, const SCEV *AccessFn,
+    SmallVectorImpl<const SCEV *> &Subscripts, SmallVectorImpl<int> &Sizes) {
+  Value *SrcPtr = getLoadStorePointerOperand(Inst);
+
+  // Check the simple case where the array dimensions are fixed size.
+  auto *SrcGEP = dyn_cast<GetElementPtrInst>(SrcPtr);
+  if (!SrcGEP)
+    return false;
+
+  getIndexExpressionsFromGEP(*SE, SrcGEP, Subscripts, Sizes);
+
+  // Check that the two size arrays are non-empty and equal in length and
+  // value.
+  // TODO: it would be better to let the caller to clear Subscripts, similar
+  // to how we handle Sizes.
+  if (Sizes.empty() || Subscripts.size() <= 1) {
+    Subscripts.clear();
+    return false;
+  }
+
+  // Check that for identical base pointers we do not miss index offsets
+  // that have been added before this GEP is applied.
+  Value *SrcBasePtr = SrcGEP->getOperand(0)->stripPointerCasts();
+  const SCEVUnknown *SrcBase =
+      dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
+  if (!SrcBase || SrcBasePtr != SrcBase->getValue()) {
+    Subscripts.clear();
+    return false;
+  }
+
+  assert(Subscripts.size() == Sizes.size() + 1 &&
+         "Expected equal number of entries in the list of size and "
+         "subscript.");
+
+  return true;
+}
+
 namespace {
 
 class Delinearization : public FunctionPass {
   Delinearization(const Delinearization &); // do not implement
 protected:
   Function *F;
   LoopInfo *LI;
   ScalarEvolution *SE;

llvm/lib/Analysis/DependenceAnalysis.cpp

for (int I = 0; I < Size; ++I) {
     Pair[I].Src = SrcSubscripts[I];
     Pair[I].Dst = DstSubscripts[I];
     unifySubscriptType(&Pair[I]);
   }
 
   return true;
 }
 
+/// Try to delinearize \p SrcAccessFn and \p DstAccessFn if the underlying
+/// arrays accessed are fixed-size arrays. Return true if delinearization was
+/// successful.
 bool DependenceInfo::tryDelinearizeFixedSize(
     Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn,
     const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts,
     SmallVectorImpl<const SCEV *> &DstSubscripts) {
-
-  Value *SrcPtr = getLoadStorePointerOperand(Src);
-  Value *DstPtr = getLoadStorePointerOperand(Dst);
   const SCEVUnknown *SrcBase =
       dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));
   const SCEVUnknown *DstBase =
       dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));
   assert(SrcBase && DstBase && SrcBase == DstBase &&
          "expected src and dst scev unknowns to be equal");
 
-  // Check the simple case where the array dimensions are fixed size.
-  auto *SrcGEP = dyn_cast<GetElementPtrInst>(SrcPtr);
-  auto *DstGEP = dyn_cast<GetElementPtrInst>(DstPtr);
-  if (!SrcGEP || !DstGEP)
+  SmallVector<int, 4> SrcSizes;
+  SmallVector<int, 4> DstSizes;
+  if (!tryDelinearizeFixedSizeImpl(SE, Src, SrcAccessFn, SrcSubscripts,
+                                   SrcSizes) ||
+      !tryDelinearizeFixedSizeImpl(SE, Dst, DstAccessFn, DstSubscripts,
+                                   DstSizes))
     return false;
 
-  SmallVector<int, 4> SrcSizes, DstSizes;
-  getIndexExpressionsFromGEP(*SE, SrcGEP, SrcSubscripts, SrcSizes);
-  getIndexExpressionsFromGEP(*SE, DstGEP, DstSubscripts, DstSizes);
-
   // Check that the two size arrays are non-empty and equal in length and
   // value.
-  if (SrcSizes.empty() || SrcSubscripts.size() <= 1 ||
-      SrcSizes.size() != DstSizes.size() ||
+  if (SrcSizes.size() != DstSizes.size() ||
       !std::equal(SrcSizes.begin(), SrcSizes.end(), DstSizes.begin())) {
     SrcSubscripts.clear();
     DstSubscripts.clear();
     return false;
   }
 
-  Value *SrcBasePtr = SrcGEP->getOperand(0)->stripPointerCasts();
-  Value *DstBasePtr = DstGEP->getOperand(0)->stripPointerCasts();
-
-  // Check that for identical base pointers we do not miss index offsets
-  // that have been added before this GEP is applied.
-  if (SrcBasePtr != SrcBase->getValue() || DstBasePtr != DstBase->getValue()) {
-    SrcSubscripts.clear();
-    DstSubscripts.clear();
-    return false;
-  }
-
   assert(SrcSubscripts.size() == DstSubscripts.size() &&
-         SrcSubscripts.size() == SrcSizes.size() + 1 &&
-         "Expected equal number of entries in the list of sizes and "
-         "subscripts.");
+         "Expected equal number of entries in the list of SrcSubscripts and "
+         "DstSubscripts.");
+
+  Value *SrcPtr = getLoadStorePointerOperand(Src);
+  Value *DstPtr = getLoadStorePointerOperand(Dst);
 
   // In general we cannot safely assume that the subscripts recovered from GEPs
   // are in the range of values defined for their corresponding array
   // dimensions. For example some C language usage/interpretation make it
   // impossible to verify this at compile-time. As such we can only delinearize
   // iff the subscripts are positive and are less than the range of the
   // dimension.
   if (!DisableDelinearizationChecks) {
if (!AllIndiciesInRange(SrcSizes, SrcSubscripts, SrcPtr) ||
         !AllIndiciesInRange(DstSizes, DstSubscripts, DstPtr)) {
       SrcSubscripts.clear();
       DstSubscripts.clear();
       return false;
     }
   }
   LLVM_DEBUG({
     dbgs() << "Delinearized subscripts of fixed-size array\n"
-           << "SrcGEP:" << *SrcGEP << "\n"
-           << "DstGEP:" << *DstGEP << "\n";
+           << "SrcGEP:" << *SrcPtr << "\n"
+           << "DstGEP:" << *DstPtr << "\n";
   });
   return true;
 }
 
 bool DependenceInfo::tryDelinearizeParametricSize(
     Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn,
     const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts,
     SmallVectorImpl<const SCEV *> &DstSubscripts) {

llvm/lib/Analysis/LoopCacheAnalysis.cpp

CacheCostTy IndexedReference::computeRefCost(const Loop &L,
   LLVM_DEBUG(dbgs().indent(4)
              << "RefCost is not a constant! Setting to RefCost=InvalidCost "
                 "(invalid value).\n");
 
   return CacheCost::InvalidCost;
 }
 
 bool IndexedReference::tryDelinearizeFixedSize(
-    ScalarEvolution *SE, Instruction *Src, const SCEV *SrcAccessFn,
-    SmallVectorImpl<const SCEV *> &SrcSubscripts) {
-  Value *SrcPtr = getLoadStorePointerOperand(Src);
-  const SCEVUnknown *SrcBase =
-      dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));
-
-  // Check the simple case where the array dimensions are fixed size.
-  auto *SrcGEP = dyn_cast<GetElementPtrInst>(SrcPtr);
-  if (!SrcGEP)
-    return false;
-
-  SmallVector<int, 4> SrcSizes;
-  getIndexExpressionsFromGEP(*SE, SrcGEP, SrcSubscripts, SrcSizes);
-
-  // Check that the two size arrays are non-empty and equal in length and
-  // value.
-  if (SrcSizes.empty() || SrcSubscripts.size() <= 1) {
-    SrcSubscripts.clear();
-    return false;
-  }
-
-  Value *SrcBasePtr = SrcGEP->getOperand(0)->stripPointerCasts();
-
-  // Check that for identical base pointers we do not miss index offsets
-  // that have been added before this GEP is applied.
-  if (SrcBasePtr != SrcBase->getValue()) {
-    SrcSubscripts.clear();
+    const SCEV *AccessFn, SmallVectorImpl<const SCEV *> &Subscripts) {
+  SmallVector<int, 4> ArraySizes;
+  if (!tryDelinearizeFixedSizeImpl(&SE, &StoreOrLoadInst, AccessFn, Subscripts,
+                                   ArraySizes))
     return false;
-  }
-
-  assert(SrcSubscripts.size() == SrcSizes.size() + 1 &&
-         "Expected equal number of entries in the list of size and "
-         "subscript.");
 
+  // Populate Sizes with scev expressions to be used in calculations later.
   for (auto Idx : seq<unsigned>(1, Subscripts.size()))
-    Sizes.push_back(SE->getConstant(Subscripts[Idx]->getType(), SrcSizes[Idx - 1]));
+    Sizes.push_back(
+        SE.getConstant(Subscripts[Idx]->getType(), ArraySizes[Idx - 1]));
 
   LLVM_DEBUG({
     dbgs() << "Delinearized subscripts of fixed-size array\n"
-           << "SrcGEP:" << *SrcGEP << "\n";
+           << "GEP:" << *getLoadStorePointerOperand(&StoreOrLoadInst)
+           << "\n";
   });
   return true;
 }
 
 bool IndexedReference::delinearize(const LoopInfo &LI) {
   assert(Subscripts.empty() && "Subscripts should be empty");
   assert(Sizes.empty() && "Sizes should be empty");
   assert(!IsValid && "Should be called once from the constructor");
if (BasePointer == nullptr) {
       LLVM_DEBUG(
           dbgs().indent(2)
           << "ERROR: failed to delinearize, can't identify base pointer\n");
       return false;
     }
 
     bool IsFixedSize = false;
     // Try to delinearize fixed-size arrays.
-    if (tryDelinearizeFixedSize(&SE, &StoreOrLoadInst, AccessFn, Subscripts)) {
+    if (tryDelinearizeFixedSize(AccessFn, Subscripts)) {
       IsFixedSize = true;
-      /// The last element of \p Sizes is the element size.
+      // The last element of Sizes is the element size.
       Sizes.push_back(ElemSize);
       LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()
                                   << "', AccessFn: " << *AccessFn << "\n");
     }
 
     AccessFn = SE.getMinusSCEV(AccessFn, BasePointer);
 
     // Try to delinearize parametric-size arrays.