gcc/ipa-utils.c

   1 /* Utilities for ipa analysis.
   2    Copyright (C) 2005-2013 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-ssa.h"
  27 #include "tree-inline.h"
  28 #include "dumpfile.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 "flags.h"
  38 #include "diagnostic.h"
  39 #include "langhooks.h"
  40 #include "lto-streamer.h"
  41 #include "ipa-inline.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 \f
  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->symbol.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->symbol.aux
 111           && (avail > AVAIL_OVERWRITABLE
 112               || (env->allow_overwritable && avail == AVAIL_OVERWRITABLE)))
 113         {
 114           w_info = (struct ipa_dfs_info *) w->symbol.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->symbol.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.
 160    You can use ipa_get_nodes_in_cycle to obtain a vector containing all real
 161    call graph nodes in a reduced node.
 162
 163    Set ALLOW_OVERWRITABLE if nodes with such availability should be included.
 164    IGNORE_EDGE, if non-NULL is a hook that may make some edges insignificant
 165    for the topological sort.   */
 166
 167 int
 168 ipa_reduced_postorder (struct cgraph_node **order,
 169                        bool reduce, bool allow_overwritable,
 170                        bool (*ignore_edge) (struct cgraph_edge *))
 171 {
 172   struct cgraph_node *node;
 173   struct searchc_env env;
 174   splay_tree_node result;
 175   env.stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
 176   env.stack_size = 0;
 177   env.result = order;
 178   env.order_pos = 0;
 179   env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
 180   env.count = 1;
 181   env.reduce = reduce;
 182   env.allow_overwritable = allow_overwritable;
 183
 184   FOR_EACH_DEFINED_FUNCTION (node)
 185     {
 186       enum availability avail = cgraph_function_body_availability (node);
 187
 188       if (avail > AVAIL_OVERWRITABLE
 189           || (allow_overwritable
 190               && (avail == AVAIL_OVERWRITABLE)))
 191         {
 192           /* Reuse the info if it is already there.  */
 193           struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->symbol.aux;
 194           if (!info)
 195             info = XCNEW (struct ipa_dfs_info);
 196           info->new_node = true;
 197           info->on_stack = false;
 198           info->next_cycle = NULL;
 199           node->symbol.aux = info;
 200
 201           splay_tree_insert (env.nodes_marked_new,
 202                              (splay_tree_key)node->uid,
 203                              (splay_tree_value)node);
 204         }
 205       else
 206         node->symbol.aux = NULL;
 207     }
 208   result = splay_tree_min (env.nodes_marked_new);
 209   while (result)
 210     {
 211       node = (struct cgraph_node *)result->value;
 212       searchc (&env, node, ignore_edge);
 213       result = splay_tree_min (env.nodes_marked_new);
 214     }
 215   splay_tree_delete (env.nodes_marked_new);
 216   free (env.stack);
 217
 218   return env.order_pos;
 219 }
 220
 221 /* Deallocate all ipa_dfs_info structures pointed to by the aux pointer of call
 222    graph nodes.  */
 223
 224 void
 225 ipa_free_postorder_info (void)
 226 {
 227   struct cgraph_node *node;
 228   FOR_EACH_DEFINED_FUNCTION (node)
 229     {
 230       /* Get rid of the aux information.  */
 231       if (node->symbol.aux)
 232         {
 233           free (node->symbol.aux);
 234           node->symbol.aux = NULL;
 235         }
 236     }
 237 }
 238
 239 /* Get the set of nodes for the cycle in the reduced call graph starting
 240    from NODE.  */
 241
 242 vec<cgraph_node_ptr>
 243 ipa_get_nodes_in_cycle (struct cgraph_node *node)
 244 {
 245   vec<cgraph_node_ptr> v = vNULL;
 246   struct ipa_dfs_info *node_dfs_info;
 247   while (node)
 248     {
 249       v.safe_push (node);
 250       node_dfs_info = (struct ipa_dfs_info *) node->symbol.aux;
 251       node = node_dfs_info->next_cycle;
 252     }
 253   return v;
 254 }
 255
 256 struct postorder_stack
 257 {
 258   struct cgraph_node *node;
 259   struct cgraph_edge *edge;
 260   int ref;
 261 };
 262
 263 /* Fill array order with all nodes with output flag set in the reverse
 264    topological order.  Return the number of elements in the array.
 265    FIXME: While walking, consider aliases, too.  */
 266
 267 int
 268 ipa_reverse_postorder (struct cgraph_node **order)
 269 {
 270   struct cgraph_node *node, *node2;
 271   int stack_size = 0;
 272   int order_pos = 0;
 273   struct cgraph_edge *edge;
 274   int pass;
 275   struct ipa_ref *ref;
 276
 277   struct postorder_stack *stack =
 278     XCNEWVEC (struct postorder_stack, cgraph_n_nodes);
 279
 280   /* We have to deal with cycles nicely, so use a depth first traversal
 281      output algorithm.  Ignore the fact that some functions won't need
 282      to be output and put them into order as well, so we get dependencies
 283      right through inline functions.  */
 284   FOR_EACH_FUNCTION (node)
 285     node->symbol.aux = NULL;
 286   for (pass = 0; pass < 2; pass++)
 287     FOR_EACH_FUNCTION (node)
 288       if (!node->symbol.aux
 289           && (pass
 290               || (!node->symbol.address_taken
 291                   && !node->global.inlined_to
 292                   && !node->symbol.alias && !node->thunk.thunk_p
 293                   && !cgraph_only_called_directly_p (node))))
 294         {
 295           stack_size = 0;
 296           stack[stack_size].node = node;
 297           stack[stack_size].edge = node->callers;
 298           stack[stack_size].ref = 0;
 299           node->symbol.aux = (void *)(size_t)1;
 300           while (stack_size >= 0)
 301             {
 302               while (true)
 303                 {
 304                   node2 = NULL;
 305                   while (stack[stack_size].edge && !node2)
 306                     {
 307                       edge = stack[stack_size].edge;
 308                       node2 = edge->caller;
 309                       stack[stack_size].edge = edge->next_caller;
 310                       /* Break possible cycles involving always-inline
 311                          functions by ignoring edges from always-inline
 312                          functions to non-always-inline functions.  */
 313                       if (DECL_DISREGARD_INLINE_LIMITS (edge->caller->symbol.decl)
 314                           && !DECL_DISREGARD_INLINE_LIMITS
 315                             (cgraph_function_node (edge->callee, NULL)->symbol.decl))
 316                         node2 = NULL;
 317                     }
 318                   for (;ipa_ref_list_referring_iterate (&stack[stack_size].node->symbol.ref_list,
 319                                                        stack[stack_size].ref,
 320                                                        ref) && !node2;
 321                        stack[stack_size].ref++)
 322                     {
 323                       if (ref->use == IPA_REF_ALIAS)
 324                         node2 = ipa_ref_referring_node (ref);
 325                     }
 326                   if (!node2)
 327                     break;
 328                   if (!node2->symbol.aux)
 329                     {
 330                       stack[++stack_size].node = node2;
 331                       stack[stack_size].edge = node2->callers;
 332                       stack[stack_size].ref = 0;
 333                       node2->symbol.aux = (void *)(size_t)1;
 334                     }
 335                 }
 336               order[order_pos++] = stack[stack_size--].node;
 337             }
 338         }
 339   free (stack);
 340   FOR_EACH_FUNCTION (node)
 341     node->symbol.aux = NULL;
 342   return order_pos;
 343 }
 344
 345
 346
 347 /* Given a memory reference T, will return the variable at the bottom
 348    of the access.  Unlike get_base_address, this will recurse through
 349    INDIRECT_REFS.  */
 350
 351 tree
 352 get_base_var (tree t)
 353 {
 354   while (!SSA_VAR_P (t)
 355          && (!CONSTANT_CLASS_P (t))
 356          && TREE_CODE (t) != LABEL_DECL
 357          && TREE_CODE (t) != FUNCTION_DECL
 358          && TREE_CODE (t) != CONST_DECL
 359          && TREE_CODE (t) != CONSTRUCTOR)
 360     {
 361       t = TREE_OPERAND (t, 0);
 362     }
 363   return t;
 364 }
 365
 366
 367 /* Create a new cgraph node set.  */
 368
 369 cgraph_node_set
 370 cgraph_node_set_new (void)
 371 {
 372   cgraph_node_set new_node_set;
 373
 374   new_node_set = XCNEW (struct cgraph_node_set_def);
 375   new_node_set->map = pointer_map_create ();
 376   new_node_set->nodes.create (0);
 377   return new_node_set;
 378 }
 379
 380
 381 /* Add cgraph_node NODE to cgraph_node_set SET.  */
 382
 383 void
 384 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
 385 {
 386   void **slot;
 387
 388   slot = pointer_map_insert (set->map, node);
 389
 390   if (*slot)
 391     {
 392       int index = (size_t) *slot - 1;
 393       gcc_checking_assert ((set->nodes[index]
 394                            == node));
 395       return;
 396     }
 397
 398   *slot = (void *)(size_t) (set->nodes.length () + 1);
 399
 400   /* Insert into node vector.  */
 401   set->nodes.safe_push (node);
 402 }
 403
 404
 405 /* Remove cgraph_node NODE from cgraph_node_set SET.  */
 406
 407 void
 408 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
 409 {
 410   void **slot, **last_slot;
 411   int index;
 412   struct cgraph_node *last_node;
 413
 414   slot = pointer_map_contains (set->map, node);
 415   if (slot == NULL || !*slot)
 416     return;
 417
 418   index = (size_t) *slot - 1;
 419   gcc_checking_assert (set->nodes[index]
 420                        == node);
 421
 422   /* Remove from vector. We do this by swapping node with the last element
 423      of the vector.  */
 424   last_node = set->nodes.pop ();
 425   if (last_node != node)
 426     {
 427       last_slot = pointer_map_contains (set->map, last_node);
 428       gcc_checking_assert (last_slot && *last_slot);
 429       *last_slot = (void *)(size_t) (index + 1);
 430
 431       /* Move the last element to the original spot of NODE.  */
 432       set->nodes[index] = last_node;
 433     }
 434
 435   /* Remove element from hash table.  */
 436   *slot = NULL;
 437 }
 438
 439
 440 /* Find NODE in SET and return an iterator to it if found.  A null iterator
 441    is returned if NODE is not in SET.  */
 442
 443 cgraph_node_set_iterator
 444 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
 445 {
 446   void **slot;
 447   cgraph_node_set_iterator csi;
 448
 449   slot = pointer_map_contains (set->map, node);
 450   if (slot == NULL || !*slot)
 451     csi.index = (unsigned) ~0;
 452   else
 453     csi.index = (size_t)*slot - 1;
 454   csi.set = set;
 455
 456   return csi;
 457 }
 458
 459
 460 /* Dump content of SET to file F.  */
 461
 462 void
 463 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
 464 {
 465   cgraph_node_set_iterator iter;
 466
 467   for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
 468     {
 469       struct cgraph_node *node = csi_node (iter);
 470       fprintf (f, " %s/%i", cgraph_node_name (node), node->symbol.order);
 471     }
 472   fprintf (f, "\n");
 473 }
 474
 475
 476 /* Dump content of SET to stderr.  */
 477
 478 DEBUG_FUNCTION void
 479 debug_cgraph_node_set (cgraph_node_set set)
 480 {
 481   dump_cgraph_node_set (stderr, set);
 482 }
 483
 484
 485 /* Free varpool node set.  */
 486
 487 void
 488 free_cgraph_node_set (cgraph_node_set set)
 489 {
 490   set->nodes.release ();
 491   pointer_map_destroy (set->map);
 492   free (set);
 493 }
 494
 495
 496 /* Create a new varpool node set.  */
 497
 498 varpool_node_set
 499 varpool_node_set_new (void)
 500 {
 501   varpool_node_set new_node_set;
 502
 503   new_node_set = XCNEW (struct varpool_node_set_def);
 504   new_node_set->map = pointer_map_create ();
 505   new_node_set->nodes.create (0);
 506   return new_node_set;
 507 }
 508
 509
 510 /* Add varpool_node NODE to varpool_node_set SET.  */
 511
 512 void
 513 varpool_node_set_add (varpool_node_set set, struct varpool_node *node)
 514 {
 515   void **slot;
 516
 517   slot = pointer_map_insert (set->map, node);
 518
 519   if (*slot)
 520     {
 521       int index = (size_t) *slot - 1;
 522       gcc_checking_assert ((set->nodes[index]
 523                            == node));
 524       return;
 525     }
 526
 527   *slot = (void *)(size_t) (set->nodes.length () + 1);
 528
 529   /* Insert into node vector.  */
 530   set->nodes.safe_push (node);
 531 }
 532
 533
 534 /* Remove varpool_node NODE from varpool_node_set SET.  */
 535
 536 void
 537 varpool_node_set_remove (varpool_node_set set, struct varpool_node *node)
 538 {
 539   void **slot, **last_slot;
 540   int index;
 541   struct varpool_node *last_node;
 542
 543   slot = pointer_map_contains (set->map, node);
 544   if (slot == NULL || !*slot)
 545     return;
 546
 547   index = (size_t) *slot - 1;
 548   gcc_checking_assert (set->nodes[index]
 549                        == node);
 550
 551   /* Remove from vector. We do this by swapping node with the last element
 552      of the vector.  */
 553   last_node = set->nodes.pop ();
 554   if (last_node != node)
 555     {
 556       last_slot = pointer_map_contains (set->map, last_node);
 557       gcc_checking_assert (last_slot && *last_slot);
 558       *last_slot = (void *)(size_t) (index + 1);
 559
 560       /* Move the last element to the original spot of NODE.  */
 561       set->nodes[index] = last_node;
 562     }
 563
 564   /* Remove element from hash table.  */
 565   *slot = NULL;
 566 }
 567
 568
 569 /* Find NODE in SET and return an iterator to it if found.  A null iterator
 570    is returned if NODE is not in SET.  */
 571
 572 varpool_node_set_iterator
 573 varpool_node_set_find (varpool_node_set set, struct varpool_node *node)
 574 {
 575   void **slot;
 576   varpool_node_set_iterator vsi;
 577
 578   slot = pointer_map_contains (set->map, node);
 579   if (slot == NULL || !*slot)
 580     vsi.index = (unsigned) ~0;
 581   else
 582     vsi.index = (size_t)*slot - 1;
 583   vsi.set = set;
 584
 585   return vsi;
 586 }
 587
 588
 589 /* Dump content of SET to file F.  */
 590
 591 void
 592 dump_varpool_node_set (FILE *f, varpool_node_set set)
 593 {
 594   varpool_node_set_iterator iter;
 595
 596   for (iter = vsi_start (set); !vsi_end_p (iter); vsi_next (&iter))
 597     {
 598       struct varpool_node *node = vsi_node (iter);
 599       fprintf (f, " %s", varpool_node_name (node));
 600     }
 601   fprintf (f, "\n");
 602 }
 603
 604
 605 /* Free varpool node set.  */
 606
 607 void
 608 free_varpool_node_set (varpool_node_set set)
 609 {
 610   set->nodes.release ();
 611   pointer_map_destroy (set->map);
 612   free (set);
 613 }
 614
 615
 616 /* Dump content of SET to stderr.  */
 617
 618 DEBUG_FUNCTION void
 619 debug_varpool_node_set (varpool_node_set set)
 620 {
 621   dump_varpool_node_set (stderr, set);
 622 }
 623
 624
 625 /* SRC and DST are going to be merged.  Take SRC's profile and merge it into
 626    DST so it is not going to be lost.  Destroy SRC's body on the way.  */
 627
 628 void
 629 ipa_merge_profiles (struct cgraph_node *dst,
 630                     struct cgraph_node *src)
 631 {
 632   tree oldsrcdecl = src->symbol.decl;
 633   struct function *srccfun, *dstcfun;
 634   bool match = true;
 635
 636   if (!src->symbol.definition
 637       || !dst->symbol.definition)
 638     return;
 639   if (src->frequency < dst->frequency)
 640     src->frequency = dst->frequency;
 641   if (!dst->count)
 642     return;
 643   if (cgraph_dump_file)
 644     {
 645       fprintf (cgraph_dump_file, "Merging profiles of %s/%i to %s/%i\n",
 646                xstrdup (cgraph_node_name (src)), src->symbol.order,
 647                xstrdup (cgraph_node_name (dst)), dst->symbol.order);
 648     }
 649   dst->count += src->count;
 650
 651   /* This is ugly.  We need to get both function bodies into memory.
 652      If declaration is merged, we need to duplicate it to be able
 653      to load body that is being replaced.  This makes symbol table
 654      temporarily inconsistent.  */
 655   if (src->symbol.decl == dst->symbol.decl)
 656     {
 657       void **slot;
 658       struct lto_in_decl_state temp;
 659       struct lto_in_decl_state *state;
 660
 661       /* We are going to move the decl, we want to remove its file decl data.
 662          and link these with the new decl. */
 663       temp.fn_decl = src->symbol.decl;
 664       slot = htab_find_slot (src->symbol.lto_file_data->function_decl_states,
 665                              &temp, NO_INSERT);
 666       state = (lto_in_decl_state *)*slot;
 667       htab_clear_slot (src->symbol.lto_file_data->function_decl_states, slot);
 668       gcc_assert (state);
 669
 670       /* Duplicate the decl and be sure it does not link into body of DST.  */
 671       src->symbol.decl = copy_node (src->symbol.decl);
 672       DECL_STRUCT_FUNCTION (src->symbol.decl) = NULL;
 673       DECL_ARGUMENTS (src->symbol.decl) = NULL;
 674       DECL_INITIAL (src->symbol.decl) = NULL;
 675       DECL_RESULT (src->symbol.decl) = NULL;
 676
 677       /* Associate the decl state with new declaration, so LTO streamer
 678          can look it up.  */
 679       state->fn_decl = src->symbol.decl;
 680       slot = htab_find_slot (src->symbol.lto_file_data->function_decl_states,
 681                              state, INSERT);
 682       gcc_assert (!*slot);
 683       *slot = state;
 684     }
 685   cgraph_get_body (src);
 686   cgraph_get_body (dst);
 687   srccfun = DECL_STRUCT_FUNCTION (src->symbol.decl);
 688   dstcfun = DECL_STRUCT_FUNCTION (dst->symbol.decl);
 689   if (n_basic_blocks_for_function (srccfun)
 690       != n_basic_blocks_for_function (dstcfun))
 691     {
 692       if (cgraph_dump_file)
 693         fprintf (cgraph_dump_file,
 694                  "Giving up; number of basic block mismatch.\n");
 695       match = false;
 696     }
 697   else if (last_basic_block_for_function (srccfun)
 698            != last_basic_block_for_function (dstcfun))
 699     {
 700       if (cgraph_dump_file)
 701         fprintf (cgraph_dump_file,
 702                  "Giving up; last block mismatch.\n");
 703       match = false;
 704     }
 705   else
 706     {
 707       basic_block srcbb, dstbb;
 708
 709       FOR_ALL_BB_FN (srcbb, srccfun)
 710         {
 711           unsigned int i;
 712
 713           dstbb = BASIC_BLOCK_FOR_FUNCTION (dstcfun, srcbb->index);
 714           if (dstbb == NULL)
 715             {
 716               if (cgraph_dump_file)
 717                 fprintf (cgraph_dump_file,
 718                          "No matching block for bb %i.\n",
 719                          srcbb->index);
 720               match = false;
 721               break;
 722             }
 723           if (EDGE_COUNT (srcbb->succs) != EDGE_COUNT (dstbb->succs))
 724             {
 725               if (cgraph_dump_file)
 726                 fprintf (cgraph_dump_file,
 727                          "Edge count mistmatch for bb %i.\n",
 728                          srcbb->index);
 729               match = false;
 730               break;
 731             }
 732           for (i = 0; i < EDGE_COUNT (srcbb->succs); i++)
 733             {
 734               edge srce = EDGE_SUCC (srcbb, i);
 735               edge dste = EDGE_SUCC (dstbb, i);
 736               if (srce->dest->index != dste->dest->index)
 737                 {
 738                   if (cgraph_dump_file)
 739                     fprintf (cgraph_dump_file,
 740                              "Succ edge mistmatch for bb %i.\n",
 741                              srce->dest->index);
 742                   match = false;
 743                   break;
 744                 }
 745             }
 746         }
 747     }
 748   if (match)
 749     {
 750       struct cgraph_edge *e;
 751       basic_block srcbb, dstbb;
 752
 753       /* TODO: merge also statement histograms.  */
 754       FOR_ALL_BB_FN (srcbb, srccfun)
 755         {
 756           unsigned int i;
 757
 758           dstbb = BASIC_BLOCK_FOR_FUNCTION (dstcfun, srcbb->index);
 759           dstbb->count += srcbb->count;
 760           for (i = 0; i < EDGE_COUNT (srcbb->succs); i++)
 761             {
 762               edge srce = EDGE_SUCC (srcbb, i);
 763               edge dste = EDGE_SUCC (dstbb, i);
 764               dste->count += srce->count;
 765             }
 766         }
 767       push_cfun (dstcfun);
 768       counts_to_freqs ();
 769       compute_function_frequency ();
 770       pop_cfun ();
 771       for (e = dst->callees; e; e = e->next_callee)
 772         {
 773           gcc_assert (!e->speculative);
 774           e->count = gimple_bb (e->call_stmt)->count;
 775           e->frequency = compute_call_stmt_bb_frequency
 776                              (dst->symbol.decl,
 777                               gimple_bb (e->call_stmt));
 778         }
 779       for (e = dst->indirect_calls; e; e = e->next_callee)
 780         {
 781           gcc_assert (!e->speculative);
 782           e->count = gimple_bb (e->call_stmt)->count;
 783           e->frequency = compute_call_stmt_bb_frequency
 784                              (dst->symbol.decl,
 785                               gimple_bb (e->call_stmt));
 786         }
 787       cgraph_release_function_body (src);
 788       inline_update_overall_summary (dst);
 789     }
 790   /* TODO: if there is no match, we can scale up.  */
 791   src->symbol.decl = oldsrcdecl;
 792 }
 793
 794 /* Return true if call to DEST is known to be self-recusive call withing FUNC.   */
 795
 796 bool
 797 recursive_call_p (tree func, tree dest)
 798 {
 799   struct cgraph_node *dest_node = cgraph_get_create_node (dest);
 800   struct cgraph_node *cnode = cgraph_get_create_node (func);
 801
 802   return symtab_semantically_equivalent_p ((symtab_node)dest_node,
 803                                            (symtab_node)cnode);
 804 }