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