1 /* Utilities for ipa analysis. 2 Copyright (C) 2005-2015 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 "hash-set.h" 26 #include "machmode.h" 27 #include "vec.h" 28 #include "double-int.h" 29 #include "input.h" 30 #include "alias.h" 31 #include "symtab.h" 32 #include "options.h" 33 #include "wide-int.h" 34 #include "inchash.h" 35 #include "tree.h" 36 #include "fold-const.h" 37 #include "predict.h" 38 #include "hard-reg-set.h" 39 #include "input.h" 40 #include "function.h" 41 #include "dominance.h" 42 #include "cfg.h" 43 #include "basic-block.h" 44 #include "tree-ssa-alias.h" 45 #include "internal-fn.h" 46 #include "gimple-expr.h" 47 #include "is-a.h" 48 #include "gimple.h" 49 #include "tree-inline.h" 50 #include "dumpfile.h" 51 #include "langhooks.h" 52 #include "splay-tree.h" 53 #include "hash-map.h" 54 #include "plugin-api.h" 55 #include "ipa-ref.h" 56 #include "cgraph.h" 57 #include "ipa-utils.h" 58 #include "bitmap.h" 59 #include "ipa-reference.h" 60 #include "flags.h" 61 #include "diagnostic.h" 62 #include "langhooks.h" 63 #include "lto-streamer.h" 64 #include "alloc-pool.h" 65 #include "symbol-summary.h" 66 #include "ipa-prop.h" 67 #include "ipa-inline.h" 68 69 /* Debugging function for postorder and inorder code. NOTE is a string 70 that is printed before the nodes are printed. ORDER is an array of 71 cgraph_nodes that has COUNT useful nodes in it. */ 72 73 void 74 ipa_print_order (FILE* out, 75 const char * note, 76 struct cgraph_node** order, 77 int count) 78 { 79 int i; 80 fprintf (out, "\n\n ordered call graph: %s\n", note); 81 82 for (i = count - 1; i >= 0; i--) 83 order[i]->dump (out); 84 fprintf (out, "\n"); 85 fflush (out); 86 } 87 88 89 struct searchc_env { 90 struct cgraph_node **stack; 91 int stack_size; 92 struct cgraph_node **result; 93 int order_pos; 94 splay_tree nodes_marked_new; 95 bool reduce; 96 bool allow_overwritable; 97 int count; 98 }; 99 100 /* This is an implementation of Tarjan's strongly connected region 101 finder as reprinted in Aho Hopcraft and Ullman's The Design and 102 Analysis of Computer Programs (1975) pages 192-193. This version 103 has been customized for cgraph_nodes. The env parameter is because 104 it is recursive and there are no nested functions here. This 105 function should only be called from itself or 106 ipa_reduced_postorder. ENV is a stack env and would be 107 unnecessary if C had nested functions. V is the node to start 108 searching from. */ 109 110 static void 111 searchc (struct searchc_env* env, struct cgraph_node *v, 112 bool (*ignore_edge) (struct cgraph_edge *)) 113 { 114 struct cgraph_edge *edge; 115 struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux; 116 117 /* mark node as old */ 118 v_info->new_node = false; 119 splay_tree_remove (env->nodes_marked_new, v->uid); 120 121 v_info->dfn_number = env->count; 122 v_info->low_link = env->count; 123 env->count++; 124 env->stack[(env->stack_size)++] = v; 125 v_info->on_stack = true; 126 127 for (edge = v->callees; edge; edge = edge->next_callee) 128 { 129 struct ipa_dfs_info * w_info; 130 enum availability avail; 131 struct cgraph_node *w = edge->callee->ultimate_alias_target (&avail); 132 133 if (!w || (ignore_edge && ignore_edge (edge))) 134 continue; 135 136 if (w->aux 137 && (avail > AVAIL_INTERPOSABLE 138 || (env->allow_overwritable && avail == AVAIL_INTERPOSABLE))) 139 { 140 w_info = (struct ipa_dfs_info *) w->aux; 141 if (w_info->new_node) 142 { 143 searchc (env, w, ignore_edge); 144 v_info->low_link = 145 (v_info->low_link < w_info->low_link) ? 146 v_info->low_link : w_info->low_link; 147 } 148 else 149 if ((w_info->dfn_number < v_info->dfn_number) 150 && (w_info->on_stack)) 151 v_info->low_link = 152 (w_info->dfn_number < v_info->low_link) ? 153 w_info->dfn_number : v_info->low_link; 154 } 155 } 156 157 158 if (v_info->low_link == v_info->dfn_number) 159 { 160 struct cgraph_node *last = NULL; 161 struct cgraph_node *x; 162 struct ipa_dfs_info *x_info; 163 do { 164 x = env->stack[--(env->stack_size)]; 165 x_info = (struct ipa_dfs_info *) x->aux; 166 x_info->on_stack = false; 167 x_info->scc_no = v_info->dfn_number; 168 169 if (env->reduce) 170 { 171 x_info->next_cycle = last; 172 last = x; 173 } 174 else 175 env->result[env->order_pos++] = x; 176 } 177 while (v != x); 178 if (env->reduce) 179 env->result[env->order_pos++] = v; 180 } 181 } 182 183 /* Topsort the call graph by caller relation. Put the result in ORDER. 184 185 The REDUCE flag is true if you want the cycles reduced to single nodes. 186 You can use ipa_get_nodes_in_cycle to obtain a vector containing all real 187 call graph nodes in a reduced node. 188 189 Set ALLOW_OVERWRITABLE if nodes with such availability should be included. 190 IGNORE_EDGE, if non-NULL is a hook that may make some edges insignificant 191 for the topological sort. */ 192 193 int 194 ipa_reduced_postorder (struct cgraph_node **order, 195 bool reduce, bool allow_overwritable, 196 bool (*ignore_edge) (struct cgraph_edge *)) 197 { 198 struct cgraph_node *node; 199 struct searchc_env env; 200 splay_tree_node result; 201 env.stack = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count); 202 env.stack_size = 0; 203 env.result = order; 204 env.order_pos = 0; 205 env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0); 206 env.count = 1; 207 env.reduce = reduce; 208 env.allow_overwritable = allow_overwritable; 209 210 FOR_EACH_DEFINED_FUNCTION (node) 211 { 212 enum availability avail = node->get_availability (); 213 214 if (avail > AVAIL_INTERPOSABLE 215 || (allow_overwritable 216 && (avail == AVAIL_INTERPOSABLE))) 217 { 218 /* Reuse the info if it is already there. */ 219 struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->aux; 220 if (!info) 221 info = XCNEW (struct ipa_dfs_info); 222 info->new_node = true; 223 info->on_stack = false; 224 info->next_cycle = NULL; 225 node->aux = info; 226 227 splay_tree_insert (env.nodes_marked_new, 228 (splay_tree_key)node->uid, 229 (splay_tree_value)node); 230 } 231 else 232 node->aux = NULL; 233 } 234 result = splay_tree_min (env.nodes_marked_new); 235 while (result) 236 { 237 node = (struct cgraph_node *)result->value; 238 searchc (&env, node, ignore_edge); 239 result = splay_tree_min (env.nodes_marked_new); 240 } 241 splay_tree_delete (env.nodes_marked_new); 242 free (env.stack); 243 244 return env.order_pos; 245 } 246 247 /* Deallocate all ipa_dfs_info structures pointed to by the aux pointer of call 248 graph nodes. */ 249 250 void 251 ipa_free_postorder_info (void) 252 { 253 struct cgraph_node *node; 254 FOR_EACH_DEFINED_FUNCTION (node) 255 { 256 /* Get rid of the aux information. */ 257 if (node->aux) 258 { 259 free (node->aux); 260 node->aux = NULL; 261 } 262 } 263 } 264 265 /* Get the set of nodes for the cycle in the reduced call graph starting 266 from NODE. */ 267 268 vec<cgraph_node *> 269 ipa_get_nodes_in_cycle (struct cgraph_node *node) 270 { 271 vec<cgraph_node *> v = vNULL; 272 struct ipa_dfs_info *node_dfs_info; 273 while (node) 274 { 275 v.safe_push (node); 276 node_dfs_info = (struct ipa_dfs_info *) node->aux; 277 node = node_dfs_info->next_cycle; 278 } 279 return v; 280 } 281 282 /* Return true iff the CS is an edge within a strongly connected component as 283 computed by ipa_reduced_postorder. */ 284 285 bool 286 ipa_edge_within_scc (struct cgraph_edge *cs) 287 { 288 struct ipa_dfs_info *caller_dfs = (struct ipa_dfs_info *) cs->caller->aux; 289 struct ipa_dfs_info *callee_dfs; 290 struct cgraph_node *callee = cs->callee->function_symbol (); 291 292 callee_dfs = (struct ipa_dfs_info *) callee->aux; 293 return (caller_dfs 294 && callee_dfs 295 && caller_dfs->scc_no == callee_dfs->scc_no); 296 } 297 298 struct postorder_stack 299 { 300 struct cgraph_node *node; 301 struct cgraph_edge *edge; 302 int ref; 303 }; 304 305 /* Fill array order with all nodes with output flag set in the reverse 306 topological order. Return the number of elements in the array. 307 FIXME: While walking, consider aliases, too. */ 308 309 int 310 ipa_reverse_postorder (struct cgraph_node **order) 311 { 312 struct cgraph_node *node, *node2; 313 int stack_size = 0; 314 int order_pos = 0; 315 struct cgraph_edge *edge; 316 int pass; 317 struct ipa_ref *ref = NULL; 318 319 struct postorder_stack *stack = 320 XCNEWVEC (struct postorder_stack, symtab->cgraph_count); 321 322 /* We have to deal with cycles nicely, so use a depth first traversal 323 output algorithm. Ignore the fact that some functions won't need 324 to be output and put them into order as well, so we get dependencies 325 right through inline functions. */ 326 FOR_EACH_FUNCTION (node) 327 node->aux = NULL; 328 for (pass = 0; pass < 2; pass++) 329 FOR_EACH_FUNCTION (node) 330 if (!node->aux 331 && (pass 332 || (!node->address_taken 333 && !node->global.inlined_to 334 && !node->alias && !node->thunk.thunk_p 335 && !node->only_called_directly_p ()))) 336 { 337 stack_size = 0; 338 stack[stack_size].node = node; 339 stack[stack_size].edge = node->callers; 340 stack[stack_size].ref = 0; 341 node->aux = (void *)(size_t)1; 342 while (stack_size >= 0) 343 { 344 while (true) 345 { 346 node2 = NULL; 347 while (stack[stack_size].edge && !node2) 348 { 349 edge = stack[stack_size].edge; 350 node2 = edge->caller; 351 stack[stack_size].edge = edge->next_caller; 352 /* Break possible cycles involving always-inline 353 functions by ignoring edges from always-inline 354 functions to non-always-inline functions. */ 355 if (DECL_DISREGARD_INLINE_LIMITS (edge->caller->decl) 356 && !DECL_DISREGARD_INLINE_LIMITS 357 (edge->callee->function_symbol ()->decl)) 358 node2 = NULL; 359 } 360 for (; stack[stack_size].node->iterate_referring ( 361 stack[stack_size].ref, 362 ref) && !node2; 363 stack[stack_size].ref++) 364 { 365 if (ref->use == IPA_REF_ALIAS) 366 node2 = dyn_cast <cgraph_node *> (ref->referring); 367 } 368 if (!node2) 369 break; 370 if (!node2->aux) 371 { 372 stack[++stack_size].node = node2; 373 stack[stack_size].edge = node2->callers; 374 stack[stack_size].ref = 0; 375 node2->aux = (void *)(size_t)1; 376 } 377 } 378 order[order_pos++] = stack[stack_size--].node; 379 } 380 } 381 free (stack); 382 FOR_EACH_FUNCTION (node) 383 node->aux = NULL; 384 return order_pos; 385 } 386 387 388 389 /* Given a memory reference T, will return the variable at the bottom 390 of the access. Unlike get_base_address, this will recurse through 391 INDIRECT_REFS. */ 392 393 tree 394 get_base_var (tree t) 395 { 396 while (!SSA_VAR_P (t) 397 && (!CONSTANT_CLASS_P (t)) 398 && TREE_CODE (t) != LABEL_DECL 399 && TREE_CODE (t) != FUNCTION_DECL 400 && TREE_CODE (t) != CONST_DECL 401 && TREE_CODE (t) != CONSTRUCTOR) 402 { 403 t = TREE_OPERAND (t, 0); 404 } 405 return t; 406 } 407 408 409 /* SRC and DST are going to be merged. Take SRC's profile and merge it into 410 DST so it is not going to be lost. Possibly destroy SRC's body on the way 411 unless PRESERVE_BODY is set. */ 412 413 void 414 ipa_merge_profiles (struct cgraph_node *dst, 415 struct cgraph_node *src, 416 bool preserve_body) 417 { 418 tree oldsrcdecl = src->decl; 419 struct function *srccfun, *dstcfun; 420 bool match = true; 421 422 if (!src->definition 423 || !dst->definition) 424 return; 425 if (src->frequency < dst->frequency) 426 src->frequency = dst->frequency; 427 428 /* Time profiles are merged. */ 429 if (dst->tp_first_run > src->tp_first_run && src->tp_first_run) 430 dst->tp_first_run = src->tp_first_run; 431 432 if (src->profile_id && !dst->profile_id) 433 dst->profile_id = src->profile_id; 434 435 if (!dst->count) 436 return; 437 if (symtab->dump_file) 438 { 439 fprintf (symtab->dump_file, "Merging profiles of %s/%i to %s/%i\n", 440 xstrdup_for_dump (src->name ()), src->order, 441 xstrdup_for_dump (dst->name ()), dst->order); 442 } 443 dst->count += src->count; 444 445 /* This is ugly. We need to get both function bodies into memory. 446 If declaration is merged, we need to duplicate it to be able 447 to load body that is being replaced. This makes symbol table 448 temporarily inconsistent. */ 449 if (src->decl == dst->decl) 450 { 451 struct lto_in_decl_state temp; 452 struct lto_in_decl_state *state; 453 454 /* We are going to move the decl, we want to remove its file decl data. 455 and link these with the new decl. */ 456 temp.fn_decl = src->decl; 457 lto_in_decl_state **slot 458 = src->lto_file_data->function_decl_states->find_slot (&temp, 459 NO_INSERT); 460 state = *slot; 461 src->lto_file_data->function_decl_states->clear_slot (slot); 462 gcc_assert (state); 463 464 /* Duplicate the decl and be sure it does not link into body of DST. */ 465 src->decl = copy_node (src->decl); 466 DECL_STRUCT_FUNCTION (src->decl) = NULL; 467 DECL_ARGUMENTS (src->decl) = NULL; 468 DECL_INITIAL (src->decl) = NULL; 469 DECL_RESULT (src->decl) = NULL; 470 471 /* Associate the decl state with new declaration, so LTO streamer 472 can look it up. */ 473 state->fn_decl = src->decl; 474 slot 475 = src->lto_file_data->function_decl_states->find_slot (state, INSERT); 476 gcc_assert (!*slot); 477 *slot = state; 478 } 479 src->get_untransformed_body (); 480 dst->get_untransformed_body (); 481 srccfun = DECL_STRUCT_FUNCTION (src->decl); 482 dstcfun = DECL_STRUCT_FUNCTION (dst->decl); 483 if (n_basic_blocks_for_fn (srccfun) 484 != n_basic_blocks_for_fn (dstcfun)) 485 { 486 if (symtab->dump_file) 487 fprintf (symtab->dump_file, 488 "Giving up; number of basic block mismatch.\n"); 489 match = false; 490 } 491 else if (last_basic_block_for_fn (srccfun) 492 != last_basic_block_for_fn (dstcfun)) 493 { 494 if (symtab->dump_file) 495 fprintf (symtab->dump_file, 496 "Giving up; last block mismatch.\n"); 497 match = false; 498 } 499 else 500 { 501 basic_block srcbb, dstbb; 502 503 FOR_ALL_BB_FN (srcbb, srccfun) 504 { 505 unsigned int i; 506 507 dstbb = BASIC_BLOCK_FOR_FN (dstcfun, srcbb->index); 508 if (dstbb == NULL) 509 { 510 if (symtab->dump_file) 511 fprintf (symtab->dump_file, 512 "No matching block for bb %i.\n", 513 srcbb->index); 514 match = false; 515 break; 516 } 517 if (EDGE_COUNT (srcbb->succs) != EDGE_COUNT (dstbb->succs)) 518 { 519 if (symtab->dump_file) 520 fprintf (symtab->dump_file, 521 "Edge count mistmatch for bb %i.\n", 522 srcbb->index); 523 match = false; 524 break; 525 } 526 for (i = 0; i < EDGE_COUNT (srcbb->succs); i++) 527 { 528 edge srce = EDGE_SUCC (srcbb, i); 529 edge dste = EDGE_SUCC (dstbb, i); 530 if (srce->dest->index != dste->dest->index) 531 { 532 if (symtab->dump_file) 533 fprintf (symtab->dump_file, 534 "Succ edge mistmatch for bb %i.\n", 535 srce->dest->index); 536 match = false; 537 break; 538 } 539 } 540 } 541 } 542 if (match) 543 { 544 struct cgraph_edge *e, *e2; 545 basic_block srcbb, dstbb; 546 547 /* TODO: merge also statement histograms. */ 548 FOR_ALL_BB_FN (srcbb, srccfun) 549 { 550 unsigned int i; 551 552 dstbb = BASIC_BLOCK_FOR_FN (dstcfun, srcbb->index); 553 dstbb->count += srcbb->count; 554 for (i = 0; i < EDGE_COUNT (srcbb->succs); i++) 555 { 556 edge srce = EDGE_SUCC (srcbb, i); 557 edge dste = EDGE_SUCC (dstbb, i); 558 dste->count += srce->count; 559 } 560 } 561 push_cfun (dstcfun); 562 counts_to_freqs (); 563 compute_function_frequency (); 564 pop_cfun (); 565 for (e = dst->callees; e; e = e->next_callee) 566 { 567 if (e->speculative) 568 continue; 569 e->count = gimple_bb (e->call_stmt)->count; 570 e->frequency = compute_call_stmt_bb_frequency 571 (dst->decl, 572 gimple_bb (e->call_stmt)); 573 } 574 for (e = dst->indirect_calls, e2 = src->indirect_calls; e; 575 e2 = (e2 ? e2->next_callee : NULL), e = e->next_callee) 576 { 577 gcov_type count = gimple_bb (e->call_stmt)->count; 578 int freq = compute_call_stmt_bb_frequency 579 (dst->decl, 580 gimple_bb (e->call_stmt)); 581 /* When call is speculative, we need to re-distribute probabilities 582 the same way as they was. This is not really correct because 583 in the other copy the speculation may differ; but probably it 584 is not really worth the effort. */ 585 if (e->speculative) 586 { 587 cgraph_edge *direct, *indirect; 588 cgraph_edge *direct2 = NULL, *indirect2 = NULL; 589 ipa_ref *ref; 590 591 e->speculative_call_info (direct, indirect, ref); 592 gcc_assert (e == indirect); 593 if (e2 && e2->speculative) 594 e2->speculative_call_info (direct2, indirect2, ref); 595 if (indirect->count || direct->count) 596 { 597 /* We should mismatch earlier if there is no matching 598 indirect edge. */ 599 if (!e2) 600 { 601 if (dump_file) 602 fprintf (dump_file, 603 "Mismatch in merging indirect edges\n"); 604 } 605 else if (!e2->speculative) 606 indirect->count += e2->count; 607 else if (e2->speculative) 608 { 609 if (DECL_ASSEMBLER_NAME (direct2->callee->decl) 610 != DECL_ASSEMBLER_NAME (direct->callee->decl)) 611 { 612 if (direct2->count >= direct->count) 613 { 614 direct->redirect_callee (direct2->callee); 615 indirect->count += indirect2->count 616 + direct->count; 617 direct->count = direct2->count; 618 } 619 else 620 indirect->count += indirect2->count + direct2->count; 621 } 622 else 623 { 624 direct->count += direct2->count; 625 indirect->count += indirect2->count; 626 } 627 } 628 int prob = RDIV (direct->count * REG_BR_PROB_BASE , 629 direct->count + indirect->count); 630 direct->frequency = RDIV (freq * prob, REG_BR_PROB_BASE); 631 indirect->frequency = RDIV (freq * (REG_BR_PROB_BASE - prob), 632 REG_BR_PROB_BASE); 633 } 634 else 635 /* At the moment we should have only profile feedback based 636 speculations when merging. */ 637 gcc_unreachable (); 638 } 639 else if (e2 && e2->speculative) 640 { 641 cgraph_edge *direct, *indirect; 642 ipa_ref *ref; 643 644 e2->speculative_call_info (direct, indirect, ref); 645 e->count = count; 646 e->frequency = freq; 647 int prob = RDIV (direct->count * REG_BR_PROB_BASE, e->count); 648 e->make_speculative (direct->callee, direct->count, 649 RDIV (freq * prob, REG_BR_PROB_BASE)); 650 } 651 else 652 { 653 e->count = count; 654 e->frequency = freq; 655 } 656 } 657 if (!preserve_body) 658 src->release_body (); 659 inline_update_overall_summary (dst); 660 } 661 /* TODO: if there is no match, we can scale up. */ 662 src->decl = oldsrcdecl; 663 } 664 665 /* Return true if call to DEST is known to be self-recusive call withing FUNC. */ 666 667 bool 668 recursive_call_p (tree func, tree dest) 669 { 670 struct cgraph_node *dest_node = cgraph_node::get_create (dest); 671 struct cgraph_node *cnode = cgraph_node::get_create (func); 672 673 return dest_node->semantically_equivalent_p (cnode); 674 } 675