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