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