gcc/tree-dfa.c

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