gcc/ipa-reference.c

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