gcc/ipa-reference.c

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