From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- gcc/ipa-utils.c | 229 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 229 insertions(+) create mode 100644 gcc/ipa-utils.c (limited to 'gcc/ipa-utils.c') diff --git a/gcc/ipa-utils.c b/gcc/ipa-utils.c new file mode 100644 index 000000000..4b88f599d --- /dev/null +++ b/gcc/ipa-utils.c @@ -0,0 +1,229 @@ +/* Utilities for ipa analysis. + Copyright (C) 2005, 2007, 2008 Free Software Foundation, Inc. + Contributed by Kenneth Zadeck + +This file is part of GCC. + +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 +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "tree.h" +#include "tree-flow.h" +#include "tree-inline.h" +#include "tree-pass.h" +#include "langhooks.h" +#include "pointer-set.h" +#include "splay-tree.h" +#include "ggc.h" +#include "ipa-utils.h" +#include "ipa-reference.h" +#include "gimple.h" +#include "cgraph.h" +#include "output.h" +#include "flags.h" +#include "timevar.h" +#include "diagnostic.h" +#include "langhooks.h" + +/* Debugging function for postorder and inorder code. NOTE is a string + that is printed before the nodes are printed. ORDER is an array of + 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) +{ + int i; + fprintf (out, "\n\n ordered call graph: %s\n", note); + + for (i = count - 1; i >= 0; i--) + dump_cgraph_node(dump_file, order[i]); + fprintf (out, "\n"); + fflush(out); +} + + +struct searchc_env { + struct cgraph_node **stack; + int stack_size; + struct cgraph_node **result; + int order_pos; + splay_tree nodes_marked_new; + bool reduce; + int count; +}; + +/* This is an implementation of Tarjan's strongly connected region + finder as reprinted in Aho Hopcraft and Ullman's The Design and + Analysis of Computer Programs (1975) pages 192-193. This version + 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 + unnecessary if C had nested functions. V is the node to start + searching from. */ + +static void +searchc (struct searchc_env* env, struct cgraph_node *v, + bool (*ignore_edge) (struct cgraph_edge *)) +{ + struct cgraph_edge *edge; + struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux; + + /* mark node as old */ + v_info->new_node = false; + splay_tree_remove (env->nodes_marked_new, v->uid); + + v_info->dfn_number = env->count; + v_info->low_link = env->count; + env->count++; + env->stack[(env->stack_size)++] = v; + v_info->on_stack = true; + + for (edge = v->callees; edge; edge = edge->next_callee) + { + struct ipa_dfs_info * w_info; + struct cgraph_node *w = edge->callee; + + if (ignore_edge && ignore_edge (edge)) + continue; + + if (w->aux && cgraph_function_body_availability (edge->callee) > AVAIL_OVERWRITABLE) + { + w_info = (struct ipa_dfs_info *) w->aux; + if (w_info->new_node) + { + searchc (env, w, ignore_edge); + v_info->low_link = + (v_info->low_link < w_info->low_link) ? + v_info->low_link : w_info->low_link; + } + else + if ((w_info->dfn_number < v_info->dfn_number) + && (w_info->on_stack)) + 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) + { + struct cgraph_node *last = NULL; + struct cgraph_node *x; + struct ipa_dfs_info *x_info; + do { + x = env->stack[--(env->stack_size)]; + x_info = (struct ipa_dfs_info *) x->aux; + x_info->on_stack = false; + + if (env->reduce) + { + x_info->next_cycle = last; + last = x; + } + else + env->result[env->order_pos++] = x; + } + while (v != x); + if (env->reduce) + env->result[env->order_pos++] = v; + } +} + +/* 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. */ + +int +ipa_utils_reduced_inorder (struct cgraph_node **order, + bool reduce, bool allow_overwritable, + bool (*ignore_edge) (struct cgraph_edge *)) +{ + struct cgraph_node *node; + struct searchc_env env; + splay_tree_node result; + env.stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); + env.stack_size = 0; + env.result = order; + env.order_pos = 0; + env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0); + env.count = 1; + env.reduce = reduce; + + for (node = cgraph_nodes; node; node = node->next) + { + enum availability avail = cgraph_function_body_availability (node); + + if (avail > AVAIL_OVERWRITABLE + || (allow_overwritable + && (avail == AVAIL_OVERWRITABLE))) + { + /* Reuse the info if it is already there. */ + struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->aux; + if (!info) + info = XCNEW (struct ipa_dfs_info); + info->new_node = true; + info->on_stack = false; + info->next_cycle = NULL; + node->aux = info; + + splay_tree_insert (env.nodes_marked_new, + (splay_tree_key)node->uid, + (splay_tree_value)node); + } + else + node->aux = NULL; + } + result = splay_tree_min (env.nodes_marked_new); + while (result) + { + node = (struct cgraph_node *)result->value; + searchc (&env, node, ignore_edge); + result = splay_tree_min (env.nodes_marked_new); + } + splay_tree_delete (env.nodes_marked_new); + free (env.stack); + + return env.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 + INDIRECT_REFS. */ + +tree +get_base_var (tree t) +{ + while (!SSA_VAR_P (t) + && (!CONSTANT_CLASS_P (t)) + && TREE_CODE (t) != LABEL_DECL + && TREE_CODE (t) != FUNCTION_DECL + && TREE_CODE (t) != CONST_DECL + && TREE_CODE (t) != CONSTRUCTOR) + { + t = TREE_OPERAND (t, 0); + } + return t; +} + -- cgit v1.2.3