[Polly][ZoneAlgo] Use getDefToTarget in makeValInst. NFC.

[Meinersbur]

Summary

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

This reduces the compile time of GrTestUtils from 2m46s to 21s.

[grosser]

Nice!

polly/trunk/include/polly/ZoneAlgo.h

protected:
   /// entries to this map.
   ///
   /// { PHIValInst[] -> IncomingValInst[] }
   isl::union_map NormalizeMap;
 
   /// 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.
   /// @param S        The SCoP to process.
   /// @param LI       LoopInfo analysis used to determine synthesizable values.
   ZoneAlgorithm(const char *PassName, Scop *S, llvm::LoopInfo *LI);
 
 private:
private:
   /// ValInst if there is no single ValInst[] the array element written to will
   /// have.
   ///
   /// @return { ValInst[] }
   isl::union_map getWrittenValue(MemoryAccess *MA, isl::map AccRel);
 
   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;
 
   isl::union_map makeEmptyUnionMap() const;
 
   /// For each 'execution' of a PHINode, get the incoming block that was
   /// executed before.
   ///
protected:
   /// Get the domain @p MA's parent statement.
   isl::set getDomainFor(MemoryAccess *MA) const;
 
   /// Get the access relation of @p MA.
   ///
   /// 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
   /// statement it is defined in. Therefore the same computation can be reused.
   ///
   /// @param Stmt The statement in which a scalar is defined.
   ///
   /// @return { Scatter[] -> DomainDef[] }

polly/trunk/lib/Transform/ForwardOpTree.cpp

private:
   /// @see computeKnown()
   isl::union_map Known;
 
   /// Translator for newly introduced ValInsts to already existing ValInsts such
   /// that new introduced load instructions can reuse the Known analysis of its
   /// 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[] }
   ///                The values for which we search for alternative locations,
   ///                per statement instance.
   ///
   /// @return { Domain[] -> Element[] }
   ///         For each statement instance, the array elements that contain the
MemoryAccess *makeReadArrayAccess(ScopStmt *Stmt, LoadInst *LI,
     S->addAccessFunction(Access);
     Stmt->addAccess(Access, true);
 
     Access->setNewAccessRelation(AccessRelation);
 
     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.
   ///
   /// @param TargetStmt  The statement the operand tree will be copied to.
   /// @param Inst        The (possibly speculatable) instruction to forward.
   /// @param UseStmt     The statement that uses @p Inst.
   /// @param UseLoop     The loop @p Inst is used in.
   /// @param DefStmt     The statement @p Inst is defined in.

polly/trunk/lib/Transform/ZoneAlgo.cpp

for (auto *MA : *Stmt) {
     }
 
     if (V != MA->getAccessValue())
       return false;
   }
   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) {
   auto Stores = makeEmptyUnionMap();
   auto Loads = makeEmptyUnionMap();
 
   // This assumes that the MemoryKind::Array MemoryAccesses are iterated in
   // order.
void ZoneAlgorithm::addArrayWriteAccess(MemoryAccess *MA) {
 
   // { [Element[] -> DomainWrite[]] -> ValInst[] }
   isl::union_map EltWriteValInst =
       WriteValInstance.apply_domain(IncludeElement);
 
   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.
 ///
 /// loop:
 ///   %phi1 = phi [0, %preheader], [%phi1, %loop]
 ///   br i1 %c, label %loop, label %exit
 ///
 /// exit:

 }
 
 isl::map ZoneAlgorithm::getAccessRelationFor(MemoryAccess *MA) const {
   auto Domain = getDomainFor(MA);
   auto AccRel = MA->getLatestAccessRelation();
   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)
     return Result;
 
   auto Domain = getDomainFor(Stmt);
   Result = computeScalarReachingDefinition(Schedule, Domain, false, true);
   simplify(Result);
case VirtualUse::Inter: {
     auto *ValStmt = S->getStmtFor(Inst);
 
     // If the llvm::Value is defined in a removed Stmt, we cannot derive its
     // domain. We could use an arbitrary statement, but this could result in
     // different ValInst[] for the same llvm::Value.
     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);
 
     // { DomainUse[] -> llvm::Value[] }
     auto ValInstSet = isl::map::from_domain_and_range(DomainUse, ValSet);
 
     // { DomainUse[] -> [DomainDef[] -> llvm::Value]  }