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 gimple_opt_pass pass_referenced_vars =
 100 {
 101  {
 102   GIMPLE_PASS,
 103   NULL,                                 /* name */
 104   NULL,                                 /* gate */
 105   find_referenced_vars,                 /* execute */
 106   NULL,                                 /* sub */
 107   NULL,                                 /* next */
 108   0,                                    /* static_pass_number */
 109   TV_FIND_REFERENCED_VARS,              /* tv_id */
 110   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 111   PROP_referenced_vars,                 /* properties_provided */
 112   0,                                    /* properties_destroyed */
 113   0,                                    /* todo_flags_start */
 114   0                                     /* todo_flags_finish */
 115  }
 116 };
 117
 118
 119 /*---------------------------------------------------------------------------
 120                             Manage annotations
 121 ---------------------------------------------------------------------------*/
 122 /* Create a new annotation for a _DECL node T.  */
 123
 124 var_ann_t
 125 create_var_ann (tree t)
 126 {
 127   var_ann_t ann;
 128   struct static_var_ann_d *sann = NULL;
 129
 130   gcc_assert (t);
 131   gcc_assert (DECL_P (t));
 132   gcc_assert (!t->base.ann || t->base.ann->common.type == VAR_ANN);
 133
 134   if (!MTAG_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
 135     {
 136       sann = GGC_CNEW (struct static_var_ann_d);
 137       ann = &sann->ann;
 138     }
 139   else
 140     ann = GGC_CNEW (struct var_ann_d);
 141
 142   ann->common.type = VAR_ANN;
 143
 144   if (!MTAG_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
 145     {
 146        void **slot;
 147        sann->uid = DECL_UID (t);
 148        slot = htab_find_slot_with_hash (gimple_var_anns (cfun),
 149                                         t, DECL_UID (t), INSERT);
 150        gcc_assert (!*slot);
 151        *slot = sann;
 152     }
 153   else
 154     t->base.ann = (tree_ann_t) ann;
 155
 156   return ann;
 157 }
 158
 159 /* Create a new annotation for a FUNCTION_DECL node T.  */
 160
 161 function_ann_t
 162 create_function_ann (tree t)
 163 {
 164   function_ann_t ann;
 165
 166   gcc_assert (t);
 167   gcc_assert (TREE_CODE (t) == FUNCTION_DECL);
 168   gcc_assert (!t->base.ann || t->base.ann->common.type == FUNCTION_ANN);
 169
 170   ann = ggc_alloc (sizeof (*ann));
 171   memset ((void *) ann, 0, sizeof (*ann));
 172
 173   ann->common.type = FUNCTION_ANN;
 174
 175   t->base.ann = (tree_ann_t) ann;
 176
 177   return ann;
 178 }
 179
 180 /* Create a new annotation for a statement node T.  */
 181
 182 stmt_ann_t
 183 create_stmt_ann (tree t)
 184 {
 185   stmt_ann_t ann;
 186
 187   gcc_assert (is_gimple_stmt (t));
 188   gcc_assert (!t->base.ann || t->base.ann->common.type == STMT_ANN);
 189
 190   ann = GGC_CNEW (struct stmt_ann_d);
 191
 192   ann->common.type = STMT_ANN;
 193
 194   /* Since we just created the annotation, mark the statement modified.  */
 195   ann->modified = true;
 196
 197   t->base.ann = (tree_ann_t) ann;
 198
 199   return ann;
 200 }
 201
 202 /* Create a new annotation for a tree T.  */
 203
 204 tree_ann_common_t
 205 create_tree_common_ann (tree t)
 206 {
 207   tree_ann_common_t ann;
 208
 209   gcc_assert (t);
 210   gcc_assert (!t->base.ann || t->base.ann->common.type == TREE_ANN_COMMON);
 211
 212   ann = GGC_CNEW (struct tree_ann_common_d);
 213
 214   ann->type = TREE_ANN_COMMON;
 215   t->base.ann = (tree_ann_t) ann;
 216
 217   return ann;
 218 }
 219
 220 /* Build a temporary.  Make sure and register it to be renamed.  */
 221
 222 tree
 223 make_rename_temp (tree type, const char *prefix)
 224 {
 225   tree t = create_tmp_var (type, prefix);
 226
 227   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 228       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 229     DECL_GIMPLE_REG_P (t) = 1;
 230
 231   if (gimple_referenced_vars (cfun))
 232     {
 233       add_referenced_var (t);
 234       mark_sym_for_renaming (t);
 235     }
 236
 237   return t;
 238 }
 239
 240
 241
 242 /*---------------------------------------------------------------------------
 243                               Debugging functions
 244 ---------------------------------------------------------------------------*/
 245 /* Dump the list of all the referenced variables in the current function to
 246    FILE.  */
 247
 248 void
 249 dump_referenced_vars (FILE *file)
 250 {
 251   tree var;
 252   referenced_var_iterator rvi;
 253
 254   fprintf (file, "\nReferenced variables in %s: %u\n\n",
 255            get_name (current_function_decl), (unsigned) num_referenced_vars);
 256
 257   FOR_EACH_REFERENCED_VAR (var, rvi)
 258     {
 259       fprintf (file, "Variable: ");
 260       dump_variable (file, var);
 261       fprintf (file, "\n");
 262     }
 263 }
 264
 265
 266 /* Dump the list of all the referenced variables to stderr.  */
 267
 268 void
 269 debug_referenced_vars (void)
 270 {
 271   dump_referenced_vars (stderr);
 272 }
 273
 274
 275 /* Dump variable VAR and its may-aliases to FILE.  */
 276
 277 void
 278 dump_variable (FILE *file, tree var)
 279 {
 280   var_ann_t ann;
 281
 282   if (TREE_CODE (var) == SSA_NAME)
 283     {
 284       if (POINTER_TYPE_P (TREE_TYPE (var)))
 285         dump_points_to_info_for (file, var);
 286       var = SSA_NAME_VAR (var);
 287     }
 288
 289   if (var == NULL_TREE)
 290     {
 291       fprintf (file, "<nil>");
 292       return;
 293     }
 294
 295   print_generic_expr (file, var, dump_flags);
 296
 297   ann = var_ann (var);
 298
 299   fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
 300
 301   fprintf (file, ", ");
 302   print_generic_expr (file, TREE_TYPE (var), dump_flags);
 303
 304   if (ann && ann->symbol_mem_tag)
 305     {
 306       fprintf (file, ", symbol memory tag: ");
 307       print_generic_expr (file, ann->symbol_mem_tag, dump_flags);
 308     }
 309
 310   if (TREE_ADDRESSABLE (var))
 311     fprintf (file, ", is addressable");
 312
 313   if (is_global_var (var))
 314     fprintf (file, ", is global");
 315
 316   if (TREE_THIS_VOLATILE (var))
 317     fprintf (file, ", is volatile");
 318
 319   dump_mem_sym_stats_for_var (file, var);
 320
 321   if (is_call_clobbered (var))
 322     {
 323       const char *s = "";
 324       var_ann_t va = var_ann (var);
 325       unsigned int escape_mask = va->escape_mask;
 326
 327       fprintf (file, ", call clobbered");
 328       fprintf (file, " (");
 329       if (escape_mask & ESCAPE_STORED_IN_GLOBAL)
 330         { fprintf (file, "%sstored in global", s); s = ", "; }
 331       if (escape_mask & ESCAPE_TO_ASM)
 332         { fprintf (file, "%sgoes through ASM", s); s = ", "; }
 333       if (escape_mask & ESCAPE_TO_CALL)
 334         { fprintf (file, "%spassed to call", s); s = ", "; }
 335       if (escape_mask & ESCAPE_BAD_CAST)
 336         { fprintf (file, "%sbad cast", s); s = ", "; }
 337       if (escape_mask & ESCAPE_TO_RETURN)
 338         { fprintf (file, "%sreturned from func", s); s = ", "; }
 339       if (escape_mask & ESCAPE_TO_PURE_CONST)
 340         { fprintf (file, "%spassed to pure/const", s); s = ", "; }
 341       if (escape_mask & ESCAPE_IS_GLOBAL)
 342         { fprintf (file, "%sis global var", s); s = ", "; }
 343       if (escape_mask & ESCAPE_IS_PARM)
 344         { fprintf (file, "%sis incoming pointer", s); s = ", "; }
 345       if (escape_mask & ESCAPE_UNKNOWN)
 346         { fprintf (file, "%sunknown escape", s); s = ", "; }
 347       fprintf (file, ")");
 348     }
 349
 350   if (ann->noalias_state == NO_ALIAS)
 351     fprintf (file, ", NO_ALIAS (does not alias other NO_ALIAS symbols)");
 352   else if (ann->noalias_state == NO_ALIAS_GLOBAL)
 353     fprintf (file, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols"
 354                    " and global vars)");
 355   else if (ann->noalias_state == NO_ALIAS_ANYTHING)
 356     fprintf (file, ", NO_ALIAS_ANYTHING (does not alias any other symbols)");
 357
 358   if (gimple_default_def (cfun, var))
 359     {
 360       fprintf (file, ", default def: ");
 361       print_generic_expr (file, gimple_default_def (cfun, var), dump_flags);
 362     }
 363
 364   if (MTAG_P (var) && may_aliases (var))
 365     {
 366       fprintf (file, ", may aliases: ");
 367       dump_may_aliases_for (file, var);
 368     }
 369
 370   if (!is_gimple_reg (var))
 371     {
 372       if (memory_partition (var))
 373         {
 374           fprintf (file, ", belongs to partition: ");
 375           print_generic_expr (file, memory_partition (var), dump_flags);
 376         }
 377
 378       if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
 379         {
 380           fprintf (file, ", partition symbols: ");
 381           dump_decl_set (file, MPT_SYMBOLS (var));
 382         }
 383     }
 384
 385   fprintf (file, "\n");
 386 }
 387
 388
 389 /* Dump variable VAR and its may-aliases to stderr.  */
 390
 391 void
 392 debug_variable (tree var)
 393 {
 394   dump_variable (stderr, var);
 395 }
 396
 397
 398 /* Dump various DFA statistics to FILE.  */
 399
 400 void
 401 dump_dfa_stats (FILE *file)
 402 {
 403   struct dfa_stats_d dfa_stats;
 404
 405   unsigned long size, total = 0;
 406   const char * const fmt_str   = "%-30s%-13s%12s\n";
 407   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 408   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 409   const char *funcname
 410     = lang_hooks.decl_printable_name (current_function_decl, 2);
 411
 412   collect_dfa_stats (&dfa_stats);
 413
 414   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 415
 416   fprintf (file, "---------------------------------------------------------\n");
 417   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 418   fprintf (file, fmt_str, "", "  instances  ", "used ");
 419   fprintf (file, "---------------------------------------------------------\n");
 420
 421   size = num_referenced_vars * sizeof (tree);
 422   total += size;
 423   fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
 424            SCALE (size), LABEL (size));
 425
 426   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
 427   total += size;
 428   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
 429            SCALE (size), LABEL (size));
 430
 431   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 432   total += size;
 433   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 434            SCALE (size), LABEL (size));
 435
 436   size = dfa_stats.num_uses * sizeof (tree *);
 437   total += size;
 438   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 439            SCALE (size), LABEL (size));
 440
 441   size = dfa_stats.num_defs * sizeof (tree *);
 442   total += size;
 443   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 444            SCALE (size), LABEL (size));
 445
 446   size = dfa_stats.num_vuses * sizeof (tree *);
 447   total += size;
 448   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 449            SCALE (size), LABEL (size));
 450
 451   size = dfa_stats.num_vdefs * sizeof (tree *);
 452   total += size;
 453   fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
 454            SCALE (size), LABEL (size));
 455
 456   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
 457   total += size;
 458   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 459            SCALE (size), LABEL (size));
 460
 461   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 462   total += size;
 463   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 464            SCALE (size), LABEL (size));
 465
 466   fprintf (file, "---------------------------------------------------------\n");
 467   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 468            LABEL (total));
 469   fprintf (file, "---------------------------------------------------------\n");
 470   fprintf (file, "\n");
 471
 472   if (dfa_stats.num_phis)
 473     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
 474              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 475              dfa_stats.max_num_phi_args);
 476
 477   fprintf (file, "\n");
 478 }
 479
 480
 481 /* Dump DFA statistics on stderr.  */
 482
 483 void
 484 debug_dfa_stats (void)
 485 {
 486   dump_dfa_stats (stderr);
 487 }
 488
 489
 490 /* Collect DFA statistics and store them in the structure pointed to by
 491    DFA_STATS_P.  */
 492
 493 static void
 494 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
 495 {
 496   struct pointer_set_t *pset;
 497   basic_block bb;
 498   block_stmt_iterator i;
 499
 500   gcc_assert (dfa_stats_p);
 501
 502   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 503
 504   /* Walk all the trees in the function counting references.  Start at
 505      basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries.  */
 506   pset = pointer_set_create ();
 507
 508   for (i = bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
 509        !bsi_end_p (i); bsi_next (&i))
 510     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
 511                pset);
 512
 513   pointer_set_destroy (pset);
 514
 515   FOR_EACH_BB (bb)
 516     {
 517       tree phi;
 518       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 519         {
 520           dfa_stats_p->num_phis++;
 521           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
 522           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
 523             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
 524         }
 525     }
 526 }
 527
 528
 529 /* Callback for walk_tree to collect DFA statistics for a tree and its
 530    children.  */
 531
 532 static tree
 533 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
 534                      void *data)
 535 {
 536   tree t = *tp;
 537   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
 538
 539   if (t->base.ann)
 540     {
 541       switch (ann_type (t->base.ann))
 542         {
 543         case STMT_ANN:
 544           {
 545             dfa_stats_p->num_stmt_anns++;
 546             dfa_stats_p->num_defs += NUM_SSA_OPERANDS (t, SSA_OP_DEF);
 547             dfa_stats_p->num_uses += NUM_SSA_OPERANDS (t, SSA_OP_USE);
 548             dfa_stats_p->num_vdefs += NUM_SSA_OPERANDS (t, SSA_OP_VDEF);
 549             dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (t, SSA_OP_VUSE);
 550             break;
 551           }
 552
 553         case VAR_ANN:
 554           dfa_stats_p->num_var_anns++;
 555           break;
 556
 557         default:
 558           break;
 559         }
 560     }
 561
 562   return NULL;
 563 }
 564
 565
 566 /*---------------------------------------------------------------------------
 567                              Miscellaneous helpers
 568 ---------------------------------------------------------------------------*/
 569 /* Callback for walk_tree.  Used to collect variables referenced in
 570    the function.  */
 571
 572 static tree
 573 find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
 574 {
 575   /* If T is a regular variable that the optimizers are interested
 576      in, add it to the list of variables.  */
 577   if (SSA_VAR_P (*tp))
 578     add_referenced_var (*tp);
 579
 580   /* Type, _DECL and constant nodes have no interesting children.
 581      Ignore them.  */
 582   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
 583     *walk_subtrees = 0;
 584
 585   return NULL_TREE;
 586 }
 587
 588 /* Lookup UID in the referenced_vars hashtable and return the associated
 589    variable.  */
 590
 591 tree
 592 referenced_var_lookup (unsigned int uid)
 593 {
 594   tree h;
 595   struct tree_decl_minimal in;
 596   in.uid = uid;
 597   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 598   gcc_assert (h || uid == 0);
 599   return h;
 600 }
 601
 602 /* Check if TO is in the referenced_vars hash table and insert it if not.
 603    Return true if it required insertion.  */
 604
 605 bool
 606 referenced_var_check_and_insert (tree to)
 607 {
 608   tree h, *loc;
 609   struct tree_decl_minimal in;
 610   unsigned int uid = DECL_UID (to);
 611
 612   in.uid = uid;
 613   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 614   if (h)
 615     {
 616       /* DECL_UID has already been entered in the table.  Verify that it is
 617          the same entry as TO.  See PR 27793.  */
 618       gcc_assert (h == to);
 619       return false;
 620     }
 621
 622   loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun),
 623                                            &in, uid, INSERT);
 624   *loc = to;
 625   return true;
 626 }
 627
 628 /* Lookup VAR UID in the default_defs hashtable and return the associated
 629    variable.  */
 630
 631 tree
 632 gimple_default_def (struct function *fn, tree var)
 633 {
 634   struct tree_decl_minimal ind;
 635   struct tree_ssa_name in;
 636   gcc_assert (SSA_VAR_P (var));
 637   in.var = (tree)&ind;
 638   ind.uid = DECL_UID (var);
 639   return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var));
 640 }
 641
 642 /* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
 643
 644 void
 645 set_default_def (tree var, tree def)
 646 {
 647   struct tree_decl_minimal ind;
 648   struct tree_ssa_name in;
 649   void **loc;
 650
 651   gcc_assert (SSA_VAR_P (var));
 652   in.var = (tree)&ind;
 653   ind.uid = DECL_UID (var);
 654   if (!def)
 655     {
 656       loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 657             DECL_UID (var), INSERT);
 658       gcc_assert (*loc);
 659       htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
 660       return;
 661     }
 662   gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
 663   loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 664                                   DECL_UID (var), INSERT);
 665
 666   /* Default definition might be changed by tail call optimization.  */
 667   if (*loc)
 668     SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false;
 669   *(tree *) loc = def;
 670
 671    /* Mark DEF as the default definition for VAR.  */
 672    SSA_NAME_IS_DEFAULT_DEF (def) = true;
 673 }
 674
 675 /* Add VAR to the list of referenced variables if it isn't already there.  */
 676
 677 void
 678 add_referenced_var (tree var)
 679 {
 680   var_ann_t v_ann;
 681
 682   v_ann = get_var_ann (var);
 683   gcc_assert (DECL_P (var));
 684
 685   /* Insert VAR into the referenced_vars has table if it isn't present.  */
 686   if (referenced_var_check_and_insert (var))
 687     {
 688       /* This is the first time we found this variable, annotate it with
 689          attributes that are intrinsic to the variable.  */
 690
 691       /* Tag's don't have DECL_INITIAL.  */
 692       if (MTAG_P (var))
 693         return;
 694
 695       /* Scan DECL_INITIAL for pointer variables as they may contain
 696          address arithmetic referencing the address of other
 697          variables.
 698          Even non-constant intializers need to be walked, because
 699          IPA passes might prove that their are invariant later on.  */
 700       if (DECL_INITIAL (var)
 701           /* Initializers of external variables are not useful to the
 702              optimizers.  */
 703           && !DECL_EXTERNAL (var))
 704         walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
 705     }
 706 }
 707
 708 /* Remove VAR from the list.  */
 709
 710 void
 711 remove_referenced_var (tree var)
 712 {
 713   var_ann_t v_ann;
 714   struct tree_decl_minimal in;
 715   void **loc;
 716   unsigned int uid = DECL_UID (var);
 717
 718   clear_call_clobbered (var);
 719   if ((v_ann = var_ann (var)))
 720     ggc_free (v_ann);
 721   var->base.ann = NULL;
 722   gcc_assert (DECL_P (var));
 723   in.uid = uid;
 724   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
 725                                   NO_INSERT);
 726   htab_clear_slot (gimple_referenced_vars (cfun), loc);
 727 }
 728
 729
 730 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 731
 732 tree
 733 get_virtual_var (tree var)
 734 {
 735   STRIP_NOPS (var);
 736
 737   if (TREE_CODE (var) == SSA_NAME)
 738     var = SSA_NAME_VAR (var);
 739
 740   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 741          || handled_component_p (var))
 742     var = TREE_OPERAND (var, 0);
 743
 744   /* Treating GIMPLE registers as virtual variables makes no sense.
 745      Also complain if we couldn't extract a _DECL out of the original
 746      expression.  */
 747   gcc_assert (SSA_VAR_P (var));
 748   gcc_assert (!is_gimple_reg (var));
 749
 750   return var;
 751 }
 752
 753 /* Mark all the naked symbols in STMT for SSA renaming.
 754
 755    NOTE: This function should only be used for brand new statements.
 756    If the caller is modifying an existing statement, it should use the
 757    combination push_stmt_changes/pop_stmt_changes.  */
 758
 759 void
 760 mark_symbols_for_renaming (tree stmt)
 761 {
 762   tree op;
 763   ssa_op_iter iter;
 764
 765   update_stmt (stmt);
 766
 767   /* Mark all the operands for renaming.  */
 768   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 769     if (DECL_P (op))
 770       mark_sym_for_renaming (op);
 771 }
 772
 773
 774 /* Find all variables within the gimplified statement that were not previously
 775    visible to the function and add them to the referenced variables list.  */
 776
 777 static tree
 778 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 779                             void *data ATTRIBUTE_UNUSED)
 780 {
 781   tree t = *tp;
 782
 783   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 784     {
 785       add_referenced_var (t);
 786       mark_sym_for_renaming (t);
 787     }
 788
 789   if (IS_TYPE_OR_DECL_P (t))
 790     *walk_subtrees = 0;
 791
 792   return NULL;
 793 }
 794
 795 void
 796 find_new_referenced_vars (tree *stmt_p)
 797 {
 798   walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
 799 }
 800
 801
 802 /* If EXP is a handled component reference for a structure, return the
 803    base variable.  The access range is delimited by bit positions *POFFSET and
 804    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 805    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 806    and *PMAX_SIZE are equal, the access is non-variable.  */
 807
 808 tree
 809 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 810                          HOST_WIDE_INT *psize,
 811                          HOST_WIDE_INT *pmax_size)
 812 {
 813   HOST_WIDE_INT bitsize = -1;
 814   HOST_WIDE_INT maxsize = -1;
 815   tree size_tree = NULL_TREE;
 816   HOST_WIDE_INT bit_offset = 0;
 817   bool seen_variable_array_ref = false;
 818
 819   gcc_assert (!SSA_VAR_P (exp));
 820
 821   /* First get the final access size from just the outermost expression.  */
 822   if (TREE_CODE (exp) == COMPONENT_REF)
 823     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 824   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 825     size_tree = TREE_OPERAND (exp, 1);
 826   else
 827     {
 828       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 829       if (mode == BLKmode)
 830         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 831       else
 832         bitsize = GET_MODE_BITSIZE (mode);
 833     }
 834   if (size_tree != NULL_TREE)
 835     {
 836       if (! host_integerp (size_tree, 1))
 837         bitsize = -1;
 838       else
 839         bitsize = TREE_INT_CST_LOW (size_tree);
 840     }
 841
 842   /* Initially, maxsize is the same as the accessed element size.
 843      In the following it will only grow (or become -1).  */
 844   maxsize = bitsize;
 845
 846   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 847      and find the ultimate containing object.  */
 848   while (1)
 849     {
 850       switch (TREE_CODE (exp))
 851         {
 852         case BIT_FIELD_REF:
 853           bit_offset += tree_low_cst (TREE_OPERAND (exp, 2), 0);
 854           break;
 855
 856         case COMPONENT_REF:
 857           {
 858             tree field = TREE_OPERAND (exp, 1);
 859             tree this_offset = component_ref_field_offset (exp);
 860
 861             if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
 862               {
 863                 HOST_WIDE_INT hthis_offset = tree_low_cst (this_offset, 0);
 864
 865                 hthis_offset *= BITS_PER_UNIT;
 866                 bit_offset += hthis_offset;
 867                 bit_offset += tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 0);
 868               }
 869             else
 870               {
 871                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 872                 /* We need to adjust maxsize to the whole structure bitsize.
 873                    But we can subtract any constant offset seen sofar,
 874                    because that would get us out of the structure otherwise.  */
 875                 if (maxsize != -1 && csize && host_integerp (csize, 1))
 876                   maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
 877                 else
 878                   maxsize = -1;
 879               }
 880           }
 881           break;
 882
 883         case ARRAY_REF:
 884         case ARRAY_RANGE_REF:
 885           {
 886             tree index = TREE_OPERAND (exp, 1);
 887             tree low_bound = array_ref_low_bound (exp);
 888             tree unit_size = array_ref_element_size (exp);
 889
 890             /* If the resulting bit-offset is constant, track it.  */
 891             if (host_integerp (index, 0)
 892                 && host_integerp (low_bound, 0)
 893                 && host_integerp (unit_size, 1))
 894               {
 895                 HOST_WIDE_INT hindex = tree_low_cst (index, 0);
 896
 897                 hindex -= tree_low_cst (low_bound, 0);
 898                 hindex *= tree_low_cst (unit_size, 1);
 899                 hindex *= BITS_PER_UNIT;
 900                 bit_offset += hindex;
 901
 902                 /* An array ref with a constant index up in the structure
 903                    hierarchy will constrain the size of any variable array ref
 904                    lower in the access hierarchy.  */
 905                 seen_variable_array_ref = false;
 906               }
 907             else
 908               {
 909                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 910                 /* We need to adjust maxsize to the whole array bitsize.
 911                    But we can subtract any constant offset seen sofar,
 912                    because that would get us outside of the array otherwise.  */
 913                 if (maxsize != -1 && asize && host_integerp (asize, 1))
 914                   maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
 915                 else
 916                   maxsize = -1;
 917
 918                 /* Remember that we have seen an array ref with a variable
 919                    index.  */
 920                 seen_variable_array_ref = true;
 921               }
 922           }
 923           break;
 924
 925         case REALPART_EXPR:
 926           break;
 927
 928         case IMAGPART_EXPR:
 929           bit_offset += bitsize;
 930           break;
 931
 932         case VIEW_CONVERT_EXPR:
 933           /* ???  We probably should give up here and bail out.  */
 934           break;
 935
 936         default:
 937           goto done;
 938         }
 939
 940       exp = TREE_OPERAND (exp, 0);
 941     }
 942  done:
 943
 944   /* We need to deal with variable arrays ending structures such as
 945        struct { int length; int a[1]; } x;           x.a[d]
 946        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 947        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 948      where we do not know maxsize for variable index accesses to
 949      the array.  The simplest way to conservatively deal with this
 950      is to punt in the case that offset + maxsize reaches the
 951      base type boundary.  */
 952   if (seen_variable_array_ref
 953       && maxsize != -1
 954       && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
 955       && bit_offset + maxsize
 956            == (signed)TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))
 957     maxsize = -1;
 958
 959   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 960      negative bit_offset here.  We might want to store a zero offset
 961      in this case.  */
 962   *poffset = bit_offset;
 963   *psize = bitsize;
 964   *pmax_size = maxsize;
 965
 966   return exp;
 967 }
 968
 969 /* Returns true if STMT references an SSA_NAME that has
 970    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
 971
 972 bool
 973 stmt_references_abnormal_ssa_name (tree stmt)
 974 {
 975   ssa_op_iter oi;
 976   use_operand_p use_p;
 977
 978   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
 979     {
 980       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
 981         return true;
 982     }
 983
 984   return false;
 985 }
 986
 987 /* Return true, if the two memory references REF1 and REF2 may alias.  */
 988
 989 bool
 990 refs_may_alias_p (tree ref1, tree ref2)
 991 {
 992   tree base1, base2;
 993   HOST_WIDE_INT offset1 = 0, offset2 = 0;
 994   HOST_WIDE_INT size1 = -1, size2 = -1;
 995   HOST_WIDE_INT max_size1 = -1, max_size2 = -1;
 996
 997   gcc_assert ((SSA_VAR_P (ref1)
 998                || handled_component_p (ref1)
 999                || INDIRECT_REF_P (ref1)
1000                || TREE_CODE (ref1) == TARGET_MEM_REF)
1001               && (SSA_VAR_P (ref2)
1002                   || handled_component_p (ref2)
1003                   || INDIRECT_REF_P (ref2)
1004                   || TREE_CODE (ref2) == TARGET_MEM_REF));
1005
1006   /* Defer to TBAA if possible.  */
1007   if (flag_strict_aliasing
1008       && !alias_sets_conflict_p (get_alias_set (ref1), get_alias_set (ref2)))
1009     return false;
1010
1011   /* Decompose the references into their base objects and the access.  */
1012   base1 = ref1;
1013   if (handled_component_p (ref1))
1014     base1 = get_ref_base_and_extent (ref1, &offset1, &size1, &max_size1);
1015   base2 = ref2;
1016   if (handled_component_p (ref2))
1017     base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &max_size2);
1018
1019   /* If both references are based on different variables, they cannot alias.
1020      If both references are based on the same variable, they cannot alias if
1021      if the accesses do not overlap.  */
1022   if (SSA_VAR_P (base1)
1023       && SSA_VAR_P (base2)
1024       && (!operand_equal_p (base1, base2, 0)
1025           || !ranges_overlap_p (offset1, max_size1, offset2, max_size2)))
1026     return false;
1027
1028   /* If both references are through pointers and both pointers are equal
1029      then they do not alias if the accesses do not overlap.  */
1030   if (TREE_CODE (base1) == INDIRECT_REF
1031       && TREE_CODE (base2) == INDIRECT_REF
1032       && operand_equal_p (TREE_OPERAND (base1, 0),
1033                           TREE_OPERAND (base2, 0), 0)
1034       && !ranges_overlap_p (offset1, max_size1, offset2, max_size2))
1035     return false;
1036
1037   return true;
1038 }
1039
1040 /* Given a stmt STMT that references memory, return the single stmt
1041    that is reached by following the VUSE -> VDEF link.  Returns
1042    NULL_TREE, if there is no single stmt that defines all VUSEs of
1043    STMT.
1044    Note that for a stmt with a single virtual operand this may return
1045    a PHI node as well.  Note that if all VUSEs are default definitions
1046    this function will return an empty statement.  */
1047
1048 tree
1049 get_single_def_stmt (tree stmt)
1050 {
1051   tree def_stmt = NULL_TREE;
1052   tree use;
1053   ssa_op_iter iter;
1054
1055   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_VIRTUAL_USES)
1056     {
1057       tree tmp = SSA_NAME_DEF_STMT (use);
1058
1059       /* ???  This is too simplistic for multiple virtual operands
1060          reaching different PHI nodes of the same basic blocks or for
1061          reaching all default definitions.  */
1062       if (def_stmt
1063           && def_stmt != tmp
1064           && !(IS_EMPTY_STMT (def_stmt)
1065                && IS_EMPTY_STMT (tmp)))
1066         return NULL_TREE;
1067
1068       def_stmt = tmp;
1069     }
1070
1071   return def_stmt;
1072 }
1073
1074 /* Given a PHI node of virtual operands, tries to eliminate cyclic
1075    reached definitions if they do not alias REF and returns the
1076    defining statement of the single virtual operand that flows in
1077    from a non-backedge.  Returns NULL_TREE if such statement within
1078    the above conditions cannot be found.  */
1079
1080 tree
1081 get_single_def_stmt_from_phi (tree ref, tree phi)
1082 {
1083   tree def_arg = NULL_TREE;
1084   int i;
1085
1086   /* Find the single PHI argument that is not flowing in from a
1087      back edge and verify that the loop-carried definitions do
1088      not alias the reference we look for.  */
1089   for (i = 0; i < PHI_NUM_ARGS (phi); ++i)
1090     {
1091       tree arg = PHI_ARG_DEF (phi, i);
1092       tree def_stmt;
1093
1094       if (!(PHI_ARG_EDGE (phi, i)->flags & EDGE_DFS_BACK))
1095         {
1096           /* Multiple non-back edges?  Do not try to handle this.  */
1097           if (def_arg)
1098             return NULL_TREE;
1099           def_arg = arg;
1100           continue;
1101         }
1102
1103       /* Follow the definitions back to the original PHI node.  Bail
1104          out once a definition is found that may alias REF.  */
1105       def_stmt = SSA_NAME_DEF_STMT (arg);
1106       do
1107         {
1108           if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT
1109               || refs_may_alias_p (ref, GIMPLE_STMT_OPERAND (def_stmt, 0)))
1110             return NULL_TREE;
1111           /* ???  This will only work, reaching the PHI node again if
1112              there is a single virtual operand on def_stmt.  */
1113           def_stmt = get_single_def_stmt (def_stmt);
1114           if (!def_stmt)
1115             return NULL_TREE;
1116         }
1117       while (def_stmt != phi);
1118     }
1119
1120   return SSA_NAME_DEF_STMT (def_arg);
1121 }
1122
1123 /* Return the single reference statement defining all virtual uses
1124    on STMT or NULL_TREE, if there are multiple defining statements.
1125    Take into account only definitions that alias REF if following
1126    back-edges when looking through a loop PHI node.  */
1127
1128 tree
1129 get_single_def_stmt_with_phi (tree ref, tree stmt)
1130 {
1131   switch (NUM_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES))
1132     {
1133     case 0:
1134       gcc_unreachable ();
1135
1136     case 1:
1137       {
1138         tree def_stmt = SSA_NAME_DEF_STMT (SINGLE_SSA_TREE_OPERAND
1139                                              (stmt, SSA_OP_VIRTUAL_USES));
1140         /* We can handle lookups over PHI nodes only for a single
1141            virtual operand.  */
1142         if (TREE_CODE (def_stmt) == PHI_NODE)
1143           return get_single_def_stmt_from_phi (ref, def_stmt);
1144         return def_stmt;
1145       }
1146
1147     default:
1148       return get_single_def_stmt (stmt);
1149     }
1150 }