gcc/dse.c

   1 /* RTL dead store elimination.
   2    Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
   3
   4    Contributed by Richard Sandiford <rsandifor@codesourcery.com>
   5    and Kenneth Zadeck <zadeck@naturalbridge.com>
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it under
  10 the terms of the GNU General Public License as published by the Free
  11 Software Foundation; either version 3, or (at your option) any later
  12 version.
  13
  14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17 for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING3.  If not see
  21 <http://www.gnu.org/licenses/>.  */
  22
  23 #undef BASELINE
  24
  25 #include "config.h"
  26 #include "system.h"
  27 #include "coretypes.h"
  28 #include "hashtab.h"
  29 #include "tm.h"
  30 #include "rtl.h"
  31 #include "tree.h"
  32 #include "tm_p.h"
  33 #include "regs.h"
  34 #include "hard-reg-set.h"
  35 #include "flags.h"
  36 #include "df.h"
  37 #include "cselib.h"
  38 #include "timevar.h"
  39 #include "tree-pass.h"
  40 #include "alloc-pool.h"
  41 #include "alias.h"
  42 #include "insn-config.h"
  43 #include "expr.h"
  44 #include "recog.h"
  45 #include "dse.h"
  46 #include "optabs.h"
  47 #include "dbgcnt.h"
  48 #include "target.h"
  49
  50 /* This file contains three techniques for performing Dead Store
  51    Elimination (dse).
  52
  53    * The first technique performs dse locally on any base address.  It
  54    is based on the cselib which is a local value numbering technique.
  55    This technique is local to a basic block but deals with a fairly
  56    general addresses.
  57
  58    * The second technique performs dse globally but is restricted to
  59    base addresses that are either constant or are relative to the
  60    frame_pointer.
  61
  62    * The third technique, (which is only done after register allocation)
  63    processes the spill spill slots.  This differs from the second
  64    technique because it takes advantage of the fact that spilling is
  65    completely free from the effects of aliasing.
  66
  67    Logically, dse is a backwards dataflow problem.  A store can be
  68    deleted if it if cannot be reached in the backward direction by any
  69    use of the value being stored.  However, the local technique uses a
  70    forwards scan of the basic block because cselib requires that the
  71    block be processed in that order.
  72
  73    The pass is logically broken into 7 steps:
  74
  75    0) Initialization.
  76
  77    1) The local algorithm, as well as scanning the insns for the two
  78    global algorithms.
  79
  80    2) Analysis to see if the global algs are necessary.  In the case
  81    of stores base on a constant address, there must be at least two
  82    stores to that address, to make it possible to delete some of the
  83    stores.  In the case of stores off of the frame or spill related
  84    stores, only one store to an address is necessary because those
  85    stores die at the end of the function.
  86
  87    3) Set up the global dataflow equations based on processing the
  88    info parsed in the first step.
  89
  90    4) Solve the dataflow equations.
  91
  92    5) Delete the insns that the global analysis has indicated are
  93    unnecessary.
  94
  95    6) Delete insns that store the same value as preceeding store
  96    where the earlier store couldn't be eliminated.
  97
  98    7) Cleanup.
  99
 100    This step uses cselib and canon_rtx to build the largest expression
 101    possible for each address.  This pass is a forwards pass through
 102    each basic block.  From the point of view of the global technique,
 103    the first pass could examine a block in either direction.  The
 104    forwards ordering is to accommodate cselib.
 105
 106    We a simplifying assumption: addresses fall into four broad
 107    categories:
 108
 109    1) base has rtx_varies_p == false, offset is constant.
 110    2) base has rtx_varies_p == false, offset variable.
 111    3) base has rtx_varies_p == true, offset constant.
 112    4) base has rtx_varies_p == true, offset variable.
 113
 114    The local passes are able to process all 4 kinds of addresses.  The
 115    global pass only handles (1).
 116
 117    The global problem is formulated as follows:
 118
 119      A store, S1, to address A, where A is not relative to the stack
 120      frame, can be eliminated if all paths from S1 to the end of the
 121      of the function contain another store to A before a read to A.
 122
 123      If the address A is relative to the stack frame, a store S2 to A
 124      can be eliminated if there are no paths from S1 that reach the
 125      end of the function that read A before another store to A.  In
 126      this case S2 can be deleted if there are paths to from S2 to the
 127      end of the function that have no reads or writes to A.  This
 128      second case allows stores to the stack frame to be deleted that
 129      would otherwise die when the function returns.  This cannot be
 130      done if stores_off_frame_dead_at_return is not true.  See the doc
 131      for that variable for when this variable is false.
 132
 133      The global problem is formulated as a backwards set union
 134      dataflow problem where the stores are the gens and reads are the
 135      kills.  Set union problems are rare and require some special
 136      handling given our representation of bitmaps.  A straightforward
 137      implementation of requires a lot of bitmaps filled with 1s.
 138      These are expensive and cumbersome in our bitmap formulation so
 139      care has been taken to avoid large vectors filled with 1s.  See
 140      the comments in bb_info and in the dataflow confluence functions
 141      for details.
 142
 143    There are two places for further enhancements to this algorithm:
 144
 145    1) The original dse which was embedded in a pass called flow also
 146    did local address forwarding.  For example in
 147
 148    A <- r100
 149    ... <- A
 150
 151    flow would replace the right hand side of the second insn with a
 152    reference to r100.  Most of the information is available to add this
 153    to this pass.  It has not done it because it is a lot of work in
 154    the case that either r100 is assigned to between the first and
 155    second insn and/or the second insn is a load of part of the value
 156    stored by the first insn.
 157
 158    insn 5 in gcc.c-torture/compile/990203-1.c simple case.
 159    insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
 160    insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
 161    insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
 162
 163    2) The cleaning up of spill code is quite profitable.  It currently
 164    depends on reading tea leaves and chicken entrails left by reload.
 165    This pass depends on reload creating a singleton alias set for each
 166    spill slot and telling the next dse pass which of these alias sets
 167    are the singletons.  Rather than analyze the addresses of the
 168    spills, dse's spill processing just does analysis of the loads and
 169    stores that use those alias sets.  There are three cases where this
 170    falls short:
 171
 172      a) Reload sometimes creates the slot for one mode of access, and
 173      then inserts loads and/or stores for a smaller mode.  In this
 174      case, the current code just punts on the slot.  The proper thing
 175      to do is to back out and use one bit vector position for each
 176      byte of the entity associated with the slot.  This depends on
 177      KNOWING that reload always generates the accesses for each of the
 178      bytes in some canonical (read that easy to understand several
 179      passes after reload happens) way.
 180
 181      b) Reload sometimes decides that spill slot it allocated was not
 182      large enough for the mode and goes back and allocates more slots
 183      with the same mode and alias set.  The backout in this case is a
 184      little more graceful than (a).  In this case the slot is unmarked
 185      as being a spill slot and if final address comes out to be based
 186      off the frame pointer, the global algorithm handles this slot.
 187
 188      c) For any pass that may prespill, there is currently no
 189      mechanism to tell the dse pass that the slot being used has the
 190      special properties that reload uses.  It may be that all that is
 191      required is to have those passes make the same calls that reload
 192      does, assuming that the alias sets can be manipulated in the same
 193      way.  */
 194
 195 /* There are limits to the size of constant offsets we model for the
 196    global problem.  There are certainly test cases, that exceed this
 197    limit, however, it is unlikely that there are important programs
 198    that really have constant offsets this size.  */
 199 #define MAX_OFFSET (64 * 1024)
 200
 201
 202 static bitmap scratch = NULL;
 203 struct insn_info;
 204
 205 /* This structure holds information about a candidate store.  */
 206 struct store_info
 207 {
 208
 209   /* False means this is a clobber.  */
 210   bool is_set;
 211
 212   /* False if a single HOST_WIDE_INT bitmap is used for positions_needed.  */
 213   bool is_large;
 214
 215   /* The id of the mem group of the base address.  If rtx_varies_p is
 216      true, this is -1.  Otherwise, it is the index into the group
 217      table.  */
 218   int group_id;
 219
 220   /* This is the cselib value.  */
 221   cselib_val *cse_base;
 222
 223   /* This canonized mem.  */
 224   rtx mem;
 225
 226   /* Canonized MEM address for use by canon_true_dependence.  */
 227   rtx mem_addr;
 228
 229   /* If this is non-zero, it is the alias set of a spill location.  */
 230   alias_set_type alias_set;
 231
 232   /* The offset of the first and byte before the last byte associated
 233      with the operation.  */
 234   HOST_WIDE_INT begin, end;
 235
 236   union
 237     {
 238       /* A bitmask as wide as the number of bytes in the word that
 239          contains a 1 if the byte may be needed.  The store is unused if
 240          all of the bits are 0.  This is used if IS_LARGE is false.  */
 241       unsigned HOST_WIDE_INT small_bitmask;
 242
 243       struct
 244         {
 245           /* A bitmap with one bit per byte.  Cleared bit means the position
 246              is needed.  Used if IS_LARGE is false.  */
 247           bitmap bitmap;
 248
 249           /* Number of set bits (i.e. unneeded bytes) in BITMAP.  If it is
 250              equal to END - BEGIN, the whole store is unused.  */
 251           int count;
 252         } large;
 253     } positions_needed;
 254
 255   /* The next store info for this insn.  */
 256   struct store_info *next;
 257
 258   /* The right hand side of the store.  This is used if there is a
 259      subsequent reload of the mems address somewhere later in the
 260      basic block.  */
 261   rtx rhs;
 262
 263   /* If rhs is or holds a constant, this contains that constant,
 264      otherwise NULL.  */
 265   rtx const_rhs;
 266
 267   /* Set if this store stores the same constant value as REDUNDANT_REASON
 268      insn stored.  These aren't eliminated early, because doing that
 269      might prevent the earlier larger store to be eliminated.  */
 270   struct insn_info *redundant_reason;
 271 };
 272
 273 /* Return a bitmask with the first N low bits set.  */
 274
 275 static unsigned HOST_WIDE_INT
 276 lowpart_bitmask (int n)
 277 {
 278   unsigned HOST_WIDE_INT mask = ~(unsigned HOST_WIDE_INT) 0;
 279   return mask >> (HOST_BITS_PER_WIDE_INT - n);
 280 }
 281
 282 typedef struct store_info *store_info_t;
 283 static alloc_pool cse_store_info_pool;
 284 static alloc_pool rtx_store_info_pool;
 285
 286 /* This structure holds information about a load.  These are only
 287    built for rtx bases.  */
 288 struct read_info
 289 {
 290   /* The id of the mem group of the base address.  */
 291   int group_id;
 292
 293   /* If this is non-zero, it is the alias set of a spill location.  */
 294   alias_set_type alias_set;
 295
 296   /* The offset of the first and byte after the last byte associated
 297      with the operation.  If begin == end == 0, the read did not have
 298      a constant offset.  */
 299   int begin, end;
 300
 301   /* The mem being read.  */
 302   rtx mem;
 303
 304   /* The next read_info for this insn.  */
 305   struct read_info *next;
 306 };
 307 typedef struct read_info *read_info_t;
 308 static alloc_pool read_info_pool;
 309
 310
 311 /* One of these records is created for each insn.  */
 312
 313 struct insn_info
 314 {
 315   /* Set true if the insn contains a store but the insn itself cannot
 316      be deleted.  This is set if the insn is a parallel and there is
 317      more than one non dead output or if the insn is in some way
 318      volatile.  */
 319   bool cannot_delete;
 320
 321   /* This field is only used by the global algorithm.  It is set true
 322      if the insn contains any read of mem except for a (1).  This is
 323      also set if the insn is a call or has a clobber mem.  If the insn
 324      contains a wild read, the use_rec will be null.  */
 325   bool wild_read;
 326
 327   /* This field is only used for the processing of const functions.
 328      These functions cannot read memory, but they can read the stack
 329      because that is where they may get their parms.  We need to be
 330      this conservative because, like the store motion pass, we don't
 331      consider CALL_INSN_FUNCTION_USAGE when processing call insns.
 332      Moreover, we need to distinguish two cases:
 333      1. Before reload (register elimination), the stores related to
 334         outgoing arguments are stack pointer based and thus deemed
 335         of non-constant base in this pass.  This requires special
 336         handling but also means that the frame pointer based stores
 337         need not be killed upon encountering a const function call.
 338      2. After reload, the stores related to outgoing arguments can be
 339         either stack pointer or hard frame pointer based.  This means
 340         that we have no other choice than also killing all the frame
 341         pointer based stores upon encountering a const function call.
 342      This field is set after reload for const function calls.  Having
 343      this set is less severe than a wild read, it just means that all
 344      the frame related stores are killed rather than all the stores.  */
 345   bool frame_read;
 346
 347   /* This field is only used for the processing of const functions.
 348      It is set if the insn may contain a stack pointer based store.  */
 349   bool stack_pointer_based;
 350
 351   /* This is true if any of the sets within the store contains a
 352      cselib base.  Such stores can only be deleted by the local
 353      algorithm.  */
 354   bool contains_cselib_groups;
 355
 356   /* The insn. */
 357   rtx insn;
 358
 359   /* The list of mem sets or mem clobbers that are contained in this
 360      insn.  If the insn is deletable, it contains only one mem set.
 361      But it could also contain clobbers.  Insns that contain more than
 362      one mem set are not deletable, but each of those mems are here in
 363      order to provide info to delete other insns.  */
 364   store_info_t store_rec;
 365
 366   /* The linked list of mem uses in this insn.  Only the reads from
 367      rtx bases are listed here.  The reads to cselib bases are
 368      completely processed during the first scan and so are never
 369      created.  */
 370   read_info_t read_rec;
 371
 372   /* The prev insn in the basic block.  */
 373   struct insn_info * prev_insn;
 374
 375   /* The linked list of insns that are in consideration for removal in
 376      the forwards pass thru the basic block.  This pointer may be
 377      trash as it is not cleared when a wild read occurs.  The only
 378      time it is guaranteed to be correct is when the traversal starts
 379      at active_local_stores.  */
 380   struct insn_info * next_local_store;
 381 };
 382
 383 typedef struct insn_info *insn_info_t;
 384 static alloc_pool insn_info_pool;
 385
 386 /* The linked list of stores that are under consideration in this
 387    basic block.  */
 388 static insn_info_t active_local_stores;
 389
 390 struct bb_info
 391 {
 392
 393   /* Pointer to the insn info for the last insn in the block.  These
 394      are linked so this is how all of the insns are reached.  During
 395      scanning this is the current insn being scanned.  */
 396   insn_info_t last_insn;
 397
 398   /* The info for the global dataflow problem.  */
 399
 400
 401   /* This is set if the transfer function should and in the wild_read
 402      bitmap before applying the kill and gen sets.  That vector knocks
 403      out most of the bits in the bitmap and thus speeds up the
 404      operations.  */
 405   bool apply_wild_read;
 406
 407   /* The following 4 bitvectors hold information about which positions
 408      of which stores are live or dead.  They are indexed by
 409      get_bitmap_index.  */
 410
 411   /* The set of store positions that exist in this block before a wild read.  */
 412   bitmap gen;
 413
 414   /* The set of load positions that exist in this block above the
 415      same position of a store.  */
 416   bitmap kill;
 417
 418   /* The set of stores that reach the top of the block without being
 419      killed by a read.
 420
 421      Do not represent the in if it is all ones.  Note that this is
 422      what the bitvector should logically be initialized to for a set
 423      intersection problem.  However, like the kill set, this is too
 424      expensive.  So initially, the in set will only be created for the
 425      exit block and any block that contains a wild read.  */
 426   bitmap in;
 427
 428   /* The set of stores that reach the bottom of the block from it's
 429      successors.
 430
 431      Do not represent the in if it is all ones.  Note that this is
 432      what the bitvector should logically be initialized to for a set
 433      intersection problem.  However, like the kill and in set, this is
 434      too expensive.  So what is done is that the confluence operator
 435      just initializes the vector from one of the out sets of the
 436      successors of the block.  */
 437   bitmap out;
 438
 439   /* The following bitvector is indexed by the reg number.  It
 440      contains the set of regs that are live at the current instruction
 441      being processed.  While it contains info for all of the
 442      registers, only the pseudos are actually examined.  It is used to
 443      assure that shift sequences that are inserted do not accidently
 444      clobber live hard regs.  */
 445   bitmap regs_live;
 446 };
 447
 448 typedef struct bb_info *bb_info_t;
 449 static alloc_pool bb_info_pool;
 450
 451 /* Table to hold all bb_infos.  */
 452 static bb_info_t *bb_table;
 453
 454 /* There is a group_info for each rtx base that is used to reference
 455    memory.  There are also not many of the rtx bases because they are
 456    very limited in scope.  */
 457
 458 struct group_info
 459 {
 460   /* The actual base of the address.  */
 461   rtx rtx_base;
 462
 463   /* The sequential id of the base.  This allows us to have a
 464      canonical ordering of these that is not based on addresses.  */
 465   int id;
 466
 467   /* True if there are any positions that are to be processed
 468      globally.  */
 469   bool process_globally;
 470
 471   /* True if the base of this group is either the frame_pointer or
 472      hard_frame_pointer.  */
 473   bool frame_related;
 474
 475   /* A mem wrapped around the base pointer for the group in order to
 476      do read dependency.  */
 477   rtx base_mem;
 478
 479   /* Canonized version of base_mem's address.  */
 480   rtx canon_base_addr;
 481
 482   /* These two sets of two bitmaps are used to keep track of how many
 483      stores are actually referencing that position from this base.  We
 484      only do this for rtx bases as this will be used to assign
 485      positions in the bitmaps for the global problem.  Bit N is set in
 486      store1 on the first store for offset N.  Bit N is set in store2
 487      for the second store to offset N.  This is all we need since we
 488      only care about offsets that have two or more stores for them.
 489
 490      The "_n" suffix is for offsets less than 0 and the "_p" suffix is
 491      for 0 and greater offsets.
 492
 493      There is one special case here, for stores into the stack frame,
 494      we will or store1 into store2 before deciding which stores look
 495      at globally.  This is because stores to the stack frame that have
 496      no other reads before the end of the function can also be
 497      deleted.  */
 498   bitmap store1_n, store1_p, store2_n, store2_p;
 499
 500   /* The positions in this bitmap have the same assignments as the in,
 501      out, gen and kill bitmaps.  This bitmap is all zeros except for
 502      the positions that are occupied by stores for this group.  */
 503   bitmap group_kill;
 504
 505   /* The offset_map is used to map the offsets from this base into
 506      positions in the global bitmaps.  It is only created after all of
 507      the all of stores have been scanned and we know which ones we
 508      care about.  */
 509   int *offset_map_n, *offset_map_p;
 510   int offset_map_size_n, offset_map_size_p;
 511 };
 512 typedef struct group_info *group_info_t;
 513 typedef const struct group_info *const_group_info_t;
 514 static alloc_pool rtx_group_info_pool;
 515
 516 /* Tables of group_info structures, hashed by base value.  */
 517 static htab_t rtx_group_table;
 518
 519 /* Index into the rtx_group_vec.  */
 520 static int rtx_group_next_id;
 521
 522 DEF_VEC_P(group_info_t);
 523 DEF_VEC_ALLOC_P(group_info_t,heap);
 524
 525 static VEC(group_info_t,heap) *rtx_group_vec;
 526
 527
 528 /* This structure holds the set of changes that are being deferred
 529    when removing read operation.  See replace_read.  */
 530 struct deferred_change
 531 {
 532
 533   /* The mem that is being replaced.  */
 534   rtx *loc;
 535
 536   /* The reg it is being replaced with.  */
 537   rtx reg;
 538
 539   struct deferred_change *next;
 540 };
 541
 542 typedef struct deferred_change *deferred_change_t;
 543 static alloc_pool deferred_change_pool;
 544
 545 static deferred_change_t deferred_change_list = NULL;
 546
 547 /* This are used to hold the alias sets of spill variables.  Since
 548    these are never aliased and there may be a lot of them, it makes
 549    sense to treat them specially.  This bitvector is only allocated in
 550    calls from dse_record_singleton_alias_set which currently is only
 551    made during reload1.  So when dse is called before reload this
 552    mechanism does nothing.  */
 553
 554 static bitmap clear_alias_sets = NULL;
 555
 556 /* The set of clear_alias_sets that have been disqualified because
 557    there are loads or stores using a different mode than the alias set
 558    was registered with.  */
 559 static bitmap disqualified_clear_alias_sets = NULL;
 560
 561 /* The group that holds all of the clear_alias_sets.  */
 562 static group_info_t clear_alias_group;
 563
 564 /* The modes of the clear_alias_sets.  */
 565 static htab_t clear_alias_mode_table;
 566
 567 /* Hash table element to look up the mode for an alias set.  */
 568 struct clear_alias_mode_holder
 569 {
 570   alias_set_type alias_set;
 571   enum machine_mode mode;
 572 };
 573
 574 static alloc_pool clear_alias_mode_pool;
 575
 576 /* This is true except if cfun->stdarg -- i.e. we cannot do
 577    this for vararg functions because they play games with the frame.  */
 578 static bool stores_off_frame_dead_at_return;
 579
 580 /* Counter for stats.  */
 581 static int globally_deleted;
 582 static int locally_deleted;
 583 static int spill_deleted;
 584
 585 static bitmap all_blocks;
 586
 587 /* The number of bits used in the global bitmaps.  */
 588 static unsigned int current_position;
 589
 590
 591 static bool gate_dse (void);
 592 static bool gate_dse1 (void);
 593 static bool gate_dse2 (void);
 594
 595 \f
 596 /*----------------------------------------------------------------------------
 597    Zeroth step.
 598
 599    Initialization.
 600 ----------------------------------------------------------------------------*/
 601
 602 /* Hashtable callbacks for maintaining the "bases" field of
 603    store_group_info, given that the addresses are function invariants.  */
 604
 605 static int
 606 clear_alias_mode_eq (const void *p1, const void *p2)
 607 {
 608   const struct clear_alias_mode_holder * h1
 609     = (const struct clear_alias_mode_holder *) p1;
 610   const struct clear_alias_mode_holder * h2
 611     = (const struct clear_alias_mode_holder *) p2;
 612   return h1->alias_set == h2->alias_set;
 613 }
 614
 615
 616 static hashval_t
 617 clear_alias_mode_hash (const void *p)
 618 {
 619   const struct clear_alias_mode_holder *holder
 620     = (const struct clear_alias_mode_holder *) p;
 621   return holder->alias_set;
 622 }
 623
 624
 625 /* Find the entry associated with ALIAS_SET.  */
 626
 627 static struct clear_alias_mode_holder *
 628 clear_alias_set_lookup (alias_set_type alias_set)
 629 {
 630   struct clear_alias_mode_holder tmp_holder;
 631   void **slot;
 632
 633   tmp_holder.alias_set = alias_set;
 634   slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, NO_INSERT);
 635   gcc_assert (*slot);
 636
 637   return (struct clear_alias_mode_holder *) *slot;
 638 }
 639
 640
 641 /* Hashtable callbacks for maintaining the "bases" field of
 642    store_group_info, given that the addresses are function invariants.  */
 643
 644 static int
 645 invariant_group_base_eq (const void *p1, const void *p2)
 646 {
 647   const_group_info_t gi1 = (const_group_info_t) p1;
 648   const_group_info_t gi2 = (const_group_info_t) p2;
 649   return rtx_equal_p (gi1->rtx_base, gi2->rtx_base);
 650 }
 651
 652
 653 static hashval_t
 654 invariant_group_base_hash (const void *p)
 655 {
 656   const_group_info_t gi = (const_group_info_t) p;
 657   int do_not_record;
 658   return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false);
 659 }
 660
 661
 662 /* Get the GROUP for BASE.  Add a new group if it is not there.  */
 663
 664 static group_info_t
 665 get_group_info (rtx base)
 666 {
 667   struct group_info tmp_gi;
 668   group_info_t gi;
 669   void **slot;
 670
 671   if (base)
 672     {
 673       /* Find the store_base_info structure for BASE, creating a new one
 674          if necessary.  */
 675       tmp_gi.rtx_base = base;
 676       slot = htab_find_slot (rtx_group_table, &tmp_gi, INSERT);
 677       gi = (group_info_t) *slot;
 678     }
 679   else
 680     {
 681       if (!clear_alias_group)
 682         {
 683           clear_alias_group = gi =
 684             (group_info_t) pool_alloc (rtx_group_info_pool);
 685           memset (gi, 0, sizeof (struct group_info));
 686           gi->id = rtx_group_next_id++;
 687           gi->store1_n = BITMAP_ALLOC (NULL);
 688           gi->store1_p = BITMAP_ALLOC (NULL);
 689           gi->store2_n = BITMAP_ALLOC (NULL);
 690           gi->store2_p = BITMAP_ALLOC (NULL);
 691           gi->group_kill = BITMAP_ALLOC (NULL);
 692           gi->process_globally = false;
 693           gi->offset_map_size_n = 0;
 694           gi->offset_map_size_p = 0;
 695           gi->offset_map_n = NULL;
 696           gi->offset_map_p = NULL;
 697           VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);
 698         }
 699       return clear_alias_group;
 700     }
 701
 702   if (gi == NULL)
 703     {
 704       *slot = gi = (group_info_t) pool_alloc (rtx_group_info_pool);
 705       gi->rtx_base = base;
 706       gi->id = rtx_group_next_id++;
 707       gi->base_mem = gen_rtx_MEM (QImode, base);
 708       gi->canon_base_addr = canon_rtx (base);
 709       gi->store1_n = BITMAP_ALLOC (NULL);
 710       gi->store1_p = BITMAP_ALLOC (NULL);
 711       gi->store2_n = BITMAP_ALLOC (NULL);
 712       gi->store2_p = BITMAP_ALLOC (NULL);
 713       gi->group_kill = BITMAP_ALLOC (NULL);
 714       gi->process_globally = false;
 715       gi->frame_related =
 716         (base == frame_pointer_rtx) || (base == hard_frame_pointer_rtx);
 717       gi->offset_map_size_n = 0;
 718       gi->offset_map_size_p = 0;
 719       gi->offset_map_n = NULL;
 720       gi->offset_map_p = NULL;
 721       VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);
 722     }
 723
 724   return gi;
 725 }
 726
 727
 728 /* Initialization of data structures.  */
 729
 730 static void
 731 dse_step0 (void)
 732 {
 733   locally_deleted = 0;
 734   globally_deleted = 0;
 735   spill_deleted = 0;
 736
 737   scratch = BITMAP_ALLOC (NULL);
 738
 739   rtx_store_info_pool
 740     = create_alloc_pool ("rtx_store_info_pool",
 741                          sizeof (struct store_info), 100);
 742   read_info_pool
 743     = create_alloc_pool ("read_info_pool",
 744                          sizeof (struct read_info), 100);
 745   insn_info_pool
 746     = create_alloc_pool ("insn_info_pool",
 747                          sizeof (struct insn_info), 100);
 748   bb_info_pool
 749     = create_alloc_pool ("bb_info_pool",
 750                          sizeof (struct bb_info), 100);
 751   rtx_group_info_pool
 752     = create_alloc_pool ("rtx_group_info_pool",
 753                          sizeof (struct group_info), 100);
 754   deferred_change_pool
 755     = create_alloc_pool ("deferred_change_pool",
 756                          sizeof (struct deferred_change), 10);
 757
 758   rtx_group_table = htab_create (11, invariant_group_base_hash,
 759                                  invariant_group_base_eq, NULL);
 760
 761   bb_table = XCNEWVEC (bb_info_t, last_basic_block);
 762   rtx_group_next_id = 0;
 763
 764   stores_off_frame_dead_at_return = !cfun->stdarg;
 765
 766   init_alias_analysis ();
 767
 768   if (clear_alias_sets)
 769     clear_alias_group = get_group_info (NULL);
 770   else
 771     clear_alias_group = NULL;
 772 }
 773
 774
 775 \f
 776 /*----------------------------------------------------------------------------
 777    First step.
 778
 779    Scan all of the insns.  Any random ordering of the blocks is fine.
 780    Each block is scanned in forward order to accommodate cselib which
 781    is used to remove stores with non-constant bases.
 782 ----------------------------------------------------------------------------*/
 783
 784 /* Delete all of the store_info recs from INSN_INFO.  */
 785
 786 static void
 787 free_store_info (insn_info_t insn_info)
 788 {
 789   store_info_t store_info = insn_info->store_rec;
 790   while (store_info)
 791     {
 792       store_info_t next = store_info->next;
 793       if (store_info->is_large)
 794         BITMAP_FREE (store_info->positions_needed.large.bitmap);
 795       if (store_info->cse_base)
 796         pool_free (cse_store_info_pool, store_info);
 797       else
 798         pool_free (rtx_store_info_pool, store_info);
 799       store_info = next;
 800     }
 801
 802   insn_info->cannot_delete = true;
 803   insn_info->contains_cselib_groups = false;
 804   insn_info->store_rec = NULL;
 805 }
 806
 807
 808 struct insn_size {
 809   int size;
 810   rtx insn;
 811 };
 812
 813
 814 /* Add an insn to do the add inside a x if it is a
 815    PRE/POST-INC/DEC/MODIFY.  D is an structure containing the insn and
 816    the size of the mode of the MEM that this is inside of.  */
 817
 818 static int
 819 replace_inc_dec (rtx *r, void *d)
 820 {
 821   rtx x = *r;
 822   struct insn_size *data = (struct insn_size *)d;
 823   switch (GET_CODE (x))
 824     {
 825     case PRE_INC:
 826     case POST_INC:
 827       {
 828         rtx r1 = XEXP (x, 0);
 829         rtx c = gen_int_mode (data->size, Pmode);
 830         emit_insn_before (gen_rtx_SET (Pmode, r1,
 831                                        gen_rtx_PLUS (Pmode, r1, c)),
 832                           data->insn);
 833         return -1;
 834       }
 835
 836     case PRE_DEC:
 837     case POST_DEC:
 838       {
 839         rtx r1 = XEXP (x, 0);
 840         rtx c = gen_int_mode (-data->size, Pmode);
 841         emit_insn_before (gen_rtx_SET (Pmode, r1,
 842                                        gen_rtx_PLUS (Pmode, r1, c)),
 843                           data->insn);
 844         return -1;
 845       }
 846
 847     case PRE_MODIFY:
 848     case POST_MODIFY:
 849       {
 850         /* We can reuse the add because we are about to delete the
 851            insn that contained it.  */
 852         rtx add = XEXP (x, 0);
 853         rtx r1 = XEXP (add, 0);
 854         emit_insn_before (gen_rtx_SET (Pmode, r1, add), data->insn);
 855         return -1;
 856       }
 857
 858     default:
 859       return 0;
 860     }
 861 }
 862
 863
 864 /* If X is a MEM, check the address to see if it is PRE/POST-INC/DEC/MODIFY
 865    and generate an add to replace that.  */
 866
 867 static int
 868 replace_inc_dec_mem (rtx *r, void *d)
 869 {
 870   rtx x = *r;
 871   if (x != NULL_RTX && MEM_P (x))
 872     {
 873       struct insn_size data;
 874
 875       data.size = GET_MODE_SIZE (GET_MODE (x));
 876       data.insn = (rtx) d;
 877
 878       for_each_rtx (&XEXP (x, 0), replace_inc_dec, &data);
 879
 880       return -1;
 881     }
 882   return 0;
 883 }
 884
 885 /* Before we delete INSN, make sure that the auto inc/dec, if it is
 886    there, is split into a separate insn.  */
 887
 888 static void
 889 check_for_inc_dec (rtx insn)
 890 {
 891   rtx note = find_reg_note (insn, REG_INC, NULL_RTX);
 892   if (note)
 893     for_each_rtx (&insn, replace_inc_dec_mem, insn);
 894 }
 895
 896
 897 /* Delete the insn and free all of the fields inside INSN_INFO.  */
 898
 899 static void
 900 delete_dead_store_insn (insn_info_t insn_info)
 901 {
 902   read_info_t read_info;
 903
 904   if (!dbg_cnt (dse))
 905     return;
 906
 907   check_for_inc_dec (insn_info->insn);
 908   if (dump_file)
 909     {
 910       fprintf (dump_file, "Locally deleting insn %d ",
 911                INSN_UID (insn_info->insn));
 912       if (insn_info->store_rec->alias_set)
 913         fprintf (dump_file, "alias set %d\n",
 914                  (int) insn_info->store_rec->alias_set);
 915       else
 916         fprintf (dump_file, "\n");
 917     }
 918
 919   free_store_info (insn_info);
 920   read_info = insn_info->read_rec;
 921
 922   while (read_info)
 923     {
 924       read_info_t next = read_info->next;
 925       pool_free (read_info_pool, read_info);
 926       read_info = next;
 927     }
 928   insn_info->read_rec = NULL;
 929
 930   delete_insn (insn_info->insn);
 931   locally_deleted++;
 932   insn_info->insn = NULL;
 933
 934   insn_info->wild_read = false;
 935 }
 936
 937
 938 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
 939    OFFSET and WIDTH.  */
 940
 941 static void
 942 set_usage_bits (group_info_t group, HOST_WIDE_INT offset, HOST_WIDE_INT width)
 943 {
 944   HOST_WIDE_INT i;
 945
 946   if (offset > -MAX_OFFSET && offset + width < MAX_OFFSET)
 947     for (i=offset; i<offset+width; i++)
 948       {
 949         bitmap store1;
 950         bitmap store2;
 951         int ai;
 952         if (i < 0)
 953           {
 954             store1 = group->store1_n;
 955             store2 = group->store2_n;
 956             ai = -i;
 957           }
 958         else
 959           {
 960             store1 = group->store1_p;
 961             store2 = group->store2_p;
 962             ai = i;
 963           }
 964
 965         if (bitmap_bit_p (store1, ai))
 966           bitmap_set_bit (store2, ai);
 967         else
 968           {
 969             bitmap_set_bit (store1, ai);
 970             if (i < 0)
 971               {
 972                 if (group->offset_map_size_n < ai)
 973                   group->offset_map_size_n = ai;
 974               }
 975             else
 976               {
 977                 if (group->offset_map_size_p < ai)
 978                   group->offset_map_size_p = ai;
 979               }
 980           }
 981       }
 982 }
 983
 984
 985 /* Set the BB_INFO so that the last insn is marked as a wild read.  */
 986
 987 static void
 988 add_wild_read (bb_info_t bb_info)
 989 {
 990   insn_info_t insn_info = bb_info->last_insn;
 991   read_info_t *ptr = &insn_info->read_rec;
 992
 993   while (*ptr)
 994     {
 995       read_info_t next = (*ptr)->next;
 996       if ((*ptr)->alias_set == 0)
 997         {
 998           pool_free (read_info_pool, *ptr);
 999           *ptr = next;
1000         }
1001       else
1002         ptr = &(*ptr)->next;
1003     }
1004   insn_info->wild_read = true;
1005   active_local_stores = NULL;
1006 }
1007
1008
1009 /* Return true if X is a constant or one of the registers that behave
1010    as a constant over the life of a function.  This is equivalent to
1011    !rtx_varies_p for memory addresses.  */
1012
1013 static bool
1014 const_or_frame_p (rtx x)
1015 {
1016   switch (GET_CODE (x))
1017     {
1018     case MEM:
1019       return MEM_READONLY_P (x);
1020
1021     case CONST:
1022     case CONST_INT:
1023     case CONST_DOUBLE:
1024     case CONST_VECTOR:
1025     case SYMBOL_REF:
1026     case LABEL_REF:
1027       return true;
1028
1029     case REG:
1030       /* Note that we have to test for the actual rtx used for the frame
1031          and arg pointers and not just the register number in case we have
1032          eliminated the frame and/or arg pointer and are using it
1033          for pseudos.  */
1034       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
1035           /* The arg pointer varies if it is not a fixed register.  */
1036           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
1037           || x == pic_offset_table_rtx)
1038         return true;
1039       return false;
1040
1041     default:
1042       return false;
1043     }
1044 }
1045
1046 /* Take all reasonable action to put the address of MEM into the form
1047    that we can do analysis on.
1048
1049    The gold standard is to get the address into the form: address +
1050    OFFSET where address is something that rtx_varies_p considers a
1051    constant.  When we can get the address in this form, we can do
1052    global analysis on it.  Note that for constant bases, address is
1053    not actually returned, only the group_id.  The address can be
1054    obtained from that.
1055
1056    If that fails, we try cselib to get a value we can at least use
1057    locally.  If that fails we return false.
1058
1059    The GROUP_ID is set to -1 for cselib bases and the index of the
1060    group for non_varying bases.
1061
1062    FOR_READ is true if this is a mem read and false if not.  */
1063
1064 static bool
1065 canon_address (rtx mem,
1066                alias_set_type *alias_set_out,
1067                int *group_id,
1068                HOST_WIDE_INT *offset,
1069                cselib_val **base)
1070 {
1071   rtx mem_address = XEXP (mem, 0);
1072   rtx expanded_address, address;
1073   /* Make sure that cselib is has initialized all of the operands of
1074      the address before asking it to do the subst.  */
1075
1076   if (clear_alias_sets)
1077     {
1078       /* If this is a spill, do not do any further processing.  */
1079       alias_set_type alias_set = MEM_ALIAS_SET (mem);
1080       if (dump_file)
1081         fprintf (dump_file, "found alias set %d\n", (int) alias_set);
1082       if (bitmap_bit_p (clear_alias_sets, alias_set))
1083         {
1084           struct clear_alias_mode_holder *entry
1085             = clear_alias_set_lookup (alias_set);
1086
1087           /* If the modes do not match, we cannot process this set.  */
1088           if (entry->mode != GET_MODE (mem))
1089             {
1090               if (dump_file)
1091                 fprintf (dump_file,
1092                          "disqualifying alias set %d, (%s) != (%s)\n",
1093                          (int) alias_set, GET_MODE_NAME (entry->mode),
1094                          GET_MODE_NAME (GET_MODE (mem)));
1095
1096               bitmap_set_bit (disqualified_clear_alias_sets, alias_set);
1097               return false;
1098             }
1099
1100           *alias_set_out = alias_set;
1101           *group_id = clear_alias_group->id;
1102           return true;
1103         }
1104     }
1105
1106   *alias_set_out = 0;
1107
1108   cselib_lookup (mem_address, Pmode, 1);
1109
1110   if (dump_file)
1111     {
1112       fprintf (dump_file, "  mem: ");
1113       print_inline_rtx (dump_file, mem_address, 0);
1114       fprintf (dump_file, "\n");
1115     }
1116
1117   /* Use cselib to replace all of the reg references with the full
1118      expression.  This will take care of the case where we have
1119
1120      r_x = base + offset;
1121      val = *r_x;
1122
1123      by making it into
1124
1125      val = *(base + offset);
1126   */
1127
1128   expanded_address = cselib_expand_value_rtx (mem_address, scratch, 5);
1129
1130   /* If this fails, just go with the mem_address.  */
1131   if (!expanded_address)
1132     expanded_address = mem_address;
1133
1134   /* Split the address into canonical BASE + OFFSET terms.  */
1135   address = canon_rtx (expanded_address);
1136
1137   *offset = 0;
1138
1139   if (dump_file)
1140     {
1141       fprintf (dump_file, "\n   after cselib_expand address: ");
1142       print_inline_rtx (dump_file, expanded_address, 0);
1143       fprintf (dump_file, "\n");
1144
1145       fprintf (dump_file, "\n   after canon_rtx address: ");
1146       print_inline_rtx (dump_file, address, 0);
1147       fprintf (dump_file, "\n");
1148     }
1149
1150   if (GET_CODE (address) == CONST)
1151     address = XEXP (address, 0);
1152
1153   if (GET_CODE (address) == PLUS && GET_CODE (XEXP (address, 1)) == CONST_INT)
1154     {
1155       *offset = INTVAL (XEXP (address, 1));
1156       address = XEXP (address, 0);
1157     }
1158
1159   if (const_or_frame_p (address))
1160     {
1161       group_info_t group = get_group_info (address);
1162
1163       if (dump_file)
1164         fprintf (dump_file, "  gid=%d offset=%d \n", group->id, (int)*offset);
1165       *base = NULL;
1166       *group_id = group->id;
1167     }
1168   else
1169     {
1170       *base = cselib_lookup (address, Pmode, true);
1171       *group_id = -1;
1172
1173       if (*base == NULL)
1174         {
1175           if (dump_file)
1176             fprintf (dump_file, " no cselib val - should be a wild read.\n");
1177           return false;
1178         }
1179       if (dump_file)
1180         fprintf (dump_file, "  varying cselib base=%d offset = %d\n",
1181                  (*base)->value, (int)*offset);
1182     }
1183   return true;
1184 }
1185
1186
1187 /* Clear the rhs field from the active_local_stores array.  */
1188
1189 static void
1190 clear_rhs_from_active_local_stores (void)
1191 {
1192   insn_info_t ptr = active_local_stores;
1193
1194   while (ptr)
1195     {
1196       store_info_t store_info = ptr->store_rec;
1197       /* Skip the clobbers.  */
1198       while (!store_info->is_set)
1199         store_info = store_info->next;
1200
1201       store_info->rhs = NULL;
1202       store_info->const_rhs = NULL;
1203
1204       ptr = ptr->next_local_store;
1205     }
1206 }
1207
1208
1209 /* Mark byte POS bytes from the beginning of store S_INFO as unneeded.  */
1210
1211 static inline void
1212 set_position_unneeded (store_info_t s_info, int pos)
1213 {
1214   if (__builtin_expect (s_info->is_large, false))
1215     {
1216       if (!bitmap_bit_p (s_info->positions_needed.large.bitmap, pos))
1217         {
1218           s_info->positions_needed.large.count++;
1219           bitmap_set_bit (s_info->positions_needed.large.bitmap, pos);
1220         }
1221     }
1222   else
1223     s_info->positions_needed.small_bitmask
1224       &= ~(((unsigned HOST_WIDE_INT) 1) << pos);
1225 }
1226
1227 /* Mark the whole store S_INFO as unneeded.  */
1228
1229 static inline void
1230 set_all_positions_unneeded (store_info_t s_info)
1231 {
1232   if (__builtin_expect (s_info->is_large, false))
1233     {
1234       int pos, end = s_info->end - s_info->begin;
1235       for (pos = 0; pos < end; pos++)
1236         bitmap_set_bit (s_info->positions_needed.large.bitmap, pos);
1237       s_info->positions_needed.large.count = end;
1238     }
1239   else
1240     s_info->positions_needed.small_bitmask = (unsigned HOST_WIDE_INT) 0;
1241 }
1242
1243 /* Return TRUE if any bytes from S_INFO store are needed.  */
1244
1245 static inline bool
1246 any_positions_needed_p (store_info_t s_info)
1247 {
1248   if (__builtin_expect (s_info->is_large, false))
1249     return (s_info->positions_needed.large.count
1250             < s_info->end - s_info->begin);
1251   else
1252     return (s_info->positions_needed.small_bitmask
1253             != (unsigned HOST_WIDE_INT) 0);
1254 }
1255
1256 /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
1257    store are needed.  */
1258
1259 static inline bool
1260 all_positions_needed_p (store_info_t s_info, int start, int width)
1261 {
1262   if (__builtin_expect (s_info->is_large, false))
1263     {
1264       int end = start + width;
1265       while (start < end)
1266         if (bitmap_bit_p (s_info->positions_needed.large.bitmap, start++))
1267           return false;
1268       return true;
1269     }
1270   else
1271     {
1272       unsigned HOST_WIDE_INT mask = lowpart_bitmask (width) << start;
1273       return (s_info->positions_needed.small_bitmask & mask) == mask;
1274     }
1275 }
1276
1277
1278 static rtx get_stored_val (store_info_t, enum machine_mode, HOST_WIDE_INT,
1279                            HOST_WIDE_INT, basic_block, bool);
1280
1281
1282 /* BODY is an instruction pattern that belongs to INSN.  Return 1 if
1283    there is a candidate store, after adding it to the appropriate
1284    local store group if so.  */
1285
1286 static int
1287 record_store (rtx body, bb_info_t bb_info)
1288 {
1289   rtx mem, rhs, const_rhs, mem_addr;
1290   HOST_WIDE_INT offset = 0;
1291   HOST_WIDE_INT width = 0;
1292   alias_set_type spill_alias_set;
1293   insn_info_t insn_info = bb_info->last_insn;
1294   store_info_t store_info = NULL;
1295   int group_id;
1296   cselib_val *base = NULL;
1297   insn_info_t ptr, last, redundant_reason;
1298   bool store_is_unused;
1299
1300   if (GET_CODE (body) != SET && GET_CODE (body) != CLOBBER)
1301     return 0;
1302
1303   mem = SET_DEST (body);
1304
1305   /* If this is not used, then this cannot be used to keep the insn
1306      from being deleted.  On the other hand, it does provide something
1307      that can be used to prove that another store is dead.  */
1308   store_is_unused
1309     = (find_reg_note (insn_info->insn, REG_UNUSED, mem) != NULL);
1310
1311   /* Check whether that value is a suitable memory location.  */
1312   if (!MEM_P (mem))
1313     {
1314       /* If the set or clobber is unused, then it does not effect our
1315          ability to get rid of the entire insn.  */
1316       if (!store_is_unused)
1317         insn_info->cannot_delete = true;
1318       return 0;
1319     }
1320
1321   /* At this point we know mem is a mem. */
1322   if (GET_MODE (mem) == BLKmode)
1323     {
1324       if (GET_CODE (XEXP (mem, 0)) == SCRATCH)
1325         {
1326           if (dump_file)
1327             fprintf (dump_file, " adding wild read for (clobber (mem:BLK (scratch))\n");
1328           add_wild_read (bb_info);
1329           insn_info->cannot_delete = true;
1330           return 0;
1331         }
1332       /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
1333          as memset (addr, 0, 36);  */
1334       else if (!MEM_SIZE (mem)
1335                || !CONST_INT_P (MEM_SIZE (mem))
1336                || GET_CODE (body) != SET
1337                || INTVAL (MEM_SIZE (mem)) <= 0
1338                || INTVAL (MEM_SIZE (mem)) > MAX_OFFSET
1339                || !CONST_INT_P (SET_SRC (body)))
1340         {
1341           if (!store_is_unused)
1342             {
1343               /* If the set or clobber is unused, then it does not effect our
1344                  ability to get rid of the entire insn.  */
1345               insn_info->cannot_delete = true;
1346               clear_rhs_from_active_local_stores ();
1347             }
1348           return 0;
1349         }
1350     }
1351
1352   /* We can still process a volatile mem, we just cannot delete it.  */
1353   if (MEM_VOLATILE_P (mem))
1354     insn_info->cannot_delete = true;
1355
1356   if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
1357     {
1358       clear_rhs_from_active_local_stores ();
1359       return 0;
1360     }
1361
1362   if (GET_MODE (mem) == BLKmode)
1363     width = INTVAL (MEM_SIZE (mem));
1364   else
1365     {
1366       width = GET_MODE_SIZE (GET_MODE (mem));
1367       gcc_assert ((unsigned) width <= HOST_BITS_PER_WIDE_INT);
1368     }
1369
1370   if (spill_alias_set)
1371     {
1372       bitmap store1 = clear_alias_group->store1_p;
1373       bitmap store2 = clear_alias_group->store2_p;
1374
1375       gcc_assert (GET_MODE (mem) != BLKmode);
1376
1377       if (bitmap_bit_p (store1, spill_alias_set))
1378         bitmap_set_bit (store2, spill_alias_set);
1379       else
1380         bitmap_set_bit (store1, spill_alias_set);
1381
1382       if (clear_alias_group->offset_map_size_p < spill_alias_set)
1383         clear_alias_group->offset_map_size_p = spill_alias_set;
1384
1385       store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1386
1387       if (dump_file)
1388         fprintf (dump_file, " processing spill store %d(%s)\n",
1389                  (int) spill_alias_set, GET_MODE_NAME (GET_MODE (mem)));
1390     }
1391   else if (group_id >= 0)
1392     {
1393       /* In the restrictive case where the base is a constant or the
1394          frame pointer we can do global analysis.  */
1395
1396       group_info_t group
1397         = VEC_index (group_info_t, rtx_group_vec, group_id);
1398
1399       store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1400       set_usage_bits (group, offset, width);
1401
1402       if (dump_file)
1403         fprintf (dump_file, " processing const base store gid=%d[%d..%d)\n",
1404                  group_id, (int)offset, (int)(offset+width));
1405     }
1406   else
1407     {
1408       rtx base_term = find_base_term (XEXP (mem, 0));
1409       if (!base_term
1410           || (GET_CODE (base_term) == ADDRESS
1411               && GET_MODE (base_term) == Pmode
1412               && XEXP (base_term, 0) == stack_pointer_rtx))
1413         insn_info->stack_pointer_based = true;
1414       insn_info->contains_cselib_groups = true;
1415
1416       store_info = (store_info_t) pool_alloc (cse_store_info_pool);
1417       group_id = -1;
1418
1419       if (dump_file)
1420         fprintf (dump_file, " processing cselib store [%d..%d)\n",
1421                  (int)offset, (int)(offset+width));
1422     }
1423
1424   const_rhs = rhs = NULL_RTX;
1425   if (GET_CODE (body) == SET
1426       /* No place to keep the value after ra.  */
1427       && !reload_completed
1428       && (REG_P (SET_SRC (body))
1429           || GET_CODE (SET_SRC (body)) == SUBREG
1430           || CONSTANT_P (SET_SRC (body)))
1431       && !MEM_VOLATILE_P (mem)
1432       /* Sometimes the store and reload is used for truncation and
1433          rounding.  */
1434       && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
1435     {
1436       rhs = SET_SRC (body);
1437       if (CONSTANT_P (rhs))
1438         const_rhs = rhs;
1439       else if (body == PATTERN (insn_info->insn))
1440         {
1441           rtx tem = find_reg_note (insn_info->insn, REG_EQUAL, NULL_RTX);
1442           if (tem && CONSTANT_P (XEXP (tem, 0)))
1443             const_rhs = XEXP (tem, 0);
1444         }
1445       if (const_rhs == NULL_RTX && REG_P (rhs))
1446         {
1447           rtx tem = cselib_expand_value_rtx (rhs, scratch, 5);
1448
1449           if (tem && CONSTANT_P (tem))
1450             const_rhs = tem;
1451         }
1452     }
1453
1454   /* Check to see if this stores causes some other stores to be
1455      dead.  */
1456   ptr = active_local_stores;
1457   last = NULL;
1458   redundant_reason = NULL;
1459   mem = canon_rtx (mem);
1460   /* For alias_set != 0 canon_true_dependence should be never called.  */
1461   if (spill_alias_set)
1462     mem_addr = NULL_RTX;
1463   else
1464     {
1465       if (group_id < 0)
1466         mem_addr = base->val_rtx;
1467       else
1468         {
1469           group_info_t group
1470             = VEC_index (group_info_t, rtx_group_vec, group_id);
1471           mem_addr = group->canon_base_addr;
1472         }
1473       if (offset)
1474         mem_addr = plus_constant (mem_addr, offset);
1475     }
1476
1477   while (ptr)
1478     {
1479       insn_info_t next = ptr->next_local_store;
1480       store_info_t s_info = ptr->store_rec;
1481       bool del = true;
1482
1483       /* Skip the clobbers. We delete the active insn if this insn
1484          shadows the set.  To have been put on the active list, it
1485          has exactly on set. */
1486       while (!s_info->is_set)
1487         s_info = s_info->next;
1488
1489       if (s_info->alias_set != spill_alias_set)
1490         del = false;
1491       else if (s_info->alias_set)
1492         {
1493           struct clear_alias_mode_holder *entry
1494             = clear_alias_set_lookup (s_info->alias_set);
1495           /* Generally, spills cannot be processed if and of the
1496              references to the slot have a different mode.  But if
1497              we are in the same block and mode is exactly the same
1498              between this store and one before in the same block,
1499              we can still delete it.  */
1500           if ((GET_MODE (mem) == GET_MODE (s_info->mem))
1501               && (GET_MODE (mem) == entry->mode))
1502             {
1503               del = true;
1504               set_all_positions_unneeded (s_info);
1505             }
1506           if (dump_file)
1507             fprintf (dump_file, "    trying spill store in insn=%d alias_set=%d\n",
1508                      INSN_UID (ptr->insn), (int) s_info->alias_set);
1509         }
1510       else if ((s_info->group_id == group_id)
1511                && (s_info->cse_base == base))
1512         {
1513           HOST_WIDE_INT i;
1514           if (dump_file)
1515             fprintf (dump_file, "    trying store in insn=%d gid=%d[%d..%d)\n",
1516                      INSN_UID (ptr->insn), s_info->group_id,
1517                      (int)s_info->begin, (int)s_info->end);
1518
1519           /* Even if PTR won't be eliminated as unneeded, if both
1520              PTR and this insn store the same constant value, we might
1521              eliminate this insn instead.  */
1522           if (s_info->const_rhs
1523               && const_rhs
1524               && offset >= s_info->begin
1525               && offset + width <= s_info->end
1526               && all_positions_needed_p (s_info, offset - s_info->begin,
1527                                          width))
1528             {
1529               if (GET_MODE (mem) == BLKmode)
1530                 {
1531                   if (GET_MODE (s_info->mem) == BLKmode
1532                       && s_info->const_rhs == const_rhs)
1533                     redundant_reason = ptr;
1534                 }
1535               else if (s_info->const_rhs == const0_rtx
1536                        && const_rhs == const0_rtx)
1537                 redundant_reason = ptr;
1538               else
1539                 {
1540                   rtx val;
1541                   start_sequence ();
1542                   val = get_stored_val (s_info, GET_MODE (mem),
1543                                         offset, offset + width,
1544                                         BLOCK_FOR_INSN (insn_info->insn),
1545                                         true);
1546                   if (get_insns () != NULL)
1547                     val = NULL_RTX;
1548                   end_sequence ();
1549                   if (val && rtx_equal_p (val, const_rhs))
1550                     redundant_reason = ptr;
1551                 }
1552             }
1553
1554           for (i = MAX (offset, s_info->begin);
1555                i < offset + width && i < s_info->end;
1556                i++)
1557             set_position_unneeded (s_info, i - s_info->begin);
1558         }
1559       else if (s_info->rhs)
1560         /* Need to see if it is possible for this store to overwrite
1561            the value of store_info.  If it is, set the rhs to NULL to
1562            keep it from being used to remove a load.  */
1563         {
1564           if (canon_true_dependence (s_info->mem,
1565                                      GET_MODE (s_info->mem),
1566                                      s_info->mem_addr,
1567                                      mem, mem_addr, rtx_varies_p))
1568             {
1569               s_info->rhs = NULL;
1570               s_info->const_rhs = NULL;
1571             }
1572         }
1573
1574       /* An insn can be deleted if every position of every one of
1575          its s_infos is zero.  */
1576       if (any_positions_needed_p (s_info)
1577           || ptr->cannot_delete)
1578         del = false;
1579
1580       if (del)
1581         {
1582           insn_info_t insn_to_delete = ptr;
1583
1584           if (last)
1585             last->next_local_store = ptr->next_local_store;
1586           else
1587             active_local_stores = ptr->next_local_store;
1588
1589           delete_dead_store_insn (insn_to_delete);
1590         }
1591       else
1592         last = ptr;
1593
1594       ptr = next;
1595     }
1596
1597   /* Finish filling in the store_info.  */
1598   store_info->next = insn_info->store_rec;
1599   insn_info->store_rec = store_info;
1600   store_info->mem = mem;
1601   store_info->alias_set = spill_alias_set;
1602   store_info->mem_addr = mem_addr;
1603   store_info->cse_base = base;
1604   if (width > HOST_BITS_PER_WIDE_INT)
1605     {
1606       store_info->is_large = true;
1607       store_info->positions_needed.large.count = 0;
1608       store_info->positions_needed.large.bitmap = BITMAP_ALLOC (NULL);
1609     }
1610   else
1611     {
1612       store_info->is_large = false;
1613       store_info->positions_needed.small_bitmask = lowpart_bitmask (width);
1614     }
1615   store_info->group_id = group_id;
1616   store_info->begin = offset;
1617   store_info->end = offset + width;
1618   store_info->is_set = GET_CODE (body) == SET;
1619   store_info->rhs = rhs;
1620   store_info->const_rhs = const_rhs;
1621   store_info->redundant_reason = redundant_reason;
1622
1623   /* If this is a clobber, we return 0.  We will only be able to
1624      delete this insn if there is only one store USED store, but we
1625      can use the clobber to delete other stores earlier.  */
1626   return store_info->is_set ? 1 : 0;
1627 }
1628
1629
1630 static void
1631 dump_insn_info (const char * start, insn_info_t insn_info)
1632 {
1633   fprintf (dump_file, "%s insn=%d %s\n", start,
1634            INSN_UID (insn_info->insn),
1635            insn_info->store_rec ? "has store" : "naked");
1636 }
1637
1638
1639 /* If the modes are different and the value's source and target do not
1640    line up, we need to extract the value from lower part of the rhs of
1641    the store, shift it, and then put it into a form that can be shoved
1642    into the read_insn.  This function generates a right SHIFT of a
1643    value that is at least ACCESS_SIZE bytes wide of READ_MODE.  The
1644    shift sequence is returned or NULL if we failed to find a
1645    shift.  */
1646
1647 static rtx
1648 find_shift_sequence (int access_size,
1649                      store_info_t store_info,
1650                      enum machine_mode read_mode,
1651                      int shift, bool speed, bool require_cst)
1652 {
1653   enum machine_mode store_mode = GET_MODE (store_info->mem);
1654   enum machine_mode new_mode;
1655   rtx read_reg = NULL;
1656
1657   /* Some machines like the x86 have shift insns for each size of
1658      operand.  Other machines like the ppc or the ia-64 may only have
1659      shift insns that shift values within 32 or 64 bit registers.
1660      This loop tries to find the smallest shift insn that will right
1661      justify the value we want to read but is available in one insn on
1662      the machine.  */
1663
1664   for (new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
1665                                           MODE_INT);
1666        GET_MODE_BITSIZE (new_mode) <= BITS_PER_WORD;
1667        new_mode = GET_MODE_WIDER_MODE (new_mode))
1668     {
1669       rtx target, new_reg, shift_seq, insn, new_lhs;
1670       int cost;
1671
1672       /* If a constant was stored into memory, try to simplify it here,
1673          otherwise the cost of the shift might preclude this optimization
1674          e.g. at -Os, even when no actual shift will be needed.  */
1675       if (store_info->const_rhs)
1676         {
1677           unsigned int byte = subreg_lowpart_offset (new_mode, store_mode);
1678           rtx ret = simplify_subreg (new_mode, store_info->const_rhs,
1679                                      store_mode, byte);
1680           if (ret && CONSTANT_P (ret))
1681             {
1682               ret = simplify_const_binary_operation (LSHIFTRT, new_mode,
1683                                                      ret, GEN_INT (shift));
1684               if (ret && CONSTANT_P (ret))
1685                 {
1686                   byte = subreg_lowpart_offset (read_mode, new_mode);
1687                   ret = simplify_subreg (read_mode, ret, new_mode, byte);
1688                   if (ret && CONSTANT_P (ret)
1689                       && rtx_cost (ret, SET, speed) <= COSTS_N_INSNS (1))
1690                     return ret;
1691                 }
1692             }
1693         }
1694
1695       if (require_cst)
1696         return NULL_RTX;
1697
1698       /* Try a wider mode if truncating the store mode to NEW_MODE
1699          requires a real instruction.  */
1700       if (GET_MODE_BITSIZE (new_mode) < GET_MODE_BITSIZE (store_mode)
1701           && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (new_mode),
1702                                      GET_MODE_BITSIZE (store_mode)))
1703         continue;
1704
1705       /* Also try a wider mode if the necessary punning is either not
1706          desirable or not possible.  */
1707       if (!CONSTANT_P (store_info->rhs)
1708           && !MODES_TIEABLE_P (new_mode, store_mode))
1709         continue;
1710
1711       new_reg = gen_reg_rtx (new_mode);
1712
1713       start_sequence ();
1714
1715       /* In theory we could also check for an ashr.  Ian Taylor knows
1716          of one dsp where the cost of these two was not the same.  But
1717          this really is a rare case anyway.  */
1718       target = expand_binop (new_mode, lshr_optab, new_reg,
1719                              GEN_INT (shift), new_reg, 1, OPTAB_DIRECT);
1720
1721       shift_seq = get_insns ();
1722       end_sequence ();
1723
1724       if (target != new_reg || shift_seq == NULL)
1725         continue;
1726
1727       cost = 0;
1728       for (insn = shift_seq; insn != NULL_RTX; insn = NEXT_INSN (insn))
1729         if (INSN_P (insn))
1730           cost += insn_rtx_cost (PATTERN (insn), speed);
1731
1732       /* The computation up to here is essentially independent
1733          of the arguments and could be precomputed.  It may
1734          not be worth doing so.  We could precompute if
1735          worthwhile or at least cache the results.  The result
1736          technically depends on both SHIFT and ACCESS_SIZE,
1737          but in practice the answer will depend only on ACCESS_SIZE.  */
1738
1739       if (cost > COSTS_N_INSNS (1))
1740         continue;
1741
1742       new_lhs = extract_low_bits (new_mode, store_mode,
1743                                   copy_rtx (store_info->rhs));
1744       if (new_lhs == NULL_RTX)
1745         continue;
1746
1747       /* We found an acceptable shift.  Generate a move to
1748          take the value from the store and put it into the
1749          shift pseudo, then shift it, then generate another
1750          move to put in into the target of the read.  */
1751       emit_move_insn (new_reg, new_lhs);
1752       emit_insn (shift_seq);
1753       read_reg = extract_low_bits (read_mode, new_mode, new_reg);
1754       break;
1755     }
1756
1757   return read_reg;
1758 }
1759
1760
1761 /* Call back for note_stores to find the hard regs set or clobbered by
1762    insn.  Data is a bitmap of the hardregs set so far.  */
1763
1764 static void
1765 look_for_hardregs (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
1766 {
1767   bitmap regs_set = (bitmap) data;
1768
1769   if (REG_P (x)
1770       && REGNO (x) < FIRST_PSEUDO_REGISTER)
1771     {
1772       int regno = REGNO (x);
1773       int n = hard_regno_nregs[regno][GET_MODE (x)];
1774       while (--n >= 0)
1775         bitmap_set_bit (regs_set, regno + n);
1776     }
1777 }
1778
1779 /* Helper function for replace_read and record_store.
1780    Attempt to return a value stored in STORE_INFO, from READ_BEGIN
1781    to one before READ_END bytes read in READ_MODE.  Return NULL
1782    if not successful.  If REQUIRE_CST is true, return always constant.  */
1783
1784 static rtx
1785 get_stored_val (store_info_t store_info, enum machine_mode read_mode,
1786                 HOST_WIDE_INT read_begin, HOST_WIDE_INT read_end,
1787                 basic_block bb, bool require_cst)
1788 {
1789   enum machine_mode store_mode = GET_MODE (store_info->mem);
1790   int shift;
1791   int access_size; /* In bytes.  */
1792   rtx read_reg;
1793
1794   /* To get here the read is within the boundaries of the write so
1795      shift will never be negative.  Start out with the shift being in
1796      bytes.  */
1797   if (store_mode == BLKmode)
1798     shift = 0;
1799   else if (BYTES_BIG_ENDIAN)
1800     shift = store_info->end - read_end;
1801   else
1802     shift = read_begin - store_info->begin;
1803
1804   access_size = shift + GET_MODE_SIZE (read_mode);
1805
1806   /* From now on it is bits.  */
1807   shift *= BITS_PER_UNIT;
1808
1809   if (shift)
1810     read_reg = find_shift_sequence (access_size, store_info, read_mode, shift,
1811                                     optimize_bb_for_speed_p (bb),
1812                                     require_cst);
1813   else if (store_mode == BLKmode)
1814     {
1815       /* The store is a memset (addr, const_val, const_size).  */
1816       gcc_assert (CONST_INT_P (store_info->rhs));
1817       store_mode = int_mode_for_mode (read_mode);
1818       if (store_mode == BLKmode)
1819         read_reg = NULL_RTX;
1820       else if (store_info->rhs == const0_rtx)
1821         read_reg = extract_low_bits (read_mode, store_mode, const0_rtx);
1822       else if (GET_MODE_BITSIZE (store_mode) > HOST_BITS_PER_WIDE_INT
1823                || BITS_PER_UNIT >= HOST_BITS_PER_WIDE_INT)
1824         read_reg = NULL_RTX;
1825       else
1826         {
1827           unsigned HOST_WIDE_INT c
1828             = INTVAL (store_info->rhs)
1829               & (((HOST_WIDE_INT) 1 << BITS_PER_UNIT) - 1);
1830           int shift = BITS_PER_UNIT;
1831           while (shift < HOST_BITS_PER_WIDE_INT)
1832             {
1833               c |= (c << shift);
1834               shift <<= 1;
1835             }
1836           read_reg = GEN_INT (trunc_int_for_mode (c, store_mode));
1837           read_reg = extract_low_bits (read_mode, store_mode, read_reg);
1838         }
1839     }
1840   else if (store_info->const_rhs
1841            && (require_cst
1842                || GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode)))
1843     read_reg = extract_low_bits (read_mode, store_mode,
1844                                  copy_rtx (store_info->const_rhs));
1845   else
1846     read_reg = extract_low_bits (read_mode, store_mode,
1847                                  copy_rtx (store_info->rhs));
1848   if (require_cst && read_reg && !CONSTANT_P (read_reg))
1849     read_reg = NULL_RTX;
1850   return read_reg;
1851 }
1852
1853 /* Take a sequence of:
1854      A <- r1
1855      ...
1856      ... <- A
1857
1858    and change it into
1859    r2 <- r1
1860    A <- r1
1861    ...
1862    ... <- r2
1863
1864    or
1865
1866    r3 <- extract (r1)
1867    r3 <- r3 >> shift
1868    r2 <- extract (r3)
1869    ... <- r2
1870
1871    or
1872
1873    r2 <- extract (r1)
1874    ... <- r2
1875
1876    Depending on the alignment and the mode of the store and
1877    subsequent load.
1878
1879
1880    The STORE_INFO and STORE_INSN are for the store and READ_INFO
1881    and READ_INSN are for the read.  Return true if the replacement
1882    went ok.  */
1883
1884 static bool
1885 replace_read (store_info_t store_info, insn_info_t store_insn,
1886               read_info_t read_info, insn_info_t read_insn, rtx *loc,
1887               bitmap regs_live)
1888 {
1889   enum machine_mode store_mode = GET_MODE (store_info->mem);
1890   enum machine_mode read_mode = GET_MODE (read_info->mem);
1891   rtx insns, this_insn, read_reg;
1892   basic_block bb;
1893
1894   if (!dbg_cnt (dse))
1895     return false;
1896
1897   /* Create a sequence of instructions to set up the read register.
1898      This sequence goes immediately before the store and its result
1899      is read by the load.
1900
1901      We need to keep this in perspective.  We are replacing a read
1902      with a sequence of insns, but the read will almost certainly be
1903      in cache, so it is not going to be an expensive one.  Thus, we
1904      are not willing to do a multi insn shift or worse a subroutine
1905      call to get rid of the read.  */
1906   if (dump_file)
1907     fprintf (dump_file, "trying to replace %smode load in insn %d"
1908              " from %smode store in insn %d\n",
1909              GET_MODE_NAME (read_mode), INSN_UID (read_insn->insn),
1910              GET_MODE_NAME (store_mode), INSN_UID (store_insn->insn));
1911   start_sequence ();
1912   bb = BLOCK_FOR_INSN (read_insn->insn);
1913   read_reg = get_stored_val (store_info,
1914                              read_mode, read_info->begin, read_info->end,
1915                              bb, false);
1916   if (read_reg == NULL_RTX)
1917     {
1918       end_sequence ();
1919       if (dump_file)
1920         fprintf (dump_file, " -- could not extract bits of stored value\n");
1921       return false;
1922     }
1923   /* Force the value into a new register so that it won't be clobbered
1924      between the store and the load.  */
1925   read_reg = copy_to_mode_reg (read_mode, read_reg);
1926   insns = get_insns ();
1927   end_sequence ();
1928
1929   if (insns != NULL_RTX)
1930     {
1931       /* Now we have to scan the set of new instructions to see if the
1932          sequence contains and sets of hardregs that happened to be
1933          live at this point.  For instance, this can happen if one of
1934          the insns sets the CC and the CC happened to be live at that
1935          point.  This does occasionally happen, see PR 37922.  */
1936       bitmap regs_set = BITMAP_ALLOC (NULL);
1937
1938       for (this_insn = insns; this_insn != NULL_RTX; this_insn = NEXT_INSN (this_insn))
1939         note_stores (PATTERN (this_insn), look_for_hardregs, regs_set);
1940
1941       bitmap_and_into (regs_set, regs_live);
1942       if (!bitmap_empty_p (regs_set))
1943         {
1944           if (dump_file)
1945             {
1946               fprintf (dump_file,
1947                        "abandoning replacement because sequence clobbers live hardregs:");
1948               df_print_regset (dump_file, regs_set);
1949             }
1950
1951           BITMAP_FREE (regs_set);
1952           return false;
1953         }
1954       BITMAP_FREE (regs_set);
1955     }
1956
1957   if (validate_change (read_insn->insn, loc, read_reg, 0))
1958     {
1959       deferred_change_t deferred_change =
1960         (deferred_change_t) pool_alloc (deferred_change_pool);
1961
1962       /* Insert this right before the store insn where it will be safe
1963          from later insns that might change it before the read.  */
1964       emit_insn_before (insns, store_insn->insn);
1965
1966       /* And now for the kludge part: cselib croaks if you just
1967          return at this point.  There are two reasons for this:
1968
1969          1) Cselib has an idea of how many pseudos there are and
1970          that does not include the new ones we just added.
1971
1972          2) Cselib does not know about the move insn we added
1973          above the store_info, and there is no way to tell it
1974          about it, because it has "moved on".
1975
1976          Problem (1) is fixable with a certain amount of engineering.
1977          Problem (2) is requires starting the bb from scratch.  This
1978          could be expensive.
1979
1980          So we are just going to have to lie.  The move/extraction
1981          insns are not really an issue, cselib did not see them.  But
1982          the use of the new pseudo read_insn is a real problem because
1983          cselib has not scanned this insn.  The way that we solve this
1984          problem is that we are just going to put the mem back for now
1985          and when we are finished with the block, we undo this.  We
1986          keep a table of mems to get rid of.  At the end of the basic
1987          block we can put them back.  */
1988
1989       *loc = read_info->mem;
1990       deferred_change->next = deferred_change_list;
1991       deferred_change_list = deferred_change;
1992       deferred_change->loc = loc;
1993       deferred_change->reg = read_reg;
1994
1995       /* Get rid of the read_info, from the point of view of the
1996          rest of dse, play like this read never happened.  */
1997       read_insn->read_rec = read_info->next;
1998       pool_free (read_info_pool, read_info);
1999       if (dump_file)
2000         {
2001           fprintf (dump_file, " -- replaced the loaded MEM with ");
2002           print_simple_rtl (dump_file, read_reg);
2003           fprintf (dump_file, "\n");
2004         }
2005       return true;
2006     }
2007   else
2008     {
2009       if (dump_file)
2010         {
2011           fprintf (dump_file, " -- replacing the loaded MEM with ");
2012           print_simple_rtl (dump_file, read_reg);
2013           fprintf (dump_file, " led to an invalid instruction\n");
2014         }
2015       return false;
2016     }
2017 }
2018
2019 /* A for_each_rtx callback in which DATA is the bb_info.  Check to see
2020    if LOC is a mem and if it is look at the address and kill any
2021    appropriate stores that may be active.  */
2022
2023 static int
2024 check_mem_read_rtx (rtx *loc, void *data)
2025 {
2026   rtx mem = *loc, mem_addr;
2027   bb_info_t bb_info;
2028   insn_info_t insn_info;
2029   HOST_WIDE_INT offset = 0;
2030   HOST_WIDE_INT width = 0;
2031   alias_set_type spill_alias_set = 0;
2032   cselib_val *base = NULL;
2033   int group_id;
2034   read_info_t read_info;
2035
2036   if (!mem || !MEM_P (mem))
2037     return 0;
2038
2039   bb_info = (bb_info_t) data;
2040   insn_info = bb_info->last_insn;
2041
2042   if ((MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2043       || (MEM_VOLATILE_P (mem)))
2044     {
2045       if (dump_file)
2046         fprintf (dump_file, " adding wild read, volatile or barrier.\n");
2047       add_wild_read (bb_info);
2048       insn_info->cannot_delete = true;
2049       return 0;
2050     }
2051
2052   /* If it is reading readonly mem, then there can be no conflict with
2053      another write. */
2054   if (MEM_READONLY_P (mem))
2055     return 0;
2056
2057   if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
2058     {
2059       if (dump_file)
2060         fprintf (dump_file, " adding wild read, canon_address failure.\n");
2061       add_wild_read (bb_info);
2062       return 0;
2063     }
2064
2065   if (GET_MODE (mem) == BLKmode)
2066     width = -1;
2067   else
2068     width = GET_MODE_SIZE (GET_MODE (mem));
2069
2070   read_info = (read_info_t) pool_alloc (read_info_pool);
2071   read_info->group_id = group_id;
2072   read_info->mem = mem;
2073   read_info->alias_set = spill_alias_set;
2074   read_info->begin = offset;
2075   read_info->end = offset + width;
2076   read_info->next = insn_info->read_rec;
2077   insn_info->read_rec = read_info;
2078   /* For alias_set != 0 canon_true_dependence should be never called.  */
2079   if (spill_alias_set)
2080     mem_addr = NULL_RTX;
2081   else
2082     {
2083       if (group_id < 0)
2084         mem_addr = base->val_rtx;
2085       else
2086         {
2087           group_info_t group
2088             = VEC_index (group_info_t, rtx_group_vec, group_id);
2089           mem_addr = group->canon_base_addr;
2090         }
2091       if (offset)
2092         mem_addr = plus_constant (mem_addr, offset);
2093     }
2094
2095   /* We ignore the clobbers in store_info.  The is mildly aggressive,
2096      but there really should not be a clobber followed by a read.  */
2097
2098   if (spill_alias_set)
2099     {
2100       insn_info_t i_ptr = active_local_stores;
2101       insn_info_t last = NULL;
2102
2103       if (dump_file)
2104         fprintf (dump_file, " processing spill load %d\n",
2105                  (int) spill_alias_set);
2106
2107       while (i_ptr)
2108         {
2109           store_info_t store_info = i_ptr->store_rec;
2110
2111           /* Skip the clobbers.  */
2112           while (!store_info->is_set)
2113             store_info = store_info->next;
2114
2115           if (store_info->alias_set == spill_alias_set)
2116             {
2117               if (dump_file)
2118                 dump_insn_info ("removing from active", i_ptr);
2119
2120               if (last)
2121                 last->next_local_store = i_ptr->next_local_store;
2122               else
2123                 active_local_stores = i_ptr->next_local_store;
2124             }
2125           else
2126             last = i_ptr;
2127           i_ptr = i_ptr->next_local_store;
2128         }
2129     }
2130   else if (group_id >= 0)
2131     {
2132       /* This is the restricted case where the base is a constant or
2133          the frame pointer and offset is a constant.  */
2134       insn_info_t i_ptr = active_local_stores;
2135       insn_info_t last = NULL;
2136
2137       if (dump_file)
2138         {
2139           if (width == -1)
2140             fprintf (dump_file, " processing const load gid=%d[BLK]\n",
2141                      group_id);
2142           else
2143             fprintf (dump_file, " processing const load gid=%d[%d..%d)\n",
2144                      group_id, (int)offset, (int)(offset+width));
2145         }
2146
2147       while (i_ptr)
2148         {
2149           bool remove = false;
2150           store_info_t store_info = i_ptr->store_rec;
2151
2152           /* Skip the clobbers.  */
2153           while (!store_info->is_set)
2154             store_info = store_info->next;
2155
2156           /* There are three cases here.  */
2157           if (store_info->group_id < 0)
2158             /* We have a cselib store followed by a read from a
2159                const base. */
2160             remove
2161               = canon_true_dependence (store_info->mem,
2162                                        GET_MODE (store_info->mem),
2163                                        store_info->mem_addr,
2164                                        mem, mem_addr, rtx_varies_p);
2165
2166           else if (group_id == store_info->group_id)
2167             {
2168               /* This is a block mode load.  We may get lucky and
2169                  canon_true_dependence may save the day.  */
2170               if (width == -1)
2171                 remove
2172                   = canon_true_dependence (store_info->mem,
2173                                            GET_MODE (store_info->mem),
2174                                            store_info->mem_addr,
2175                                            mem, mem_addr, rtx_varies_p);
2176
2177               /* If this read is just reading back something that we just
2178                  stored, rewrite the read.  */
2179               else
2180                 {
2181                   if (store_info->rhs
2182                       && offset >= store_info->begin
2183                       && offset + width <= store_info->end
2184                       && all_positions_needed_p (store_info,
2185                                                  offset - store_info->begin,
2186                                                  width)
2187                       && replace_read (store_info, i_ptr, read_info,
2188                                        insn_info, loc, bb_info->regs_live))
2189                     return 0;
2190
2191                   /* The bases are the same, just see if the offsets
2192                      overlap.  */
2193                   if ((offset < store_info->end)
2194                       && (offset + width > store_info->begin))
2195                     remove = true;
2196                 }
2197             }
2198
2199           /* else
2200              The else case that is missing here is that the
2201              bases are constant but different.  There is nothing
2202              to do here because there is no overlap.  */
2203
2204           if (remove)
2205             {
2206               if (dump_file)
2207                 dump_insn_info ("removing from active", i_ptr);
2208
2209               if (last)
2210                 last->next_local_store = i_ptr->next_local_store;
2211               else
2212                 active_local_stores = i_ptr->next_local_store;
2213             }
2214           else
2215             last = i_ptr;
2216           i_ptr = i_ptr->next_local_store;
2217         }
2218     }
2219   else
2220     {
2221       insn_info_t i_ptr = active_local_stores;
2222       insn_info_t last = NULL;
2223       if (dump_file)
2224         {
2225           fprintf (dump_file, " processing cselib load mem:");
2226           print_inline_rtx (dump_file, mem, 0);
2227           fprintf (dump_file, "\n");
2228         }
2229
2230       while (i_ptr)
2231         {
2232           bool remove = false;
2233           store_info_t store_info = i_ptr->store_rec;
2234
2235           if (dump_file)
2236             fprintf (dump_file, " processing cselib load against insn %d\n",
2237                      INSN_UID (i_ptr->insn));
2238
2239           /* Skip the clobbers.  */
2240           while (!store_info->is_set)
2241             store_info = store_info->next;
2242
2243           /* If this read is just reading back something that we just
2244              stored, rewrite the read.  */
2245           if (store_info->rhs
2246               && store_info->group_id == -1
2247               && store_info->cse_base == base
2248               && offset >= store_info->begin
2249               && offset + width <= store_info->end
2250               && all_positions_needed_p (store_info,
2251                                          offset - store_info->begin, width)
2252               && replace_read (store_info, i_ptr,  read_info, insn_info, loc,
2253                                bb_info->regs_live))
2254             return 0;
2255
2256           if (!store_info->alias_set)
2257             remove = canon_true_dependence (store_info->mem,
2258                                             GET_MODE (store_info->mem),
2259                                             store_info->mem_addr,
2260                                             mem, mem_addr, rtx_varies_p);
2261
2262           if (remove)
2263             {
2264               if (dump_file)
2265                 dump_insn_info ("removing from active", i_ptr);
2266
2267               if (last)
2268                 last->next_local_store = i_ptr->next_local_store;
2269               else
2270                 active_local_stores = i_ptr->next_local_store;
2271             }
2272           else
2273             last = i_ptr;
2274           i_ptr = i_ptr->next_local_store;
2275         }
2276     }
2277   return 0;
2278 }
2279
2280 /* A for_each_rtx callback in which DATA points the INSN_INFO for
2281    as check_mem_read_rtx.  Nullify the pointer if i_m_r_m_r returns
2282    true for any part of *LOC.  */
2283
2284 static void
2285 check_mem_read_use (rtx *loc, void *data)
2286 {
2287   for_each_rtx (loc, check_mem_read_rtx, data);
2288 }
2289
2290
2291 /* Get arguments passed to CALL_INSN.  Return TRUE if successful.
2292    So far it only handles arguments passed in registers.  */
2293
2294 static bool
2295 get_call_args (rtx call_insn, tree fn, rtx *args, int nargs)
2296 {
2297   CUMULATIVE_ARGS args_so_far;
2298   tree arg;
2299   int idx;
2300
2301   INIT_CUMULATIVE_ARGS (args_so_far, TREE_TYPE (fn), NULL_RTX, 0, 3);
2302
2303   arg = TYPE_ARG_TYPES (TREE_TYPE (fn));
2304   for (idx = 0;
2305        arg != void_list_node && idx < nargs;
2306        arg = TREE_CHAIN (arg), idx++)
2307     {
2308       enum machine_mode mode = TYPE_MODE (TREE_VALUE (arg));
2309       rtx reg = FUNCTION_ARG (args_so_far, mode, NULL_TREE, 1), link, tmp;
2310       if (!reg || !REG_P (reg) || GET_MODE (reg) != mode
2311           || GET_MODE_CLASS (mode) != MODE_INT)
2312         return false;
2313
2314       for (link = CALL_INSN_FUNCTION_USAGE (call_insn);
2315            link;
2316            link = XEXP (link, 1))
2317         if (GET_CODE (XEXP (link, 0)) == USE)
2318           {
2319             args[idx] = XEXP (XEXP (link, 0), 0);
2320             if (REG_P (args[idx])
2321                 && REGNO (args[idx]) == REGNO (reg)
2322                 && (GET_MODE (args[idx]) == mode
2323                     || (GET_MODE_CLASS (GET_MODE (args[idx])) == MODE_INT
2324                         && (GET_MODE_SIZE (GET_MODE (args[idx]))
2325                             <= UNITS_PER_WORD)
2326                         && (GET_MODE_SIZE (GET_MODE (args[idx]))
2327                             > GET_MODE_SIZE (mode)))))
2328               break;
2329           }
2330       if (!link)
2331         return false;
2332
2333       tmp = cselib_expand_value_rtx (args[idx], scratch, 5);
2334       if (GET_MODE (args[idx]) != mode)
2335         {
2336           if (!tmp || !CONST_INT_P (tmp))
2337             return false;
2338           tmp = GEN_INT (trunc_int_for_mode (INTVAL (tmp), mode));
2339         }
2340       if (tmp)
2341         args[idx] = tmp;
2342
2343       FUNCTION_ARG_ADVANCE (args_so_far, mode, NULL_TREE, 1);
2344     }
2345   if (arg != void_list_node || idx != nargs)
2346     return false;
2347   return true;
2348 }
2349
2350
2351 /* Apply record_store to all candidate stores in INSN.  Mark INSN
2352    if some part of it is not a candidate store and assigns to a
2353    non-register target.  */
2354
2355 static void
2356 scan_insn (bb_info_t bb_info, rtx insn)
2357 {
2358   rtx body;
2359   insn_info_t insn_info = (insn_info_t) pool_alloc (insn_info_pool);
2360   int mems_found = 0;
2361   memset (insn_info, 0, sizeof (struct insn_info));
2362
2363   if (dump_file)
2364     fprintf (dump_file, "\n**scanning insn=%d\n",
2365              INSN_UID (insn));
2366
2367   insn_info->prev_insn = bb_info->last_insn;
2368   insn_info->insn = insn;
2369   bb_info->last_insn = insn_info;
2370
2371
2372   /* Cselib clears the table for this case, so we have to essentially
2373      do the same.  */
2374   if (NONJUMP_INSN_P (insn)
2375       && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
2376       && MEM_VOLATILE_P (PATTERN (insn)))
2377     {
2378       add_wild_read (bb_info);
2379       insn_info->cannot_delete = true;
2380       return;
2381     }
2382
2383   /* Look at all of the uses in the insn.  */
2384   note_uses (&PATTERN (insn), check_mem_read_use, bb_info);
2385
2386   if (CALL_P (insn))
2387     {
2388       bool const_call;
2389       tree memset_call = NULL_TREE;
2390
2391       insn_info->cannot_delete = true;
2392
2393       /* Const functions cannot do anything bad i.e. read memory,
2394          however, they can read their parameters which may have
2395          been pushed onto the stack.
2396          memset and bzero don't read memory either.  */
2397       const_call = RTL_CONST_CALL_P (insn);
2398       if (!const_call)
2399         {
2400           rtx call = PATTERN (insn);
2401           if (GET_CODE (call) == PARALLEL)
2402             call = XVECEXP (call, 0, 0);
2403           if (GET_CODE (call) == SET)
2404             call = SET_SRC (call);
2405           if (GET_CODE (call) == CALL
2406               && MEM_P (XEXP (call, 0))
2407               && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
2408             {
2409               rtx symbol = XEXP (XEXP (call, 0), 0);
2410               if (SYMBOL_REF_DECL (symbol)
2411                   && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
2412                 {
2413                   if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
2414                        == BUILT_IN_NORMAL
2415                        && (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))
2416                            == BUILT_IN_MEMSET))
2417                       || SYMBOL_REF_DECL (symbol) == block_clear_fn)
2418                     memset_call = SYMBOL_REF_DECL (symbol);
2419                 }
2420             }
2421         }
2422       if (const_call || memset_call)
2423         {
2424           insn_info_t i_ptr = active_local_stores;
2425           insn_info_t last = NULL;
2426
2427           if (dump_file)
2428             fprintf (dump_file, "%s call %d\n",
2429                      const_call ? "const" : "memset", INSN_UID (insn));
2430
2431           /* See the head comment of the frame_read field.  */
2432           if (reload_completed)
2433             insn_info->frame_read = true;
2434
2435           /* Loop over the active stores and remove those which are
2436              killed by the const function call.  */
2437           while (i_ptr)
2438             {
2439               bool remove_store = false;
2440
2441               /* The stack pointer based stores are always killed.  */
2442               if (i_ptr->stack_pointer_based)
2443                 remove_store = true;
2444
2445               /* If the frame is read, the frame related stores are killed.  */
2446               else if (insn_info->frame_read)
2447                 {
2448                   store_info_t store_info = i_ptr->store_rec;
2449
2450                   /* Skip the clobbers.  */
2451                   while (!store_info->is_set)
2452                     store_info = store_info->next;
2453
2454                   if (store_info->group_id >= 0
2455                       && VEC_index (group_info_t, rtx_group_vec,
2456                                     store_info->group_id)->frame_related)
2457                     remove_store = true;
2458                 }
2459
2460               if (remove_store)
2461                 {
2462                   if (dump_file)
2463                     dump_insn_info ("removing from active", i_ptr);
2464
2465                   if (last)
2466                     last->next_local_store = i_ptr->next_local_store;
2467                   else
2468                     active_local_stores = i_ptr->next_local_store;
2469                 }
2470               else
2471                 last = i_ptr;
2472
2473               i_ptr = i_ptr->next_local_store;
2474             }
2475
2476           if (memset_call)
2477             {
2478               rtx args[3];
2479               if (get_call_args (insn, memset_call, args, 3)
2480                   && CONST_INT_P (args[1])
2481                   && CONST_INT_P (args[2])
2482                   && INTVAL (args[2]) > 0)
2483                 {
2484                   rtx mem = gen_rtx_MEM (BLKmode, args[0]);
2485                   set_mem_size (mem, args[2]);
2486                   body = gen_rtx_SET (VOIDmode, mem, args[1]);
2487                   mems_found += record_store (body, bb_info);
2488                   if (dump_file)
2489                     fprintf (dump_file, "handling memset as BLKmode store\n");
2490                   if (mems_found == 1)
2491                     {
2492                       insn_info->next_local_store = active_local_stores;
2493                       active_local_stores = insn_info;
2494                     }
2495                 }
2496             }
2497         }
2498
2499       else
2500         /* Every other call, including pure functions, may read memory.  */
2501         add_wild_read (bb_info);
2502
2503       return;
2504     }
2505
2506   /* Assuming that there are sets in these insns, we cannot delete
2507      them.  */
2508   if ((GET_CODE (PATTERN (insn)) == CLOBBER)
2509       || volatile_refs_p (PATTERN (insn))
2510       || (flag_non_call_exceptions && may_trap_p (PATTERN (insn)))
2511       || (RTX_FRAME_RELATED_P (insn))
2512       || find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX))
2513     insn_info->cannot_delete = true;
2514
2515   body = PATTERN (insn);
2516   if (GET_CODE (body) == PARALLEL)
2517     {
2518       int i;
2519       for (i = 0; i < XVECLEN (body, 0); i++)
2520         mems_found += record_store (XVECEXP (body, 0, i), bb_info);
2521     }
2522   else
2523     mems_found += record_store (body, bb_info);
2524
2525   if (dump_file)
2526     fprintf (dump_file, "mems_found = %d, cannot_delete = %s\n",
2527              mems_found, insn_info->cannot_delete ? "true" : "false");
2528
2529   /* If we found some sets of mems, add it into the active_local_stores so
2530      that it can be locally deleted if found dead or used for
2531      replace_read and redundant constant store elimination.  Otherwise mark
2532      it as cannot delete.  This simplifies the processing later.  */
2533   if (mems_found == 1)
2534     {
2535       insn_info->next_local_store = active_local_stores;
2536       active_local_stores = insn_info;
2537     }
2538   else
2539     insn_info->cannot_delete = true;
2540 }
2541
2542
2543 /* Remove BASE from the set of active_local_stores.  This is a
2544    callback from cselib that is used to get rid of the stores in
2545    active_local_stores.  */
2546
2547 static void
2548 remove_useless_values (cselib_val *base)
2549 {
2550   insn_info_t insn_info = active_local_stores;
2551   insn_info_t last = NULL;
2552
2553   while (insn_info)
2554     {
2555       store_info_t store_info = insn_info->store_rec;
2556       bool del = false;
2557
2558       /* If ANY of the store_infos match the cselib group that is
2559          being deleted, then the insn can not be deleted.  */
2560       while (store_info)
2561         {
2562           if ((store_info->group_id == -1)
2563               && (store_info->cse_base == base))
2564             {
2565               del = true;
2566               break;
2567             }
2568           store_info = store_info->next;
2569         }
2570
2571       if (del)
2572         {
2573           if (last)
2574             last->next_local_store = insn_info->next_local_store;
2575           else
2576             active_local_stores = insn_info->next_local_store;
2577           free_store_info (insn_info);
2578         }
2579       else
2580         last = insn_info;
2581
2582       insn_info = insn_info->next_local_store;
2583     }
2584 }
2585
2586
2587 /* Do all of step 1.  */
2588
2589 static void
2590 dse_step1 (void)
2591 {
2592   basic_block bb;
2593   bitmap regs_live = BITMAP_ALLOC (NULL);
2594
2595   cselib_init (false);
2596   all_blocks = BITMAP_ALLOC (NULL);
2597   bitmap_set_bit (all_blocks, ENTRY_BLOCK);
2598   bitmap_set_bit (all_blocks, EXIT_BLOCK);
2599
2600   FOR_ALL_BB (bb)
2601     {
2602       insn_info_t ptr;
2603       bb_info_t bb_info = (bb_info_t) pool_alloc (bb_info_pool);
2604
2605       memset (bb_info, 0, sizeof (struct bb_info));
2606       bitmap_set_bit (all_blocks, bb->index);
2607       bb_info->regs_live = regs_live;
2608
2609       bitmap_copy (regs_live, DF_LR_IN (bb));
2610       df_simulate_initialize_forwards (bb, regs_live);
2611
2612       bb_table[bb->index] = bb_info;
2613       cselib_discard_hook = remove_useless_values;
2614
2615       if (bb->index >= NUM_FIXED_BLOCKS)
2616         {
2617           rtx insn;
2618
2619           cse_store_info_pool
2620             = create_alloc_pool ("cse_store_info_pool",
2621                                  sizeof (struct store_info), 100);
2622           active_local_stores = NULL;
2623           cselib_clear_table ();
2624
2625           /* Scan the insns.  */
2626           FOR_BB_INSNS (bb, insn)
2627             {
2628               if (INSN_P (insn))
2629                 scan_insn (bb_info, insn);
2630               cselib_process_insn (insn);
2631               if (INSN_P (insn))
2632                 df_simulate_one_insn_forwards (bb, insn, regs_live);
2633             }
2634
2635           /* This is something of a hack, because the global algorithm
2636              is supposed to take care of the case where stores go dead
2637              at the end of the function.  However, the global
2638              algorithm must take a more conservative view of block
2639              mode reads than the local alg does.  So to get the case
2640              where you have a store to the frame followed by a non
2641              overlapping block more read, we look at the active local
2642              stores at the end of the function and delete all of the
2643              frame and spill based ones.  */
2644           if (stores_off_frame_dead_at_return
2645               && (EDGE_COUNT (bb->succs) == 0
2646                   || (single_succ_p (bb)
2647                       && single_succ (bb) == EXIT_BLOCK_PTR
2648                       && ! crtl->calls_eh_return)))
2649             {
2650               insn_info_t i_ptr = active_local_stores;
2651               while (i_ptr)
2652                 {
2653                   store_info_t store_info = i_ptr->store_rec;
2654
2655                   /* Skip the clobbers.  */
2656                   while (!store_info->is_set)
2657                     store_info = store_info->next;
2658                   if (store_info->alias_set && !i_ptr->cannot_delete)
2659                     delete_dead_store_insn (i_ptr);
2660                   else
2661                     if (store_info->group_id >= 0)
2662                       {
2663                         group_info_t group
2664                           = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
2665                         if (group->frame_related && !i_ptr->cannot_delete)
2666                           delete_dead_store_insn (i_ptr);
2667                       }
2668
2669                   i_ptr = i_ptr->next_local_store;
2670                 }
2671             }
2672
2673           /* Get rid of the loads that were discovered in
2674              replace_read.  Cselib is finished with this block.  */
2675           while (deferred_change_list)
2676             {
2677               deferred_change_t next = deferred_change_list->next;
2678
2679               /* There is no reason to validate this change.  That was
2680                  done earlier.  */
2681               *deferred_change_list->loc = deferred_change_list->reg;
2682               pool_free (deferred_change_pool, deferred_change_list);
2683               deferred_change_list = next;
2684             }
2685
2686           /* Get rid of all of the cselib based store_infos in this
2687              block and mark the containing insns as not being
2688              deletable.  */
2689           ptr = bb_info->last_insn;
2690           while (ptr)
2691             {
2692               if (ptr->contains_cselib_groups)
2693                 {
2694                   store_info_t s_info = ptr->store_rec;
2695                   while (s_info && !s_info->is_set)
2696                     s_info = s_info->next;
2697                   if (s_info
2698                       && s_info->redundant_reason
2699                       && s_info->redundant_reason->insn
2700                       && !ptr->cannot_delete)
2701                     {
2702                       if (dump_file)
2703                         fprintf (dump_file, "Locally deleting insn %d "
2704                                             "because insn %d stores the "
2705                                             "same value and couldn't be "
2706                                             "eliminated\n",
2707                                  INSN_UID (ptr->insn),
2708                                  INSN_UID (s_info->redundant_reason->insn));
2709                       delete_dead_store_insn (ptr);
2710                     }
2711                   if (s_info)
2712                     s_info->redundant_reason = NULL;
2713                   free_store_info (ptr);
2714                 }
2715               else
2716                 {
2717                   store_info_t s_info;
2718
2719                   /* Free at least positions_needed bitmaps.  */
2720                   for (s_info = ptr->store_rec; s_info; s_info = s_info->next)
2721                     if (s_info->is_large)
2722                       {
2723                         BITMAP_FREE (s_info->positions_needed.large.bitmap);
2724                         s_info->is_large = false;
2725                       }
2726                 }
2727               ptr = ptr->prev_insn;
2728             }
2729
2730           free_alloc_pool (cse_store_info_pool);
2731         }
2732       bb_info->regs_live = NULL;
2733     }
2734
2735   BITMAP_FREE (regs_live);
2736   cselib_finish ();
2737   htab_empty (rtx_group_table);
2738 }
2739
2740 \f
2741 /*----------------------------------------------------------------------------
2742    Second step.
2743
2744    Assign each byte position in the stores that we are going to
2745    analyze globally to a position in the bitmaps.  Returns true if
2746    there are any bit positions assigned.
2747 ----------------------------------------------------------------------------*/
2748
2749 static void
2750 dse_step2_init (void)
2751 {
2752   unsigned int i;
2753   group_info_t group;
2754
2755   for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2756     {
2757       /* For all non stack related bases, we only consider a store to
2758          be deletable if there are two or more stores for that
2759          position.  This is because it takes one store to make the
2760          other store redundant.  However, for the stores that are
2761          stack related, we consider them if there is only one store
2762          for the position.  We do this because the stack related
2763          stores can be deleted if their is no read between them and
2764          the end of the function.
2765
2766          To make this work in the current framework, we take the stack
2767          related bases add all of the bits from store1 into store2.
2768          This has the effect of making the eligible even if there is
2769          only one store.   */
2770
2771       if (stores_off_frame_dead_at_return && group->frame_related)
2772         {
2773           bitmap_ior_into (group->store2_n, group->store1_n);
2774           bitmap_ior_into (group->store2_p, group->store1_p);
2775           if (dump_file)
2776             fprintf (dump_file, "group %d is frame related ", i);
2777         }
2778
2779       group->offset_map_size_n++;
2780       group->offset_map_n = XNEWVEC (int, group->offset_map_size_n);
2781       group->offset_map_size_p++;
2782       group->offset_map_p = XNEWVEC (int, group->offset_map_size_p);
2783       group->process_globally = false;
2784       if (dump_file)
2785         {
2786           fprintf (dump_file, "group %d(%d+%d): ", i,
2787                    (int)bitmap_count_bits (group->store2_n),
2788                    (int)bitmap_count_bits (group->store2_p));
2789           bitmap_print (dump_file, group->store2_n, "n ", " ");
2790           bitmap_print (dump_file, group->store2_p, "p ", "\n");
2791         }
2792     }
2793 }
2794
2795
2796 /* Init the offset tables for the normal case.  */
2797
2798 static bool
2799 dse_step2_nospill (void)
2800 {
2801   unsigned int i;
2802   group_info_t group;
2803   /* Position 0 is unused because 0 is used in the maps to mean
2804      unused.  */
2805   current_position = 1;
2806
2807   for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2808     {
2809       bitmap_iterator bi;
2810       unsigned int j;
2811
2812       if (group == clear_alias_group)
2813         continue;
2814
2815       memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2816       memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2817       bitmap_clear (group->group_kill);
2818
2819       EXECUTE_IF_SET_IN_BITMAP (group->store2_n, 0, j, bi)
2820         {
2821           bitmap_set_bit (group->group_kill, current_position);
2822           group->offset_map_n[j] = current_position++;
2823           group->process_globally = true;
2824         }
2825       EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2826         {
2827           bitmap_set_bit (group->group_kill, current_position);
2828           group->offset_map_p[j] = current_position++;
2829           group->process_globally = true;
2830         }
2831     }
2832   return current_position != 1;
2833 }
2834
2835
2836 /* Init the offset tables for the spill case.  */
2837
2838 static bool
2839 dse_step2_spill (void)
2840 {
2841   unsigned int j;
2842   group_info_t group = clear_alias_group;
2843   bitmap_iterator bi;
2844
2845   /* Position 0 is unused because 0 is used in the maps to mean
2846      unused.  */
2847   current_position = 1;
2848
2849   if (dump_file)
2850     {
2851       bitmap_print (dump_file, clear_alias_sets,
2852                     "clear alias sets              ", "\n");
2853       bitmap_print (dump_file, disqualified_clear_alias_sets,
2854                     "disqualified clear alias sets ", "\n");
2855     }
2856
2857   memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2858   memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2859   bitmap_clear (group->group_kill);
2860
2861   /* Remove the disqualified positions from the store2_p set.  */
2862   bitmap_and_compl_into (group->store2_p, disqualified_clear_alias_sets);
2863
2864   /* We do not need to process the store2_n set because
2865      alias_sets are always positive.  */
2866   EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2867     {
2868       bitmap_set_bit (group->group_kill, current_position);
2869       group->offset_map_p[j] = current_position++;
2870       group->process_globally = true;
2871     }
2872
2873   return current_position != 1;
2874 }
2875
2876
2877 \f
2878 /*----------------------------------------------------------------------------
2879   Third step.
2880
2881   Build the bit vectors for the transfer functions.
2882 ----------------------------------------------------------------------------*/
2883
2884
2885 /* Note that this is NOT a general purpose function.  Any mem that has
2886    an alias set registered here expected to be COMPLETELY unaliased:
2887    i.e it's addresses are not and need not be examined.
2888
2889    It is known that all references to this address will have this
2890    alias set and there are NO other references to this address in the
2891    function.
2892
2893    Currently the only place that is known to be clean enough to use
2894    this interface is the code that assigns the spill locations.
2895
2896    All of the mems that have alias_sets registered are subjected to a
2897    very powerful form of dse where function calls, volatile reads and
2898    writes, and reads from random location are not taken into account.
2899
2900    It is also assumed that these locations go dead when the function
2901    returns.  This assumption could be relaxed if there were found to
2902    be places that this assumption was not correct.
2903
2904    The MODE is passed in and saved.  The mode of each load or store to
2905    a mem with ALIAS_SET is checked against MEM.  If the size of that
2906    load or store is different from MODE, processing is halted on this
2907    alias set.  For the vast majority of aliases sets, all of the loads
2908    and stores will use the same mode.  But vectors are treated
2909    differently: the alias set is established for the entire vector,
2910    but reload will insert loads and stores for individual elements and
2911    we do not necessarily have the information to track those separate
2912    elements.  So when we see a mode mismatch, we just bail.  */
2913
2914
2915 void
2916 dse_record_singleton_alias_set (alias_set_type alias_set,
2917                                 enum machine_mode mode)
2918 {
2919   struct clear_alias_mode_holder tmp_holder;
2920   struct clear_alias_mode_holder *entry;
2921   void **slot;
2922
2923   /* If we are not going to run dse, we need to return now or there
2924      will be problems with allocating the bitmaps.  */
2925   if ((!gate_dse()) || !alias_set)
2926     return;
2927
2928   if (!clear_alias_sets)
2929     {
2930       clear_alias_sets = BITMAP_ALLOC (NULL);
2931       disqualified_clear_alias_sets = BITMAP_ALLOC (NULL);
2932       clear_alias_mode_table = htab_create (11, clear_alias_mode_hash,
2933                                             clear_alias_mode_eq, NULL);
2934       clear_alias_mode_pool = create_alloc_pool ("clear_alias_mode_pool",
2935                                                  sizeof (struct clear_alias_mode_holder), 100);
2936     }
2937
2938   bitmap_set_bit (clear_alias_sets, alias_set);
2939
2940   tmp_holder.alias_set = alias_set;
2941
2942   slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, INSERT);
2943   gcc_assert (*slot == NULL);
2944
2945   *slot = entry =
2946     (struct clear_alias_mode_holder *) pool_alloc (clear_alias_mode_pool);
2947   entry->alias_set = alias_set;
2948   entry->mode = mode;
2949 }
2950
2951
2952 /* Remove ALIAS_SET from the sets of stack slots being considered.  */
2953
2954 void
2955 dse_invalidate_singleton_alias_set (alias_set_type alias_set)
2956 {
2957   if ((!gate_dse()) || !alias_set)
2958     return;
2959
2960   bitmap_clear_bit (clear_alias_sets, alias_set);
2961 }
2962
2963
2964 /* Look up the bitmap index for OFFSET in GROUP_INFO.  If it is not
2965    there, return 0.  */
2966
2967 static int
2968 get_bitmap_index (group_info_t group_info, HOST_WIDE_INT offset)
2969 {
2970   if (offset < 0)
2971     {
2972       HOST_WIDE_INT offset_p = -offset;
2973       if (offset_p >= group_info->offset_map_size_n)
2974         return 0;
2975       return group_info->offset_map_n[offset_p];
2976     }
2977   else
2978     {
2979       if (offset >= group_info->offset_map_size_p)
2980         return 0;
2981       return group_info->offset_map_p[offset];
2982     }
2983 }
2984
2985
2986 /* Process the STORE_INFOs into the bitmaps into GEN and KILL.  KILL
2987    may be NULL. */
2988
2989 static void
2990 scan_stores_nospill (store_info_t store_info, bitmap gen, bitmap kill)
2991 {
2992   while (store_info)
2993     {
2994       HOST_WIDE_INT i;
2995       group_info_t group_info
2996         = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
2997       if (group_info->process_globally)
2998         for (i = store_info->begin; i < store_info->end; i++)
2999           {
3000             int index = get_bitmap_index (group_info, i);
3001             if (index != 0)
3002               {
3003                 bitmap_set_bit (gen, index);
3004                 if (kill)
3005                   bitmap_clear_bit (kill, index);
3006               }
3007           }
3008       store_info = store_info->next;
3009     }
3010 }
3011
3012
3013 /* Process the STORE_INFOs into the bitmaps into GEN and KILL.  KILL
3014    may be NULL. */
3015
3016 static void
3017 scan_stores_spill (store_info_t store_info, bitmap gen, bitmap kill)
3018 {
3019   while (store_info)
3020     {
3021       if (store_info->alias_set)
3022         {
3023           int index = get_bitmap_index (clear_alias_group,
3024                                         store_info->alias_set);
3025           if (index != 0)
3026             {
3027               bitmap_set_bit (gen, index);
3028               if (kill)
3029                 bitmap_clear_bit (kill, index);
3030             }
3031         }
3032       store_info = store_info->next;
3033     }
3034 }
3035
3036
3037 /* Process the READ_INFOs into the bitmaps into GEN and KILL.  KILL
3038    may be NULL.  */
3039
3040 static void
3041 scan_reads_nospill (insn_info_t insn_info, bitmap gen, bitmap kill)
3042 {
3043   read_info_t read_info = insn_info->read_rec;
3044   int i;
3045   group_info_t group;
3046
3047   /* If this insn reads the frame, kill all the frame related stores.  */
3048   if (insn_info->frame_read)
3049     {
3050       for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
3051         if (group->process_globally && group->frame_related)
3052           {
3053             if (kill)
3054               bitmap_ior_into (kill, group->group_kill);
3055             bitmap_and_compl_into (gen, group->group_kill);
3056           }
3057     }
3058
3059   while (read_info)
3060     {
3061       for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
3062         {
3063           if (group->process_globally)
3064             {
3065               if (i == read_info->group_id)
3066                 {
3067                   if (read_info->begin > read_info->end)
3068                     {
3069                       /* Begin > end for block mode reads.  */
3070                       if (kill)
3071                         bitmap_ior_into (kill, group->group_kill);
3072                       bitmap_and_compl_into (gen, group->group_kill);
3073                     }
3074                   else
3075                     {
3076                       /* The groups are the same, just process the
3077                          offsets.  */
3078                       HOST_WIDE_INT j;
3079                       for (j = read_info->begin; j < read_info->end; j++)
3080                         {
3081                           int index = get_bitmap_index (group, j);
3082                           if (index != 0)
3083                             {
3084                               if (kill)
3085                                 bitmap_set_bit (kill, index);
3086                               bitmap_clear_bit (gen, index);
3087                             }
3088                         }
3089                     }
3090                 }
3091               else
3092                 {
3093                   /* The groups are different, if the alias sets
3094                      conflict, clear the entire group.  We only need
3095                      to apply this test if the read_info is a cselib
3096                      read.  Anything with a constant base cannot alias
3097                      something else with a different constant
3098                      base.  */
3099                   if ((read_info->group_id < 0)
3100                       && canon_true_dependence (group->base_mem,
3101                                                 QImode,
3102                                                 group->canon_base_addr,
3103                                                 read_info->mem, NULL_RTX,
3104                                                 rtx_varies_p))
3105                     {
3106                       if (kill)
3107                         bitmap_ior_into (kill, group->group_kill);
3108                       bitmap_and_compl_into (gen, group->group_kill);
3109                     }
3110                 }
3111             }
3112         }
3113
3114       read_info = read_info->next;
3115     }
3116 }
3117
3118 /* Process the READ_INFOs into the bitmaps into GEN and KILL.  KILL
3119    may be NULL.  */
3120
3121 static void
3122 scan_reads_spill (read_info_t read_info, bitmap gen, bitmap kill)
3123 {
3124   while (read_info)
3125     {
3126       if (read_info->alias_set)
3127         {
3128           int index = get_bitmap_index (clear_alias_group,
3129                                         read_info->alias_set);
3130           if (index != 0)
3131             {
3132               if (kill)
3133                 bitmap_set_bit (kill, index);
3134               bitmap_clear_bit (gen, index);
3135             }
3136         }
3137
3138       read_info = read_info->next;
3139     }
3140 }
3141
3142
3143 /* Return the insn in BB_INFO before the first wild read or if there
3144    are no wild reads in the block, return the last insn.  */
3145
3146 static insn_info_t
3147 find_insn_before_first_wild_read (bb_info_t bb_info)
3148 {
3149   insn_info_t insn_info = bb_info->last_insn;
3150   insn_info_t last_wild_read = NULL;
3151
3152   while (insn_info)
3153     {
3154       if (insn_info->wild_read)
3155         {
3156           last_wild_read = insn_info->prev_insn;
3157           /* Block starts with wild read.  */
3158           if (!last_wild_read)
3159             return NULL;
3160         }
3161
3162       insn_info = insn_info->prev_insn;
3163     }
3164
3165   if (last_wild_read)
3166     return last_wild_read;
3167   else
3168     return bb_info->last_insn;
3169 }
3170
3171
3172 /* Scan the insns in BB_INFO starting at PTR and going to the top of
3173    the block in order to build the gen and kill sets for the block.
3174    We start at ptr which may be the last insn in the block or may be
3175    the first insn with a wild read.  In the latter case we are able to
3176    skip the rest of the block because it just does not matter:
3177    anything that happens is hidden by the wild read.  */
3178
3179 static void
3180 dse_step3_scan (bool for_spills, basic_block bb)
3181 {
3182   bb_info_t bb_info = bb_table[bb->index];
3183   insn_info_t insn_info;
3184
3185   if (for_spills)
3186     /* There are no wild reads in the spill case.  */
3187     insn_info = bb_info->last_insn;
3188   else
3189     insn_info = find_insn_before_first_wild_read (bb_info);
3190
3191   /* In the spill case or in the no_spill case if there is no wild
3192      read in the block, we will need a kill set.  */
3193   if (insn_info == bb_info->last_insn)
3194     {
3195       if (bb_info->kill)
3196         bitmap_clear (bb_info->kill);
3197       else
3198         bb_info->kill = BITMAP_ALLOC (NULL);
3199     }
3200   else
3201     if (bb_info->kill)
3202       BITMAP_FREE (bb_info->kill);
3203
3204   while (insn_info)
3205     {
3206       /* There may have been code deleted by the dce pass run before
3207          this phase.  */
3208       if (insn_info->insn && INSN_P (insn_info->insn))
3209         {
3210           /* Process the read(s) last.  */
3211           if (for_spills)
3212             {
3213               scan_stores_spill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3214               scan_reads_spill (insn_info->read_rec, bb_info->gen, bb_info->kill);
3215             }
3216           else
3217             {
3218               scan_stores_nospill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3219               scan_reads_nospill (insn_info, bb_info->gen, bb_info->kill);
3220             }
3221         }
3222
3223       insn_info = insn_info->prev_insn;
3224     }
3225 }
3226
3227
3228 /* Set the gen set of the exit block, and also any block with no
3229    successors that does not have a wild read.  */
3230
3231 static void
3232 dse_step3_exit_block_scan (bb_info_t bb_info)
3233 {
3234   /* The gen set is all 0's for the exit block except for the
3235      frame_pointer_group.  */
3236
3237   if (stores_off_frame_dead_at_return)
3238     {
3239       unsigned int i;
3240       group_info_t group;
3241
3242       for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
3243         {
3244           if (group->process_globally && group->frame_related)
3245             bitmap_ior_into (bb_info->gen, group->group_kill);
3246         }
3247     }
3248 }
3249
3250
3251 /* Find all of the blocks that are not backwards reachable from the
3252    exit block or any block with no successors (BB).  These are the
3253    infinite loops or infinite self loops.  These blocks will still
3254    have their bits set in UNREACHABLE_BLOCKS.  */
3255
3256 static void
3257 mark_reachable_blocks (sbitmap unreachable_blocks, basic_block bb)
3258 {
3259   edge e;
3260   edge_iterator ei;
3261
3262   if (TEST_BIT (unreachable_blocks, bb->index))
3263     {
3264       RESET_BIT (unreachable_blocks, bb->index);
3265       FOR_EACH_EDGE (e, ei, bb->preds)
3266         {
3267           mark_reachable_blocks (unreachable_blocks, e->src);
3268         }
3269     }
3270 }
3271
3272 /* Build the transfer functions for the function.  */
3273
3274 static void
3275 dse_step3 (bool for_spills)
3276 {
3277   basic_block bb;
3278   sbitmap unreachable_blocks = sbitmap_alloc (last_basic_block);
3279   sbitmap_iterator sbi;
3280   bitmap all_ones = NULL;
3281   unsigned int i;
3282
3283   sbitmap_ones (unreachable_blocks);
3284
3285   FOR_ALL_BB (bb)
3286     {
3287       bb_info_t bb_info = bb_table[bb->index];
3288       if (bb_info->gen)
3289         bitmap_clear (bb_info->gen);
3290       else
3291         bb_info->gen = BITMAP_ALLOC (NULL);
3292
3293       if (bb->index == ENTRY_BLOCK)
3294         ;
3295       else if (bb->index == EXIT_BLOCK)
3296         dse_step3_exit_block_scan (bb_info);
3297       else
3298         dse_step3_scan (for_spills, bb);
3299       if (EDGE_COUNT (bb->succs) == 0)
3300         mark_reachable_blocks (unreachable_blocks, bb);
3301
3302       /* If this is the second time dataflow is run, delete the old
3303          sets.  */
3304       if (bb_info->in)
3305         BITMAP_FREE (bb_info->in);
3306       if (bb_info->out)
3307         BITMAP_FREE (bb_info->out);
3308     }
3309
3310   /* For any block in an infinite loop, we must initialize the out set
3311      to all ones.  This could be expensive, but almost never occurs in
3312      practice. However, it is common in regression tests.  */
3313   EXECUTE_IF_SET_IN_SBITMAP (unreachable_blocks, 0, i, sbi)
3314     {
3315       if (bitmap_bit_p (all_blocks, i))
3316         {
3317           bb_info_t bb_info = bb_table[i];
3318           if (!all_ones)
3319             {
3320               unsigned int j;
3321               group_info_t group;
3322
3323               all_ones = BITMAP_ALLOC (NULL);
3324               for (j = 0; VEC_iterate (group_info_t, rtx_group_vec, j, group); j++)
3325                 bitmap_ior_into (all_ones, group->group_kill);
3326             }
3327           if (!bb_info->out)
3328             {
3329               bb_info->out = BITMAP_ALLOC (NULL);
3330               bitmap_copy (bb_info->out, all_ones);
3331             }
3332         }
3333     }
3334
3335   if (all_ones)
3336     BITMAP_FREE (all_ones);
3337   sbitmap_free (unreachable_blocks);
3338 }
3339
3340
3341 \f
3342 /*----------------------------------------------------------------------------
3343    Fourth step.
3344
3345    Solve the bitvector equations.
3346 ----------------------------------------------------------------------------*/
3347
3348
3349 /* Confluence function for blocks with no successors.  Create an out
3350    set from the gen set of the exit block.  This block logically has
3351    the exit block as a successor.  */
3352
3353
3354
3355 static void
3356 dse_confluence_0 (basic_block bb)
3357 {
3358   bb_info_t bb_info = bb_table[bb->index];
3359
3360   if (bb->index == EXIT_BLOCK)
3361     return;
3362
3363   if (!bb_info->out)
3364     {
3365       bb_info->out = BITMAP_ALLOC (NULL);
3366       bitmap_copy (bb_info->out, bb_table[EXIT_BLOCK]->gen);
3367     }
3368 }
3369
3370 /* Propagate the information from the in set of the dest of E to the
3371    out set of the src of E.  If the various in or out sets are not
3372    there, that means they are all ones.  */
3373
3374 static void
3375 dse_confluence_n (edge e)
3376 {
3377   bb_info_t src_info = bb_table[e->src->index];
3378   bb_info_t dest_info = bb_table[e->dest->index];
3379
3380   if (dest_info->in)
3381     {
3382       if (src_info->out)
3383         bitmap_and_into (src_info->out, dest_info->in);
3384       else
3385         {
3386           src_info->out = BITMAP_ALLOC (NULL);
3387           bitmap_copy (src_info->out, dest_info->in);
3388         }
3389     }
3390 }
3391
3392
3393 /* Propagate the info from the out to the in set of BB_INDEX's basic
3394    block.  There are three cases:
3395
3396    1) The block has no kill set.  In this case the kill set is all
3397    ones.  It does not matter what the out set of the block is, none of
3398    the info can reach the top.  The only thing that reaches the top is
3399    the gen set and we just copy the set.
3400
3401    2) There is a kill set but no out set and bb has successors.  In
3402    this case we just return. Eventually an out set will be created and
3403    it is better to wait than to create a set of ones.
3404
3405    3) There is both a kill and out set.  We apply the obvious transfer
3406    function.
3407 */
3408
3409 static bool
3410 dse_transfer_function (int bb_index)
3411 {
3412   bb_info_t bb_info = bb_table[bb_index];
3413
3414   if (bb_info->kill)
3415     {
3416       if (bb_info->out)
3417         {
3418           /* Case 3 above.  */
3419           if (bb_info->in)
3420             return bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3421                                          bb_info->out, bb_info->kill);
3422           else
3423             {
3424               bb_info->in = BITMAP_ALLOC (NULL);
3425               bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3426                                     bb_info->out, bb_info->kill);
3427               return true;
3428             }
3429         }
3430       else
3431         /* Case 2 above.  */
3432         return false;
3433     }
3434   else
3435     {
3436       /* Case 1 above.  If there is already an in set, nothing
3437          happens.  */
3438       if (bb_info->in)
3439         return false;
3440       else
3441         {
3442           bb_info->in = BITMAP_ALLOC (NULL);
3443           bitmap_copy (bb_info->in, bb_info->gen);
3444           return true;
3445         }
3446     }
3447 }
3448
3449 /* Solve the dataflow equations.  */
3450
3451 static void
3452 dse_step4 (void)
3453 {
3454   df_simple_dataflow (DF_BACKWARD, NULL, dse_confluence_0,
3455                       dse_confluence_n, dse_transfer_function,
3456                       all_blocks, df_get_postorder (DF_BACKWARD),
3457                       df_get_n_blocks (DF_BACKWARD));
3458   if (dump_file)
3459     {
3460       basic_block bb;
3461
3462       fprintf (dump_file, "\n\n*** Global dataflow info after analysis.\n");
3463       FOR_ALL_BB (bb)
3464         {
3465           bb_info_t bb_info = bb_table[bb->index];
3466
3467           df_print_bb_index (bb, dump_file);
3468           if (bb_info->in)
3469             bitmap_print (dump_file, bb_info->in, "  in:   ", "\n");
3470           else
3471             fprintf (dump_file, "  in:   *MISSING*\n");
3472           if (bb_info->gen)
3473             bitmap_print (dump_file, bb_info->gen, "  gen:  ", "\n");
3474           else
3475             fprintf (dump_file, "  gen:  *MISSING*\n");
3476           if (bb_info->kill)
3477             bitmap_print (dump_file, bb_info->kill, "  kill: ", "\n");
3478           else
3479             fprintf (dump_file, "  kill: *MISSING*\n");
3480           if (bb_info->out)
3481             bitmap_print (dump_file, bb_info->out, "  out:  ", "\n");
3482           else
3483             fprintf (dump_file, "  out:  *MISSING*\n\n");
3484         }
3485     }
3486 }
3487
3488
3489 \f
3490 /*----------------------------------------------------------------------------
3491    Fifth step.
3492
3493    Delete the stores that can only be deleted using the global information.
3494 ----------------------------------------------------------------------------*/
3495
3496
3497 static void
3498 dse_step5_nospill (void)
3499 {
3500   basic_block bb;
3501   FOR_EACH_BB (bb)
3502     {
3503       bb_info_t bb_info = bb_table[bb->index];
3504       insn_info_t insn_info = bb_info->last_insn;
3505       bitmap v = bb_info->out;
3506
3507       while (insn_info)
3508         {
3509           bool deleted = false;
3510           if (dump_file && insn_info->insn)
3511             {
3512               fprintf (dump_file, "starting to process insn %d\n",
3513                        INSN_UID (insn_info->insn));
3514               bitmap_print (dump_file, v, "  v:  ", "\n");
3515             }
3516
3517           /* There may have been code deleted by the dce pass run before
3518              this phase.  */
3519           if (insn_info->insn
3520               && INSN_P (insn_info->insn)
3521               && (!insn_info->cannot_delete)
3522               && (!bitmap_empty_p (v)))
3523             {
3524               store_info_t store_info = insn_info->store_rec;
3525
3526               /* Try to delete the current insn.  */
3527               deleted = true;
3528
3529               /* Skip the clobbers.  */
3530               while (!store_info->is_set)
3531                 store_info = store_info->next;
3532
3533               if (store_info->alias_set)
3534                 deleted = false;
3535               else
3536                 {
3537                   HOST_WIDE_INT i;
3538                   group_info_t group_info
3539                     = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
3540
3541                   for (i = store_info->begin; i < store_info->end; i++)
3542                     {
3543                       int index = get_bitmap_index (group_info, i);
3544
3545                       if (dump_file)
3546                         fprintf (dump_file, "i = %d, index = %d\n", (int)i, index);
3547                       if (index == 0 || !bitmap_bit_p (v, index))
3548                         {
3549                           if (dump_file)
3550                             fprintf (dump_file, "failing at i = %d\n", (int)i);
3551                           deleted = false;
3552                           break;
3553                         }
3554                     }
3555                 }
3556               if (deleted)
3557                 {
3558                   if (dbg_cnt (dse))
3559                     {
3560                       check_for_inc_dec (insn_info->insn);
3561                       delete_insn (insn_info->insn);
3562                       insn_info->insn = NULL;
3563                       globally_deleted++;
3564                     }
3565                 }
3566             }
3567           /* We do want to process the local info if the insn was
3568              deleted.  For instance, if the insn did a wild read, we
3569              no longer need to trash the info.  */
3570           if (insn_info->insn
3571               && INSN_P (insn_info->insn)
3572               && (!deleted))
3573             {
3574               scan_stores_nospill (insn_info->store_rec, v, NULL);
3575               if (insn_info->wild_read)
3576                 {
3577                   if (dump_file)
3578                     fprintf (dump_file, "wild read\n");
3579                   bitmap_clear (v);
3580                 }
3581               else if (insn_info->read_rec)
3582                 {
3583                   if (dump_file)
3584                     fprintf (dump_file, "regular read\n");
3585                   scan_reads_nospill (insn_info, v, NULL);
3586                 }
3587             }
3588
3589           insn_info = insn_info->prev_insn;
3590         }
3591     }
3592 }
3593
3594
3595 static void
3596 dse_step5_spill (void)
3597 {
3598   basic_block bb;
3599   FOR_EACH_BB (bb)
3600     {
3601       bb_info_t bb_info = bb_table[bb->index];
3602       insn_info_t insn_info = bb_info->last_insn;
3603       bitmap v = bb_info->out;
3604
3605       while (insn_info)
3606         {
3607           bool deleted = false;
3608           /* There may have been code deleted by the dce pass run before
3609              this phase.  */
3610           if (insn_info->insn
3611               && INSN_P (insn_info->insn)
3612               && (!insn_info->cannot_delete)
3613               && (!bitmap_empty_p (v)))
3614             {
3615               /* Try to delete the current insn.  */
3616               store_info_t store_info = insn_info->store_rec;
3617               deleted = true;
3618
3619               while (store_info)
3620                 {
3621                   if (store_info->alias_set)
3622                     {
3623                       int index = get_bitmap_index (clear_alias_group,
3624                                                     store_info->alias_set);
3625                       if (index == 0 || !bitmap_bit_p (v, index))
3626                         {
3627                           deleted = false;
3628                           break;
3629                         }
3630                     }
3631                   else
3632                     deleted = false;
3633                   store_info = store_info->next;
3634                 }
3635               if (deleted && dbg_cnt (dse))
3636                 {
3637                   if (dump_file)
3638                     fprintf (dump_file, "Spill deleting insn %d\n",
3639                              INSN_UID (insn_info->insn));
3640                   check_for_inc_dec (insn_info->insn);
3641                   delete_insn (insn_info->insn);
3642                   spill_deleted++;
3643                   insn_info->insn = NULL;
3644                 }
3645             }
3646
3647           if (insn_info->insn
3648               && INSN_P (insn_info->insn)
3649               && (!deleted))
3650             {
3651               scan_stores_spill (insn_info->store_rec, v, NULL);
3652               scan_reads_spill (insn_info->read_rec, v, NULL);
3653             }
3654
3655           insn_info = insn_info->prev_insn;
3656         }
3657     }
3658 }
3659
3660
3661 \f
3662 /*----------------------------------------------------------------------------
3663    Sixth step.
3664
3665    Delete stores made redundant by earlier stores (which store the same
3666    value) that couldn't be eliminated.
3667 ----------------------------------------------------------------------------*/
3668
3669 static void
3670 dse_step6 (void)
3671 {
3672   basic_block bb;
3673
3674   FOR_ALL_BB (bb)
3675     {
3676       bb_info_t bb_info = bb_table[bb->index];
3677       insn_info_t insn_info = bb_info->last_insn;
3678
3679       while (insn_info)
3680         {
3681           /* There may have been code deleted by the dce pass run before
3682              this phase.  */
3683           if (insn_info->insn
3684               && INSN_P (insn_info->insn)
3685               && !insn_info->cannot_delete)
3686             {
3687               store_info_t s_info = insn_info->store_rec;
3688
3689               while (s_info && !s_info->is_set)
3690                 s_info = s_info->next;
3691               if (s_info
3692                   && s_info->redundant_reason
3693                   && s_info->redundant_reason->insn
3694                   && INSN_P (s_info->redundant_reason->insn))
3695                 {
3696                   rtx rinsn = s_info->redundant_reason->insn;
3697                   if (dump_file)
3698                     fprintf (dump_file, "Locally deleting insn %d "
3699                                         "because insn %d stores the "
3700                                         "same value and couldn't be "
3701                                         "eliminated\n",
3702                                         INSN_UID (insn_info->insn),
3703                                         INSN_UID (rinsn));
3704                   delete_dead_store_insn (insn_info);
3705                 }
3706             }
3707           insn_info = insn_info->prev_insn;
3708         }
3709     }
3710 }
3711 \f
3712 /*----------------------------------------------------------------------------
3713    Seventh step.
3714
3715    Destroy everything left standing.
3716 ----------------------------------------------------------------------------*/
3717
3718 static void
3719 dse_step7 (bool global_done)
3720 {
3721   unsigned int i;
3722   group_info_t group;
3723   basic_block bb;
3724
3725   for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
3726     {
3727       free (group->offset_map_n);
3728       free (group->offset_map_p);
3729       BITMAP_FREE (group->store1_n);
3730       BITMAP_FREE (group->store1_p);
3731       BITMAP_FREE (group->store2_n);
3732       BITMAP_FREE (group->store2_p);
3733       BITMAP_FREE (group->group_kill);
3734     }
3735
3736   if (global_done)
3737     FOR_ALL_BB (bb)
3738       {
3739         bb_info_t bb_info = bb_table[bb->index];
3740         BITMAP_FREE (bb_info->gen);
3741         if (bb_info->kill)
3742           BITMAP_FREE (bb_info->kill);
3743         if (bb_info->in)
3744           BITMAP_FREE (bb_info->in);
3745         if (bb_info->out)
3746           BITMAP_FREE (bb_info->out);
3747       }
3748
3749   if (clear_alias_sets)
3750     {
3751       BITMAP_FREE (clear_alias_sets);
3752       BITMAP_FREE (disqualified_clear_alias_sets);
3753       free_alloc_pool (clear_alias_mode_pool);
3754       htab_delete (clear_alias_mode_table);
3755     }
3756
3757   end_alias_analysis ();
3758   free (bb_table);
3759   htab_delete (rtx_group_table);
3760   VEC_free (group_info_t, heap, rtx_group_vec);
3761   BITMAP_FREE (all_blocks);
3762   BITMAP_FREE (scratch);
3763
3764   free_alloc_pool (rtx_store_info_pool);
3765   free_alloc_pool (read_info_pool);
3766   free_alloc_pool (insn_info_pool);
3767   free_alloc_pool (bb_info_pool);
3768   free_alloc_pool (rtx_group_info_pool);
3769   free_alloc_pool (deferred_change_pool);
3770 }
3771
3772
3773 /* -------------------------------------------------------------------------
3774    DSE
3775    ------------------------------------------------------------------------- */
3776
3777 /* Callback for running pass_rtl_dse.  */
3778
3779 static unsigned int
3780 rest_of_handle_dse (void)
3781 {
3782   bool did_global = false;
3783
3784   df_set_flags (DF_DEFER_INSN_RESCAN);
3785
3786   /* Need the notes since we must track live hardregs in the forwards
3787      direction.  */
3788   df_note_add_problem ();
3789   df_analyze ();
3790
3791   dse_step0 ();
3792   dse_step1 ();
3793   dse_step2_init ();
3794   if (dse_step2_nospill ())
3795     {
3796       df_set_flags (DF_LR_RUN_DCE);
3797       df_analyze ();
3798       did_global = true;
3799       if (dump_file)
3800         fprintf (dump_file, "doing global processing\n");
3801       dse_step3 (false);
3802       dse_step4 ();
3803       dse_step5_nospill ();
3804     }
3805
3806   /* For the instance of dse that runs after reload, we make a special
3807      pass to process the spills.  These are special in that they are
3808      totally transparent, i.e, there is no aliasing issues that need
3809      to be considered.  This means that the wild reads that kill
3810      everything else do not apply here.  */
3811   if (clear_alias_sets && dse_step2_spill ())
3812     {
3813       if (!did_global)
3814         {
3815           df_set_flags (DF_LR_RUN_DCE);
3816           df_analyze ();
3817         }
3818       did_global = true;
3819       if (dump_file)
3820         fprintf (dump_file, "doing global spill processing\n");
3821       dse_step3 (true);
3822       dse_step4 ();
3823       dse_step5_spill ();
3824     }
3825
3826   dse_step6 ();
3827   dse_step7 (did_global);
3828
3829   if (dump_file)
3830     fprintf (dump_file, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3831              locally_deleted, globally_deleted, spill_deleted);
3832   return 0;
3833 }
3834
3835 static bool
3836 gate_dse (void)
3837 {
3838   return gate_dse1 () || gate_dse2 ();
3839 }
3840
3841 static bool
3842 gate_dse1 (void)
3843 {
3844   return optimize > 0 && flag_dse
3845     && dbg_cnt (dse1);
3846 }
3847
3848 static bool
3849 gate_dse2 (void)
3850 {
3851   return optimize > 0 && flag_dse
3852     && dbg_cnt (dse2);
3853 }
3854
3855 struct rtl_opt_pass pass_rtl_dse1 =
3856 {
3857  {
3858   RTL_PASS,
3859   "dse1",                               /* name */
3860   gate_dse1,                            /* gate */
3861   rest_of_handle_dse,                   /* execute */
3862   NULL,                                 /* sub */
3863   NULL,                                 /* next */
3864   0,                                    /* static_pass_number */
3865   TV_DSE1,                              /* tv_id */
3866   0,                                    /* properties_required */
3867   0,                                    /* properties_provided */
3868   0,                                    /* properties_destroyed */
3869   0,                                    /* todo_flags_start */
3870   TODO_dump_func |
3871   TODO_df_finish | TODO_verify_rtl_sharing |
3872   TODO_ggc_collect                      /* todo_flags_finish */
3873  }
3874 };
3875
3876 struct rtl_opt_pass pass_rtl_dse2 =
3877 {
3878  {
3879   RTL_PASS,
3880   "dse2",                               /* name */
3881   gate_dse2,                            /* gate */
3882   rest_of_handle_dse,                   /* execute */
3883   NULL,                                 /* sub */
3884   NULL,                                 /* next */
3885   0,                                    /* static_pass_number */
3886   TV_DSE2,                              /* tv_id */
3887   0,                                    /* properties_required */
3888   0,                                    /* properties_provided */
3889   0,                                    /* properties_destroyed */
3890   0,                                    /* todo_flags_start */
3891   TODO_dump_func |
3892   TODO_df_finish | TODO_verify_rtl_sharing |
3893   TODO_ggc_collect                      /* todo_flags_finish */
3894  }
3895 };