re PR fortran/48636 (Enable more inlining with -O2 and higher)

	PR fortran/48636
	* gcc.dg/ipa/inlinehint-2.c: New testcase.
	* ipa-inline-analysis.c (dump_inline_hints): Dump loop stride.
	(set_hint_predicate): New function.
	(reset_inline_summary): Reset loop stride.
	(remap_predicate_after_duplication): New function.
	(remap_hint_predicate_after_duplication): New function.
	(inline_node_duplication_hook): Update.
	(dump_inline_summary): Dump stride summaries.
	(estimate_function_body_sizes): Compute strides.
	(remap_hint_predicate): New function.
	(inline_merge_summary): Use it.
	(inline_read_section): Read stride.
	(inline_write_summary): Write stride.
	* ipa-inline.c (want_inline_small_function_p): Handle strides.
	(edge_badness): Likewise.
	* ipa-inline.h (inline_hints_vals): Add stride hint.
	(inline_summary): Update stride.

From-SVN: r191232

6 files changed, 265 insertions, 97 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 8b35ab4..ff6dd57 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,23 @@
+2012-09-12  Jan Hubicka  <jh@suse.cz>
+
+	PR fortran/48636
+	* ipa-inline-analysis.c (dump_inline_hints): Dump loop stride.
+	(set_hint_predicate): New function.
+	(reset_inline_summary): Reset loop stride.
+	(remap_predicate_after_duplication): New function.
+	(remap_hint_predicate_after_duplication): New function.
+	(inline_node_duplication_hook): Update.
+	(dump_inline_summary): Dump stride summaries.
+	(estimate_function_body_sizes): Compute strides.
+	(remap_hint_predicate): New function.
+	(inline_merge_summary): Use it.
+	(inline_read_section): Read stride.
+	(inline_write_summary): Write stride.
+	* ipa-inline.c (want_inline_small_function_p): Handle strides.
+	(edge_badness): Likewise.
+	* ipa-inline.h (inline_hints_vals): Add stride hint.
+	(inline_summary): Update stride.
+
 2012-09-12  Uros Bizjak  <ubizjak@gmail.com>
 
 	* config/i386/i386.c (x86_prefetch_sse): Change to unsigned char.
diff --git a/gcc/ipa-inline-analysis.c b/gcc/ipa-inline-analysis.c
index 613b606..268f077 100644
--- a/gcc/ipa-inline-analysis.c
+++ b/gcc/ipa-inline-analysis.c
@@ -634,6 +634,11 @@ dump_inline_hints (FILE *f, inline_hints hints)
       hints &= ~INLINE_HINT_loop_iterations;
       fprintf (f, " loop_iterations");
     }
+  if (hints & INLINE_HINT_loop_stride)
+    {
+      hints &= ~INLINE_HINT_loop_stride;
+      fprintf (f, " loop_stride");
+    }
   gcc_assert (!hints);
 }
 
@@ -719,6 +724,26 @@ edge_set_predicate (struct cgraph_edge *e, struct predicate *predicate)
     }
 }
 
+/* Set predicate for hint *P.  */
+
+static void
+set_hint_predicate (struct predicate **p, struct predicate new_predicate)
+{
+  if (false_predicate_p (&new_predicate)
+      || true_predicate_p (&new_predicate))
+    {
+      if (*p)
+	pool_free (edge_predicate_pool, *p);
+      *p = NULL;
+    }
+  else
+    {
+      if (!*p)
+	*p = (struct predicate *)pool_alloc (edge_predicate_pool);
+      **p = new_predicate;
+    }
+}
+
 
 /* KNOWN_VALS is partial mapping of parameters of NODE to constant values.
    KNOWN_AGGS is a vector of aggreggate jump functions for each parameter.
@@ -953,6 +978,11 @@ reset_inline_summary (struct cgraph_node *node)
       pool_free (edge_predicate_pool, info->loop_iterations);
       info->loop_iterations = NULL;
     }
+  if (info->loop_stride)
+    {
+      pool_free (edge_predicate_pool, info->loop_stride);
+      info->loop_stride = NULL;
+    }
   VEC_free (condition, gc, info->conds);
   VEC_free (size_time_entry,gc, info->entry);
   for (e = node->callees; e; e = e->next_callee)
@@ -975,6 +1005,52 @@ inline_node_removal_hook (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
   memset (info, 0, sizeof (inline_summary_t));
 }
 
+/* Remap predicate P of former function to be predicate of duplicated functoin.
+   POSSIBLE_TRUTHS is clause of possible truths in the duplicated node,
+   INFO is inline summary of the duplicated node.  */
+
+static struct predicate
+remap_predicate_after_duplication (struct predicate *p,
+				   clause_t possible_truths,
+				   struct inline_summary *info)
+{
+  struct predicate new_predicate = true_predicate ();
+  int j;
+  for (j = 0; p->clause[j]; j++)
+    if (!(possible_truths & p->clause[j]))
+      {
+	new_predicate = false_predicate ();
+	break;
+      }
+    else
+      add_clause (info->conds, &new_predicate,
+		  possible_truths & p->clause[j]);
+  return new_predicate;
+}
+
+/* Same as remap_predicate_after_duplication but handle hint predicate *P.
+   Additionally care about allocating new memory slot for updated predicate
+   and set it to NULL when it becomes true or false (and thus uninteresting).
+ */
+
+static void
+remap_hint_predicate_after_duplication (struct predicate **p,
+					clause_t possible_truths,
+					struct inline_summary *info)
+{
+  struct predicate new_predicate;
+
+  if (!*p)
+    return;
+
+  new_predicate = remap_predicate_after_duplication (*p,
+						     possible_truths,
+						     info);
+  /* We do not want to free previous predicate; it is used by node origin.  */
+  *p = NULL;
+  set_hint_predicate (p, new_predicate);
+}
+
 
 /* Hook that is called by cgraph.c when a node is duplicated.  */
 
@@ -1042,16 +1118,10 @@ inline_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
 	 to be true.  */
       for (i = 0; VEC_iterate (size_time_entry, entry, i, e); i++)
 	{
-	  struct predicate new_predicate = true_predicate ();
-	  for (j = 0; e->predicate.clause[j]; j++)
-	    if (!(possible_truths & e->predicate.clause[j]))
-	      {
-		new_predicate = false_predicate ();
-		break;
-	      }
-	    else
-	      add_clause (info->conds, &new_predicate,
-			  possible_truths & e->predicate.clause[j]);
+	  struct predicate new_predicate;
+	  new_predicate = remap_predicate_after_duplication (&e->predicate,
+							     possible_truths,
+							     info);
 	  if (false_predicate_p (&new_predicate))
 	    {
 	      optimized_out_size += e->size;
@@ -1065,22 +1135,16 @@ inline_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
 	 Also copy constantness arrays.   */
       for (edge = dst->callees; edge; edge = edge->next_callee)
 	{
-	  struct predicate new_predicate = true_predicate ();
+	  struct predicate new_predicate;
 	  struct inline_edge_summary *es = inline_edge_summary (edge);
 
 	  if (!edge->inline_failed)
 	    inlined_to_p = true;
 	  if (!es->predicate)
 	    continue;
-	  for (j = 0; es->predicate->clause[j]; j++)
-	    if (!(possible_truths & es->predicate->clause[j]))
-	      {
-		new_predicate = false_predicate ();
-		break;
-	      }
-	    else
-	      add_clause (info->conds, &new_predicate,
-			  possible_truths & es->predicate->clause[j]);
+	  new_predicate = remap_predicate_after_duplication (es->predicate,
+							     possible_truths,
+							     info);
 	  if (false_predicate_p (&new_predicate)
 	      && !false_predicate_p (es->predicate))
 	    {
@@ -1097,22 +1161,15 @@ inline_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
 	 Also copy constantness arrays.   */
       for (edge = dst->indirect_calls; edge; edge = edge->next_callee)
 	{
-	  struct predicate new_predicate = true_predicate ();
+	  struct predicate new_predicate;
 	  struct inline_edge_summary *es = inline_edge_summary (edge);
 
-	  if (!edge->inline_failed)
-	    inlined_to_p = true;
+	  gcc_checking_assert (edge->inline_failed);
 	  if (!es->predicate)
 	    continue;
-	  for (j = 0; es->predicate->clause[j]; j++)
-	    if (!(possible_truths & es->predicate->clause[j]))
-	      {
-		new_predicate = false_predicate ();
-		break;
-	      }
-	    else
-	      add_clause (info->conds, &new_predicate,
-			  possible_truths & es->predicate->clause[j]);
+	  new_predicate = remap_predicate_after_duplication (es->predicate,
+							     possible_truths,
+							     info);
 	  if (false_predicate_p (&new_predicate)
 	      && !false_predicate_p (es->predicate))
 	    {
@@ -1124,28 +1181,12 @@ inline_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
 	    }
 	  edge_set_predicate (edge, &new_predicate);
 	}
-      if (info->loop_iterations)
-	{
-	  struct predicate new_predicate = true_predicate ();
-
-	  for (j = 0; info->loop_iterations->clause[j]; j++)
-	    if (!(possible_truths & info->loop_iterations->clause[j]))
-	      {
-		new_predicate = false_predicate ();
-		break;
-	      }
-	    else
-	      add_clause (info->conds, &new_predicate,
-			  possible_truths & info->loop_iterations->clause[j]);
-	  if (false_predicate_p (&new_predicate)
-	      || true_predicate_p (&new_predicate))
-	    info->loop_iterations = NULL;
-	  else
-	    {
-	      info->loop_iterations = (struct predicate *)pool_alloc (edge_predicate_pool);
-	      *info->loop_iterations = new_predicate;
-	    }
-	}
+      remap_hint_predicate_after_duplication (&info->loop_iterations,
+					      possible_truths,
+					      info);
+      remap_hint_predicate_after_duplication (&info->loop_stride,
+					      possible_truths,
+					      info);
 
       /* If inliner or someone after inliner will ever start producing
 	 non-trivial clones, we will get trouble with lack of information
@@ -1175,8 +1216,14 @@ inline_node_duplication_hook (struct cgraph_node *src, struct cgraph_node *dst,
       if (info->loop_iterations)
 	{
 	  predicate p = *info->loop_iterations;
-	  info->loop_iterations = (struct predicate *)pool_alloc (edge_predicate_pool);
-	  *info->loop_iterations = p;
+	  info->loop_iterations = NULL;
+	  set_hint_predicate (&info->loop_iterations, p);
+	}
+      if (info->loop_stride)
+	{
+	  predicate p = *info->loop_stride;
+	  info->loop_stride = NULL;
+	  set_hint_predicate (&info->loop_stride, p);
 	}
     }
 }
@@ -1355,6 +1402,11 @@ dump_inline_summary (FILE * f, struct cgraph_node *node)
 	  fprintf (f, "  loop iterations:");
 	  dump_predicate (f, s->conds, s->loop_iterations);
 	}
+      if (s->loop_stride)
+	{
+	  fprintf (f, "  loop stride:");
+	  dump_predicate (f, s->conds, s->loop_stride);
+	}
       fprintf (f, "  calls:\n");
       dump_inline_edge_summary (f, 4, node, s);
       fprintf (f, "\n");
@@ -1851,13 +1903,37 @@ will_be_nonconstant_expr_predicate (struct ipa_node_params *info,
   if (TREE_CODE (expr) == SSA_NAME)
     return VEC_index (predicate_t, nonconstant_names,
                       SSA_NAME_VERSION (expr));
-  if (BINARY_CLASS_P (expr))
+  if (BINARY_CLASS_P (expr)
+      || COMPARISON_CLASS_P (expr))
+    {
+      struct predicate p1 = will_be_nonconstant_expr_predicate
+			      (info, summary, TREE_OPERAND (expr, 0),
+			       nonconstant_names);
+      struct predicate p2;
+      if (true_predicate_p (&p1))
+	return p1;
+      p2 = will_be_nonconstant_expr_predicate (info, summary,
+					       TREE_OPERAND (expr, 1),
+					       nonconstant_names);
+      return or_predicates (summary->conds, &p1, &p2);
+    }
+  else if (TREE_CODE (expr) == COND_EXPR)
     {
-      struct predicate p1 =  will_be_nonconstant_expr_predicate (info, summary, TREE_OPERAND (expr, 0), nonconstant_names);
+      struct predicate p1 = will_be_nonconstant_expr_predicate
+			      (info, summary, TREE_OPERAND (expr, 0),
+			       nonconstant_names);
       struct predicate p2;
       if (true_predicate_p (&p1))
 	return p1;
-      p2 = will_be_nonconstant_expr_predicate (info, summary, TREE_OPERAND (expr, 0), nonconstant_names);
+      p2 = will_be_nonconstant_expr_predicate (info, summary,
+					       TREE_OPERAND (expr, 1),
+					       nonconstant_names);
+      if (true_predicate_p (&p2))
+	return p2;
+      p1 = or_predicates (summary->conds, &p1, &p2);
+      p2 = will_be_nonconstant_expr_predicate (info, summary,
+					       TREE_OPERAND (expr, 2),
+					       nonconstant_names);
       return or_predicates (summary->conds, &p1, &p2);
     }
   else
@@ -2390,6 +2466,7 @@ estimate_function_body_sizes (struct cgraph_node *node, bool early)
       struct loop *loop;
       loop_iterator li;
       predicate loop_iterations = true_predicate ();
+      predicate loop_stride = true_predicate ();
 
       if (dump_file && (dump_flags & TDF_DETAILS))
 	flow_loops_dump (dump_file, NULL, 0);
@@ -2398,8 +2475,9 @@ estimate_function_body_sizes (struct cgraph_node *node, bool early)
 	{
           VEC (edge, heap) *exits;
           edge ex;
-	  unsigned int j;
+	  unsigned int j, i;
 	  struct tree_niter_desc niter_desc;
+	  basic_block *body = get_loop_body (loop);
 
 	  exits = get_loop_exit_edges (loop);
           FOR_EACH_VEC_ELT (edge, exits, j, ex)
@@ -2416,12 +2494,39 @@ estimate_function_body_sizes (struct cgraph_node *node, bool early)
 		  loop_iterations = and_predicates (info->conds, &loop_iterations, &will_be_nonconstant);
 	      }
           VEC_free (edge, heap, exits);
+
+          for (i = 0; i < loop->num_nodes; i++)
+	    {
+	      gimple_stmt_iterator gsi;
+	      for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
+		{
+		  gimple stmt = gsi_stmt (gsi);
+		  affine_iv iv;
+		  ssa_op_iter iter;
+		  tree use;
+
+		  FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+		    {
+		      predicate will_be_nonconstant;
+
+		      if (!simple_iv (loop, loop_containing_stmt (stmt), use, &iv, true)
+			  || is_gimple_min_invariant (iv.step))
+			continue;
+		      will_be_nonconstant
+		       = will_be_nonconstant_expr_predicate (parms_info, info,
+							     iv.step, nonconstant_names);
+		      if (!true_predicate_p (&will_be_nonconstant)
+			  && !false_predicate_p (&will_be_nonconstant))
+			/* This is slightly inprecise.  We may want to represent each loop with
+			   independent predicate.  */
+			loop_stride = and_predicates (info->conds, &loop_stride, &will_be_nonconstant);
+		    }
+		}
+	    }
+	  free (body);
 	}
-      if (!true_predicate_p (&loop_iterations))
-	{
-          inline_summary (node)->loop_iterations = (struct predicate *)pool_alloc (edge_predicate_pool);
-          *inline_summary (node)->loop_iterations = loop_iterations;
-	}
+      set_hint_predicate (&inline_summary (node)->loop_iterations, loop_iterations);
+      set_hint_predicate (&inline_summary (node)->loop_stride, loop_stride);
       scev_finalize ();
     }
   inline_summary (node)->self_time = time;
@@ -2715,6 +2820,9 @@ estimate_node_size_and_time (struct cgraph_node *node,
   if (info->loop_iterations
       && !evaluate_predicate (info->loop_iterations, possible_truths))
     hints |=INLINE_HINT_loop_iterations;
+  if (info->loop_stride
+      && !evaluate_predicate (info->loop_stride, possible_truths))
+    hints |=INLINE_HINT_loop_stride;
 
   if (time > MAX_TIME * INLINE_TIME_SCALE)
     time = MAX_TIME * INLINE_TIME_SCALE;
@@ -3011,6 +3119,37 @@ remap_edge_summaries  (struct cgraph_edge *inlined_edge,
     }
 }
 
+/* Same as remap_predicate, but set result into hint *HINT.  */
+
+static void
+remap_hint_predicate (struct inline_summary *info,
+		      struct inline_summary *callee_info,
+		      struct predicate **hint,
+		      VEC (int, heap) *operand_map,
+		      VEC (int, heap) *offset_map,
+		      clause_t possible_truths,
+		      struct predicate *toplev_predicate)
+{
+  predicate p;
+
+  if (!*hint)
+    return;
+  p = remap_predicate (info, callee_info,
+		       *hint,
+		       operand_map, offset_map,
+		       possible_truths,
+		       toplev_predicate);
+  if (!false_predicate_p (&p)
+      && !true_predicate_p (&p))
+    {
+      if (!*hint)
+	set_hint_predicate (hint, p);
+      else
+	**hint = and_predicates (info->conds, 
+				 *hint,
+				 &p);
+    }
+}
 
 /* We inlined EDGE.  Update summary of the function we inlined into.  */
 
@@ -3102,28 +3241,14 @@ inline_merge_summary (struct cgraph_edge *edge)
     }
   remap_edge_summaries (edge, edge->callee, info, callee_info, operand_map,
 			offset_map, clause, &toplev_predicate);
-  if (callee_info->loop_iterations)
-    {
-      predicate p = remap_predicate (info, callee_info,
-				     callee_info->loop_iterations,
-				     operand_map, offset_map,
-				     clause,
-				     &toplev_predicate);
-      if (!false_predicate_p (&p)
-	  && !true_predicate_p (&p))
-	{
-	  if (!info->loop_iterations)
-	    {
-	      info->loop_iterations
-		 = (struct predicate *)pool_alloc (edge_predicate_pool);
-	      *info->loop_iterations = p;
-	    }
-	  else
-	    *info->loop_iterations = and_predicates (info->conds, 
-						     info->loop_iterations,
-						     &p);
-	}
-    }
+  remap_hint_predicate (info, callee_info,
+			&callee_info->loop_iterations,
+			operand_map, offset_map,
+			clause, &toplev_predicate);
+  remap_hint_predicate (info, callee_info,
+			&callee_info->loop_stride,
+			operand_map, offset_map,
+			clause, &toplev_predicate);
 
   inline_update_callee_summaries (edge->callee,
 				  inline_edge_summary (edge)->loop_depth);
@@ -3595,11 +3720,9 @@ inline_read_section (struct lto_file_decl_data *file_data, const char *data,
 	}
      
       p = read_predicate (&ib);
-      if (!true_predicate_p (&p))
-	{
-	  info->loop_iterations = (struct predicate *)pool_alloc (edge_predicate_pool);
-	  *info->loop_iterations = p;
-	}
+      set_hint_predicate (&info->loop_iterations, p);
+      p = read_predicate (&ib);
+      set_hint_predicate (&info->loop_stride, p);
       for (e = node->callees; e; e = e->next_callee)
 	read_inline_edge_summary (&ib, e);
       for (e = node->indirect_calls; e; e = e->next_callee)
@@ -3747,6 +3870,7 @@ inline_write_summary (void)
 	      write_predicate (ob, &e->predicate);
 	    }
 	  write_predicate (ob, info->loop_iterations);
+	  write_predicate (ob, info->loop_stride);
 	  for (edge = node->callees; edge; edge = edge->next_callee)
 	    write_inline_edge_summary (ob, edge);
 	  for (edge = node->indirect_calls; edge; edge = edge->next_callee)
diff --git a/gcc/ipa-inline.c b/gcc/ipa-inline.c
index 95842bd..f5c255c 100644
--- a/gcc/ipa-inline.c
+++ b/gcc/ipa-inline.c
@@ -481,7 +481,8 @@ want_inline_small_function_p (struct cgraph_edge *e, bool report)
       else if (DECL_DECLARED_INLINE_P (callee->symbol.decl)
 	       && growth >= MAX_INLINE_INSNS_SINGLE
 	       && !(hints & (INLINE_HINT_indirect_call
-			     | INLINE_HINT_loop_iterations)))
+			     | INLINE_HINT_loop_iterations
+			     | INLINE_HINT_loop_stride)))
 	{
           e->inline_failed = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
 	  want_inline = false;
@@ -533,7 +534,8 @@ want_inline_small_function_p (struct cgraph_edge *e, bool report)
 	 inlining given function is very profitable.  */
       else if (!DECL_DECLARED_INLINE_P (callee->symbol.decl)
 	       && growth >= ((hints & (INLINE_HINT_indirect_call
-				       | INLINE_HINT_loop_iterations))
+				       | INLINE_HINT_loop_iterations
+				       | INLINE_HINT_loop_stride))
 			     ? MAX (MAX_INLINE_INSNS_AUTO,
 				    MAX_INLINE_INSNS_SINGLE)
 			     : MAX_INLINE_INSNS_AUTO))
@@ -866,7 +868,8 @@ edge_badness (struct cgraph_edge *edge, bool dump)
 	    fprintf (dump_file, "Badness overflow\n");
 	}
       if (hints & (INLINE_HINT_indirect_call
-		   | INLINE_HINT_loop_iterations))
+		   | INLINE_HINT_loop_iterations
+		   | INLINE_HINT_loop_stride))
 	badness /= 8;
       if (dump)
 	{
diff --git a/gcc/ipa-inline.h b/gcc/ipa-inline.h
index c990716..ec9cf4d 100644
--- a/gcc/ipa-inline.h
+++ b/gcc/ipa-inline.h
@@ -46,7 +46,8 @@ typedef struct GTY(()) condition
    They are represtented as bitmap of the following values.  */
 enum inline_hints_vals {
   INLINE_HINT_indirect_call = 1,
-  INLINE_HINT_loop_iterations = 2
+  INLINE_HINT_loop_iterations = 2,
+  INLINE_HINT_loop_stride = 4
 };
 typedef int inline_hints;
 
@@ -120,9 +121,12 @@ struct GTY(()) inline_summary
   conditions conds;
   VEC(size_time_entry,gc) *entry;
 
-  /* Predicate on when some loop in the function sbecomes to have known
+  /* Predicate on when some loop in the function becomes to have known
      bounds.   */
   struct predicate * GTY((skip)) loop_iterations;
+  /* Predicate on when some loop in the function becomes to have known
+     stride.   */
+  struct predicate * GTY((skip)) loop_stride;
 };
 
 
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 62f96b5..2ad0dfd 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@
+2012-09-12  Jan Hubicka  <jh@suse.cz>
+
+	* gcc.dg/ipa/inlinehint-2.c: New testcase.
+
 2012-09-12  H.J. Lu  <hongjiu.lu@intel.com>
 
 	PR target/54445
diff --git a/gcc/testsuite/gcc.dg/ipa/inlinehint-2.c b/gcc/testsuite/gcc.dg/ipa/inlinehint-2.c
new file mode 100644
index 0000000..a06d725
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ipa/inlinehint-2.c
@@ -0,0 +1,13 @@
+/* { dg-options "-O3 -c -fdump-ipa-inline-details -fno-early-inlining -fno-ipa-cp"  } */
+t(int s, void **p)
+{
+  int i;
+  for (i;i<10000;i+=s)
+    p[i]=0;
+}
+m(void **p)
+{
+  t (10, p);
+}
+/* { dg-final { scan-ipa-dump "loop_stride"  "inline"  } } */
+/* { dg-final { cleanup-ipa-dump "inline" } } */