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