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