gcc/tree-ssa-dse.c

   1 /* Dead store elimination
   2    Copyright (C) 2004, 2005, 2006, 2007 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 3, 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 COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "ggc.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "basic-block.h"
  29 #include "timevar.h"
  30 #include "diagnostic.h"
  31 #include "tree-flow.h"
  32 #include "tree-pass.h"
  33 #include "tree-dump.h"
  34 #include "domwalk.h"
  35 #include "flags.h"
  36 #include "hashtab.h"
  37 #include "sbitmap.h"
  38
  39 /* This file implements dead store elimination.
  40
  41    A dead store is a store into a memory location which will later be
  42    overwritten by another store without any intervening loads.  In this
  43    case the earlier store can be deleted.
  44
  45    In our SSA + virtual operand world we use immediate uses of virtual
  46    operands to detect dead stores.  If a store's virtual definition
  47    is used precisely once by a later store to the same location which
  48    post dominates the first store, then the first store is dead.
  49
  50    The single use of the store's virtual definition ensures that
  51    there are no intervening aliased loads and the requirement that
  52    the second load post dominate the first ensures that if the earlier
  53    store executes, then the later stores will execute before the function
  54    exits.
  55
  56    It may help to think of this as first moving the earlier store to
  57    the point immediately before the later store.  Again, the single
  58    use of the virtual definition and the post-dominance relationship
  59    ensure that such movement would be safe.  Clearly if there are
  60    back to back stores, then the second is redundant.
  61
  62    Reviewing section 10.7.2 in Morgan's "Building an Optimizing Compiler"
  63    may also help in understanding this code since it discusses the
  64    relationship between dead store and redundant load elimination.  In
  65    fact, they are the same transformation applied to different views of
  66    the CFG.  */
  67
  68
  69 /* Given an aggregate, this records the parts of it which have been
  70    stored into.  */
  71 struct aggregate_vardecl_d
  72 {
  73   /* The aggregate.  */
  74   tree decl;
  75
  76   /* Some aggregates are too big for us to handle or never get stored
  77      to as a whole.  If this field is TRUE, we don't care about this
  78      aggregate.  */
  79   bool ignore;
  80
  81   /* Number of parts in the whole.  */
  82   unsigned nparts;
  83
  84   /* A bitmap of parts of the aggregate that have been set.  If part N
  85      of an aggregate has been stored to, bit N should be on.  */
  86   sbitmap parts_set;
  87 };
  88
  89 struct dse_global_data
  90 {
  91   /* This is the global bitmap for store statements.
  92
  93      Each statement has a unique ID.  When we encounter a store statement
  94      that we want to record, set the bit corresponding to the statement's
  95      unique ID in this bitmap.  */
  96   bitmap stores;
  97
  98   /* A hash table containing the parts of an aggregate which have been
  99      stored to.  */
 100   htab_t aggregate_vardecl;
 101 };
 102
 103 /* We allocate a bitmap-per-block for stores which are encountered
 104    during the scan of that block.  This allows us to restore the
 105    global bitmap of stores when we finish processing a block.  */
 106 struct dse_block_local_data
 107 {
 108   bitmap stores;
 109 };
 110
 111 /* Basic blocks of the potentially dead store and the following
 112    store, for memory_address_same.  */
 113 struct address_walk_data
 114 {
 115   basic_block store1_bb, store2_bb;
 116 };
 117
 118 static bool gate_dse (void);
 119 static unsigned int tree_ssa_dse (void);
 120 static void dse_initialize_block_local_data (struct dom_walk_data *,
 121                                              basic_block,
 122                                              bool);
 123 static void dse_optimize_stmt (struct dom_walk_data *,
 124                                basic_block,
 125                                block_stmt_iterator);
 126 static void dse_record_phis (struct dom_walk_data *, basic_block);
 127 static void dse_finalize_block (struct dom_walk_data *, basic_block);
 128 static void record_voperand_set (bitmap, bitmap *, unsigned int);
 129 static void dse_record_partial_aggregate_store (tree, struct dse_global_data *);
 130
 131 static unsigned max_stmt_uid;   /* Maximal uid of a statement.  Uids to phi
 132                                    nodes are assigned using the versions of
 133                                    ssa names they define.  */
 134
 135 /* Returns uid of statement STMT.  */
 136
 137 static unsigned
 138 get_stmt_uid (tree stmt)
 139 {
 140   if (TREE_CODE (stmt) == PHI_NODE)
 141     return SSA_NAME_VERSION (PHI_RESULT (stmt)) + max_stmt_uid;
 142
 143   return stmt_ann (stmt)->uid;
 144 }
 145
 146 /* Set bit UID in bitmaps GLOBAL and *LOCAL, creating *LOCAL as needed.  */
 147
 148 static void
 149 record_voperand_set (bitmap global, bitmap *local, unsigned int uid)
 150 {
 151   /* Lazily allocate the bitmap.  Note that we do not get a notification
 152      when the block local data structures die, so we allocate the local
 153      bitmap backed by the GC system.  */
 154   if (*local == NULL)
 155     *local = BITMAP_GGC_ALLOC ();
 156
 157   /* Set the bit in the local and global bitmaps.  */
 158   bitmap_set_bit (*local, uid);
 159   bitmap_set_bit (global, uid);
 160 }
 161
 162 /* Initialize block local data structures.  */
 163
 164 static void
 165 dse_initialize_block_local_data (struct dom_walk_data *walk_data,
 166                                  basic_block bb ATTRIBUTE_UNUSED,
 167                                  bool recycled)
 168 {
 169   struct dse_block_local_data *bd
 170     = (struct dse_block_local_data *)
 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 = (struct address_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     = (struct dse_block_local_data *)
 619         VEC_last (void_p, walk_data->block_data_stack);
 620   struct dse_global_data *dse_gd
 621     = (struct dse_global_data *) walk_data->global_data;
 622   tree stmt = bsi_stmt (bsi);
 623   stmt_ann_t ann = stmt_ann (stmt);
 624
 625   /* If this statement has no virtual defs, then there is nothing
 626      to do.  */
 627   if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF))
 628     return;
 629
 630   /* We know we have virtual definitions.  If this is a GIMPLE_MODIFY_STMT
 631      that's not also a function call, then record it into our table.  */
 632   if (get_call_expr_in (stmt))
 633     return;
 634
 635   if (ann->has_volatile_ops)
 636     return;
 637
 638   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 639     {
 640       use_operand_p first_use_p = NULL_USE_OPERAND_P;
 641       use_operand_p use_p = NULL;
 642       tree use_stmt;
 643
 644       if (!dse_possible_dead_store_p (stmt, &first_use_p, &use_p, &use_stmt,
 645                                       dse_gd, bd))
 646         return;
 647
 648       /* If this is a partial store into an aggregate, record it.  */
 649       dse_record_partial_aggregate_store (stmt, dse_gd);
 650
 651       if (use_p != NULL_USE_OPERAND_P
 652           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
 653           && (!operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
 654                                 GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
 655               && !dse_partial_kill_p (stmt, dse_gd))
 656           && memory_address_same (stmt, use_stmt))
 657         {
 658           /* If we have precisely one immediate use at this point, but
 659              the stores are not to the same memory location then walk the
 660              virtual def-use chain to get the stmt which stores to that same
 661              memory location.  */
 662           if (get_use_of_stmt_lhs (stmt, &first_use_p, &use_p, &use_stmt) ==
 663               NULL_TREE)
 664             {
 665               record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 666               return;
 667             }
 668         }
 669
 670       /* If we have precisely one immediate use at this point and the
 671          stores are to the same memory location or there is a chain of
 672          virtual uses from stmt and the stmt which stores to that same
 673          memory location, then we may have found redundant store.  */
 674       if (use_p != NULL_USE_OPERAND_P
 675           && bitmap_bit_p (dse_gd->stores, get_stmt_uid (use_stmt))
 676           && (operand_equal_p (GIMPLE_STMT_OPERAND (stmt, 0),
 677                                GIMPLE_STMT_OPERAND (use_stmt, 0), 0)
 678               || dse_partial_kill_p (stmt, dse_gd))
 679           && memory_address_same (stmt, use_stmt))
 680         {
 681           ssa_op_iter op_iter;
 682           def_operand_p var1;
 683           vuse_vec_p vv;
 684           tree stmt_lhs;
 685
 686           if (dump_file && (dump_flags & TDF_DETAILS))
 687             {
 688               fprintf (dump_file, "  Deleted dead store '");
 689               print_generic_expr (dump_file, bsi_stmt (bsi), dump_flags);
 690               fprintf (dump_file, "'\n");
 691             }
 692
 693           /* Then we need to fix the operand of the consuming stmt.  */
 694           stmt_lhs = USE_FROM_PTR (first_use_p);
 695           FOR_EACH_SSA_VDEF_OPERAND (var1, vv, stmt, op_iter)
 696             {
 697               tree usevar, temp;
 698
 699               single_imm_use (DEF_FROM_PTR (var1), &use_p, &temp);
 700               gcc_assert (VUSE_VECT_NUM_ELEM (*vv) == 1);
 701               usevar = VUSE_ELEMENT_VAR (*vv, 0);
 702               SET_USE (use_p, usevar);
 703
 704               /* Make sure we propagate the ABNORMAL bit setting.  */
 705               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (stmt_lhs))
 706                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (usevar) = 1;
 707             }
 708
 709           /* Remove the dead store.  */
 710           bsi_remove (&bsi, true);
 711
 712           /* And release any SSA_NAMEs set in this statement back to the
 713              SSA_NAME manager.  */
 714           release_defs (stmt);
 715         }
 716
 717       record_voperand_set (dse_gd->stores, &bd->stores, ann->uid);
 718     }
 719 }
 720
 721 /* Record that we have seen the PHIs at the start of BB which correspond
 722    to virtual operands.  */
 723 static void
 724 dse_record_phis (struct dom_walk_data *walk_data, basic_block bb)
 725 {
 726   struct dse_block_local_data *bd
 727     = (struct dse_block_local_data *)
 728         VEC_last (void_p, walk_data->block_data_stack);
 729   struct dse_global_data *dse_gd
 730     = (struct dse_global_data *) walk_data->global_data;
 731   tree phi;
 732
 733   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 734     if (!is_gimple_reg (PHI_RESULT (phi)))
 735       record_voperand_set (dse_gd->stores,
 736                            &bd->stores,
 737                            get_stmt_uid (phi));
 738 }
 739
 740 static void
 741 dse_finalize_block (struct dom_walk_data *walk_data,
 742                     basic_block bb ATTRIBUTE_UNUSED)
 743 {
 744   struct dse_block_local_data *bd
 745     = (struct dse_block_local_data *)
 746         VEC_last (void_p, walk_data->block_data_stack);
 747   struct dse_global_data *dse_gd
 748     = (struct dse_global_data *) walk_data->global_data;
 749   bitmap stores = dse_gd->stores;
 750   unsigned int i;
 751   bitmap_iterator bi;
 752
 753   /* Unwind the stores noted in this basic block.  */
 754   if (bd->stores)
 755     EXECUTE_IF_SET_IN_BITMAP (bd->stores, 0, i, bi)
 756       {
 757         bitmap_clear_bit (stores, i);
 758       }
 759 }
 760
 761
 762 /* Hashing and equality functions for AGGREGATE_VARDECL.  */
 763
 764 static hashval_t
 765 aggregate_vardecl_hash (const void *p)
 766 {
 767   return htab_hash_pointer
 768     ((const void *)((const struct aggregate_vardecl_d *)p)->decl);
 769 }
 770
 771 static int
 772 aggregate_vardecl_eq (const void *p1, const void *p2)
 773 {
 774   return ((const struct aggregate_vardecl_d *)p1)->decl
 775     == ((const struct aggregate_vardecl_d *)p2)->decl;
 776 }
 777
 778
 779 /* Free memory allocated by one entry in AGGREGATE_VARDECL.  */
 780
 781 static void
 782 aggregate_vardecl_free (void *p)
 783 {
 784   struct aggregate_vardecl_d *entry = (struct aggregate_vardecl_d *) p;
 785   sbitmap_free (entry->parts_set);
 786   free (entry);
 787 }
 788
 789
 790 /* Return true if STMT is a store into an entire aggregate.  */
 791
 792 static bool
 793 aggregate_whole_store_p (tree stmt)
 794 {
 795   if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 796     {
 797       tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 798       enum tree_code code = TREE_CODE (TREE_TYPE (lhs));
 799
 800       if (code == COMPLEX_TYPE || code == RECORD_TYPE)
 801         return true;
 802     }
 803   return false;
 804 }
 805
 806
 807 /* Main entry point.  */
 808
 809 static unsigned int
 810 tree_ssa_dse (void)
 811 {
 812   struct dom_walk_data walk_data;
 813   struct dse_global_data dse_gd;
 814   basic_block bb;
 815
 816   dse_gd.aggregate_vardecl =
 817     htab_create (37, aggregate_vardecl_hash,
 818                  aggregate_vardecl_eq, aggregate_vardecl_free);
 819
 820   max_stmt_uid = 0;
 821   FOR_EACH_BB (bb)
 822     {
 823       block_stmt_iterator bsi;
 824
 825       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 826         {
 827           tree stmt = bsi_stmt (bsi);
 828
 829           /* Record aggregates which have been stored into as a whole.  */
 830           if (aggregate_whole_store_p (stmt))
 831             {
 832               tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 833               if (TREE_CODE (lhs) == VAR_DECL)
 834                 {
 835                   struct aggregate_vardecl_d *av_p;
 836
 837                   av_p = get_aggregate_vardecl (lhs, &dse_gd, /*insert=*/true);
 838                   av_p->ignore = false;
 839
 840                   /* Ignore aggregates with too many parts.  */
 841                   if (av_p->nparts > HOST_BITS_PER_LONG)
 842                     av_p->ignore = true;
 843                 }
 844             }
 845
 846           /* Create a UID for each statement in the function.
 847              Ordering of the UIDs is not important for this pass.  */
 848           stmt_ann (stmt)->uid = max_stmt_uid++;
 849         }
 850     }
 851
 852   /* We might consider making this a property of each pass so that it
 853      can be [re]computed on an as-needed basis.  Particularly since
 854      this pass could be seen as an extension of DCE which needs post
 855      dominators.  */
 856   calculate_dominance_info (CDI_POST_DOMINATORS);
 857
 858   /* Dead store elimination is fundamentally a walk of the post-dominator
 859      tree and a backwards walk of statements within each block.  */
 860   walk_data.walk_stmts_backward = true;
 861   walk_data.dom_direction = CDI_POST_DOMINATORS;
 862   walk_data.initialize_block_local_data = dse_initialize_block_local_data;
 863   walk_data.before_dom_children_before_stmts = NULL;
 864   walk_data.before_dom_children_walk_stmts = dse_optimize_stmt;
 865   walk_data.before_dom_children_after_stmts = dse_record_phis;
 866   walk_data.after_dom_children_before_stmts = NULL;
 867   walk_data.after_dom_children_walk_stmts = NULL;
 868   walk_data.after_dom_children_after_stmts = dse_finalize_block;
 869   walk_data.interesting_blocks = NULL;
 870
 871   walk_data.block_local_data_size = sizeof (struct dse_block_local_data);
 872
 873   /* This is the main hash table for the dead store elimination pass.  */
 874   dse_gd.stores = BITMAP_ALLOC (NULL);
 875
 876   walk_data.global_data = &dse_gd;
 877
 878   /* Initialize the dominator walker.  */
 879   init_walk_dominator_tree (&walk_data);
 880
 881   /* Recursively walk the dominator tree.  */
 882   walk_dominator_tree (&walk_data, EXIT_BLOCK_PTR);
 883
 884   /* Finalize the dominator walker.  */
 885   fini_walk_dominator_tree (&walk_data);
 886
 887   /* Release unneeded data.  */
 888   BITMAP_FREE (dse_gd.stores);
 889   htab_delete (dse_gd.aggregate_vardecl);
 890
 891   /* For now, just wipe the post-dominator information.  */
 892   free_dominance_info (CDI_POST_DOMINATORS);
 893   return 0;
 894 }
 895
 896 static bool
 897 gate_dse (void)
 898 {
 899   return flag_tree_dse != 0;
 900 }
 901
 902 struct tree_opt_pass pass_dse = {
 903   "dse",                        /* name */
 904   gate_dse,                     /* gate */
 905   tree_ssa_dse,                 /* execute */
 906   NULL,                         /* sub */
 907   NULL,                         /* next */
 908   0,                            /* static_pass_number */
 909   TV_TREE_DSE,                  /* tv_id */
 910   PROP_cfg
 911     | PROP_ssa
 912     | PROP_alias,               /* properties_required */
 913   0,                            /* properties_provided */
 914   0,                            /* properties_destroyed */
 915   0,                            /* todo_flags_start */
 916   TODO_dump_func
 917     | TODO_ggc_collect
 918     | TODO_verify_ssa,          /* todo_flags_finish */
 919   0                             /* letter */
 920 };