This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [RFC][IPA-VRP] Add support for IPA VRP in ipa-cp/ipa-prop


Hi Martin,

Thanks for the review. I have revised the patch based on the review. Please see the comments below.

On 15/07/16 22:23, Martin Jambor wrote:
Hi,

thanks for working on extending IPA-CP in this way.  I do have a few
comments though:

On Fri, Jul 15, 2016 at 02:46:50PM +1000, kugan wrote:
Hi,

This patch extends ipa-cp/ipa-prop infrastructure to handle propagation of
VR.
Thanks,

Kugan

gcc/testsuite/ChangeLog:

2016-07-14  Kugan Vivekanandarajah  <kuganv@linaro.org>

         * gcc.dg/ipa/vrp1.c: New test.
         * gcc.dg/ipa/vrp2.c: New test.
         * gcc.dg/ipa/vrp3.c: New test.

gcc/ChangeLog:

2016-07-14  Kugan Vivekanandarajah  <kuganv@linaro.org>

         * common.opt: New option -fipa-vrp.
         * ipa-cp.c (ipa_get_vr_lat): New.
         (ipcp_vr_lattice::print): Likewise.
         (print_all_lattices): Call ipcp_vr_lattice::print.
         (ipcp_vr_lattice::meet_with): New.
         (ipcp_vr_lattice::meet_with_1): Likewise.
         (ipcp_vr_lattice::top_p): Likewise.
         (ipcp_vr_lattice::bottom_p): Likewsie.
         (ipcp_vr_lattice::set_to_bottom): Likewise.
         (set_all_contains_variable): Call VR set_to_bottom.
         (initialize_node_lattices): Init VR lattices.
         (propagate_vr_accross_jump_function): New.
         (propagate_constants_accross_call): Call
         propagate_vr_accross_jump_function.
         (ipcp_store_alignment_results): Rename to
         ipcp_store_alignment_and_vr_results and handke VR.
         * ipa-prop.c (ipa_set_jf_unknown):
         (ipa_compute_jump_functions_for_edge): Handle Value Range.
         (ipa_node_params_t::duplicate): Likewise.
         (ipa_write_jump_function): Likewise.
         (ipa_read_jump_function): Likewise.
         (write_ipcp_transformation_info): Likewise.
         (read_ipcp_transformation_info): Likewise.
         (ipcp_update_alignments): Rename to ipcp_update_vr_and_alignments
         and handle VR.


 From 092cbccd79c3859ff24846bb0e1892ef5d8086bc Mon Sep 17 00:00:00 2001
From: Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org>
Date: Tue, 21 Jun 2016 12:43:01 +1000
Subject: [PATCH 5/6] Add ipa vrp

---
  gcc/common.opt                  |   4 +
  gcc/ipa-cp.c                    | 220 +++++++++++++++++++++++++++++++++++++++-
  gcc/ipa-prop.c                  | 110 ++++++++++++++++++--
  gcc/ipa-prop.h                  |  16 +++
  gcc/testsuite/gcc.dg/ipa/vrp1.c |  32 ++++++
  gcc/testsuite/gcc.dg/ipa/vrp2.c |  35 +++++++
  gcc/testsuite/gcc.dg/ipa/vrp3.c |  30 ++++++
  7 files changed, 433 insertions(+), 14 deletions(-)
  create mode 100644 gcc/testsuite/gcc.dg/ipa/vrp1.c
  create mode 100644 gcc/testsuite/gcc.dg/ipa/vrp2.c
  create mode 100644 gcc/testsuite/gcc.dg/ipa/vrp3.c

diff --git a/gcc/common.opt b/gcc/common.opt
index 29d0e4d..7bf7305 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2475,6 +2475,10 @@ ftree-evrp
  Common Report Var(flag_tree_early_vrp) Init(1) Optimization
  Perform Early Value Range Propagation on trees.

+fipa-vrp
+ommon Report Var(flag_ipa_vrp) Init(1) Optimization

Common

Done.


+Perform IPA Value Range Propagation on trees.

I think that nowadays we should omit the "on trees" part, they are not
particularly useful.


Done.

+
  fsplit-paths
  Common Report Var(flag_split_paths) Init(0) Optimization
  Split paths leading to loop backedges.
diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c
index 4b7f6bb..97cd04b 100644
--- a/gcc/ipa-cp.c
+++ b/gcc/ipa-cp.c
@@ -120,6 +120,7 @@ along with GCC; see the file COPYING3.  If not see
  #include "params.h"
  #include "ipa-inline.h"
  #include "ipa-utils.h"
+#include "tree-vrp.h"

  template <typename valtype> class ipcp_value;

@@ -266,6 +267,25 @@ private:
    bool meet_with_1 (unsigned new_align, unsigned new_misalign);
  };

+/* Lattice of value ranges.  */
+
+class ipcp_vr_lattice
+{
+public:
+  value_range vr;
+
+  inline bool bottom_p () const;
+  inline bool top_p () const;
+  inline bool set_to_bottom ();
+  bool meet_with (const value_range *vr);

Please do not call the parameter the same name as that of a member
variable, that might become very confusing in future.

Done.

+  bool meet_with (const ipcp_vr_lattice &other);
+  void init () { vr.type = VR_UNDEFINED; }
+  void print (FILE * f);
+
+private:
+  bool meet_with_1 (const value_range *vr);

Likewise.

I know that no other classes in the file do, but if you want to
strictly follow the GCC coding style, member vr should be called m_vr.
Perhaps I should add the m_ prefixes to other classes as well, I am
becoming to appreciate them.


Done.

+};
+
  /* Structure containing lattices for a parameter itself and for pieces of
     aggregates that are passed in the parameter or by a reference in a parameter
     plus some other useful flags.  */
@@ -281,6 +301,8 @@ public:
    ipcp_agg_lattice *aggs;
    /* Lattice describing known alignment.  */
    ipcp_alignment_lattice alignment;
+  /* Lattice describing value range.  */
+  ipcp_vr_lattice vr;
    /* Number of aggregate lattices */
    int aggs_count;
    /* True if aggregate data were passed by reference (as opposed to by
@@ -348,6 +370,15 @@ ipa_get_poly_ctx_lat (struct ipa_node_params *info, int i)
    return &plats->ctxlat;
  }

+/* Return the lattice corresponding to the value range of the Ith formal
+   parameter of the function described by INFO.  */

GCC coding style requires (exactly) one blank in between a function
and its preceding comment.

Done.

+static inline ipcp_vr_lattice *
+ipa_get_vr_lat (struct ipa_node_params *info, int i)
+{
+  struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
+  return &plats->vr;
+}
+
  /* Return whether LAT is a lattice with a single constant and without an
     undefined value.  */

@@ -458,6 +489,16 @@ ipcp_alignment_lattice::print (FILE * f)
      fprintf (f, "         Alignment %u, misalignment %u\n", align, misalign);
  }

+/* Print vr lattice to F.  */
+
+void
+ipcp_vr_lattice::print (FILE * f)
+{
+  fprintf (f, "         ");

Please move the above line to the caller.  It will make the function
much more versatile, for example also reasonably callable from the debugger.

Done.

+  dump_value_range (f, &vr);
+  fprintf (f, "\n");
+}
+
  /* Print all ipcp_lattices of all functions to F.  */

  static void
@@ -484,6 +525,7 @@ print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
  	  fprintf (f, "         ctxs: ");
  	  plats->ctxlat.print (f, dump_sources, dump_benefits);
  	  plats->alignment.print (f);
+	  plats->vr.print (f);
  	  if (plats->virt_call)
  	    fprintf (f, "        virt_call flag set\n");

@@ -828,6 +870,77 @@ ipcp_alignment_lattice::set_to_bottom ()
    return true;
  }

+/* Meet the current value of the lattice with described by OTHER
+   lattice.  */
+
+bool
+ipcp_vr_lattice::meet_with (const ipcp_vr_lattice &other)
+{
+  return meet_with_1 (&other.vr);
+}
+
+/* Meet the current value of the lattice with value ranfge described by VR
+   lattice.  */
+
+bool
+ipcp_vr_lattice::meet_with (const value_range *vr)
+{
+  return meet_with_1 (vr);

As I wrote above, the parameter should have a name different from a
member variable.  Moreover, I do not really understand why you need
meet_with_1, why don't you just do the meet here?

Done.

+}
+
+/* Meet the current value of the lattice with value ranfge described by
+   OTHER_VR lattice.  */
+
+bool
+ipcp_vr_lattice::meet_with_1 (const value_range *other_vr)
+{
+  tree min = vr.min, max = vr.max;
+  value_range_type type = vr.type;
+
+  if (bottom_p ())
+    return false;
+
+  if (other_vr->type == VR_VARYING)
+    return set_to_bottom ();
+
+  vrp_meet (&vr, const_cast<value_range *> (other_vr));

The const cast is bad.  Please try to make the second parameter of
vrp_meet const first.  Only if it for some reason proves to be so big
a task that it would unreasonably delay the IPA-VRP implementation,
then explain why that is so and we might leave the cast here.

Done. This also means I am changing tree-vrp. I will send that part of the patch later.

+  if (type != vr.type
+      || min != vr.min
+      || max != vr.max)
+    return true;
+  else
+    return false;
+}
+
+/* Return true if alignment information in the lattice is yet unknown.  */

s/alignment/value range/ or just omit the word completely.

Done.

+
+bool
+ipcp_vr_lattice::top_p () const
+{
+  return vr.type == VR_UNDEFINED;
+}
+
+/* Return true if value range information in the lattice is known to be
+   unusable.  */
+
+bool
+ipcp_vr_lattice::bottom_p () const
+{
+  return vr.type == VR_VARYING;
+}
+
+/* Set value range information in the lattice to bottom.  Return true if it
+   previously was in a different state.  */
+
+bool
+ipcp_vr_lattice::set_to_bottom ()
+{
+  if (vr.type == VR_VARYING)
+    return false;
+  vr.type = VR_VARYING;
+  return true;
+}
+
  /* Meet the current value of the lattice with alignment described by NEW_ALIGN
     and NEW_MISALIGN, assuming that we know the current value is neither TOP nor
     BOTTOM.  Return true if the value of lattice has changed.  */
@@ -915,6 +1028,7 @@ set_all_contains_variable (struct ipcp_param_lattices *plats)
    ret |= plats->ctxlat.set_contains_variable ();
    ret |= set_agg_lats_contain_variable (plats);
    ret |= plats->alignment.set_to_bottom ();
+  ret |= plats->vr.set_to_bottom ();
    return ret;
  }

@@ -985,6 +1099,12 @@ initialize_node_lattices (struct cgraph_node *node)
  	disable = true;
      }

+  for (i = 0; i < ipa_get_param_count (info) ; i++)
+    {
+      struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
+      plats->vr.init ();
+    }
+
    if (disable || variable)
      {
        for (i = 0; i < ipa_get_param_count (info) ; i++)
@@ -996,6 +1116,7 @@ initialize_node_lattices (struct cgraph_node *node)
  	      plats->ctxlat.set_to_bottom ();
  	      set_agg_lats_to_bottom (plats);
  	      plats->alignment.set_to_bottom ();
+	      plats->vr.set_to_bottom ();
  	    }
  	  else
  	    set_all_contains_variable (plats);
@@ -1614,7 +1735,62 @@ propagate_alignment_accross_jump_function (cgraph_edge *cs,
      }
  }

-/* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
+/* Propagate alignments across jump function JFUNC that is associated with

s/alignment/value range/

Done.


+   edge CS and update DEST_LAT accordingly.  */
+static bool
+propagate_vr_accross_jump_function (cgraph_edge *cs,
+				    ipa_jump_func *jfunc,
+				    struct ipcp_param_lattices *dest_plats)
+{
+  struct ipcp_param_lattices *src_lats;
+  enum availability availability;
+  cgraph_node *callee = cs->callee->function_symbol (&availability);
+  struct ipa_node_params *callee_info = IPA_NODE_REF (callee);
+  ipcp_vr_lattice *dest_lat = &dest_plats->vr;
+
+  if (dest_lat->bottom_p ())
+    return false;
+
+  if (callee_info->versionable)
+    return dest_lat->set_to_bottom ();

Why is this necessary?  You do not seem to be doing any cloning based
on VR information.


Well I dont do cloning based on VR. I was trying to be safe here. But, as you mentioned, this is not needed and. I have removed it.


+
+  if (jfunc->type == IPA_JF_PASS_THROUGH)
+    {
+      struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
+      int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
+      src_lats = ipa_get_parm_lattices (caller_info, src_idx);
+
+      if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
+	return dest_lat->meet_with (src_lats->vr);
+    }
+  else if (jfunc->type == IPA_JF_ANCESTOR)
+    {
+      struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
+      int src_idx = ipa_get_jf_ancestor_formal_id (jfunc);
+      src_lats = ipa_get_parm_lattices (caller_info, src_idx);
+
+      return dest_lat->meet_with (src_lats->vr);

I do not understand how come that you are fine with IPA_JF_ANCESTOR
and yet refuse IPA_JF_PASS_THROUGH with a non-NOP operation.

IPA_JF_ANCESTOR is basically an arithmetic jump function for pointers
so I believe you need to punt here or adjust the lattices you meet
with by the offset specified in the jump function.

I have removed the IPA_JF_ANCESTOR part.



+    }
+  else if (jfunc->type == IPA_JF_CONST)
+    {
+      tree val = ipa_get_jf_constant (jfunc);
+      if (TREE_CODE (val) == INTEGER_CST)
+	{
+	  jfunc->vr_known = true;
+	  jfunc->vr.type = VR_RANGE;
+	  jfunc->vr.min = val;
+	  jfunc->vr.max = val;
+	  return dest_lat->meet_with (&jfunc->vr);
+	}
+    }
+
+  if (jfunc->vr_known)
+    return dest_lat->meet_with (&jfunc->vr);
+  else
+    return dest_lat->set_to_bottom ();
+}
+
+/* If DEST_PLATS alvrhas aggregate items, check that aggs_by_ref matches
     NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
     other cases, return false).  If there are no aggregate items, set
     aggs_by_ref to NEW_AGGS_BY_REF.  */
@@ -1963,6 +2139,7 @@ propagate_constants_accross_call (struct cgraph_edge *cs)
  							 &dest_plats->alignment);
  	  ret |= propagate_aggs_accross_jump_function (cs, jump_func,
  						       dest_plats);
+	  ret |= propagate_vr_accross_jump_function (cs, jump_func, dest_plats);
  	}
      }
    for (; i < parms_count; i++)
@@ -4514,7 +4691,7 @@ ipcp_decision_stage (struct ipa_topo_info *topo)
     to the transformation summary.  */

  static void
-ipcp_store_alignment_results (void)
+ipcp_store_alignment_and_vr_results (void)
  {
    cgraph_node *node;

@@ -4523,6 +4700,8 @@ ipcp_store_alignment_results (void)
      ipa_node_params *info = IPA_NODE_REF (node);
      bool dumped_sth = false;
      bool found_useful_result = false;
+    bool do_not_update_alignment = false;
+    bool do_not_update_vr = false;

It is usually easier to work with bool flags that do not have a
negative meaning.  So please turn these into update_alignment_p and
update_vr_p.

Done.



      if (!opt_for_fn (node->decl, flag_ipa_cp_alignment))
        {
@@ -4530,7 +4709,16 @@ ipcp_store_alignment_results (void)
  	  fprintf (dump_file, "Not considering %s for alignment discovery "
  		   "and propagate; -fipa-cp-alignment: disabled.\n",
  		   node->name ());
-	continue;
+	do_not_update_alignment = true;
+      }
+
+    if (!opt_for_fn (node->decl, flag_ipa_vrp))
+      {
+	if (dump_file)
+	  fprintf (dump_file, "Not considering %s for VR discovery "
+		   "and propagate; -fipa-ipa-vrp: disabled.\n",
+		   node->name ());
+	do_not_update_vr = true;
        }

     if (info->ipcp_orig_node)
@@ -4540,13 +4728,21 @@ ipcp_store_alignment_results (void)
     for (unsigned i = 0; i < count ; i++)
       {
         ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
-       if (!plats->alignment.bottom_p ()
+       if (!do_not_update_alignment
+	   && !plats->alignment.bottom_p ()
  	   && !plats->alignment.top_p ())
  	 {
  	   gcc_checking_assert (plats->alignment.align > 0);
  	   found_useful_result = true;
  	   break;
  	 }
+       if (!do_not_update_vr
+	   && !plats->vr.bottom_p ()
+	   && !plats->vr.top_p ())
+	 {
+	   found_useful_result = true;
+	   break;
+	 }
       }
     if (!found_useful_result)
       continue;
@@ -4554,11 +4750,13 @@ ipcp_store_alignment_results (void)
     ipcp_grow_transformations_if_necessary ();
     ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
     vec_safe_reserve_exact (ts->alignments, count);
+   vec_safe_reserve_exact (ts->vr, count);

And here you need to respect update_alignment_p and update_vr_p too
and only create and store results if indicated by them.

Done.


     for (unsigned i = 0; i < count ; i++)
       {
         ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
         ipa_alignment al;
+       ipa_vr vr;

         if (!plats->alignment.bottom_p ()
  	   && !plats->alignment.top_p ())
@@ -4570,7 +4768,19 @@ ipcp_store_alignment_results (void)
         else
  	 al.known = false;

+       if (!plats->vr.bottom_p ()
+	   && !plats->vr.top_p ())
+	 {
+	   vr.known = true;
+	   vr.type = plats->vr.vr.type;
+	   vr.min = plats->vr.vr.min;
+	   vr.max = plats->vr.vr.max;
+	 }
+       else
+	 vr.known = false;
+
         ts->alignments->quick_push (al);
+       ts->vr->quick_push (vr);
         if (!dump_file || !al.known)
  	 continue;
         if (!dumped_sth)
@@ -4617,7 +4827,7 @@ ipcp_driver (void)
    /* Decide what constant propagation and cloning should be performed.  */
    ipcp_decision_stage (&topo);
    /* Store results of alignment propagation. */
-  ipcp_store_alignment_results ();
+  ipcp_store_alignment_and_vr_results ();

    /* Free all IPCP structures.  */
    free_toporder_info (&topo);
diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c
index 132b622..25a4d49 100644
--- a/gcc/ipa-prop.c
+++ b/gcc/ipa-prop.c
@@ -41,6 +41,7 @@ along with GCC; see the file COPYING3.  If not see
  #include "gimplify-me.h"
  #include "gimple-walk.h"
  #include "symbol-summary.h"
+#include "tree-vrp.h"
  #include "ipa-prop.h"
  #include "tree-cfg.h"
  #include "tree-dfa.h"
@@ -381,6 +382,7 @@ ipa_set_jf_unknown (struct ipa_jump_func *jfunc)
  {
    jfunc->type = IPA_JF_UNKNOWN;
    jfunc->alignment.known = false;
+  jfunc->vr_known = false;
  }

  /* Set JFUNC to be a copy of another jmp (to be used by jump function
@@ -1672,7 +1674,21 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
  	    gcc_assert (!jfunc->alignment.known);
  	}
        else
-	gcc_assert (!jfunc->alignment.known);

It seems that this assert was removed by accident?  (It is not
particularly useful and should probably be turned into a gcc_checking
assert but anyway...)

Done.

+	{
+	  wide_int min, max;
+	  value_range_type type;
+	  if (TREE_CODE (arg) == SSA_NAME
+	      && (type = get_range_info (arg, &min, &max))
+	      && (type == VR_RANGE || type == VR_ANTI_RANGE))
+	    {
+	      jfunc->vr_known = true;
+	      jfunc->vr.type = type;
+	      jfunc->vr.min = wide_int_to_tree (TREE_TYPE (arg), min);
+	      jfunc->vr.max = wide_int_to_tree (TREE_TYPE (arg), max);

Well, if you do these conversions anyway, it might make sense to do
the whole IPA part in wide_int and convert back to trees only in the
transformation phase?  I acknowledge that I do not know how friendly
wide_int is to streaming.  Or is there any other reason to do it on
trees?


wide_int streaming is not handled now. Once that is the case, I can change it to wide_int.
I can add a TODO and implement it as follow up if you prefer that.


+	    }
+	  else
+	    gcc_assert (!jfunc->vr_known);

You are putting in the jump function creation here, into a non-pointer
branch.  Does that mean the IPA-VRP is not supposed to work for
pointers?  That would be a shame because I hoped it would also
propagate non-NULL information which should be particularly useful.

As of now SSA_NAMEs set value range for non-pointers as range_info and ptr_info are unions. If we can find a spare bit in ptr_info, we can infact propagate non-null info. I will look into it once this part is done.


In any event, consider moving this code to the
"if (TREE_CODE (arg) == SSA_NAME)" branch slightly below this.

+	}

        if (is_gimple_ip_invariant (arg)
  	  || (TREE_CODE (arg) == VAR_DECL
@@ -3679,16 +3695,24 @@ ipa_node_params_t::duplicate(cgraph_node *src, cgraph_node *dst,

    ipcp_transformation_summary *src_trans = ipcp_get_transformation_summary (src);

-  if (src_trans && vec_safe_length (src_trans->alignments) > 0)
+  if (src_trans
+      && (vec_safe_length (src_trans->alignments) > 0
+	  || vec_safe_length (src_trans->vr) > 0))
      {
        ipcp_grow_transformations_if_necessary ();
        src_trans = ipcp_get_transformation_summary (src);
        const vec<ipa_alignment, va_gc> *src_alignments = src_trans->alignments;
+      const vec<ipa_vr, va_gc> *src_vr = src_trans->vr;
        vec<ipa_alignment, va_gc> *&dst_alignments
  	= ipcp_get_transformation_summary (dst)->alignments;
+      vec<ipa_vr, va_gc> *&dst_vr
+	= ipcp_get_transformation_summary (dst)->vr;
        vec_safe_reserve_exact (dst_alignments, src_alignments->length ());
+      vec_safe_reserve_exact (dst_vr, src_vr->length ());
        for (unsigned i = 0; i < src_alignments->length (); ++i)
  	dst_alignments->quick_push ((*src_alignments)[i]);
+      for (unsigned i = 0; i < src_vr->length (); ++i)
+	dst_vr->quick_push ((*src_vr)[i]);
      }
  }

@@ -4609,6 +4633,14 @@ ipa_write_jump_function (struct output_block *ob,
        streamer_write_uhwi (ob, jump_func->alignment.align);
        streamer_write_uhwi (ob, jump_func->alignment.misalign);
      }
+  bp_pack_value (&bp, jump_func->vr_known, 1);
+  streamer_write_bitpack (&bp);
+  if (jump_func->vr_known)
+    {
+      streamer_write_enum (ob->main_stream, value_rang_type, VR_LAST, jump_func->vr.type);
+      stream_write_tree (ob, jump_func->vr.min, true);
+      stream_write_tree (ob, jump_func->vr.max, true);
+    }
  }

  /* Read in jump function JUMP_FUNC from IB.  */
@@ -4685,6 +4717,17 @@ ipa_read_jump_function (struct lto_input_block *ib,
      }
    else
      jump_func->alignment.known = false;
+  struct bitpack_d vr_bp = streamer_read_bitpack (ib);
+  bool vr_known = bp_unpack_value (&vr_bp, 1);
+  if (vr_known)
+    {
+      jump_func->vr_known = true;
+      jump_func->vr.type = streamer_read_enum (ib, value_range_type, VR_LAST);
+      jump_func->vr.min = stream_read_tree (ib, data_in);
+      jump_func->vr.max = stream_read_tree (ib, data_in);
+    }
+  else
+    jump_func->vr_known = false;
  }

  /* Stream out parts of cgraph_indirect_call_info corresponding to CS that are
@@ -5027,7 +5070,9 @@ write_ipcp_transformation_info (output_block *ob, cgraph_node *node)
      }

    ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
-  if (ts && vec_safe_length (ts->alignments) > 0)
+  if (ts
+      && (vec_safe_length (ts->alignments) > 0
+	  || vec_safe_length (ts->alignments) > 0))
      {
        count = ts->alignments->length ();

@@ -5035,6 +5080,7 @@ write_ipcp_transformation_info (output_block *ob, cgraph_node *node)
        for (unsigned i = 0; i < count; ++i)
  	{
  	  ipa_alignment *parm_al = &(*ts->alignments)[i];
+	  ipa_vr *parm_vr = &(*ts->vr)[i];

  	  struct bitpack_d bp;
  	  bp = bitpack_create (ob->main_stream);
@@ -5046,6 +5092,16 @@ write_ipcp_transformation_info (output_block *ob, cgraph_node *node)
  	      streamer_write_hwi_in_range (ob->main_stream, 0, parm_al->align,
  					   parm_al->misalign);
  	    }
+	  bp = bitpack_create (ob->main_stream);
+	  bp_pack_value (&bp, parm_vr->known, 1);
+	  streamer_write_bitpack (&bp);
+	  if (parm_vr->known)
+	    {
+	      streamer_write_enum (ob->main_stream, value_rang_type,
+				   VR_LAST, parm_vr->type);
+	      stream_write_tree (ob, parm_vr->min, true);
+	      stream_write_tree (ob, parm_vr->max, true);
+	    }
  	}
      }
    else
@@ -5085,11 +5141,14 @@ read_ipcp_transformation_info (lto_input_block *ib, cgraph_node *node,

        ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
        vec_safe_grow_cleared (ts->alignments, count);
+      vec_safe_grow_cleared (ts->vr, count);

        for (i = 0; i < count; i++)
  	{
  	  ipa_alignment *parm_al;
+	  ipa_vr *parm_vr;
  	  parm_al = &(*ts->alignments)[i];
+	  parm_vr = &(*ts->vr)[i];
  	  struct bitpack_d bp;
  	  bp = streamer_read_bitpack (ib);
  	  parm_al->known = bp_unpack_value (&bp, 1);
@@ -5100,6 +5159,14 @@ read_ipcp_transformation_info (lto_input_block *ib, cgraph_node *node,
  		= streamer_read_hwi_in_range (ib, "ipa-prop misalign",
  					      0, parm_al->align);
  	    }
+	  bp = streamer_read_bitpack (ib);
+	  parm_vr->known = bp_unpack_value (&bp, 1);
+	  if (parm_vr->known)
+	    {
+	      parm_vr->type = streamer_read_enum (ib, value_range_type, VR_LAST);
+	      parm_vr->min = stream_read_tree (ib, data_in);
+	      parm_vr->max = stream_read_tree (ib, data_in);
+	    }
  	}
      }
  }
@@ -5356,15 +5423,17 @@ ipcp_modif_dom_walker::before_dom_children (basic_block bb)
     ipcp_transformation_summary.  */

  static void
-ipcp_update_alignments (struct cgraph_node *node)
+ipcp_update_vr_and_alignments (struct cgraph_node *node)
  {
    tree fndecl = node->decl;
    tree parm = DECL_ARGUMENTS (fndecl);
    tree next_parm = parm;
    ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
-  if (!ts || vec_safe_length (ts->alignments) == 0)
+  if (!ts || ((vec_safe_length (ts->alignments) == 0)
+	      && (vec_safe_length (ts->vr) == 0)))
      return;
    const vec<ipa_alignment, va_gc> &alignments = *ts->alignments;
+  const vec<ipa_vr, va_gc> &vr = *ts->vr;
    unsigned count = alignments.length ();

    for (unsigned i = 0; i < count; ++i, parm = next_parm)
@@ -5374,13 +5443,36 @@ ipcp_update_alignments (struct cgraph_node *node)
  	continue;
        gcc_checking_assert (parm);
        next_parm = DECL_CHAIN (parm);
-
-      if (!alignments[i].known || !is_gimple_reg (parm))
-	continue;

Please leave the is_gimple_reg check here.  I suppose that if parm is
not a gimple register, the following will always return a NULL ddef,
but non-registers do not have SSA names so let's not even try.

Done.


        tree ddef = ssa_default_def (DECL_STRUCT_FUNCTION (node->decl), parm);
        if (!ddef)
  	continue;

+      if (cgraph_local_p (node)
+	  && vr[i].known
+	  && INTEGRAL_TYPE_P (TREE_TYPE (ddef))
+	  && !POINTER_TYPE_P (TREE_TYPE (ddef))
+	  && (vr[i].type == VR_RANGE || vr[i].type == VR_ANTI_RANGE)
+	  && TREE_CODE (vr[i].min) == INTEGER_CST
+	  && TREE_CODE (vr[i].max) == INTEGER_CST)
+	{
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "Setting value range of param %u ", i);
+	      fprintf (dump_file, "%s[", (vr[i].type == VR_ANTI_RANGE) ? "~" : "");
+	      print_generic_expr (dump_file, vr[i].min, 0);
+	      fprintf (dump_file, ", ");
+	      print_generic_expr (dump_file, vr[i].max, 0);
+	      fprintf (dump_file, "]\n");
+	    }
+	  set_range_info (ddef, vr[i].type,
+			  wide_int_to_tree (TREE_TYPE (ddef), vr[i].min),
+			  wide_int_to_tree (TREE_TYPE (ddef), vr[i].max));

I don't understand, vr is a vector containing ipa_vr elements which is
a structure in which min and max fields are already trees.  So why the
convert?  (And how can this even compile?  I suppose I am missing
something obvious here but again, if you only work with integers and
go through a wide-int anyway, I suppose ipa_vr should just contain
wide-ints, if we can stream them).

SSA_NAMEs have range into in wide_int. To convert tree into the right precision, I am doing this. I have seen similar uses elsewhere.


+
+	}
+
+      if (!alignments[i].known || !is_gimple_reg (parm))
+	continue;
+
        if (dump_file)
  	fprintf (dump_file, "  Adjusting alignment of param %u to %u, "
  		 "misalignment to %u\n", i, alignments[i].align,
@@ -5422,7 +5514,7 @@ ipcp_transform_function (struct cgraph_node *node)
      fprintf (dump_file, "Modification phase of node %s/%i\n",
  	     node->name (), node->order);

-  ipcp_update_alignments (node);
+  ipcp_update_vr_and_alignments (node);
    aggval = ipa_get_agg_replacements_for_node (node);
    if (!aggval)
        return 0;
diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
index e32d078..490be5f 100644
--- a/gcc/ipa-prop.h
+++ b/gcc/ipa-prop.h
@@ -154,6 +154,16 @@ struct GTY(()) ipa_alignment
    unsigned misalign;
  };

+/* Info about value ranges. */

Missing newline.

Done.

+struct GTY(()) ipa_vr
+{
+  /* The data fields below are valid only if known is true.  */
+  bool known;
+  enum value_range_type type;
+  tree GTY ((skip)) min;
+  tree GTY ((skip)) max;

The GTY((skip)) seems wrong to me.  What are the other places the
values are referenced from or why did you decide to put it there?

Indeed. Removed it.

+};
+
  /* A jump function for a callsite represents the values passed as actual
     arguments of the callsite. See enum jump_func_type for the various
     types of jump functions supported.  */
@@ -166,6 +176,10 @@ struct GTY (()) ipa_jump_func
    /* Information about alignment of pointers. */
    struct ipa_alignment alignment;

+  /* Information about value range. */
+  bool vr_known;
+  value_range vr;
+
    enum jump_func_type type;
    /* Represents a value of a jump function.  pass_through is used only in jump
       function context.  constant represents the actual constant in constant jump
@@ -482,6 +496,8 @@ struct GTY(()) ipcp_transformation_summary
    ipa_agg_replacement_value *agg_values;
    /* Alignment information for pointers.  */
    vec<ipa_alignment, va_gc> *alignments;
+  /* Value range information.  */
+  vec<ipa_vr, va_gc> *vr;
  };

Thanks,
Kugan



Thanks,

Martin

>From 8613b15365e4ce224d4f660d832d22997662da8c Mon Sep 17 00:00:00 2001
From: Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org>
Date: Tue, 21 Jun 2016 12:43:01 +1000
Subject: [PATCH 5/6] Add ipa vrp

---
 gcc/common.opt                  |   4 +
 gcc/ipa-cp.c                    | 241 +++++++++++++++++++++++++++++++++++++---
 gcc/ipa-prop.c                  | 126 +++++++++++++++++++--
 gcc/ipa-prop.h                  |  17 +++
 gcc/testsuite/gcc.dg/ipa/vrp1.c |  32 ++++++
 gcc/testsuite/gcc.dg/ipa/vrp2.c |  35 ++++++
 gcc/testsuite/gcc.dg/ipa/vrp3.c |  30 +++++
 7 files changed, 461 insertions(+), 24 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/ipa/vrp1.c
 create mode 100644 gcc/testsuite/gcc.dg/ipa/vrp2.c
 create mode 100644 gcc/testsuite/gcc.dg/ipa/vrp3.c

diff --git a/gcc/common.opt b/gcc/common.opt
index 29d0e4d..7e3ab5f 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2475,6 +2475,10 @@ ftree-evrp
 Common Report Var(flag_tree_early_vrp) Init(1) Optimization
 Perform Early Value Range Propagation on trees.
 
+fipa-vrp
+Common Report Var(flag_ipa_vrp) Init(1) Optimization
+Perform IPA Value Range Propagation.
+
 fsplit-paths
 Common Report Var(flag_split_paths) Init(0) Optimization
 Split paths leading to loop backedges.
diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c
index 4b7f6bb..30b1f2e 100644
--- a/gcc/ipa-cp.c
+++ b/gcc/ipa-cp.c
@@ -120,6 +120,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "params.h"
 #include "ipa-inline.h"
 #include "ipa-utils.h"
+#include "tree-vrp.h"
 
 template <typename valtype> class ipcp_value;
 
@@ -266,6 +267,25 @@ private:
   bool meet_with_1 (unsigned new_align, unsigned new_misalign);
 };
 
+/* Lattice of value ranges.  */
+
+class ipcp_vr_lattice
+{
+public:
+  value_range m_vr;
+
+  inline bool bottom_p () const;
+  inline bool top_p () const;
+  inline bool set_to_bottom ();
+  bool meet_with (const value_range *p_vr);
+  bool meet_with (const ipcp_vr_lattice &other);
+  void init () { m_vr.type = VR_UNDEFINED; }
+  void print (FILE * f);
+
+private:
+  bool meet_with_1 (const value_range *other_vr);
+};
+
 /* Structure containing lattices for a parameter itself and for pieces of
    aggregates that are passed in the parameter or by a reference in a parameter
    plus some other useful flags.  */
@@ -281,6 +301,8 @@ public:
   ipcp_agg_lattice *aggs;
   /* Lattice describing known alignment.  */
   ipcp_alignment_lattice alignment;
+  /* Lattice describing value range.  */
+  ipcp_vr_lattice m_value_range;
   /* Number of aggregate lattices */
   int aggs_count;
   /* True if aggregate data were passed by reference (as opposed to by
@@ -348,6 +370,16 @@ ipa_get_poly_ctx_lat (struct ipa_node_params *info, int i)
   return &plats->ctxlat;
 }
 
+/* Return the lattice corresponding to the value range of the Ith formal
+   parameter of the function described by INFO.  */
+
+static inline ipcp_vr_lattice *
+ipa_get_vr_lat (struct ipa_node_params *info, int i)
+{
+  struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
+  return &plats->m_value_range;
+}
+
 /* Return whether LAT is a lattice with a single constant and without an
    undefined value.  */
 
@@ -458,6 +490,14 @@ ipcp_alignment_lattice::print (FILE * f)
     fprintf (f, "         Alignment %u, misalignment %u\n", align, misalign);
 }
 
+/* Print value range lattice to F.  */
+
+void
+ipcp_vr_lattice::print (FILE * f)
+{
+  dump_value_range (f, &m_vr);
+}
+
 /* Print all ipcp_lattices of all functions to F.  */
 
 static void
@@ -484,6 +524,9 @@ print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
 	  fprintf (f, "         ctxs: ");
 	  plats->ctxlat.print (f, dump_sources, dump_benefits);
 	  plats->alignment.print (f);
+	  fprintf (f, "         ");
+	  plats->m_value_range.print (f);
+	  fprintf (f, "\n");
 	  if (plats->virt_call)
 	    fprintf (f, "        virt_call flag set\n");
 
@@ -828,6 +871,77 @@ ipcp_alignment_lattice::set_to_bottom ()
   return true;
 }
 
+/* Meet the current value of the lattice with described by OTHER
+   lattice.  */
+
+bool
+ipcp_vr_lattice::meet_with (const ipcp_vr_lattice &other)
+{
+  return meet_with_1 (&other.m_vr);
+}
+
+/* Meet the current value of the lattice with value ranfge described by VR
+   lattice.  */
+
+bool
+ipcp_vr_lattice::meet_with (const value_range *p_vr)
+{
+  return meet_with_1 (p_vr);
+}
+
+/* Meet the current value of the lattice with value ranfge described by
+   OTHER_VR lattice.  */
+
+bool
+ipcp_vr_lattice::meet_with_1 (const value_range *other_vr)
+{
+  tree min = m_vr.min, max = m_vr.max;
+  value_range_type type = m_vr.type;
+
+  if (bottom_p ())
+    return false;
+
+  if (other_vr->type == VR_VARYING)
+    return set_to_bottom ();
+
+  vrp_meet (&m_vr, other_vr);
+  if (type != m_vr.type
+      || min != m_vr.min
+      || max != m_vr.max)
+    return true;
+  else
+    return false;
+}
+
+/* Return true if value range information in the lattice is yet unknown.  */
+
+bool
+ipcp_vr_lattice::top_p () const
+{
+  return m_vr.type == VR_UNDEFINED;
+}
+
+/* Return true if value range information in the lattice is known to be
+   unusable.  */
+
+bool
+ipcp_vr_lattice::bottom_p () const
+{
+  return m_vr.type == VR_VARYING;
+}
+
+/* Set value range information in the lattice to bottom.  Return true if it
+   previously was in a different state.  */
+
+bool
+ipcp_vr_lattice::set_to_bottom ()
+{
+  if (m_vr.type == VR_VARYING)
+    return false;
+  m_vr.type = VR_VARYING;
+  return true;
+}
+
 /* Meet the current value of the lattice with alignment described by NEW_ALIGN
    and NEW_MISALIGN, assuming that we know the current value is neither TOP nor
    BOTTOM.  Return true if the value of lattice has changed.  */
@@ -915,6 +1029,7 @@ set_all_contains_variable (struct ipcp_param_lattices *plats)
   ret |= plats->ctxlat.set_contains_variable ();
   ret |= set_agg_lats_contain_variable (plats);
   ret |= plats->alignment.set_to_bottom ();
+  ret |= plats->m_value_range.set_to_bottom ();
   return ret;
 }
 
@@ -985,6 +1100,12 @@ initialize_node_lattices (struct cgraph_node *node)
 	disable = true;
     }
 
+  for (i = 0; i < ipa_get_param_count (info) ; i++)
+    {
+      struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
+      plats->m_value_range.init ();
+    }
+
   if (disable || variable)
     {
       for (i = 0; i < ipa_get_param_count (info) ; i++)
@@ -996,6 +1117,7 @@ initialize_node_lattices (struct cgraph_node *node)
 	      plats->ctxlat.set_to_bottom ();
 	      set_agg_lats_to_bottom (plats);
 	      plats->alignment.set_to_bottom ();
+	      plats->m_value_range.set_to_bottom ();
 	    }
 	  else
 	    set_all_contains_variable (plats);
@@ -1614,7 +1736,49 @@ propagate_alignment_accross_jump_function (cgraph_edge *cs,
     }
 }
 
-/* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches
+/* Propagate value range across jump function JFUNC that is associated with
+   edge CS and update DEST_PLATS accordingly.  */
+
+static bool
+propagate_vr_accross_jump_function (cgraph_edge *cs,
+				    ipa_jump_func *jfunc,
+				    struct ipcp_param_lattices *dest_plats)
+{
+  struct ipcp_param_lattices *src_lats;
+  ipcp_vr_lattice *dest_lat = &dest_plats->m_value_range;
+
+  if (dest_lat->bottom_p ())
+    return false;
+
+  if (jfunc->type == IPA_JF_PASS_THROUGH)
+    {
+      struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
+      int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
+      src_lats = ipa_get_parm_lattices (caller_info, src_idx);
+
+      if (ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
+	return dest_lat->meet_with (src_lats->m_value_range);
+    }
+  else if (jfunc->type == IPA_JF_CONST)
+    {
+      tree val = ipa_get_jf_constant (jfunc);
+      if (TREE_CODE (val) == INTEGER_CST)
+	{
+	  jfunc->vr_known = true;
+	  jfunc->m_vr.type = VR_RANGE;
+	  jfunc->m_vr.min = val;
+	  jfunc->m_vr.max = val;
+	  return dest_lat->meet_with (&jfunc->m_vr);
+	}
+    }
+
+  if (jfunc->vr_known)
+    return dest_lat->meet_with (&jfunc->m_vr);
+  else
+    return dest_lat->set_to_bottom ();
+}
+
+/* If DEST_PLATS alvrhas aggregate items, check that aggs_by_ref matches
    NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all
    other cases, return false).  If there are no aggregate items, set
    aggs_by_ref to NEW_AGGS_BY_REF.  */
@@ -1963,6 +2127,7 @@ propagate_constants_accross_call (struct cgraph_edge *cs)
 							 &dest_plats->alignment);
 	  ret |= propagate_aggs_accross_jump_function (cs, jump_func,
 						       dest_plats);
+	  ret |= propagate_vr_accross_jump_function (cs, jump_func, dest_plats);
 	}
     }
   for (; i < parms_count; i++)
@@ -4514,7 +4679,7 @@ ipcp_decision_stage (struct ipa_topo_info *topo)
    to the transformation summary.  */
 
 static void
-ipcp_store_alignment_results (void)
+ipcp_store_alignment_and_vr_results (void)
 {
   cgraph_node *node;
 
@@ -4523,6 +4688,8 @@ ipcp_store_alignment_results (void)
     ipa_node_params *info = IPA_NODE_REF (node);
     bool dumped_sth = false;
     bool found_useful_result = false;
+    bool update_alignment_p = true;
+    bool update_vr_p = true;
 
     if (!opt_for_fn (node->decl, flag_ipa_cp_alignment))
       {
@@ -4530,7 +4697,16 @@ ipcp_store_alignment_results (void)
 	  fprintf (dump_file, "Not considering %s for alignment discovery "
 		   "and propagate; -fipa-cp-alignment: disabled.\n",
 		   node->name ());
-	continue;
+	update_alignment_p = false;
+      }
+
+    if (!opt_for_fn (node->decl, flag_ipa_vrp))
+      {
+	if (dump_file)
+	  fprintf (dump_file, "Not considering %s for VR discovery "
+		   "and propagate; -fipa-ipa-vrp: disabled.\n",
+		   node->name ());
+	update_vr_p = false;
       }
 
    if (info->ipcp_orig_node)
@@ -4540,37 +4716,72 @@ ipcp_store_alignment_results (void)
    for (unsigned i = 0; i < count ; i++)
      {
        ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
-       if (!plats->alignment.bottom_p ()
+       if (update_alignment_p
+	   && !plats->alignment.bottom_p ()
 	   && !plats->alignment.top_p ())
 	 {
 	   gcc_checking_assert (plats->alignment.align > 0);
 	   found_useful_result = true;
 	   break;
 	 }
+       if (update_vr_p
+	   && !plats->m_value_range.bottom_p ()
+	   && !plats->m_value_range.top_p ())
+	 {
+	   found_useful_result = true;
+	   break;
+	 }
      }
    if (!found_useful_result)
      continue;
 
    ipcp_grow_transformations_if_necessary ();
    ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
-   vec_safe_reserve_exact (ts->alignments, count);
+   if (update_alignment_p)
+     vec_safe_reserve_exact (ts->alignments, count);
+   if (update_vr_p)
+     vec_safe_reserve_exact (ts->m_vr, count);
 
    for (unsigned i = 0; i < count ; i++)
      {
        ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
        ipa_alignment al;
+       ipa_vr vr;
 
-       if (!plats->alignment.bottom_p ()
-	   && !plats->alignment.top_p ())
+       if (update_alignment_p)
+	 {
+	   if (!plats->alignment.bottom_p ()
+	       && !plats->alignment.top_p ())
+	     {
+	       al.known = true;
+	       al.align = plats->alignment.align;
+	       al.misalign = plats->alignment.misalign;
+	     }
+	   else
+	     al.known = false;
+	   ts->alignments->quick_push (al);
+	 }
+
+       if (update_vr_p)
 	 {
-	   al.known = true;
-	   al.align = plats->alignment.align;
-	   al.misalign = plats->alignment.misalign;
+	   if (!plats->m_value_range.bottom_p ()
+	       && !plats->m_value_range.top_p ())
+	     {
+	       vr.known = true;
+	       vr.type = plats->m_value_range.m_vr.type;
+	       vr.min = plats->m_value_range.m_vr.min;
+	       vr.max = plats->m_value_range.m_vr.max;
+	     }
+	   else
+	     {
+	       vr.known = false;
+	       vr.type = VR_VARYING;
+	       vr.min = NULL_TREE;
+	       vr.max = NULL_TREE;
+	     }
+	   ts->m_vr->quick_push (vr);
 	 }
-       else
-	 al.known = false;
 
-       ts->alignments->quick_push (al);
        if (!dump_file || !al.known)
 	 continue;
        if (!dumped_sth)
@@ -4616,8 +4827,8 @@ ipcp_driver (void)
   ipcp_propagate_stage (&topo);
   /* Decide what constant propagation and cloning should be performed.  */
   ipcp_decision_stage (&topo);
-  /* Store results of alignment propagation. */
-  ipcp_store_alignment_results ();
+  /* Store results of alignment and value range propagation.  */
+  ipcp_store_alignment_and_vr_results ();
 
   /* Free all IPCP structures.  */
   free_toporder_info (&topo);
diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c
index 132b622..a8f6b23 100644
--- a/gcc/ipa-prop.c
+++ b/gcc/ipa-prop.c
@@ -41,6 +41,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimplify-me.h"
 #include "gimple-walk.h"
 #include "symbol-summary.h"
+#include "tree-vrp.h"
 #include "ipa-prop.h"
 #include "tree-cfg.h"
 #include "tree-dfa.h"
@@ -302,6 +303,18 @@ ipa_print_node_jump_functions_for_edge (FILE *f, struct cgraph_edge *cs)
 	}
       else
 	fprintf (f, "         Unknown alignment\n");
+
+      if (jump_func->vr_known)
+	{
+	  fprintf (f, "         VR  ");
+	  fprintf (f, "%s[", (jump_func->m_vr.type == VR_ANTI_RANGE) ? "~" : "");
+	  print_generic_expr (f, jump_func->m_vr.min, 0);
+	  fprintf (f, ", ");
+	  print_generic_expr (f, jump_func->m_vr.max, 0);
+	  fprintf (f, "]\n");
+	}
+      else
+	fprintf (f, "         Unknown VR\n");
     }
 }
 
@@ -381,6 +394,7 @@ ipa_set_jf_unknown (struct ipa_jump_func *jfunc)
 {
   jfunc->type = IPA_JF_UNKNOWN;
   jfunc->alignment.known = false;
+  jfunc->vr_known = false;
 }
 
 /* Set JFUNC to be a copy of another jmp (to be used by jump function
@@ -1670,9 +1684,25 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
 	    }
 	  else
 	    gcc_assert (!jfunc->alignment.known);
+	  gcc_assert (!jfunc->vr_known);
 	}
       else
-	gcc_assert (!jfunc->alignment.known);
+	{
+	  wide_int min, max;
+	  value_range_type type;
+	  if (TREE_CODE (arg) == SSA_NAME
+	      && (type = get_range_info (arg, &min, &max))
+	      && (type == VR_RANGE || type == VR_ANTI_RANGE))
+	    {
+	      jfunc->vr_known = true;
+	      jfunc->m_vr.type = type;
+	      jfunc->m_vr.min = wide_int_to_tree (TREE_TYPE (arg), min);
+	      jfunc->m_vr.max = wide_int_to_tree (TREE_TYPE (arg), max);
+	    }
+	  else
+	    gcc_assert (!jfunc->vr_known);
+	  gcc_assert (!jfunc->alignment.known);
+	}
 
       if (is_gimple_ip_invariant (arg)
 	  || (TREE_CODE (arg) == VAR_DECL
@@ -3679,16 +3709,24 @@ ipa_node_params_t::duplicate(cgraph_node *src, cgraph_node *dst,
 
   ipcp_transformation_summary *src_trans = ipcp_get_transformation_summary (src);
 
-  if (src_trans && vec_safe_length (src_trans->alignments) > 0)
+  if (src_trans
+      && (vec_safe_length (src_trans->alignments) > 0
+	  || vec_safe_length (src_trans->m_vr) > 0))
     {
       ipcp_grow_transformations_if_necessary ();
       src_trans = ipcp_get_transformation_summary (src);
       const vec<ipa_alignment, va_gc> *src_alignments = src_trans->alignments;
+      const vec<ipa_vr, va_gc> *src_vr = src_trans->m_vr;
       vec<ipa_alignment, va_gc> *&dst_alignments
 	= ipcp_get_transformation_summary (dst)->alignments;
+      vec<ipa_vr, va_gc> *&dst_vr
+	= ipcp_get_transformation_summary (dst)->m_vr;
       vec_safe_reserve_exact (dst_alignments, src_alignments->length ());
+      vec_safe_reserve_exact (dst_vr, src_vr->length ());
       for (unsigned i = 0; i < src_alignments->length (); ++i)
 	dst_alignments->quick_push ((*src_alignments)[i]);
+      for (unsigned i = 0; i < src_vr->length (); ++i)
+	dst_vr->quick_push ((*src_vr)[i]);
     }
 }
 
@@ -4609,6 +4647,14 @@ ipa_write_jump_function (struct output_block *ob,
       streamer_write_uhwi (ob, jump_func->alignment.align);
       streamer_write_uhwi (ob, jump_func->alignment.misalign);
     }
+  bp_pack_value (&bp, jump_func->vr_known, 1);
+  streamer_write_bitpack (&bp);
+  if (jump_func->vr_known)
+    {
+      streamer_write_enum (ob->main_stream, value_rang_type, VR_LAST, jump_func->m_vr.type);
+      stream_write_tree (ob, jump_func->m_vr.min, true);
+      stream_write_tree (ob, jump_func->m_vr.max, true);
+    }
 }
 
 /* Read in jump function JUMP_FUNC from IB.  */
@@ -4685,6 +4731,17 @@ ipa_read_jump_function (struct lto_input_block *ib,
     }
   else
     jump_func->alignment.known = false;
+  struct bitpack_d vr_bp = streamer_read_bitpack (ib);
+  bool vr_known = bp_unpack_value (&vr_bp, 1);
+  if (vr_known)
+    {
+      jump_func->vr_known = true;
+      jump_func->m_vr.type = streamer_read_enum (ib, value_range_type, VR_LAST);
+      jump_func->m_vr.min = stream_read_tree (ib, data_in);
+      jump_func->m_vr.max = stream_read_tree (ib, data_in);
+    }
+  else
+    jump_func->vr_known = false;
 }
 
 /* Stream out parts of cgraph_indirect_call_info corresponding to CS that are
@@ -5027,7 +5084,9 @@ write_ipcp_transformation_info (output_block *ob, cgraph_node *node)
     }
 
   ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
-  if (ts && vec_safe_length (ts->alignments) > 0)
+  if (ts
+      && ((ts->alignments && vec_safe_length (ts->alignments) > 0)
+	  || (ts->m_vr && vec_safe_length (ts->m_vr) > 0)))
     {
       count = ts->alignments->length ();
 
@@ -5035,6 +5094,7 @@ write_ipcp_transformation_info (output_block *ob, cgraph_node *node)
       for (unsigned i = 0; i < count; ++i)
 	{
 	  ipa_alignment *parm_al = &(*ts->alignments)[i];
+	  ipa_vr *parm_vr = &(*ts->m_vr)[i];
 
 	  struct bitpack_d bp;
 	  bp = bitpack_create (ob->main_stream);
@@ -5046,6 +5106,16 @@ write_ipcp_transformation_info (output_block *ob, cgraph_node *node)
 	      streamer_write_hwi_in_range (ob->main_stream, 0, parm_al->align,
 					   parm_al->misalign);
 	    }
+	  bp = bitpack_create (ob->main_stream);
+	  bp_pack_value (&bp, parm_vr->known, 1);
+	  streamer_write_bitpack (&bp);
+	  if (parm_vr->known)
+	    {
+	      streamer_write_enum (ob->main_stream, value_rang_type,
+				   VR_LAST, parm_vr->type);
+	      stream_write_tree (ob, parm_vr->min, true);
+	      stream_write_tree (ob, parm_vr->max, true);
+	    }
 	}
     }
   else
@@ -5085,11 +5155,14 @@ read_ipcp_transformation_info (lto_input_block *ib, cgraph_node *node,
 
       ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
       vec_safe_grow_cleared (ts->alignments, count);
+      vec_safe_grow_cleared (ts->m_vr, count);
 
       for (i = 0; i < count; i++)
 	{
 	  ipa_alignment *parm_al;
+	  ipa_vr *parm_vr;
 	  parm_al = &(*ts->alignments)[i];
+	  parm_vr = &(*ts->m_vr)[i];
 	  struct bitpack_d bp;
 	  bp = streamer_read_bitpack (ib);
 	  parm_al->known = bp_unpack_value (&bp, 1);
@@ -5100,6 +5173,14 @@ read_ipcp_transformation_info (lto_input_block *ib, cgraph_node *node,
 		= streamer_read_hwi_in_range (ib, "ipa-prop misalign",
 					      0, parm_al->align);
 	    }
+	  bp = streamer_read_bitpack (ib);
+	  parm_vr->known = bp_unpack_value (&bp, 1);
+	  if (parm_vr->known)
+	    {
+	      parm_vr->type = streamer_read_enum (ib, value_range_type, VR_LAST);
+	      parm_vr->min = stream_read_tree (ib, data_in);
+	      parm_vr->max = stream_read_tree (ib, data_in);
+	    }
 	}
     }
 }
@@ -5356,15 +5437,18 @@ ipcp_modif_dom_walker::before_dom_children (basic_block bb)
    ipcp_transformation_summary.  */
 
 static void
-ipcp_update_alignments (struct cgraph_node *node)
+ipcp_update_vr_and_alignments (struct cgraph_node *node)
 {
   tree fndecl = node->decl;
   tree parm = DECL_ARGUMENTS (fndecl);
   tree next_parm = parm;
   ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node);
-  if (!ts || vec_safe_length (ts->alignments) == 0)
+  if (!ts
+      || ((!ts->alignments || vec_safe_length (ts->alignments) == 0)
+	  && (!ts->m_vr || vec_safe_length (ts->m_vr) == 0)))
     return;
   const vec<ipa_alignment, va_gc> &alignments = *ts->alignments;
+  const vec<ipa_vr, va_gc> &vr = *ts->m_vr;
   unsigned count = alignments.length ();
 
   for (unsigned i = 0; i < count; ++i, parm = next_parm)
@@ -5374,11 +5458,35 @@ ipcp_update_alignments (struct cgraph_node *node)
 	continue;
       gcc_checking_assert (parm);
       next_parm = DECL_CHAIN (parm);
+      tree ddef = ssa_default_def (DECL_STRUCT_FUNCTION (node->decl), parm);
 
-      if (!alignments[i].known || !is_gimple_reg (parm))
+      if (!ddef || !is_gimple_reg (parm))
 	continue;
-      tree ddef = ssa_default_def (DECL_STRUCT_FUNCTION (node->decl), parm);
-      if (!ddef)
+
+      if (cgraph_local_p (node)
+	  && vr[i].known
+	  && INTEGRAL_TYPE_P (TREE_TYPE (ddef))
+	  && !POINTER_TYPE_P (TREE_TYPE (ddef))
+	  && (vr[i].type == VR_RANGE || vr[i].type == VR_ANTI_RANGE)
+	  && TREE_CODE (vr[i].min) == INTEGER_CST
+	  && TREE_CODE (vr[i].max) == INTEGER_CST)
+	{
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "Setting value range of param %u ", i);
+	      fprintf (dump_file, "%s[", (vr[i].type == VR_ANTI_RANGE) ? "~" : "");
+	      print_generic_expr (dump_file, vr[i].min, 0);
+	      fprintf (dump_file, ", ");
+	      print_generic_expr (dump_file, vr[i].max, 0);
+	      fprintf (dump_file, "]\n");
+	    }
+	  set_range_info (ddef, vr[i].type,
+			  wide_int_to_tree (TREE_TYPE (ddef), vr[i].min),
+			  wide_int_to_tree (TREE_TYPE (ddef), vr[i].max));
+
+	}
+
+      if (!alignments[i].known)
 	continue;
 
       if (dump_file)
@@ -5422,7 +5530,7 @@ ipcp_transform_function (struct cgraph_node *node)
     fprintf (dump_file, "Modification phase of node %s/%i\n",
 	     node->name (), node->order);
 
-  ipcp_update_alignments (node);
+  ipcp_update_vr_and_alignments (node);
   aggval = ipa_get_agg_replacements_for_node (node);
   if (!aggval)
       return 0;
diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
index e32d078..82c1086 100644
--- a/gcc/ipa-prop.h
+++ b/gcc/ipa-prop.h
@@ -154,6 +154,17 @@ struct GTY(()) ipa_alignment
   unsigned misalign;
 };
 
+/* Info about value ranges.  */
+
+struct GTY(()) ipa_vr
+{
+  /* The data fields below are valid only if known is true.  */
+  bool known;
+  enum value_range_type type;
+  tree min;
+  tree max;
+};
+
 /* A jump function for a callsite represents the values passed as actual
    arguments of the callsite. See enum jump_func_type for the various
    types of jump functions supported.  */
@@ -166,6 +177,10 @@ struct GTY (()) ipa_jump_func
   /* Information about alignment of pointers. */
   struct ipa_alignment alignment;
 
+  /* Information about value range.  */
+  bool vr_known;
+  value_range m_vr;
+
   enum jump_func_type type;
   /* Represents a value of a jump function.  pass_through is used only in jump
      function context.  constant represents the actual constant in constant jump
@@ -482,6 +497,8 @@ struct GTY(()) ipcp_transformation_summary
   ipa_agg_replacement_value *agg_values;
   /* Alignment information for pointers.  */
   vec<ipa_alignment, va_gc> *alignments;
+  /* Value range information.  */
+  vec<ipa_vr, va_gc> *m_vr;
 };
 
 void ipa_set_node_agg_value_chain (struct cgraph_node *node,
diff --git a/gcc/testsuite/gcc.dg/ipa/vrp1.c b/gcc/testsuite/gcc.dg/ipa/vrp1.c
new file mode 100644
index 0000000..72a3139
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ipa/vrp1.c
@@ -0,0 +1,32 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-ipa-cp-details" } */
+
+static __attribute__((noinline, noclone))
+int foo (int i)
+{
+  if (i < 5)
+    __builtin_abort ();
+  return 0;
+}
+
+static __attribute__((noinline, noclone))
+int bar (int j)
+{
+  if (j > 8)
+    return foo (j + 2);
+  else if (j > 2)
+    return foo (j + 3);
+
+  return 0;
+}
+
+int main ()
+{
+  for (unsigned int i =0; i < 1000; ++i)
+    bar (i);
+
+  return 0;
+}
+
+/* { dg-final { scan-ipa-dump "Setting value range of param 0 \\\[6," "cp" } } */
+/* { dg-final { scan-ipa-dump "Setting value range of param 0 \\\[0, 999\\\]" "cp" } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/vrp2.c b/gcc/testsuite/gcc.dg/ipa/vrp2.c
new file mode 100644
index 0000000..c720e5c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ipa/vrp2.c
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-ipa-cp-details" } */
+
+static __attribute__((noinline, noclone))
+int foo (int i)
+{
+  if (i < 4)
+    __builtin_abort ();
+  return 0;
+}
+
+static __attribute__((noinline, noclone))
+int bar (int j)
+{
+  if (j > 8)
+    return foo (j + 2);
+  else if (j > 2)
+    return foo (j + 3);
+
+  return 0;
+}
+
+int main ()
+{
+  foo (100);
+  for (unsigned int i = 0; i < 12; ++i)
+    {
+      bar (i);
+    }
+  foo (4);
+  return 0;
+}
+
+/* { dg-final { scan-ipa-dump "Setting value range of param 0 \\\[4," "cp" } } */
+/* { dg-final { scan-ipa-dump "Setting value range of param 0 \\\[0, 11\\\]" "cp" } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/vrp3.c b/gcc/testsuite/gcc.dg/ipa/vrp3.c
new file mode 100644
index 0000000..fb5d54a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ipa/vrp3.c
@@ -0,0 +1,30 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-ipa-cp-details" } */
+
+volatile int cond;
+
+static __attribute__((noinline, noclone))
+int foo (int i)
+{
+  if (i < 5)
+    __builtin_abort ();
+  return 0;
+}
+
+static __attribute__((noinline, noclone))
+int bar (int j)
+{
+  if (cond)
+    foo (j);
+  return 0;
+}
+
+int main ()
+{
+  for (unsigned int i = 0; i < 10; ++i)
+    bar (i);
+
+  return 0;
+}
+
+/* { dg-final { scan-ipa-dump-times "Setting value range of param 0 \\\[0, 9\\\]" 2 "cp" } } */
-- 
1.9.1


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]