[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

llvm-svn: 335606

1 files changed, 34 insertions, 0 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