Loop stride inline hint
Jan Hubicka
hubicka@ucw.cz
Wed Sep 12 21:53:00 GMT 2012
Hi,
this patch makes inliner to realize that it is good idea to inline when loop
stride becomes constant. This is mostly to help fortran testcases where
it is important to inline to get array descriptors.
Bootstrapped/regtested x86_64-linux, comitted.
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.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: 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");
*************** will_be_nonconstant_expr_predicate (stru
*** 1851,1863 ****
if (TREE_CODE (expr) == SSA_NAME)
return VEC_index (predicate_t, nonconstant_names,
SSA_NAME_VERSION (expr));
! if (BINARY_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, 0), nonconstant_names);
return or_predicates (summary->conds, &p1, &p2);
}
else
--- 1903,1939 ----
if (TREE_CODE (expr) == SSA_NAME)
return VEC_index (predicate_t, nonconstant_names,
SSA_NAME_VERSION (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 p2;
if (true_predicate_p (&p1))
return p1;
! 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
*************** estimate_function_body_sizes (struct cgr
*** 2390,2395 ****
--- 2466,2472 ----
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)
--- 2475,2483 ----
{
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;
--- 2494,2532 ----
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 ****
--- 2820,2828 ----
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 ****
--- 3119,3155 ----
}
}
+ /* 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);
--- 3241,3254 ----
}
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)
--- 3720,3728 ----
}
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 ****
--- 3870,3876 ----
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)
More information about the Gcc-patches
mailing list