gcc/tree-dfa.c

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