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