Hi,
today while discussing the two functions that we have in gcc to
topologically sort the call graph, Honza asked me to put them both
into the ipa-utils file and rename them.
So this patch moves cgraph_postorder there and renames it to
ipa_reverse_postorder, and similarly, it renames
ipa_utils_reduced_inorder to ipa_reduced_postorder because that is
what it is. The names are perhaps too similar but the number of
parameters required for the latter function should be enough to
distinguish between the two well. The new names should help users to
pick the one that better suits their needs.
The functions are quite similar and in future we might want to merge
them but that was not the goal today. They are also a bit different,
ipa_reverse_postorder works on callers edges rather than on callees,
does not have an option to reduce SCCs or ignore some edges, the
latter is more efficient and automatically ignores edges from
always_inline functions to non-always_inline ones.
Additionally, there are a few cleanups. ipa_utils_print_order also
lost the utils part from its prefix and I have introduced
ipa_free_postorder_info to deallocate the structures
ipa_reduced_postorder allocates and assigns th aux pointers to them.
Finally, propagate() function in ipa-reference.c seemed to make an
extra topological sorting for no good reason so I removed that.
Bootstrapped and tested on x86_64-linux. OK for trunk?
Thanks,
Martin
2011-04-29 Martin Jambor <mjam...@suse.cz>
* cgraph.h (cgraph_postorder): Remove declaration.
* ipa-utils.h (ipa_free_postorder_info): Declare.
(ipa_reverse_postorder): Likewise.
* cgraphunit.c: Include ipa-utils.h.
(cgraph_expand_all_functions): Update call to ipa_reverse_postorder.
* ipa-inline.c: Include ipa-utils.h.
(ipa_inline): Update call to ipa_reverse_postorder.
* ipa-pure-const.c (propagate_pure_const): Update call to
ipa_reduced_postorder and ipa_print_order. Call
ipa_free_postorder_info to clean up.
(propagate_nothrow): Likewise.
* ipa-reference.c (propagate): Removed a useless call to
ipa_utils_reduced_inorder, updated a call to ipa_reduced_postorder
and ipa_print_order. Call ipa_free_postorder_info to clean up.
* ipa.c: Include ipa-utils.h.
(ipa_profile): Update call to ipa_reverse_postorder.
(cgraph_postorder): Moved to...
* ipa-utils.c (ipa_reverse_postorder): ...here and renamed.
(ipa_utils_print_order): Renamed to ipa_print_order.
(ipa_utils_reduced_inorder): Renamed to ipa_reduced_postorder. Updated
comments.
(ipa_free_postorder_info): New function.
* passes.c: Include ipa-utils.h.
(do_per_function_toporder): Update call to ipa_reverse_postorder.
(ipa_write_summaries): Likewise.
* Makefile.in (passes.o): Add IPA_UTILS_H to dependencies.
(cgraphunit.o): Likewise.
(ipa.o): Likewise.
(ipa-inline.o): Likewise.
lto/
* lto.c: Include ipa-utils.h.
(lto_balanced_map): Update call to ipa_reverse_postorder.
* Make-lang.in (lto/lto.o): Add IPA_UTILS_H to dependencies.
Index: src/gcc/Makefile.in
===================================================================
--- src.orig/gcc/Makefile.in
+++ src/gcc/Makefile.in
@@ -2847,7 +2847,7 @@ passes.o : passes.c $(CONFIG_H) $(SYSTEM
hosthooks.h $(CGRAPH_H) $(COVERAGE_H) $(TREE_PASS_H) $(TREE_DUMP_H) \
$(GGC_H) $(INTEGRATE_H) $(CPPLIB_H) $(OPTS_H) $(TREE_FLOW_H)
$(TREE_INLINE_H) \
gt-passes.h $(DF_H) $(PREDICT_H) $(LTO_HEADER_H) $(LTO_SECTION_OUT_H) \
- $(PLUGIN_H)
+ $(PLUGIN_H) $(IPA_UTILS_H)
plugin.o : plugin.c $(PLUGIN_H) $(CONFIG_H) $(SYSTEM_H) coretypes.h \
$(DIAGNOSTIC_CORE_H) $(TREE_H) $(TREE_PASS_H) intl.h $(PLUGIN_VERSION_H)
$(GGC_H)
@@ -2997,7 +2997,7 @@ cgraphunit.o : cgraphunit.c $(CONFIG_H)
$(TREE_FLOW_H) $(TREE_PASS_H) debug.h $(DIAGNOSTIC_H) \
$(FIBHEAP_H) output.h $(PARAMS_H) $(RTL_H) $(TIMEVAR_H) $(IPA_PROP_H) \
gt-cgraphunit.h tree-iterator.h $(COVERAGE_H) $(TREE_DUMP_H) \
- tree-pretty-print.h gimple-pretty-print.h ipa-inline.h
+ tree-pretty-print.h gimple-pretty-print.h ipa-inline.h $(IPA_UTILS_H)
cgraphbuild.o : cgraphbuild.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(TREE_H) langhooks.h $(CGRAPH_H) intl.h pointer-set.h $(GIMPLE_H) \
$(TREE_FLOW_H) $(TREE_PASS_H) $(IPA_UTILS_H) $(EXCEPT_H) \
@@ -3007,7 +3007,8 @@ varpool.o : varpool.c $(CONFIG_H) $(SYST
$(GGC_H) $(TIMEVAR_H) debug.h $(TARGET_H) output.h $(GIMPLE_H) \
$(TREE_FLOW_H) gt-varpool.h
ipa.o : ipa.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(CGRAPH_H) \
- $(TREE_PASS_H) $(TIMEVAR_H) $(GIMPLE_H) $(GGC_H) pointer-set.h
+ $(TREE_PASS_H) $(TIMEVAR_H) $(GIMPLE_H) $(GGC_H) pointer-set.h \
+ $(IPA_UTILS_H)
ipa-prop.o : ipa-prop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
langhooks.h $(GGC_H) $(TARGET_H) $(CGRAPH_H) $(IPA_PROP_H) $(DIAGNOSTIC_H) \
$(TREE_FLOW_H) $(TM_H) $(TREE_PASS_H) $(FLAGS_H) $(TREE_H) \
@@ -3035,7 +3036,7 @@ ipa-inline.o : ipa-inline.c $(CONFIG_H)
$(TREE_H) langhooks.h $(TREE_INLINE_H) $(FLAGS_H) $(CGRAPH_H) intl.h \
$(DIAGNOSTIC_H) $(FIBHEAP_H) $(PARAMS_H) $(TIMEVAR_H) $(TREE_PASS_H) \
$(COVERAGE_H) $(GGC_H) $(TREE_FLOW_H) $(RTL_H) $(IPA_PROP_H) \
- $(EXCEPT_H) gimple-pretty-print.h ipa-inline.h $(TARGET_H)
+ $(EXCEPT_H) gimple-pretty-print.h ipa-inline.h $(TARGET_H) $(IPA_UTILS_H)
ipa-inline-analysis.o : ipa-inline-analysis.c $(CONFIG_H) $(SYSTEM_H)
coretypes.h $(TM_H) \
$(TREE_H) langhooks.h $(TREE_INLINE_H) $(FLAGS_H) $(CGRAPH_H) intl.h \
$(DIAGNOSTIC_H) $(PARAMS_H) $(TIMEVAR_H) $(TREE_PASS_H) \
Index: src/gcc/cgraph.h
===================================================================
--- src.orig/gcc/cgraph.h
+++ src/gcc/cgraph.h
@@ -625,7 +625,6 @@ int compute_call_stmt_bb_frequency (tree
/* In ipa.c */
bool cgraph_remove_unreachable_nodes (bool, FILE *);
-int cgraph_postorder (struct cgraph_node **);
cgraph_node_set cgraph_node_set_new (void);
cgraph_node_set_iterator cgraph_node_set_find (cgraph_node_set,
struct cgraph_node *);
Index: src/gcc/cgraphunit.c
===================================================================
--- src.orig/gcc/cgraphunit.c
+++ src/gcc/cgraphunit.c
@@ -139,6 +139,7 @@ along with GCC; see the file COPYING3.
#include "coverage.h"
#include "plugin.h"
#include "ipa-inline.h"
+#include "ipa-utils.h"
static void cgraph_expand_all_functions (void);
static void cgraph_mark_functions_to_output (void);
@@ -1618,7 +1619,7 @@ cgraph_expand_all_functions (void)
int order_pos, new_order_pos = 0;
int i;
- order_pos = cgraph_postorder (order);
+ order_pos = ipa_reverse_postorder (order);
gcc_assert (order_pos == cgraph_n_nodes);
/* Garbage collector may remove inline clones we eliminate during
Index: src/gcc/ipa-inline.c
===================================================================
--- src.orig/gcc/ipa-inline.c
+++ src/gcc/ipa-inline.c
@@ -114,6 +114,7 @@ along with GCC; see the file COPYING3.
#include "except.h"
#include "target.h"
#include "ipa-inline.h"
+#include "ipa-utils.h"
/* Statistics we collect about inlining algorithm. */
static int overall_size;
@@ -1457,7 +1458,7 @@ ipa_inline (void)
if (dump_file)
dump_inline_summaries (dump_file);
- nnodes = cgraph_postorder (order);
+ nnodes = ipa_reverse_postorder (order);
for (node = cgraph_nodes; node; node = node->next)
node->aux = 0;
Index: src/gcc/ipa-pure-const.c
===================================================================
--- src.orig/gcc/ipa-pure-const.c
+++ src/gcc/ipa-pure-const.c
@@ -1089,11 +1089,11 @@ propagate_pure_const (void)
int i;
struct ipa_dfs_info * w_info;
- order_pos = ipa_utils_reduced_inorder (order, true, false, NULL);
+ order_pos = ipa_reduced_postorder (order, true, false, NULL);
if (dump_file)
{
dump_cgraph (dump_file);
- ipa_utils_print_order(dump_file, "reduced", order, order_pos);
+ ipa_print_order(dump_file, "reduced", order, order_pos);
}
/* Propagate the local information thru the call graph to produce
@@ -1339,18 +1339,7 @@ propagate_pure_const (void)
}
}
- /* Cleanup. */
- for (node = cgraph_nodes; node; node = node->next)
- {
- /* Get rid of the aux information. */
- if (node->aux)
- {
- w_info = (struct ipa_dfs_info *) node->aux;
- free (node->aux);
- node->aux = NULL;
- }
- }
-
+ ipa_free_postorder_info ();
free (order);
}
@@ -1368,11 +1357,11 @@ propagate_nothrow (void)
int i;
struct ipa_dfs_info * w_info;
- order_pos = ipa_utils_reduced_inorder (order, true, false, ignore_edge);
+ order_pos = ipa_reduced_postorder (order, true, false, ignore_edge);
if (dump_file)
{
dump_cgraph (dump_file);
- ipa_utils_print_order(dump_file, "reduced for nothrow", order,
order_pos);
+ ipa_print_order (dump_file, "reduced for nothrow", order, order_pos);
}
/* Propagate the local information thru the call graph to produce
@@ -1445,18 +1434,7 @@ propagate_nothrow (void)
}
}
- /* Cleanup. */
- for (node = cgraph_nodes; node; node = node->next)
- {
- /* Get rid of the aux information. */
- if (node->aux)
- {
- w_info = (struct ipa_dfs_info *) node->aux;
- free (node->aux);
- node->aux = NULL;
- }
- }
-
+ ipa_free_postorder_info ();
free (order);
}
Index: src/gcc/ipa-reference.c
===================================================================
--- src.orig/gcc/ipa-reference.c
+++ src/gcc/ipa-reference.c
@@ -615,7 +615,7 @@ propagate (void)
struct cgraph_node *w;
struct cgraph_node **order =
XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
- int order_pos = ipa_utils_reduced_inorder (order, false, true, NULL);
+ int order_pos;
int i;
if (dump_file)
@@ -628,9 +628,9 @@ propagate (void)
the global information. All the nodes within a cycle will have
the same info so we collapse cycles first. Then we can do the
propagation in one pass from the leaves to the roots. */
- order_pos = ipa_utils_reduced_inorder (order, true, true, NULL);
+ order_pos = ipa_reduced_postorder (order, true, true, NULL);
if (dump_file)
- ipa_utils_print_order(dump_file, "reduced", order, order_pos);
+ ipa_print_order (dump_file, "reduced", order, order_pos);
for (i = 0; i < order_pos; i++ )
{
@@ -914,13 +914,9 @@ propagate (void)
}
}
free (node_info);
- if (node->aux)
- {
- free (node->aux);
- node->aux = NULL;
- }
}
+ ipa_free_postorder_info ();
free (order);
bitmap_obstack_release (&local_info_obstack);
Index: src/gcc/ipa-utils.c
===================================================================
--- src.orig/gcc/ipa-utils.c
+++ src/gcc/ipa-utils.c
@@ -45,10 +45,10 @@ along with GCC; see the file COPYING3.
cgraph_nodes that has COUNT useful nodes in it. */
void
-ipa_utils_print_order (FILE* out,
- const char * note,
- struct cgraph_node** order,
- int count)
+ipa_print_order (FILE* out,
+ const char * note,
+ struct cgraph_node** order,
+ int count)
{
int i;
fprintf (out, "\n\n ordered call graph: %s\n", note);
@@ -76,7 +76,7 @@ struct searchc_env {
has been customized for cgraph_nodes. The env parameter is because
it is recursive and there are no nested functions here. This
function should only be called from itself or
- ipa_utils_reduced_inorder. ENV is a stack env and would be
+ ipa_reduced_postorder. ENV is a stack env and would be
unnecessary if C had nested functions. V is the node to start
searching from. */
@@ -151,13 +151,15 @@ searchc (struct searchc_env* env, struct
/* 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
- nodes. Only consider nodes that have the output bit set. */
+ The REDUCE flag is true if you want the cycles reduced to single nodes. Set
+ ALLOW_OVERWRITABLE if nodes with such availability should be included.
+ IGNORE_EDGE, if non-NULL is a hook that may make some edges insignificant
+ for the topological sort. */
int
-ipa_utils_reduced_inorder (struct cgraph_node **order,
- bool reduce, bool allow_overwritable,
- bool (*ignore_edge) (struct cgraph_edge *))
+ipa_reduced_postorder (struct cgraph_node **order,
+ bool reduce, bool allow_overwritable,
+ bool (*ignore_edge) (struct cgraph_edge *))
{
struct cgraph_node *node;
struct searchc_env env;
@@ -207,6 +209,101 @@ ipa_utils_reduced_inorder (struct cgraph
return env.order_pos;
}
+/* Deallocate all ipa_dfs_info structures pointed to by the aux pointer of call
+ graph nodes. */
+
+void
+ipa_free_postorder_info (void)
+{
+ struct cgraph_node *node;
+ for (node = cgraph_nodes; node; node = node->next)
+ {
+ /* Get rid of the aux information. */
+ if (node->aux)
+ {
+ free (node->aux);
+ node->aux = NULL;
+ }
+ }
+}
+
+/* Fill array order with all nodes with output flag set in the reverse
+ topological order. Return the number of elements in the array. */
+
+int
+ipa_reverse_postorder (struct cgraph_node **order)
+{
+ struct cgraph_node *node, *node2;
+ int stack_size = 0;
+ int order_pos = 0;
+ struct cgraph_edge *edge, last;
+ int pass;
+
+ struct cgraph_node **stack =
+ XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
+
+ /* We have to deal with cycles nicely, so use a depth first traversal
+ 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
+ right through inline functions. */
+ for (node = cgraph_nodes; node; node = node->next)
+ node->aux = NULL;
+ for (pass = 0; pass < 2; pass++)
+ for (node = cgraph_nodes; node; node = node->next)
+ if (!node->aux
+ && (pass
+ || (!node->address_taken
+ && !node->global.inlined_to
+ && !cgraph_only_called_directly_p (node))))
+ {
+ node2 = node;
+ if (!node->callers)
+ node->aux = &last;
+ else
+ node->aux = node->callers;
+ while (node2)
+ {
+ while (node2->aux != &last)
+ {
+ edge = (struct cgraph_edge *) node2->aux;
+ if (edge->next_caller)
+ node2->aux = edge->next_caller;
+ else
+ node2->aux = &last;
+ /* Break possible cycles involving always-inline
+ functions by ignoring edges from always-inline
+ functions to non-always-inline functions. */
+ if (DECL_DISREGARD_INLINE_LIMITS (edge->caller->decl)
+ && !DECL_DISREGARD_INLINE_LIMITS (edge->callee->decl))
+ continue;
+ 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;
+ }
+ }
+ }
+ free (stack);
+ for (node = cgraph_nodes; node; node = node->next)
+ node->aux = NULL;
+ return order_pos;
+}
+
+
/* Given a memory reference T, will return the variable at the bottom
of the access. Unlike get_base_address, this will recurse thru
Index: src/gcc/ipa-utils.h
===================================================================
--- src.orig/gcc/ipa-utils.h
+++ src/gcc/ipa-utils.h
@@ -35,9 +35,11 @@ struct ipa_dfs_info {
/* In ipa-utils.c */
-void ipa_utils_print_order (FILE*, const char *, struct cgraph_node**, int);
-int ipa_utils_reduced_inorder (struct cgraph_node **, bool, bool,
- bool (*ignore_edge) (struct cgraph_edge *));
+void ipa_print_order (FILE*, const char *, struct cgraph_node**, int);
+int ipa_reduced_postorder (struct cgraph_node **, bool, bool,
+ bool (*ignore_edge) (struct cgraph_edge *));
+void ipa_free_postorder_info (void);
+int ipa_reverse_postorder (struct cgraph_node **);
tree get_base_var (tree);
Index: src/gcc/ipa.c
===================================================================
--- src.orig/gcc/ipa.c
+++ src/gcc/ipa.c
@@ -31,82 +31,7 @@ along with GCC; see the file COPYING3.
#include "pointer-set.h"
#include "target.h"
#include "tree-iterator.h"
-
-/* Fill array order with all nodes with output flag set in the reverse
- topological order. */
-
-int
-cgraph_postorder (struct cgraph_node **order)
-{
- struct cgraph_node *node, *node2;
- int stack_size = 0;
- int order_pos = 0;
- struct cgraph_edge *edge, last;
- int pass;
-
- struct cgraph_node **stack =
- XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
-
- /* We have to deal with cycles nicely, so use a depth first traversal
- 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
- right through inline functions. */
- for (node = cgraph_nodes; node; node = node->next)
- node->aux = NULL;
- for (pass = 0; pass < 2; pass++)
- for (node = cgraph_nodes; node; node = node->next)
- if (!node->aux
- && (pass
- || (!node->address_taken
- && !node->global.inlined_to
- && !cgraph_only_called_directly_p (node))))
- {
- node2 = node;
- if (!node->callers)
- node->aux = &last;
- else
- node->aux = node->callers;
- while (node2)
- {
- while (node2->aux != &last)
- {
- edge = (struct cgraph_edge *) node2->aux;
- if (edge->next_caller)
- node2->aux = edge->next_caller;
- else
- node2->aux = &last;
- /* Break possible cycles involving always-inline
- functions by ignoring edges from always-inline
- functions to non-always-inline functions. */
- if (DECL_DISREGARD_INLINE_LIMITS (edge->caller->decl)
- && !DECL_DISREGARD_INLINE_LIMITS (edge->callee->decl))
- continue;
- 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;
- }
- }
- }
- free (stack);
- for (node = cgraph_nodes; node; node = node->next)
- node->aux = NULL;
- return order_pos;
-}
+#include "ipa-utils.h"
/* Look for all functions inlined to NODE and update their inlined_to pointers
to INLINED_TO. */
@@ -1448,7 +1373,7 @@ ipa_profile (void)
bool something_changed = false;
int i;
- order_pos = cgraph_postorder (order);
+ order_pos = ipa_reverse_postorder (order);
for (i = order_pos - 1; i >= 0; i--)
{
if (order[i]->local.local && cgraph_propagate_frequency (order[i]))
Index: src/gcc/lto/Make-lang.in
===================================================================
--- src.orig/gcc/lto/Make-lang.in
+++ src/gcc/lto/Make-lang.in
@@ -86,7 +86,7 @@ lto/lto.o: lto/lto.c $(CONFIG_H) $(SYSTE
langhooks.h $(VEC_H) $(BITMAP_H) pointer-set.h $(IPA_PROP_H) \
$(COMMON_H) debug.h $(TIMEVAR_H) $(GIMPLE_H) $(LTO_H) $(LTO_TREE_H) \
$(LTO_TAGS_H) $(LTO_STREAMER_H) $(SPLAY_TREE_H) gt-lto-lto.h
$(PARAMS_H) \
- ipa-inline.h
+ ipa-inline.h $(IPA_UTILS_H)
lto/lto-object.o: lto/lto-object.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
$(DIAGNOSTIC_CORE_H) $(LTO_H) $(TM_H) $(LTO_STREAMER_H) \
../include/simple-object.h
Index: src/gcc/lto/lto.c
===================================================================
--- src.orig/gcc/lto/lto.c
+++ src/gcc/lto/lto.c
@@ -45,6 +45,7 @@ along with GCC; see the file COPYING3.
#include "splay-tree.h"
#include "params.h"
#include "ipa-inline.h"
+#include "ipa-utils.h"
static GTY(()) tree first_personality_decl;
@@ -1026,7 +1027,7 @@ lto_balanced_map (void)
size. Note that since nodes that are not partitioned might be put into
multiple partitions, this is just an estimate of real size. This is why
we keep partition_size updated after every partition is finalized. */
- postorder_len = cgraph_postorder (postorder);
+ postorder_len = ipa_reverse_postorder (postorder);
for (i = 0; i < postorder_len; i++)
{
node = postorder[i];
Index: src/gcc/passes.c
===================================================================
--- src.orig/gcc/passes.c
+++ src/gcc/passes.c
@@ -73,6 +73,7 @@ along with GCC; see the file COPYING3.
#include "predict.h"
#include "lto-streamer.h"
#include "plugin.h"
+#include "ipa-utils.h"
#if defined (DWARF2_UNWIND_INFO) || defined (DWARF2_DEBUGGING_INFO)
#include "dwarf2out.h"
@@ -1124,7 +1125,7 @@ do_per_function_toporder (void (*callbac
{
gcc_assert (!order);
order = ggc_alloc_vec_cgraph_node_ptr (cgraph_n_nodes);
- nnodes = cgraph_postorder (order);
+ nnodes = ipa_reverse_postorder (order);
for (i = nnodes - 1; i >= 0; i--)
order[i]->process = 1;
for (i = nnodes - 1; i >= 0; i--)
@@ -1697,7 +1698,7 @@ ipa_write_summaries (void)
since it causes the gimple file to be processed in the same order
as the source code. */
order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
- order_pos = cgraph_postorder (order);
+ order_pos = ipa_reverse_postorder (order);
gcc_assert (order_pos == cgraph_n_nodes);
for (i = order_pos - 1; i >= 0; i--)
