Re: [RFC][PATCH 12/n Embed range analysis in DOM

[Richard Biener <richard dot guenther at gmail dot com>]

On Sat, Nov 18, 2017 at 10:31 AM, Jeff Law <law@redhat.com> wrote:
> And a WIP.  I can justify continuing work on this during stage3 for
> pr78496.  But I thought it was worth giving folks a looksie.
>
> The goal here is to make tree-vrp's threading obsolete and remove it and
> at the same time pick up all the missed jump threads in pr78496.
>
> Essentially this patch embeds the evrp analysis into DOM and adds some
> simplification code to use the results of the evrp analysis within jump
> threading.
>
> This bootstraps, but doesn't quite pass regression testing.  There's a
> few tests that need adjustment.  There's also two failing tests which I
> think are a manifestation of a latent bug in the EVRP bits I've been
> worried about since I started looking at the code.
>
> It does find *all* the missing threads in pr78496.  I'm still evaluating
> the impact of dropping tree-vrp.c's jump threading, but it looks promising.
>
> There's two patches I'm not posting at this time.  First is the range
> analyzer embedded in the sprintf warning pass to avoid a false positive
> reported to gcc-bugs a while back.  I'm pretty sure it tickles the same
> latent bug I mentioned above with the range analyzer embedded in DOM.
> It also needs minor fixes to deal with being called when the optimizer
> is not on.  Given the false positive posted to gcc-bugs and the tiny
> size of the patch I can justify wrapping that up early in stage3.
>
> The second patch I'm not posting rips jump threading out of tree-vrp.c
> It's just too rough in its current state.  I'm sure there's a bug that
> says GCC has gotten slower than I can use to justify pushing on this
> early in stage3 as well.
>
> I'm calling it a night from my virtual office in Hawaii.

So DOM now does EVRP in parallel but only uses the result for
threading, not for other simplification.  That somehow feels like
a waste of cycles?  Isn't this the opportunity to "merge" DOM and EVRP
to make one (configurable) DOM-walker optimization pass?

I applaud the first and foremost goal of ripping threading out of VRP
(and to be honest I'd rather get rid of the SSA propagator VRP
implementation completely at some point...).

Richard.

> Jeff
>
>
>         * gimple-ssa-evrp-analyze.h (class evrp_range_analyzer): Add new
>         private member, use_scev to control use of SCEV.
>         * gimple-ssa-evrp-analyze.c
>         (evrp_range_analyzer::evrp_range_analyzer): Initialize use_scev
>         from argument.  Pass it along to vr_values ctor as well.
>         (evrp_range_analyzer::record_ranges_from_phis): Only call
>         SCEV routines if use_scev is true.
>         * gimple-ssa-evrp.c (evrp_dom_walker): Pass use_scev along to
>         evrp_range_analyzer ctor.
>         * tree-vrp.c (vrp_prop::vrp_prop): Accept along use_scev to to
>         vr_values ctor.
>         (execute_vrp): Add new argument to vrp_prop::vrp_prop.
>         * vr-values.h (class vr_values): New data member use_scev.
>         * vr-values.c (vr_values::vr_values): Accept and initialize use_scev.
>         (vr_values::extract_range_from_phi_node): Only call SCEV routines
>         if use_scev is true.
>
>         * tree-ssa-dom.c: Include alloc-pool.h, tree-vrp.h, vr-values.h
>         and gimple-ssa-evrp-analyze.h.
>         (dom_opt_dom_walker class): Add evrp_range_analyzer member and
>         initialize it.
>         (simplify_stmt_for_jump_threading): Copy a blob of code from
>         tree-vrp.c to use ranges to simplify statements.
>         (dom_opt_dom_walker::before_dom_children): Call
>         evrp_range_analyzer::{enter,record_ranges_from_stmt} methods.
>         (dom_opt_dom_walker::after_dom_children): Similarly for
>         evrp_range_analyzer::leave.
>
>
>
>
> diff --git a/gcc/gimple-ssa-evrp-analyze.c b/gcc/gimple-ssa-evrp-analyze.c
> index 5702a5e..0fd5a01 100644
> --- a/gcc/gimple-ssa-evrp-analyze.c
> +++ b/gcc/gimple-ssa-evrp-analyze.c
> @@ -42,7 +42,8 @@ along with GCC; see the file COPYING3.  If not see
>  #include "vr-values.h"
>  #include "gimple-ssa-evrp-analyze.h"
>
> -evrp_range_analyzer::evrp_range_analyzer () : stack (10)
> +evrp_range_analyzer::evrp_range_analyzer (bool use_scev_)
> +  : use_scev (use_scev_), stack (10)
>  {
>    edge e;
>    edge_iterator ei;
> @@ -53,7 +54,7 @@ evrp_range_analyzer::evrp_range_analyzer () : stack (10)
>        FOR_EACH_EDGE (e, ei, bb->preds)
>          e->flags |= EDGE_EXECUTABLE;
>      }
> -  vr_values = new class vr_values;
> +  vr_values = new class vr_values (use_scev);
>  }
>
>  void
> @@ -178,7 +179,8 @@ evrp_range_analyzer::record_ranges_from_phis (basic_block bb)
>              to use VARYING for them.  But we can still resort to
>              SCEV for loop header PHIs.  */
>           struct loop *l;
> -         if (interesting
> +         if (use_scev
> +             && interesting
>               && (l = loop_containing_stmt (phi))
>               && l->header == gimple_bb (phi))
>           vr_values->adjust_range_with_scev (&vr_result, l, phi, lhs);
> diff --git a/gcc/gimple-ssa-evrp-analyze.h b/gcc/gimple-ssa-evrp-analyze.h
> index b60bba8..c327836 100644
> --- a/gcc/gimple-ssa-evrp-analyze.h
> +++ b/gcc/gimple-ssa-evrp-analyze.h
> @@ -23,7 +23,7 @@ along with GCC; see the file COPYING3.  If not see
>  class evrp_range_analyzer
>  {
>   public:
> -  evrp_range_analyzer (void);
> +  evrp_range_analyzer (bool);
>    ~evrp_range_analyzer (void)
>    {
>      if (vr_values)
> @@ -70,6 +70,9 @@ class evrp_range_analyzer
>    void record_ranges_from_incoming_edge (basic_block);
>    void record_ranges_from_phis (basic_block);
>
> +  /* Whether or not to use SCEV to refine ranges.  */
> +  bool use_scev;
> +
>    /* STACK holds the old VR.  */
>    auto_vec<std::pair <tree, value_range*> > stack;
>  };
> diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c
> index 30d0689..f9a014d 100644
> --- a/gcc/gimple-ssa-evrp.c
> +++ b/gcc/gimple-ssa-evrp.c
> @@ -69,6 +69,7 @@ class evrp_dom_walker : public dom_walker
>  public:
>    evrp_dom_walker ()
>      : dom_walker (CDI_DOMINATORS),
> +      evrp_range_analyzer (true),
>        evrp_folder (evrp_range_analyzer.get_vr_values (false))
>      {
>        need_eh_cleanup = BITMAP_ALLOC (NULL);
> diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
> index eb85b4a..d7f2095 100644
> --- a/gcc/tree-ssa-dom.c
> +++ b/gcc/tree-ssa-dom.c
> @@ -46,6 +46,10 @@ along with GCC; see the file COPYING3.  If not see
>  #include "gimplify.h"
>  #include "tree-cfgcleanup.h"
>  #include "dbgcnt.h"
> +#include "alloc-pool.h"
> +#include "tree-vrp.h"
> +#include "vr-values.h"
> +#include "gimple-ssa-evrp-analyze.h"
>
>  /* This file implements optimizations on the dominator tree.  */
>
> @@ -573,6 +577,7 @@ public:
>      : dom_walker (direction, true),
>        m_const_and_copies (const_and_copies),
>        m_avail_exprs_stack (avail_exprs_stack),
> +      evrp_range_analyzer (false),
>        m_dummy_cond (dummy_cond) { }
>
>    virtual edge before_dom_children (basic_block);
> @@ -584,6 +589,9 @@ private:
>    class const_and_copies *m_const_and_copies;
>    class avail_exprs_stack *m_avail_exprs_stack;
>
> +  /* And VRP data.  */
> +  class evrp_range_analyzer evrp_range_analyzer;
> +
>    /* Dummy condition to avoid creating lots of throw away statements.  */
>    gcond *m_dummy_cond;
>
> @@ -835,6 +843,8 @@ make_pass_dominator (gcc::context *ctxt)
>    return new pass_dominator (ctxt);
>  }
>
> +/* A hack.  */
> +static class vr_values *x_vr_values;
>
>  /* A trivial wrapper so that we can present the generic jump
>     threading code with a simple API for simplifying statements.  */
> @@ -844,7 +854,91 @@ simplify_stmt_for_jump_threading (gimple *stmt,
>                                   class avail_exprs_stack *avail_exprs_stack,
>                                   basic_block bb ATTRIBUTE_UNUSED)
>  {
> -  return avail_exprs_stack->lookup_avail_expr (stmt, false, true);
> +  tree cached_lhs =  avail_exprs_stack->lookup_avail_expr (stmt, false, true);
> +  if (cached_lhs && is_gimple_min_invariant (cached_lhs))
> +    return cached_lhs;
> +
> +  /* */
> +  vr_values *vr_values = x_vr_values;
> +  if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
> +    {
> +      return vr_values->vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
> +                                          gimple_cond_lhs (cond_stmt),
> +                                          gimple_cond_rhs (cond_stmt),
> +                                          within_stmt);
> +    }
> +
> +  if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt))
> +    {
> +      tree op = gimple_switch_index (switch_stmt);
> +      if (TREE_CODE (op) != SSA_NAME)
> +       return NULL_TREE;
> +
> +      value_range *vr = vr_values->get_value_range (op);
> +      if ((vr->type != VR_RANGE && vr->type != VR_ANTI_RANGE)
> +         || symbolic_range_p (vr))
> +       return NULL_TREE;
> +
> +      if (vr->type == VR_RANGE)
> +       {
> +         size_t i, j;
> +
> +         find_case_label_range (switch_stmt, vr->min, vr->max, &i, &j);
> +
> +         if (i == j)
> +           {
> +             tree label = gimple_switch_label (switch_stmt, i);
> +
> +             if (CASE_HIGH (label) != NULL_TREE
> +                 ? (tree_int_cst_compare (CASE_LOW (label), vr->min) <= 0
> +                    && tree_int_cst_compare (CASE_HIGH (label), vr->max) >= 0)
> +                 : (tree_int_cst_equal (CASE_LOW (label), vr->min)
> +                    && tree_int_cst_equal (vr->min, vr->max)))
> +               return label;
> +
> +             if (i > j)
> +               return gimple_switch_label (switch_stmt, 0);
> +           }
> +       }
> +
> +      if (vr->type == VR_ANTI_RANGE)
> +          {
> +            unsigned n = gimple_switch_num_labels (switch_stmt);
> +            tree min_label = gimple_switch_label (switch_stmt, 1);
> +            tree max_label = gimple_switch_label (switch_stmt, n - 1);
> +
> +            /* The default label will be taken only if the anti-range of the
> +               operand is entirely outside the bounds of all the (non-default)
> +               case labels.  */
> +            if (tree_int_cst_compare (vr->min, CASE_LOW (min_label)) <= 0
> +                && (CASE_HIGH (max_label) != NULL_TREE
> +                    ? tree_int_cst_compare (vr->max, CASE_HIGH (max_label)) >= 0
> +                    : tree_int_cst_compare (vr->max, CASE_LOW (max_label)) >= 0))
> +            return gimple_switch_label (switch_stmt, 0);
> +          }
> +
> +       return NULL_TREE;
> +    }
> +
> +  if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
> +    {
> +      tree lhs = gimple_assign_lhs (assign_stmt);
> +      if (TREE_CODE (lhs) == SSA_NAME
> +         && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
> +             || POINTER_TYPE_P (TREE_TYPE (lhs)))
> +         && stmt_interesting_for_vrp (stmt))
> +       {
> +         edge dummy_e;
> +         tree dummy_tree;
> +         value_range new_vr = VR_INITIALIZER;
> +         vr_values->extract_range_from_stmt (stmt, &dummy_e,
> +                                             &dummy_tree, &new_vr);
> +         if (range_int_cst_singleton_p (&new_vr))
> +           return new_vr.min;
> +       }
> +    }
> +  return NULL;
> +
>  }
>
>  /* Valueize hook for gimple_fold_stmt_to_constant_1.  */
> @@ -1299,6 +1393,8 @@ dom_opt_dom_walker::before_dom_children (basic_block bb)
>    if (dump_file && (dump_flags & TDF_DETAILS))
>      fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
>
> +  evrp_range_analyzer.enter (bb);
> +
>    /* Push a marker on the stacks of local information so that we know how
>       far to unwind when we finalize this block.  */
>    m_avail_exprs_stack->push_marker ();
> @@ -1321,7 +1417,10 @@ dom_opt_dom_walker::before_dom_children (basic_block bb)
>
>    edge taken_edge = NULL;
>    for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> -    taken_edge = this->optimize_stmt (bb, gsi);
> +    {
> +      evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi));
> +      taken_edge = this->optimize_stmt (bb, gsi);
> +    }
>
>    /* Now prepare to process dominated blocks.  */
>    record_edge_info (bb);
> @@ -1339,13 +1438,16 @@ dom_opt_dom_walker::before_dom_children (basic_block bb)
>  void
>  dom_opt_dom_walker::after_dom_children (basic_block bb)
>  {
> +  x_vr_values = evrp_range_analyzer.get_vr_values (false);
>    thread_outgoing_edges (bb, m_dummy_cond, m_const_and_copies,
>                          m_avail_exprs_stack,
>                          simplify_stmt_for_jump_threading);
> +  x_vr_values = NULL;
>
>    /* These remove expressions local to BB from the tables.  */
>    m_avail_exprs_stack->pop_to_marker ();
>    m_const_and_copies->pop_to_marker ();
> +  evrp_range_analyzer.leave (bb);
>  }
>
>  /* Search for redundant computations in STMT.  If any are found, then
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index 838822d..46be749 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -4737,6 +4737,7 @@ insert_range_assertions (void)
>  class vrp_prop : public ssa_propagation_engine
>  {
>   public:
> +  vrp_prop (bool use_scev_) : vr_values (use_scev_) { }
>    enum ssa_prop_result visit_stmt (gimple *, edge *, tree *) FINAL OVERRIDE;
>    enum ssa_prop_result visit_phi (gphi *) FINAL OVERRIDE;
>
> @@ -6862,7 +6863,7 @@ execute_vrp (bool warn_array_bounds_p)
>    /* For visiting PHI nodes we need EDGE_DFS_BACK computed.  */
>    mark_dfs_back_edges ();
>
> -  class vrp_prop vrp_prop;
> +  class vrp_prop vrp_prop (true);
>    vrp_prop.vrp_initialize ();
>    vrp_prop.ssa_propagate ();
>    vrp_prop.vrp_finalize (warn_array_bounds_p);
> diff --git a/gcc/vr-values.c b/gcc/vr-values.c
> index 3e760a3..a0e68fb 100644
> --- a/gcc/vr-values.c
> +++ b/gcc/vr-values.c
> @@ -1888,7 +1888,8 @@ vr_values::dump_all_value_ranges (FILE *file)
>
>  /* Initialize VRP lattice.  */
>
> -vr_values::vr_values () : vrp_value_range_pool ("Tree VRP value ranges")
> +vr_values::vr_values (bool use_scev_)
> +  : vrp_value_range_pool ("Tree VRP value ranges"), use_scev (use_scev_)
>  {
>    values_propagated = false;
>    num_vr_values = num_ssa_names;
> @@ -2916,7 +2917,8 @@ scev_check:
>       scev_check can be reached from two paths, one is a fall through from above
>       "varying" label, the other is direct goto from code block which tries to
>       avoid infinite simulation.  */
> -  if ((l = loop_containing_stmt (phi))
> +  if (use_scev
> +      && (l = loop_containing_stmt (phi))
>        && l->header == gimple_bb (phi))
>      adjust_range_with_scev (vr_result, l, phi, lhs);
>
> diff --git a/gcc/vr-values.h b/gcc/vr-values.h
> index 124ee6f..816bdc0 100644
> --- a/gcc/vr-values.h
> +++ b/gcc/vr-values.h
> @@ -37,7 +37,7 @@ along with GCC; see the file COPYING3.  If not see
>  class vr_values
>  {
>   public:
> -  vr_values (void);
> +  vr_values (bool);
>    ~vr_values (void);
>
>    value_range *get_value_range (const_tree);
> @@ -109,6 +109,9 @@ class vr_values
>    /* Allocation pools for value_range objects.  */
>    object_allocator<value_range> vrp_value_range_pool;
>
> +  /* Whether or not to use SCEV to refine ranges.  */
> +  bool use_scev;
> +
>    /* This probably belongs in the lattice rather than in here.  */
>    bool values_propagated;
>
>