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