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    There are two categories of information produced by this pass:
  26
  27    1) The addressable (TREE_ADDRESSABLE) bit and readonly
  28    (TREE_READONLY) bit associated with these variables is properly set
  29    based on scanning all of the code withing the compilation unit.
  30
  31    2) The transitive call site specific clobber effects are computed
  32    for the variables whose scope is contained within this compilation
  33    unit.
  34
  35    First each function and static variable initialization is analyzed
  36    to determine which local static variables are either read, written,
  37    or have their address taken.  Any local static that has its address
  38    taken is removed from consideration.  Once the local read and
  39    writes are determined, a transitive closure of this information is
  40    performed over the call graph to determine the worst case set of
  41    side effects of each call.  In later parts of the compiler, these
  42    local and global sets are examined to make the call clobbering less
  43    traumatic, promote some statics to registers, and improve aliasing
  44    information.
  45
  46    Currently must be run after inlining decisions have been made since
  47    otherwise, the local sets will not contain information that is
  48    consistent with post inlined state.  The global sets are not prone
  49    to this problem since they are by definition transitive.  */
  50
  51 #include "config.h"
  52 #include "system.h"
  53 #include "coretypes.h"
  54 #include "tm.h"
  55 #include "tree.h"
  56 #include "tree-flow.h"
  57 #include "tree-inline.h"
  58 #include "tree-pass.h"
  59 #include "langhooks.h"
  60 #include "pointer-set.h"
  61 #include "splay-tree.h"
  62 #include "ggc.h"
  63 #include "ipa-utils.h"
  64 #include "ipa-reference.h"
  65 #include "gimple.h"
  66 #include "cgraph.h"
  67 #include "output.h"
  68 #include "flags.h"
  69 #include "timevar.h"
  70 #include "diagnostic.h"
  71 #include "langhooks.h"
  72 #include "lto-streamer.h"
  73
  74 static void remove_node_data (struct cgraph_node *node,
  75                               void *data ATTRIBUTE_UNUSED);
  76 static void duplicate_node_data (struct cgraph_node *src,
  77                                  struct cgraph_node *dst,
  78                                  void *data ATTRIBUTE_UNUSED);
  79
  80 /* The static variables defined within the compilation unit that are
  81    loaded or stored directly by function that owns this structure.  */
  82
  83 struct ipa_reference_local_vars_info_d
  84 {
  85   bitmap statics_read;
  86   bitmap statics_written;
  87
  88   /* Set when this function calls another function external to the
  89      compilation unit or if the function has a asm clobber of memory.
  90      In general, such calls are modeled as reading and writing all
  91      variables (both bits on) but sometime there are attributes on the
  92      called function so we can do better.  */
  93   bool calls_read_all;
  94   bool calls_write_all;
  95 };
  96
  97 /* Statics that are read and written by some set of functions. The
  98    local ones are based on the loads and stores local to the function.
  99    The global ones are based on the local info as well as the
 100    transitive closure of the functions that are called.  The
 101    structures are separated to allow the global structures to be
 102    shared between several functions since every function within a
 103    strongly connected component will have the same information.  This
 104    sharing saves both time and space in the computation of the vectors
 105    as well as their translation from decl_uid form to ann_uid
 106    form.  */
 107
 108 struct ipa_reference_global_vars_info_d
 109 {
 110   bitmap statics_read;
 111   bitmap statics_written;
 112   bitmap statics_not_read;
 113   bitmap statics_not_written;
 114 };
 115
 116 typedef struct ipa_reference_local_vars_info_d *ipa_reference_local_vars_info_t;
 117 typedef struct ipa_reference_global_vars_info_d *ipa_reference_global_vars_info_t;
 118 struct ipa_reference_vars_info_d
 119 {
 120   ipa_reference_local_vars_info_t local;
 121   ipa_reference_global_vars_info_t global;
 122 };
 123
 124 typedef struct ipa_reference_vars_info_d *ipa_reference_vars_info_t;
 125
 126 /* This splay tree contains all of the static variables that are
 127    being considered by the compilation level alias analysis.  For
 128    module_at_a_time compilation, this is the set of static but not
 129    public variables.  Any variables that either have their address
 130    taken or participate in otherwise unsavory operations are deleted
 131    from this list.  */
 132 static GTY((param1_is(int), param2_is(tree)))
 133      splay_tree reference_vars_to_consider;
 134
 135 /* This bitmap is used to knock out the module static variables whose
 136    addresses have been taken and passed around.  */
 137 static bitmap module_statics_escape;
 138
 139 /* This bitmap is used to knock out the module static variables that
 140    are not readonly.  */
 141 static bitmap module_statics_written;
 142
 143 /* A bit is set for every module static we are considering.  This is
 144    ored into the local info when asm code is found that clobbers all
 145    memory. */
 146 static bitmap all_module_statics;
 147
 148 /* Obstack holding bitmaps of local analysis (live from analysis to
 149    propagation)  */
 150 static bitmap_obstack local_info_obstack;
 151 /* Obstack holding global analysis live forever.  */
 152 static bitmap_obstack global_info_obstack;
 153
 154 /* Holders of ipa cgraph hooks: */
 155 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
 156 static struct cgraph_node_hook_list *node_removal_hook_holder;
 157
 158 enum initialization_status_t
 159 {
 160   UNINITIALIZED,
 161   RUNNING,
 162   FINISHED
 163 };
 164
 165 tree memory_identifier_string;
 166
 167 /* Vector where the reference var infos are actually stored. */
 168 DEF_VEC_P (ipa_reference_vars_info_t);
 169 DEF_VEC_ALLOC_P (ipa_reference_vars_info_t, heap);
 170 static VEC (ipa_reference_vars_info_t, heap) *ipa_reference_vars_vector;
 171
 172 /* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
 173 static inline ipa_reference_vars_info_t
 174 get_reference_vars_info (struct cgraph_node *node)
 175 {
 176   if (!ipa_reference_vars_vector
 177       || VEC_length (ipa_reference_vars_info_t, ipa_reference_vars_vector) <= (unsigned int)node->uid)
 178     return NULL;
 179   return VEC_index (ipa_reference_vars_info_t, ipa_reference_vars_vector, node->uid);
 180 }
 181
 182 /* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
 183 static inline void
 184 set_reference_vars_info (struct cgraph_node *node, ipa_reference_vars_info_t info)
 185 {
 186   if (!ipa_reference_vars_vector
 187       || VEC_length (ipa_reference_vars_info_t, ipa_reference_vars_vector) <= (unsigned int)node->uid)
 188      VEC_safe_grow_cleared (ipa_reference_vars_info_t, heap, ipa_reference_vars_vector, node->uid + 1);
 189   VEC_replace (ipa_reference_vars_info_t, ipa_reference_vars_vector, node->uid, info);
 190 }
 191
 192 /* Get a bitmap that contains all of the globally referenced static
 193    variables for function FN.  */
 194
 195 static ipa_reference_global_vars_info_t
 196 get_global_reference_vars_info (struct cgraph_node *fn)
 197 {
 198   ipa_reference_vars_info_t info = get_reference_vars_info (fn);
 199
 200   if (info)
 201     return info->global;
 202   else
 203     /* This phase was not run.  */
 204     return NULL;
 205 }
 206
 207 /* Return a bitmap indexed by VAR_DECL uid for the static variables
 208    that are read during the execution of the function FN.  Returns
 209    NULL if no data is available.  */
 210
 211 bitmap
 212 ipa_reference_get_read_global (struct cgraph_node *fn)
 213 {
 214   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
 215   if (g)
 216     return g->statics_read;
 217   else
 218     return NULL;
 219 }
 220
 221 /* Return a bitmap indexed by VAR_DECL uid for the static variables
 222    that are written during the execution of the function FN.  Note
 223    that variables written may or may not be read during the function
 224    call.  Returns NULL if no data is available.  */
 225
 226 bitmap
 227 ipa_reference_get_written_global (struct cgraph_node *fn)
 228 {
 229   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
 230   if (g)
 231     return g->statics_written;
 232   else
 233     return NULL;
 234 }
 235
 236 /* Return a bitmap indexed by_DECL_UID uid for the static variables
 237    that are not read during the execution of the function FN.  Returns
 238    NULL if no data is available.  */
 239
 240 bitmap
 241 ipa_reference_get_not_read_global (struct cgraph_node *fn)
 242 {
 243   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
 244   if (g)
 245     return g->statics_not_read;
 246   else
 247     return NULL;
 248 }
 249
 250 /* Return a bitmap indexed by DECL_UID uid for the static variables
 251    that are not written during the execution of the function FN.  Note
 252    that variables written may or may not be read during the function
 253    call.  Returns NULL if no data is available.  */
 254
 255 bitmap
 256 ipa_reference_get_not_written_global (struct cgraph_node *fn)
 257 {
 258   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
 259   if (g)
 260     return g->statics_not_written;
 261   else
 262     return NULL;
 263 }
 264
 265 \f
 266
 267 /* Add VAR to all_module_statics and the two
 268    reference_vars_to_consider* sets.  */
 269
 270 static inline void
 271 add_static_var (tree var)
 272 {
 273   int uid = DECL_UID (var);
 274   gcc_assert (TREE_CODE (var) == VAR_DECL);
 275   if (!bitmap_bit_p (all_module_statics, uid))
 276     {
 277       splay_tree_insert (reference_vars_to_consider,
 278                          uid, (splay_tree_value)var);
 279       bitmap_set_bit (all_module_statics, uid);
 280     }
 281 }
 282
 283 /* Return true if the variable T is the right kind of static variable to
 284    perform compilation unit scope escape analysis.  */
 285
 286 static inline bool
 287 is_proper_for_analysis (tree t)
 288 {
 289   /* If the variable has the "used" attribute, treat it as if it had a
 290      been touched by the devil.  */
 291   if (DECL_PRESERVE_P (t))
 292     return false;
 293
 294   /* Do not want to do anything with volatile except mark any
 295      function that uses one to be not const or pure.  */
 296   if (TREE_THIS_VOLATILE (t))
 297     return false;
 298
 299   /* We cannot touch decls where the type needs constructing.  */
 300   if (TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (t)))
 301     return false;
 302
 303   /* This is a variable we care about.  Check if we have seen it
 304      before, and if not add it the set of variables we care about.  */
 305   if (!bitmap_bit_p (all_module_statics, DECL_UID (t)))
 306     add_static_var (t);
 307
 308   return true;
 309 }
 310
 311 /* Lookup the tree node for the static variable that has UID.  */
 312 static tree
 313 get_static_decl (int index)
 314 {
 315   splay_tree_node stn =
 316     splay_tree_lookup (reference_vars_to_consider, index);
 317   if (stn)
 318     return (tree)stn->value;
 319   return NULL;
 320 }
 321
 322 /* Lookup the tree node for the static variable that has UID and
 323    convert the name to a string for debugging.  */
 324
 325 static const char *
 326 get_static_name (int index)
 327 {
 328   splay_tree_node stn =
 329     splay_tree_lookup (reference_vars_to_consider, index);
 330   if (stn)
 331     return lang_hooks.decl_printable_name ((tree)(stn->value), 2);
 332   return NULL;
 333 }
 334
 335 /* Or in all of the bits from every callee of X into X_GLOBAL, the caller's cycle,
 336    bit vector.  There are several cases to check to avoid the sparse
 337    bitmap oring.  */
 338
 339 static void
 340 propagate_bits (ipa_reference_global_vars_info_t x_global, struct cgraph_node *x)
 341 {
 342   struct cgraph_edge *e;
 343   for (e = x->callees; e; e = e->next_callee)
 344     {
 345       struct cgraph_node *y = e->callee;
 346
 347       /* Only look into nodes we can propagate something.  */
 348       if (cgraph_function_body_availability (e->callee) > AVAIL_OVERWRITABLE)
 349         {
 350           if (get_reference_vars_info (y))
 351             {
 352               ipa_reference_vars_info_t y_info
 353                 = get_reference_vars_info (y);
 354               ipa_reference_global_vars_info_t y_global = y_info->global;
 355
 356               /* Calls in current cycle do not have global computed yet.  */
 357               if (!y_info->global)
 358                 continue;
 359
 360               if (x_global->statics_read
 361                   != all_module_statics)
 362                 {
 363                   if (y_global->statics_read
 364                       == all_module_statics)
 365                     {
 366                       BITMAP_FREE (x_global->statics_read);
 367                       x_global->statics_read
 368                         = all_module_statics;
 369                     }
 370                   /* Skip bitmaps that are pointer equal to node's bitmap
 371                      (no reason to spin within the cycle).  */
 372                   else if (x_global->statics_read
 373                            != y_global->statics_read)
 374                     bitmap_ior_into (x_global->statics_read,
 375                                      y_global->statics_read);
 376                 }
 377
 378               if (x_global->statics_written
 379                   != all_module_statics)
 380                 {
 381                   if (y_global->statics_written
 382                       == all_module_statics)
 383                     {
 384                       BITMAP_FREE (x_global->statics_written);
 385                       x_global->statics_written
 386                         = all_module_statics;
 387                     }
 388                   /* Skip bitmaps that are pointer equal to node's bitmap
 389                      (no reason to spin within the cycle).  */
 390                   else if (x_global->statics_written
 391                            != y_global->statics_written)
 392                     bitmap_ior_into (x_global->statics_written,
 393                                      y_global->statics_written);
 394                 }
 395             }
 396           else
 397             gcc_unreachable ();
 398         }
 399     }
 400 }
 401
 402 /* The init routine for analyzing global static variable usage.  See
 403    comments at top for description.  */
 404 static void
 405 ipa_init (void)
 406 {
 407   static bool init_p = false;
 408
 409   if (init_p)
 410     return;
 411
 412   init_p = true;
 413
 414   memory_identifier_string = build_string(7, "memory");
 415
 416   reference_vars_to_consider =
 417     splay_tree_new_ggc (splay_tree_compare_ints);
 418
 419   bitmap_obstack_initialize (&local_info_obstack);
 420   bitmap_obstack_initialize (&global_info_obstack);
 421   module_statics_escape = BITMAP_ALLOC (&local_info_obstack);
 422   module_statics_written = BITMAP_ALLOC (&local_info_obstack);
 423   all_module_statics = BITMAP_ALLOC (&global_info_obstack);
 424
 425   node_removal_hook_holder =
 426       cgraph_add_node_removal_hook (&remove_node_data, NULL);
 427   node_duplication_hook_holder =
 428       cgraph_add_node_duplication_hook (&duplicate_node_data, NULL);
 429 }
 430
 431 /* Check out the rhs of a static or global initialization VNODE to see
 432    if any of them contain addressof operations.  Note that some of
 433    these variables may  not even be referenced in the code in this
 434    compilation unit but their right hand sides may contain references
 435    to variables defined within this unit.  */
 436
 437 static void
 438 analyze_variable (struct varpool_node *vnode)
 439 {
 440   int i;
 441   struct ipa_ref *ref;
 442   for (i = 0; ipa_ref_list_reference_iterate (&vnode->ref_list, i, ref); i++)
 443     {
 444       tree var;
 445       if (ref->refered_type != IPA_REF_VARPOOL)
 446         continue;
 447       var = ipa_ref_varpool_node (ref)->decl;
 448       if (ipa_ref_varpool_node (ref)->externally_visible
 449           || !ipa_ref_varpool_node (ref)->analyzed
 450           || !is_proper_for_analysis (var))
 451         continue;
 452       switch (ref->use)
 453         {
 454         case IPA_REF_LOAD:
 455         case IPA_REF_STORE:
 456           gcc_unreachable ();
 457           break;
 458         case IPA_REF_ADDR:
 459           bitmap_set_bit (module_statics_escape, DECL_UID (var));
 460           break;
 461         }
 462     }
 463 }
 464
 465
 466 /* Set up the persistent info for FN.  */
 467
 468 static ipa_reference_local_vars_info_t
 469 init_function_info (struct cgraph_node *fn)
 470 {
 471   ipa_reference_vars_info_t info
 472     = XCNEW (struct ipa_reference_vars_info_d);
 473   ipa_reference_local_vars_info_t l
 474     = XCNEW (struct ipa_reference_local_vars_info_d);
 475
 476   /* Add the info to the tree's annotation.  */
 477   set_reference_vars_info (fn, info);
 478
 479   info->local = l;
 480   l->statics_read = BITMAP_ALLOC (&local_info_obstack);
 481   l->statics_written = BITMAP_ALLOC (&local_info_obstack);
 482
 483   return l;
 484 }
 485
 486
 487 /* This is the main routine for finding the reference patterns for
 488    global variables within a function FN.  */
 489
 490 static void
 491 analyze_function (struct cgraph_node *fn)
 492 {
 493   ipa_reference_local_vars_info_t local;
 494   struct ipa_ref *ref;
 495   int i;
 496   tree var;
 497   struct cgraph_edge *ie;
 498
 499   local = init_function_info (fn);
 500   /* Process indirect calls.  All direct calles are handled at propagation
 501      time.  */
 502   for (ie = fn->indirect_calls; ie; ie = ie->next_callee)
 503     if (!(ie->indirect_info->ecf_flags & ECF_CONST))
 504       {
 505         local->calls_read_all = true;
 506         if (!(ie->indirect_info->ecf_flags & ECF_PURE)
 507             && ((ie->indirect_info->ecf_flags & (ECF_NOTHROW | ECF_NORETURN))
 508                 !=  (ECF_NOTHROW | ECF_NORETURN)))
 509           local->calls_write_all = true;
 510       }
 511   for (i = 0; ipa_ref_list_reference_iterate (&fn->ref_list, i, ref); i++)
 512     {
 513       if (ref->refered_type != IPA_REF_VARPOOL)
 514         continue;
 515       var = ipa_ref_varpool_node (ref)->decl;
 516       if (ipa_ref_varpool_node (ref)->externally_visible
 517           || !ipa_ref_varpool_node (ref)->analyzed
 518           || !is_proper_for_analysis (var))
 519         continue;
 520       switch (ref->use)
 521         {
 522         case IPA_REF_LOAD:
 523           bitmap_set_bit (local->statics_read, DECL_UID (var));
 524           break;
 525         case IPA_REF_STORE:
 526           bitmap_set_bit (local->statics_written, DECL_UID (var));
 527           bitmap_set_bit (module_statics_written, DECL_UID (var));
 528           break;
 529         case IPA_REF_ADDR:
 530           bitmap_set_bit (module_statics_escape, DECL_UID (var));
 531           break;
 532         }
 533     }
 534
 535   if ((flags_from_decl_or_type (fn->decl) & (ECF_NOTHROW | ECF_NORETURN))
 536       == (ECF_NOTHROW | ECF_NORETURN))
 537     {
 538       local->calls_write_all = false;
 539       bitmap_clear (local->statics_written);
 540     }
 541
 542   /* Free bitmaps of direct references if we can not use them anyway.  */
 543   if (local->calls_write_all)
 544     BITMAP_FREE (local->statics_written);
 545   if (local->calls_read_all)
 546     BITMAP_FREE (local->statics_read);
 547 }
 548
 549 /* Remove local data associated with function FN.  */
 550 static void
 551 clean_function_local_data (struct cgraph_node *fn)
 552 {
 553   ipa_reference_vars_info_t info = get_reference_vars_info (fn);
 554   ipa_reference_local_vars_info_t l = info->local;
 555   if (l)
 556     {
 557       if (l->statics_read
 558           && l->statics_read != all_module_statics)
 559         BITMAP_FREE (l->statics_read);
 560       if (l->statics_written
 561           &&l->statics_written != all_module_statics)
 562         BITMAP_FREE (l->statics_written);
 563       free (l);
 564       info->local = NULL;
 565     }
 566 }
 567
 568 /* Remove all data associated with function FN.  */
 569
 570 static void
 571 clean_function (struct cgraph_node *fn)
 572 {
 573   ipa_reference_vars_info_t info = get_reference_vars_info (fn);
 574   ipa_reference_global_vars_info_t g = info->global;
 575
 576   clean_function_local_data (fn);
 577   if (g)
 578     {
 579       if (g->statics_read
 580           && g->statics_read != all_module_statics)
 581         BITMAP_FREE (g->statics_read);
 582
 583       if (g->statics_written
 584           && g->statics_written != all_module_statics)
 585         BITMAP_FREE (g->statics_written);
 586
 587       if (g->statics_not_read
 588           && g->statics_not_read != all_module_statics)
 589         BITMAP_FREE (g->statics_not_read);
 590
 591       if (g->statics_not_written
 592           && g->statics_not_written != all_module_statics)
 593         BITMAP_FREE (g->statics_not_written);
 594       free (g);
 595       info->global = NULL;
 596     }
 597
 598   free (get_reference_vars_info (fn));
 599   set_reference_vars_info (fn, NULL);
 600 }
 601
 602 static bitmap
 603 copy_global_bitmap (bitmap src)
 604 {
 605   bitmap dst;
 606   if (!src)
 607     return NULL;
 608   if (src == all_module_statics)
 609     return all_module_statics;
 610   dst = BITMAP_ALLOC (&global_info_obstack);
 611   bitmap_copy (dst, src);
 612   return dst;
 613 }
 614
 615
 616 /* Called when new clone is inserted to callgraph late.  */
 617
 618 static void
 619 duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst,
 620                      void *data ATTRIBUTE_UNUSED)
 621 {
 622   ipa_reference_global_vars_info_t ginfo;
 623   ipa_reference_global_vars_info_t dst_ginfo;
 624
 625   ginfo = get_global_reference_vars_info (src);
 626   if (!ginfo)
 627     return;
 628   init_function_info (dst);
 629   if (ginfo)
 630     {
 631       get_reference_vars_info (dst)->global = XCNEW (struct ipa_reference_global_vars_info_d);
 632       dst_ginfo = get_global_reference_vars_info (dst);
 633       dst_ginfo->statics_read = copy_global_bitmap (ginfo->statics_read);
 634       dst_ginfo->statics_written = copy_global_bitmap (ginfo->statics_written);
 635       dst_ginfo->statics_not_read = copy_global_bitmap (ginfo->statics_not_read);
 636       dst_ginfo->statics_not_written = copy_global_bitmap (ginfo->statics_not_written);
 637     }
 638 }
 639
 640 /* Called when node is removed.  */
 641
 642 static void
 643 remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 644 {
 645   if (get_reference_vars_info (node))
 646     clean_function (node);
 647 }
 648
 649 /* Analyze each function in the cgraph to see which global or statics
 650    are read or written.  */
 651
 652 static void
 653 generate_summary (void)
 654 {
 655   struct cgraph_node *node;
 656   struct varpool_node *vnode;
 657   unsigned int index;
 658   bitmap_iterator bi;
 659   bitmap module_statics_readonly;
 660   bitmap bm_temp;
 661
 662   ipa_init ();
 663   module_statics_readonly = BITMAP_ALLOC (&local_info_obstack);
 664   bm_temp = BITMAP_ALLOC (&local_info_obstack);
 665
 666   /* Process all of the variables first.  */
 667   FOR_EACH_STATIC_INITIALIZER (vnode)
 668     analyze_variable (vnode);
 669
 670   /* Process all of the functions next.  */
 671   for (node = cgraph_nodes; node; node = node->next)
 672     if (node->analyzed)
 673       analyze_function (node);
 674
 675   /* Prune out the variables that were found to behave badly
 676      (i.e. have their address taken).  */
 677   EXECUTE_IF_SET_IN_BITMAP (module_statics_escape, 0, index, bi)
 678     {
 679       splay_tree_remove (reference_vars_to_consider, index);
 680     }
 681
 682   bitmap_and_compl_into (all_module_statics,
 683                          module_statics_escape);
 684
 685   bitmap_and_compl (module_statics_readonly, all_module_statics,
 686                     module_statics_written);
 687
 688   /* If the address is not taken, we can unset the addressable bit
 689      on this variable.  */
 690   EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
 691     {
 692       tree var = get_static_decl (index);
 693       TREE_ADDRESSABLE (var) = 0;
 694       if (dump_file)
 695         fprintf (dump_file, "Not TREE_ADDRESSABLE var %s\n",
 696                  get_static_name (index));
 697     }
 698
 699   /* If the variable is never written, we can set the TREE_READONLY
 700      flag.  Additionally if it has a DECL_INITIAL that is made up of
 701      constants we can treat the entire global as a constant.  */
 702
 703   bitmap_and_compl (module_statics_readonly, all_module_statics,
 704                     module_statics_written);
 705   EXECUTE_IF_SET_IN_BITMAP (module_statics_readonly, 0, index, bi)
 706     {
 707       tree var = get_static_decl (index);
 708
 709       /* Ignore variables in named sections - changing TREE_READONLY
 710          changes the section flags, potentially causing conflicts with
 711          other variables in the same named section.  */
 712       if (DECL_SECTION_NAME (var) == NULL_TREE)
 713         {
 714           TREE_READONLY (var) = 1;
 715           if (dump_file)
 716             fprintf (dump_file, "read-only var %s\n",
 717                      get_static_name (index));
 718         }
 719     }
 720
 721   BITMAP_FREE(module_statics_escape);
 722   BITMAP_FREE(module_statics_written);
 723   module_statics_escape = NULL;
 724   module_statics_written = NULL;
 725
 726   if (dump_file)
 727     EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
 728       {
 729         fprintf (dump_file, "\nPromotable global:%s",
 730                  get_static_name (index));
 731       }
 732
 733   for (node = cgraph_nodes; node; node = node->next)
 734     if (cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
 735       {
 736         ipa_reference_local_vars_info_t l;
 737         l = get_reference_vars_info (node)->local;
 738
 739         /* Any variables that are not in all_module_statics are
 740            removed from the local maps.  This will include all of the
 741            variables that were found to escape in the function
 742            scanning.  */
 743         if (l->statics_read)
 744           bitmap_and_into (l->statics_read,
 745                            all_module_statics);
 746         if (l->statics_written)
 747           bitmap_and_into (l->statics_written,
 748                            all_module_statics);
 749       }
 750
 751   BITMAP_FREE(module_statics_readonly);
 752   BITMAP_FREE(bm_temp);
 753
 754   if (dump_file)
 755     for (node = cgraph_nodes; node; node = node->next)
 756       if (cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
 757         {
 758           ipa_reference_local_vars_info_t l;
 759           unsigned int index;
 760           bitmap_iterator bi;
 761
 762           l = get_reference_vars_info (node)->local;
 763           fprintf (dump_file,
 764                    "\nFunction name:%s/%i:",
 765                    cgraph_node_name (node), node->uid);
 766           fprintf (dump_file, "\n  locals read: ");
 767           if (l->statics_read)
 768             EXECUTE_IF_SET_IN_BITMAP (l->statics_read,
 769                                       0, index, bi)
 770               {
 771                 fprintf (dump_file, "%s ",
 772                          get_static_name (index));
 773               }
 774           fprintf (dump_file, "\n  locals written: ");
 775           if (l->statics_written)
 776             EXECUTE_IF_SET_IN_BITMAP (l->statics_written,
 777                                       0, index, bi)
 778               {
 779                 fprintf(dump_file, "%s ",
 780                         get_static_name (index));
 781               }
 782           if (l->calls_read_all)
 783              fprintf (dump_file, "\n  calls read all: ");
 784           if (l->calls_write_all)
 785              fprintf (dump_file, "\n  calls read all: ");
 786         }
 787 }
 788 \f
 789 /* Set READ_ALL/WRITE_ALL based on DECL flags.  */
 790 static void
 791 read_write_all_from_decl (tree decl, bool * read_all, bool * write_all)
 792 {
 793   int flags = flags_from_decl_or_type (decl);
 794   if (flags & ECF_CONST)
 795     ;
 796   else if (flags & ECF_PURE)
 797     *read_all = true;
 798   else
 799     {
 800        /* TODO: To be able to produce sane results, we should also handle
 801           common builtins, in particular throw.
 802           Indirect calls hsould be only counted and as inliner is replacing them
 803           by direct calls, we can conclude if any indirect calls are left in body */
 804       *read_all = true;
 805       /* When function does not reutrn, it is safe to ignore anythign it writes
 806          to, because the effect will never happen.  */
 807       if ((flags & (ECF_NOTHROW | ECF_NORETURN))
 808           != (ECF_NOTHROW | ECF_NORETURN))
 809         *write_all = true;
 810     }
 811 }
 812
 813 /* Produce the global information by preforming a transitive closure
 814    on the local information that was produced by ipa_analyze_function
 815    and ipa_analyze_variable.  */
 816
 817 static unsigned int
 818 propagate (void)
 819 {
 820   struct cgraph_node *node;
 821   struct cgraph_node *w;
 822   struct cgraph_node **order =
 823     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
 824   int order_pos = ipa_utils_reduced_inorder (order, false, true, NULL);
 825   int i;
 826
 827   if (dump_file)
 828     dump_cgraph (dump_file);
 829
 830   generate_summary ();
 831
 832   /* Propagate the local information thru the call graph to produce
 833      the global information.  All the nodes within a cycle will have
 834      the same info so we collapse cycles first.  Then we can do the
 835      propagation in one pass from the leaves to the roots.  */
 836   order_pos = ipa_utils_reduced_inorder (order, true, true, NULL);
 837   if (dump_file)
 838     ipa_utils_print_order(dump_file, "reduced", order, order_pos);
 839
 840   for (i = 0; i < order_pos; i++ )
 841     {
 842       ipa_reference_vars_info_t node_info;
 843       ipa_reference_global_vars_info_t node_g =
 844         XCNEW (struct ipa_reference_global_vars_info_d);
 845       ipa_reference_local_vars_info_t node_l;
 846       struct cgraph_edge *e;
 847
 848       bool read_all;
 849       bool write_all;
 850       struct ipa_dfs_info * w_info;
 851
 852       node = order[i];
 853       node_info = get_reference_vars_info (node);
 854       if (!node_info)
 855         {
 856           dump_cgraph_node (stderr, node);
 857           dump_cgraph (stderr);
 858           gcc_unreachable ();
 859         }
 860
 861       gcc_assert (!node_info->global);
 862       node_l = node_info->local;
 863
 864       read_all = node_l->calls_read_all;
 865       write_all = node_l->calls_write_all;
 866
 867       /* When function is overwrittable, we can not assume anything.  */
 868       if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
 869         read_write_all_from_decl (node->decl, &read_all, &write_all);
 870
 871       for (e = node->callees; e; e = e->next_callee)
 872         if (cgraph_function_body_availability (e->callee) <= AVAIL_OVERWRITABLE)
 873           read_write_all_from_decl (e->callee->decl, &read_all, &write_all);
 874
 875
 876       /* If any node in a cycle is calls_read_all or calls_write_all
 877          they all are. */
 878       w_info = (struct ipa_dfs_info *) node->aux;
 879       w = w_info->next_cycle;
 880       while (w)
 881         {
 882           ipa_reference_local_vars_info_t w_l =
 883             get_reference_vars_info (w)->local;
 884
 885           /* When function is overwrittable, we can not assume anything.  */
 886           if (cgraph_function_body_availability (w) <= AVAIL_OVERWRITABLE)
 887             read_write_all_from_decl (w->decl, &read_all, &write_all);
 888
 889           for (e = w->callees; e; e = e->next_callee)
 890             if (cgraph_function_body_availability (e->callee) <= AVAIL_OVERWRITABLE)
 891               read_write_all_from_decl (e->callee->decl, &read_all, &write_all);
 892
 893           read_all |= w_l->calls_read_all;
 894           write_all |= w_l->calls_write_all;
 895
 896           w_info = (struct ipa_dfs_info *) w->aux;
 897           w = w_info->next_cycle;
 898         }
 899
 900
 901       /* Initialized the bitmaps for the reduced nodes */
 902       if (read_all)
 903         node_g->statics_read = all_module_statics;
 904       else
 905         {
 906           node_g->statics_read = BITMAP_ALLOC (&global_info_obstack);
 907           bitmap_copy (node_g->statics_read,
 908                        node_l->statics_read);
 909         }
 910       if (write_all)
 911         node_g->statics_written = all_module_statics;
 912       else
 913         {
 914           node_g->statics_written = BITMAP_ALLOC (&global_info_obstack);
 915           bitmap_copy (node_g->statics_written,
 916                        node_l->statics_written);
 917         }
 918
 919       propagate_bits (node_g, node);
 920       w_info = (struct ipa_dfs_info *) node->aux;
 921       w = w_info->next_cycle;
 922       while (w)
 923         {
 924           ipa_reference_vars_info_t w_ri =
 925             get_reference_vars_info (w);
 926           ipa_reference_local_vars_info_t w_l = w_ri->local;
 927
 928           /* These global bitmaps are initialized from the local info
 929              of all of the nodes in the region.  However there is no
 930              need to do any work if the bitmaps were set to
 931              all_module_statics.  */
 932           if (!read_all)
 933             bitmap_ior_into (node_g->statics_read,
 934                              w_l->statics_read);
 935           if (!write_all)
 936             bitmap_ior_into (node_g->statics_written,
 937                              w_l->statics_written);
 938           propagate_bits (node_g, w);
 939           w_info = (struct ipa_dfs_info *) w->aux;
 940           w = w_info->next_cycle;
 941         }
 942
 943       /* All nodes within a cycle have the same global info bitmaps.  */
 944       node_info->global = node_g;
 945       w_info = (struct ipa_dfs_info *) node->aux;
 946       w = w_info->next_cycle;
 947       while (w)
 948         {
 949           ipa_reference_vars_info_t w_ri =
 950             get_reference_vars_info (w);
 951
 952           gcc_assert (!w_ri->global);
 953           w_ri->global = XCNEW (struct ipa_reference_global_vars_info_d);
 954           w_ri->global->statics_read = copy_global_bitmap (node_g->statics_read);
 955           w_ri->global->statics_written = copy_global_bitmap (node_g->statics_written);
 956
 957           w_info = (struct ipa_dfs_info *) w->aux;
 958           w = w_info->next_cycle;
 959         }
 960     }
 961
 962   if (dump_file)
 963     {
 964       for (i = 0; i < order_pos; i++ )
 965         {
 966           ipa_reference_vars_info_t node_info;
 967           ipa_reference_global_vars_info_t node_g;
 968           ipa_reference_local_vars_info_t node_l;
 969           unsigned int index;
 970           bitmap_iterator bi;
 971           struct ipa_dfs_info * w_info;
 972
 973           node = order[i];
 974           node_info = get_reference_vars_info (node);
 975           node_g = node_info->global;
 976           node_l = node_info->local;
 977           fprintf (dump_file,
 978                    "\nFunction name:%s/%i:",
 979                    cgraph_node_name (node), node->uid);
 980           fprintf (dump_file, "\n  locals read: ");
 981           if (node_l->statics_read)
 982             EXECUTE_IF_SET_IN_BITMAP (node_l->statics_read,
 983                                       0, index, bi)
 984               {
 985                 fprintf (dump_file, "%s ",
 986                          get_static_name (index));
 987               }
 988           fprintf (dump_file, "\n  locals written: ");
 989           if (node_l->statics_written)
 990             EXECUTE_IF_SET_IN_BITMAP (node_l->statics_written,
 991                                       0, index, bi)
 992               {
 993                 fprintf(dump_file, "%s ",
 994                         get_static_name (index));
 995               }
 996
 997           w_info = (struct ipa_dfs_info *) node->aux;
 998           w = w_info->next_cycle;
 999           while (w)
1000             {
1001               ipa_reference_vars_info_t w_ri =
1002                 get_reference_vars_info (w);
1003               ipa_reference_local_vars_info_t w_l = w_ri->local;
1004               fprintf (dump_file, "\n  next cycle: %s/%i ",
1005                        cgraph_node_name (w), w->uid);
1006               fprintf (dump_file, "\n    locals read: ");
1007               if (w_l->statics_read)
1008                 EXECUTE_IF_SET_IN_BITMAP (w_l->statics_read,
1009                                           0, index, bi)
1010                   {
1011                     fprintf (dump_file, "%s ",
1012                              get_static_name (index));
1013                   }
1014
1015               fprintf (dump_file, "\n    locals written: ");
1016               if (w_l->statics_written)
1017                 EXECUTE_IF_SET_IN_BITMAP (w_l->statics_written,
1018                                           0, index, bi)
1019                   {
1020                     fprintf (dump_file, "%s ",
1021                              get_static_name (index));
1022                   }
1023
1024               w_info = (struct ipa_dfs_info *) w->aux;
1025               w = w_info->next_cycle;
1026             }
1027           fprintf (dump_file, "\n  globals read: ");
1028           if (node_g->statics_read == all_module_statics)
1029             fprintf (dump_file, "ALL");
1030           else
1031             EXECUTE_IF_SET_IN_BITMAP (node_g->statics_read,
1032                                       0, index, bi)
1033               {
1034                 fprintf (dump_file, "%s ",
1035                          get_static_name (index));
1036               }
1037           fprintf (dump_file, "\n  globals written: ");
1038           if (node_g->statics_written == all_module_statics)
1039             fprintf (dump_file, "ALL");
1040           else
1041             EXECUTE_IF_SET_IN_BITMAP (node_g->statics_written,
1042                                       0, index, bi)
1043               {
1044                 fprintf (dump_file, "%s ",
1045                          get_static_name (index));
1046               }
1047         }
1048     }
1049
1050   /* Cleanup. */
1051   for (i = 0; i < order_pos; i++ )
1052     {
1053       ipa_reference_vars_info_t node_info;
1054       ipa_reference_global_vars_info_t node_g;
1055       node = order[i];
1056       node_info = get_reference_vars_info (node);
1057       node_g = node_info->global;
1058
1059       /* Create the complimentary sets.  These are more useful for
1060          certain apis.  */
1061       node_g->statics_not_read = BITMAP_ALLOC (&global_info_obstack);
1062       node_g->statics_not_written = BITMAP_ALLOC (&global_info_obstack);
1063
1064       if (node_g->statics_read != all_module_statics)
1065         bitmap_and_compl (node_g->statics_not_read,
1066                           all_module_statics,
1067                           node_g->statics_read);
1068
1069       if (node_g->statics_written
1070           != all_module_statics)
1071         bitmap_and_compl (node_g->statics_not_written,
1072                           all_module_statics,
1073                           node_g->statics_written);
1074    }
1075
1076   free (order);
1077
1078   for (node = cgraph_nodes; node; node = node->next)
1079     {
1080       ipa_reference_vars_info_t node_info;
1081       node_info = get_reference_vars_info (node);
1082       /* Get rid of the aux information.  */
1083
1084       if (node->aux)
1085         {
1086           free (node->aux);
1087           node->aux = NULL;
1088         }
1089
1090       if (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE)
1091         clean_function (node);
1092       else if (node_info)
1093         clean_function_local_data (node);
1094     }
1095   bitmap_obstack_release (&local_info_obstack);
1096   return 0;
1097 }
1098
1099
1100 static bool
1101 gate_reference (void)
1102 {
1103   return (flag_ipa_reference
1104           /* Don't bother doing anything if the program has errors.  */
1105           && !(errorcount || sorrycount));
1106 }
1107
1108 struct ipa_opt_pass_d pass_ipa_reference =
1109 {
1110  {
1111   IPA_PASS,
1112   "static-var",                         /* name */
1113   gate_reference,                       /* gate */
1114   propagate,                            /* execute */
1115   NULL,                                 /* sub */
1116   NULL,                                 /* next */
1117   0,                                    /* static_pass_number */
1118   TV_IPA_REFERENCE,                     /* tv_id */
1119   0,                                    /* properties_required */
1120   0,                                    /* properties_provided */
1121   0,                                    /* properties_destroyed */
1122   0,                                    /* todo_flags_start */
1123   0                                     /* todo_flags_finish */
1124  },
1125  NULL,                                  /* generate_summary */
1126  NULL,                                  /* write_summary */
1127  NULL,                                  /* read_summary */
1128  NULL,                                  /* write_optimization_summary */
1129  NULL,                                  /* read_optimization_summary */
1130  NULL,                                  /* stmt_fixup */
1131  0,                                     /* TODOs */
1132  NULL,                                  /* function_transform */
1133  NULL                                   /* variable_transform */
1134 };
1135
1136 #include "gt-ipa-reference.h"