gcc/ipa-utils.c

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