gcc/ipa-reference.c

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