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