gcc/tree-dfa.c

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