gcc/ipa-reference.c

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