[Refactor] Eliminate the global variable "InsnToMemAcc".

[etherzhhb]

Summary

Eliminate the global variable "InsnToMemAcc" to make Scop/ScopInfo become more protable, such that we can safely use them in a CallGraphSCC pass.

[jdoerfert]

Comments are inlined.

include/polly/ScopDetection.h

225

Why mutable? If you try to modify it but the "const" state of almost all methods in the ScopDetection is blocking you, put the InstToMemAcc into the DetectionContext, that is what we always did and what makes it clear it belongs to this detection context.

523

In methods like "getBoxedLoops" you can easily see how you can access the "correct" InstToMemAcc once it is moved to the DetectionContext.

lib/Analysis/ScopDetection.cpp

505

Thank you sooo much! Finally, somebody removed that thing...

[etherzhhb]

include/polly/ScopDetection.h

225

Ok

523

ok

[jdoerfert]

LGTM.

include/polly/ScopDetection.h

private:
   /// @brief Remove cached results for @p R.
   void removeCachedResults(const Region &R);
 
   /// @brief Remove cached results for the children of @p R recursively.
   ///
   /// @returns The number of regions erased regions.
   unsigned removeCachedResultsRecursively(const Region &R);
 
+  /// @brief Map to memory access description for the corresponding LLVM
+  ///        instructions.
+  mutable MapInsnToMemAcc InsnToMemAcc;
+
   /// @brief Add the region @p AR as over approximated sub-region in @p Context.
   ///
   /// @param AR      The non-affine subregion.
   /// @param Context The current detection context.
   ///
   /// @returns True if the subregion can be over approximated, false otherwise.
   bool addOverApproximatedRegion(Region *AR, DetectionContext &Context) const;
 
public:
 
   /// @brief Get a message why a region is invalid
   ///
   /// @param R The region for which we get the error message
   ///
   /// @return The error or "" if no error appeared.
   std::string regionIsInvalidBecause(const Region *R) const;
 
+  /// @brief Get the instruction to memory access mapping of the current
+  ///        function
+  MapInsnToMemAcc &getInsnToMemAccMap() const { return InsnToMemAcc; }
+
   /// @name Maximum Region In Scops Iterators
   ///
   /// These iterators iterator over all maximum region in Scops of this
   /// function.
   //@{
   typedef RegionSet::iterator iterator;
   typedef RegionSet::const_iterator const_iterator;
 

include/polly/ScopInfo.h

class ScopInfo : public RegionPass {
   /// @brief Try to build a multi-dimensional parameteric sized MemoryAccess
   ///        from the Load/Store instruction.
   ///
   /// @param Inst       The Load/Store instruction that access the memory
   /// @param L          The parent loop of the instruction
   /// @param R          The region on which to build the data access dictionary.
   /// @param BoxedLoops The set of loops that are overapproximated in @p R.
   /// @param ScopRIL    The required invariant loads equivalence classes.
+  /// @param InsnToMemAcc The Instruction to MemoryAccess mapping
   /// @returns True if the access could be built, False otherwise.
   bool
   buildAccessMultiDimParam(MemAccInst Inst, Loop *L, Region *R,
                            const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
-                           const InvariantLoadsSetTy &ScopRIL);
+                           const InvariantLoadsSetTy &ScopRIL,
+                           const MapInsnToMemAcc &InsnToMemAcc);
 
   /// @brief Build a single-dimensional parameteric sized MemoryAccess
   ///        from the Load/Store instruction.
   ///
   /// @param Inst       The Load/Store instruction that access the memory
   /// @param L          The parent loop of the instruction
   /// @param R          The region on which to build the data access dictionary.
   /// @param BoxedLoops The set of loops that are overapproximated in @p R.
   /// @param ScopRIL    The required invariant loads equivalence classes.
   void buildAccessSingleDim(MemAccInst Inst, Loop *L, Region *R,
                             const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
                             const InvariantLoadsSetTy &ScopRIL);
 
   /// @brief Build an instance of MemoryAccess from the Load/Store instruction.
   ///
   /// @param Inst       The Load/Store instruction that access the memory
   /// @param L          The parent loop of the instruction
   /// @param R          The region on which to build the data access dictionary.
   /// @param BoxedLoops The set of loops that are overapproximated in @p R.
   /// @param ScopRIL    The required invariant loads equivalence classes.
+  /// @param InsnToMemAcc The Instruction to MemoryAccess mapping.
   void buildMemoryAccess(MemAccInst Inst, Loop *L, Region *R,
                          const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
-                         const InvariantLoadsSetTy &ScopRIL);
+                         const InvariantLoadsSetTy &ScopRIL,
+                         const MapInsnToMemAcc &InsnToMemAcc);
 
   /// @brief Analyze and extract the cross-BB scalar dependences (or,
   ///        dataflow dependencies) of an instruction.
   ///
   /// @param Inst    The instruction to be analyzed.
   void buildScalarDependences(Instruction *Inst);
 
   /// @brief Search for uses of the llvm::Value defined by @p Inst that are not
class ScopInfo : public RegionPass {
   /// @param R                  The SCoP region
   /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
   /// @param IsExitBlock        Flag to indicate that @p PHI is in the exit BB.
   void buildPHIAccesses(PHINode *PHI, Region &R, Region *NonAffineSubRegion,
                         bool IsExitBlock = false);
 
   /// @brief Build the access functions for the subregion @p SR.
   ///
-  /// @param R  The SCoP region.
-  /// @param SR A subregion of @p R.
-  void buildAccessFunctions(Region &R, Region &SR);
+  /// @param R            The SCoP region.
+  /// @param SR           A subregion of @p R.
+  /// @param InsnToMemAcc The Instruction to MemoryAccess mapping.
+  void buildAccessFunctions(Region &R, Region &SR,
+                            const MapInsnToMemAcc &InsnToMemAcc);
 
   /// @brief Create ScopStmt for all BBs and non-affine subregions of @p SR.
   ///
   /// @param R  The SCoP region.
   /// @param SR A subregion of @p R.
   ///
   /// Some of the statments might be optimized away later when they do not
   /// access any memory and thus have no effect.
   void buildStmts(Region &R, Region &SR);
 
   /// @brief Build the access functions for the basic block @p BB
   ///
   /// @param R                  The SCoP region.
   /// @param BB                 A basic block in @p R.
+  /// @param InsnToMemAcc       The Instruction to MemoryAccess mapping.
   /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
   /// @param IsExitBlock        Flag to indicate that @p BB is in the exit BB.
   void buildAccessFunctions(Region &R, BasicBlock &BB,
+                            const MapInsnToMemAcc &InsnToMemAcc,
                             Region *NonAffineSubRegion = nullptr,
                             bool IsExitBlock = false);
 
   /// @brief Create a new MemoryAccess object and add it to #AccFuncMap.
   ///
   /// @param BB          The block where the access takes place.
   /// @param Inst        The instruction doing the access. It is not necessarily
   ///                    inside @p BB.

lib/Analysis/ScopDetection.cpp

bool ScopDetection::isInvariant(const Value &Val, const Region &Reg) const {
 
   for (const Use &Operand : I->operands())
     if (!isInvariant(*Operand, Reg))
       return false;
 
   return true;
 }
 
-MapInsnToMemAcc InsnToMemAcc;
-
 /// @brief Remove smax of smax(0, size) expressions from a SCEV expression and
 /// register the '...' components.
 ///
 /// Array access expressions as they are generated by gfortran contain smax(0,
 /// size) expressions that confuse the 'normal' delinearization algorithm.
 /// However, if we extract such expressions before the normal delinearization
 /// takes place they can actually help to identify array size expressions in
 /// fortran accesses. For the subsequently following delinearization the smax(0,

lib/Analysis/ScopInfo.cpp

if (!R->contains(UseParent) ||
          R->getExitingBlock())) {
       // At least one escaping use found.
       ensureValueWrite(Inst);
       break;
     }
   }
 }
 
-extern MapInsnToMemAcc InsnToMemAcc;
-
 bool ScopInfo::buildAccessMultiDimFixed(
     MemAccInst Inst, Loop *L, Region *R,
     const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
     const InvariantLoadsSetTy &ScopRIL) {
   Value *Val = Inst.getValueOperand();
   Type *SizeType = Val->getType();
   unsigned ElementSize = DL->getTypeAllocSize(SizeType);
   Value *Address = Inst.getPointerOperand();
if (isa<GetElementPtrInst>(Address) || isa<BitCastInst>(Address)) {
     }
   }
   return false;
 }
 
 bool ScopInfo::buildAccessMultiDimParam(
     MemAccInst Inst, Loop *L, Region *R,
     const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
-    const InvariantLoadsSetTy &ScopRIL) {
+    const InvariantLoadsSetTy &ScopRIL, const MapInsnToMemAcc &InsnToMemAcc) {
   Value *Address = Inst.getPointerOperand();
   Value *Val = Inst.getValueOperand();
   Type *SizeType = Val->getType();
   unsigned ElementSize = DL->getTypeAllocSize(SizeType);
   enum MemoryAccess::AccessType Type =
       Inst.isLoad() ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 
   const SCEV *AccessFunction = SE->getSCEVAtScope(Address, L);
void ScopInfo::buildAccessSingleDim(
 
   addArrayAccess(Inst, Type, BasePointer->getValue(), ElementSize, IsAffine,
                  {AccessFunction}, {}, Val);
 }
 
 void ScopInfo::buildMemoryAccess(
     MemAccInst Inst, Loop *L, Region *R,
     const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
-    const InvariantLoadsSetTy &ScopRIL) {
+    const InvariantLoadsSetTy &ScopRIL, const MapInsnToMemAcc &InsnToMemAcc) {
 
   if (buildAccessMultiDimFixed(Inst, L, R, BoxedLoops, ScopRIL))
     return;
 
-  if (buildAccessMultiDimParam(Inst, L, R, BoxedLoops, ScopRIL))
+  if (buildAccessMultiDimParam(Inst, L, R, BoxedLoops, ScopRIL, InsnToMemAcc))
     return;
 
   buildAccessSingleDim(Inst, L, R, BoxedLoops, ScopRIL);
 }
 
-void ScopInfo::buildAccessFunctions(Region &R, Region &SR) {
+void ScopInfo::buildAccessFunctions(Region &R, Region &SR,
+                                    const MapInsnToMemAcc &InsnToMemAcc) {
 
   if (SD->isNonAffineSubRegion(&SR, &R)) {
     for (BasicBlock *BB : SR.blocks())
-      buildAccessFunctions(R, *BB, &SR);
+      buildAccessFunctions(R, *BB, InsnToMemAcc, &SR);
     return;
   }
 
   for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
     if (I->isSubRegion())
-      buildAccessFunctions(R, *I->getNodeAs<Region>());
+      buildAccessFunctions(R, *I->getNodeAs<Region>(), InsnToMemAcc);
     else
-      buildAccessFunctions(R, *I->getNodeAs<BasicBlock>());
+      buildAccessFunctions(R, *I->getNodeAs<BasicBlock>(), InsnToMemAcc);
 }
 
 void ScopInfo::buildStmts(Region &R, Region &SR) {
 
   if (SD->isNonAffineSubRegion(&SR, &R)) {
     scop->addScopStmt(nullptr, &SR);
     return;
   }
 
   for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
     if (I->isSubRegion())
       buildStmts(R, *I->getNodeAs<Region>());
     else
       scop->addScopStmt(I->getNodeAs<BasicBlock>(), nullptr);
 }
 
 void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
+                                    const MapInsnToMemAcc &InsnToMemAcc,
                                     Region *NonAffineSubRegion,
                                     bool IsExitBlock) {
   // We do not build access functions for error blocks, as they may contain
   // instructions we can not model.
   if (isErrorBlock(BB, R, *LI, *DT) && !IsExitBlock)
     return;
 
   Loop *L = LI->getLoopFor(&BB);
for (Instruction &Inst : BB) {
     if (!PHI && IsExitBlock)
       break;
 
     // TODO: At this point we only know that elements of ScopRIL have to be
     //       invariant and will be hoisted for the SCoP to be processed. Though,
     //       there might be other invariant accesses that will be hoisted and
     //       that would allow to make a non-affine access affine.
     if (auto MemInst = MemAccInst::dyn_cast(Inst))
-      buildMemoryAccess(MemInst, L, &R, BoxedLoops, ScopRIL);
+      buildMemoryAccess(MemInst, L, &R, BoxedLoops, ScopRIL, InsnToMemAcc);
 
     if (isIgnoredIntrinsic(&Inst))
       continue;
 
     if (!PHI)
       buildScalarDependences(&Inst);
     if (!IsExitBlock)
       buildEscapingDependences(&Inst);
addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
                   ScopArrayInfo::MK_PHI);
 }
 
 void ScopInfo::buildScop(Region &R, AssumptionCache &AC) {
   unsigned MaxLoopDepth = getMaxLoopDepthInRegion(R, *LI, *SD);
   scop = new Scop(R, *SE, ctx, MaxLoopDepth);
 
   buildStmts(R, R);
-  buildAccessFunctions(R, R);
+  buildAccessFunctions(R, R, SD->getInsnToMemAccMap());
 
   // In case the region does not have an exiting block we will later (during
   // code generation) split the exit block. This will move potential PHI nodes
   // from the current exit block into the new region exiting block. Hence, PHI
   // nodes that are at this point not part of the region will be.
   // To handle these PHI nodes later we will now model their operands as scalar
   // accesses. Note that we do not model anything in the exit block if we have
   // an exiting block in the region, as there will not be any splitting later.
   if (!R.getExitingBlock())
-    buildAccessFunctions(R, *R.getExit(), nullptr, /* IsExitBlock */ true);
+    buildAccessFunctions(R, *R.getExit(), SD->getInsnToMemAccMap(), nullptr,
+                         /* IsExitBlock */ true);
 
   scop->init(*AA, AC, *SD, *DT, *LI);
 }
 
 void ScopInfo::print(raw_ostream &OS, const Module *) const {
   if (!scop) {
     OS << "Invalid Scop!\n";
     return;