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