Generalized value pass-through for self-recursive function (ipa/pr93203)
diff mbox series

Message ID BYAPR01MB4869A2AB6A21551E4EA51FFCF7090@BYAPR01MB4869.prod.exchangelabs.com
State New
Headers show
Series
  • Generalized value pass-through for self-recursive function (ipa/pr93203)
Related show

Commit Message

Feng Xue OS Jan. 25, 2020, 9:54 a.m. UTC
Besides simple pass-through (aggregate) jump function, arithmetic (aggregate)
jump function could also bring same (aggregate) value as parameter passed-in
for self-feeding recursive call.  For example,

      f1 (int i)    /*  normal jump function */
         {
            f1 (i & 1);
         }

Suppose i is 0, recursive propagation via (i & 1) also gets 0, which
can be seen as a simple pass-through of i.

      f2 (int *p)  /* aggregate jump function */
         {
            int t = *p & 1;
            f2 (&t);
         }
Likewise, if *p is 0, (*p & 1) is also 0, and &t is an aggregate simple
pass-through of p.

This patch is to support these two kinds of value pass-through.
Bootstrapped/regtested on x86_64-linux and aarch64-linux.

Feng

---
2020-01-25  Feng Xue  <fxue@os.amperecomputing.com>

        PR ipa/93203
        * ipa-cp.c (ipcp_lattice::add_value): Add source with same call
        edge but different source value.
        (adjust_callers_for_value_intersection): New function.
        (gather_edges_for_value): Adjust order of callers to let a
        non-self-recursive caller be the first element.
        (self_recursive_pass_through_p): Add a new parameter simple, and
	check generalized self-recursive pass-through jump function. 
        (self_recursive_agg_pass_through_p): Likewise.
        (find_more_scalar_values_for_callers_subset): Compute value from
        pass-through jump function for self-recursive.
        (intersect_with_plats): Remove code of itersection with unknown
	place holder value.
        (intersect_with_agg_replacements): Likewise.
        (intersect_aggregates_with_edge): Deduce with from pass-through
        jump function for self-recursive.
        (decide_whether_version_node): Remove dead callers and adjust
        order to let a non-self-recursive caller be the first element.

Patch
diff mbox series

From 406c23711077c0df18d5e77270d0a82be098224b Mon Sep 17 00:00:00 2001
From: Feng Xue <fxue@os.amperecomputing.com>
Date: Tue, 21 Jan 2020 20:53:38 +0800
Subject: [PATCH] Generalized value pass-through for self-recusive function

---
 gcc/ipa-cp.c                       | 196 ++++++++++++++++++-----------
 gcc/testsuite/g++.dg/ipa/pr93203.C |  95 ++++++++++++++
 gcc/testsuite/gcc.dg/ipa/ipcp-1.c  |   2 +-
 3 files changed, 217 insertions(+), 76 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/ipa/pr93203.C

diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c
index 17da1d8e8a7..533a429ba3b 100644
--- a/gcc/ipa-cp.c
+++ b/gcc/ipa-cp.c
@@ -1850,7 +1850,7 @@  ipcp_lattice<valtype>::add_value (valtype newval, cgraph_edge *cs,
 	  {
 	    ipcp_value_source<valtype> *s;
 	    for (s = val->sources; s; s = s->next)
-	      if (s->cs == cs)
+	      if (s->cs == cs && s->val == src_val)
 		break;
 	    if (s)
 	      return false;
@@ -4207,6 +4207,33 @@  get_info_about_necessary_edges (ipcp_value<valtype> *val, cgraph_node *dest,
   return hot;
 }
 
+/* Given a NODE, and a set of its CALLERS, try to adjust order of the callers
+   to let a non-self-recursive caller be the first element.  Thus, we can
+   simplify intersecting operations on values that arrive from all of these
+   callers, especially when there exists self-recursive call.  Return true if
+   this kind of adjustment is possible.  */
+
+static bool
+adjust_callers_for_value_intersection (vec<cgraph_edge *> callers,
+				       cgraph_node *node)
+{
+  for (unsigned i = 0; i < callers.length (); i++)
+    {
+      cgraph_edge *cs = callers[i];
+
+      if (cs->caller != node)
+	{
+	  if (i > 0)
+	    {
+	      callers[i] = callers[0];
+	      callers[0] = cs;
+	    }
+	  return true;
+	}
+    }
+  return false;
+}
+
 /* Return a vector of incoming edges that do bring value VAL to node DEST.  It
    is assumed their number is known and equal to CALLER_COUNT.  */
 
@@ -4230,6 +4257,9 @@  gather_edges_for_value (ipcp_value<valtype> *val, cgraph_node *dest,
 	}
     }
 
+  if (caller_count > 1)
+    adjust_callers_for_value_intersection (ret, dest);
+
   return ret;
 }
 
@@ -4241,7 +4271,6 @@  get_replacement_map (class ipa_node_params *info, tree value, int parm_num)
 {
   struct ipa_replace_map *replace_map;
 
-
   replace_map = ggc_alloc<ipa_replace_map> ();
   if (dump_file)
     {
@@ -4592,36 +4621,40 @@  create_specialized_node (struct cgraph_node *node,
 }
 
 /* Return true, if JFUNC, which describes a i-th parameter of call CS, is a
-   simple no-operation pass-through function to itself.  */
+   pass-through function to itself.  When SIMPLE is true, further check if
+   JFUNC is a simple no-operation pass-through.  */
 
 static bool
-self_recursive_pass_through_p (cgraph_edge *cs, ipa_jump_func *jfunc, int i)
+self_recursive_pass_through_p (cgraph_edge *cs, ipa_jump_func *jfunc, int i,
+			       bool simple = true)
 {
   enum availability availability;
   if (cs->caller == cs->callee->function_symbol (&availability)
       && availability > AVAIL_INTERPOSABLE
       && jfunc->type == IPA_JF_PASS_THROUGH
-      && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR
+      && (!simple || ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
       && ipa_get_jf_pass_through_formal_id (jfunc) == i)
     return true;
   return false;
 }
 
 /* Return true, if JFUNC, which describes a part of an aggregate represented
-   or pointed to by the i-th parameter of call CS, is a simple no-operation
-   pass-through function to itself.  */
+   or pointed to by the i-th parameter of call CS, is a pass-through function
+   to itself.  When SIMPLE is true, further check if JFUNC is a simple
+   no-operation pass-through.  */
 
 static bool
 self_recursive_agg_pass_through_p (cgraph_edge *cs, ipa_agg_jf_item *jfunc,
-				   int i)
+				   int i, bool simple = true)
 {
   enum availability availability;
   if (cs->caller == cs->callee->function_symbol (&availability)
       && availability > AVAIL_INTERPOSABLE
       && jfunc->jftype == IPA_JF_LOAD_AGG
       && jfunc->offset == jfunc->value.load_agg.offset
-      && jfunc->value.pass_through.operation == NOP_EXPR
-      && jfunc->value.pass_through.formal_id == i)
+      && (!simple || jfunc->value.pass_through.operation == NOP_EXPR)
+      && jfunc->value.pass_through.formal_id == i
+      && useless_type_conversion_p (jfunc->value.load_agg.type, jfunc->type))
     return true;
   return false;
 }
@@ -4653,9 +4686,6 @@  find_more_scalar_values_for_callers_subset (struct cgraph_node *node,
 	  struct ipa_jump_func *jump_func;
 	  tree t;
 
-	  if (IPA_NODE_REF (cs->caller) && IPA_NODE_REF (cs->caller)->node_dead)
-	    continue;
-
 	  if (!IPA_EDGE_REF (cs)
 	      || i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
 	      || (i == 0
@@ -4665,10 +4695,30 @@  find_more_scalar_values_for_callers_subset (struct cgraph_node *node,
 	      break;
 	    }
 	  jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
-	  if (self_recursive_pass_through_p (cs, jump_func, i))
-	    continue;
 
-	  t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func, type);
+	  /* Besides simple pass-through jump function, arithmetic jump
+	     function could also introduce argument-direct-pass-through for
+	     self-feeding recursive call.  For example,
+
+	        fn (int i)
+	        {
+	          fn (i & 1);
+	        }
+
+	     Given that i is 0, recursive propagation via (i & 1) also gets
+	     0.  */
+	  if (self_recursive_pass_through_p (cs, jump_func, i, false))
+	    {
+	      gcc_assert (newval);
+	      t = ipa_get_jf_arith_result (
+				ipa_get_jf_pass_through_operation (jump_func),
+				newval,
+				ipa_get_jf_pass_through_operand (jump_func),
+				type);
+	    }
+	  else
+	    t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func,
+				      type);
 	  if (!t
 	      || (newval
 		  && !values_equal_for_ipcp_p (t, newval))
@@ -4817,19 +4867,12 @@  intersect_with_plats (class ipcp_param_lattices *plats,
 	    break;
 	  if (aglat->offset - offset == item->offset)
 	    {
-	      gcc_checking_assert (item->value);
 	      if (aglat->is_single_const ())
 		{
 		  tree value = aglat->values->value;
 
 		  if (values_equal_for_ipcp_p (item->value, value))
 		    found = true;
-		  else if (item->value == error_mark_node)
-		    {
-		      /* Replace unknown place holder value with real one.  */
-		      item->value = value;
-		      found = true;
-		    }
 		}
 	      break;
 	    }
@@ -4898,12 +4941,6 @@  intersect_with_agg_replacements (struct cgraph_node *node, int index,
 	    {
 	      if (values_equal_for_ipcp_p (item->value, av->value))
 		found = true;
-	      else if (item->value == error_mark_node)
-		{
-		  /* Replace place holder value with real one.  */
-		  item->value = av->value;
-		  found = true;
-		}
 	      break;
 	    }
 	}
@@ -5008,31 +5045,16 @@  intersect_aggregates_with_edge (struct cgraph_edge *cs, int index,
 	for (unsigned i = 0; i < jfunc->agg.items->length (); i++)
 	  {
 	    struct ipa_agg_jf_item *agg_item = &(*jfunc->agg.items)[i];
-	    struct ipa_agg_value agg_value;
-
-	    if (self_recursive_agg_pass_through_p (cs, agg_item, index))
+	    tree value = ipa_agg_value_from_node (caller_info, cs->caller,
+						  agg_item);
+	    if (value)
 	      {
-		/* For a self-recursive call, if aggregate jump function is a
-		   simple pass-through, the exact value that it stands for is
-		   not known at this point, which must comes from other call
-		   sites.  But we still need to add a place holder in value
-		   sets to indicate it, here we use error_mark_node to
-		   represent the special unknown value, which will be replaced
-		   with real one during later intersecting operations.  */
-		agg_value.value = error_mark_node;
-	      }
-	    else
-	      {
-		tree value = ipa_agg_value_from_node (caller_info, cs->caller,
-						      agg_item);
-		if (!value)
-		  continue;
+		struct ipa_agg_value agg_value;
 
 		agg_value.value = value;
+		agg_value.offset = agg_item->offset;
+		inter.safe_push (agg_value);
 	      }
-
-	    agg_value.offset = agg_item->offset;
-	    inter.safe_push (agg_value);
 	  }
       else
 	FOR_EACH_VEC_ELT (inter, k, item)
@@ -5053,25 +5075,32 @@  intersect_aggregates_with_edge (struct cgraph_edge *cs, int index,
 		  {
 		    tree value;
 
-		    if (self_recursive_agg_pass_through_p (cs, ti, index))
-		      {
-			/* A simple aggregate pass-through in self-recursive
-			   call should lead to same value.  */
-			found = true;
-		      }
-		    else if ((value = ipa_agg_value_from_node (caller_info,
-							     cs->caller, ti)))
-		      {
-			if (values_equal_for_ipcp_p (item->value, value))
-			  found = true;
-			else if (item->value == error_mark_node)
-			  {
-			    /* Replace unknown place holder value with real
-			       one.  */
-			    item->value = value;
-			    found = true;
-			  }
-		      }
+		    /* Besides simple pass-through aggregate jump function,
+		       arithmetic aggregate jump function could also bring
+		       same aggregate value as parameter passed-in for
+		       self-feeding recursive call.  For example,
+
+		         fn (int *i)
+		           {
+		             int j = *i & 1;
+		             fn (&j);
+		           }
+
+		       Given that *i is 0, recursive propagation via (*i & 1)
+		       also gets 0.  */
+		    if (self_recursive_agg_pass_through_p (cs, ti, index,
+							   false))
+		      value = ipa_get_jf_arith_result (
+					ti->value.pass_through.operation,
+					item->value,
+					ti->value.pass_through.operand,
+					ti->type);
+		    else
+		      value = ipa_agg_value_from_node (caller_info,
+						       cs->caller, ti);
+
+		    if (value && values_equal_for_ipcp_p (item->value, value))
+		      found = true;
 		    break;
 		  }
 		l++;
@@ -5147,9 +5176,6 @@  find_aggregate_values_for_callers_subset (struct cgraph_node *node,
 	  if (!item->value)
 	    continue;
 
-	  /* All values must be real values, not unknown place holders.  */
-	  gcc_assert (item->value != error_mark_node);
-
 	  v = ggc_alloc<ipa_agg_replacement_value> ();
 	  v->index = i;
 	  v->offset = item->offset;
@@ -5488,6 +5514,7 @@  decide_whether_version_node (struct cgraph_node *node)
   int i, count = ipa_get_param_count (info);
   vec<tree> known_csts;
   vec<ipa_polymorphic_call_context> known_contexts;
+  vec<cgraph_edge *> callers;
   bool ret = false;
 
   if (count == 0)
@@ -5542,16 +5569,36 @@  decide_whether_version_node (struct cgraph_node *node)
 	info = IPA_NODE_REF (node);
     }
 
+  if (info->do_clone_for_all_contexts)
+    {
+      callers = node->collect_callers ();
+
+      for (unsigned i = 0; i < callers.length (); i++)
+	{
+	  cgraph_edge *cs = callers[i];
+	  class ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
+
+	  if (caller_info && caller_info->node_dead)
+	    callers.unordered_remove (i);
+	}
+
+      if (!adjust_callers_for_value_intersection (callers, node))
+	{
+	  /* If all caller edges of node are self-recursive, the node
+	     is not really be in use, no need to do cloning.  */
+	  callers.release ();
+	  info->do_clone_for_all_contexts = false;
+	}
+    }
+
   if (info->do_clone_for_all_contexts)
     {
       struct cgraph_node *clone;
-      vec<cgraph_edge *> callers;
 
       if (dump_file)
 	fprintf (dump_file, " - Creating a specialized node of %s "
 		 "for all known contexts.\n", node->dump_name ());
 
-      callers = node->collect_callers ();
       find_more_scalar_values_for_callers_subset (node, known_csts, callers);
       find_more_contexts_for_caller_subset (node, &known_contexts, callers);
       ipa_agg_replacement_value *aggvals
@@ -5564,7 +5611,6 @@  decide_whether_version_node (struct cgraph_node *node)
 	}
       clone = create_specialized_node (node, known_csts, known_contexts,
 				       aggvals, callers);
-      info = IPA_NODE_REF (node);
       info->do_clone_for_all_contexts = false;
       IPA_NODE_REF (clone)->is_all_contexts_clone = true;
       ret = true;
diff --git a/gcc/testsuite/g++.dg/ipa/pr93203.C b/gcc/testsuite/g++.dg/ipa/pr93203.C
new file mode 100644
index 00000000000..b4cd69001b5
--- /dev/null
+++ b/gcc/testsuite/g++.dg/ipa/pr93203.C
@@ -0,0 +1,95 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O3 -w -std=gnu++11" } */
+
+class a {
+public:
+  a(char *);
+};
+class ad {
+public:
+  ad(a *);
+};
+class b {};
+using ah = class ak {
+  using al = char;
+
+public:
+  ak(b) : ak(0) {}
+  ak an() { return ap & 1; }
+  al ap;
+  ak(al af) : ap(af) {}
+};
+struct at {
+  ah au;
+  int av;
+  char aw;
+  char ax;
+};
+class az {
+public:
+  struct ba {
+    void bb(ak am) {
+      ak bc = am.an();
+      bb(bc);
+    }
+  };
+  void bd(ak am) { be.bb(am); }
+  ba be;
+};
+class bg {
+public:
+  int bh;
+  at bi;
+};
+int bj;
+int *bk;
+int c;
+class bl {
+  bool bm();
+  bg bn;
+  az bo;
+  int e;
+  int bq;
+};
+class bs {
+public:
+  bs(int *, ah *, char *, char *, int);
+};
+template < typename bt > class bu : bs {
+  using bv = typename bt::bv;
+
+public:
+  template < typename... bx >
+  bu(a *by, int *bz, at body, bx...)
+      : bs(bz, &body.au, &body.aw, &body.ax, body.av), ca(bx()...), cb(by),
+        cc(by), cd(by), ce(by) {}
+  void cf() {
+    auto cg = ch();
+    auto ci = *cj();
+    ca.ck(this, cg, &ci);
+  }
+  bt ca;
+  ad cb;
+  ad cc;
+  ad cd;
+  ad ce;
+  bv *cj();
+  bv ch();
+};
+class cl {
+public:
+  using bv = struct {};
+  cl(az *, int, int, int, int, a *, int, int **);
+  void ck(bs *, bv, bv *) {
+    b d;
+    ak ci(d);
+    bo.bd(ci);
+  }
+  az bo;
+};
+bool bl::bm() {
+  a by("");
+  bu< cl > cn(&by, &bj, bn.bi, &bo, c, bn.bh, e, 0, &by, bq, &bk);
+  cn.cf();
+}
+
diff --git a/gcc/testsuite/gcc.dg/ipa/ipcp-1.c b/gcc/testsuite/gcc.dg/ipa/ipcp-1.c
index 952694d302b..baa9c97ffb0 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipcp-1.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipcp-1.c
@@ -45,7 +45,7 @@  main (int argc, char *argv[])
 }
 
 
-/* { dg-final { scan-ipa-dump "Creating a specialized node of f.*for all known contexts" "cp" } } */
+/* { dg-final { scan-ipa-dump "Creating a specialized node of f" "cp" } } */
 /* { dg-final { scan-ipa-dump "replacing param .0 a with const 7" "cp"  } } */
 
 
-- 
2.17.1