/* Basic IPA optimizations and utilities.
|
/* Basic IPA optimizations and utilities.
|
Copyright (C) 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
|
Copyright (C) 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
|
|
|
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 "cgraph.h"
|
#include "cgraph.h"
|
|
|
/* Fill array order with all nodes with output flag set in the reverse
|
/* Fill array order with all nodes with output flag set in the reverse
|
topological order. */
|
topological order. */
|
|
|
int
|
int
|
cgraph_postorder (struct cgraph_node **order)
|
cgraph_postorder (struct cgraph_node **order)
|
{
|
{
|
struct cgraph_node *node, *node2;
|
struct cgraph_node *node, *node2;
|
int stack_size = 0;
|
int stack_size = 0;
|
int order_pos = 0;
|
int order_pos = 0;
|
struct cgraph_edge *edge, last;
|
struct cgraph_edge *edge, last;
|
|
|
struct cgraph_node **stack =
|
struct cgraph_node **stack =
|
XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
|
XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
|
|
|
/* We have to deal with cycles nicely, so use a depth first traversal
|
/* We have to deal with cycles nicely, so use a depth first traversal
|
output algorithm. Ignore the fact that some functions won't need
|
output algorithm. Ignore the fact that some functions won't need
|
to be output and put them into order as well, so we get dependencies
|
to be output and put them into order as well, so we get dependencies
|
right through intline functions. */
|
right through intline functions. */
|
for (node = cgraph_nodes; node; node = node->next)
|
for (node = cgraph_nodes; node; node = node->next)
|
node->aux = NULL;
|
node->aux = NULL;
|
for (node = cgraph_nodes; node; node = node->next)
|
for (node = cgraph_nodes; node; node = node->next)
|
if (!node->aux)
|
if (!node->aux)
|
{
|
{
|
node2 = node;
|
node2 = node;
|
if (!node->callers)
|
if (!node->callers)
|
node->aux = &last;
|
node->aux = &last;
|
else
|
else
|
node->aux = node->callers;
|
node->aux = node->callers;
|
while (node2)
|
while (node2)
|
{
|
{
|
while (node2->aux != &last)
|
while (node2->aux != &last)
|
{
|
{
|
edge = node2->aux;
|
edge = node2->aux;
|
if (edge->next_caller)
|
if (edge->next_caller)
|
node2->aux = edge->next_caller;
|
node2->aux = edge->next_caller;
|
else
|
else
|
node2->aux = &last;
|
node2->aux = &last;
|
if (!edge->caller->aux)
|
if (!edge->caller->aux)
|
{
|
{
|
if (!edge->caller->callers)
|
if (!edge->caller->callers)
|
edge->caller->aux = &last;
|
edge->caller->aux = &last;
|
else
|
else
|
edge->caller->aux = edge->caller->callers;
|
edge->caller->aux = edge->caller->callers;
|
stack[stack_size++] = node2;
|
stack[stack_size++] = node2;
|
node2 = edge->caller;
|
node2 = edge->caller;
|
break;
|
break;
|
}
|
}
|
}
|
}
|
if (node2->aux == &last)
|
if (node2->aux == &last)
|
{
|
{
|
order[order_pos++] = node2;
|
order[order_pos++] = node2;
|
if (stack_size)
|
if (stack_size)
|
node2 = stack[--stack_size];
|
node2 = stack[--stack_size];
|
else
|
else
|
node2 = NULL;
|
node2 = NULL;
|
}
|
}
|
}
|
}
|
}
|
}
|
free (stack);
|
free (stack);
|
for (node = cgraph_nodes; node; node = node->next)
|
for (node = cgraph_nodes; node; node = node->next)
|
node->aux = NULL;
|
node->aux = NULL;
|
return order_pos;
|
return order_pos;
|
}
|
}
|
|
|
/* Perform reachability analysis and reclaim all unreachable nodes.
|
/* Perform reachability analysis and reclaim all unreachable nodes.
|
If BEFORE_INLINING_P is true this function is called before inlining
|
If BEFORE_INLINING_P is true this function is called before inlining
|
decisions has been made. If BEFORE_INLINING_P is false this function also
|
decisions has been made. If BEFORE_INLINING_P is false this function also
|
removes unneeded bodies of extern inline functions. */
|
removes unneeded bodies of extern inline functions. */
|
|
|
bool
|
bool
|
cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
|
cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
|
{
|
{
|
struct cgraph_node *first = (void *) 1;
|
struct cgraph_node *first = (void *) 1;
|
struct cgraph_node *node, *next;
|
struct cgraph_node *node, *next;
|
bool changed = false;
|
bool changed = false;
|
int insns = 0;
|
int insns = 0;
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
verify_cgraph ();
|
verify_cgraph ();
|
#endif
|
#endif
|
if (file)
|
if (file)
|
fprintf (file, "\nReclaiming functions:");
|
fprintf (file, "\nReclaiming functions:");
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
for (node = cgraph_nodes; node; node = node->next)
|
for (node = cgraph_nodes; node; node = node->next)
|
gcc_assert (!node->aux);
|
gcc_assert (!node->aux);
|
#endif
|
#endif
|
for (node = cgraph_nodes; node; node = node->next)
|
for (node = cgraph_nodes; node; node = node->next)
|
if (node->needed && !node->global.inlined_to
|
if (node->needed && !node->global.inlined_to
|
&& ((!DECL_EXTERNAL (node->decl))
|
&& ((!DECL_EXTERNAL (node->decl))
|
|| !node->analyzed
|
|| !node->analyzed
|
|| before_inlining_p))
|
|| before_inlining_p))
|
{
|
{
|
node->aux = first;
|
node->aux = first;
|
first = node;
|
first = node;
|
}
|
}
|
else
|
else
|
gcc_assert (!node->aux);
|
gcc_assert (!node->aux);
|
|
|
/* Perform reachability analysis. As a special case do not consider
|
/* Perform reachability analysis. As a special case do not consider
|
extern inline functions not inlined as live because we won't output
|
extern inline functions not inlined as live because we won't output
|
them at all. */
|
them at all. */
|
while (first != (void *) 1)
|
while (first != (void *) 1)
|
{
|
{
|
struct cgraph_edge *e;
|
struct cgraph_edge *e;
|
node = first;
|
node = first;
|
first = first->aux;
|
first = first->aux;
|
|
|
for (e = node->callees; e; e = e->next_callee)
|
for (e = node->callees; e; e = e->next_callee)
|
if (!e->callee->aux
|
if (!e->callee->aux
|
&& node->analyzed
|
&& node->analyzed
|
&& (!e->inline_failed || !e->callee->analyzed
|
&& (!e->inline_failed || !e->callee->analyzed
|
|| (!DECL_EXTERNAL (e->callee->decl))
|
|| (!DECL_EXTERNAL (e->callee->decl))
|
|| before_inlining_p))
|
|| before_inlining_p))
|
{
|
{
|
e->callee->aux = first;
|
e->callee->aux = first;
|
first = e->callee;
|
first = e->callee;
|
}
|
}
|
}
|
}
|
|
|
/* Remove unreachable nodes. Extern inline functions need special care;
|
/* Remove unreachable nodes. Extern inline functions need special care;
|
Unreachable extern inline functions shall be removed.
|
Unreachable extern inline functions shall be removed.
|
Reachable extern inline functions we never inlined shall get their bodies
|
Reachable extern inline functions we never inlined shall get their bodies
|
eliminated.
|
eliminated.
|
Reachable extern inline functions we sometimes inlined will be turned into
|
Reachable extern inline functions we sometimes inlined will be turned into
|
unanalyzed nodes so they look like for true extern functions to the rest
|
unanalyzed nodes so they look like for true extern functions to the rest
|
of code. Body of such functions is released via remove_node once the
|
of code. Body of such functions is released via remove_node once the
|
inline clones are eliminated. */
|
inline clones are eliminated. */
|
for (node = cgraph_nodes; node; node = next)
|
for (node = cgraph_nodes; node; node = next)
|
{
|
{
|
next = node->next;
|
next = node->next;
|
if (!node->aux)
|
if (!node->aux)
|
{
|
{
|
int local_insns;
|
int local_insns;
|
tree decl = node->decl;
|
tree decl = node->decl;
|
|
|
node->global.inlined_to = NULL;
|
node->global.inlined_to = NULL;
|
if (DECL_STRUCT_FUNCTION (decl))
|
if (DECL_STRUCT_FUNCTION (decl))
|
local_insns = node->local.self_insns;
|
local_insns = node->local.self_insns;
|
else
|
else
|
local_insns = 0;
|
local_insns = 0;
|
if (file)
|
if (file)
|
fprintf (file, " %s", cgraph_node_name (node));
|
fprintf (file, " %s", cgraph_node_name (node));
|
if (!node->analyzed || !DECL_EXTERNAL (node->decl)
|
if (!node->analyzed || !DECL_EXTERNAL (node->decl)
|
|| before_inlining_p)
|
|| before_inlining_p)
|
cgraph_remove_node (node);
|
cgraph_remove_node (node);
|
else
|
else
|
{
|
{
|
struct cgraph_edge *e;
|
struct cgraph_edge *e;
|
|
|
for (e = node->callers; e; e = e->next_caller)
|
for (e = node->callers; e; e = e->next_caller)
|
if (e->caller->aux)
|
if (e->caller->aux)
|
break;
|
break;
|
if (e || node->needed)
|
if (e || node->needed)
|
{
|
{
|
struct cgraph_node *clone;
|
struct cgraph_node *clone;
|
|
|
for (clone = node->next_clone; clone;
|
for (clone = node->next_clone; clone;
|
clone = clone->next_clone)
|
clone = clone->next_clone)
|
if (clone->aux)
|
if (clone->aux)
|
break;
|
break;
|
if (!clone)
|
if (!clone)
|
{
|
{
|
DECL_SAVED_TREE (node->decl) = NULL;
|
DECL_SAVED_TREE (node->decl) = NULL;
|
DECL_STRUCT_FUNCTION (node->decl) = NULL;
|
DECL_STRUCT_FUNCTION (node->decl) = NULL;
|
DECL_INITIAL (node->decl) = error_mark_node;
|
DECL_INITIAL (node->decl) = error_mark_node;
|
node->analyzed = false;
|
node->analyzed = false;
|
}
|
}
|
cgraph_node_remove_callees (node);
|
cgraph_node_remove_callees (node);
|
node->analyzed = false;
|
node->analyzed = false;
|
}
|
}
|
else
|
else
|
cgraph_remove_node (node);
|
cgraph_remove_node (node);
|
}
|
}
|
if (!DECL_SAVED_TREE (decl))
|
if (!DECL_SAVED_TREE (decl))
|
insns += local_insns;
|
insns += local_insns;
|
changed = true;
|
changed = true;
|
}
|
}
|
}
|
}
|
for (node = cgraph_nodes; node; node = node->next)
|
for (node = cgraph_nodes; node; node = node->next)
|
node->aux = NULL;
|
node->aux = NULL;
|
if (file)
|
if (file)
|
fprintf (file, "\nReclaimed %i insns", insns);
|
fprintf (file, "\nReclaimed %i insns", insns);
|
return changed;
|
return changed;
|
}
|
}
|
|
|
