ipa.c revision 169689
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 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); 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 *file) 98{ 99 struct cgraph_node *first = (void *) 1; 100 struct cgraph_node *node, *next; 101 bool changed = false; 102 int insns = 0; 103 104#ifdef ENABLE_CHECKING 105 verify_cgraph (); 106#endif 107 if (file) 108 fprintf (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 = next) 155 { 156 next = node->next; 157 if (!node->aux) 158 { 159 int local_insns; 160 tree decl = node->decl; 161 162 node->global.inlined_to = NULL; 163 if (DECL_STRUCT_FUNCTION (decl)) 164 local_insns = node->local.self_insns; 165 else 166 local_insns = 0; 167 if (file) 168 fprintf (file, " %s", cgraph_node_name (node)); 169 if (!node->analyzed || !DECL_EXTERNAL (node->decl) 170 || before_inlining_p) 171 cgraph_remove_node (node); 172 else 173 { 174 struct cgraph_edge *e; 175 176 for (e = node->callers; e; e = e->next_caller) 177 if (e->caller->aux) 178 break; 179 if (e || node->needed) 180 { 181 struct cgraph_node *clone; 182 183 for (clone = node->next_clone; clone; 184 clone = clone->next_clone) 185 if (clone->aux) 186 break; 187 if (!clone) 188 { 189 DECL_SAVED_TREE (node->decl) = NULL; 190 DECL_STRUCT_FUNCTION (node->decl) = NULL; 191 DECL_INITIAL (node->decl) = error_mark_node; 192 node->analyzed = false; 193 } 194 cgraph_node_remove_callees (node); 195 node->analyzed = false; 196 } 197 else 198 cgraph_remove_node (node); 199 } 200 if (!DECL_SAVED_TREE (decl)) 201 insns += local_insns; 202 changed = true; 203 } 204 } 205 for (node = cgraph_nodes; node; node = node->next) 206 node->aux = NULL; 207 if (file) 208 fprintf (file, "\nReclaimed %i insns", insns); 209 return changed; 210} 211