1169689Skan/* Basic IPA optimizations and utilities. 2169689Skan Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3169689Skan 4169689SkanThis file is part of GCC. 5169689Skan 6169689SkanGCC is free software; you can redistribute it and/or modify it under 7169689Skanthe terms of the GNU General Public License as published by the Free 8169689SkanSoftware Foundation; either version 2, or (at your option) any later 9169689Skanversion. 10169689Skan 11169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 12169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 13169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14169689Skanfor more details. 15169689Skan 16169689SkanYou should have received a copy of the GNU General Public License 17169689Skanalong with GCC; see the file COPYING. If not, write to the Free 18169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19169689Skan02110-1301, USA. */ 20169689Skan 21169689Skan#include "config.h" 22169689Skan#include "system.h" 23169689Skan#include "coretypes.h" 24169689Skan#include "tm.h" 25169689Skan#include "cgraph.h" 26169689Skan 27169689Skan/* Fill array order with all nodes with output flag set in the reverse 28169689Skan topological order. */ 29169689Skan 30169689Skanint 31169689Skancgraph_postorder (struct cgraph_node **order) 32169689Skan{ 33169689Skan struct cgraph_node *node, *node2; 34169689Skan int stack_size = 0; 35169689Skan int order_pos = 0; 36169689Skan struct cgraph_edge *edge, last; 37169689Skan 38169689Skan struct cgraph_node **stack = 39169689Skan XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); 40169689Skan 41169689Skan /* We have to deal with cycles nicely, so use a depth first traversal 42169689Skan output algorithm. Ignore the fact that some functions won't need 43169689Skan to be output and put them into order as well, so we get dependencies 44169689Skan right through intline functions. */ 45169689Skan for (node = cgraph_nodes; node; node = node->next) 46169689Skan node->aux = NULL; 47169689Skan for (node = cgraph_nodes; node; node = node->next) 48169689Skan if (!node->aux) 49169689Skan { 50169689Skan node2 = node; 51169689Skan if (!node->callers) 52169689Skan node->aux = &last; 53169689Skan else 54169689Skan node->aux = node->callers; 55169689Skan while (node2) 56169689Skan { 57169689Skan while (node2->aux != &last) 58169689Skan { 59169689Skan edge = node2->aux; 60169689Skan if (edge->next_caller) 61169689Skan node2->aux = edge->next_caller; 62169689Skan else 63169689Skan node2->aux = &last; 64169689Skan if (!edge->caller->aux) 65169689Skan { 66169689Skan if (!edge->caller->callers) 67169689Skan edge->caller->aux = &last; 68169689Skan else 69169689Skan edge->caller->aux = edge->caller->callers; 70169689Skan stack[stack_size++] = node2; 71169689Skan node2 = edge->caller; 72169689Skan break; 73169689Skan } 74169689Skan } 75169689Skan if (node2->aux == &last) 76169689Skan { 77169689Skan order[order_pos++] = node2; 78169689Skan if (stack_size) 79169689Skan node2 = stack[--stack_size]; 80169689Skan else 81169689Skan node2 = NULL; 82169689Skan } 83169689Skan } 84169689Skan } 85169689Skan free (stack); 86169689Skan for (node = cgraph_nodes; node; node = node->next) 87169689Skan node->aux = NULL; 88169689Skan return order_pos; 89169689Skan} 90169689Skan 91169689Skan/* Perform reachability analysis and reclaim all unreachable nodes. 92169689Skan If BEFORE_INLINING_P is true this function is called before inlining 93169689Skan decisions has been made. If BEFORE_INLINING_P is false this function also 94169689Skan removes unneeded bodies of extern inline functions. */ 95169689Skan 96169689Skanbool 97169689Skancgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file) 98169689Skan{ 99169689Skan struct cgraph_node *first = (void *) 1; 100169689Skan struct cgraph_node *node, *next; 101169689Skan bool changed = false; 102169689Skan int insns = 0; 103169689Skan 104169689Skan#ifdef ENABLE_CHECKING 105169689Skan verify_cgraph (); 106169689Skan#endif 107169689Skan if (file) 108169689Skan fprintf (file, "\nReclaiming functions:"); 109169689Skan#ifdef ENABLE_CHECKING 110169689Skan for (node = cgraph_nodes; node; node = node->next) 111169689Skan gcc_assert (!node->aux); 112169689Skan#endif 113169689Skan for (node = cgraph_nodes; node; node = node->next) 114169689Skan if (node->needed && !node->global.inlined_to 115169689Skan && ((!DECL_EXTERNAL (node->decl)) 116169689Skan || !node->analyzed 117169689Skan || before_inlining_p)) 118169689Skan { 119169689Skan node->aux = first; 120169689Skan first = node; 121169689Skan } 122169689Skan else 123169689Skan gcc_assert (!node->aux); 124169689Skan 125169689Skan /* Perform reachability analysis. As a special case do not consider 126169689Skan extern inline functions not inlined as live because we won't output 127169689Skan them at all. */ 128169689Skan while (first != (void *) 1) 129169689Skan { 130169689Skan struct cgraph_edge *e; 131169689Skan node = first; 132169689Skan first = first->aux; 133169689Skan 134169689Skan for (e = node->callees; e; e = e->next_callee) 135169689Skan if (!e->callee->aux 136169689Skan && node->analyzed 137169689Skan && (!e->inline_failed || !e->callee->analyzed 138169689Skan || (!DECL_EXTERNAL (e->callee->decl)) 139169689Skan || before_inlining_p)) 140169689Skan { 141169689Skan e->callee->aux = first; 142169689Skan first = e->callee; 143169689Skan } 144169689Skan } 145169689Skan 146169689Skan /* Remove unreachable nodes. Extern inline functions need special care; 147169689Skan Unreachable extern inline functions shall be removed. 148169689Skan Reachable extern inline functions we never inlined shall get their bodies 149169689Skan eliminated. 150169689Skan Reachable extern inline functions we sometimes inlined will be turned into 151169689Skan unanalyzed nodes so they look like for true extern functions to the rest 152169689Skan of code. Body of such functions is released via remove_node once the 153169689Skan inline clones are eliminated. */ 154169689Skan for (node = cgraph_nodes; node; node = next) 155169689Skan { 156169689Skan next = node->next; 157169689Skan if (!node->aux) 158169689Skan { 159169689Skan int local_insns; 160169689Skan tree decl = node->decl; 161169689Skan 162169689Skan node->global.inlined_to = NULL; 163169689Skan if (DECL_STRUCT_FUNCTION (decl)) 164169689Skan local_insns = node->local.self_insns; 165169689Skan else 166169689Skan local_insns = 0; 167169689Skan if (file) 168169689Skan fprintf (file, " %s", cgraph_node_name (node)); 169169689Skan if (!node->analyzed || !DECL_EXTERNAL (node->decl) 170169689Skan || before_inlining_p) 171169689Skan cgraph_remove_node (node); 172169689Skan else 173169689Skan { 174169689Skan struct cgraph_edge *e; 175169689Skan 176169689Skan for (e = node->callers; e; e = e->next_caller) 177169689Skan if (e->caller->aux) 178169689Skan break; 179169689Skan if (e || node->needed) 180169689Skan { 181169689Skan struct cgraph_node *clone; 182169689Skan 183169689Skan for (clone = node->next_clone; clone; 184169689Skan clone = clone->next_clone) 185169689Skan if (clone->aux) 186169689Skan break; 187169689Skan if (!clone) 188169689Skan { 189169689Skan DECL_SAVED_TREE (node->decl) = NULL; 190169689Skan DECL_STRUCT_FUNCTION (node->decl) = NULL; 191169689Skan DECL_INITIAL (node->decl) = error_mark_node; 192169689Skan node->analyzed = false; 193169689Skan } 194169689Skan cgraph_node_remove_callees (node); 195169689Skan node->analyzed = false; 196169689Skan } 197169689Skan else 198169689Skan cgraph_remove_node (node); 199169689Skan } 200169689Skan if (!DECL_SAVED_TREE (decl)) 201169689Skan insns += local_insns; 202169689Skan changed = true; 203169689Skan } 204169689Skan } 205169689Skan for (node = cgraph_nodes; node; node = node->next) 206169689Skan node->aux = NULL; 207169689Skan if (file) 208169689Skan fprintf (file, "\nReclaimed %i insns", insns); 209169689Skan return changed; 210169689Skan} 211