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