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