#include <float.h>
#include "config.h"
#include "system.h"
#include "tree.h"
#include "c-common.h"
#include "tree-inline.h"
#include "langhooks.h"
#include "hashtab.h"
#include "toplev.h"
#include "flags.h"
#include "ggc.h"
#include "debug.h"
#include "target.h"
#include "varray.h"
#include "cgraph.h"
#include "diagnostic.h"
#include "params.h"
#include "feedback.h"
#define INSNS_PER_STMT (10)
static void cgraph_expand_functions PARAMS ((void));
static tree cgraph_find_calls_r PARAMS ((tree *, int *, void *));
static struct cgraph_edge *cgraph_inlining_callee_list PARAMS ((struct cgraph_node *, tree *));
static void cgraph_mark_functions_to_output PARAMS ((void));
static void cgraph_directed_inlining_r PARAMS ((struct cgraph_edge *, varray_type *));
static void cgraph_expand_function PARAMS ((struct cgraph_node *));
static tree record_call_1 PARAMS ((tree *, int *, void *));
static void cgraph_mark_local_functions PARAMS ((void));
static void cgraph_mark_functions_to_inline_once PARAMS ((void));
static bool cgraph_inlinable_function_p PARAMS ((tree));
static inline double cgraph_call_body_desirability PARAMS ((struct cgraph_node *));
static inline struct cgraph_edge *cgraph_most_desirable_edge PARAMS ((struct cgraph_edge *));
static void cgraph_make_inlining_choices PARAMS ((void));
static void cgraph_clone_parms PARAMS ((tree, tree, splay_tree));
static void cgraph_display_inlining_step_r PARAMS ((struct cgraph_edge *));
static void cgraph_display_inlining_step PARAMS ((struct cgraph_edge *, const char *));
static tree cgraph_directed_inlining PARAMS ((struct cgraph_node *));
static void cgraph_optimize_function PARAMS ((struct cgraph_node *));
static inline void revise_desirabilities_r PARAMS ((struct cgraph_edge *edge));
static inline HOST_WIDEST_INT scaled_execution_count PARAMS ((struct cgraph_edge *edge));
static inline struct cgraph_edge *cgraph_most_desirable_edge PARAMS ((struct cgraph_edge *));
static bool choices_made = FALSE;
void
cgraph_finalize_function (decl, body)
tree decl;
tree body ATTRIBUTE_UNUSED;
{
struct cgraph_node *node = cgraph_node (decl);
node->decl = decl;
node->local.can_inline_once = tree_inlinable_function_p (decl, 1);
if (flag_inline_trees)
node->local.inline_many = tree_inlinable_function_p (decl, 0);
else
node->local.inline_many = 0;
(*debug_hooks->deferred_inline_function) (decl);
}
static GTY(()) struct cgraph_node *queue = NULL;
void
cgraph_mark_needed_node (node, needed)
struct cgraph_node *node;
int needed;
{
if (needed)
{
if (DECL_SAVED_TREE (node->decl))
announce_function (node->decl);
node->needed = 1;
}
if (!node->reachable)
{
node->reachable = 1;
if (DECL_SAVED_TREE (node->decl))
{
node->aux = queue;
queue = node;
}
}
}
static tree
record_call_1 (tp, walk_subtrees, data)
tree *tp;
int *walk_subtrees ATTRIBUTE_UNUSED;
void *data;
{
if (TREE_CODE (*tp) == ADDR_EXPR)
{
tree decl = TREE_OPERAND (*tp, 0);
if (TREE_CODE (decl) == FUNCTION_DECL)
cgraph_mark_needed_node (cgraph_node (decl), 1);
}
else if (TREE_CODE (*tp) == CALL_EXPR)
{
tree decl = TREE_OPERAND (*tp, 0);
if (TREE_CODE (decl) == ADDR_EXPR)
decl = TREE_OPERAND (decl, 0);
if (TREE_CODE (decl) == FUNCTION_DECL)
{
if (DECL_BUILT_IN (decl))
return NULL;
cgraph_record_call (data, decl, tp, (HOST_WIDEST_INT)1);
}
}
return NULL;
}
void
cgraph_create_edges (decl, body)
tree decl;
tree body;
{
walk_tree_without_duplicates (&body, record_call_1, decl);
}
static tree
cgraph_find_calls_r (tp, walk_subtrees, data)
tree *tp;
int *walk_subtrees ATTRIBUTE_UNUSED;
void *data;
{
if (TYPE_P (*tp))
*walk_subtrees = 0;
else if (TREE_CODE (*tp) == CALL_EXPR)
{
varray_type *callee_varray = (varray_type *)data;
tree decl = TREE_OPERAND (*tp, 0);
if (TREE_CODE (decl) == ADDR_EXPR)
decl = TREE_OPERAND (decl, 0);
if (TREE_CODE (decl) == FUNCTION_DECL)
{
if (DECL_BUILT_IN (decl))
return NULL;
VARRAY_PUSH_GENERIC_PTR (*callee_varray, tp);
}
}
return NULL;
}
varray_type
cgraph_find_calls (body)
tree *body;
{
varray_type callee_array;
VARRAY_GENERIC_PTR_INIT (callee_array, 10, "list of ptrs to CALL_EXPRs");
walk_tree_without_duplicates (body, (walk_tree_fn)cgraph_find_calls_r, (void *)&callee_array);
return callee_array;
}
static struct cgraph_edge *
cgraph_inlining_callee_list (caller, tp)
struct cgraph_node *caller ATTRIBUTE_UNUSED;
tree *tp;
{
struct cgraph_edge *first, **step;
tree *callp, decl;
varray_type callee_varray = cgraph_find_calls (tp);
unsigned int i, limit = VARRAY_ACTIVE_SIZE (callee_varray);
first = (struct cgraph_edge *)NULL;
step = &first;
for (i=0; i<limit; i++)
{
callp = VARRAY_GENERIC_PTR (callee_varray, i);
decl = TREE_OPERAND (*callp, 0);
if (TREE_CODE (decl) == ADDR_EXPR)
decl = TREE_OPERAND (decl, 0);
if (TREE_CODE (decl) == FUNCTION_DECL)
{
*step = create_edge ((struct cgraph_node *)NULL, (struct cgraph_node *)NULL, callp);
(*step)->caller = caller;
(*step)->callee = cgraph_node (decl);
step = &((*step)->next_callee);
}
else
abort();
}
*step = (struct cgraph_edge *)NULL;
return first;
}
void
cgraph_finalize_compilation_unit ()
{
struct cgraph_node *node;
struct cgraph_edge *edge;
if (!quiet_flag)
fprintf (stderr, "\n\nUnit entry points:");
for (node = cgraph_nodes; node; node = node->next)
{
tree decl = node->decl;
if (!DECL_SAVED_TREE (decl))
continue;
if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
|| (DECL_ASSEMBLER_NAME_SET_P (decl)
&& TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
{
if (!quiet_flag)
fprintf (stderr, " 0x%p", (void *)node);
cgraph_mark_needed_node (node, 1);
}
}
while (queue)
{
tree decl = queue->decl;
node = queue;
queue = queue->aux;
if (node->lowered || !node->reachable || !DECL_SAVED_TREE (decl))
abort ();
if (node->nested)
{
struct cgraph_node *node2;
for (node2 = node->nested; node2; node2 = node2->next_nested)
if (!node2->reachable)
cgraph_mark_needed_node (node2, 0);
}
if (lang_hooks.callgraph.lower_function)
(*lang_hooks.callgraph.lower_function) (decl);
cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
for (edge = node->callees; edge; edge = edge->next_callee)
{
if (!edge->callee->reachable)
cgraph_mark_needed_node (edge->callee, 0);
}
node->lowered = true;
}
if (!quiet_flag)
fprintf (stderr, "\n\nReclaiming functions:");
for (node = cgraph_nodes; node; node = node->next)
{
tree decl = node->decl;
if (!node->reachable && DECL_SAVED_TREE (decl))
{
cgraph_remove_node (node);
announce_function (decl);
}
}
ggc_collect ();
}
static void
cgraph_mark_functions_to_output ()
{
struct cgraph_node *node;
for (node = cgraph_nodes; node; node = node->next)
{
tree decl = node->decl;
if (DECL_SAVED_TREE (decl)
&& (node->needed
|| (!node->local.inline_many && !node->global.inline_once
&& node->reachable)
|| TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
&& !TREE_ASM_WRITTEN (decl) && !node->origin
&& !DECL_EXTERNAL (decl))
node->output = 1;
}
}
static void
cgraph_display_inlining_step_r (edge)
struct cgraph_edge *edge;
{
if (edge->inliner.uplink)
{
cgraph_display_inlining_step_r (edge->inliner.uplink);
fprintf (stderr, "->");
}
fprintf (stderr, "%s",
IDENTIFIER_POINTER (DECL_NAME (edge->caller->decl)));
}
static void
cgraph_display_inlining_step (edge, verb)
struct cgraph_edge *edge;
const char *verb;
{
fprintf (stderr, "\n[0x%p ", (void *)edge);
cgraph_display_inlining_step_r (edge);
fprintf (stderr, " %s %s edge %llu callee %llu - %llur %e]", verb,
IDENTIFIER_POINTER (DECL_NAME (edge->callee->decl)),
edge->inliner.execution_count,
edge->callee->inliner.execution_count,
edge->callee->inliner.removed_execution_count,
edge->inliner.desirability);
}
void
cgraph_display_function_callgraph (edge, verb)
struct cgraph_edge *edge;
const char *verb;
{
struct cgraph_edge *step;
for (step=edge; step; step=step->next_callee)
{
if (step->inliner.inline_this)
{
cgraph_display_inlining_step (step, verb);
}
else
{
cgraph_display_inlining_step (step, "calls");
cgraph_display_function_callgraph (step->inliner.callees, verb);
}
}
}
static void
cgraph_directed_inlining_r (edge, inlinee_list)
struct cgraph_edge *edge;
varray_type *inlinee_list;
{
struct cgraph_edge *prev, *step;
varray_type callee_array = (varray_type)NULL;
tree *p_2_body, *tp;
int i;
double scale;
HOST_WIDEST_INT scaled_edge_exec_count;
if (edge->inliner.inline_this)
{
scaled_edge_exec_count = edge->inliner.execution_count;
if (edge->callee->inliner.execution_count == 0)
scale = 0.0;
else
scale = (double)edge->inliner.execution_count
/ (double)edge->callee->inliner.execution_count;
{
HOST_WIDEST_INT tweak = 1;
while ((HOST_WIDEST_INT)(scale * edge->callee->inliner.execution_count)
< edge->inliner.execution_count)
scale = (double)edge->inliner.execution_count
/ ((double)edge->callee->inliner.execution_count - tweak++);
tweak = 1;
while ((HOST_WIDEST_INT)(scale * edge->callee->inliner.execution_count)
> edge->inliner.execution_count)
scale = (double)edge->inliner.execution_count
/ ((double)edge->callee->inliner.execution_count + tweak++);
}
if (!quiet_flag)
{
fprintf (stderr, "[scale: %lld/%lld=%f", scaled_edge_exec_count,
edge->callee->inliner.execution_count, scale);
if ((scale > 1.0) || (scale <= 0.0))
fprintf (stderr, " ***error***");
fprintf (stderr, "]");
}
tp = edge->inliner.call_expr;
p_2_body = inline_this_call(tp, edge->callee->decl, scale);
if (edge->callee->global.inline_once)
DECL_SAVED_TREE (edge->callee->decl) = NULL;
if (edge->inliner.callees)
callee_array = cgraph_find_calls (p_2_body);
if (inlinee_list)
VARRAY_PUSH_GENERIC_PTR (*inlinee_list, edge->callee->decl);
for (prev=(struct cgraph_edge *)NULL, i=0, step=edge->inliner.callees;
step;
i++, step=step->next_callee)
{
if ( 0 && flag_use_feedback)
set_times_call_executed (*(tree *)VARRAY_GENERIC_PTR (callee_array, i), step->inliner.execution_count);
step->inliner.prev = prev;
prev = step;
}
for (i--, step=prev; step; i--, step=step->inliner.prev)
{
if (step->inliner.inline_this)
{
step->inliner.call_expr = VARRAY_GENERIC_PTR (callee_array, i);
cgraph_directed_inlining_r (step, inlinee_list);
}
}
}
}
static void
cgraph_clone_parms (clone, fn, arg_map)
tree clone, fn;
splay_tree arg_map;
{
tree *clone_parm = &DECL_ARGUMENTS (clone);
tree fn_parm = DECL_ARGUMENTS (fn);
for ( ; fn_parm; clone_parm = &TREE_CHAIN (*clone_parm), fn_parm = TREE_CHAIN (fn_parm))
{
*clone_parm = copy_node (fn_parm);
DECL_CONTEXT (*clone_parm) = clone;
(void) splay_tree_insert (arg_map,
(splay_tree_key) fn_parm,
(splay_tree_value) *clone_parm);
}
*clone_parm = NULL_TREE;
if (DECL_RESULT (clone))
{
DECL_RESULT (clone) = copy_node (DECL_RESULT (clone));
DECL_CONTEXT (DECL_RESULT (clone)) = clone;
(void) splay_tree_insert (arg_map,
(splay_tree_key) DECL_RESULT (fn),
(splay_tree_value) DECL_RESULT (clone));
}
}
splay_tree_foreach_fn debug_splay_tree_node PARAMS ((struct splay_tree_node_s *, void *));
void debug_splay_tree PARAMS ((splay_tree));
splay_tree_foreach_fn
debug_splay_tree_node (sp, v)
struct splay_tree_node_s *sp;
void *v ATTRIBUTE_UNUSED;
{
fprintf (stderr, "key: "); debug_tree ((tree)sp->key);
fprintf (stderr, "val: "); debug_tree ((tree)sp->value);
return 0;
}
void
debug_splay_tree (sp)
splay_tree sp;
{
splay_tree_foreach (sp, (splay_tree_foreach_fn)debug_splay_tree_node, (void *)NULL);
}
static tree
cgraph_directed_inlining (node)
struct cgraph_node *node;
{
struct cgraph_edge *prev, *step;
varray_type inlinee_list = (varray_type)NULL;
varray_type call_expr_array;
tree clone = node->decl;
int i;
double scale;
if (DECL_LANG_SPECIFIC (node->decl))
VARRAY_GENERIC_PTR_INIT (inlinee_list, 10, "list of inlined functions");
if (!quiet_flag && node->inliner.top_edge && node->inliner.top_edge->inliner.callees)
cgraph_display_function_callgraph (node->inliner.top_edge->inliner.callees, "inlines");
for (step=node->inliner.top_edge->inliner.callees; step; step=step->next_callee)
if (step->inliner.inline_this)
break;
if (step)
{
splay_tree arg_map = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
scale = (((double)node->inliner.execution_count) - ((double)node->inliner.removed_execution_count))
/ ((double)node->inliner.execution_count);
clone = copy_node (node->decl);
current_function_decl = node->decl;
clone_rtx_feedback_counter (node->decl, clone);
current_function_decl = clone;
cgraph_clone_parms (clone, node->decl, arg_map);
DECL_SAVED_TREE (clone) = copy_node (DECL_SAVED_TREE (node->decl));
clone_body_scaled (clone, node->decl, arg_map, 1.0);
DECL_SAVED_TREE (clone) = TREE_CHAIN (DECL_SAVED_TREE (clone));
DECL_INITIAL (clone) = clone_tree_into_context (clone, DECL_INITIAL (clone), arg_map);
BLOCK_SUPERCONTEXT (DECL_INITIAL (clone)) = clone;
call_expr_array = cgraph_find_calls (&DECL_SAVED_TREE (clone));
for (prev=(struct cgraph_edge *)NULL, i=0, step=node->inliner.top_edge->inliner.callees;
step;
i++, step=step->next_callee)
{
step->inliner.prev = prev;
prev = step;
}
for (i--, step=prev; step; i--, step=step->inliner.prev)
{
if (step->inliner.inline_this)
{
step->inliner.call_expr = VARRAY_GENERIC_PTR (call_expr_array, i);
if ( 0 && flag_use_feedback)
set_times_call_executed (*step->inliner.call_expr, step->inliner.execution_count);
cgraph_directed_inlining_r (step, &inlinee_list);
}
}
if (DECL_LANG_SPECIFIC (clone))
{
tree ifn = make_tree_vec (VARRAY_ACTIVE_SIZE (inlinee_list));
if (VARRAY_ACTIVE_SIZE (inlinee_list))
memcpy (&TREE_VEC_ELT (ifn, 0), &VARRAY_TREE (inlinee_list, 0),
VARRAY_ACTIVE_SIZE (inlinee_list) * sizeof (tree));
DECL_INLINED_FNS (clone) = ifn;
}
}
else
{
if (DECL_LANG_SPECIFIC (clone))
DECL_INLINED_FNS (clone) = make_tree_vec (0);
}
current_function_decl = NULL_TREE;
return clone;
}
static void
cgraph_optimize_function (node)
struct cgraph_node *node;
{
if (choices_made)
node->inliner.fully_inlined_decl = cgraph_directed_inlining (node);
else
node->inliner.fully_inlined_decl = node->decl;
if (node->nested)
{
for (node = node->nested; node; node = node->next_nested)
{
cgraph_optimize_function (node);
}
}
}
static void
cgraph_expand_function (node)
struct cgraph_node *node;
{
tree decl = node->decl;
announce_function (decl);
cgraph_optimize_function (node);
(*lang_hooks.callgraph.expand_function) (node->inliner.fully_inlined_decl);
if (node->global.inline_once)
abort ();
node->inliner.fully_inlined_decl = NULL_TREE;
current_function_decl = NULL;
TREE_ASM_WRITTEN (node->decl) = TRUE;
}
static void
cgraph_expand_functions ()
{
struct cgraph_node *node, *node2;
struct cgraph_node **stack =
xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
struct cgraph_node **order =
xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
int stack_size = 0;
int order_pos = 0;
struct cgraph_edge *edge, last;
int i;
cgraph_mark_functions_to_output ();
for (node = cgraph_nodes; node; node = node->next)
node->aux = NULL;
for (node = cgraph_nodes; node; node = node->next)
if (node->output && !node->aux)
{
node2 = node;
if (!node->callers)
node->aux = &last;
else
node->aux = node->callers;
while (node2)
{
while (node2->aux != &last)
{
edge = node2->aux;
if (edge->next_caller)
node2->aux = edge->next_caller;
else
node2->aux = &last;
if (!edge->caller->aux)
{
if (!edge->caller->callers)
edge->caller->aux = &last;
else
edge->caller->aux = edge->caller->callers;
stack[stack_size++] = node2;
node2 = edge->caller;
break;
}
}
if (node2->aux == &last)
{
order[order_pos++] = node2;
if (stack_size)
node2 = stack[--stack_size];
else
node2 = NULL;
}
}
}
for (i = order_pos - 1; i >= 0; i--)
{
node = order[i];
if (node->output)
{
if (!node->reachable)
abort ();
node->output = 0;
cgraph_expand_function (node);
}
}
free (stack);
free (order);
}
static inline void
cgraph_mark_local_functions ()
{
struct cgraph_node *node;
if (!quiet_flag)
fprintf (stderr, "\n\nMarking local functions:");
for (node = cgraph_nodes; node; node = node->next)
{
node->local.local = (!node->needed
&& DECL_SAVED_TREE (node->decl)
&& !TREE_PUBLIC (node->decl));
if (node->local.local)
announce_function (node->decl);
}
}
static inline void
cgraph_mark_functions_to_inline_once ()
{
struct cgraph_node *node, *node1;
if (!quiet_flag)
fprintf (stderr, "\n\nMarking functions to inline once:");
for (node = cgraph_nodes; node; node = node->next)
{
if (node->callers && !node->callers->next_caller && !node->needed
&& node->local.can_inline_once)
{
bool ok = true;
for (node1 = node->callers->caller;
node1->local.inline_many
&& node1->callers
&& ok;
node1 = node1->callers->caller)
if (node1->callers->next_caller || node1->needed)
ok = false;
if (ok)
{
node->global.inline_once = true;
announce_function (node->decl);
}
}
}
}
static bool
cgraph_inlinable_function_p (fn)
tree fn;
{
tree fntype;
if (!DECL_SAVED_TREE (fn))
return FALSE;
fntype = TREE_TYPE (fn);
if ((TYPE_ARG_TYPES (fntype) != 0)
&& (TREE_VALUE (tree_last (TYPE_ARG_TYPES (fntype)))
!= void_type_node))
return FALSE;
if (find_builtin_longjmp_call (DECL_SAVED_TREE (fn)))
return FALSE;
if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)) == NULL
&& find_alloca_call (DECL_SAVED_TREE (fn)))
return FALSE;
if (lookup_attribute ("noinline", DECL_ATTRIBUTES (fn)))
return FALSE;
if ((*lang_hooks.tree_inlining.cannot_inline_tree_fn) (&fn))
return FALSE;
return TRUE;
}
static inline double
cgraph_call_body_desirability (struct cgraph_node *node)
{
double desirability=0.0;
unsigned long stmts;
if (node && cgraph_inlinable_function_p (node->decl))
{
desirability = 1.0;
stmts = DECL_NUM_STMTS (node->decl);
if (stmts == 0)
stmts = 1;
if (node->global.inline_once)
desirability = DBL_MAX;
else if (flag_callgraph_inline_small
&& (stmts <= flag_callgraph_inline_small))
desirability = DBL_MAX;
else if ( node->local.inline_many)
desirability = 100.0 / stmts;
}
return desirability;
}
double
cgraph_call_desirability (struct cgraph_edge *edge)
{
double desirability = 0.0, scale;
struct cgraph_node *callee, *caller, *top_node;
struct cgraph_edge *up, *top_edge;
if (edge->callee && edge->callee->inliner.body_desirability > 0.0)
{
callee = edge->callee;
caller = edge->caller;
desirability = callee->inliner.body_desirability;
if (flag_use_feedback)
{
scale = (caller->inliner.execution_count - caller->inliner.removed_execution_count) / caller->inliner.execution_count;
desirability *= (edge->inliner.execution_count * scale);
if (flag_callgraph_inlining_callee_ratio)
{
if ((100 * edge->inliner.execution_count) <
(flag_callgraph_inlining_callee_ratio * edge->callee->inliner.execution_count))
desirability = 0.0;
}
if (flag_callgraph_inlining_caller_ratio)
{
if ((100 * edge->inliner.execution_count) <
(flag_callgraph_inlining_caller_ratio * edge->caller->inliner.execution_count))
desirability = 0.0;
}
}
if (callee->global.inline_once
|| lookup_attribute ("always_inline", DECL_ATTRIBUTES (callee->decl)))
desirability = DBL_MAX;
else if (flag_callgraph_inline_small
&& (DECL_NUM_STMTS (callee->decl) <= flag_callgraph_inline_small))
desirability = DBL_MAX;
for (top_edge=up=edge; up->inliner.uplink; top_edge=up, up=up->inliner.uplink)
if (up->caller == callee)
desirability = 0.0;
top_node = top_edge->caller;
if (top_node->global.inline_once
|| (DECL_NUM_STMTS (top_node->decl) + top_node->inliner.additional_lines
> 300))
desirability = 0.0;
}
if (desirability < 0.0)
fprintf (stderr, "\n[*** error bad desirability: 0x%p %f]\n", (void *)edge, desirability);
return desirability;
}
static inline void
revise_desirabilities_r (edge)
struct cgraph_edge *edge;
{
struct cgraph_edge *step;
for (step=edge; step; step=step->next_callee)
{
step->inliner.desirability = cgraph_call_desirability (step);
if (step->inliner.callees)
revise_desirabilities_r (step->inliner.callees);
}
}
static inline HOST_WIDEST_INT
scaled_execution_count (edge)
struct cgraph_edge *edge;
{
struct cgraph_edge *step;
struct cgraph_node *callee, *top_caller;
double combined_scale=1.0, scale;
HOST_WIDEST_INT scaled_execution_count;
if (!edge)
return (HOST_WIDEST_INT)0;
if (edge->inliner.uplink)
{
for (step=edge; step->inliner.uplink; step=step->inliner.uplink)
{
callee = step->callee;
scale = ((double)step->inliner.execution_count)
/ (double)callee->inliner.execution_count;
combined_scale *= scale;
}
}
else
step = edge;
top_caller = step->caller;
scale = ((double)top_caller->inliner.execution_count - (double)top_caller->inliner.removed_execution_count)
/ (double)top_caller->inliner.execution_count;
combined_scale *= scale;
scaled_execution_count = (HOST_WIDEST_INT) (edge->inliner.execution_count * combined_scale);
return scaled_execution_count;
}
static inline struct cgraph_edge *
cgraph_most_desirable_edge (edge)
struct cgraph_edge *edge;
{
struct cgraph_edge *child_hottest, *hottest=NULL, *step=edge;
float child_hottest_desirability = 0.0, hottest_desirability = 0.0;
for (step = edge ; step ; step = step->next_callee)
{
if (step->inliner.inline_this && step->inliner.callees)
{
child_hottest = cgraph_most_desirable_edge (step->inliner.callees);
child_hottest_desirability = (child_hottest) ? child_hottest->inliner.desirability : 0.0 ;
if (child_hottest_desirability > hottest_desirability)
{
hottest = child_hottest;
hottest_desirability = child_hottest_desirability;
}
}
else if ((!step->inliner.inline_this)
&& (step->inliner.desirability > hottest_desirability))
{
hottest = step;
hottest_desirability = hottest->inliner.desirability;
}
}
return hottest;
}
static inline void
cgraph_make_inlining_choices ()
{
struct cgraph_node *node;
struct cgraph_edge *edge;
unsigned long bloat_estimate=0, bloat_limit;
unsigned long total_original_statements=0;
varray_type caller_nodes_varray;
bool more, only_call;
HOST_WIDEST_INT max_edge_exec_count = 0;
if (!quiet_flag)
fprintf (stderr, "\n\nMaking inlining decisions:");
VARRAY_GENERIC_PTR_INIT(caller_nodes_varray, 10, "node vector");
for (node = cgraph_nodes; node; node = node->next)
{
node->inliner.name = (char *)IDENTIFIER_POINTER (DECL_NAME (node->decl));
node->inliner.highest_desirability = 0.0;
node->inliner.most_desirable_edge = NULL;
node->inliner.additional_lines = 0;
node->inliner.removed_execution_count = 0;
node->inliner.top_edge = create_edge ((struct cgraph_node *)NULL,
(struct cgraph_node *)NULL,
(tree *)NULL);
node->inliner.top_edge->inliner.callees = cgraph_inlining_callee_list (node, &DECL_SAVED_TREE(node->decl));
node->inliner.top_edge->inliner.callee_array = (varray_type)NULL;
if (node->inliner.top_edge->inliner.callees)
VARRAY_PUSH (caller_nodes_varray, generic, node);
node->inliner.top_edge->inliner.inline_this = FALSE;
node->inliner.body_desirability = cgraph_call_body_desirability (node);
node->inliner.callee_count = 0;
if (DECL_SAVED_TREE (node->decl))
node->inliner.execution_count = times_arc_executed (node->decl, 0);
else
node->inliner.execution_count = 0;
total_original_statements += DECL_NUM_STMTS (node->decl);
}
if (flag_callgraph_inlining_count)
{
bloat_limit = 0;
if (!quiet_flag)
fprintf (stderr, "\n[** original statements: %lu inline edges with execution counts above %llu]\n",
total_original_statements, flag_callgraph_inlining_count);
}
else if (flag_callgraph_inlining_limit)
{
unsigned long fully_inlined_size_100 = total_original_statements
* (flag_callgraph_inlining_limit + 100);
unsigned long fully_inlined_size = fully_inlined_size_100 / 100;
bloat_limit = fully_inlined_size - total_original_statements;
if (!quiet_flag)
fprintf (stderr, "\n[** original statements: %lu bloat limit: %lu (%u%%)]\n",
total_original_statements, bloat_limit, flag_callgraph_inlining_limit);
}
else
bloat_limit = MAX_INLINE_INSNS / INSNS_PER_STMT;
for (node = cgraph_nodes; node; node = node->next)
{
if (node->inliner.top_edge->inliner.callees)
{
VARRAY_GENERIC_PTR_INIT(node->inliner.top_edge->inliner.callee_array,
10, "callee edges");
for (edge = node->inliner.top_edge->inliner.callees;
edge;
edge = edge->next_callee)
{
VARRAY_PUSH_GENERIC_PTR (node->inliner.top_edge->inliner.callee_array, edge);
if (flag_use_feedback)
edge->inliner.execution_count = times_call_executed (*edge->inliner.call_expr);
edge->inliner.desirability = cgraph_call_desirability (edge);
if (edge->inliner.desirability > node->inliner.highest_desirability)
{
node->inliner.highest_desirability = edge->inliner.desirability;
node->inliner.most_desirable_edge = edge;
}
}
}
}
if (flag_use_feedback
&& flag_callgraph_inlining_ratio)
{
for (node = cgraph_nodes; node; node = node->next)
for (edge = node->inliner.top_edge->inliner.callees;
edge;
edge = edge->next_callee)
{
if (edge->inliner.execution_count > max_edge_exec_count)
max_edge_exec_count = edge->inliner.execution_count;
}
max_edge_exec_count *= flag_callgraph_inlining_ratio;
}
do {
unsigned int i, limit, new_statements;
float hottest_fn_desirability = 0.0;
struct cgraph_node *callee, *hottest_fn = (struct cgraph_node *)NULL, *step;
struct cgraph_edge *s_edge;
more = FALSE;
limit = VARRAY_ACTIVE_SIZE (caller_nodes_varray);
for (i = 0; i < limit; i++)
{
step = VARRAY_GENERIC_PTR (caller_nodes_varray, i);
if (step->inliner.highest_desirability > hottest_fn_desirability)
{
hottest_fn = step;
hottest_fn_desirability = hottest_fn->inliner.highest_desirability;
}
}
if ( ! hottest_fn)
break;
new_statements = DECL_NUM_STMTS (hottest_fn->inliner.most_desirable_edge->callee->decl);
if (new_statements == 0)
new_statements = 1;
only_call = hottest_fn->inliner.most_desirable_edge->callee->global.inline_once;
if (only_call
|| ((new_statements + bloat_estimate) < (unsigned int)bloat_limit)
|| (flag_callgraph_inlining_count
&& (hottest_fn->inliner.most_desirable_edge->inliner.execution_count > flag_callgraph_inlining_count))
|| (flag_callgraph_inlining_ratio
&& ((100 * hottest_fn->inliner.most_desirable_edge->inliner.execution_count) > max_edge_exec_count))
|| (flag_callgraph_inline_small
&& (new_statements < flag_callgraph_inline_small)))
{
if (!quiet_flag)
cgraph_display_inlining_step (hottest_fn->inliner.most_desirable_edge, "chooses");
cgraph_record_inlining_choice (hottest_fn->inliner.most_desirable_edge);
callee = hottest_fn->inliner.most_desirable_edge->callee;
callee->inliner.removed_execution_count += hottest_fn->inliner.most_desirable_edge->inliner.execution_count;
for (s_edge = hottest_fn->inliner.most_desirable_edge->inliner.callees;
s_edge ;
s_edge = s_edge->next_callee)
{
s_edge->callee->inliner.removed_execution_count -= s_edge->inliner.execution_count;
}
if (!quiet_flag && callee->inliner.removed_execution_count > callee->inliner.execution_count)
fprintf (stderr, "\n[bad removed_exec_count 0x%p %llu %llu]\n",
(void *)callee, callee->inliner.execution_count, callee->inliner.removed_execution_count);
revise_desirabilities_r (callee->inliner.top_edge);
hottest_fn->inliner.additional_lines += new_statements;
if (!only_call)
bloat_estimate += new_statements;
hottest_fn->inliner.most_desirable_edge = cgraph_most_desirable_edge (hottest_fn->inliner.top_edge->inliner.callees);
hottest_fn->inliner.highest_desirability = (hottest_fn->inliner.most_desirable_edge)
? hottest_fn->inliner.most_desirable_edge->inliner.desirability
: -1.0;
more = TRUE;
}
} while (more);
choices_made = TRUE;
}
void
cgraph_optimize ()
{
struct cgraph_node *node;
bool changed = true;
cgraph_mark_local_functions ();
cgraph_mark_functions_to_inline_once ();
if (flag_callgraph_inlining && !flag_create_feedback)
cgraph_make_inlining_choices ();
cgraph_global_info_ready = true;
if (!quiet_flag)
dump_cgraph (stderr);
if (!quiet_flag)
fprintf (stderr, "\n\nAssembling functions:");
cgraph_expand_functions ();
if (!quiet_flag)
fprintf (stderr, "\n\nAssembling functions that failed to inline:");
while (changed && !errorcount && !sorrycount)
{
changed = false;
for (node = cgraph_nodes; node; node = node->next)
{
tree decl = node->decl;
if (!node->origin
&& !TREE_ASM_WRITTEN (decl)
&& DECL_SAVED_TREE (decl)
&& !DECL_EXTERNAL (decl))
{
struct cgraph_edge *edge;
for (edge = node->callers; edge; edge = edge->next_caller)
if (TREE_ASM_WRITTEN (edge->caller->decl))
{
changed = true;
cgraph_expand_function (node);
break;
}
}
}
}
}
#include "gt-cgraphunit.h"