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

[Sebastian Pop]

On Wed, Sep 27, 2017 at 6:48 AM, Richard Biener  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  
>
> * 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!

[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  

* 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_nest;
-
   /* Basic blocks contained in this SESE.  */
   vec bbs;