gcc/tree-dfa.c

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