[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 ↗

(On Diff #47901)

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 ↗

(On Diff #47901)

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 ↗

(On Diff #47901)

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

[etherzhhb]

include/polly/ScopDetection.h

225 ↗

(On Diff #47901)

Ok

523 ↗

(On Diff #47901)

ok

[jdoerfert]

LGTM.

polly/trunk/include/polly/ScopDetection.h

struct DetectionContext {
     NonAffineSubRegionSetTy NonAffineSubRegionSet;
 
     /// @brief The set of loops contained in non-affine regions.
     BoxedLoopsSetTy BoxedLoopsSet;
 
     /// @brief Loads that need to be invariant during execution.
     InvariantLoadsSetTy RequiredILS;
 
+    /// @brief Map to memory access description for the corresponding LLVM
+    ///        instructions.
+    MapInsnToMemAcc InsnToMemAcc;
+
     /// @brief Initialize a DetectionContext from scratch.
     DetectionContext(Region &R, AliasAnalysis &AA, bool Verify)
         : CurRegion(R), AST(AA), Verifying(Verify), Log(&R), hasLoads(false),
           hasStores(false) {}
 
     /// @brief Initialize a DetectionContext with the data from @p DC.
     DetectionContext(const DetectionContext &&DC)
         : CurRegion(DC.CurRegion), AST(DC.AST.getAliasAnalysis()),
public:
   bool isMaxRegionInScop(const Region &R, bool Verify = true) const;
 
   /// @brief Return the detection context for @p R, nullptr if @p R was invalid.
   const DetectionContext *getDetectionContext(const Region *R) const;
 
   /// @brief Return the set of loops in non-affine subregions for @p R.
   const BoxedLoopsSetTy *getBoxedLoops(const Region *R) const;
 
+  /// @brief Get the instruction to memory access mapping of the current
+  ///        function for @p R.
+  const MapInsnToMemAcc *getInsnToMemAccMap(const Region *R) const;
+
   /// @brief Return the set of required invariant loads for @p R.
   const InvariantLoadsSetTy *getRequiredInvariantLoads(const Region *R) const;
 
   /// @brief Return true if @p SubR is a non-affine subregion in @p ScopR.
   bool isNonAffineSubRegion(const Region *SubR, const Region *ScopR) const;
 
   /// @brief Get a message why a region is invalid
   ///

polly/trunk/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.

polly/trunk/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,
if (IsNonAffine) {
         invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, Pair.second,
                                        Insn, BaseValue);
       if (!KeepGoing && !AllowNonAffine)
         return false;
     }
   }
 
   if (!BasePtrHasNonAffine)
-    InsnToMemAcc.insert(TempMemoryAccesses.begin(), TempMemoryAccesses.end());
+    Context.InsnToMemAcc.insert(TempMemoryAccesses.begin(),
+                                TempMemoryAccesses.end());
 
   return true;
 }
 
 bool ScopDetection::hasBaseAffineAccesses(
     DetectionContext &Context, const SCEVUnknown *BasePointer) const {
   auto Shape = std::shared_ptr<ArrayShape>(new ArrayShape(BasePointer));
 

 
 const ScopDetection::BoxedLoopsSetTy *
 ScopDetection::getBoxedLoops(const Region *R) const {
   const DetectionContext *DC = getDetectionContext(R);
   assert(DC && "ScopR is no valid region!");
   return &DC->BoxedLoopsSet;
 }
 
+const MapInsnToMemAcc *
+ScopDetection::getInsnToMemAccMap(const Region *R) const {
+  const DetectionContext *DC = getDetectionContext(R);
+  assert(DC && "ScopR is no valid region!");
+  return &DC->InsnToMemAcc;
+}
+
 const InvariantLoadsSetTy *
 ScopDetection::getRequiredInvariantLoads(const Region *R) const {
   const DetectionContext *DC = getDetectionContext(R);
   assert(DC && "ScopR is no valid region!");
   return &DC->RequiredILS;
 }
 
 void polly::ScopDetection::verifyRegion(const Region &R) const {
for (const Region *R : ValidRegions)
     OS << "Valid Region for Scop: " << R->getNameStr() << '\n';
 
   OS << "\n";
 }
 
 void ScopDetection::releaseMemory() {
   RejectLogs.clear();
   ValidRegions.clear();
-  InsnToMemAcc.clear();
   DetectionContextMap.clear();
 
   // Do not clear the invalid function set.
 }
 
 char ScopDetection::ID = 0;
 
 Pass *polly::createScopDetectionPass() { return new ScopDetection(); }

polly/trunk/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.reset(new Scop(R, *SE, ctx, MaxLoopDepth));
 
   buildStmts(R, R);
-  buildAccessFunctions(R, R);
+  buildAccessFunctions(R, R, *SD->getInsnToMemAccMap(&R));
 
   // 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(&R), 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;