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