gcc/ipa-reference.c

   1 /* Callgraph based analysis of static variables.
   2    Copyright (C) 2004, 2005, 2007, 2008 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 "ggc.h"
  61 #include "ipa-utils.h"
  62 #include "ipa-reference.h"
  63 #include "c-common.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 /* Mark load of T.  */
 338
 339 static void
 340 mark_load (ipa_reference_local_vars_info_t local,
 341            tree t)
 342 {
 343   if (TREE_CODE (t) == VAR_DECL
 344       && has_proper_scope_for_analysis (t))
 345     bitmap_set_bit (local->statics_read, DECL_UID (t));
 346 }
 347
 348 /* Mark store of T.  */
 349
 350 static void
 351 mark_store (ipa_reference_local_vars_info_t local,
 352            tree t)
 353 {
 354   if (TREE_CODE (t) == VAR_DECL
 355       && has_proper_scope_for_analysis (t))
 356     {
 357       if (local)
 358         bitmap_set_bit (local->statics_written, DECL_UID (t));
 359       /* Mark the write so we can tell which statics are
 360          readonly.  */
 361       if (module_statics_written)
 362         bitmap_set_bit (module_statics_written, DECL_UID (t));
 363     }
 364 }
 365
 366 /* Look for memory clobber and set read_all/write_all if present.  */
 367
 368 static void
 369 check_asm_memory_clobber (ipa_reference_local_vars_info_t local, gimple stmt)
 370 {
 371   size_t i;
 372   tree op;
 373
 374   for (i = 0; i < gimple_asm_nclobbers (stmt); i++)
 375     {
 376       op = gimple_asm_clobber_op (stmt, i);
 377       if (simple_cst_equal(TREE_VALUE (op), memory_identifier_string) == 1)
 378         {
 379           /* Abandon all hope, ye who enter here. */
 380           local->calls_read_all = true;
 381           local->calls_write_all = true;
 382         }
 383     }
 384 }
 385
 386 /* Look for external calls and set read_all/write_all correspondingly.  */
 387
 388 static void
 389 check_call (ipa_reference_local_vars_info_t local, gimple stmt)
 390 {
 391   int flags = gimple_call_flags (stmt);
 392   tree callee_t = gimple_call_fndecl (stmt);
 393   enum availability avail = AVAIL_NOT_AVAILABLE;
 394
 395   if (callee_t)
 396     {
 397       struct cgraph_node* callee = cgraph_node(callee_t);
 398       avail = cgraph_function_body_availability (callee);
 399     }
 400
 401   if (avail <= AVAIL_OVERWRITABLE)
 402     if (local)
 403       {
 404         if (flags & ECF_CONST)
 405           ;
 406         else if (flags & ECF_PURE)
 407           local->calls_read_all = true;
 408         else
 409           {
 410             local->calls_read_all = true;
 411             local->calls_write_all = true;
 412           }
 413       }
 414    /* TODO: To be able to produce sane results, we should also handle
 415       common builtins, in particular throw.
 416       Indirect calls hsould be only counted and as inliner is replacing them
 417       by direct calls, we can conclude if any indirect calls are left in body */
 418 }
 419
 420 /* TP is the part of the tree currently under the microscope.
 421    WALK_SUBTREES is part of the walk_tree api but is unused here.
 422    DATA is cgraph_node of the function being walked.  */
 423
 424 static tree
 425 scan_stmt_for_static_refs (gimple_stmt_iterator *gsip,
 426                            struct cgraph_node *fn)
 427 {
 428   gimple stmt = gsi_stmt (*gsip);
 429   ipa_reference_local_vars_info_t local = NULL;
 430   unsigned int i;
 431   bitmap_iterator bi;
 432
 433   if (fn)
 434     local = get_reference_vars_info (fn)->local;
 435
 436   /* Look for direct loads and stores.  */
 437   if (gimple_has_lhs (stmt))
 438     {
 439       tree lhs = get_base_address (gimple_get_lhs (stmt));
 440       if (lhs && DECL_P (lhs))
 441         mark_store (local, lhs);
 442     }
 443   if (gimple_assign_single_p (stmt))
 444     {
 445       tree rhs = get_base_address (gimple_assign_rhs1 (stmt));
 446       if (rhs && DECL_P (rhs))
 447         mark_load (local, rhs);
 448     }
 449   else if (is_gimple_call (stmt))
 450     {
 451       for (i = 0; i < gimple_call_num_args (stmt); ++i)
 452         {
 453           tree rhs = get_base_address (gimple_call_arg (stmt, i));
 454           if (rhs && DECL_P (rhs))
 455             mark_load (local, rhs);
 456         }
 457       check_call (local, stmt);
 458     }
 459   else if (gimple_code (stmt) == GIMPLE_ASM)
 460     {
 461       for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
 462         {
 463           tree op = TREE_VALUE (gimple_asm_input_op (stmt, i));
 464           op = get_base_address (op);
 465           if (op && DECL_P (op))
 466             mark_load (local, op);
 467         }
 468       for (i = 0; i < gimple_asm_noutputs (stmt); ++i)
 469         {
 470           tree op = TREE_VALUE (gimple_asm_output_op (stmt, i));
 471           op = get_base_address (op);
 472           if (op && DECL_P (op))
 473             mark_store (local, op);
 474         }
 475       check_asm_memory_clobber (local, stmt);
 476     }
 477
 478   if (gimple_addresses_taken (stmt))
 479     EXECUTE_IF_SET_IN_BITMAP (gimple_addresses_taken (stmt), 0, i, bi)
 480       mark_address_taken (referenced_var_lookup (i));
 481
 482   return NULL;
 483 }
 484
 485 /* Call-back to scan variable initializers for static references.
 486    Called using walk_tree.  */
 487
 488 static tree
 489 scan_initializer_for_static_refs (tree *tp, int *walk_subtrees,
 490                                   void *data ATTRIBUTE_UNUSED)
 491 {
 492   tree t = *tp;
 493
 494   if (TREE_CODE (t) == ADDR_EXPR)
 495     {
 496       mark_address_taken (get_base_var (t));
 497       *walk_subtrees = 0;
 498     }
 499   /* Save some cycles by not walking types and declaration as we
 500      won't find anything useful there anyway.  */
 501   else if (IS_TYPE_OR_DECL_P (*tp))
 502     *walk_subtrees = 0;
 503
 504   return NULL;
 505 }
 506
 507 /* Lookup the tree node for the static variable that has UID.  */
 508 static tree
 509 get_static_decl (int index)
 510 {
 511   splay_tree_node stn =
 512     splay_tree_lookup (reference_vars_to_consider, index);
 513   if (stn)
 514     return (tree)stn->value;
 515   return NULL;
 516 }
 517
 518 /* Lookup the tree node for the static variable that has UID and
 519    convert the name to a string for debugging.  */
 520
 521 static const char *
 522 get_static_name (int index)
 523 {
 524   splay_tree_node stn =
 525     splay_tree_lookup (reference_vars_to_consider, index);
 526   if (stn)
 527     return lang_hooks.decl_printable_name ((tree)(stn->value), 2);
 528   return NULL;
 529 }
 530
 531 /* Or in all of the bits from every callee of X into X_GLOBAL, the caller's cycle,
 532    bit vector.  There are several cases to check to avoid the sparse
 533    bitmap oring.  */
 534
 535 static void
 536 propagate_bits (ipa_reference_global_vars_info_t x_global, struct cgraph_node *x)
 537 {
 538   struct cgraph_edge *e;
 539   for (e = x->callees; e; e = e->next_callee)
 540     {
 541       struct cgraph_node *y = e->callee;
 542
 543       /* Only look at the master nodes and skip external nodes.  */
 544       if (cgraph_function_body_availability (e->callee) > AVAIL_OVERWRITABLE)
 545         {
 546           if (get_reference_vars_info (y))
 547             {
 548               ipa_reference_vars_info_t y_info
 549                 = get_reference_vars_info (y);
 550               ipa_reference_global_vars_info_t y_global = y_info->global;
 551
 552               /* Calls in current cycle do not have global computed yet.  */
 553               if (!y_info->global)
 554                 continue;
 555
 556               if (x_global->statics_read
 557                   != all_module_statics)
 558                 {
 559                   if (y_global->statics_read
 560                       == all_module_statics)
 561                     {
 562                       BITMAP_FREE (x_global->statics_read);
 563                       x_global->statics_read
 564                         = all_module_statics;
 565                     }
 566                   /* Skip bitmaps that are pointer equal to node's bitmap
 567                      (no reason to spin within the cycle).  */
 568                   else if (x_global->statics_read
 569                            != y_global->statics_read)
 570                     bitmap_ior_into (x_global->statics_read,
 571                                      y_global->statics_read);
 572                 }
 573
 574               if (x_global->statics_written
 575                   != all_module_statics)
 576                 {
 577                   if (y_global->statics_written
 578                       == all_module_statics)
 579                     {
 580                       BITMAP_FREE (x_global->statics_written);
 581                       x_global->statics_written
 582                         = all_module_statics;
 583                     }
 584                   /* Skip bitmaps that are pointer equal to node's bitmap
 585                      (no reason to spin within the cycle).  */
 586                   else if (x_global->statics_written
 587                            != y_global->statics_written)
 588                     bitmap_ior_into (x_global->statics_written,
 589                                      y_global->statics_written);
 590                 }
 591             }
 592           else
 593             gcc_unreachable ();
 594         }
 595     }
 596 }
 597
 598 /* The init routine for analyzing global static variable usage.  See
 599    comments at top for description.  */
 600 static void
 601 ipa_init (void)
 602 {
 603   memory_identifier_string = build_string(7, "memory");
 604
 605   reference_vars_to_consider =
 606     splay_tree_new_ggc (splay_tree_compare_ints);
 607
 608   bitmap_obstack_initialize (&local_info_obstack);
 609   bitmap_obstack_initialize (&global_info_obstack);
 610   module_statics_escape = BITMAP_ALLOC (&local_info_obstack);
 611   module_statics_written = BITMAP_ALLOC (&local_info_obstack);
 612   all_module_statics = BITMAP_ALLOC (&global_info_obstack);
 613
 614   /* There are some shared nodes, in particular the initializers on
 615      static declarations.  We do not need to scan them more than once
 616      since all we would be interested in are the addressof
 617      operations.  */
 618   visited_nodes = pointer_set_create ();
 619 }
 620
 621 /* Check out the rhs of a static or global initialization VNODE to see
 622    if any of them contain addressof operations.  Note that some of
 623    these variables may  not even be referenced in the code in this
 624    compilation unit but their right hand sides may contain references
 625    to variables defined within this unit.  */
 626
 627 static void
 628 analyze_variable (struct varpool_node *vnode)
 629 {
 630   struct walk_stmt_info wi;
 631   tree global = vnode->decl;
 632
 633   memset (&wi, 0, sizeof (wi));
 634   wi.pset = visited_nodes;
 635   walk_tree (&DECL_INITIAL (global), scan_initializer_for_static_refs,
 636              &wi, wi.pset);
 637 }
 638
 639 /* Set up the persistent info for FN.  */
 640
 641 static ipa_reference_local_vars_info_t
 642 init_function_info (struct cgraph_node *fn)
 643 {
 644   ipa_reference_vars_info_t info
 645     = XCNEW (struct ipa_reference_vars_info_d);
 646   ipa_reference_local_vars_info_t l
 647     = XCNEW (struct ipa_reference_local_vars_info_d);
 648
 649   /* Add the info to the tree's annotation.  */
 650   set_reference_vars_info (fn, info);
 651
 652   info->local = l;
 653   l->statics_read = BITMAP_ALLOC (&local_info_obstack);
 654   l->statics_written = BITMAP_ALLOC (&local_info_obstack);
 655
 656   return l;
 657 }
 658
 659 /* This is the main routine for finding the reference patterns for
 660    global variables within a function FN.  */
 661
 662 static void
 663 analyze_function (struct cgraph_node *fn)
 664 {
 665   tree decl = fn->decl;
 666   struct function *this_cfun = DECL_STRUCT_FUNCTION (decl);
 667   basic_block this_block;
 668 #ifdef ENABLE_CHECKING
 669   tree step;
 670 #endif
 671
 672   if (dump_file)
 673     fprintf (dump_file, "\n local analysis of %s\n", cgraph_node_name (fn));
 674
 675   push_cfun (DECL_STRUCT_FUNCTION (decl));
 676   current_function_decl = decl;
 677
 678   init_function_info (fn);
 679   FOR_EACH_BB_FN (this_block, this_cfun)
 680     {
 681       gimple_stmt_iterator gsi;
 682       gimple phi;
 683       tree op;
 684       use_operand_p use;
 685       ssa_op_iter iter;
 686
 687       /* Find the addresses taken in phi node arguments.  */
 688       for (gsi = gsi_start_phis (this_block);
 689            !gsi_end_p (gsi);
 690            gsi_next (&gsi))
 691         {
 692           phi = gsi_stmt (gsi);
 693           FOR_EACH_PHI_ARG (use, phi, iter, SSA_OP_USE)
 694             {
 695               op = USE_FROM_PTR (use);
 696               if (TREE_CODE (op) == ADDR_EXPR)
 697                 mark_address_taken (get_base_var (op));
 698             }
 699         }
 700
 701       for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
 702         scan_stmt_for_static_refs (&gsi, fn);
 703     }
 704
 705 #ifdef ENABLE_CHECKING
 706   /* Verify that all local initializers was expanded by gimplifier.  */
 707   for (step = DECL_STRUCT_FUNCTION (decl)->local_decls;
 708        step;
 709        step = TREE_CHAIN (step))
 710     {
 711       tree var = TREE_VALUE (step);
 712       if (TREE_CODE (var) == VAR_DECL
 713           && DECL_INITIAL (var)
 714           && !TREE_STATIC (var))
 715         gcc_unreachable ();
 716     }
 717 #endif
 718   pop_cfun ();
 719   current_function_decl = NULL;
 720 }
 721
 722 /* Remove local data associated with function FN.  */
 723 static void
 724 clean_function_local_data (struct cgraph_node *fn)
 725 {
 726   ipa_reference_vars_info_t info = get_reference_vars_info (fn);
 727   ipa_reference_local_vars_info_t l = info->local;
 728   if (l)
 729     {
 730       if (l->statics_read
 731           && l->statics_read != all_module_statics)
 732         BITMAP_FREE (l->statics_read);
 733       if (l->statics_written
 734           &&l->statics_written != all_module_statics)
 735         BITMAP_FREE (l->statics_written);
 736       free (l);
 737       info->local = NULL;
 738     }
 739 }
 740
 741 /* Remove all data associated with function FN.  */
 742
 743 static void
 744 clean_function (struct cgraph_node *fn)
 745 {
 746   ipa_reference_vars_info_t info = get_reference_vars_info (fn);
 747   ipa_reference_global_vars_info_t g = info->global;
 748
 749   clean_function_local_data (fn);
 750   if (g)
 751     {
 752       if (g->statics_read
 753           && g->statics_read != all_module_statics)
 754         BITMAP_FREE (g->statics_read);
 755
 756       if (g->statics_written
 757           && g->statics_written != all_module_statics)
 758         BITMAP_FREE (g->statics_written);
 759
 760       if (g->statics_not_read
 761           && g->statics_not_read != all_module_statics)
 762         BITMAP_FREE (g->statics_not_read);
 763
 764       if (g->statics_not_written
 765           && g->statics_not_written != all_module_statics)
 766         BITMAP_FREE (g->statics_not_written);
 767       free (g);
 768       info->global = NULL;
 769     }
 770
 771   free (get_reference_vars_info (fn));
 772   set_reference_vars_info (fn, NULL);
 773 }
 774
 775 /* Called when new function is inserted to callgraph late.  */
 776 static void
 777 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 778 {
 779   /* There are some shared nodes, in particular the initializers on
 780      static declarations.  We do not need to scan them more than once
 781      since all we would be interested in are the addressof
 782      operations.  */
 783   analyze_function (node);
 784   visited_nodes = NULL;
 785 }
 786
 787 static bitmap
 788 copy_local_bitmap (bitmap src)
 789 {
 790   bitmap dst;
 791   if (!src)
 792     return NULL;
 793   if (src == all_module_statics)
 794     return all_module_statics;
 795   dst = BITMAP_ALLOC (&local_info_obstack);
 796   bitmap_copy (dst, src);
 797   return dst;
 798 }
 799
 800 static bitmap
 801 copy_global_bitmap (bitmap src)
 802 {
 803   bitmap dst;
 804   if (!src)
 805     return NULL;
 806   if (src == all_module_statics)
 807     return all_module_statics;
 808   dst = BITMAP_ALLOC (&global_info_obstack);
 809   bitmap_copy (dst, src);
 810   return dst;
 811 }
 812
 813 /* Called when new clone is inserted to callgraph late.  */
 814
 815 static void
 816 duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst,
 817                      void *data ATTRIBUTE_UNUSED)
 818 {
 819   ipa_reference_global_vars_info_t ginfo;
 820   ipa_reference_local_vars_info_t linfo;
 821   ipa_reference_global_vars_info_t dst_ginfo;
 822   ipa_reference_local_vars_info_t dst_linfo;
 823
 824   ginfo = get_global_reference_vars_info (src);
 825   linfo = get_local_reference_vars_info (src);
 826   if (!linfo && !ginfo)
 827     return;
 828   init_function_info (dst);
 829   if (linfo)
 830     {
 831       dst_linfo = get_local_reference_vars_info (dst);
 832       dst_linfo->statics_read = copy_local_bitmap (linfo->statics_read);
 833       dst_linfo->statics_written = copy_local_bitmap (linfo->statics_written);
 834       dst_linfo->calls_read_all = linfo->calls_read_all;
 835       dst_linfo->calls_write_all = linfo->calls_write_all;
 836     }
 837   if (ginfo)
 838     {
 839       get_reference_vars_info (dst)->global = XCNEW (struct ipa_reference_global_vars_info_d);
 840       dst_ginfo = get_global_reference_vars_info (dst);
 841       dst_ginfo->statics_read = copy_global_bitmap (ginfo->statics_read);
 842       dst_ginfo->statics_written = copy_global_bitmap (ginfo->statics_written);
 843       dst_ginfo->statics_not_read = copy_global_bitmap (ginfo->statics_not_read);
 844       dst_ginfo->statics_not_written = copy_global_bitmap (ginfo->statics_not_written);
 845     }
 846 }
 847
 848 /* Called when node is removed.  */
 849
 850 static void
 851 remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
 852 {
 853   if (get_reference_vars_info (node))
 854     clean_function (node);
 855 }
 856
 857 /* Analyze each function in the cgraph to see which global or statics
 858    are read or written.  */
 859
 860 static void
 861 generate_summary (void)
 862 {
 863   struct cgraph_node *node;
 864   struct varpool_node *vnode;
 865   unsigned int index;
 866   bitmap_iterator bi;
 867   bitmap module_statics_readonly;
 868   bitmap bm_temp;
 869
 870   function_insertion_hook_holder =
 871       cgraph_add_function_insertion_hook (&add_new_function, NULL);
 872   node_removal_hook_holder =
 873       cgraph_add_node_removal_hook (&remove_node_data, NULL);
 874   node_duplication_hook_holder =
 875       cgraph_add_node_duplication_hook (&duplicate_node_data, NULL);
 876   ipa_init ();
 877   module_statics_readonly = BITMAP_ALLOC (&local_info_obstack);
 878   bm_temp = BITMAP_ALLOC (&local_info_obstack);
 879
 880   /* Process all of the variables first.  */
 881   FOR_EACH_STATIC_INITIALIZER (vnode)
 882     analyze_variable (vnode);
 883
 884   /* Process all of the functions next.
 885
 886      We do not want to process any of the clones so we check that this
 887      is a master clone.  However, we do need to process any
 888      AVAIL_OVERWRITABLE functions (these are never clones) because
 889      they may cause a static variable to escape.  The code that can
 890      overwrite such a function cannot access the statics because it
 891      would not be in the same compilation unit.  When the analysis is
 892      finished, the computed information of these AVAIL_OVERWRITABLE is
 893      replaced with worst case info.
 894   */
 895   for (node = cgraph_nodes; node; node = node->next)
 896     if (cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
 897       analyze_function (node);
 898
 899   pointer_set_destroy (visited_nodes);
 900   visited_nodes = NULL;
 901
 902   /* Prune out the variables that were found to behave badly
 903      (i.e. have their address taken).  */
 904   EXECUTE_IF_SET_IN_BITMAP (module_statics_escape, 0, index, bi)
 905     {
 906       splay_tree_remove (reference_vars_to_consider, index);
 907     }
 908
 909   bitmap_and_compl_into (all_module_statics,
 910                          module_statics_escape);
 911
 912   bitmap_and_compl (module_statics_readonly, all_module_statics,
 913                     module_statics_written);
 914
 915   /* If the address is not taken, we can unset the addressable bit
 916      on this variable.  */
 917   EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
 918     {
 919       tree var = get_static_decl (index);
 920       TREE_ADDRESSABLE (var) = 0;
 921       if (dump_file)
 922         fprintf (dump_file, "Not TREE_ADDRESSABLE var %s\n",
 923                  get_static_name (index));
 924     }
 925
 926   /* If the variable is never written, we can set the TREE_READONLY
 927      flag.  Additionally if it has a DECL_INITIAL that is made up of
 928      constants we can treat the entire global as a constant.  */
 929
 930   bitmap_and_compl (module_statics_readonly, all_module_statics,
 931                     module_statics_written);
 932   EXECUTE_IF_SET_IN_BITMAP (module_statics_readonly, 0, index, bi)
 933     {
 934       tree var = get_static_decl (index);
 935
 936       /* Ignore variables in named sections - changing TREE_READONLY
 937          changes the section flags, potentially causing conflicts with
 938          other variables in the same named section.  */
 939       if (DECL_SECTION_NAME (var) == NULL_TREE)
 940         {
 941           TREE_READONLY (var) = 1;
 942           if (dump_file)
 943             fprintf (dump_file, "read-only var %s\n",
 944                      get_static_name (index));
 945         }
 946     }
 947
 948   BITMAP_FREE(module_statics_escape);
 949   BITMAP_FREE(module_statics_written);
 950   module_statics_escape = NULL;
 951   module_statics_written = NULL;
 952
 953   if (dump_file)
 954     EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
 955       {
 956         fprintf (dump_file, "\nPromotable global:%s",
 957                  get_static_name (index));
 958       }
 959
 960   for (node = cgraph_nodes; node; node = node->next)
 961     if (cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
 962       {
 963         ipa_reference_local_vars_info_t l;
 964         l = get_reference_vars_info (node)->local;
 965
 966         /* Any variables that are not in all_module_statics are
 967            removed from the local maps.  This will include all of the
 968            variables that were found to escape in the function
 969            scanning.  */
 970         bitmap_and_into (l->statics_read,
 971                          all_module_statics);
 972         bitmap_and_into (l->statics_written,
 973                          all_module_statics);
 974       }
 975
 976   BITMAP_FREE(module_statics_readonly);
 977   BITMAP_FREE(bm_temp);
 978
 979   if (dump_file)
 980     for (node = cgraph_nodes; node; node = node->next)
 981       if (cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
 982         {
 983           ipa_reference_local_vars_info_t l;
 984           unsigned int index;
 985           bitmap_iterator bi;
 986
 987           l = get_reference_vars_info (node)->local;
 988           fprintf (dump_file,
 989                    "\nFunction name:%s/%i:",
 990                    cgraph_node_name (node), node->uid);
 991           fprintf (dump_file, "\n  locals read: ");
 992           EXECUTE_IF_SET_IN_BITMAP (l->statics_read,
 993                                     0, index, bi)
 994             {
 995               fprintf (dump_file, "%s ",
 996                        get_static_name (index));
 997             }
 998           fprintf (dump_file, "\n  locals written: ");
 999           EXECUTE_IF_SET_IN_BITMAP (l->statics_written,
1000                                     0, index, bi)
1001             {
1002               fprintf(dump_file, "%s ",
1003                       get_static_name (index));
1004             }
1005           if (l->calls_read_all)
1006              fprintf (dump_file, "\n  calls read all: ");
1007           if (l->calls_write_all)
1008              fprintf (dump_file, "\n  calls read all: ");
1009         }
1010 }
1011 \f
1012 /* Produce the global information by preforming a transitive closure
1013    on the local information that was produced by ipa_analyze_function
1014    and ipa_analyze_variable.  */
1015
1016 static unsigned int
1017 propagate (void)
1018 {
1019   struct cgraph_node *node;
1020   struct cgraph_node *w;
1021   struct cgraph_node **order =
1022     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1023   int order_pos = ipa_utils_reduced_inorder (order, false, true);
1024   int i;
1025
1026   cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
1027   if (dump_file)
1028     dump_cgraph (dump_file);
1029
1030   /* Propagate the local information thru the call graph to produce
1031      the global information.  All the nodes within a cycle will have
1032      the same info so we collapse cycles first.  Then we can do the
1033      propagation in one pass from the leaves to the roots.  */
1034   order_pos = ipa_utils_reduced_inorder (order, true, true);
1035   if (dump_file)
1036     ipa_utils_print_order(dump_file, "reduced", order, order_pos);
1037
1038   for (i = 0; i < order_pos; i++ )
1039     {
1040       ipa_reference_vars_info_t node_info;
1041       ipa_reference_global_vars_info_t node_g =
1042         XCNEW (struct ipa_reference_global_vars_info_d);
1043       ipa_reference_local_vars_info_t node_l;
1044
1045       bool read_all;
1046       bool write_all;
1047       struct ipa_dfs_info * w_info;
1048
1049       node = order[i];
1050       node_info = get_reference_vars_info (node);
1051       if (!node_info)
1052         {
1053           dump_cgraph_node (stderr, node);
1054           dump_cgraph (stderr);
1055           gcc_unreachable ();
1056         }
1057
1058       gcc_assert (!node_info->global);
1059       node_l = node_info->local;
1060
1061       read_all = node_l->calls_read_all;
1062       write_all = node_l->calls_write_all;
1063
1064       /* If any node in a cycle is calls_read_all or calls_write_all
1065          they all are. */
1066       w_info = (struct ipa_dfs_info *) node->aux;
1067       w = w_info->next_cycle;
1068       while (w)
1069         {
1070           ipa_reference_local_vars_info_t w_l =
1071             get_reference_vars_info (w)->local;
1072           read_all |= w_l->calls_read_all;
1073           write_all |= w_l->calls_write_all;
1074
1075           w_info = (struct ipa_dfs_info *) w->aux;
1076           w = w_info->next_cycle;
1077         }
1078
1079       /* Initialized the bitmaps for the reduced nodes */
1080       if (read_all)
1081         node_g->statics_read = all_module_statics;
1082       else
1083         {
1084           node_g->statics_read = BITMAP_ALLOC (&global_info_obstack);
1085           bitmap_copy (node_g->statics_read,
1086                        node_l->statics_read);
1087         }
1088
1089       if (write_all)
1090         node_g->statics_written = all_module_statics;
1091       else
1092         {
1093           node_g->statics_written = BITMAP_ALLOC (&global_info_obstack);
1094           bitmap_copy (node_g->statics_written,
1095                        node_l->statics_written);
1096         }
1097
1098       propagate_bits (node_g, node);
1099       w_info = (struct ipa_dfs_info *) node->aux;
1100       w = w_info->next_cycle;
1101       while (w)
1102         {
1103           ipa_reference_vars_info_t w_ri =
1104             get_reference_vars_info (w);
1105           ipa_reference_local_vars_info_t w_l = w_ri->local;
1106
1107           /* These global bitmaps are initialized from the local info
1108              of all of the nodes in the region.  However there is no
1109              need to do any work if the bitmaps were set to
1110              all_module_statics.  */
1111           if (!read_all)
1112             bitmap_ior_into (node_g->statics_read,
1113                              w_l->statics_read);
1114           if (!write_all)
1115             bitmap_ior_into (node_g->statics_written,
1116                              w_l->statics_written);
1117           propagate_bits (node_g, w);
1118           w_info = (struct ipa_dfs_info *) w->aux;
1119           w = w_info->next_cycle;
1120         }
1121
1122       /* All nodes within a cycle have the same global info bitmaps.  */
1123       node_info->global = node_g;
1124       w_info = (struct ipa_dfs_info *) node->aux;
1125       w = w_info->next_cycle;
1126       while (w)
1127         {
1128           ipa_reference_vars_info_t w_ri =
1129             get_reference_vars_info (w);
1130
1131           gcc_assert (!w_ri->global);
1132           w_ri->global = XCNEW (struct ipa_reference_global_vars_info_d);
1133           w_ri->global->statics_read = copy_global_bitmap (node_g->statics_read);
1134           w_ri->global->statics_written = copy_global_bitmap (node_g->statics_written);
1135
1136           w_info = (struct ipa_dfs_info *) w->aux;
1137           w = w_info->next_cycle;
1138         }
1139     }
1140
1141   if (dump_file)
1142     {
1143       for (i = 0; i < order_pos; i++ )
1144         {
1145           ipa_reference_vars_info_t node_info;
1146           ipa_reference_global_vars_info_t node_g;
1147           ipa_reference_local_vars_info_t node_l;
1148           unsigned int index;
1149           bitmap_iterator bi;
1150           struct ipa_dfs_info * w_info;
1151
1152           node = order[i];
1153           node_info = get_reference_vars_info (node);
1154           node_g = node_info->global;
1155           node_l = node_info->local;
1156           fprintf (dump_file,
1157                    "\nFunction name:%s/%i:",
1158                    cgraph_node_name (node), node->uid);
1159           fprintf (dump_file, "\n  locals read: ");
1160           EXECUTE_IF_SET_IN_BITMAP (node_l->statics_read,
1161                                     0, index, bi)
1162             {
1163               fprintf (dump_file, "%s ",
1164                        get_static_name (index));
1165             }
1166           fprintf (dump_file, "\n  locals written: ");
1167           EXECUTE_IF_SET_IN_BITMAP (node_l->statics_written,
1168                                     0, index, bi)
1169             {
1170               fprintf(dump_file, "%s ",
1171                       get_static_name (index));
1172             }
1173
1174           w_info = (struct ipa_dfs_info *) node->aux;
1175           w = w_info->next_cycle;
1176           while (w)
1177             {
1178               ipa_reference_vars_info_t w_ri =
1179                 get_reference_vars_info (w);
1180               ipa_reference_local_vars_info_t w_l = w_ri->local;
1181               fprintf (dump_file, "\n  next cycle: %s/%i ",
1182                        cgraph_node_name (w), w->uid);
1183               fprintf (dump_file, "\n    locals read: ");
1184               EXECUTE_IF_SET_IN_BITMAP (w_l->statics_read,
1185                                         0, index, bi)
1186                 {
1187                   fprintf (dump_file, "%s ",
1188                            get_static_name (index));
1189                 }
1190
1191               fprintf (dump_file, "\n    locals written: ");
1192               EXECUTE_IF_SET_IN_BITMAP (w_l->statics_written,
1193                                         0, index, bi)
1194                 {
1195                   fprintf(dump_file, "%s ",
1196                           get_static_name (index));
1197                 }
1198
1199
1200               w_info = (struct ipa_dfs_info *) w->aux;
1201               w = w_info->next_cycle;
1202             }
1203           fprintf (dump_file, "\n  globals read: ");
1204           EXECUTE_IF_SET_IN_BITMAP (node_g->statics_read,
1205                                     0, index, bi)
1206             {
1207               fprintf (dump_file, "%s ",
1208                        get_static_name (index));
1209             }
1210           fprintf (dump_file, "\n  globals written: ");
1211           EXECUTE_IF_SET_IN_BITMAP (node_g->statics_written,
1212                                     0, index, bi)
1213             {
1214               fprintf (dump_file, "%s ",
1215                        get_static_name (index));
1216             }
1217         }
1218     }
1219
1220   /* Cleanup. */
1221   for (i = 0; i < order_pos; i++ )
1222     {
1223       ipa_reference_vars_info_t node_info;
1224       ipa_reference_global_vars_info_t node_g;
1225       node = order[i];
1226       node_info = get_reference_vars_info (node);
1227       node_g = node_info->global;
1228
1229       /* Create the complimentary sets.  These are more useful for
1230          certain apis.  */
1231       node_g->statics_not_read = BITMAP_ALLOC (&global_info_obstack);
1232       node_g->statics_not_written = BITMAP_ALLOC (&global_info_obstack);
1233
1234       if (node_g->statics_read != all_module_statics)
1235         bitmap_and_compl (node_g->statics_not_read,
1236                           all_module_statics,
1237                           node_g->statics_read);
1238
1239       if (node_g->statics_written
1240           != all_module_statics)
1241         bitmap_and_compl (node_g->statics_not_written,
1242                           all_module_statics,
1243                           node_g->statics_written);
1244    }
1245
1246   free (order);
1247
1248   for (node = cgraph_nodes; node; node = node->next)
1249     {
1250       ipa_reference_vars_info_t node_info;
1251       node_info = get_reference_vars_info (node);
1252       /* Get rid of the aux information.  */
1253
1254       if (node->aux)
1255         {
1256           free (node->aux);
1257           node->aux = NULL;
1258         }
1259
1260       if (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE)
1261         clean_function (node);
1262       else if (node_info)
1263         clean_function_local_data (node);
1264     }
1265   bitmap_obstack_release (&local_info_obstack);
1266   return 0;
1267 }
1268
1269
1270 static bool
1271 gate_reference (void)
1272 {
1273   return (flag_ipa_reference
1274           /* Don't bother doing anything if the program has errors.  */
1275           && !(errorcount || sorrycount));
1276 }
1277
1278 struct ipa_opt_pass pass_ipa_reference =
1279 {
1280  {
1281   IPA_PASS,
1282   "static-var",                         /* name */
1283   gate_reference,                       /* gate */
1284   propagate,                            /* execute */
1285   NULL,                                 /* sub */
1286   NULL,                                 /* next */
1287   0,                                    /* static_pass_number */
1288   TV_IPA_REFERENCE,                     /* tv_id */
1289   0,                                    /* properties_required */
1290   0,                                    /* properties_provided */
1291   0,                                    /* properties_destroyed */
1292   0,                                    /* todo_flags_start */
1293   0                                     /* todo_flags_finish */
1294  },
1295  generate_summary,                      /* generate_summary */
1296  NULL,                                  /* write_summary */
1297  NULL,                                  /* read_summary */
1298  NULL,                                  /* function_read_summary */
1299  0,                                     /* TODOs */
1300  NULL,                                  /* function_transform */
1301  NULL                                   /* variable_transform */
1302 };
1303
1304 #include "gt-ipa-reference.h"