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