gcc/ipa-reference.c

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