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