gcc/tree-dfa.c

   1 /* Data flow functions for trees.
   2    Copyright (C) 2001-2015 Free Software Foundation, Inc.
   3    Contributed by Diego Novillo <dnovillo@redhat.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "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.  */
 372
 373 tree
 374 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
 375                          HOST_WIDE_INT *psize,
 376                          HOST_WIDE_INT *pmax_size)
 377 {
 378   offset_int bitsize = -1;
 379   offset_int maxsize;
 380   tree size_tree = NULL_TREE;
 381   offset_int bit_offset = 0;
 382   bool seen_variable_array_ref = false;
 383
 384   /* First get the final access size from just the outermost expression.  */
 385   if (TREE_CODE (exp) == COMPONENT_REF)
 386     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
 387   else if (TREE_CODE (exp) == BIT_FIELD_REF)
 388     size_tree = TREE_OPERAND (exp, 1);
 389   else if (!VOID_TYPE_P (TREE_TYPE (exp)))
 390     {
 391       machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
 392       if (mode == BLKmode)
 393         size_tree = TYPE_SIZE (TREE_TYPE (exp));
 394       else
 395         bitsize = int (GET_MODE_PRECISION (mode));
 396     }
 397   if (size_tree != NULL_TREE
 398       && TREE_CODE (size_tree) == INTEGER_CST)
 399     bitsize = wi::to_offset (size_tree);
 400
 401   /* Initially, maxsize is the same as the accessed element size.
 402      In the following it will only grow (or become -1).  */
 403   maxsize = bitsize;
 404
 405   /* Compute cumulative bit-offset for nested component-refs and array-refs,
 406      and find the ultimate containing object.  */
 407   while (1)
 408     {
 409       switch (TREE_CODE (exp))
 410         {
 411         case BIT_FIELD_REF:
 412           bit_offset += wi::to_offset (TREE_OPERAND (exp, 2));
 413           break;
 414
 415         case COMPONENT_REF:
 416           {
 417             tree field = TREE_OPERAND (exp, 1);
 418             tree this_offset = component_ref_field_offset (exp);
 419
 420             if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
 421               {
 422                 offset_int woffset = wi::lshift (wi::to_offset (this_offset),
 423                                                  LOG2_BITS_PER_UNIT);
 424                 woffset += wi::to_offset (DECL_FIELD_BIT_OFFSET (field));
 425                 bit_offset += woffset;
 426
 427                 /* If we had seen a variable array ref already and we just
 428                    referenced the last field of a struct or a union member
 429                    then we have to adjust maxsize by the padding at the end
 430                    of our field.  */
 431                 if (seen_variable_array_ref && maxsize != -1)
 432                   {
 433                     tree stype = TREE_TYPE (TREE_OPERAND (exp, 0));
 434                     tree next = DECL_CHAIN (field);
 435                     while (next && TREE_CODE (next) != FIELD_DECL)
 436                       next = DECL_CHAIN (next);
 437                     if (!next
 438                         || TREE_CODE (stype) != RECORD_TYPE)
 439                       {
 440                         tree fsize = DECL_SIZE_UNIT (field);
 441                         tree ssize = TYPE_SIZE_UNIT (stype);
 442                         if (fsize == NULL
 443                             || TREE_CODE (fsize) != INTEGER_CST
 444                             || ssize == NULL
 445                             || TREE_CODE (ssize) != INTEGER_CST)
 446                           maxsize = -1;
 447                         else
 448                           {
 449                             offset_int tem = (wi::to_offset (ssize)
 450                                               - wi::to_offset (fsize));
 451                             tem = wi::lshift (tem, LOG2_BITS_PER_UNIT);
 452                             tem -= woffset;
 453                             maxsize += tem;
 454                           }
 455                       }
 456                   }
 457               }
 458             else
 459               {
 460                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 461                 /* We need to adjust maxsize to the whole structure bitsize.
 462                    But we can subtract any constant offset seen so far,
 463                    because that would get us out of the structure otherwise.  */
 464                 if (maxsize != -1
 465                     && csize
 466                     && TREE_CODE (csize) == INTEGER_CST)
 467                   maxsize = wi::to_offset (csize) - bit_offset;
 468                 else
 469                   maxsize = -1;
 470               }
 471           }
 472           break;
 473
 474         case ARRAY_REF:
 475         case ARRAY_RANGE_REF:
 476           {
 477             tree index = TREE_OPERAND (exp, 1);
 478             tree low_bound, unit_size;
 479
 480             /* If the resulting bit-offset is constant, track it.  */
 481             if (TREE_CODE (index) == INTEGER_CST
 482                 && (low_bound = array_ref_low_bound (exp),
 483                     TREE_CODE (low_bound) == INTEGER_CST)
 484                 && (unit_size = array_ref_element_size (exp),
 485                     TREE_CODE (unit_size) == INTEGER_CST))
 486               {
 487                 offset_int woffset
 488                   = wi::sext (wi::to_offset (index) - wi::to_offset (low_bound),
 489                               TYPE_PRECISION (TREE_TYPE (index)));
 490                 woffset *= wi::to_offset (unit_size);
 491                 woffset = wi::lshift (woffset, LOG2_BITS_PER_UNIT);
 492                 bit_offset += woffset;
 493
 494                 /* An array ref with a constant index up in the structure
 495                    hierarchy will constrain the size of any variable array ref
 496                    lower in the access hierarchy.  */
 497                 seen_variable_array_ref = false;
 498               }
 499             else
 500               {
 501                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 502                 /* We need to adjust maxsize to the whole array bitsize.
 503                    But we can subtract any constant offset seen so far,
 504                    because that would get us outside of the array otherwise.  */
 505                 if (maxsize != -1
 506                     && asize
 507                     && TREE_CODE (asize) == INTEGER_CST)
 508                   maxsize = wi::to_offset (asize) - bit_offset;
 509                 else
 510                   maxsize = -1;
 511
 512                 /* Remember that we have seen an array ref with a variable
 513                    index.  */
 514                 seen_variable_array_ref = true;
 515               }
 516           }
 517           break;
 518
 519         case REALPART_EXPR:
 520           break;
 521
 522         case IMAGPART_EXPR:
 523           bit_offset += bitsize;
 524           break;
 525
 526         case VIEW_CONVERT_EXPR:
 527           break;
 528
 529         case TARGET_MEM_REF:
 530           /* Via the variable index or index2 we can reach the
 531              whole object.  Still hand back the decl here.  */
 532           if (TREE_CODE (TMR_BASE (exp)) == ADDR_EXPR
 533               && (TMR_INDEX (exp) || TMR_INDEX2 (exp)))
 534             {
 535               exp = TREE_OPERAND (TMR_BASE (exp), 0);
 536               bit_offset = 0;
 537               maxsize = -1;
 538               goto done;
 539             }
 540           /* Fallthru.  */
 541         case MEM_REF:
 542           /* We need to deal with variable arrays ending structures such as
 543              struct { int length; int a[1]; } x;           x.a[d]
 544              struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 545              struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 546              struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d]
 547              where we do not know maxsize for variable index accesses to
 548              the array.  The simplest way to conservatively deal with this
 549              is to punt in the case that offset + maxsize reaches the
 550              base type boundary.  This needs to include possible trailing
 551              padding that is there for alignment purposes.  */
 552           if (seen_variable_array_ref
 553               && maxsize != -1
 554               && (TYPE_SIZE (TREE_TYPE (exp)) == NULL_TREE
 555                   || TREE_CODE (TYPE_SIZE (TREE_TYPE (exp))) != INTEGER_CST
 556                   || (bit_offset + maxsize
 557                       == wi::to_offset (TYPE_SIZE (TREE_TYPE (exp))))))
 558             maxsize = -1;
 559
 560           /* Hand back the decl for MEM[&decl, off].  */
 561           if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR)
 562             {
 563               if (integer_zerop (TREE_OPERAND (exp, 1)))
 564                 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 565               else
 566                 {
 567                   offset_int off = mem_ref_offset (exp);
 568                   off = wi::lshift (off, LOG2_BITS_PER_UNIT);
 569                   off += bit_offset;
 570                   if (wi::fits_shwi_p (off))
 571                     {
 572                       bit_offset = off;
 573                       exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 574                     }
 575                 }
 576             }
 577           goto done;
 578
 579         default:
 580           goto done;
 581         }
 582
 583       exp = TREE_OPERAND (exp, 0);
 584     }
 585
 586   /* We need to deal with variable arrays ending structures.  */
 587   if (seen_variable_array_ref
 588       && maxsize != -1
 589       && (TYPE_SIZE (TREE_TYPE (exp)) == NULL_TREE
 590           || TREE_CODE (TYPE_SIZE (TREE_TYPE (exp))) != INTEGER_CST
 591           || (bit_offset + maxsize
 592               == wi::to_offset (TYPE_SIZE (TREE_TYPE (exp))))))
 593     maxsize = -1;
 594
 595  done:
 596   if (!wi::fits_shwi_p (bitsize) || wi::neg_p (bitsize))
 597     {
 598       *poffset = 0;
 599       *psize = -1;
 600       *pmax_size = -1;
 601
 602       return exp;
 603     }
 604
 605   *psize = bitsize.to_shwi ();
 606
 607   if (!wi::fits_shwi_p (bit_offset))
 608     {
 609       *poffset = 0;
 610       *pmax_size = -1;
 611
 612       return exp;
 613     }
 614
 615   /* In case of a decl or constant base object we can do better.  */
 616
 617   if (DECL_P (exp))
 618     {
 619       /* If maxsize is unknown adjust it according to the size of the
 620          base decl.  */
 621       if (maxsize == -1
 622           && DECL_SIZE (exp)
 623           && TREE_CODE (DECL_SIZE (exp)) == INTEGER_CST)
 624         maxsize = wi::to_offset (DECL_SIZE (exp)) - bit_offset;
 625     }
 626   else if (CONSTANT_CLASS_P (exp))
 627     {
 628       /* If maxsize is unknown adjust it according to the size of the
 629          base type constant.  */
 630       if (maxsize == -1
 631           && TYPE_SIZE (TREE_TYPE (exp))
 632           && TREE_CODE (TYPE_SIZE (TREE_TYPE (exp))) == INTEGER_CST)
 633         maxsize = (wi::to_offset (TYPE_SIZE (TREE_TYPE (exp)))
 634                    - bit_offset);
 635     }
 636
 637   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 638      negative bit_offset here.  We might want to store a zero offset
 639      in this case.  */
 640   *poffset = bit_offset.to_shwi ();
 641   if (!wi::fits_shwi_p (maxsize) || wi::neg_p (maxsize))
 642     *pmax_size = -1;
 643   else
 644     *pmax_size = maxsize.to_shwi ();
 645
 646   return exp;
 647 }
 648
 649 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
 650    denotes the starting address of the memory access EXP.
 651    Returns NULL_TREE if the offset is not constant or any component
 652    is not BITS_PER_UNIT-aligned.
 653    VALUEIZE if non-NULL is used to valueize SSA names.  It should return
 654    its argument or a constant if the argument is known to be constant.  */
 655
 656 tree
 657 get_addr_base_and_unit_offset_1 (tree exp, HOST_WIDE_INT *poffset,
 658                                  tree (*valueize) (tree))
 659 {
 660   HOST_WIDE_INT byte_offset = 0;
 661
 662   /* Compute cumulative byte-offset for nested component-refs and array-refs,
 663      and find the ultimate containing object.  */
 664   while (1)
 665     {
 666       switch (TREE_CODE (exp))
 667         {
 668         case BIT_FIELD_REF:
 669           {
 670             HOST_WIDE_INT this_off = TREE_INT_CST_LOW (TREE_OPERAND (exp, 2));
 671             if (this_off % BITS_PER_UNIT)
 672               return NULL_TREE;
 673             byte_offset += this_off / BITS_PER_UNIT;
 674           }
 675           break;
 676
 677         case COMPONENT_REF:
 678           {
 679             tree field = TREE_OPERAND (exp, 1);
 680             tree this_offset = component_ref_field_offset (exp);
 681             HOST_WIDE_INT hthis_offset;
 682
 683             if (!this_offset
 684                 || TREE_CODE (this_offset) != INTEGER_CST
 685                 || (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
 686                     % BITS_PER_UNIT))
 687               return NULL_TREE;
 688
 689             hthis_offset = TREE_INT_CST_LOW (this_offset);
 690             hthis_offset += (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
 691                              / BITS_PER_UNIT);
 692             byte_offset += hthis_offset;
 693           }
 694           break;
 695
 696         case ARRAY_REF:
 697         case ARRAY_RANGE_REF:
 698           {
 699             tree index = TREE_OPERAND (exp, 1);
 700             tree low_bound, unit_size;
 701
 702             if (valueize
 703                 && TREE_CODE (index) == SSA_NAME)
 704               index = (*valueize) (index);
 705
 706             /* If the resulting bit-offset is constant, track it.  */
 707             if (TREE_CODE (index) == INTEGER_CST
 708                 && (low_bound = array_ref_low_bound (exp),
 709                     TREE_CODE (low_bound) == INTEGER_CST)
 710                 && (unit_size = array_ref_element_size (exp),
 711                     TREE_CODE (unit_size) == INTEGER_CST))
 712               {
 713                 offset_int woffset
 714                   = wi::sext (wi::to_offset (index) - wi::to_offset (low_bound),
 715                               TYPE_PRECISION (TREE_TYPE (index)));
 716                 woffset *= wi::to_offset (unit_size);
 717                 byte_offset += woffset.to_shwi ();
 718               }
 719             else
 720               return NULL_TREE;
 721           }
 722           break;
 723
 724         case REALPART_EXPR:
 725           break;
 726
 727         case IMAGPART_EXPR:
 728           byte_offset += TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (exp)));
 729           break;
 730
 731         case VIEW_CONVERT_EXPR:
 732           break;
 733
 734         case MEM_REF:
 735           {
 736             tree base = TREE_OPERAND (exp, 0);
 737             if (valueize
 738                 && TREE_CODE (base) == SSA_NAME)
 739               base = (*valueize) (base);
 740
 741             /* Hand back the decl for MEM[&decl, off].  */
 742             if (TREE_CODE (base) == ADDR_EXPR)
 743               {
 744                 if (!integer_zerop (TREE_OPERAND (exp, 1)))
 745                   {
 746                     offset_int off = mem_ref_offset (exp);
 747                     byte_offset += off.to_short_addr ();
 748                   }
 749                 exp = TREE_OPERAND (base, 0);
 750               }
 751             goto done;
 752           }
 753
 754         case TARGET_MEM_REF:
 755           {
 756             tree base = TREE_OPERAND (exp, 0);
 757             if (valueize
 758                 && TREE_CODE (base) == SSA_NAME)
 759               base = (*valueize) (base);
 760
 761             /* Hand back the decl for MEM[&decl, off].  */
 762             if (TREE_CODE (base) == ADDR_EXPR)
 763               {
 764                 if (TMR_INDEX (exp) || TMR_INDEX2 (exp))
 765                   return NULL_TREE;
 766                 if (!integer_zerop (TMR_OFFSET (exp)))
 767                   {
 768                     offset_int off = mem_ref_offset (exp);
 769                     byte_offset += off.to_short_addr ();
 770                   }
 771                 exp = TREE_OPERAND (base, 0);
 772               }
 773             goto done;
 774           }
 775
 776         default:
 777           goto done;
 778         }
 779
 780       exp = TREE_OPERAND (exp, 0);
 781     }
 782 done:
 783
 784   *poffset = byte_offset;
 785   return exp;
 786 }
 787
 788 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
 789    denotes the starting address of the memory access EXP.
 790    Returns NULL_TREE if the offset is not constant or any component
 791    is not BITS_PER_UNIT-aligned.  */
 792
 793 tree
 794 get_addr_base_and_unit_offset (tree exp, HOST_WIDE_INT *poffset)
 795 {
 796   return get_addr_base_and_unit_offset_1 (exp, poffset, NULL);
 797 }
 798
 799 /* Returns true if STMT references an SSA_NAME that has
 800    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
 801
 802 bool
 803 stmt_references_abnormal_ssa_name (gimple *stmt)
 804 {
 805   ssa_op_iter oi;
 806   use_operand_p use_p;
 807
 808   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
 809     {
 810       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
 811         return true;
 812     }
 813
 814   return false;
 815 }
 816
 817 /* Pair of tree and a sorting index, for dump_enumerated_decls.  */
 818 struct GTY(()) numbered_tree
 819 {
 820   tree t;
 821   int num;
 822 };
 823
 824
 825 /* Compare two declarations references by their DECL_UID / sequence number.
 826    Called via qsort.  */
 827
 828 static int
 829 compare_decls_by_uid (const void *pa, const void *pb)
 830 {
 831   const numbered_tree *nt_a = ((const numbered_tree *)pa);
 832   const numbered_tree *nt_b = ((const numbered_tree *)pb);
 833
 834   if (DECL_UID (nt_a->t) != DECL_UID (nt_b->t))
 835     return  DECL_UID (nt_a->t) - DECL_UID (nt_b->t);
 836   return nt_a->num - nt_b->num;
 837 }
 838
 839 /* Called via walk_gimple_stmt / walk_gimple_op by dump_enumerated_decls.  */
 840 static tree
 841 dump_enumerated_decls_push (tree *tp, int *walk_subtrees, void *data)
 842 {
 843   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
 844   vec<numbered_tree> *list = (vec<numbered_tree> *) wi->info;
 845   numbered_tree nt;
 846
 847   if (!DECL_P (*tp))
 848     return NULL_TREE;
 849   nt.t = *tp;
 850   nt.num = list->length ();
 851   list->safe_push (nt);
 852   *walk_subtrees = 0;
 853   return NULL_TREE;
 854 }
 855
 856 /* Find all the declarations used by the current function, sort them by uid,
 857    and emit the sorted list.  Each declaration is tagged with a sequence
 858    number indicating when it was found during statement / tree walking,
 859    so that TDF_NOUID comparisons of anonymous declarations are still
 860    meaningful.  Where a declaration was encountered more than once, we
 861    emit only the sequence number of the first encounter.
 862    FILE is the dump file where to output the list and FLAGS is as in
 863    print_generic_expr.  */
 864 void
 865 dump_enumerated_decls (FILE *file, int flags)
 866 {
 867   basic_block bb;
 868   struct walk_stmt_info wi;
 869   auto_vec<numbered_tree, 40> decl_list;
 870
 871   memset (&wi, '\0', sizeof (wi));
 872   wi.info = (void *) &decl_list;
 873   FOR_EACH_BB_FN (bb, cfun)
 874     {
 875       gimple_stmt_iterator gsi;
 876
 877       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 878         if (!is_gimple_debug (gsi_stmt (gsi)))
 879           walk_gimple_stmt (&gsi, NULL, dump_enumerated_decls_push, &wi);
 880     }
 881   decl_list.qsort (compare_decls_by_uid);
 882   if (decl_list.length ())
 883     {
 884       unsigned ix;
 885       numbered_tree *ntp;
 886       tree last = NULL_TREE;
 887
 888       fprintf (file, "Declarations used by %s, sorted by DECL_UID:\n",
 889                current_function_name ());
 890       FOR_EACH_VEC_ELT (decl_list, ix, ntp)
 891         {
 892           if (ntp->t == last)
 893             continue;
 894           fprintf (file, "%d: ", ntp->num);
 895           print_generic_decl (file, ntp->t, flags);
 896           fprintf (file, "\n");
 897           last = ntp->t;
 898         }
 899     }
 900 }