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