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             {
 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   struct cgraph_node *node;
 745   memory_identifier_string = build_string(7, "memory");
 746
 747   reference_vars_to_consider =
 748     splay_tree_new_ggc (splay_tree_compare_ints);
 749
 750   bitmap_obstack_initialize (&ipa_obstack);
 751   module_statics_escape = BITMAP_ALLOC (&ipa_obstack);
 752   module_statics_written = BITMAP_ALLOC (&ipa_obstack);
 753   all_module_statics = BITMAP_ALLOC (&ipa_obstack);
 754
 755   /* This will add NODE->DECL to the splay trees.  */
 756   for (node = cgraph_nodes; node; node = node->next)
 757     has_proper_scope_for_analysis (node->decl);
 758
 759   /* There are some shared nodes, in particular the initializers on
 760      static declarations.  We do not need to scan them more than once
 761      since all we would be interested in are the addressof
 762      operations.  */
 763   visited_nodes = pointer_set_create ();
 764 }
 765
 766 /* Check out the rhs of a static or global initialization VNODE to see
 767    if any of them contain addressof operations.  Note that some of
 768    these variables may  not even be referenced in the code in this
 769    compilation unit but their right hand sides may contain references
 770    to variables defined within this unit.  */
 771
 772 static void
 773 analyze_variable (struct cgraph_varpool_node *vnode)
 774 {
 775   tree global = vnode->decl;
 776   if (TREE_CODE (global) == VAR_DECL)
 777     {
 778       if (DECL_INITIAL (global))
 779         walk_tree (&DECL_INITIAL (global), scan_for_static_refs,
 780                    NULL, visited_nodes);
 781     }
 782   else gcc_unreachable ();
 783 }
 784
 785 /* This is the main routine for finding the reference patterns for
 786    global variables within a function FN.  */
 787
 788 static void
 789 analyze_function (struct cgraph_node *fn)
 790 {
 791   ipa_reference_vars_info_t info
 792     = xcalloc (1, sizeof (struct ipa_reference_vars_info_d));
 793   ipa_reference_local_vars_info_t l
 794     = xcalloc (1, sizeof (struct ipa_reference_local_vars_info_d));
 795   tree decl = fn->decl;
 796
 797   /* Add the info to the tree's annotation.  */
 798   get_function_ann (fn->decl)->reference_vars_info = info;
 799
 800   info->local = l;
 801   l->statics_read = BITMAP_ALLOC (&ipa_obstack);
 802   l->statics_written = BITMAP_ALLOC (&ipa_obstack);
 803
 804   if (dump_file)
 805     fprintf (dump_file, "\n local analysis of %s\n", cgraph_node_name (fn));
 806
 807   {
 808     struct function *this_cfun = DECL_STRUCT_FUNCTION (decl);
 809     basic_block this_block;
 810
 811     FOR_EACH_BB_FN (this_block, this_cfun)
 812       {
 813         block_stmt_iterator bsi;
 814         for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
 815           walk_tree (bsi_stmt_ptr (bsi), scan_for_static_refs,
 816                      fn, visited_nodes);
 817       }
 818   }
 819
 820   /* There may be const decls with interesting right hand sides.  */
 821   if (DECL_STRUCT_FUNCTION (decl))
 822     {
 823       tree step;
 824       for (step = DECL_STRUCT_FUNCTION (decl)->unexpanded_var_list;
 825            step;
 826            step = TREE_CHAIN (step))
 827         {
 828           tree var = TREE_VALUE (step);
 829           if (TREE_CODE (var) == VAR_DECL
 830               && DECL_INITIAL (var)
 831               && !TREE_STATIC (var))
 832             walk_tree (&DECL_INITIAL (var), scan_for_static_refs,
 833                        fn, visited_nodes);
 834         }
 835     }
 836 }
 837
 838 /* If FN is avail == AVAIL_OVERWRITABLE, replace the effects bit
 839    vectors with worst case bit vectors.  We had to analyze it above to
 840    find out if it took the address of any statics. However, now that
 841    we know that, we can get rid of all of the other side effects.  */
 842
 843 static void
 844 clean_function (struct cgraph_node *fn)
 845 {
 846   ipa_reference_vars_info_t info = get_reference_vars_info_from_cgraph (fn);
 847   ipa_reference_local_vars_info_t l = info->local;
 848   ipa_reference_global_vars_info_t g = info->global;
 849
 850   if (l)
 851     {
 852       if (l->statics_read
 853           && l->statics_read != all_module_statics)
 854         BITMAP_FREE (l->statics_read);
 855       if (l->statics_written
 856           &&l->statics_written != all_module_statics)
 857         BITMAP_FREE (l->statics_written);
 858       free (l);
 859     }
 860
 861   if (g)
 862     {
 863       if (g->statics_read
 864           && g->statics_read != all_module_statics)
 865         BITMAP_FREE (g->statics_read);
 866
 867       if (g->statics_written
 868           && g->statics_written != all_module_statics)
 869         BITMAP_FREE (g->statics_written);
 870
 871       if (g->statics_not_read
 872           && g->statics_not_read != all_module_statics)
 873         BITMAP_FREE (g->statics_not_read);
 874
 875       if (g->statics_not_written
 876           && g->statics_not_written != all_module_statics)
 877         BITMAP_FREE (g->statics_not_written);
 878       free (g);
 879     }
 880
 881
 882   free (get_function_ann (fn->decl)->reference_vars_info);
 883   get_function_ann (fn->decl)->reference_vars_info = NULL;
 884 }
 885
 886 \f
 887 /* Produce the global information by preforming a transitive closure
 888    on the local information that was produced by ipa_analyze_function
 889    and ipa_analyze_variable.  */
 890
 891 static unsigned int
 892 static_execute (void)
 893 {
 894   struct cgraph_node *node;
 895   struct cgraph_varpool_node *vnode;
 896   struct cgraph_node *w;
 897   struct cgraph_node **order =
 898     xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *));
 899   int order_pos = order_pos = ipa_utils_reduced_inorder (order, false, true);
 900   int i;
 901
 902   ipa_init ();
 903
 904   /* Process all of the variables first.  */
 905   for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 906     analyze_variable (vnode);
 907
 908   /* Process all of the functions next.
 909
 910      We do not want to process any of the clones so we check that this
 911      is a master clone.  However, we do need to process any
 912      AVAIL_OVERWRITABLE functions (these are never clones) because
 913      they may cause a static variable to escape.  The code that can
 914      overwrite such a function cannot access the statics because it
 915      would not be in the same compilation unit.  When the analysis is
 916      finished, the computed information of these AVAIL_OVERWRITABLE is
 917      replaced with worst case info.
 918   */
 919   for (node = cgraph_nodes; node; node = node->next)
 920     if (node->analyzed
 921         && (cgraph_is_master_clone (node)
 922             || (cgraph_function_body_availability (node)
 923                 == AVAIL_OVERWRITABLE)))
 924       analyze_function (node);
 925
 926   pointer_set_destroy (visited_nodes);
 927   visited_nodes = NULL;
 928   if (dump_file)
 929     dump_cgraph (dump_file);
 930
 931   /* Prune out the variables that were found to behave badly
 932      (i.e. have their address taken).  */
 933   {
 934     unsigned int index;
 935     bitmap_iterator bi;
 936     bitmap module_statics_readonly = BITMAP_ALLOC (&ipa_obstack);
 937     bitmap module_statics_const = BITMAP_ALLOC (&ipa_obstack);
 938     bitmap bm_temp = BITMAP_ALLOC (&ipa_obstack);
 939
 940     EXECUTE_IF_SET_IN_BITMAP (module_statics_escape, 0, index, bi)
 941       {
 942         splay_tree_remove (reference_vars_to_consider, index);
 943       }
 944
 945     bitmap_and_compl_into (all_module_statics,
 946                            module_statics_escape);
 947
 948     bitmap_and_compl (module_statics_readonly, all_module_statics,
 949                       module_statics_written);
 950
 951     /* If the address is not taken, we can unset the addressable bit
 952        on this variable.  */
 953     EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
 954       {
 955         tree var = get_static_decl (index);
 956         TREE_ADDRESSABLE (var) = 0;
 957         if (dump_file)
 958           fprintf (dump_file, "Not TREE_ADDRESSABLE var %s\n",
 959                    get_static_name (index));
 960       }
 961
 962     /* If the variable is never written, we can set the TREE_READONLY
 963        flag.  Additionally if it has a DECL_INITIAL that is made up of
 964        constants we can treat the entire global as a constant.  */
 965
 966     bitmap_and_compl (module_statics_readonly, all_module_statics,
 967                       module_statics_written);
 968     EXECUTE_IF_SET_IN_BITMAP (module_statics_readonly, 0, index, bi)
 969       {
 970         tree var = get_static_decl (index);
 971
 972         /* Readonly on a function decl is very different from the
 973            variable.  */
 974         if (TREE_CODE (var) == FUNCTION_DECL)
 975           continue;
 976
 977         /* Ignore variables in named sections - changing TREE_READONLY
 978            changes the section flags, potentially causing conflicts with
 979            other variables in the same named section.  */
 980         if (DECL_SECTION_NAME (var) == NULL_TREE)
 981           {
 982             TREE_READONLY (var) = 1;
 983             if (dump_file)
 984               fprintf (dump_file, "read-only var %s\n",
 985                        get_static_name (index));
 986           }
 987         if (DECL_INITIAL (var)
 988             && is_gimple_min_invariant (DECL_INITIAL (var)))
 989           {
 990             bitmap_set_bit (module_statics_const, index);
 991             if (dump_file)
 992               fprintf (dump_file, "read-only constant %s\n",
 993                        get_static_name (index));
 994           }
 995       }
 996
 997     BITMAP_FREE(module_statics_escape);
 998     BITMAP_FREE(module_statics_written);
 999
1000     if (dump_file)
1001       EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi)
1002         {
1003           fprintf (dump_file, "\nPromotable global:%s",
1004                    get_static_name (index));
1005         }
1006
1007     for (i = 0; i < order_pos; i++ )
1008       {
1009         ipa_reference_local_vars_info_t l;
1010         node = order[i];
1011         l = get_reference_vars_info_from_cgraph (node)->local;
1012
1013         /* Any variables that are not in all_module_statics are
1014            removed from the local maps.  This will include all of the
1015            variables that were found to escape in the function
1016            scanning.  */
1017         bitmap_and_into (l->statics_read,
1018                          all_module_statics);
1019         bitmap_and_into (l->statics_written,
1020                          all_module_statics);
1021       }
1022
1023     BITMAP_FREE(module_statics_readonly);
1024     BITMAP_FREE(module_statics_const);
1025     BITMAP_FREE(bm_temp);
1026   }
1027
1028   if (dump_file)
1029     {
1030       for (i = 0; i < order_pos; i++ )
1031         {
1032           unsigned int index;
1033           ipa_reference_local_vars_info_t l;
1034           bitmap_iterator bi;
1035
1036           node = order[i];
1037           l = get_reference_vars_info_from_cgraph (node)->local;
1038           fprintf (dump_file,
1039                    "\nFunction name:%s/%i:",
1040                    cgraph_node_name (node), node->uid);
1041           fprintf (dump_file, "\n  locals read: ");
1042           EXECUTE_IF_SET_IN_BITMAP (l->statics_read,
1043                                     0, index, bi)
1044             {
1045               fprintf (dump_file, "%s ",
1046                        get_static_name (index));
1047             }
1048           fprintf (dump_file, "\n  locals written: ");
1049           EXECUTE_IF_SET_IN_BITMAP (l->statics_written,
1050                                     0, index, bi)
1051             {
1052               fprintf(dump_file, "%s ",
1053                       get_static_name (index));
1054             }
1055         }
1056     }
1057
1058   /* Propagate the local information thru the call graph to produce
1059      the global information.  All the nodes within a cycle will have
1060      the same info so we collapse cycles first.  Then we can do the
1061      propagation in one pass from the leaves to the roots.  */
1062   order_pos = ipa_utils_reduced_inorder (order, true, true);
1063   if (dump_file)
1064     ipa_utils_print_order(dump_file, "reduced", order, order_pos);
1065
1066   for (i = 0; i < order_pos; i++ )
1067     {
1068       ipa_reference_vars_info_t node_info;
1069       ipa_reference_global_vars_info_t node_g =
1070         xcalloc (1, sizeof (struct ipa_reference_global_vars_info_d));
1071       ipa_reference_local_vars_info_t node_l;
1072
1073       bool read_all;
1074       bool write_all;
1075       struct ipa_dfs_info * w_info;
1076
1077       node = order[i];
1078       node_info = get_reference_vars_info_from_cgraph (node);
1079       if (!node_info)
1080         {
1081           dump_cgraph_node (stderr, node);
1082           dump_cgraph (stderr);
1083           gcc_unreachable ();
1084         }
1085
1086       node_info->global = node_g;
1087       node_l = node_info->local;
1088
1089       read_all = node_l->calls_read_all;
1090       write_all = node_l->calls_write_all;
1091
1092       /* If any node in a cycle is calls_read_all or calls_write_all
1093          they all are. */
1094       w_info = node->aux;
1095       w = w_info->next_cycle;
1096       while (w)
1097         {
1098           ipa_reference_local_vars_info_t w_l =
1099             get_reference_vars_info_from_cgraph (w)->local;
1100           read_all |= w_l->calls_read_all;
1101           write_all |= w_l->calls_write_all;
1102
1103           w_info = w->aux;
1104           w = w_info->next_cycle;
1105         }
1106
1107       /* Initialized the bitmaps for the reduced nodes */
1108       if (read_all)
1109         node_g->statics_read = all_module_statics;
1110       else
1111         {
1112           node_g->statics_read = BITMAP_ALLOC (&ipa_obstack);
1113           bitmap_copy (node_g->statics_read,
1114                        node_l->statics_read);
1115         }
1116
1117       if (write_all)
1118         node_g->statics_written = all_module_statics;
1119       else
1120         {
1121           node_g->statics_written = BITMAP_ALLOC (&ipa_obstack);
1122           bitmap_copy (node_g->statics_written,
1123                        node_l->statics_written);
1124         }
1125
1126       w_info = node->aux;
1127       w = w_info->next_cycle;
1128       while (w)
1129         {
1130           ipa_reference_vars_info_t w_ri =
1131             get_reference_vars_info_from_cgraph (w);
1132           ipa_reference_local_vars_info_t w_l = w_ri->local;
1133
1134           /* All nodes within a cycle share the same global info bitmaps.  */
1135           w_ri->global = node_g;
1136
1137           /* These global bitmaps are initialized from the local info
1138              of all of the nodes in the region.  However there is no
1139              need to do any work if the bitmaps were set to
1140              all_module_statics.  */
1141           if (!read_all)
1142             bitmap_ior_into (node_g->statics_read,
1143                              w_l->statics_read);
1144           if (!write_all)
1145             bitmap_ior_into (node_g->statics_written,
1146                              w_l->statics_written);
1147           w_info = w->aux;
1148           w = w_info->next_cycle;
1149         }
1150
1151       w = node;
1152       while (w)
1153         {
1154           propagate_bits (w);
1155           w_info = w->aux;
1156           w = w_info->next_cycle;
1157         }
1158     }
1159
1160   /* Need to fix up the local information sets.  The information that
1161      has been gathered so far is preinlining.  However, the
1162      compilation will progress post inlining so the local sets for the
1163      inlined calls need to be merged into the callers.  Note that the
1164      local sets are not shared between all of the nodes in a cycle so
1165      those nodes in the cycle must be processed explicitly.  */
1166   for (i = 0; i < order_pos; i++ )
1167     {
1168       struct ipa_dfs_info * w_info;
1169       node = order[i];
1170       merge_callee_local_info (node, node);
1171
1172       w_info = node->aux;
1173       w = w_info->next_cycle;
1174       while (w)
1175         {
1176           merge_callee_local_info (w, w);
1177           w_info = w->aux;
1178           w = w_info->next_cycle;
1179         }
1180     }
1181
1182   if (dump_file)
1183     {
1184       for (i = 0; i < order_pos; i++ )
1185         {
1186           ipa_reference_vars_info_t node_info;
1187           ipa_reference_global_vars_info_t node_g;
1188           ipa_reference_local_vars_info_t node_l;
1189           unsigned int index;
1190           bitmap_iterator bi;
1191           struct ipa_dfs_info * w_info;
1192
1193           node = order[i];
1194           node_info = get_reference_vars_info_from_cgraph (node);
1195           node_g = node_info->global;
1196           node_l = node_info->local;
1197           fprintf (dump_file,
1198                    "\nFunction name:%s/%i:",
1199                    cgraph_node_name (node), node->uid);
1200           fprintf (dump_file, "\n  locals read: ");
1201           EXECUTE_IF_SET_IN_BITMAP (node_l->statics_read,
1202                                     0, index, bi)
1203             {
1204               fprintf (dump_file, "%s ",
1205                        get_static_name (index));
1206             }
1207           fprintf (dump_file, "\n  locals written: ");
1208           EXECUTE_IF_SET_IN_BITMAP (node_l->statics_written,
1209                                     0, index, bi)
1210             {
1211               fprintf(dump_file, "%s ",
1212                       get_static_name (index));
1213             }
1214
1215           w_info = node->aux;
1216           w = w_info->next_cycle;
1217           while (w)
1218             {
1219               ipa_reference_vars_info_t w_ri =
1220                 get_reference_vars_info_from_cgraph (w);
1221               ipa_reference_local_vars_info_t w_l = w_ri->local;
1222               fprintf (dump_file, "\n  next cycle: %s/%i ",
1223                        cgraph_node_name (w), w->uid);
1224               fprintf (dump_file, "\n    locals read: ");
1225               EXECUTE_IF_SET_IN_BITMAP (w_l->statics_read,
1226                                         0, index, bi)
1227                 {
1228                   fprintf (dump_file, "%s ",
1229                            get_static_name (index));
1230                 }
1231
1232               fprintf (dump_file, "\n    locals written: ");
1233               EXECUTE_IF_SET_IN_BITMAP (w_l->statics_written,
1234                                         0, index, bi)
1235                 {
1236                   fprintf(dump_file, "%s ",
1237                           get_static_name (index));
1238                 }
1239
1240
1241               w_info = w->aux;
1242               w = w_info->next_cycle;
1243             }
1244           fprintf (dump_file, "\n  globals read: ");
1245           EXECUTE_IF_SET_IN_BITMAP (node_g->statics_read,
1246                                     0, index, bi)
1247             {
1248               fprintf (dump_file, "%s ",
1249                        get_static_name (index));
1250             }
1251           fprintf (dump_file, "\n  globals written: ");
1252           EXECUTE_IF_SET_IN_BITMAP (node_g->statics_written,
1253                                     0, index, bi)
1254             {
1255               fprintf (dump_file, "%s ",
1256                        get_static_name (index));
1257             }
1258         }
1259     }
1260
1261   /* Cleanup. */
1262   for (i = 0; i < order_pos; i++ )
1263     {
1264       ipa_reference_vars_info_t node_info;
1265       ipa_reference_global_vars_info_t node_g;
1266       node = order[i];
1267       node_info = get_reference_vars_info_from_cgraph (node);
1268       node_g = node_info->global;
1269
1270       /* Create the complimentary sets.  These are more useful for
1271          certain apis.  */
1272       node_g->statics_not_read = BITMAP_ALLOC (&ipa_obstack);
1273       node_g->statics_not_written = BITMAP_ALLOC (&ipa_obstack);
1274
1275       if (node_g->statics_read != all_module_statics)
1276         {
1277           bitmap_and_compl (node_g->statics_not_read,
1278                             all_module_statics,
1279                             node_g->statics_read);
1280         }
1281
1282       if (node_g->statics_written
1283           != all_module_statics)
1284         bitmap_and_compl (node_g->statics_not_written,
1285                           all_module_statics,
1286                           node_g->statics_written);
1287    }
1288
1289   free (order);
1290
1291   for (node = cgraph_nodes; node; node = node->next)
1292     {
1293       /* Get rid of the aux information.  */
1294
1295       if (node->aux)
1296         {
1297           free (node->aux);
1298           node->aux = NULL;
1299         }
1300
1301       if (node->analyzed
1302           && (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE))
1303         clean_function (node);
1304     }
1305   return 0;
1306 }
1307
1308
1309 static bool
1310 gate_reference (void)
1311 {
1312   return (flag_unit_at_a_time != 0  && flag_ipa_reference
1313           /* Don't bother doing anything if the program has errors.  */
1314           && !(errorcount || sorrycount));
1315 }
1316
1317 struct tree_opt_pass pass_ipa_reference =
1318 {
1319   "static-var",                         /* name */
1320   gate_reference,                       /* gate */
1321   static_execute,                       /* execute */
1322   NULL,                                 /* sub */
1323   NULL,                                 /* next */
1324   0,                                    /* static_pass_number */
1325   TV_IPA_REFERENCE,                     /* tv_id */
1326   0,                                    /* properties_required */
1327   0,                                    /* properties_provided */
1328   0,                                    /* properties_destroyed */
1329   0,                                    /* todo_flags_start */
1330   0,                                    /* todo_flags_finish */
1331   0                                     /* letter */
1332 };
1333
1334 #include "gt-ipa-reference.h"
1335