[ZoneAlgo] Use getDefToTarget in makeValInst. NFC.

Move the optimized getDefToTarget() from ForwardOpTree to ZoneAlgo such
that it can be used by makeValInst.

This reduces the compile time of GrTestUtils of the aosp buildbot from
2m46s to 21s, which should fix the timeout issue.

Differential Revision: https://reviews.llvm.org/D48579

3 files changed, 119 insertions, 115 deletions

diff --git a/polly/include/polly/ZoneAlgo.h b/polly/include/polly/ZoneAlgo.h
index 5f009c8befc..c4f5debd021 100644
--- a/polly/include/polly/ZoneAlgo.h
+++ b/polly/include/polly/ZoneAlgo.h
@@ -154,6 +154,9 @@ protected:
   /// Cache for computePerPHI(const ScopArrayInfo *)
   llvm::SmallDenseMap<llvm::PHINode *, isl::union_map> PerPHIMaps;
 
+  /// A cache for getDefToTarget().
+  llvm::DenseMap<std::pair<ScopStmt *, ScopStmt *>, isl::map> DefToTargetCache;
+
   /// Prepare the object before computing the zones of @p S.
   ///
   /// @param PassName Name of the pass using this analysis.
@@ -192,6 +195,15 @@ private:
 
   void addArrayWriteAccess(MemoryAccess *MA);
 
+  /// For an llvm::Value defined in @p DefStmt, compute the RAW dependency for a
+  /// use in every instance of @p UseStmt.
+  ///
+  /// @param UseStmt Statement a scalar is used in.
+  /// @param DefStmt Statement a scalar is defined in.
+  ///
+  /// @return { DomainUse[] -> DomainDef[] }
+  isl::map computeUseToDefFlowDependency(ScopStmt *UseStmt, ScopStmt *DefStmt);
+
 protected:
   isl::union_set makeEmptyUnionSet() const;
 
@@ -236,6 +248,28 @@ protected:
   /// The domain of the result is as narrow as possible.
   isl::map getAccessRelationFor(MemoryAccess *MA) const;
 
+  /// Get a domain translation map from a (scalar) definition to the statement
+  /// where the definition is being moved to.
+  ///
+  /// @p TargetStmt can also be seen at an llvm::Use of an llvm::Value in
+  /// @p DefStmt. In addition, we allow transitive uses:
+  ///
+  /// DefStmt -> MiddleStmt -> TargetStmt
+  ///
+  /// where an operand tree of instructions in DefStmt and MiddleStmt are to be
+  /// moved to TargetStmt. To be generally correct, we also need to know all the
+  /// intermediate statements. However, we make use of the fact that
+  /// ForwardOpTree currently does not support a move from a loop body across
+  /// its header such that only the first definition and the target statement
+  /// are relevant.
+  ///
+  /// @param DefStmt    Statement from where a definition might be moved from.
+  /// @param TargetStmt Statement where the definition is potentially being
+  ///                   moved to (should contain a use of that definition).
+  ///
+  /// @return { DomainDef[] -> DomainTarget[] }
+  isl::map getDefToTarget(ScopStmt *DefStmt, ScopStmt *TargetStmt);
+
   /// Get the reaching definition of a scalar defined in @p Stmt.
   ///
   /// Note that this does not depend on the llvm::Instruction, only on the
diff --git a/polly/lib/Transform/ForwardOpTree.cpp b/polly/lib/Transform/ForwardOpTree.cpp
index 00d611e5e04..17985ecf11f 100644
--- a/polly/lib/Transform/ForwardOpTree.cpp
+++ b/polly/lib/Transform/ForwardOpTree.cpp
@@ -181,9 +181,6 @@ private:
   /// original load. { ValInst[] -> ValInst[] }
   isl::union_map Translator;
 
-  /// A cache for getDefToTarget().
-  DenseMap<std::pair<ScopStmt *, ScopStmt *>, isl::map> DefToTargetCache;
-
   /// Get list of array elements that do contain the same ValInst[] at Domain[].
   ///
   /// @param ValInst { Domain[] -> ValInst[] }
@@ -374,108 +371,6 @@ public:
     return Access;
   }
 
-  /// For an llvm::Value defined in @p DefStmt, compute the RAW dependency for a
-  /// use in every instance of @p UseStmt.
-  ///
-  /// @param UseStmt Statement a scalar is used in.
-  /// @param DefStmt Statement a scalar is defined in.
-  ///
-  /// @return { DomainUse[] -> DomainDef[] }
-  isl::map computeUseToDefFlowDependency(ScopStmt *UseStmt, ScopStmt *DefStmt) {
-    // { DomainUse[] -> Scatter[] }
-    isl::map UseScatter = getScatterFor(UseStmt);
-
-    // { Zone[] -> DomainDef[] }
-    isl::map ReachDefZone = getScalarReachingDefinition(DefStmt);
-
-    // { Scatter[] -> DomainDef[] }
-    isl::map ReachDefTimepoints =
-        convertZoneToTimepoints(ReachDefZone, isl::dim::in, false, true);
-
-    // { DomainUse[] -> DomainDef[] }
-    return UseScatter.apply_range(ReachDefTimepoints);
-  }
-
-  /// Is @p InnerLoop nested inside @p OuterLoop?
-  static bool isInsideLoop(Loop *OuterLoop, Loop *InnerLoop) {
-    // If OuterLoop is nullptr, we cannot call its contains() method. In this
-    // case OuterLoop represents the 'top level' and therefore contains all
-    // loop.
-    return !OuterLoop || OuterLoop->contains(InnerLoop);
-  }
-
-  /// Get a domain translation map from a (scalar) definition to the statement
-  /// where the definition is being moved to.
-  ///
-  /// @p TargetStmt can also be seen an llvm::Use of an llvm::Value in
-  /// @p DefStmt. In addition, we allow transitive uses:
-  ///
-  /// DefStmt -> MiddleStmt -> TargetStmt
-  ///
-  /// where an operand tree of instructions in DefStmt and MiddleStmt are to be
-  /// moved to TargetStmt. To be generally correct, we also need to know all the
-  /// intermediate statements. However, we make use of the fact that we
-  /// currently do not support a move from a loop body across its header such
-  /// that only the first definition and the target statement are relevant.
-  ///
-  /// @param DefStmt    Statement from where a definition might be moved from.
-  /// @param TargetStmt Statement where the definition is potentially being
-  ///                   moved to (should contain a use of that definition).
-  ///
-  /// @return  { DomainDef[] -> DomainTarget[] }
-  isl::map getDefToTarget(ScopStmt *DefStmt, ScopStmt *TargetStmt) {
-    // No translation required if the definition is already at the target.
-    if (TargetStmt == DefStmt)
-      return isl::map::identity(
-          getDomainFor(TargetStmt).get_space().map_from_set());
-
-    isl::map &Result = DefToTargetCache[std::make_pair(TargetStmt, DefStmt)];
-
-    // This is a shortcut in case the schedule is still the original and
-    // TargetStmt is in the same or nested inside DefStmt's loop. With the
-    // additional assumption that operand trees do not cross DefStmt's loop
-    // header, then TargetStmt's instance shared coordinated are the same as
-    // DefStmt's coordinated. All TargetStmt instances with this prefix share
-    // the same DefStmt instance.
-    // Model:
-    //
-    //   for (int i < 0; i < N; i+=1) {
-    // DefStmt:
-    //    D = ...;
-    //    for (int j < 0; j < N; j+=1) {
-    // TargetStmt:
-    //      use(D);
-    //    }
-    //  }
-    //
-    // Here, the value used in TargetStmt is defined in the corresponding
-    // DefStmt, i.e.
-    //
-    //   { DefStmt[i] -> TargetStmt[i,j] }
-    //
-    // In practice, this should cover the majority of cases.
-    if (S->isOriginalSchedule() &&
-        isInsideLoop(DefStmt->getSurroundingLoop(),
-                     TargetStmt->getSurroundingLoop())) {
-      isl::set DefDomain = getDomainFor(DefStmt);
-      isl::set TargetDomain = getDomainFor(TargetStmt);
-      assert(DefDomain.dim(isl::dim::set) <= TargetDomain.dim(isl::dim::set));
-
-      Result = isl::map::from_domain_and_range(DefDomain, TargetDomain);
-      for (unsigned i = 0, DefDims = DefDomain.dim(isl::dim::set); i < DefDims;
-           i += 1)
-        Result = Result.equate(isl::dim::in, i, isl::dim::out, i);
-    }
-
-    if (!Result) {
-      // { DomainDef[] -> DomainTarget[] }
-      Result = computeUseToDefFlowDependency(TargetStmt, DefStmt).reverse();
-      simplify(Result);
-    }
-
-    return Result;
-  }
-
   /// Forward a load by reading from an array element that contains the same
   /// value. Typically the location it was loaded from.
   ///
diff --git a/polly/lib/Transform/ZoneAlgo.cpp b/polly/lib/Transform/ZoneAlgo.cpp
index a34fcb37754..ce4d21753c0 100644
--- a/polly/lib/Transform/ZoneAlgo.cpp
+++ b/polly/lib/Transform/ZoneAlgo.cpp
@@ -315,6 +315,13 @@ static bool onlySameValueWrites(ScopStmt *Stmt) {
   return true;
 }
 
+/// Is @p InnerLoop nested inside @p OuterLoop?
+static bool isInsideLoop(Loop *OuterLoop, Loop *InnerLoop) {
+  // If OuterLoop is nullptr, we cannot call its contains() method. In this case
+  // OuterLoop represents the 'top level' and therefore contains all loop.
+  return !OuterLoop || OuterLoop->contains(InnerLoop);
+}
+
 void ZoneAlgorithm::collectIncompatibleElts(ScopStmt *Stmt,
                                             isl::union_set &IncompatibleElts,
                                             isl::union_set &AllElts) {
@@ -469,6 +476,29 @@ void ZoneAlgorithm::addArrayWriteAccess(MemoryAccess *MA) {
   AllWriteValInst = AllWriteValInst.unite(EltWriteValInst);
 }
 
+/// For an llvm::Value defined in @p DefStmt, compute the RAW dependency for a
+/// use in every instance of @p UseStmt.
+///
+/// @param UseStmt Statement a scalar is used in.
+/// @param DefStmt Statement a scalar is defined in.
+///
+/// @return { DomainUse[] -> DomainDef[] }
+isl::map ZoneAlgorithm::computeUseToDefFlowDependency(ScopStmt *UseStmt,
+                                                      ScopStmt *DefStmt) {
+  // { DomainUse[] -> Scatter[] }
+  isl::map UseScatter = getScatterFor(UseStmt);
+
+  // { Zone[] -> DomainDef[] }
+  isl::map ReachDefZone = getScalarReachingDefinition(DefStmt);
+
+  // { Scatter[] -> DomainDef[] }
+  isl::map ReachDefTimepoints =
+      convertZoneToTimepoints(ReachDefZone, isl::dim::in, false, true);
+
+  // { DomainUse[] -> DomainDef[] }
+  return UseScatter.apply_range(ReachDefTimepoints);
+}
+
 /// Return whether @p PHI refers (also transitively through other PHIs) to
 /// itself.
 ///
@@ -611,6 +641,60 @@ isl::map ZoneAlgorithm::getAccessRelationFor(MemoryAccess *MA) const {
   return AccRel.intersect_domain(Domain);
 }
 
+isl::map ZoneAlgorithm::getDefToTarget(ScopStmt *DefStmt,
+                                       ScopStmt *TargetStmt) {
+  // No translation required if the definition is already at the target.
+  if (TargetStmt == DefStmt)
+    return isl::map::identity(
+        getDomainFor(TargetStmt).get_space().map_from_set());
+
+  isl::map &Result = DefToTargetCache[std::make_pair(TargetStmt, DefStmt)];
+
+  // This is a shortcut in case the schedule is still the original and
+  // TargetStmt is in the same or nested inside DefStmt's loop. With the
+  // additional assumption that operand trees do not cross DefStmt's loop
+  // header, then TargetStmt's instance shared coordinates are the same as
+  // DefStmt's coordinates. All TargetStmt instances with this prefix share
+  // the same DefStmt instance.
+  // Model:
+  //
+  //   for (int i < 0; i < N; i+=1) {
+  // DefStmt:
+  //    D = ...;
+  //    for (int j < 0; j < N; j+=1) {
+  // TargetStmt:
+  //      use(D);
+  //    }
+  //  }
+  //
+  // Here, the value used in TargetStmt is defined in the corresponding
+  // DefStmt, i.e.
+  //
+  //   { DefStmt[i] -> TargetStmt[i,j] }
+  //
+  // In practice, this should cover the majority of cases.
+  if (!Result && S->isOriginalSchedule() &&
+      isInsideLoop(DefStmt->getSurroundingLoop(),
+                   TargetStmt->getSurroundingLoop())) {
+    isl::set DefDomain = getDomainFor(DefStmt);
+    isl::set TargetDomain = getDomainFor(TargetStmt);
+    assert(DefDomain.dim(isl::dim::set) <= TargetDomain.dim(isl::dim::set));
+
+    Result = isl::map::from_domain_and_range(DefDomain, TargetDomain);
+    for (unsigned i = 0, DefDims = DefDomain.dim(isl::dim::set); i < DefDims;
+         i += 1)
+      Result = Result.equate(isl::dim::in, i, isl::dim::out, i);
+  }
+
+  if (!Result) {
+    // { DomainDef[] -> DomainTarget[] }
+    Result = computeUseToDefFlowDependency(TargetStmt, DefStmt).reverse();
+    simplify(Result);
+  }
+
+  return Result;
+}
+
 isl::map ZoneAlgorithm::getScalarReachingDefinition(ScopStmt *Stmt) {
   auto &Result = ScalarReachDefZone[Stmt];
   if (Result)
@@ -726,17 +810,8 @@ isl::map ZoneAlgorithm::makeValInst(Value *Val, ScopStmt *UserStmt, Loop *Scope,
     if (!ValStmt)
       return ::makeUnknownForDomain(DomainUse);
 
-    // { DomainDef[] }
-    auto DomainDef = getDomainFor(ValStmt);
-
-    // { Scatter[] -> DomainDef[] }
-    auto ReachDef = getScalarReachingDefinition(DomainDef);
-
-    // { DomainUse[] -> Scatter[] }
-    auto UserSched = getScatterFor(DomainUse);
-
     // { DomainUse[] -> DomainDef[] }
-    auto UsedInstance = UserSched.apply_range(ReachDef);
+    auto UsedInstance = getDefToTarget(ValStmt, UserStmt).reverse();
 
     // { llvm::Value }
     auto ValSet = makeValueSet(Val);