gcc/tree-dfa.c

   1 /* Data flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008 Free Software
   3    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 void
 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;
 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 }
 672
 673 /* Remove VAR from the list.  */
 674
 675 void
 676 remove_referenced_var (tree var)
 677 {
 678   var_ann_t v_ann;
 679   struct tree_decl_minimal in;
 680   void **loc;
 681   unsigned int uid = DECL_UID (var);
 682
 683   clear_call_clobbered (var);
 684   bitmap_clear_bit (gimple_call_used_vars (cfun), uid);
 685   if ((v_ann = var_ann (var)))
 686     {
 687       /* Preserve var_anns of globals, but clear their alias info.  */
 688       if (MTAG_P (var)
 689           || (!TREE_STATIC (var) && !DECL_EXTERNAL (var)))
 690         {
 691           ggc_free (v_ann);
 692           var->base.ann = NULL;
 693         }
 694       else
 695         {
 696           v_ann->mpt = NULL_TREE;
 697           v_ann->symbol_mem_tag = NULL_TREE;
 698         }
 699     }
 700   gcc_assert (DECL_P (var));
 701   in.uid = uid;
 702   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
 703                                   NO_INSERT);
 704   htab_clear_slot (gimple_referenced_vars (cfun), loc);
 705 }
 706
 707
 708 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 709
 710 tree
 711 get_virtual_var (tree var)
 712 {
 713   STRIP_NOPS (var);
 714
 715   if (TREE_CODE (var) == SSA_NAME)
 716     var = SSA_NAME_VAR (var);
 717
 718   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 719          || handled_component_p (var))
 720     var = TREE_OPERAND (var, 0);
 721
 722   /* Treating GIMPLE registers as virtual variables makes no sense.
 723      Also complain if we couldn't extract a _DECL out of the original
 724      expression.  */
 725   gcc_assert (SSA_VAR_P (var));
 726   gcc_assert (!is_gimple_reg (var));
 727
 728   return var;
 729 }
 730
 731 /* Mark all the naked symbols in STMT for SSA renaming.
 732
 733    NOTE: This function should only be used for brand new statements.
 734    If the caller is modifying an existing statement, it should use the
 735    combination push_stmt_changes/pop_stmt_changes.  */
 736
 737 void
 738 mark_symbols_for_renaming (gimple stmt)
 739 {
 740   tree op;
 741   ssa_op_iter iter;
 742
 743   update_stmt (stmt);
 744
 745   /* Mark all the operands for renaming.  */
 746   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 747     if (DECL_P (op))
 748       mark_sym_for_renaming (op);
 749 }
 750
 751
 752 /* Find all variables within the gimplified statement that were not
 753    previously visible to the function and add them to the referenced
 754    variables list.  */
 755
 756 static tree
 757 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 758                             void *data ATTRIBUTE_UNUSED)
 759 {
 760   tree t = *tp;
 761
 762   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 763     {
 764       add_referenced_var (t);
 765       mark_sym_for_renaming (t);
 766     }
 767
 768   if (IS_TYPE_OR_DECL_P (t))
 769     *walk_subtrees = 0;
 770
 771   return NULL;
 772 }
 773
 774
 775 /* Find any new referenced variables in STMT.  */
 776
 777 void
 778 find_new_referenced_vars (gimple stmt)
 779 {
 780   walk_gimple_op (stmt, find_new_referenced_vars_1, NULL);
 781 }
 782
 783
 784 /* If EXP is a handled component reference for a structure, return the
 785    base variable.  The access range is delimited by bit positions *POFFSET and
 786    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 787    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 788    and *PMAX_SIZE are equal, the access is non-variable.  */
 789
 790 tree
 791 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 792                          HOST_WIDE_INT *psize,
 793                          HOST_WIDE_INT *pmax_size)
 794 {
 795   HOST_WIDE_INT bitsize = -1;
 796   HOST_WIDE_INT maxsize = -1;
 797   tree size_tree = NULL_TREE;
 798   HOST_WIDE_INT bit_offset = 0;
 799   bool seen_variable_array_ref = false;
 800
 801   gcc_assert (!SSA_VAR_P (exp));
 802
 803   /* First get the final access size from just the outermost expression.  */
 804   if (TREE_CODE (exp) == COMPONENT_REF)
 805     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 806   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 807     size_tree = TREE_OPERAND (exp, 1);
 808   else
 809     {
 810       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 811       if (mode == BLKmode)
 812         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 813       else
 814         bitsize = GET_MODE_BITSIZE (mode);
 815     }
 816   if (size_tree != NULL_TREE)
 817     {
 818       if (! host_integerp (size_tree, 1))
 819         bitsize = -1;
 820       else
 821         bitsize = TREE_INT_CST_LOW (size_tree);
 822     }
 823
 824   /* Initially, maxsize is the same as the accessed element size.
 825      In the following it will only grow (or become -1).  */
 826   maxsize = bitsize;
 827
 828   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 829      and find the ultimate containing object.  */
 830   while (1)
 831     {
 832       switch (TREE_CODE (exp))
 833         {
 834         case BIT_FIELD_REF:
 835           bit_offset += tree_low_cst (TREE_OPERAND (exp, 2), 0);
 836           break;
 837
 838         case COMPONENT_REF:
 839           {
 840             tree field = TREE_OPERAND (exp, 1);
 841             tree this_offset = component_ref_field_offset (exp);
 842
 843             if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
 844               {
 845                 HOST_WIDE_INT hthis_offset = tree_low_cst (this_offset, 0);
 846
 847                 hthis_offset *= BITS_PER_UNIT;
 848                 bit_offset += hthis_offset;
 849                 bit_offset += tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 0);
 850               }
 851             else
 852               {
 853                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 854                 /* We need to adjust maxsize to the whole structure bitsize.
 855                    But we can subtract any constant offset seen so far,
 856                    because that would get us out of the structure otherwise.  */
 857                 if (maxsize != -1 && csize && host_integerp (csize, 1))
 858                   maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
 859                 else
 860                   maxsize = -1;
 861               }
 862           }
 863           break;
 864
 865         case ARRAY_REF:
 866         case ARRAY_RANGE_REF:
 867           {
 868             tree index = TREE_OPERAND (exp, 1);
 869             tree low_bound = array_ref_low_bound (exp);
 870             tree unit_size = array_ref_element_size (exp);
 871
 872             /* If the resulting bit-offset is constant, track it.  */
 873             if (host_integerp (index, 0)
 874                 && host_integerp (low_bound, 0)
 875                 && host_integerp (unit_size, 1))
 876               {
 877                 HOST_WIDE_INT hindex = tree_low_cst (index, 0);
 878
 879                 hindex -= tree_low_cst (low_bound, 0);
 880                 hindex *= tree_low_cst (unit_size, 1);
 881                 hindex *= BITS_PER_UNIT;
 882                 bit_offset += hindex;
 883
 884                 /* An array ref with a constant index up in the structure
 885                    hierarchy will constrain the size of any variable array ref
 886                    lower in the access hierarchy.  */
 887                 seen_variable_array_ref = false;
 888               }
 889             else
 890               {
 891                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 892                 /* We need to adjust maxsize to the whole array bitsize.
 893                    But we can subtract any constant offset seen so far,
 894                    because that would get us outside of the array otherwise.  */
 895                 if (maxsize != -1 && asize && host_integerp (asize, 1))
 896                   maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
 897                 else
 898                   maxsize = -1;
 899
 900                 /* Remember that we have seen an array ref with a variable
 901                    index.  */
 902                 seen_variable_array_ref = true;
 903               }
 904           }
 905           break;
 906
 907         case REALPART_EXPR:
 908           break;
 909
 910         case IMAGPART_EXPR:
 911           bit_offset += bitsize;
 912           break;
 913
 914         case VIEW_CONVERT_EXPR:
 915           /* ???  We probably should give up here and bail out.  */
 916           break;
 917
 918         default:
 919           goto done;
 920         }
 921
 922       exp = TREE_OPERAND (exp, 0);
 923     }
 924  done:
 925
 926   /* We need to deal with variable arrays ending structures such as
 927        struct { int length; int a[1]; } x;           x.a[d]
 928        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 929        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 930      where we do not know maxsize for variable index accesses to
 931      the array.  The simplest way to conservatively deal with this
 932      is to punt in the case that offset + maxsize reaches the
 933      base type boundary.  */
 934   if (seen_variable_array_ref
 935       && maxsize != -1
 936       && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
 937       && bit_offset + maxsize
 938            == (signed)TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))
 939     maxsize = -1;
 940
 941   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 942      negative bit_offset here.  We might want to store a zero offset
 943      in this case.  */
 944   *poffset = bit_offset;
 945   *psize = bitsize;
 946   *pmax_size = maxsize;
 947
 948   return exp;
 949 }
 950
 951 /* Returns true if STMT references an SSA_NAME that has
 952    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
 953
 954 bool
 955 stmt_references_abnormal_ssa_name (gimple stmt)
 956 {
 957   ssa_op_iter oi;
 958   use_operand_p use_p;
 959
 960   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
 961     {
 962       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
 963         return true;
 964     }
 965
 966   return false;
 967 }
 968
 969 /* Return true, if the two memory references REF1 and REF2 may alias.  */
 970
 971 bool
 972 refs_may_alias_p (tree ref1, tree ref2)
 973 {
 974   tree base1, base2;
 975   HOST_WIDE_INT offset1 = 0, offset2 = 0;
 976   HOST_WIDE_INT size1 = -1, size2 = -1;
 977   HOST_WIDE_INT max_size1 = -1, max_size2 = -1;
 978   bool strict_aliasing_applies;
 979
 980   gcc_assert ((SSA_VAR_P (ref1)
 981                || handled_component_p (ref1)
 982                || INDIRECT_REF_P (ref1)
 983                || TREE_CODE (ref1) == TARGET_MEM_REF)
 984               && (SSA_VAR_P (ref2)
 985                   || handled_component_p (ref2)
 986                   || INDIRECT_REF_P (ref2)
 987                   || TREE_CODE (ref2) == TARGET_MEM_REF));
 988
 989   /* Defer to TBAA if possible.  */
 990   if (flag_strict_aliasing
 991       && !alias_sets_conflict_p (get_alias_set (ref1), get_alias_set (ref2)))
 992     return false;
 993
 994   /* Decompose the references into their base objects and the access.  */
 995   base1 = ref1;
 996   if (handled_component_p (ref1))
 997     base1 = get_ref_base_and_extent (ref1, &offset1, &size1, &max_size1);
 998   base2 = ref2;
 999   if (handled_component_p (ref2))
1000     base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &max_size2);
1001
1002   /* If both references are based on different variables, they cannot alias.
1003      If both references are based on the same variable, they cannot alias if
1004      the accesses do not overlap.  */
1005   if (SSA_VAR_P (base1)
1006       && SSA_VAR_P (base2))
1007     {
1008       if (!operand_equal_p (base1, base2, 0))
1009         return false;
1010       return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1011     }
1012
1013   /* If one base is a ref-all pointer weird things are allowed.  */
1014   strict_aliasing_applies = (flag_strict_aliasing
1015                              && (!INDIRECT_REF_P (base1)
1016                                  || get_alias_set (base1) != 0)
1017                              && (!INDIRECT_REF_P (base2)
1018                                  || get_alias_set (base2) != 0));
1019
1020   /* If strict aliasing applies the only way to access a scalar variable
1021      is through a pointer dereference or through a union (gcc extension).  */
1022   if (strict_aliasing_applies
1023       && ((SSA_VAR_P (ref2)
1024            && !AGGREGATE_TYPE_P (TREE_TYPE (ref2))
1025            && !INDIRECT_REF_P (ref1)
1026            && TREE_CODE (TREE_TYPE (base1)) != UNION_TYPE)
1027           || (SSA_VAR_P (ref1)
1028               && !AGGREGATE_TYPE_P (TREE_TYPE (ref1))
1029               && !INDIRECT_REF_P (ref2)
1030               && TREE_CODE (TREE_TYPE (base2)) != UNION_TYPE)))
1031     return false;
1032
1033   /* If both references are through the same type, or if strict aliasing
1034      doesn't apply they are through two same pointers, they do not alias
1035      if the accesses do not overlap.  */
1036   if ((strict_aliasing_applies
1037        && (TYPE_MAIN_VARIANT (TREE_TYPE (base1))
1038            == TYPE_MAIN_VARIANT (TREE_TYPE (base2))))
1039       || (TREE_CODE (base1) == INDIRECT_REF
1040           && TREE_CODE (base2) == INDIRECT_REF
1041           && operand_equal_p (TREE_OPERAND (base1, 0),
1042                               TREE_OPERAND (base2, 0), 0)))
1043     return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1044
1045   /* If both are component references through pointers try to find a
1046      common base and apply offset based disambiguation.  This handles
1047      for example
1048        struct A { int i; int j; } *q;
1049        struct B { struct A a; int k; } *p;
1050      disambiguating q->i and p->a.j.  */
1051   if (strict_aliasing_applies
1052       && (TREE_CODE (base1) == INDIRECT_REF
1053           || TREE_CODE (base2) == INDIRECT_REF)
1054       && handled_component_p (ref1)
1055       && handled_component_p (ref2))
1056     {
1057       tree *refp;
1058       /* Now search for the type of base1 in the access path of ref2.  This
1059          would be a common base for doing offset based disambiguation on.  */
1060       refp = &ref2;
1061       while (handled_component_p (*refp)
1062              /* Note that the following is only conservative if there are
1063                 never copies of types appearing as sub-structures.  */
1064              && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1065                  != TYPE_MAIN_VARIANT (TREE_TYPE (base1))))
1066         refp = &TREE_OPERAND (*refp, 0);
1067       if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1068           == TYPE_MAIN_VARIANT (TREE_TYPE (base1)))
1069         {
1070           HOST_WIDE_INT offadj, sztmp, msztmp;
1071           get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
1072           offset2 -= offadj;
1073           return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1074         }
1075       /* The other way around.  */
1076       refp = &ref1;
1077       while (handled_component_p (*refp)
1078              && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1079                  != TYPE_MAIN_VARIANT (TREE_TYPE (base2))))
1080         refp = &TREE_OPERAND (*refp, 0);
1081       if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1082           == TYPE_MAIN_VARIANT (TREE_TYPE (base2)))
1083         {
1084           HOST_WIDE_INT offadj, sztmp, msztmp;
1085           get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
1086           offset1 -= offadj;
1087           return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1088         }
1089       /* If we can be sure to catch all equivalent types in the search
1090          for the common base then we could return false here.  In that
1091          case we would be able to disambiguate q->i and p->k.  */
1092     }
1093
1094   return true;
1095 }
1096
1097 /* Given a stmt STMT that references memory, return the single stmt
1098    that is reached by following the VUSE -> VDEF link.  Returns
1099    NULL_TREE, if there is no single stmt that defines all VUSEs of
1100    STMT.
1101    Note that for a stmt with a single virtual operand this may return
1102    a PHI node as well.  Note that if all VUSEs are default definitions
1103    this function will return an empty statement.  */
1104
1105 gimple
1106 get_single_def_stmt (gimple stmt)
1107 {
1108   gimple def_stmt = NULL;
1109   tree use;
1110   ssa_op_iter iter;
1111
1112   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_VIRTUAL_USES)
1113     {
1114       gimple tmp = SSA_NAME_DEF_STMT (use);
1115
1116       /* ???  This is too simplistic for multiple virtual operands
1117          reaching different PHI nodes of the same basic blocks or for
1118          reaching all default definitions.  */
1119       if (def_stmt
1120           && def_stmt != tmp
1121           && !(gimple_nop_p (def_stmt)
1122                && gimple_nop_p (tmp)))
1123         return NULL;
1124
1125       def_stmt = tmp;
1126     }
1127
1128   return def_stmt;
1129 }
1130
1131 /* Given a PHI node of virtual operands, tries to eliminate cyclic
1132    reached definitions if they do not alias REF and returns the
1133    defining statement of the single virtual operand that flows in
1134    from a non-backedge.  Returns NULL_TREE if such statement within
1135    the above conditions cannot be found.  */
1136
1137 gimple
1138 get_single_def_stmt_from_phi (tree ref, gimple phi)
1139 {
1140   tree def_arg = NULL_TREE;
1141   unsigned i;
1142
1143   /* Find the single PHI argument that is not flowing in from a
1144      back edge and verify that the loop-carried definitions do
1145      not alias the reference we look for.  */
1146   for (i = 0; i < gimple_phi_num_args (phi); ++i)
1147     {
1148       tree arg = PHI_ARG_DEF (phi, i);
1149       gimple def_stmt;
1150
1151       if (!(gimple_phi_arg_edge (phi, i)->flags & EDGE_DFS_BACK))
1152         {
1153           /* Multiple non-back edges?  Do not try to handle this.  */
1154           if (def_arg)
1155             return NULL;
1156           def_arg = arg;
1157           continue;
1158         }
1159
1160       /* Follow the definitions back to the original PHI node.  Bail
1161          out once a definition is found that may alias REF.  */
1162       def_stmt = SSA_NAME_DEF_STMT (arg);
1163       do
1164         {
1165           if (!is_gimple_assign (def_stmt)
1166               || refs_may_alias_p (ref, gimple_assign_lhs (def_stmt)))
1167             return NULL;
1168           /* ???  This will only work, reaching the PHI node again if
1169              there is a single virtual operand on def_stmt.  */
1170           def_stmt = get_single_def_stmt (def_stmt);
1171           if (!def_stmt)
1172             return NULL;
1173         }
1174       while (def_stmt != phi);
1175     }
1176
1177   return SSA_NAME_DEF_STMT (def_arg);
1178 }
1179
1180 /* Return the single reference statement defining all virtual uses
1181    on STMT or NULL_TREE, if there are multiple defining statements.
1182    Take into account only definitions that alias REF if following
1183    back-edges when looking through a loop PHI node.  */
1184
1185 gimple
1186 get_single_def_stmt_with_phi (tree ref, gimple stmt)
1187 {
1188   switch (NUM_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES))
1189     {
1190     case 0:
1191       gcc_unreachable ();
1192
1193     case 1:
1194       {
1195         gimple def_stmt = SSA_NAME_DEF_STMT (SINGLE_SSA_TREE_OPERAND
1196                                              (stmt, SSA_OP_VIRTUAL_USES));
1197         /* We can handle lookups over PHI nodes only for a single
1198            virtual operand.  */
1199         if (gimple_code (def_stmt) == GIMPLE_PHI)
1200           return get_single_def_stmt_from_phi (ref, def_stmt);
1201         return def_stmt;
1202       }
1203
1204     default:
1205       return get_single_def_stmt (stmt);
1206     }
1207 }