[GPGPU] Simplify PPCGSCop to reduce compile time [NFC]

Summary:
Drop unused parameter dimensions to reduce the size of the sets we are working
with. Especially the computed dependences tend to accumulate a lot of parameters
that are present in the input memory accesses, but often not necessary to
express the actual dependences. As isl represents maps and sets with dense
matrices, reducing the dimensionality of isl sets commonly reduces code
generation performance.

This reduces compile time from 17 to 11 seconds for our test case. While this is
not impressive, this patch helped me to identify the previous two performance
improvements and additionally also increases readability of the isl data
structures we use.

Reviewers: Meinersbur, bollu, singam-sanjay

Reviewed By: bollu

Subscribers: nemanjai, pollydev, llvm-commits, kbarton

Tags: #polly

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

llvm-svn: 311161

1 files changed, 79 insertions, 3 deletions

diff --git a/polly/lib/CodeGen/PPCGCodeGeneration.cpp b/polly/lib/CodeGen/PPCGCodeGeneration.cpp
index bc70c478e65d..e95cf2ff548a 100644
--- a/polly/lib/CodeGen/PPCGCodeGeneration.cpp
+++ b/polly/lib/CodeGen/PPCGCodeGeneration.cpp
@@ -2632,6 +2632,77 @@ public:
     return Names;
   }
 
+  /// Remove unreferenced parameter dimensions from union_map.
+  isl::union_map removeUnusedParameters(isl::union_map UMap) {
+    auto New = isl::union_map::empty(isl::space(UMap.get_ctx(), 0, 0));
+
+    auto RemoveUnusedDims = [&New](isl::map S) -> isl::stat {
+      int Removed = 0;
+      int NumDims = S.dim(isl::dim::param);
+      for (long i = 0; i < NumDims; i++) {
+        const int Dim = i - Removed;
+        if (!S.involves_dims(isl::dim::param, Dim, 1)) {
+          S = S.remove_dims(isl::dim::param, Dim, 1);
+          Removed++;
+        }
+      }
+      New = New.unite(S);
+      return isl::stat::ok;
+    };
+
+    UMap.foreach_map(RemoveUnusedDims);
+    return New;
+  }
+
+  /// Remove unreferenced parameter dimensions from union_set.
+  isl::union_set removeUnusedParameters(isl::union_set USet) {
+    auto New = isl::union_set::empty(isl::space(USet.get_ctx(), 0, 0));
+
+    auto RemoveUnusedDims = [&New](isl::set S) -> isl::stat {
+      int Removed = 0;
+      int NumDims = S.dim(isl::dim::param);
+      for (long i = 0; i < NumDims; i++) {
+        const int Dim = i - Removed;
+        if (!S.involves_dims(isl::dim::param, Dim, 1)) {
+          S = S.remove_dims(isl::dim::param, Dim, 1);
+          Removed++;
+        }
+      }
+      New = New.unite(S);
+      return isl::stat::ok;
+    };
+
+    USet.foreach_set(RemoveUnusedDims);
+    return New;
+  }
+
+  /// Simplify PPCG scop to improve compile time.
+  ///
+  /// We drop unused parameter dimensions to reduce the size of the sets we are
+  /// working with. Especially the computed dependences tend to accumulate a lot
+  /// of parameters that are present in the input memory accesses, but often are
+  /// not necessary to express the actual dependences. As isl represents maps
+  /// and sets with dense matrices, reducing the dimensionality of isl sets
+  /// commonly reduces code generation performance.
+  void simplifyPPCGScop(ppcg_scop *PPCGScop) {
+    PPCGScop->domain =
+        removeUnusedParameters(isl::manage(PPCGScop->domain)).release();
+
+    PPCGScop->dep_forced =
+        removeUnusedParameters(isl::manage(PPCGScop->dep_forced)).release();
+    PPCGScop->dep_false =
+        removeUnusedParameters(isl::manage(PPCGScop->dep_false)).release();
+    PPCGScop->dep_flow =
+        removeUnusedParameters(isl::manage(PPCGScop->dep_flow)).release();
+    PPCGScop->tagged_dep_flow =
+        removeUnusedParameters(isl::manage(PPCGScop->tagged_dep_flow))
+            .release();
+
+    PPCGScop->tagged_dep_order =
+        removeUnusedParameters(isl::manage(PPCGScop->tagged_dep_order))
+            .release();
+  }
+
   /// Create a new PPCG scop from the current scop.
   ///
   /// The PPCG scop is initialized with data from the current polly::Scop. From
@@ -2689,6 +2760,7 @@ public:
     compute_tagger(PPCGScop);
     compute_dependences(PPCGScop);
     eliminate_dead_code(PPCGScop);
+    simplifyPPCGScop(PPCGScop);
 
     return PPCGScop;
   }
@@ -3130,10 +3202,14 @@ public:
 
     isl_schedule *Schedule = get_schedule(PPCGGen);
 
-    int has_permutable = has_any_permutable_node(Schedule);
+    /// Copy to and from device functions may introduce new parameters, which
+    /// must be present in the schedule tree root for code generation. Hence,
+    /// we ensure that all possible parameters are introduced from this point.
+    if (!PollyManagedMemory)
+      Schedule =
+          isl_schedule_align_params(Schedule, S->getFullParamSpace().release());
 
-    Schedule =
-        isl_schedule_align_params(Schedule, S->getFullParamSpace().release());
+    int has_permutable = has_any_permutable_node(Schedule);
 
     if (!has_permutable || has_permutable < 0) {
       Schedule = isl_schedule_free(Schedule);