gcc/ipa-reference.c

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