gcc/dse.c

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