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