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