Redesign Graphite scop detection

Redesign Graphite scop detection for faster compiler time and detecting more SCoPs.

Existing algorithm for SCoP detection in graphite was based on dominator tree
where a tree (CFG) traversal was required for analyzing an SESE. The tree
traversal is linear in the number of basic blocks and SCoP detection is
(probably) linear in number of instructions. That algorithm utilized a generic
infrastructure of SESE which does not directly represent loops.  With regards to
graphite framework, we are only interested in subtrees with loops. The new
algorithm is geared towards tree traversal on loop structure. The algorithm is
linear in number of loops which is faster than the previous algorithm.

Briefly, we start the traversal at a loop-nest and analyze it recursively for
validity. Once a valid loop is found we find a valid adjacent loop. If an
adjacent loop is found and is valid, we merge both loop nests otherwise we form
a SCoP from the previous loop nest, and resume the algorithm from the adjacent
loop nest. The data structure to represent an SESE is an ordered pair of edges
(entry, exit). The new algoritm can extend a SCoP in both the directions. With
this approach, the number of instructions to be analyzed for validity reduces to
a minimal set.  We start by analyzing those statements which are inside a loop,
because validity of those statements is necessary for the validity of loop. The
statements outside the loop nest can be just excluded from the SESE if they are
not valid.

This patch depends on: https://gcc.gnu.org/ml/gcc-patches/2015-09/msg02024.html

Passes (c,c++,fortran) regtest and bootstrap.

gcc/ChangeLog:

2015-09-27  Aditya Kumar  <hiraditya@msn.com>
            Sebastian Pop  <s.pop@samsung.com>
        * graphite-optimize-isl.c (optimize_isl):
        * graphite-scop-detection.c (struct sese_l): New type.
        (get_entry_bb): API for getting entry bb of SESE.
        (get_exit_bb): API for getting exit bb of SESE.
        (class debug_printer): New type. Simple printer in debug mode.
        (trivially_empty_bb_p): New. Return true when BB is empty or
	contains only debug instructions.
        (graphite_can_represent_expr): Call scalar_evoution_in_region
	instead of analyze_scalar_evolution. Pass in scop instead of only
	the scop entry.
        (stmt_has_simple_data_refs_p): Pass in scop instead of only the
	scop entry.
        (stmt_simple_for_scop_p): Same.
        (harmful_stmt_in_bb): Same.
        (graphite_can_represent_loop): Deleted.
        (struct scopdet_info): Deleted.
        (scopdet_basic_block_info): Deleted.
        (build_scops_1): Deleted.
        (bb_in_sd_region): Deleted.
        (find_single_entry_edge): Deleted.
        (find_single_exit_edge): Deleted.
        (create_single_entry_edge): Deleted.
        (sd_region_without_exit): Deleted.
        (create_single_exit_edge): Deleted.
        (unmark_exit_edges): Deleted.
        (mark_exit_edges): Deleted.
        (create_sese_edges): Deleted.
        (build_graphite_scops): Deleted.
        (canonicalize_loop_closed_ssa): Recompute all dominators at the
	end.
        (build_scops): Use the new scop_builder to build scops.
        (dot_all_scops_1): Use the new pretty printer. Print loop father
	as well.
        (loop_body_is_valid_scop): New. Return true if loop body is a
	valid scop.
        (class scop_builder): New. Builds SCoPs for polyhedral
	optimizatios.
        (scop_builder): New. Constructor.
        (static sese_l invalid_sese): sese_l with invalid edges.
        (get_sese): Get an sese (from a loop) if possible, invalid_sese
	otherwise.
        (get_nearest_dom_with_single_entry): Get nearest dominator of a
	basic_block with single entry. Return NULL if we get to the
	beginning of a function.
        (get_nearest_pdom_with_single_exit): Get nearest post-dominator of
	a basic_block with single exit. Return NULL if we get to the
	beginning of a function.
        (print_sese): Pretty-print SESE.
        (merge_sese): Merge two SESEs if possible and return the new SESE.
        (build_scop_depth): Start building the SCoP within a loop nest.
        (build_scop_breadth): Start building the SCoP at a single loop
	depth. Merge adjacent SESEs if valid.
        (can_represent_loop_1): Returns true if Graphite can represent
	loop inside SCoP. Helper for can_represent_loop.
        (can_represent_loop): Returns true if Graphite can represent LOOP
	and all its nested loops in SCoP.
        (loop_is_valid_scop): Returns true if LOOP and all its nests
	constitute a valid SCoP.
        (region_has_one_loop): Returns true of a region has only one loop.
        (add_scop): Add SCoP to the list of valid scops. Removes an
	already existing scop if it intersects with or subsumed by this
	one.
        (harmful_stmt_in_region): Returns true if SCoP has any statment
	which cannot be represented by Graphite.
        (subsumes): Returns true of SCoP S1 subsumes SCoP S2.
        (remove_subscops): Remove any SCoP from the list of already found
	SCoPs, if subsumed by S1.
        (intersects): Return true if region bounded by SCoPs S1 and S2
	intersect.
        (remove_intersecting_scops): Remove any SCoP which intersects with
	S1.
        * graphite.c (print_graphite_scop_statistics):
        (print_graphite_statistics): Print SCoP info while debugging.
        (graphite_initialize): Early exit in case number of loops in a
	function is less than PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION or
	basic blocks are more than PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION.
        (graphite_finalize):
        * params.def: Add PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION.
        * sese.h (sese_loop_depth): Remove unnecessary gcc_assert.
        (recompute_all_dominators): Recalculate POST_DOMINATORS.
        * tree-cfg.c (print_loops): Print the function name while printing
	loops.

gcc/testsuite/ChangeLog:

2015-09-27  Aditya Kumar  <hiraditya@msn.com>
            Sebastian Pop  <s.pop@samsung.com>
        * gcc.dg/graphite/block-1.c: Modified to match the pattern.
        * gcc.dg/graphite/block-3.c: Same.
        * gcc.dg/graphite/block-4.c: Same.
        * gcc.dg/graphite/block-5.c: Same.
        * gcc.dg/graphite/block-6.c: Same.
        * gcc.dg/graphite/block-7.c: Same.
        * gcc.dg/graphite/block-8.c: Same.
        * gcc.dg/graphite/block-pr47654.c: Same.
        * gcc.dg/graphite/interchange-0.c: Same.
        * gcc.dg/graphite/interchange-1.c: Same.
        * gcc.dg/graphite/interchange-10.c: Same.
        * gcc.dg/graphite/interchange-11.c: Same.
        * gcc.dg/graphite/interchange-12.c: Same.
        * gcc.dg/graphite/interchange-13.c: Same.
        * gcc.dg/graphite/interchange-14.c: Same.
        * gcc.dg/graphite/interchange-15.c: Same.
        * gcc.dg/graphite/interchange-3.c: Same.
        * gcc.dg/graphite/interchange-4.c: Same.
        * gcc.dg/graphite/interchange-5.c: Same.
        * gcc.dg/graphite/interchange-6.c: Same.
        * gcc.dg/graphite/interchange-7.c: Same.
        * gcc.dg/graphite/interchange-8.c: Same.
        * gcc.dg/graphite/interchange-9.c: Same.
        * gcc.dg/graphite/interchange-mvt.c: Same.
        * gcc.dg/graphite/pr35356-1.c (foo): Same.
        * gcc.dg/graphite/pr35356-3.c: Same.
        * gcc.dg/graphite/pr37485.c: Same.
        * gcc/testsuite/gcc.dg/graphite/run-id-pr67700-1.c: New test case.
        * gcc.dg/graphite/scop-1.c (int toto): Modified to match the pattern.
        * gcc.dg/graphite/scop-11.c: Same.
        * gcc.dg/graphite/scop-5.c: Same.
        * gcc.dg/graphite/uns-block-1.c: Same.
        * gcc.dg/graphite/uns-interchange-9.c: Same.
        * gfortran.dg/graphite/block-1.f90: Same.
        * gfortran.dg/graphite/interchange-3.f90: Same.
        * gfortran.dg/graphite/pr14741.f90: Same.

From-SVN: r228215

1 files changed, 41 insertions, 5 deletions

diff --git a/gcc/graphite.c b/gcc/graphite.c
index 36b97a7..a957d93 100644
--- a/gcc/graphite.c
+++ b/gcc/graphite.c
@@ -47,6 +47,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "cfgloop.h"
 #include "tree-pass.h"
 #include "params.h"
+#include "pretty-print.h"
 
 #ifdef HAVE_isl
 #include "cfghooks.h"
@@ -168,6 +169,16 @@ print_graphite_scop_statistics (FILE* file, scop_p scop)
 	}
     }
 
+  fprintf (file, "\nFunction Name: %s\n", current_function_name ());
+
+  edge scop_begin = scop->region->entry;
+  edge scop_end = scop->region->exit;
+
+  fprintf (file, "\nSCoP (entry_edge (bb_%d, bb_%d), ",
+	   scop_begin->src->index, scop_begin->dest->index);
+  fprintf (file, "exit_edge (bb_%d, bb_%d))",
+	   scop_end->src->index, scop_end->dest->index);
+
   fprintf (file, "\nSCoP statistics (");
   fprintf (file, "BBS:%ld, ", n_bbs);
   fprintf (file, "LOOPS:%ld, ", n_loops);
@@ -191,6 +202,10 @@ print_graphite_statistics (FILE* file, vec<scop_p> scops)
 
   FOR_EACH_VEC_ELT (scops, i, scop)
     print_graphite_scop_statistics (file, scop);
+
+  /* Print the loop structure.  */
+  print_loops (file, 2);
+  print_loops (file, 3);
 }
 
 /* Initialize graphite: when there are no loops returns false.  */
@@ -198,14 +213,30 @@ print_graphite_statistics (FILE* file, vec<scop_p> scops)
 static bool
 graphite_initialize (isl_ctx *ctx)
 {
-  if (number_of_loops (cfun) <= 1
+  int min_loops = PARAM_VALUE (PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION);
+  int max_bbs = PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION);
+  int nbbs = n_basic_blocks_for_fn (cfun);
+  int nloops = number_of_loops (cfun);
+
+  if (nloops <= min_loops
       /* FIXME: This limit on the number of basic blocks of a function
 	 should be removed when the SCOP detection is faster.  */
-      || (n_basic_blocks_for_fn (cfun) >
-	  PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION)))
+      || (nbbs > max_bbs))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
-	print_global_statistics (dump_file);
+	{
+	  if (nloops <= min_loops)
+	    fprintf (dump_file, "\nFunction does not have enough loops: "
+		     "PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION = %d.\n",
+		     min_loops);
+
+	  else if (nbbs > max_bbs)
+	    fprintf (dump_file, "\nFunction has too many basic blocks: "
+		     "PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION = %d.\n", max_bbs);
+
+	  fprintf (dump_file, "\nnumber of SCoPs: 0\n");
+	  print_global_statistics (dump_file);
+	}
 
       isl_ctx_free (ctx);
       return false;
@@ -216,7 +247,10 @@ graphite_initialize (isl_ctx *ctx)
   initialize_original_copy_tables ();
 
   if (dump_file && dump_flags)
-    dump_function_to_file (current_function_decl, dump_file, dump_flags);
+    {
+      dump_function_to_file (current_function_decl, dump_file, dump_flags);
+      print_loops (dump_file, 3);
+    }
 
   return true;
 }
@@ -227,8 +261,10 @@ graphite_initialize (isl_ctx *ctx)
 static void
 graphite_finalize (bool need_cfg_cleanup_p)
 {
+  free_dominance_info (CDI_POST_DOMINATORS);
   if (need_cfg_cleanup_p)
     {
+      free_dominance_info (CDI_DOMINATORS);
       scev_reset ();
       cleanup_tree_cfg ();
       profile_status_for_fn (cfun) = PROFILE_ABSENT;