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