Re: [PATCH] Replace evrp use in loop versioning with ranger.

[Richard Sandiford <richard.sandiford@arm.com>]

Aldy Hernandez <aldyh@redhat.com> writes:
> This patch replaces the evrp_range_analyzer in the loop versioning code
> with an on-demand ranger.
>
> Everything was pretty straightforward, except that range_of_expr requires
> a gimple statement as context to provide context aware ranges.  I didn't see
> a convient place where the statement was saved, so I made a vector indexed
> by SSA names.  As an alternative, I tried to use the loop's first statement,
> but that proved to be insufficient.

The mapping is one-to-many though: there can be multiple statements
for each SSA name.  Maybe that doesn't matter in this context and
any of the statements can act as a representative.

I'm surprised that the loop's first statement didn't work though,
since the SSA name is supposedly known to be loop-invariant.  What went
wrong when you tried that?

> I am not familiar with loop versioning, but if the DOM walk was only
> necessary for the calls to record_ranges_from_stmt, this too could be
> removed as the ranger will work without it.

Yeah, that was the only reason.  If the information is available at
version_for_unity (I guess it is) then we should just avoid recording
the versioning there if so.

How expensive is the check?  If the result is worth caching, perhaps
we should have two bitmaps: the existing one, and one that records
whether we've checked a particular SSA name.

If the check is relatively cheap then that won't be worth it though.

Thanks,
Richard

>
> Tested on x86-64 Linux.
>
> OK?
>
> gcc/ChangeLog:
>
> 	* gimple-loop-versioning.cc (lv_dom_walker::lv_dom_walker): Remove
> 	use of m_range_analyzer.
> 	(loop_versioning::lv_dom_walker::before_dom_children): Same.
> 	(loop_versioning::lv_dom_walker::after_dom_children): Remove.
> 	(loop_versioning::loop_versioning): Allocate space for
> 	m_ssa_context.
> 	(loop_versioning::version_for_unity): Set m_ssa_context.
> 	(loop_versioning::prune_loop_conditions): Replace vr_values use
> 	with range_query interface.
> 	(pass_loop_versioning::execute): Use ranger.
> ---
>  gcc/gimple-loop-versioning.cc | 49 ++++++++++++++---------------------
>  1 file changed, 20 insertions(+), 29 deletions(-)
>
> diff --git a/gcc/gimple-loop-versioning.cc b/gcc/gimple-loop-versioning.cc
> index 4b70c5a4aab..987994d4995 100644
> --- a/gcc/gimple-loop-versioning.cc
> +++ b/gcc/gimple-loop-versioning.cc
> @@ -30,19 +30,17 @@ along with GCC; see the file COPYING3.  If not see
>  #include "tree-ssa-loop.h"
>  #include "ssa.h"
>  #include "tree-scalar-evolution.h"
> -#include "tree-chrec.h"
>  #include "tree-ssa-loop-ivopts.h"
>  #include "fold-const.h"
>  #include "tree-ssa-propagate.h"
>  #include "tree-inline.h"
>  #include "domwalk.h"
> -#include "alloc-pool.h"
> -#include "vr-values.h"
> -#include "gimple-ssa-evrp-analyze.h"
>  #include "tree-vectorizer.h"
>  #include "omp-general.h"
>  #include "predict.h"
>  #include "tree-into-ssa.h"
> +#include "gimple-range.h"
> +#include "tree-cfg.h"
>  
>  namespace {
>  
> @@ -261,14 +259,10 @@ private:
>      lv_dom_walker (loop_versioning &);
>  
>      edge before_dom_children (basic_block) FINAL OVERRIDE;
> -    void after_dom_children (basic_block) FINAL OVERRIDE;
>  
>    private:
>      /* The parent pass.  */
>      loop_versioning &m_lv;
> -
> -    /* Used to build context-dependent range information.  */
> -    evrp_range_analyzer m_range_analyzer;
>    };
>  
>    /* Used to simplify statements based on conditions that are established
> @@ -308,7 +302,7 @@ private:
>    bool analyze_block (basic_block);
>    bool analyze_blocks ();
>  
> -  void prune_loop_conditions (class loop *, vr_values *);
> +  void prune_loop_conditions (class loop *);
>    bool prune_conditions ();
>  
>    void merge_loop_info (class loop *, class loop *);
> @@ -355,6 +349,9 @@ private:
>  
>    /* A list of all addresses in M_ADDRESS_TABLE, in a predictable order.  */
>    auto_vec <address_info *, 32> m_address_list;
> +
> +  /* Gimple context for each SSA in loop_info::unity_names.  */
> +  auto_vec <gimple *> m_ssa_context;
>  };
>  
>  /* If EXPR is an SSA name and not a default definition, return the
> @@ -500,7 +497,7 @@ loop_info::worth_versioning_p () const
>  }
>  
>  loop_versioning::lv_dom_walker::lv_dom_walker (loop_versioning &lv)
> -  : dom_walker (CDI_DOMINATORS), m_lv (lv), m_range_analyzer (false)
> +  : dom_walker (CDI_DOMINATORS), m_lv (lv)
>  {
>  }
>  
> @@ -509,26 +506,12 @@ loop_versioning::lv_dom_walker::lv_dom_walker (loop_versioning &lv)
>  edge
>  loop_versioning::lv_dom_walker::before_dom_children (basic_block bb)
>  {
> -  m_range_analyzer.enter (bb);
> -
>    if (bb == bb->loop_father->header)
> -    m_lv.prune_loop_conditions (bb->loop_father, &m_range_analyzer);
> -
> -  for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
> -       gsi_next (&si))
> -    m_range_analyzer.record_ranges_from_stmt (gsi_stmt (si), false);
> +    m_lv.prune_loop_conditions (bb->loop_father);
>  
>    return NULL;
>  }
>  
> -/* Process BB after processing the blocks it dominates.  */
> -
> -void
> -loop_versioning::lv_dom_walker::after_dom_children (basic_block bb)
> -{
> -  m_range_analyzer.leave (bb);
> -}
> -
>  /* Decide whether to replace VAL with a new value in a versioned loop.
>     Return the new value if so, otherwise return null.  */
>  
> @@ -549,6 +532,7 @@ loop_versioning::loop_versioning (function *fn)
>      m_num_conditions (0),
>      m_address_table (31)
>  {
> +  m_ssa_context.safe_grow (num_ssa_names);
>    bitmap_obstack_initialize (&m_bitmap_obstack);
>    gcc_obstack_init (&m_obstack);
>  
> @@ -644,6 +628,8 @@ loop_versioning::version_for_unity (gimple *stmt, tree name)
>        if (loop_depth (li.outermost) < loop_depth (outermost))
>  	li.outermost = outermost;
>  
> +      m_ssa_context[SSA_NAME_VERSION(name)] = stmt;
> +
>        if (dump_enabled_p ())
>  	{
>  	  dump_printf_loc (MSG_NOTE, stmt, "want to version containing loop"
> @@ -1483,18 +1469,20 @@ loop_versioning::analyze_blocks ()
>     LOOP.  */
>  
>  void
> -loop_versioning::prune_loop_conditions (class loop *loop, vr_values *vrs)
> +loop_versioning::prune_loop_conditions (class loop *loop)
>  {
>    loop_info &li = get_loop_info (loop);
>  
>    int to_remove = -1;
>    bitmap_iterator bi;
>    unsigned int i;
> +  int_range_max r;
>    EXECUTE_IF_SET_IN_BITMAP (&li.unity_names, 0, i, bi)
>      {
>        tree name = ssa_name (i);
> -      const value_range_equiv *vr = vrs->get_value_range (name);
> -      if (vr && !vr->may_contain_p (build_one_cst (TREE_TYPE (name))))
> +      gimple *stmt = m_ssa_context[SSA_NAME_VERSION (name)];
> +      if (get_range_query (cfun)->range_of_expr (r, name, stmt)
> +	  && !r.contains_p (build_one_cst (TREE_TYPE (name))))
>  	{
>  	  if (dump_enabled_p ())
>  	    dump_printf_loc (MSG_NOTE, find_loop_location (loop),
> @@ -1810,7 +1798,10 @@ pass_loop_versioning::execute (function *fn)
>    if (number_of_loops (fn) <= 1)
>      return 0;
>  
> -  return loop_versioning (fn).run ();
> +  enable_ranger (fn);
> +  unsigned int ret = loop_versioning (fn).run ();
> +  disable_ranger (fn);
> +  return ret;
>  }
>  
>  } // anon namespace