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 "ipa-prop.h"
  59 #include "ipa-inline.h"
  60
  61 /* Debugging function for postorder and inorder code. NOTE is a string
  62    that is printed before the nodes are printed.  ORDER is an array of
  63    cgraph_nodes that has COUNT useful nodes in it.  */
  64
  65 void
  66 ipa_print_order (FILE* out,
  67                  const char * note,
  68                  struct cgraph_node** order,
  69                  int count)
  70 {
  71   int i;
  72   fprintf (out, "\n\n ordered call graph: %s\n", note);
  73
  74   for (i = count - 1; i >= 0; i--)
  75     order[i]->dump (out);
  76   fprintf (out, "\n");
  77   fflush (out);
  78 }
  79
  80
  81 struct searchc_env {
  82   struct cgraph_node **stack;
  83   int stack_size;
  84   struct cgraph_node **result;
  85   int order_pos;
  86   splay_tree nodes_marked_new;
  87   bool reduce;
  88   bool allow_overwritable;
  89   int count;
  90 };
  91
  92 /* This is an implementation of Tarjan's strongly connected region
  93    finder as reprinted in Aho Hopcraft and Ullman's The Design and
  94    Analysis of Computer Programs (1975) pages 192-193.  This version
  95    has been customized for cgraph_nodes.  The env parameter is because
  96    it is recursive and there are no nested functions here.  This
  97    function should only be called from itself or
  98    ipa_reduced_postorder.  ENV is a stack env and would be
  99    unnecessary if C had nested functions.  V is the node to start
 100    searching from.  */
 101
 102 static void
 103 searchc (struct searchc_env* env, struct cgraph_node *v,
 104          bool (*ignore_edge) (struct cgraph_edge *))
 105 {
 106   struct cgraph_edge *edge;
 107   struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux;
 108
 109   /* mark node as old */
 110   v_info->new_node = false;
 111   splay_tree_remove (env->nodes_marked_new, v->uid);
 112
 113   v_info->dfn_number = env->count;
 114   v_info->low_link = env->count;
 115   env->count++;
 116   env->stack[(env->stack_size)++] = v;
 117   v_info->on_stack = true;
 118
 119   for (edge = v->callees; edge; edge = edge->next_callee)
 120     {
 121       struct ipa_dfs_info * w_info;
 122       enum availability avail;
 123       struct cgraph_node *w = edge->callee->ultimate_alias_target (&avail);
 124
 125       if (!w || (ignore_edge && ignore_edge (edge)))
 126         continue;
 127
 128       if (w->aux
 129           && (avail > AVAIL_INTERPOSABLE
 130               || (env->allow_overwritable && avail == AVAIL_INTERPOSABLE)))
 131         {
 132           w_info = (struct ipa_dfs_info *) w->aux;
 133           if (w_info->new_node)
 134             {
 135               searchc (env, w, ignore_edge);
 136               v_info->low_link =
 137                 (v_info->low_link < w_info->low_link) ?
 138                 v_info->low_link : w_info->low_link;
 139             }
 140           else
 141             if ((w_info->dfn_number < v_info->dfn_number)
 142                 && (w_info->on_stack))
 143               v_info->low_link =
 144                 (w_info->dfn_number < v_info->low_link) ?
 145                 w_info->dfn_number : v_info->low_link;
 146         }
 147     }
 148
 149
 150   if (v_info->low_link == v_info->dfn_number)
 151     {
 152       struct cgraph_node *last = NULL;
 153       struct cgraph_node *x;
 154       struct ipa_dfs_info *x_info;
 155       do {
 156         x = env->stack[--(env->stack_size)];
 157         x_info = (struct ipa_dfs_info *) x->aux;
 158         x_info->on_stack = false;
 159         x_info->scc_no = v_info->dfn_number;
 160
 161         if (env->reduce)
 162           {
 163             x_info->next_cycle = last;
 164             last = x;
 165           }
 166         else
 167           env->result[env->order_pos++] = x;
 168       }
 169       while (v != x);
 170       if (env->reduce)
 171         env->result[env->order_pos++] = v;
 172     }
 173 }
 174
 175 /* Topsort the call graph by caller relation.  Put the result in ORDER.
 176
 177    The REDUCE flag is true if you want the cycles reduced to single nodes.
 178    You can use ipa_get_nodes_in_cycle to obtain a vector containing all real
 179    call graph nodes in a reduced node.
 180
 181    Set ALLOW_OVERWRITABLE if nodes with such availability should be included.
 182    IGNORE_EDGE, if non-NULL is a hook that may make some edges insignificant
 183    for the topological sort.   */
 184
 185 int
 186 ipa_reduced_postorder (struct cgraph_node **order,
 187                        bool reduce, bool allow_overwritable,
 188                        bool (*ignore_edge) (struct cgraph_edge *))
 189 {
 190   struct cgraph_node *node;
 191   struct searchc_env env;
 192   splay_tree_node result;
 193   env.stack = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
 194   env.stack_size = 0;
 195   env.result = order;
 196   env.order_pos = 0;
 197   env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
 198   env.count = 1;
 199   env.reduce = reduce;
 200   env.allow_overwritable = allow_overwritable;
 201
 202   FOR_EACH_DEFINED_FUNCTION (node)
 203     {
 204       enum availability avail = node->get_availability ();
 205
 206       if (avail > AVAIL_INTERPOSABLE
 207           || (allow_overwritable
 208               && (avail == AVAIL_INTERPOSABLE)))
 209         {
 210           /* Reuse the info if it is already there.  */
 211           struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->aux;
 212           if (!info)
 213             info = XCNEW (struct ipa_dfs_info);
 214           info->new_node = true;
 215           info->on_stack = false;
 216           info->next_cycle = NULL;
 217           node->aux = info;
 218
 219           splay_tree_insert (env.nodes_marked_new,
 220                              (splay_tree_key)node->uid,
 221                              (splay_tree_value)node);
 222         }
 223       else
 224         node->aux = NULL;
 225     }
 226   result = splay_tree_min (env.nodes_marked_new);
 227   while (result)
 228     {
 229       node = (struct cgraph_node *)result->value;
 230       searchc (&env, node, ignore_edge);
 231       result = splay_tree_min (env.nodes_marked_new);
 232     }
 233   splay_tree_delete (env.nodes_marked_new);
 234   free (env.stack);
 235
 236   return env.order_pos;
 237 }
 238
 239 /* Deallocate all ipa_dfs_info structures pointed to by the aux pointer of call
 240    graph nodes.  */
 241
 242 void
 243 ipa_free_postorder_info (void)
 244 {
 245   struct cgraph_node *node;
 246   FOR_EACH_DEFINED_FUNCTION (node)
 247     {
 248       /* Get rid of the aux information.  */
 249       if (node->aux)
 250         {
 251           free (node->aux);
 252           node->aux = NULL;
 253         }
 254     }
 255 }
 256
 257 /* Get the set of nodes for the cycle in the reduced call graph starting
 258    from NODE.  */
 259
 260 vec<cgraph_node *>
 261 ipa_get_nodes_in_cycle (struct cgraph_node *node)
 262 {
 263   vec<cgraph_node *> v = vNULL;
 264   struct ipa_dfs_info *node_dfs_info;
 265   while (node)
 266     {
 267       v.safe_push (node);
 268       node_dfs_info = (struct ipa_dfs_info *) node->aux;
 269       node = node_dfs_info->next_cycle;
 270     }
 271   return v;
 272 }
 273
 274 /* Return true iff the CS is an edge within a strongly connected component as
 275    computed by ipa_reduced_postorder.  */
 276
 277 bool
 278 ipa_edge_within_scc (struct cgraph_edge *cs)
 279 {
 280   struct ipa_dfs_info *caller_dfs = (struct ipa_dfs_info *) cs->caller->aux;
 281   struct ipa_dfs_info *callee_dfs;
 282   struct cgraph_node *callee = cs->callee->function_symbol ();
 283
 284   callee_dfs = (struct ipa_dfs_info *) callee->aux;
 285   return (caller_dfs
 286           && callee_dfs
 287           && caller_dfs->scc_no == callee_dfs->scc_no);
 288 }
 289
 290 struct postorder_stack
 291 {
 292   struct cgraph_node *node;
 293   struct cgraph_edge *edge;
 294   int ref;
 295 };
 296
 297 /* Fill array order with all nodes with output flag set in the reverse
 298    topological order.  Return the number of elements in the array.
 299    FIXME: While walking, consider aliases, too.  */
 300
 301 int
 302 ipa_reverse_postorder (struct cgraph_node **order)
 303 {
 304   struct cgraph_node *node, *node2;
 305   int stack_size = 0;
 306   int order_pos = 0;
 307   struct cgraph_edge *edge;
 308   int pass;
 309   struct ipa_ref *ref = NULL;
 310
 311   struct postorder_stack *stack =
 312     XCNEWVEC (struct postorder_stack, symtab->cgraph_count);
 313
 314   /* We have to deal with cycles nicely, so use a depth first traversal
 315      output algorithm.  Ignore the fact that some functions won't need
 316      to be output and put them into order as well, so we get dependencies
 317      right through inline functions.  */
 318   FOR_EACH_FUNCTION (node)
 319     node->aux = NULL;
 320   for (pass = 0; pass < 2; pass++)
 321     FOR_EACH_FUNCTION (node)
 322       if (!node->aux
 323           && (pass
 324               || (!node->address_taken
 325                   && !node->global.inlined_to
 326                   && !node->alias && !node->thunk.thunk_p
 327                   && !node->only_called_directly_p ())))
 328         {
 329           stack_size = 0;
 330           stack[stack_size].node = node;
 331           stack[stack_size].edge = node->callers;
 332           stack[stack_size].ref = 0;
 333           node->aux = (void *)(size_t)1;
 334           while (stack_size >= 0)
 335             {
 336               while (true)
 337                 {
 338                   node2 = NULL;
 339                   while (stack[stack_size].edge && !node2)
 340                     {
 341                       edge = stack[stack_size].edge;
 342                       node2 = edge->caller;
 343                       stack[stack_size].edge = edge->next_caller;
 344                       /* Break possible cycles involving always-inline
 345                          functions by ignoring edges from always-inline
 346                          functions to non-always-inline functions.  */
 347                       if (DECL_DISREGARD_INLINE_LIMITS (edge->caller->decl)
 348                           && !DECL_DISREGARD_INLINE_LIMITS
 349                             (edge->callee->function_symbol ()->decl))
 350                         node2 = NULL;
 351                     }
 352                   for (; stack[stack_size].node->iterate_referring (
 353                                                        stack[stack_size].ref,
 354                                                        ref) && !node2;
 355                        stack[stack_size].ref++)
 356                     {
 357                       if (ref->use == IPA_REF_ALIAS)
 358                         node2 = dyn_cast <cgraph_node *> (ref->referring);
 359                     }
 360                   if (!node2)
 361                     break;
 362                   if (!node2->aux)
 363                     {
 364                       stack[++stack_size].node = node2;
 365                       stack[stack_size].edge = node2->callers;
 366                       stack[stack_size].ref = 0;
 367                       node2->aux = (void *)(size_t)1;
 368                     }
 369                 }
 370               order[order_pos++] = stack[stack_size--].node;
 371             }
 372         }
 373   free (stack);
 374   FOR_EACH_FUNCTION (node)
 375     node->aux = NULL;
 376   return order_pos;
 377 }
 378
 379
 380
 381 /* Given a memory reference T, will return the variable at the bottom
 382    of the access.  Unlike get_base_address, this will recurse through
 383    INDIRECT_REFS.  */
 384
 385 tree
 386 get_base_var (tree t)
 387 {
 388   while (!SSA_VAR_P (t)
 389          && (!CONSTANT_CLASS_P (t))
 390          && TREE_CODE (t) != LABEL_DECL
 391          && TREE_CODE (t) != FUNCTION_DECL
 392          && TREE_CODE (t) != CONST_DECL
 393          && TREE_CODE (t) != CONSTRUCTOR)
 394     {
 395       t = TREE_OPERAND (t, 0);
 396     }
 397   return t;
 398 }
 399
 400
 401 /* SRC and DST are going to be merged.  Take SRC's profile and merge it into
 402    DST so it is not going to be lost.  Destroy SRC's body on the way.  */
 403
 404 void
 405 ipa_merge_profiles (struct cgraph_node *dst,
 406                     struct cgraph_node *src)
 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 (src->name ()), src->order,
 431                xstrdup (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       void **slot;
 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       slot = htab_find_slot (src->lto_file_data->function_decl_states,
 449                              &temp, NO_INSERT);
 450       state = (lto_in_decl_state *)*slot;
 451       htab_clear_slot (src->lto_file_data->function_decl_states, 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 = htab_find_slot (src->lto_file_data->function_decl_states,
 465                              state, INSERT);
 466       gcc_assert (!*slot);
 467       *slot = state;
 468     }
 469   src->get_body ();
 470   dst->get_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;
 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           gcc_assert (!e->speculative);
 558           e->count = gimple_bb (e->call_stmt)->count;
 559           e->frequency = compute_call_stmt_bb_frequency
 560                              (dst->decl,
 561                               gimple_bb (e->call_stmt));
 562         }
 563       for (e = dst->indirect_calls; e; e = e->next_callee)
 564         {
 565           gcc_assert (!e->speculative);
 566           e->count = gimple_bb (e->call_stmt)->count;
 567           e->frequency = compute_call_stmt_bb_frequency
 568                              (dst->decl,
 569                               gimple_bb (e->call_stmt));
 570         }
 571       src->release_body ();
 572       inline_update_overall_summary (dst);
 573     }
 574   /* TODO: if there is no match, we can scale up.  */
 575   src->decl = oldsrcdecl;
 576 }
 577
 578 /* Return true if call to DEST is known to be self-recusive call withing FUNC.   */
 579
 580 bool
 581 recursive_call_p (tree func, tree dest)
 582 {
 583   struct cgraph_node *dest_node = cgraph_node::get_create (dest);
 584   struct cgraph_node *cnode = cgraph_node::get_create (func);
 585
 586   return dest_node->semantically_equivalent_p (cnode);
 587 }