gcc/tree-dfa.c

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