1/* Basic IPA optimizations and utilities. 2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 2, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to the Free 18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 1902110-1301, USA. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tm.h" 25#include "cgraph.h" 26 27/* Fill array order with all nodes with output flag set in the reverse 28 topological order. */ 29 30int 31cgraph_postorder (struct cgraph_node **order) 32{ 33 struct cgraph_node *node, *node2; 34 int stack_size = 0; 35 int order_pos = 0; 36 struct cgraph_edge *edge, last; 37 38 struct cgraph_node **stack = 39 xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); 40 41 /* We have to deal with cycles nicely, so use a depth first traversal 42 output algorithm. Ignore the fact that some functions won't need 43 to be output and put them into order as well, so we get dependencies 44 right through intline functions. */ 45 for (node = cgraph_nodes; node; node = node->next) 46 node->aux = NULL; 47 for (node = cgraph_nodes; node; node = node->next) 48 if (!node->aux) 49 { 50 node2 = node; 51 if (!node->callers) 52 node->aux = &last; 53 else 54 node->aux = node->callers; 55 while (node2) 56 { 57 while (node2->aux != &last) 58 { 59 edge = node2->aux; 60 if (edge->next_caller) 61 node2->aux = edge->next_caller; 62 else 63 node2->aux = &last; 64 if (!edge->caller->aux) 65 { 66 if (!edge->caller->callers) 67 edge->caller->aux = &last; 68 else 69 edge->caller->aux = edge->caller->callers; 70 stack[stack_size++] = node2; 71 node2 = edge->caller; 72 break; 73 } 74 } 75 if (node2->aux == &last) 76 { 77 order[order_pos++] = node2; 78 if (stack_size) 79 node2 = stack[--stack_size]; 80 else 81 node2 = NULL; 82 } 83 } 84 } 85 free (stack); 86 for (node = cgraph_nodes; node; node = node->next) 87 node->aux = NULL; 88 return order_pos; 89} 90 91/* Perform reachability analysis and reclaim all unreachable nodes. 92 If BEFORE_INLINING_P is true this function is called before inlining 93 decisions has been made. If BEFORE_INLINING_P is false this function also 94 removes unneeded bodies of extern inline functions. */ 95 96bool 97cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *dump_file) 98{ 99 struct cgraph_node *first = (void *) 1; 100 struct cgraph_node *node; 101 bool changed = false; 102 int insns = 0; 103 104#ifdef ENABLE_CHECKING 105 verify_cgraph (); 106#endif 107 if (dump_file) 108 fprintf (dump_file, "\nReclaiming functions:"); 109#ifdef ENABLE_CHECKING 110 for (node = cgraph_nodes; node; node = node->next) 111 gcc_assert (!node->aux); 112#endif 113 for (node = cgraph_nodes; node; node = node->next) 114 if (node->needed && !node->global.inlined_to 115 && ((!DECL_EXTERNAL (node->decl)) 116 || !node->analyzed 117 || before_inlining_p)) 118 { 119 node->aux = first; 120 first = node; 121 } 122 else 123 gcc_assert (!node->aux); 124 125 /* Perform reachability analysis. As a special case do not consider 126 extern inline functions not inlined as live because we won't output 127 them at all. */ 128 while (first != (void *) 1) 129 { 130 struct cgraph_edge *e; 131 node = first; 132 first = first->aux; 133 134 for (e = node->callees; e; e = e->next_callee) 135 if (!e->callee->aux 136 && node->analyzed 137 && (!e->inline_failed || !e->callee->analyzed 138 || (!DECL_EXTERNAL (e->callee->decl)) 139 || before_inlining_p)) 140 { 141 e->callee->aux = first; 142 first = e->callee; 143 } 144 } 145 146 /* Remove unreachable nodes. Extern inline functions need special care; 147 Unreachable extern inline functions shall be removed. 148 Reachable extern inline functions we never inlined shall get their bodies 149 eliminated. 150 Reachable extern inline functions we sometimes inlined will be turned into 151 unanalyzed nodes so they look like for true extern functions to the rest 152 of code. Body of such functions is released via remove_node once the 153 inline clones are eliminated. */ 154 for (node = cgraph_nodes; node; node = node->next) 155 { 156 if (!node->aux) 157 { 158 int local_insns; 159 tree decl = node->decl; 160 161 node->global.inlined_to = NULL; 162 if (DECL_STRUCT_FUNCTION (decl)) 163 local_insns = node->local.self_insns; 164 else 165 local_insns = 0; 166 if (dump_file) 167 fprintf (dump_file, " %s", cgraph_node_name (node)); 168 if (!node->analyzed || !DECL_EXTERNAL (node->decl) 169 || before_inlining_p) 170 cgraph_remove_node (node); 171 else 172 { 173 struct cgraph_edge *e; 174 175 for (e = node->callers; e; e = e->next_caller) 176 if (e->caller->aux) 177 break; 178 if (e || node->needed) 179 { 180 struct cgraph_node *clone; 181 182 for (clone = node->next_clone; clone; 183 clone = clone->next_clone) 184 if (clone->aux) 185 break; 186 if (!clone) 187 { 188 DECL_SAVED_TREE (node->decl) = NULL; 189 DECL_STRUCT_FUNCTION (node->decl) = NULL; 190 DECL_INITIAL (node->decl) = error_mark_node; 191 node->analyzed = false; 192 } 193 cgraph_node_remove_callees (node); 194 node->analyzed = false; 195 } 196 else 197 cgraph_remove_node (node); 198 } 199 if (!DECL_SAVED_TREE (decl)) 200 insns += local_insns; 201 changed = true; 202 } 203 } 204 for (node = cgraph_nodes; node; node = node->next) 205 node->aux = NULL; 206 if (dump_file) 207 fprintf (dump_file, "\nReclaimed %i insns", insns); 208 return changed; 209} 210