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