You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
/* Inlining decision heuristics
#include "fibheap.h"
#include "intl.h"
#include "tree-pass.h"
+#include "hashtab.h"
#include "coverage.h"
+#include "ggc.h"
/* Statistics we collect about inlining algorithm. */
static int ncalls_inlined;
}
else if (duplicate)
{
- n = cgraph_clone_node (e->callee, e->count, e->loop_nest);
+ n = cgraph_clone_node (e->callee, e->count, e->loop_nest, true);
cgraph_redirect_edge_callee (e, n);
}
/* Return true when function N is small enough to be inlined. */
bool
-cgraph_default_inline_p (struct cgraph_node *n)
+cgraph_default_inline_p (struct cgraph_node *n, const char **reason)
{
- if (!DECL_INLINE (n->decl) || !DECL_SAVED_TREE (n->decl))
- return false;
+ if (!DECL_INLINE (n->decl))
+ {
+ if (reason)
+ *reason = N_("function not inlinable");
+ return false;
+ }
+
+ if (!DECL_SAVED_TREE (n->decl))
+ {
+ if (reason)
+ *reason = N_("function body not available");
+ return false;
+ }
+
if (DECL_DECLARED_INLINE_P (n->decl))
- return n->global.insns < MAX_INLINE_INSNS_SINGLE;
+ {
+ if (n->global.insns >= MAX_INLINE_INSNS_SINGLE)
+ {
+ if (reason)
+ *reason = N_("--param max-inline-insns-single limit reached");
+ return false;
+ }
+ }
else
- return n->global.insns < MAX_INLINE_INSNS_AUTO;
+ {
+ if (n->global.insns >= MAX_INLINE_INSNS_AUTO)
+ {
+ if (reason)
+ *reason = N_("--param max-inline-insns-auto limit reached");
+ return false;
+ }
+ }
+
+ return true;
}
/* Return true when inlining WHAT would create recursive inlining.
metrics may accurately depend on values such as number of inlinable callers
of the function or function body size.
- For the moment we use estimated growth caused by inlining callee into all
- it's callers for driving the inlining but once we have loop depth or
- frequency information readily available we should do better.
-
With profiling we use number of executions of each edge to drive the cost.
We also should distinguish hot and cold calls where the cold calls are
inlined into only when code size is overall improved.
-
- Value INT_MAX can be returned to prevent function from being inlined.
*/
static int
{
int nest = MIN (edge->loop_nest, 8);
int badness = cgraph_estimate_growth (edge->callee) * 256;
-
- badness >>= nest;
+
+ /* Decrease badness if call is nested. */
+ if (badness > 0)
+ badness >>= nest;
+ else
+ badness <<= nest;
/* Make recursive inlining happen always after other inlining is done. */
if (cgraph_recursive_inlining_p (edge->caller, edge->callee, NULL))
if (bitmap_bit_p (updated_nodes, node->uid))
return;
bitmap_set_bit (updated_nodes, node->uid);
+ node->global.estimated_growth = INT_MIN;
for (edge = node->callers; edge; edge = edge->next_caller)
if (edge->inline_failed)
for (e = where->callees; e; e = e->next_callee)
if (e->callee == node)
{
- /* FIXME: Once counts and frequencies are available we should drive the
- order by these. For now force the order to be simple queue since
- we get order dependent on recursion depth for free by this. */
- fibheap_insert (heap, priority++, e);
+ /* When profile feedback is available, prioritize by expected number
+ of calls. Without profile feedback we maintain simple queue
+ to order candidates via recursive depths. */
+ fibheap_insert (heap,
+ !max_count ? priority++
+ : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
+ e);
}
for (e = where->callees; e; e = e->next_callee)
if (!e->inline_failed)
lookup_recursive_calls (node, e->callee, heap);
}
+/* Find callgraph nodes closing a circle in the graph. The
+ resulting hashtab can be used to avoid walking the circles.
+ Uses the cgraph nodes ->aux field which needs to be zero
+ before and will be zero after operation. */
+
+static void
+cgraph_find_cycles (struct cgraph_node *node, htab_t cycles)
+{
+ struct cgraph_edge *e;
+
+ if (node->aux)
+ {
+ void **slot;
+ slot = htab_find_slot (cycles, node, INSERT);
+ if (!*slot)
+ {
+ if (dump_file)
+ fprintf (dump_file, "Cycle contains %s\n", cgraph_node_name (node));
+ *slot = node;
+ }
+ return;
+ }
+
+ node->aux = node;
+ for (e = node->callees; e; e = e->next_callee)
+ cgraph_find_cycles (e->callee, cycles);
+ node->aux = 0;
+}
+
+/* Leafify the cgraph node. We have to be careful in recursing
+ as to not run endlessly in circles of the callgraph.
+ We do so by using a hashtab of cycle entering nodes as generated
+ by cgraph_find_cycles. */
+
+static void
+cgraph_flatten_node (struct cgraph_node *node, htab_t cycles)
+{
+ struct cgraph_edge *e;
+
+ for (e = node->callees; e; e = e->next_callee)
+ {
+ /* Inline call, if possible, and recurse. Be sure we are not
+ entering callgraph circles here. */
+ if (e->inline_failed
+ && e->callee->local.inlinable
+ && !cgraph_recursive_inlining_p (node, e->callee,
+ &e->inline_failed)
+ && !htab_find (cycles, e->callee))
+ {
+ if (dump_file)
+ fprintf (dump_file, " inlining %s", cgraph_node_name (e->callee));
+ cgraph_mark_inline_edge (e);
+ cgraph_flatten_node (e->callee, cycles);
+ }
+ else if (dump_file)
+ fprintf (dump_file, " !inlining %s", cgraph_node_name (e->callee));
+ }
+}
+
/* Decide on recursive inlining: in the case function has recursive calls,
inline until body size reaches given argument. */
{
int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
+ int probability = PARAM_VALUE (PARAM_MIN_INLINE_RECURSIVE_PROBABILITY);
fibheap_t heap;
struct cgraph_edge *e;
struct cgraph_node *master_clone;
cgraph_node_name (node));
/* We need original clone to copy around. */
- master_clone = cgraph_clone_node (node, 0, 1);
+ master_clone = cgraph_clone_node (node, node->count, 1, false);
master_clone->needed = true;
for (e = master_clone->callees; e; e = e->next_callee)
if (!e->inline_failed)
/* Do the inlining and update list of recursive call during process. */
while (!fibheap_empty (heap)
- && cgraph_estimate_size_after_inlining (1, node, master_clone) <= limit)
+ && (cgraph_estimate_size_after_inlining (1, node, master_clone)
+ <= limit))
{
struct cgraph_edge *curr = fibheap_extract_min (heap);
- struct cgraph_node *node;
+ struct cgraph_node *cnode;
- depth = 0;
- for (node = curr->caller;
- node; node = node->global.inlined_to)
+ depth = 1;
+ for (cnode = curr->caller;
+ cnode->global.inlined_to; cnode = cnode->callers->caller)
if (node->decl == curr->callee->decl)
depth++;
if (depth > max_depth)
- continue;
+ {
+ if (dump_file)
+ fprintf (dump_file,
+ " maxmal depth reached\n");
+ continue;
+ }
+
+ if (max_count)
+ {
+ if (!cgraph_maybe_hot_edge_p (curr))
+ {
+ if (dump_file)
+ fprintf (dump_file, " Not inlining cold call\n");
+ continue;
+ }
+ if (curr->count * 100 / node->count < probability)
+ {
+ if (dump_file)
+ fprintf (dump_file,
+ " Probability of edge is too small\n");
+ continue;
+ }
+ }
if (dump_file)
- fprintf (dump_file,
- " Inlining call of depth %i\n", depth);
+ {
+ fprintf (dump_file,
+ " Inlining call of depth %i", depth);
+ if (node->count)
+ {
+ fprintf (dump_file, " called approx. %.2f times per call",
+ (double)curr->count / node->count);
+ }
+ fprintf (dump_file, "\n");
+ }
cgraph_redirect_edge_callee (curr, master_clone);
cgraph_mark_inline_edge (curr);
lookup_recursive_calls (node, curr->callee, heap);
n++;
}
+ if (!fibheap_empty (heap) && dump_file)
+ fprintf (dump_file, " Recursive inlining growth limit met.\n");
fibheap_delete (heap);
if (dump_file)
if (node->global.inlined_to == master_clone)
cgraph_remove_node (node);
cgraph_remove_node (master_clone);
+ /* FIXME: Recursive inlining actually reduces number of calls of the
+ function. At this place we should probably walk the function and
+ inline clones and compensate the counts accordingly. This probably
+ doesn't matter much in practice. */
return true;
}
{
struct cgraph_node *node;
struct cgraph_edge *edge;
+ const char *failed_reason;
fibheap_t heap = fibheap_new ();
bitmap updated_nodes = BITMAP_ALLOC (NULL);
fprintf (dump_file, "Considering inline candidate %s.\n", cgraph_node_name (node));
node->global.estimated_growth = INT_MIN;
- if (!cgraph_default_inline_p (node))
+ if (!cgraph_default_inline_p (node, &failed_reason))
{
- cgraph_set_inline_failed (node,
- N_("--param max-inline-insns-single limit reached"));
+ cgraph_set_inline_failed (node, failed_reason);
continue;
}
}
continue;
}
- if (!cgraph_default_inline_p (edge->callee))
+ if (!cgraph_default_inline_p (edge->callee, &edge->inline_failed))
{
if (!cgraph_recursive_inlining_p (edge->caller, edge->callee,
&edge->inline_failed))
{
- edge->inline_failed =
- N_("--param max-inline-insns-single limit reached after inlining into the callee");
if (dump_file)
fprintf (dump_file, " inline_failed:%s.\n", edge->inline_failed);
}
}
else
{
+ struct cgraph_node *callee;
if (!cgraph_check_inline_limits (edge->caller, edge->callee,
&edge->inline_failed))
{
cgraph_node_name (edge->caller), edge->inline_failed);
continue;
}
+ callee = edge->callee;
cgraph_mark_inline_edge (edge);
- update_callee_keys (heap, edge->callee, updated_nodes);
+ update_callee_keys (heap, callee, updated_nodes);
}
where = edge->caller;
if (where->global.inlined_to)
node = order[i];
+ /* Handle nodes to be flattened, but don't update overall unit size. */
+ if (lookup_attribute ("flatten", DECL_ATTRIBUTES (node->decl)) != NULL)
+ {
+ int old_overall_insns = overall_insns;
+ htab_t cycles;
+ if (dump_file)
+ fprintf (dump_file,
+ "Leafifying %s\n", cgraph_node_name (node));
+ cycles = htab_create (7, htab_hash_pointer, htab_eq_pointer, NULL);
+ cgraph_find_cycles (node, cycles);
+ cgraph_flatten_node (node, cycles);
+ htab_delete (cycles);
+ overall_insns = old_overall_insns;
+ /* We don't need to consider always_inline functions inside the flattened
+ function anymore. */
+ continue;
+ }
+
if (!node->local.disregard_inline_limits)
continue;
if (dump_file)
}
if (!flag_really_no_inline)
- {
- cgraph_decide_inlining_of_small_functions ();
+ cgraph_decide_inlining_of_small_functions ();
+ if (!flag_really_no_inline
+ && flag_inline_functions_called_once)
+ {
if (dump_file)
fprintf (dump_file, "\nDeciding on functions called once:\n");
/* Decide on the inlining. We do so in the topological order to avoid
expenses on updating data structures. */
-void
-cgraph_decide_inlining_incrementally (struct cgraph_node *node)
+bool
+cgraph_decide_inlining_incrementally (struct cgraph_node *node, bool early)
{
struct cgraph_edge *e;
+ bool inlined = false;
+ const char *failed_reason;
/* First of all look for always inline functions. */
for (e = node->callees; e; e = e->next_callee)
/* ??? It is possible that renaming variable removed the function body
in duplicate_decls. See gcc.c-torture/compile/20011119-2.c */
&& DECL_SAVED_TREE (e->callee->decl))
- cgraph_mark_inline (e);
+ {
+ if (dump_file && early)
+ fprintf (dump_file, " Early inlining %s into %s\n",
+ cgraph_node_name (e->callee), cgraph_node_name (node));
+ cgraph_mark_inline (e);
+ inlined = true;
+ }
/* Now do the automatic inlining. */
if (!flag_really_no_inline)
&& e->inline_failed
&& !e->callee->local.disregard_inline_limits
&& !cgraph_recursive_inlining_p (node, e->callee, &e->inline_failed)
+ && (!early
+ || (cgraph_estimate_size_after_inlining (1, e->caller, node)
+ <= e->caller->global.insns))
&& cgraph_check_inline_limits (node, e->callee, &e->inline_failed)
&& DECL_SAVED_TREE (e->callee->decl))
{
- if (cgraph_default_inline_p (e->callee))
- cgraph_mark_inline (e);
- else
- e->inline_failed
- = N_("--param max-inline-insns-single limit reached");
+ if (cgraph_default_inline_p (e->callee, &failed_reason))
+ {
+ if (dump_file && early)
+ fprintf (dump_file, " Early inlining %s into %s\n",
+ cgraph_node_name (e->callee), cgraph_node_name (node));
+ cgraph_mark_inline (e);
+ inlined = true;
+ }
+ else if (!early)
+ e->inline_failed = failed_reason;
}
+ if (early && inlined)
+ {
+ push_cfun (DECL_STRUCT_FUNCTION (node->decl));
+ tree_register_cfg_hooks ();
+ current_function_decl = node->decl;
+ optimize_inline_calls (current_function_decl);
+ node->local.self_insns = node->global.insns;
+ current_function_decl = NULL;
+ pop_cfun ();
+ }
+ return inlined;
}
/* When inlining shall be performed. */
0, /* static_pass_number */
TV_INTEGRATION, /* tv_id */
0, /* properties_required */
- PROP_trees, /* properties_provided */
+ PROP_cfg, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */
+ 0 /* letter */
+};
+
+/* Do inlining of small functions. Doing so early helps profiling and other
+ passes to be somewhat more effective and avoids some code duplication in
+ later real inlining pass for testcases with very many function calls. */
+static void
+cgraph_early_inlining (void)
+{
+ struct cgraph_node *node;
+ int nnodes;
+ struct cgraph_node **order =
+ xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
+ int i;
+
+ if (sorrycount || errorcount)
+ return;
+#ifdef ENABLE_CHECKING
+ for (node = cgraph_nodes; node; node = node->next)
+ gcc_assert (!node->aux);
+#endif
+
+ nnodes = cgraph_postorder (order);
+ for (i = nnodes - 1; i >= 0; i--)
+ {
+ node = order[i];
+ if (node->analyzed && node->local.inlinable
+ && (node->needed || node->reachable)
+ && node->callers)
+ cgraph_decide_inlining_incrementally (node, true);
+ }
+ cgraph_remove_unreachable_nodes (true, dump_file);
+#ifdef ENABLE_CHECKING
+ for (node = cgraph_nodes; node; node = node->next)
+ gcc_assert (!node->global.inlined_to);
+#endif
+ free (order);
+}
+
+/* When inlining shall be performed. */
+static bool
+cgraph_gate_early_inlining (void)
+{
+ return flag_inline_trees && flag_early_inlining;
+}
+
+struct tree_opt_pass pass_early_ipa_inline =
+{
+ "einline", /* name */
+ cgraph_gate_early_inlining, /* gate */
+ cgraph_early_inlining, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_INTEGRATION, /* tv_id */
+ 0, /* properties_required */
+ PROP_cfg, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
TODO_dump_cgraph | TODO_dump_func, /* todo_flags_finish */
OSDN Git Service
