[NFC] [DA] Refactoring getIndexExpressionsFromGEP

[bmahjour]

Summary

This patch moves the getIndexExpressionsFromGEP function from polly into ScalarEvolution so that both polly and DependenceAnalysis can use it for the purpose of subscript delinearization when the array sizes are not parametric.

[Meinersbur]

llvm/lib/Analysis/ScalarEvolution.cpp

11452

[style] It might be useful to return true here and false at the bail-outs. Otherwise, the return here is redundant.

llvm/include/llvm/Analysis/ScalarEvolution.h

void collectParametricTerms(const SCEV *Expr,
                               SmallVectorImpl<const SCEV *> &Terms);
 
   /// Return in Subscripts the access functions for each dimension in Sizes
   /// (third step of delinearization).
   void computeAccessFunctions(const SCEV *Expr,
                               SmallVectorImpl<const SCEV *> &Subscripts,
                               SmallVectorImpl<const SCEV *> &Sizes);
 
+  /// Gathers the individual index expressions from a GEP instruction.
+  ///
+  /// This function optimistically assumes the GEP references into a fixed size
+  /// array. If this is actually true, this function returns a list of array
+  /// subscript expressions as SCEV as well as a list of integers describing
+  /// the size of the individual array dimensions. Both lists have either equal
+  /// length or the size list is one element shorter in case there is no known
+  /// size available for the outermost array dimension.
+  void getIndexExpressionsFromGEP(const GetElementPtrInst *GEP,
+                                  SmallVectorImpl<const SCEV *> &Subscripts,
+                                  SmallVectorImpl<int> &Sizes);
+
   /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the
   /// subscripts and sizes of an array access.
   ///
   /// The delinearization is a 3 step process: the first two steps compute the
   /// sizes of each subscript and the third step computes the access functions
   /// for the delinearized array:
   ///
   /// 1. Find the terms in the step functions

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;
 }
 
-static void
-getIndexExpressionsFromGEP(const GetElementPtrInst *GEP,
-                           SmallVectorImpl<const SCEV *> &Subscripts,
-                           SmallVectorImpl<int> &Sizes, ScalarEvolution &SE) {
-  assert(GEP && "getIndexExpressionsFromGEP called with a null GEP");
-  Type *Ty = GEP->getPointerOperandType();
-  bool DroppedFirstDim = false;
-  for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
-    const SCEV *Expr = SE.getSCEV(GEP->getOperand(i));
-    if (i == 1) {
-      if (auto *PtrTy = dyn_cast<PointerType>(Ty)) {
-        Ty = PtrTy->getElementType();
-      } else if (auto *ArrayTy = dyn_cast<ArrayType>(Ty)) {
-        Ty = ArrayTy->getElementType();
-      } else {
-        Subscripts.clear();
-        Sizes.clear();
-        break;
-      }
-      if (auto *Const = dyn_cast<SCEVConstant>(Expr))
-        if (Const->getValue()->isZero()) {
-          DroppedFirstDim = true;
-          continue;
-        }
-      Subscripts.push_back(Expr);
-      continue;
-    }
-
-    auto *ArrayTy = dyn_cast<ArrayType>(Ty);
-    if (!ArrayTy) {
-      Subscripts.clear();
-      Sizes.clear();
-      break;
-    }
-
-    Subscripts.push_back(Expr);
-    if (!(DroppedFirstDim && i == 2))
-      Sizes.push_back(ArrayTy->getNumElements());
-
-    Ty = ArrayTy->getElementType();
-  }
-  return;
-}
-
 bool DependenceInfo::tryDelinearizeFixedSize(
     Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn,
     const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts,
     SmallVectorImpl<const SCEV *> &DstSubscripts) {
 
   if (!DisableDelinearizationChecks)
     return false;
 
   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)
     return false;
 
   SmallVector<int, 4> SrcSizes, DstSizes;
-  getIndexExpressionsFromGEP(SrcGEP, SrcSubscripts, SrcSizes, *SE);
-  getIndexExpressionsFromGEP(DstGEP, DstSubscripts, DstSizes, *SE);
+  SE->getIndexExpressionsFromGEP(SrcGEP, SrcSubscripts, SrcSizes);
+  SE->getIndexExpressionsFromGEP(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() ||
       !std::equal(SrcSizes.begin(), SrcSizes.end(), DstSizes.begin())) {
     SrcSubscripts.clear();
     DstSubscripts.clear();
     return false;

llvm/lib/Analysis/ScalarEvolution.cpp

LLVM_DEBUG({
 
     dbgs() << "\nArrayRef";
     for (const SCEV *S : Subscripts)
       dbgs() << "[" << *S << "]";
     dbgs() << "\n";
   });
 }
 
+void ScalarEvolution::getIndexExpressionsFromGEP(
+    const GetElementPtrInst *GEP, SmallVectorImpl<const SCEV *> &Subscripts,
+    SmallVectorImpl<int> &Sizes) {
+  assert(GEP && "getIndexExpressionsFromGEP called with a null GEP");
+  Type *Ty = GEP->getPointerOperandType();
+  bool DroppedFirstDim = false;
+  for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
+    const SCEV *Expr = getSCEV(GEP->getOperand(i));
+    if (i == 1) {
+      if (auto *PtrTy = dyn_cast<PointerType>(Ty)) {
+        Ty = PtrTy->getElementType();
+      } else if (auto *ArrayTy = dyn_cast<ArrayType>(Ty)) {
+        Ty = ArrayTy->getElementType();
+      } else {
+        Subscripts.clear();
+        Sizes.clear();
+        break;
+      }
+      if (auto *Const = dyn_cast<SCEVConstant>(Expr))
+        if (Const->getValue()->isZero()) {
+          DroppedFirstDim = true;
+          continue;
+        }
+      Subscripts.push_back(Expr);
+      continue;
+    }
+
+    auto *ArrayTy = dyn_cast<ArrayType>(Ty);
+    if (!ArrayTy) {
+      Subscripts.clear();
+      Sizes.clear();
+      break;
+    }
+
+    Subscripts.push_back(Expr);
+    if (!(DroppedFirstDim && i == 2))
+      Sizes.push_back(ArrayTy->getNumElements());
+
+    Ty = ArrayTy->getElementType();
+  }
+  return;
+}
+
 //===----------------------------------------------------------------------===//
 //                   SCEVCallbackVH Class Implementation
 //===----------------------------------------------------------------------===//
 
 void ScalarEvolution::SCEVCallbackVH::deleted() {
   assert(SE && "SCEVCallbackVH called with a null ScalarEvolution!");
   if (PHINode *PN = dyn_cast<PHINode>(getValPtr()))
     SE->ConstantEvolutionLoopExitValue.erase(PN);

polly/include/polly/Support/ScopHelper.h

 ///
 /// For normal instructions, this is the instruction's parent block. For PHI
 /// nodes, this is the incoming block of that use, because this is where the
 /// operand must be defined (i.e. its definition dominates this block).
 /// Non-instructions do not use operands at a specific point such that in this
 /// case this function returns nullptr.
 llvm::BasicBlock *getUseBlock(const llvm::Use &U);
 
-/// Derive the individual index expressions from a GEP instruction.
-///
-/// This function optimistically assumes the GEP references into a fixed size
-/// array. If this is actually true, this function returns a list of array
-/// subscript expressions as SCEV as well as a list of integers describing
-/// the size of the individual array dimensions. Both lists have either equal
-/// length or the size list is one element shorter in case there is no known
-/// size available for the outermost array dimension.
-///
-/// @param GEP The GetElementPtr instruction to analyze.
-///
-/// @return A tuple with the subscript expressions and the dimension sizes.
-std::tuple<std::vector<const llvm::SCEV *>, std::vector<int>>
-getIndexExpressionsFromGEP(llvm::GetElementPtrInst *GEP,
-                           llvm::ScalarEvolution &SE);
-
 // If the loop is nonaffine/boxed, return the first non-boxed surrounding loop
 // for Polly. If the loop is affine, return the loop itself.
 //
 // @param L             Pointer to the Loop object to analyze.
 // @param LI            Reference to the LoopInfo.
 // @param BoxedLoops    Set of Boxed Loops we get from the SCoP.
 llvm::Loop *getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI,
                                     const BoxedLoopsSetTy &BoxedLoops);

polly/lib/Analysis/ScopBuilder.cpp

if (SrcTy->isPointerTy() && DstTy->isPointerTy() &&
             DL.getTypeAllocSize(DstTy->getPointerElementType()))
       Address = Src;
   }
 
   auto *GEP = dyn_cast<GetElementPtrInst>(Address);
   if (!GEP)
     return false;
 
-  std::vector<const SCEV *> Subscripts;
-  std::vector<int> Sizes;
-  std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, SE);
+  SmallVector<const SCEV *, 4> Subscripts;
+  SmallVector<int, 4> Sizes;
+  SE.getIndexExpressionsFromGEP(GEP, Subscripts, Sizes);
   auto *BasePtr = GEP->getOperand(0);
 
   if (auto *BasePtrCast = dyn_cast<BitCastInst>(BasePtr))
     BasePtr = BasePtrCast->getOperand(0);
 
   // Check for identical base pointers to ensure that we do not miss index
   // offsets that have been added before this GEP is applied.
   if (BasePtr != BasePointer->getValue())

polly/lib/Support/ScopHelper.cpp

if (!UI)
     return nullptr;
 
   if (PHINode *PHI = dyn_cast<PHINode>(UI))
     return PHI->getIncomingBlock(U);
 
   return UI->getParent();
 }
 
-std::tuple<std::vector<const SCEV *>, std::vector<int>>
-polly::getIndexExpressionsFromGEP(GetElementPtrInst *GEP, ScalarEvolution &SE) {
-  std::vector<const SCEV *> Subscripts;
-  std::vector<int> Sizes;
-
-  Type *Ty = GEP->getPointerOperandType();
-
-  bool DroppedFirstDim = false;
-
-  for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
-
-    const SCEV *Expr = SE.getSCEV(GEP->getOperand(i));
-
-    if (i == 1) {
-      if (auto *PtrTy = dyn_cast<PointerType>(Ty)) {
-        Ty = PtrTy->getElementType();
-      } else if (auto *ArrayTy = dyn_cast<ArrayType>(Ty)) {
-        Ty = ArrayTy->getElementType();
-      } else {
-        Subscripts.clear();
-        Sizes.clear();
-        break;
-      }
-      if (auto *Const = dyn_cast<SCEVConstant>(Expr))
-        if (Const->getValue()->isZero()) {
-          DroppedFirstDim = true;
-          continue;
-        }
-      Subscripts.push_back(Expr);
-      continue;
-    }
-
-    auto *ArrayTy = dyn_cast<ArrayType>(Ty);
-    if (!ArrayTy) {
-      Subscripts.clear();
-      Sizes.clear();
-      break;
-    }
-
-    Subscripts.push_back(Expr);
-    if (!(DroppedFirstDim && i == 2))
-      Sizes.push_back(ArrayTy->getNumElements());
-
-    Ty = ArrayTy->getElementType();
-  }
-
-  return std::make_tuple(Subscripts, Sizes);
-}
-
 llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI,
                                            const BoxedLoopsSetTy &BoxedLoops) {
   while (BoxedLoops.count(L))
     L = L->getParentLoop();
   return L;
 }
 
 llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::BasicBlock *BB,