gcc/tree-dfa.c

   1 /* Data flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009
   3    Free Software Foundation, Inc.
   4    Contributed by Diego Novillo <dnovillo@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  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 "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_var_anns;
  56   long num_defs;
  57   long num_uses;
  58   long num_phis;
  59   long num_phi_args;
  60   size_t 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 find_vars_r (tree *, int *, void *);
  69
  70
  71 /*---------------------------------------------------------------------------
  72                         Dataflow analysis (DFA) routines
  73 ---------------------------------------------------------------------------*/
  74 /* Find all the variables referenced in the function.  This function
  75    builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
  76
  77    Note that this function does not look for statement operands, it simply
  78    determines what variables are referenced in the program and detects
  79    various attributes for each variable used by alias analysis and the
  80    optimizer.  */
  81
  82 static unsigned int
  83 find_referenced_vars (void)
  84 {
  85   basic_block bb;
  86   gimple_stmt_iterator si;
  87
  88   FOR_EACH_BB (bb)
  89     {
  90       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
  91         {
  92           gimple stmt = gsi_stmt (si);
  93           if (is_gimple_debug (stmt))
  94             continue;
  95           find_referenced_vars_in (gsi_stmt (si));
  96         }
  97
  98       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
  99         find_referenced_vars_in (gsi_stmt (si));
 100     }
 101
 102   return 0;
 103 }
 104
 105 struct gimple_opt_pass pass_referenced_vars =
 106 {
 107  {
 108   GIMPLE_PASS,
 109   NULL,                                 /* name */
 110   NULL,                                 /* gate */
 111   find_referenced_vars,                 /* execute */
 112   NULL,                                 /* sub */
 113   NULL,                                 /* next */
 114   0,                                    /* static_pass_number */
 115   TV_FIND_REFERENCED_VARS,              /* tv_id */
 116   PROP_gimple_leh | PROP_cfg,           /* properties_required */
 117   PROP_referenced_vars,                 /* properties_provided */
 118   0,                                    /* properties_destroyed */
 119   TODO_dump_func,                       /* todo_flags_start */
 120   TODO_dump_func                        /* todo_flags_finish */
 121  }
 122 };
 123
 124
 125 /*---------------------------------------------------------------------------
 126                             Manage annotations
 127 ---------------------------------------------------------------------------*/
 128 /* Create a new annotation for a _DECL node T.  */
 129
 130 var_ann_t
 131 create_var_ann (tree t)
 132 {
 133   var_ann_t ann;
 134
 135   gcc_assert (t);
 136   gcc_assert (DECL_P (t));
 137   gcc_assert (!t->base.ann || t->base.ann->common.type == VAR_ANN);
 138
 139   ann = GGC_CNEW (struct var_ann_d);
 140   ann->common.type = VAR_ANN;
 141   t->base.ann = (tree_ann_t) ann;
 142
 143   return ann;
 144 }
 145
 146 /* Renumber all of the gimple stmt uids.  */
 147
 148 void
 149 renumber_gimple_stmt_uids (void)
 150 {
 151   basic_block bb;
 152
 153   set_gimple_stmt_max_uid (cfun, 0);
 154   FOR_ALL_BB (bb)
 155     {
 156       gimple_stmt_iterator bsi;
 157       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 158         {
 159           gimple stmt = gsi_stmt (bsi);
 160           gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
 161         }
 162     }
 163 }
 164
 165 /* Like renumber_gimple_stmt_uids, but only do work on the basic blocks
 166    in BLOCKS, of which there are N_BLOCKS.  Also renumbers PHIs.  */
 167
 168 void
 169 renumber_gimple_stmt_uids_in_blocks (basic_block *blocks, int n_blocks)
 170 {
 171   int i;
 172
 173   set_gimple_stmt_max_uid (cfun, 0);
 174   for (i = 0; i < n_blocks; i++)
 175     {
 176       basic_block bb = blocks[i];
 177       gimple_stmt_iterator bsi;
 178       for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 179         {
 180           gimple stmt = gsi_stmt (bsi);
 181           gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
 182         }
 183       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 184         {
 185           gimple stmt = gsi_stmt (bsi);
 186           gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
 187         }
 188     }
 189 }
 190
 191 /* Create a new annotation for a tree T.  */
 192
 193 tree_ann_common_t
 194 create_tree_common_ann (tree t)
 195 {
 196   tree_ann_common_t ann;
 197
 198   gcc_assert (t);
 199   gcc_assert (!t->base.ann || t->base.ann->common.type == TREE_ANN_COMMON);
 200
 201   ann = GGC_CNEW (struct tree_ann_common_d);
 202
 203   ann->type = TREE_ANN_COMMON;
 204   ann->rn = -1;
 205   t->base.ann = (tree_ann_t) ann;
 206
 207   return ann;
 208 }
 209
 210 /* Build a temporary.  Make sure and register it to be renamed.  */
 211
 212 tree
 213 make_rename_temp (tree type, const char *prefix)
 214 {
 215   tree t = create_tmp_var (type, prefix);
 216
 217   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 218       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 219     DECL_GIMPLE_REG_P (t) = 1;
 220
 221   if (gimple_referenced_vars (cfun))
 222     {
 223       add_referenced_var (t);
 224       mark_sym_for_renaming (t);
 225     }
 226
 227   return t;
 228 }
 229
 230
 231
 232 /*---------------------------------------------------------------------------
 233                               Debugging functions
 234 ---------------------------------------------------------------------------*/
 235 /* Dump the list of all the referenced variables in the current function to
 236    FILE.  */
 237
 238 void
 239 dump_referenced_vars (FILE *file)
 240 {
 241   tree var;
 242   referenced_var_iterator rvi;
 243
 244   fprintf (file, "\nReferenced variables in %s: %u\n\n",
 245            get_name (current_function_decl), (unsigned) num_referenced_vars);
 246
 247   FOR_EACH_REFERENCED_VAR (var, rvi)
 248     {
 249       fprintf (file, "Variable: ");
 250       dump_variable (file, var);
 251     }
 252
 253   fprintf (file, "\n");
 254 }
 255
 256
 257 /* Dump the list of all the referenced variables to stderr.  */
 258
 259 void
 260 debug_referenced_vars (void)
 261 {
 262   dump_referenced_vars (stderr);
 263 }
 264
 265
 266 /* Dump variable VAR and its may-aliases to FILE.  */
 267
 268 void
 269 dump_variable (FILE *file, tree var)
 270 {
 271   var_ann_t ann;
 272
 273   if (TREE_CODE (var) == SSA_NAME)
 274     {
 275       if (POINTER_TYPE_P (TREE_TYPE (var)))
 276         dump_points_to_info_for (file, var);
 277       var = SSA_NAME_VAR (var);
 278     }
 279
 280   if (var == NULL_TREE)
 281     {
 282       fprintf (file, "<nil>");
 283       return;
 284     }
 285
 286   print_generic_expr (file, var, dump_flags);
 287
 288   ann = var_ann (var);
 289
 290   fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
 291
 292   fprintf (file, ", ");
 293   print_generic_expr (file, TREE_TYPE (var), dump_flags);
 294
 295   if (TREE_ADDRESSABLE (var))
 296     fprintf (file, ", is addressable");
 297
 298   if (is_global_var (var))
 299     fprintf (file, ", is global");
 300
 301   if (TREE_THIS_VOLATILE (var))
 302     fprintf (file, ", is volatile");
 303
 304   if (is_call_clobbered (var))
 305     fprintf (file, ", call clobbered");
 306   else if (is_call_used (var))
 307     fprintf (file, ", call used");
 308
 309   if (ann && ann->noalias_state == NO_ALIAS)
 310     fprintf (file, ", NO_ALIAS (does not alias other NO_ALIAS symbols)");
 311   else if (ann && ann->noalias_state == NO_ALIAS_GLOBAL)
 312     fprintf (file, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols"
 313                    " and global vars)");
 314   else if (ann && ann->noalias_state == NO_ALIAS_ANYTHING)
 315     fprintf (file, ", NO_ALIAS_ANYTHING (does not alias any other symbols)");
 316
 317   if (cfun && gimple_default_def (cfun, var))
 318     {
 319       fprintf (file, ", default def: ");
 320       print_generic_expr (file, gimple_default_def (cfun, var), dump_flags);
 321     }
 322
 323   if (DECL_INITIAL (var))
 324     {
 325       fprintf (file, ", initial: ");
 326       print_generic_expr (file, DECL_INITIAL (var), dump_flags);
 327     }
 328
 329   fprintf (file, "\n");
 330 }
 331
 332
 333 /* Dump variable VAR and its may-aliases to stderr.  */
 334
 335 void
 336 debug_variable (tree var)
 337 {
 338   dump_variable (stderr, var);
 339 }
 340
 341
 342 /* Dump various DFA statistics to FILE.  */
 343
 344 void
 345 dump_dfa_stats (FILE *file)
 346 {
 347   struct dfa_stats_d dfa_stats;
 348
 349   unsigned long size, total = 0;
 350   const char * const fmt_str   = "%-30s%-13s%12s\n";
 351   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 352   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 353   const char *funcname
 354     = lang_hooks.decl_printable_name (current_function_decl, 2);
 355
 356   collect_dfa_stats (&dfa_stats);
 357
 358   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 359
 360   fprintf (file, "---------------------------------------------------------\n");
 361   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 362   fprintf (file, fmt_str, "", "  instances  ", "used ");
 363   fprintf (file, "---------------------------------------------------------\n");
 364
 365   size = num_referenced_vars * sizeof (tree);
 366   total += size;
 367   fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
 368            SCALE (size), LABEL (size));
 369
 370   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 371   total += size;
 372   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 373            SCALE (size), LABEL (size));
 374
 375   size = dfa_stats.num_uses * sizeof (tree *);
 376   total += size;
 377   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 378            SCALE (size), LABEL (size));
 379
 380   size = dfa_stats.num_defs * sizeof (tree *);
 381   total += size;
 382   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 383            SCALE (size), LABEL (size));
 384
 385   size = dfa_stats.num_vuses * sizeof (tree *);
 386   total += size;
 387   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 388            SCALE (size), LABEL (size));
 389
 390   size = dfa_stats.num_vdefs * sizeof (tree *);
 391   total += size;
 392   fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
 393            SCALE (size), LABEL (size));
 394
 395   size = dfa_stats.num_phis * sizeof (struct gimple_statement_phi);
 396   total += size;
 397   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 398            SCALE (size), LABEL (size));
 399
 400   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 401   total += size;
 402   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 403            SCALE (size), LABEL (size));
 404
 405   fprintf (file, "---------------------------------------------------------\n");
 406   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 407            LABEL (total));
 408   fprintf (file, "---------------------------------------------------------\n");
 409   fprintf (file, "\n");
 410
 411   if (dfa_stats.num_phis)
 412     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %ld)\n",
 413              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 414              (long) dfa_stats.max_num_phi_args);
 415
 416   fprintf (file, "\n");
 417 }
 418
 419
 420 /* Dump DFA statistics on stderr.  */
 421
 422 void
 423 debug_dfa_stats (void)
 424 {
 425   dump_dfa_stats (stderr);
 426 }
 427
 428
 429 /* Collect DFA statistics and store them in the structure pointed to by
 430    DFA_STATS_P.  */
 431
 432 static void
 433 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED)
 434 {
 435   basic_block bb;
 436   referenced_var_iterator vi;
 437   tree var;
 438
 439   gcc_assert (dfa_stats_p);
 440
 441   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 442
 443   /* Count all the variable annotations.  */
 444   FOR_EACH_REFERENCED_VAR (var, vi)
 445     if (var_ann (var))
 446       dfa_stats_p->num_var_anns++;
 447
 448   /* Walk all the statements in the function counting references.  */
 449   FOR_EACH_BB (bb)
 450     {
 451       gimple_stmt_iterator si;
 452
 453       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
 454         {
 455           gimple phi = gsi_stmt (si);
 456           dfa_stats_p->num_phis++;
 457           dfa_stats_p->num_phi_args += gimple_phi_num_args (phi);
 458           if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args)
 459             dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi);
 460         }
 461
 462       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
 463         {
 464           gimple stmt = gsi_stmt (si);
 465           dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF);
 466           dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE);
 467           dfa_stats_p->num_vdefs += gimple_vdef (stmt) ? 1 : 0;
 468           dfa_stats_p->num_vuses += gimple_vuse (stmt) ? 1 : 0;
 469         }
 470     }
 471 }
 472
 473
 474 /*---------------------------------------------------------------------------
 475                              Miscellaneous helpers
 476 ---------------------------------------------------------------------------*/
 477 /* Callback for walk_tree.  Used to collect variables referenced in
 478    the function.  */
 479
 480 static tree
 481 find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
 482 {
 483   /* If we are reading the lto info back in, we need to rescan the
 484      referenced vars.  */
 485   if (TREE_CODE (*tp) == SSA_NAME)
 486     add_referenced_var (SSA_NAME_VAR (*tp));
 487
 488   /* If T is a regular variable that the optimizers are interested
 489      in, add it to the list of variables.  */
 490   else if (SSA_VAR_P (*tp))
 491     add_referenced_var (*tp);
 492
 493   /* Type, _DECL and constant nodes have no interesting children.
 494      Ignore them.  */
 495   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
 496     *walk_subtrees = 0;
 497
 498   return NULL_TREE;
 499 }
 500
 501 /* Find referenced variables in STMT.  In contrast with
 502    find_new_referenced_vars, this function will not mark newly found
 503    variables for renaming.  */
 504
 505 void
 506 find_referenced_vars_in (gimple stmt)
 507 {
 508   size_t i;
 509
 510   if (gimple_code (stmt) != GIMPLE_PHI)
 511     {
 512       for (i = 0; i < gimple_num_ops (stmt); i++)
 513         walk_tree (gimple_op_ptr (stmt, i), find_vars_r, NULL, NULL);
 514     }
 515   else
 516     {
 517       walk_tree (gimple_phi_result_ptr (stmt), find_vars_r, NULL, NULL);
 518
 519       for (i = 0; i < gimple_phi_num_args (stmt); i++)
 520         {
 521           tree arg = gimple_phi_arg_def (stmt, i);
 522           walk_tree (&arg, find_vars_r, NULL, NULL);
 523         }
 524     }
 525 }
 526
 527
 528 /* Lookup UID in the referenced_vars hashtable and return the associated
 529    variable.  */
 530
 531 tree
 532 referenced_var_lookup (unsigned int uid)
 533 {
 534   tree h;
 535   struct tree_decl_minimal in;
 536   in.uid = uid;
 537   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 538   gcc_assert (h || uid == 0);
 539   return h;
 540 }
 541
 542 /* Check if TO is in the referenced_vars hash table and insert it if not.
 543    Return true if it required insertion.  */
 544
 545 bool
 546 referenced_var_check_and_insert (tree to)
 547 {
 548   tree h, *loc;
 549   struct tree_decl_minimal in;
 550   unsigned int uid = DECL_UID (to);
 551
 552   in.uid = uid;
 553   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 554   if (h)
 555     {
 556       /* DECL_UID has already been entered in the table.  Verify that it is
 557          the same entry as TO.  See PR 27793.  */
 558       gcc_assert (h == to);
 559       return false;
 560     }
 561
 562   loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun),
 563                                            &in, uid, INSERT);
 564   *loc = to;
 565   return true;
 566 }
 567
 568 /* Lookup VAR UID in the default_defs hashtable and return the associated
 569    variable.  */
 570
 571 tree
 572 gimple_default_def (struct function *fn, tree var)
 573 {
 574   struct tree_decl_minimal ind;
 575   struct tree_ssa_name in;
 576   gcc_assert (SSA_VAR_P (var));
 577   in.var = (tree)&ind;
 578   ind.uid = DECL_UID (var);
 579   return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var));
 580 }
 581
 582 /* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
 583
 584 void
 585 set_default_def (tree var, tree def)
 586 {
 587   struct tree_decl_minimal ind;
 588   struct tree_ssa_name in;
 589   void **loc;
 590
 591   gcc_assert (SSA_VAR_P (var));
 592   in.var = (tree)&ind;
 593   ind.uid = DECL_UID (var);
 594   if (!def)
 595     {
 596       loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 597             DECL_UID (var), INSERT);
 598       gcc_assert (*loc);
 599       htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
 600       return;
 601     }
 602   gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
 603   loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 604                                   DECL_UID (var), INSERT);
 605
 606   /* Default definition might be changed by tail call optimization.  */
 607   if (*loc)
 608     SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false;
 609   *(tree *) loc = def;
 610
 611    /* Mark DEF as the default definition for VAR.  */
 612    SSA_NAME_IS_DEFAULT_DEF (def) = true;
 613 }
 614
 615 /* Add VAR to the list of referenced variables if it isn't already there.  */
 616
 617 bool
 618 add_referenced_var (tree var)
 619 {
 620   var_ann_t v_ann;
 621
 622   v_ann = get_var_ann (var);
 623   gcc_assert (DECL_P (var));
 624
 625   /* Insert VAR into the referenced_vars has table if it isn't present.  */
 626   if (referenced_var_check_and_insert (var))
 627     {
 628       /* Scan DECL_INITIAL for pointer variables as they may contain
 629          address arithmetic referencing the address of other
 630          variables.  As we are only interested in directly referenced
 631          globals or referenced locals restrict this to initializers
 632          than can refer to local variables.  */
 633       if (DECL_INITIAL (var)
 634           && DECL_CONTEXT (var) == current_function_decl)
 635         walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
 636
 637       return true;
 638     }
 639
 640   return false;
 641 }
 642
 643 /* Remove VAR from the list.  */
 644
 645 void
 646 remove_referenced_var (tree var)
 647 {
 648   var_ann_t v_ann;
 649   struct tree_decl_minimal in;
 650   void **loc;
 651   unsigned int uid = DECL_UID (var);
 652
 653   /* Preserve var_anns of globals.  */
 654   if (!is_global_var (var)
 655       && (v_ann = var_ann (var)))
 656     {
 657       ggc_free (v_ann);
 658       var->base.ann = NULL;
 659     }
 660   gcc_assert (DECL_P (var));
 661   in.uid = uid;
 662   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
 663                                   NO_INSERT);
 664   htab_clear_slot (gimple_referenced_vars (cfun), loc);
 665 }
 666
 667
 668 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 669
 670 tree
 671 get_virtual_var (tree var)
 672 {
 673   STRIP_NOPS (var);
 674
 675   if (TREE_CODE (var) == SSA_NAME)
 676     var = SSA_NAME_VAR (var);
 677
 678   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 679          || handled_component_p (var))
 680     var = TREE_OPERAND (var, 0);
 681
 682   /* Treating GIMPLE registers as virtual variables makes no sense.
 683      Also complain if we couldn't extract a _DECL out of the original
 684      expression.  */
 685   gcc_assert (SSA_VAR_P (var));
 686   gcc_assert (!is_gimple_reg (var));
 687
 688   return var;
 689 }
 690
 691 /* Mark all the naked symbols in STMT for SSA renaming.  */
 692
 693 void
 694 mark_symbols_for_renaming (gimple stmt)
 695 {
 696   tree op;
 697   ssa_op_iter iter;
 698
 699   update_stmt (stmt);
 700
 701   /* Mark all the operands for renaming.  */
 702   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 703     if (DECL_P (op))
 704       mark_sym_for_renaming (op);
 705 }
 706
 707
 708 /* Find all variables within the gimplified statement that were not
 709    previously visible to the function and add them to the referenced
 710    variables list.  */
 711
 712 static tree
 713 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 714                             void *data ATTRIBUTE_UNUSED)
 715 {
 716   tree t = *tp;
 717
 718   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 719     {
 720       add_referenced_var (t);
 721       mark_sym_for_renaming (t);
 722     }
 723
 724   if (IS_TYPE_OR_DECL_P (t))
 725     *walk_subtrees = 0;
 726
 727   return NULL;
 728 }
 729
 730
 731 /* Find any new referenced variables in STMT.  */
 732
 733 void
 734 find_new_referenced_vars (gimple stmt)
 735 {
 736   walk_gimple_op (stmt, find_new_referenced_vars_1, NULL);
 737 }
 738
 739
 740 /* If EXP is a handled component reference for a structure, return the
 741    base variable.  The access range is delimited by bit positions *POFFSET and
 742    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 743    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 744    and *PMAX_SIZE are equal, the access is non-variable.  */
 745
 746 tree
 747 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 748                          HOST_WIDE_INT *psize,
 749                          HOST_WIDE_INT *pmax_size)
 750 {
 751   HOST_WIDE_INT bitsize = -1;
 752   HOST_WIDE_INT maxsize = -1;
 753   tree size_tree = NULL_TREE;
 754   HOST_WIDE_INT bit_offset = 0;
 755   bool seen_variable_array_ref = false;
 756   bool seen_union = false;
 757
 758   /* First get the final access size from just the outermost expression.  */
 759   if (TREE_CODE (exp) == COMPONENT_REF)
 760     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 761   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 762     size_tree = TREE_OPERAND (exp, 1);
 763   else if (!VOID_TYPE_P (TREE_TYPE (exp)))
 764     {
 765       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 766       if (mode == BLKmode)
 767         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 768       else
 769         bitsize = GET_MODE_BITSIZE (mode);
 770     }
 771   if (size_tree != NULL_TREE)
 772     {
 773       if (! host_integerp (size_tree, 1))
 774         bitsize = -1;
 775       else
 776         bitsize = TREE_INT_CST_LOW (size_tree);
 777     }
 778
 779   /* Initially, maxsize is the same as the accessed element size.
 780      In the following it will only grow (or become -1).  */
 781   maxsize = bitsize;
 782
 783   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 784      and find the ultimate containing object.  */
 785   while (1)
 786     {
 787       switch (TREE_CODE (exp))
 788         {
 789         case BIT_FIELD_REF:
 790           bit_offset += TREE_INT_CST_LOW (TREE_OPERAND (exp, 2));
 791           break;
 792
 793         case COMPONENT_REF:
 794           {
 795             tree field = TREE_OPERAND (exp, 1);
 796             tree this_offset = component_ref_field_offset (exp);
 797
 798             if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == UNION_TYPE)
 799               seen_union = true;
 800
 801             if (this_offset
 802                 && TREE_CODE (this_offset) == INTEGER_CST
 803                 && host_integerp (this_offset, 0))
 804               {
 805                 HOST_WIDE_INT hthis_offset = TREE_INT_CST_LOW (this_offset);
 806                 hthis_offset *= BITS_PER_UNIT;
 807                 bit_offset += hthis_offset;
 808                 bit_offset += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
 809               }
 810             else
 811               {
 812                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 813                 /* We need to adjust maxsize to the whole structure bitsize.
 814                    But we can subtract any constant offset seen so far,
 815                    because that would get us out of the structure otherwise.  */
 816                 if (maxsize != -1 && csize && host_integerp (csize, 1))
 817                   maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
 818                 else
 819                   maxsize = -1;
 820               }
 821           }
 822           break;
 823
 824         case ARRAY_REF:
 825         case ARRAY_RANGE_REF:
 826           {
 827             tree index = TREE_OPERAND (exp, 1);
 828             tree low_bound, unit_size;
 829
 830             /* If the resulting bit-offset is constant, track it.  */
 831             if (TREE_CODE (index) == INTEGER_CST
 832                 && host_integerp (index, 0)
 833                 && (low_bound = array_ref_low_bound (exp),
 834                     host_integerp (low_bound, 0))
 835                 && (unit_size = array_ref_element_size (exp),
 836                     host_integerp (unit_size, 1)))
 837               {
 838                 HOST_WIDE_INT hindex = TREE_INT_CST_LOW (index);
 839
 840                 hindex -= TREE_INT_CST_LOW (low_bound);
 841                 hindex *= TREE_INT_CST_LOW (unit_size);
 842                 hindex *= BITS_PER_UNIT;
 843                 bit_offset += hindex;
 844
 845                 /* An array ref with a constant index up in the structure
 846                    hierarchy will constrain the size of any variable array ref
 847                    lower in the access hierarchy.  */
 848                 seen_variable_array_ref = false;
 849               }
 850             else
 851               {
 852                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 853                 /* We need to adjust maxsize to the whole array bitsize.
 854                    But we can subtract any constant offset seen so far,
 855                    because that would get us outside of the array otherwise.  */
 856                 if (maxsize != -1 && asize && host_integerp (asize, 1))
 857                   maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
 858                 else
 859                   maxsize = -1;
 860
 861                 /* Remember that we have seen an array ref with a variable
 862                    index.  */
 863                 seen_variable_array_ref = true;
 864               }
 865           }
 866           break;
 867
 868         case REALPART_EXPR:
 869           break;
 870
 871         case IMAGPART_EXPR:
 872           bit_offset += bitsize;
 873           break;
 874
 875         case VIEW_CONVERT_EXPR:
 876           /* ???  We probably should give up here and bail out.  */
 877           break;
 878
 879         default:
 880           goto done;
 881         }
 882
 883       exp = TREE_OPERAND (exp, 0);
 884     }
 885  done:
 886
 887   /* We need to deal with variable arrays ending structures such as
 888        struct { int length; int a[1]; } x;           x.a[d]
 889        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 890        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 891      where we do not know maxsize for variable index accesses to
 892      the array.  The simplest way to conservatively deal with this
 893      is to punt in the case that offset + maxsize reaches the
 894      base type boundary.
 895
 896      Unfortunately this is difficult to determine reliably when unions are
 897      involved and so we are conservative in such cases.
 898
 899      FIXME: This approach may be too conservative, we probably want to at least
 900      check that the union is the last field/element at its level or even
 901      propagate the calculated offsets back up the access chain and check
 902      there.  */
 903
 904   if (seen_variable_array_ref
 905       && (seen_union
 906           || (maxsize != -1
 907               && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
 908               && bit_offset + maxsize
 909               == (signed) TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))))
 910     maxsize = -1;
 911
 912   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 913      negative bit_offset here.  We might want to store a zero offset
 914      in this case.  */
 915   *poffset = bit_offset;
 916   *psize = bitsize;
 917   *pmax_size = maxsize;
 918
 919   return exp;
 920 }
 921
 922 /* Returns true if STMT references an SSA_NAME that has
 923    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
 924
 925 bool
 926 stmt_references_abnormal_ssa_name (gimple stmt)
 927 {
 928   ssa_op_iter oi;
 929   use_operand_p use_p;
 930
 931   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
 932     {
 933       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
 934         return true;
 935     }
 936
 937   return false;
 938 }
 939