[Polly][OpTree] Introduce shortcut for computing the def->target mapping. NFCI.

[Meinersbur]

Summary

In case the schedule has not changed and the operand tree root uses a value defined in an ancestor loop, the def-to-target mapping is trivial. Let the SCoP be

    for (int i < 0; i < N; i+=1) {
  DefStmt:
    D = ...;
    for (int j < 0; j < N; j+=1) {
  TargetStmt:
     use(D);
  }
}

then the DefStmt-to-TargetStmt mapping is

{ DefStmt[i] -> TargetStmt[i,j] }

This case should apply on the majority of cases. This patch detects this case and directly construct the expected mapping. This assumes that the mapping never crosses the loop header DefStmt is in, which ForwardOpTree does not support at the moment anyway.

This should fix the timeout while compiling GrTestUtils.cpp of the Qualcom aosp buildbot. It still needs nearly 5 minutes to compile (which should be below the timeout), but no noticeable time is spent in the getDefToTarget function anymore.

[grosser]

Cool.

include/polly/ScopInfo.h

private:
   ///
   /// Besides band nodes, schedule trees contain additional nodes that specify
   /// a textual ordering between two subtrees or filter nodes that filter the
   /// set of statement instances that will be scheduled in a subtree. There
   /// are also several other nodes. A full description of the different nodes
   /// in a schedule tree is given in the isl manual.
   isl::schedule Schedule = nullptr;
 
+  /// Whether the schedule has been modified after derived from the CFG by
+  /// ScopBuilder.
+  bool ScheduleModified = false;
+
   /// The set of minimal/maximal accesses for each alias group.
   ///
   /// When building runtime alias checks we look at all memory instructions and
   /// build so called alias groups. Each group contains a set of accesses to
   /// different base arrays which might alias with each other. However, between
   /// alias groups there is no aliasing possible.
   ///
   /// In a program with int and float pointers annotated with tbaa information
#endif
   /// NewSchedule The new schedule (given as a flat union-map).
   void setSchedule(isl::union_map NewSchedule);
 
   /// Update the current schedule
   ///
   /// NewSchedule The new schedule (given as schedule tree).
   void setScheduleTree(isl::schedule NewSchedule);
 
+  /// Whether the schedule is the original schedule as derived from the CFG by
+  /// ScopBuilder.
+  bool isOriginalSchedule() const { return !ScheduleModified; }
+
   /// Intersects the domains of all statements in the SCoP.
   ///
   /// @return true if a change was made
   bool restrictDomains(isl::union_set Domain);
 
   /// Get the depth of a loop relative to the outermost loop in the Scop.
   ///
   /// This will return

lib/Analysis/ScopInfo.cpp

 isl::schedule Scop::getScheduleTree() const {
   return Schedule.intersect_domain(getDomains());
 }
 
 void Scop::setSchedule(isl::union_map NewSchedule) {
   auto S = isl::schedule::from_domain(getDomains());
   Schedule = S.insert_partial_schedule(
       isl::multi_union_pw_aff::from_union_map(NewSchedule));
+  ScheduleModified = true;
 }
 
 void Scop::setScheduleTree(isl::schedule NewSchedule) {
   Schedule = NewSchedule;
+  ScheduleModified = true;
 }
 
 bool Scop::restrictDomains(isl::union_set Domain) {
   bool Changed = false;
   for (ScopStmt &Stmt : *this) {
     isl::union_set StmtDomain = isl::union_set(Stmt.getDomain());
     isl::union_set NewStmtDomain = StmtDomain.intersect(Domain);
 

lib/Transform/ForwardOpTree.cpp

isl::map computeUseToDefFlowDependency(ScopStmt *UseStmt, ScopStmt *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
   ///
public:
   /// @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(TargetDomain.dim(isl::dim::set) <= DefDomain.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;
   }