gcc/ipa-reference.c

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