contrib/gcc/ipa-reference.c

   1 /* Callgraph based analysis of static variables.
   2    Copyright (C) 2004, 2005 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 2, 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 COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.
  21 */
  22
  23 /* This file gathers information about how variables whose scope is
  24    confined to the compilation unit are used.
  25
  26    There are two categories of information produced by this pass:
  27
  28    1) The addressable (TREE_ADDRESSABLE) bit and readonly
  29    (TREE_READONLY) bit associated with these variables is properly set
  30    based on scanning all of the code withing the compilation unit.
  31
  32    2) The transitive call site specific clobber effects are computed
  33    for the variables whose scope is contained within this compilation
  34    unit.
  35
  36    First each function and static variable initialization is analyzed
  37    to determine which local static variables are either read, written,
  38    or have their address taken.  Any local static that has its address
  39    taken is removed from consideration.  Once the local read and
  40    writes are determined, a transitive closure of this information is
  41    performed over the call graph to determine the worst case set of
  42    side effects of each call.  In later parts of the compiler, these
  43    local and global sets are examined to make the call clobbering less
  44    traumatic, promote some statics to registers, and improve aliasing
  45    information.
  46
  47    Currently must be run after inlining decisions have been made since
  48    otherwise, the local sets will not contain information that is
  49    consistent with post inlined state.  The global sets are not prone
  50    to this problem since they are by definition transitive.
  51 */
  52
  53 #include "config.h"
  54 #include "system.h"
  55 #include "coretypes.h"
  56 #include "tm.h"
  57 #include "tree.h"
  58 #include "tree-flow.h"
  59 #include "tree-inline.h"
  60 #include "tree-pass.h"
  61 #include "langhooks.h"
  62 #include "pointer-set.h"
  63 #include "ggc.h"
  64 #include "ipa-utils.h"
  65 #include "ipa-reference.h"
  66 #include "c-common.h"
  67 #include "tree-gimple.h"
  68 #include "cgraph.h"
  69 #include "output.h"
  70 #include "flags.h"
  71 #include "timevar.h"
  72 #include "diagnostic.h"
  73 #include "langhooks.h"
  74
  75 /* This splay tree contains all of the static variables that are
  76    being considered by the compilation level alias analysis.  For
  77    module_at_a_time compilation, this is the set of static but not
  78    public variables.  Any variables that either have their address
  79    taken or participate in otherwise unsavory operations are deleted
  80    from this list.  */
  81 static GTY((param1_is(int), param2_is(tree)))
  82      splay_tree reference_vars_to_consider;
  83
  84 /* This bitmap is used to knock out the module static variables whose
  85    addresses have been taken and passed around.  */
  86 static bitmap module_statics_escape;
  87
  88 /* This bitmap is used to knock out the module static variables that
  89    are not readonly.  */
  90 static bitmap module_statics_written;
  91
  92 /* A bit is set for every module static we are considering.  This is
  93    ored into the local info when asm code is found that clobbers all
  94    memory. */
  95 static bitmap all_module_statics;
  96
  97 static struct pointer_set_t *visited_nodes;
  98
  99 static bitmap_obstack ipa_obstack;
 100
 101 enum initialization_status_t
 102 {
 103   UNINITIALIZED,
 104   RUNNING,
 105   FINISHED
 106 };
 107
 108 tree memory_identifier_string;
 109
 110 /* Return the ipa_reference_vars structure starting from the cgraph NODE.  */
 111 static inline ipa_reference_vars_info_t
 112 get_reference_vars_info_from_cgraph (struct cgraph_node * node)
 113 {
 114   return get_function_ann (node->decl)->reference_vars_info;
 115 }
 116
 117 /* Get a bitmap that contains all of the locally referenced static
 118    variables for function FN.  */
 119 static ipa_reference_local_vars_info_t
 120 get_local_reference_vars_info (tree fn)
 121 {
 122   ipa_reference_vars_info_t info = get_function_ann (fn)->reference_vars_info;
 123
 124   if (info)
 125     return info->local;
 126   else
 127     /* This phase was not run.  */
 128     return NULL;
 129 }
 130
 131 /* Get a bitmap that contains all of the globally referenced static
 132    variables for function FN.  */
 133
 134 static ipa_reference_global_vars_info_t
 135 get_global_reference_vars_info (tree fn)
 136 {
 137   ipa_reference_vars_info_t info = get_function_ann (fn)->reference_vars_info;
 138
 139   if (info)
 140     return info->global;
 141   else
 142     /* This phase was not run.  */
 143     return NULL;
 144 }
 145
 146 /* Return a bitmap indexed by VAR_DECL uid for the static variables
 147    that may be read locally by the execution of the function fn.
 148    Returns NULL if no data is available.  */
 149
 150 bitmap
 151 ipa_reference_get_read_local (tree fn)
 152 {
 153   ipa_reference_local_vars_info_t l = get_local_reference_vars_info (fn);
 154   if (l)
 155     return l->statics_read;
 156   else
 157     return NULL;
 158 }
 159
 160 /* Return a bitmap indexed by VAR_DECL uid for the static variables
 161    that may be written locally by the execution of the function fn.
 162    Returns NULL if no data is available.  */
 163
 164 bitmap
 165 ipa_reference_get_written_local (tree fn)
 166 {
 167   ipa_reference_local_vars_info_t l = get_local_reference_vars_info (fn);
 168   if (l)
 169     return l->statics_written;
 170   else
 171     return NULL;
 172 }
 173
 174 /* Return a bitmap indexed by VAR_DECL uid for the static variables
 175    that are read during the execution of the function FN.  Returns
 176    NULL if no data is available.  */
 177
 178 bitmap
 179 ipa_reference_get_read_global (tree fn)
 180 {
 181   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
 182   if (g)
 183     return g->statics_read;
 184   else
 185     return NULL;
 186 }
 187
 188 /* Return a bitmap indexed by VAR_DECL uid for the static variables
 189    that are written during the execution of the function FN.  Note
 190    that variables written may or may not be read during the function
 191    call.  Returns NULL if no data is available.  */
 192
 193 bitmap
 194 ipa_reference_get_written_global (tree fn)
 195 {
 196   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
 197   if (g)
 198     return g->statics_written;
 199   else
 200     return NULL;
 201 }
 202
 203 /* Return a bitmap indexed by_DECL_UID uid for the static variables
 204    that are not read during the execution of the function FN.  Returns
 205    NULL if no data is available.  */
 206
 207 bitmap
 208 ipa_reference_get_not_read_global (tree fn)
 209 {
 210   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
 211   if (g)
 212     return g->statics_not_read;
 213   else
 214     return NULL;
 215 }
 216
 217 /* Return a bitmap indexed by DECL_UID uid for the static variables
 218    that are not written during the execution of the function FN.  Note
 219    that variables written may or may not be read during the function
 220    call.  Returns NULL if no data is available.  */
 221
 222 bitmap
 223 ipa_reference_get_not_written_global (tree fn)
 224 {
 225   ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn);
 226   if (g)
 227     return g->statics_not_written;
 228   else
 229     return NULL;
 230 }
 231
 232 \f
 233
 234 /* Add VAR to all_module_statics and the two
 235    reference_vars_to_consider* sets.  */
 236
 237 static inline void
 238 add_static_var (tree var)
 239 {
 240   int uid = DECL_UID (var);
 241   if (!bitmap_bit_p (all_module_statics, uid))
 242     {
 243       splay_tree_insert (reference_vars_to_consider,
 244                          uid, (splay_tree_value)var);
 245       bitmap_set_bit (all_module_statics, uid);
 246     }
 247 }
 248
 249 /* Return true if the variable T is the right kind of static variable to
 250    perform compilation unit scope escape analysis.  */
 251
 252 static inline bool
 253 has_proper_scope_for_analysis (tree t)
 254 {
 255   /* If the variable has the "used" attribute, treat it as if it had a
 256      been touched by the devil.  */
 257   if (lookup_attribute ("used", DECL_ATTRIBUTES (t)))
 258     return false;
 259
 260   /* Do not want to do anything with volatile except mark any
 261      function that uses one to be not const or pure.  */
 262   if (TREE_THIS_VOLATILE (t))
 263     return false;
 264
 265   /* Do not care about a local automatic that is not static.  */
 266   if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
 267     return false;
 268
 269   if (DECL_EXTERNAL (t) || TREE_PUBLIC (t))
 270     return false;
 271
 272   /* This is a variable we care about.  Check if we have seen it
 273      before, and if not add it the set of variables we care about.  */
 274   if (!bitmap_bit_p (all_module_statics, DECL_UID (t)))
 275     add_static_var (t);
 276
 277   return true;
 278 }
 279
 280 /* If T is a VAR_DECL for a static that we are interested in, add the
 281    uid to the bitmap.  */
 282
 283 static void
 284 check_operand (ipa_reference_local_vars_info_t local,
 285                tree t, bool checking_write)
 286 {
 287   if (!t) return;
 288
 289   if ((TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == FUNCTION_DECL)
 290       && (has_proper_scope_for_analysis (t)))
 291     {
 292       if (checking_write)
 293         {
 294           if (local)
 295             bitmap_set_bit (local->statics_written, DECL_UID (t));
 296           /* Mark the write so we can tell which statics are
 297              readonly.  */
 298           bitmap_set_bit (module_statics_written, DECL_UID (t));
 299         }
 300       else if (local)
 301         bitmap_set_bit (local->statics_read, DECL_UID (t));
 302     }
 303 }
 304
 305 /* Examine tree T for references to static variables. All internal
 306    references like array references or indirect references are added
 307    to the READ_BM. Direct references are added to either READ_BM or
 308    WRITE_BM depending on the value of CHECKING_WRITE.   */
 309
 310 static void
 311 check_tree (ipa_reference_local_vars_info_t local, tree t, bool checking_write)
 312 {
 313   if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
 314     return;
 315
 316   while (TREE_CODE (t) == REALPART_EXPR
 317          || TREE_CODE (t) == IMAGPART_EXPR
 318          || handled_component_p (t))
 319     {
 320       if (TREE_CODE (t) == ARRAY_REF)
 321         check_operand (local, TREE_OPERAND (t, 1), false);
 322       t = TREE_OPERAND (t, 0);
 323     }
 324
 325   /* The bottom of an indirect reference can only be read, not
 326      written.  So just recurse and whatever we find, check it against
 327      the read bitmaps.  */
 328
 329   /*  if (INDIRECT_REF_P (t) || TREE_CODE (t) == MEM_REF) */
 330   /* FIXME when we have array_ref's of pointers.  */
 331   if (INDIRECT_REF_P (t))
 332     check_tree (local, TREE_OPERAND (t, 0), false);
 333
 334   if (SSA_VAR_P (t))
 335     check_operand (local, t, checking_write);
 336 }
 337
 338 /* Scan tree T to see if there are any addresses taken in within T.  */
 339
 340 static void
 341 look_for_address_of (tree t)
 342 {
 343   if (TREE_CODE (t) == ADDR_EXPR)
 344     {
 345       tree x = get_base_var (t);
 346       if (TREE_CODE (x) == VAR_DECL || TREE_CODE (x) == FUNCTION_DECL)
 347         if (has_proper_scope_for_analysis (x))
 348           bitmap_set_bit (module_statics_escape, DECL_UID (x));
 349     }
 350 }
 351
 352 /* Check to see if T is a read or address of operation on a static var
 353    we are interested in analyzing.  LOCAL is passed in to get access
 354    to its bit vectors.  Local is NULL if this is called from a static
 355    initializer.  */
 356
 357 static void
 358 check_rhs_var (ipa_reference_local_vars_info_t local, tree t)
 359 {
 360   look_for_address_of (t);
 361
 362   if (local == NULL)
 363     return;
 364
 365   check_tree(local, t, false);
 366 }
 367
 368 /* Check to see if T is an assignment to a static var we are
 369    interested in analyzing.  LOCAL is passed in to get access to its bit
 370    vectors.  */
 371
 372 static void
 373 check_lhs_var (ipa_reference_local_vars_info_t local, tree t)
 374 {
 375   if (local == NULL)
 376     return;
 377
 378   check_tree(local, t, true);
 379 }
 380
 381 /* This is a scaled down version of get_asm_expr_operands from
 382    tree_ssa_operands.c.  The version there runs much later and assumes
 383    that aliasing information is already available. Here we are just
 384    trying to find if the set of inputs and outputs contain references
 385    or address of operations to local static variables.  FN is the
 386    function being analyzed and STMT is the actual asm statement.  */
 387
 388 static void
 389 get_asm_expr_operands (ipa_reference_local_vars_info_t local, tree stmt)
 390 {
 391   int noutputs = list_length (ASM_OUTPUTS (stmt));
 392   const char **oconstraints
 393     = (const char **) alloca ((noutputs) * sizeof (const char *));
 394   int i;
 395   tree link;
 396   const char *constraint;
 397   bool allows_mem, allows_reg, is_inout;
 398
 399   for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link))
 400     {
 401       oconstraints[i] = constraint
 402         = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
 403       parse_output_constraint (&constraint, i, 0, 0,
 404                                &allows_mem, &allows_reg, &is_inout);
 405
 406       check_lhs_var (local, TREE_VALUE (link));
 407     }
 408
 409   for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
 410     {
 411       constraint
 412         = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
 413       parse_input_constraint (&constraint, 0, 0, noutputs, 0,
 414                               oconstraints, &allows_mem, &allows_reg);
 415
 416       check_rhs_var (local, TREE_VALUE (link));
 417     }
 418
 419   for (link = ASM_CLOBBERS (stmt); link; link = TREE_CHAIN (link))
 420     if (simple_cst_equal(TREE_VALUE (link), memory_identifier_string) == 1)
 421       {
 422         /* Abandon all hope, ye who enter here. */
 423         local->calls_read_all = true;
 424         local->calls_write_all = true;
 425       }
 426 }
 427
 428 /* Check the parameters of a function call from CALLER to CALL_EXPR to
 429    see if any of them are static vars.  Also check to see if this is
 430    either an indirect call, a call outside the compilation unit, or
 431    has special attributes that effect the clobbers.  The caller
 432    parameter is the tree node for the caller and the second operand is
 433    the tree node for the entire call expression.  */
 434
 435 static void
 436 check_call (ipa_reference_local_vars_info_t local, tree call_expr)
 437 {
 438   int flags = call_expr_flags (call_expr);
 439   tree operand_list = TREE_OPERAND (call_expr, 1);
 440   tree operand;
 441   tree callee_t = get_callee_fndecl (call_expr);
 442   enum availability avail = AVAIL_NOT_AVAILABLE;
 443
 444   for (operand = operand_list;
 445        operand != NULL_TREE;
 446        operand = TREE_CHAIN (operand))
 447     {
 448       tree argument = TREE_VALUE (operand);
 449       check_rhs_var (local, argument);
 450     }
 451
 452   if (callee_t)
 453     {
 454       struct cgraph_node* callee = cgraph_node(callee_t);
 455       avail = cgraph_function_body_availability (callee);
 456     }
 457
 458   if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
 459     if (local)
 460       {
 461         if (flags & ECF_PURE)
 462           local->calls_read_all = true;
 463         else
 464           {
 465             local->calls_read_all = true;
 466             local->calls_write_all = true;
 467           }
 468       }
 469 }
 470
 471 /* TP is the part of the tree currently under the microscope.
 472    WALK_SUBTREES is part of the walk_tree api but is unused here.
 473    DATA is cgraph_node of the function being walked.  */
 474
 475 /* FIXME: When this is converted to run over SSA form, this code
 476    should be converted to use the operand scanner.  */
 477
 478 static tree
 479 scan_for_static_refs (tree *tp,
 480                       int *walk_subtrees,
 481                       void *data)
 482 {
 483   struct cgraph_node *fn = data;
 484   tree t = *tp;
 485   ipa_reference_local_vars_info_t local = NULL;
 486   if (fn)
 487     local = get_reference_vars_info_from_cgraph (fn)->local;
 488
 489   switch (TREE_CODE (t))
 490     {
 491     case VAR_DECL:
 492       if (DECL_INITIAL (t))
 493         walk_tree (&DECL_INITIAL (t), scan_for_static_refs, fn, visited_nodes);
 494       *walk_subtrees = 0;
 495       break;
 496
 497     case MODIFY_EXPR:
 498       {
 499         /* First look on the lhs and see what variable is stored to */
 500         tree lhs = TREE_OPERAND (t, 0);
 501         tree rhs = TREE_OPERAND (t, 1);
 502         check_lhs_var (local, lhs);
 503
 504         /* For the purposes of figuring out what the cast affects */
 505
 506         /* Next check the operands on the rhs to see if they are ok. */
 507         switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
 508           {
 509           case tcc_binary:
 510           case tcc_comparison:
 511             {
 512               tree op0 = TREE_OPERAND (rhs, 0);
 513               tree op1 = TREE_OPERAND (rhs, 1);
 514               check_rhs_var (local, op0);
 515               check_rhs_var (local, op1);
 516             }
 517             break;
 518           case tcc_unary:
 519             {
 520               tree op0 = TREE_OPERAND (rhs, 0);
 521               check_rhs_var (local, op0);
 522             }
 523
 524             break;
 525           case tcc_reference:
 526             check_rhs_var (local, rhs);
 527             break;
 528           case tcc_declaration:
 529             check_rhs_var (local, rhs);
 530             break;
 531           case tcc_expression:
 532             switch (TREE_CODE (rhs))
 533               {
 534               case ADDR_EXPR:
 535                 check_rhs_var (local, rhs);
 536                 break;
 537               case CALL_EXPR:
 538                 check_call (local, rhs);
 539                 break;
 540               default:
 541                 break;
 542               }
 543             break;
 544           default:
 545             break;
 546           }
 547         *walk_subtrees = 0;
 548       }
 549       break;
 550
 551     case ADDR_EXPR:
 552       /* This case is here to find addresses on rhs of constructors in
 553          decl_initial of static variables. */
 554       check_rhs_var (local, t);
 555       *walk_subtrees = 0;
 556       break;
 557
 558     case LABEL_EXPR:
 559       if (DECL_NONLOCAL (TREE_OPERAND (t, 0)))
 560         {
 561           /* Target of long jump. */
 562           local->calls_read_all = true;
 563           local->calls_write_all = true;
 564         }
 565       break;
 566
 567     case CALL_EXPR:
 568       check_call (local, t);
 569       *walk_subtrees = 0;
 570       break;
 571
 572     case ASM_EXPR:
 573       get_asm_expr_operands (local, t);
 574       *walk_subtrees = 0;
 575       break;
 576
 577     default:
 578       break;
 579     }
 580   return NULL;
 581 }
 582
 583
 584 /* Lookup the tree node for the static variable that has UID.  */
 585 static tree
 586 get_static_decl (int index)
 587 {
 588   splay_tree_node stn =
 589     splay_tree_lookup (reference_vars_to_consider, index);
 590   if (stn)
 591     return (tree)stn->value;
 592   return NULL;
 593 }
 594
 595 /* Lookup the tree node for the static variable that has UID and
 596    convert the name to a string for debugging.  */
 597
 598 static const char *
 599 get_static_name (int index)
 600 {
 601   splay_tree_node stn =
 602     splay_tree_lookup (reference_vars_to_consider, index);
 603   if (stn)
 604     return lang_hooks.decl_printable_name ((tree)(stn->value), 2);
 605   return NULL;
 606 }
 607
 608 /* Or in all of the bits from every callee into X, the caller's, bit
 609    vector.  There are several cases to check to avoid the sparse
 610    bitmap oring.  */
 611
 612 static void
 613 propagate_bits (struct cgraph_node *x)
 614 {
 615   ipa_reference_vars_info_t x_info = get_reference_vars_info_from_cgraph (x);
 616   ipa_reference_global_vars_info_t x_global = x_info->global;
 617
 618   struct cgraph_edge *e;
 619   for (e = x->callees; e; e = e->next_callee)
 620     {
 621       struct cgraph_node *y = e->callee;
 622
 623       /* Only look at the master nodes and skip external nodes.  */
 624       y = cgraph_master_clone (y);
 625       if (y)
 626         {
 627           if (get_reference_vars_info_from_cgraph (y))
 628             {
 629               ipa_reference_vars_info_t y_info = get_reference_vars_info_from_cgraph (y);
 630               ipa_reference_global_vars_info_t y_global = y_info->global;
 631
 632               if (x_global->statics_read
 633                   != all_module_statics)
 634                 {
 635                   if (y_global->statics_read
 636                       == all_module_statics)
 637                     {
 638                       BITMAP_FREE (x_global->statics_read);
 639                       x_global->statics_read
 640                         = all_module_statics;
 641                     }
 642                   /* Skip bitmaps that are pointer equal to node's bitmap
 643                      (no reason to spin within the cycle).  */
 644                   else if (x_global->statics_read
 645                            != y_global->statics_read)
 646                     bitmap_ior_into (x_global->statics_read,
 647                                      y_global->statics_read);
 648                 }
 649
 650               if (x_global->statics_written
 651                   != all_module_statics)
 652                 {
 653                   if (y_global->statics_written
 654                       == all_module_statics)
 655                     {
 656                       BITMAP_FREE (x_global->statics_written);
 657                       x_global->statics_written
 658                         = all_module_statics;
 659                     }
 660                   /* Skip bitmaps that are pointer equal to node's bitmap
 661                      (no reason to spin within the cycle).  */
 662                   else if (x_global->statics_written
 663                            != y_global->statics_written)
 664                     bitmap_ior_into (x_global->statics_written,
 665                                      y_global->statics_written);
 666                 }
 667             }
 668           else
 669             {
 670               gcc_unreachable ();
 671             }
 672         }
 673     }
 674 }
 675
 676 /* Look at all of the callees of X to see which ones represent inlined
 677    calls.  For each of these callees, merge their local info into
 678    TARGET and check their children recursively.
 679
 680    This function goes away when Jan changes the inliner and IPA
 681    analysis so that this is not run between the time when inlining
 682    decisions are made and when the inlining actually occurs.  */
 683
 684 static void
 685 merge_callee_local_info (struct cgraph_node *target,
 686                          struct cgraph_node *x)
 687 {
 688   struct cgraph_edge *e;
 689   ipa_reference_local_vars_info_t x_l =
 690     get_reference_vars_info_from_cgraph (target)->local;
 691
 692   /* Make the world safe for tail recursion.  */
 693   struct ipa_dfs_info *node_info = x->aux;
 694
 695   if (node_info->aux)
 696     return;
 697
 698   node_info->aux = x;
 699
 700   for (e = x->callees; e; e = e->next_callee)
 701     {
 702       struct cgraph_node *y = e->callee;
 703       if (y->global.inlined_to)
 704         {
 705           ipa_reference_vars_info_t y_info;
 706           ipa_reference_local_vars_info_t y_l;
 707           struct cgraph_node* orig_y = y;
 708
 709           y = cgraph_master_clone (y);
 710           if (y)
 711             {
 712               y_info = get_reference_vars_info_from_cgraph (y);
 713               y_l = y_info->local;
 714               if (x_l != y_l)
 715                 {
 716                   bitmap_ior_into (x_l->statics_read,
 717                                    y_l->statics_read);
 718                   bitmap_ior_into (x_l->statics_written,
 719                                    y_l->statics_written);
 720                 }
 721               x_l->calls_read_all |= y_l->calls_read_all;
 722               x_l->calls_write_all |= y_l->calls_write_all;
 723               merge_callee_local_info (target, y);
 724             }
 725           else
 726             {
 727               fprintf(stderr, "suspect inlining of ");
 728               dump_cgraph_node (stderr, orig_y);
 729               fprintf(stderr, "\ninto ");
 730               dump_cgraph_node (stderr, target);
 731               dump_cgraph (stderr);
 732               gcc_assert(false);
 733             }
 734         }
 735     }
 736
 737   node_info->aux = NULL;
 738 }
 739
 740 /* The init routine for analyzing global static variable usage.  See
 741    comments at top for description.  */
 742 static void
 743 ipa_init (void)
 744 {
 745   struct cgraph_node *node;
 746   memory_identifier_string = build_string(7, "memory");
 747
 748   reference_vars_to_consider =
 749     splay_tree_new_ggc (splay_tree_compare_ints);
 750
 751   bitmap_obstack_initialize (&ipa_obstack);
 752   module_statics_escape = BITMAP_ALLOC (&ipa_obstack);
 753   module_statics_written = BITMAP_ALLOC (&ipa_obstack);
 754   all_module_statics = BITMAP_ALLOC (&ipa_obstack);
 755
 756   /* This will add NODE->DECL to the splay trees.  */
 757   for (node = cgraph_nodes; node; node = node->next)
 758     has_proper_scope_for_analysis (node->decl);
 759
 760   /* There are some shared nodes, in particular the initializers on
 761      static declarations.  We do not need to scan them more than once
 762      since all we would be interested in are the addressof
 763      operations.  */
 764   visited_nodes = pointer_set_create ();
 765 }
 766
 767 /* Check out the rhs of a static or global initialization VNODE to see
 768    if any of them contain addressof operations.  Note that some of
 769    these variables may  not even be referenced in the code in this
 770    compilation unit but their right hand sides may contain references
 771    to variables defined within this unit.  */
 772
 773 static void
 774 analyze_variable (struct cgraph_varpool_node *vnode)
 775 {
 776   tree global = vnode->decl;
 777   if (TREE_CODE (global) == VAR_DECL)
 778     {
 779       if (DECL_INITIAL (global))
 780         walk_tree (&DECL_INITIAL (global), scan_for_static_refs,
 781                    NULL, visited_nodes);
 782     }
 783   else gcc_unreachable ();
 784 }
 785
 786 /* This is the main routine for finding the reference patterns for
 787    global variables within a function FN.  */
 788
 789 static void
 790 analyze_function (struct cgraph_node *fn)
 791 {
 792   ipa_reference_vars_info_t info
 793     = xcalloc (1, sizeof (struct ipa_reference_vars_info_d));
 794   ipa_reference_local_vars_info_t l
 795     = xcalloc (1, sizeof (struct ipa_reference_local_vars_info_d));
 796   tree decl = fn->decl;
 797
 798   /* Add the info to the tree's annotation.  */
 799   get_function_ann (fn->decl)->reference_vars_info = info;
 800
 801   info->local = l;
 802   l->statics_read = BITMAP_ALLOC (&ipa_obstack);
 803   l->statics_written = BITMAP_ALLOC (&ipa_obstack);
 804
 805   if (dump_file)
 806     fprintf (dump_file, "\n local analysis of %s\n", cgraph_node_name (fn));
 807
 808   {
 809     struct function *this_cfun = DECL_STRUCT_FUNCTION (decl);
 810     basic_block this_block;
 811
 812     FOR_EACH_BB_FN (this_block, this_cfun)
 813       {
 814         block_stmt_iterator bsi;
 815         for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
 816           walk_tree (bsi_stmt_ptr (bsi), scan_for_static_refs,
 817                      fn, visited_nodes);
 818       }
 819   }
 820
 821   /* There may be const decls with interesting right hand sides.  */
 822   if (DECL_STRUCT_FUNCTION (decl))
 823     {
 824       tree step;
 825       for (step = DECL_STRUCT_FUNCTION (decl)->unexpanded_var_list;
 826            step;
 827            step = TREE_CHAIN (step))
 828         {
 829           tree var = TREE_VALUE (step);
 830           if (TREE_CODE (var) == VAR_DECL
 831               && DECL_INITIAL (var)
 832               && !TREE_STATIC (var))
 833             walk_tree (&DECL_INITIAL (var), scan_for_static_refs,
 834                        fn, visited_nodes);
 835         }
 836     }
 837 }
 838
 839 /* If FN is avail == AVAIL_OVERWRITABLE, replace the effects bit
 840    vectors with worst case bit vectors.  We had to analyze it above to
 841    find out if it took the address of any statics. However, now that
 842    we know that, we can get rid of all of the other side effects.  */
 843
 844 static void
 845 clean_function (struct cgraph_node *fn)
 846 {
 847   ipa_reference_vars_info_t info = get_reference_vars_info_from_cgraph (fn);
 848   ipa_reference_local_vars_info_t l = info->local;
 849   ipa_reference_global_vars_info_t g = info->global;
 850
 851   if (l)
 852     {
 853       if (l->statics_read
 854           && l->statics_read != all_module_statics)
 855         BITMAP_FREE (l->statics_read);
 856       if (l->statics_written
 857           &&l->statics_written != all_module_statics)
 858         BITMAP_FREE (l->statics_written);
 859       free (l);
 860     }
 861
 862   if (g)
 863     {
 864       if (g->statics_read
 865           && g->statics_read != all_module_statics)
 866         BITMAP_FREE (g->statics_read);
 867
 868       if (g->statics_written
 869           && g->statics_written != all_module_statics)
 870         BITMAP_FREE (g->statics_written);
 871
 872       if (g->statics_not_read
 873           && g->statics_not_read != all_module_statics)
 874         BITMAP_FREE (g->statics_not_read);
 875
 876       if (g->statics_not_written
 877           && g->statics_not_written != all_module_statics)
 878         BITMAP_FREE (g->statics_not_written);
 879       free (g);
 880     }
 881
 882
 883   free (get_function_ann (fn->decl)->reference_vars_info);
 884   get_function_ann (fn->decl)->reference_vars_info = NULL;
 885 }
 886
 887 \f
 888 /* Produce the global information by preforming a transitive closure
 889    on the local information that was produced by ipa_analyze_function
 890    and ipa_analyze_variable.  */
 891
 892 static unsigned int
 893 static_execute (void)
 894 {
 895   struct cgraph_node *node;
 896   struct cgraph_varpool_node *vnode;
 897   struct cgraph_node *w;
 898   struct cgraph_node **order =
 899     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
 900   int order_pos = order_pos = ipa_utils_reduced_inorder (order, false, true);
 901   int i;
 902
 903   ipa_init ();
 904
 905   /* Process all of the variables first.  */
 906   for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 907     analyze_variable (vnode);
 908
 909   /* Process all of the functions next.
 910
 911      We do not want to process any of the clones so we check that this
 912      is a master clone.  However, we do need to process any
 913      AVAIL_OVERWRITABLE functions (these are never clones) because
 914      they may cause a static variable to escape.  The code that can
 915      overwrite such a function cannot access the statics because it
 916      would not be in the same compilation unit.  When the analysis is
 917      finished, the computed information of these AVAIL_OVERWRITABLE is
 918      replaced with worst case info.
 919   */
 920   for (node = cgraph_nodes; node; node = node->next)
 921     if (node->analyzed
 922         && (cgraph_is_master_clone (node)
 923             || (cgraph_function_body_availability (node)
 924                 == AVAIL_OVERWRITABLE)))
 925       analyze_function (node);
 926
 927   pointer_set_destroy (visited_nodes);
 928   visited_nodes = NULL;
 929   if (dump_file)
 930     dump_cgraph (dump_file);
 931
 932   /* Prune out the variables that were found to behave badly
 933      (i.e. have their address taken).  */
 934   {
 935     unsigned int index;
 936     bitmap_iterator bi;
 937     bitmap module_statics_readonly = BITMAP_ALLOC (&ipa_obstack);
 938     bitmap module_statics_const = BITMAP_ALLOC (&ipa_obstack);
 939     bitmap bm_temp = BITMAP_ALLOC (&ipa_obstack);
 940
 941     EXECUTE_IF_SET_IN_BITMAP (module_statics_escape, 0, index, bi)
 942       {
 943         splay_tree_remove (reference_vars_to_consider, index);
 944       }
 945
 946     bitmap_and_compl_into (all_module_statics,
 947                            module_statics_escape);
 948
 949     bitmap_and_compl (module_statics_readonly, all_module_statics,
 950                       module_statics_written);
 951
 952     /* If the address is not taken, we can unset the addressable bit
 953        on this variable.  */
 954     EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
 955       {
 956         tree var = get_static_decl (index);
 957         TREE_ADDRESSABLE (var) = 0;
 958         if (dump_file)
 959           fprintf (dump_file, "Not TREE_ADDRESSABLE var %s\n",
 960                    get_static_name (index));
 961       }
 962
 963     /* If the variable is never written, we can set the TREE_READONLY
 964        flag.  Additionally if it has a DECL_INITIAL that is made up of
 965        constants we can treat the entire global as a constant.  */
 966
 967     bitmap_and_compl (module_statics_readonly, all_module_statics,
 968                       module_statics_written);
 969     EXECUTE_IF_SET_IN_BITMAP (module_statics_readonly, 0, index, bi)
 970       {
 971         tree var = get_static_decl (index);
 972
 973         /* Readonly on a function decl is very different from the
 974            variable.  */
 975         if (TREE_CODE (var) == FUNCTION_DECL)
 976           continue;
 977
 978         /* Ignore variables in named sections - changing TREE_READONLY
 979            changes the section flags, potentially causing conflicts with
 980            other variables in the same named section.  */
 981         if (DECL_SECTION_NAME (var) == NULL_TREE)
 982           {
 983             TREE_READONLY (var) = 1;
 984             if (dump_file)
 985               fprintf (dump_file, "read-only var %s\n",
 986                        get_static_name (index));
 987           }
 988         if (DECL_INITIAL (var)
 989             && is_gimple_min_invariant (DECL_INITIAL (var)))
 990           {
 991             bitmap_set_bit (module_statics_const, index);
 992             if (dump_file)
 993               fprintf (dump_file, "read-only constant %s\n",
 994                        get_static_name (index));
 995           }
 996       }
 997
 998     BITMAP_FREE(module_statics_escape);
 999     BITMAP_FREE(module_statics_written);
1000
1001     if (dump_file)
1002       EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
1003         {
1004           fprintf (dump_file, "\nPromotable global:%s",
1005                    get_static_name (index));
1006         }
1007
1008     for (i = 0; i < order_pos; i++ )
1009       {
1010         ipa_reference_local_vars_info_t l;
1011         node = order[i];
1012         l = get_reference_vars_info_from_cgraph (node)->local;
1013
1014         /* Any variables that are not in all_module_statics are
1015            removed from the local maps.  This will include all of the
1016            variables that were found to escape in the function
1017            scanning.  */
1018         bitmap_and_into (l->statics_read,
1019                          all_module_statics);
1020         bitmap_and_into (l->statics_written,
1021                          all_module_statics);
1022       }
1023
1024     BITMAP_FREE(module_statics_readonly);
1025     BITMAP_FREE(module_statics_const);
1026     BITMAP_FREE(bm_temp);
1027   }
1028
1029   if (dump_file)
1030     {
1031       for (i = 0; i < order_pos; i++ )
1032         {
1033           unsigned int index;
1034           ipa_reference_local_vars_info_t l;
1035           bitmap_iterator bi;
1036
1037           node = order[i];
1038           l = get_reference_vars_info_from_cgraph (node)->local;
1039           fprintf (dump_file,
1040                    "\nFunction name:%s/%i:",
1041                    cgraph_node_name (node), node->uid);
1042           fprintf (dump_file, "\n  locals read: ");
1043           EXECUTE_IF_SET_IN_BITMAP (l->statics_read,
1044                                     0, index, bi)
1045             {
1046               fprintf (dump_file, "%s ",
1047                        get_static_name (index));
1048             }
1049           fprintf (dump_file, "\n  locals written: ");
1050           EXECUTE_IF_SET_IN_BITMAP (l->statics_written,
1051                                     0, index, bi)
1052             {
1053               fprintf(dump_file, "%s ",
1054                       get_static_name (index));
1055             }
1056         }
1057     }
1058
1059   /* Propagate the local information thru the call graph to produce
1060      the global information.  All the nodes within a cycle will have
1061      the same info so we collapse cycles first.  Then we can do the
1062      propagation in one pass from the leaves to the roots.  */
1063   order_pos = ipa_utils_reduced_inorder (order, true, true);
1064   if (dump_file)
1065     ipa_utils_print_order(dump_file, "reduced", order, order_pos);
1066
1067   for (i = 0; i < order_pos; i++ )
1068     {
1069       ipa_reference_vars_info_t node_info;
1070       ipa_reference_global_vars_info_t node_g =
1071         xcalloc (1, sizeof (struct ipa_reference_global_vars_info_d));
1072       ipa_reference_local_vars_info_t node_l;
1073
1074       bool read_all;
1075       bool write_all;
1076       struct ipa_dfs_info * w_info;
1077
1078       node = order[i];
1079       node_info = get_reference_vars_info_from_cgraph (node);
1080       if (!node_info)
1081         {
1082           dump_cgraph_node (stderr, node);
1083           dump_cgraph (stderr);
1084           gcc_unreachable ();
1085         }
1086
1087       node_info->global = node_g;
1088       node_l = node_info->local;
1089
1090       read_all = node_l->calls_read_all;
1091       write_all = node_l->calls_write_all;
1092
1093       /* If any node in a cycle is calls_read_all or calls_write_all
1094          they all are. */
1095       w_info = node->aux;
1096       w = w_info->next_cycle;
1097       while (w)
1098         {
1099           ipa_reference_local_vars_info_t w_l =
1100             get_reference_vars_info_from_cgraph (w)->local;
1101           read_all |= w_l->calls_read_all;
1102           write_all |= w_l->calls_write_all;
1103
1104           w_info = w->aux;
1105           w = w_info->next_cycle;
1106         }
1107
1108       /* Initialized the bitmaps for the reduced nodes */
1109       if (read_all)
1110         node_g->statics_read = all_module_statics;
1111       else
1112         {
1113           node_g->statics_read = BITMAP_ALLOC (&ipa_obstack);
1114           bitmap_copy (node_g->statics_read,
1115                        node_l->statics_read);
1116         }
1117
1118       if (write_all)
1119         node_g->statics_written = all_module_statics;
1120       else
1121         {
1122           node_g->statics_written = BITMAP_ALLOC (&ipa_obstack);
1123           bitmap_copy (node_g->statics_written,
1124                        node_l->statics_written);
1125         }
1126
1127       w_info = node->aux;
1128       w = w_info->next_cycle;
1129       while (w)
1130         {
1131           ipa_reference_vars_info_t w_ri =
1132             get_reference_vars_info_from_cgraph (w);
1133           ipa_reference_local_vars_info_t w_l = w_ri->local;
1134
1135           /* All nodes within a cycle share the same global info bitmaps.  */
1136           w_ri->global = node_g;
1137
1138           /* These global bitmaps are initialized from the local info
1139              of all of the nodes in the region.  However there is no
1140              need to do any work if the bitmaps were set to
1141              all_module_statics.  */
1142           if (!read_all)
1143             bitmap_ior_into (node_g->statics_read,
1144                              w_l->statics_read);
1145           if (!write_all)
1146             bitmap_ior_into (node_g->statics_written,
1147                              w_l->statics_written);
1148           w_info = w->aux;
1149           w = w_info->next_cycle;
1150         }
1151
1152       w = node;
1153       while (w)
1154         {
1155           propagate_bits (w);
1156           w_info = w->aux;
1157           w = w_info->next_cycle;
1158         }
1159     }
1160
1161   /* Need to fix up the local information sets.  The information that
1162      has been gathered so far is preinlining.  However, the
1163      compilation will progress post inlining so the local sets for the
1164      inlined calls need to be merged into the callers.  Note that the
1165      local sets are not shared between all of the nodes in a cycle so
1166      those nodes in the cycle must be processed explicitly.  */
1167   for (i = 0; i < order_pos; i++ )
1168     {
1169       struct ipa_dfs_info * w_info;
1170       node = order[i];
1171       merge_callee_local_info (node, node);
1172
1173       w_info = node->aux;
1174       w = w_info->next_cycle;
1175       while (w)
1176         {
1177           merge_callee_local_info (w, w);
1178           w_info = w->aux;
1179           w = w_info->next_cycle;
1180         }
1181     }
1182
1183   if (dump_file)
1184     {
1185       for (i = 0; i < order_pos; i++ )
1186         {
1187           ipa_reference_vars_info_t node_info;
1188           ipa_reference_global_vars_info_t node_g;
1189           ipa_reference_local_vars_info_t node_l;
1190           unsigned int index;
1191           bitmap_iterator bi;
1192           struct ipa_dfs_info * w_info;
1193
1194           node = order[i];
1195           node_info = get_reference_vars_info_from_cgraph (node);
1196           node_g = node_info->global;
1197           node_l = node_info->local;
1198           fprintf (dump_file,
1199                    "\nFunction name:%s/%i:",
1200                    cgraph_node_name (node), node->uid);
1201           fprintf (dump_file, "\n  locals read: ");
1202           EXECUTE_IF_SET_IN_BITMAP (node_l->statics_read,
1203                                     0, index, bi)
1204             {
1205               fprintf (dump_file, "%s ",
1206                        get_static_name (index));
1207             }
1208           fprintf (dump_file, "\n  locals written: ");
1209           EXECUTE_IF_SET_IN_BITMAP (node_l->statics_written,
1210                                     0, index, bi)
1211             {
1212               fprintf(dump_file, "%s ",
1213                       get_static_name (index));
1214             }
1215
1216           w_info = node->aux;
1217           w = w_info->next_cycle;
1218           while (w)
1219             {
1220               ipa_reference_vars_info_t w_ri =
1221                 get_reference_vars_info_from_cgraph (w);
1222               ipa_reference_local_vars_info_t w_l = w_ri->local;
1223               fprintf (dump_file, "\n  next cycle: %s/%i ",
1224                        cgraph_node_name (w), w->uid);
1225               fprintf (dump_file, "\n    locals read: ");
1226               EXECUTE_IF_SET_IN_BITMAP (w_l->statics_read,
1227                                         0, index, bi)
1228                 {
1229                   fprintf (dump_file, "%s ",
1230                            get_static_name (index));
1231                 }
1232
1233               fprintf (dump_file, "\n    locals written: ");
1234               EXECUTE_IF_SET_IN_BITMAP (w_l->statics_written,
1235                                         0, index, bi)
1236                 {
1237                   fprintf(dump_file, "%s ",
1238                           get_static_name (index));
1239                 }
1240
1241
1242               w_info = w->aux;
1243               w = w_info->next_cycle;
1244             }
1245           fprintf (dump_file, "\n  globals read: ");
1246           EXECUTE_IF_SET_IN_BITMAP (node_g->statics_read,
1247                                     0, index, bi)
1248             {
1249               fprintf (dump_file, "%s ",
1250                        get_static_name (index));
1251             }
1252           fprintf (dump_file, "\n  globals written: ");
1253           EXECUTE_IF_SET_IN_BITMAP (node_g->statics_written,
1254                                     0, index, bi)
1255             {
1256               fprintf (dump_file, "%s ",
1257                        get_static_name (index));
1258             }
1259         }
1260     }
1261
1262   /* Cleanup. */
1263   for (i = 0; i < order_pos; i++ )
1264     {
1265       ipa_reference_vars_info_t node_info;
1266       ipa_reference_global_vars_info_t node_g;
1267       node = order[i];
1268       node_info = get_reference_vars_info_from_cgraph (node);
1269       node_g = node_info->global;
1270
1271       /* Create the complimentary sets.  These are more useful for
1272          certain apis.  */
1273       node_g->statics_not_read = BITMAP_ALLOC (&ipa_obstack);
1274       node_g->statics_not_written = BITMAP_ALLOC (&ipa_obstack);
1275
1276       if (node_g->statics_read != all_module_statics)
1277         {
1278           bitmap_and_compl (node_g->statics_not_read,
1279                             all_module_statics,
1280                             node_g->statics_read);
1281         }
1282
1283       if (node_g->statics_written
1284           != all_module_statics)
1285         bitmap_and_compl (node_g->statics_not_written,
1286                           all_module_statics,
1287                           node_g->statics_written);
1288    }
1289
1290   free (order);
1291
1292   for (node = cgraph_nodes; node; node = node->next)
1293     {
1294       /* Get rid of the aux information.  */
1295
1296       if (node->aux)
1297         {
1298           free (node->aux);
1299           node->aux = NULL;
1300         }
1301
1302       if (node->analyzed
1303           && (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE))
1304         clean_function (node);
1305     }
1306   return 0;
1307 }
1308
1309
1310 static bool
1311 gate_reference (void)
1312 {
1313   return (flag_unit_at_a_time != 0  && flag_ipa_reference
1314           /* Don't bother doing anything if the program has errors.  */
1315           && !(errorcount || sorrycount));
1316 }
1317
1318 struct tree_opt_pass pass_ipa_reference =
1319 {
1320   "static-var",                         /* name */
1321   gate_reference,                       /* gate */
1322   static_execute,                       /* execute */
1323   NULL,                                 /* sub */
1324   NULL,                                 /* next */
1325   0,                                    /* static_pass_number */
1326   TV_IPA_REFERENCE,                     /* tv_id */
1327   0,                                    /* properties_required */
1328   0,                                    /* properties_provided */
1329   0,                                    /* properties_destroyed */
1330   0,                                    /* todo_flags_start */
1331   0,                                    /* todo_flags_finish */
1332   0                                     /* letter */
1333 };
1334
1335 #include "gt-ipa-reference.h"
1336