gcc/tree-dfa.c

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