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, "@" HOST_WIDE_INT_PRINT_UNSIGNED " ", SFT_OFFSET (subvar));
 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   subvar_t sv;
 755
 756   /* If we remove a var, we should also remove its subvars, as we kill
 757      their parent var and its annotation.  */
 758   if (var_can_have_subvars (var)
 759       && (sv = get_subvars_for_var (var)))
 760     {
 761       unsigned int i;
 762       tree subvar;
 763       for (i = 0; VEC_iterate (tree, sv, i, subvar); ++i)
 764         remove_referenced_var (subvar);
 765     }
 766
 767   clear_call_clobbered (var);
 768   if ((v_ann = var_ann (var)))
 769     ggc_free (v_ann);
 770   var->base.ann = NULL;
 771   gcc_assert (DECL_P (var));
 772   in.uid = uid;
 773   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
 774                                   NO_INSERT);
 775   htab_clear_slot (gimple_referenced_vars (cfun), loc);
 776 }
 777
 778
 779 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 780
 781 tree
 782 get_virtual_var (tree var)
 783 {
 784   STRIP_NOPS (var);
 785
 786   if (TREE_CODE (var) == SSA_NAME)
 787     var = SSA_NAME_VAR (var);
 788
 789   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 790          || handled_component_p (var))
 791     var = TREE_OPERAND (var, 0);
 792
 793   /* Treating GIMPLE registers as virtual variables makes no sense.
 794      Also complain if we couldn't extract a _DECL out of the original
 795      expression.  */
 796   gcc_assert (SSA_VAR_P (var));
 797   gcc_assert (!is_gimple_reg (var));
 798
 799   return var;
 800 }
 801
 802 /* Mark all the naked symbols in STMT for SSA renaming.
 803
 804    NOTE: This function should only be used for brand new statements.
 805    If the caller is modifying an existing statement, it should use the
 806    combination push_stmt_changes/pop_stmt_changes.  */
 807
 808 void
 809 mark_symbols_for_renaming (tree stmt)
 810 {
 811   tree op;
 812   ssa_op_iter iter;
 813
 814   update_stmt (stmt);
 815
 816   /* Mark all the operands for renaming.  */
 817   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 818     if (DECL_P (op))
 819       mark_sym_for_renaming (op);
 820 }
 821
 822
 823 /* Find all variables within the gimplified statement that were not previously
 824    visible to the function and add them to the referenced variables list.  */
 825
 826 static tree
 827 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 828                             void *data ATTRIBUTE_UNUSED)
 829 {
 830   tree t = *tp;
 831
 832   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 833     {
 834       add_referenced_var (t);
 835       mark_sym_for_renaming (t);
 836     }
 837
 838   if (IS_TYPE_OR_DECL_P (t))
 839     *walk_subtrees = 0;
 840
 841   return NULL;
 842 }
 843
 844 void
 845 find_new_referenced_vars (tree *stmt_p)
 846 {
 847   walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
 848 }
 849
 850
 851 /* If EXP is a handled component reference for a structure, return the
 852    base variable.  The access range is delimited by bit positions *POFFSET and
 853    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 854    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 855    and *PMAX_SIZE are equal, the access is non-variable.  */
 856
 857 tree
 858 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 859                          HOST_WIDE_INT *psize,
 860                          HOST_WIDE_INT *pmax_size)
 861 {
 862   HOST_WIDE_INT bitsize = -1;
 863   HOST_WIDE_INT maxsize = -1;
 864   tree size_tree = NULL_TREE;
 865   HOST_WIDE_INT bit_offset = 0;
 866   bool seen_variable_array_ref = false;
 867
 868   gcc_assert (!SSA_VAR_P (exp));
 869
 870   /* First get the final access size from just the outermost expression.  */
 871   if (TREE_CODE (exp) == COMPONENT_REF)
 872     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 873   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 874     size_tree = TREE_OPERAND (exp, 1);
 875   else
 876     {
 877       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 878       if (mode == BLKmode)
 879         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 880       else
 881         bitsize = GET_MODE_BITSIZE (mode);
 882     }
 883   if (size_tree != NULL_TREE)
 884     {
 885       if (! host_integerp (size_tree, 1))
 886         bitsize = -1;
 887       else
 888         bitsize = TREE_INT_CST_LOW (size_tree);
 889     }
 890
 891   /* Initially, maxsize is the same as the accessed element size.
 892      In the following it will only grow (or become -1).  */
 893   maxsize = bitsize;
 894
 895   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 896      and find the ultimate containing object.  */
 897   while (1)
 898     {
 899       switch (TREE_CODE (exp))
 900         {
 901         case BIT_FIELD_REF:
 902           bit_offset += tree_low_cst (TREE_OPERAND (exp, 2), 0);
 903           break;
 904
 905         case COMPONENT_REF:
 906           {
 907             tree field = TREE_OPERAND (exp, 1);
 908             tree this_offset = component_ref_field_offset (exp);
 909
 910             if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
 911               {
 912                 HOST_WIDE_INT hthis_offset = tree_low_cst (this_offset, 0);
 913
 914                 hthis_offset *= BITS_PER_UNIT;
 915                 bit_offset += hthis_offset;
 916                 bit_offset += tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 0);
 917               }
 918             else
 919               {
 920                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 921                 /* We need to adjust maxsize to the whole structure bitsize.
 922                    But we can subtract any constant offset seen sofar,
 923                    because that would get us out of the structure otherwise.  */
 924                 if (maxsize != -1 && csize && host_integerp (csize, 1))
 925                   maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
 926                 else
 927                   maxsize = -1;
 928               }
 929           }
 930           break;
 931
 932         case ARRAY_REF:
 933         case ARRAY_RANGE_REF:
 934           {
 935             tree index = TREE_OPERAND (exp, 1);
 936             tree low_bound = array_ref_low_bound (exp);
 937             tree unit_size = array_ref_element_size (exp);
 938
 939             /* If the resulting bit-offset is constant, track it.  */
 940             if (host_integerp (index, 0)
 941                 && host_integerp (low_bound, 0)
 942                 && host_integerp (unit_size, 1))
 943               {
 944                 HOST_WIDE_INT hindex = tree_low_cst (index, 0);
 945
 946                 hindex -= tree_low_cst (low_bound, 0);
 947                 hindex *= tree_low_cst (unit_size, 1);
 948                 hindex *= BITS_PER_UNIT;
 949                 bit_offset += hindex;
 950
 951                 /* An array ref with a constant index up in the structure
 952                    hierarchy will constrain the size of any variable array ref
 953                    lower in the access hierarchy.  */
 954                 seen_variable_array_ref = false;
 955               }
 956             else
 957               {
 958                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 959                 /* We need to adjust maxsize to the whole array bitsize.
 960                    But we can subtract any constant offset seen sofar,
 961                    because that would get us outside of the array otherwise.  */
 962                 if (maxsize != -1 && asize && host_integerp (asize, 1))
 963                   maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
 964                 else
 965                   maxsize = -1;
 966
 967                 /* Remember that we have seen an array ref with a variable
 968                    index.  */
 969                 seen_variable_array_ref = true;
 970               }
 971           }
 972           break;
 973
 974         case REALPART_EXPR:
 975           break;
 976
 977         case IMAGPART_EXPR:
 978           bit_offset += bitsize;
 979           break;
 980
 981         case VIEW_CONVERT_EXPR:
 982           /* ???  We probably should give up here and bail out.  */
 983           break;
 984
 985         default:
 986           goto done;
 987         }
 988
 989       exp = TREE_OPERAND (exp, 0);
 990     }
 991  done:
 992
 993   /* We need to deal with variable arrays ending structures such as
 994        struct { int length; int a[1]; } x;           x.a[d]
 995        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 996        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 997      where we do not know maxsize for variable index accesses to
 998      the array.  The simplest way to conservatively deal with this
 999      is to punt in the case that offset + maxsize reaches the
1000      base type boundary.  */
1001   if (seen_variable_array_ref
1002       && maxsize != -1
1003       && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
1004       && bit_offset + maxsize
1005            == (signed)TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))
1006     maxsize = -1;
1007
1008   /* ???  Due to negative offsets in ARRAY_REF we can end up with
1009      negative bit_offset here.  We might want to store a zero offset
1010      in this case.  */
1011   *poffset = bit_offset;
1012   *psize = bitsize;
1013   *pmax_size = maxsize;
1014
1015   return exp;
1016 }
1017