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