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 (TREE_CODE (var) == VAR_DECL
 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 (TREE_CODE (var) == VAR_DECL
 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
 616           && TREE_CODE (exp) == VAR_DECL && DECL_COMMON (exp))
 617         {
 618           tree sz_tree = TYPE_SIZE (TREE_TYPE (exp));
 619           /* If size is unknown, or we have read to the end, assume there
 620              may be more to the structure than we are told.  */
 621           if (TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE
 622               || (seen_variable_array_ref
 623                   && (sz_tree == NULL_TREE
 624                       || TREE_CODE (sz_tree) != INTEGER_CST
 625                       || (bit_offset + maxsize == wi::to_offset (sz_tree)))))
 626             maxsize = -1;
 627         }
 628       /* If maxsize is unknown adjust it according to the size of the
 629          base decl.  */
 630       else if (maxsize == -1
 631           && DECL_SIZE (exp)
 632           && TREE_CODE (DECL_SIZE (exp)) == INTEGER_CST)
 633         maxsize = wi::to_offset (DECL_SIZE (exp)) - bit_offset;
 634     }
 635   else if (CONSTANT_CLASS_P (exp))
 636     {
 637       /* If maxsize is unknown adjust it according to the size of the
 638          base type constant.  */
 639       if (maxsize == -1
 640           && TYPE_SIZE (TREE_TYPE (exp))
 641           && TREE_CODE (TYPE_SIZE (TREE_TYPE (exp))) == INTEGER_CST)
 642         maxsize = (wi::to_offset (TYPE_SIZE (TREE_TYPE (exp)))
 643                    - bit_offset);
 644     }
 645
 646   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 647      negative bit_offset here.  We might want to store a zero offset
 648      in this case.  */
 649   *poffset = bit_offset.to_shwi ();
 650   if (!wi::fits_shwi_p (maxsize) || wi::neg_p (maxsize))
 651     *pmax_size = -1;
 652   else
 653     *pmax_size = maxsize.to_shwi ();
 654
 655   return exp;
 656 }
 657
 658 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
 659    denotes the starting address of the memory access EXP.
 660    Returns NULL_TREE if the offset is not constant or any component
 661    is not BITS_PER_UNIT-aligned.
 662    VALUEIZE if non-NULL is used to valueize SSA names.  It should return
 663    its argument or a constant if the argument is known to be constant.  */
 664
 665 tree
 666 get_addr_base_and_unit_offset_1 (tree exp, HOST_WIDE_INT *poffset,
 667                                  tree (*valueize) (tree))
 668 {
 669   HOST_WIDE_INT byte_offset = 0;
 670
 671   /* Compute cumulative byte-offset for nested component-refs and array-refs,
 672      and find the ultimate containing object.  */
 673   while (1)
 674     {
 675       switch (TREE_CODE (exp))
 676         {
 677         case BIT_FIELD_REF:
 678           {
 679             HOST_WIDE_INT this_off = TREE_INT_CST_LOW (TREE_OPERAND (exp, 2));
 680             if (this_off % BITS_PER_UNIT)
 681               return NULL_TREE;
 682             byte_offset += this_off / BITS_PER_UNIT;
 683           }
 684           break;
 685
 686         case COMPONENT_REF:
 687           {
 688             tree field = TREE_OPERAND (exp, 1);
 689             tree this_offset = component_ref_field_offset (exp);
 690             HOST_WIDE_INT hthis_offset;
 691
 692             if (!this_offset
 693                 || TREE_CODE (this_offset) != INTEGER_CST
 694                 || (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
 695                     % BITS_PER_UNIT))
 696               return NULL_TREE;
 697
 698             hthis_offset = TREE_INT_CST_LOW (this_offset);
 699             hthis_offset += (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
 700                              / BITS_PER_UNIT);
 701             byte_offset += hthis_offset;
 702           }
 703           break;
 704
 705         case ARRAY_REF:
 706         case ARRAY_RANGE_REF:
 707           {
 708             tree index = TREE_OPERAND (exp, 1);
 709             tree low_bound, unit_size;
 710
 711             if (valueize
 712                 && TREE_CODE (index) == SSA_NAME)
 713               index = (*valueize) (index);
 714
 715             /* If the resulting bit-offset is constant, track it.  */
 716             if (TREE_CODE (index) == INTEGER_CST
 717                 && (low_bound = array_ref_low_bound (exp),
 718                     TREE_CODE (low_bound) == INTEGER_CST)
 719                 && (unit_size = array_ref_element_size (exp),
 720                     TREE_CODE (unit_size) == INTEGER_CST))
 721               {
 722                 offset_int woffset
 723                   = wi::sext (wi::to_offset (index) - wi::to_offset (low_bound),
 724                               TYPE_PRECISION (TREE_TYPE (index)));
 725                 woffset *= wi::to_offset (unit_size);
 726                 byte_offset += woffset.to_shwi ();
 727               }
 728             else
 729               return NULL_TREE;
 730           }
 731           break;
 732
 733         case REALPART_EXPR:
 734           break;
 735
 736         case IMAGPART_EXPR:
 737           byte_offset += TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (exp)));
 738           break;
 739
 740         case VIEW_CONVERT_EXPR:
 741           break;
 742
 743         case MEM_REF:
 744           {
 745             tree base = TREE_OPERAND (exp, 0);
 746             if (valueize
 747                 && TREE_CODE (base) == SSA_NAME)
 748               base = (*valueize) (base);
 749
 750             /* Hand back the decl for MEM[&decl, off].  */
 751             if (TREE_CODE (base) == ADDR_EXPR)
 752               {
 753                 if (!integer_zerop (TREE_OPERAND (exp, 1)))
 754                   {
 755                     offset_int off = mem_ref_offset (exp);
 756                     byte_offset += off.to_short_addr ();
 757                   }
 758                 exp = TREE_OPERAND (base, 0);
 759               }
 760             goto done;
 761           }
 762
 763         case TARGET_MEM_REF:
 764           {
 765             tree base = TREE_OPERAND (exp, 0);
 766             if (valueize
 767                 && TREE_CODE (base) == SSA_NAME)
 768               base = (*valueize) (base);
 769
 770             /* Hand back the decl for MEM[&decl, off].  */
 771             if (TREE_CODE (base) == ADDR_EXPR)
 772               {
 773                 if (TMR_INDEX (exp) || TMR_INDEX2 (exp))
 774                   return NULL_TREE;
 775                 if (!integer_zerop (TMR_OFFSET (exp)))
 776                   {
 777                     offset_int off = mem_ref_offset (exp);
 778                     byte_offset += off.to_short_addr ();
 779                   }
 780                 exp = TREE_OPERAND (base, 0);
 781               }
 782             goto done;
 783           }
 784
 785         default:
 786           goto done;
 787         }
 788
 789       exp = TREE_OPERAND (exp, 0);
 790     }
 791 done:
 792
 793   *poffset = byte_offset;
 794   return exp;
 795 }
 796
 797 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
 798    denotes the starting address of the memory access EXP.
 799    Returns NULL_TREE if the offset is not constant or any component
 800    is not BITS_PER_UNIT-aligned.  */
 801
 802 tree
 803 get_addr_base_and_unit_offset (tree exp, HOST_WIDE_INT *poffset)
 804 {
 805   return get_addr_base_and_unit_offset_1 (exp, poffset, NULL);
 806 }
 807
 808 /* Returns true if STMT references an SSA_NAME that has
 809    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
 810
 811 bool
 812 stmt_references_abnormal_ssa_name (gimple *stmt)
 813 {
 814   ssa_op_iter oi;
 815   use_operand_p use_p;
 816
 817   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
 818     {
 819       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
 820         return true;
 821     }
 822
 823   return false;
 824 }
 825
 826 /* If STMT takes any abnormal PHI values as input, replace them with
 827    local copies.  */
 828
 829 void
 830 replace_abnormal_ssa_names (gimple *stmt)
 831 {
 832   ssa_op_iter oi;
 833   use_operand_p use_p;
 834
 835   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
 836     {
 837       tree op = USE_FROM_PTR (use_p);
 838       if (TREE_CODE (op) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
 839         {
 840           gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 841           tree new_name = make_ssa_name (TREE_TYPE (op));
 842           gassign *assign = gimple_build_assign (new_name, op);
 843           gsi_insert_before (&gsi, assign, GSI_SAME_STMT);
 844           SET_USE (use_p, new_name);
 845         }
 846     }
 847 }
 848
 849 /* Pair of tree and a sorting index, for dump_enumerated_decls.  */
 850 struct GTY(()) numbered_tree
 851 {
 852   tree t;
 853   int num;
 854 };
 855
 856
 857 /* Compare two declarations references by their DECL_UID / sequence number.
 858    Called via qsort.  */
 859
 860 static int
 861 compare_decls_by_uid (const void *pa, const void *pb)
 862 {
 863   const numbered_tree *nt_a = ((const numbered_tree *)pa);
 864   const numbered_tree *nt_b = ((const numbered_tree *)pb);
 865
 866   if (DECL_UID (nt_a->t) != DECL_UID (nt_b->t))
 867     return  DECL_UID (nt_a->t) - DECL_UID (nt_b->t);
 868   return nt_a->num - nt_b->num;
 869 }
 870
 871 /* Called via walk_gimple_stmt / walk_gimple_op by dump_enumerated_decls.  */
 872 static tree
 873 dump_enumerated_decls_push (tree *tp, int *walk_subtrees, void *data)
 874 {
 875   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
 876   vec<numbered_tree> *list = (vec<numbered_tree> *) wi->info;
 877   numbered_tree nt;
 878
 879   if (!DECL_P (*tp))
 880     return NULL_TREE;
 881   nt.t = *tp;
 882   nt.num = list->length ();
 883   list->safe_push (nt);
 884   *walk_subtrees = 0;
 885   return NULL_TREE;
 886 }
 887
 888 /* Find all the declarations used by the current function, sort them by uid,
 889    and emit the sorted list.  Each declaration is tagged with a sequence
 890    number indicating when it was found during statement / tree walking,
 891    so that TDF_NOUID comparisons of anonymous declarations are still
 892    meaningful.  Where a declaration was encountered more than once, we
 893    emit only the sequence number of the first encounter.
 894    FILE is the dump file where to output the list and FLAGS is as in
 895    print_generic_expr.  */
 896 void
 897 dump_enumerated_decls (FILE *file, int flags)
 898 {
 899   basic_block bb;
 900   struct walk_stmt_info wi;
 901   auto_vec<numbered_tree, 40> decl_list;
 902
 903   memset (&wi, '\0', sizeof (wi));
 904   wi.info = (void *) &decl_list;
 905   FOR_EACH_BB_FN (bb, cfun)
 906     {
 907       gimple_stmt_iterator gsi;
 908
 909       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 910         if (!is_gimple_debug (gsi_stmt (gsi)))
 911           walk_gimple_stmt (&gsi, NULL, dump_enumerated_decls_push, &wi);
 912     }
 913   decl_list.qsort (compare_decls_by_uid);
 914   if (decl_list.length ())
 915     {
 916       unsigned ix;
 917       numbered_tree *ntp;
 918       tree last = NULL_TREE;
 919
 920       fprintf (file, "Declarations used by %s, sorted by DECL_UID:\n",
 921                current_function_name ());
 922       FOR_EACH_VEC_ELT (decl_list, ix, ntp)
 923         {
 924           if (ntp->t == last)
 925             continue;
 926           fprintf (file, "%d: ", ntp->num);
 927           print_generic_decl (file, ntp->t, flags);
 928           fprintf (file, "\n");
 929           last = ntp->t;
 930         }
 931     }
 932 }