gcc/ipa-reference.c

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