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 "input.h"
  26 #include "alias.h"
  27 #include "symtab.h"
  28 #include "tree.h"
  29 #include "fold-const.h"
  30 #include "stor-layout.h"
  31 #include "tm_p.h"
  32 #include "predict.h"
  33 #include "hard-reg-set.h"
  34 #include "function.h"
  35 #include "dominance.h"
  36 #include "cfg.h"
  37 #include "basic-block.h"
  38 #include "langhooks.h"
  39 #include "flags.h"
  40 #include "tree-pretty-print.h"
  41 #include "tree-ssa-alias.h"
  42 #include "internal-fn.h"
  43 #include "gimple-expr.h"
  44 #include "is-a.h"
  45 #include "gimple.h"
  46 #include "gimple-iterator.h"
  47 #include "gimple-walk.h"
  48 #include "gimple-ssa.h"
  49 #include "tree-phinodes.h"
  50 #include "ssa-iterators.h"
  51 #include "stringpool.h"
  52 #include "tree-ssanames.h"
  53 #include "rtl.h"
  54 #include "insn-config.h"
  55 #include "expmed.h"
  56 #include "dojump.h"
  57 #include "explow.h"
  58 #include "calls.h"
  59 #include "emit-rtl.h"
  60 #include "varasm.h"
  61 #include "stmt.h"
  62 #include "expr.h"
  63 #include "tree-dfa.h"
  64 #include "tree-inline.h"
  65 #include "tree-pass.h"
  66 #include "params.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.  If *PREVERSE is
 402    true, the storage order of the reference is reversed.  */
 403
 404 tree
 405 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 406                          HOST_WIDE_INT *psize,
 407                          HOST_WIDE_INT *pmax_size,
 408                          bool *preverse)
 409 {
 410   offset_int bitsize = -1;
 411   offset_int maxsize;
 412   tree size_tree = NULL_TREE;
 413   offset_int bit_offset = 0;
 414   bool seen_variable_array_ref = false;
 415
 416   /* First get the final access size and the storage order from just the
 417      outermost expression.  */
 418   if (TREE_CODE (exp) == COMPONENT_REF)
 419     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 420   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 421     size_tree = TREE_OPERAND (exp, 1);
 422   else if (!VOID_TYPE_P (TREE_TYPE (exp)))
 423     {
 424       machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 425       if (mode == BLKmode)
 426         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 427       else
 428         bitsize = int (GET_MODE_PRECISION (mode));
 429     }
 430   if (size_tree != NULL_TREE
 431       && TREE_CODE (size_tree) == INTEGER_CST)
 432     bitsize = wi::to_offset (size_tree);
 433
 434   *preverse = reverse_storage_order_for_component_p (exp);
 435
 436   /* Initially, maxsize is the same as the accessed element size.
 437      In the following it will only grow (or become -1).  */
 438   maxsize = bitsize;
 439
 440   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 441      and find the ultimate containing object.  */
 442   while (1)
 443     {
 444       switch (TREE_CODE (exp))
 445         {
 446         case BIT_FIELD_REF:
 447           bit_offset += wi::to_offset (TREE_OPERAND (exp, 2));
 448           break;
 449
 450         case COMPONENT_REF:
 451           {
 452             tree field = TREE_OPERAND (exp, 1);
 453             tree this_offset = component_ref_field_offset (exp);
 454
 455             if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
 456               {
 457                 offset_int woffset = wi::lshift (wi::to_offset (this_offset),
 458                                                  LOG2_BITS_PER_UNIT);
 459                 woffset += wi::to_offset (DECL_FIELD_BIT_OFFSET (field));
 460                 bit_offset += woffset;
 461
 462                 /* If we had seen a variable array ref already and we just
 463                    referenced the last field of a struct or a union member
 464                    then we have to adjust maxsize by the padding at the end
 465                    of our field.  */
 466                 if (seen_variable_array_ref && maxsize != -1)
 467                   {
 468                     tree stype = TREE_TYPE (TREE_OPERAND (exp, 0));
 469                     tree next = DECL_CHAIN (field);
 470                     while (next && TREE_CODE (next) != FIELD_DECL)
 471                       next = DECL_CHAIN (next);
 472                     if (!next
 473                         || TREE_CODE (stype) != RECORD_TYPE)
 474                       {
 475                         tree fsize = DECL_SIZE_UNIT (field);
 476                         tree ssize = TYPE_SIZE_UNIT (stype);
 477                         if (fsize == NULL
 478                             || TREE_CODE (fsize) != INTEGER_CST
 479                             || ssize == NULL
 480                             || TREE_CODE (ssize) != INTEGER_CST)
 481                           maxsize = -1;
 482                         else
 483                           {
 484                             offset_int tem = (wi::to_offset (ssize)
 485                                               - wi::to_offset (fsize));
 486                             tem = wi::lshift (tem, LOG2_BITS_PER_UNIT);
 487                             tem -= woffset;
 488                             maxsize += tem;
 489                           }
 490                       }
 491                   }
 492               }
 493             else
 494               {
 495                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 496                 /* We need to adjust maxsize to the whole structure bitsize.
 497                    But we can subtract any constant offset seen so far,
 498                    because that would get us out of the structure otherwise.  */
 499                 if (maxsize != -1
 500                     && csize
 501                     && TREE_CODE (csize) == INTEGER_CST)
 502                   maxsize = wi::to_offset (csize) - bit_offset;
 503                 else
 504                   maxsize = -1;
 505               }
 506           }
 507           break;
 508
 509         case ARRAY_REF:
 510         case ARRAY_RANGE_REF:
 511           {
 512             tree index = TREE_OPERAND (exp, 1);
 513             tree low_bound, unit_size;
 514
 515             /* If the resulting bit-offset is constant, track it.  */
 516             if (TREE_CODE (index) == INTEGER_CST
 517                 && (low_bound = array_ref_low_bound (exp),
 518                     TREE_CODE (low_bound) == INTEGER_CST)
 519                 && (unit_size = array_ref_element_size (exp),
 520                     TREE_CODE (unit_size) == INTEGER_CST))
 521               {
 522                 offset_int woffset
 523                   = wi::sext (wi::to_offset (index) - wi::to_offset (low_bound),
 524                               TYPE_PRECISION (TREE_TYPE (index)));
 525                 woffset *= wi::to_offset (unit_size);
 526                 woffset = wi::lshift (woffset, LOG2_BITS_PER_UNIT);
 527                 bit_offset += woffset;
 528
 529                 /* An array ref with a constant index up in the structure
 530                    hierarchy will constrain the size of any variable array ref
 531                    lower in the access hierarchy.  */
 532                 seen_variable_array_ref = false;
 533               }
 534             else
 535               {
 536                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 537                 /* We need to adjust maxsize to the whole array bitsize.
 538                    But we can subtract any constant offset seen so far,
 539                    because that would get us outside of the array otherwise.  */
 540                 if (maxsize != -1
 541                     && asize
 542                     && TREE_CODE (asize) == INTEGER_CST)
 543                   maxsize = wi::to_offset (asize) - bit_offset;
 544                 else
 545                   maxsize = -1;
 546
 547                 /* Remember that we have seen an array ref with a variable
 548                    index.  */
 549                 seen_variable_array_ref = true;
 550               }
 551           }
 552           break;
 553
 554         case REALPART_EXPR:
 555           break;
 556
 557         case IMAGPART_EXPR:
 558           bit_offset += bitsize;
 559           break;
 560
 561         case VIEW_CONVERT_EXPR:
 562           break;
 563
 564         case TARGET_MEM_REF:
 565           /* Via the variable index or index2 we can reach the
 566              whole object.  Still hand back the decl here.  */
 567           if (TREE_CODE (TMR_BASE (exp)) == ADDR_EXPR
 568               && (TMR_INDEX (exp) || TMR_INDEX2 (exp)))
 569             {
 570               exp = TREE_OPERAND (TMR_BASE (exp), 0);
 571               bit_offset = 0;
 572               maxsize = -1;
 573               goto done;
 574             }
 575           /* Fallthru.  */
 576         case MEM_REF:
 577           /* We need to deal with variable arrays ending structures such as
 578              struct { int length; int a[1]; } x;           x.a[d]
 579              struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 580              struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 581              struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d]
 582              where we do not know maxsize for variable index accesses to
 583              the array.  The simplest way to conservatively deal with this
 584              is to punt in the case that offset + maxsize reaches the
 585              base type boundary.  This needs to include possible trailing
 586              padding that is there for alignment purposes.  */
 587           if (seen_variable_array_ref
 588               && maxsize != -1
 589               && (TYPE_SIZE (TREE_TYPE (exp)) == NULL_TREE
 590                   || TREE_CODE (TYPE_SIZE (TREE_TYPE (exp))) != INTEGER_CST
 591                   || (bit_offset + maxsize
 592                       == wi::to_offset (TYPE_SIZE (TREE_TYPE (exp))))))
 593             maxsize = -1;
 594
 595           /* Hand back the decl for MEM[&decl, off].  */
 596           if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR)
 597             {
 598               if (integer_zerop (TREE_OPERAND (exp, 1)))
 599                 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 600               else
 601                 {
 602                   offset_int off = mem_ref_offset (exp);
 603                   off = wi::lshift (off, LOG2_BITS_PER_UNIT);
 604                   off += bit_offset;
 605                   if (wi::fits_shwi_p (off))
 606                     {
 607                       bit_offset = off;
 608                       exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 609                     }
 610                 }
 611             }
 612           goto done;
 613
 614         default:
 615           goto done;
 616         }
 617
 618       exp = TREE_OPERAND (exp, 0);
 619     }
 620
 621   /* We need to deal with variable arrays ending structures.  */
 622   if (seen_variable_array_ref
 623       && maxsize != -1
 624       && (TYPE_SIZE (TREE_TYPE (exp)) == NULL_TREE
 625           || TREE_CODE (TYPE_SIZE (TREE_TYPE (exp))) != INTEGER_CST
 626           || (bit_offset + maxsize
 627               == wi::to_offset (TYPE_SIZE (TREE_TYPE (exp))))))
 628     maxsize = -1;
 629
 630  done:
 631   if (!wi::fits_shwi_p (bitsize) || wi::neg_p (bitsize))
 632     {
 633       *poffset = 0;
 634       *psize = -1;
 635       *pmax_size = -1;
 636
 637       return exp;
 638     }
 639
 640   *psize = bitsize.to_shwi ();
 641
 642   if (!wi::fits_shwi_p (bit_offset))
 643     {
 644       *poffset = 0;
 645       *pmax_size = -1;
 646
 647       return exp;
 648     }
 649
 650   /* In case of a decl or constant base object we can do better.  */
 651
 652   if (DECL_P (exp))
 653     {
 654       /* If maxsize is unknown adjust it according to the size of the
 655          base decl.  */
 656       if (maxsize == -1
 657           && DECL_SIZE (exp)
 658           && TREE_CODE (DECL_SIZE (exp)) == INTEGER_CST)
 659         maxsize = wi::to_offset (DECL_SIZE (exp)) - bit_offset;
 660     }
 661   else if (CONSTANT_CLASS_P (exp))
 662     {
 663       /* If maxsize is unknown adjust it according to the size of the
 664          base type constant.  */
 665       if (maxsize == -1
 666           && TYPE_SIZE (TREE_TYPE (exp))
 667           && TREE_CODE (TYPE_SIZE (TREE_TYPE (exp))) == INTEGER_CST)
 668         maxsize = (wi::to_offset (TYPE_SIZE (TREE_TYPE (exp)))
 669                    - bit_offset);
 670     }
 671
 672   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 673      negative bit_offset here.  We might want to store a zero offset
 674      in this case.  */
 675   *poffset = bit_offset.to_shwi ();
 676   if (!wi::fits_shwi_p (maxsize) || wi::neg_p (maxsize))
 677     *pmax_size = -1;
 678   else
 679     *pmax_size = maxsize.to_shwi ();
 680
 681   return exp;
 682 }
 683
 684 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
 685    denotes the starting address of the memory access EXP.
 686    Returns NULL_TREE if the offset is not constant or any component
 687    is not BITS_PER_UNIT-aligned.
 688    VALUEIZE if non-NULL is used to valueize SSA names.  It should return
 689    its argument or a constant if the argument is known to be constant.  */
 690
 691 tree
 692 get_addr_base_and_unit_offset_1 (tree exp, HOST_WIDE_INT *poffset,
 693                                  tree (*valueize) (tree))
 694 {
 695   HOST_WIDE_INT byte_offset = 0;
 696
 697   /* Compute cumulative byte-offset for nested component-refs and array-refs,
 698      and find the ultimate containing object.  */
 699   while (1)
 700     {
 701       switch (TREE_CODE (exp))
 702         {
 703         case BIT_FIELD_REF:
 704           {
 705             HOST_WIDE_INT this_off = TREE_INT_CST_LOW (TREE_OPERAND (exp, 2));
 706             if (this_off % BITS_PER_UNIT)
 707               return NULL_TREE;
 708             byte_offset += this_off / BITS_PER_UNIT;
 709           }
 710           break;
 711
 712         case COMPONENT_REF:
 713           {
 714             tree field = TREE_OPERAND (exp, 1);
 715             tree this_offset = component_ref_field_offset (exp);
 716             HOST_WIDE_INT hthis_offset;
 717
 718             if (!this_offset
 719                 || TREE_CODE (this_offset) != INTEGER_CST
 720                 || (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
 721                     % BITS_PER_UNIT))
 722               return NULL_TREE;
 723
 724             hthis_offset = TREE_INT_CST_LOW (this_offset);
 725             hthis_offset += (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
 726                              / BITS_PER_UNIT);
 727             byte_offset += hthis_offset;
 728           }
 729           break;
 730
 731         case ARRAY_REF:
 732         case ARRAY_RANGE_REF:
 733           {
 734             tree index = TREE_OPERAND (exp, 1);
 735             tree low_bound, unit_size;
 736
 737             if (valueize
 738                 && TREE_CODE (index) == SSA_NAME)
 739               index = (*valueize) (index);
 740
 741             /* If the resulting bit-offset is constant, track it.  */
 742             if (TREE_CODE (index) == INTEGER_CST
 743                 && (low_bound = array_ref_low_bound (exp),
 744                     TREE_CODE (low_bound) == INTEGER_CST)
 745                 && (unit_size = array_ref_element_size (exp),
 746                     TREE_CODE (unit_size) == INTEGER_CST))
 747               {
 748                 offset_int woffset
 749                   = wi::sext (wi::to_offset (index) - wi::to_offset (low_bound),
 750                               TYPE_PRECISION (TREE_TYPE (index)));
 751                 woffset *= wi::to_offset (unit_size);
 752                 byte_offset += woffset.to_shwi ();
 753               }
 754             else
 755               return NULL_TREE;
 756           }
 757           break;
 758
 759         case REALPART_EXPR:
 760           break;
 761
 762         case IMAGPART_EXPR:
 763           byte_offset += TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (exp)));
 764           break;
 765
 766         case VIEW_CONVERT_EXPR:
 767           break;
 768
 769         case MEM_REF:
 770           {
 771             tree base = TREE_OPERAND (exp, 0);
 772             if (valueize
 773                 && TREE_CODE (base) == SSA_NAME)
 774               base = (*valueize) (base);
 775
 776             /* Hand back the decl for MEM[&decl, off].  */
 777             if (TREE_CODE (base) == ADDR_EXPR)
 778               {
 779                 if (!integer_zerop (TREE_OPERAND (exp, 1)))
 780                   {
 781                     offset_int off = mem_ref_offset (exp);
 782                     byte_offset += off.to_short_addr ();
 783                   }
 784                 exp = TREE_OPERAND (base, 0);
 785               }
 786             goto done;
 787           }
 788
 789         case TARGET_MEM_REF:
 790           {
 791             tree base = TREE_OPERAND (exp, 0);
 792             if (valueize
 793                 && TREE_CODE (base) == SSA_NAME)
 794               base = (*valueize) (base);
 795
 796             /* Hand back the decl for MEM[&decl, off].  */
 797             if (TREE_CODE (base) == ADDR_EXPR)
 798               {
 799                 if (TMR_INDEX (exp) || TMR_INDEX2 (exp))
 800                   return NULL_TREE;
 801                 if (!integer_zerop (TMR_OFFSET (exp)))
 802                   {
 803                     offset_int off = mem_ref_offset (exp);
 804                     byte_offset += off.to_short_addr ();
 805                   }
 806                 exp = TREE_OPERAND (base, 0);
 807               }
 808             goto done;
 809           }
 810
 811         default:
 812           goto done;
 813         }
 814
 815       exp = TREE_OPERAND (exp, 0);
 816     }
 817 done:
 818
 819   *poffset = byte_offset;
 820   return exp;
 821 }
 822
 823 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
 824    denotes the starting address of the memory access EXP.
 825    Returns NULL_TREE if the offset is not constant or any component
 826    is not BITS_PER_UNIT-aligned.  */
 827
 828 tree
 829 get_addr_base_and_unit_offset (tree exp, HOST_WIDE_INT *poffset)
 830 {
 831   return get_addr_base_and_unit_offset_1 (exp, poffset, NULL);
 832 }
 833
 834 /* Returns true if STMT references an SSA_NAME that has
 835    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
 836
 837 bool
 838 stmt_references_abnormal_ssa_name (gimple stmt)
 839 {
 840   ssa_op_iter oi;
 841   use_operand_p use_p;
 842
 843   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
 844     {
 845       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
 846         return true;
 847     }
 848
 849   return false;
 850 }
 851
 852 /* Pair of tree and a sorting index, for dump_enumerated_decls.  */
 853 struct GTY(()) numbered_tree_d
 854 {
 855   tree t;
 856   int num;
 857 };
 858 typedef struct numbered_tree_d numbered_tree;
 859
 860
 861 /* Compare two declarations references by their DECL_UID / sequence number.
 862    Called via qsort.  */
 863
 864 static int
 865 compare_decls_by_uid (const void *pa, const void *pb)
 866 {
 867   const numbered_tree *nt_a = ((const numbered_tree *)pa);
 868   const numbered_tree *nt_b = ((const numbered_tree *)pb);
 869
 870   if (DECL_UID (nt_a->t) != DECL_UID (nt_b->t))
 871     return  DECL_UID (nt_a->t) - DECL_UID (nt_b->t);
 872   return nt_a->num - nt_b->num;
 873 }
 874
 875 /* Called via walk_gimple_stmt / walk_gimple_op by dump_enumerated_decls.  */
 876 static tree
 877 dump_enumerated_decls_push (tree *tp, int *walk_subtrees, void *data)
 878 {
 879   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
 880   vec<numbered_tree> *list = (vec<numbered_tree> *) wi->info;
 881   numbered_tree nt;
 882
 883   if (!DECL_P (*tp))
 884     return NULL_TREE;
 885   nt.t = *tp;
 886   nt.num = list->length ();
 887   list->safe_push (nt);
 888   *walk_subtrees = 0;
 889   return NULL_TREE;
 890 }
 891
 892 /* Find all the declarations used by the current function, sort them by uid,
 893    and emit the sorted list.  Each declaration is tagged with a sequence
 894    number indicating when it was found during statement / tree walking,
 895    so that TDF_NOUID comparisons of anonymous declarations are still
 896    meaningful.  Where a declaration was encountered more than once, we
 897    emit only the sequence number of the first encounter.
 898    FILE is the dump file where to output the list and FLAGS is as in
 899    print_generic_expr.  */
 900 void
 901 dump_enumerated_decls (FILE *file, int flags)
 902 {
 903   basic_block bb;
 904   struct walk_stmt_info wi;
 905   auto_vec<numbered_tree, 40> decl_list;
 906
 907   memset (&wi, '\0', sizeof (wi));
 908   wi.info = (void *) &decl_list;
 909   FOR_EACH_BB_FN (bb, cfun)
 910     {
 911       gimple_stmt_iterator gsi;
 912
 913       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 914         if (!is_gimple_debug (gsi_stmt (gsi)))
 915           walk_gimple_stmt (&gsi, NULL, dump_enumerated_decls_push, &wi);
 916     }
 917   decl_list.qsort (compare_decls_by_uid);
 918   if (decl_list.length ())
 919     {
 920       unsigned ix;
 921       numbered_tree *ntp;
 922       tree last = NULL_TREE;
 923
 924       fprintf (file, "Declarations used by %s, sorted by DECL_UID:\n",
 925                current_function_name ());
 926       FOR_EACH_VEC_ELT (decl_list, ix, ntp)
 927         {
 928           if (ntp->t == last)
 929             continue;
 930           fprintf (file, "%d: ", ntp->num);
 931           print_generic_decl (file, ntp->t, flags);
 932           fprintf (file, "\n");
 933           last = ntp->t;
 934         }
 935     }
 936 }