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