On Wed, Sep 12, 2012 at 11:53 PM, Jan Hubicka <hubi...@ucw.cz> wrote: > 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.
I think the same applies to upper/lower bounds. Richard. > 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)