gcc/tree-dfa.cc

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