gcc/tree-ssa-dse.c

   1 /* Dead store elimination
   2    Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  19 Boston, MA 02110-1301, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "ggc.h"
  26 #include "tree.h"
  27 #include "rtl.h"
  28 #include "tm_p.h"
  29 #include "basic-block.h"
  30 #include "timevar.h"
  31 #include "diagnostic.h"
  32 #include "tree-flow.h"
  33 #include "tree-pass.h"
  34 #include "tree-dump.h"
  35 #include "domwalk.h"
  36 #include "flags.h"
  37 #include "hashtab.h"
  38 #include "sbitmap.h"
  39
  40 /* This file implements dead store elimination.
  41
  42    A dead store is a store into a memory location which will later be
  43    overwritten by another store without any intervening loads.  In this
  44    case the earlier store can be deleted.
  45
  46    In our SSA + virtual operand world we use immediate uses of virtual
  47    operands to detect dead stores.  If a store's virtual definition
  48    is used precisely once by a later store to the same location which
  49    post dominates the first store, then the first store is dead.
  50
  51    The single use of the store's virtual definition ensures that
  52    there are no intervening aliased loads and the requirement that
  53    the second load post dominate the first ensures that if the earlier
  54    store executes, then the later stores will execute before the function
  55    exits.
  56
  57    It may help to think of this as first moving the earlier store to
  58    the point immediately before the later store.  Again, the single
  59    use of the virtual definition and the post-dominance relationship
  60    ensure that such movement would be safe.  Clearly if there are
  61    back to back stores, then the second is redundant.
  62
  63    Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
  64    may also help in understanding this code since it discusses the
  65    relationship between dead store and redundant load elimination.  In
  66    fact, they are the same transformation applied to different views of
  67    the CFG.  */
  68
  69
  70 /* Given an aggregate, this records the parts of it which have been
  71    stored into.  */
  72 struct aggregate_vardecl_d
  73 {
  74   /* The aggregate.  */
  75   tree decl;
  76
  77   /* Some aggregates are too big for us to handle or never get stored
  78      to as a whole.  If this field is TRUE, we don't care about this
  79      aggregate.  */
  80   bool ignore;
  81
  82   /* Number of parts in the whole.  */
  83   unsigned nparts;
  84
  85   /* A bitmap of parts of the aggregate that have been set.  If part N
  86      of an aggregate has been stored to, bit N should be on.  */
  87   sbitmap parts_set;
  88 };
  89
  90 struct dse_global_data
  91 {
  92   /* This is the global bitmap for store statements.
  93
  94      Each statement has a unique ID.  When we encounter a store statement
  95      that we want to record, set the bit corresponding to the statement's
  96      unique ID in this bitmap.  */
  97   bitmap stores;
  98
  99   /* A hash table containing the parts of an aggregate which have been
 100      stored to.  */
 101   htab_t aggregate_vardecl;
 102 };
 103
 104 /* We allocate a bitmap-per-block for stores which are encountered
 105    during the scan of that block.  This allows us to restore the
 106    global bitmap of stores when we finish processing a block.  */
 107 struct dse_block_local_data
 108 {
 109   bitmap stores;
 110 };
 111
 112 /* Basic blocks of the potentially dead store and the following
 113    store, for memory_address_same.  */
 114 struct address_walk_data
 115 {
 116   basic_block store1_bb, store2_bb;
 117 };
 118
 119 static bool gate_dse (void);
 120 static unsigned int tree_ssa_dse (void);
 121 static void dse_initialize_block_local_data (struct dom_walk_data *,
 122                                              basic_block,
 123                                              bool);
 124 static void dse_optimize_stmt (struct dom_walk_data *,
 125                                basic_block,
 126                                block_stmt_iterator);
 127 static void dse_record_phis (struct dom_walk_data *, basic_block);
 128 static void dse_finalize_block (struct dom_walk_data *, basic_block);
 129 static void record_voperand_set (bitmap, bitmap *, unsigned int);
 130 static void dse_record_partial_aggregate_store (tree, struct dse_global_data *);
 131
 132 static unsigned max_stmt_uid;   /* Maximal uid of a statement.  Uids to phi
 133                                    nodes are assigned using the versions of
 134                                    ssa names they define.  */
 135
 136 /* Returns uid of statement STMT.  */
 137
 138 static unsigned
 139 get_stmt_uid (tree stmt)
 140 {
 141   if (TREE_CODE (stmt) == PHI_NODE)
 142     return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;
 143
 144   return stmt_ann (stmt)->uid;
 145 }
 146
 147 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed.  */
 148
 149 static void
 150 record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
 151 {
 152   /* Lazily allocate the bitmap.  Note that we do not get a notification
 153      when the block local data structures die, so we allocate the local
 154      bitmap backed by the GC system.  */
 155   if (*local == NULL)
 156     *local = BITMAP_GGC_ALLOC ();
 157
 158   /* Set the bit in the local and global bitmaps.  */
 159   bitmap_set_bit (*local, uid);
 160   bitmap_set_bit (global, uid);
 161 }
 162
 163 /* Initialize block local data structures.  */
 164
 165 static void
 166 dse_initialize_block_local_data (struct dom_walk_data *walk_data,
 167                                  basic_block bb ATTRIBUTE_UNUSED,
 168                                  bool recycled)
 169 {
 170   struct dse_block_local_data *bd
 171     = (struct dse_block_local_data *)
 172         VEC_last (void_p, walk_data->block_data_stack);
 173
 174   /* If we are given a recycled block local data structure, ensure any
 175      bitmap associated with the block is cleared.  */
 176   if (recycled)
 177     {
 178       if (bd->stores)
 179         bitmap_clear (bd->stores);
 180     }
 181 }
 182
 183 /* Helper function for memory_address_same via walk_tree.  Returns
 184    non-NULL if it finds an SSA_NAME which is part of the address,
 185    such that the definition of the SSA_NAME post-dominates the store
 186    we want to delete but not the store that we believe makes it
 187    redundant.  This indicates that the address may change between
 188    the two stores.  */
 189
 190 static tree
 191 memory_ssa_name_same (tree *expr_p, int *walk_subtrees ATTRIBUTE_UNUSED,
 192                       void *data)
 193 {
 194   struct address_walk_data *walk_data = (struct address_walk_data *) data;
 195   tree expr = *expr_p;
 196   tree def_stmt;
 197   basic_block def_bb;
 198
 199   if (TREE_CODE (expr) != SSA_NAME)
 200     return NULL_TREE;
 201
 202   /* If we've found a default definition, then there's no problem.  Both
 203      stores will post-dominate it.  And def_bb will be NULL.  */
 204   if (SSA_NAME_IS_DEFAULT_DEF (expr))
 205     return NULL_TREE;
 206
 207   def_stmt = SSA_NAME_DEF_STMT (expr);
 208   def_bb = bb_for_stmt (def_stmt);
 209
 210   /* DEF_STMT must dominate both stores.  So if it is in the same
 211      basic block as one, it does not post-dominate that store.  */
 212   if (walk_data->store1_bb != def_bb
 213       && dominated_by_p (CDI_POST_DOMINATORS, walk_data->store1_bb, def_bb))
 214     {
 215       if (walk_data->store2_bb == def_bb
 216           || !dominated_by_p (CDI_POST_DOMINATORS, walk_data->store2_bb,
 217                               def_bb))
 218         /* Return non-NULL to stop the walk.  */
 219         return def_stmt;
 220     }
 221
 222   return NULL_TREE;
 223 }
 224
 225 /* Return TRUE if the destination memory address in STORE1 and STORE2
 226    might be modified after STORE1, before control reaches STORE2.  */
 227
 228 static bool
 229 memory_address_same (tree store1, tree store2)
 230 {
 231   struct address_walk_data walk_data;
 232
 233   walk_data.store1_bb = bb_for_stmt (store1);
 234   walk_data.store2_bb = bb_for_stmt (store2);
 235
 236   return (walk_tree (&GIMPLE_STMT_OPERAND (store1, 0), memory_ssa_name_same,
 237                      &walk_data, NULL)
 238           == NULL);
 239 }
 240
 241 /* Return the use stmt for the lhs of STMT following the virtual
 242    def-use chains.  Returns the MODIFY_EXPR stmt which lhs is equal to
 243    the lhs of STMT or NULL_TREE if no such stmt can be found.  */
 244 static tree
 245 get_use_of_stmt_lhs (tree stmt,
 246                      use_operand_p * first_use_p,
 247                      use_operand_p * use_p, tree * use_stmt)
 248 {
 249   tree usevar, lhs;
 250   def_operand_p def_p;
 251
 252   if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
 253     return NULL_TREE;
 254
 255   lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 256
 257   /* The stmt must have a single VDEF.  */
 258   def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_VDEF);
 259   if (def_p == NULL_DEF_OPERAND_P)
 260     return NULL_TREE;
 261
 262   if (!has_single_use (DEF_FROM_PTR (def_p)))
 263     return NULL_TREE;
 264   /* Get the immediate use of the def.  */
 265   single_imm_use (DEF_FROM_PTR (def_p), use_p, use_stmt);
 266   gcc_assert (*use_p != NULL_USE_OPERAND_P);
 267   first_use_p = use_p;
 268   if (TREE_CODE (*use_stmt) != GIMPLE_MODIFY_STMT)
 269     return NULL_TREE;
 270
 271   do
 272     {
 273       /* Look at the use stmt and see if it's LHS matches
 274          stmt's lhs SSA_NAME.  */
 275       def_p = SINGLE_SSA_DEF_OPERAND (*use_stmt, SSA_OP_VDEF);
 276       if (def_p == NULL_DEF_OPERAND_P)
 277         return NULL_TREE;
 278
 279       usevar = GIMPLE_STMT_OPERAND (*use_stmt, 0);
 280       if (operand_equal_p (usevar, lhs, 0))
 281         return *use_stmt;
 282
 283       if (!has_single_use (DEF_FROM_PTR (def_p)))
 284         return NULL_TREE;
 285       single_imm_use (DEF_FROM_PTR (def_p), use_p, use_stmt);
 286       gcc_assert (*use_p != NULL_USE_OPERAND_P);
 287       if (TREE_CODE (*use_stmt) != GIMPLE_MODIFY_STMT)
 288         return NULL_TREE;
 289     }
 290   while (1);
 291
 292   return NULL_TREE;
 293 }
 294
 295 /* A helper of dse_optimize_stmt.
 296    Given a GIMPLE_MODIFY_STMT in STMT, check that each VDEF has one
 297    use, and that one use is another VDEF clobbering the first one.
 298
 299    Return TRUE if the above conditions are met, otherwise FALSE.  */
 300
 301 static bool
 302 dse_possible_dead_store_p (tree stmt,
 303                            use_operand_p *first_use_p,
 304                            use_operand_p *use_p,
 305                            tree *use_stmt,
 306                            struct dse_global_data *dse_gd,
 307                            struct dse_block_local_data *bd)
 308 {
 309   ssa_op_iter op_iter;
 310   bool fail = false;
 311   def_operand_p var1;
 312   vuse_vec_p vv;
 313   tree defvar = NULL_TREE, temp;
 314   tree prev_defvar = NULL_TREE;
 315   stmt_ann_t ann = stmt_ann (stmt);
 316
 317   /* We want to verify that each virtual definition in STMT has
 318      precisely one use and that all the virtual definitions are
 319      used by the same single statement.  When complete, we
 320      want USE_STMT to refer to the one statement which uses
 321      all of the virtual definitions from STMT.  */
 322   *use_stmt = NULL;
 323   FOR_EACH_SSA_VDEF_OPERAND (var1, vv, stmt, op_iter)
 324     {
 325       defvar = DEF_FROM_PTR (var1);
 326
 327       /* If this virtual def does not have precisely one use, then
 328          we will not be able to eliminate STMT.  */
 329       if (!has_single_use (defvar))
 330         {
 331           fail = true;
 332           break;
 333         }
 334
 335       /* Get the one and only immediate use of DEFVAR.  */
 336       single_imm_use (defvar, use_p, &temp);
 337       gcc_assert (*use_p != NULL_USE_OPERAND_P);
 338       *first_use_p = *use_p;
 339
 340       /* In the case of memory partitions, we may get:
 341
 342            # MPT.764_162 = VDEF <MPT.764_161(D)>
 343            x = {};
 344            # MPT.764_167 = VDEF <MPT.764_162>
 345            y = {};
 346
 347            So we must make sure we're talking about the same LHS.
 348       */
 349       if (TREE_CODE (temp) == GIMPLE_MODIFY_STMT)
 350         {
 351           tree base1 = get_base_address (GIMPLE_STMT_OPERAND (stmt, 0));
 352           tree base2 =  get_base_address (GIMPLE_STMT_OPERAND (temp, 0));
 353
 354           while (base1 && INDIRECT_REF_P (base1))
 355             base1 = TREE_OPERAND (base1, 0);
 356           while (base2 && INDIRECT_REF_P (base2))
 357             base2 = TREE_OPERAND (base2, 0);
 358
 359           if (base1 != base2)
 360             {
 361               fail = true;
 362               break;
 363             }
 364         }
 365
 366       /* If the immediate use of DEF_VAR is not the same as the
 367          previously find immediate uses, then we will not be able
 368          to eliminate STMT.  */
 369       if (*use_stmt == NULL)
 370         {
 371           *use_stmt = temp;
 372           prev_defvar = defvar;
 373         }
 374       else if (temp != *use_stmt)
 375         {
 376           /* The immediate use and the previously found immediate use
 377              must be the same, except... if they're uses of different
 378              parts of the whole.  */
 379           if (TREE_CODE (defvar) == SSA_NAME
 380               && TREE_CODE (SSA_NAME_VAR (defvar)) == STRUCT_FIELD_TAG
 381               && TREE_CODE (prev_defvar) == SSA_NAME
 382               && TREE_CODE (SSA_NAME_VAR (prev_defvar)) == STRUCT_FIELD_TAG
 383               && (SFT_PARENT_VAR (SSA_NAME_VAR (defvar))
 384                   == SFT_PARENT_VAR (SSA_NAME_VAR (prev_defvar))))
 385             ;
 386           else
 387             {
 388               fail = true;
 389               break;
 390             }
 391         }
 392     }
 393
 394   if (fail)
 395     {
 396       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 397       dse_record_partial_aggregate_store (stmt, dse_gd);
 398       return false;
 399     }
 400
 401   /* Skip through any PHI nodes we have already seen if the PHI
 402      represents the only use of this store.
 403
 404      Note this does not handle the case where the store has
 405      multiple VDEFs which all reach a set of PHI nodes in the same block.  */
 406   while (*use_p != NULL_USE_OPERAND_P
 407          && TREE_CODE (*use_stmt) == PHI_NODE
 408          && bitmap_bit_p (dse_gd->stores, get_stmt_uid (*use_stmt)))
 409     {
 410       /* A PHI node can both define and use the same SSA_NAME if
 411          the PHI is at the top of a loop and the PHI_RESULT is
 412          a loop invariant and copies have not been fully propagated.
 413
 414          The safe thing to do is exit assuming no optimization is
 415          possible.  */
 416       if (SSA_NAME_DEF_STMT (PHI_RESULT (*use_stmt)) == *use_stmt)
 417         return false;
 418
 419       /* Skip past this PHI and loop again in case we had a PHI
 420          chain.  */
 421       single_imm_use (PHI_RESULT (*use_stmt), use_p, use_stmt);
 422     }
 423
 424   return true;
 425 }
 426
 427
 428 /* Given a DECL, return its AGGREGATE_VARDECL_D entry.  If no entry is
 429    found and INSERT is TRUE, add a new entry.  */
 430
 431 static struct aggregate_vardecl_d *
 432 get_aggregate_vardecl (tree decl, struct dse_global_data *dse_gd, bool insert)
 433 {
 434   struct aggregate_vardecl_d av, *av_p;
 435   void **slot;
 436
 437   av.decl = decl;
 438   slot = htab_find_slot (dse_gd->aggregate_vardecl, &av, insert ? INSERT : NO_INSERT);
 439
 440
 441   /* Not found, and we don't want to insert.  */
 442   if (slot == NULL)
 443     return NULL;
 444
 445   /* Create new entry.  */
 446   if (*slot == NULL)
 447     {
 448       av_p = XNEW (struct aggregate_vardecl_d);
 449       av_p->decl = decl;
 450
 451       /* Record how many parts the whole has.  */
 452       if (TREE_CODE (TREE_TYPE (decl)) == COMPLEX_TYPE)
 453         av_p->nparts = 2;
 454       else if (TREE_CODE (TREE_TYPE (decl)) == RECORD_TYPE)
 455         {
 456           tree fields;
 457
 458           /* Count the number of fields.  */
 459           fields = TYPE_FIELDS (TREE_TYPE (decl));
 460           av_p->nparts = 0;
 461           while (fields)
 462             {
 463               av_p->nparts++;
 464               fields = TREE_CHAIN (fields);
 465             }
 466         }
 467       else
 468         abort ();
 469
 470       av_p->ignore = true;
 471       av_p->parts_set = sbitmap_alloc (HOST_BITS_PER_LONG);
 472       sbitmap_zero (av_p->parts_set);
 473       *slot = av_p;
 474     }
 475   else
 476     av_p = (struct aggregate_vardecl_d *) *slot;
 477
 478   return av_p;
 479 }
 480
 481
 482 /* If STMT is a partial store into an aggregate, record which part got set.  */
 483
 484 static void
 485 dse_record_partial_aggregate_store (tree stmt, struct dse_global_data *dse_gd)
 486 {
 487   tree lhs, decl;
 488   enum tree_code code;
 489   struct aggregate_vardecl_d *av_p;
 490   int part;
 491
 492   gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
 493
 494   lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 495   code = TREE_CODE (lhs);
 496   if (code != IMAGPART_EXPR
 497       && code != REALPART_EXPR
 498       && code != COMPONENT_REF)
 499     return;
 500   decl = TREE_OPERAND (lhs, 0);
 501   /* Early bail on things like nested COMPONENT_REFs.  */
 502   if (TREE_CODE (decl) != VAR_DECL)
 503     return;
 504   /* Early bail on unions.  */
 505   if (code == COMPONENT_REF
 506       && TREE_CODE (TREE_TYPE (TREE_OPERAND (lhs, 0))) != RECORD_TYPE)
 507     return;
 508
 509   av_p = get_aggregate_vardecl (decl, dse_gd, /*insert=*/false);
 510   /* Run away, this isn't an aggregate we care about.  */
 511   if (!av_p || av_p->ignore)
 512     return;
 513
 514   switch (code)
 515     {
 516     case IMAGPART_EXPR:
 517       part = 0;
 518       break;
 519     case REALPART_EXPR:
 520       part = 1;
 521       break;
 522     case COMPONENT_REF:
 523       {
 524         tree orig_field, fields;
 525         tree record_type = TREE_TYPE (TREE_OPERAND (lhs, 0));
 526
 527         /* Get FIELD_DECL.  */
 528         orig_field = TREE_OPERAND (lhs, 1);
 529
 530         /* FIXME: Eeech, do this more efficiently.  Perhaps
 531            calculate bit/byte offsets.  */
 532         part = -1;
 533         fields = TYPE_FIELDS (record_type);
 534         while (fields)
 535           {
 536             ++part;
 537             if (fields == orig_field)
 538               break;
 539             fields = TREE_CHAIN (fields);
 540           }
 541         gcc_assert (part >= 0);
 542       }
 543       break;
 544     default:
 545       return;
 546     }
 547
 548   /* Record which part was set.  */
 549   SET_BIT (av_p->parts_set, part);
 550 }
 551
 552
 553 /* Return TRUE if all parts in an AGGREGATE_VARDECL have been set.  */
 554
 555 static inline bool
 556 dse_whole_aggregate_clobbered_p (struct aggregate_vardecl_d *av_p)
 557 {
 558   unsigned int i;
 559   sbitmap_iterator sbi;
 560   int nbits_set = 0;
 561
 562   /* Count the number of partial stores (bits set).  */
 563   EXECUTE_IF_SET_IN_SBITMAP (av_p->parts_set, 0, i, sbi)
 564     nbits_set++;
 565   return ((unsigned) nbits_set == av_p->nparts);
 566 }
 567
 568
 569 /* Return TRUE if STMT is a store into a whole aggregate whose parts we
 570    have already seen and recorded.  */
 571
 572 static bool
 573 dse_partial_kill_p (tree stmt, struct dse_global_data *dse_gd)
 574 {
 575   tree decl;
 576   struct aggregate_vardecl_d *av_p;
 577
 578   /* Make sure this is a store into the whole.  */
 579   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 580     {
 581       enum tree_code code;
 582
 583       decl = GIMPLE_STMT_OPERAND (stmt, 0);
 584       code = TREE_CODE (TREE_TYPE (decl));
 585
 586       if (code != COMPLEX_TYPE && code != RECORD_TYPE)
 587         return false;
 588
 589       if (TREE_CODE (decl) != VAR_DECL)
 590         return false;
 591     }
 592   else
 593     return false;
 594
 595   av_p = get_aggregate_vardecl (decl, dse_gd, /*insert=*/false);
 596   gcc_assert (av_p != NULL);
 597
 598   return dse_whole_aggregate_clobbered_p (av_p);
 599 }
 600
 601
 602 /* Attempt to eliminate dead stores in the statement referenced by BSI.
 603
 604    A dead store is a store into a memory location which will later be
 605    overwritten by another store without any intervening loads.  In this
 606    case the earlier store can be deleted.
 607
 608    In our SSA + virtual operand world we use immediate uses of virtual
 609    operands to detect dead stores.  If a store's virtual definition
 610    is used precisely once by a later store to the same location which
 611    post dominates the first store, then the first store is dead.  */
 612
 613 static void
 614 dse_optimize_stmt (struct dom_walk_data *walk_data,
 615                    basic_block bb ATTRIBUTE_UNUSED,
 616                    block_stmt_iterator bsi)
 617 {
 618   struct dse_block_local_data *bd
 619     = (struct dse_block_local_data *)
 620         VEC_last (void_p, walk_data->block_data_stack);
 621   struct dse_global_data *dse_gd
 622     = (struct dse_global_data *) walk_data->global_data;
 623   tree stmt = bsi_stmt (bsi);
 624   stmt_ann_t ann = stmt_ann (stmt);
 625
 626   /* If this statement has no virtual defs, then there is nothing
 627      to do.  */
 628   if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF))
 629     return;
 630
 631   /* We know we have virtual definitions.  If this is a GIMPLE_MODIFY_STMT
 632      that's not also a function call, then record it into our table.  */
 633   if (get_call_expr_in (stmt))
 634     return;
 635
 636   if (ann->has_volatile_ops)
 637     return;
 638
 639   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 640     {
 641       use_operand_p first_use_p = NULL_USE_OPERAND_P;
 642       use_operand_p use_p = NULL;
 643       tree use_stmt;
 644
 645       if (!dse_possible_dead_store_p (stmt, &first_use_p, &use_p, &use_stmt,
 646                                       dse_gd, bd))
 647         return;
 648
 649       /* If this is a partial store into an aggregate, record it.  */
 650       dse_record_partial_aggregate_store (stmt, dse_gd);
 651
 652       if (use_p != NULL_USE_OPERAND_P
 653           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
 654           && (!operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
 655                                 GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
 656               && !dse_partial_kill_p (stmt, dse_gd))
 657           && memory_address_same (stmt, use_stmt))
 658         {
 659           /* If we have precisely one immediate use at this point, but
 660              the stores are not to the same memory location then walk the
 661              virtual def-use chain to get the stmt which stores to that same
 662              memory location.  */
 663           if (get_use_of_stmt_lhs (stmt, &first_use_p, &use_p, &use_stmt) ==
 664               NULL_TREE)
 665             {
 666               record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 667               return;
 668             }
 669         }
 670
 671       /* If we have precisely one immediate use at this point and the
 672          stores are to the same memory location or there is a chain of
 673          virtual uses from stmt and the stmt which stores to that same
 674          memory location, then we may have found redundant store.  */
 675       if (use_p != NULL_USE_OPERAND_P
 676           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
 677           && (operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
 678                                GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
 679               || dse_partial_kill_p (stmt, dse_gd))
 680           && memory_address_same (stmt, use_stmt))
 681         {
 682           ssa_op_iter op_iter;
 683           def_operand_p var1;
 684           vuse_vec_p vv;
 685           tree stmt_lhs;
 686
 687           if (dump_file && (dump_flags & TDF_DETAILS))
 688             {
 689               fprintf (dump_file, "  Deleted dead store '");
 690               print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
 691               fprintf (dump_file, "'\n");
 692             }
 693
 694           /* Then we need to fix the operand of the consuming stmt.  */
 695           stmt_lhs = USE_FROM_PTR (first_use_p);
 696           FOR_EACH_SSA_VDEF_OPERAND (var1, vv, stmt, op_iter)
 697             {
 698               tree usevar, temp;
 699
 700               single_imm_use (DEF_FROM_PTR (var1), &use_p, &temp);
 701               gcc_assert (VUSE_VECT_NUM_ELEM (*vv) == 1);
 702               usevar = VUSE_ELEMENT_VAR (*vv, 0);
 703               SET_USE (use_p, usevar);
 704
 705               /* Make sure we propagate the ABNORMAL bit setting.  */
 706               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (stmt_lhs))
 707                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
 708             }
 709
 710           /* Remove the dead store.  */
 711           bsi_remove (&bsi, true);
 712
 713           /* And release any SSA_NAMEs set in this statement back to the
 714              SSA_NAME manager.  */
 715           release_defs (stmt);
 716         }
 717
 718       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 719     }
 720 }
 721
 722 /* Record that we have seen the PHIs at the start of BB which correspond
 723    to virtual operands.  */
 724 static void
 725 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
 726 {
 727   struct dse_block_local_data *bd
 728     = (struct dse_block_local_data *)
 729         VEC_last (void_p, walk_data->block_data_stack);
 730   struct dse_global_data *dse_gd
 731     = (struct dse_global_data *) walk_data->global_data;
 732   tree phi;
 733
 734   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 735     if (!is_gimple_reg (PHI_RESULT (phi)))
 736       record_voperand_set (dse_gd->stores,
 737                            &bd->stores,
 738                            get_stmt_uid (phi));
 739 }
 740
 741 static void
 742 dse_finalize_block (struct dom_walk_data *walk_data,
 743                     basic_block bb ATTRIBUTE_UNUSED)
 744 {
 745   struct dse_block_local_data *bd
 746     = (struct dse_block_local_data *)
 747         VEC_last (void_p, walk_data->block_data_stack);
 748   struct dse_global_data *dse_gd
 749     = (struct dse_global_data *) walk_data->global_data;
 750   bitmap stores = dse_gd->stores;
 751   unsigned int i;
 752   bitmap_iterator bi;
 753
 754   /* Unwind the stores noted in this basic block.  */
 755   if (bd->stores)
 756     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
 757       {
 758         bitmap_clear_bit (stores, i);
 759       }
 760 }
 761
 762
 763 /* Hashing and equality functions for AGGREGATE_VARDECL.  */
 764
 765 static hashval_t
 766 aggregate_vardecl_hash (const void *p)
 767 {
 768   return htab_hash_pointer
 769     ((const void *)((const struct aggregate_vardecl_d *)p)->decl);
 770 }
 771
 772 static int
 773 aggregate_vardecl_eq (const void *p1, const void *p2)
 774 {
 775   return ((const struct aggregate_vardecl_d *)p1)->decl
 776     == ((const struct aggregate_vardecl_d *)p2)->decl;
 777 }
 778
 779
 780 /* Free memory allocated by one entry in AGGREGATE_VARDECL.  */
 781
 782 static void
 783 aggregate_vardecl_free (void *p)
 784 {
 785   struct aggregate_vardecl_d *entry = (struct aggregate_vardecl_d *) p;
 786   sbitmap_free (entry->parts_set);
 787   free (entry);
 788 }
 789
 790
 791 /* Return true if STMT is a store into an entire aggregate.  */
 792
 793 static bool
 794 aggregate_whole_store_p (tree stmt)
 795 {
 796   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 797     {
 798       tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 799       enum tree_code code = TREE_CODE (TREE_TYPE (lhs));
 800
 801       if (code == COMPLEX_TYPE || code == RECORD_TYPE)
 802         return true;
 803     }
 804   return false;
 805 }
 806
 807
 808 /* Main entry point.  */
 809
 810 static unsigned int
 811 tree_ssa_dse (void)
 812 {
 813   struct dom_walk_data walk_data;
 814   struct dse_global_data dse_gd;
 815   basic_block bb;
 816
 817   dse_gd.aggregate_vardecl =
 818     htab_create (37, aggregate_vardecl_hash,
 819                  aggregate_vardecl_eq, aggregate_vardecl_free);
 820
 821   max_stmt_uid = 0;
 822   FOR_EACH_BB (bb)
 823     {
 824       block_stmt_iterator bsi;
 825
 826       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 827         {
 828           tree stmt = bsi_stmt (bsi);
 829
 830           /* Record aggregates which have been stored into as a whole.  */
 831           if (aggregate_whole_store_p (stmt))
 832             {
 833               tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 834               if (TREE_CODE (lhs) == VAR_DECL)
 835                 {
 836                   struct aggregate_vardecl_d *av_p;
 837
 838                   av_p = get_aggregate_vardecl (lhs, &dse_gd, /*insert=*/true);
 839                   av_p->ignore = false;
 840
 841                   /* Ignore aggregates with too many parts.  */
 842                   if (av_p->nparts > HOST_BITS_PER_LONG)
 843                     av_p->ignore = true;
 844                 }
 845             }
 846
 847           /* Create a UID for each statement in the function.
 848              Ordering of the UIDs is not important for this pass.  */
 849           stmt_ann (stmt)->uid = max_stmt_uid++;
 850         }
 851     }
 852
 853   /* We might consider making this a property of each pass so that it
 854      can be [re]computed on an as-needed basis.  Particularly since
 855      this pass could be seen as an extension of DCE which needs post
 856      dominators.  */
 857   calculate_dominance_info (CDI_POST_DOMINATORS);
 858
 859   /* Dead store elimination is fundamentally a walk of the post-dominator
 860      tree and a backwards walk of statements within each block.  */
 861   walk_data.walk_stmts_backward = true;
 862   walk_data.dom_direction = CDI_POST_DOMINATORS;
 863   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
 864   walk_data.before_dom_children_before_stmts = NULL;
 865   walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
 866   walk_data.before_dom_children_after_stmts = dse_record_phis;
 867   walk_data.after_dom_children_before_stmts = NULL;
 868   walk_data.after_dom_children_walk_stmts = NULL;
 869   walk_data.after_dom_children_after_stmts = dse_finalize_block;
 870   walk_data.interesting_blocks = NULL;
 871
 872   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
 873
 874   /* This is the main hash table for the dead store elimination pass.  */
 875   dse_gd.stores = BITMAP_ALLOC (NULL);
 876
 877   walk_data.global_data = &dse_gd;
 878
 879   /* Initialize the dominator walker.  */
 880   init_walk_dominator_tree (&walk_data);
 881
 882   /* Recursively walk the dominator tree.  */
 883   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
 884
 885   /* Finalize the dominator walker.  */
 886   fini_walk_dominator_tree (&walk_data);
 887
 888   /* Release unneeded data.  */
 889   BITMAP_FREE (dse_gd.stores);
 890   htab_delete (dse_gd.aggregate_vardecl);
 891
 892   /* For now, just wipe the post-dominator information.  */
 893   free_dominance_info (CDI_POST_DOMINATORS);
 894   return 0;
 895 }
 896
 897 static bool
 898 gate_dse (void)
 899 {
 900   return flag_tree_dse != 0;
 901 }
 902
 903 struct tree_opt_pass pass_dse = {
 904   "dse",                        /* name */
 905   gate_dse,                     /* gate */
 906   tree_ssa_dse,                 /* execute */
 907   NULL,                         /* sub */
 908   NULL,                         /* next */
 909   0,                            /* static_pass_number */
 910   TV_TREE_DSE,                  /* tv_id */
 911   PROP_cfg
 912     | PROP_ssa
 913     | PROP_alias,               /* properties_required */
 914   0,                            /* properties_provided */
 915   0,                            /* properties_destroyed */
 916   0,                            /* todo_flags_start */
 917   TODO_dump_func
 918     | TODO_ggc_collect
 919     | TODO_verify_ssa,          /* todo_flags_finish */
 920   0                             /* letter */
 921 };