This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Loop stride optimization hint
- From: Jan Hubicka <hubicka at ucw dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 12 Sep 2012 19:57:16 +0200
- Subject: Loop stride optimization hint
Hi,
for Fortran one of common reason to inline is because array descriptor is known and defines
loop stride. This patch makes ipa-inline-analysis to notice these cases.
Bootstrapped/regtested x86_64-linux, will commit it tomorrow if there are no complains.
Honza
* 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.
* gcc.dg/ipa/inlinehint-2.c: New testcase.
Index: ipa-inline-analysis.c
===================================================================
*** ipa-inline-analysis.c (revision 191228)
--- ipa-inline-analysis.c (working copy)
*************** dump_inline_hints (FILE *f, inline_hints
*** 634,639 ****
--- 634,644 ----
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);
}
*************** edge_set_predicate (struct cgraph_edge *
*** 719,724 ****
--- 724,749 ----
}
}
+ /* 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.
*************** reset_inline_summary (struct cgraph_node
*** 953,958 ****
--- 978,988 ----
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)
*************** inline_node_removal_hook (struct cgraph_
*** 975,980 ****
--- 1005,1056 ----
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. */
*************** inline_node_duplication_hook (struct cgr
*** 1042,1057 ****
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]);
if (false_predicate_p (&new_predicate))
{
optimized_out_size += e->size;
--- 1118,1127 ----
to be true. */
for (i = 0; VEC_iterate (size_time_entry, entry, i, e); i++)
{
! 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;
*************** inline_node_duplication_hook (struct cgr
*** 1065,1086 ****
Also copy constantness arrays. */
for (edge = dst->callees; edge; edge = edge->next_callee)
{
! struct predicate new_predicate = true_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]);
if (false_predicate_p (&new_predicate)
&& !false_predicate_p (es->predicate))
{
--- 1135,1150 ----
Also copy constantness arrays. */
for (edge = dst->callees; edge; edge = edge->next_callee)
{
! 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;
! new_predicate = remap_predicate_after_duplication (es->predicate,
! possible_truths,
! info);
if (false_predicate_p (&new_predicate)
&& !false_predicate_p (es->predicate))
{
*************** inline_node_duplication_hook (struct cgr
*** 1097,1118 ****
Also copy constantness arrays. */
for (edge = dst->indirect_calls; edge; edge = edge->next_callee)
{
! struct predicate new_predicate = true_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]);
if (false_predicate_p (&new_predicate)
&& !false_predicate_p (es->predicate))
{
--- 1161,1175 ----
Also copy constantness arrays. */
for (edge = dst->indirect_calls; edge; edge = edge->next_callee)
{
! struct predicate new_predicate;
struct inline_edge_summary *es = inline_edge_summary (edge);
! gcc_checking_assert (edge->inline_failed);
if (!es->predicate)
continue;
! new_predicate = remap_predicate_after_duplication (es->predicate,
! possible_truths,
! info);
if (false_predicate_p (&new_predicate)
&& !false_predicate_p (es->predicate))
{
*************** inline_node_duplication_hook (struct cgr
*** 1124,1151 ****
}
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;
! }
! }
/* If inliner or someone after inliner will ever start producing
non-trivial clones, we will get trouble with lack of information
--- 1181,1192 ----
}
edge_set_predicate (edge, &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
*************** inline_node_duplication_hook (struct cgr
*** 1175,1182 ****
if (info->loop_iterations)
{
predicate p = *info->loop_iterations;
! info->loop_iterations = (struct predicate *)pool_alloc (edge_predicate_pool);
! *info->loop_iterations = p;
}
}
}
--- 1216,1229 ----
if (info->loop_iterations)
{
predicate p = *info->loop_iterations;
! 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);
}
}
}
*************** dump_inline_summary (FILE * f, struct cg
*** 1355,1360 ****
--- 1402,1412 ----
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");
*************** estimate_function_body_sizes (struct cgr
*** 2390,2395 ****
--- 2442,2448 ----
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);
*************** estimate_function_body_sizes (struct cgr
*** 2398,2405 ****
{
VEC (edge, heap) *exits;
edge ex;
! unsigned int j;
struct tree_niter_desc niter_desc;
exits = get_loop_exit_edges (loop);
FOR_EACH_VEC_ELT (edge, exits, j, ex)
--- 2451,2459 ----
{
VEC (edge, heap) *exits;
edge ex;
! 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)
*************** estimate_function_body_sizes (struct cgr
*** 2416,2427 ****
loop_iterations = and_predicates (info->conds, &loop_iterations, &will_be_nonconstant);
}
VEC_free (edge, heap, exits);
}
! 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;
! }
scev_finalize ();
}
inline_summary (node)->self_time = time;
--- 2470,2508 ----
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);
}
! 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;
*************** estimate_node_size_and_time (struct cgra
*** 2715,2720 ****
--- 2796,2804 ----
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;
*************** remap_edge_summaries (struct cgraph_edg
*** 3011,3016 ****
--- 3095,3131 ----
}
}
+ /* 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. */
*************** inline_merge_summary (struct cgraph_edge
*** 3102,3129 ****
}
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);
! }
! }
inline_update_callee_summaries (edge->callee,
inline_edge_summary (edge)->loop_depth);
--- 3217,3230 ----
}
remap_edge_summaries (edge, edge->callee, info, callee_info, operand_map,
offset_map, clause, &toplev_predicate);
! 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);
*************** inline_read_section (struct lto_file_dec
*** 3595,3605 ****
}
p = read_predicate (&ib);
! if (!true_predicate_p (&p))
! {
! info->loop_iterations = (struct predicate *)pool_alloc (edge_predicate_pool);
! *info->loop_iterations = 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)
--- 3696,3704 ----
}
p = read_predicate (&ib);
! 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)
*************** inline_write_summary (void)
*** 3747,3752 ****
--- 3846,3852 ----
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)
Index: ipa-inline.c
===================================================================
*** ipa-inline.c (revision 191228)
--- ipa-inline.c (working copy)
*************** want_inline_small_function_p (struct cgr
*** 481,487 ****
else if (DECL_DECLARED_INLINE_P (callee->symbol.decl)
&& growth >= MAX_INLINE_INSNS_SINGLE
&& !(hints & (INLINE_HINT_indirect_call
! | INLINE_HINT_loop_iterations)))
{
e->inline_failed = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
want_inline = false;
--- 481,488 ----
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_stride)))
{
e->inline_failed = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
want_inline = false;
*************** want_inline_small_function_p (struct cgr
*** 533,539 ****
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))
? MAX (MAX_INLINE_INSNS_AUTO,
MAX_INLINE_INSNS_SINGLE)
: MAX_INLINE_INSNS_AUTO))
--- 534,541 ----
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_stride))
? MAX (MAX_INLINE_INSNS_AUTO,
MAX_INLINE_INSNS_SINGLE)
: MAX_INLINE_INSNS_AUTO))
*************** edge_badness (struct cgraph_edge *edge,
*** 866,872 ****
fprintf (dump_file, "Badness overflow\n");
}
if (hints & (INLINE_HINT_indirect_call
! | INLINE_HINT_loop_iterations))
badness /= 8;
if (dump)
{
--- 868,875 ----
fprintf (dump_file, "Badness overflow\n");
}
if (hints & (INLINE_HINT_indirect_call
! | INLINE_HINT_loop_iterations
! | INLINE_HINT_loop_stride))
badness /= 8;
if (dump)
{
Index: ipa-inline.h
===================================================================
*** ipa-inline.h (revision 191228)
--- ipa-inline.h (working copy)
*************** typedef struct GTY(()) condition
*** 46,52 ****
They are represtented as bitmap of the following values. */
enum inline_hints_vals {
INLINE_HINT_indirect_call = 1,
! INLINE_HINT_loop_iterations = 2
};
typedef int inline_hints;
--- 46,53 ----
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_stride = 4
};
typedef int inline_hints;
*************** struct GTY(()) inline_summary
*** 120,128 ****
conditions conds;
VEC(size_time_entry,gc) *entry;
! /* Predicate on when some loop in the function sbecomes to have known
bounds. */
struct predicate * GTY((skip)) loop_iterations;
};
--- 121,132 ----
conditions conds;
VEC(size_time_entry,gc) *entry;
! /* 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;
};
Index: testsuite/gcc.dg/ipa/inlinehint-2.c
===================================================================
*** testsuite/gcc.dg/ipa/inlinehint-2.c (revision 0)
--- testsuite/gcc.dg/ipa/inlinehint-2.c (working copy)
***************
*** 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);
+ }
+ /* { dg-final { scan-ipa-dump "loop_stride" "inline" } } */
+ /* { dg-final { cleanup-ipa-dump "inline" } } */