gcc/tree-dfa.c

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