1 /* Utilities for ipa analysis. 2 Copyright (C) 2005, 2007, 2008 Free Software Foundation, Inc. 3 Contributed by Kenneth Zadeck <zadeck@naturalbridge.com> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "tm.h" 25 #include "tree.h" 26 #include "tree-flow.h" 27 #include "tree-inline.h" 28 #include "tree-pass.h" 29 #include "langhooks.h" 30 #include "pointer-set.h" 31 #include "splay-tree.h" 32 #include "ggc.h" 33 #include "ipa-utils.h" 34 #include "ipa-reference.h" 35 #include "gimple.h" 36 #include "cgraph.h" 37 #include "output.h" 38 #include "flags.h" 39 #include "timevar.h" 40 #include "diagnostic.h" 41 #include "langhooks.h" 42 43 /* Debugging function for postorder and inorder code. NOTE is a string 44 that is printed before the nodes are printed. ORDER is an array of 45 cgraph_nodes that has COUNT useful nodes in it. */ 46 47 void 48 ipa_print_order (FILE* out, 49 const char * note, 50 struct cgraph_node** order, 51 int count) 52 { 53 int i; 54 fprintf (out, "\n\n ordered call graph: %s\n", note); 55 56 for (i = count - 1; i >= 0; i--) 57 dump_cgraph_node(dump_file, order[i]); 58 fprintf (out, "\n"); 59 fflush(out); 60 } 61 62 63 struct searchc_env { 64 struct cgraph_node **stack; 65 int stack_size; 66 struct cgraph_node **result; 67 int order_pos; 68 splay_tree nodes_marked_new; 69 bool reduce; 70 bool allow_overwritable; 71 int count; 72 }; 73 74 /* This is an implementation of Tarjan's strongly connected region 75 finder as reprinted in Aho Hopcraft and Ullman's The Design and 76 Analysis of Computer Programs (1975) pages 192-193. This version 77 has been customized for cgraph_nodes. The env parameter is because 78 it is recursive and there are no nested functions here. This 79 function should only be called from itself or 80 ipa_reduced_postorder. ENV is a stack env and would be 81 unnecessary if C had nested functions. V is the node to start 82 searching from. */ 83 84 static void 85 searchc (struct searchc_env* env, struct cgraph_node *v, 86 bool (*ignore_edge) (struct cgraph_edge *)) 87 { 88 struct cgraph_edge *edge; 89 struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux; 90 91 /* mark node as old */ 92 v_info->new_node = false; 93 splay_tree_remove (env->nodes_marked_new, v->uid); 94 95 v_info->dfn_number = env->count; 96 v_info->low_link = env->count; 97 env->count++; 98 env->stack[(env->stack_size)++] = v; 99 v_info->on_stack = true; 100 101 for (edge = v->callees; edge; edge = edge->next_callee) 102 { 103 struct ipa_dfs_info * w_info; 104 enum availability avail; 105 struct cgraph_node *w = cgraph_function_or_thunk_node (edge->callee, &avail); 106 107 if (!w || (ignore_edge && ignore_edge (edge))) 108 continue; 109 110 if (w->aux 111 && (avail > AVAIL_OVERWRITABLE 112 || (env->allow_overwritable && avail == AVAIL_OVERWRITABLE))) 113 { 114 w_info = (struct ipa_dfs_info *) w->aux; 115 if (w_info->new_node) 116 { 117 searchc (env, w, ignore_edge); 118 v_info->low_link = 119 (v_info->low_link < w_info->low_link) ? 120 v_info->low_link : w_info->low_link; 121 } 122 else 123 if ((w_info->dfn_number < v_info->dfn_number) 124 && (w_info->on_stack)) 125 v_info->low_link = 126 (w_info->dfn_number < v_info->low_link) ? 127 w_info->dfn_number : v_info->low_link; 128 } 129 } 130 131 132 if (v_info->low_link == v_info->dfn_number) 133 { 134 struct cgraph_node *last = NULL; 135 struct cgraph_node *x; 136 struct ipa_dfs_info *x_info; 137 do { 138 x = env->stack[--(env->stack_size)]; 139 x_info = (struct ipa_dfs_info *) x->aux; 140 x_info->on_stack = false; 141 x_info->scc_no = v_info->dfn_number; 142 143 if (env->reduce) 144 { 145 x_info->next_cycle = last; 146 last = x; 147 } 148 else 149 env->result[env->order_pos++] = x; 150 } 151 while (v != x); 152 if (env->reduce) 153 env->result[env->order_pos++] = v; 154 } 155 } 156 157 /* Topsort the call graph by caller relation. Put the result in ORDER. 158 159 The REDUCE flag is true if you want the cycles reduced to single nodes. Set 160 ALLOW_OVERWRITABLE if nodes with such availability should be included. 161 IGNORE_EDGE, if non-NULL is a hook that may make some edges insignificant 162 for the topological sort. */ 163 164 int 165 ipa_reduced_postorder (struct cgraph_node **order, 166 bool reduce, bool allow_overwritable, 167 bool (*ignore_edge) (struct cgraph_edge *)) 168 { 169 struct cgraph_node *node; 170 struct searchc_env env; 171 splay_tree_node result; 172 env.stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); 173 env.stack_size = 0; 174 env.result = order; 175 env.order_pos = 0; 176 env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0); 177 env.count = 1; 178 env.reduce = reduce; 179 env.allow_overwritable = allow_overwritable; 180 181 for (node = cgraph_nodes; node; node = node->next) 182 { 183 enum availability avail = cgraph_function_body_availability (node); 184 185 if (avail > AVAIL_OVERWRITABLE 186 || (allow_overwritable 187 && (avail == AVAIL_OVERWRITABLE))) 188 { 189 /* Reuse the info if it is already there. */ 190 struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->aux; 191 if (!info) 192 info = XCNEW (struct ipa_dfs_info); 193 info->new_node = true; 194 info->on_stack = false; 195 info->next_cycle = NULL; 196 node->aux = info; 197 198 splay_tree_insert (env.nodes_marked_new, 199 (splay_tree_key)node->uid, 200 (splay_tree_value)node); 201 } 202 else 203 node->aux = NULL; 204 } 205 result = splay_tree_min (env.nodes_marked_new); 206 while (result) 207 { 208 node = (struct cgraph_node *)result->value; 209 searchc (&env, node, ignore_edge); 210 result = splay_tree_min (env.nodes_marked_new); 211 } 212 splay_tree_delete (env.nodes_marked_new); 213 free (env.stack); 214 215 return env.order_pos; 216 } 217 218 /* Deallocate all ipa_dfs_info structures pointed to by the aux pointer of call 219 graph nodes. */ 220 221 void 222 ipa_free_postorder_info (void) 223 { 224 struct cgraph_node *node; 225 for (node = cgraph_nodes; node; node = node->next) 226 { 227 /* Get rid of the aux information. */ 228 if (node->aux) 229 { 230 free (node->aux); 231 node->aux = NULL; 232 } 233 } 234 } 235 236 struct postorder_stack 237 { 238 struct cgraph_node *node; 239 struct cgraph_edge *edge; 240 int ref; 241 }; 242 243 /* Fill array order with all nodes with output flag set in the reverse 244 topological order. Return the number of elements in the array. 245 FIXME: While walking, consider aliases, too. */ 246 247 int 248 ipa_reverse_postorder (struct cgraph_node **order) 249 { 250 struct cgraph_node *node, *node2; 251 int stack_size = 0; 252 int order_pos = 0; 253 struct cgraph_edge *edge; 254 int pass; 255 struct ipa_ref *ref; 256 257 struct postorder_stack *stack = 258 XCNEWVEC (struct postorder_stack, cgraph_n_nodes); 259 260 /* We have to deal with cycles nicely, so use a depth first traversal 261 output algorithm. Ignore the fact that some functions won't need 262 to be output and put them into order as well, so we get dependencies 263 right through inline functions. */ 264 for (node = cgraph_nodes; node; node = node->next) 265 node->aux = NULL; 266 for (pass = 0; pass < 2; pass++) 267 for (node = cgraph_nodes; node; node = node->next) 268 if (!node->aux 269 && (pass 270 || (!node->address_taken 271 && !node->global.inlined_to 272 && !node->alias && !node->thunk.thunk_p 273 && !cgraph_only_called_directly_p (node)))) 274 { 275 stack_size = 0; 276 stack[stack_size].node = node; 277 stack[stack_size].edge = node->callers; 278 stack[stack_size].ref = 0; 279 node->aux = (void *)(size_t)1; 280 while (stack_size >= 0) 281 { 282 while (true) 283 { 284 node2 = NULL; 285 while (stack[stack_size].edge && !node2) 286 { 287 edge = stack[stack_size].edge; 288 node2 = edge->caller; 289 stack[stack_size].edge = edge->next_caller; 290 /* Break possible cycles involving always-inline 291 functions by ignoring edges from always-inline 292 functions to non-always-inline functions. */ 293 if (DECL_DISREGARD_INLINE_LIMITS (edge->caller->decl) 294 && !DECL_DISREGARD_INLINE_LIMITS 295 (cgraph_function_node (edge->callee, NULL)->decl)) 296 node2 = NULL; 297 } 298 for (;ipa_ref_list_refering_iterate (&stack[stack_size].node->ref_list, 299 stack[stack_size].ref, 300 ref) && !node2; 301 stack[stack_size].ref++) 302 { 303 if (ref->use == IPA_REF_ALIAS) 304 node2 = ipa_ref_refering_node (ref); 305 } 306 if (!node2) 307 break; 308 if (!node2->aux) 309 { 310 stack[++stack_size].node = node2; 311 stack[stack_size].edge = node2->callers; 312 stack[stack_size].ref = 0; 313 node2->aux = (void *)(size_t)1; 314 } 315 } 316 order[order_pos++] = stack[stack_size--].node; 317 } 318 } 319 free (stack); 320 for (node = cgraph_nodes; node; node = node->next) 321 node->aux = NULL; 322 return order_pos; 323 } 324 325 326 327 /* Given a memory reference T, will return the variable at the bottom 328 of the access. Unlike get_base_address, this will recurse thru 329 INDIRECT_REFS. */ 330 331 tree 332 get_base_var (tree t) 333 { 334 while (!SSA_VAR_P (t) 335 && (!CONSTANT_CLASS_P (t)) 336 && TREE_CODE (t) != LABEL_DECL 337 && TREE_CODE (t) != FUNCTION_DECL 338 && TREE_CODE (t) != CONST_DECL 339 && TREE_CODE (t) != CONSTRUCTOR) 340 { 341 t = TREE_OPERAND (t, 0); 342 } 343 return t; 344 } 345 346 347 /* Create a new cgraph node set. */ 348 349 cgraph_node_set 350 cgraph_node_set_new (void) 351 { 352 cgraph_node_set new_node_set; 353 354 new_node_set = XCNEW (struct cgraph_node_set_def); 355 new_node_set->map = pointer_map_create (); 356 new_node_set->nodes = NULL; 357 return new_node_set; 358 } 359 360 361 /* Add cgraph_node NODE to cgraph_node_set SET. */ 362 363 void 364 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node) 365 { 366 void **slot; 367 368 slot = pointer_map_insert (set->map, node); 369 370 if (*slot) 371 { 372 int index = (size_t) *slot - 1; 373 gcc_checking_assert ((VEC_index (cgraph_node_ptr, set->nodes, index) 374 == node)); 375 return; 376 } 377 378 *slot = (void *)(size_t) (VEC_length (cgraph_node_ptr, set->nodes) + 1); 379 380 /* Insert into node vector. */ 381 VEC_safe_push (cgraph_node_ptr, heap, set->nodes, node); 382 } 383 384 385 /* Remove cgraph_node NODE from cgraph_node_set SET. */ 386 387 void 388 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node) 389 { 390 void **slot, **last_slot; 391 int index; 392 struct cgraph_node *last_node; 393 394 slot = pointer_map_contains (set->map, node); 395 if (slot == NULL || !*slot) 396 return; 397 398 index = (size_t) *slot - 1; 399 gcc_checking_assert (VEC_index (cgraph_node_ptr, set->nodes, index) 400 == node); 401 402 /* Remove from vector. We do this by swapping node with the last element 403 of the vector. */ 404 last_node = VEC_pop (cgraph_node_ptr, set->nodes); 405 if (last_node != node) 406 { 407 last_slot = pointer_map_contains (set->map, last_node); 408 gcc_checking_assert (last_slot && *last_slot); 409 *last_slot = (void *)(size_t) (index + 1); 410 411 /* Move the last element to the original spot of NODE. */ 412 VEC_replace (cgraph_node_ptr, set->nodes, index, last_node); 413 } 414 415 /* Remove element from hash table. */ 416 *slot = NULL; 417 } 418 419 420 /* Find NODE in SET and return an iterator to it if found. A null iterator 421 is returned if NODE is not in SET. */ 422 423 cgraph_node_set_iterator 424 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node) 425 { 426 void **slot; 427 cgraph_node_set_iterator csi; 428 429 slot = pointer_map_contains (set->map, node); 430 if (slot == NULL || !*slot) 431 csi.index = (unsigned) ~0; 432 else 433 csi.index = (size_t)*slot - 1; 434 csi.set = set; 435 436 return csi; 437 } 438 439 440 /* Dump content of SET to file F. */ 441 442 void 443 dump_cgraph_node_set (FILE *f, cgraph_node_set set) 444 { 445 cgraph_node_set_iterator iter; 446 447 for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter)) 448 { 449 struct cgraph_node *node = csi_node (iter); 450 fprintf (f, " %s/%i", cgraph_node_name (node), node->uid); 451 } 452 fprintf (f, "\n"); 453 } 454 455 456 /* Dump content of SET to stderr. */ 457 458 DEBUG_FUNCTION void 459 debug_cgraph_node_set (cgraph_node_set set) 460 { 461 dump_cgraph_node_set (stderr, set); 462 } 463 464 465 /* Free varpool node set. */ 466 467 void 468 free_cgraph_node_set (cgraph_node_set set) 469 { 470 VEC_free (cgraph_node_ptr, heap, set->nodes); 471 pointer_map_destroy (set->map); 472 free (set); 473 } 474 475 476 /* Create a new varpool node set. */ 477 478 varpool_node_set 479 varpool_node_set_new (void) 480 { 481 varpool_node_set new_node_set; 482 483 new_node_set = XCNEW (struct varpool_node_set_def); 484 new_node_set->map = pointer_map_create (); 485 new_node_set->nodes = NULL; 486 return new_node_set; 487 } 488 489 490 /* Add varpool_node NODE to varpool_node_set SET. */ 491 492 void 493 varpool_node_set_add (varpool_node_set set, struct varpool_node *node) 494 { 495 void **slot; 496 497 slot = pointer_map_insert (set->map, node); 498 499 if (*slot) 500 { 501 int index = (size_t) *slot - 1; 502 gcc_checking_assert ((VEC_index (varpool_node_ptr, set->nodes, index) 503 == node)); 504 return; 505 } 506 507 *slot = (void *)(size_t) (VEC_length (varpool_node_ptr, set->nodes) + 1); 508 509 /* Insert into node vector. */ 510 VEC_safe_push (varpool_node_ptr, heap, set->nodes, node); 511 } 512 513 514 /* Remove varpool_node NODE from varpool_node_set SET. */ 515 516 void 517 varpool_node_set_remove (varpool_node_set set, struct varpool_node *node) 518 { 519 void **slot, **last_slot; 520 int index; 521 struct varpool_node *last_node; 522 523 slot = pointer_map_contains (set->map, node); 524 if (slot == NULL || !*slot) 525 return; 526 527 index = (size_t) *slot - 1; 528 gcc_checking_assert (VEC_index (varpool_node_ptr, set->nodes, index) 529 == node); 530 531 /* Remove from vector. We do this by swapping node with the last element 532 of the vector. */ 533 last_node = VEC_pop (varpool_node_ptr, set->nodes); 534 if (last_node != node) 535 { 536 last_slot = pointer_map_contains (set->map, last_node); 537 gcc_checking_assert (last_slot && *last_slot); 538 *last_slot = (void *)(size_t) (index + 1); 539 540 /* Move the last element to the original spot of NODE. */ 541 VEC_replace (varpool_node_ptr, set->nodes, index, last_node); 542 } 543 544 /* Remove element from hash table. */ 545 *slot = NULL; 546 } 547 548 549 /* Find NODE in SET and return an iterator to it if found. A null iterator 550 is returned if NODE is not in SET. */ 551 552 varpool_node_set_iterator 553 varpool_node_set_find (varpool_node_set set, struct varpool_node *node) 554 { 555 void **slot; 556 varpool_node_set_iterator vsi; 557 558 slot = pointer_map_contains (set->map, node); 559 if (slot == NULL || !*slot) 560 vsi.index = (unsigned) ~0; 561 else 562 vsi.index = (size_t)*slot - 1; 563 vsi.set = set; 564 565 return vsi; 566 } 567 568 569 /* Dump content of SET to file F. */ 570 571 void 572 dump_varpool_node_set (FILE *f, varpool_node_set set) 573 { 574 varpool_node_set_iterator iter; 575 576 for (iter = vsi_start (set); !vsi_end_p (iter); vsi_next (&iter)) 577 { 578 struct varpool_node *node = vsi_node (iter); 579 fprintf (f, " %s", varpool_node_name (node)); 580 } 581 fprintf (f, "\n"); 582 } 583 584 585 /* Free varpool node set. */ 586 587 void 588 free_varpool_node_set (varpool_node_set set) 589 { 590 VEC_free (varpool_node_ptr, heap, set->nodes); 591 pointer_map_destroy (set->map); 592 free (set); 593 } 594 595 596 /* Dump content of SET to stderr. */ 597 598 DEBUG_FUNCTION void 599 debug_varpool_node_set (varpool_node_set set) 600 { 601 dump_varpool_node_set (stderr, set); 602 } 603