gcc/dse.c

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