gcc/ipa-utils.c

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