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