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