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 && ann->noalias_state == NO_ALIAS)
 279     fprintf (file, ", NO_ALIAS (does not alias other NO_ALIAS symbols)");
 280   else if (ann && 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 && ann->noalias_state == NO_ALIAS_ANYTHING)
 284     fprintf (file, ", NO_ALIAS_ANYTHING (does not alias any other symbols)");
 285
 286   if (cfun && 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   if (DECL_INITIAL (var))
 293     {
 294       fprintf (file, ", initial: ");
 295       print_generic_expr (file, DECL_INITIAL (var), dump_flags);
 296     }
 297
 298   fprintf (file, "\n");
 299 }
 300
 301
 302 /* Dump variable VAR and its may-aliases to stderr.  */
 303
 304 void
 305 debug_variable (tree var)
 306 {
 307   dump_variable (stderr, var);
 308 }
 309
 310
 311 /* Dump various DFA statistics to FILE.  */
 312
 313 void
 314 dump_dfa_stats (FILE *file)
 315 {
 316   struct dfa_stats_d dfa_stats;
 317
 318   unsigned long size, total = 0;
 319   const char * const fmt_str   = "%-30s%-13s%12s\n";
 320   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 321   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 322   const char *funcname
 323     = lang_hooks.decl_printable_name (current_function_decl, 2);
 324
 325   collect_dfa_stats (&dfa_stats);
 326
 327   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 328
 329   fprintf (file, "---------------------------------------------------------\n");
 330   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 331   fprintf (file, fmt_str, "", "  instances  ", "used ");
 332   fprintf (file, "---------------------------------------------------------\n");
 333
 334   size = num_referenced_vars * sizeof (tree);
 335   total += size;
 336   fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
 337            SCALE (size), LABEL (size));
 338
 339   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 340   total += size;
 341   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 342            SCALE (size), LABEL (size));
 343
 344   size = dfa_stats.num_uses * sizeof (tree *);
 345   total += size;
 346   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 347            SCALE (size), LABEL (size));
 348
 349   size = dfa_stats.num_defs * sizeof (tree *);
 350   total += size;
 351   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 352            SCALE (size), LABEL (size));
 353
 354   size = dfa_stats.num_vuses * sizeof (tree *);
 355   total += size;
 356   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 357            SCALE (size), LABEL (size));
 358
 359   size = dfa_stats.num_vdefs * sizeof (tree *);
 360   total += size;
 361   fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
 362            SCALE (size), LABEL (size));
 363
 364   size = dfa_stats.num_phis * sizeof (struct gimple_statement_phi);
 365   total += size;
 366   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 367            SCALE (size), LABEL (size));
 368
 369   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 370   total += size;
 371   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 372            SCALE (size), LABEL (size));
 373
 374   fprintf (file, "---------------------------------------------------------\n");
 375   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 376            LABEL (total));
 377   fprintf (file, "---------------------------------------------------------\n");
 378   fprintf (file, "\n");
 379
 380   if (dfa_stats.num_phis)
 381     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %ld)\n",
 382              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 383              (long) dfa_stats.max_num_phi_args);
 384
 385   fprintf (file, "\n");
 386 }
 387
 388
 389 /* Dump DFA statistics on stderr.  */
 390
 391 void
 392 debug_dfa_stats (void)
 393 {
 394   dump_dfa_stats (stderr);
 395 }
 396
 397
 398 /* Collect DFA statistics and store them in the structure pointed to by
 399    DFA_STATS_P.  */
 400
 401 static void
 402 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED)
 403 {
 404   basic_block bb;
 405   referenced_var_iterator vi;
 406   tree var;
 407
 408   gcc_assert (dfa_stats_p);
 409
 410   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 411
 412   /* Count all the variable annotations.  */
 413   FOR_EACH_REFERENCED_VAR (var, vi)
 414     if (var_ann (var))
 415       dfa_stats_p->num_var_anns++;
 416
 417   /* Walk all the statements in the function counting references.  */
 418   FOR_EACH_BB (bb)
 419     {
 420       gimple_stmt_iterator si;
 421
 422       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
 423         {
 424           gimple phi = gsi_stmt (si);
 425           dfa_stats_p->num_phis++;
 426           dfa_stats_p->num_phi_args += gimple_phi_num_args (phi);
 427           if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args)
 428             dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi);
 429         }
 430
 431       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
 432         {
 433           gimple stmt = gsi_stmt (si);
 434           dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF);
 435           dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE);
 436           dfa_stats_p->num_vdefs += gimple_vdef (stmt) ? 1 : 0;
 437           dfa_stats_p->num_vuses += gimple_vuse (stmt) ? 1 : 0;
 438         }
 439     }
 440 }
 441
 442
 443 /*---------------------------------------------------------------------------
 444                              Miscellaneous helpers
 445 ---------------------------------------------------------------------------*/
 446 /* Callback for walk_tree.  Used to collect variables referenced in
 447    the function.  */
 448
 449 static tree
 450 find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
 451 {
 452   /* If we are reading the lto info back in, we need to rescan the
 453      referenced vars.  */
 454   if (TREE_CODE (*tp) == SSA_NAME)
 455     add_referenced_var (SSA_NAME_VAR (*tp));
 456
 457   /* If T is a regular variable that the optimizers are interested
 458      in, add it to the list of variables.  */
 459   else if (SSA_VAR_P (*tp))
 460     add_referenced_var (*tp);
 461
 462   /* Type, _DECL and constant nodes have no interesting children.
 463      Ignore them.  */
 464   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
 465     *walk_subtrees = 0;
 466
 467   return NULL_TREE;
 468 }
 469
 470 /* Find referenced variables in STMT.  In contrast with
 471    find_new_referenced_vars, this function will not mark newly found
 472    variables for renaming.  */
 473
 474 void
 475 find_referenced_vars_in (gimple stmt)
 476 {
 477   size_t i;
 478
 479   if (gimple_code (stmt) != GIMPLE_PHI)
 480     {
 481       for (i = 0; i < gimple_num_ops (stmt); i++)
 482         walk_tree (gimple_op_ptr (stmt, i), find_vars_r, NULL, NULL);
 483     }
 484   else
 485     {
 486       walk_tree (gimple_phi_result_ptr (stmt), find_vars_r, NULL, NULL);
 487
 488       for (i = 0; i < gimple_phi_num_args (stmt); i++)
 489         {
 490           tree arg = gimple_phi_arg_def (stmt, i);
 491           walk_tree (&arg, find_vars_r, NULL, NULL);
 492         }
 493     }
 494 }
 495
 496
 497 /* Lookup UID in the referenced_vars hashtable and return the associated
 498    variable.  */
 499
 500 tree
 501 referenced_var_lookup (unsigned int uid)
 502 {
 503   tree h;
 504   struct tree_decl_minimal in;
 505   in.uid = uid;
 506   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 507   gcc_assert (h || uid == 0);
 508   return h;
 509 }
 510
 511 /* Check if TO is in the referenced_vars hash table and insert it if not.
 512    Return true if it required insertion.  */
 513
 514 bool
 515 referenced_var_check_and_insert (tree to)
 516 {
 517   tree h, *loc;
 518   struct tree_decl_minimal in;
 519   unsigned int uid = DECL_UID (to);
 520
 521   in.uid = uid;
 522   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 523   if (h)
 524     {
 525       /* DECL_UID has already been entered in the table.  Verify that it is
 526          the same entry as TO.  See PR 27793.  */
 527       gcc_assert (h == to);
 528       return false;
 529     }
 530
 531   loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun),
 532                                            &in, uid, INSERT);
 533   *loc = to;
 534   return true;
 535 }
 536
 537 /* Lookup VAR UID in the default_defs hashtable and return the associated
 538    variable.  */
 539
 540 tree
 541 gimple_default_def (struct function *fn, tree var)
 542 {
 543   struct tree_decl_minimal ind;
 544   struct tree_ssa_name in;
 545   gcc_assert (SSA_VAR_P (var));
 546   in.var = (tree)&ind;
 547   ind.uid = DECL_UID (var);
 548   return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var));
 549 }
 550
 551 /* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
 552
 553 void
 554 set_default_def (tree var, tree def)
 555 {
 556   struct tree_decl_minimal ind;
 557   struct tree_ssa_name in;
 558   void **loc;
 559
 560   gcc_assert (SSA_VAR_P (var));
 561   in.var = (tree)&ind;
 562   ind.uid = DECL_UID (var);
 563   if (!def)
 564     {
 565       loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 566             DECL_UID (var), INSERT);
 567       gcc_assert (*loc);
 568       htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
 569       return;
 570     }
 571   gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
 572   loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 573                                   DECL_UID (var), INSERT);
 574
 575   /* Default definition might be changed by tail call optimization.  */
 576   if (*loc)
 577     SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false;
 578   *(tree *) loc = def;
 579
 580    /* Mark DEF as the default definition for VAR.  */
 581    SSA_NAME_IS_DEFAULT_DEF (def) = true;
 582 }
 583
 584 /* Add VAR to the list of referenced variables if it isn't already there.  */
 585
 586 bool
 587 add_referenced_var (tree var)
 588 {
 589   var_ann_t v_ann;
 590
 591   v_ann = 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       var->base.ann = 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   bool seen_union = false;
 726
 727   /* First get the final access size from just the outermost expression.  */
 728   if (TREE_CODE (exp) == COMPONENT_REF)
 729     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 730   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 731     size_tree = TREE_OPERAND (exp, 1);
 732   else
 733     {
 734       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 735       if (mode == BLKmode)
 736         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 737       else
 738         bitsize = GET_MODE_BITSIZE (mode);
 739     }
 740   if (size_tree != NULL_TREE)
 741     {
 742       if (! host_integerp (size_tree, 1))
 743         bitsize = -1;
 744       else
 745         bitsize = TREE_INT_CST_LOW (size_tree);
 746     }
 747
 748   /* Initially, maxsize is the same as the accessed element size.
 749      In the following it will only grow (or become -1).  */
 750   maxsize = bitsize;
 751
 752   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 753      and find the ultimate containing object.  */
 754   while (1)
 755     {
 756       switch (TREE_CODE (exp))
 757         {
 758         case BIT_FIELD_REF:
 759           bit_offset += TREE_INT_CST_LOW (TREE_OPERAND (exp, 2));
 760           break;
 761
 762         case COMPONENT_REF:
 763           {
 764             tree field = TREE_OPERAND (exp, 1);
 765             tree this_offset = component_ref_field_offset (exp);
 766
 767             if (TREE_CODE (TREE_TYPE (TREE_OPERAND (exp, 0))) == UNION_TYPE)
 768               seen_union = true;
 769
 770             if (this_offset
 771                 && TREE_CODE (this_offset) == INTEGER_CST
 772                 && host_integerp (this_offset, 0))
 773               {
 774                 HOST_WIDE_INT hthis_offset = TREE_INT_CST_LOW (this_offset);
 775                 hthis_offset *= BITS_PER_UNIT;
 776                 bit_offset += hthis_offset;
 777                 bit_offset += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
 778               }
 779             else
 780               {
 781                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 782                 /* We need to adjust maxsize to the whole structure bitsize.
 783                    But we can subtract any constant offset seen so far,
 784                    because that would get us out of the structure otherwise.  */
 785                 if (maxsize != -1 && csize && host_integerp (csize, 1))
 786                   maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
 787                 else
 788                   maxsize = -1;
 789               }
 790           }
 791           break;
 792
 793         case ARRAY_REF:
 794         case ARRAY_RANGE_REF:
 795           {
 796             tree index = TREE_OPERAND (exp, 1);
 797             tree low_bound, unit_size;
 798
 799             /* If the resulting bit-offset is constant, track it.  */
 800             if (TREE_CODE (index) == INTEGER_CST
 801                 && host_integerp (index, 0)
 802                 && (low_bound = array_ref_low_bound (exp),
 803                     host_integerp (low_bound, 0))
 804                 && (unit_size = array_ref_element_size (exp),
 805                     host_integerp (unit_size, 1)))
 806               {
 807                 HOST_WIDE_INT hindex = TREE_INT_CST_LOW (index);
 808
 809                 hindex -= TREE_INT_CST_LOW (low_bound);
 810                 hindex *= TREE_INT_CST_LOW (unit_size);
 811                 hindex *= BITS_PER_UNIT;
 812                 bit_offset += hindex;
 813
 814                 /* An array ref with a constant index up in the structure
 815                    hierarchy will constrain the size of any variable array ref
 816                    lower in the access hierarchy.  */
 817                 seen_variable_array_ref = false;
 818               }
 819             else
 820               {
 821                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 822                 /* We need to adjust maxsize to the whole array bitsize.
 823                    But we can subtract any constant offset seen so far,
 824                    because that would get us outside of the array otherwise.  */
 825                 if (maxsize != -1 && asize && host_integerp (asize, 1))
 826                   maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
 827                 else
 828                   maxsize = -1;
 829
 830                 /* Remember that we have seen an array ref with a variable
 831                    index.  */
 832                 seen_variable_array_ref = true;
 833               }
 834           }
 835           break;
 836
 837         case REALPART_EXPR:
 838           break;
 839
 840         case IMAGPART_EXPR:
 841           bit_offset += bitsize;
 842           break;
 843
 844         case VIEW_CONVERT_EXPR:
 845           /* ???  We probably should give up here and bail out.  */
 846           break;
 847
 848         default:
 849           goto done;
 850         }
 851
 852       exp = TREE_OPERAND (exp, 0);
 853     }
 854  done:
 855
 856   /* We need to deal with variable arrays ending structures such as
 857        struct { int length; int a[1]; } x;           x.a[d]
 858        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 859        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 860      where we do not know maxsize for variable index accesses to
 861      the array.  The simplest way to conservatively deal with this
 862      is to punt in the case that offset + maxsize reaches the
 863      base type boundary.
 864
 865      Unfortunately this is difficult to determine reliably when unions are
 866      involved and so we are conservative in such cases.
 867
 868      FIXME: This approach may be too conservative, we probably want to at least
 869      check that the union is the last field/element at its level or even
 870      propagate the calculated offsets back up the access chain and check
 871      there.  */
 872
 873   if (seen_variable_array_ref
 874       && (seen_union
 875           || (maxsize != -1
 876               && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
 877               && bit_offset + maxsize
 878               == (signed) TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))))
 879     maxsize = -1;
 880
 881   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 882      negative bit_offset here.  We might want to store a zero offset
 883      in this case.  */
 884   *poffset = bit_offset;
 885   *psize = bitsize;
 886   *pmax_size = maxsize;
 887
 888   return exp;
 889 }
 890
 891 /* Returns true if STMT references an SSA_NAME that has
 892    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
 893
 894 bool
 895 stmt_references_abnormal_ssa_name (gimple stmt)
 896 {
 897   ssa_op_iter oi;
 898   use_operand_p use_p;
 899
 900   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
 901     {
 902       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
 903         return true;
 904     }
 905
 906   return false;
 907 }
 908