[Refactor] Do not carry DominatorTree along with a Scop.

[etherzhhb]

Summary

Make Scop become more portable such that we can use it in a CallGraphSCC pass.
The first step is to drop the analyses that are only used during Scop construction.
This patch drop DominatorTree from Scop.

[etherzhhb]

Pushed

include/polly/ScopInfo.h

public:
   /// non read only and read only accesses for each alias group.
   using MinMaxVectorPairVectorTy = SmallVector<MinMaxVectorPairTy, 4>;
 
 private:
   Scop(const Scop &) = delete;
   const Scop &operator=(const Scop &) = delete;
 
   LoopInfo &LI;
-  DominatorTree &DT;
   ScalarEvolution *SE;
 
   /// The underlying Region.
   Region &R;
 
   // Access function of bbs.
   AccFuncMapType &AccFuncMap;
 
private:
   /// @brief Mapping from invariant loads to the representing invariant load of
   ///        their equivalence class.
   ValueToValueMap InvEquivClassVMap;
 
   /// @brief List of invariant accesses.
   InvariantEquivClassesTy InvariantEquivClasses;
 
   /// @brief Scop constructor; invoked from ScopInfo::buildScop.
-  Scop(Region &R, AccFuncMapType &AccFuncMap, ScalarEvolution &SE,
-       DominatorTree &DT, LoopInfo &LI, isl_ctx *ctx, unsigned MaxLoopDepth);
+  Scop(Region &R, AccFuncMapType &AccFuncMap, ScalarEvolution &SE, LoopInfo &LI,
+       isl_ctx *ctx, unsigned MaxLoopDepth);
 
   /// @brief Initialize this ScopInfo .
-  void init(AliasAnalysis &AA, AssumptionCache &AC, ScopDetection &SD);
+  void init(AliasAnalysis &AA, AssumptionCache &AC, ScopDetection &SD,
+            DominatorTree &DT);
 
   /// @brief Add loop carried constraints to the header block of the loop @p L.
   ///
   /// @param L  The loop to process.
   void addLoopBoundsToHeaderDomain(Loop *L);
 
   /// @brief Compute the branching constraints for each basic block in @p R.
   ///
   /// @param R  The region we currently build branching conditions for.
   /// @param SD The ScopDetection analysis for the current function.
-  void buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD);
+  /// @param DT The DominatorTree for the current function.
+  void buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD,
+                                         DominatorTree &DT);
 
   /// @brief Propagate the domain constraints through the region @p R.
   ///
   /// @param R  The region we currently build branching conditions for.
   /// @param SD The ScopDetection analysis for the current function.
-  void propagateDomainConstraints(Region *R, ScopDetection &SD);
+  /// @param DT The DominatorTree for the current function.
+  void propagateDomainConstraints(Region *R, ScopDetection &SD,
+                                  DominatorTree &DT);
 
   /// @brief Remove domains of error blocks/regions (and blocks dominated by
   ///        them).
   ///
   /// @param SD The ScopDetection analysis for the current function.
-  void removeErrorBlockDomains(ScopDetection &SD);
+  /// @param DT The DominatorTree for the current function.
+  void removeErrorBlockDomains(ScopDetection &SD, DominatorTree &DT);
 
   /// @brief Compute the domain for each basic block in @p R.
   ///
   /// @param R  The region we currently traverse.
   /// @param SD The ScopDetection analysis for the current function.
-  void buildDomains(Region *R, ScopDetection &SD);
+  /// @param DT The DominatorTree for the current function.
+  void buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT);
 
   /// @brief Check if a region part should be represented in the SCoP or not.
   ///
   /// If @p RN does not contain any useful calculation or is only reachable
   /// via error blocks we do not model it in the polyhedral representation.
   ///
   /// @param RN The region part to check.
+  /// @param DT The DominatorTree for the current function.
   ///
   /// @return True if the part should be ignored, otherwise false.
-  bool isIgnored(RegionNode *RN);
+  bool isIgnored(RegionNode *RN, DominatorTree &DT);
 
   /// @brief Add parameter constraints to @p C that imply a non-empty domain.
   __isl_give isl_set *addNonEmptyDomainConstraints(__isl_take isl_set *C) const;
 
   /// @brief Simplify the SCoP representation
   ///
   /// At the moment we perform the following simplifications:
   ///   - removal of no-op statements
   /// @param RemoveIgnoredStmts If true, also removed ignored statments.
   /// @see isIgnored()
-  void simplifySCoP(bool RemoveIgnoredStmts);
+  void simplifySCoP(bool RemoveIgnoredStmts, DominatorTree &DT);
 
   /// @brief Create equivalence classes for required invariant accesses.
   ///
   /// These classes will consolidate multiple required invariant loads from the
   /// same address in order to keep the number of dimensions in the SCoP
   /// description small. For each such class equivalence class only one
   /// representing element, hence one required invariant load, will be chosen
   /// and modeled as parameter. The method
private:
 
   /// @brief Build the Context of the Scop.
   void buildContext();
 
   /// @brief Build the BoundaryContext based on the wrapping of expressions.
   void buildBoundaryContext();
 
   /// @brief Add user provided parameter constraints to context (source code).
-  void addUserAssumptions(AssumptionCache &AC);
+  void addUserAssumptions(AssumptionCache &AC, DominatorTree &DT);
 
   /// @brief Add user provided parameter constraints to context (command line).
   void addUserContext();
 
   /// @brief Add the bounds of the parameters to the context.
   void addParameterBounds();
 
   /// @brief Simplify the assumed and boundary context.

lib/Analysis/ScopInfo.cpp

void Scop::buildBoundaryContext() {
 
   isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_ABORT);
   isl_ctx_reset_operations(getIslCtx());
   isl_ctx_set_max_operations(getIslCtx(), MaxOpsOld);
   BoundaryContext = isl_set_gist_params(BoundaryContext, getContext());
   trackAssumption(WRAPPING, BoundaryContext, DebugLoc());
 }
 
-void Scop::addUserAssumptions(AssumptionCache &AC) {
+void Scop::addUserAssumptions(AssumptionCache &AC, DominatorTree &DT) {
   auto *R = &getRegion();
   auto &F = *R->getEntry()->getParent();
   for (auto &Assumption : AC.assumptions()) {
     auto *CI = dyn_cast_or_null<CallInst>(Assumption);
     if (!CI || CI->getNumArgOperands() != 1)
       continue;
     if (!DT.dominates(CI->getParent(), R->getEntry()))
       continue;
isl_set *Scop::getDomainConditions(ScopStmt *Stmt) {
   return getDomainConditions(BB);
 }
 
 isl_set *Scop::getDomainConditions(BasicBlock *BB) {
   assert(DomainMap.count(BB) && "Requested BB did not have a domain");
   return isl_set_copy(DomainMap[BB]);
 }
 
-void Scop::removeErrorBlockDomains(ScopDetection &SD) {
-  auto removeDomains = [this](BasicBlock *Start) {
+void Scop::removeErrorBlockDomains(ScopDetection &SD, DominatorTree &DT) {
+  auto removeDomains = [this, &DT](BasicBlock *Start) {
     auto BBNode = DT.getNode(Start);
     for (auto ErrorChild : depth_first(BBNode)) {
       auto ErrorChildBlock = ErrorChild->getBlock();
       auto CurrentDomain = DomainMap[ErrorChildBlock];
       auto Empty = isl_set_empty(isl_set_get_space(CurrentDomain));
       DomainMap[ErrorChildBlock] = Empty;
       isl_set_free(CurrentDomain);
     }
if (containsErrorBlock(SubRegion->getNode(), getRegion(), LI, DT))
       removeDomains(SubRegion->getEntry());
   }
 
   for (auto BB : R.blocks())
     if (isErrorBlock(*BB, R, LI, DT))
       removeDomains(BB);
 }
 
-void Scop::buildDomains(Region *R, ScopDetection &SD) {
+void Scop::buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT) {
 
   bool IsOnlyNonAffineRegion = SD.isNonAffineSubRegion(R, R);
   auto *EntryBB = R->getEntry();
   auto *L = IsOnlyNonAffineRegion ? nullptr : LI.getLoopFor(EntryBB);
   int LD = getRelativeLoopDepth(L);
   auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx(), 0, LD + 1));
 
   while (LD-- >= 0) {
     S = addDomainDimId(S, LD + 1, L);
     L = L->getParentLoop();
   }
 
   DomainMap[EntryBB] = S;
 
   if (IsOnlyNonAffineRegion)
     return;
 
-  buildDomainsWithBranchConstraints(R, SD);
-  propagateDomainConstraints(R, SD);
+  buildDomainsWithBranchConstraints(R, SD, DT);
+  propagateDomainConstraints(R, SD, DT);
 
   // Error blocks and blocks dominated by them have been assumed to never be
   // executed. Representing them in the Scop does not add any value. In fact,
   // it is likely to cause issues during construction of the ScopStmts. The
   // contents of error blocks have not been verfied to be expressible and
   // will cause problems when building up a ScopStmt for them.
   // Furthermore, basic blocks dominated by error blocks may reference
   // instructions in the error block which, if the error block is not modeled,
   // can themselves not be constructed properly.
-  removeErrorBlockDomains(SD);
+  removeErrorBlockDomains(SD, DT);
 }
 
-void Scop::buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD) {
+void Scop::buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD,
+                                             DominatorTree &DT) {
   auto &BoxedLoops = *SD.getBoxedLoops(&getRegion());
 
   // To create the domain for each block in R we iterate over all blocks and
   // subregions in R and propagate the conditions under which the current region
   // element is executed. To this end we iterate in reverse post order over R as
   // it ensures that we first visit all predecessors of a region node (either a
   // basic block or a subregion) before we visit the region node itself.
   // Initially, only the domain for the SCoP region entry block is set and from
   // there we propagate the current domain to all successors, however we add the
   // condition that the successor is actually executed next.
   // As we are only interested in non-loop carried constraints here we can
   // simply skip loop back edges.
 
   ReversePostOrderTraversal<Region *> RTraversal(R);
   for (auto *RN : RTraversal) {
 
     // Recurse for affine subregions but go on for basic blocks and non-affine
     // subregions.
     if (RN->isSubRegion()) {
       Region *SubRegion = RN->getNodeAs<Region>();
       if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
-        buildDomainsWithBranchConstraints(SubRegion, SD);
+        buildDomainsWithBranchConstraints(SubRegion, SD, DT);
         continue;
       }
     }
 
     if (containsErrorBlock(RN, getRegion(), LI, DT))
       HasErrorBlock = true;
 
     BasicBlock *BB = getRegionNodeBasicBlock(RN);
if (DIt != DomainMap.end())
     return isl_set_copy(DIt->getSecond());
 
   Region *R = RI.getRegionFor(BB);
   while (R->getEntry() == BB)
     R = R->getParent();
   return getDomainForBlock(R->getEntry(), DomainMap, RI);
 }
 
-void Scop::propagateDomainConstraints(Region *R, ScopDetection &SD) {
+void Scop::propagateDomainConstraints(Region *R, ScopDetection &SD,
+                                      DominatorTree &DT) {
   // Iterate over the region R and propagate the domain constrains from the
   // predecessors to the current node. In contrast to the
   // buildDomainsWithBranchConstraints function, this one will pull the domain
   // information from the predecessors instead of pushing it to the successors.
   // Additionally, we assume the domains to be already present in the domain
   // map here. However, we iterate again in reverse post order so we know all
   // predecessors have been visited before a block or non-affine subregion is
   // visited.
 
   // The set of boxed loops (loops in non-affine subregions) for this SCoP.
   auto &BoxedLoops = *SD.getBoxedLoops(&getRegion());
 
   ReversePostOrderTraversal<Region *> RTraversal(R);
   for (auto *RN : RTraversal) {
 
     // Recurse for affine subregions but go on for basic blocks and non-affine
     // subregions.
     if (RN->isSubRegion()) {
       Region *SubRegion = RN->getNodeAs<Region>();
       if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
-        propagateDomainConstraints(SubRegion, SD);
+        propagateDomainConstraints(SubRegion, SD, DT);
         continue;
       }
     }
 
     // Get the domain for the current block and check if it was initialized or
     // not. The only way it was not is if this block is only reachable via error
     // blocks, thus will not be executed under the assumptions we make. Such
     // blocks have to be skipped as their predecessors might not have domains
static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI,
 
   assert(MinLD >= 1 && "Minimal loop depth should be at least one");
   assert(MaxLD >= MinLD &&
          "Maximal loop depth was smaller than mininaml loop depth?");
   return MaxLD - MinLD + 1;
 }
 
 Scop::Scop(Region &R, AccFuncMapType &AccFuncMap,
-           ScalarEvolution &ScalarEvolution, DominatorTree &DT, LoopInfo &LI,
-           isl_ctx *Context, unsigned MaxLoopDepth)
-    : LI(LI), DT(DT), SE(&ScalarEvolution), R(R), AccFuncMap(AccFuncMap),
+           ScalarEvolution &ScalarEvolution, LoopInfo &LI, isl_ctx *Context,
+           unsigned MaxLoopDepth)
+    : LI(LI), SE(&ScalarEvolution), R(R), AccFuncMap(AccFuncMap),
       IsOptimized(false), HasSingleExitEdge(R.getExitingBlock()),
       HasErrorBlock(false), MaxLoopDepth(MaxLoopDepth), IslCtx(Context),
       Context(nullptr), Affinator(this), AssumedContext(nullptr),
       BoundaryContext(nullptr), Schedule(nullptr) {
   buildContext();
 }
 
-void Scop::init(AliasAnalysis &AA, AssumptionCache &AC, ScopDetection &SD) {
-  addUserAssumptions(AC);
+void Scop::init(AliasAnalysis &AA, AssumptionCache &AC, ScopDetection &SD,
+                DominatorTree &DT) {
+  addUserAssumptions(AC, DT);
   buildInvariantEquivalenceClasses(SD);
 
-  buildDomains(&R, SD);
+  buildDomains(&R, SD, DT);
 
   // Remove empty and ignored statements.
   // Exit early in case there are no executable statements left in this scop.
-  simplifySCoP(true);
+  simplifySCoP(true, DT);
   if (Stmts.empty())
     return;
 
   // The ScopStmts now have enough information to initialize themselves.
   for (ScopStmt &Stmt : Stmts)
     Stmt.init(SD);
 
   buildSchedule(SD);
 
   if (isl_set_is_empty(AssumedContext))
     return;
 
   updateAccessDimensionality();
   realignParams();
   addParameterBounds();
   addUserContext();
   buildBoundaryContext();
   simplifyContexts();
   buildAliasChecks(AA);
 
   hoistInvariantLoads(SD);
-  simplifySCoP(false);
+  simplifySCoP(false, DT);
 }
 
 Scop::~Scop() {
   isl_set_free(Context);
   isl_set_free(AssumedContext);
   isl_set_free(BoundaryContext);
   isl_schedule_free(Schedule);
 

 }
 
 void Scop::updateAccessDimensionality() {
   for (auto &Stmt : *this)
     for (auto &Access : Stmt)
       Access->updateDimensionality();
 }
 
-void Scop::simplifySCoP(bool RemoveIgnoredStmts) {
+void Scop::simplifySCoP(bool RemoveIgnoredStmts, DominatorTree &DT) {
   for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) {
     ScopStmt &Stmt = *StmtIt;
     RegionNode *RN = Stmt.isRegionStmt()
                          ? Stmt.getRegion()->getNode()
                          : getRegion().getBBNode(Stmt.getBasicBlock());
 
     bool RemoveStmt = StmtIt->isEmpty();
     if (!RemoveStmt)
       RemoveStmt = isl_set_is_empty(DomainMap[getRegionNodeBasicBlock(RN)]);
     if (!RemoveStmt)
-      RemoveStmt = (RemoveIgnoredStmts && isIgnored(RN));
+      RemoveStmt = (RemoveIgnoredStmts && isIgnored(RN, DT));
 
     // Remove read only statements only after invariant loop hoisting.
     if (!RemoveStmt && !RemoveIgnoredStmts) {
       bool OnlyRead = true;
       for (MemoryAccess *MA : Stmt) {
         if (MA->isRead())
           continue;
 
if (isl_union_set_is_empty(NewStmtDomain)) {
       Stmt.restrictDomain(isl_set_from_union_set(NewStmtDomain));
   }
   isl_union_set_free(Domain);
   return Changed;
 }
 
 ScalarEvolution *Scop::getSE() const { return SE; }
 
-bool Scop::isIgnored(RegionNode *RN) {
+bool Scop::isIgnored(RegionNode *RN, DominatorTree &DT) {
   BasicBlock *BB = getRegionNodeBasicBlock(RN);
   ScopStmt *Stmt = getStmtForRegionNode(RN);
 
   // If there is no stmt, then it already has been removed.
   if (!Stmt)
     return true;
 
   // Check if there are accesses contained.

 void ScopInfo::addPHIReadAccess(PHINode *PHI) {
   addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
                   ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                   ScopArrayInfo::MK_PHI);
 }
 
 void ScopInfo::buildScop(Region &R, AssumptionCache &AC) {
   unsigned MaxLoopDepth = getMaxLoopDepthInRegion(R, *LI, *SD);
-  scop = new Scop(R, AccFuncMap, *SE, *DT, *LI, ctx, MaxLoopDepth);
+  scop = new Scop(R, AccFuncMap, *SE, *LI, ctx, MaxLoopDepth);
 
   buildStmts(R, R);
   buildAccessFunctions(R, 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);
 
-  scop->init(*AA, AC, *SD);
+  scop->init(*AA, AC, *SD, *DT);
 }
 
 void ScopInfo::print(raw_ostream &OS, const Module *) const {
   if (!scop) {
     OS << "Invalid Scop!\n";
     return;
   }