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