/* Utilities for ipa analysis.
|
/* Utilities for ipa analysis.
|
Copyright (C) 2005, 2007 Free Software Foundation, Inc.
|
Copyright (C) 2005, 2007 Free Software Foundation, Inc.
|
Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
|
Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it under
|
GCC is free software; you can redistribute it and/or modify it under
|
the terms of the GNU General Public License as published by the Free
|
the terms of the GNU General Public License as published by the Free
|
Software Foundation; either version 3, or (at your option) any later
|
Software Foundation; either version 3, or (at your option) any later
|
version.
|
version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "tree-inline.h"
|
#include "tree-inline.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
#include "langhooks.h"
|
#include "langhooks.h"
|
#include "pointer-set.h"
|
#include "pointer-set.h"
|
#include "ggc.h"
|
#include "ggc.h"
|
#include "ipa-utils.h"
|
#include "ipa-utils.h"
|
#include "ipa-reference.h"
|
#include "ipa-reference.h"
|
#include "c-common.h"
|
#include "c-common.h"
|
#include "tree-gimple.h"
|
#include "tree-gimple.h"
|
#include "cgraph.h"
|
#include "cgraph.h"
|
#include "output.h"
|
#include "output.h"
|
#include "flags.h"
|
#include "flags.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "diagnostic.h"
|
#include "diagnostic.h"
|
#include "langhooks.h"
|
#include "langhooks.h"
|
|
|
/* Debugging function for postorder and inorder code. NOTE is a string
|
/* Debugging function for postorder and inorder code. NOTE is a string
|
that is printed before the nodes are printed. ORDER is an array of
|
that is printed before the nodes are printed. ORDER is an array of
|
cgraph_nodes that has COUNT useful nodes in it. */
|
cgraph_nodes that has COUNT useful nodes in it. */
|
|
|
void
|
void
|
ipa_utils_print_order (FILE* out,
|
ipa_utils_print_order (FILE* out,
|
const char * note,
|
const char * note,
|
struct cgraph_node** order,
|
struct cgraph_node** order,
|
int count)
|
int count)
|
{
|
{
|
int i;
|
int i;
|
fprintf (out, "\n\n ordered call graph: %s\n", note);
|
fprintf (out, "\n\n ordered call graph: %s\n", note);
|
|
|
for (i = count - 1; i >= 0; i--)
|
for (i = count - 1; i >= 0; i--)
|
dump_cgraph_node(dump_file, order[i]);
|
dump_cgraph_node(dump_file, order[i]);
|
fprintf (out, "\n");
|
fprintf (out, "\n");
|
fflush(out);
|
fflush(out);
|
}
|
}
|
|
|
|
|
struct searchc_env {
|
struct searchc_env {
|
struct cgraph_node **stack;
|
struct cgraph_node **stack;
|
int stack_size;
|
int stack_size;
|
struct cgraph_node **result;
|
struct cgraph_node **result;
|
int order_pos;
|
int order_pos;
|
splay_tree nodes_marked_new;
|
splay_tree nodes_marked_new;
|
bool reduce;
|
bool reduce;
|
int count;
|
int count;
|
};
|
};
|
|
|
/* This is an implementation of Tarjan's strongly connected region
|
/* This is an implementation of Tarjan's strongly connected region
|
finder as reprinted in Aho Hopcraft and Ullman's The Design and
|
finder as reprinted in Aho Hopcraft and Ullman's The Design and
|
Analysis of Computer Programs (1975) pages 192-193. This version
|
Analysis of Computer Programs (1975) pages 192-193. This version
|
has been customized for cgraph_nodes. The env parameter is because
|
has been customized for cgraph_nodes. The env parameter is because
|
it is recursive and there are no nested functions here. This
|
it is recursive and there are no nested functions here. This
|
function should only be called from itself or
|
function should only be called from itself or
|
cgraph_reduced_inorder. ENV is a stack env and would be
|
cgraph_reduced_inorder. ENV is a stack env and would be
|
unnecessary if C had nested functions. V is the node to start
|
unnecessary if C had nested functions. V is the node to start
|
searching from. */
|
searching from. */
|
|
|
static void
|
static void
|
searchc (struct searchc_env* env, struct cgraph_node *v)
|
searchc (struct searchc_env* env, struct cgraph_node *v)
|
{
|
{
|
struct cgraph_edge *edge;
|
struct cgraph_edge *edge;
|
struct ipa_dfs_info *v_info = v->aux;
|
struct ipa_dfs_info *v_info = v->aux;
|
|
|
/* mark node as old */
|
/* mark node as old */
|
v_info->new = false;
|
v_info->new = false;
|
splay_tree_remove (env->nodes_marked_new, v->uid);
|
splay_tree_remove (env->nodes_marked_new, v->uid);
|
|
|
v_info->dfn_number = env->count;
|
v_info->dfn_number = env->count;
|
v_info->low_link = env->count;
|
v_info->low_link = env->count;
|
env->count++;
|
env->count++;
|
env->stack[(env->stack_size)++] = v;
|
env->stack[(env->stack_size)++] = v;
|
v_info->on_stack = true;
|
v_info->on_stack = true;
|
|
|
for (edge = v->callees; edge; edge = edge->next_callee)
|
for (edge = v->callees; edge; edge = edge->next_callee)
|
{
|
{
|
struct ipa_dfs_info * w_info;
|
struct ipa_dfs_info * w_info;
|
struct cgraph_node *w = edge->callee;
|
struct cgraph_node *w = edge->callee;
|
/* Bypass the clones and only look at the master node. Skip
|
/* Bypass the clones and only look at the master node. Skip
|
external and other bogus nodes. */
|
external and other bogus nodes. */
|
w = cgraph_master_clone (w);
|
w = cgraph_master_clone (w);
|
if (w && w->aux)
|
if (w && w->aux)
|
{
|
{
|
w_info = w->aux;
|
w_info = w->aux;
|
if (w_info->new)
|
if (w_info->new)
|
{
|
{
|
searchc (env, w);
|
searchc (env, w);
|
v_info->low_link =
|
v_info->low_link =
|
(v_info->low_link < w_info->low_link) ?
|
(v_info->low_link < w_info->low_link) ?
|
v_info->low_link : w_info->low_link;
|
v_info->low_link : w_info->low_link;
|
}
|
}
|
else
|
else
|
if ((w_info->dfn_number < v_info->dfn_number)
|
if ((w_info->dfn_number < v_info->dfn_number)
|
&& (w_info->on_stack))
|
&& (w_info->on_stack))
|
v_info->low_link =
|
v_info->low_link =
|
(w_info->dfn_number < v_info->low_link) ?
|
(w_info->dfn_number < v_info->low_link) ?
|
w_info->dfn_number : v_info->low_link;
|
w_info->dfn_number : v_info->low_link;
|
}
|
}
|
}
|
}
|
|
|
|
|
if (v_info->low_link == v_info->dfn_number)
|
if (v_info->low_link == v_info->dfn_number)
|
{
|
{
|
struct cgraph_node *last = NULL;
|
struct cgraph_node *last = NULL;
|
struct cgraph_node *x;
|
struct cgraph_node *x;
|
struct ipa_dfs_info *x_info;
|
struct ipa_dfs_info *x_info;
|
do {
|
do {
|
x = env->stack[--(env->stack_size)];
|
x = env->stack[--(env->stack_size)];
|
x_info = x->aux;
|
x_info = x->aux;
|
x_info->on_stack = false;
|
x_info->on_stack = false;
|
|
|
if (env->reduce)
|
if (env->reduce)
|
{
|
{
|
x_info->next_cycle = last;
|
x_info->next_cycle = last;
|
last = x;
|
last = x;
|
}
|
}
|
else
|
else
|
env->result[env->order_pos++] = x;
|
env->result[env->order_pos++] = x;
|
}
|
}
|
while (v != x);
|
while (v != x);
|
if (env->reduce)
|
if (env->reduce)
|
env->result[env->order_pos++] = v;
|
env->result[env->order_pos++] = v;
|
}
|
}
|
}
|
}
|
|
|
/* Topsort the call graph by caller relation. Put the result in ORDER.
|
/* Topsort the call graph by caller relation. Put the result in ORDER.
|
|
|
The REDUCE flag is true if you want the cycles reduced to single
|
The REDUCE flag is true if you want the cycles reduced to single
|
nodes. Only consider nodes that have the output bit set. */
|
nodes. Only consider nodes that have the output bit set. */
|
|
|
int
|
int
|
ipa_utils_reduced_inorder (struct cgraph_node **order,
|
ipa_utils_reduced_inorder (struct cgraph_node **order,
|
bool reduce, bool allow_overwritable)
|
bool reduce, bool allow_overwritable)
|
{
|
{
|
struct cgraph_node *node;
|
struct cgraph_node *node;
|
struct searchc_env env;
|
struct searchc_env env;
|
splay_tree_node result;
|
splay_tree_node result;
|
env.stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
|
env.stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
|
env.stack_size = 0;
|
env.stack_size = 0;
|
env.result = order;
|
env.result = order;
|
env.order_pos = 0;
|
env.order_pos = 0;
|
env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
|
env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
|
env.count = 1;
|
env.count = 1;
|
env.reduce = reduce;
|
env.reduce = reduce;
|
|
|
for (node = cgraph_nodes; node; node = node->next)
|
for (node = cgraph_nodes; node; node = node->next)
|
if ((node->analyzed)
|
if ((node->analyzed)
|
&& (cgraph_is_master_clone (node)
|
&& (cgraph_is_master_clone (node)
|
|| (allow_overwritable
|
|| (allow_overwritable
|
&& (cgraph_function_body_availability (node) ==
|
&& (cgraph_function_body_availability (node) ==
|
AVAIL_OVERWRITABLE))))
|
AVAIL_OVERWRITABLE))))
|
{
|
{
|
/* Reuse the info if it is already there. */
|
/* Reuse the info if it is already there. */
|
struct ipa_dfs_info *info = node->aux;
|
struct ipa_dfs_info *info = node->aux;
|
if (!info)
|
if (!info)
|
info = xcalloc (1, sizeof (struct ipa_dfs_info));
|
info = xcalloc (1, sizeof (struct ipa_dfs_info));
|
info->new = true;
|
info->new = true;
|
info->on_stack = false;
|
info->on_stack = false;
|
info->next_cycle = NULL;
|
info->next_cycle = NULL;
|
node->aux = info;
|
node->aux = info;
|
|
|
splay_tree_insert (env.nodes_marked_new,
|
splay_tree_insert (env.nodes_marked_new,
|
(splay_tree_key)node->uid,
|
(splay_tree_key)node->uid,
|
(splay_tree_value)node);
|
(splay_tree_value)node);
|
}
|
}
|
else
|
else
|
node->aux = NULL;
|
node->aux = NULL;
|
result = splay_tree_min (env.nodes_marked_new);
|
result = splay_tree_min (env.nodes_marked_new);
|
while (result)
|
while (result)
|
{
|
{
|
node = (struct cgraph_node *)result->value;
|
node = (struct cgraph_node *)result->value;
|
searchc (&env, node);
|
searchc (&env, node);
|
result = splay_tree_min (env.nodes_marked_new);
|
result = splay_tree_min (env.nodes_marked_new);
|
}
|
}
|
splay_tree_delete (env.nodes_marked_new);
|
splay_tree_delete (env.nodes_marked_new);
|
free (env.stack);
|
free (env.stack);
|
|
|
return env.order_pos;
|
return env.order_pos;
|
}
|
}
|
|
|
|
|
/* Given a memory reference T, will return the variable at the bottom
|
/* Given a memory reference T, will return the variable at the bottom
|
of the access. Unlike get_base_address, this will recurse thru
|
of the access. Unlike get_base_address, this will recurse thru
|
INDIRECT_REFS. */
|
INDIRECT_REFS. */
|
|
|
tree
|
tree
|
get_base_var (tree t)
|
get_base_var (tree t)
|
{
|
{
|
if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
|
if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
|
return t;
|
return t;
|
|
|
while (!SSA_VAR_P (t)
|
while (!SSA_VAR_P (t)
|
&& (!CONSTANT_CLASS_P (t))
|
&& (!CONSTANT_CLASS_P (t))
|
&& TREE_CODE (t) != LABEL_DECL
|
&& TREE_CODE (t) != LABEL_DECL
|
&& TREE_CODE (t) != FUNCTION_DECL
|
&& TREE_CODE (t) != FUNCTION_DECL
|
&& TREE_CODE (t) != CONST_DECL)
|
&& TREE_CODE (t) != CONST_DECL)
|
{
|
{
|
t = TREE_OPERAND (t, 0);
|
t = TREE_OPERAND (t, 0);
|
}
|
}
|
return t;
|
return t;
|
}
|
}
|
|
|
|
|
