gcc/tree-dfa.c

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