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