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