gcc/ipa-reference.c

   1 /* Callgraph based analysis of static variables.
   2    Copyright (C) 2004-2016 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/%i:",
 603                    node->asm_name (), node->order);
 604           fprintf (dump_file, "\n  locals read: ");
 605           if (l->statics_read)
 606             EXECUTE_IF_SET_IN_BITMAP (l->statics_read,
 607                                       0, index, bi)
 608               {
 609                 fprintf (dump_file, "%s ",
 610                          get_static_name (index));
 611               }
 612           fprintf (dump_file, "\n  locals written: ");
 613           if (l->statics_written)
 614             EXECUTE_IF_SET_IN_BITMAP (l->statics_written,
 615                                       0, index, bi)
 616               {
 617                 fprintf (dump_file, "%s ", get_static_name (index));
 618               }
 619         }
 620 }
 621 \f
 622 /* Set READ_ALL/WRITE_ALL based on decl flags of NODE.  */
 623
 624 static void
 625 read_write_all_from_decl (struct cgraph_node *node,
 626                           bool &read_all, bool &write_all)
 627 {
 628   tree decl = node->decl;
 629   int flags = flags_from_decl_or_type (decl);
 630   if ((flags & ECF_LEAF)
 631       && node->get_availability () < AVAIL_INTERPOSABLE)
 632     ;
 633   else if (flags & ECF_CONST)
 634     ;
 635   else if ((flags & ECF_PURE) || node->cannot_return_p ())
 636     {
 637       read_all = true;
 638       if (dump_file && (dump_flags & TDF_DETAILS))
 639          fprintf (dump_file, "   %s/%i -> read all\n",
 640                   node->asm_name (), node->order);
 641     }
 642   else
 643     {
 644        /* TODO: To be able to produce sane results, we should also handle
 645           common builtins, in particular throw.  */
 646       read_all = true;
 647       write_all = true;
 648       if (dump_file && (dump_flags & TDF_DETAILS))
 649          fprintf (dump_file, "   %s/%i -> read all, write all\n",
 650                   node->asm_name (), node->order);
 651     }
 652 }
 653
 654 /* Set READ_ALL/WRITE_ALL based on decl flags of NODE or any member
 655    in the cycle of NODE.  */
 656
 657 static void
 658 get_read_write_all_from_node (struct cgraph_node *node,
 659                               bool &read_all, bool &write_all)
 660 {
 661   struct cgraph_edge *e, *ie;
 662
 663   /* When function is overwritable, we can not assume anything.  */
 664   if (node->get_availability () <= AVAIL_INTERPOSABLE
 665       || (node->analyzed && !opt_for_fn (node->decl, flag_ipa_reference)))
 666     read_write_all_from_decl (node, read_all, write_all);
 667
 668   for (e = node->callees;
 669        e && !(read_all && write_all);
 670        e = e->next_callee)
 671     {
 672       enum availability avail;
 673       struct cgraph_node *callee = e->callee->function_symbol (&avail);
 674       gcc_checking_assert (callee);
 675       if (avail <= AVAIL_INTERPOSABLE
 676           || (callee->analyzed && !opt_for_fn (callee->decl, flag_ipa_reference)))
 677         read_write_all_from_decl (callee, read_all, write_all);
 678     }
 679
 680   for (ie = node->indirect_calls;
 681        ie && !(read_all && write_all);
 682        ie = ie->next_callee)
 683     if (!(ie->indirect_info->ecf_flags & ECF_CONST))
 684       {
 685         read_all = true;
 686         if (dump_file && (dump_flags & TDF_DETAILS))
 687           fprintf (dump_file, "   indirect call -> read all\n");
 688         if (!ie->cannot_lead_to_return_p ()
 689             && !(ie->indirect_info->ecf_flags & ECF_PURE))
 690           {
 691             if (dump_file && (dump_flags & TDF_DETAILS))
 692               fprintf (dump_file, "   indirect call -> write all\n");
 693             write_all = true;
 694           }
 695       }
 696 }
 697
 698 /* Skip edges from and to nodes without ipa_reference enables.  This leave
 699    them out of strongy connected coponents and makes them easyto skip in the
 700    propagation loop bellow.  */
 701
 702 static bool
 703 ignore_edge_p (cgraph_edge *e)
 704 {
 705   return (!opt_for_fn (e->caller->decl, flag_ipa_reference)
 706           || !opt_for_fn (e->callee->function_symbol ()->decl,
 707                           flag_ipa_reference));
 708 }
 709
 710 /* Produce the global information by preforming a transitive closure
 711    on the local information that was produced by ipa_analyze_function.  */
 712
 713 static unsigned int
 714 propagate (void)
 715 {
 716   struct cgraph_node *node;
 717   struct cgraph_node **order =
 718     XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
 719   int order_pos;
 720   int i;
 721   bool remove_p;
 722
 723   if (dump_file)
 724     cgraph_node::dump_cgraph (dump_file);
 725
 726   remove_p = ipa_discover_readonly_nonaddressable_vars ();
 727   generate_summary ();
 728
 729   /* Propagate the local information through the call graph to produce
 730      the global information.  All the nodes within a cycle will have
 731      the same info so we collapse cycles first.  Then we can do the
 732      propagation in one pass from the leaves to the roots.  */
 733   order_pos = ipa_reduced_postorder (order, true, true, ignore_edge_p);
 734   if (dump_file)
 735     ipa_print_order (dump_file, "reduced", order, order_pos);
 736
 737   for (i = 0; i < order_pos; i++ )
 738     {
 739       unsigned x;
 740       struct cgraph_node *w;
 741       ipa_reference_vars_info_t node_info;
 742       ipa_reference_global_vars_info_t node_g;
 743       ipa_reference_local_vars_info_t node_l;
 744       bool read_all = false;
 745       bool write_all = false;
 746
 747       node = order[i];
 748       if (node->alias || !opt_for_fn (node->decl, flag_ipa_reference))
 749         continue;
 750
 751       node_info = get_reference_vars_info (node);
 752       gcc_assert (node_info);
 753       node_l = &node_info->local;
 754       node_g = &node_info->global;
 755
 756       if (dump_file && (dump_flags & TDF_DETAILS))
 757         fprintf (dump_file, "Starting cycle with %s/%i\n",
 758                   node->asm_name (), node->order);
 759
 760       vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
 761
 762       /* If any node in a cycle is read_all or write_all, they all are.  */
 763       FOR_EACH_VEC_ELT (cycle_nodes, x, w)
 764         {
 765           if (dump_file && (dump_flags & TDF_DETAILS))
 766             fprintf (dump_file, "  Visiting %s/%i\n",
 767                      w->asm_name (), w->order);
 768           get_read_write_all_from_node (w, read_all, write_all);
 769           if (read_all && write_all)
 770             break;
 771         }
 772
 773       /* Initialized the bitmaps global sets for the reduced node.  */
 774       if (read_all)
 775         node_g->statics_read = all_module_statics;
 776       else
 777         node_g->statics_read = copy_static_var_set (node_l->statics_read);
 778       if (write_all)
 779         node_g->statics_written = all_module_statics;
 780       else
 781         node_g->statics_written = copy_static_var_set (node_l->statics_written);
 782
 783       /* Merge the sets of this cycle with all sets of callees reached
 784          from this cycle.  */
 785       FOR_EACH_VEC_ELT (cycle_nodes, x, w)
 786         {
 787           if (read_all && write_all)
 788             break;
 789
 790           if (w != node)
 791             {
 792               ipa_reference_vars_info_t w_ri = get_reference_vars_info (w);
 793               ipa_reference_local_vars_info_t w_l = &w_ri->local;
 794               int flags = flags_from_decl_or_type (w->decl);
 795
 796               if (!(flags & ECF_CONST))
 797                 read_all = union_static_var_sets (node_g->statics_read,
 798                                                   w_l->statics_read);
 799               if (!(flags & ECF_PURE)
 800                   && !w->cannot_return_p ())
 801                 write_all = union_static_var_sets (node_g->statics_written,
 802                                                    w_l->statics_written);
 803             }
 804
 805           propagate_bits (node_g, w);
 806         }
 807
 808       /* All nodes within a cycle have the same global info bitmaps.  */
 809       FOR_EACH_VEC_ELT (cycle_nodes, x, w)
 810         {
 811           ipa_reference_vars_info_t w_ri = get_reference_vars_info (w);
 812           w_ri->global = *node_g;
 813         }
 814
 815       cycle_nodes.release ();
 816     }
 817
 818   if (dump_file)
 819     {
 820       for (i = 0; i < order_pos; i++)
 821         {
 822           unsigned x;
 823           struct cgraph_node *w;
 824
 825           node = order[i];
 826           if (node->alias || !opt_for_fn (node->decl, flag_ipa_reference))
 827             continue;
 828
 829           fprintf (dump_file,
 830                    "\nFunction name:%s/%i:",
 831                    node->asm_name (), node->order);
 832
 833           ipa_reference_vars_info_t node_info = get_reference_vars_info (node);
 834           ipa_reference_global_vars_info_t node_g = &node_info->global;
 835
 836           vec<cgraph_node *> cycle_nodes = ipa_get_nodes_in_cycle (node);
 837           FOR_EACH_VEC_ELT (cycle_nodes, x, w)
 838             {
 839               ipa_reference_vars_info_t w_ri = get_reference_vars_info (w);
 840               ipa_reference_local_vars_info_t w_l = &w_ri->local;
 841               if (w != node)
 842                 fprintf (dump_file, "\n  next cycle: %s/%i ",
 843                          w->asm_name (), w->order);
 844               fprintf (dump_file, "\n    locals read: ");
 845               dump_static_vars_set_to_file (dump_file, w_l->statics_read);
 846               fprintf (dump_file, "\n    locals written: ");
 847               dump_static_vars_set_to_file (dump_file, w_l->statics_written);
 848             }
 849           cycle_nodes.release ();
 850
 851           fprintf (dump_file, "\n  globals read: ");
 852           dump_static_vars_set_to_file (dump_file, node_g->statics_read);
 853           fprintf (dump_file, "\n  globals written: ");
 854           dump_static_vars_set_to_file (dump_file, node_g->statics_written);
 855           fprintf (dump_file, "\n");
 856         }
 857     }
 858
 859   /* Cleanup. */
 860   FOR_EACH_DEFINED_FUNCTION (node)
 861     {
 862       ipa_reference_vars_info_t node_info;
 863       ipa_reference_global_vars_info_t node_g;
 864       ipa_reference_optimization_summary_t opt;
 865
 866       node_info = get_reference_vars_info (node);
 867       if (!node->alias && opt_for_fn (node->decl, flag_ipa_reference)
 868           && (node->get_availability () > AVAIL_INTERPOSABLE
 869               || (flags_from_decl_or_type (node->decl) & ECF_LEAF)))
 870         {
 871           node_g = &node_info->global;
 872
 873           opt = XCNEW (struct ipa_reference_optimization_summary_d);
 874           set_reference_optimization_summary (node, opt);
 875
 876           /* Create the complimentary sets.  */
 877
 878           if (bitmap_empty_p (node_g->statics_read))
 879             opt->statics_not_read = all_module_statics;
 880           else
 881             {
 882               opt->statics_not_read
 883                  = BITMAP_ALLOC (&optimization_summary_obstack);
 884               if (node_g->statics_read != all_module_statics)
 885                 bitmap_and_compl (opt->statics_not_read,
 886                                   all_module_statics,
 887                                   node_g->statics_read);
 888             }
 889
 890           if (bitmap_empty_p (node_g->statics_written))
 891             opt->statics_not_written = all_module_statics;
 892           else
 893             {
 894               opt->statics_not_written
 895                 = BITMAP_ALLOC (&optimization_summary_obstack);
 896               if (node_g->statics_written != all_module_statics)
 897                 bitmap_and_compl (opt->statics_not_written,
 898                                   all_module_statics,
 899                                   node_g->statics_written);
 900             }
 901         }
 902       free (node_info);
 903    }
 904
 905   ipa_free_postorder_info ();
 906   free (order);
 907
 908   bitmap_obstack_release (&local_info_obstack);
 909   ipa_reference_vars_vector.release ();
 910   if (dump_file)
 911     splay_tree_delete (reference_vars_to_consider);
 912   reference_vars_to_consider = NULL;
 913   return remove_p ? TODO_remove_functions : 0;
 914 }
 915
 916 /* Return true if we need to write summary of NODE. */
 917
 918 static bool
 919 write_node_summary_p (struct cgraph_node *node,
 920                       lto_symtab_encoder_t encoder,
 921                       bitmap ltrans_statics)
 922 {
 923   ipa_reference_optimization_summary_t info;
 924
 925   /* See if we have (non-empty) info.  */
 926   if (!node->definition || node->global.inlined_to)
 927     return false;
 928   info = get_reference_optimization_summary (node);
 929   if (!info || (bitmap_empty_p (info->statics_not_read)
 930                 && bitmap_empty_p (info->statics_not_written)))
 931     return false;
 932
 933   /* See if we want to encode it.
 934      Encode also referenced functions since constant folding might turn it into
 935      a direct call.
 936
 937      In future we might also want to include summaries of functions references
 938      by initializers of constant variables references in current unit.  */
 939   if (!reachable_from_this_partition_p (node, encoder)
 940       && !referenced_from_this_partition_p (node, encoder))
 941     return false;
 942
 943   /* See if the info has non-empty intersections with vars we want to encode.  */
 944   if (!bitmap_intersect_p (info->statics_not_read, ltrans_statics)
 945       && !bitmap_intersect_p (info->statics_not_written, ltrans_statics))
 946     return false;
 947   return true;
 948 }
 949
 950 /* Stream out BITS&LTRANS_STATICS as list of decls to OB.
 951    LTRANS_STATICS_BITCOUNT specify number of bits in LTRANS_STATICS
 952    or -1.  When it is positive, just output -1 when
 953    BITS&LTRANS_STATICS == BITS&LTRANS_STATICS.  */
 954
 955 static void
 956 stream_out_bitmap (struct lto_simple_output_block *ob,
 957                    bitmap bits, bitmap ltrans_statics,
 958                    int ltrans_statics_bitcount)
 959 {
 960   int count = 0;
 961   unsigned int index;
 962   bitmap_iterator bi;
 963   if (bits == all_module_statics)
 964     {
 965       streamer_write_hwi_stream (ob->main_stream, -1);
 966       return;
 967     }
 968   EXECUTE_IF_AND_IN_BITMAP (bits, ltrans_statics, 0, index, bi)
 969     count ++;
 970   if (count == ltrans_statics_bitcount)
 971     {
 972       streamer_write_hwi_stream (ob->main_stream, -1);
 973       return;
 974     }
 975   streamer_write_hwi_stream (ob->main_stream, count);
 976   if (!count)
 977     return;
 978   EXECUTE_IF_AND_IN_BITMAP (bits, ltrans_statics, 0, index, bi)
 979     {
 980       tree decl = (tree)splay_tree_lookup (reference_vars_to_consider, index)->value;
 981       lto_output_var_decl_index (ob->decl_state, ob->main_stream, decl);
 982     }
 983 }
 984
 985 /* Serialize the ipa info for lto.  */
 986
 987 static void
 988 ipa_reference_write_optimization_summary (void)
 989 {
 990   struct lto_simple_output_block *ob
 991     = lto_create_simple_output_block (LTO_section_ipa_reference);
 992   unsigned int count = 0;
 993   int ltrans_statics_bitcount = 0;
 994   lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
 995   bitmap ltrans_statics = BITMAP_ALLOC (NULL);
 996   int i;
 997
 998   reference_vars_to_consider = splay_tree_new (splay_tree_compare_ints, 0, 0);
 999
1000   /* See what variables we are interested in.  */
1001   for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
1002     {
1003       symtab_node *snode = lto_symtab_encoder_deref (encoder, i);
1004       varpool_node *vnode = dyn_cast <varpool_node *> (snode);
1005       if (vnode
1006           && bitmap_bit_p (all_module_statics,
1007                             ipa_reference_var_uid (vnode->decl))
1008           && referenced_from_this_partition_p (vnode, encoder))
1009         {
1010           tree decl = vnode->decl;
1011           bitmap_set_bit (ltrans_statics, ipa_reference_var_uid (decl));
1012           splay_tree_insert (reference_vars_to_consider,
1013                              ipa_reference_var_uid (decl),
1014                              (splay_tree_value)decl);
1015           ltrans_statics_bitcount ++;
1016         }
1017     }
1018
1019
1020   if (ltrans_statics_bitcount)
1021     for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
1022       {
1023         symtab_node *snode = lto_symtab_encoder_deref (encoder, i);
1024         cgraph_node *cnode = dyn_cast <cgraph_node *> (snode);
1025         if (cnode && write_node_summary_p (cnode, encoder, ltrans_statics))
1026           count++;
1027       }
1028
1029   streamer_write_uhwi_stream (ob->main_stream, count);
1030   if (count)
1031     stream_out_bitmap (ob, ltrans_statics, ltrans_statics,
1032                        -1);
1033
1034   /* Process all of the functions.  */
1035   if (ltrans_statics_bitcount)
1036     for (i = 0; i < lto_symtab_encoder_size (encoder); i++)
1037       {
1038         symtab_node *snode = lto_symtab_encoder_deref (encoder, i);
1039         cgraph_node *cnode = dyn_cast <cgraph_node *> (snode);
1040         if (cnode && write_node_summary_p (cnode, encoder, ltrans_statics))
1041           {
1042             ipa_reference_optimization_summary_t info;
1043             int node_ref;
1044
1045             info = get_reference_optimization_summary (cnode);
1046             node_ref = lto_symtab_encoder_encode (encoder, snode);
1047             streamer_write_uhwi_stream (ob->main_stream, node_ref);
1048
1049             stream_out_bitmap (ob, info->statics_not_read, ltrans_statics,
1050                                ltrans_statics_bitcount);
1051             stream_out_bitmap (ob, info->statics_not_written, ltrans_statics,
1052                                ltrans_statics_bitcount);
1053           }
1054       }
1055   BITMAP_FREE (ltrans_statics);
1056   lto_destroy_simple_output_block (ob);
1057   splay_tree_delete (reference_vars_to_consider);
1058 }
1059
1060 /* Deserialize the ipa info for lto.  */
1061
1062 static void
1063 ipa_reference_read_optimization_summary (void)
1064 {
1065   struct lto_file_decl_data ** file_data_vec
1066     = lto_get_file_decl_data ();
1067   struct lto_file_decl_data * file_data;
1068   unsigned int j = 0;
1069   bitmap_obstack_initialize (&optimization_summary_obstack);
1070
1071   node_removal_hook_holder =
1072       symtab->add_cgraph_removal_hook (&remove_node_data, NULL);
1073   node_duplication_hook_holder =
1074       symtab->add_cgraph_duplication_hook (&duplicate_node_data, NULL);
1075   all_module_statics = BITMAP_ALLOC (&optimization_summary_obstack);
1076
1077   while ((file_data = file_data_vec[j++]))
1078     {
1079       const char *data;
1080       size_t len;
1081       struct lto_input_block *ib
1082         = lto_create_simple_input_block (file_data,
1083                                          LTO_section_ipa_reference,
1084                                          &data, &len);
1085       if (ib)
1086         {
1087           unsigned int i;
1088           unsigned int f_count = streamer_read_uhwi (ib);
1089           int b_count;
1090           if (!f_count)
1091             continue;
1092           b_count = streamer_read_hwi (ib);
1093           if (dump_file)
1094             fprintf (dump_file, "all module statics:");
1095           for (i = 0; i < (unsigned int)b_count; i++)
1096             {
1097               unsigned int var_index = streamer_read_uhwi (ib);
1098               tree v_decl = lto_file_decl_data_get_var_decl (file_data,
1099                                                              var_index);
1100               bitmap_set_bit (all_module_statics,
1101                               ipa_reference_var_uid (v_decl));
1102               if (dump_file)
1103                 fprintf (dump_file, " %s", fndecl_name (v_decl));
1104             }
1105
1106           for (i = 0; i < f_count; i++)
1107             {
1108               unsigned int j, index;
1109               struct cgraph_node *node;
1110               ipa_reference_optimization_summary_t info;
1111               int v_count;
1112               lto_symtab_encoder_t encoder;
1113
1114               index = streamer_read_uhwi (ib);
1115               encoder = file_data->symtab_node_encoder;
1116               node = dyn_cast<cgraph_node *> (lto_symtab_encoder_deref
1117                 (encoder, index));
1118               info = XCNEW (struct ipa_reference_optimization_summary_d);
1119               set_reference_optimization_summary (node, info);
1120               info->statics_not_read = BITMAP_ALLOC (&optimization_summary_obstack);
1121               info->statics_not_written = BITMAP_ALLOC (&optimization_summary_obstack);
1122               if (dump_file)
1123                 fprintf (dump_file,
1124                          "\nFunction name:%s/%i:\n  static not read:",
1125                          node->asm_name (), node->order);
1126
1127               /* Set the statics not read.  */
1128               v_count = streamer_read_hwi (ib);
1129               if (v_count == -1)
1130                 {
1131                   info->statics_not_read = all_module_statics;
1132                   if (dump_file)
1133                     fprintf (dump_file, " all module statics");
1134                 }
1135               else
1136                 for (j = 0; j < (unsigned int)v_count; j++)
1137                   {
1138                     unsigned int var_index = streamer_read_uhwi (ib);
1139                     tree v_decl = lto_file_decl_data_get_var_decl (file_data,
1140                                                                    var_index);
1141                     bitmap_set_bit (info->statics_not_read,
1142                                     ipa_reference_var_uid (v_decl));
1143                     if (dump_file)
1144                       fprintf (dump_file, " %s", fndecl_name (v_decl));
1145                   }
1146
1147               if (dump_file)
1148                 fprintf (dump_file,
1149                          "\n  static not written:");
1150               /* Set the statics not written.  */
1151               v_count = streamer_read_hwi (ib);
1152               if (v_count == -1)
1153                 {
1154                   info->statics_not_written = all_module_statics;
1155                   if (dump_file)
1156                     fprintf (dump_file, " all module statics");
1157                 }
1158               else
1159                 for (j = 0; j < (unsigned int)v_count; j++)
1160                   {
1161                     unsigned int var_index = streamer_read_uhwi (ib);
1162                     tree v_decl = lto_file_decl_data_get_var_decl (file_data,
1163                                                                    var_index);
1164                     bitmap_set_bit (info->statics_not_written,
1165                                     ipa_reference_var_uid (v_decl));
1166                     if (dump_file)
1167                       fprintf (dump_file, " %s", fndecl_name (v_decl));
1168                   }
1169               if (dump_file)
1170                 fprintf (dump_file, "\n");
1171             }
1172
1173           lto_destroy_simple_input_block (file_data,
1174                                           LTO_section_ipa_reference,
1175                                           ib, data, len);
1176         }
1177       else
1178         /* Fatal error here.  We do not want to support compiling ltrans units with
1179            different version of compiler or different flags than the WPA unit, so
1180            this should never happen.  */
1181         fatal_error (input_location,
1182                      "ipa reference summary is missing in ltrans unit");
1183     }
1184 }
1185
1186 namespace {
1187
1188 const pass_data pass_data_ipa_reference =
1189 {
1190   IPA_PASS, /* type */
1191   "static-var", /* name */
1192   OPTGROUP_NONE, /* optinfo_flags */
1193   TV_IPA_REFERENCE, /* tv_id */
1194   0, /* properties_required */
1195   0, /* properties_provided */
1196   0, /* properties_destroyed */
1197   0, /* todo_flags_start */
1198   0, /* todo_flags_finish */
1199 };
1200
1201 class pass_ipa_reference : public ipa_opt_pass_d
1202 {
1203 public:
1204   pass_ipa_reference (gcc::context *ctxt)
1205     : ipa_opt_pass_d (pass_data_ipa_reference, ctxt,
1206                       NULL, /* generate_summary */
1207                       NULL, /* write_summary */
1208                       NULL, /* read_summary */
1209                       ipa_reference_write_optimization_summary, /*
1210                       write_optimization_summary */
1211                       ipa_reference_read_optimization_summary, /*
1212                       read_optimization_summary */
1213                       NULL, /* stmt_fixup */
1214                       0, /* function_transform_todo_flags_start */
1215                       NULL, /* function_transform */
1216                       NULL) /* variable_transform */
1217     {}
1218
1219   /* opt_pass methods: */
1220   virtual bool gate (function *)
1221     {
1222       return ((in_lto_p || flag_ipa_reference)
1223               /* Don't bother doing anything if the program has errors.  */
1224               && !seen_error ());
1225     }
1226
1227   virtual unsigned int execute (function *) { return propagate (); }
1228
1229 }; // class pass_ipa_reference
1230
1231 } // anon namespace
1232
1233 ipa_opt_pass_d *
1234 make_pass_ipa_reference (gcc::context *ctxt)
1235 {
1236   return new pass_ipa_reference (ctxt);
1237 }
1238
1239 /* Reset all state within ipa-reference.c so that we can rerun the compiler
1240    within the same process.  For use by toplev::finalize.  */
1241
1242 void
1243 ipa_reference_c_finalize (void)
1244 {
1245   if (ipa_init_p)
1246     {
1247       bitmap_obstack_release (&optimization_summary_obstack);
1248       ipa_init_p = false;
1249     }
1250
1251   if (node_removal_hook_holder)
1252     {
1253       symtab->remove_cgraph_removal_hook (node_removal_hook_holder);
1254       node_removal_hook_holder = NULL;
1255     }
1256   if (node_duplication_hook_holder)
1257     {
1258       symtab->remove_cgraph_duplication_hook (node_duplication_hook_holder);
1259       node_duplication_hook_holder = NULL;
1260     }
1261 }