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 (fn);
 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       struct cgraph_node *y = e->callee;
 305       enum availability avail;
 306
 307       avail = cgraph_function_body_availability (e->callee);
 308       /* Only look into nodes we can propagate something.  */
 309       if (avail > AVAIL_OVERWRITABLE
 310           || (avail == AVAIL_OVERWRITABLE
 311               && (flags_from_decl_or_type (e->callee->decl) & ECF_LEAF)))
 312         {
 313           int flags = flags_from_decl_or_type (e->callee->decl);
 314           if (get_reference_vars_info (y))
 315             {
 316               ipa_reference_vars_info_t y_info
 317                 = get_reference_vars_info (y);
 318               ipa_reference_global_vars_info_t y_global = &y_info->global;
 319
 320               /* Calls in current cycle do not have global computed yet.  */
 321               if (!y_global->statics_read)
 322                 continue;
 323
 324               /* If function is declared const, it reads no memory even if it
 325                  seems so to local analysis.  */
 326               if (flags & ECF_CONST)
 327                 continue;
 328
 329               if (x_global->statics_read
 330                   != all_module_statics)
 331                 {
 332                   if (y_global->statics_read
 333                       == all_module_statics)
 334                     {
 335                       BITMAP_FREE (x_global->statics_read);
 336                       x_global->statics_read
 337                         = all_module_statics;
 338                     }
 339                   /* Skip bitmaps that are pointer equal to node's bitmap
 340                      (no reason to spin within the cycle).  */
 341                   else if (x_global->statics_read
 342                            != y_global->statics_read)
 343                     bitmap_ior_into (x_global->statics_read,
 344                                      y_global->statics_read);
 345                 }
 346
 347               /* If function is declared pure, it has no stores even if it
 348                  seems so to local analysis; If we can not return from here,
 349                  we can safely ignore the call.  */
 350               if ((flags & ECF_PURE)
 351                   || cgraph_edge_cannot_lead_to_return (e))
 352                 continue;
 353
 354               if (x_global->statics_written
 355                   != all_module_statics)
 356                 {
 357                   if (y_global->statics_written
 358                       == all_module_statics)
 359                     {
 360                       BITMAP_FREE (x_global->statics_written);
 361                       x_global->statics_written
 362                         = all_module_statics;
 363                     }
 364                   /* Skip bitmaps that are pointer equal to node's bitmap
 365                      (no reason to spin within the cycle).  */
 366                   else if (x_global->statics_written
 367                            != y_global->statics_written)
 368                     bitmap_ior_into (x_global->statics_written,
 369                                      y_global->statics_written);
 370                 }
 371             }
 372           else
 373             gcc_unreachable ();
 374         }
 375     }
 376 }
 377
 378 /* The init routine for analyzing global static variable usage.  See
 379    comments at top for description.  */
 380 static void
 381 ipa_init (void)
 382 {
 383   static bool init_p = false;
 384
 385   if (init_p)
 386     return;
 387
 388   init_p = true;
 389
 390   if (dump_file)
 391     reference_vars_to_consider = splay_tree_new (splay_tree_compare_ints, 0, 0);
 392
 393   bitmap_obstack_initialize (&local_info_obstack);
 394   bitmap_obstack_initialize (&optimization_summary_obstack);
 395   all_module_statics = BITMAP_ALLOC (&optimization_summary_obstack);
 396
 397   node_removal_hook_holder =
 398       cgraph_add_node_removal_hook (&remove_node_data, NULL);
 399   node_duplication_hook_holder =
 400       cgraph_add_node_duplication_hook (&duplicate_node_data, NULL);
 401 }
 402
 403
 404 /* Set up the persistent info for FN.  */
 405
 406 static ipa_reference_local_vars_info_t
 407 init_function_info (struct cgraph_node *fn)
 408 {
 409   ipa_reference_vars_info_t info
 410     = XCNEW (struct ipa_reference_vars_info_d);
 411
 412   /* Add the info to the tree's annotation.  */
 413   set_reference_vars_info (fn, info);
 414
 415   info->local.statics_read = BITMAP_ALLOC (&local_info_obstack);
 416   info->local.statics_written = BITMAP_ALLOC (&local_info_obstack);
 417
 418   return &info->local;
 419 }
 420
 421
 422 /* This is the main routine for finding the reference patterns for
 423    global variables within a function FN.  */
 424
 425 static void
 426 analyze_function (struct cgraph_node *fn)
 427 {
 428   ipa_reference_local_vars_info_t local;
 429   struct ipa_ref *ref;
 430   int i;
 431   tree var;
 432
 433   local = init_function_info (fn);
 434   for (i = 0; ipa_ref_list_reference_iterate (&fn->ref_list, i, ref); i++)
 435     {
 436       if (ref->refered_type != IPA_REF_VARPOOL)
 437         continue;
 438       var = ipa_ref_varpool_node (ref)->decl;
 439       if (ipa_ref_varpool_node (ref)->externally_visible
 440           || !ipa_ref_varpool_node (ref)->analyzed
 441           || !is_proper_for_analysis (var))
 442         continue;
 443       switch (ref->use)
 444         {
 445         case IPA_REF_LOAD:
 446           bitmap_set_bit (local->statics_read, DECL_UID (var));
 447           break;
 448         case IPA_REF_STORE:
 449           if (ipa_ref_cannot_lead_to_return (ref))
 450             break;
 451           bitmap_set_bit (local->statics_written, DECL_UID (var));
 452           break;
 453         case IPA_REF_ADDR:
 454           gcc_unreachable ();
 455           break;
 456         }
 457     }
 458
 459   if (cgraph_node_cannot_return (fn))
 460     bitmap_clear (local->statics_written);
 461 }
 462
 463 static bitmap
 464 copy_global_bitmap (bitmap src)
 465 {
 466   bitmap dst;
 467   if (!src)
 468     return NULL;
 469   if (src == all_module_statics)
 470     return all_module_statics;
 471   dst = BITMAP_ALLOC (&optimization_summary_obstack);
 472   bitmap_copy (dst, src);
 473   return dst;
 474 }
 475
 476
 477 /* Called when new clone is inserted to callgraph late.  */
 478
 479 static void
 480 duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst,
 481                      void *data ATTRIBUTE_UNUSED)
 482 {
 483   ipa_reference_optimization_summary_t ginfo;
 484   ipa_reference_optimization_summary_t dst_ginfo;
 485
 486   ginfo = get_reference_optimization_summary (src);
 487   if (!ginfo)
 488     return;
 489   dst_ginfo = XCNEW (struct ipa_reference_optimization_summary_d);
 490   set_reference_optimization_summary (dst, dst_ginfo);
 491   dst_ginfo->statics_not_read = copy_global_bitmap (ginfo->statics_not_read);
 492   dst_ginfo->statics_not_written = copy_global_bitmap (ginfo->statics_not_written);
 493 }
 494
 495 /* Called when node is removed.  */
 496
 497 static void
 498 remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 499 {
 500   ipa_reference_optimization_summary_t ginfo;
 501   ginfo = get_reference_optimization_summary (node);
 502   if (ginfo)
 503     {
 504       if (ginfo->statics_not_read
 505           && ginfo->statics_not_read != all_module_statics)
 506         BITMAP_FREE (ginfo->statics_not_read);
 507
 508       if (ginfo->statics_not_written
 509           && ginfo->statics_not_written != all_module_statics)
 510         BITMAP_FREE (ginfo->statics_not_written);
 511       free (ginfo);
 512       set_reference_optimization_summary (node, NULL);
 513     }
 514 }
 515
 516 /* Analyze each function in the cgraph to see which global or statics
 517    are read or written.  */
 518
 519 static void
 520 generate_summary (void)
 521 {
 522   struct cgraph_node *node;
 523   unsigned int index;
 524   bitmap_iterator bi;
 525   bitmap bm_temp;
 526
 527   ipa_init ();
 528   bm_temp = BITMAP_ALLOC (&local_info_obstack);
 529
 530   /* Process all of the functions next.  */
 531   for (node = cgraph_nodes; node; node = node->next)
 532     if (node->analyzed)
 533       analyze_function (node);
 534
 535   if (dump_file)
 536     EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
 537       {
 538         fprintf (dump_file, "\nPromotable global:%s",
 539                  get_static_name (index));
 540       }
 541
 542   BITMAP_FREE(bm_temp);
 543
 544   if (dump_file)
 545     for (node = cgraph_nodes; node; node = node->next)
 546       if (cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
 547         {
 548           ipa_reference_local_vars_info_t l;
 549           unsigned int index;
 550           bitmap_iterator bi;
 551
 552           l = &get_reference_vars_info (node)->local;
 553           fprintf (dump_file,
 554                    "\nFunction name:%s/%i:",
 555                    cgraph_node_name (node), node->uid);
 556           fprintf (dump_file, "\n  locals read: ");
 557           if (l->statics_read)
 558             EXECUTE_IF_SET_IN_BITMAP (l->statics_read,
 559                                       0, index, bi)
 560               {
 561                 fprintf (dump_file, "%s ",
 562                          get_static_name (index));
 563               }
 564           fprintf (dump_file, "\n  locals written: ");
 565           if (l->statics_written)
 566             EXECUTE_IF_SET_IN_BITMAP (l->statics_written,
 567                                       0, index, bi)
 568               {
 569                 fprintf(dump_file, "%s ",
 570                         get_static_name (index));
 571               }
 572         }
 573 }
 574 \f
 575 /* Set READ_ALL/WRITE_ALL based on decl flags of NODE.  */
 576
 577 static void
 578 read_write_all_from_decl (struct cgraph_node *node, bool * read_all,
 579                           bool * write_all)
 580 {
 581   tree decl = node->decl;
 582   int flags = flags_from_decl_or_type (decl);
 583   if ((flags & ECF_LEAF)
 584       && cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
 585     ;
 586   else if (flags & ECF_CONST)
 587     ;
 588   else if ((flags & ECF_PURE)
 589            || cgraph_node_cannot_return (node))
 590     {
 591       *read_all = true;
 592       if (dump_file && (dump_flags & TDF_DETAILS))
 593          fprintf (dump_file, "   %s/%i -> read all\n",
 594                   cgraph_node_name (node), node->uid);
 595     }
 596   else
 597     {
 598        /* TODO: To be able to produce sane results, we should also handle
 599           common builtins, in particular throw.  */
 600       *read_all = true;
 601       *write_all = true;
 602       if (dump_file && (dump_flags & TDF_DETAILS))
 603          fprintf (dump_file, "   %s/%i -> read all, write all\n",
 604                   cgraph_node_name (node), node->uid);
 605     }
 606 }
 607
 608 /* Produce the global information by preforming a transitive closure
 609    on the local information that was produced by ipa_analyze_function */
 610
 611 static unsigned int
 612 propagate (void)
 613 {
 614   struct cgraph_node *node;
 615   struct cgraph_node *w;
 616   struct cgraph_node **order =
 617     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
 618   int order_pos = ipa_utils_reduced_inorder (order, false, true, NULL);
 619   int i;
 620
 621   if (dump_file)
 622     dump_cgraph (dump_file);
 623
 624   ipa_discover_readonly_nonaddressable_vars ();
 625   generate_summary ();
 626
 627   /* Propagate the local information thru the call graph to produce
 628      the global information.  All the nodes within a cycle will have
 629      the same info so we collapse cycles first.  Then we can do the
 630      propagation in one pass from the leaves to the roots.  */
 631   order_pos = ipa_utils_reduced_inorder (order, true, true, NULL);
 632   if (dump_file)
 633     ipa_utils_print_order(dump_file, "reduced", order, order_pos);
 634
 635   for (i = 0; i < order_pos; i++ )
 636     {
 637       ipa_reference_vars_info_t node_info;
 638       ipa_reference_global_vars_info_t node_g;
 639       ipa_reference_local_vars_info_t node_l;
 640       struct cgraph_edge *e, *ie;
 641
 642       bool read_all;
 643       bool write_all;
 644       struct ipa_dfs_info * w_info;
 645
 646       node = order[i];
 647       node_info = get_reference_vars_info (node);
 648       gcc_assert (node_info);
 649
 650
 651       if (dump_file && (dump_flags & TDF_DETAILS))
 652         fprintf (dump_file, "Starting cycle with %s/%i\n",
 653                   cgraph_node_name (node), node->uid);
 654
 655       node_l = &node_info->local;
 656       node_g = &node_info->global;
 657
 658       read_all = false;
 659       write_all = false;
 660
 661       /* When function is overwritable, we can not assume anything.  */
 662       if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
 663         read_write_all_from_decl (node, &read_all, &write_all);
 664
 665       for (e = node->callees; e; e = e->next_callee)
 666         if (cgraph_function_body_availability (e->callee) <= AVAIL_OVERWRITABLE)
 667           read_write_all_from_decl (e->callee, &read_all, &write_all);
 668
 669       for (ie = node->indirect_calls; ie; ie = ie->next_callee)
 670         if (!(ie->indirect_info->ecf_flags & ECF_CONST))
 671           {
 672             read_all = true;
 673             if (dump_file && (dump_flags & TDF_DETAILS))
 674                fprintf (dump_file, "   indirect call -> read all\n");
 675             if (!cgraph_edge_cannot_lead_to_return (ie)
 676                 && !(ie->indirect_info->ecf_flags & ECF_PURE))
 677               {
 678                 if (dump_file && (dump_flags & TDF_DETAILS))
 679                    fprintf (dump_file, "   indirect call -> write all\n");
 680                 write_all = true;
 681               }
 682           }
 683
 684
 685       /* If any node in a cycle is read_all or write_all
 686          they all are. */
 687       w_info = (struct ipa_dfs_info *) node->aux;
 688       w = w_info->next_cycle;
 689       while (w && (!read_all || !write_all))
 690         {
 691           if (dump_file && (dump_flags & TDF_DETAILS))
 692             fprintf (dump_file, "  Visiting %s/%i\n",
 693                       cgraph_node_name (w), w->uid);
 694           /* When function is overwritable, we can not assume anything.  */
 695           if (cgraph_function_body_availability (w) <= AVAIL_OVERWRITABLE)
 696             read_write_all_from_decl (w, &read_all, &write_all);
 697
 698           for (e = w->callees; e; e = e->next_callee)
 699             if (cgraph_function_body_availability (e->callee) <= AVAIL_OVERWRITABLE)
 700               read_write_all_from_decl (e->callee, &read_all, &write_all);
 701
 702           for (ie = w->indirect_calls; ie; ie = ie->next_callee)
 703             if (!(ie->indirect_info->ecf_flags & ECF_CONST))
 704               {
 705                 read_all = true;
 706                 if (dump_file && (dump_flags & TDF_DETAILS))
 707                    fprintf (dump_file, "   indirect call -> read all\n");
 708                 if (!cgraph_edge_cannot_lead_to_return (ie)
 709                     && !(ie->indirect_info->ecf_flags & ECF_PURE))
 710                   {
 711                     write_all = true;
 712                     if (dump_file && (dump_flags & TDF_DETAILS))
 713                        fprintf (dump_file, "   indirect call -> write all\n");
 714                   }
 715               }
 716
 717           w_info = (struct ipa_dfs_info *) w->aux;
 718           w = w_info->next_cycle;
 719         }
 720
 721
 722       /* Initialized the bitmaps for the reduced nodes */
 723       if (read_all)
 724         node_g->statics_read = all_module_statics;
 725       else
 726         {
 727           node_g->statics_read = BITMAP_ALLOC (&local_info_obstack);
 728           bitmap_copy (node_g->statics_read,
 729                        node_l->statics_read);
 730         }
 731       if (write_all)
 732         node_g->statics_written = all_module_statics;
 733       else
 734         {
 735           node_g->statics_written = BITMAP_ALLOC (&local_info_obstack);
 736           bitmap_copy (node_g->statics_written,
 737                        node_l->statics_written);
 738         }
 739
 740       propagate_bits (node_g, node);
 741       w_info = (struct ipa_dfs_info *) node->aux;
 742       w = w_info->next_cycle;
 743       while (w && (!read_all || !write_all))
 744         {
 745           ipa_reference_vars_info_t w_ri =
 746             get_reference_vars_info (w);
 747           ipa_reference_local_vars_info_t w_l = &w_ri->local;
 748           int flags = flags_from_decl_or_type (w->decl);
 749
 750           /* These global bitmaps are initialized from the local info
 751              of all of the nodes in the region.  However there is no
 752              need to do any work if the bitmaps were set to
 753              all_module_statics.  */
 754           if (!read_all && !(flags & ECF_CONST))
 755             bitmap_ior_into (node_g->statics_read,
 756                              w_l->statics_read);
 757           if (!write_all
 758               && !(flags & ECF_PURE)
 759               && !cgraph_node_cannot_return (w))
 760             bitmap_ior_into (node_g->statics_written,
 761                              w_l->statics_written);
 762           propagate_bits (node_g, w);
 763           w_info = (struct ipa_dfs_info *) w->aux;
 764           w = w_info->next_cycle;
 765         }
 766
 767       /* All nodes within a cycle have the same global info bitmaps.  */
 768       node_info->global = *node_g;
 769       w_info = (struct ipa_dfs_info *) node->aux;
 770       w = w_info->next_cycle;
 771       while (w)
 772         {
 773           ipa_reference_vars_info_t w_ri =
 774             get_reference_vars_info (w);
 775
 776           w_ri->global = *node_g;
 777
 778           w_info = (struct ipa_dfs_info *) w->aux;
 779           w = w_info->next_cycle;
 780         }
 781     }
 782
 783   if (dump_file)
 784     {
 785       for (i = 0; i < order_pos; i++ )
 786         {
 787           ipa_reference_vars_info_t node_info;
 788           ipa_reference_global_vars_info_t node_g;
 789           ipa_reference_local_vars_info_t node_l;
 790           unsigned int index;
 791           bitmap_iterator bi;
 792           struct ipa_dfs_info * w_info;
 793
 794           node = order[i];
 795           node_info = get_reference_vars_info (node);
 796           node_g = &node_info->global;
 797           node_l = &node_info->local;
 798           fprintf (dump_file,
 799                    "\nFunction name:%s/%i:",
 800                    cgraph_node_name (node), node->uid);
 801           fprintf (dump_file, "\n  locals read: ");
 802           if (node_l->statics_read)
 803             EXECUTE_IF_SET_IN_BITMAP (node_l->statics_read,
 804                                       0, index, bi)
 805               {
 806                 fprintf (dump_file, "%s ",
 807                          get_static_name (index));
 808               }
 809           fprintf (dump_file, "\n  locals written: ");
 810           if (node_l->statics_written)
 811             EXECUTE_IF_SET_IN_BITMAP (node_l->statics_written,
 812                                       0, index, bi)
 813               {
 814                 fprintf(dump_file, "%s ",
 815                         get_static_name (index));
 816               }
 817
 818           w_info = (struct ipa_dfs_info *) node->aux;
 819           w = w_info->next_cycle;
 820           while (w)
 821             {
 822               ipa_reference_vars_info_t w_ri =
 823                 get_reference_vars_info (w);
 824               ipa_reference_local_vars_info_t w_l = &w_ri->local;
 825               fprintf (dump_file, "\n  next cycle: %s/%i ",
 826                        cgraph_node_name (w), w->uid);
 827               fprintf (dump_file, "\n    locals read: ");
 828               if (w_l->statics_read)
 829                 EXECUTE_IF_SET_IN_BITMAP (w_l->statics_read,
 830                                           0, index, bi)
 831                   {
 832                     fprintf (dump_file, "%s ",
 833                              get_static_name (index));
 834                   }
 835
 836               fprintf (dump_file, "\n    locals written: ");
 837               if (w_l->statics_written)
 838                 EXECUTE_IF_SET_IN_BITMAP (w_l->statics_written,
 839                                           0, index, bi)
 840                   {
 841                     fprintf (dump_file, "%s ",
 842                              get_static_name (index));
 843                   }
 844
 845               w_info = (struct ipa_dfs_info *) w->aux;
 846               w = w_info->next_cycle;
 847             }
 848           fprintf (dump_file, "\n  globals read: ");
 849           if (node_g->statics_read == all_module_statics)
 850             fprintf (dump_file, "ALL");
 851           else
 852             EXECUTE_IF_SET_IN_BITMAP (node_g->statics_read,
 853                                       0, index, bi)
 854               {
 855                 fprintf (dump_file, "%s ",
 856                          get_static_name (index));
 857               }
 858           fprintf (dump_file, "\n  globals written: ");
 859           if (node_g->statics_written == all_module_statics)
 860             fprintf (dump_file, "ALL");
 861           else
 862             EXECUTE_IF_SET_IN_BITMAP (node_g->statics_written,
 863                                       0, index, bi)
 864               {
 865                 fprintf (dump_file, "%s ",
 866                          get_static_name (index));
 867               }
 868         }
 869     }
 870
 871   /* Cleanup. */
 872   for (node = cgraph_nodes; node; node = node->next)
 873     {
 874       ipa_reference_vars_info_t node_info;
 875       ipa_reference_global_vars_info_t node_g;
 876       ipa_reference_optimization_summary_t opt;
 877
 878       if (!node->analyzed)
 879         continue;
 880
 881       node_info = get_reference_vars_info (node);
 882       if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE
 883           || (flags_from_decl_or_type (node->decl) & ECF_LEAF))
 884         {
 885           node_g = &node_info->global;
 886
 887           opt = XCNEW (struct ipa_reference_optimization_summary_d);
 888           set_reference_optimization_summary (node, opt);
 889
 890           /* Create the complimentary sets.  */
 891
 892           if (bitmap_empty_p (node_g->statics_read))
 893             opt->statics_not_read = all_module_statics;
 894           else
 895             {
 896               opt->statics_not_read
 897                  = BITMAP_ALLOC (&optimization_summary_obstack);
 898               if (node_g->statics_read != all_module_statics)
 899                 bitmap_and_compl (opt->statics_not_read,
 900                                   all_module_statics,
 901                                   node_g->statics_read);
 902             }
 903
 904           if (bitmap_empty_p (node_g->statics_written))
 905             opt->statics_not_written = all_module_statics;
 906           else
 907             {
 908               opt->statics_not_written
 909                 = BITMAP_ALLOC (&optimization_summary_obstack);
 910               if (node_g->statics_written != all_module_statics)
 911                 bitmap_and_compl (opt->statics_not_written,
 912                                   all_module_statics,
 913                                   node_g->statics_written);
 914             }
 915         }
 916       if (node_info)
 917         free (node_info);
 918       if (node->aux)
 919         {
 920           free (node->aux);
 921           node->aux = NULL;
 922         }
 923    }
 924
 925   free (order);
 926
 927   bitmap_obstack_release (&local_info_obstack);
 928   VEC_free (ipa_reference_vars_info_t, heap, ipa_reference_vars_vector);
 929   ipa_reference_vars_vector = NULL;
 930   if (dump_file)
 931     splay_tree_delete (reference_vars_to_consider);
 932   reference_vars_to_consider = NULL;
 933   return 0;
 934 }
 935
 936 /* Return true if we need to write summary of NODE. */
 937
 938 static bool
 939 write_node_summary_p (struct cgraph_node *node,
 940                       cgraph_node_set set,
 941                       varpool_node_set vset,
 942                       bitmap ltrans_statics)
 943 {
 944   ipa_reference_optimization_summary_t info;
 945
 946   /* See if we have (non-empty) info.  */
 947   if (!node->analyzed || node->global.inlined_to)
 948     return false;
 949   info = get_reference_optimization_summary (node);
 950   if (!info || (bitmap_empty_p (info->statics_not_read)
 951                 && bitmap_empty_p (info->statics_not_written)))
 952     return false;
 953
 954   /* See if we want to encode it.
 955      Encode also referenced functions since constant folding might turn it into
 956      a direct call.
 957
 958      In future we might also want to include summaries of functions references
 959      by initializers of constant variables references in current unit.  */
 960   if (!reachable_from_this_partition_p (node, set)
 961       && !referenced_from_this_partition_p (&node->ref_list, set, vset))
 962     return false;
 963
 964   /* See if the info has non-empty intersections with vars we want to encode.  */
 965   if (!bitmap_intersect_p (info->statics_not_read, ltrans_statics)
 966       && !bitmap_intersect_p (info->statics_not_written, ltrans_statics))
 967     return false;
 968   return true;
 969 }
 970
 971 /* Stream out BITS&LTRANS_STATICS as list of decls to OB.
 972    LTRANS_STATICS_BITCOUNT specify number of bits in LTRANS_STATICS
 973    or -1.  When it is positive, just output -1 when
 974    BITS&LTRANS_STATICS == BITS&LTRANS_STATICS.  */
 975
 976 static void
 977 stream_out_bitmap (struct lto_simple_output_block *ob,
 978                    bitmap bits, bitmap ltrans_statics,
 979                    int ltrans_statics_bitcount)
 980 {
 981   int count = 0;
 982   unsigned int index;
 983   bitmap_iterator bi;
 984   if (bits == all_module_statics)
 985     {
 986       lto_output_sleb128_stream (ob->main_stream, -1);
 987       return;
 988     }
 989   EXECUTE_IF_AND_IN_BITMAP (bits, ltrans_statics, 0, index, bi)
 990     count ++;
 991   if (count == ltrans_statics_bitcount)
 992     {
 993       lto_output_sleb128_stream (ob->main_stream, -1);
 994       return;
 995     }
 996   lto_output_sleb128_stream (ob->main_stream, count);
 997   if (!count)
 998     return;
 999   EXECUTE_IF_AND_IN_BITMAP (bits, ltrans_statics, 0, index, bi)
1000     {
1001       tree decl = (tree)splay_tree_lookup (reference_vars_to_consider, index)->value;
1002       lto_output_var_decl_index(ob->decl_state, ob->main_stream, decl);
1003     }
1004 }
1005
1006 /* Serialize the ipa info for lto.  */
1007
1008 static void
1009 ipa_reference_write_optimization_summary (cgraph_node_set set,
1010                                           varpool_node_set vset)
1011 {
1012   struct cgraph_node *node;
1013   struct lto_simple_output_block *ob
1014     = lto_create_simple_output_block (LTO_section_ipa_reference);
1015   unsigned int count = 0;
1016   int ltrans_statics_bitcount = 0;
1017   lto_cgraph_encoder_t encoder = ob->decl_state->cgraph_node_encoder;
1018   lto_varpool_encoder_t varpool_encoder = ob->decl_state->varpool_node_encoder;
1019   bitmap ltrans_statics = BITMAP_ALLOC (NULL);
1020   int i;
1021
1022   reference_vars_to_consider = splay_tree_new (splay_tree_compare_ints, 0, 0);
1023
1024   /* See what variables we are interested in.  */
1025   for (i = 0; i < lto_varpool_encoder_size (varpool_encoder); i++)
1026     {
1027       struct varpool_node *vnode = lto_varpool_encoder_deref (varpool_encoder, i);
1028       if (!vnode->externally_visible
1029           && vnode->analyzed
1030           && bitmap_bit_p (all_module_statics, DECL_UID (vnode->decl))
1031           && referenced_from_this_partition_p (&vnode->ref_list, set, vset))
1032         {
1033           tree decl = vnode->decl;
1034           bitmap_set_bit (ltrans_statics, DECL_UID (decl));
1035           splay_tree_insert (reference_vars_to_consider,
1036                              DECL_UID (decl), (splay_tree_value)decl);
1037           ltrans_statics_bitcount ++;
1038         }
1039     }
1040
1041
1042   if (ltrans_statics_bitcount)
1043     for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
1044       if (write_node_summary_p (lto_cgraph_encoder_deref (encoder, i),
1045                                 set, vset, ltrans_statics))
1046           count++;
1047
1048   lto_output_uleb128_stream (ob->main_stream, count);
1049   if (count)
1050     stream_out_bitmap (ob, ltrans_statics, ltrans_statics,
1051                        -1);
1052
1053   /* Process all of the functions.  */
1054   if (ltrans_statics_bitcount)
1055     for (i = 0; i < lto_cgraph_encoder_size (encoder); i++)
1056       {
1057         node = lto_cgraph_encoder_deref (encoder, i);
1058         if (write_node_summary_p (node, set, vset, ltrans_statics))
1059           {
1060             ipa_reference_optimization_summary_t info;
1061             int node_ref;
1062
1063             info = get_reference_optimization_summary (node);
1064             node_ref = lto_cgraph_encoder_encode (encoder, node);
1065             lto_output_uleb128_stream (ob->main_stream, node_ref);
1066
1067             stream_out_bitmap (ob, info->statics_not_read, ltrans_statics,
1068                                ltrans_statics_bitcount);
1069             stream_out_bitmap (ob, info->statics_not_written, ltrans_statics,
1070                                ltrans_statics_bitcount);
1071           }
1072       }
1073   BITMAP_FREE (ltrans_statics);
1074   lto_destroy_simple_output_block (ob);
1075   splay_tree_delete (reference_vars_to_consider);
1076 }
1077
1078 /* Deserialize the ipa info for lto.  */
1079
1080 static void
1081 ipa_reference_read_optimization_summary (void)
1082 {
1083   struct lto_file_decl_data ** file_data_vec
1084     = lto_get_file_decl_data ();
1085   struct lto_file_decl_data * file_data;
1086   unsigned int j = 0;
1087   bitmap_obstack_initialize (&optimization_summary_obstack);
1088
1089   node_removal_hook_holder =
1090       cgraph_add_node_removal_hook (&remove_node_data, NULL);
1091   node_duplication_hook_holder =
1092       cgraph_add_node_duplication_hook (&duplicate_node_data, NULL);
1093   all_module_statics = BITMAP_ALLOC (&optimization_summary_obstack);
1094
1095   while ((file_data = file_data_vec[j++]))
1096     {
1097       const char *data;
1098       size_t len;
1099       struct lto_input_block *ib
1100         = lto_create_simple_input_block (file_data,
1101                                          LTO_section_ipa_reference,
1102                                          &data, &len);
1103       if (ib)
1104         {
1105           unsigned int i;
1106           unsigned int f_count = lto_input_uleb128 (ib);
1107           int b_count;
1108           if (!f_count)
1109             continue;
1110           b_count = lto_input_sleb128 (ib);
1111           if (dump_file)
1112             fprintf (dump_file, "all module statics:");
1113           for (i = 0; i < (unsigned int)b_count; i++)
1114             {
1115               unsigned int var_index = lto_input_uleb128 (ib);
1116               tree v_decl = lto_file_decl_data_get_var_decl (file_data,
1117                                                              var_index);
1118               bitmap_set_bit (all_module_statics, DECL_UID (v_decl));
1119               if (dump_file)
1120                 fprintf (dump_file, " %s",
1121                          lang_hooks.decl_printable_name (v_decl, 2));
1122             }
1123
1124           for (i = 0; i < f_count; i++)
1125             {
1126               unsigned int j, index;
1127               struct cgraph_node *node;
1128               ipa_reference_optimization_summary_t info;
1129               int v_count;
1130               lto_cgraph_encoder_t encoder;
1131
1132               index = lto_input_uleb128 (ib);
1133               encoder = file_data->cgraph_node_encoder;
1134               node = lto_cgraph_encoder_deref (encoder, index);
1135               info = XCNEW (struct ipa_reference_optimization_summary_d);
1136               set_reference_optimization_summary (node, info);
1137               info->statics_not_read = BITMAP_ALLOC (&optimization_summary_obstack);
1138               info->statics_not_written = BITMAP_ALLOC (&optimization_summary_obstack);
1139               if (dump_file)
1140                 fprintf (dump_file,
1141                          "\nFunction name:%s/%i:\n  static not read:",
1142                          cgraph_node_name (node), node->uid);
1143
1144               /* Set the statics not read.  */
1145               v_count = lto_input_sleb128 (ib);
1146               if (v_count == -1)
1147                 {
1148                   info->statics_not_read = all_module_statics;
1149                   if (dump_file)
1150                     fprintf (dump_file, " all module statics");
1151                 }
1152               else
1153                 for (j = 0; j < (unsigned int)v_count; j++)
1154                   {
1155                     unsigned int var_index = lto_input_uleb128 (ib);
1156                     tree v_decl = lto_file_decl_data_get_var_decl (file_data,
1157                                                                    var_index);
1158                     bitmap_set_bit (info->statics_not_read, DECL_UID (v_decl));
1159                     if (dump_file)
1160                       fprintf (dump_file, " %s",
1161                                lang_hooks.decl_printable_name (v_decl, 2));
1162                   }
1163
1164               if (dump_file)
1165                 fprintf (dump_file,
1166                          "\n  static not written:");
1167               /* Set the statics not written.  */
1168               v_count = lto_input_sleb128 (ib);
1169               if (v_count == -1)
1170                 {
1171                   info->statics_not_written = all_module_statics;
1172                   if (dump_file)
1173                     fprintf (dump_file, " all module statics");
1174                 }
1175               else
1176                 for (j = 0; j < (unsigned int)v_count; j++)
1177                   {
1178                     unsigned int var_index = lto_input_uleb128 (ib);
1179                     tree v_decl = lto_file_decl_data_get_var_decl (file_data,
1180                                                                    var_index);
1181                     bitmap_set_bit (info->statics_not_written, DECL_UID (v_decl));
1182                     if (dump_file)
1183                       fprintf (dump_file, " %s",
1184                                lang_hooks.decl_printable_name (v_decl, 2));
1185                   }
1186               if (dump_file)
1187                 fprintf (dump_file, "\n");
1188             }
1189
1190           lto_destroy_simple_input_block (file_data,
1191                                           LTO_section_ipa_reference,
1192                                           ib, data, len);
1193         }
1194       else
1195         /* Fatal error here.  We do not want to support compiling ltrans units with
1196            different version of compiler or different flags than the WPA unit, so
1197            this should never happen.  */
1198         fatal_error ("ipa reference summary is missing in ltrans unit");
1199     }
1200 }
1201
1202 static bool
1203 gate_reference (void)
1204 {
1205   return (flag_ipa_reference
1206           /* Don't bother doing anything if the program has errors.  */
1207           && !seen_error ());
1208 }
1209
1210 struct ipa_opt_pass_d pass_ipa_reference =
1211 {
1212  {
1213   IPA_PASS,
1214   "static-var",                         /* name */
1215   gate_reference,                       /* gate */
1216   propagate,                            /* execute */
1217   NULL,                                 /* sub */
1218   NULL,                                 /* next */
1219   0,                                    /* static_pass_number */
1220   TV_IPA_REFERENCE,                     /* tv_id */
1221   0,                                    /* properties_required */
1222   0,                                    /* properties_provided */
1223   0,                                    /* properties_destroyed */
1224   0,                                    /* todo_flags_start */
1225   0                                     /* todo_flags_finish */
1226  },
1227  NULL,                                  /* generate_summary */
1228  NULL,                                  /* write_summary */
1229  NULL,                                  /* read_summary */
1230  ipa_reference_write_optimization_summary,/* write_optimization_summary */
1231  ipa_reference_read_optimization_summary,/* read_optimization_summary */
1232  NULL,                                  /* stmt_fixup */
1233  0,                                     /* TODOs */
1234  NULL,                                  /* function_transform */
1235  NULL                                   /* variable_transform */
1236 };