gcc/ipa-reference.c

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