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_bb (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     }
 160 }
 161
 162 /* Like renumber_gimple_stmt_uids, but only do work on the basic blocks
 163    in BLOCKS, of which there are N_BLOCKS.  Also renumbers PHIs.  */
 164
 165 void
 166 renumber_gimple_stmt_uids_in_blocks (basic_block *blocks, int n_blocks)
 167 {
 168   int i;
 169
 170   set_gimple_stmt_max_uid (cfun, 0);
 171   for (i = 0; i < n_blocks; i++)
 172     {
 173       basic_block bb = blocks[i];
 174       gimple_stmt_iterator bsi;
 175       for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 176         {
 177           gimple stmt = gsi_stmt (bsi);
 178           gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
 179         }
 180       for (bsi = gsi_start_bb (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     }
 186 }
 187
 188 /* Build a temporary.  Make sure and register it to be renamed.  */
 189
 190 tree
 191 make_rename_temp (tree type, const char *prefix)
 192 {
 193   tree t = create_tmp_reg (type, prefix);
 194
 195   if (gimple_referenced_vars (cfun))
 196     {
 197       add_referenced_var (t);
 198       mark_sym_for_renaming (t);
 199     }
 200
 201   return t;
 202 }
 203
 204
 205
 206 /*---------------------------------------------------------------------------
 207                               Debugging functions
 208 ---------------------------------------------------------------------------*/
 209 /* Dump the list of all the referenced variables in the current function to
 210    FILE.  */
 211
 212 void
 213 dump_referenced_vars (FILE *file)
 214 {
 215   tree var;
 216   referenced_var_iterator rvi;
 217
 218   fprintf (file, "\nReferenced variables in %s: %u\n\n",
 219            get_name (current_function_decl), (unsigned) num_referenced_vars);
 220
 221   FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
 222     {
 223       fprintf (file, "Variable: ");
 224       dump_variable (file, var);
 225     }
 226
 227   fprintf (file, "\n");
 228 }
 229
 230
 231 /* Dump the list of all the referenced variables to stderr.  */
 232
 233 DEBUG_FUNCTION void
 234 debug_referenced_vars (void)
 235 {
 236   dump_referenced_vars (stderr);
 237 }
 238
 239
 240 /* Dump variable VAR and its may-aliases to FILE.  */
 241
 242 void
 243 dump_variable (FILE *file, tree var)
 244 {
 245   if (TREE_CODE (var) == SSA_NAME)
 246     {
 247       if (POINTER_TYPE_P (TREE_TYPE (var)))
 248         dump_points_to_info_for (file, var);
 249       var = SSA_NAME_VAR (var);
 250     }
 251
 252   if (var == NULL_TREE)
 253     {
 254       fprintf (file, "<nil>");
 255       return;
 256     }
 257
 258   print_generic_expr (file, var, dump_flags);
 259
 260   fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
 261   if (DECL_PT_UID (var) != DECL_UID (var))
 262     fprintf (file, ", PT-UID D.%u", (unsigned) DECL_PT_UID (var));
 263
 264   fprintf (file, ", ");
 265   print_generic_expr (file, TREE_TYPE (var), dump_flags);
 266
 267   if (TREE_ADDRESSABLE (var))
 268     fprintf (file, ", is addressable");
 269
 270   if (is_global_var (var))
 271     fprintf (file, ", is global");
 272
 273   if (TREE_THIS_VOLATILE (var))
 274     fprintf (file, ", is volatile");
 275
 276   if (cfun && gimple_default_def (cfun, var))
 277     {
 278       fprintf (file, ", default def: ");
 279       print_generic_expr (file, gimple_default_def (cfun, var), dump_flags);
 280     }
 281
 282   if (DECL_INITIAL (var))
 283     {
 284       fprintf (file, ", initial: ");
 285       print_generic_expr (file, DECL_INITIAL (var), dump_flags);
 286     }
 287
 288   fprintf (file, "\n");
 289 }
 290
 291
 292 /* Dump variable VAR and its may-aliases to stderr.  */
 293
 294 DEBUG_FUNCTION void
 295 debug_variable (tree var)
 296 {
 297   dump_variable (stderr, var);
 298 }
 299
 300
 301 /* Dump various DFA statistics to FILE.  */
 302
 303 void
 304 dump_dfa_stats (FILE *file)
 305 {
 306   struct dfa_stats_d dfa_stats;
 307
 308   unsigned long size, total = 0;
 309   const char * const fmt_str   = "%-30s%-13s%12s\n";
 310   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
 311   const char * const fmt_str_3 = "%-43s%11lu%c\n";
 312   const char *funcname
 313     = lang_hooks.decl_printable_name (current_function_decl, 2);
 314
 315   collect_dfa_stats (&dfa_stats);
 316
 317   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
 318
 319   fprintf (file, "---------------------------------------------------------\n");
 320   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
 321   fprintf (file, fmt_str, "", "  instances  ", "used ");
 322   fprintf (file, "---------------------------------------------------------\n");
 323
 324   size = num_referenced_vars * sizeof (tree);
 325   total += size;
 326   fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
 327            SCALE (size), LABEL (size));
 328
 329   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
 330   total += size;
 331   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
 332            SCALE (size), LABEL (size));
 333
 334   size = dfa_stats.num_uses * sizeof (tree *);
 335   total += size;
 336   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
 337            SCALE (size), LABEL (size));
 338
 339   size = dfa_stats.num_defs * sizeof (tree *);
 340   total += size;
 341   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
 342            SCALE (size), LABEL (size));
 343
 344   size = dfa_stats.num_vuses * sizeof (tree *);
 345   total += size;
 346   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
 347            SCALE (size), LABEL (size));
 348
 349   size = dfa_stats.num_vdefs * sizeof (tree *);
 350   total += size;
 351   fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
 352            SCALE (size), LABEL (size));
 353
 354   size = dfa_stats.num_phis * sizeof (struct gimple_statement_phi);
 355   total += size;
 356   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
 357            SCALE (size), LABEL (size));
 358
 359   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
 360   total += size;
 361   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
 362            SCALE (size), LABEL (size));
 363
 364   fprintf (file, "---------------------------------------------------------\n");
 365   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
 366            LABEL (total));
 367   fprintf (file, "---------------------------------------------------------\n");
 368   fprintf (file, "\n");
 369
 370   if (dfa_stats.num_phis)
 371     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %ld)\n",
 372              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
 373              (long) dfa_stats.max_num_phi_args);
 374
 375   fprintf (file, "\n");
 376 }
 377
 378
 379 /* Dump DFA statistics on stderr.  */
 380
 381 DEBUG_FUNCTION void
 382 debug_dfa_stats (void)
 383 {
 384   dump_dfa_stats (stderr);
 385 }
 386
 387
 388 /* Collect DFA statistics and store them in the structure pointed to by
 389    DFA_STATS_P.  */
 390
 391 static void
 392 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED)
 393 {
 394   basic_block bb;
 395   referenced_var_iterator vi;
 396   tree var;
 397
 398   gcc_assert (dfa_stats_p);
 399
 400   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
 401
 402   /* Count all the variable annotations.  */
 403   FOR_EACH_REFERENCED_VAR (cfun, var, vi)
 404     if (var_ann (var))
 405       dfa_stats_p->num_var_anns++;
 406
 407   /* Walk all the statements in the function counting references.  */
 408   FOR_EACH_BB (bb)
 409     {
 410       gimple_stmt_iterator si;
 411
 412       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
 413         {
 414           gimple phi = gsi_stmt (si);
 415           dfa_stats_p->num_phis++;
 416           dfa_stats_p->num_phi_args += gimple_phi_num_args (phi);
 417           if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args)
 418             dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi);
 419         }
 420
 421       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
 422         {
 423           gimple stmt = gsi_stmt (si);
 424           dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF);
 425           dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE);
 426           dfa_stats_p->num_vdefs += gimple_vdef (stmt) ? 1 : 0;
 427           dfa_stats_p->num_vuses += gimple_vuse (stmt) ? 1 : 0;
 428         }
 429     }
 430 }
 431
 432
 433 /*---------------------------------------------------------------------------
 434                              Miscellaneous helpers
 435 ---------------------------------------------------------------------------*/
 436 /* Callback for walk_tree.  Used to collect variables referenced in
 437    the function.  */
 438
 439 static tree
 440 find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
 441 {
 442   /* If we are reading the lto info back in, we need to rescan the
 443      referenced vars.  */
 444   if (TREE_CODE (*tp) == SSA_NAME)
 445     add_referenced_var (SSA_NAME_VAR (*tp));
 446
 447   /* If T is a regular variable that the optimizers are interested
 448      in, add it to the list of variables.  */
 449   else if (SSA_VAR_P (*tp))
 450     add_referenced_var (*tp);
 451
 452   /* Type, _DECL and constant nodes have no interesting children.
 453      Ignore them.  */
 454   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
 455     *walk_subtrees = 0;
 456
 457   return NULL_TREE;
 458 }
 459
 460 /* Find referenced variables in STMT.  In contrast with
 461    find_new_referenced_vars, this function will not mark newly found
 462    variables for renaming.  */
 463
 464 void
 465 find_referenced_vars_in (gimple stmt)
 466 {
 467   size_t i;
 468
 469   if (gimple_code (stmt) != GIMPLE_PHI)
 470     {
 471       for (i = 0; i < gimple_num_ops (stmt); i++)
 472         walk_tree (gimple_op_ptr (stmt, i), find_vars_r, NULL, NULL);
 473     }
 474   else
 475     {
 476       walk_tree (gimple_phi_result_ptr (stmt), find_vars_r, NULL, NULL);
 477
 478       for (i = 0; i < gimple_phi_num_args (stmt); i++)
 479         {
 480           tree arg = gimple_phi_arg_def (stmt, i);
 481           walk_tree (&arg, find_vars_r, NULL, NULL);
 482         }
 483     }
 484 }
 485
 486
 487 /* Lookup UID in the referenced_vars hashtable and return the associated
 488    variable.  */
 489
 490 tree
 491 referenced_var_lookup (struct function *fn, unsigned int uid)
 492 {
 493   tree h;
 494   struct tree_decl_minimal in;
 495   in.uid = uid;
 496   h = (tree) htab_find_with_hash (gimple_referenced_vars (fn), &in, uid);
 497   return h;
 498 }
 499
 500 /* Check if TO is in the referenced_vars hash table and insert it if not.
 501    Return true if it required insertion.  */
 502
 503 bool
 504 referenced_var_check_and_insert (tree to)
 505 {
 506   tree h, *loc;
 507   struct tree_decl_minimal in;
 508   unsigned int uid = DECL_UID (to);
 509
 510   in.uid = uid;
 511   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
 512   if (h)
 513     {
 514       /* DECL_UID has already been entered in the table.  Verify that it is
 515          the same entry as TO.  See PR 27793.  */
 516       gcc_assert (h == to);
 517       return false;
 518     }
 519
 520   loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun),
 521                                            &in, uid, INSERT);
 522   *loc = to;
 523   return true;
 524 }
 525
 526 /* Lookup VAR UID in the default_defs hashtable and return the associated
 527    variable.  */
 528
 529 tree
 530 gimple_default_def (struct function *fn, tree var)
 531 {
 532   struct tree_decl_minimal ind;
 533   struct tree_ssa_name in;
 534   gcc_assert (SSA_VAR_P (var));
 535   in.var = (tree)&ind;
 536   ind.uid = DECL_UID (var);
 537   return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var));
 538 }
 539
 540 /* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
 541
 542 void
 543 set_default_def (tree var, tree def)
 544 {
 545   struct tree_decl_minimal ind;
 546   struct tree_ssa_name in;
 547   void **loc;
 548
 549   gcc_assert (SSA_VAR_P (var));
 550   in.var = (tree)&ind;
 551   ind.uid = DECL_UID (var);
 552   if (!def)
 553     {
 554       loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 555             DECL_UID (var), INSERT);
 556       gcc_assert (*loc);
 557       htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
 558       return;
 559     }
 560   gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
 561   loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
 562                                   DECL_UID (var), INSERT);
 563
 564   /* Default definition might be changed by tail call optimization.  */
 565   if (*loc)
 566     SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false;
 567   *(tree *) loc = def;
 568
 569    /* Mark DEF as the default definition for VAR.  */
 570    SSA_NAME_IS_DEFAULT_DEF (def) = true;
 571 }
 572
 573 /* Add VAR to the list of referenced variables if it isn't already there.  */
 574
 575 bool
 576 add_referenced_var (tree var)
 577 {
 578   get_var_ann (var);
 579   gcc_assert (DECL_P (var));
 580
 581   /* Insert VAR into the referenced_vars has table if it isn't present.  */
 582   if (referenced_var_check_and_insert (var))
 583     {
 584       /* Scan DECL_INITIAL for pointer variables as they may contain
 585          address arithmetic referencing the address of other
 586          variables.  As we are only interested in directly referenced
 587          globals or referenced locals restrict this to initializers
 588          than can refer to local variables.  */
 589       if (DECL_INITIAL (var)
 590           && DECL_CONTEXT (var) == current_function_decl)
 591         walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
 592
 593       return true;
 594     }
 595
 596   return false;
 597 }
 598
 599 /* Remove VAR from the list.  */
 600
 601 void
 602 remove_referenced_var (tree var)
 603 {
 604   var_ann_t v_ann;
 605   struct tree_decl_minimal in;
 606   void **loc;
 607   unsigned int uid = DECL_UID (var);
 608
 609   /* Preserve var_anns of globals.  */
 610   if (!is_global_var (var)
 611       && (v_ann = var_ann (var)))
 612     {
 613       ggc_free (v_ann);
 614       *DECL_VAR_ANN_PTR (var) = NULL;
 615     }
 616   gcc_assert (DECL_P (var));
 617   in.uid = uid;
 618   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
 619                                   NO_INSERT);
 620   htab_clear_slot (gimple_referenced_vars (cfun), loc);
 621 }
 622
 623
 624 /* Return the virtual variable associated to the non-scalar variable VAR.  */
 625
 626 tree
 627 get_virtual_var (tree var)
 628 {
 629   STRIP_NOPS (var);
 630
 631   if (TREE_CODE (var) == SSA_NAME)
 632     var = SSA_NAME_VAR (var);
 633
 634   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
 635          || handled_component_p (var))
 636     var = TREE_OPERAND (var, 0);
 637
 638   /* Treating GIMPLE registers as virtual variables makes no sense.
 639      Also complain if we couldn't extract a _DECL out of the original
 640      expression.  */
 641   gcc_assert (SSA_VAR_P (var));
 642   gcc_assert (!is_gimple_reg (var));
 643
 644   return var;
 645 }
 646
 647 /* Mark all the naked symbols in STMT for SSA renaming.  */
 648
 649 void
 650 mark_symbols_for_renaming (gimple stmt)
 651 {
 652   tree op;
 653   ssa_op_iter iter;
 654
 655   update_stmt (stmt);
 656
 657   /* Mark all the operands for renaming.  */
 658   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
 659     if (DECL_P (op))
 660       mark_sym_for_renaming (op);
 661 }
 662
 663
 664 /* Find all variables within the gimplified statement that were not
 665    previously visible to the function and add them to the referenced
 666    variables list.  */
 667
 668 static tree
 669 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
 670                             void *data ATTRIBUTE_UNUSED)
 671 {
 672   tree t = *tp;
 673
 674   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
 675     {
 676       add_referenced_var (t);
 677       mark_sym_for_renaming (t);
 678     }
 679
 680   if (IS_TYPE_OR_DECL_P (t))
 681     *walk_subtrees = 0;
 682
 683   return NULL;
 684 }
 685
 686
 687 /* Find any new referenced variables in STMT.  */
 688
 689 void
 690 find_new_referenced_vars (gimple stmt)
 691 {
 692   walk_gimple_op (stmt, find_new_referenced_vars_1, NULL);
 693 }
 694
 695
 696 /* If EXP is a handled component reference for a structure, return the
 697    base variable.  The access range is delimited by bit positions *POFFSET and
 698    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
 699    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
 700    and *PMAX_SIZE are equal, the access is non-variable.  */
 701
 702 tree
 703 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 704                          HOST_WIDE_INT *psize,
 705                          HOST_WIDE_INT *pmax_size)
 706 {
 707   HOST_WIDE_INT bitsize = -1;
 708   HOST_WIDE_INT maxsize = -1;
 709   tree size_tree = NULL_TREE;
 710   HOST_WIDE_INT bit_offset = 0;
 711   bool seen_variable_array_ref = false;
 712   tree base_type;
 713
 714   /* First get the final access size from just the outermost expression.  */
 715   if (TREE_CODE (exp) == COMPONENT_REF)
 716     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 717   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 718     size_tree = TREE_OPERAND (exp, 1);
 719   else if (!VOID_TYPE_P (TREE_TYPE (exp)))
 720     {
 721       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 722       if (mode == BLKmode)
 723         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 724       else
 725         bitsize = GET_MODE_BITSIZE (mode);
 726     }
 727   if (size_tree != NULL_TREE)
 728     {
 729       if (! host_integerp (size_tree, 1))
 730         bitsize = -1;
 731       else
 732         bitsize = TREE_INT_CST_LOW (size_tree);
 733     }
 734
 735   /* Initially, maxsize is the same as the accessed element size.
 736      In the following it will only grow (or become -1).  */
 737   maxsize = bitsize;
 738
 739   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 740      and find the ultimate containing object.  */
 741   while (1)
 742     {
 743       base_type = TREE_TYPE (exp);
 744
 745       switch (TREE_CODE (exp))
 746         {
 747         case BIT_FIELD_REF:
 748           bit_offset += TREE_INT_CST_LOW (TREE_OPERAND (exp, 2));
 749           break;
 750
 751         case COMPONENT_REF:
 752           {
 753             tree field = TREE_OPERAND (exp, 1);
 754             tree this_offset = component_ref_field_offset (exp);
 755
 756             if (this_offset
 757                 && TREE_CODE (this_offset) == INTEGER_CST
 758                 && host_integerp (this_offset, 0))
 759               {
 760                 HOST_WIDE_INT hthis_offset = TREE_INT_CST_LOW (this_offset);
 761                 hthis_offset *= BITS_PER_UNIT;
 762                 hthis_offset
 763                   += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field));
 764                 bit_offset += hthis_offset;
 765
 766                 /* If we had seen a variable array ref already and we just
 767                    referenced the last field of a struct or a union member
 768                    then we have to adjust maxsize by the padding at the end
 769                    of our field.  */
 770                 if (seen_variable_array_ref
 771                     && maxsize != -1)
 772                   {
 773                     tree stype = TREE_TYPE (TREE_OPERAND (exp, 0));
 774                     tree next = DECL_CHAIN (field);
 775                     while (next && TREE_CODE (next) != FIELD_DECL)
 776                       next = DECL_CHAIN (next);
 777                     if (!next
 778                         || TREE_CODE (stype) != RECORD_TYPE)
 779                       {
 780                         tree fsize = DECL_SIZE_UNIT (field);
 781                         tree ssize = TYPE_SIZE_UNIT (stype);
 782                         if (host_integerp (fsize, 0)
 783                             && host_integerp (ssize, 0))
 784                           maxsize += ((TREE_INT_CST_LOW (ssize)
 785                                        - TREE_INT_CST_LOW (fsize))
 786                                       * BITS_PER_UNIT - hthis_offset);
 787                         else
 788                           maxsize = -1;
 789                       }
 790                   }
 791               }
 792             else
 793               {
 794                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 795                 /* We need to adjust maxsize to the whole structure bitsize.
 796                    But we can subtract any constant offset seen so far,
 797                    because that would get us out of the structure otherwise.  */
 798                 if (maxsize != -1 && csize && host_integerp (csize, 1))
 799                   maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
 800                 else
 801                   maxsize = -1;
 802               }
 803           }
 804           break;
 805
 806         case ARRAY_REF:
 807         case ARRAY_RANGE_REF:
 808           {
 809             tree index = TREE_OPERAND (exp, 1);
 810             tree low_bound, unit_size;
 811
 812             /* If the resulting bit-offset is constant, track it.  */
 813             if (TREE_CODE (index) == INTEGER_CST
 814                 && host_integerp (index, 0)
 815                 && (low_bound = array_ref_low_bound (exp),
 816                     host_integerp (low_bound, 0))
 817                 && (unit_size = array_ref_element_size (exp),
 818                     host_integerp (unit_size, 1)))
 819               {
 820                 HOST_WIDE_INT hindex = TREE_INT_CST_LOW (index);
 821
 822                 hindex -= TREE_INT_CST_LOW (low_bound);
 823                 hindex *= TREE_INT_CST_LOW (unit_size);
 824                 hindex *= BITS_PER_UNIT;
 825                 bit_offset += hindex;
 826
 827                 /* An array ref with a constant index up in the structure
 828                    hierarchy will constrain the size of any variable array ref
 829                    lower in the access hierarchy.  */
 830                 seen_variable_array_ref = false;
 831               }
 832             else
 833               {
 834                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 835                 /* We need to adjust maxsize to the whole array bitsize.
 836                    But we can subtract any constant offset seen so far,
 837                    because that would get us outside of the array otherwise.  */
 838                 if (maxsize != -1 && asize && host_integerp (asize, 1))
 839                   maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
 840                 else
 841                   maxsize = -1;
 842
 843                 /* Remember that we have seen an array ref with a variable
 844                    index.  */
 845                 seen_variable_array_ref = true;
 846               }
 847           }
 848           break;
 849
 850         case REALPART_EXPR:
 851           break;
 852
 853         case IMAGPART_EXPR:
 854           bit_offset += bitsize;
 855           break;
 856
 857         case VIEW_CONVERT_EXPR:
 858           break;
 859
 860         case MEM_REF:
 861           /* Hand back the decl for MEM[&decl, off].  */
 862           if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR)
 863             {
 864               if (integer_zerop (TREE_OPERAND (exp, 1)))
 865                 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 866               else
 867                 {
 868                   double_int off = mem_ref_offset (exp);
 869                   off = double_int_lshift (off,
 870                                            BITS_PER_UNIT == 8
 871                                            ? 3 : exact_log2 (BITS_PER_UNIT),
 872                                            HOST_BITS_PER_DOUBLE_INT, true);
 873                   off = double_int_add (off, shwi_to_double_int (bit_offset));
 874                   if (double_int_fits_in_shwi_p (off))
 875                     {
 876                       bit_offset = double_int_to_shwi (off);
 877                       exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 878                     }
 879                 }
 880             }
 881           goto done;
 882
 883         case TARGET_MEM_REF:
 884           /* Hand back the decl for MEM[&decl, off].  */
 885           if (TREE_CODE (TMR_BASE (exp)) == ADDR_EXPR)
 886             {
 887               /* Via the variable index or index2 we can reach the
 888                  whole object.  */
 889               if (TMR_INDEX (exp) || TMR_INDEX2 (exp))
 890                 {
 891                   exp = TREE_OPERAND (TMR_BASE (exp), 0);
 892                   bit_offset = 0;
 893                   maxsize = -1;
 894                   goto done;
 895                 }
 896               if (integer_zerop (TMR_OFFSET (exp)))
 897                 exp = TREE_OPERAND (TMR_BASE (exp), 0);
 898               else
 899                 {
 900                   double_int off = mem_ref_offset (exp);
 901                   off = double_int_lshift (off,
 902                                            BITS_PER_UNIT == 8
 903                                            ? 3 : exact_log2 (BITS_PER_UNIT),
 904                                            HOST_BITS_PER_DOUBLE_INT, true);
 905                   off = double_int_add (off, shwi_to_double_int (bit_offset));
 906                   if (double_int_fits_in_shwi_p (off))
 907                     {
 908                       bit_offset = double_int_to_shwi (off);
 909                       exp = TREE_OPERAND (TMR_BASE (exp), 0);
 910                     }
 911                 }
 912             }
 913           goto done;
 914
 915         default:
 916           goto done;
 917         }
 918
 919       exp = TREE_OPERAND (exp, 0);
 920     }
 921  done:
 922
 923   /* We need to deal with variable arrays ending structures such as
 924        struct { int length; int a[1]; } x;           x.a[d]
 925        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 926        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 927        struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d]
 928      where we do not know maxsize for variable index accesses to
 929      the array.  The simplest way to conservatively deal with this
 930      is to punt in the case that offset + maxsize reaches the
 931      base type boundary.  This needs to include possible trailing padding
 932      that is there for alignment purposes.  */
 933
 934   if (seen_variable_array_ref
 935       && maxsize != -1
 936       && (!host_integerp (TYPE_SIZE (base_type), 1)
 937           || (bit_offset + maxsize
 938               == (signed) TREE_INT_CST_LOW (TYPE_SIZE (base_type)))))
 939     maxsize = -1;
 940
 941   /* In case of a decl or constant base object we can do better.  */
 942
 943   if (DECL_P (exp))
 944     {
 945       /* If maxsize is unknown adjust it according to the size of the
 946          base decl.  */
 947       if (maxsize == -1
 948           && host_integerp (DECL_SIZE (exp), 1))
 949         maxsize = TREE_INT_CST_LOW (DECL_SIZE (exp)) - bit_offset;
 950     }
 951   else if (CONSTANT_CLASS_P (exp))
 952     {
 953       /* If maxsize is unknown adjust it according to the size of the
 954          base type constant.  */
 955       if (maxsize == -1
 956           && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1))
 957         maxsize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))) - bit_offset;
 958     }
 959
 960   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 961      negative bit_offset here.  We might want to store a zero offset
 962      in this case.  */
 963   *poffset = bit_offset;
 964   *psize = bitsize;
 965   *pmax_size = maxsize;
 966
 967   return exp;
 968 }
 969
 970 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
 971    denotes the starting address of the memory access EXP.
 972    Returns NULL_TREE if the offset is not constant or any component
 973    is not BITS_PER_UNIT-aligned.  */
 974
 975 tree
 976 get_addr_base_and_unit_offset (tree exp, HOST_WIDE_INT *poffset)
 977 {
 978   HOST_WIDE_INT byte_offset = 0;
 979
 980   /* Compute cumulative byte-offset for nested component-refs and array-refs,
 981      and find the ultimate containing object.  */
 982   while (1)
 983     {
 984       switch (TREE_CODE (exp))
 985         {
 986         case BIT_FIELD_REF:
 987           return NULL_TREE;
 988
 989         case COMPONENT_REF:
 990           {
 991             tree field = TREE_OPERAND (exp, 1);
 992             tree this_offset = component_ref_field_offset (exp);
 993             HOST_WIDE_INT hthis_offset;
 994
 995             if (!this_offset
 996                 || TREE_CODE (this_offset) != INTEGER_CST
 997                 || (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
 998                     % BITS_PER_UNIT))
 999               return NULL_TREE;
1000
1001             hthis_offset = TREE_INT_CST_LOW (this_offset);
1002             hthis_offset += (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
1003                              / BITS_PER_UNIT);
1004             byte_offset += hthis_offset;
1005           }
1006           break;
1007
1008         case ARRAY_REF:
1009         case ARRAY_RANGE_REF:
1010           {
1011             tree index = TREE_OPERAND (exp, 1);
1012             tree low_bound, unit_size;
1013
1014             /* If the resulting bit-offset is constant, track it.  */
1015             if (TREE_CODE (index) == INTEGER_CST
1016                 && (low_bound = array_ref_low_bound (exp),
1017                     TREE_CODE (low_bound) == INTEGER_CST)
1018                 && (unit_size = array_ref_element_size (exp),
1019                     TREE_CODE (unit_size) == INTEGER_CST))
1020               {
1021                 HOST_WIDE_INT hindex = TREE_INT_CST_LOW (index);
1022
1023                 hindex -= TREE_INT_CST_LOW (low_bound);
1024                 hindex *= TREE_INT_CST_LOW (unit_size);
1025                 byte_offset += hindex;
1026               }
1027             else
1028               return NULL_TREE;
1029           }
1030           break;
1031
1032         case REALPART_EXPR:
1033           break;
1034
1035         case IMAGPART_EXPR:
1036           byte_offset += TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (exp)));
1037           break;
1038
1039         case VIEW_CONVERT_EXPR:
1040           break;
1041
1042         case MEM_REF:
1043           /* Hand back the decl for MEM[&decl, off].  */
1044           if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR)
1045             {
1046               if (!integer_zerop (TREE_OPERAND (exp, 1)))
1047                 {
1048                   double_int off = mem_ref_offset (exp);
1049                   gcc_assert (off.high == -1 || off.high == 0);
1050                   byte_offset += double_int_to_shwi (off);
1051                 }
1052               exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
1053             }
1054           goto done;
1055
1056         case TARGET_MEM_REF:
1057           /* Hand back the decl for MEM[&decl, off].  */
1058           if (TREE_CODE (TMR_BASE (exp)) == ADDR_EXPR)
1059             {
1060               if (TMR_INDEX (exp) || TMR_INDEX2 (exp))
1061                 return NULL_TREE;
1062               if (!integer_zerop (TMR_OFFSET (exp)))
1063                 {
1064                   double_int off = mem_ref_offset (exp);
1065                   gcc_assert (off.high == -1 || off.high == 0);
1066                   byte_offset += double_int_to_shwi (off);
1067                 }
1068               exp = TREE_OPERAND (TMR_BASE (exp), 0);
1069             }
1070           goto done;
1071
1072         default:
1073           goto done;
1074         }
1075
1076       exp = TREE_OPERAND (exp, 0);
1077     }
1078 done:
1079
1080   *poffset = byte_offset;
1081   return exp;
1082 }
1083
1084 /* Returns true if STMT references an SSA_NAME that has
1085    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
1086
1087 bool
1088 stmt_references_abnormal_ssa_name (gimple stmt)
1089 {
1090   ssa_op_iter oi;
1091   use_operand_p use_p;
1092
1093   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
1094     {
1095       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
1096         return true;
1097     }
1098
1099   return false;
1100 }
1101