1169689Skan/* Utilities for ipa analysis. 2169689Skan Copyright (C) 2005 Free Software Foundation, Inc. 3169689Skan Contributed by Kenneth Zadeck <zadeck@naturalbridge.com> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify it under 8169689Skanthe terms of the GNU General Public License as published by the Free 9169689SkanSoftware Foundation; either version 2, or (at your option) any later 10169689Skanversion. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 14169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15169689Skanfor more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. 21169689Skan*/ 22169689Skan 23169689Skan#include "config.h" 24169689Skan#include "system.h" 25169689Skan#include "coretypes.h" 26169689Skan#include "tm.h" 27169689Skan#include "tree.h" 28169689Skan#include "tree-flow.h" 29169689Skan#include "tree-inline.h" 30169689Skan#include "tree-pass.h" 31169689Skan#include "langhooks.h" 32169689Skan#include "pointer-set.h" 33169689Skan#include "ggc.h" 34169689Skan#include "ipa-utils.h" 35169689Skan#include "ipa-reference.h" 36169689Skan#include "c-common.h" 37169689Skan#include "tree-gimple.h" 38169689Skan#include "cgraph.h" 39169689Skan#include "output.h" 40169689Skan#include "flags.h" 41169689Skan#include "timevar.h" 42169689Skan#include "diagnostic.h" 43169689Skan#include "langhooks.h" 44169689Skan 45169689Skan/* Debugging function for postorder and inorder code. NOTE is a string 46169689Skan that is printed before the nodes are printed. ORDER is an array of 47169689Skan cgraph_nodes that has COUNT useful nodes in it. */ 48169689Skan 49169689Skanvoid 50169689Skanipa_utils_print_order (FILE* out, 51169689Skan const char * note, 52169689Skan struct cgraph_node** order, 53169689Skan int count) 54169689Skan{ 55169689Skan int i; 56169689Skan fprintf (out, "\n\n ordered call graph: %s\n", note); 57169689Skan 58169689Skan for (i = count - 1; i >= 0; i--) 59169689Skan dump_cgraph_node(dump_file, order[i]); 60169689Skan fprintf (out, "\n"); 61169689Skan fflush(out); 62169689Skan} 63169689Skan 64169689Skan 65169689Skanstruct searchc_env { 66169689Skan struct cgraph_node **stack; 67169689Skan int stack_size; 68169689Skan struct cgraph_node **result; 69169689Skan int order_pos; 70169689Skan splay_tree nodes_marked_new; 71169689Skan bool reduce; 72169689Skan int count; 73169689Skan}; 74169689Skan 75169689Skan/* This is an implementation of Tarjan's strongly connected region 76169689Skan finder as reprinted in Aho Hopcraft and Ullman's The Design and 77169689Skan Analysis of Computer Programs (1975) pages 192-193. This version 78169689Skan has been customized for cgraph_nodes. The env parameter is because 79169689Skan it is recursive and there are no nested functions here. This 80169689Skan function should only be called from itself or 81235623Spfg ipa_utils_reduced_inorder. ENV is a stack env and would be 82169689Skan unnecessary if C had nested functions. V is the node to start 83169689Skan searching from. */ 84169689Skan 85169689Skanstatic void 86169689Skansearchc (struct searchc_env* env, struct cgraph_node *v) 87169689Skan{ 88169689Skan struct cgraph_edge *edge; 89169689Skan struct ipa_dfs_info *v_info = v->aux; 90169689Skan 91169689Skan /* mark node as old */ 92169689Skan v_info->new = false; 93169689Skan splay_tree_remove (env->nodes_marked_new, v->uid); 94169689Skan 95169689Skan v_info->dfn_number = env->count; 96169689Skan v_info->low_link = env->count; 97169689Skan env->count++; 98169689Skan env->stack[(env->stack_size)++] = v; 99169689Skan v_info->on_stack = true; 100169689Skan 101169689Skan for (edge = v->callees; edge; edge = edge->next_callee) 102169689Skan { 103169689Skan struct ipa_dfs_info * w_info; 104169689Skan struct cgraph_node *w = edge->callee; 105169689Skan /* Bypass the clones and only look at the master node. Skip 106169689Skan external and other bogus nodes. */ 107169689Skan w = cgraph_master_clone (w); 108169689Skan if (w && w->aux) 109169689Skan { 110169689Skan w_info = w->aux; 111169689Skan if (w_info->new) 112169689Skan { 113169689Skan searchc (env, w); 114169689Skan v_info->low_link = 115169689Skan (v_info->low_link < w_info->low_link) ? 116169689Skan v_info->low_link : w_info->low_link; 117169689Skan } 118169689Skan else 119169689Skan if ((w_info->dfn_number < v_info->dfn_number) 120169689Skan && (w_info->on_stack)) 121169689Skan v_info->low_link = 122169689Skan (w_info->dfn_number < v_info->low_link) ? 123169689Skan w_info->dfn_number : v_info->low_link; 124169689Skan } 125169689Skan } 126169689Skan 127169689Skan 128169689Skan if (v_info->low_link == v_info->dfn_number) 129169689Skan { 130169689Skan struct cgraph_node *last = NULL; 131169689Skan struct cgraph_node *x; 132169689Skan struct ipa_dfs_info *x_info; 133169689Skan do { 134169689Skan x = env->stack[--(env->stack_size)]; 135169689Skan x_info = x->aux; 136169689Skan x_info->on_stack = false; 137169689Skan 138169689Skan if (env->reduce) 139169689Skan { 140169689Skan x_info->next_cycle = last; 141169689Skan last = x; 142169689Skan } 143169689Skan else 144169689Skan env->result[env->order_pos++] = x; 145169689Skan } 146169689Skan while (v != x); 147169689Skan if (env->reduce) 148169689Skan env->result[env->order_pos++] = v; 149169689Skan } 150169689Skan} 151169689Skan 152169689Skan/* Topsort the call graph by caller relation. Put the result in ORDER. 153169689Skan 154169689Skan The REDUCE flag is true if you want the cycles reduced to single 155169689Skan nodes. Only consider nodes that have the output bit set. */ 156169689Skan 157169689Skanint 158169689Skanipa_utils_reduced_inorder (struct cgraph_node **order, 159169689Skan bool reduce, bool allow_overwritable) 160169689Skan{ 161169689Skan struct cgraph_node *node; 162169689Skan struct searchc_env env; 163169689Skan splay_tree_node result; 164169689Skan env.stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); 165169689Skan env.stack_size = 0; 166169689Skan env.result = order; 167169689Skan env.order_pos = 0; 168169689Skan env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0); 169169689Skan env.count = 1; 170169689Skan env.reduce = reduce; 171169689Skan 172169689Skan for (node = cgraph_nodes; node; node = node->next) 173169689Skan if ((node->analyzed) 174169689Skan && (cgraph_is_master_clone (node) 175169689Skan || (allow_overwritable 176169689Skan && (cgraph_function_body_availability (node) == 177169689Skan AVAIL_OVERWRITABLE)))) 178169689Skan { 179169689Skan /* Reuse the info if it is already there. */ 180169689Skan struct ipa_dfs_info *info = node->aux; 181169689Skan if (!info) 182169689Skan info = xcalloc (1, sizeof (struct ipa_dfs_info)); 183169689Skan info->new = true; 184169689Skan info->on_stack = false; 185169689Skan info->next_cycle = NULL; 186169689Skan node->aux = info; 187169689Skan 188169689Skan splay_tree_insert (env.nodes_marked_new, 189169689Skan (splay_tree_key)node->uid, 190169689Skan (splay_tree_value)node); 191169689Skan } 192169689Skan else 193169689Skan node->aux = NULL; 194169689Skan result = splay_tree_min (env.nodes_marked_new); 195169689Skan while (result) 196169689Skan { 197169689Skan node = (struct cgraph_node *)result->value; 198169689Skan searchc (&env, node); 199169689Skan result = splay_tree_min (env.nodes_marked_new); 200169689Skan } 201169689Skan splay_tree_delete (env.nodes_marked_new); 202169689Skan free (env.stack); 203169689Skan 204169689Skan return env.order_pos; 205169689Skan} 206169689Skan 207169689Skan 208169689Skan/* Given a memory reference T, will return the variable at the bottom 209169689Skan of the access. Unlike get_base_address, this will recurse thru 210169689Skan INDIRECT_REFS. */ 211169689Skan 212169689Skantree 213169689Skanget_base_var (tree t) 214169689Skan{ 215169689Skan if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)) 216169689Skan return t; 217169689Skan 218169689Skan while (!SSA_VAR_P (t) 219169689Skan && (!CONSTANT_CLASS_P (t)) 220169689Skan && TREE_CODE (t) != LABEL_DECL 221169689Skan && TREE_CODE (t) != FUNCTION_DECL 222169689Skan && TREE_CODE (t) != CONST_DECL) 223169689Skan { 224169689Skan t = TREE_OPERAND (t, 0); 225169689Skan } 226169689Skan return t; 227169689Skan} 228169689Skan 229