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