contrib/gcc-5.0/gcc/ipa-reference.c

   1 /* Callgraph based analysis of static variables.
   2    Copyright (C) 2004-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 /* This file gathers information about how variables whose scope is
  22    confined to the compilation unit are used.
  23
  24    The transitive call site specific clobber effects are computed
  25    for the variables whose scope is contained within this compilation
  26    unit.
  27
  28    First each function and static variable initialization is analyzed
  29    to determine which local static variables are either read, written,
  30    or have their address taken.  Any local static that has its address
  31    taken is removed from consideration.  Once the local read and
  32    writes are determined, a transitive closure of this information is
  33    performed over the call graph to determine the worst case set of
  34    side effects of each call.  In later parts of the compiler, these
  35    local and global sets are examined to make the call clobbering less
  36    traumatic, promote some statics to registers, and improve aliasing
  37    information.  */
  38
  39 #include "config.h"
  40 #include "system.h"
  41 #include "coretypes.h"
  42 #include "tm.h"
  43 #include "hash-set.h"
  44 #include "machmode.h"
  45 #include "vec.h"
  46 #include "double-int.h"
  47 #include "input.h"
  48 #include "alias.h"
  49 #include "symtab.h"
  50 #include "options.h"
  51 #include "wide-int.h"
  52 #include "inchash.h"
  53 #include "tree.h"
  54 #include "fold-const.h"
  55 #include "calls.h"
  56 #include "predict.h"
  57 #include "hard-reg-set.h"
  58 #include "input.h"
  59 #include "function.h"
  60 #include "basic-block.h"
  61 #include "tree-ssa-alias.h"
  62 #include "internal-fn.h"
  63 #include "gimple-expr.h"
  64 #include "is-a.h"
  65 #include "gimple.h"
  66 #include "tree-inline.h"
  67 #include "tree-pass.h"
  68 #include "splay-tree.h"
  69 #include "hash-map.h"
  70 #include "plugin-api.h"
  71 #include "ipa-ref.h"
  72 #include "cgraph.h"
  73 #include "ipa-utils.h"
  74 #include "bitmap.h"
  75 #include "ipa-reference.h"
  76 #include "flags.h"
  77 #include "diagnostic.h"
  78 #include "data-streamer.h"
  79 #include "lto-streamer.h"
  80
  81 static void remove_node_data (struct cgraph_node *node,
  82                               void *data ATTRIBUTE_UNUSED);
  83 static void duplicate_node_data (struct cgraph_node *src,
  84                                  struct cgraph_node *dst,
  85                                  void *data ATTRIBUTE_UNUSED);
  86
  87 /* The static variables defined within the compilation unit that are
  88    loaded or stored directly by function that owns this structure.  */
  89
  90 struct ipa_reference_local_vars_info_d
  91 {
  92   bitmap statics_read;
  93   bitmap statics_written;
  94 };
  95
  96 /* Statics that are read and written by some set of functions. The
  97    local ones are based on the loads and stores local to the function.
  98    The global ones are based on the local info as well as the
  99    transitive closure of the functions that are called. */
 100
 101 struct ipa_reference_global_vars_info_d
 102 {
 103   bitmap statics_read;
 104   bitmap statics_written;
 105 };
 106
 107 /* Information we save about every function after ipa-reference is completed.  */
 108
 109 struct ipa_reference_optimization_summary_d
 110 {
 111   bitmap statics_not_read;
 112   bitmap statics_not_written;
 113 };
 114
 115 typedef struct ipa_reference_local_vars_info_d *ipa_reference_local_vars_info_t;
 116 typedef struct ipa_reference_global_vars_info_d *ipa_reference_global_vars_info_t;
 117 typedef struct ipa_reference_optimization_summary_d *ipa_reference_optimization_summary_t;
 118
 119 struct ipa_reference_vars_info_d
 120 {
 121   struct ipa_reference_local_vars_info_d local;
 122   struct ipa_reference_global_vars_info_d global;
 123 };
 124
 125 typedef struct ipa_reference_vars_info_d *ipa_reference_vars_info_t;
 126
 127 /* This splay tree contains all of the static variables that are
 128    being considered by the compilation level alias analysis.  */
 129 static splay_tree reference_vars_to_consider;
 130
 131 /* Set of all interesting module statics.  A bit is set for every module
 132    static we are considering.  This is added to the local info when asm
 133    code is found that clobbers all memory.  */
 134 static bitmap all_module_statics;
 135 /* Set of all statics that should be ignored becuase they are touched by
 136    -fno-ipa-reference code.  */
 137 static bitmap ignore_module_statics;
 138
 139 /* Obstack holding bitmaps of local analysis (live from analysis to
 140    propagation)  */
 141 static bitmap_obstack local_info_obstack;
 142 /* Obstack holding global analysis live forever.  */
 143 static bitmap_obstack optimization_summary_obstack;
 144
 145 /* Holders of ipa cgraph hooks: */
 146 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
 147 static struct cgraph_node_hook_list *node_removal_hook_holder;
 148
 149 /* Vector where the reference var infos are actually stored.
 150    Indexed by UID of call graph nodes.  */
 151 static vec<ipa_reference_vars_info_t> ipa_reference_vars_vector;
 152
 153 static vec<ipa_reference_optimization_summary_t> ipa_reference_opt_sum_vector;
 154
 155 /* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
 156 static inline ipa_reference_vars_info_t
 157 get_reference_vars_info (struct cgraph_node *node)
 158 {
 159   if (!ipa_reference_vars_vector.exists ()
 160       || ipa_reference_vars_vector.length () <= (unsigned int) node->uid)
 161     return NULL;
 162   return ipa_reference_vars_vector[node->uid];
 163 }
 164
 165 /* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
 166 static inline ipa_reference_optimization_summary_t
 167 get_reference_optimization_summary (struct cgraph_node *node)
 168 {
 169   if (!ipa_reference_opt_sum_vector.exists ()
 170       || (ipa_reference_opt_sum_vector.length () <= (unsigned int) node->uid))
 171     return NULL;
 172   return ipa_reference_opt_sum_vector[node->uid];
 173 }
 174
 175 /* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
 176 static inline void
 177 set_reference_vars_info (struct cgraph_node *node,
 178                          ipa_reference_vars_info_t info)
 179 {
 180   if (!ipa_reference_vars_vector.exists ()
 181       || ipa_reference_vars_vector.length () <= (unsigned int) node->uid)
 182     ipa_reference_vars_vector.safe_grow_cleared (node->uid + 1);
 183   ipa_reference_vars_vector[node->uid] = info;
 184 }
 185
 186 /* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
 187 static inline void
 188 set_reference_optimization_summary (struct cgraph_node *node,
 189                                     ipa_reference_optimization_summary_t info)
 190 {
 191   if (!ipa_reference_opt_sum_vector.exists ()
 192       || (ipa_reference_opt_sum_vector.length () <= (unsigned int) node->uid))
 193     ipa_reference_opt_sum_vector.safe_grow_cleared (node->uid + 1);
 194   ipa_reference_opt_sum_vector[node->uid] = info;
 195 }
 196
 197 /* Return a bitmap indexed by DECL_UID for the static variables that
 198    are *not* read during the execution of the function FN.  Returns
 199    NULL if no data is available.  */
 200
 201 bitmap
 202 ipa_reference_get_not_read_global (struct cgraph_node *fn)
 203 {
 204   if (!opt_for_fn (fn->decl, flag_ipa_reference)
 205       || !opt_for_fn (current_function_decl, flag_ipa_reference))
 206     return NULL;
 207   ipa_reference_optimization_summary_t info =
 208     get_reference_optimization_summary (fn->function_symbol (NULL));
 209   if (info)
 210     return info->statics_not_read;
 211   else if (flags_from_decl_or_type (fn->decl) & ECF_LEAF)
 212     return all_module_statics;
 213   else
 214     return NULL;
 215 }
 216
 217 /* Return a bitmap indexed by DECL_UID for the static variables that
 218    are *not* written during the execution of the function FN.  Note
 219    that variables written may or may not be read during the function
 220    call.  Returns NULL if no data is available.  */
 221
 222 bitmap
 223 ipa_reference_get_not_written_global (struct cgraph_node *fn)
 224 {
 225   if (!opt_for_fn (fn->decl, flag_ipa_reference)
 226       || !opt_for_fn (current_function_decl, flag_ipa_reference))
 227     return NULL;
 228   ipa_reference_optimization_summary_t info =
 229     get_reference_optimization_summary (fn);
 230   if (info)
 231     return info->statics_not_written;
 232   else if (flags_from_decl_or_type (fn->decl) & ECF_LEAF)
 233     return all_module_statics;
 234   else
 235     return NULL;
 236 }
 237
 238 \f
 239 /* Return true if the variable T is the right kind of static variable to
 240    perform compilation unit scope escape analysis.  */
 241
 242 static inline bool
 243 is_proper_for_analysis (tree t)
 244 {
 245   /* If the variable has the "used" attribute, treat it as if it had a
 246      been touched by the devil.  */
 247   if (DECL_PRESERVE_P (t))
 248     return false;
 249
 250   /* Do not want to do anything with volatile except mark any
 251      function that uses one to be not const or pure.  */
 252   if (TREE_THIS_VOLATILE (t))
 253     return false;
 254
 255   /* We do not need to analyze readonly vars, we already know they do not
 256      alias.  */
 257   if (TREE_READONLY (t))
 258     return false;
 259
 260   /* We can not track variables with address taken.  */
 261   if (TREE_ADDRESSABLE (t))
 262     return false;
 263
 264   /* TODO: We could track public variables that are not addressable, but currently
 265      frontends don't give us those.  */
 266   if (TREE_PUBLIC (t))
 267     return false;
 268
 269   /* TODO: Check aliases.  */
 270   if (bitmap_bit_p (ignore_module_statics, DECL_UID (t)))
 271     return false;
 272
 273   return true;
 274 }
 275
 276 /* Lookup the tree node for the static variable that has UID and
 277    convert the name to a string for debugging.  */
 278
 279 static const char *
 280 get_static_name (int index)
 281 {
 282   splay_tree_node stn =
 283     splay_tree_lookup (reference_vars_to_consider, index);
 284   return fndecl_name ((tree)(stn->value));
 285 }
 286
 287 /* Dump a set of static vars to FILE.  */
 288 static void
 289 dump_static_vars_set_to_file (FILE *f, bitmap set)
 290 {
 291   unsigned int index;
 292   bitmap_iterator bi;
 293   if (set == NULL)
 294     return;
 295   else if (set == all_module_statics)
 296     fprintf (f, "ALL");
 297   else
 298     EXECUTE_IF_SET_IN_BITMAP (set, 0, index, bi)
 299       {
 300         fprintf (f, "%s ", get_static_name (index));
 301       }
 302 }
 303
 304 /* Compute X |= Y, taking into account the possibility that
 305    either X or Y is already the maximum set.
 306    Return true if X is the maximum set after taking the union with Y.  */
 307
 308 static bool
 309 union_static_var_sets (bitmap &x, bitmap y)
 310 {
 311   if (x != all_module_statics)
 312     {
 313       if (y == all_module_statics)
 314         {
 315           BITMAP_FREE (x);
 316           x = all_module_statics;
 317         }
 318       else if (bitmap_ior_into (x, y))
 319         {
 320           /* The union may have reduced X to the maximum set.
 321              In that case, we want to make that visible explicitly.
 322              Even though bitmap_equal_p can be very expensive, it
 323              turns out to be an overall win to check this here for
 324              an LTO bootstrap of GCC itself.  Liberally extrapoliate
 325              that result to be applicable to all cases.  */
 326           if (bitmap_equal_p (x, all_module_statics))
 327             {
 328               BITMAP_FREE (x);
 329               x = all_module_statics;
 330             }
 331         }
 332     }
 333   return x == all_module_statics;
 334 }
 335
 336 /* Return a copy of SET on the bitmap obstack containing SET.
 337    But if SET is NULL or the maximum set, return that instead.  */
 338
 339 static bitmap
 340 copy_static_var_set (bitmap set)
 341 {
 342   if (set == NULL || set == all_module_statics)
 343     return set;
 344   bitmap_obstack *o = set->obstack;
 345   gcc_checking_assert (o);
 346   bitmap copy = BITMAP_ALLOC (o);
 347   bitmap_copy (copy, set);
 348   return copy;
 349 }
 350
 351 /* Compute the union all of the statics read and written by every callee of X
 352    into X_GLOBAL->statics_read and X_GLOBAL->statics_written.  X_GLOBAL is
 353    actually the set representing the cycle containing X.  If the read and
 354    written sets of X_GLOBAL has been reduced to the maximum set, we don't
 355    have to look at the remaining callees.  */
 356
 357 static void
 358 propagate_bits (ipa_reference_global_vars_info_t x_global, struct cgraph_node *x)
 359 {
 360   struct cgraph_edge *e;
 361   bool read_all = x_global->statics_read == all_module_statics;
 362   bool write_all = x_global->statics_written == all_module_statics;
 363   for (e = x->callees;
 364        e && !(read_all && write_all);
 365        e = e->next_callee)
 366     {
 367       enum availability avail;
 368       struct cgraph_node *y = e->callee->function_symbol (&avail);
 369       if (!y)
 370         continue;
 371
 372       /* Only look into nodes we can propagate something.  */
 373       int flags = flags_from_decl_or_type (y->decl);
 374       if (opt_for_fn (y->decl, flag_ipa_reference)
 375           && (avail > AVAIL_INTERPOSABLE
 376               || (avail == AVAIL_INTERPOSABLE && (flags & ECF_LEAF))))
 377         {
 378           if (get_reference_vars_info (y))
 379             {
 380               ipa_reference_vars_info_t y_info = get_reference_vars_info (y);
 381               ipa_reference_global_vars_info_t y_global = &y_info->global;
 382
 383               /* Calls in the current cycle do not have their global set
 384                  computed yet (but everything else does because we're
 385                  visiting nodes in topological order).  */
 386               if (!y_global->statics_read)
 387                 continue;
 388
 389               /* If the function is const, it reads no memory even if it
 390                  seems so to local analysis.  */
 391               if (flags & ECF_CONST)
 392                 continue;
 393
 394               union_static_var_sets (x_global->statics_read,
 395                                      y_global->statics_read);
 396
 397               /* If the function is pure, it has no stores even if it
 398                  seems so to local analysis.  If we cannot return from
 399                  the function, we can safely ignore the call.  */
 400               if ((flags & ECF_PURE)
 401                   || e->cannot_lead_to_return_p ())
 402                 continue;
 403
 404               union_static_var_sets (x_global->statics_written,
 405                                      y_global->statics_written);
 406             }
 407           else
 408             gcc_unreachable ();
 409         }
 410     }
 411 }
 412
 413 static bool ipa_init_p = false;
 414
 415 /* The init routine for analyzing global static variable usage.  See
 416    comments at top for description.  */
 417 static void
 418 ipa_init (void)
 419 {
 420   if (ipa_init_p)
 421     return;
 422
 423   ipa_init_p = true;
 424
 425   if (dump_file)
 426     reference_vars_to_consider = splay_tree_new (splay_tree_compare_ints, 0, 0);
 427
 428   bitmap_obstack_initialize (&local_info_obstack);
 429   bitmap_obstack_initialize (&optimization_summary_obstack);
 430   all_module_statics = BITMAP_ALLOC (&optimization_summary_obstack);
 431   ignore_module_statics = BITMAP_ALLOC (&optimization_summary_obstack);
 432
 433   node_removal_hook_holder =
 434       symtab->add_cgraph_removal_hook (&remove_node_data, NULL);
 435   node_duplication_hook_holder =
 436       symtab->add_cgraph_duplication_hook (&duplicate_node_data, NULL);
 437 }
 438
 439
 440 /* Set up the persistent info for FN.  */
 441
 442 static ipa_reference_local_vars_info_t
 443 init_function_info (struct cgraph_node *fn)
 444 {
 445   ipa_reference_vars_info_t info
 446     = XCNEW (struct ipa_reference_vars_info_d);
 447
 448   /* Add the info to the tree's annotation.  */
 449   set_reference_vars_info (fn, info);
 450
 451   info->local.statics_read = BITMAP_ALLOC (&local_info_obstack);
 452   info->local.statics_written = BITMAP_ALLOC (&local_info_obstack);
 453
 454   return &info->local;
 455 }
 456
 457
 458 /* This is the main routine for finding the reference patterns for
 459    global variables within a function FN.  */
 460
 461 static void
 462 analyze_function (struct cgraph_node *fn)
 463 {
 464   ipa_reference_local_vars_info_t local;
 465   struct ipa_ref *ref = NULL;
 466   int i;
 467   tree var;
 468
 469   if (!opt_for_fn (fn->decl, flag_ipa_reference))
 470     return;
 471   local = init_function_info (fn);
 472   for (i = 0; fn->iterate_reference (i, ref); i++)
 473     {
 474       if (!is_a <varpool_node *> (ref->referred))
 475         continue;
 476       var = ref->referred->decl;
 477       if (!is_proper_for_analysis (var))
 478         continue;
 479       /* This is a variable we care about.  Check if we have seen it
 480          before, and if not add it the set of variables we care about.  */
 481       if (all_module_statics
 482           && bitmap_set_bit (all_module_statics, DECL_UID (var)))
 483         {
 484           if (dump_file)
 485             splay_tree_insert (reference_vars_to_consider,
 486                                DECL_UID (var), (splay_tree_value)var);
 487         }
 488       switch (ref->use)
 489         {
 490         case IPA_REF_LOAD:
 491           bitmap_set_bit (local->statics_read, DECL_UID (var));
 492           break;
 493         case IPA_REF_STORE:
 494           if (ref->cannot_lead_to_return ())
 495             break;
 496           bitmap_set_bit (local->statics_written, DECL_UID (var));
 497           break;
 498         case IPA_REF_ADDR:
 499           break;
 500         default:
 501           gcc_unreachable ();
 502         }
 503     }
 504
 505   if (fn->cannot_return_p ())
 506     bitmap_clear (local->statics_written);
 507 }
 508
 509
 510 /* Called when new clone is inserted to callgraph late.  */
 511
 512 static void
 513 duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst,
 514                      void *data ATTRIBUTE_UNUSED)
 515 {
 516   ipa_reference_optimization_summary_t ginfo;
 517   ipa_reference_optimization_summary_t dst_ginfo;
 518
 519   ginfo = get_reference_optimization_summary (src);
 520   if (!ginfo)
 521     return;
 522   dst_ginfo = XCNEW (struct ipa_reference_optimization_summary_d);
 523   set_reference_optimization_summary (dst, dst_ginfo);
 524   dst_ginfo->statics_not_read =
 525     copy_static_var_set (ginfo->statics_not_read);
 526   dst_ginfo->statics_not_written =
 527     copy_static_var_set (ginfo->statics_not_written);
 528 }
 529
 530 /* Called when node is removed.  */
 531
 532 static void
 533 remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 534 {
 535   ipa_reference_optimization_summary_t ginfo;
 536   ginfo = get_reference_optimization_summary (node);
 537   if (ginfo)
 538     {
 539       if (ginfo->statics_not_read
 540           && ginfo->statics_not_read != all_module_statics)
 541         BITMAP_FREE (ginfo->statics_not_read);
 542
 543       if (ginfo->statics_not_written
 544           && ginfo->statics_not_written != all_module_statics)
 545         BITMAP_FREE (ginfo->statics_not_written);
 546       free (ginfo);
 547       set_reference_optimization_summary (node, NULL);
 548     }
 549 }
 550
 551 /* Analyze each function in the cgraph to see which global or statics
 552    are read or written.  */
 553
 554 static void
 555 generate_summary (void)
 556 {
 557   struct cgraph_node *node;
 558   unsigned int index;
 559   bitmap_iterator bi;
 560
 561   ipa_init ();
 562
 563   /* Process all of the functions next.  */
 564   FOR_EACH_DEFINED_FUNCTION (node)
 565     if (!node->alias && !opt_for_fn (node->decl, flag_ipa_reference))
 566       {
 567         struct ipa_ref *ref = NULL;
 568         int i;
 569         tree var;
 570         for (i = 0; node->iterate_reference (i, ref); i++)
 571           {
 572             if (!is_a <varpool_node *> (ref->referred))
 573               continue;
 574             var = ref->referred->decl;
 575             if (!is_proper_for_analysis (var))
 576               continue;
 577             bitmap_set_bit (ignore_module_statics, DECL_UID (var));
 578           }
 579       }
 580   FOR_EACH_DEFINED_FUNCTION (node)
 581     analyze_function (node);
 582
 583   if (dump_file)
 584     EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
 585       {
 586         fprintf (dump_file, "\nPromotable global:%s (uid=%u)\n",
 587                  get_static_name (index), index);
 588       }
 589
 590   if (dump_file)
 591     FOR_EACH_DEFINED_FUNCTION (node)
 592       if (node->get_availability () >= AVAIL_INTERPOSABLE
 593           && opt_for_fn (node->decl, flag_ipa_reference))
 594         {
 595           ipa_reference_local_vars_info_t l;
 596           unsigned int index;
 597           bitmap_iterator bi;
 598
 599           l = &get_reference_vars_info (node)->local;
 600           fprintf (dump_file,
 601                    "\nFunction name:%s/%i:",
 602                    node->asm_name (), node->order);
 603           fprintf (dump_file, "\n  locals read: ");
 604           if (l->statics_read)
 605             EXECUTE_IF_SET_IN_BITMAP (l->statics_read,
 606                                       0, index, bi)
 607               {
 608                 fprintf (dump_file, "%s ",
 609                          get_static_name (index));
 610               }
 611           fprintf (dump_file, "\n  locals written: ");
 612           if (l->statics_written)
 613             EXECUTE_IF_SET_IN_BITMAP (l->statics_written,
 614                                       0, index, bi)
 615               {
 616                 fprintf (dump_file, "%s ", get_static_name (index));
 617               }
 618         }
 619 }
 620 \f
 621 /* Set READ_ALL/WRITE_ALL based on decl flags of NODE.  */
 622
 623 static void
 624 read_write_all_from_decl (struct cgraph_node *node,
 625                           bool &read_all, bool &write_all)
 626 {
 627   tree decl = node->decl;
 628   int flags = flags_from_decl_or_type (decl);
 629   if ((flags & ECF_LEAF)
 630       && node->get_availability () < AVAIL_INTERPOSABLE)
 631     ;
 632   else if (flags & ECF_CONST)
 633     ;
 634   else if ((flags & ECF_PURE) || node->cannot_return_p ())
 635     {
 636       read_all = true;
 637       if (dump_file && (dump_flags & TDF_DETAILS))
 638          fprintf (dump_file, "   %s/%i -> read all\n",
 639                   node->asm_name (), node->order);
 640     }
 641   else
 642     {
 643        /* TODO: To be able to produce sane results, we should also handle
 644           common builtins, in particular throw.  */
 645       read_all = true;
 646       write_all = true;
 647       if (dump_file && (dump_flags & TDF_DETAILS))
 648          fprintf (dump_file, "   %s/%i -> read all, write all\n",
 649                   node->asm_name (), node->order);
 650     }
 651 }
 652
 653 /* Set READ_ALL/WRITE_ALL based on decl flags of NODE or any member
 654    in the cycle of NODE.  */
 655
 656 static void
 657 get_read_write_all_from_node (struct cgraph_node *node,
 658                               bool &read_all, bool &write_all)
 659 {
 660   struct cgraph_edge *e, *ie;
 661
 662   /* When function is overwritable, we can not assume anything.  */
 663   if (node->get_availability () <= AVAIL_INTERPOSABLE
 664       || (node->analyzed && !opt_for_fn (node->decl, flag_ipa_reference)))
 665     read_write_all_from_decl (node, read_all, write_all);
 666
 667   for (e = node->callees;
 668        e && !(read_all && write_all);
 669        e = e->next_callee)
 670     {
 671       enum availability avail;
 672       struct cgraph_node *callee = e->callee->function_symbol (&avail);
 673       gcc_checking_assert (callee);
 674       if (avail <= AVAIL_INTERPOSABLE
 675           || (callee->analyzed && !opt_for_fn (callee->decl, flag_ipa_reference)))
 676         read_write_all_from_decl (callee, read_all, write_all);
 677     }
 678
 679   for (ie = node->indirect_calls;
 680        ie && !(read_all && write_all);
 681        ie = ie->next_callee)
 682     if (!(ie->indirect_info->ecf_flags & ECF_CONST))
 683       {
 684         read_all = true;
 685         if (dump_file && (dump_flags & TDF_DETAILS))
 686           fprintf (dump_file, "   indirect call -> read all\n");
 687         if (!ie->cannot_lead_to_return_p ()
 688             && !(ie->indirect_info->ecf_flags & ECF_PURE))
 689           {
 690             if (dump_file && (dump_flags & TDF_DETAILS))
 691               fprintf (dump_file, "   indirect call -> write all\n");
 692             write_all = true;
 693           }
 694       }
 695 }
 696
 697 /* Skip edges from and to nodes without ipa_reference enables.  This leave
 698    them out of strongy connected coponents and makes them easyto skip in the
 699    propagation loop bellow.  */
 700
 701 static bool
 702 ignore_edge_p (cgraph_edge *e)
 703 {
 704   return (!opt_for_fn (e->caller->decl, flag_ipa_reference)
 705           || !opt_for_fn (e->callee->function_symbol ()->decl,
 706                           flag_ipa_reference));
 707 }
 708
 709 /* Produce the global information by preforming a transitive closure
 710    on the local information that was produced by ipa_analyze_function.  */
 711
 712 static unsigned int
 713 propagate (void)
 714 {
 715   struct cgraph_node *node;
 716   struct cgraph_node **order =
 717     XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
 718   int order_pos;
 719   int i;
 720   bool remove_p;
 721
 722   if (dump_file)
 723     cgraph_node::dump_cgraph (dump_file);
 724
 725   remove_p = ipa_discover_readonly_nonaddressable_vars ();
 726   generate_summary ();
 727
 728   /* Propagate the local information through the call graph to produce
 729      the global information.  All the nodes within a cycle will have
 730      the same info so we collapse cycles first.  Then we can do the
 731      propagation in one pass from the leaves to the roots.  */
 732   order_pos = ipa_reduced_postorder (order, true, true, ignore_edge_p);
 733   if (dump_file)
 734     ipa_print_order (dump_file, "reduced", order, order_pos);
 735
 736   for (i = 0; i < order_pos; i++ )
 737     {
 738       unsigned x;
 739       struct cgraph_node *w;
 740       ipa_reference_vars_info_t node_info;
 741       ipa_reference_global_vars_info_t node_g;
 742       ipa_reference_local_vars_info_t node_l;
 743       bool read_all = false;
 744       bool write_all = false;
 745
 746       node = order[i];
 747       if (node->alias || !opt_for_fn (node->decl, flag_ipa_reference))
 748         continue;
 749
 750       node_info = get_reference_vars_info (node);
 751       gcc_assert (node_info);
 752       node_l = &node_info->local;
 753       node_g = &node_info->global;
 754
 755       if (dump_file && (dump_flags & TDF_DETAILS))
 756         fprintf (dump_file, "Starting cycle with %s/%i\n",
 757                   node->asm_name (), node->order);
 758
 759       vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
 760
 761       /* If any node in a cycle is read_all or write_all, they all are.  */
 762       FOR_EACH_VEC_ELT (cycle_nodes, x, w)
 763         {
 764           if (dump_file && (dump_flags & TDF_DETAILS))
 765             fprintf (dump_file, "  Visiting %s/%i\n",
 766                      w->asm_name (), w->order);
 767           get_read_write_all_from_node (w, read_all, write_all);
 768           if (read_all && write_all)
 769             break;
 770         }
 771
 772       /* Initialized the bitmaps global sets for the reduced node.  */
 773       if (read_all)
 774         node_g->statics_read = all_module_statics;
 775       else
 776         node_g->statics_read = copy_static_var_set (node_l->statics_read);
 777       if (write_all)
 778         node_g->statics_written = all_module_statics;
 779       else
 780         node_g->statics_written = copy_static_var_set (node_l->statics_written);
 781
 782       /* Merge the sets of this cycle with all sets of callees reached
 783          from this cycle.  */
 784       FOR_EACH_VEC_ELT (cycle_nodes, x, w)
 785         {
 786           if (read_all && write_all)
 787             break;
 788
 789           if (w != node)
 790             {
 791               ipa_reference_vars_info_t w_ri = get_reference_vars_info (w);
 792               ipa_reference_local_vars_info_t w_l = &w_ri->local;
 793               int flags = flags_from_decl_or_type (w->decl);
 794
 795               if (!(flags & ECF_CONST))
 796                 read_all = union_static_var_sets (node_g->statics_read,
 797                                                   w_l->statics_read);
 798               if (!(flags & ECF_PURE)
 799                   && !w->cannot_return_p ())
 800                 write_all = union_static_var_sets (node_g->statics_written,
 801                                                    w_l->statics_written);
 802             }
 803
 804           propagate_bits (node_g, w);
 805         }
 806
 807       /* All nodes within a cycle have the same global info bitmaps.  */
 808       FOR_EACH_VEC_ELT (cycle_nodes, x, w)
 809         {
 810           ipa_reference_vars_info_t w_ri = get_reference_vars_info (w);
 811           w_ri->global = *node_g;
 812         }
 813
 814       cycle_nodes.release ();
 815     }
 816
 817   if (dump_file)
 818     {
 819       for (i = 0; i < order_pos; i++)
 820         {
 821           unsigned x;
 822           struct cgraph_node *w;
 823
 824           node = order[i];
 825           if (node->alias || !opt_for_fn (node->decl, flag_ipa_reference))
 826             continue;
 827
 828           fprintf (dump_file,
 829                    "\nFunction name:%s/%i:",
 830                    node->asm_name (), node->order);
 831
 832           ipa_reference_vars_info_t node_info = get_reference_vars_info (node);
 833           ipa_reference_global_vars_info_t node_g = &node_info->global;
 834
 835           vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
 836           FOR_EACH_VEC_ELT (cycle_nodes, x, w)
 837             {
 838               ipa_reference_vars_info_t w_ri = get_reference_vars_info (w);
 839               ipa_reference_local_vars_info_t w_l = &w_ri->local;
 840               if (w != node)
 841                 fprintf (dump_file, "\n  next cycle: %s/%i ",
 842                          w->asm_name (), w->order);
 843               fprintf (dump_file, "\n    locals read: ");
 844               dump_static_vars_set_to_file (dump_file, w_l->statics_read);
 845               fprintf (dump_file, "\n    locals written: ");
 846               dump_static_vars_set_to_file (dump_file, w_l->statics_written);
 847             }
 848           cycle_nodes.release ();
 849
 850           fprintf (dump_file, "\n  globals read: ");
 851           dump_static_vars_set_to_file (dump_file, node_g->statics_read);
 852           fprintf (dump_file, "\n  globals written: ");
 853           dump_static_vars_set_to_file (dump_file, node_g->statics_written);
 854           fprintf (dump_file, "\n");
 855         }
 856     }
 857
 858   /* Cleanup. */
 859   FOR_EACH_DEFINED_FUNCTION (node)
 860     {
 861       ipa_reference_vars_info_t node_info;
 862       ipa_reference_global_vars_info_t node_g;
 863       ipa_reference_optimization_summary_t opt;
 864
 865       node_info = get_reference_vars_info (node);
 866       if (!node->alias && opt_for_fn (node->decl, flag_ipa_reference)
 867           && (node->get_availability () > AVAIL_INTERPOSABLE
 868               || (flags_from_decl_or_type (node->decl) & ECF_LEAF)))
 869         {
 870           node_g = &node_info->global;
 871
 872           opt = XCNEW (struct ipa_reference_optimization_summary_d);
 873           set_reference_optimization_summary (node, opt);
 874
 875           /* Create the complimentary sets.  */
 876
 877           if (bitmap_empty_p (node_g->statics_read))
 878             opt->statics_not_read = all_module_statics;
 879           else
 880             {
 881               opt->statics_not_read
 882                  = BITMAP_ALLOC (&optimization_summary_obstack);
 883               if (node_g->statics_read != all_module_statics)
 884                 bitmap_and_compl (opt->statics_not_read,
 885                                   all_module_statics,
 886                                   node_g->statics_read);
 887             }
 888
 889           if (bitmap_empty_p (node_g->statics_written))
 890             opt->statics_not_written = all_module_statics;
 891           else
 892             {
 893               opt->statics_not_written
 894                 = BITMAP_ALLOC (&optimization_summary_obstack);
 895               if (node_g->statics_written != all_module_statics)
 896                 bitmap_and_compl (opt->statics_not_written,
 897                                   all_module_statics,
 898                                   node_g->statics_written);
 899             }
 900         }
 901       free (node_info);
 902    }
 903
 904   ipa_free_postorder_info ();
 905   free (order);
 906
 907   bitmap_obstack_release (&local_info_obstack);
 908   ipa_reference_vars_vector.release ();
 909   if (dump_file)
 910     splay_tree_delete (reference_vars_to_consider);
 911   reference_vars_to_consider = NULL;
 912   return remove_p ? TODO_remove_functions : 0;
 913 }
 914
 915 /* Return true if we need to write summary of NODE. */
 916
 917 static bool
 918 write_node_summary_p (struct cgraph_node *node,
 919                       lto_symtab_encoder_t encoder,
 920                       bitmap ltrans_statics)
 921 {
 922   ipa_reference_optimization_summary_t info;
 923
 924   /* See if we have (non-empty) info.  */
 925   if (!node->definition || node->global.inlined_to)
 926     return false;
 927   info = get_reference_optimization_summary (node);
 928   if (!info || (bitmap_empty_p (info->statics_not_read)
 929                 && bitmap_empty_p (info->statics_not_written)))
 930     return false;
 931
 932   /* See if we want to encode it.
 933      Encode also referenced functions since constant folding might turn it into
 934      a direct call.
 935
 936      In future we might also want to include summaries of functions references
 937      by initializers of constant variables references in current unit.  */
 938   if (!reachable_from_this_partition_p (node, encoder)
 939       && !referenced_from_this_partition_p (node, encoder))
 940     return false;
 941
 942   /* See if the info has non-empty intersections with vars we want to encode.  */
 943   if (!bitmap_intersect_p (info->statics_not_read, ltrans_statics)
 944       && !bitmap_intersect_p (info->statics_not_written, ltrans_statics))
 945     return false;
 946   return true;
 947 }
 948
 949 /* Stream out BITS&LTRANS_STATICS as list of decls to OB.
 950    LTRANS_STATICS_BITCOUNT specify number of bits in LTRANS_STATICS
 951    or -1.  When it is positive, just output -1 when
 952    BITS&LTRANS_STATICS == BITS&LTRANS_STATICS.  */
 953
 954 static void
 955 stream_out_bitmap (struct lto_simple_output_block *ob,
 956                    bitmap bits, bitmap ltrans_statics,
 957                    int ltrans_statics_bitcount)
 958 {
 959   int count = 0;
 960   unsigned int index;
 961   bitmap_iterator bi;
 962   if (bits == all_module_statics)
 963     {
 964       streamer_write_hwi_stream (ob->main_stream, -1);
 965       return;
 966     }
 967   EXECUTE_IF_AND_IN_BITMAP (bits, ltrans_statics, 0, index, bi)
 968     count ++;
 969   if (count == ltrans_statics_bitcount)
 970     {
 971       streamer_write_hwi_stream (ob->main_stream, -1);
 972       return;
 973     }
 974   streamer_write_hwi_stream (ob->main_stream, count);
 975   if (!count)
 976     return;
 977   EXECUTE_IF_AND_IN_BITMAP (bits, ltrans_statics, 0, index, bi)
 978     {
 979       tree decl = (tree)splay_tree_lookup (reference_vars_to_consider, index)->value;
 980       lto_output_var_decl_index (ob->decl_state, ob->main_stream, decl);
 981     }
 982 }
 983
 984 /* Serialize the ipa info for lto.  */
 985
 986 static void
 987 ipa_reference_write_optimization_summary (void)
 988 {
 989   struct lto_simple_output_block *ob
 990     = lto_create_simple_output_block (LTO_section_ipa_reference);
 991   unsigned int count = 0;
 992   int ltrans_statics_bitcount = 0;
 993   lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
 994   bitmap ltrans_statics = BITMAP_ALLOC (NULL);
 995   int i;
 996
 997   reference_vars_to_consider = splay_tree_new (splay_tree_compare_ints, 0, 0);
 998
 999   /* See what variables we are interested in.  */
1000   for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
1001     {
1002       symtab_node *snode = lto_symtab_encoder_deref (encoder, i);
1003       varpool_node *vnode = dyn_cast <varpool_node *> (snode);
1004       if (vnode
1005           && bitmap_bit_p (all_module_statics, DECL_UID (vnode->decl))
1006           && referenced_from_this_partition_p (vnode, encoder))
1007         {
1008           tree decl = vnode->decl;
1009           bitmap_set_bit (ltrans_statics, DECL_UID (decl));
1010           splay_tree_insert (reference_vars_to_consider,
1011                              DECL_UID (decl), (splay_tree_value)decl);
1012           ltrans_statics_bitcount ++;
1013         }
1014     }
1015
1016
1017   if (ltrans_statics_bitcount)
1018     for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
1019       {
1020         symtab_node *snode = lto_symtab_encoder_deref (encoder, i);
1021         cgraph_node *cnode = dyn_cast <cgraph_node *> (snode);
1022         if (cnode && write_node_summary_p (cnode, encoder, ltrans_statics))
1023           count++;
1024       }
1025
1026   streamer_write_uhwi_stream (ob->main_stream, count);
1027   if (count)
1028     stream_out_bitmap (ob, ltrans_statics, ltrans_statics,
1029                        -1);
1030
1031   /* Process all of the functions.  */
1032   if (ltrans_statics_bitcount)
1033     for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
1034       {
1035         symtab_node *snode = lto_symtab_encoder_deref (encoder, i);
1036         cgraph_node *cnode = dyn_cast <cgraph_node *> (snode);
1037         if (cnode && write_node_summary_p (cnode, encoder, ltrans_statics))
1038           {
1039             ipa_reference_optimization_summary_t info;
1040             int node_ref;
1041
1042             info = get_reference_optimization_summary (cnode);
1043             node_ref = lto_symtab_encoder_encode (encoder, snode);
1044             streamer_write_uhwi_stream (ob->main_stream, node_ref);
1045
1046             stream_out_bitmap (ob, info->statics_not_read, ltrans_statics,
1047                                ltrans_statics_bitcount);
1048             stream_out_bitmap (ob, info->statics_not_written, ltrans_statics,
1049                                ltrans_statics_bitcount);
1050           }
1051       }
1052   BITMAP_FREE (ltrans_statics);
1053   lto_destroy_simple_output_block (ob);
1054   splay_tree_delete (reference_vars_to_consider);
1055 }
1056
1057 /* Deserialize the ipa info for lto.  */
1058
1059 static void
1060 ipa_reference_read_optimization_summary (void)
1061 {
1062   struct lto_file_decl_data ** file_data_vec
1063     = lto_get_file_decl_data ();
1064   struct lto_file_decl_data * file_data;
1065   unsigned int j = 0;
1066   bitmap_obstack_initialize (&optimization_summary_obstack);
1067
1068   node_removal_hook_holder =
1069       symtab->add_cgraph_removal_hook (&remove_node_data, NULL);
1070   node_duplication_hook_holder =
1071       symtab->add_cgraph_duplication_hook (&duplicate_node_data, NULL);
1072   all_module_statics = BITMAP_ALLOC (&optimization_summary_obstack);
1073
1074   while ((file_data = file_data_vec[j++]))
1075     {
1076       const char *data;
1077       size_t len;
1078       struct lto_input_block *ib
1079         = lto_create_simple_input_block (file_data,
1080                                          LTO_section_ipa_reference,
1081                                          &data, &len);
1082       if (ib)
1083         {
1084           unsigned int i;
1085           unsigned int f_count = streamer_read_uhwi (ib);
1086           int b_count;
1087           if (!f_count)
1088             continue;
1089           b_count = streamer_read_hwi (ib);
1090           if (dump_file)
1091             fprintf (dump_file, "all module statics:");
1092           for (i = 0; i < (unsigned int)b_count; i++)
1093             {
1094               unsigned int var_index = streamer_read_uhwi (ib);
1095               tree v_decl = lto_file_decl_data_get_var_decl (file_data,
1096                                                              var_index);
1097               bitmap_set_bit (all_module_statics, DECL_UID (v_decl));
1098               if (dump_file)
1099                 fprintf (dump_file, " %s", fndecl_name (v_decl));
1100             }
1101
1102           for (i = 0; i < f_count; i++)
1103             {
1104               unsigned int j, index;
1105               struct cgraph_node *node;
1106               ipa_reference_optimization_summary_t info;
1107               int v_count;
1108               lto_symtab_encoder_t encoder;
1109
1110               index = streamer_read_uhwi (ib);
1111               encoder = file_data->symtab_node_encoder;
1112               node = dyn_cast<cgraph_node *> (lto_symtab_encoder_deref
1113                 (encoder, index));
1114               info = XCNEW (struct ipa_reference_optimization_summary_d);
1115               set_reference_optimization_summary (node, info);
1116               info->statics_not_read = BITMAP_ALLOC (&optimization_summary_obstack);
1117               info->statics_not_written = BITMAP_ALLOC (&optimization_summary_obstack);
1118               if (dump_file)
1119                 fprintf (dump_file,
1120                          "\nFunction name:%s/%i:\n  static not read:",
1121                          node->asm_name (), node->order);
1122
1123               /* Set the statics not read.  */
1124               v_count = streamer_read_hwi (ib);
1125               if (v_count == -1)
1126                 {
1127                   info->statics_not_read = all_module_statics;
1128                   if (dump_file)
1129                     fprintf (dump_file, " all module statics");
1130                 }
1131               else
1132                 for (j = 0; j < (unsigned int)v_count; j++)
1133                   {
1134                     unsigned int var_index = streamer_read_uhwi (ib);
1135                     tree v_decl = lto_file_decl_data_get_var_decl (file_data,
1136                                                                    var_index);
1137                     bitmap_set_bit (info->statics_not_read, DECL_UID (v_decl));
1138                     if (dump_file)
1139                       fprintf (dump_file, " %s", fndecl_name (v_decl));
1140                   }
1141
1142               if (dump_file)
1143                 fprintf (dump_file,
1144                          "\n  static not written:");
1145               /* Set the statics not written.  */
1146               v_count = streamer_read_hwi (ib);
1147               if (v_count == -1)
1148                 {
1149                   info->statics_not_written = all_module_statics;
1150                   if (dump_file)
1151                     fprintf (dump_file, " all module statics");
1152                 }
1153               else
1154                 for (j = 0; j < (unsigned int)v_count; j++)
1155                   {
1156                     unsigned int var_index = streamer_read_uhwi (ib);
1157                     tree v_decl = lto_file_decl_data_get_var_decl (file_data,
1158                                                                    var_index);
1159                     bitmap_set_bit (info->statics_not_written, DECL_UID (v_decl));
1160                     if (dump_file)
1161                       fprintf (dump_file, " %s", fndecl_name (v_decl));
1162                   }
1163               if (dump_file)
1164                 fprintf (dump_file, "\n");
1165             }
1166
1167           lto_destroy_simple_input_block (file_data,
1168                                           LTO_section_ipa_reference,
1169                                           ib, data, len);
1170         }
1171       else
1172         /* Fatal error here.  We do not want to support compiling ltrans units with
1173            different version of compiler or different flags than the WPA unit, so
1174            this should never happen.  */
1175         fatal_error (input_location,
1176                      "ipa reference summary is missing in ltrans unit");
1177     }
1178 }
1179
1180 namespace {
1181
1182 const pass_data pass_data_ipa_reference =
1183 {
1184   IPA_PASS, /* type */
1185   "static-var", /* name */
1186   OPTGROUP_NONE, /* optinfo_flags */
1187   TV_IPA_REFERENCE, /* tv_id */
1188   0, /* properties_required */
1189   0, /* properties_provided */
1190   0, /* properties_destroyed */
1191   0, /* todo_flags_start */
1192   0, /* todo_flags_finish */
1193 };
1194
1195 class pass_ipa_reference : public ipa_opt_pass_d
1196 {
1197 public:
1198   pass_ipa_reference (gcc::context *ctxt)
1199     : ipa_opt_pass_d (pass_data_ipa_reference, ctxt,
1200                       NULL, /* generate_summary */
1201                       NULL, /* write_summary */
1202                       NULL, /* read_summary */
1203                       ipa_reference_write_optimization_summary, /*
1204                       write_optimization_summary */
1205                       ipa_reference_read_optimization_summary, /*
1206                       read_optimization_summary */
1207                       NULL, /* stmt_fixup */
1208                       0, /* function_transform_todo_flags_start */
1209                       NULL, /* function_transform */
1210                       NULL) /* variable_transform */
1211     {}
1212
1213   /* opt_pass methods: */
1214   virtual bool gate (function *)
1215     {
1216       return ((in_lto_p || flag_ipa_reference)
1217               /* Don't bother doing anything if the program has errors.  */
1218               && !seen_error ());
1219     }
1220
1221   virtual unsigned int execute (function *) { return propagate (); }
1222
1223 }; // class pass_ipa_reference
1224
1225 } // anon namespace
1226
1227 ipa_opt_pass_d *
1228 make_pass_ipa_reference (gcc::context *ctxt)
1229 {
1230   return new pass_ipa_reference (ctxt);
1231 }
1232
1233 /* Reset all state within ipa-reference.c so that we can rerun the compiler
1234    within the same process.  For use by toplev::finalize.  */
1235
1236 void
1237 ipa_reference_c_finalize (void)
1238 {
1239   if (ipa_init_p)
1240     {
1241       bitmap_obstack_release (&optimization_summary_obstack);
1242       ipa_init_p = false;
1243     }
1244
1245   if (node_removal_hook_holder)
1246     {
1247       symtab->remove_cgraph_removal_hook (node_removal_hook_holder);
1248       node_removal_hook_holder = NULL;
1249     }
1250   if (node_duplication_hook_holder)
1251     {
1252       symtab->remove_cgraph_duplication_hook (node_duplication_hook_holder);
1253       node_duplication_hook_holder = NULL;
1254     }
1255 }