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 bmap;
 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.bmap);
 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, GET_MODE (r1));
 830         emit_insn_before (gen_rtx_SET (VOIDmode, r1,
 831                                        gen_rtx_PLUS (GET_MODE (r1), 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, GET_MODE (r1));
 841         emit_insn_before (gen_rtx_SET (VOIDmode, r1,
 842                                        gen_rtx_PLUS (GET_MODE (r1), 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 (VOIDmode, 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 CONST:
1019     case CONST_INT:
1020     case CONST_DOUBLE:
1021     case CONST_VECTOR:
1022     case SYMBOL_REF:
1023     case LABEL_REF:
1024       return true;
1025
1026     case REG:
1027       /* Note that we have to test for the actual rtx used for the frame
1028          and arg pointers and not just the register number in case we have
1029          eliminated the frame and/or arg pointer and are using it
1030          for pseudos.  */
1031       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
1032           /* The arg pointer varies if it is not a fixed register.  */
1033           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
1034           || x == pic_offset_table_rtx)
1035         return true;
1036       return false;
1037
1038     default:
1039       return false;
1040     }
1041 }
1042
1043 /* Take all reasonable action to put the address of MEM into the form
1044    that we can do analysis on.
1045
1046    The gold standard is to get the address into the form: address +
1047    OFFSET where address is something that rtx_varies_p considers a
1048    constant.  When we can get the address in this form, we can do
1049    global analysis on it.  Note that for constant bases, address is
1050    not actually returned, only the group_id.  The address can be
1051    obtained from that.
1052
1053    If that fails, we try cselib to get a value we can at least use
1054    locally.  If that fails we return false.
1055
1056    The GROUP_ID is set to -1 for cselib bases and the index of the
1057    group for non_varying bases.
1058
1059    FOR_READ is true if this is a mem read and false if not.  */
1060
1061 static bool
1062 canon_address (rtx mem,
1063                alias_set_type *alias_set_out,
1064                int *group_id,
1065                HOST_WIDE_INT *offset,
1066                cselib_val **base)
1067 {
1068   enum machine_mode address_mode
1069     = targetm.addr_space.address_mode (MEM_ADDR_SPACE (mem));
1070   rtx mem_address = XEXP (mem, 0);
1071   rtx expanded_address, address;
1072   int expanded;
1073
1074   /* Make sure that cselib is has initialized all of the operands of
1075      the address before asking it to do the subst.  */
1076
1077   if (clear_alias_sets)
1078     {
1079       /* If this is a spill, do not do any further processing.  */
1080       alias_set_type alias_set = MEM_ALIAS_SET (mem);
1081       if (dump_file)
1082         fprintf (dump_file, "found alias set %d\n", (int) alias_set);
1083       if (bitmap_bit_p (clear_alias_sets, alias_set))
1084         {
1085           struct clear_alias_mode_holder *entry
1086             = clear_alias_set_lookup (alias_set);
1087
1088           /* If the modes do not match, we cannot process this set.  */
1089           if (entry->mode != GET_MODE (mem))
1090             {
1091               if (dump_file)
1092                 fprintf (dump_file,
1093                          "disqualifying alias set %d, (%s) != (%s)\n",
1094                          (int) alias_set, GET_MODE_NAME (entry->mode),
1095                          GET_MODE_NAME (GET_MODE (mem)));
1096
1097               bitmap_set_bit (disqualified_clear_alias_sets, alias_set);
1098               return false;
1099             }
1100
1101           *alias_set_out = alias_set;
1102           *group_id = clear_alias_group->id;
1103           return true;
1104         }
1105     }
1106
1107   *alias_set_out = 0;
1108
1109   cselib_lookup (mem_address, address_mode, 1);
1110
1111   if (dump_file)
1112     {
1113       fprintf (dump_file, "  mem: ");
1114       print_inline_rtx (dump_file, mem_address, 0);
1115       fprintf (dump_file, "\n");
1116     }
1117
1118   /* First see if just canon_rtx (mem_address) is const or frame,
1119      if not, try cselib_expand_value_rtx and call canon_rtx on that.  */
1120   address = NULL_RTX;
1121   for (expanded = 0; expanded < 2; expanded++)
1122     {
1123       if (expanded)
1124         {
1125           /* Use cselib to replace all of the reg references with the full
1126              expression.  This will take care of the case where we have
1127
1128              r_x = base + offset;
1129              val = *r_x;
1130
1131              by making it into
1132
1133              val = *(base + offset);  */
1134
1135           expanded_address = cselib_expand_value_rtx (mem_address,
1136                                                       scratch, 5);
1137
1138           /* If this fails, just go with the address from first
1139              iteration.  */
1140           if (!expanded_address)
1141             break;
1142         }
1143       else
1144         expanded_address = mem_address;
1145
1146       /* Split the address into canonical BASE + OFFSET terms.  */
1147       address = canon_rtx (expanded_address);
1148
1149       *offset = 0;
1150
1151       if (dump_file)
1152         {
1153           if (expanded)
1154             {
1155               fprintf (dump_file, "\n   after cselib_expand address: ");
1156               print_inline_rtx (dump_file, expanded_address, 0);
1157               fprintf (dump_file, "\n");
1158             }
1159
1160           fprintf (dump_file, "\n   after canon_rtx address: ");
1161           print_inline_rtx (dump_file, address, 0);
1162           fprintf (dump_file, "\n");
1163         }
1164
1165       if (GET_CODE (address) == CONST)
1166         address = XEXP (address, 0);
1167
1168       if (GET_CODE (address) == PLUS
1169           && CONST_INT_P (XEXP (address, 1)))
1170         {
1171           *offset = INTVAL (XEXP (address, 1));
1172           address = XEXP (address, 0);
1173         }
1174
1175       if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem))
1176           && const_or_frame_p (address))
1177         {
1178           group_info_t group = get_group_info (address);
1179
1180           if (dump_file)
1181             fprintf (dump_file, "  gid=%d offset=%d \n",
1182                      group->id, (int)*offset);
1183           *base = NULL;
1184           *group_id = group->id;
1185           return true;
1186         }
1187     }
1188
1189   *base = cselib_lookup (address, address_mode, true);
1190   *group_id = -1;
1191
1192   if (*base == NULL)
1193     {
1194       if (dump_file)
1195         fprintf (dump_file, " no cselib val - should be a wild read.\n");
1196       return false;
1197     }
1198   if (dump_file)
1199     fprintf (dump_file, "  varying cselib base=%u:%u offset = %d\n",
1200              (*base)->uid, (*base)->hash, (int)*offset);
1201   return true;
1202 }
1203
1204
1205 /* Clear the rhs field from the active_local_stores array.  */
1206
1207 static void
1208 clear_rhs_from_active_local_stores (void)
1209 {
1210   insn_info_t ptr = active_local_stores;
1211
1212   while (ptr)
1213     {
1214       store_info_t store_info = ptr->store_rec;
1215       /* Skip the clobbers.  */
1216       while (!store_info->is_set)
1217         store_info = store_info->next;
1218
1219       store_info->rhs = NULL;
1220       store_info->const_rhs = NULL;
1221
1222       ptr = ptr->next_local_store;
1223     }
1224 }
1225
1226
1227 /* Mark byte POS bytes from the beginning of store S_INFO as unneeded.  */
1228
1229 static inline void
1230 set_position_unneeded (store_info_t s_info, int pos)
1231 {
1232   if (__builtin_expect (s_info->is_large, false))
1233     {
1234       if (!bitmap_bit_p (s_info->positions_needed.large.bmap, pos))
1235         {
1236           s_info->positions_needed.large.count++;
1237           bitmap_set_bit (s_info->positions_needed.large.bmap, pos);
1238         }
1239     }
1240   else
1241     s_info->positions_needed.small_bitmask
1242       &= ~(((unsigned HOST_WIDE_INT) 1) << pos);
1243 }
1244
1245 /* Mark the whole store S_INFO as unneeded.  */
1246
1247 static inline void
1248 set_all_positions_unneeded (store_info_t s_info)
1249 {
1250   if (__builtin_expect (s_info->is_large, false))
1251     {
1252       int pos, end = s_info->end - s_info->begin;
1253       for (pos = 0; pos < end; pos++)
1254         bitmap_set_bit (s_info->positions_needed.large.bmap, pos);
1255       s_info->positions_needed.large.count = end;
1256     }
1257   else
1258     s_info->positions_needed.small_bitmask = (unsigned HOST_WIDE_INT) 0;
1259 }
1260
1261 /* Return TRUE if any bytes from S_INFO store are needed.  */
1262
1263 static inline bool
1264 any_positions_needed_p (store_info_t s_info)
1265 {
1266   if (__builtin_expect (s_info->is_large, false))
1267     return (s_info->positions_needed.large.count
1268             < s_info->end - s_info->begin);
1269   else
1270     return (s_info->positions_needed.small_bitmask
1271             != (unsigned HOST_WIDE_INT) 0);
1272 }
1273
1274 /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
1275    store are needed.  */
1276
1277 static inline bool
1278 all_positions_needed_p (store_info_t s_info, int start, int width)
1279 {
1280   if (__builtin_expect (s_info->is_large, false))
1281     {
1282       int end = start + width;
1283       while (start < end)
1284         if (bitmap_bit_p (s_info->positions_needed.large.bmap, start++))
1285           return false;
1286       return true;
1287     }
1288   else
1289     {
1290       unsigned HOST_WIDE_INT mask = lowpart_bitmask (width) << start;
1291       return (s_info->positions_needed.small_bitmask & mask) == mask;
1292     }
1293 }
1294
1295
1296 static rtx get_stored_val (store_info_t, enum machine_mode, HOST_WIDE_INT,
1297                            HOST_WIDE_INT, basic_block, bool);
1298
1299
1300 /* BODY is an instruction pattern that belongs to INSN.  Return 1 if
1301    there is a candidate store, after adding it to the appropriate
1302    local store group if so.  */
1303
1304 static int
1305 record_store (rtx body, bb_info_t bb_info)
1306 {
1307   rtx mem, rhs, const_rhs, mem_addr;
1308   HOST_WIDE_INT offset = 0;
1309   HOST_WIDE_INT width = 0;
1310   alias_set_type spill_alias_set;
1311   insn_info_t insn_info = bb_info->last_insn;
1312   store_info_t store_info = NULL;
1313   int group_id;
1314   cselib_val *base = NULL;
1315   insn_info_t ptr, last, redundant_reason;
1316   bool store_is_unused;
1317
1318   if (GET_CODE (body) != SET && GET_CODE (body) != CLOBBER)
1319     return 0;
1320
1321   mem = SET_DEST (body);
1322
1323   /* If this is not used, then this cannot be used to keep the insn
1324      from being deleted.  On the other hand, it does provide something
1325      that can be used to prove that another store is dead.  */
1326   store_is_unused
1327     = (find_reg_note (insn_info->insn, REG_UNUSED, mem) != NULL);
1328
1329   /* Check whether that value is a suitable memory location.  */
1330   if (!MEM_P (mem))
1331     {
1332       /* If the set or clobber is unused, then it does not effect our
1333          ability to get rid of the entire insn.  */
1334       if (!store_is_unused)
1335         insn_info->cannot_delete = true;
1336       return 0;
1337     }
1338
1339   /* At this point we know mem is a mem. */
1340   if (GET_MODE (mem) == BLKmode)
1341     {
1342       if (GET_CODE (XEXP (mem, 0)) == SCRATCH)
1343         {
1344           if (dump_file)
1345             fprintf (dump_file, " adding wild read for (clobber (mem:BLK (scratch))\n");
1346           add_wild_read (bb_info);
1347           insn_info->cannot_delete = true;
1348           return 0;
1349         }
1350       /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
1351          as memset (addr, 0, 36);  */
1352       else if (!MEM_SIZE (mem)
1353                || !CONST_INT_P (MEM_SIZE (mem))
1354                || GET_CODE (body) != SET
1355                || INTVAL (MEM_SIZE (mem)) <= 0
1356                || INTVAL (MEM_SIZE (mem)) > MAX_OFFSET
1357                || !CONST_INT_P (SET_SRC (body)))
1358         {
1359           if (!store_is_unused)
1360             {
1361               /* If the set or clobber is unused, then it does not effect our
1362                  ability to get rid of the entire insn.  */
1363               insn_info->cannot_delete = true;
1364               clear_rhs_from_active_local_stores ();
1365             }
1366           return 0;
1367         }
1368     }
1369
1370   /* We can still process a volatile mem, we just cannot delete it.  */
1371   if (MEM_VOLATILE_P (mem))
1372     insn_info->cannot_delete = true;
1373
1374   if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
1375     {
1376       clear_rhs_from_active_local_stores ();
1377       return 0;
1378     }
1379
1380   if (GET_MODE (mem) == BLKmode)
1381     width = INTVAL (MEM_SIZE (mem));
1382   else
1383     {
1384       width = GET_MODE_SIZE (GET_MODE (mem));
1385       gcc_assert ((unsigned) width <= HOST_BITS_PER_WIDE_INT);
1386     }
1387
1388   if (spill_alias_set)
1389     {
1390       bitmap store1 = clear_alias_group->store1_p;
1391       bitmap store2 = clear_alias_group->store2_p;
1392
1393       gcc_assert (GET_MODE (mem) != BLKmode);
1394
1395       if (bitmap_bit_p (store1, spill_alias_set))
1396         bitmap_set_bit (store2, spill_alias_set);
1397       else
1398         bitmap_set_bit (store1, spill_alias_set);
1399
1400       if (clear_alias_group->offset_map_size_p < spill_alias_set)
1401         clear_alias_group->offset_map_size_p = spill_alias_set;
1402
1403       store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1404
1405       if (dump_file)
1406         fprintf (dump_file, " processing spill store %d(%s)\n",
1407                  (int) spill_alias_set, GET_MODE_NAME (GET_MODE (mem)));
1408     }
1409   else if (group_id >= 0)
1410     {
1411       /* In the restrictive case where the base is a constant or the
1412          frame pointer we can do global analysis.  */
1413
1414       group_info_t group
1415         = VEC_index (group_info_t, rtx_group_vec, group_id);
1416
1417       store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1418       set_usage_bits (group, offset, width);
1419
1420       if (dump_file)
1421         fprintf (dump_file, " processing const base store gid=%d[%d..%d)\n",
1422                  group_id, (int)offset, (int)(offset+width));
1423     }
1424   else
1425     {
1426       rtx base_term = find_base_term (XEXP (mem, 0));
1427       if (!base_term
1428           || (GET_CODE (base_term) == ADDRESS
1429               && GET_MODE (base_term) == Pmode
1430               && XEXP (base_term, 0) == stack_pointer_rtx))
1431         insn_info->stack_pointer_based = true;
1432       insn_info->contains_cselib_groups = true;
1433
1434       store_info = (store_info_t) pool_alloc (cse_store_info_pool);
1435       group_id = -1;
1436
1437       if (dump_file)
1438         fprintf (dump_file, " processing cselib store [%d..%d)\n",
1439                  (int)offset, (int)(offset+width));
1440     }
1441
1442   const_rhs = rhs = NULL_RTX;
1443   if (GET_CODE (body) == SET
1444       /* No place to keep the value after ra.  */
1445       && !reload_completed
1446       && (REG_P (SET_SRC (body))
1447           || GET_CODE (SET_SRC (body)) == SUBREG
1448           || CONSTANT_P (SET_SRC (body)))
1449       && !MEM_VOLATILE_P (mem)
1450       /* Sometimes the store and reload is used for truncation and
1451          rounding.  */
1452       && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
1453     {
1454       rhs = SET_SRC (body);
1455       if (CONSTANT_P (rhs))
1456         const_rhs = rhs;
1457       else if (body == PATTERN (insn_info->insn))
1458         {
1459           rtx tem = find_reg_note (insn_info->insn, REG_EQUAL, NULL_RTX);
1460           if (tem && CONSTANT_P (XEXP (tem, 0)))
1461             const_rhs = XEXP (tem, 0);
1462         }
1463       if (const_rhs == NULL_RTX && REG_P (rhs))
1464         {
1465           rtx tem = cselib_expand_value_rtx (rhs, scratch, 5);
1466
1467           if (tem && CONSTANT_P (tem))
1468             const_rhs = tem;
1469         }
1470     }
1471
1472   /* Check to see if this stores causes some other stores to be
1473      dead.  */
1474   ptr = active_local_stores;
1475   last = NULL;
1476   redundant_reason = NULL;
1477   mem = canon_rtx (mem);
1478   /* For alias_set != 0 canon_true_dependence should be never called.  */
1479   if (spill_alias_set)
1480     mem_addr = NULL_RTX;
1481   else
1482     {
1483       if (group_id < 0)
1484         mem_addr = base->val_rtx;
1485       else
1486         {
1487           group_info_t group
1488             = VEC_index (group_info_t, rtx_group_vec, group_id);
1489           mem_addr = group->canon_base_addr;
1490         }
1491       if (offset)
1492         mem_addr = plus_constant (mem_addr, offset);
1493     }
1494
1495   while (ptr)
1496     {
1497       insn_info_t next = ptr->next_local_store;
1498       store_info_t s_info = ptr->store_rec;
1499       bool del = true;
1500
1501       /* Skip the clobbers. We delete the active insn if this insn
1502          shadows the set.  To have been put on the active list, it
1503          has exactly on set. */
1504       while (!s_info->is_set)
1505         s_info = s_info->next;
1506
1507       if (s_info->alias_set != spill_alias_set)
1508         del = false;
1509       else if (s_info->alias_set)
1510         {
1511           struct clear_alias_mode_holder *entry
1512             = clear_alias_set_lookup (s_info->alias_set);
1513           /* Generally, spills cannot be processed if and of the
1514              references to the slot have a different mode.  But if
1515              we are in the same block and mode is exactly the same
1516              between this store and one before in the same block,
1517              we can still delete it.  */
1518           if ((GET_MODE (mem) == GET_MODE (s_info->mem))
1519               && (GET_MODE (mem) == entry->mode))
1520             {
1521               del = true;
1522               set_all_positions_unneeded (s_info);
1523             }
1524           if (dump_file)
1525             fprintf (dump_file, "    trying spill store in insn=%d alias_set=%d\n",
1526                      INSN_UID (ptr->insn), (int) s_info->alias_set);
1527         }
1528       else if ((s_info->group_id == group_id)
1529                && (s_info->cse_base == base))
1530         {
1531           HOST_WIDE_INT i;
1532           if (dump_file)
1533             fprintf (dump_file, "    trying store in insn=%d gid=%d[%d..%d)\n",
1534                      INSN_UID (ptr->insn), s_info->group_id,
1535                      (int)s_info->begin, (int)s_info->end);
1536
1537           /* Even if PTR won't be eliminated as unneeded, if both
1538              PTR and this insn store the same constant value, we might
1539              eliminate this insn instead.  */
1540           if (s_info->const_rhs
1541               && const_rhs
1542               && offset >= s_info->begin
1543               && offset + width <= s_info->end
1544               && all_positions_needed_p (s_info, offset - s_info->begin,
1545                                          width))
1546             {
1547               if (GET_MODE (mem) == BLKmode)
1548                 {
1549                   if (GET_MODE (s_info->mem) == BLKmode
1550                       && s_info->const_rhs == const_rhs)
1551                     redundant_reason = ptr;
1552                 }
1553               else if (s_info->const_rhs == const0_rtx
1554                        && const_rhs == const0_rtx)
1555                 redundant_reason = ptr;
1556               else
1557                 {
1558                   rtx val;
1559                   start_sequence ();
1560                   val = get_stored_val (s_info, GET_MODE (mem),
1561                                         offset, offset + width,
1562                                         BLOCK_FOR_INSN (insn_info->insn),
1563                                         true);
1564                   if (get_insns () != NULL)
1565                     val = NULL_RTX;
1566                   end_sequence ();
1567                   if (val && rtx_equal_p (val, const_rhs))
1568                     redundant_reason = ptr;
1569                 }
1570             }
1571
1572           for (i = MAX (offset, s_info->begin);
1573                i < offset + width && i < s_info->end;
1574                i++)
1575             set_position_unneeded (s_info, i - s_info->begin);
1576         }
1577       else if (s_info->rhs)
1578         /* Need to see if it is possible for this store to overwrite
1579            the value of store_info.  If it is, set the rhs to NULL to
1580            keep it from being used to remove a load.  */
1581         {
1582           if (canon_true_dependence (s_info->mem,
1583                                      GET_MODE (s_info->mem),
1584                                      s_info->mem_addr,
1585                                      mem, mem_addr, rtx_varies_p))
1586             {
1587               s_info->rhs = NULL;
1588               s_info->const_rhs = NULL;
1589             }
1590         }
1591
1592       /* An insn can be deleted if every position of every one of
1593          its s_infos is zero.  */
1594       if (any_positions_needed_p (s_info)
1595           || ptr->cannot_delete)
1596         del = false;
1597
1598       if (del)
1599         {
1600           insn_info_t insn_to_delete = ptr;
1601
1602           if (last)
1603             last->next_local_store = ptr->next_local_store;
1604           else
1605             active_local_stores = ptr->next_local_store;
1606
1607           delete_dead_store_insn (insn_to_delete);
1608         }
1609       else
1610         last = ptr;
1611
1612       ptr = next;
1613     }
1614
1615   /* Finish filling in the store_info.  */
1616   store_info->next = insn_info->store_rec;
1617   insn_info->store_rec = store_info;
1618   store_info->mem = mem;
1619   store_info->alias_set = spill_alias_set;
1620   store_info->mem_addr = mem_addr;
1621   store_info->cse_base = base;
1622   if (width > HOST_BITS_PER_WIDE_INT)
1623     {
1624       store_info->is_large = true;
1625       store_info->positions_needed.large.count = 0;
1626       store_info->positions_needed.large.bmap = BITMAP_ALLOC (NULL);
1627     }
1628   else
1629     {
1630       store_info->is_large = false;
1631       store_info->positions_needed.small_bitmask = lowpart_bitmask (width);
1632     }
1633   store_info->group_id = group_id;
1634   store_info->begin = offset;
1635   store_info->end = offset + width;
1636   store_info->is_set = GET_CODE (body) == SET;
1637   store_info->rhs = rhs;
1638   store_info->const_rhs = const_rhs;
1639   store_info->redundant_reason = redundant_reason;
1640
1641   /* If this is a clobber, we return 0.  We will only be able to
1642      delete this insn if there is only one store USED store, but we
1643      can use the clobber to delete other stores earlier.  */
1644   return store_info->is_set ? 1 : 0;
1645 }
1646
1647
1648 static void
1649 dump_insn_info (const char * start, insn_info_t insn_info)
1650 {
1651   fprintf (dump_file, "%s insn=%d %s\n", start,
1652            INSN_UID (insn_info->insn),
1653            insn_info->store_rec ? "has store" : "naked");
1654 }
1655
1656
1657 /* If the modes are different and the value's source and target do not
1658    line up, we need to extract the value from lower part of the rhs of
1659    the store, shift it, and then put it into a form that can be shoved
1660    into the read_insn.  This function generates a right SHIFT of a
1661    value that is at least ACCESS_SIZE bytes wide of READ_MODE.  The
1662    shift sequence is returned or NULL if we failed to find a
1663    shift.  */
1664
1665 static rtx
1666 find_shift_sequence (int access_size,
1667                      store_info_t store_info,
1668                      enum machine_mode read_mode,
1669                      int shift, bool speed, bool require_cst)
1670 {
1671   enum machine_mode store_mode = GET_MODE (store_info->mem);
1672   enum machine_mode new_mode;
1673   rtx read_reg = NULL;
1674
1675   /* Some machines like the x86 have shift insns for each size of
1676      operand.  Other machines like the ppc or the ia-64 may only have
1677      shift insns that shift values within 32 or 64 bit registers.
1678      This loop tries to find the smallest shift insn that will right
1679      justify the value we want to read but is available in one insn on
1680      the machine.  */
1681
1682   for (new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
1683                                           MODE_INT);
1684        GET_MODE_BITSIZE (new_mode) <= BITS_PER_WORD;
1685        new_mode = GET_MODE_WIDER_MODE (new_mode))
1686     {
1687       rtx target, new_reg, shift_seq, insn, new_lhs;
1688       int cost;
1689
1690       /* If a constant was stored into memory, try to simplify it here,
1691          otherwise the cost of the shift might preclude this optimization
1692          e.g. at -Os, even when no actual shift will be needed.  */
1693       if (store_info->const_rhs)
1694         {
1695           unsigned int byte = subreg_lowpart_offset (new_mode, store_mode);
1696           rtx ret = simplify_subreg (new_mode, store_info->const_rhs,
1697                                      store_mode, byte);
1698           if (ret && CONSTANT_P (ret))
1699             {
1700               ret = simplify_const_binary_operation (LSHIFTRT, new_mode,
1701                                                      ret, GEN_INT (shift));
1702               if (ret && CONSTANT_P (ret))
1703                 {
1704                   byte = subreg_lowpart_offset (read_mode, new_mode);
1705                   ret = simplify_subreg (read_mode, ret, new_mode, byte);
1706                   if (ret && CONSTANT_P (ret)
1707                       && rtx_cost (ret, SET, speed) <= COSTS_N_INSNS (1))
1708                     return ret;
1709                 }
1710             }
1711         }
1712
1713       if (require_cst)
1714         return NULL_RTX;
1715
1716       /* Try a wider mode if truncating the store mode to NEW_MODE
1717          requires a real instruction.  */
1718       if (GET_MODE_BITSIZE (new_mode) < GET_MODE_BITSIZE (store_mode)
1719           && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (new_mode),
1720                                      GET_MODE_BITSIZE (store_mode)))
1721         continue;
1722
1723       /* Also try a wider mode if the necessary punning is either not
1724          desirable or not possible.  */
1725       if (!CONSTANT_P (store_info->rhs)
1726           && !MODES_TIEABLE_P (new_mode, store_mode))
1727         continue;
1728
1729       new_reg = gen_reg_rtx (new_mode);
1730
1731       start_sequence ();
1732
1733       /* In theory we could also check for an ashr.  Ian Taylor knows
1734          of one dsp where the cost of these two was not the same.  But
1735          this really is a rare case anyway.  */
1736       target = expand_binop (new_mode, lshr_optab, new_reg,
1737                              GEN_INT (shift), new_reg, 1, OPTAB_DIRECT);
1738
1739       shift_seq = get_insns ();
1740       end_sequence ();
1741
1742       if (target != new_reg || shift_seq == NULL)
1743         continue;
1744
1745       cost = 0;
1746       for (insn = shift_seq; insn != NULL_RTX; insn = NEXT_INSN (insn))
1747         if (INSN_P (insn))
1748           cost += insn_rtx_cost (PATTERN (insn), speed);
1749
1750       /* The computation up to here is essentially independent
1751          of the arguments and could be precomputed.  It may
1752          not be worth doing so.  We could precompute if
1753          worthwhile or at least cache the results.  The result
1754          technically depends on both SHIFT and ACCESS_SIZE,
1755          but in practice the answer will depend only on ACCESS_SIZE.  */
1756
1757       if (cost > COSTS_N_INSNS (1))
1758         continue;
1759
1760       new_lhs = extract_low_bits (new_mode, store_mode,
1761                                   copy_rtx (store_info->rhs));
1762       if (new_lhs == NULL_RTX)
1763         continue;
1764
1765       /* We found an acceptable shift.  Generate a move to
1766          take the value from the store and put it into the
1767          shift pseudo, then shift it, then generate another
1768          move to put in into the target of the read.  */
1769       emit_move_insn (new_reg, new_lhs);
1770       emit_insn (shift_seq);
1771       read_reg = extract_low_bits (read_mode, new_mode, new_reg);
1772       break;
1773     }
1774
1775   return read_reg;
1776 }
1777
1778
1779 /* Call back for note_stores to find the hard regs set or clobbered by
1780    insn.  Data is a bitmap of the hardregs set so far.  */
1781
1782 static void
1783 look_for_hardregs (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
1784 {
1785   bitmap regs_set = (bitmap) data;
1786
1787   if (REG_P (x)
1788       && REGNO (x) < FIRST_PSEUDO_REGISTER)
1789     {
1790       int regno = REGNO (x);
1791       int n = hard_regno_nregs[regno][GET_MODE (x)];
1792       while (--n >= 0)
1793         bitmap_set_bit (regs_set, regno + n);
1794     }
1795 }
1796
1797 /* Helper function for replace_read and record_store.
1798    Attempt to return a value stored in STORE_INFO, from READ_BEGIN
1799    to one before READ_END bytes read in READ_MODE.  Return NULL
1800    if not successful.  If REQUIRE_CST is true, return always constant.  */
1801
1802 static rtx
1803 get_stored_val (store_info_t store_info, enum machine_mode read_mode,
1804                 HOST_WIDE_INT read_begin, HOST_WIDE_INT read_end,
1805                 basic_block bb, bool require_cst)
1806 {
1807   enum machine_mode store_mode = GET_MODE (store_info->mem);
1808   int shift;
1809   int access_size; /* In bytes.  */
1810   rtx read_reg;
1811
1812   /* To get here the read is within the boundaries of the write so
1813      shift will never be negative.  Start out with the shift being in
1814      bytes.  */
1815   if (store_mode == BLKmode)
1816     shift = 0;
1817   else if (BYTES_BIG_ENDIAN)
1818     shift = store_info->end - read_end;
1819   else
1820     shift = read_begin - store_info->begin;
1821
1822   access_size = shift + GET_MODE_SIZE (read_mode);
1823
1824   /* From now on it is bits.  */
1825   shift *= BITS_PER_UNIT;
1826
1827   if (shift)
1828     read_reg = find_shift_sequence (access_size, store_info, read_mode, shift,
1829                                     optimize_bb_for_speed_p (bb),
1830                                     require_cst);
1831   else if (store_mode == BLKmode)
1832     {
1833       /* The store is a memset (addr, const_val, const_size).  */
1834       gcc_assert (CONST_INT_P (store_info->rhs));
1835       store_mode = int_mode_for_mode (read_mode);
1836       if (store_mode == BLKmode)
1837         read_reg = NULL_RTX;
1838       else if (store_info->rhs == const0_rtx)
1839         read_reg = extract_low_bits (read_mode, store_mode, const0_rtx);
1840       else if (GET_MODE_BITSIZE (store_mode) > HOST_BITS_PER_WIDE_INT
1841                || BITS_PER_UNIT >= HOST_BITS_PER_WIDE_INT)
1842         read_reg = NULL_RTX;
1843       else
1844         {
1845           unsigned HOST_WIDE_INT c
1846             = INTVAL (store_info->rhs)
1847               & (((HOST_WIDE_INT) 1 << BITS_PER_UNIT) - 1);
1848           int shift = BITS_PER_UNIT;
1849           while (shift < HOST_BITS_PER_WIDE_INT)
1850             {
1851               c |= (c << shift);
1852               shift <<= 1;
1853             }
1854           read_reg = GEN_INT (trunc_int_for_mode (c, store_mode));
1855           read_reg = extract_low_bits (read_mode, store_mode, read_reg);
1856         }
1857     }
1858   else if (store_info->const_rhs
1859            && (require_cst
1860                || GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode)))
1861     read_reg = extract_low_bits (read_mode, store_mode,
1862                                  copy_rtx (store_info->const_rhs));
1863   else
1864     read_reg = extract_low_bits (read_mode, store_mode,
1865                                  copy_rtx (store_info->rhs));
1866   if (require_cst && read_reg && !CONSTANT_P (read_reg))
1867     read_reg = NULL_RTX;
1868   return read_reg;
1869 }
1870
1871 /* Take a sequence of:
1872      A <- r1
1873      ...
1874      ... <- A
1875
1876    and change it into
1877    r2 <- r1
1878    A <- r1
1879    ...
1880    ... <- r2
1881
1882    or
1883
1884    r3 <- extract (r1)
1885    r3 <- r3 >> shift
1886    r2 <- extract (r3)
1887    ... <- r2
1888
1889    or
1890
1891    r2 <- extract (r1)
1892    ... <- r2
1893
1894    Depending on the alignment and the mode of the store and
1895    subsequent load.
1896
1897
1898    The STORE_INFO and STORE_INSN are for the store and READ_INFO
1899    and READ_INSN are for the read.  Return true if the replacement
1900    went ok.  */
1901
1902 static bool
1903 replace_read (store_info_t store_info, insn_info_t store_insn,
1904               read_info_t read_info, insn_info_t read_insn, rtx *loc,
1905               bitmap regs_live)
1906 {
1907   enum machine_mode store_mode = GET_MODE (store_info->mem);
1908   enum machine_mode read_mode = GET_MODE (read_info->mem);
1909   rtx insns, this_insn, read_reg;
1910   basic_block bb;
1911
1912   if (!dbg_cnt (dse))
1913     return false;
1914
1915   /* Create a sequence of instructions to set up the read register.
1916      This sequence goes immediately before the store and its result
1917      is read by the load.
1918
1919      We need to keep this in perspective.  We are replacing a read
1920      with a sequence of insns, but the read will almost certainly be
1921      in cache, so it is not going to be an expensive one.  Thus, we
1922      are not willing to do a multi insn shift or worse a subroutine
1923      call to get rid of the read.  */
1924   if (dump_file)
1925     fprintf (dump_file, "trying to replace %smode load in insn %d"
1926              " from %smode store in insn %d\n",
1927              GET_MODE_NAME (read_mode), INSN_UID (read_insn->insn),
1928              GET_MODE_NAME (store_mode), INSN_UID (store_insn->insn));
1929   start_sequence ();
1930   bb = BLOCK_FOR_INSN (read_insn->insn);
1931   read_reg = get_stored_val (store_info,
1932                              read_mode, read_info->begin, read_info->end,
1933                              bb, false);
1934   if (read_reg == NULL_RTX)
1935     {
1936       end_sequence ();
1937       if (dump_file)
1938         fprintf (dump_file, " -- could not extract bits of stored value\n");
1939       return false;
1940     }
1941   /* Force the value into a new register so that it won't be clobbered
1942      between the store and the load.  */
1943   read_reg = copy_to_mode_reg (read_mode, read_reg);
1944   insns = get_insns ();
1945   end_sequence ();
1946
1947   if (insns != NULL_RTX)
1948     {
1949       /* Now we have to scan the set of new instructions to see if the
1950          sequence contains and sets of hardregs that happened to be
1951          live at this point.  For instance, this can happen if one of
1952          the insns sets the CC and the CC happened to be live at that
1953          point.  This does occasionally happen, see PR 37922.  */
1954       bitmap regs_set = BITMAP_ALLOC (NULL);
1955
1956       for (this_insn = insns; this_insn != NULL_RTX; this_insn = NEXT_INSN (this_insn))
1957         note_stores (PATTERN (this_insn), look_for_hardregs, regs_set);
1958
1959       bitmap_and_into (regs_set, regs_live);
1960       if (!bitmap_empty_p (regs_set))
1961         {
1962           if (dump_file)
1963             {
1964               fprintf (dump_file,
1965                        "abandoning replacement because sequence clobbers live hardregs:");
1966               df_print_regset (dump_file, regs_set);
1967             }
1968
1969           BITMAP_FREE (regs_set);
1970           return false;
1971         }
1972       BITMAP_FREE (regs_set);
1973     }
1974
1975   if (validate_change (read_insn->insn, loc, read_reg, 0))
1976     {
1977       deferred_change_t deferred_change =
1978         (deferred_change_t) pool_alloc (deferred_change_pool);
1979
1980       /* Insert this right before the store insn where it will be safe
1981          from later insns that might change it before the read.  */
1982       emit_insn_before (insns, store_insn->insn);
1983
1984       /* And now for the kludge part: cselib croaks if you just
1985          return at this point.  There are two reasons for this:
1986
1987          1) Cselib has an idea of how many pseudos there are and
1988          that does not include the new ones we just added.
1989
1990          2) Cselib does not know about the move insn we added
1991          above the store_info, and there is no way to tell it
1992          about it, because it has "moved on".
1993
1994          Problem (1) is fixable with a certain amount of engineering.
1995          Problem (2) is requires starting the bb from scratch.  This
1996          could be expensive.
1997
1998          So we are just going to have to lie.  The move/extraction
1999          insns are not really an issue, cselib did not see them.  But
2000          the use of the new pseudo read_insn is a real problem because
2001          cselib has not scanned this insn.  The way that we solve this
2002          problem is that we are just going to put the mem back for now
2003          and when we are finished with the block, we undo this.  We
2004          keep a table of mems to get rid of.  At the end of the basic
2005          block we can put them back.  */
2006
2007       *loc = read_info->mem;
2008       deferred_change->next = deferred_change_list;
2009       deferred_change_list = deferred_change;
2010       deferred_change->loc = loc;
2011       deferred_change->reg = read_reg;
2012
2013       /* Get rid of the read_info, from the point of view of the
2014          rest of dse, play like this read never happened.  */
2015       read_insn->read_rec = read_info->next;
2016       pool_free (read_info_pool, read_info);
2017       if (dump_file)
2018         {
2019           fprintf (dump_file, " -- replaced the loaded MEM with ");
2020           print_simple_rtl (dump_file, read_reg);
2021           fprintf (dump_file, "\n");
2022         }
2023       return true;
2024     }
2025   else
2026     {
2027       if (dump_file)
2028         {
2029           fprintf (dump_file, " -- replacing the loaded MEM with ");
2030           print_simple_rtl (dump_file, read_reg);
2031           fprintf (dump_file, " led to an invalid instruction\n");
2032         }
2033       return false;
2034     }
2035 }
2036
2037 /* A for_each_rtx callback in which DATA is the bb_info.  Check to see
2038    if LOC is a mem and if it is look at the address and kill any
2039    appropriate stores that may be active.  */
2040
2041 static int
2042 check_mem_read_rtx (rtx *loc, void *data)
2043 {
2044   rtx mem = *loc, mem_addr;
2045   bb_info_t bb_info;
2046   insn_info_t insn_info;
2047   HOST_WIDE_INT offset = 0;
2048   HOST_WIDE_INT width = 0;
2049   alias_set_type spill_alias_set = 0;
2050   cselib_val *base = NULL;
2051   int group_id;
2052   read_info_t read_info;
2053
2054   if (!mem || !MEM_P (mem))
2055     return 0;
2056
2057   bb_info = (bb_info_t) data;
2058   insn_info = bb_info->last_insn;
2059
2060   if ((MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2061       || (MEM_VOLATILE_P (mem)))
2062     {
2063       if (dump_file)
2064         fprintf (dump_file, " adding wild read, volatile or barrier.\n");
2065       add_wild_read (bb_info);
2066       insn_info->cannot_delete = true;
2067       return 0;
2068     }
2069
2070   /* If it is reading readonly mem, then there can be no conflict with
2071      another write. */
2072   if (MEM_READONLY_P (mem))
2073     return 0;
2074
2075   if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
2076     {
2077       if (dump_file)
2078         fprintf (dump_file, " adding wild read, canon_address failure.\n");
2079       add_wild_read (bb_info);
2080       return 0;
2081     }
2082
2083   if (GET_MODE (mem) == BLKmode)
2084     width = -1;
2085   else
2086     width = GET_MODE_SIZE (GET_MODE (mem));
2087
2088   read_info = (read_info_t) pool_alloc (read_info_pool);
2089   read_info->group_id = group_id;
2090   read_info->mem = mem;
2091   read_info->alias_set = spill_alias_set;
2092   read_info->begin = offset;
2093   read_info->end = offset + width;
2094   read_info->next = insn_info->read_rec;
2095   insn_info->read_rec = read_info;
2096   /* For alias_set != 0 canon_true_dependence should be never called.  */
2097   if (spill_alias_set)
2098     mem_addr = NULL_RTX;
2099   else
2100     {
2101       if (group_id < 0)
2102         mem_addr = base->val_rtx;
2103       else
2104         {
2105           group_info_t group
2106             = VEC_index (group_info_t, rtx_group_vec, group_id);
2107           mem_addr = group->canon_base_addr;
2108         }
2109       if (offset)
2110         mem_addr = plus_constant (mem_addr, offset);
2111     }
2112
2113   /* We ignore the clobbers in store_info.  The is mildly aggressive,
2114      but there really should not be a clobber followed by a read.  */
2115
2116   if (spill_alias_set)
2117     {
2118       insn_info_t i_ptr = active_local_stores;
2119       insn_info_t last = NULL;
2120
2121       if (dump_file)
2122         fprintf (dump_file, " processing spill load %d\n",
2123                  (int) spill_alias_set);
2124
2125       while (i_ptr)
2126         {
2127           store_info_t store_info = i_ptr->store_rec;
2128
2129           /* Skip the clobbers.  */
2130           while (!store_info->is_set)
2131             store_info = store_info->next;
2132
2133           if (store_info->alias_set == spill_alias_set)
2134             {
2135               if (dump_file)
2136                 dump_insn_info ("removing from active", i_ptr);
2137
2138               if (last)
2139                 last->next_local_store = i_ptr->next_local_store;
2140               else
2141                 active_local_stores = i_ptr->next_local_store;
2142             }
2143           else
2144             last = i_ptr;
2145           i_ptr = i_ptr->next_local_store;
2146         }
2147     }
2148   else if (group_id >= 0)
2149     {
2150       /* This is the restricted case where the base is a constant or
2151          the frame pointer and offset is a constant.  */
2152       insn_info_t i_ptr = active_local_stores;
2153       insn_info_t last = NULL;
2154
2155       if (dump_file)
2156         {
2157           if (width == -1)
2158             fprintf (dump_file, " processing const load gid=%d[BLK]\n",
2159                      group_id);
2160           else
2161             fprintf (dump_file, " processing const load gid=%d[%d..%d)\n",
2162                      group_id, (int)offset, (int)(offset+width));
2163         }
2164
2165       while (i_ptr)
2166         {
2167           bool remove = false;
2168           store_info_t store_info = i_ptr->store_rec;
2169
2170           /* Skip the clobbers.  */
2171           while (!store_info->is_set)
2172             store_info = store_info->next;
2173
2174           /* There are three cases here.  */
2175           if (store_info->group_id < 0)
2176             /* We have a cselib store followed by a read from a
2177                const base. */
2178             remove
2179               = canon_true_dependence (store_info->mem,
2180                                        GET_MODE (store_info->mem),
2181                                        store_info->mem_addr,
2182                                        mem, mem_addr, rtx_varies_p);
2183
2184           else if (group_id == store_info->group_id)
2185             {
2186               /* This is a block mode load.  We may get lucky and
2187                  canon_true_dependence may save the day.  */
2188               if (width == -1)
2189                 remove
2190                   = canon_true_dependence (store_info->mem,
2191                                            GET_MODE (store_info->mem),
2192                                            store_info->mem_addr,
2193                                            mem, mem_addr, rtx_varies_p);
2194
2195               /* If this read is just reading back something that we just
2196                  stored, rewrite the read.  */
2197               else
2198                 {
2199                   if (store_info->rhs
2200                       && offset >= store_info->begin
2201                       && offset + width <= store_info->end
2202                       && all_positions_needed_p (store_info,
2203                                                  offset - store_info->begin,
2204                                                  width)
2205                       && replace_read (store_info, i_ptr, read_info,
2206                                        insn_info, loc, bb_info->regs_live))
2207                     return 0;
2208
2209                   /* The bases are the same, just see if the offsets
2210                      overlap.  */
2211                   if ((offset < store_info->end)
2212                       && (offset + width > store_info->begin))
2213                     remove = true;
2214                 }
2215             }
2216
2217           /* else
2218              The else case that is missing here is that the
2219              bases are constant but different.  There is nothing
2220              to do here because there is no overlap.  */
2221
2222           if (remove)
2223             {
2224               if (dump_file)
2225                 dump_insn_info ("removing from active", i_ptr);
2226
2227               if (last)
2228                 last->next_local_store = i_ptr->next_local_store;
2229               else
2230                 active_local_stores = i_ptr->next_local_store;
2231             }
2232           else
2233             last = i_ptr;
2234           i_ptr = i_ptr->next_local_store;
2235         }
2236     }
2237   else
2238     {
2239       insn_info_t i_ptr = active_local_stores;
2240       insn_info_t last = NULL;
2241       if (dump_file)
2242         {
2243           fprintf (dump_file, " processing cselib load mem:");
2244           print_inline_rtx (dump_file, mem, 0);
2245           fprintf (dump_file, "\n");
2246         }
2247
2248       while (i_ptr)
2249         {
2250           bool remove = false;
2251           store_info_t store_info = i_ptr->store_rec;
2252
2253           if (dump_file)
2254             fprintf (dump_file, " processing cselib load against insn %d\n",
2255                      INSN_UID (i_ptr->insn));
2256
2257           /* Skip the clobbers.  */
2258           while (!store_info->is_set)
2259             store_info = store_info->next;
2260
2261           /* If this read is just reading back something that we just
2262              stored, rewrite the read.  */
2263           if (store_info->rhs
2264               && store_info->group_id == -1
2265               && store_info->cse_base == base
2266               && width != -1
2267               && offset >= store_info->begin
2268               && offset + width <= store_info->end
2269               && all_positions_needed_p (store_info,
2270                                          offset - store_info->begin, width)
2271               && replace_read (store_info, i_ptr,  read_info, insn_info, loc,
2272                                bb_info->regs_live))
2273             return 0;
2274
2275           if (!store_info->alias_set)
2276             remove = canon_true_dependence (store_info->mem,
2277                                             GET_MODE (store_info->mem),
2278                                             store_info->mem_addr,
2279                                             mem, mem_addr, rtx_varies_p);
2280
2281           if (remove)
2282             {
2283               if (dump_file)
2284                 dump_insn_info ("removing from active", i_ptr);
2285
2286               if (last)
2287                 last->next_local_store = i_ptr->next_local_store;
2288               else
2289                 active_local_stores = i_ptr->next_local_store;
2290             }
2291           else
2292             last = i_ptr;
2293           i_ptr = i_ptr->next_local_store;
2294         }
2295     }
2296   return 0;
2297 }
2298
2299 /* A for_each_rtx callback in which DATA points the INSN_INFO for
2300    as check_mem_read_rtx.  Nullify the pointer if i_m_r_m_r returns
2301    true for any part of *LOC.  */
2302
2303 static void
2304 check_mem_read_use (rtx *loc, void *data)
2305 {
2306   for_each_rtx (loc, check_mem_read_rtx, data);
2307 }
2308
2309
2310 /* Get arguments passed to CALL_INSN.  Return TRUE if successful.
2311    So far it only handles arguments passed in registers.  */
2312
2313 static bool
2314 get_call_args (rtx call_insn, tree fn, rtx *args, int nargs)
2315 {
2316   CUMULATIVE_ARGS args_so_far;
2317   tree arg;
2318   int idx;
2319
2320   INIT_CUMULATIVE_ARGS (args_so_far, TREE_TYPE (fn), NULL_RTX, 0, 3);
2321
2322   arg = TYPE_ARG_TYPES (TREE_TYPE (fn));
2323   for (idx = 0;
2324        arg != void_list_node && idx < nargs;
2325        arg = TREE_CHAIN (arg), idx++)
2326     {
2327       enum machine_mode mode = TYPE_MODE (TREE_VALUE (arg));
2328       rtx reg = FUNCTION_ARG (args_so_far, mode, NULL_TREE, 1), link, tmp;
2329       if (!reg || !REG_P (reg) || GET_MODE (reg) != mode
2330           || GET_MODE_CLASS (mode) != MODE_INT)
2331         return false;
2332
2333       for (link = CALL_INSN_FUNCTION_USAGE (call_insn);
2334            link;
2335            link = XEXP (link, 1))
2336         if (GET_CODE (XEXP (link, 0)) == USE)
2337           {
2338             args[idx] = XEXP (XEXP (link, 0), 0);
2339             if (REG_P (args[idx])
2340                 && REGNO (args[idx]) == REGNO (reg)
2341                 && (GET_MODE (args[idx]) == mode
2342                     || (GET_MODE_CLASS (GET_MODE (args[idx])) == MODE_INT
2343                         && (GET_MODE_SIZE (GET_MODE (args[idx]))
2344                             <= UNITS_PER_WORD)
2345                         && (GET_MODE_SIZE (GET_MODE (args[idx]))
2346                             > GET_MODE_SIZE (mode)))))
2347               break;
2348           }
2349       if (!link)
2350         return false;
2351
2352       tmp = cselib_expand_value_rtx (args[idx], scratch, 5);
2353       if (GET_MODE (args[idx]) != mode)
2354         {
2355           if (!tmp || !CONST_INT_P (tmp))
2356             return false;
2357           tmp = GEN_INT (trunc_int_for_mode (INTVAL (tmp), mode));
2358         }
2359       if (tmp)
2360         args[idx] = tmp;
2361
2362       FUNCTION_ARG_ADVANCE (args_so_far, mode, NULL_TREE, 1);
2363     }
2364   if (arg != void_list_node || idx != nargs)
2365     return false;
2366   return true;
2367 }
2368
2369
2370 /* Apply record_store to all candidate stores in INSN.  Mark INSN
2371    if some part of it is not a candidate store and assigns to a
2372    non-register target.  */
2373
2374 static void
2375 scan_insn (bb_info_t bb_info, rtx insn)
2376 {
2377   rtx body;
2378   insn_info_t insn_info = (insn_info_t) pool_alloc (insn_info_pool);
2379   int mems_found = 0;
2380   memset (insn_info, 0, sizeof (struct insn_info));
2381
2382   if (dump_file)
2383     fprintf (dump_file, "\n**scanning insn=%d\n",
2384              INSN_UID (insn));
2385
2386   insn_info->prev_insn = bb_info->last_insn;
2387   insn_info->insn = insn;
2388   bb_info->last_insn = insn_info;
2389
2390   if (DEBUG_INSN_P (insn))
2391     {
2392       insn_info->cannot_delete = true;
2393       return;
2394     }
2395
2396   /* Cselib clears the table for this case, so we have to essentially
2397      do the same.  */
2398   if (NONJUMP_INSN_P (insn)
2399       && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
2400       && MEM_VOLATILE_P (PATTERN (insn)))
2401     {
2402       add_wild_read (bb_info);
2403       insn_info->cannot_delete = true;
2404       return;
2405     }
2406
2407   /* Look at all of the uses in the insn.  */
2408   note_uses (&PATTERN (insn), check_mem_read_use, bb_info);
2409
2410   if (CALL_P (insn))
2411     {
2412       bool const_call;
2413       tree memset_call = NULL_TREE;
2414
2415       insn_info->cannot_delete = true;
2416
2417       /* Const functions cannot do anything bad i.e. read memory,
2418          however, they can read their parameters which may have
2419          been pushed onto the stack.
2420          memset and bzero don't read memory either.  */
2421       const_call = RTL_CONST_CALL_P (insn);
2422       if (!const_call)
2423         {
2424           rtx call = PATTERN (insn);
2425           if (GET_CODE (call) == PARALLEL)
2426             call = XVECEXP (call, 0, 0);
2427           if (GET_CODE (call) == SET)
2428             call = SET_SRC (call);
2429           if (GET_CODE (call) == CALL
2430               && MEM_P (XEXP (call, 0))
2431               && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
2432             {
2433               rtx symbol = XEXP (XEXP (call, 0), 0);
2434               if (SYMBOL_REF_DECL (symbol)
2435                   && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
2436                 {
2437                   if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
2438                        == BUILT_IN_NORMAL
2439                        && (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))
2440                            == BUILT_IN_MEMSET))
2441                       || SYMBOL_REF_DECL (symbol) == block_clear_fn)
2442                     memset_call = SYMBOL_REF_DECL (symbol);
2443                 }
2444             }
2445         }
2446       if (const_call || memset_call)
2447         {
2448           insn_info_t i_ptr = active_local_stores;
2449           insn_info_t last = NULL;
2450
2451           if (dump_file)
2452             fprintf (dump_file, "%s call %d\n",
2453                      const_call ? "const" : "memset", INSN_UID (insn));
2454
2455           /* See the head comment of the frame_read field.  */
2456           if (reload_completed)
2457             insn_info->frame_read = true;
2458
2459           /* Loop over the active stores and remove those which are
2460              killed by the const function call.  */
2461           while (i_ptr)
2462             {
2463               bool remove_store = false;
2464
2465               /* The stack pointer based stores are always killed.  */
2466               if (i_ptr->stack_pointer_based)
2467                 remove_store = true;
2468
2469               /* If the frame is read, the frame related stores are killed.  */
2470               else if (insn_info->frame_read)
2471                 {
2472                   store_info_t store_info = i_ptr->store_rec;
2473
2474                   /* Skip the clobbers.  */
2475                   while (!store_info->is_set)
2476                     store_info = store_info->next;
2477
2478                   if (store_info->group_id >= 0
2479                       && VEC_index (group_info_t, rtx_group_vec,
2480                                     store_info->group_id)->frame_related)
2481                     remove_store = true;
2482                 }
2483
2484               if (remove_store)
2485                 {
2486                   if (dump_file)
2487                     dump_insn_info ("removing from active", i_ptr);
2488
2489                   if (last)
2490                     last->next_local_store = i_ptr->next_local_store;
2491                   else
2492                     active_local_stores = i_ptr->next_local_store;
2493                 }
2494               else
2495                 last = i_ptr;
2496
2497               i_ptr = i_ptr->next_local_store;
2498             }
2499
2500           if (memset_call)
2501             {
2502               rtx args[3];
2503               if (get_call_args (insn, memset_call, args, 3)
2504                   && CONST_INT_P (args[1])
2505                   && CONST_INT_P (args[2])
2506                   && INTVAL (args[2]) > 0)
2507                 {
2508                   rtx mem = gen_rtx_MEM (BLKmode, args[0]);
2509                   set_mem_size (mem, args[2]);
2510                   body = gen_rtx_SET (VOIDmode, mem, args[1]);
2511                   mems_found += record_store (body, bb_info);
2512                   if (dump_file)
2513                     fprintf (dump_file, "handling memset as BLKmode store\n");
2514                   if (mems_found == 1)
2515                     {
2516                       insn_info->next_local_store = active_local_stores;
2517                       active_local_stores = insn_info;
2518                     }
2519                 }
2520             }
2521         }
2522
2523       else
2524         /* Every other call, including pure functions, may read memory.  */
2525         add_wild_read (bb_info);
2526
2527       return;
2528     }
2529
2530   /* Assuming that there are sets in these insns, we cannot delete
2531      them.  */
2532   if ((GET_CODE (PATTERN (insn)) == CLOBBER)
2533       || volatile_refs_p (PATTERN (insn))
2534       || insn_could_throw_p (insn)
2535       || (RTX_FRAME_RELATED_P (insn))
2536       || find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX))
2537     insn_info->cannot_delete = true;
2538
2539   body = PATTERN (insn);
2540   if (GET_CODE (body) == PARALLEL)
2541     {
2542       int i;
2543       for (i = 0; i < XVECLEN (body, 0); i++)
2544         mems_found += record_store (XVECEXP (body, 0, i), bb_info);
2545     }
2546   else
2547     mems_found += record_store (body, bb_info);
2548
2549   if (dump_file)
2550     fprintf (dump_file, "mems_found = %d, cannot_delete = %s\n",
2551              mems_found, insn_info->cannot_delete ? "true" : "false");
2552
2553   /* If we found some sets of mems, add it into the active_local_stores so
2554      that it can be locally deleted if found dead or used for
2555      replace_read and redundant constant store elimination.  Otherwise mark
2556      it as cannot delete.  This simplifies the processing later.  */
2557   if (mems_found == 1)
2558     {
2559       insn_info->next_local_store = active_local_stores;
2560       active_local_stores = insn_info;
2561     }
2562   else
2563     insn_info->cannot_delete = true;
2564 }
2565
2566
2567 /* Remove BASE from the set of active_local_stores.  This is a
2568    callback from cselib that is used to get rid of the stores in
2569    active_local_stores.  */
2570
2571 static void
2572 remove_useless_values (cselib_val *base)
2573 {
2574   insn_info_t insn_info = active_local_stores;
2575   insn_info_t last = NULL;
2576
2577   while (insn_info)
2578     {
2579       store_info_t store_info = insn_info->store_rec;
2580       bool del = false;
2581
2582       /* If ANY of the store_infos match the cselib group that is
2583          being deleted, then the insn can not be deleted.  */
2584       while (store_info)
2585         {
2586           if ((store_info->group_id == -1)
2587               && (store_info->cse_base == base))
2588             {
2589               del = true;
2590               break;
2591             }
2592           store_info = store_info->next;
2593         }
2594
2595       if (del)
2596         {
2597           if (last)
2598             last->next_local_store = insn_info->next_local_store;
2599           else
2600             active_local_stores = insn_info->next_local_store;
2601           free_store_info (insn_info);
2602         }
2603       else
2604         last = insn_info;
2605
2606       insn_info = insn_info->next_local_store;
2607     }
2608 }
2609
2610
2611 /* Do all of step 1.  */
2612
2613 static void
2614 dse_step1 (void)
2615 {
2616   basic_block bb;
2617   bitmap regs_live = BITMAP_ALLOC (NULL);
2618
2619   cselib_init (false);
2620   all_blocks = BITMAP_ALLOC (NULL);
2621   bitmap_set_bit (all_blocks, ENTRY_BLOCK);
2622   bitmap_set_bit (all_blocks, EXIT_BLOCK);
2623
2624   FOR_ALL_BB (bb)
2625     {
2626       insn_info_t ptr;
2627       bb_info_t bb_info = (bb_info_t) pool_alloc (bb_info_pool);
2628
2629       memset (bb_info, 0, sizeof (struct bb_info));
2630       bitmap_set_bit (all_blocks, bb->index);
2631       bb_info->regs_live = regs_live;
2632
2633       bitmap_copy (regs_live, DF_LR_IN (bb));
2634       df_simulate_initialize_forwards (bb, regs_live);
2635
2636       bb_table[bb->index] = bb_info;
2637       cselib_discard_hook = remove_useless_values;
2638
2639       if (bb->index >= NUM_FIXED_BLOCKS)
2640         {
2641           rtx insn;
2642
2643           cse_store_info_pool
2644             = create_alloc_pool ("cse_store_info_pool",
2645                                  sizeof (struct store_info), 100);
2646           active_local_stores = NULL;
2647           cselib_clear_table ();
2648
2649           /* Scan the insns.  */
2650           FOR_BB_INSNS (bb, insn)
2651             {
2652               if (INSN_P (insn))
2653                 scan_insn (bb_info, insn);
2654               cselib_process_insn (insn);
2655               if (INSN_P (insn))
2656                 df_simulate_one_insn_forwards (bb, insn, regs_live);
2657             }
2658
2659           /* This is something of a hack, because the global algorithm
2660              is supposed to take care of the case where stores go dead
2661              at the end of the function.  However, the global
2662              algorithm must take a more conservative view of block
2663              mode reads than the local alg does.  So to get the case
2664              where you have a store to the frame followed by a non
2665              overlapping block more read, we look at the active local
2666              stores at the end of the function and delete all of the
2667              frame and spill based ones.  */
2668           if (stores_off_frame_dead_at_return
2669               && (EDGE_COUNT (bb->succs) == 0
2670                   || (single_succ_p (bb)
2671                       && single_succ (bb) == EXIT_BLOCK_PTR
2672                       && ! crtl->calls_eh_return)))
2673             {
2674               insn_info_t i_ptr = active_local_stores;
2675               while (i_ptr)
2676                 {
2677                   store_info_t store_info = i_ptr->store_rec;
2678
2679                   /* Skip the clobbers.  */
2680                   while (!store_info->is_set)
2681                     store_info = store_info->next;
2682                   if (store_info->alias_set && !i_ptr->cannot_delete)
2683                     delete_dead_store_insn (i_ptr);
2684                   else
2685                     if (store_info->group_id >= 0)
2686                       {
2687                         group_info_t group
2688                           = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
2689                         if (group->frame_related && !i_ptr->cannot_delete)
2690                           delete_dead_store_insn (i_ptr);
2691                       }
2692
2693                   i_ptr = i_ptr->next_local_store;
2694                 }
2695             }
2696
2697           /* Get rid of the loads that were discovered in
2698              replace_read.  Cselib is finished with this block.  */
2699           while (deferred_change_list)
2700             {
2701               deferred_change_t next = deferred_change_list->next;
2702
2703               /* There is no reason to validate this change.  That was
2704                  done earlier.  */
2705               *deferred_change_list->loc = deferred_change_list->reg;
2706               pool_free (deferred_change_pool, deferred_change_list);
2707               deferred_change_list = next;
2708             }
2709
2710           /* Get rid of all of the cselib based store_infos in this
2711              block and mark the containing insns as not being
2712              deletable.  */
2713           ptr = bb_info->last_insn;
2714           while (ptr)
2715             {
2716               if (ptr->contains_cselib_groups)
2717                 {
2718                   store_info_t s_info = ptr->store_rec;
2719                   while (s_info && !s_info->is_set)
2720                     s_info = s_info->next;
2721                   if (s_info
2722                       && s_info->redundant_reason
2723                       && s_info->redundant_reason->insn
2724                       && !ptr->cannot_delete)
2725                     {
2726                       if (dump_file)
2727                         fprintf (dump_file, "Locally deleting insn %d "
2728                                             "because insn %d stores the "
2729                                             "same value and couldn't be "
2730                                             "eliminated\n",
2731                                  INSN_UID (ptr->insn),
2732                                  INSN_UID (s_info->redundant_reason->insn));
2733                       delete_dead_store_insn (ptr);
2734                     }
2735                   if (s_info)
2736                     s_info->redundant_reason = NULL;
2737                   free_store_info (ptr);
2738                 }
2739               else
2740                 {
2741                   store_info_t s_info;
2742
2743                   /* Free at least positions_needed bitmaps.  */
2744                   for (s_info = ptr->store_rec; s_info; s_info = s_info->next)
2745                     if (s_info->is_large)
2746                       {
2747                         BITMAP_FREE (s_info->positions_needed.large.bmap);
2748                         s_info->is_large = false;
2749                       }
2750                 }
2751               ptr = ptr->prev_insn;
2752             }
2753
2754           free_alloc_pool (cse_store_info_pool);
2755         }
2756       bb_info->regs_live = NULL;
2757     }
2758
2759   BITMAP_FREE (regs_live);
2760   cselib_finish ();
2761   htab_empty (rtx_group_table);
2762 }
2763
2764 \f
2765 /*----------------------------------------------------------------------------
2766    Second step.
2767
2768    Assign each byte position in the stores that we are going to
2769    analyze globally to a position in the bitmaps.  Returns true if
2770    there are any bit positions assigned.
2771 ----------------------------------------------------------------------------*/
2772
2773 static void
2774 dse_step2_init (void)
2775 {
2776   unsigned int i;
2777   group_info_t group;
2778
2779   for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2780     {
2781       /* For all non stack related bases, we only consider a store to
2782          be deletable if there are two or more stores for that
2783          position.  This is because it takes one store to make the
2784          other store redundant.  However, for the stores that are
2785          stack related, we consider them if there is only one store
2786          for the position.  We do this because the stack related
2787          stores can be deleted if their is no read between them and
2788          the end of the function.
2789
2790          To make this work in the current framework, we take the stack
2791          related bases add all of the bits from store1 into store2.
2792          This has the effect of making the eligible even if there is
2793          only one store.   */
2794
2795       if (stores_off_frame_dead_at_return && group->frame_related)
2796         {
2797           bitmap_ior_into (group->store2_n, group->store1_n);
2798           bitmap_ior_into (group->store2_p, group->store1_p);
2799           if (dump_file)
2800             fprintf (dump_file, "group %d is frame related ", i);
2801         }
2802
2803       group->offset_map_size_n++;
2804       group->offset_map_n = XNEWVEC (int, group->offset_map_size_n);
2805       group->offset_map_size_p++;
2806       group->offset_map_p = XNEWVEC (int, group->offset_map_size_p);
2807       group->process_globally = false;
2808       if (dump_file)
2809         {
2810           fprintf (dump_file, "group %d(%d+%d): ", i,
2811                    (int)bitmap_count_bits (group->store2_n),
2812                    (int)bitmap_count_bits (group->store2_p));
2813           bitmap_print (dump_file, group->store2_n, "n ", " ");
2814           bitmap_print (dump_file, group->store2_p, "p ", "\n");
2815         }
2816     }
2817 }
2818
2819
2820 /* Init the offset tables for the normal case.  */
2821
2822 static bool
2823 dse_step2_nospill (void)
2824 {
2825   unsigned int i;
2826   group_info_t group;
2827   /* Position 0 is unused because 0 is used in the maps to mean
2828      unused.  */
2829   current_position = 1;
2830
2831   for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2832     {
2833       bitmap_iterator bi;
2834       unsigned int j;
2835
2836       if (group == clear_alias_group)
2837         continue;
2838
2839       memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2840       memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2841       bitmap_clear (group->group_kill);
2842
2843       EXECUTE_IF_SET_IN_BITMAP (group->store2_n, 0, j, bi)
2844         {
2845           bitmap_set_bit (group->group_kill, current_position);
2846           group->offset_map_n[j] = current_position++;
2847           group->process_globally = true;
2848         }
2849       EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2850         {
2851           bitmap_set_bit (group->group_kill, current_position);
2852           group->offset_map_p[j] = current_position++;
2853           group->process_globally = true;
2854         }
2855     }
2856   return current_position != 1;
2857 }
2858
2859
2860 /* Init the offset tables for the spill case.  */
2861
2862 static bool
2863 dse_step2_spill (void)
2864 {
2865   unsigned int j;
2866   group_info_t group = clear_alias_group;
2867   bitmap_iterator bi;
2868
2869   /* Position 0 is unused because 0 is used in the maps to mean
2870      unused.  */
2871   current_position = 1;
2872
2873   if (dump_file)
2874     {
2875       bitmap_print (dump_file, clear_alias_sets,
2876                     "clear alias sets              ", "\n");
2877       bitmap_print (dump_file, disqualified_clear_alias_sets,
2878                     "disqualified clear alias sets ", "\n");
2879     }
2880
2881   memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2882   memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2883   bitmap_clear (group->group_kill);
2884
2885   /* Remove the disqualified positions from the store2_p set.  */
2886   bitmap_and_compl_into (group->store2_p, disqualified_clear_alias_sets);
2887
2888   /* We do not need to process the store2_n set because
2889      alias_sets are always positive.  */
2890   EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2891     {
2892       bitmap_set_bit (group->group_kill, current_position);
2893       group->offset_map_p[j] = current_position++;
2894       group->process_globally = true;
2895     }
2896
2897   return current_position != 1;
2898 }
2899
2900
2901 \f
2902 /*----------------------------------------------------------------------------
2903   Third step.
2904
2905   Build the bit vectors for the transfer functions.
2906 ----------------------------------------------------------------------------*/
2907
2908
2909 /* Note that this is NOT a general purpose function.  Any mem that has
2910    an alias set registered here expected to be COMPLETELY unaliased:
2911    i.e it's addresses are not and need not be examined.
2912
2913    It is known that all references to this address will have this
2914    alias set and there are NO other references to this address in the
2915    function.
2916
2917    Currently the only place that is known to be clean enough to use
2918    this interface is the code that assigns the spill locations.
2919
2920    All of the mems that have alias_sets registered are subjected to a
2921    very powerful form of dse where function calls, volatile reads and
2922    writes, and reads from random location are not taken into account.
2923
2924    It is also assumed that these locations go dead when the function
2925    returns.  This assumption could be relaxed if there were found to
2926    be places that this assumption was not correct.
2927
2928    The MODE is passed in and saved.  The mode of each load or store to
2929    a mem with ALIAS_SET is checked against MEM.  If the size of that
2930    load or store is different from MODE, processing is halted on this
2931    alias set.  For the vast majority of aliases sets, all of the loads
2932    and stores will use the same mode.  But vectors are treated
2933    differently: the alias set is established for the entire vector,
2934    but reload will insert loads and stores for individual elements and
2935    we do not necessarily have the information to track those separate
2936    elements.  So when we see a mode mismatch, we just bail.  */
2937
2938
2939 void
2940 dse_record_singleton_alias_set (alias_set_type alias_set,
2941                                 enum machine_mode mode)
2942 {
2943   struct clear_alias_mode_holder tmp_holder;
2944   struct clear_alias_mode_holder *entry;
2945   void **slot;
2946
2947   /* If we are not going to run dse, we need to return now or there
2948      will be problems with allocating the bitmaps.  */
2949   if ((!gate_dse()) || !alias_set)
2950     return;
2951
2952   if (!clear_alias_sets)
2953     {
2954       clear_alias_sets = BITMAP_ALLOC (NULL);
2955       disqualified_clear_alias_sets = BITMAP_ALLOC (NULL);
2956       clear_alias_mode_table = htab_create (11, clear_alias_mode_hash,
2957                                             clear_alias_mode_eq, NULL);
2958       clear_alias_mode_pool = create_alloc_pool ("clear_alias_mode_pool",
2959                                                  sizeof (struct clear_alias_mode_holder), 100);
2960     }
2961
2962   bitmap_set_bit (clear_alias_sets, alias_set);
2963
2964   tmp_holder.alias_set = alias_set;
2965
2966   slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, INSERT);
2967   gcc_assert (*slot == NULL);
2968
2969   *slot = entry =
2970     (struct clear_alias_mode_holder *) pool_alloc (clear_alias_mode_pool);
2971   entry->alias_set = alias_set;
2972   entry->mode = mode;
2973 }
2974
2975
2976 /* Remove ALIAS_SET from the sets of stack slots being considered.  */
2977
2978 void
2979 dse_invalidate_singleton_alias_set (alias_set_type alias_set)
2980 {
2981   if ((!gate_dse()) || !alias_set)
2982     return;
2983
2984   bitmap_clear_bit (clear_alias_sets, alias_set);
2985 }
2986
2987
2988 /* Look up the bitmap index for OFFSET in GROUP_INFO.  If it is not
2989    there, return 0.  */
2990
2991 static int
2992 get_bitmap_index (group_info_t group_info, HOST_WIDE_INT offset)
2993 {
2994   if (offset < 0)
2995     {
2996       HOST_WIDE_INT offset_p = -offset;
2997       if (offset_p >= group_info->offset_map_size_n)
2998         return 0;
2999       return group_info->offset_map_n[offset_p];
3000     }
3001   else
3002     {
3003       if (offset >= group_info->offset_map_size_p)
3004         return 0;
3005       return group_info->offset_map_p[offset];
3006     }
3007 }
3008
3009
3010 /* Process the STORE_INFOs into the bitmaps into GEN and KILL.  KILL
3011    may be NULL. */
3012
3013 static void
3014 scan_stores_nospill (store_info_t store_info, bitmap gen, bitmap kill)
3015 {
3016   while (store_info)
3017     {
3018       HOST_WIDE_INT i;
3019       group_info_t group_info
3020         = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
3021       if (group_info->process_globally)
3022         for (i = store_info->begin; i < store_info->end; i++)
3023           {
3024             int index = get_bitmap_index (group_info, i);
3025             if (index != 0)
3026               {
3027                 bitmap_set_bit (gen, index);
3028                 if (kill)
3029                   bitmap_clear_bit (kill, index);
3030               }
3031           }
3032       store_info = store_info->next;
3033     }
3034 }
3035
3036
3037 /* Process the STORE_INFOs into the bitmaps into GEN and KILL.  KILL
3038    may be NULL. */
3039
3040 static void
3041 scan_stores_spill (store_info_t store_info, bitmap gen, bitmap kill)
3042 {
3043   while (store_info)
3044     {
3045       if (store_info->alias_set)
3046         {
3047           int index = get_bitmap_index (clear_alias_group,
3048                                         store_info->alias_set);
3049           if (index != 0)
3050             {
3051               bitmap_set_bit (gen, index);
3052               if (kill)
3053                 bitmap_clear_bit (kill, index);
3054             }
3055         }
3056       store_info = store_info->next;
3057     }
3058 }
3059
3060
3061 /* Process the READ_INFOs into the bitmaps into GEN and KILL.  KILL
3062    may be NULL.  */
3063
3064 static void
3065 scan_reads_nospill (insn_info_t insn_info, bitmap gen, bitmap kill)
3066 {
3067   read_info_t read_info = insn_info->read_rec;
3068   int i;
3069   group_info_t group;
3070
3071   /* If this insn reads the frame, kill all the frame related stores.  */
3072   if (insn_info->frame_read)
3073     {
3074       for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
3075         if (group->process_globally && group->frame_related)
3076           {
3077             if (kill)
3078               bitmap_ior_into (kill, group->group_kill);
3079             bitmap_and_compl_into (gen, group->group_kill);
3080           }
3081     }
3082
3083   while (read_info)
3084     {
3085       for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
3086         {
3087           if (group->process_globally)
3088             {
3089               if (i == read_info->group_id)
3090                 {
3091                   if (read_info->begin > read_info->end)
3092                     {
3093                       /* Begin > end for block mode reads.  */
3094                       if (kill)
3095                         bitmap_ior_into (kill, group->group_kill);
3096                       bitmap_and_compl_into (gen, group->group_kill);
3097                     }
3098                   else
3099                     {
3100                       /* The groups are the same, just process the
3101                          offsets.  */
3102                       HOST_WIDE_INT j;
3103                       for (j = read_info->begin; j < read_info->end; j++)
3104                         {
3105                           int index = get_bitmap_index (group, j);
3106                           if (index != 0)
3107                             {
3108                               if (kill)
3109                                 bitmap_set_bit (kill, index);
3110                               bitmap_clear_bit (gen, index);
3111                             }
3112                         }
3113                     }
3114                 }
3115               else
3116                 {
3117                   /* The groups are different, if the alias sets
3118                      conflict, clear the entire group.  We only need
3119                      to apply this test if the read_info is a cselib
3120                      read.  Anything with a constant base cannot alias
3121                      something else with a different constant
3122                      base.  */
3123                   if ((read_info->group_id < 0)
3124                       && canon_true_dependence (group->base_mem,
3125                                                 QImode,
3126                                                 group->canon_base_addr,
3127                                                 read_info->mem, NULL_RTX,
3128                                                 rtx_varies_p))
3129                     {
3130                       if (kill)
3131                         bitmap_ior_into (kill, group->group_kill);
3132                       bitmap_and_compl_into (gen, group->group_kill);
3133                     }
3134                 }
3135             }
3136         }
3137
3138       read_info = read_info->next;
3139     }
3140 }
3141
3142 /* Process the READ_INFOs into the bitmaps into GEN and KILL.  KILL
3143    may be NULL.  */
3144
3145 static void
3146 scan_reads_spill (read_info_t read_info, bitmap gen, bitmap kill)
3147 {
3148   while (read_info)
3149     {
3150       if (read_info->alias_set)
3151         {
3152           int index = get_bitmap_index (clear_alias_group,
3153                                         read_info->alias_set);
3154           if (index != 0)
3155             {
3156               if (kill)
3157                 bitmap_set_bit (kill, index);
3158               bitmap_clear_bit (gen, index);
3159             }
3160         }
3161
3162       read_info = read_info->next;
3163     }
3164 }
3165
3166
3167 /* Return the insn in BB_INFO before the first wild read or if there
3168    are no wild reads in the block, return the last insn.  */
3169
3170 static insn_info_t
3171 find_insn_before_first_wild_read (bb_info_t bb_info)
3172 {
3173   insn_info_t insn_info = bb_info->last_insn;
3174   insn_info_t last_wild_read = NULL;
3175
3176   while (insn_info)
3177     {
3178       if (insn_info->wild_read)
3179         {
3180           last_wild_read = insn_info->prev_insn;
3181           /* Block starts with wild read.  */
3182           if (!last_wild_read)
3183             return NULL;
3184         }
3185
3186       insn_info = insn_info->prev_insn;
3187     }
3188
3189   if (last_wild_read)
3190     return last_wild_read;
3191   else
3192     return bb_info->last_insn;
3193 }
3194
3195
3196 /* Scan the insns in BB_INFO starting at PTR and going to the top of
3197    the block in order to build the gen and kill sets for the block.
3198    We start at ptr which may be the last insn in the block or may be
3199    the first insn with a wild read.  In the latter case we are able to
3200    skip the rest of the block because it just does not matter:
3201    anything that happens is hidden by the wild read.  */
3202
3203 static void
3204 dse_step3_scan (bool for_spills, basic_block bb)
3205 {
3206   bb_info_t bb_info = bb_table[bb->index];
3207   insn_info_t insn_info;
3208
3209   if (for_spills)
3210     /* There are no wild reads in the spill case.  */
3211     insn_info = bb_info->last_insn;
3212   else
3213     insn_info = find_insn_before_first_wild_read (bb_info);
3214
3215   /* In the spill case or in the no_spill case if there is no wild
3216      read in the block, we will need a kill set.  */
3217   if (insn_info == bb_info->last_insn)
3218     {
3219       if (bb_info->kill)
3220         bitmap_clear (bb_info->kill);
3221       else
3222         bb_info->kill = BITMAP_ALLOC (NULL);
3223     }
3224   else
3225     if (bb_info->kill)
3226       BITMAP_FREE (bb_info->kill);
3227
3228   while (insn_info)
3229     {
3230       /* There may have been code deleted by the dce pass run before
3231          this phase.  */
3232       if (insn_info->insn && INSN_P (insn_info->insn))
3233         {
3234           /* Process the read(s) last.  */
3235           if (for_spills)
3236             {
3237               scan_stores_spill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3238               scan_reads_spill (insn_info->read_rec, bb_info->gen, bb_info->kill);
3239             }
3240           else
3241             {
3242               scan_stores_nospill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3243               scan_reads_nospill (insn_info, bb_info->gen, bb_info->kill);
3244             }
3245         }
3246
3247       insn_info = insn_info->prev_insn;
3248     }
3249 }
3250
3251
3252 /* Set the gen set of the exit block, and also any block with no
3253    successors that does not have a wild read.  */
3254
3255 static void
3256 dse_step3_exit_block_scan (bb_info_t bb_info)
3257 {
3258   /* The gen set is all 0's for the exit block except for the
3259      frame_pointer_group.  */
3260
3261   if (stores_off_frame_dead_at_return)
3262     {
3263       unsigned int i;
3264       group_info_t group;
3265
3266       for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
3267         {
3268           if (group->process_globally && group->frame_related)
3269             bitmap_ior_into (bb_info->gen, group->group_kill);
3270         }
3271     }
3272 }
3273
3274
3275 /* Find all of the blocks that are not backwards reachable from the
3276    exit block or any block with no successors (BB).  These are the
3277    infinite loops or infinite self loops.  These blocks will still
3278    have their bits set in UNREACHABLE_BLOCKS.  */
3279
3280 static void
3281 mark_reachable_blocks (sbitmap unreachable_blocks, basic_block bb)
3282 {
3283   edge e;
3284   edge_iterator ei;
3285
3286   if (TEST_BIT (unreachable_blocks, bb->index))
3287     {
3288       RESET_BIT (unreachable_blocks, bb->index);
3289       FOR_EACH_EDGE (e, ei, bb->preds)
3290         {
3291           mark_reachable_blocks (unreachable_blocks, e->src);
3292         }
3293     }
3294 }
3295
3296 /* Build the transfer functions for the function.  */
3297
3298 static void
3299 dse_step3 (bool for_spills)
3300 {
3301   basic_block bb;
3302   sbitmap unreachable_blocks = sbitmap_alloc (last_basic_block);
3303   sbitmap_iterator sbi;
3304   bitmap all_ones = NULL;
3305   unsigned int i;
3306
3307   sbitmap_ones (unreachable_blocks);
3308
3309   FOR_ALL_BB (bb)
3310     {
3311       bb_info_t bb_info = bb_table[bb->index];
3312       if (bb_info->gen)
3313         bitmap_clear (bb_info->gen);
3314       else
3315         bb_info->gen = BITMAP_ALLOC (NULL);
3316
3317       if (bb->index == ENTRY_BLOCK)
3318         ;
3319       else if (bb->index == EXIT_BLOCK)
3320         dse_step3_exit_block_scan (bb_info);
3321       else
3322         dse_step3_scan (for_spills, bb);
3323       if (EDGE_COUNT (bb->succs) == 0)
3324         mark_reachable_blocks (unreachable_blocks, bb);
3325
3326       /* If this is the second time dataflow is run, delete the old
3327          sets.  */
3328       if (bb_info->in)
3329         BITMAP_FREE (bb_info->in);
3330       if (bb_info->out)
3331         BITMAP_FREE (bb_info->out);
3332     }
3333
3334   /* For any block in an infinite loop, we must initialize the out set
3335      to all ones.  This could be expensive, but almost never occurs in
3336      practice. However, it is common in regression tests.  */
3337   EXECUTE_IF_SET_IN_SBITMAP (unreachable_blocks, 0, i, sbi)
3338     {
3339       if (bitmap_bit_p (all_blocks, i))
3340         {
3341           bb_info_t bb_info = bb_table[i];
3342           if (!all_ones)
3343             {
3344               unsigned int j;
3345               group_info_t group;
3346
3347               all_ones = BITMAP_ALLOC (NULL);
3348               for (j = 0; VEC_iterate (group_info_t, rtx_group_vec, j, group); j++)
3349                 bitmap_ior_into (all_ones, group->group_kill);
3350             }
3351           if (!bb_info->out)
3352             {
3353               bb_info->out = BITMAP_ALLOC (NULL);
3354               bitmap_copy (bb_info->out, all_ones);
3355             }
3356         }
3357     }
3358
3359   if (all_ones)
3360     BITMAP_FREE (all_ones);
3361   sbitmap_free (unreachable_blocks);
3362 }
3363
3364
3365 \f
3366 /*----------------------------------------------------------------------------
3367    Fourth step.
3368
3369    Solve the bitvector equations.
3370 ----------------------------------------------------------------------------*/
3371
3372
3373 /* Confluence function for blocks with no successors.  Create an out
3374    set from the gen set of the exit block.  This block logically has
3375    the exit block as a successor.  */
3376
3377
3378
3379 static void
3380 dse_confluence_0 (basic_block bb)
3381 {
3382   bb_info_t bb_info = bb_table[bb->index];
3383
3384   if (bb->index == EXIT_BLOCK)
3385     return;
3386
3387   if (!bb_info->out)
3388     {
3389       bb_info->out = BITMAP_ALLOC (NULL);
3390       bitmap_copy (bb_info->out, bb_table[EXIT_BLOCK]->gen);
3391     }
3392 }
3393
3394 /* Propagate the information from the in set of the dest of E to the
3395    out set of the src of E.  If the various in or out sets are not
3396    there, that means they are all ones.  */
3397
3398 static void
3399 dse_confluence_n (edge e)
3400 {
3401   bb_info_t src_info = bb_table[e->src->index];
3402   bb_info_t dest_info = bb_table[e->dest->index];
3403
3404   if (dest_info->in)
3405     {
3406       if (src_info->out)
3407         bitmap_and_into (src_info->out, dest_info->in);
3408       else
3409         {
3410           src_info->out = BITMAP_ALLOC (NULL);
3411           bitmap_copy (src_info->out, dest_info->in);
3412         }
3413     }
3414 }
3415
3416
3417 /* Propagate the info from the out to the in set of BB_INDEX's basic
3418    block.  There are three cases:
3419
3420    1) The block has no kill set.  In this case the kill set is all
3421    ones.  It does not matter what the out set of the block is, none of
3422    the info can reach the top.  The only thing that reaches the top is
3423    the gen set and we just copy the set.
3424
3425    2) There is a kill set but no out set and bb has successors.  In
3426    this case we just return. Eventually an out set will be created and
3427    it is better to wait than to create a set of ones.
3428
3429    3) There is both a kill and out set.  We apply the obvious transfer
3430    function.
3431 */
3432
3433 static bool
3434 dse_transfer_function (int bb_index)
3435 {
3436   bb_info_t bb_info = bb_table[bb_index];
3437
3438   if (bb_info->kill)
3439     {
3440       if (bb_info->out)
3441         {
3442           /* Case 3 above.  */
3443           if (bb_info->in)
3444             return bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3445                                          bb_info->out, bb_info->kill);
3446           else
3447             {
3448               bb_info->in = BITMAP_ALLOC (NULL);
3449               bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3450                                     bb_info->out, bb_info->kill);
3451               return true;
3452             }
3453         }
3454       else
3455         /* Case 2 above.  */
3456         return false;
3457     }
3458   else
3459     {
3460       /* Case 1 above.  If there is already an in set, nothing
3461          happens.  */
3462       if (bb_info->in)
3463         return false;
3464       else
3465         {
3466           bb_info->in = BITMAP_ALLOC (NULL);
3467           bitmap_copy (bb_info->in, bb_info->gen);
3468           return true;
3469         }
3470     }
3471 }
3472
3473 /* Solve the dataflow equations.  */
3474
3475 static void
3476 dse_step4 (void)
3477 {
3478   df_simple_dataflow (DF_BACKWARD, NULL, dse_confluence_0,
3479                       dse_confluence_n, dse_transfer_function,
3480                       all_blocks, df_get_postorder (DF_BACKWARD),
3481                       df_get_n_blocks (DF_BACKWARD));
3482   if (dump_file)
3483     {
3484       basic_block bb;
3485
3486       fprintf (dump_file, "\n\n*** Global dataflow info after analysis.\n");
3487       FOR_ALL_BB (bb)
3488         {
3489           bb_info_t bb_info = bb_table[bb->index];
3490
3491           df_print_bb_index (bb, dump_file);
3492           if (bb_info->in)
3493             bitmap_print (dump_file, bb_info->in, "  in:   ", "\n");
3494           else
3495             fprintf (dump_file, "  in:   *MISSING*\n");
3496           if (bb_info->gen)
3497             bitmap_print (dump_file, bb_info->gen, "  gen:  ", "\n");
3498           else
3499             fprintf (dump_file, "  gen:  *MISSING*\n");
3500           if (bb_info->kill)
3501             bitmap_print (dump_file, bb_info->kill, "  kill: ", "\n");
3502           else
3503             fprintf (dump_file, "  kill: *MISSING*\n");
3504           if (bb_info->out)
3505             bitmap_print (dump_file, bb_info->out, "  out:  ", "\n");
3506           else
3507             fprintf (dump_file, "  out:  *MISSING*\n\n");
3508         }
3509     }
3510 }
3511
3512
3513 \f
3514 /*----------------------------------------------------------------------------
3515    Fifth step.
3516
3517    Delete the stores that can only be deleted using the global information.
3518 ----------------------------------------------------------------------------*/
3519
3520
3521 static void
3522 dse_step5_nospill (void)
3523 {
3524   basic_block bb;
3525   FOR_EACH_BB (bb)
3526     {
3527       bb_info_t bb_info = bb_table[bb->index];
3528       insn_info_t insn_info = bb_info->last_insn;
3529       bitmap v = bb_info->out;
3530
3531       while (insn_info)
3532         {
3533           bool deleted = false;
3534           if (dump_file && insn_info->insn)
3535             {
3536               fprintf (dump_file, "starting to process insn %d\n",
3537                        INSN_UID (insn_info->insn));
3538               bitmap_print (dump_file, v, "  v:  ", "\n");
3539             }
3540
3541           /* There may have been code deleted by the dce pass run before
3542              this phase.  */
3543           if (insn_info->insn
3544               && INSN_P (insn_info->insn)
3545               && (!insn_info->cannot_delete)
3546               && (!bitmap_empty_p (v)))
3547             {
3548               store_info_t store_info = insn_info->store_rec;
3549
3550               /* Try to delete the current insn.  */
3551               deleted = true;
3552
3553               /* Skip the clobbers.  */
3554               while (!store_info->is_set)
3555                 store_info = store_info->next;
3556
3557               if (store_info->alias_set)
3558                 deleted = false;
3559               else
3560                 {
3561                   HOST_WIDE_INT i;
3562                   group_info_t group_info
3563                     = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
3564
3565                   for (i = store_info->begin; i < store_info->end; i++)
3566                     {
3567                       int index = get_bitmap_index (group_info, i);
3568
3569                       if (dump_file)
3570                         fprintf (dump_file, "i = %d, index = %d\n", (int)i, index);
3571                       if (index == 0 || !bitmap_bit_p (v, index))
3572                         {
3573                           if (dump_file)
3574                             fprintf (dump_file, "failing at i = %d\n", (int)i);
3575                           deleted = false;
3576                           break;
3577                         }
3578                     }
3579                 }
3580               if (deleted)
3581                 {
3582                   if (dbg_cnt (dse))
3583                     {
3584                       check_for_inc_dec (insn_info->insn);
3585                       delete_insn (insn_info->insn);
3586                       insn_info->insn = NULL;
3587                       globally_deleted++;
3588                     }
3589                 }
3590             }
3591           /* We do want to process the local info if the insn was
3592              deleted.  For instance, if the insn did a wild read, we
3593              no longer need to trash the info.  */
3594           if (insn_info->insn
3595               && INSN_P (insn_info->insn)
3596               && (!deleted))
3597             {
3598               scan_stores_nospill (insn_info->store_rec, v, NULL);
3599               if (insn_info->wild_read)
3600                 {
3601                   if (dump_file)
3602                     fprintf (dump_file, "wild read\n");
3603                   bitmap_clear (v);
3604                 }
3605               else if (insn_info->read_rec)
3606                 {
3607                   if (dump_file)
3608                     fprintf (dump_file, "regular read\n");
3609                   scan_reads_nospill (insn_info, v, NULL);
3610                 }
3611             }
3612
3613           insn_info = insn_info->prev_insn;
3614         }
3615     }
3616 }
3617
3618
3619 static void
3620 dse_step5_spill (void)
3621 {
3622   basic_block bb;
3623   FOR_EACH_BB (bb)
3624     {
3625       bb_info_t bb_info = bb_table[bb->index];
3626       insn_info_t insn_info = bb_info->last_insn;
3627       bitmap v = bb_info->out;
3628
3629       while (insn_info)
3630         {
3631           bool deleted = false;
3632           /* There may have been code deleted by the dce pass run before
3633              this phase.  */
3634           if (insn_info->insn
3635               && INSN_P (insn_info->insn)
3636               && (!insn_info->cannot_delete)
3637               && (!bitmap_empty_p (v)))
3638             {
3639               /* Try to delete the current insn.  */
3640               store_info_t store_info = insn_info->store_rec;
3641               deleted = true;
3642
3643               while (store_info)
3644                 {
3645                   if (store_info->alias_set)
3646                     {
3647                       int index = get_bitmap_index (clear_alias_group,
3648                                                     store_info->alias_set);
3649                       if (index == 0 || !bitmap_bit_p (v, index))
3650                         {
3651                           deleted = false;
3652                           break;
3653                         }
3654                     }
3655                   else
3656                     deleted = false;
3657                   store_info = store_info->next;
3658                 }
3659               if (deleted && dbg_cnt (dse))
3660                 {
3661                   if (dump_file)
3662                     fprintf (dump_file, "Spill deleting insn %d\n",
3663                              INSN_UID (insn_info->insn));
3664                   check_for_inc_dec (insn_info->insn);
3665                   delete_insn (insn_info->insn);
3666                   spill_deleted++;
3667                   insn_info->insn = NULL;
3668                 }
3669             }
3670
3671           if (insn_info->insn
3672               && INSN_P (insn_info->insn)
3673               && (!deleted))
3674             {
3675               scan_stores_spill (insn_info->store_rec, v, NULL);
3676               scan_reads_spill (insn_info->read_rec, v, NULL);
3677             }
3678
3679           insn_info = insn_info->prev_insn;
3680         }
3681     }
3682 }
3683
3684
3685 \f
3686 /*----------------------------------------------------------------------------
3687    Sixth step.
3688
3689    Delete stores made redundant by earlier stores (which store the same
3690    value) that couldn't be eliminated.
3691 ----------------------------------------------------------------------------*/
3692
3693 static void
3694 dse_step6 (void)
3695 {
3696   basic_block bb;
3697
3698   FOR_ALL_BB (bb)
3699     {
3700       bb_info_t bb_info = bb_table[bb->index];
3701       insn_info_t insn_info = bb_info->last_insn;
3702
3703       while (insn_info)
3704         {
3705           /* There may have been code deleted by the dce pass run before
3706              this phase.  */
3707           if (insn_info->insn
3708               && INSN_P (insn_info->insn)
3709               && !insn_info->cannot_delete)
3710             {
3711               store_info_t s_info = insn_info->store_rec;
3712
3713               while (s_info && !s_info->is_set)
3714                 s_info = s_info->next;
3715               if (s_info
3716                   && s_info->redundant_reason
3717                   && s_info->redundant_reason->insn
3718                   && INSN_P (s_info->redundant_reason->insn))
3719                 {
3720                   rtx rinsn = s_info->redundant_reason->insn;
3721                   if (dump_file)
3722                     fprintf (dump_file, "Locally deleting insn %d "
3723                                         "because insn %d stores the "
3724                                         "same value and couldn't be "
3725                                         "eliminated\n",
3726                                         INSN_UID (insn_info->insn),
3727                                         INSN_UID (rinsn));
3728                   delete_dead_store_insn (insn_info);
3729                 }
3730             }
3731           insn_info = insn_info->prev_insn;
3732         }
3733     }
3734 }
3735 \f
3736 /*----------------------------------------------------------------------------
3737    Seventh step.
3738
3739    Destroy everything left standing.
3740 ----------------------------------------------------------------------------*/
3741
3742 static void
3743 dse_step7 (bool global_done)
3744 {
3745   unsigned int i;
3746   group_info_t group;
3747   basic_block bb;
3748
3749   for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
3750     {
3751       free (group->offset_map_n);
3752       free (group->offset_map_p);
3753       BITMAP_FREE (group->store1_n);
3754       BITMAP_FREE (group->store1_p);
3755       BITMAP_FREE (group->store2_n);
3756       BITMAP_FREE (group->store2_p);
3757       BITMAP_FREE (group->group_kill);
3758     }
3759
3760   if (global_done)
3761     FOR_ALL_BB (bb)
3762       {
3763         bb_info_t bb_info = bb_table[bb->index];
3764         BITMAP_FREE (bb_info->gen);
3765         if (bb_info->kill)
3766           BITMAP_FREE (bb_info->kill);
3767         if (bb_info->in)
3768           BITMAP_FREE (bb_info->in);
3769         if (bb_info->out)
3770           BITMAP_FREE (bb_info->out);
3771       }
3772
3773   if (clear_alias_sets)
3774     {
3775       BITMAP_FREE (clear_alias_sets);
3776       BITMAP_FREE (disqualified_clear_alias_sets);
3777       free_alloc_pool (clear_alias_mode_pool);
3778       htab_delete (clear_alias_mode_table);
3779     }
3780
3781   end_alias_analysis ();
3782   free (bb_table);
3783   htab_delete (rtx_group_table);
3784   VEC_free (group_info_t, heap, rtx_group_vec);
3785   BITMAP_FREE (all_blocks);
3786   BITMAP_FREE (scratch);
3787
3788   free_alloc_pool (rtx_store_info_pool);
3789   free_alloc_pool (read_info_pool);
3790   free_alloc_pool (insn_info_pool);
3791   free_alloc_pool (bb_info_pool);
3792   free_alloc_pool (rtx_group_info_pool);
3793   free_alloc_pool (deferred_change_pool);
3794 }
3795
3796
3797 /* -------------------------------------------------------------------------
3798    DSE
3799    ------------------------------------------------------------------------- */
3800
3801 /* Callback for running pass_rtl_dse.  */
3802
3803 static unsigned int
3804 rest_of_handle_dse (void)
3805 {
3806   bool did_global = false;
3807
3808   df_set_flags (DF_DEFER_INSN_RESCAN);
3809
3810   /* Need the notes since we must track live hardregs in the forwards
3811      direction.  */
3812   df_note_add_problem ();
3813   df_analyze ();
3814
3815   dse_step0 ();
3816   dse_step1 ();
3817   dse_step2_init ();
3818   if (dse_step2_nospill ())
3819     {
3820       df_set_flags (DF_LR_RUN_DCE);
3821       df_analyze ();
3822       did_global = true;
3823       if (dump_file)
3824         fprintf (dump_file, "doing global processing\n");
3825       dse_step3 (false);
3826       dse_step4 ();
3827       dse_step5_nospill ();
3828     }
3829
3830   /* For the instance of dse that runs after reload, we make a special
3831      pass to process the spills.  These are special in that they are
3832      totally transparent, i.e, there is no aliasing issues that need
3833      to be considered.  This means that the wild reads that kill
3834      everything else do not apply here.  */
3835   if (clear_alias_sets && dse_step2_spill ())
3836     {
3837       if (!did_global)
3838         {
3839           df_set_flags (DF_LR_RUN_DCE);
3840           df_analyze ();
3841         }
3842       did_global = true;
3843       if (dump_file)
3844         fprintf (dump_file, "doing global spill processing\n");
3845       dse_step3 (true);
3846       dse_step4 ();
3847       dse_step5_spill ();
3848     }
3849
3850   dse_step6 ();
3851   dse_step7 (did_global);
3852
3853   if (dump_file)
3854     fprintf (dump_file, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3855              locally_deleted, globally_deleted, spill_deleted);
3856   return 0;
3857 }
3858
3859 static bool
3860 gate_dse (void)
3861 {
3862   return gate_dse1 () || gate_dse2 ();
3863 }
3864
3865 static bool
3866 gate_dse1 (void)
3867 {
3868   return optimize > 0 && flag_dse
3869     && dbg_cnt (dse1);
3870 }
3871
3872 static bool
3873 gate_dse2 (void)
3874 {
3875   return optimize > 0 && flag_dse
3876     && dbg_cnt (dse2);
3877 }
3878
3879 struct rtl_opt_pass pass_rtl_dse1 =
3880 {
3881  {
3882   RTL_PASS,
3883   "dse1",                               /* name */
3884   gate_dse1,                            /* gate */
3885   rest_of_handle_dse,                   /* execute */
3886   NULL,                                 /* sub */
3887   NULL,                                 /* next */
3888   0,                                    /* static_pass_number */
3889   TV_DSE1,                              /* tv_id */
3890   0,                                    /* properties_required */
3891   0,                                    /* properties_provided */
3892   0,                                    /* properties_destroyed */
3893   0,                                    /* todo_flags_start */
3894   TODO_dump_func |
3895   TODO_df_finish | TODO_verify_rtl_sharing |
3896   TODO_ggc_collect                      /* todo_flags_finish */
3897  }
3898 };
3899
3900 struct rtl_opt_pass pass_rtl_dse2 =
3901 {
3902  {
3903   RTL_PASS,
3904   "dse2",                               /* name */
3905   gate_dse2,                            /* gate */
3906   rest_of_handle_dse,                   /* execute */
3907   NULL,                                 /* sub */
3908   NULL,                                 /* next */
3909   0,                                    /* static_pass_number */
3910   TV_DSE2,                              /* tv_id */
3911   0,                                    /* properties_required */
3912   0,                                    /* properties_provided */
3913   0,                                    /* properties_destroyed */
3914   0,                                    /* todo_flags_start */
3915   TODO_dump_func |
3916   TODO_df_finish | TODO_verify_rtl_sharing |
3917   TODO_ggc_collect                      /* todo_flags_finish */
3918  }
3919 };