#include "config.h"
#include "system.h"
#include "tree.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"
static GTY(()) varray_type known_fns;
static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
struct cgraph_node *cgraph_nodes;
int cgraph_n_nodes;
bool cgraph_global_info_ready = false;
static void cgraph_remove_edge PARAMS ((struct cgraph_node *, struct cgraph_node *));
static hashval_t hash_node PARAMS ((const PTR));
static int eq_node PARAMS ((const PTR, const PTR));
static struct cgraph_edge *clone_callee_list PARAMS ((struct cgraph_edge *, struct cgraph_edge *));
static char *callee_string PARAMS ((tree));
static void dump_inlining_choices PARAMS ((FILE *, struct cgraph_edge *));
static hashval_t
hash_node (p)
const PTR p;
{
return (hashval_t)
htab_hash_pointer (DECL_ASSEMBLER_NAME
(((struct cgraph_node *) p)->decl));
}
static int
eq_node (p1, p2)
const PTR p1;
const PTR p2;
{
return ((DECL_ASSEMBLER_NAME (((struct cgraph_node *) p1)->decl)) ==
DECL_ASSEMBLER_NAME ((tree) p2));
}
struct cgraph_node *
cgraph_node (decl)
tree decl;
{
struct cgraph_node *node;
struct cgraph_node **slot;
struct cgraph_node *step;
static bool cgraph_hash_init = FALSE;
if (TREE_CODE (decl) != FUNCTION_DECL)
abort ();
if (!cgraph_hash_init)
{
cgraph_hash = htab_create_ggc (10, hash_node, eq_node, NULL);
VARRAY_TREE_INIT (known_fns, 32, "known_fns");
for (step = cgraph_nodes; step ; step = step->next)
{
slot =
(struct cgraph_node **)
htab_find_slot_with_hash (cgraph_hash, step->decl,
htab_hash_pointer
(DECL_ASSEMBLER_NAME
(step->decl)), 1);
*slot = step;
}
cgraph_hash_init = TRUE;
}
slot =
(struct cgraph_node **) htab_find_slot_with_hash (cgraph_hash, decl,
htab_hash_pointer
(DECL_ASSEMBLER_NAME
(decl)), 1);
if (*slot)
return *slot;
node = (struct cgraph_node *) ggc_alloc_cleared (sizeof (*node));
node->decl = decl;
node->next = cgraph_nodes;
if (cgraph_nodes)
cgraph_nodes->previous = node;
node->previous = NULL;
cgraph_nodes = node;
cgraph_n_nodes++;
*slot = node;
if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
{
node->origin = cgraph_node (DECL_CONTEXT (decl));
node->next_nested = node->origin->nested;
node->origin->nested = node;
}
VARRAY_PUSH_TREE (known_fns, decl);
return node;
}
struct cgraph_edge *
create_edge (caller, callee, call_expr)
struct cgraph_node *caller, *callee;
tree *call_expr;
{
struct cgraph_edge *edge = (struct cgraph_edge *) ggc_alloc_cleared (sizeof (struct cgraph_edge));
edge->caller = caller;
edge->callee = callee;
if (callee)
{
edge->next_caller = callee->callers;
callee->callers = edge;
}
if (caller)
{
edge->next_callee = caller->callees;
caller->callees = edge;
}
edge->inliner.call_expr = call_expr;
return edge;
}
static void
cgraph_remove_edge (caller, callee)
struct cgraph_node *caller, *callee;
{
struct cgraph_edge **edge, **edge2;
for (edge = &callee->callers; *edge && (*edge)->caller != caller;
edge = &((*edge)->next_caller))
continue;
if (!*edge)
abort ();
*edge = (*edge)->next_caller;
for (edge2 = &caller->callees; *edge2 && (*edge2)->callee != callee;
edge2 = &(*edge2)->next_callee)
continue;
if (!*edge2)
abort ();
*edge2 = (*edge2)->next_callee;
}
void
cgraph_remove_node (node)
struct cgraph_node *node;
{
while (node->callers)
cgraph_remove_edge (node->callers->caller, node);
while (node->callees)
cgraph_remove_edge (node, node->callees->callee);
while (node->nested)
cgraph_remove_node (node->nested);
if (node->origin)
{
struct cgraph_node **node2 = &node->origin->nested;
while (*node2 != node)
node2 = &(*node2)->next_nested;
*node2 = node->next_nested;
}
if (node->previous)
node->previous->next = node->next;
else
cgraph_nodes = node;
if (node->next)
node->next->previous = node->previous;
DECL_SAVED_TREE (node->decl) = NULL;
}
struct cgraph_edge *
cgraph_record_call (caller, callee, call_expr, invocations)
tree caller, callee, *call_expr;
HOST_WIDE_INT invocations;
{
struct cgraph_node *node = cgraph_node (caller);
struct cgraph_edge *edge = create_edge (cgraph_node (caller), cgraph_node (callee), call_expr);
varray_type callee_array = (varray_type)NULL;
edge->inliner.invocations = invocations;
edge->inliner.desirability = cgraph_call_desirability (edge);
node->inliner.callee_count++;
if (node->inliner.top_edge)
callee_array = node->inliner.top_edge->inliner.callee_array;
if (callee_array)
VARRAY_PUSH_GENERIC_PTR (callee_array, call_expr);
return edge;
}
void
cgraph_remove_call (caller, callee)
tree caller, callee;
{
cgraph_remove_edge (cgraph_node (caller), cgraph_node (callee));
}
bool
cgraph_calls_p (caller_decl, callee_decl)
tree caller_decl, callee_decl;
{
struct cgraph_node *caller = cgraph_node (caller_decl);
struct cgraph_node *callee = cgraph_node (callee_decl);
struct cgraph_edge *edge;
for (edge = callee->callers; edge && (edge)->caller != caller;
edge = (edge->next_caller))
continue;
return edge != NULL;
}
struct cgraph_local_info *
cgraph_local_info (decl)
tree decl;
{
struct cgraph_node *node;
if (TREE_CODE (decl) != FUNCTION_DECL)
abort ();
node = cgraph_node (decl);
return &node->local;
}
struct cgraph_global_info *
cgraph_global_info (decl)
tree decl;
{
struct cgraph_node *node;
if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
abort ();
node = cgraph_node (decl);
return &node->global;
}
struct cgraph_rtl_info *
cgraph_rtl_info (decl)
tree decl;
{
struct cgraph_node *node;
if (TREE_CODE (decl) != FUNCTION_DECL)
abort ();
node = cgraph_node (decl);
if (decl != current_function_decl
&& !TREE_ASM_WRITTEN (node->decl))
return NULL;
return &node->rtl;
}
static inline struct cgraph_edge *
clone_callee_list (callee, caller)
struct cgraph_edge *callee, *caller;
{
struct cgraph_edge *callee_list = callee->inliner.callees;
struct cgraph_edge *new_list=NULL, *new, *prev=(struct cgraph_edge *)NULL, *step;
double scale;
if (caller->callee->inliner.execution_count == 0)
scale = 0.0;
else
scale = (double)caller->inliner.execution_count
/ (double)caller->callee->inliner.execution_count;
{
HOST_WIDEST_INT tweak = 1;
unsigned int maxtweak = 10;
while (((HOST_WIDEST_INT)(scale * caller->callee->inliner.execution_count)
< caller->inliner.execution_count)
&& --maxtweak)
scale = (double)caller->inliner.execution_count
/ ((double)caller->callee->inliner.execution_count - tweak++);
tweak = 1;
maxtweak = 10;
while (((HOST_WIDEST_INT)(scale * caller->callee->inliner.execution_count)
> caller->inliner.execution_count)
&& --maxtweak)
scale = (double)caller->inliner.execution_count
/ ((double)caller->callee->inliner.execution_count + tweak++);
}
for (step = callee_list ; step ; step = step->next_callee)
{
new = create_edge (step->caller, step->callee, (tree *)NULL);
*new = *step;
new->inliner.inline_this = FALSE;
new->inliner.callees = (struct cgraph_edge *)NULL;
new->inliner.callee_array = (varray_type)NULL;
new->inliner.uplink = caller;
if (flag_use_feedback)
{
new->inliner.execution_count =
(HOST_WIDE_INT)(step->inliner.execution_count * scale);
new->inliner.desirability = cgraph_call_desirability (new);
}
new->next_caller = (struct cgraph_edge *)NULL;
if (prev)
prev->next_callee = new;
if (!new_list)
new_list = new;
prev = new;
}
return new_list;
}
void
cgraph_record_inlining_choice (edge)
struct cgraph_edge *edge;
{
edge->inliner.callees = clone_callee_list (edge->callee->inliner.top_edge, edge);
edge->inliner.callee_array = NULL;
edge->inliner.inline_this = TRUE;
}
static inline char *
callee_string (call_node)
tree call_node;
{
tree addr_node, decl_node;
if (TREE_CODE (call_node) == CALL_EXPR)
{
addr_node = TREE_OPERAND (call_node, 0);
if (TREE_CODE (addr_node) == ADDR_EXPR)
{
decl_node = TREE_OPERAND (addr_node, 0);
if (TREE_CODE (decl_node) == FUNCTION_DECL)
return (char *) IDENTIFIER_POINTER (DECL_NAME (decl_node));
}
}
abort();
}
static inline void
dump_inlining_choices (f, inlines)
FILE *f;
struct cgraph_edge *inlines;
{
struct cgraph_edge *step;
char *name;
for (step = inlines; step; step = step->next_callee)
{
name = callee_string (*step->inliner.call_expr);
fprintf (f, " %s", name ? name : "");
fprintf (f, " [%llu %e]", step->inliner.execution_count,
step->inliner.desirability);
if (step->inliner.callees)
{
fprintf (f, "(");
dump_inlining_choices (f, step->inliner.callees);
fprintf (f, ")");
}
}
}
void
dump_cgraph (f)
FILE *f;
{
struct cgraph_node *node;
fprintf (f, "\nCallgraph:\n\n");
for (node = cgraph_nodes; node; node = node->next)
{
struct cgraph_edge *edge;
fprintf (f, "%s", IDENTIFIER_POINTER (DECL_NAME (node->decl)));
if (node->origin)
fprintf (f, " nested in: %s",
IDENTIFIER_POINTER (DECL_NAME (node->origin->decl)));
if (node->needed)
fprintf (f, " needed");
else if (node->reachable)
fprintf (f, " reachable");
if (DECL_SAVED_TREE (node->decl))
fprintf (f, " tree");
fprintf (f, "\n called by :");
for (edge = node->callers; edge; edge = edge->next_caller)
fprintf (f, "%s ",
IDENTIFIER_POINTER (DECL_NAME (edge->caller->decl)));
fprintf (f, "\n calls: ");
for (edge = node->callees; edge; edge = edge->next_callee)
fprintf (f, "%s ",
IDENTIFIER_POINTER (DECL_NAME (edge->callee->decl)));
if (node->inliner.top_edge && node->inliner.top_edge->inliner.callees)
{
fprintf (f, "\n inlines: ");
dump_inlining_choices (f, node->inliner.top_edge->inliner.callees);
}
else
fprintf (f, "\n (no inlines)");
fprintf (f, "\n decl: %p saved_tree: %p exec_count: %llu\n",
(void *)node->decl, (void *)DECL_SAVED_TREE (node->decl),
node->inliner.execution_count);
fprintf (f, "\n");
}
}
#include "gt-cgraph.h"