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_var_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_var_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_var_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)
 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)
 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             {
 511               tree op0 = TREE_OPERAND (rhs, 0);
 512               tree op1 = TREE_OPERAND (rhs, 1);
 513               check_rhs_var (local, op0);
 514               check_rhs_var (local, op1);
 515             }
 516             break;
 517           case tcc_unary:
 518             {
 519               tree op0 = TREE_OPERAND (rhs, 0);
 520               check_rhs_var (local, op0);
 521             }
 522
 523             break;
 524           case tcc_reference:
 525             check_rhs_var (local, rhs);
 526             break;
 527           case tcc_declaration:
 528             check_rhs_var (local, rhs);
 529             break;
 530           case tcc_expression:
 531             switch (TREE_CODE (rhs))
 532               {
 533               case ADDR_EXPR:
 534                 check_rhs_var (local, rhs);
 535                 break;
 536               case CALL_EXPR:
 537                 check_call (local, rhs);
 538                 break;
 539               default:
 540                 break;
 541               }
 542             break;
 543           default:
 544             break;
 545           }
 546         *walk_subtrees = 0;
 547       }
 548       break;
 549
 550     case ADDR_EXPR:
 551       /* This case is here to find addresses on rhs of constructors in
 552          decl_initial of static variables. */
 553       check_rhs_var (local, t);
 554       *walk_subtrees = 0;
 555       break;
 556
 557     case LABEL_EXPR:
 558       if (DECL_NONLOCAL (TREE_OPERAND (t, 0)))
 559         {
 560           /* Target of long jump. */
 561           local->calls_read_all = true;
 562           local->calls_write_all = true;
 563         }
 564       break;
 565
 566     case CALL_EXPR:
 567       check_call (local, t);
 568       *walk_subtrees = 0;
 569       break;
 570
 571     case ASM_EXPR:
 572       get_asm_expr_operands (local, t);
 573       *walk_subtrees = 0;
 574       break;
 575
 576     default:
 577       break;
 578     }
 579   return NULL;
 580 }
 581
 582
 583 /* Lookup the tree node for the static variable that has UID.  */
 584 static tree
 585 get_static_decl (int index)
 586 {
 587   splay_tree_node stn =
 588     splay_tree_lookup (reference_vars_to_consider, index);
 589   if (stn)
 590     return (tree)stn->value;
 591   return NULL;
 592 }
 593
 594 /* Lookup the tree node for the static variable that has UID and
 595    convert the name to a string for debugging.  */
 596
 597 static const char *
 598 get_static_name (int index)
 599 {
 600   splay_tree_node stn =
 601     splay_tree_lookup (reference_vars_to_consider, index);
 602   if (stn)
 603     return lang_hooks.decl_printable_name ((tree)(stn->value), 2);
 604   return NULL;
 605 }
 606
 607 /* Or in all of the bits from every callee into X, the caller's, bit
 608    vector.  There are several cases to check to avoid the sparse
 609    bitmap oring.  */
 610
 611 static void
 612 propagate_bits (struct cgraph_node *x)
 613 {
 614   ipa_reference_vars_info_t x_info = get_reference_vars_info_from_cgraph (x);
 615   ipa_reference_global_vars_info_t x_global = x_info->global;
 616
 617   struct cgraph_edge *e;
 618   for (e = x->callees; e; e = e->next_callee)
 619     {
 620       struct cgraph_node *y = e->callee;
 621
 622       /* Only look at the master nodes and skip external nodes.  */
 623       y = cgraph_master_clone (y);
 624       if (y)
 625         {
 626           if (get_reference_vars_info_from_cgraph (y))
 627             {
 628               ipa_reference_vars_info_t y_info = get_reference_vars_info_from_cgraph (y);
 629               ipa_reference_global_vars_info_t y_global = y_info->global;
 630
 631               if (x_global->statics_read
 632                   != all_module_statics)
 633                 {
 634                   if (y_global->statics_read
 635                       == all_module_statics)
 636                     {
 637                       BITMAP_FREE (x_global->statics_read);
 638                       x_global->statics_read
 639                         = all_module_statics;
 640                     }
 641                   /* Skip bitmaps that are pointer equal to node's bitmap
 642                      (no reason to spin within the cycle).  */
 643                   else if (x_global->statics_read
 644                            != y_global->statics_read)
 645                     bitmap_ior_into (x_global->statics_read,
 646                                      y_global->statics_read);
 647                 }
 648
 649               if (x_global->statics_written
 650                   != all_module_statics)
 651                 {
 652                   if (y_global->statics_written
 653                       == all_module_statics)
 654                     {
 655                       BITMAP_FREE (x_global->statics_written);
 656                       x_global->statics_written
 657                         = all_module_statics;
 658                     }
 659                   /* Skip bitmaps that are pointer equal to node's bitmap
 660                      (no reason to spin within the cycle).  */
 661                   else if (x_global->statics_written
 662                            != y_global->statics_written)
 663                     bitmap_ior_into (x_global->statics_written,
 664                                      y_global->statics_written);
 665                 }
 666             }
 667           else
 668             {
 669               gcc_unreachable ();
 670             }
 671         }
 672     }
 673 }
 674
 675 /* Look at all of the callees of X to see which ones represent inlined
 676    calls.  For each of these callees, merge their local info into
 677    TARGET and check their children recursively.
 678
 679    This function goes away when Jan changes the inliner and IPA
 680    analysis so that this is not run between the time when inlining
 681    decisions are made and when the inlining actually occurs.  */
 682
 683 static void
 684 merge_callee_local_info (struct cgraph_node *target,
 685                          struct cgraph_node *x)
 686 {
 687   struct cgraph_edge *e;
 688   ipa_reference_local_vars_info_t x_l =
 689     get_reference_vars_info_from_cgraph (target)->local;
 690
 691   /* Make the world safe for tail recursion.  */
 692   struct ipa_dfs_info *node_info = x->aux;
 693
 694   if (node_info->aux)
 695     return;
 696
 697   node_info->aux = x;
 698
 699   for (e = x->callees; e; e = e->next_callee)
 700     {
 701       struct cgraph_node *y = e->callee;
 702       if (y->global.inlined_to)
 703         {
 704           ipa_reference_vars_info_t y_info;
 705           ipa_reference_local_vars_info_t y_l;
 706           struct cgraph_node* orig_y = y;
 707
 708           y = cgraph_master_clone (y);
 709           if (y)
 710             {
 711               y_info = get_reference_vars_info_from_cgraph (y);
 712               y_l = y_info->local;
 713               if (x_l != y_l)
 714                 {
 715                   bitmap_ior_into (x_l->statics_read,
 716                                    y_l->statics_read);
 717                   bitmap_ior_into (x_l->statics_written,
 718                                    y_l->statics_written);
 719                 }
 720               x_l->calls_read_all |= y_l->calls_read_all;
 721               x_l->calls_write_all |= y_l->calls_write_all;
 722               merge_callee_local_info (target, y);
 723             }
 724           else
 725             {
 726               fprintf(stderr, "suspect inlining of ");
 727               dump_cgraph_node (stderr, orig_y);
 728               fprintf(stderr, "\ninto ");
 729               dump_cgraph_node (stderr, target);
 730               dump_cgraph (stderr);
 731               gcc_assert(false);
 732             }
 733         }
 734     }
 735
 736   node_info->aux = NULL;
 737 }
 738
 739 /* The init routine for analyzing global static variable usage.  See
 740    comments at top for description.  */
 741 static void
 742 ipa_init (void)
 743 {
 744   memory_identifier_string = build_string(7, "memory");
 745
 746   reference_vars_to_consider =
 747     splay_tree_new_ggc (splay_tree_compare_ints);
 748
 749   bitmap_obstack_initialize (&ipa_obstack);
 750   module_statics_escape = BITMAP_ALLOC (&ipa_obstack);
 751   module_statics_written = BITMAP_ALLOC (&ipa_obstack);
 752   all_module_statics = BITMAP_ALLOC (&ipa_obstack);
 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   visited_nodes = pointer_set_create ();
 759 }
 760
 761 /* Check out the rhs of a static or global initialization VNODE to see
 762    if any of them contain addressof operations.  Note that some of
 763    these variables may  not even be referenced in the code in this
 764    compilation unit but their right hand sides may contain references
 765    to variables defined within this unit.  */
 766
 767 static void
 768 analyze_variable (struct cgraph_varpool_node *vnode)
 769 {
 770   tree global = vnode->decl;
 771   if (TREE_CODE (global) == VAR_DECL)
 772     {
 773       if (DECL_INITIAL (global))
 774         walk_tree (&DECL_INITIAL (global), scan_for_static_refs,
 775                    NULL, visited_nodes);
 776     }
 777   else gcc_unreachable ();
 778 }
 779
 780 /* This is the main routine for finding the reference patterns for
 781    global variables within a function FN.  */
 782
 783 static void
 784 analyze_function (struct cgraph_node *fn)
 785 {
 786   ipa_reference_vars_info_t info
 787     = xcalloc (1, sizeof (struct ipa_reference_vars_info_d));
 788   ipa_reference_local_vars_info_t l
 789     = xcalloc (1, sizeof (struct ipa_reference_local_vars_info_d));
 790   tree decl = fn->decl;
 791
 792   /* Add the info to the tree's annotation.  */
 793   get_var_ann (fn->decl)->reference_vars_info = info;
 794
 795   info->local = l;
 796   l->statics_read = BITMAP_ALLOC (&ipa_obstack);
 797   l->statics_written = BITMAP_ALLOC (&ipa_obstack);
 798
 799   if (dump_file)
 800     fprintf (dump_file, "\n local analysis of %s\n", cgraph_node_name (fn));
 801
 802   {
 803     struct function *this_cfun = DECL_STRUCT_FUNCTION (decl);
 804     basic_block this_block;
 805
 806     FOR_EACH_BB_FN (this_block, this_cfun)
 807       {
 808         block_stmt_iterator bsi;
 809         for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
 810           walk_tree (bsi_stmt_ptr (bsi), scan_for_static_refs,
 811                      fn, visited_nodes);
 812       }
 813   }
 814
 815   /* There may be const decls with interesting right hand sides.  */
 816   if (DECL_STRUCT_FUNCTION (decl))
 817     {
 818       tree step;
 819       for (step = DECL_STRUCT_FUNCTION (decl)->unexpanded_var_list;
 820            step;
 821            step = TREE_CHAIN (step))
 822         {
 823           tree var = TREE_VALUE (step);
 824           if (TREE_CODE (var) == VAR_DECL
 825               && DECL_INITIAL (var)
 826               && !TREE_STATIC (var))
 827             walk_tree (&DECL_INITIAL (var), scan_for_static_refs,
 828                        fn, visited_nodes);
 829         }
 830     }
 831 }
 832
 833 /* If FN is avail == AVAIL_OVERWRITABLE, replace the effects bit
 834    vectors with worst case bit vectors.  We had to analyze it above to
 835    find out if it took the address of any statics. However, now that
 836    we know that, we can get rid of all of the other side effects.  */
 837
 838 static void
 839 clean_function (struct cgraph_node *fn)
 840 {
 841   ipa_reference_vars_info_t info = get_reference_vars_info_from_cgraph (fn);
 842   ipa_reference_local_vars_info_t l = info->local;
 843   ipa_reference_global_vars_info_t g = info->global;
 844
 845   if (l)
 846     {
 847       if (l->statics_read
 848           && l->statics_read != all_module_statics)
 849         BITMAP_FREE (l->statics_read);
 850       if (l->statics_written
 851           &&l->statics_written != all_module_statics)
 852         BITMAP_FREE (l->statics_written);
 853       free (l);
 854     }
 855
 856   if (g)
 857     {
 858       if (g->statics_read
 859           && g->statics_read != all_module_statics)
 860         BITMAP_FREE (g->statics_read);
 861
 862       if (g->statics_written
 863           && g->statics_written != all_module_statics)
 864         BITMAP_FREE (g->statics_written);
 865
 866       if (g->statics_not_read
 867           && g->statics_not_read != all_module_statics)
 868         BITMAP_FREE (g->statics_not_read);
 869
 870       if (g->statics_not_written
 871           && g->statics_not_written != all_module_statics)
 872         BITMAP_FREE (g->statics_not_written);
 873       free (g);
 874     }
 875
 876
 877   free (get_var_ann (fn->decl)->reference_vars_info);
 878   get_var_ann (fn->decl)->reference_vars_info = NULL;
 879 }
 880
 881 \f
 882 /* Produce the global information by preforming a transitive closure
 883    on the local information that was produced by ipa_analyze_function
 884    and ipa_analyze_variable.  */
 885
 886 static void
 887 static_execute (void)
 888 {
 889   struct cgraph_node *node;
 890   struct cgraph_varpool_node *vnode;
 891   struct cgraph_node *w;
 892   struct cgraph_node **order =
 893     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
 894   int order_pos = order_pos = ipa_utils_reduced_inorder (order, false, true);
 895   int i;
 896
 897   ipa_init ();
 898
 899   /* Process all of the variables first.  */
 900   for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 901     analyze_variable (vnode);
 902
 903   /* Process all of the functions next.
 904
 905      We do not want to process any of the clones so we check that this
 906      is a master clone.  However, we do need to process any
 907      AVAIL_OVERWRITABLE functions (these are never clones) because
 908      they may cause a static variable to escape.  The code that can
 909      overwrite such a function cannot access the statics because it
 910      would not be in the same compilation unit.  When the analysis is
 911      finished, the computed information of these AVAIL_OVERWRITABLE is
 912      replaced with worst case info.
 913   */
 914   for (node = cgraph_nodes; node; node = node->next)
 915     if (node->analyzed
 916         && (cgraph_is_master_clone (node)
 917             || (cgraph_function_body_availability (node)
 918                 == AVAIL_OVERWRITABLE)))
 919       analyze_function (node);
 920
 921   pointer_set_destroy (visited_nodes);
 922   visited_nodes = NULL;
 923   if (dump_file)
 924     dump_cgraph (dump_file);
 925
 926   /* Prune out the variables that were found to behave badly
 927      (i.e. have their address taken).  */
 928   {
 929     unsigned int index;
 930     bitmap_iterator bi;
 931     bitmap module_statics_readonly = BITMAP_ALLOC (&ipa_obstack);
 932     bitmap module_statics_const = BITMAP_ALLOC (&ipa_obstack);
 933     bitmap bm_temp = BITMAP_ALLOC (&ipa_obstack);
 934
 935     EXECUTE_IF_SET_IN_BITMAP (module_statics_escape, 0, index, bi)
 936       {
 937         splay_tree_remove (reference_vars_to_consider, index);
 938       }
 939
 940     bitmap_and_compl_into (all_module_statics,
 941                            module_statics_escape);
 942
 943     bitmap_and_compl (module_statics_readonly, all_module_statics,
 944                       module_statics_written);
 945
 946     /* If the address is not taken, we can unset the addressable bit
 947        on this variable.  */
 948     EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
 949       {
 950         tree var = get_static_decl (index);
 951         TREE_ADDRESSABLE (var) = 0;
 952         if (dump_file)
 953           fprintf (dump_file, "Not TREE_ADDRESSABLE var %s\n",
 954                    get_static_name (index));
 955       }
 956
 957     /* If the variable is never written, we can set the TREE_READONLY
 958        flag.  Additionally if it has a DECL_INITIAL that is made up of
 959        constants we can treat the entire global as a constant.  */
 960
 961     bitmap_and_compl (module_statics_readonly, all_module_statics,
 962                       module_statics_written);
 963     EXECUTE_IF_SET_IN_BITMAP (module_statics_readonly, 0, index, bi)
 964       {
 965         tree var = get_static_decl (index);
 966         TREE_READONLY (var) = 1;
 967         if (dump_file)
 968           fprintf (dump_file, "read-only var %s\n",
 969                    get_static_name (index));
 970         if (DECL_INITIAL (var)
 971             && is_gimple_min_invariant (DECL_INITIAL (var)))
 972           {
 973             bitmap_set_bit (module_statics_const, index);
 974             if (dump_file)
 975               fprintf (dump_file, "read-only constant %s\n",
 976                        get_static_name (index));
 977           }
 978       }
 979
 980     BITMAP_FREE(module_statics_escape);
 981     BITMAP_FREE(module_statics_written);
 982
 983     if (dump_file)
 984       EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
 985         {
 986           fprintf (dump_file, "\nPromotable global:%s",
 987                    get_static_name (index));
 988         }
 989
 990     for (i = 0; i < order_pos; i++ )
 991       {
 992         ipa_reference_local_vars_info_t l;
 993         node = order[i];
 994         l = get_reference_vars_info_from_cgraph (node)->local;
 995
 996         /* Any variables that are not in all_module_statics are
 997            removed from the local maps.  This will include all of the
 998            variables that were found to escape in the function
 999            scanning.  */
1000         bitmap_and_into (l->statics_read,
1001                          all_module_statics);
1002         bitmap_and_into (l->statics_written,
1003                          all_module_statics);
1004       }
1005
1006     BITMAP_FREE(module_statics_readonly);
1007     BITMAP_FREE(module_statics_const);
1008     BITMAP_FREE(bm_temp);
1009   }
1010
1011   if (dump_file)
1012     {
1013       for (i = 0; i < order_pos; i++ )
1014         {
1015           unsigned int index;
1016           ipa_reference_local_vars_info_t l;
1017           bitmap_iterator bi;
1018
1019           node = order[i];
1020           l = get_reference_vars_info_from_cgraph (node)->local;
1021           fprintf (dump_file,
1022                    "\nFunction name:%s/%i:",
1023                    cgraph_node_name (node), node->uid);
1024           fprintf (dump_file, "\n  locals read: ");
1025           EXECUTE_IF_SET_IN_BITMAP (l->statics_read,
1026                                     0, index, bi)
1027             {
1028               fprintf (dump_file, "%s ",
1029                        get_static_name (index));
1030             }
1031           fprintf (dump_file, "\n  locals written: ");
1032           EXECUTE_IF_SET_IN_BITMAP (l->statics_written,
1033                                     0, index, bi)
1034             {
1035               fprintf(dump_file, "%s ",
1036                       get_static_name (index));
1037             }
1038         }
1039     }
1040
1041   /* Propagate the local information thru the call graph to produce
1042      the global information.  All the nodes within a cycle will have
1043      the same info so we collapse cycles first.  Then we can do the
1044      propagation in one pass from the leaves to the roots.  */
1045   order_pos = ipa_utils_reduced_inorder (order, true, true);
1046   if (dump_file)
1047     ipa_utils_print_order(dump_file, "reduced", order, order_pos);
1048
1049   for (i = 0; i < order_pos; i++ )
1050     {
1051       ipa_reference_vars_info_t node_info;
1052       ipa_reference_global_vars_info_t node_g =
1053         xcalloc (1, sizeof (struct ipa_reference_global_vars_info_d));
1054       ipa_reference_local_vars_info_t node_l;
1055
1056       bool read_all;
1057       bool write_all;
1058       struct ipa_dfs_info * w_info;
1059
1060       node = order[i];
1061       node_info = get_reference_vars_info_from_cgraph (node);
1062       if (!node_info)
1063         {
1064           dump_cgraph_node (stderr, node);
1065           dump_cgraph (stderr);
1066           gcc_unreachable ();
1067         }
1068
1069       node_info->global = node_g;
1070       node_l = node_info->local;
1071
1072       read_all = node_l->calls_read_all;
1073       write_all = node_l->calls_write_all;
1074
1075       /* If any node in a cycle is calls_read_all or calls_write_all
1076          they all are. */
1077       w_info = node->aux;
1078       w = w_info->next_cycle;
1079       while (w)
1080         {
1081           ipa_reference_local_vars_info_t w_l =
1082             get_reference_vars_info_from_cgraph (w)->local;
1083           read_all |= w_l->calls_read_all;
1084           write_all |= w_l->calls_write_all;
1085
1086           w_info = w->aux;
1087           w = w_info->next_cycle;
1088         }
1089
1090       /* Initialized the bitmaps for the reduced nodes */
1091       if (read_all)
1092         node_g->statics_read = all_module_statics;
1093       else
1094         {
1095           node_g->statics_read = BITMAP_ALLOC (&ipa_obstack);
1096           bitmap_copy (node_g->statics_read,
1097                        node_l->statics_read);
1098         }
1099
1100       if (write_all)
1101         node_g->statics_written = all_module_statics;
1102       else
1103         {
1104           node_g->statics_written = BITMAP_ALLOC (&ipa_obstack);
1105           bitmap_copy (node_g->statics_written,
1106                        node_l->statics_written);
1107         }
1108
1109       w_info = node->aux;
1110       w = w_info->next_cycle;
1111       while (w)
1112         {
1113           ipa_reference_vars_info_t w_ri =
1114             get_reference_vars_info_from_cgraph (w);
1115           ipa_reference_local_vars_info_t w_l = w_ri->local;
1116
1117           /* All nodes within a cycle share the same global info bitmaps.  */
1118           w_ri->global = node_g;
1119
1120           /* These global bitmaps are initialized from the local info
1121              of all of the nodes in the region.  However there is no
1122              need to do any work if the bitmaps were set to
1123              all_module_statics.  */
1124           if (!read_all)
1125             bitmap_ior_into (node_g->statics_read,
1126                              w_l->statics_read);
1127           if (!write_all)
1128             bitmap_ior_into (node_g->statics_written,
1129                              w_l->statics_written);
1130           w_info = w->aux;
1131           w = w_info->next_cycle;
1132         }
1133
1134       w = node;
1135       while (w)
1136         {
1137           propagate_bits (w);
1138           w_info = w->aux;
1139           w = w_info->next_cycle;
1140         }
1141     }
1142
1143   /* Need to fix up the local information sets.  The information that
1144      has been gathered so far is preinlining.  However, the
1145      compilation will progress post inlining so the local sets for the
1146      inlined calls need to be merged into the callers.  Note that the
1147      local sets are not shared between all of the nodes in a cycle so
1148      those nodes in the cycle must be processed explicitly.  */
1149   for (i = 0; i < order_pos; i++ )
1150     {
1151       struct ipa_dfs_info * w_info;
1152       node = order[i];
1153       merge_callee_local_info (node, node);
1154
1155       w_info = node->aux;
1156       w = w_info->next_cycle;
1157       while (w)
1158         {
1159           merge_callee_local_info (w, w);
1160           w_info = w->aux;
1161           w = w_info->next_cycle;
1162         }
1163     }
1164
1165   if (dump_file)
1166     {
1167       for (i = 0; i < order_pos; i++ )
1168         {
1169           ipa_reference_vars_info_t node_info;
1170           ipa_reference_global_vars_info_t node_g;
1171           ipa_reference_local_vars_info_t node_l;
1172           unsigned int index;
1173           bitmap_iterator bi;
1174           struct ipa_dfs_info * w_info;
1175
1176           node = order[i];
1177           node_info = get_reference_vars_info_from_cgraph (node);
1178           node_g = node_info->global;
1179           node_l = node_info->local;
1180           fprintf (dump_file,
1181                    "\nFunction name:%s/%i:",
1182                    cgraph_node_name (node), node->uid);
1183           fprintf (dump_file, "\n  locals read: ");
1184           EXECUTE_IF_SET_IN_BITMAP (node_l->statics_read,
1185                                     0, index, bi)
1186             {
1187               fprintf (dump_file, "%s ",
1188                        get_static_name (index));
1189             }
1190           fprintf (dump_file, "\n  locals written: ");
1191           EXECUTE_IF_SET_IN_BITMAP (node_l->statics_written,
1192                                     0, index, bi)
1193             {
1194               fprintf(dump_file, "%s ",
1195                       get_static_name (index));
1196             }
1197
1198           w_info = node->aux;
1199           w = w_info->next_cycle;
1200           while (w)
1201             {
1202               ipa_reference_vars_info_t w_ri =
1203                 get_reference_vars_info_from_cgraph (w);
1204               ipa_reference_local_vars_info_t w_l = w_ri->local;
1205               fprintf (dump_file, "\n  next cycle: %s/%i ",
1206                        cgraph_node_name (w), w->uid);
1207               fprintf (dump_file, "\n    locals read: ");
1208               EXECUTE_IF_SET_IN_BITMAP (w_l->statics_read,
1209                                         0, index, bi)
1210                 {
1211                   fprintf (dump_file, "%s ",
1212                            get_static_name (index));
1213                 }
1214
1215               fprintf (dump_file, "\n    locals written: ");
1216               EXECUTE_IF_SET_IN_BITMAP (w_l->statics_written,
1217                                         0, index, bi)
1218                 {
1219                   fprintf(dump_file, "%s ",
1220                           get_static_name (index));
1221                 }
1222
1223
1224               w_info = w->aux;
1225               w = w_info->next_cycle;
1226             }
1227           fprintf (dump_file, "\n  globals read: ");
1228           EXECUTE_IF_SET_IN_BITMAP (node_g->statics_read,
1229                                     0, index, bi)
1230             {
1231               fprintf (dump_file, "%s ",
1232                        get_static_name (index));
1233             }
1234           fprintf (dump_file, "\n  globals written: ");
1235           EXECUTE_IF_SET_IN_BITMAP (node_g->statics_written,
1236                                     0, index, bi)
1237             {
1238               fprintf (dump_file, "%s ",
1239                        get_static_name (index));
1240             }
1241         }
1242     }
1243
1244   /* Cleanup. */
1245   for (i = 0; i < order_pos; i++ )
1246     {
1247       ipa_reference_vars_info_t node_info;
1248       ipa_reference_global_vars_info_t node_g;
1249       node = order[i];
1250       node_info = get_reference_vars_info_from_cgraph (node);
1251       node_g = node_info->global;
1252
1253       /* Create the complimentary sets.  These are more useful for
1254          certain apis.  */
1255       node_g->statics_not_read = BITMAP_ALLOC (&ipa_obstack);
1256       node_g->statics_not_written = BITMAP_ALLOC (&ipa_obstack);
1257
1258       if (node_g->statics_read != all_module_statics)
1259         {
1260           bitmap_and_compl (node_g->statics_not_read,
1261                             all_module_statics,
1262                             node_g->statics_read);
1263         }
1264
1265       if (node_g->statics_written
1266           != all_module_statics)
1267         bitmap_and_compl (node_g->statics_not_written,
1268                           all_module_statics,
1269                           node_g->statics_written);
1270    }
1271
1272   free (order);
1273
1274   for (node = cgraph_nodes; node; node = node->next)
1275     {
1276       /* Get rid of the aux information.  */
1277
1278       if (node->aux)
1279         {
1280           free (node->aux);
1281           node->aux = NULL;
1282         }
1283
1284       if (node->analyzed
1285           && (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE))
1286         clean_function (node);
1287     }
1288 }
1289
1290
1291 static bool
1292 gate_reference (void)
1293 {
1294   return (flag_unit_at_a_time != 0  && flag_ipa_reference
1295           /* Don't bother doing anything if the program has errors.  */
1296           && !(errorcount || sorrycount));
1297 }
1298
1299 struct tree_opt_pass pass_ipa_reference =
1300 {
1301   "static-var",                         /* name */
1302   gate_reference,                       /* gate */
1303   static_execute,                       /* execute */
1304   NULL,                                 /* sub */
1305   NULL,                                 /* next */
1306   0,                                    /* static_pass_number */
1307   TV_IPA_REFERENCE,                     /* tv_id */
1308   0,                                    /* properties_required */
1309   0,                                    /* properties_provided */
1310   0,                                    /* properties_destroyed */
1311   0,                                    /* todo_flags_start */
1312   0,                                    /* todo_flags_finish */
1313   0                                     /* letter */
1314 };
1315
1316 #include "gt-ipa-reference.h"
1317