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