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