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