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 tree_opt_pass pass_referenced_vars =
 100 {
 101   NULL,                                 /* name */
 102   NULL,                                 /* gate */
 103   find_referenced_vars,                 /* execute */
 104   NULL,                                 /* sub */
 105   NULL,                                 /* next */
 106   0,                                    /* static_pass_number */
 107   TV_FIND_REFERENCED_VARS,              /* tv_id */
 108   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 109   PROP_referenced_vars,                 /* properties_provided */
 110   0,                                    /* properties_destroyed */
 111   0,                                    /* todo_flags_start */
 112   0,                                    /* todo_flags_finish */
 113   0                                     /* letter */
 114 };
 115
 116
 117 /*---------------------------------------------------------------------------
 118                             Manage annotations
 119 ---------------------------------------------------------------------------*/
 120 /* Create a new annotation for a _DECL node T.  */
 121
 122 var_ann_t
 123 create_var_ann (tree t)
 124 {
 125   var_ann_t ann;
 126   struct static_var_ann_d *sann = NULL;
 127
 128   gcc_assert (t);
 129   gcc_assert (DECL_P (t));
 130   gcc_assert (!t->base.ann || t->base.ann->common.type == VAR_ANN);
 131
 132   if (!MTAG_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
 133     {
 134       sann = GGC_CNEW (struct static_var_ann_d);
 135       ann = &sann->ann;
 136     }
 137   else
 138     ann = GGC_CNEW (struct var_ann_d);
 139
 140   ann->common.type = VAR_ANN;
 141
 142   if (!MTAG_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
 143     {
 144        void **slot;
 145        sann->uid = DECL_UID (t);
 146        slot = htab_find_slot_with_hash (gimple_var_anns (cfun),
 147                                         t, DECL_UID (t), INSERT);
 148        gcc_assert (!*slot);
 149        *slot = sann;
 150     }
 151   else
 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 = 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 /* Create a new annotation for a statement node T.  */
 179
 180 stmt_ann_t
 181 create_stmt_ann (tree t)
 182 {
 183   stmt_ann_t ann;
 184
 185   gcc_assert (is_gimple_stmt (t));
 186   gcc_assert (!t->base.ann || t->base.ann->common.type == STMT_ANN);
 187
 188   ann = GGC_CNEW (struct stmt_ann_d);
 189
 190   ann->common.type = STMT_ANN;
 191
 192   /* Since we just created the annotation, mark the statement modified.  */
 193   ann->modified = true;
 194
 195   t->base.ann = (tree_ann_t) ann;
 196
 197   return ann;
 198 }
 199
 200 /* Create a new annotation for a tree T.  */
 201
 202 tree_ann_common_t
 203 create_tree_common_ann (tree t)
 204 {
 205   tree_ann_common_t ann;
 206
 207   gcc_assert (t);
 208   gcc_assert (!t->base.ann || t->base.ann->common.type == TREE_ANN_COMMON);
 209
 210   ann = GGC_CNEW (struct tree_ann_common_d);
 211
 212   ann->type = TREE_ANN_COMMON;
 213   t->base.ann = (tree_ann_t) ann;
 214
 215   return ann;
 216 }
 217
 218 /* Build a temporary.  Make sure and register it to be renamed.  */
 219
 220 tree
 221 make_rename_temp (tree type, const char *prefix)
 222 {
 223   tree t = create_tmp_var (type, prefix);
 224
 225   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 226       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 227     DECL_GIMPLE_REG_P (t) = 1;
 228
 229   if (gimple_referenced_vars (cfun))
 230     {
 231       add_referenced_var (t);
 232       mark_sym_for_renaming (t);
 233     }
 234
 235   return t;
 236 }
 237
 238
 239
 240 /*---------------------------------------------------------------------------
 241                               Debugging functions
 242 ---------------------------------------------------------------------------*/
 243 /* Dump the list of all the referenced variables in the current function to
 244    FILE.  */
 245
 246 void
 247 dump_referenced_vars (FILE *file)
 248 {
 249   tree var;
 250   referenced_var_iterator rvi;
 251
 252   fprintf (file, "\nReferenced variables in %s: %u\n\n",
 253            get_name (current_function_decl), (unsigned) num_referenced_vars);
 254
 255   FOR_EACH_REFERENCED_VAR (var, rvi)
 256     {
 257       fprintf (file, "Variable: ");
 258       dump_variable (file, var);
 259       fprintf (file, "\n");
 260     }
 261 }
 262
 263
 264 /* Dump the list of all the referenced variables to stderr.  */
 265
 266 void
 267 debug_referenced_vars (void)
 268 {
 269   dump_referenced_vars (stderr);
 270 }
 271
 272
 273 /* Dump sub-variables for VAR to FILE.  */
 274
 275 void
 276 dump_subvars_for (FILE *file, tree var)
 277 {
 278   subvar_t sv = get_subvars_for_var (var);
 279   tree subvar;
 280   unsigned int i;
 281
 282   if (!sv)
 283     return;
 284
 285   fprintf (file, "{ ");
 286
 287   for (i = 0; VEC_iterate (tree, sv, i, subvar); ++i)
 288     {
 289       print_generic_expr (file, subvar, dump_flags);
 290       fprintf (file, " ");
 291     }
 292
 293   fprintf (file, "}");
 294 }
 295
 296
 297 /* Dumb sub-variables for VAR to stderr.  */
 298
 299 void
 300 debug_subvars_for (tree var)
 301 {
 302   dump_subvars_for (stderr, var);
 303 }
 304
 305
 306 /* Dump variable VAR and its may-aliases to FILE.  */
 307
 308 void
 309 dump_variable (FILE *file, tree var)
 310 {
 311   var_ann_t ann;
 312
 313   if (TREE_CODE (var) == SSA_NAME)
 314     {
 315       if (POINTER_TYPE_P (TREE_TYPE (var)))
 316         dump_points_to_info_for (file, var);
 317       var = SSA_NAME_VAR (var);
 318     }
 319
 320   if (var == NULL_TREE)
 321     {
 322       fprintf (file, "<nil>");
 323       return;
 324     }
 325
 326   print_generic_expr (file, var, dump_flags);
 327
 328   ann = var_ann (var);
 329
 330   fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
 331
 332   fprintf (file, ", ");
 333   print_generic_expr (file, TREE_TYPE (var), dump_flags);
 334
 335   if (ann && ann->symbol_mem_tag)
 336     {
 337       fprintf (file, ", symbol memory tag: ");
 338       print_generic_expr (file, ann->symbol_mem_tag, dump_flags);
 339     }
 340
 341   if (TREE_ADDRESSABLE (var))
 342     fprintf (file, ", is addressable");
 343
 344   if (is_global_var (var))
 345     fprintf (file, ", is global");
 346
 347   if (TREE_THIS_VOLATILE (var))
 348     fprintf (file, ", is volatile");
 349
 350   dump_mem_sym_stats_for_var (file, var);
 351
 352   if (is_call_clobbered (var))
 353     {
 354       const char *s = "";
 355       var_ann_t va = var_ann (var);
 356       unsigned int escape_mask = va->escape_mask;
 357
 358       fprintf (file, ", call clobbered");
 359       fprintf (file, " (");
 360       if (escape_mask & ESCAPE_STORED_IN_GLOBAL)
 361         { fprintf (file, "%sstored in global", s); s = ", "; }
 362       if (escape_mask & ESCAPE_TO_ASM)
 363         { fprintf (file, "%sgoes through ASM", s); s = ", "; }
 364       if (escape_mask & ESCAPE_TO_CALL)
 365         { fprintf (file, "%spassed to call", s); s = ", "; }
 366       if (escape_mask & ESCAPE_BAD_CAST)
 367         { fprintf (file, "%sbad cast", s); s = ", "; }
 368       if (escape_mask & ESCAPE_TO_RETURN)
 369         { fprintf (file, "%sreturned from func", s); s = ", "; }
 370       if (escape_mask & ESCAPE_TO_PURE_CONST)
 371         { fprintf (file, "%spassed to pure/const", s); s = ", "; }
 372       if (escape_mask & ESCAPE_IS_GLOBAL)
 373         { fprintf (file, "%sis global var", s); s = ", "; }
 374       if (escape_mask & ESCAPE_IS_PARM)
 375         { fprintf (file, "%sis incoming pointer", s); s = ", "; }
 376       if (escape_mask & ESCAPE_UNKNOWN)
 377         { fprintf (file, "%sunknown escape", s); s = ", "; }
 378       fprintf (file, ")");
 379     }
 380
 381   if (ann->noalias_state == NO_ALIAS)
 382     fprintf (file, ", NO_ALIAS (does not alias other NO_ALIAS symbols)");
 383   else if (ann->noalias_state == NO_ALIAS_GLOBAL)
 384     fprintf (file, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols"
 385                    " and global vars)");
 386   else if (ann->noalias_state == NO_ALIAS_ANYTHING)
 387     fprintf (file, ", NO_ALIAS_ANYTHING (does not alias any other symbols)");
 388
 389   if (gimple_default_def (cfun, var))
 390     {
 391       fprintf (file, ", default def: ");
 392       print_generic_expr (file, gimple_default_def (cfun, var), dump_flags);
 393     }
 394
 395   if (MTAG_P (var) && may_aliases (var))
 396     {
 397       fprintf (file, ", may aliases: ");
 398       dump_may_aliases_for (file, var);
 399     }
 400
 401   if (get_subvars_for_var (var))
 402     {
 403       fprintf (file, ", sub-vars: ");
 404       dump_subvars_for (file, var);
 405     }
 406
 407   if (!is_gimple_reg (var))
 408     {
 409       if (memory_partition (var))
 410         {
 411           fprintf (file, ", belongs to partition: ");
 412           print_generic_expr (file, memory_partition (var), dump_flags);
 413         }
 414
 415       if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
 416         {
 417           fprintf (file, ", partition symbols: ");
 418           dump_decl_set (file, MPT_SYMBOLS (var));
 419         }
 420     }
 421
 422   fprintf (file, "\n");
 423 }
 424
 425
 426 /* Dump variable VAR and its may-aliases to stderr.  */
 427
 428 void
 429 debug_variable (tree var)
 430 {
 431   dump_variable (stderr, var);
 432 }
 433
 434
 435 /* Dump various DFA statistics to FILE.  */
 436
 437 void
 438 dump_dfa_stats (FILE *file)
 439 {
 440   struct dfa_stats_d dfa_stats;
 441
 442   unsigned long size, total = 0;
 443   const char * const fmt_str   = "%-30s%-13s%12s\n";
 444   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 445   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 446   const char *funcname
 447     = lang_hooks.decl_printable_name (current_function_decl, 2);
 448
 449   collect_dfa_stats (&dfa_stats);
 450
 451   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 452
 453   fprintf (file, "---------------------------------------------------------\n");
 454   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 455   fprintf (file, fmt_str, "", "  instances  ", "used ");
 456   fprintf (file, "---------------------------------------------------------\n");
 457
 458   size = num_referenced_vars * sizeof (tree);
 459   total += size;
 460   fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
 461            SCALE (size), LABEL (size));
 462
 463   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
 464   total += size;
 465   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
 466            SCALE (size), LABEL (size));
 467
 468   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 469   total += size;
 470   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 471            SCALE (size), LABEL (size));
 472
 473   size = dfa_stats.num_uses * sizeof (tree *);
 474   total += size;
 475   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 476            SCALE (size), LABEL (size));
 477
 478   size = dfa_stats.num_defs * sizeof (tree *);
 479   total += size;
 480   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 481            SCALE (size), LABEL (size));
 482
 483   size = dfa_stats.num_vuses * sizeof (tree *);
 484   total += size;
 485   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 486            SCALE (size), LABEL (size));
 487
 488   size = dfa_stats.num_vdefs * sizeof (tree *);
 489   total += size;
 490   fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
 491            SCALE (size), LABEL (size));
 492
 493   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
 494   total += size;
 495   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 496            SCALE (size), LABEL (size));
 497
 498   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 499   total += size;
 500   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 501            SCALE (size), LABEL (size));
 502
 503   fprintf (file, "---------------------------------------------------------\n");
 504   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 505            LABEL (total));
 506   fprintf (file, "---------------------------------------------------------\n");
 507   fprintf (file, "\n");
 508
 509   if (dfa_stats.num_phis)
 510     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
 511              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 512              dfa_stats.max_num_phi_args);
 513
 514   fprintf (file, "\n");
 515 }
 516
 517
 518 /* Dump DFA statistics on stderr.  */
 519
 520 void
 521 debug_dfa_stats (void)
 522 {
 523   dump_dfa_stats (stderr);
 524 }
 525
 526
 527 /* Collect DFA statistics and store them in the structure pointed to by
 528    DFA_STATS_P.  */
 529
 530 static void
 531 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
 532 {
 533   struct pointer_set_t *pset;
 534   basic_block bb;
 535   block_stmt_iterator i;
 536
 537   gcc_assert (dfa_stats_p);
 538
 539   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 540
 541   /* Walk all the trees in the function counting references.  Start at
 542      basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries.  */
 543   pset = pointer_set_create ();
 544
 545   for (i = bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
 546        !bsi_end_p (i); bsi_next (&i))
 547     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
 548                pset);
 549
 550   pointer_set_destroy (pset);
 551
 552   FOR_EACH_BB (bb)
 553     {
 554       tree phi;
 555       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 556         {
 557           dfa_stats_p->num_phis++;
 558           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
 559           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
 560             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
 561         }
 562     }
 563 }
 564
 565
 566 /* Callback for walk_tree to collect DFA statistics for a tree and its
 567    children.  */
 568
 569 static tree
 570 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 571                      void *data)
 572 {
 573   tree t = *tp;
 574   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
 575
 576   if (t->base.ann)
 577     {
 578       switch (ann_type (t->base.ann))
 579         {
 580         case STMT_ANN:
 581           {
 582             dfa_stats_p->num_stmt_anns++;
 583             dfa_stats_p->num_defs += NUM_SSA_OPERANDS (t, SSA_OP_DEF);
 584             dfa_stats_p->num_uses += NUM_SSA_OPERANDS (t, SSA_OP_USE);
 585             dfa_stats_p->num_vdefs += NUM_SSA_OPERANDS (t, SSA_OP_VDEF);
 586             dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (t, SSA_OP_VUSE);
 587             break;
 588           }
 589
 590         case VAR_ANN:
 591           dfa_stats_p->num_var_anns++;
 592           break;
 593
 594         default:
 595           break;
 596         }
 597     }
 598
 599   return NULL;
 600 }
 601
 602
 603 /*---------------------------------------------------------------------------
 604                              Miscellaneous helpers
 605 ---------------------------------------------------------------------------*/
 606 /* Callback for walk_tree.  Used to collect variables referenced in
 607    the function.  */
 608
 609 static tree
 610 find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
 611 {
 612   /* If T is a regular variable that the optimizers are interested
 613      in, add it to the list of variables.  */
 614   if (SSA_VAR_P (*tp))
 615     add_referenced_var (*tp);
 616
 617   /* Type, _DECL and constant nodes have no interesting children.
 618      Ignore them.  */
 619   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
 620     *walk_subtrees = 0;
 621
 622   return NULL_TREE;
 623 }
 624
 625 /* Lookup UID in the referenced_vars hashtable and return the associated
 626    variable.  */
 627
 628 tree
 629 referenced_var_lookup (unsigned int uid)
 630 {
 631   tree h;
 632   struct tree_decl_minimal in;
 633   in.uid = uid;
 634   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 635   gcc_assert (h || uid == 0);
 636   return h;
 637 }
 638
 639 /* Check if TO is in the referenced_vars hash table and insert it if not.
 640    Return true if it required insertion.  */
 641
 642 bool
 643 referenced_var_check_and_insert (tree to)
 644 {
 645   tree h, *loc;
 646   struct tree_decl_minimal in;
 647   unsigned int uid = DECL_UID (to);
 648
 649   in.uid = uid;
 650   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 651   if (h)
 652     {
 653       /* DECL_UID has already been entered in the table.  Verify that it is
 654          the same entry as TO.  See PR 27793.  */
 655       gcc_assert (h == to);
 656       return false;
 657     }
 658
 659   loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun),
 660                                            &in, uid, INSERT);
 661   *loc = to;
 662   return true;
 663 }
 664
 665 /* Lookup VAR UID in the default_defs hashtable and return the associated
 666    variable.  */
 667
 668 tree
 669 gimple_default_def (struct function *fn, tree var)
 670 {
 671   struct tree_decl_minimal ind;
 672   struct tree_ssa_name in;
 673   gcc_assert (SSA_VAR_P (var));
 674   in.var = (tree)&ind;
 675   ind.uid = DECL_UID (var);
 676   return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var));
 677 }
 678
 679 /* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
 680
 681 void
 682 set_default_def (tree var, tree def)
 683 {
 684   struct tree_decl_minimal ind;
 685   struct tree_ssa_name in;
 686   void **loc;
 687
 688   gcc_assert (SSA_VAR_P (var));
 689   in.var = (tree)&ind;
 690   ind.uid = DECL_UID (var);
 691   if (!def)
 692     {
 693       loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 694             DECL_UID (var), INSERT);
 695       gcc_assert (*loc);
 696       htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
 697       return;
 698     }
 699   gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
 700   loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 701                                   DECL_UID (var), INSERT);
 702
 703   /* Default definition might be changed by tail call optimization.  */
 704   if (*loc)
 705     SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false;
 706   *(tree *) loc = def;
 707
 708    /* Mark DEF as the default definition for VAR.  */
 709    SSA_NAME_IS_DEFAULT_DEF (def) = true;
 710 }
 711
 712 /* Add VAR to the list of referenced variables if it isn't already there.  */
 713
 714 void
 715 add_referenced_var (tree var)
 716 {
 717   var_ann_t v_ann;
 718
 719   v_ann = get_var_ann (var);
 720   gcc_assert (DECL_P (var));
 721
 722   /* Insert VAR into the referenced_vars has table if it isn't present.  */
 723   if (referenced_var_check_and_insert (var))
 724     {
 725       /* This is the first time we found this variable, annotate it with
 726          attributes that are intrinsic to the variable.  */
 727
 728       /* Tag's don't have DECL_INITIAL.  */
 729       if (MTAG_P (var))
 730         return;
 731
 732       /* Scan DECL_INITIAL for pointer variables as they may contain
 733          address arithmetic referencing the address of other
 734          variables.
 735          Even non-constant intializers need to be walked, because
 736          IPA passes might prove that their are invariant later on.  */
 737       if (DECL_INITIAL (var)
 738           /* Initializers of external variables are not useful to the
 739              optimizers.  */
 740           && !DECL_EXTERNAL (var))
 741         walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
 742     }
 743 }
 744
 745 /* Remove VAR from the list.  */
 746
 747 void
 748 remove_referenced_var (tree var)
 749 {
 750   var_ann_t v_ann;
 751   struct tree_decl_minimal in;
 752   void **loc;
 753   unsigned int uid = DECL_UID (var);
 754
 755   clear_call_clobbered (var);
 756   v_ann = get_var_ann (var);
 757   ggc_free (v_ann);
 758   var->base.ann = NULL;
 759   gcc_assert (DECL_P (var));
 760   in.uid = uid;
 761   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
 762                                   NO_INSERT);
 763   htab_clear_slot (gimple_referenced_vars (cfun), loc);
 764 }
 765
 766
 767 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 768
 769 tree
 770 get_virtual_var (tree var)
 771 {
 772   STRIP_NOPS (var);
 773
 774   if (TREE_CODE (var) == SSA_NAME)
 775     var = SSA_NAME_VAR (var);
 776
 777   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 778          || handled_component_p (var))
 779     var = TREE_OPERAND (var, 0);
 780
 781   /* Treating GIMPLE registers as virtual variables makes no sense.
 782      Also complain if we couldn't extract a _DECL out of the original
 783      expression.  */
 784   gcc_assert (SSA_VAR_P (var));
 785   gcc_assert (!is_gimple_reg (var));
 786
 787   return var;
 788 }
 789
 790 /* Mark all the naked symbols in STMT for SSA renaming.
 791
 792    NOTE: This function should only be used for brand new statements.
 793    If the caller is modifying an existing statement, it should use the
 794    combination push_stmt_changes/pop_stmt_changes.  */
 795
 796 void
 797 mark_symbols_for_renaming (tree stmt)
 798 {
 799   tree op;
 800   ssa_op_iter iter;
 801
 802   update_stmt (stmt);
 803
 804   /* Mark all the operands for renaming.  */
 805   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 806     if (DECL_P (op))
 807       mark_sym_for_renaming (op);
 808 }
 809
 810
 811 /* Find all variables within the gimplified statement that were not previously
 812    visible to the function and add them to the referenced variables list.  */
 813
 814 static tree
 815 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 816                             void *data ATTRIBUTE_UNUSED)
 817 {
 818   tree t = *tp;
 819
 820   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 821     {
 822       add_referenced_var (t);
 823       mark_sym_for_renaming (t);
 824     }
 825
 826   if (IS_TYPE_OR_DECL_P (t))
 827     *walk_subtrees = 0;
 828
 829   return NULL;
 830 }
 831
 832 void
 833 find_new_referenced_vars (tree *stmt_p)
 834 {
 835   walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
 836 }
 837
 838
 839 /* If EXP is a handled component reference for a structure, return the
 840    base variable.  The access range is delimited by bit positions *POFFSET and
 841    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 842    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 843    and *PMAX_SIZE are equal, the access is non-variable.  */
 844
 845 tree
 846 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 847                          HOST_WIDE_INT *psize,
 848                          HOST_WIDE_INT *pmax_size)
 849 {
 850   HOST_WIDE_INT bitsize = -1;
 851   HOST_WIDE_INT maxsize = -1;
 852   tree size_tree = NULL_TREE;
 853   HOST_WIDE_INT bit_offset = 0;
 854   bool seen_variable_array_ref = false;
 855
 856   gcc_assert (!SSA_VAR_P (exp));
 857
 858   /* First get the final access size from just the outermost expression.  */
 859   if (TREE_CODE (exp) == COMPONENT_REF)
 860     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 861   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 862     size_tree = TREE_OPERAND (exp, 1);
 863   else
 864     {
 865       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 866       if (mode == BLKmode)
 867         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 868       else
 869         bitsize = GET_MODE_BITSIZE (mode);
 870     }
 871   if (size_tree != NULL_TREE)
 872     {
 873       if (! host_integerp (size_tree, 1))
 874         bitsize = -1;
 875       else
 876         bitsize = TREE_INT_CST_LOW (size_tree);
 877     }
 878
 879   /* Initially, maxsize is the same as the accessed element size.
 880      In the following it will only grow (or become -1).  */
 881   maxsize = bitsize;
 882
 883   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 884      and find the ultimate containing object.  */
 885   while (1)
 886     {
 887       switch (TREE_CODE (exp))
 888         {
 889         case BIT_FIELD_REF:
 890           bit_offset += tree_low_cst (TREE_OPERAND (exp, 2), 0);
 891           break;
 892
 893         case COMPONENT_REF:
 894           {
 895             tree field = TREE_OPERAND (exp, 1);
 896             tree this_offset = component_ref_field_offset (exp);
 897
 898             if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
 899               {
 900                 HOST_WIDE_INT hthis_offset = tree_low_cst (this_offset, 0);
 901
 902                 hthis_offset *= BITS_PER_UNIT;
 903                 bit_offset += hthis_offset;
 904                 bit_offset += tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 0);
 905               }
 906             else
 907               {
 908                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 909                 /* We need to adjust maxsize to the whole structure bitsize.
 910                    But we can subtract any constant offset seen sofar,
 911                    because that would get us out of the structure otherwise.  */
 912                 if (maxsize != -1 && csize && host_integerp (csize, 1))
 913                   maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
 914                 else
 915                   maxsize = -1;
 916               }
 917           }
 918           break;
 919
 920         case ARRAY_REF:
 921         case ARRAY_RANGE_REF:
 922           {
 923             tree index = TREE_OPERAND (exp, 1);
 924             tree low_bound = array_ref_low_bound (exp);
 925             tree unit_size = array_ref_element_size (exp);
 926
 927             /* If the resulting bit-offset is constant, track it.  */
 928             if (host_integerp (index, 0)
 929                 && host_integerp (low_bound, 0)
 930                 && host_integerp (unit_size, 1))
 931               {
 932                 HOST_WIDE_INT hindex = tree_low_cst (index, 0);
 933
 934                 hindex -= tree_low_cst (low_bound, 0);
 935                 hindex *= tree_low_cst (unit_size, 1);
 936                 hindex *= BITS_PER_UNIT;
 937                 bit_offset += hindex;
 938
 939                 /* An array ref with a constant index up in the structure
 940                    hierarchy will constrain the size of any variable array ref
 941                    lower in the access hierarchy.  */
 942                 seen_variable_array_ref = false;
 943               }
 944             else
 945               {
 946                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 947                 /* We need to adjust maxsize to the whole array bitsize.
 948                    But we can subtract any constant offset seen sofar,
 949                    because that would get us outside of the array otherwise.  */
 950                 if (maxsize != -1 && asize && host_integerp (asize, 1))
 951                   maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
 952                 else
 953                   maxsize = -1;
 954
 955                 /* Remember that we have seen an array ref with a variable
 956                    index.  */
 957                 seen_variable_array_ref = true;
 958               }
 959           }
 960           break;
 961
 962         case REALPART_EXPR:
 963           break;
 964
 965         case IMAGPART_EXPR:
 966           bit_offset += bitsize;
 967           break;
 968
 969         case VIEW_CONVERT_EXPR:
 970           /* ???  We probably should give up here and bail out.  */
 971           break;
 972
 973         default:
 974           goto done;
 975         }
 976
 977       exp = TREE_OPERAND (exp, 0);
 978     }
 979  done:
 980
 981   /* We need to deal with variable arrays ending structures such as
 982        struct { int length; int a[1]; } x;           x.a[d]
 983        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 984        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 985      where we do not know maxsize for variable index accesses to
 986      the array.  The simplest way to conservatively deal with this
 987      is to punt in the case that offset + maxsize reaches the
 988      base type boundary.  */
 989   if (seen_variable_array_ref
 990       && maxsize != -1
 991       && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
 992       && bit_offset + maxsize
 993            == (signed)TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))
 994     maxsize = -1;
 995
 996   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 997      negative bit_offset here.  We might want to store a zero offset
 998      in this case.  */
 999   *poffset = bit_offset;
1000   *psize = bitsize;
1001   *pmax_size = maxsize;
1002
1003   return exp;
1004 }
1005