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