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   TODO_dump_func,                       /* todo_flags_start */
 117   TODO_dump_func                        /* 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
 718   /* First get the final access size from just the outermost expression.  */
 719   if (TREE_CODE (exp) == COMPONENT_REF)
 720     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 721   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 722     size_tree = TREE_OPERAND (exp, 1);
 723   else if (!VOID_TYPE_P (TREE_TYPE (exp)))
 724     {
 725       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 726       if (mode == BLKmode)
 727         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 728       else
 729         bitsize = GET_MODE_BITSIZE (mode);
 730     }
 731   if (size_tree != NULL_TREE)
 732     {
 733       if (! host_integerp (size_tree, 1))
 734         bitsize = -1;
 735       else
 736         bitsize = TREE_INT_CST_LOW (size_tree);
 737     }
 738
 739   /* Initially, maxsize is the same as the accessed element size.
 740      In the following it will only grow (or become -1).  */
 741   maxsize = bitsize;
 742
 743   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 744      and find the ultimate containing object.  */
 745   while (1)
 746     {
 747       switch (TREE_CODE (exp))
 748         {
 749         case BIT_FIELD_REF:
 750           bit_offset += TREE_INT_CST_LOW (TREE_OPERAND (exp, 2));
 751           break;
 752
 753         case COMPONENT_REF:
 754           {
 755             tree field = TREE_OPERAND (exp, 1);
 756             tree this_offset = component_ref_field_offset (exp);
 757
 758             if (this_offset
 759                 && TREE_CODE (this_offset) == INTEGER_CST
 760                 && host_integerp (this_offset, 0))
 761               {
 762                 HOST_WIDE_INT hthis_offset = TREE_INT_CST_LOW (this_offset);
 763                 hthis_offset *= BITS_PER_UNIT;
 764                 hthis_offset
 765                   += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
 766                 bit_offset += hthis_offset;
 767
 768                 /* If we had seen a variable array ref already and we just
 769                    referenced the last field of a struct or a union member
 770                    then we have to adjust maxsize by the padding at the end
 771                    of our field.  */
 772                 if (seen_variable_array_ref
 773                     && maxsize != -1)
 774                   {
 775                     tree stype = TREE_TYPE (TREE_OPERAND (exp, 0));
 776                     tree next = DECL_CHAIN (field);
 777                     while (next && TREE_CODE (next) != FIELD_DECL)
 778                       next = DECL_CHAIN (next);
 779                     if (!next
 780                         || TREE_CODE (stype) != RECORD_TYPE)
 781                       {
 782                         tree fsize = DECL_SIZE_UNIT (field);
 783                         tree ssize = TYPE_SIZE_UNIT (stype);
 784                         if (host_integerp (fsize, 0)
 785                             && host_integerp (ssize, 0))
 786                           maxsize += ((TREE_INT_CST_LOW (ssize)
 787                                        - TREE_INT_CST_LOW (fsize))
 788                                       * BITS_PER_UNIT - hthis_offset);
 789                         else
 790                           maxsize = -1;
 791                       }
 792                   }
 793               }
 794             else
 795               {
 796                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 797                 /* We need to adjust maxsize to the whole structure bitsize.
 798                    But we can subtract any constant offset seen so far,
 799                    because that would get us out of the structure otherwise.  */
 800                 if (maxsize != -1 && csize && host_integerp (csize, 1))
 801                   maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
 802                 else
 803                   maxsize = -1;
 804               }
 805           }
 806           break;
 807
 808         case ARRAY_REF:
 809         case ARRAY_RANGE_REF:
 810           {
 811             tree index = TREE_OPERAND (exp, 1);
 812             tree low_bound, unit_size;
 813
 814             /* If the resulting bit-offset is constant, track it.  */
 815             if (TREE_CODE (index) == INTEGER_CST
 816                 && host_integerp (index, 0)
 817                 && (low_bound = array_ref_low_bound (exp),
 818                     host_integerp (low_bound, 0))
 819                 && (unit_size = array_ref_element_size (exp),
 820                     host_integerp (unit_size, 1)))
 821               {
 822                 HOST_WIDE_INT hindex = TREE_INT_CST_LOW (index);
 823
 824                 hindex -= TREE_INT_CST_LOW (low_bound);
 825                 hindex *= TREE_INT_CST_LOW (unit_size);
 826                 hindex *= BITS_PER_UNIT;
 827                 bit_offset += hindex;
 828
 829                 /* An array ref with a constant index up in the structure
 830                    hierarchy will constrain the size of any variable array ref
 831                    lower in the access hierarchy.  */
 832                 seen_variable_array_ref = false;
 833               }
 834             else
 835               {
 836                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 837                 /* We need to adjust maxsize to the whole array bitsize.
 838                    But we can subtract any constant offset seen so far,
 839                    because that would get us outside of the array otherwise.  */
 840                 if (maxsize != -1 && asize && host_integerp (asize, 1))
 841                   maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
 842                 else
 843                   maxsize = -1;
 844
 845                 /* Remember that we have seen an array ref with a variable
 846                    index.  */
 847                 seen_variable_array_ref = true;
 848               }
 849           }
 850           break;
 851
 852         case REALPART_EXPR:
 853           break;
 854
 855         case IMAGPART_EXPR:
 856           bit_offset += bitsize;
 857           break;
 858
 859         case VIEW_CONVERT_EXPR:
 860           break;
 861
 862         case MEM_REF:
 863           /* Hand back the decl for MEM[&decl, off].  */
 864           if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR)
 865             {
 866               if (integer_zerop (TREE_OPERAND (exp, 1)))
 867                 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 868               else
 869                 {
 870                   double_int off = mem_ref_offset (exp);
 871                   off = double_int_lshift (off,
 872                                            BITS_PER_UNIT == 8
 873                                            ? 3 : exact_log2 (BITS_PER_UNIT),
 874                                            HOST_BITS_PER_DOUBLE_INT, true);
 875                   off = double_int_add (off, shwi_to_double_int (bit_offset));
 876                   if (double_int_fits_in_shwi_p (off))
 877                     {
 878                       bit_offset = double_int_to_shwi (off);
 879                       exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 880                     }
 881                 }
 882             }
 883           goto done;
 884
 885         case TARGET_MEM_REF:
 886           /* Hand back the decl for MEM[&decl, off].  */
 887           if (TREE_CODE (TMR_BASE (exp)) == ADDR_EXPR)
 888             {
 889               /* Via the variable index or index2 we can reach the
 890                  whole object.  */
 891               if (TMR_INDEX (exp) || TMR_INDEX2 (exp))
 892                 {
 893                   exp = TREE_OPERAND (TMR_BASE (exp), 0);
 894                   bit_offset = 0;
 895                   maxsize = -1;
 896                   goto done;
 897                 }
 898               if (integer_zerop (TMR_OFFSET (exp)))
 899                 exp = TREE_OPERAND (TMR_BASE (exp), 0);
 900               else
 901                 {
 902                   double_int off = mem_ref_offset (exp);
 903                   off = double_int_lshift (off,
 904                                            BITS_PER_UNIT == 8
 905                                            ? 3 : exact_log2 (BITS_PER_UNIT),
 906                                            HOST_BITS_PER_DOUBLE_INT, true);
 907                   off = double_int_add (off, shwi_to_double_int (bit_offset));
 908                   if (double_int_fits_in_shwi_p (off))
 909                     {
 910                       bit_offset = double_int_to_shwi (off);
 911                       exp = TREE_OPERAND (TMR_BASE (exp), 0);
 912                     }
 913                 }
 914             }
 915           goto done;
 916
 917         default:
 918           goto done;
 919         }
 920
 921       exp = TREE_OPERAND (exp, 0);
 922     }
 923  done:
 924
 925   /* We need to deal with variable arrays ending structures such as
 926        struct { int length; int a[1]; } x;           x.a[d]
 927        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 928        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 929        struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d]
 930      where we do not know maxsize for variable index accesses to
 931      the array.  The simplest way to conservatively deal with this
 932      is to punt in the case that offset + maxsize reaches the
 933      base type boundary.  This needs to include possible trailing padding
 934      that is there for alignment purposes.
 935
 936      That is of course only true if the base object is not a decl.  */
 937
 938   if (DECL_P (exp))
 939     {
 940       /* If maxsize is unknown adjust it according to the size of the
 941          base decl.  */
 942       if (maxsize == -1
 943           && host_integerp (DECL_SIZE (exp), 1))
 944         maxsize = TREE_INT_CST_LOW (DECL_SIZE (exp)) - bit_offset;
 945     }
 946   else if (seen_variable_array_ref
 947            && maxsize != -1
 948            && (!host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
 949                || (bit_offset + maxsize
 950                    == (signed) TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))))
 951     maxsize = -1;
 952
 953   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 954      negative bit_offset here.  We might want to store a zero offset
 955      in this case.  */
 956   *poffset = bit_offset;
 957   *psize = bitsize;
 958   *pmax_size = maxsize;
 959
 960   return exp;
 961 }
 962
 963 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
 964    denotes the starting address of the memory access EXP.
 965    Returns NULL_TREE if the offset is not constant or any component
 966    is not BITS_PER_UNIT-aligned.  */
 967
 968 tree
 969 get_addr_base_and_unit_offset (tree exp, HOST_WIDE_INT *poffset)
 970 {
 971   return get_addr_base_and_unit_offset_1 (exp, poffset, NULL);
 972 }
 973
 974 /* Returns true if STMT references an SSA_NAME that has
 975    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
 976
 977 bool
 978 stmt_references_abnormal_ssa_name (gimple stmt)
 979 {
 980   ssa_op_iter oi;
 981   use_operand_p use_p;
 982
 983   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
 984     {
 985       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
 986         return true;
 987     }
 988
 989   return false;
 990 }
 991