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