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   gcc_assert (DECL_P (var));
 584   if (!*DECL_VAR_ANN_PTR (var))
 585     create_var_ann (var);
 586
 587   /* Insert VAR into the referenced_vars hash table if it isn't present.  */
 588   if (referenced_var_check_and_insert (var))
 589     {
 590       /* Scan DECL_INITIAL for pointer variables as they may contain
 591          address arithmetic referencing the address of other
 592          variables.  As we are only interested in directly referenced
 593          globals or referenced locals restrict this to initializers
 594          than can refer to local variables.  */
 595       if (DECL_INITIAL (var)
 596           && DECL_CONTEXT (var) == current_function_decl)
 597         walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
 598
 599       return true;
 600     }
 601
 602   return false;
 603 }
 604
 605 /* Remove VAR from the list.  */
 606
 607 void
 608 remove_referenced_var (tree var)
 609 {
 610   var_ann_t v_ann;
 611   struct tree_decl_minimal in;
 612   void **loc;
 613   unsigned int uid = DECL_UID (var);
 614
 615   /* Preserve var_anns of globals.  */
 616   if (!is_global_var (var)
 617       && (v_ann = var_ann (var)))
 618     {
 619       ggc_free (v_ann);
 620       *DECL_VAR_ANN_PTR (var) = NULL;
 621     }
 622   gcc_assert (DECL_P (var));
 623   in.uid = uid;
 624   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
 625                                   NO_INSERT);
 626   htab_clear_slot (gimple_referenced_vars (cfun), loc);
 627 }
 628
 629
 630 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 631
 632 tree
 633 get_virtual_var (tree var)
 634 {
 635   STRIP_NOPS (var);
 636
 637   if (TREE_CODE (var) == SSA_NAME)
 638     var = SSA_NAME_VAR (var);
 639
 640   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 641          || handled_component_p (var))
 642     var = TREE_OPERAND (var, 0);
 643
 644   /* Treating GIMPLE registers as virtual variables makes no sense.
 645      Also complain if we couldn't extract a _DECL out of the original
 646      expression.  */
 647   gcc_assert (SSA_VAR_P (var));
 648   gcc_assert (!is_gimple_reg (var));
 649
 650   return var;
 651 }
 652
 653 /* Mark all the naked symbols in STMT for SSA renaming.  */
 654
 655 void
 656 mark_symbols_for_renaming (gimple stmt)
 657 {
 658   tree op;
 659   ssa_op_iter iter;
 660
 661   update_stmt (stmt);
 662
 663   /* Mark all the operands for renaming.  */
 664   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 665     if (DECL_P (op))
 666       mark_sym_for_renaming (op);
 667 }
 668
 669
 670 /* Find all variables within the gimplified statement that were not
 671    previously visible to the function and add them to the referenced
 672    variables list.  */
 673
 674 static tree
 675 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 676                             void *data ATTRIBUTE_UNUSED)
 677 {
 678   tree t = *tp;
 679
 680   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 681     {
 682       add_referenced_var (t);
 683       mark_sym_for_renaming (t);
 684     }
 685
 686   if (IS_TYPE_OR_DECL_P (t))
 687     *walk_subtrees = 0;
 688
 689   return NULL;
 690 }
 691
 692
 693 /* Find any new referenced variables in STMT.  */
 694
 695 void
 696 find_new_referenced_vars (gimple stmt)
 697 {
 698   walk_gimple_op (stmt, find_new_referenced_vars_1, NULL);
 699 }
 700
 701
 702 /* If EXP is a handled component reference for a structure, return the
 703    base variable.  The access range is delimited by bit positions *POFFSET and
 704    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 705    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 706    and *PMAX_SIZE are equal, the access is non-variable.  */
 707
 708 tree
 709 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 710                          HOST_WIDE_INT *psize,
 711                          HOST_WIDE_INT *pmax_size)
 712 {
 713   HOST_WIDE_INT bitsize = -1;
 714   HOST_WIDE_INT maxsize = -1;
 715   tree size_tree = NULL_TREE;
 716   HOST_WIDE_INT bit_offset = 0;
 717   bool seen_variable_array_ref = false;
 718   tree base_type;
 719
 720   /* First get the final access size from just the outermost expression.  */
 721   if (TREE_CODE (exp) == COMPONENT_REF)
 722     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 723   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 724     size_tree = TREE_OPERAND (exp, 1);
 725   else if (!VOID_TYPE_P (TREE_TYPE (exp)))
 726     {
 727       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 728       if (mode == BLKmode)
 729         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 730       else
 731         bitsize = GET_MODE_BITSIZE (mode);
 732     }
 733   if (size_tree != NULL_TREE)
 734     {
 735       if (! host_integerp (size_tree, 1))
 736         bitsize = -1;
 737       else
 738         bitsize = TREE_INT_CST_LOW (size_tree);
 739     }
 740
 741   /* Initially, maxsize is the same as the accessed element size.
 742      In the following it will only grow (or become -1).  */
 743   maxsize = bitsize;
 744
 745   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 746      and find the ultimate containing object.  */
 747   while (1)
 748     {
 749       base_type = TREE_TYPE (exp);
 750
 751       switch (TREE_CODE (exp))
 752         {
 753         case BIT_FIELD_REF:
 754           bit_offset += TREE_INT_CST_LOW (TREE_OPERAND (exp, 2));
 755           break;
 756
 757         case COMPONENT_REF:
 758           {
 759             tree field = TREE_OPERAND (exp, 1);
 760             tree this_offset = component_ref_field_offset (exp);
 761
 762             if (this_offset
 763                 && TREE_CODE (this_offset) == INTEGER_CST
 764                 && host_integerp (this_offset, 0))
 765               {
 766                 HOST_WIDE_INT hthis_offset = TREE_INT_CST_LOW (this_offset);
 767                 hthis_offset *= BITS_PER_UNIT;
 768                 hthis_offset
 769                   += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
 770                 bit_offset += hthis_offset;
 771
 772                 /* If we had seen a variable array ref already and we just
 773                    referenced the last field of a struct or a union member
 774                    then we have to adjust maxsize by the padding at the end
 775                    of our field.  */
 776                 if (seen_variable_array_ref
 777                     && maxsize != -1)
 778                   {
 779                     tree stype = TREE_TYPE (TREE_OPERAND (exp, 0));
 780                     tree next = DECL_CHAIN (field);
 781                     while (next && TREE_CODE (next) != FIELD_DECL)
 782                       next = DECL_CHAIN (next);
 783                     if (!next
 784                         || TREE_CODE (stype) != RECORD_TYPE)
 785                       {
 786                         tree fsize = DECL_SIZE_UNIT (field);
 787                         tree ssize = TYPE_SIZE_UNIT (stype);
 788                         if (host_integerp (fsize, 0)
 789                             && host_integerp (ssize, 0))
 790                           maxsize += ((TREE_INT_CST_LOW (ssize)
 791                                        - TREE_INT_CST_LOW (fsize))
 792                                       * BITS_PER_UNIT - hthis_offset);
 793                         else
 794                           maxsize = -1;
 795                       }
 796                   }
 797               }
 798             else
 799               {
 800                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 801                 /* We need to adjust maxsize to the whole structure bitsize.
 802                    But we can subtract any constant offset seen so far,
 803                    because that would get us out of the structure otherwise.  */
 804                 if (maxsize != -1 && csize && host_integerp (csize, 1))
 805                   maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
 806                 else
 807                   maxsize = -1;
 808               }
 809           }
 810           break;
 811
 812         case ARRAY_REF:
 813         case ARRAY_RANGE_REF:
 814           {
 815             tree index = TREE_OPERAND (exp, 1);
 816             tree low_bound, unit_size;
 817
 818             /* If the resulting bit-offset is constant, track it.  */
 819             if (TREE_CODE (index) == INTEGER_CST
 820                 && host_integerp (index, 0)
 821                 && (low_bound = array_ref_low_bound (exp),
 822                     host_integerp (low_bound, 0))
 823                 && (unit_size = array_ref_element_size (exp),
 824                     host_integerp (unit_size, 1)))
 825               {
 826                 HOST_WIDE_INT hindex = TREE_INT_CST_LOW (index);
 827
 828                 hindex -= TREE_INT_CST_LOW (low_bound);
 829                 hindex *= TREE_INT_CST_LOW (unit_size);
 830                 hindex *= BITS_PER_UNIT;
 831                 bit_offset += hindex;
 832
 833                 /* An array ref with a constant index up in the structure
 834                    hierarchy will constrain the size of any variable array ref
 835                    lower in the access hierarchy.  */
 836                 seen_variable_array_ref = false;
 837               }
 838             else
 839               {
 840                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 841                 /* We need to adjust maxsize to the whole array bitsize.
 842                    But we can subtract any constant offset seen so far,
 843                    because that would get us outside of the array otherwise.  */
 844                 if (maxsize != -1 && asize && host_integerp (asize, 1))
 845                   maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
 846                 else
 847                   maxsize = -1;
 848
 849                 /* Remember that we have seen an array ref with a variable
 850                    index.  */
 851                 seen_variable_array_ref = true;
 852               }
 853           }
 854           break;
 855
 856         case REALPART_EXPR:
 857           break;
 858
 859         case IMAGPART_EXPR:
 860           bit_offset += bitsize;
 861           break;
 862
 863         case VIEW_CONVERT_EXPR:
 864           break;
 865
 866         case MEM_REF:
 867           /* Hand back the decl for MEM[&decl, off].  */
 868           if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR)
 869             {
 870               if (integer_zerop (TREE_OPERAND (exp, 1)))
 871                 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 872               else
 873                 {
 874                   double_int off = mem_ref_offset (exp);
 875                   off = double_int_lshift (off,
 876                                            BITS_PER_UNIT == 8
 877                                            ? 3 : exact_log2 (BITS_PER_UNIT),
 878                                            HOST_BITS_PER_DOUBLE_INT, true);
 879                   off = double_int_add (off, shwi_to_double_int (bit_offset));
 880                   if (double_int_fits_in_shwi_p (off))
 881                     {
 882                       bit_offset = double_int_to_shwi (off);
 883                       exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 884                     }
 885                 }
 886             }
 887           goto done;
 888
 889         case TARGET_MEM_REF:
 890           /* Hand back the decl for MEM[&decl, off].  */
 891           if (TREE_CODE (TMR_BASE (exp)) == ADDR_EXPR)
 892             {
 893               /* Via the variable index or index2 we can reach the
 894                  whole object.  */
 895               if (TMR_INDEX (exp) || TMR_INDEX2 (exp))
 896                 {
 897                   exp = TREE_OPERAND (TMR_BASE (exp), 0);
 898                   bit_offset = 0;
 899                   maxsize = -1;
 900                   goto done;
 901                 }
 902               if (integer_zerop (TMR_OFFSET (exp)))
 903                 exp = TREE_OPERAND (TMR_BASE (exp), 0);
 904               else
 905                 {
 906                   double_int off = mem_ref_offset (exp);
 907                   off = double_int_lshift (off,
 908                                            BITS_PER_UNIT == 8
 909                                            ? 3 : exact_log2 (BITS_PER_UNIT),
 910                                            HOST_BITS_PER_DOUBLE_INT, true);
 911                   off = double_int_add (off, shwi_to_double_int (bit_offset));
 912                   if (double_int_fits_in_shwi_p (off))
 913                     {
 914                       bit_offset = double_int_to_shwi (off);
 915                       exp = TREE_OPERAND (TMR_BASE (exp), 0);
 916                     }
 917                 }
 918             }
 919           goto done;
 920
 921         default:
 922           goto done;
 923         }
 924
 925       exp = TREE_OPERAND (exp, 0);
 926     }
 927  done:
 928
 929   /* We need to deal with variable arrays ending structures such as
 930        struct { int length; int a[1]; } x;           x.a[d]
 931        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 932        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 933        struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d]
 934      where we do not know maxsize for variable index accesses to
 935      the array.  The simplest way to conservatively deal with this
 936      is to punt in the case that offset + maxsize reaches the
 937      base type boundary.  This needs to include possible trailing padding
 938      that is there for alignment purposes.  */
 939
 940   if (seen_variable_array_ref
 941       && maxsize != -1
 942       && (!host_integerp (TYPE_SIZE (base_type), 1)
 943           || (bit_offset + maxsize
 944               == (signed) TREE_INT_CST_LOW (TYPE_SIZE (base_type)))))
 945     maxsize = -1;
 946
 947   /* In case of a decl or constant base object we can do better.  */
 948
 949   if (DECL_P (exp))
 950     {
 951       /* If maxsize is unknown adjust it according to the size of the
 952          base decl.  */
 953       if (maxsize == -1
 954           && host_integerp (DECL_SIZE (exp), 1))
 955         maxsize = TREE_INT_CST_LOW (DECL_SIZE (exp)) - bit_offset;
 956     }
 957   else if (CONSTANT_CLASS_P (exp))
 958     {
 959       /* If maxsize is unknown adjust it according to the size of the
 960          base type constant.  */
 961       if (maxsize == -1
 962           && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1))
 963         maxsize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))) - bit_offset;
 964     }
 965
 966   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 967      negative bit_offset here.  We might want to store a zero offset
 968      in this case.  */
 969   *poffset = bit_offset;
 970   *psize = bitsize;
 971   *pmax_size = maxsize;
 972
 973   return exp;
 974 }
 975
 976 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
 977    denotes the starting address of the memory access EXP.
 978    Returns NULL_TREE if the offset is not constant or any component
 979    is not BITS_PER_UNIT-aligned.  */
 980
 981 tree
 982 get_addr_base_and_unit_offset (tree exp, HOST_WIDE_INT *poffset)
 983 {
 984   return get_addr_base_and_unit_offset_1 (exp, poffset, NULL);
 985 }
 986
 987 /* Returns true if STMT references an SSA_NAME that has
 988    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
 989
 990 bool
 991 stmt_references_abnormal_ssa_name (gimple stmt)
 992 {
 993   ssa_op_iter oi;
 994   use_operand_p use_p;
 995
 996   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
 997     {
 998       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
 999         return true;
1000     }
1001
1002   return false;
1003 }