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