gcc/tree-dfa.c

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