[PATCH][GRAPHITE] Remove another small quadraticness

[PATCH][GRAPHITE] Remove another small quadraticness

[Richard Biener]

Turns out loop_nest recorded in scop-info isn't really necessary as
we can simply process parameters in loop bounds during the gather_bbs
walk where we encounter each loop (identified by its header) once.

This avoids the linear search in record_loop_in_sese.

Bootstrap / regtest running on x86_64-unknown-linux-gnu, will apply.

Richard.

2017-09-27  Richard Biener  <rguenther@suse.de>

	* graphite-scop-detection.c (find_scop_parameters): Move
	loop bound handling ...
	(gather_bbs::before_dom_children): ... here, avoiding the need
	to build scop_info->loop_nest.
	(record_loop_in_sese): Remove.
	* sese.h (sese_info_t::loop_nest): Remove.
	* sese.c (new_sese_info): Do not allocate loop_nest.
	(free_sese_info): Do not free loop_nest.

Index: gcc/graphite-scop-detection.c
===================================================================
--- gcc/graphite-scop-detection.c	(revision 253226)
+++ gcc/graphite-scop-detection.c	(working copy)
@@ -1330,7 +1324,7 @@ find_params_in_bb (sese_info_p region, g
     }
 }
 
-/* Record the parameters used in the SCOP.  A variable is a parameter
+/* Record the parameters used in the SCOP BBs.  A variable is a parameter
    in a scop if it does not vary during the execution of that scop.  */
 
 static void
@@ -1338,19 +1332,8 @@ find_scop_parameters (scop_p scop)
 {
   unsigned i;
   sese_info_p region = scop->scop_info;
-  struct loop *loop;
 
-  /* Find the parameters used in the loop bounds.  */
-  FOR_EACH_VEC_ELT (region->loop_nest, i, loop)
-    {
-      tree nb_iters = number_of_latch_executions (loop);
-
-      if (!chrec_contains_symbols (nb_iters))
-	continue;
-
-      nb_iters = scalar_evolution_in_region (region->region, loop, nb_iters);
-      scan_tree_for_params (region, nb_iters);
-    }
+  /* Parameters used in loop bounds are processed during gather_bbs.  */
 
   /* Find the parameters used in data accesses.  */
   poly_bb_p pbb;
@@ -1560,28 +1544,6 @@ gather_bbs::gather_bbs (cdi_direction di
 {
 }
 
-/* Record in execution order the loops fully contained in the region.  */
-
-static void
-record_loop_in_sese (basic_block bb, sese_info_p region)
-{
-  loop_p father = bb->loop_father;
-  if (loop_in_sese_p (father, region->region))
-    {
-      bool found = false;
-      loop_p loop0;
-      int j;
-      FOR_EACH_VEC_ELT (region->loop_nest, j, loop0)
-	if (father == loop0)
-	  {
-	    found = true;
-	    break;
-	  }
-      if (!found)
-	region->loop_nest.safe_push (father);
-    }
-}
-
 /* Call-back for dom_walk executed before visiting the dominated
    blocks.  */
 
@@ -1592,7 +1554,20 @@ gather_bbs::before_dom_children (basic_b
   if (!bb_in_sese_p (bb, region->region))
     return dom_walker::STOP;
 
-  record_loop_in_sese (bb, region);
+  /* For loops fully contained in the region record parameters in the
+     loop bounds.  */
+  loop_p loop = bb->loop_father;
+  if (loop->header == bb
+      && loop_in_sese_p (loop, region->region))
+    {
+      tree nb_iters = number_of_latch_executions (loop);
+      if (chrec_contains_symbols (nb_iters))
+	{
+	  nb_iters = scalar_evolution_in_region (region->region,
+						 loop, nb_iters);
+	  scan_tree_for_params (region, nb_iters);
+	}
+    }
 
   gcond *stmt = single_pred_cond_non_loop_exit (bb);
 
Index: gcc/sese.c
===================================================================
--- gcc/sese.c	(revision 253226)
+++ gcc/sese.c	(working copy)
@@ -179,7 +179,6 @@ new_sese_info (edge entry, edge exit)
 
   region->region.entry = entry;
   region->region.exit = exit;
-  region->loop_nest.create (3);
   region->params.create (3);
   region->rename_map = new rename_map_t;
   region->parameter_rename_map = new parameter_rename_map_t;
@@ -197,7 +196,6 @@ void
 free_sese_info (sese_info_p region)
 {
   region->params.release ();
-  region->loop_nest.release ();
 
   for (rename_map_t::iterator it = region->rename_map->begin ();
        it != region->rename_map->end (); ++it)
Index: gcc/sese.h
===================================================================
--- gcc/sese.h	(revision 253226)
+++ gcc/sese.h	(working copy)
@@ -94,9 +94,6 @@ typedef struct sese_info_t
   /* Parameters to be renamed.  */
   parameter_rename_map_t *parameter_rename_map;
 
-  /* Loops completely contained in this SESE.  */
-  vec<loop_p> loop_nest;
-
   /* Basic blocks contained in this SESE.  */
   vec<basic_block> bbs;
 

Re: [PATCH][GRAPHITE] Remove another small quadraticness

[Sebastian Pop]

On Wed, Sep 27, 2017 at 6:48 AM, Richard Biener <rguenther@suse.de> wrote:
>
> Turns out loop_nest recorded in scop-info isn't really necessary as
> we can simply process parameters in loop bounds during the gather_bbs
> walk where we encounter each loop (identified by its header) once.
>
> This avoids the linear search in record_loop_in_sese.
>
> Bootstrap / regtest running on x86_64-unknown-linux-gnu, will apply.
>
> Richard.
>
> 2017-09-27  Richard Biener  <rguenther@suse.de>
>
>         * graphite-scop-detection.c (find_scop_parameters): Move
>         loop bound handling ...
>         (gather_bbs::before_dom_children): ... here, avoiding the need
>         to build scop_info->loop_nest.
>         (record_loop_in_sese): Remove.
>         * sese.h (sese_info_t::loop_nest): Remove.
>         * sese.c (new_sese_info): Do not allocate loop_nest.
>         (free_sese_info): Do not free loop_nest.

Looks good.  Thanks!