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
 427             = double_int_add (bit_offset,
 428                               tree_to_double_int (TREE_OPERAND (exp, 2)));
 429           break;
 430
 431         case COMPONENT_REF:
 432           {
 433             tree field = TREE_OPERAND (exp, 1);
 434             tree this_offset = component_ref_field_offset (exp);
 435
 436             if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
 437               {
 438                 double_int doffset = tree_to_double_int (this_offset);
 439                 doffset = double_int_lshift (doffset,
 440                                              BITS_PER_UNIT == 8
 441                                              ? 3 : exact_log2 (BITS_PER_UNIT),
 442                                              HOST_BITS_PER_DOUBLE_INT, true);
 443                 doffset = double_int_add (doffset,
 444                                           tree_to_double_int
 445                                           (DECL_FIELD_BIT_OFFSET (field)));
 446                 bit_offset = double_int_add (bit_offset, doffset);
 447
 448                 /* If we had seen a variable array ref already and we just
 449                    referenced the last field of a struct or a union member
 450                    then we have to adjust maxsize by the padding at the end
 451                    of our field.  */
 452                 if (seen_variable_array_ref && maxsize != -1)
 453                   {
 454                     tree stype = TREE_TYPE (TREE_OPERAND (exp, 0));
 455                     tree next = DECL_CHAIN (field);
 456                     while (next && TREE_CODE (next) != FIELD_DECL)
 457                       next = DECL_CHAIN (next);
 458                     if (!next
 459                         || TREE_CODE (stype) != RECORD_TYPE)
 460                       {
 461                         tree fsize = DECL_SIZE_UNIT (field);
 462                         tree ssize = TYPE_SIZE_UNIT (stype);
 463                         if (host_integerp (fsize, 0)
 464                             && host_integerp (ssize, 0)
 465                             && double_int_fits_in_shwi_p (doffset))
 466                           maxsize += ((TREE_INT_CST_LOW (ssize)
 467                                        - TREE_INT_CST_LOW (fsize))
 468                                       * BITS_PER_UNIT
 469                                         - double_int_to_shwi (doffset));
 470                         else
 471                           maxsize = -1;
 472                       }
 473                   }
 474               }
 475             else
 476               {
 477                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 478                 /* We need to adjust maxsize to the whole structure bitsize.
 479                    But we can subtract any constant offset seen so far,
 480                    because that would get us out of the structure otherwise.  */
 481                 if (maxsize != -1
 482                     && csize
 483                     && host_integerp (csize, 1)
 484                     && double_int_fits_in_shwi_p (bit_offset))
 485                   maxsize = TREE_INT_CST_LOW (csize)
 486                             - double_int_to_shwi (bit_offset);
 487                 else
 488                   maxsize = -1;
 489               }
 490           }
 491           break;
 492
 493         case ARRAY_REF:
 494         case ARRAY_RANGE_REF:
 495           {
 496             tree index = TREE_OPERAND (exp, 1);
 497             tree low_bound, unit_size;
 498
 499             /* If the resulting bit-offset is constant, track it.  */
 500             if (TREE_CODE (index) == INTEGER_CST
 501                 && (low_bound = array_ref_low_bound (exp),
 502                     TREE_CODE (low_bound) == INTEGER_CST)
 503                 && (unit_size = array_ref_element_size (exp),
 504                     TREE_CODE (unit_size) == INTEGER_CST))
 505               {
 506                 double_int doffset
 507                   = double_int_sext
 508                     (double_int_sub (TREE_INT_CST (index),
 509                                      TREE_INT_CST (low_bound)),
 510                      TYPE_PRECISION (TREE_TYPE (index)));
 511                 doffset = double_int_mul (doffset,
 512                                           tree_to_double_int (unit_size));
 513                 doffset = double_int_lshift (doffset,
 514                                              BITS_PER_UNIT == 8
 515                                              ? 3 : exact_log2 (BITS_PER_UNIT),
 516                                              HOST_BITS_PER_DOUBLE_INT, true);
 517                 bit_offset = double_int_add (bit_offset, doffset);
 518
 519                 /* An array ref with a constant index up in the structure
 520                    hierarchy will constrain the size of any variable array ref
 521                    lower in the access hierarchy.  */
 522                 seen_variable_array_ref = false;
 523               }
 524             else
 525               {
 526                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
 527                 /* We need to adjust maxsize to the whole array bitsize.
 528                    But we can subtract any constant offset seen so far,
 529                    because that would get us outside of the array otherwise.  */
 530                 if (maxsize != -1
 531                     && asize
 532                     && host_integerp (asize, 1)
 533                     && double_int_fits_in_shwi_p (bit_offset))
 534                   maxsize = TREE_INT_CST_LOW (asize)
 535                             - double_int_to_shwi (bit_offset);
 536                 else
 537                   maxsize = -1;
 538
 539                 /* Remember that we have seen an array ref with a variable
 540                    index.  */
 541                 seen_variable_array_ref = true;
 542               }
 543           }
 544           break;
 545
 546         case REALPART_EXPR:
 547           break;
 548
 549         case IMAGPART_EXPR:
 550           bit_offset
 551             = double_int_add (bit_offset, uhwi_to_double_int (bitsize));
 552           break;
 553
 554         case VIEW_CONVERT_EXPR:
 555           break;
 556
 557         case MEM_REF:
 558           /* Hand back the decl for MEM[&decl, off].  */
 559           if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR)
 560             {
 561               if (integer_zerop (TREE_OPERAND (exp, 1)))
 562                 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 563               else
 564                 {
 565                   double_int off = mem_ref_offset (exp);
 566                   off = double_int_lshift (off,
 567                                            BITS_PER_UNIT == 8
 568                                            ? 3 : exact_log2 (BITS_PER_UNIT),
 569                                            HOST_BITS_PER_DOUBLE_INT, true);
 570                   off = double_int_add (off, bit_offset);
 571                   if (double_int_fits_in_shwi_p (off))
 572                     {
 573                       bit_offset = off;
 574                       exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
 575                     }
 576                 }
 577             }
 578           goto done;
 579
 580         case TARGET_MEM_REF:
 581           /* Hand back the decl for MEM[&decl, off].  */
 582           if (TREE_CODE (TMR_BASE (exp)) == ADDR_EXPR)
 583             {
 584               /* Via the variable index or index2 we can reach the
 585                  whole object.  */
 586               if (TMR_INDEX (exp) || TMR_INDEX2 (exp))
 587                 {
 588                   exp = TREE_OPERAND (TMR_BASE (exp), 0);
 589                   bit_offset = double_int_zero;
 590                   maxsize = -1;
 591                   goto done;
 592                 }
 593               if (integer_zerop (TMR_OFFSET (exp)))
 594                 exp = TREE_OPERAND (TMR_BASE (exp), 0);
 595               else
 596                 {
 597                   double_int off = mem_ref_offset (exp);
 598                   off = double_int_lshift (off,
 599                                            BITS_PER_UNIT == 8
 600                                            ? 3 : exact_log2 (BITS_PER_UNIT),
 601                                            HOST_BITS_PER_DOUBLE_INT, true);
 602                   off = double_int_add (off, bit_offset);
 603                   if (double_int_fits_in_shwi_p (off))
 604                     {
 605                       bit_offset = off;
 606                       exp = TREE_OPERAND (TMR_BASE (exp), 0);
 607                     }
 608                 }
 609             }
 610           goto done;
 611
 612         default:
 613           goto done;
 614         }
 615
 616       exp = TREE_OPERAND (exp, 0);
 617     }
 618  done:
 619
 620   if (!double_int_fits_in_shwi_p (bit_offset))
 621     {
 622       *poffset = 0;
 623       *psize = bitsize;
 624       *pmax_size = -1;
 625
 626       return exp;
 627     }
 628
 629   hbit_offset = double_int_to_shwi (bit_offset);
 630
 631   /* We need to deal with variable arrays ending structures such as
 632        struct { int length; int a[1]; } x;           x.a[d]
 633        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
 634        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
 635        struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d]
 636      where we do not know maxsize for variable index accesses to
 637      the array.  The simplest way to conservatively deal with this
 638      is to punt in the case that offset + maxsize reaches the
 639      base type boundary.  This needs to include possible trailing padding
 640      that is there for alignment purposes.  */
 641
 642   if (seen_variable_array_ref
 643       && maxsize != -1
 644       && (!host_integerp (TYPE_SIZE (base_type), 1)
 645           || (hbit_offset + maxsize
 646               == (signed) TREE_INT_CST_LOW (TYPE_SIZE (base_type)))))
 647     maxsize = -1;
 648
 649   /* In case of a decl or constant base object we can do better.  */
 650
 651   if (DECL_P (exp))
 652     {
 653       /* If maxsize is unknown adjust it according to the size of the
 654          base decl.  */
 655       if (maxsize == -1
 656           && host_integerp (DECL_SIZE (exp), 1))
 657         maxsize = TREE_INT_CST_LOW (DECL_SIZE (exp)) - hbit_offset;
 658     }
 659   else if (CONSTANT_CLASS_P (exp))
 660     {
 661       /* If maxsize is unknown adjust it according to the size of the
 662          base type constant.  */
 663       if (maxsize == -1
 664           && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1))
 665         maxsize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))) - hbit_offset;
 666     }
 667
 668   /* ???  Due to negative offsets in ARRAY_REF we can end up with
 669      negative bit_offset here.  We might want to store a zero offset
 670      in this case.  */
 671   *poffset = hbit_offset;
 672   *psize = bitsize;
 673   *pmax_size = maxsize;
 674
 675   return exp;
 676 }
 677
 678 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
 679    denotes the starting address of the memory access EXP.
 680    Returns NULL_TREE if the offset is not constant or any component
 681    is not BITS_PER_UNIT-aligned.  */
 682
 683 tree
 684 get_addr_base_and_unit_offset (tree exp, HOST_WIDE_INT *poffset)
 685 {
 686   return get_addr_base_and_unit_offset_1 (exp, poffset, NULL);
 687 }
 688
 689 /* Returns true if STMT references an SSA_NAME that has
 690    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
 691
 692 bool
 693 stmt_references_abnormal_ssa_name (gimple stmt)
 694 {
 695   ssa_op_iter oi;
 696   use_operand_p use_p;
 697
 698   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
 699     {
 700       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
 701         return true;
 702     }
 703
 704   return false;
 705 }
 706
 707 /* Pair of tree and a sorting index, for dump_enumerated_decls.  */
 708 struct GTY(()) numbered_tree_d
 709 {
 710   tree t;
 711   int num;
 712 };
 713 typedef struct numbered_tree_d numbered_tree;
 714
 715 DEF_VEC_O (numbered_tree);
 716 DEF_VEC_ALLOC_O (numbered_tree, heap);
 717
 718 /* Compare two declarations references by their DECL_UID / sequence number.
 719    Called via qsort.  */
 720
 721 static int
 722 compare_decls_by_uid (const void *pa, const void *pb)
 723 {
 724   const numbered_tree *nt_a = ((const numbered_tree *)pa);
 725   const numbered_tree *nt_b = ((const numbered_tree *)pb);
 726
 727   if (DECL_UID (nt_a->t) != DECL_UID (nt_b->t))
 728     return  DECL_UID (nt_a->t) - DECL_UID (nt_b->t);
 729   return nt_a->num - nt_b->num;
 730 }
 731
 732 /* Called via walk_gimple_stmt / walk_gimple_op by dump_enumerated_decls.  */
 733 static tree
 734 dump_enumerated_decls_push (tree *tp, int *walk_subtrees, void *data)
 735 {
 736   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
 737   VEC (numbered_tree, heap) **list = (VEC (numbered_tree, heap) **) &wi->info;
 738   numbered_tree nt;
 739
 740   if (!DECL_P (*tp))
 741     return NULL_TREE;
 742   nt.t = *tp;
 743   nt.num = VEC_length (numbered_tree, *list);
 744   VEC_safe_push (numbered_tree, heap, *list, &nt);
 745   *walk_subtrees = 0;
 746   return NULL_TREE;
 747 }
 748
 749 /* Find all the declarations used by the current function, sort them by uid,
 750    and emit the sorted list.  Each declaration is tagged with a sequence
 751    number indicating when it was found during statement / tree walking,
 752    so that TDF_NOUID comparisons of anonymous declarations are still
 753    meaningful.  Where a declaration was encountered more than once, we
 754    emit only the sequence number of the first encounter.
 755    FILE is the dump file where to output the list and FLAGS is as in
 756    print_generic_expr.  */
 757 void
 758 dump_enumerated_decls (FILE *file, int flags)
 759 {
 760   basic_block bb;
 761   struct walk_stmt_info wi;
 762   VEC (numbered_tree, heap) *decl_list = VEC_alloc (numbered_tree, heap, 40);
 763
 764   memset (&wi, '\0', sizeof (wi));
 765   wi.info = (void*) decl_list;
 766   FOR_EACH_BB (bb)
 767     {
 768       gimple_stmt_iterator gsi;
 769
 770       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 771         if (!is_gimple_debug (gsi_stmt (gsi)))
 772           walk_gimple_stmt (&gsi, NULL, dump_enumerated_decls_push, &wi);
 773     }
 774   decl_list = (VEC (numbered_tree, heap) *) wi.info;
 775   VEC_qsort (numbered_tree, decl_list, compare_decls_by_uid);
 776   if (VEC_length (numbered_tree, decl_list))
 777     {
 778       unsigned ix;
 779       numbered_tree *ntp;
 780       tree last = NULL_TREE;
 781
 782       fprintf (file, "Declarations used by %s, sorted by DECL_UID:\n",
 783                current_function_name ());
 784       FOR_EACH_VEC_ELT (numbered_tree, decl_list, ix, ntp)
 785         {
 786           if (ntp->t == last)
 787             continue;
 788           fprintf (file, "%d: ", ntp->num);
 789           print_generic_decl (file, ntp->t, flags);
 790           fprintf (file, "\n");
 791           last = ntp->t;
 792         }
 793     }
 794   VEC_free (numbered_tree, heap, decl_list);
 795 }
 796