Remove limit_scops

This patch removes graphite-scop-detection.c:limit_scops function and fix
related issues arising because of that. The functionality limit_scop was added
as an intermediate step to discard the loops which graphite could not
handle. Removing limit_scop required handling of different cases of loops and
surrounding code.  The scop is now larger so most test cases required 'number of
scops detected' to be fixed. By increasing the size of scop we can now optimize
loops which are 'siblings' of each other. This could enable loop fusion on a
number of loops. Since in the graphite framework we mostly want to opimize
loop-nests/adjacent-loops, we now discard scops with less than 2 loops. We
also discard scops without any data references.

Essentially:
 - Remove limite_scops.
 - Only select scops when there are at least two loops (loop nest or, side by side).
 - Discard loops without data-refs.
 - Fix test cases.

Passes bootstrap and reg-test.

gcc/ChangeLog:

2015-09-02  Aditya Kumar  <hiraditya@msn.com>
            Sebastian Pop  <s.pop@samsung.com>

        * graphite-isl-ast-to-gimple.c (gcc_expression_from_isl_ast_expr_id):
        Return the parameter if it was saved in corresponding
        parameter_rename_map of the region.
        (copy_def): Copy def from sese region to the newly created region.
        (copy_internal_parameters): Copy all the internal parameters defined
        within a region to the newly created region.
        (graphite_regenerate_ast_isl): Copy parameters to the new region before
        translating isl to gimple.
        * graphite-scop-detection.c (graphite_can_represent_loop): Bail out if
          the loop-nest does not have any data-references.
        (build_graphite_scops): Create a scop only when there is at least one
        loop inside it.
        (contains_only_close_phi_nodes): Deleted.
        (print_graphite_scop_statistics): Deleted
        (print_graphite_statistics): Deleted
        (limit_scops): Deleted.
        (build_scops): Removed call to limit_scops.
        * sese.c (new_sese): Construct.
        (free_sese): Destruct.
        (sese_add_exit_phis_edge): update_stmt after exit phi edge has been
        added.
        (set_rename): Pass sese region so that parameters inside the region can
        be added to its parameter_rename_map.
        (rename_uses): Pass sese region.
        (graphite_copy_stmts_from_block): Do not copy parameters that have been
        generated in the header of the scop. For each SSA_NAME in the
        parameter_rename_map rename its usage.
        (invariant_in_sese_p_rec): Return false if tree t is defined outside
        sese region.
        (scalar_evolution_in_region): If the tree t is invariant just return t.
        * sese.h: Added a parameter renamne map (parameter_rename_map_t) to
          struct sese to keep track of all the parameters which need renaming.
        * tree-data-ref.c (loop_nest_has_data_refs): Check if a loop nest has
          any data-refs.
        * tree-data-ref.h: Declaration of loop_nest_has_data_refs.

gcc/testsuite/ChangeLog:

2015-09-02  Aditya Kumar  <hiraditya@msn.com>
            Sebastian Pop  <s.pop@samsung.com>

        * gcc.dg/graphite/block-0.c: Modifed test case to match current output.
        * gcc.dg/graphite/block-1.c: Same.
        * gcc.dg/graphite/block-5.c: Same.
        * gcc.dg/graphite/block-6.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-13.c: Same.
        * gcc.dg/graphite/interchange-14.c: Same.
        * gcc.dg/graphite/interchange-3.c: Same.
        * gcc.dg/graphite/interchange-4.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/isl-codegen-loop-dumping.c: Same.
        * gcc.dg/graphite/pr35356-1.c (foo): Same.
        * gcc.dg/graphite/pr37485.c: Same.
        * gcc.dg/graphite/scop-0.c (int toto): Same.
        * gcc.dg/graphite/scop-1.c: Same.
        * gcc.dg/graphite/scop-10.c: Same.
        * gcc.dg/graphite/scop-11.c: Same.
        * gcc.dg/graphite/scop-12.c: Same.
        * gcc.dg/graphite/scop-13.c: Same.
        * gcc.dg/graphite/scop-16.c: Same.
        * gcc.dg/graphite/scop-17.c: Same.
        * gcc.dg/graphite/scop-18.c: Same.
        * gcc.dg/graphite/scop-2.c: Same.
        * gcc.dg/graphite/scop-21.c (int test): Same.
        * gcc.dg/graphite/scop-22.c (void foo): Same.
        * gcc.dg/graphite/scop-4.c: Same.
        * gcc.dg/graphite/scop-5.c: Same.
        * gcc.dg/graphite/scop-6.c: Same.
        * gcc.dg/graphite/scop-7.c: Same.
        * gcc.dg/graphite/scop-8.c: Same.
        * gcc.dg/graphite/scop-9.c: Same.
        * gcc.dg/graphite/scop-mvt.c (void mvt): Introduced dependency so that
          data-refs remain inside the inner loop.
        * gcc.dg/graphite/uns-block-1.c: Modifed test case to match o/p.
        * gcc.dg/graphite/uns-interchange-14.c: Same.
        * gcc.dg/graphite/uns-interchange-9.c: Same.
        * gfortran.dg/graphite/interchange-3.f90

libgomp/ChangeLog:

2015-09-04  Aditya Kumar  <hiraditya@msn.com>
            Sebastian Pop  <s.pop@samsung.com>

        * testsuite/libgomp.graphite/bounds.c (int foo): Modifed test case to
          match o/p.
        * testsuite/libgomp.graphite/force-parallel-1.c (void parloop): Same.
        * testsuite/libgomp.graphite/force-parallel-4.c: Same.
        * testsuite/libgomp.graphite/force-parallel-5.c: Same.
        * testsuite/libgomp.graphite/force-parallel-7.c: Same.
        * testsuite/libgomp.graphite/force-parallel-8.c: Same.

Co-Authored-By: Sebastian Pop <s.pop@samsung.com>

From-SVN: r227567

1 files changed, 22 insertions, 151 deletions

diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
index dbd9842..3ac56de 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -472,6 +472,17 @@ graphite_can_represent_loop (basic_block scop_entry, loop_p loop)
   tree niter;
   struct tree_niter_desc niter_desc;
 
+  if (!loop_nest_has_data_refs (loop))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "[scop-detection-fail] ");
+	  fprintf (dump_file, "Loop %d does not have any data reference.\n",
+		   loop->num);
+	}
+      return false;
+    }
+
   /* FIXME: For the moment, graphite cannot be used on loops that
      iterate using induction variables that wrap.  */
 
@@ -1155,8 +1166,17 @@ build_graphite_scops (vec<sd_region> regions,
       if (!exit)
 	continue;
 
-      scop = new_scop (new_sese (entry, exit));
-      scops->safe_push (scop);
+      sese sese_reg = new_sese (entry, exit);
+      scop = new_scop (sese_reg);
+
+      build_sese_loop_nests (sese_reg);
+
+      /* Scops with one or no loops are not interesting.  */
+      if (SESE_LOOP_NEST (sese_reg).length () > 1)
+	scops->safe_push (scop);
+      else if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Discarded scop: %d loops\n",
+		 SESE_LOOP_NEST (sese_reg).length ());
 
       /* Are there overlapping SCoPs?  */
 #ifdef ENABLE_CHECKING
@@ -1172,151 +1192,6 @@ build_graphite_scops (vec<sd_region> regions,
     }
 }
 
-/* Returns true when BB contains only close phi nodes.  */
-
-static bool
-contains_only_close_phi_nodes (basic_block bb)
-{
-  gimple_stmt_iterator gsi;
-
-  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
-    if (gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
-      return false;
-
-  return true;
-}
-
-/* Print statistics for SCOP to FILE.  */
-
-static void
-print_graphite_scop_statistics (FILE* file, scop_p scop)
-{
-  long n_bbs = 0;
-  long n_loops = 0;
-  long n_stmts = 0;
-  long n_conditions = 0;
-  long n_p_bbs = 0;
-  long n_p_loops = 0;
-  long n_p_stmts = 0;
-  long n_p_conditions = 0;
-
-  basic_block bb;
-
-  FOR_ALL_BB_FN (bb, cfun)
-    {
-      gimple_stmt_iterator psi;
-      loop_p loop = bb->loop_father;
-
-      if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
-	continue;
-
-      n_bbs++;
-      n_p_bbs += bb->count;
-
-      if (EDGE_COUNT (bb->succs) > 1)
-	{
-	  n_conditions++;
-	  n_p_conditions += bb->count;
-	}
-
-      for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
-	{
-	  n_stmts++;
-	  n_p_stmts += bb->count;
-	}
-
-      if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
-	{
-	  n_loops++;
-	  n_p_loops += bb->count;
-	}
-
-    }
-
-  fprintf (file, "\nBefore limit_scops SCoP statistics (");
-  fprintf (file, "BBS:%ld, ", n_bbs);
-  fprintf (file, "LOOPS:%ld, ", n_loops);
-  fprintf (file, "CONDITIONS:%ld, ", n_conditions);
-  fprintf (file, "STMTS:%ld)\n", n_stmts);
-  fprintf (file, "\nBefore limit_scops SCoP profiling statistics (");
-  fprintf (file, "BBS:%ld, ", n_p_bbs);
-  fprintf (file, "LOOPS:%ld, ", n_p_loops);
-  fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
-  fprintf (file, "STMTS:%ld)\n", n_p_stmts);
-}
-
-/* Print statistics for SCOPS to FILE.  */
-
-static void
-print_graphite_statistics (FILE* file, vec<scop_p> scops)
-{
-  int i;
-  scop_p scop;
-
-  FOR_EACH_VEC_ELT (scops, i, scop)
-    print_graphite_scop_statistics (file, scop);
-}
-
-/* We limit all SCoPs to SCoPs, that are completely surrounded by a loop.
-
-   Example:
-
-   for (i      |
-     {         |
-       for (j  |  SCoP 1
-       for (k  |
-     }         |
-
-   * SCoP frontier, as this line is not surrounded by any loop. *
-
-   for (l      |  SCoP 2
-
-   This is necessary as scalar evolution and parameter detection need a
-   outermost loop to initialize parameters correctly.
-
-   TODO: FIX scalar evolution and parameter detection to allow more flexible
-         SCoP frontiers.  */
-
-static void
-limit_scops (vec<scop_p> *scops)
-{
-  auto_vec<sd_region, 3> regions;
-
-  int i;
-  scop_p scop;
-
-  FOR_EACH_VEC_ELT (*scops, i, scop)
-    {
-      int j;
-      loop_p loop;
-      sese region = SCOP_REGION (scop);
-      build_sese_loop_nests (region);
-
-      FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), j, loop)
-        if (!loop_in_sese_p (loop_outer (loop), region)
-	    && single_exit (loop))
-          {
-	    sd_region open_scop;
-	    open_scop.entry = loop->header;
-	    open_scop.exit = single_exit (loop)->dest;
-
-	    /* This is a hack on top of the limit_scops hack.  The
-	       limit_scops hack should disappear all together.  */
-	    if (single_succ_p (open_scop.exit)
-		&& contains_only_close_phi_nodes (open_scop.exit))
-	      open_scop.exit = single_succ_edge (open_scop.exit)->dest;
-
-	    regions.safe_push (open_scop);
-	  }
-    }
-
-  free_scops (*scops);
-  scops->create (3);
-
-  create_sese_edges (regions);
-  build_graphite_scops (regions, scops);
-}
-
 /* Returns true when P1 and P2 are close phis with the same
    argument.  */
 
@@ -1501,10 +1376,6 @@ build_scops (vec<scop_p> *scops)
   create_sese_edges (regions);
   build_graphite_scops (regions, scops);
 
-  if (dump_file && (dump_flags & TDF_DETAILS))
-    print_graphite_statistics (dump_file, *scops);
-
-  limit_scops (scops);
   regions.release ();
 
   if (dump_file && (dump_flags & TDF_DETAILS))