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   double_int bit_offset = double_int_zero;
 717   HOST_WIDE_INT hbit_offset;
 718   bool seen_variable_array_ref = false;
 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       switch (TREE_CODE (exp))
 750         {
 751         case BIT_FIELD_REF:
 752           bit_offset
 753             = double_int_add (bit_offset,
 754                               tree_to_double_int (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 && TREE_CODE (this_offset) == INTEGER_CST)
 763               {
 764                 double_int doffset = tree_to_double_int (this_offset);
 765                 doffset = double_int_lshift (doffset,
 766                                              BITS_PER_UNIT == 8
 767                                              ? 3 : exact_log2 (BITS_PER_UNIT),
 768                                              HOST_BITS_PER_DOUBLE_INT, true);
 769                 doffset = double_int_add (doffset,
 770                                           tree_to_double_int
 771                                           (DECL_FIELD_BIT_OFFSET (field)));
 772                 bit_offset = double_int_add (bit_offset, doffset);
 773
 774                 /* If we had seen a variable array ref already and we just
 775                    referenced the last field of a struct or a union member
 776                    then we have to adjust maxsize by the padding at the end
 777                    of our field.  */
 778                 if (seen_variable_array_ref && maxsize != -1)
 779                   {
 780                     tree stype = TREE_TYPE (TREE_OPERAND (exp, 0));
 781                     tree next = DECL_CHAIN (field);
 782                     while (next && TREE_CODE (next) != FIELD_DECL)
 783                       next = DECL_CHAIN (next);
 784                     if (!next
 785                         || TREE_CODE (stype) != RECORD_TYPE)
 786                       {
 787                         tree fsize = DECL_SIZE_UNIT (field);
 788                         tree ssize = TYPE_SIZE_UNIT (stype);
 789                         if (host_integerp (fsize, 0)
 790                             && host_integerp (ssize, 0)
 791                             && double_int_fits_in_shwi_p (doffset))
 792                           maxsize += ((TREE_INT_CST_LOW (ssize)
 793                                        - TREE_INT_CST_LOW (fsize))
 794                                       * BITS_PER_UNIT
 795                                         - double_int_to_shwi (doffset));
 796                         else
 797                           maxsize = -1;
 798                       }
 799                   }
 800               }
 801             else
 802               {
 803                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 804                 /* We need to adjust maxsize to the whole structure bitsize.
 805                    But we can subtract any constant offset seen so far,
 806                    because that would get us out of the structure otherwise.  */
 807                 if (maxsize != -1
 808                     && csize
 809                     && host_integerp (csize, 1)
 810                     && double_int_fits_in_shwi_p (bit_offset))
 811                   maxsize = TREE_INT_CST_LOW (csize)
 812                             - double_int_to_shwi (bit_offset);
 813                 else
 814                   maxsize = -1;
 815               }
 816           }
 817           break;
 818
 819         case ARRAY_REF:
 820         case ARRAY_RANGE_REF:
 821           {
 822             tree index = TREE_OPERAND (exp, 1);
 823             tree low_bound, unit_size;
 824
 825             /* If the resulting bit-offset is constant, track it.  */
 826             if (TREE_CODE (index) == INTEGER_CST
 827                 && (low_bound = array_ref_low_bound (exp),
 828                     TREE_CODE (low_bound) == INTEGER_CST)
 829                 && (unit_size = array_ref_element_size (exp),
 830                     TREE_CODE (unit_size) == INTEGER_CST))
 831               {
 832                 double_int doffset
 833                   = double_int_sext
 834                     (double_int_sub (TREE_INT_CST (index),
 835                                      TREE_INT_CST (low_bound)),
 836                      TYPE_PRECISION (TREE_TYPE (index)));
 837                 doffset = double_int_mul (doffset,
 838                                           tree_to_double_int (unit_size));
 839                 doffset = double_int_lshift (doffset,
 840                                              BITS_PER_UNIT == 8
 841                                              ? 3 : exact_log2 (BITS_PER_UNIT),
 842                                              HOST_BITS_PER_DOUBLE_INT, true);
 843                 bit_offset = double_int_add (bit_offset, doffset);
 844
 845                 /* An array ref with a constant index up in the structure
 846                    hierarchy will constrain the size of any variable array ref
 847                    lower in the access hierarchy.  */
 848                 seen_variable_array_ref = false;
 849               }
 850             else
 851               {
 852                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 853                 /* We need to adjust maxsize to the whole array bitsize.
 854                    But we can subtract any constant offset seen so far,
 855                    because that would get us outside of the array otherwise.  */
 856                 if (maxsize != -1
 857                     && asize
 858                     && host_integerp (asize, 1)
 859                     && double_int_fits_in_shwi_p (bit_offset))
 860                   maxsize = TREE_INT_CST_LOW (asize)
 861                             - double_int_to_shwi (bit_offset);
 862                 else
 863                   maxsize = -1;
 864
 865                 /* Remember that we have seen an array ref with a variable
 866                    index.  */
 867                 seen_variable_array_ref = true;
 868               }
 869           }
 870           break;
 871
 872         case REALPART_EXPR:
 873           break;
 874
 875         case IMAGPART_EXPR:
 876           bit_offset
 877             = double_int_add (bit_offset, uhwi_to_double_int (bitsize));
 878           break;
 879
 880         case VIEW_CONVERT_EXPR:
 881           break;
 882
 883         case TARGET_MEM_REF:
 884           /* Via the variable index or index2 we can reach the
 885              whole object.  Still hand back the decl here.  */
 886           if (TREE_CODE (TMR_BASE (exp)) == ADDR_EXPR
 887               && (TMR_INDEX (exp) || TMR_INDEX2 (exp)))
 888             {
 889               exp = TREE_OPERAND (TMR_BASE (exp), 0);
 890               bit_offset = double_int_zero;
 891               maxsize = -1;
 892               goto done;
 893             }
 894           /* Fallthru.  */
 895         case MEM_REF:
 896           /* We need to deal with variable arrays ending structures such as
 897              struct { int length; int a[1]; } x;           x.a[d]
 898              struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 899              struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 900              struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d]
 901              where we do not know maxsize for variable index accesses to
 902              the array.  The simplest way to conservatively deal with this
 903              is to punt in the case that offset + maxsize reaches the
 904              base type boundary.  This needs to include possible trailing
 905              padding that is there for alignment purposes.  */
 906           if (seen_variable_array_ref
 907               && maxsize != -1
 908               && (!double_int_fits_in_shwi_p (bit_offset)
 909                   || !host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
 910                   || (double_int_to_shwi (bit_offset) + maxsize
 911                       == (HOST_WIDE_INT) TREE_INT_CST_LOW
 912                             (TYPE_SIZE (TREE_TYPE (exp))))))
 913             maxsize = -1;
 914
 915           /* Hand back the decl for MEM[&decl, off].  */
 916           if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR)
 917             {
 918               if (integer_zerop (TREE_OPERAND (exp, 1)))
 919                 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 920               else
 921                 {
 922                   double_int off = mem_ref_offset (exp);
 923                   off = double_int_lshift (off,
 924                                            BITS_PER_UNIT == 8
 925                                            ? 3 : exact_log2 (BITS_PER_UNIT),
 926                                            HOST_BITS_PER_DOUBLE_INT, true);
 927                   off = double_int_add (off, bit_offset);
 928                   if (double_int_fits_in_shwi_p (off))
 929                     {
 930                       bit_offset = off;
 931                       exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 932                     }
 933                 }
 934             }
 935           goto done;
 936
 937         default:
 938           goto done;
 939         }
 940
 941       exp = TREE_OPERAND (exp, 0);
 942     }
 943
 944   /* We need to deal with variable arrays ending structures.  */
 945   if (seen_variable_array_ref
 946       && maxsize != -1
 947       && (!double_int_fits_in_shwi_p (bit_offset)
 948           || !host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
 949           || (double_int_to_shwi (bit_offset) + maxsize
 950               == (HOST_WIDE_INT)
 951                    TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))))
 952     maxsize = -1;
 953
 954  done:
 955   if (!double_int_fits_in_shwi_p (bit_offset))
 956     {
 957       *poffset = 0;
 958       *psize = bitsize;
 959       *pmax_size = -1;
 960
 961       return exp;
 962     }
 963
 964   hbit_offset = double_int_to_shwi (bit_offset);
 965
 966   /* In case of a decl or constant base object we can do better.  */
 967
 968   if (DECL_P (exp))
 969     {
 970       /* If maxsize is unknown adjust it according to the size of the
 971          base decl.  */
 972       if (maxsize == -1
 973           && host_integerp (DECL_SIZE (exp), 1))
 974         maxsize = TREE_INT_CST_LOW (DECL_SIZE (exp)) - hbit_offset;
 975     }
 976   else if (CONSTANT_CLASS_P (exp))
 977     {
 978       /* If maxsize is unknown adjust it according to the size of the
 979          base type constant.  */
 980       if (maxsize == -1
 981           && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1))
 982         maxsize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))) - hbit_offset;
 983     }
 984
 985   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 986      negative bit_offset here.  We might want to store a zero offset
 987      in this case.  */
 988   *poffset = hbit_offset;
 989   *psize = bitsize;
 990   *pmax_size = maxsize;
 991
 992   return exp;
 993 }
 994
 995 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
 996    denotes the starting address of the memory access EXP.
 997    Returns NULL_TREE if the offset is not constant or any component
 998    is not BITS_PER_UNIT-aligned.  */
 999
1000 tree
1001 get_addr_base_and_unit_offset (tree exp, HOST_WIDE_INT *poffset)
1002 {
1003   return get_addr_base_and_unit_offset_1 (exp, poffset, NULL);
1004 }
1005
1006 /* Returns true if STMT references an SSA_NAME that has
1007    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
1008
1009 bool
1010 stmt_references_abnormal_ssa_name (gimple stmt)
1011 {
1012   ssa_op_iter oi;
1013   use_operand_p use_p;
1014
1015   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
1016     {
1017       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
1018         return true;
1019     }
1020
1021   return false;
1022 }