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   "*referenced_vars",                   /* 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   t->base.ann = (tree_ann_t) ann;
 205
 206   return ann;
 207 }
 208
 209 /* Build a temporary.  Make sure and register it to be renamed.  */
 210
 211 tree
 212 make_rename_temp (tree type, const char *prefix)
 213 {
 214   tree t = create_tmp_var (type, prefix);
 215
 216   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 217       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 218     DECL_GIMPLE_REG_P (t) = 1;
 219
 220   if (gimple_referenced_vars (cfun))
 221     {
 222       add_referenced_var (t);
 223       mark_sym_for_renaming (t);
 224     }
 225
 226   return t;
 227 }
 228
 229
 230
 231 /*---------------------------------------------------------------------------
 232                               Debugging functions
 233 ---------------------------------------------------------------------------*/
 234 /* Dump the list of all the referenced variables in the current function to
 235    FILE.  */
 236
 237 void
 238 dump_referenced_vars (FILE *file)
 239 {
 240   tree var;
 241   referenced_var_iterator rvi;
 242
 243   fprintf (file, "\nReferenced variables in %s: %u\n\n",
 244            get_name (current_function_decl), (unsigned) num_referenced_vars);
 245
 246   FOR_EACH_REFERENCED_VAR (var, rvi)
 247     {
 248       fprintf (file, "Variable: ");
 249       dump_variable (file, var);
 250     }
 251
 252   fprintf (file, "\n");
 253 }
 254
 255
 256 /* Dump the list of all the referenced variables to stderr.  */
 257
 258 void
 259 debug_referenced_vars (void)
 260 {
 261   dump_referenced_vars (stderr);
 262 }
 263
 264
 265 /* Dump variable VAR and its may-aliases to FILE.  */
 266
 267 void
 268 dump_variable (FILE *file, tree var)
 269 {
 270   var_ann_t ann;
 271
 272   if (TREE_CODE (var) == SSA_NAME)
 273     {
 274       if (POINTER_TYPE_P (TREE_TYPE (var)))
 275         dump_points_to_info_for (file, var);
 276       var = SSA_NAME_VAR (var);
 277     }
 278
 279   if (var == NULL_TREE)
 280     {
 281       fprintf (file, "<nil>");
 282       return;
 283     }
 284
 285   print_generic_expr (file, var, dump_flags);
 286
 287   ann = var_ann (var);
 288
 289   fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
 290
 291   fprintf (file, ", ");
 292   print_generic_expr (file, TREE_TYPE (var), dump_flags);
 293
 294   if (TREE_ADDRESSABLE (var))
 295     fprintf (file, ", is addressable");
 296
 297   if (is_global_var (var))
 298     fprintf (file, ", is global");
 299
 300   if (TREE_THIS_VOLATILE (var))
 301     fprintf (file, ", is volatile");
 302
 303   if (is_call_clobbered (var))
 304     fprintf (file, ", call clobbered");
 305   else if (is_call_used (var))
 306     fprintf (file, ", call used");
 307
 308   if (ann && ann->noalias_state == NO_ALIAS)
 309     fprintf (file, ", NO_ALIAS (does not alias other NO_ALIAS symbols)");
 310   else if (ann && ann->noalias_state == NO_ALIAS_GLOBAL)
 311     fprintf (file, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols"
 312                    " and global vars)");
 313   else if (ann && ann->noalias_state == NO_ALIAS_ANYTHING)
 314     fprintf (file, ", NO_ALIAS_ANYTHING (does not alias any other symbols)");
 315
 316   if (cfun && gimple_default_def (cfun, var))
 317     {
 318       fprintf (file, ", default def: ");
 319       print_generic_expr (file, gimple_default_def (cfun, var), dump_flags);
 320     }
 321
 322   if (DECL_INITIAL (var))
 323     {
 324       fprintf (file, ", initial: ");
 325       print_generic_expr (file, DECL_INITIAL (var), dump_flags);
 326     }
 327
 328   fprintf (file, "\n");
 329 }
 330
 331
 332 /* Dump variable VAR and its may-aliases to stderr.  */
 333
 334 void
 335 debug_variable (tree var)
 336 {
 337   dump_variable (stderr, var);
 338 }
 339
 340
 341 /* Dump various DFA statistics to FILE.  */
 342
 343 void
 344 dump_dfa_stats (FILE *file)
 345 {
 346   struct dfa_stats_d dfa_stats;
 347
 348   unsigned long size, total = 0;
 349   const char * const fmt_str   = "%-30s%-13s%12s\n";
 350   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 351   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 352   const char *funcname
 353     = lang_hooks.decl_printable_name (current_function_decl, 2);
 354
 355   collect_dfa_stats (&dfa_stats);
 356
 357   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 358
 359   fprintf (file, "---------------------------------------------------------\n");
 360   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 361   fprintf (file, fmt_str, "", "  instances  ", "used ");
 362   fprintf (file, "---------------------------------------------------------\n");
 363
 364   size = num_referenced_vars * sizeof (tree);
 365   total += size;
 366   fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
 367            SCALE (size), LABEL (size));
 368
 369   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 370   total += size;
 371   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 372            SCALE (size), LABEL (size));
 373
 374   size = dfa_stats.num_uses * sizeof (tree *);
 375   total += size;
 376   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 377            SCALE (size), LABEL (size));
 378
 379   size = dfa_stats.num_defs * sizeof (tree *);
 380   total += size;
 381   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 382            SCALE (size), LABEL (size));
 383
 384   size = dfa_stats.num_vuses * sizeof (tree *);
 385   total += size;
 386   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 387            SCALE (size), LABEL (size));
 388
 389   size = dfa_stats.num_vdefs * sizeof (tree *);
 390   total += size;
 391   fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
 392            SCALE (size), LABEL (size));
 393
 394   size = dfa_stats.num_phis * sizeof (struct gimple_statement_phi);
 395   total += size;
 396   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 397            SCALE (size), LABEL (size));
 398
 399   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 400   total += size;
 401   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 402            SCALE (size), LABEL (size));
 403
 404   fprintf (file, "---------------------------------------------------------\n");
 405   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 406            LABEL (total));
 407   fprintf (file, "---------------------------------------------------------\n");
 408   fprintf (file, "\n");
 409
 410   if (dfa_stats.num_phis)
 411     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %ld)\n",
 412              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 413              (long) dfa_stats.max_num_phi_args);
 414
 415   fprintf (file, "\n");
 416 }
 417
 418
 419 /* Dump DFA statistics on stderr.  */
 420
 421 void
 422 debug_dfa_stats (void)
 423 {
 424   dump_dfa_stats (stderr);
 425 }
 426
 427
 428 /* Collect DFA statistics and store them in the structure pointed to by
 429    DFA_STATS_P.  */
 430
 431 static void
 432 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED)
 433 {
 434   basic_block bb;
 435   referenced_var_iterator vi;
 436   tree var;
 437
 438   gcc_assert (dfa_stats_p);
 439
 440   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 441
 442   /* Count all the variable annotations.  */
 443   FOR_EACH_REFERENCED_VAR (var, vi)
 444     if (var_ann (var))
 445       dfa_stats_p->num_var_anns++;
 446
 447   /* Walk all the statements in the function counting references.  */
 448   FOR_EACH_BB (bb)
 449     {
 450       gimple_stmt_iterator si;
 451
 452       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
 453         {
 454           gimple phi = gsi_stmt (si);
 455           dfa_stats_p->num_phis++;
 456           dfa_stats_p->num_phi_args += gimple_phi_num_args (phi);
 457           if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args)
 458             dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi);
 459         }
 460
 461       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
 462         {
 463           gimple stmt = gsi_stmt (si);
 464           dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF);
 465           dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE);
 466           dfa_stats_p->num_vdefs += gimple_vdef (stmt) ? 1 : 0;
 467           dfa_stats_p->num_vuses += gimple_vuse (stmt) ? 1 : 0;
 468         }
 469     }
 470 }
 471
 472
 473 /*---------------------------------------------------------------------------
 474                              Miscellaneous helpers
 475 ---------------------------------------------------------------------------*/
 476 /* Callback for walk_tree.  Used to collect variables referenced in
 477    the function.  */
 478
 479 static tree
 480 find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
 481 {
 482   /* If we are reading the lto info back in, we need to rescan the
 483      referenced vars.  */
 484   if (TREE_CODE (*tp) == SSA_NAME)
 485     add_referenced_var (SSA_NAME_VAR (*tp));
 486
 487   /* If T is a regular variable that the optimizers are interested
 488      in, add it to the list of variables.  */
 489   else if (SSA_VAR_P (*tp))
 490     add_referenced_var (*tp);
 491
 492   /* Type, _DECL and constant nodes have no interesting children.
 493      Ignore them.  */
 494   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
 495     *walk_subtrees = 0;
 496
 497   return NULL_TREE;
 498 }
 499
 500 /* Find referenced variables in STMT.  In contrast with
 501    find_new_referenced_vars, this function will not mark newly found
 502    variables for renaming.  */
 503
 504 void
 505 find_referenced_vars_in (gimple stmt)
 506 {
 507   size_t i;
 508
 509   if (gimple_code (stmt) != GIMPLE_PHI)
 510     {
 511       for (i = 0; i < gimple_num_ops (stmt); i++)
 512         walk_tree (gimple_op_ptr (stmt, i), find_vars_r, NULL, NULL);
 513     }
 514   else
 515     {
 516       walk_tree (gimple_phi_result_ptr (stmt), find_vars_r, NULL, NULL);
 517
 518       for (i = 0; i < gimple_phi_num_args (stmt); i++)
 519         {
 520           tree arg = gimple_phi_arg_def (stmt, i);
 521           walk_tree (&arg, find_vars_r, NULL, NULL);
 522         }
 523     }
 524 }
 525
 526
 527 /* Lookup UID in the referenced_vars hashtable and return the associated
 528    variable.  */
 529
 530 tree
 531 referenced_var_lookup (unsigned int uid)
 532 {
 533   tree h;
 534   struct tree_decl_minimal in;
 535   in.uid = uid;
 536   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 537   gcc_assert (h || uid == 0);
 538   return h;
 539 }
 540
 541 /* Check if TO is in the referenced_vars hash table and insert it if not.
 542    Return true if it required insertion.  */
 543
 544 bool
 545 referenced_var_check_and_insert (tree to)
 546 {
 547   tree h, *loc;
 548   struct tree_decl_minimal in;
 549   unsigned int uid = DECL_UID (to);
 550
 551   in.uid = uid;
 552   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 553   if (h)
 554     {
 555       /* DECL_UID has already been entered in the table.  Verify that it is
 556          the same entry as TO.  See PR 27793.  */
 557       gcc_assert (h == to);
 558       return false;
 559     }
 560
 561   loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun),
 562                                            &in, uid, INSERT);
 563   *loc = to;
 564   return true;
 565 }
 566
 567 /* Lookup VAR UID in the default_defs hashtable and return the associated
 568    variable.  */
 569
 570 tree
 571 gimple_default_def (struct function *fn, tree var)
 572 {
 573   struct tree_decl_minimal ind;
 574   struct tree_ssa_name in;
 575   gcc_assert (SSA_VAR_P (var));
 576   in.var = (tree)&ind;
 577   ind.uid = DECL_UID (var);
 578   return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var));
 579 }
 580
 581 /* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
 582
 583 void
 584 set_default_def (tree var, tree def)
 585 {
 586   struct tree_decl_minimal ind;
 587   struct tree_ssa_name in;
 588   void **loc;
 589
 590   gcc_assert (SSA_VAR_P (var));
 591   in.var = (tree)&ind;
 592   ind.uid = DECL_UID (var);
 593   if (!def)
 594     {
 595       loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 596             DECL_UID (var), INSERT);
 597       gcc_assert (*loc);
 598       htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
 599       return;
 600     }
 601   gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
 602   loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 603                                   DECL_UID (var), INSERT);
 604
 605   /* Default definition might be changed by tail call optimization.  */
 606   if (*loc)
 607     SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false;
 608   *(tree *) loc = def;
 609
 610    /* Mark DEF as the default definition for VAR.  */
 611    SSA_NAME_IS_DEFAULT_DEF (def) = true;
 612 }
 613
 614 /* Add VAR to the list of referenced variables if it isn't already there.  */
 615
 616 bool
 617 add_referenced_var (tree var)
 618 {
 619   var_ann_t v_ann;
 620
 621   v_ann = get_var_ann (var);
 622   gcc_assert (DECL_P (var));
 623
 624   /* Insert VAR into the referenced_vars has table if it isn't present.  */
 625   if (referenced_var_check_and_insert (var))
 626     {
 627       /* Scan DECL_INITIAL for pointer variables as they may contain
 628          address arithmetic referencing the address of other
 629          variables.  As we are only interested in directly referenced
 630          globals or referenced locals restrict this to initializers
 631          than can refer to local variables.  */
 632       if (DECL_INITIAL (var)
 633           && DECL_CONTEXT (var) == current_function_decl)
 634         walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
 635
 636       return true;
 637     }
 638
 639   return false;
 640 }
 641
 642 /* Remove VAR from the list.  */
 643
 644 void
 645 remove_referenced_var (tree var)
 646 {
 647   var_ann_t v_ann;
 648   struct tree_decl_minimal in;
 649   void **loc;
 650   unsigned int uid = DECL_UID (var);
 651
 652   /* Preserve var_anns of globals.  */
 653   if (!is_global_var (var)
 654       && (v_ann = var_ann (var)))
 655     {
 656       ggc_free (v_ann);
 657       var->base.ann = NULL;
 658     }
 659   gcc_assert (DECL_P (var));
 660   in.uid = uid;
 661   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
 662                                   NO_INSERT);
 663   htab_clear_slot (gimple_referenced_vars (cfun), loc);
 664 }
 665
 666
 667 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 668
 669 tree
 670 get_virtual_var (tree var)
 671 {
 672   STRIP_NOPS (var);
 673
 674   if (TREE_CODE (var) == SSA_NAME)
 675     var = SSA_NAME_VAR (var);
 676
 677   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 678          || handled_component_p (var))
 679     var = TREE_OPERAND (var, 0);
 680
 681   /* Treating GIMPLE registers as virtual variables makes no sense.
 682      Also complain if we couldn't extract a _DECL out of the original
 683      expression.  */
 684   gcc_assert (SSA_VAR_P (var));
 685   gcc_assert (!is_gimple_reg (var));
 686
 687   return var;
 688 }
 689
 690 /* Mark all the naked symbols in STMT for SSA renaming.  */
 691
 692 void
 693 mark_symbols_for_renaming (gimple stmt)
 694 {
 695   tree op;
 696   ssa_op_iter iter;
 697
 698   update_stmt (stmt);
 699
 700   /* Mark all the operands for renaming.  */
 701   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 702     if (DECL_P (op))
 703       mark_sym_for_renaming (op);
 704 }
 705
 706
 707 /* Find all variables within the gimplified statement that were not
 708    previously visible to the function and add them to the referenced
 709    variables list.  */
 710
 711 static tree
 712 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 713                             void *data ATTRIBUTE_UNUSED)
 714 {
 715   tree t = *tp;
 716
 717   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 718     {
 719       add_referenced_var (t);
 720       mark_sym_for_renaming (t);
 721     }
 722
 723   if (IS_TYPE_OR_DECL_P (t))
 724     *walk_subtrees = 0;
 725
 726   return NULL;
 727 }
 728
 729
 730 /* Find any new referenced variables in STMT.  */
 731
 732 void
 733 find_new_referenced_vars (gimple stmt)
 734 {
 735   walk_gimple_op (stmt, find_new_referenced_vars_1, NULL);
 736 }
 737
 738
 739 /* If EXP is a handled component reference for a structure, return the
 740    base variable.  The access range is delimited by bit positions *POFFSET and
 741    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 742    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 743    and *PMAX_SIZE are equal, the access is non-variable.  */
 744
 745 tree
 746 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 747                          HOST_WIDE_INT *psize,
 748                          HOST_WIDE_INT *pmax_size)
 749 {
 750   HOST_WIDE_INT bitsize = -1;
 751   HOST_WIDE_INT maxsize = -1;
 752   tree size_tree = NULL_TREE;
 753   HOST_WIDE_INT bit_offset = 0;
 754   bool seen_variable_array_ref = false;
 755
 756   /* First get the final access size from just the outermost expression.  */
 757   if (TREE_CODE (exp) == COMPONENT_REF)
 758     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 759   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 760     size_tree = TREE_OPERAND (exp, 1);
 761   else if (!VOID_TYPE_P (TREE_TYPE (exp)))
 762     {
 763       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 764       if (mode == BLKmode)
 765         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 766       else
 767         bitsize = GET_MODE_BITSIZE (mode);
 768     }
 769   if (size_tree != NULL_TREE)
 770     {
 771       if (! host_integerp (size_tree, 1))
 772         bitsize = -1;
 773       else
 774         bitsize = TREE_INT_CST_LOW (size_tree);
 775     }
 776
 777   /* Initially, maxsize is the same as the accessed element size.
 778      In the following it will only grow (or become -1).  */
 779   maxsize = bitsize;
 780
 781   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 782      and find the ultimate containing object.  */
 783   while (1)
 784     {
 785       switch (TREE_CODE (exp))
 786         {
 787         case BIT_FIELD_REF:
 788           bit_offset += TREE_INT_CST_LOW (TREE_OPERAND (exp, 2));
 789           break;
 790
 791         case COMPONENT_REF:
 792           {
 793             tree field = TREE_OPERAND (exp, 1);
 794             tree this_offset = component_ref_field_offset (exp);
 795
 796             if (this_offset
 797                 && TREE_CODE (this_offset) == INTEGER_CST
 798                 && host_integerp (this_offset, 0))
 799               {
 800                 HOST_WIDE_INT hthis_offset = TREE_INT_CST_LOW (this_offset);
 801                 hthis_offset *= BITS_PER_UNIT;
 802                 hthis_offset
 803                   += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
 804                 bit_offset += hthis_offset;
 805
 806                 /* If we had seen a variable array ref already and we just
 807                    referenced the last field of a struct or a union member
 808                    then we have to adjust maxsize by the padding at the end
 809                    of our field.  */
 810                 if (seen_variable_array_ref
 811                     && maxsize != -1)
 812                   {
 813                     tree stype = TREE_TYPE (TREE_OPERAND (exp, 0));
 814                     tree next = TREE_CHAIN (field);
 815                     while (next && TREE_CODE (next) != FIELD_DECL)
 816                       next = TREE_CHAIN (next);
 817                     if (!next
 818                         || TREE_CODE (stype) != RECORD_TYPE)
 819                       {
 820                         tree fsize = DECL_SIZE_UNIT (field);
 821                         tree ssize = TYPE_SIZE_UNIT (stype);
 822                         if (host_integerp (fsize, 0)
 823                             && host_integerp (ssize, 0))
 824                           maxsize += ((TREE_INT_CST_LOW (ssize)
 825                                        - TREE_INT_CST_LOW (fsize))
 826                                       * BITS_PER_UNIT - hthis_offset);
 827                         else
 828                           maxsize = -1;
 829                       }
 830                   }
 831               }
 832             else
 833               {
 834                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 835                 /* We need to adjust maxsize to the whole structure bitsize.
 836                    But we can subtract any constant offset seen so far,
 837                    because that would get us out of the structure otherwise.  */
 838                 if (maxsize != -1 && csize && host_integerp (csize, 1))
 839                   maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
 840                 else
 841                   maxsize = -1;
 842               }
 843           }
 844           break;
 845
 846         case ARRAY_REF:
 847         case ARRAY_RANGE_REF:
 848           {
 849             tree index = TREE_OPERAND (exp, 1);
 850             tree low_bound, unit_size;
 851
 852             /* If the resulting bit-offset is constant, track it.  */
 853             if (TREE_CODE (index) == INTEGER_CST
 854                 && host_integerp (index, 0)
 855                 && (low_bound = array_ref_low_bound (exp),
 856                     host_integerp (low_bound, 0))
 857                 && (unit_size = array_ref_element_size (exp),
 858                     host_integerp (unit_size, 1)))
 859               {
 860                 HOST_WIDE_INT hindex = TREE_INT_CST_LOW (index);
 861
 862                 hindex -= TREE_INT_CST_LOW (low_bound);
 863                 hindex *= TREE_INT_CST_LOW (unit_size);
 864                 hindex *= BITS_PER_UNIT;
 865                 bit_offset += hindex;
 866
 867                 /* An array ref with a constant index up in the structure
 868                    hierarchy will constrain the size of any variable array ref
 869                    lower in the access hierarchy.  */
 870                 seen_variable_array_ref = false;
 871               }
 872             else
 873               {
 874                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 875                 /* We need to adjust maxsize to the whole array bitsize.
 876                    But we can subtract any constant offset seen so far,
 877                    because that would get us outside of the array otherwise.  */
 878                 if (maxsize != -1 && asize && host_integerp (asize, 1))
 879                   maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
 880                 else
 881                   maxsize = -1;
 882
 883                 /* Remember that we have seen an array ref with a variable
 884                    index.  */
 885                 seen_variable_array_ref = true;
 886               }
 887           }
 888           break;
 889
 890         case REALPART_EXPR:
 891           break;
 892
 893         case IMAGPART_EXPR:
 894           bit_offset += bitsize;
 895           break;
 896
 897         case VIEW_CONVERT_EXPR:
 898           break;
 899
 900         default:
 901           goto done;
 902         }
 903
 904       exp = TREE_OPERAND (exp, 0);
 905     }
 906  done:
 907
 908   /* We need to deal with variable arrays ending structures such as
 909        struct { int length; int a[1]; } x;           x.a[d]
 910        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 911        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 912        struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d]
 913      where we do not know maxsize for variable index accesses to
 914      the array.  The simplest way to conservatively deal with this
 915      is to punt in the case that offset + maxsize reaches the
 916      base type boundary.  This needs to include possible trailing padding
 917      that is there for alignment purposes.  */
 918
 919   if (seen_variable_array_ref
 920       && maxsize != -1
 921       && (!host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
 922           || (bit_offset + maxsize
 923               == (signed) TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))))
 924     maxsize = -1;
 925
 926   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 927      negative bit_offset here.  We might want to store a zero offset
 928      in this case.  */
 929   *poffset = bit_offset;
 930   *psize = bitsize;
 931   *pmax_size = maxsize;
 932
 933   return exp;
 934 }
 935
 936 /* Returns true if STMT references an SSA_NAME that has
 937    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
 938
 939 bool
 940 stmt_references_abnormal_ssa_name (gimple stmt)
 941 {
 942   ssa_op_iter oi;
 943   use_operand_p use_p;
 944
 945   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
 946     {
 947       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
 948         return true;
 949     }
 950
 951   return false;
 952 }
 953