gcc/tree-dfa.c

   1 /* Data flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009
   3    Free Software Foundation, Inc.
   4    Contributed by Diego Novillo <dnovillo@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "hashtab.h"
  27 #include "pointer-set.h"
  28 #include "tree.h"
  29 #include "rtl.h"
  30 #include "tm_p.h"
  31 #include "hard-reg-set.h"
  32 #include "basic-block.h"
  33 #include "output.h"
  34 #include "timevar.h"
  35 #include "expr.h"
  36 #include "ggc.h"
  37 #include "langhooks.h"
  38 #include "flags.h"
  39 #include "function.h"
  40 #include "diagnostic.h"
  41 #include "tree-dump.h"
  42 #include "gimple.h"
  43 #include "tree-flow.h"
  44 #include "tree-inline.h"
  45 #include "tree-pass.h"
  46 #include "convert.h"
  47 #include "params.h"
  48 #include "cgraph.h"
  49
  50 /* Build and maintain data flow information for trees.  */
  51
  52 /* Counters used to display DFA and SSA statistics.  */
  53 struct dfa_stats_d
  54 {
  55   long num_var_anns;
  56   long num_defs;
  57   long num_uses;
  58   long num_phis;
  59   long num_phi_args;
  60   size_t max_num_phi_args;
  61   long num_vdefs;
  62   long num_vuses;
  63 };
  64
  65
  66 /* Local functions.  */
  67 static void collect_dfa_stats (struct dfa_stats_d *);
  68 static tree find_vars_r (tree *, int *, void *);
  69
  70
  71 /*---------------------------------------------------------------------------
  72                         Dataflow analysis (DFA) routines
  73 ---------------------------------------------------------------------------*/
  74 /* Find all the variables referenced in the function.  This function
  75    builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
  76
  77    Note that this function does not look for statement operands, it simply
  78    determines what variables are referenced in the program and detects
  79    various attributes for each variable used by alias analysis and the
  80    optimizer.  */
  81
  82 static unsigned int
  83 find_referenced_vars (void)
  84 {
  85   basic_block bb;
  86   gimple_stmt_iterator si;
  87
  88   FOR_EACH_BB (bb)
  89     {
  90       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
  91         {
  92           size_t i;
  93           gimple stmt = gsi_stmt (si);
  94           for (i = 0; i < gimple_num_ops (stmt); i++)
  95             walk_tree (gimple_op_ptr (stmt, i), find_vars_r, NULL, NULL);
  96         }
  97
  98       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
  99         {
 100           gimple phi = gsi_stmt (si);
 101           size_t i, len = gimple_phi_num_args (phi);
 102
 103           walk_tree (gimple_phi_result_ptr (phi), find_vars_r, NULL, NULL);
 104
 105           for (i = 0; i < len; i++)
 106             {
 107               tree arg = gimple_phi_arg_def (phi, i);
 108               walk_tree (&arg, find_vars_r, NULL, NULL);
 109             }
 110         }
 111     }
 112
 113   return 0;
 114 }
 115
 116 struct gimple_opt_pass pass_referenced_vars =
 117 {
 118  {
 119   GIMPLE_PASS,
 120   NULL,                                 /* name */
 121   NULL,                                 /* gate */
 122   find_referenced_vars,                 /* execute */
 123   NULL,                                 /* sub */
 124   NULL,                                 /* next */
 125   0,                                    /* static_pass_number */
 126   TV_FIND_REFERENCED_VARS,              /* tv_id */
 127   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 128   PROP_referenced_vars,                 /* properties_provided */
 129   0,                                    /* properties_destroyed */
 130   TODO_dump_func,                       /* todo_flags_start */
 131   TODO_dump_func                        /* todo_flags_finish */
 132  }
 133 };
 134
 135
 136 /*---------------------------------------------------------------------------
 137                             Manage annotations
 138 ---------------------------------------------------------------------------*/
 139 /* Create a new annotation for a _DECL node T.  */
 140
 141 var_ann_t
 142 create_var_ann (tree t)
 143 {
 144   var_ann_t ann;
 145
 146   gcc_assert (t);
 147   gcc_assert (DECL_P (t));
 148   gcc_assert (!t->base.ann || t->base.ann->common.type == VAR_ANN);
 149
 150   ann = GGC_CNEW (struct var_ann_d);
 151   ann->common.type = VAR_ANN;
 152   t->base.ann = (tree_ann_t) ann;
 153
 154   return ann;
 155 }
 156
 157 /* Create a new annotation for a FUNCTION_DECL node T.  */
 158
 159 function_ann_t
 160 create_function_ann (tree t)
 161 {
 162   function_ann_t ann;
 163
 164   gcc_assert (t);
 165   gcc_assert (TREE_CODE (t) == FUNCTION_DECL);
 166   gcc_assert (!t->base.ann || t->base.ann->common.type == FUNCTION_ANN);
 167
 168   ann = (function_ann_t) ggc_alloc (sizeof (*ann));
 169   memset ((void *) ann, 0, sizeof (*ann));
 170
 171   ann->common.type = FUNCTION_ANN;
 172
 173   t->base.ann = (tree_ann_t) ann;
 174
 175   return ann;
 176 }
 177
 178 /* Renumber all of the gimple stmt uids.  */
 179
 180 void
 181 renumber_gimple_stmt_uids (void)
 182 {
 183   basic_block bb;
 184
 185   set_gimple_stmt_max_uid (cfun, 0);
 186   FOR_ALL_BB (bb)
 187     {
 188       gimple_stmt_iterator bsi;
 189       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 190         {
 191           gimple stmt = gsi_stmt (bsi);
 192           gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
 193         }
 194     }
 195 }
 196
 197 /* Create a new annotation for a tree T.  */
 198
 199 tree_ann_common_t
 200 create_tree_common_ann (tree t)
 201 {
 202   tree_ann_common_t ann;
 203
 204   gcc_assert (t);
 205   gcc_assert (!t->base.ann || t->base.ann->common.type == TREE_ANN_COMMON);
 206
 207   ann = GGC_CNEW (struct tree_ann_common_d);
 208
 209   ann->type = TREE_ANN_COMMON;
 210   ann->rn = -1;
 211   t->base.ann = (tree_ann_t) ann;
 212
 213   return ann;
 214 }
 215
 216 /* Build a temporary.  Make sure and register it to be renamed.  */
 217
 218 tree
 219 make_rename_temp (tree type, const char *prefix)
 220 {
 221   tree t = create_tmp_var (type, prefix);
 222
 223   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 224       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 225     DECL_GIMPLE_REG_P (t) = 1;
 226
 227   if (gimple_referenced_vars (cfun))
 228     {
 229       add_referenced_var (t);
 230       mark_sym_for_renaming (t);
 231     }
 232
 233   return t;
 234 }
 235
 236
 237
 238 /*---------------------------------------------------------------------------
 239                               Debugging functions
 240 ---------------------------------------------------------------------------*/
 241 /* Dump the list of all the referenced variables in the current function to
 242    FILE.  */
 243
 244 void
 245 dump_referenced_vars (FILE *file)
 246 {
 247   tree var;
 248   referenced_var_iterator rvi;
 249
 250   fprintf (file, "\nReferenced variables in %s: %u\n\n",
 251            get_name (current_function_decl), (unsigned) num_referenced_vars);
 252
 253   FOR_EACH_REFERENCED_VAR (var, rvi)
 254     {
 255       fprintf (file, "Variable: ");
 256       dump_variable (file, var);
 257       fprintf (file, "\n");
 258     }
 259 }
 260
 261
 262 /* Dump the list of all the referenced variables to stderr.  */
 263
 264 void
 265 debug_referenced_vars (void)
 266 {
 267   dump_referenced_vars (stderr);
 268 }
 269
 270
 271 /* Dump variable VAR and its may-aliases to FILE.  */
 272
 273 void
 274 dump_variable (FILE *file, tree var)
 275 {
 276   var_ann_t ann;
 277
 278   if (TREE_CODE (var) == SSA_NAME)
 279     {
 280       if (POINTER_TYPE_P (TREE_TYPE (var)))
 281         dump_points_to_info_for (file, var);
 282       var = SSA_NAME_VAR (var);
 283     }
 284
 285   if (var == NULL_TREE)
 286     {
 287       fprintf (file, "<nil>");
 288       return;
 289     }
 290
 291   print_generic_expr (file, var, dump_flags);
 292
 293   ann = var_ann (var);
 294
 295   fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
 296
 297   fprintf (file, ", ");
 298   print_generic_expr (file, TREE_TYPE (var), dump_flags);
 299
 300   if (ann && ann->symbol_mem_tag)
 301     {
 302       fprintf (file, ", symbol memory tag: ");
 303       print_generic_expr (file, ann->symbol_mem_tag, dump_flags);
 304     }
 305
 306   if (TREE_ADDRESSABLE (var))
 307     fprintf (file, ", is addressable");
 308
 309   if (is_global_var (var))
 310     fprintf (file, ", is global");
 311
 312   if (TREE_THIS_VOLATILE (var))
 313     fprintf (file, ", is volatile");
 314
 315   dump_mem_sym_stats_for_var (file, var);
 316
 317   if (is_call_clobbered (var))
 318     {
 319       const char *s = "";
 320       var_ann_t va = var_ann (var);
 321       unsigned int escape_mask = va->escape_mask;
 322
 323       fprintf (file, ", call clobbered");
 324       fprintf (file, " (");
 325       if (escape_mask & ESCAPE_STORED_IN_GLOBAL)
 326         { fprintf (file, "%sstored in global", s); s = ", "; }
 327       if (escape_mask & ESCAPE_TO_ASM)
 328         { fprintf (file, "%sgoes through ASM", s); s = ", "; }
 329       if (escape_mask & ESCAPE_TO_CALL)
 330         { fprintf (file, "%spassed to call", s); s = ", "; }
 331       if (escape_mask & ESCAPE_BAD_CAST)
 332         { fprintf (file, "%sbad cast", s); s = ", "; }
 333       if (escape_mask & ESCAPE_TO_RETURN)
 334         { fprintf (file, "%sreturned from func", s); s = ", "; }
 335       if (escape_mask & ESCAPE_TO_PURE_CONST)
 336         { fprintf (file, "%spassed to pure/const", s); s = ", "; }
 337       if (escape_mask & ESCAPE_IS_GLOBAL)
 338         { fprintf (file, "%sis global var", s); s = ", "; }
 339       if (escape_mask & ESCAPE_IS_PARM)
 340         { fprintf (file, "%sis incoming pointer", s); s = ", "; }
 341       if (escape_mask & ESCAPE_UNKNOWN)
 342         { fprintf (file, "%sunknown escape", s); s = ", "; }
 343       fprintf (file, ")");
 344     }
 345
 346   if (ann->noalias_state == NO_ALIAS)
 347     fprintf (file, ", NO_ALIAS (does not alias other NO_ALIAS symbols)");
 348   else if (ann->noalias_state == NO_ALIAS_GLOBAL)
 349     fprintf (file, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols"
 350                    " and global vars)");
 351   else if (ann->noalias_state == NO_ALIAS_ANYTHING)
 352     fprintf (file, ", NO_ALIAS_ANYTHING (does not alias any other symbols)");
 353
 354   if (gimple_default_def (cfun, var))
 355     {
 356       fprintf (file, ", default def: ");
 357       print_generic_expr (file, gimple_default_def (cfun, var), dump_flags);
 358     }
 359
 360   if (MTAG_P (var) && may_aliases (var))
 361     {
 362       fprintf (file, ", may aliases: ");
 363       dump_may_aliases_for (file, var);
 364     }
 365
 366   if (!is_gimple_reg (var))
 367     {
 368       if (memory_partition (var))
 369         {
 370           fprintf (file, ", belongs to partition: ");
 371           print_generic_expr (file, memory_partition (var), dump_flags);
 372         }
 373
 374       if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
 375         {
 376           fprintf (file, ", partition symbols: ");
 377           dump_decl_set (file, MPT_SYMBOLS (var));
 378         }
 379     }
 380
 381   fprintf (file, "\n");
 382 }
 383
 384
 385 /* Dump variable VAR and its may-aliases to stderr.  */
 386
 387 void
 388 debug_variable (tree var)
 389 {
 390   dump_variable (stderr, var);
 391 }
 392
 393
 394 /* Dump various DFA statistics to FILE.  */
 395
 396 void
 397 dump_dfa_stats (FILE *file)
 398 {
 399   struct dfa_stats_d dfa_stats;
 400
 401   unsigned long size, total = 0;
 402   const char * const fmt_str   = "%-30s%-13s%12s\n";
 403   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 404   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 405   const char *funcname
 406     = lang_hooks.decl_printable_name (current_function_decl, 2);
 407
 408   collect_dfa_stats (&dfa_stats);
 409
 410   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 411
 412   fprintf (file, "---------------------------------------------------------\n");
 413   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 414   fprintf (file, fmt_str, "", "  instances  ", "used ");
 415   fprintf (file, "---------------------------------------------------------\n");
 416
 417   size = num_referenced_vars * sizeof (tree);
 418   total += size;
 419   fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
 420            SCALE (size), LABEL (size));
 421
 422   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 423   total += size;
 424   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 425            SCALE (size), LABEL (size));
 426
 427   size = dfa_stats.num_uses * sizeof (tree *);
 428   total += size;
 429   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 430            SCALE (size), LABEL (size));
 431
 432   size = dfa_stats.num_defs * sizeof (tree *);
 433   total += size;
 434   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 435            SCALE (size), LABEL (size));
 436
 437   size = dfa_stats.num_vuses * sizeof (tree *);
 438   total += size;
 439   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 440            SCALE (size), LABEL (size));
 441
 442   size = dfa_stats.num_vdefs * sizeof (tree *);
 443   total += size;
 444   fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
 445            SCALE (size), LABEL (size));
 446
 447   size = dfa_stats.num_phis * sizeof (struct gimple_statement_phi);
 448   total += size;
 449   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 450            SCALE (size), LABEL (size));
 451
 452   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 453   total += size;
 454   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 455            SCALE (size), LABEL (size));
 456
 457   fprintf (file, "---------------------------------------------------------\n");
 458   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 459            LABEL (total));
 460   fprintf (file, "---------------------------------------------------------\n");
 461   fprintf (file, "\n");
 462
 463   if (dfa_stats.num_phis)
 464     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %ld)\n",
 465              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 466              (long) dfa_stats.max_num_phi_args);
 467
 468   fprintf (file, "\n");
 469 }
 470
 471
 472 /* Dump DFA statistics on stderr.  */
 473
 474 void
 475 debug_dfa_stats (void)
 476 {
 477   dump_dfa_stats (stderr);
 478 }
 479
 480
 481 /* Collect DFA statistics and store them in the structure pointed to by
 482    DFA_STATS_P.  */
 483
 484 static void
 485 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED)
 486 {
 487   basic_block bb;
 488   referenced_var_iterator vi;
 489   tree var;
 490
 491   gcc_assert (dfa_stats_p);
 492
 493   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 494
 495   /* Count all the variable annotations.  */
 496   FOR_EACH_REFERENCED_VAR (var, vi)
 497     if (var_ann (var))
 498       dfa_stats_p->num_var_anns++;
 499
 500   /* Walk all the statements in the function counting references.  */
 501   FOR_EACH_BB (bb)
 502     {
 503       gimple_stmt_iterator si;
 504
 505       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
 506         {
 507           gimple phi = gsi_stmt (si);
 508           dfa_stats_p->num_phis++;
 509           dfa_stats_p->num_phi_args += gimple_phi_num_args (phi);
 510           if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args)
 511             dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi);
 512         }
 513
 514       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
 515         {
 516           gimple stmt = gsi_stmt (si);
 517           dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF);
 518           dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE);
 519           dfa_stats_p->num_vdefs += NUM_SSA_OPERANDS (stmt, SSA_OP_VDEF);
 520           dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (stmt, SSA_OP_VUSE);
 521         }
 522     }
 523 }
 524
 525
 526 /*---------------------------------------------------------------------------
 527                              Miscellaneous helpers
 528 ---------------------------------------------------------------------------*/
 529 /* Callback for walk_tree.  Used to collect variables referenced in
 530    the function.  */
 531
 532 static tree
 533 find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
 534 {
 535   /* If we are reading the lto info back in, we need to rescan the
 536      referenced vars.  */
 537   if (TREE_CODE (*tp) == SSA_NAME)
 538     add_referenced_var (SSA_NAME_VAR (*tp));
 539
 540   /* If T is a regular variable that the optimizers are interested
 541      in, add it to the list of variables.  */
 542   else if (SSA_VAR_P (*tp))
 543     add_referenced_var (*tp);
 544
 545   /* Type, _DECL and constant nodes have no interesting children.
 546      Ignore them.  */
 547   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
 548     *walk_subtrees = 0;
 549
 550   return NULL_TREE;
 551 }
 552
 553 /* Lookup UID in the referenced_vars hashtable and return the associated
 554    variable.  */
 555
 556 tree
 557 referenced_var_lookup (unsigned int uid)
 558 {
 559   tree h;
 560   struct tree_decl_minimal in;
 561   in.uid = uid;
 562   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 563   gcc_assert (h || uid == 0);
 564   return h;
 565 }
 566
 567 /* Check if TO is in the referenced_vars hash table and insert it if not.
 568    Return true if it required insertion.  */
 569
 570 bool
 571 referenced_var_check_and_insert (tree to)
 572 {
 573   tree h, *loc;
 574   struct tree_decl_minimal in;
 575   unsigned int uid = DECL_UID (to);
 576
 577   in.uid = uid;
 578   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 579   if (h)
 580     {
 581       /* DECL_UID has already been entered in the table.  Verify that it is
 582          the same entry as TO.  See PR 27793.  */
 583       gcc_assert (h == to);
 584       return false;
 585     }
 586
 587   loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun),
 588                                            &in, uid, INSERT);
 589   *loc = to;
 590   return true;
 591 }
 592
 593 /* Lookup VAR UID in the default_defs hashtable and return the associated
 594    variable.  */
 595
 596 tree
 597 gimple_default_def (struct function *fn, tree var)
 598 {
 599   struct tree_decl_minimal ind;
 600   struct tree_ssa_name in;
 601   gcc_assert (SSA_VAR_P (var));
 602   in.var = (tree)&ind;
 603   ind.uid = DECL_UID (var);
 604   return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var));
 605 }
 606
 607 /* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
 608
 609 void
 610 set_default_def (tree var, tree def)
 611 {
 612   struct tree_decl_minimal ind;
 613   struct tree_ssa_name in;
 614   void **loc;
 615
 616   gcc_assert (SSA_VAR_P (var));
 617   in.var = (tree)&ind;
 618   ind.uid = DECL_UID (var);
 619   if (!def)
 620     {
 621       loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 622             DECL_UID (var), INSERT);
 623       gcc_assert (*loc);
 624       htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
 625       return;
 626     }
 627   gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
 628   loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 629                                   DECL_UID (var), INSERT);
 630
 631   /* Default definition might be changed by tail call optimization.  */
 632   if (*loc)
 633     SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false;
 634   *(tree *) loc = def;
 635
 636    /* Mark DEF as the default definition for VAR.  */
 637    SSA_NAME_IS_DEFAULT_DEF (def) = true;
 638 }
 639
 640 /* Add VAR to the list of referenced variables if it isn't already there.  */
 641
 642 bool
 643 add_referenced_var (tree var)
 644 {
 645   var_ann_t v_ann;
 646
 647   v_ann = get_var_ann (var);
 648   gcc_assert (DECL_P (var));
 649
 650   /* Insert VAR into the referenced_vars has table if it isn't present.  */
 651   if (referenced_var_check_and_insert (var))
 652     {
 653       /* This is the first time we found this variable, annotate it with
 654          attributes that are intrinsic to the variable.  */
 655
 656       /* Tag's don't have DECL_INITIAL.  */
 657       if (MTAG_P (var))
 658         return true;
 659
 660       /* Scan DECL_INITIAL for pointer variables as they may contain
 661          address arithmetic referencing the address of other
 662          variables.
 663          Even non-constant initializers need to be walked, because
 664          IPA passes might prove that their are invariant later on.  */
 665       if (DECL_INITIAL (var)
 666           /* Initializers of external variables are not useful to the
 667              optimizers.  */
 668           && !DECL_EXTERNAL (var))
 669         walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
 670
 671       return true;
 672     }
 673
 674   return false;
 675 }
 676
 677 /* Remove VAR from the list.  */
 678
 679 void
 680 remove_referenced_var (tree var)
 681 {
 682   var_ann_t v_ann;
 683   struct tree_decl_minimal in;
 684   void **loc;
 685   unsigned int uid = DECL_UID (var);
 686
 687   clear_call_clobbered (var);
 688   bitmap_clear_bit (gimple_call_used_vars (cfun), uid);
 689   if ((v_ann = var_ann (var)))
 690     {
 691       /* Preserve var_anns of globals, but clear their alias info.  */
 692       if (MTAG_P (var)
 693           || (!TREE_STATIC (var) && !DECL_EXTERNAL (var)))
 694         {
 695           ggc_free (v_ann);
 696           var->base.ann = NULL;
 697         }
 698       else
 699         {
 700           v_ann->mpt = NULL_TREE;
 701           v_ann->symbol_mem_tag = NULL_TREE;
 702         }
 703     }
 704   gcc_assert (DECL_P (var));
 705   in.uid = uid;
 706   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
 707                                   NO_INSERT);
 708   htab_clear_slot (gimple_referenced_vars (cfun), loc);
 709 }
 710
 711
 712 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 713
 714 tree
 715 get_virtual_var (tree var)
 716 {
 717   STRIP_NOPS (var);
 718
 719   if (TREE_CODE (var) == SSA_NAME)
 720     var = SSA_NAME_VAR (var);
 721
 722   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 723          || handled_component_p (var))
 724     var = TREE_OPERAND (var, 0);
 725
 726   /* Treating GIMPLE registers as virtual variables makes no sense.
 727      Also complain if we couldn't extract a _DECL out of the original
 728      expression.  */
 729   gcc_assert (SSA_VAR_P (var));
 730   gcc_assert (!is_gimple_reg (var));
 731
 732   return var;
 733 }
 734
 735 /* Mark all the naked symbols in STMT for SSA renaming.
 736
 737    NOTE: This function should only be used for brand new statements.
 738    If the caller is modifying an existing statement, it should use the
 739    combination push_stmt_changes/pop_stmt_changes.  */
 740
 741 void
 742 mark_symbols_for_renaming (gimple stmt)
 743 {
 744   tree op;
 745   ssa_op_iter iter;
 746
 747   update_stmt (stmt);
 748
 749   /* Mark all the operands for renaming.  */
 750   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 751     if (DECL_P (op))
 752       mark_sym_for_renaming (op);
 753 }
 754
 755
 756 /* Find all variables within the gimplified statement that were not
 757    previously visible to the function and add them to the referenced
 758    variables list.  */
 759
 760 static tree
 761 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 762                             void *data ATTRIBUTE_UNUSED)
 763 {
 764   tree t = *tp;
 765
 766   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 767     {
 768       add_referenced_var (t);
 769       mark_sym_for_renaming (t);
 770     }
 771
 772   if (IS_TYPE_OR_DECL_P (t))
 773     *walk_subtrees = 0;
 774
 775   return NULL;
 776 }
 777
 778
 779 /* Find any new referenced variables in STMT.  */
 780
 781 void
 782 find_new_referenced_vars (gimple stmt)
 783 {
 784   walk_gimple_op (stmt, find_new_referenced_vars_1, NULL);
 785 }
 786
 787
 788 /* If EXP is a handled component reference for a structure, return the
 789    base variable.  The access range is delimited by bit positions *POFFSET and
 790    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 791    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 792    and *PMAX_SIZE are equal, the access is non-variable.  */
 793
 794 tree
 795 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 796                          HOST_WIDE_INT *psize,
 797                          HOST_WIDE_INT *pmax_size)
 798 {
 799   HOST_WIDE_INT bitsize = -1;
 800   HOST_WIDE_INT maxsize = -1;
 801   tree size_tree = NULL_TREE;
 802   HOST_WIDE_INT bit_offset = 0;
 803   bool seen_variable_array_ref = false;
 804   bool seen_union = false;
 805
 806   gcc_assert (!SSA_VAR_P (exp));
 807
 808   /* First get the final access size from just the outermost expression.  */
 809   if (TREE_CODE (exp) == COMPONENT_REF)
 810     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 811   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 812     size_tree = TREE_OPERAND (exp, 1);
 813   else
 814     {
 815       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 816       if (mode == BLKmode)
 817         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 818       else
 819         bitsize = GET_MODE_BITSIZE (mode);
 820     }
 821   if (size_tree != NULL_TREE)
 822     {
 823       if (! host_integerp (size_tree, 1))
 824         bitsize = -1;
 825       else
 826         bitsize = TREE_INT_CST_LOW (size_tree);
 827     }
 828
 829   /* Initially, maxsize is the same as the accessed element size.
 830      In the following it will only grow (or become -1).  */
 831   maxsize = bitsize;
 832
 833   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 834      and find the ultimate containing object.  */
 835   while (1)
 836     {
 837       switch (TREE_CODE (exp))
 838         {
 839         case BIT_FIELD_REF:
 840           bit_offset += tree_low_cst (TREE_OPERAND (exp, 2), 0);
 841           break;
 842
 843         case COMPONENT_REF:
 844           {
 845             tree field = TREE_OPERAND (exp, 1);
 846             tree this_offset = component_ref_field_offset (exp);
 847
 848             if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == UNION_TYPE)
 849               seen_union = true;
 850
 851             if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
 852               {
 853                 HOST_WIDE_INT hthis_offset = tree_low_cst (this_offset, 0);
 854
 855                 hthis_offset *= BITS_PER_UNIT;
 856                 bit_offset += hthis_offset;
 857                 bit_offset += tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 0);
 858               }
 859             else
 860               {
 861                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 862                 /* We need to adjust maxsize to the whole structure bitsize.
 863                    But we can subtract any constant offset seen so far,
 864                    because that would get us out of the structure otherwise.  */
 865                 if (maxsize != -1 && csize && host_integerp (csize, 1))
 866                   maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
 867                 else
 868                   maxsize = -1;
 869               }
 870           }
 871           break;
 872
 873         case ARRAY_REF:
 874         case ARRAY_RANGE_REF:
 875           {
 876             tree index = TREE_OPERAND (exp, 1);
 877             tree low_bound = array_ref_low_bound (exp);
 878             tree unit_size = array_ref_element_size (exp);
 879
 880             /* If the resulting bit-offset is constant, track it.  */
 881             if (host_integerp (index, 0)
 882                 && host_integerp (low_bound, 0)
 883                 && host_integerp (unit_size, 1))
 884               {
 885                 HOST_WIDE_INT hindex = tree_low_cst (index, 0);
 886
 887                 hindex -= tree_low_cst (low_bound, 0);
 888                 hindex *= tree_low_cst (unit_size, 1);
 889                 hindex *= BITS_PER_UNIT;
 890                 bit_offset += hindex;
 891
 892                 /* An array ref with a constant index up in the structure
 893                    hierarchy will constrain the size of any variable array ref
 894                    lower in the access hierarchy.  */
 895                 seen_variable_array_ref = false;
 896               }
 897             else
 898               {
 899                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 900                 /* We need to adjust maxsize to the whole array bitsize.
 901                    But we can subtract any constant offset seen so far,
 902                    because that would get us outside of the array otherwise.  */
 903                 if (maxsize != -1 && asize && host_integerp (asize, 1))
 904                   maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
 905                 else
 906                   maxsize = -1;
 907
 908                 /* Remember that we have seen an array ref with a variable
 909                    index.  */
 910                 seen_variable_array_ref = true;
 911               }
 912           }
 913           break;
 914
 915         case REALPART_EXPR:
 916           break;
 917
 918         case IMAGPART_EXPR:
 919           bit_offset += bitsize;
 920           break;
 921
 922         case VIEW_CONVERT_EXPR:
 923           /* ???  We probably should give up here and bail out.  */
 924           break;
 925
 926         default:
 927           goto done;
 928         }
 929
 930       exp = TREE_OPERAND (exp, 0);
 931     }
 932  done:
 933
 934   /* We need to deal with variable arrays ending structures such as
 935        struct { int length; int a[1]; } x;           x.a[d]
 936        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 937        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 938      where we do not know maxsize for variable index accesses to
 939      the array.  The simplest way to conservatively deal with this
 940      is to punt in the case that offset + maxsize reaches the
 941      base type boundary.
 942
 943      Unfortunately this is difficult to determine reliably when unions are
 944      involved and so we are conservative in such cases.
 945
 946      FIXME: This approach may be too conservative, we probably want to at least
 947      check that the union is the last field/element at its level or even
 948      propagate the calculated offsets back up the access chain and check
 949      there.  */
 950
 951   if (seen_variable_array_ref
 952       && (seen_union
 953           || (maxsize != -1
 954               && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
 955               && bit_offset + maxsize
 956               == (signed) TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))))
 957     maxsize = -1;
 958
 959   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 960      negative bit_offset here.  We might want to store a zero offset
 961      in this case.  */
 962   *poffset = bit_offset;
 963   *psize = bitsize;
 964   *pmax_size = maxsize;
 965
 966   return exp;
 967 }
 968
 969 /* Returns true if STMT references an SSA_NAME that has
 970    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
 971
 972 bool
 973 stmt_references_abnormal_ssa_name (gimple stmt)
 974 {
 975   ssa_op_iter oi;
 976   use_operand_p use_p;
 977
 978   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
 979     {
 980       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
 981         return true;
 982     }
 983
 984   return false;
 985 }
 986
 987 /* Return true, if the two memory references REF1 and REF2 may alias.  */
 988
 989 bool
 990 refs_may_alias_p (tree ref1, tree ref2)
 991 {
 992   tree base1, base2;
 993   HOST_WIDE_INT offset1 = 0, offset2 = 0;
 994   HOST_WIDE_INT size1 = -1, size2 = -1;
 995   HOST_WIDE_INT max_size1 = -1, max_size2 = -1;
 996   bool strict_aliasing_applies;
 997
 998   gcc_assert ((SSA_VAR_P (ref1)
 999                || handled_component_p (ref1)
1000                || INDIRECT_REF_P (ref1)
1001                || TREE_CODE (ref1) == TARGET_MEM_REF)
1002               && (SSA_VAR_P (ref2)
1003                   || handled_component_p (ref2)
1004                   || INDIRECT_REF_P (ref2)
1005                   || TREE_CODE (ref2) == TARGET_MEM_REF));
1006
1007   /* Defer to TBAA if possible.  */
1008   if (flag_strict_aliasing
1009       && !alias_sets_conflict_p (get_alias_set (ref1), get_alias_set (ref2)))
1010     return false;
1011
1012   /* Decompose the references into their base objects and the access.  */
1013   base1 = ref1;
1014   if (handled_component_p (ref1))
1015     base1 = get_ref_base_and_extent (ref1, &offset1, &size1, &max_size1);
1016   base2 = ref2;
1017   if (handled_component_p (ref2))
1018     base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &max_size2);
1019
1020   /* If both references are based on different variables, they cannot alias.
1021      If both references are based on the same variable, they cannot alias if
1022      the accesses do not overlap.  */
1023   if (SSA_VAR_P (base1)
1024       && SSA_VAR_P (base2))
1025     {
1026       if (!operand_equal_p (base1, base2, 0))
1027         return false;
1028       return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1029     }
1030
1031   /* If one base is a ref-all pointer weird things are allowed.  */
1032   strict_aliasing_applies = (flag_strict_aliasing
1033                              && (!INDIRECT_REF_P (base1)
1034                                  || get_alias_set (base1) != 0)
1035                              && (!INDIRECT_REF_P (base2)
1036                                  || get_alias_set (base2) != 0));
1037
1038   /* If strict aliasing applies the only way to access a scalar variable
1039      is through a pointer dereference or through a union (gcc extension).  */
1040   if (strict_aliasing_applies
1041       && ((SSA_VAR_P (ref2)
1042            && !AGGREGATE_TYPE_P (TREE_TYPE (ref2))
1043            && !INDIRECT_REF_P (ref1)
1044            && TREE_CODE (TREE_TYPE (base1)) != UNION_TYPE)
1045           || (SSA_VAR_P (ref1)
1046               && !AGGREGATE_TYPE_P (TREE_TYPE (ref1))
1047               && !INDIRECT_REF_P (ref2)
1048               && TREE_CODE (TREE_TYPE (base2)) != UNION_TYPE)))
1049     return false;
1050
1051   /* If both references are through the same type, or if strict aliasing
1052      doesn't apply they are through two same pointers, they do not alias
1053      if the accesses do not overlap.  */
1054   if ((strict_aliasing_applies
1055        && (TYPE_MAIN_VARIANT (TREE_TYPE (base1))
1056            == TYPE_MAIN_VARIANT (TREE_TYPE (base2))))
1057       || (TREE_CODE (base1) == INDIRECT_REF
1058           && TREE_CODE (base2) == INDIRECT_REF
1059           && operand_equal_p (TREE_OPERAND (base1, 0),
1060                               TREE_OPERAND (base2, 0), 0)))
1061     return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1062
1063   /* If both are component references through pointers try to find a
1064      common base and apply offset based disambiguation.  This handles
1065      for example
1066        struct A { int i; int j; } *q;
1067        struct B { struct A a; int k; } *p;
1068      disambiguating q->i and p->a.j.  */
1069   if (strict_aliasing_applies
1070       && (TREE_CODE (base1) == INDIRECT_REF
1071           || TREE_CODE (base2) == INDIRECT_REF)
1072       && handled_component_p (ref1)
1073       && handled_component_p (ref2))
1074     {
1075       tree *refp;
1076       /* Now search for the type of base1 in the access path of ref2.  This
1077          would be a common base for doing offset based disambiguation on.  */
1078       refp = &ref2;
1079       while (handled_component_p (*refp)
1080              /* Note that the following is only conservative if there are
1081                 never copies of types appearing as sub-structures.  */
1082              && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1083                  != TYPE_MAIN_VARIANT (TREE_TYPE (base1))))
1084         refp = &TREE_OPERAND (*refp, 0);
1085       if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1086           == TYPE_MAIN_VARIANT (TREE_TYPE (base1)))
1087         {
1088           HOST_WIDE_INT offadj, sztmp, msztmp;
1089           get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
1090           offset2 -= offadj;
1091           return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1092         }
1093       /* The other way around.  */
1094       refp = &ref1;
1095       while (handled_component_p (*refp)
1096              && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1097                  != TYPE_MAIN_VARIANT (TREE_TYPE (base2))))
1098         refp = &TREE_OPERAND (*refp, 0);
1099       if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1100           == TYPE_MAIN_VARIANT (TREE_TYPE (base2)))
1101         {
1102           HOST_WIDE_INT offadj, sztmp, msztmp;
1103           get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
1104           offset1 -= offadj;
1105           return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1106         }
1107       /* If we can be sure to catch all equivalent types in the search
1108          for the common base then we could return false here.  In that
1109          case we would be able to disambiguate q->i and p->k.  */
1110     }
1111
1112   return true;
1113 }
1114
1115 /* Given a stmt STMT that references memory, return the single stmt
1116    that is reached by following the VUSE -> VDEF link.  Returns
1117    NULL_TREE, if there is no single stmt that defines all VUSEs of
1118    STMT.
1119    Note that for a stmt with a single virtual operand this may return
1120    a PHI node as well.  Note that if all VUSEs are default definitions
1121    this function will return an empty statement.  */
1122
1123 gimple
1124 get_single_def_stmt (gimple stmt)
1125 {
1126   gimple def_stmt = NULL;
1127   tree use;
1128   ssa_op_iter iter;
1129
1130   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_VIRTUAL_USES)
1131     {
1132       gimple tmp = SSA_NAME_DEF_STMT (use);
1133
1134       /* ???  This is too simplistic for multiple virtual operands
1135          reaching different PHI nodes of the same basic blocks or for
1136          reaching all default definitions.  */
1137       if (def_stmt
1138           && def_stmt != tmp
1139           && !(gimple_nop_p (def_stmt)
1140                && gimple_nop_p (tmp)))
1141         return NULL;
1142
1143       def_stmt = tmp;
1144     }
1145
1146   return def_stmt;
1147 }
1148
1149 /* Given a PHI node of virtual operands, tries to eliminate cyclic
1150    reached definitions if they do not alias REF and returns the
1151    defining statement of the single virtual operand that flows in
1152    from a non-backedge.  Returns NULL_TREE if such statement within
1153    the above conditions cannot be found.  */
1154
1155 gimple
1156 get_single_def_stmt_from_phi (tree ref, gimple phi)
1157 {
1158   tree def_arg = NULL_TREE;
1159   unsigned i;
1160
1161   /* Find the single PHI argument that is not flowing in from a
1162      back edge and verify that the loop-carried definitions do
1163      not alias the reference we look for.  */
1164   for (i = 0; i < gimple_phi_num_args (phi); ++i)
1165     {
1166       tree arg = PHI_ARG_DEF (phi, i);
1167       gimple def_stmt;
1168
1169       if (!(gimple_phi_arg_edge (phi, i)->flags & EDGE_DFS_BACK))
1170         {
1171           /* Multiple non-back edges?  Do not try to handle this.  */
1172           if (def_arg)
1173             return NULL;
1174           def_arg = arg;
1175           continue;
1176         }
1177
1178       /* Follow the definitions back to the original PHI node.  Bail
1179          out once a definition is found that may alias REF.  */
1180       def_stmt = SSA_NAME_DEF_STMT (arg);
1181       do
1182         {
1183           if (!is_gimple_assign (def_stmt)
1184               || refs_may_alias_p (ref, gimple_assign_lhs (def_stmt)))
1185             return NULL;
1186           /* ???  This will only work, reaching the PHI node again if
1187              there is a single virtual operand on def_stmt.  */
1188           def_stmt = get_single_def_stmt (def_stmt);
1189           if (!def_stmt)
1190             return NULL;
1191         }
1192       while (def_stmt != phi);
1193     }
1194
1195   return SSA_NAME_DEF_STMT (def_arg);
1196 }
1197
1198 /* Return the single reference statement defining all virtual uses
1199    on STMT or NULL_TREE, if there are multiple defining statements.
1200    Take into account only definitions that alias REF if following
1201    back-edges when looking through a loop PHI node.  */
1202
1203 gimple
1204 get_single_def_stmt_with_phi (tree ref, gimple stmt)
1205 {
1206   switch (NUM_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES))
1207     {
1208     case 0:
1209       gcc_unreachable ();
1210
1211     case 1:
1212       {
1213         gimple def_stmt = SSA_NAME_DEF_STMT (SINGLE_SSA_TREE_OPERAND
1214                                              (stmt, SSA_OP_VIRTUAL_USES));
1215         /* We can handle lookups over PHI nodes only for a single
1216            virtual operand.  */
1217         if (gimple_code (def_stmt) == GIMPLE_PHI)
1218           return get_single_def_stmt_from_phi (ref, def_stmt);
1219         return def_stmt;
1220       }
1221
1222     default:
1223       return get_single_def_stmt (stmt);
1224     }
1225 }