gcc/ipa-reference.c

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