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