gcc/tree-dfa.c

   1 /* Data flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010
   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 "toplev.h"
  27 #include "hashtab.h"
  28 #include "pointer-set.h"
  29 #include "tree.h"
  30 #include "tm_p.h"
  31 #include "basic-block.h"
  32 #include "output.h"
  33 #include "timevar.h"
  34 #include "ggc.h"
  35 #include "langhooks.h"
  36 #include "flags.h"
  37 #include "function.h"
  38 #include "tree-pretty-print.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_alloc_cleared_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 DEBUG_FUNCTION 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   if (TREE_CODE (var) == SSA_NAME)
 247     {
 248       if (POINTER_TYPE_P (TREE_TYPE (var)))
 249         dump_points_to_info_for (file, var);
 250       var = SSA_NAME_VAR (var);
 251     }
 252
 253   if (var == NULL_TREE)
 254     {
 255       fprintf (file, "<nil>");
 256       return;
 257     }
 258
 259   print_generic_expr (file, var, dump_flags);
 260
 261   fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
 262   if (DECL_PT_UID (var) != DECL_UID (var))
 263     fprintf (file, ", PT-UID D.%u", (unsigned) DECL_PT_UID (var));
 264
 265   fprintf (file, ", ");
 266   print_generic_expr (file, TREE_TYPE (var), dump_flags);
 267
 268   if (TREE_ADDRESSABLE (var))
 269     fprintf (file, ", is addressable");
 270
 271   if (is_global_var (var))
 272     fprintf (file, ", is global");
 273
 274   if (TREE_THIS_VOLATILE (var))
 275     fprintf (file, ", is volatile");
 276
 277   if (cfun && gimple_default_def (cfun, var))
 278     {
 279       fprintf (file, ", default def: ");
 280       print_generic_expr (file, gimple_default_def (cfun, var), dump_flags);
 281     }
 282
 283   if (DECL_INITIAL (var))
 284     {
 285       fprintf (file, ", initial: ");
 286       print_generic_expr (file, DECL_INITIAL (var), dump_flags);
 287     }
 288
 289   fprintf (file, "\n");
 290 }
 291
 292
 293 /* Dump variable VAR and its may-aliases to stderr.  */
 294
 295 DEBUG_FUNCTION void
 296 debug_variable (tree var)
 297 {
 298   dump_variable (stderr, var);
 299 }
 300
 301
 302 /* Dump various DFA statistics to FILE.  */
 303
 304 void
 305 dump_dfa_stats (FILE *file)
 306 {
 307   struct dfa_stats_d dfa_stats;
 308
 309   unsigned long size, total = 0;
 310   const char * const fmt_str   = "%-30s%-13s%12s\n";
 311   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 312   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 313   const char *funcname
 314     = lang_hooks.decl_printable_name (current_function_decl, 2);
 315
 316   collect_dfa_stats (&dfa_stats);
 317
 318   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 319
 320   fprintf (file, "---------------------------------------------------------\n");
 321   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 322   fprintf (file, fmt_str, "", "  instances  ", "used ");
 323   fprintf (file, "---------------------------------------------------------\n");
 324
 325   size = num_referenced_vars * sizeof (tree);
 326   total += size;
 327   fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
 328            SCALE (size), LABEL (size));
 329
 330   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 331   total += size;
 332   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 333            SCALE (size), LABEL (size));
 334
 335   size = dfa_stats.num_uses * sizeof (tree *);
 336   total += size;
 337   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 338            SCALE (size), LABEL (size));
 339
 340   size = dfa_stats.num_defs * sizeof (tree *);
 341   total += size;
 342   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 343            SCALE (size), LABEL (size));
 344
 345   size = dfa_stats.num_vuses * sizeof (tree *);
 346   total += size;
 347   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 348            SCALE (size), LABEL (size));
 349
 350   size = dfa_stats.num_vdefs * sizeof (tree *);
 351   total += size;
 352   fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
 353            SCALE (size), LABEL (size));
 354
 355   size = dfa_stats.num_phis * sizeof (struct gimple_statement_phi);
 356   total += size;
 357   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 358            SCALE (size), LABEL (size));
 359
 360   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 361   total += size;
 362   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 363            SCALE (size), LABEL (size));
 364
 365   fprintf (file, "---------------------------------------------------------\n");
 366   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 367            LABEL (total));
 368   fprintf (file, "---------------------------------------------------------\n");
 369   fprintf (file, "\n");
 370
 371   if (dfa_stats.num_phis)
 372     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %ld)\n",
 373              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 374              (long) dfa_stats.max_num_phi_args);
 375
 376   fprintf (file, "\n");
 377 }
 378
 379
 380 /* Dump DFA statistics on stderr.  */
 381
 382 DEBUG_FUNCTION void
 383 debug_dfa_stats (void)
 384 {
 385   dump_dfa_stats (stderr);
 386 }
 387
 388
 389 /* Collect DFA statistics and store them in the structure pointed to by
 390    DFA_STATS_P.  */
 391
 392 static void
 393 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED)
 394 {
 395   basic_block bb;
 396   referenced_var_iterator vi;
 397   tree var;
 398
 399   gcc_assert (dfa_stats_p);
 400
 401   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 402
 403   /* Count all the variable annotations.  */
 404   FOR_EACH_REFERENCED_VAR (var, vi)
 405     if (var_ann (var))
 406       dfa_stats_p->num_var_anns++;
 407
 408   /* Walk all the statements in the function counting references.  */
 409   FOR_EACH_BB (bb)
 410     {
 411       gimple_stmt_iterator si;
 412
 413       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
 414         {
 415           gimple phi = gsi_stmt (si);
 416           dfa_stats_p->num_phis++;
 417           dfa_stats_p->num_phi_args += gimple_phi_num_args (phi);
 418           if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args)
 419             dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi);
 420         }
 421
 422       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
 423         {
 424           gimple stmt = gsi_stmt (si);
 425           dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF);
 426           dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE);
 427           dfa_stats_p->num_vdefs += gimple_vdef (stmt) ? 1 : 0;
 428           dfa_stats_p->num_vuses += gimple_vuse (stmt) ? 1 : 0;
 429         }
 430     }
 431 }
 432
 433
 434 /*---------------------------------------------------------------------------
 435                              Miscellaneous helpers
 436 ---------------------------------------------------------------------------*/
 437 /* Callback for walk_tree.  Used to collect variables referenced in
 438    the function.  */
 439
 440 static tree
 441 find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
 442 {
 443   /* If we are reading the lto info back in, we need to rescan the
 444      referenced vars.  */
 445   if (TREE_CODE (*tp) == SSA_NAME)
 446     add_referenced_var (SSA_NAME_VAR (*tp));
 447
 448   /* If T is a regular variable that the optimizers are interested
 449      in, add it to the list of variables.  */
 450   else if (SSA_VAR_P (*tp))
 451     add_referenced_var (*tp);
 452
 453   /* Type, _DECL and constant nodes have no interesting children.
 454      Ignore them.  */
 455   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
 456     *walk_subtrees = 0;
 457
 458   return NULL_TREE;
 459 }
 460
 461 /* Find referenced variables in STMT.  In contrast with
 462    find_new_referenced_vars, this function will not mark newly found
 463    variables for renaming.  */
 464
 465 void
 466 find_referenced_vars_in (gimple stmt)
 467 {
 468   size_t i;
 469
 470   if (gimple_code (stmt) != GIMPLE_PHI)
 471     {
 472       for (i = 0; i < gimple_num_ops (stmt); i++)
 473         walk_tree (gimple_op_ptr (stmt, i), find_vars_r, NULL, NULL);
 474     }
 475   else
 476     {
 477       walk_tree (gimple_phi_result_ptr (stmt), find_vars_r, NULL, NULL);
 478
 479       for (i = 0; i < gimple_phi_num_args (stmt); i++)
 480         {
 481           tree arg = gimple_phi_arg_def (stmt, i);
 482           walk_tree (&arg, find_vars_r, NULL, NULL);
 483         }
 484     }
 485 }
 486
 487
 488 /* Lookup UID in the referenced_vars hashtable and return the associated
 489    variable.  */
 490
 491 tree
 492 referenced_var_lookup (unsigned int uid)
 493 {
 494   tree h;
 495   struct tree_decl_minimal in;
 496   in.uid = uid;
 497   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 498   gcc_assert (h || uid == 0);
 499   return h;
 500 }
 501
 502 /* Check if TO is in the referenced_vars hash table and insert it if not.
 503    Return true if it required insertion.  */
 504
 505 bool
 506 referenced_var_check_and_insert (tree to)
 507 {
 508   tree h, *loc;
 509   struct tree_decl_minimal in;
 510   unsigned int uid = DECL_UID (to);
 511
 512   in.uid = uid;
 513   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 514   if (h)
 515     {
 516       /* DECL_UID has already been entered in the table.  Verify that it is
 517          the same entry as TO.  See PR 27793.  */
 518       gcc_assert (h == to);
 519       return false;
 520     }
 521
 522   loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun),
 523                                            &in, uid, INSERT);
 524   *loc = to;
 525   return true;
 526 }
 527
 528 /* Lookup VAR UID in the default_defs hashtable and return the associated
 529    variable.  */
 530
 531 tree
 532 gimple_default_def (struct function *fn, tree var)
 533 {
 534   struct tree_decl_minimal ind;
 535   struct tree_ssa_name in;
 536   gcc_assert (SSA_VAR_P (var));
 537   in.var = (tree)&ind;
 538   ind.uid = DECL_UID (var);
 539   return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var));
 540 }
 541
 542 /* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
 543
 544 void
 545 set_default_def (tree var, tree def)
 546 {
 547   struct tree_decl_minimal ind;
 548   struct tree_ssa_name in;
 549   void **loc;
 550
 551   gcc_assert (SSA_VAR_P (var));
 552   in.var = (tree)&ind;
 553   ind.uid = DECL_UID (var);
 554   if (!def)
 555     {
 556       loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 557             DECL_UID (var), INSERT);
 558       gcc_assert (*loc);
 559       htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
 560       return;
 561     }
 562   gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
 563   loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 564                                   DECL_UID (var), INSERT);
 565
 566   /* Default definition might be changed by tail call optimization.  */
 567   if (*loc)
 568     SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false;
 569   *(tree *) loc = def;
 570
 571    /* Mark DEF as the default definition for VAR.  */
 572    SSA_NAME_IS_DEFAULT_DEF (def) = true;
 573 }
 574
 575 /* Add VAR to the list of referenced variables if it isn't already there.  */
 576
 577 bool
 578 add_referenced_var (tree var)
 579 {
 580   get_var_ann (var);
 581   gcc_assert (DECL_P (var));
 582
 583   /* Insert VAR into the referenced_vars has table if it isn't present.  */
 584   if (referenced_var_check_and_insert (var))
 585     {
 586       /* Scan DECL_INITIAL for pointer variables as they may contain
 587          address arithmetic referencing the address of other
 588          variables.  As we are only interested in directly referenced
 589          globals or referenced locals restrict this to initializers
 590          than can refer to local variables.  */
 591       if (DECL_INITIAL (var)
 592           && DECL_CONTEXT (var) == current_function_decl)
 593         walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
 594
 595       return true;
 596     }
 597
 598   return false;
 599 }
 600
 601 /* Remove VAR from the list.  */
 602
 603 void
 604 remove_referenced_var (tree var)
 605 {
 606   var_ann_t v_ann;
 607   struct tree_decl_minimal in;
 608   void **loc;
 609   unsigned int uid = DECL_UID (var);
 610
 611   /* Preserve var_anns of globals.  */
 612   if (!is_global_var (var)
 613       && (v_ann = var_ann (var)))
 614     {
 615       ggc_free (v_ann);
 616       *DECL_VAR_ANN_PTR (var) = NULL;
 617     }
 618   gcc_assert (DECL_P (var));
 619   in.uid = uid;
 620   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
 621                                   NO_INSERT);
 622   htab_clear_slot (gimple_referenced_vars (cfun), loc);
 623 }
 624
 625
 626 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 627
 628 tree
 629 get_virtual_var (tree var)
 630 {
 631   STRIP_NOPS (var);
 632
 633   if (TREE_CODE (var) == SSA_NAME)
 634     var = SSA_NAME_VAR (var);
 635
 636   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 637          || handled_component_p (var))
 638     var = TREE_OPERAND (var, 0);
 639
 640   /* Treating GIMPLE registers as virtual variables makes no sense.
 641      Also complain if we couldn't extract a _DECL out of the original
 642      expression.  */
 643   gcc_assert (SSA_VAR_P (var));
 644   gcc_assert (!is_gimple_reg (var));
 645
 646   return var;
 647 }
 648
 649 /* Mark all the naked symbols in STMT for SSA renaming.  */
 650
 651 void
 652 mark_symbols_for_renaming (gimple stmt)
 653 {
 654   tree op;
 655   ssa_op_iter iter;
 656
 657   update_stmt (stmt);
 658
 659   /* Mark all the operands for renaming.  */
 660   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 661     if (DECL_P (op))
 662       mark_sym_for_renaming (op);
 663 }
 664
 665
 666 /* Find all variables within the gimplified statement that were not
 667    previously visible to the function and add them to the referenced
 668    variables list.  */
 669
 670 static tree
 671 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 672                             void *data ATTRIBUTE_UNUSED)
 673 {
 674   tree t = *tp;
 675
 676   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 677     {
 678       add_referenced_var (t);
 679       mark_sym_for_renaming (t);
 680     }
 681
 682   if (IS_TYPE_OR_DECL_P (t))
 683     *walk_subtrees = 0;
 684
 685   return NULL;
 686 }
 687
 688
 689 /* Find any new referenced variables in STMT.  */
 690
 691 void
 692 find_new_referenced_vars (gimple stmt)
 693 {
 694   walk_gimple_op (stmt, find_new_referenced_vars_1, NULL);
 695 }
 696
 697
 698 /* If EXP is a handled component reference for a structure, return the
 699    base variable.  The access range is delimited by bit positions *POFFSET and
 700    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 701    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 702    and *PMAX_SIZE are equal, the access is non-variable.  */
 703
 704 tree
 705 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 706                          HOST_WIDE_INT *psize,
 707                          HOST_WIDE_INT *pmax_size)
 708 {
 709   HOST_WIDE_INT bitsize = -1;
 710   HOST_WIDE_INT maxsize = -1;
 711   tree size_tree = NULL_TREE;
 712   HOST_WIDE_INT bit_offset = 0;
 713   bool seen_variable_array_ref = false;
 714
 715   /* First get the final access size from just the outermost expression.  */
 716   if (TREE_CODE (exp) == COMPONENT_REF)
 717     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 718   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 719     size_tree = TREE_OPERAND (exp, 1);
 720   else if (!VOID_TYPE_P (TREE_TYPE (exp)))
 721     {
 722       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 723       if (mode == BLKmode)
 724         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 725       else
 726         bitsize = GET_MODE_BITSIZE (mode);
 727     }
 728   if (size_tree != NULL_TREE)
 729     {
 730       if (! host_integerp (size_tree, 1))
 731         bitsize = -1;
 732       else
 733         bitsize = TREE_INT_CST_LOW (size_tree);
 734     }
 735
 736   /* Initially, maxsize is the same as the accessed element size.
 737      In the following it will only grow (or become -1).  */
 738   maxsize = bitsize;
 739
 740   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 741      and find the ultimate containing object.  */
 742   while (1)
 743     {
 744       switch (TREE_CODE (exp))
 745         {
 746         case BIT_FIELD_REF:
 747           bit_offset += TREE_INT_CST_LOW (TREE_OPERAND (exp, 2));
 748           break;
 749
 750         case COMPONENT_REF:
 751           {
 752             tree field = TREE_OPERAND (exp, 1);
 753             tree this_offset = component_ref_field_offset (exp);
 754
 755             if (this_offset
 756                 && TREE_CODE (this_offset) == INTEGER_CST
 757                 && host_integerp (this_offset, 0))
 758               {
 759                 HOST_WIDE_INT hthis_offset = TREE_INT_CST_LOW (this_offset);
 760                 hthis_offset *= BITS_PER_UNIT;
 761                 hthis_offset
 762                   += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
 763                 bit_offset += hthis_offset;
 764
 765                 /* If we had seen a variable array ref already and we just
 766                    referenced the last field of a struct or a union member
 767                    then we have to adjust maxsize by the padding at the end
 768                    of our field.  */
 769                 if (seen_variable_array_ref
 770                     && maxsize != -1)
 771                   {
 772                     tree stype = TREE_TYPE (TREE_OPERAND (exp, 0));
 773                     tree next = TREE_CHAIN (field);
 774                     while (next && TREE_CODE (next) != FIELD_DECL)
 775                       next = TREE_CHAIN (next);
 776                     if (!next
 777                         || TREE_CODE (stype) != RECORD_TYPE)
 778                       {
 779                         tree fsize = DECL_SIZE_UNIT (field);
 780                         tree ssize = TYPE_SIZE_UNIT (stype);
 781                         if (host_integerp (fsize, 0)
 782                             && host_integerp (ssize, 0))
 783                           maxsize += ((TREE_INT_CST_LOW (ssize)
 784                                        - TREE_INT_CST_LOW (fsize))
 785                                       * BITS_PER_UNIT - hthis_offset);
 786                         else
 787                           maxsize = -1;
 788                       }
 789                   }
 790               }
 791             else
 792               {
 793                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 794                 /* We need to adjust maxsize to the whole structure bitsize.
 795                    But we can subtract any constant offset seen so far,
 796                    because that would get us out of the structure otherwise.  */
 797                 if (maxsize != -1 && csize && host_integerp (csize, 1))
 798                   maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
 799                 else
 800                   maxsize = -1;
 801               }
 802           }
 803           break;
 804
 805         case ARRAY_REF:
 806         case ARRAY_RANGE_REF:
 807           {
 808             tree index = TREE_OPERAND (exp, 1);
 809             tree low_bound, unit_size;
 810
 811             /* If the resulting bit-offset is constant, track it.  */
 812             if (TREE_CODE (index) == INTEGER_CST
 813                 && host_integerp (index, 0)
 814                 && (low_bound = array_ref_low_bound (exp),
 815                     host_integerp (low_bound, 0))
 816                 && (unit_size = array_ref_element_size (exp),
 817                     host_integerp (unit_size, 1)))
 818               {
 819                 HOST_WIDE_INT hindex = TREE_INT_CST_LOW (index);
 820
 821                 hindex -= TREE_INT_CST_LOW (low_bound);
 822                 hindex *= TREE_INT_CST_LOW (unit_size);
 823                 hindex *= BITS_PER_UNIT;
 824                 bit_offset += hindex;
 825
 826                 /* An array ref with a constant index up in the structure
 827                    hierarchy will constrain the size of any variable array ref
 828                    lower in the access hierarchy.  */
 829                 seen_variable_array_ref = false;
 830               }
 831             else
 832               {
 833                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 834                 /* We need to adjust maxsize to the whole array bitsize.
 835                    But we can subtract any constant offset seen so far,
 836                    because that would get us outside of the array otherwise.  */
 837                 if (maxsize != -1 && asize && host_integerp (asize, 1))
 838                   maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
 839                 else
 840                   maxsize = -1;
 841
 842                 /* Remember that we have seen an array ref with a variable
 843                    index.  */
 844                 seen_variable_array_ref = true;
 845               }
 846           }
 847           break;
 848
 849         case REALPART_EXPR:
 850           break;
 851
 852         case IMAGPART_EXPR:
 853           bit_offset += bitsize;
 854           break;
 855
 856         case VIEW_CONVERT_EXPR:
 857           break;
 858
 859         case MEM_REF:
 860           /* Hand back the decl for MEM[&decl, off].  */
 861           if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR)
 862             {
 863               if (integer_zerop (TREE_OPERAND (exp, 1)))
 864                 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 865               else
 866                 {
 867                   double_int off = mem_ref_offset (exp);
 868                   off = double_int_lshift (off,
 869                                            BITS_PER_UNIT == 8
 870                                            ? 3 : exact_log2 (BITS_PER_UNIT),
 871                                            HOST_BITS_PER_DOUBLE_INT, true);
 872                   off = double_int_add (off, shwi_to_double_int (bit_offset));
 873                   if (double_int_fits_in_shwi_p (off))
 874                     {
 875                       bit_offset = double_int_to_shwi (off);
 876                       exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 877                     }
 878                 }
 879             }
 880           goto done;
 881
 882         default:
 883           goto done;
 884         }
 885
 886       exp = TREE_OPERAND (exp, 0);
 887     }
 888  done:
 889
 890   /* We need to deal with variable arrays ending structures such as
 891        struct { int length; int a[1]; } x;           x.a[d]
 892        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 893        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 894        struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d]
 895      where we do not know maxsize for variable index accesses to
 896      the array.  The simplest way to conservatively deal with this
 897      is to punt in the case that offset + maxsize reaches the
 898      base type boundary.  This needs to include possible trailing padding
 899      that is there for alignment purposes.
 900
 901      That is of course only true if the base object is not a decl.  */
 902
 903   if (DECL_P (exp))
 904     {
 905       /* If maxsize is unknown adjust it according to the size of the
 906          base decl.  */
 907       if (maxsize == -1
 908           && host_integerp (DECL_SIZE (exp), 1))
 909         maxsize = TREE_INT_CST_LOW (DECL_SIZE (exp)) - bit_offset;
 910     }
 911   else if (seen_variable_array_ref
 912            && maxsize != -1
 913            && (!host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
 914                || (bit_offset + maxsize
 915                    == (signed) TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))))
 916     maxsize = -1;
 917
 918   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 919      negative bit_offset here.  We might want to store a zero offset
 920      in this case.  */
 921   *poffset = bit_offset;
 922   *psize = bitsize;
 923   *pmax_size = maxsize;
 924
 925   return exp;
 926 }
 927
 928 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
 929    denotes the starting address of the memory access EXP.
 930    Returns NULL_TREE if the offset is not constant or any component
 931    is not BITS_PER_UNIT-aligned.  */
 932
 933 tree
 934 get_addr_base_and_unit_offset (tree exp, HOST_WIDE_INT *poffset)
 935 {
 936   HOST_WIDE_INT byte_offset = 0;
 937
 938   /* Compute cumulative byte-offset for nested component-refs and array-refs,
 939      and find the ultimate containing object.  */
 940   while (1)
 941     {
 942       switch (TREE_CODE (exp))
 943         {
 944         case BIT_FIELD_REF:
 945           return NULL_TREE;
 946
 947         case COMPONENT_REF:
 948           {
 949             tree field = TREE_OPERAND (exp, 1);
 950             tree this_offset = component_ref_field_offset (exp);
 951             HOST_WIDE_INT hthis_offset;
 952
 953             if (!this_offset
 954                 || TREE_CODE (this_offset) != INTEGER_CST
 955                 || (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
 956                     % BITS_PER_UNIT))
 957               return NULL_TREE;
 958
 959             hthis_offset = TREE_INT_CST_LOW (this_offset);
 960             hthis_offset += (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
 961                              / BITS_PER_UNIT);
 962             byte_offset += hthis_offset;
 963           }
 964           break;
 965
 966         case ARRAY_REF:
 967         case ARRAY_RANGE_REF:
 968           {
 969             tree index = TREE_OPERAND (exp, 1);
 970             tree low_bound, unit_size;
 971
 972             /* If the resulting bit-offset is constant, track it.  */
 973             if (TREE_CODE (index) == INTEGER_CST
 974                 && (low_bound = array_ref_low_bound (exp),
 975                     TREE_CODE (low_bound) == INTEGER_CST)
 976                 && (unit_size = array_ref_element_size (exp),
 977                     TREE_CODE (unit_size) == INTEGER_CST))
 978               {
 979                 HOST_WIDE_INT hindex = TREE_INT_CST_LOW (index);
 980
 981                 hindex -= TREE_INT_CST_LOW (low_bound);
 982                 hindex *= TREE_INT_CST_LOW (unit_size);
 983                 byte_offset += hindex;
 984               }
 985             else
 986               return NULL_TREE;
 987           }
 988           break;
 989
 990         case REALPART_EXPR:
 991           break;
 992
 993         case IMAGPART_EXPR:
 994           byte_offset += TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (exp)));
 995           break;
 996
 997         case VIEW_CONVERT_EXPR:
 998           break;
 999
1000         case MEM_REF:
1001           /* Hand back the decl for MEM[&decl, off].  */
1002           if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR)
1003             {
1004               if (!integer_zerop (TREE_OPERAND (exp, 1)))
1005                 {
1006                   double_int off = mem_ref_offset (exp);
1007                   gcc_assert (off.high == -1 || off.high == 0);
1008                   byte_offset += double_int_to_shwi (off);
1009                 }
1010               exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
1011             }
1012           goto done;
1013
1014         default:
1015           goto done;
1016         }
1017
1018       exp = TREE_OPERAND (exp, 0);
1019     }
1020 done:
1021
1022   *poffset = byte_offset;
1023   return exp;
1024 }
1025
1026 /* Returns true if STMT references an SSA_NAME that has
1027    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
1028
1029 bool
1030 stmt_references_abnormal_ssa_name (gimple stmt)
1031 {
1032   ssa_op_iter oi;
1033   use_operand_p use_p;
1034
1035   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
1036     {
1037       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
1038         return true;
1039     }
1040
1041   return false;
1042 }
1043