1 /* RTL dead store elimination.
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
5 Contributed by Richard Sandiford <rsandifor@codesourcery.com>
6 and Kenneth Zadeck <zadeck@naturalbridge.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
28 #include "coretypes.h"
35 #include "hard-reg-set.h"
40 #include "tree-pass.h"
41 #include "alloc-pool.h"
43 #include "insn-config.h"
51 #include "tree-flow.h"
53 /* This file contains three techniques for performing Dead Store
56 * The first technique performs dse locally on any base address. It
57 is based on the cselib which is a local value numbering technique.
58 This technique is local to a basic block but deals with a fairly
61 * The second technique performs dse globally but is restricted to
62 base addresses that are either constant or are relative to the
65 * The third technique, (which is only done after register allocation)
66 processes the spill spill slots. This differs from the second
67 technique because it takes advantage of the fact that spilling is
68 completely free from the effects of aliasing.
70 Logically, dse is a backwards dataflow problem. A store can be
71 deleted if it if cannot be reached in the backward direction by any
72 use of the value being stored. However, the local technique uses a
73 forwards scan of the basic block because cselib requires that the
74 block be processed in that order.
76 The pass is logically broken into 7 steps:
80 1) The local algorithm, as well as scanning the insns for the two
83 2) Analysis to see if the global algs are necessary. In the case
84 of stores base on a constant address, there must be at least two
85 stores to that address, to make it possible to delete some of the
86 stores. In the case of stores off of the frame or spill related
87 stores, only one store to an address is necessary because those
88 stores die at the end of the function.
90 3) Set up the global dataflow equations based on processing the
91 info parsed in the first step.
93 4) Solve the dataflow equations.
95 5) Delete the insns that the global analysis has indicated are
98 6) Delete insns that store the same value as preceeding store
99 where the earlier store couldn't be eliminated.
103 This step uses cselib and canon_rtx to build the largest expression
104 possible for each address. This pass is a forwards pass through
105 each basic block. From the point of view of the global technique,
106 the first pass could examine a block in either direction. The
107 forwards ordering is to accommodate cselib.
109 We a simplifying assumption: addresses fall into four broad
112 1) base has rtx_varies_p == false, offset is constant.
113 2) base has rtx_varies_p == false, offset variable.
114 3) base has rtx_varies_p == true, offset constant.
115 4) base has rtx_varies_p == true, offset variable.
117 The local passes are able to process all 4 kinds of addresses. The
118 global pass only handles (1).
120 The global problem is formulated as follows:
122 A store, S1, to address A, where A is not relative to the stack
123 frame, can be eliminated if all paths from S1 to the end of the
124 of the function contain another store to A before a read to A.
126 If the address A is relative to the stack frame, a store S2 to A
127 can be eliminated if there are no paths from S1 that reach the
128 end of the function that read A before another store to A. In
129 this case S2 can be deleted if there are paths to from S2 to the
130 end of the function that have no reads or writes to A. This
131 second case allows stores to the stack frame to be deleted that
132 would otherwise die when the function returns. This cannot be
133 done if stores_off_frame_dead_at_return is not true. See the doc
134 for that variable for when this variable is false.
136 The global problem is formulated as a backwards set union
137 dataflow problem where the stores are the gens and reads are the
138 kills. Set union problems are rare and require some special
139 handling given our representation of bitmaps. A straightforward
140 implementation of requires a lot of bitmaps filled with 1s.
141 These are expensive and cumbersome in our bitmap formulation so
142 care has been taken to avoid large vectors filled with 1s. See
143 the comments in bb_info and in the dataflow confluence functions
146 There are two places for further enhancements to this algorithm:
148 1) The original dse which was embedded in a pass called flow also
149 did local address forwarding. For example in
154 flow would replace the right hand side of the second insn with a
155 reference to r100. Most of the information is available to add this
156 to this pass. It has not done it because it is a lot of work in
157 the case that either r100 is assigned to between the first and
158 second insn and/or the second insn is a load of part of the value
159 stored by the first insn.
161 insn 5 in gcc.c-torture/compile/990203-1.c simple case.
162 insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
163 insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
164 insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
166 2) The cleaning up of spill code is quite profitable. It currently
167 depends on reading tea leaves and chicken entrails left by reload.
168 This pass depends on reload creating a singleton alias set for each
169 spill slot and telling the next dse pass which of these alias sets
170 are the singletons. Rather than analyze the addresses of the
171 spills, dse's spill processing just does analysis of the loads and
172 stores that use those alias sets. There are three cases where this
175 a) Reload sometimes creates the slot for one mode of access, and
176 then inserts loads and/or stores for a smaller mode. In this
177 case, the current code just punts on the slot. The proper thing
178 to do is to back out and use one bit vector position for each
179 byte of the entity associated with the slot. This depends on
180 KNOWING that reload always generates the accesses for each of the
181 bytes in some canonical (read that easy to understand several
182 passes after reload happens) way.
184 b) Reload sometimes decides that spill slot it allocated was not
185 large enough for the mode and goes back and allocates more slots
186 with the same mode and alias set. The backout in this case is a
187 little more graceful than (a). In this case the slot is unmarked
188 as being a spill slot and if final address comes out to be based
189 off the frame pointer, the global algorithm handles this slot.
191 c) For any pass that may prespill, there is currently no
192 mechanism to tell the dse pass that the slot being used has the
193 special properties that reload uses. It may be that all that is
194 required is to have those passes make the same calls that reload
195 does, assuming that the alias sets can be manipulated in the same
198 /* There are limits to the size of constant offsets we model for the
199 global problem. There are certainly test cases, that exceed this
200 limit, however, it is unlikely that there are important programs
201 that really have constant offsets this size. */
202 #define MAX_OFFSET (64 * 1024)
205 static bitmap scratch = NULL;
208 /* This structure holds information about a candidate store. */
212 /* False means this is a clobber. */
215 /* False if a single HOST_WIDE_INT bitmap is used for positions_needed. */
218 /* The id of the mem group of the base address. If rtx_varies_p is
219 true, this is -1. Otherwise, it is the index into the group
223 /* This is the cselib value. */
224 cselib_val *cse_base;
226 /* This canonized mem. */
229 /* Canonized MEM address for use by canon_true_dependence. */
232 /* If this is non-zero, it is the alias set of a spill location. */
233 alias_set_type alias_set;
235 /* The offset of the first and byte before the last byte associated
236 with the operation. */
237 HOST_WIDE_INT begin, end;
241 /* A bitmask as wide as the number of bytes in the word that
242 contains a 1 if the byte may be needed. The store is unused if
243 all of the bits are 0. This is used if IS_LARGE is false. */
244 unsigned HOST_WIDE_INT small_bitmask;
248 /* A bitmap with one bit per byte. Cleared bit means the position
249 is needed. Used if IS_LARGE is false. */
252 /* Number of set bits (i.e. unneeded bytes) in BITMAP. If it is
253 equal to END - BEGIN, the whole store is unused. */
258 /* The next store info for this insn. */
259 struct store_info *next;
261 /* The right hand side of the store. This is used if there is a
262 subsequent reload of the mems address somewhere later in the
266 /* If rhs is or holds a constant, this contains that constant,
270 /* Set if this store stores the same constant value as REDUNDANT_REASON
271 insn stored. These aren't eliminated early, because doing that
272 might prevent the earlier larger store to be eliminated. */
273 struct insn_info *redundant_reason;
276 /* Return a bitmask with the first N low bits set. */
278 static unsigned HOST_WIDE_INT
279 lowpart_bitmask (int n)
281 unsigned HOST_WIDE_INT mask = ~(unsigned HOST_WIDE_INT) 0;
282 return mask >> (HOST_BITS_PER_WIDE_INT - n);
285 typedef struct store_info *store_info_t;
286 static alloc_pool cse_store_info_pool;
287 static alloc_pool rtx_store_info_pool;
289 /* This structure holds information about a load. These are only
290 built for rtx bases. */
293 /* The id of the mem group of the base address. */
296 /* If this is non-zero, it is the alias set of a spill location. */
297 alias_set_type alias_set;
299 /* The offset of the first and byte after the last byte associated
300 with the operation. If begin == end == 0, the read did not have
301 a constant offset. */
304 /* The mem being read. */
307 /* The next read_info for this insn. */
308 struct read_info *next;
310 typedef struct read_info *read_info_t;
311 static alloc_pool read_info_pool;
314 /* One of these records is created for each insn. */
318 /* Set true if the insn contains a store but the insn itself cannot
319 be deleted. This is set if the insn is a parallel and there is
320 more than one non dead output or if the insn is in some way
324 /* This field is only used by the global algorithm. It is set true
325 if the insn contains any read of mem except for a (1). This is
326 also set if the insn is a call or has a clobber mem. If the insn
327 contains a wild read, the use_rec will be null. */
330 /* This is true only for CALL instructions which could potentially read
331 any non-frame memory location. This field is used by the global
333 bool non_frame_wild_read;
335 /* This field is only used for the processing of const functions.
336 These functions cannot read memory, but they can read the stack
337 because that is where they may get their parms. We need to be
338 this conservative because, like the store motion pass, we don't
339 consider CALL_INSN_FUNCTION_USAGE when processing call insns.
340 Moreover, we need to distinguish two cases:
341 1. Before reload (register elimination), the stores related to
342 outgoing arguments are stack pointer based and thus deemed
343 of non-constant base in this pass. This requires special
344 handling but also means that the frame pointer based stores
345 need not be killed upon encountering a const function call.
346 2. After reload, the stores related to outgoing arguments can be
347 either stack pointer or hard frame pointer based. This means
348 that we have no other choice than also killing all the frame
349 pointer based stores upon encountering a const function call.
350 This field is set after reload for const function calls. Having
351 this set is less severe than a wild read, it just means that all
352 the frame related stores are killed rather than all the stores. */
355 /* This field is only used for the processing of const functions.
356 It is set if the insn may contain a stack pointer based store. */
357 bool stack_pointer_based;
359 /* This is true if any of the sets within the store contains a
360 cselib base. Such stores can only be deleted by the local
362 bool contains_cselib_groups;
367 /* The list of mem sets or mem clobbers that are contained in this
368 insn. If the insn is deletable, it contains only one mem set.
369 But it could also contain clobbers. Insns that contain more than
370 one mem set are not deletable, but each of those mems are here in
371 order to provide info to delete other insns. */
372 store_info_t store_rec;
374 /* The linked list of mem uses in this insn. Only the reads from
375 rtx bases are listed here. The reads to cselib bases are
376 completely processed during the first scan and so are never
378 read_info_t read_rec;
380 /* The prev insn in the basic block. */
381 struct insn_info * prev_insn;
383 /* The linked list of insns that are in consideration for removal in
384 the forwards pass thru the basic block. This pointer may be
385 trash as it is not cleared when a wild read occurs. The only
386 time it is guaranteed to be correct is when the traversal starts
387 at active_local_stores. */
388 struct insn_info * next_local_store;
391 typedef struct insn_info *insn_info_t;
392 static alloc_pool insn_info_pool;
394 /* The linked list of stores that are under consideration in this
396 static insn_info_t active_local_stores;
397 static int active_local_stores_len;
402 /* Pointer to the insn info for the last insn in the block. These
403 are linked so this is how all of the insns are reached. During
404 scanning this is the current insn being scanned. */
405 insn_info_t last_insn;
407 /* The info for the global dataflow problem. */
410 /* This is set if the transfer function should and in the wild_read
411 bitmap before applying the kill and gen sets. That vector knocks
412 out most of the bits in the bitmap and thus speeds up the
414 bool apply_wild_read;
416 /* The following 4 bitvectors hold information about which positions
417 of which stores are live or dead. They are indexed by
420 /* The set of store positions that exist in this block before a wild read. */
423 /* The set of load positions that exist in this block above the
424 same position of a store. */
427 /* The set of stores that reach the top of the block without being
430 Do not represent the in if it is all ones. Note that this is
431 what the bitvector should logically be initialized to for a set
432 intersection problem. However, like the kill set, this is too
433 expensive. So initially, the in set will only be created for the
434 exit block and any block that contains a wild read. */
437 /* The set of stores that reach the bottom of the block from it's
440 Do not represent the in if it is all ones. Note that this is
441 what the bitvector should logically be initialized to for a set
442 intersection problem. However, like the kill and in set, this is
443 too expensive. So what is done is that the confluence operator
444 just initializes the vector from one of the out sets of the
445 successors of the block. */
448 /* The following bitvector is indexed by the reg number. It
449 contains the set of regs that are live at the current instruction
450 being processed. While it contains info for all of the
451 registers, only the pseudos are actually examined. It is used to
452 assure that shift sequences that are inserted do not accidently
453 clobber live hard regs. */
457 typedef struct bb_info *bb_info_t;
458 static alloc_pool bb_info_pool;
460 /* Table to hold all bb_infos. */
461 static bb_info_t *bb_table;
463 /* There is a group_info for each rtx base that is used to reference
464 memory. There are also not many of the rtx bases because they are
465 very limited in scope. */
469 /* The actual base of the address. */
472 /* The sequential id of the base. This allows us to have a
473 canonical ordering of these that is not based on addresses. */
476 /* True if there are any positions that are to be processed
478 bool process_globally;
480 /* True if the base of this group is either the frame_pointer or
481 hard_frame_pointer. */
484 /* A mem wrapped around the base pointer for the group in order to do
485 read dependency. It must be given BLKmode in order to encompass all
486 the possible offsets from the base. */
489 /* Canonized version of base_mem's address. */
492 /* These two sets of two bitmaps are used to keep track of how many
493 stores are actually referencing that position from this base. We
494 only do this for rtx bases as this will be used to assign
495 positions in the bitmaps for the global problem. Bit N is set in
496 store1 on the first store for offset N. Bit N is set in store2
497 for the second store to offset N. This is all we need since we
498 only care about offsets that have two or more stores for them.
500 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
501 for 0 and greater offsets.
503 There is one special case here, for stores into the stack frame,
504 we will or store1 into store2 before deciding which stores look
505 at globally. This is because stores to the stack frame that have
506 no other reads before the end of the function can also be
508 bitmap store1_n, store1_p, store2_n, store2_p;
510 /* These bitmaps keep track of offsets in this group escape this function.
511 An offset escapes if it corresponds to a named variable whose
512 addressable flag is set. */
513 bitmap escaped_n, escaped_p;
515 /* The positions in this bitmap have the same assignments as the in,
516 out, gen and kill bitmaps. This bitmap is all zeros except for
517 the positions that are occupied by stores for this group. */
520 /* The offset_map is used to map the offsets from this base into
521 positions in the global bitmaps. It is only created after all of
522 the all of stores have been scanned and we know which ones we
524 int *offset_map_n, *offset_map_p;
525 int offset_map_size_n, offset_map_size_p;
527 typedef struct group_info *group_info_t;
528 typedef const struct group_info *const_group_info_t;
529 static alloc_pool rtx_group_info_pool;
531 /* Tables of group_info structures, hashed by base value. */
532 static htab_t rtx_group_table;
534 /* Index into the rtx_group_vec. */
535 static int rtx_group_next_id;
537 DEF_VEC_P(group_info_t);
538 DEF_VEC_ALLOC_P(group_info_t,heap);
540 static VEC(group_info_t,heap) *rtx_group_vec;
543 /* This structure holds the set of changes that are being deferred
544 when removing read operation. See replace_read. */
545 struct deferred_change
548 /* The mem that is being replaced. */
551 /* The reg it is being replaced with. */
554 struct deferred_change *next;
557 typedef struct deferred_change *deferred_change_t;
558 static alloc_pool deferred_change_pool;
560 static deferred_change_t deferred_change_list = NULL;
562 /* This are used to hold the alias sets of spill variables. Since
563 these are never aliased and there may be a lot of them, it makes
564 sense to treat them specially. This bitvector is only allocated in
565 calls from dse_record_singleton_alias_set which currently is only
566 made during reload1. So when dse is called before reload this
567 mechanism does nothing. */
569 static bitmap clear_alias_sets = NULL;
571 /* The set of clear_alias_sets that have been disqualified because
572 there are loads or stores using a different mode than the alias set
573 was registered with. */
574 static bitmap disqualified_clear_alias_sets = NULL;
576 /* The group that holds all of the clear_alias_sets. */
577 static group_info_t clear_alias_group;
579 /* The modes of the clear_alias_sets. */
580 static htab_t clear_alias_mode_table;
582 /* Hash table element to look up the mode for an alias set. */
583 struct clear_alias_mode_holder
585 alias_set_type alias_set;
586 enum machine_mode mode;
589 static alloc_pool clear_alias_mode_pool;
591 /* This is true except if cfun->stdarg -- i.e. we cannot do
592 this for vararg functions because they play games with the frame. */
593 static bool stores_off_frame_dead_at_return;
595 /* Counter for stats. */
596 static int globally_deleted;
597 static int locally_deleted;
598 static int spill_deleted;
600 static bitmap all_blocks;
602 /* Locations that are killed by calls in the global phase. */
603 static bitmap kill_on_calls;
605 /* The number of bits used in the global bitmaps. */
606 static unsigned int current_position;
609 static bool gate_dse (void);
610 static bool gate_dse1 (void);
611 static bool gate_dse2 (void);
614 /*----------------------------------------------------------------------------
618 ----------------------------------------------------------------------------*/
620 /* Hashtable callbacks for maintaining the "bases" field of
621 store_group_info, given that the addresses are function invariants. */
624 clear_alias_mode_eq (const void *p1, const void *p2)
626 const struct clear_alias_mode_holder * h1
627 = (const struct clear_alias_mode_holder *) p1;
628 const struct clear_alias_mode_holder * h2
629 = (const struct clear_alias_mode_holder *) p2;
630 return h1->alias_set == h2->alias_set;
635 clear_alias_mode_hash (const void *p)
637 const struct clear_alias_mode_holder *holder
638 = (const struct clear_alias_mode_holder *) p;
639 return holder->alias_set;
643 /* Find the entry associated with ALIAS_SET. */
645 static struct clear_alias_mode_holder *
646 clear_alias_set_lookup (alias_set_type alias_set)
648 struct clear_alias_mode_holder tmp_holder;
651 tmp_holder.alias_set = alias_set;
652 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, NO_INSERT);
655 return (struct clear_alias_mode_holder *) *slot;
659 /* Hashtable callbacks for maintaining the "bases" field of
660 store_group_info, given that the addresses are function invariants. */
663 invariant_group_base_eq (const void *p1, const void *p2)
665 const_group_info_t gi1 = (const_group_info_t) p1;
666 const_group_info_t gi2 = (const_group_info_t) p2;
667 return rtx_equal_p (gi1->rtx_base, gi2->rtx_base);
672 invariant_group_base_hash (const void *p)
674 const_group_info_t gi = (const_group_info_t) p;
676 return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false);
680 /* Get the GROUP for BASE. Add a new group if it is not there. */
683 get_group_info (rtx base)
685 struct group_info tmp_gi;
691 /* Find the store_base_info structure for BASE, creating a new one
693 tmp_gi.rtx_base = base;
694 slot = htab_find_slot (rtx_group_table, &tmp_gi, INSERT);
695 gi = (group_info_t) *slot;
699 if (!clear_alias_group)
701 clear_alias_group = gi =
702 (group_info_t) pool_alloc (rtx_group_info_pool);
703 memset (gi, 0, sizeof (struct group_info));
704 gi->id = rtx_group_next_id++;
705 gi->store1_n = BITMAP_ALLOC (NULL);
706 gi->store1_p = BITMAP_ALLOC (NULL);
707 gi->store2_n = BITMAP_ALLOC (NULL);
708 gi->store2_p = BITMAP_ALLOC (NULL);
709 gi->escaped_p = BITMAP_ALLOC (NULL);
710 gi->escaped_n = BITMAP_ALLOC (NULL);
711 gi->group_kill = BITMAP_ALLOC (NULL);
712 gi->process_globally = false;
713 gi->offset_map_size_n = 0;
714 gi->offset_map_size_p = 0;
715 gi->offset_map_n = NULL;
716 gi->offset_map_p = NULL;
717 VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);
719 return clear_alias_group;
724 *slot = gi = (group_info_t) pool_alloc (rtx_group_info_pool);
726 gi->id = rtx_group_next_id++;
727 gi->base_mem = gen_rtx_MEM (BLKmode, base);
728 gi->canon_base_addr = canon_rtx (base);
729 gi->store1_n = BITMAP_ALLOC (NULL);
730 gi->store1_p = BITMAP_ALLOC (NULL);
731 gi->store2_n = BITMAP_ALLOC (NULL);
732 gi->store2_p = BITMAP_ALLOC (NULL);
733 gi->escaped_p = BITMAP_ALLOC (NULL);
734 gi->escaped_n = BITMAP_ALLOC (NULL);
735 gi->group_kill = BITMAP_ALLOC (NULL);
736 gi->process_globally = false;
738 (base == frame_pointer_rtx) || (base == hard_frame_pointer_rtx);
739 gi->offset_map_size_n = 0;
740 gi->offset_map_size_p = 0;
741 gi->offset_map_n = NULL;
742 gi->offset_map_p = NULL;
743 VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);
750 /* Initialization of data structures. */
756 globally_deleted = 0;
759 scratch = BITMAP_ALLOC (NULL);
760 kill_on_calls = BITMAP_ALLOC (NULL);
763 = create_alloc_pool ("rtx_store_info_pool",
764 sizeof (struct store_info), 100);
766 = create_alloc_pool ("read_info_pool",
767 sizeof (struct read_info), 100);
769 = create_alloc_pool ("insn_info_pool",
770 sizeof (struct insn_info), 100);
772 = create_alloc_pool ("bb_info_pool",
773 sizeof (struct bb_info), 100);
775 = create_alloc_pool ("rtx_group_info_pool",
776 sizeof (struct group_info), 100);
778 = create_alloc_pool ("deferred_change_pool",
779 sizeof (struct deferred_change), 10);
781 rtx_group_table = htab_create (11, invariant_group_base_hash,
782 invariant_group_base_eq, NULL);
784 bb_table = XCNEWVEC (bb_info_t, last_basic_block);
785 rtx_group_next_id = 0;
787 stores_off_frame_dead_at_return = !cfun->stdarg;
789 init_alias_analysis ();
791 if (clear_alias_sets)
792 clear_alias_group = get_group_info (NULL);
794 clear_alias_group = NULL;
799 /*----------------------------------------------------------------------------
802 Scan all of the insns. Any random ordering of the blocks is fine.
803 Each block is scanned in forward order to accommodate cselib which
804 is used to remove stores with non-constant bases.
805 ----------------------------------------------------------------------------*/
807 /* Delete all of the store_info recs from INSN_INFO. */
810 free_store_info (insn_info_t insn_info)
812 store_info_t store_info = insn_info->store_rec;
815 store_info_t next = store_info->next;
816 if (store_info->is_large)
817 BITMAP_FREE (store_info->positions_needed.large.bmap);
818 if (store_info->cse_base)
819 pool_free (cse_store_info_pool, store_info);
821 pool_free (rtx_store_info_pool, store_info);
825 insn_info->cannot_delete = true;
826 insn_info->contains_cselib_groups = false;
827 insn_info->store_rec = NULL;
830 /* Callback for for_each_inc_dec that emits an INSN that sets DEST to
831 SRC + SRCOFF before insn ARG. */
834 emit_inc_dec_insn_before (rtx mem ATTRIBUTE_UNUSED,
835 rtx op ATTRIBUTE_UNUSED,
836 rtx dest, rtx src, rtx srcoff, void *arg)
841 src = gen_rtx_PLUS (GET_MODE (src), src, srcoff);
843 /* We can reuse all operands without copying, because we are about
844 to delete the insn that contained it. */
846 emit_insn_before (gen_rtx_SET (VOIDmode, dest, src), insn);
851 /* Before we delete INSN, make sure that the auto inc/dec, if it is
852 there, is split into a separate insn. */
855 check_for_inc_dec (rtx insn)
857 rtx note = find_reg_note (insn, REG_INC, NULL_RTX);
859 for_each_inc_dec (&insn, emit_inc_dec_insn_before, insn);
863 /* Delete the insn and free all of the fields inside INSN_INFO. */
866 delete_dead_store_insn (insn_info_t insn_info)
868 read_info_t read_info;
873 check_for_inc_dec (insn_info->insn);
876 fprintf (dump_file, "Locally deleting insn %d ",
877 INSN_UID (insn_info->insn));
878 if (insn_info->store_rec->alias_set)
879 fprintf (dump_file, "alias set %d\n",
880 (int) insn_info->store_rec->alias_set);
882 fprintf (dump_file, "\n");
885 free_store_info (insn_info);
886 read_info = insn_info->read_rec;
890 read_info_t next = read_info->next;
891 pool_free (read_info_pool, read_info);
894 insn_info->read_rec = NULL;
896 delete_insn (insn_info->insn);
898 insn_info->insn = NULL;
900 insn_info->wild_read = false;
903 /* Check if EXPR can possibly escape the current function scope. */
905 can_escape (tree expr)
910 base = get_base_address (expr);
912 && !may_be_aliased (base))
917 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
921 set_usage_bits (group_info_t group, HOST_WIDE_INT offset, HOST_WIDE_INT width,
925 bool expr_escapes = can_escape (expr);
926 if (offset > -MAX_OFFSET && offset + width < MAX_OFFSET)
927 for (i=offset; i<offset+width; i++)
935 store1 = group->store1_n;
936 store2 = group->store2_n;
937 escaped = group->escaped_n;
942 store1 = group->store1_p;
943 store2 = group->store2_p;
944 escaped = group->escaped_p;
948 if (!bitmap_set_bit (store1, ai))
949 bitmap_set_bit (store2, ai);
954 if (group->offset_map_size_n < ai)
955 group->offset_map_size_n = ai;
959 if (group->offset_map_size_p < ai)
960 group->offset_map_size_p = ai;
964 bitmap_set_bit (escaped, ai);
969 reset_active_stores (void)
971 active_local_stores = NULL;
972 active_local_stores_len = 0;
975 /* Free all READ_REC of the LAST_INSN of BB_INFO. */
978 free_read_records (bb_info_t bb_info)
980 insn_info_t insn_info = bb_info->last_insn;
981 read_info_t *ptr = &insn_info->read_rec;
984 read_info_t next = (*ptr)->next;
985 if ((*ptr)->alias_set == 0)
987 pool_free (read_info_pool, *ptr);
995 /* Set the BB_INFO so that the last insn is marked as a wild read. */
998 add_wild_read (bb_info_t bb_info)
1000 insn_info_t insn_info = bb_info->last_insn;
1001 insn_info->wild_read = true;
1002 free_read_records (bb_info);
1003 reset_active_stores ();
1006 /* Set the BB_INFO so that the last insn is marked as a wild read of
1007 non-frame locations. */
1010 add_non_frame_wild_read (bb_info_t bb_info)
1012 insn_info_t insn_info = bb_info->last_insn;
1013 insn_info->non_frame_wild_read = true;
1014 free_read_records (bb_info);
1015 reset_active_stores ();
1018 /* Return true if X is a constant or one of the registers that behave
1019 as a constant over the life of a function. This is equivalent to
1020 !rtx_varies_p for memory addresses. */
1023 const_or_frame_p (rtx x)
1025 switch (GET_CODE (x))
1036 /* Note that we have to test for the actual rtx used for the frame
1037 and arg pointers and not just the register number in case we have
1038 eliminated the frame and/or arg pointer and are using it
1040 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
1041 /* The arg pointer varies if it is not a fixed register. */
1042 || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
1043 || x == pic_offset_table_rtx)
1052 /* Take all reasonable action to put the address of MEM into the form
1053 that we can do analysis on.
1055 The gold standard is to get the address into the form: address +
1056 OFFSET where address is something that rtx_varies_p considers a
1057 constant. When we can get the address in this form, we can do
1058 global analysis on it. Note that for constant bases, address is
1059 not actually returned, only the group_id. The address can be
1062 If that fails, we try cselib to get a value we can at least use
1063 locally. If that fails we return false.
1065 The GROUP_ID is set to -1 for cselib bases and the index of the
1066 group for non_varying bases.
1068 FOR_READ is true if this is a mem read and false if not. */
1071 canon_address (rtx mem,
1072 alias_set_type *alias_set_out,
1074 HOST_WIDE_INT *offset,
1077 enum machine_mode address_mode
1078 = targetm.addr_space.address_mode (MEM_ADDR_SPACE (mem));
1079 rtx mem_address = XEXP (mem, 0);
1080 rtx expanded_address, address;
1083 /* Make sure that cselib is has initialized all of the operands of
1084 the address before asking it to do the subst. */
1086 if (clear_alias_sets)
1088 /* If this is a spill, do not do any further processing. */
1089 alias_set_type alias_set = MEM_ALIAS_SET (mem);
1091 fprintf (dump_file, "found alias set %d\n", (int) alias_set);
1092 if (bitmap_bit_p (clear_alias_sets, alias_set))
1094 struct clear_alias_mode_holder *entry
1095 = clear_alias_set_lookup (alias_set);
1097 /* If the modes do not match, we cannot process this set. */
1098 if (entry->mode != GET_MODE (mem))
1102 "disqualifying alias set %d, (%s) != (%s)\n",
1103 (int) alias_set, GET_MODE_NAME (entry->mode),
1104 GET_MODE_NAME (GET_MODE (mem)));
1106 bitmap_set_bit (disqualified_clear_alias_sets, alias_set);
1110 *alias_set_out = alias_set;
1111 *group_id = clear_alias_group->id;
1118 cselib_lookup (mem_address, address_mode, 1, GET_MODE (mem));
1122 fprintf (dump_file, " mem: ");
1123 print_inline_rtx (dump_file, mem_address, 0);
1124 fprintf (dump_file, "\n");
1127 /* First see if just canon_rtx (mem_address) is const or frame,
1128 if not, try cselib_expand_value_rtx and call canon_rtx on that. */
1130 for (expanded = 0; expanded < 2; expanded++)
1134 /* Use cselib to replace all of the reg references with the full
1135 expression. This will take care of the case where we have
1137 r_x = base + offset;
1142 val = *(base + offset); */
1144 expanded_address = cselib_expand_value_rtx (mem_address,
1147 /* If this fails, just go with the address from first
1149 if (!expanded_address)
1153 expanded_address = mem_address;
1155 /* Split the address into canonical BASE + OFFSET terms. */
1156 address = canon_rtx (expanded_address);
1164 fprintf (dump_file, "\n after cselib_expand address: ");
1165 print_inline_rtx (dump_file, expanded_address, 0);
1166 fprintf (dump_file, "\n");
1169 fprintf (dump_file, "\n after canon_rtx address: ");
1170 print_inline_rtx (dump_file, address, 0);
1171 fprintf (dump_file, "\n");
1174 if (GET_CODE (address) == CONST)
1175 address = XEXP (address, 0);
1177 if (GET_CODE (address) == PLUS
1178 && CONST_INT_P (XEXP (address, 1)))
1180 *offset = INTVAL (XEXP (address, 1));
1181 address = XEXP (address, 0);
1184 if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem))
1185 && const_or_frame_p (address))
1187 group_info_t group = get_group_info (address);
1190 fprintf (dump_file, " gid=%d offset=%d \n",
1191 group->id, (int)*offset);
1193 *group_id = group->id;
1198 *base = cselib_lookup (address, address_mode, true, GET_MODE (mem));
1204 fprintf (dump_file, " no cselib val - should be a wild read.\n");
1208 fprintf (dump_file, " varying cselib base=%u:%u offset = %d\n",
1209 (*base)->uid, (*base)->hash, (int)*offset);
1214 /* Clear the rhs field from the active_local_stores array. */
1217 clear_rhs_from_active_local_stores (void)
1219 insn_info_t ptr = active_local_stores;
1223 store_info_t store_info = ptr->store_rec;
1224 /* Skip the clobbers. */
1225 while (!store_info->is_set)
1226 store_info = store_info->next;
1228 store_info->rhs = NULL;
1229 store_info->const_rhs = NULL;
1231 ptr = ptr->next_local_store;
1236 /* Mark byte POS bytes from the beginning of store S_INFO as unneeded. */
1239 set_position_unneeded (store_info_t s_info, int pos)
1241 if (__builtin_expect (s_info->is_large, false))
1243 if (bitmap_set_bit (s_info->positions_needed.large.bmap, pos))
1244 s_info->positions_needed.large.count++;
1247 s_info->positions_needed.small_bitmask
1248 &= ~(((unsigned HOST_WIDE_INT) 1) << pos);
1251 /* Mark the whole store S_INFO as unneeded. */
1254 set_all_positions_unneeded (store_info_t s_info)
1256 if (__builtin_expect (s_info->is_large, false))
1258 int pos, end = s_info->end - s_info->begin;
1259 for (pos = 0; pos < end; pos++)
1260 bitmap_set_bit (s_info->positions_needed.large.bmap, pos);
1261 s_info->positions_needed.large.count = end;
1264 s_info->positions_needed.small_bitmask = (unsigned HOST_WIDE_INT) 0;
1267 /* Return TRUE if any bytes from S_INFO store are needed. */
1270 any_positions_needed_p (store_info_t s_info)
1272 if (__builtin_expect (s_info->is_large, false))
1273 return (s_info->positions_needed.large.count
1274 < s_info->end - s_info->begin);
1276 return (s_info->positions_needed.small_bitmask
1277 != (unsigned HOST_WIDE_INT) 0);
1280 /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
1281 store are needed. */
1284 all_positions_needed_p (store_info_t s_info, int start, int width)
1286 if (__builtin_expect (s_info->is_large, false))
1288 int end = start + width;
1290 if (bitmap_bit_p (s_info->positions_needed.large.bmap, start++))
1296 unsigned HOST_WIDE_INT mask = lowpart_bitmask (width) << start;
1297 return (s_info->positions_needed.small_bitmask & mask) == mask;
1302 static rtx get_stored_val (store_info_t, enum machine_mode, HOST_WIDE_INT,
1303 HOST_WIDE_INT, basic_block, bool);
1306 /* BODY is an instruction pattern that belongs to INSN. Return 1 if
1307 there is a candidate store, after adding it to the appropriate
1308 local store group if so. */
1311 record_store (rtx body, bb_info_t bb_info)
1313 rtx mem, rhs, const_rhs, mem_addr;
1314 HOST_WIDE_INT offset = 0;
1315 HOST_WIDE_INT width = 0;
1316 alias_set_type spill_alias_set;
1317 insn_info_t insn_info = bb_info->last_insn;
1318 store_info_t store_info = NULL;
1320 cselib_val *base = NULL;
1321 insn_info_t ptr, last, redundant_reason;
1322 bool store_is_unused;
1324 if (GET_CODE (body) != SET && GET_CODE (body) != CLOBBER)
1327 mem = SET_DEST (body);
1329 /* If this is not used, then this cannot be used to keep the insn
1330 from being deleted. On the other hand, it does provide something
1331 that can be used to prove that another store is dead. */
1333 = (find_reg_note (insn_info->insn, REG_UNUSED, mem) != NULL);
1335 /* Check whether that value is a suitable memory location. */
1338 /* If the set or clobber is unused, then it does not effect our
1339 ability to get rid of the entire insn. */
1340 if (!store_is_unused)
1341 insn_info->cannot_delete = true;
1345 /* At this point we know mem is a mem. */
1346 if (GET_MODE (mem) == BLKmode)
1348 if (GET_CODE (XEXP (mem, 0)) == SCRATCH)
1351 fprintf (dump_file, " adding wild read for (clobber (mem:BLK (scratch))\n");
1352 add_wild_read (bb_info);
1353 insn_info->cannot_delete = true;
1356 /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
1357 as memset (addr, 0, 36); */
1358 else if (!MEM_SIZE (mem)
1359 || !CONST_INT_P (MEM_SIZE (mem))
1360 || GET_CODE (body) != SET
1361 || INTVAL (MEM_SIZE (mem)) <= 0
1362 || INTVAL (MEM_SIZE (mem)) > MAX_OFFSET
1363 || !CONST_INT_P (SET_SRC (body)))
1365 if (!store_is_unused)
1367 /* If the set or clobber is unused, then it does not effect our
1368 ability to get rid of the entire insn. */
1369 insn_info->cannot_delete = true;
1370 clear_rhs_from_active_local_stores ();
1376 /* We can still process a volatile mem, we just cannot delete it. */
1377 if (MEM_VOLATILE_P (mem))
1378 insn_info->cannot_delete = true;
1380 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
1382 clear_rhs_from_active_local_stores ();
1386 if (GET_MODE (mem) == BLKmode)
1387 width = INTVAL (MEM_SIZE (mem));
1390 width = GET_MODE_SIZE (GET_MODE (mem));
1391 gcc_assert ((unsigned) width <= HOST_BITS_PER_WIDE_INT);
1394 if (spill_alias_set)
1396 bitmap store1 = clear_alias_group->store1_p;
1397 bitmap store2 = clear_alias_group->store2_p;
1399 gcc_assert (GET_MODE (mem) != BLKmode);
1401 if (!bitmap_set_bit (store1, spill_alias_set))
1402 bitmap_set_bit (store2, spill_alias_set);
1404 if (clear_alias_group->offset_map_size_p < spill_alias_set)
1405 clear_alias_group->offset_map_size_p = spill_alias_set;
1407 store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1410 fprintf (dump_file, " processing spill store %d(%s)\n",
1411 (int) spill_alias_set, GET_MODE_NAME (GET_MODE (mem)));
1413 else if (group_id >= 0)
1415 /* In the restrictive case where the base is a constant or the
1416 frame pointer we can do global analysis. */
1419 = VEC_index (group_info_t, rtx_group_vec, group_id);
1420 tree expr = MEM_EXPR (mem);
1422 store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1423 set_usage_bits (group, offset, width, expr);
1426 fprintf (dump_file, " processing const base store gid=%d[%d..%d)\n",
1427 group_id, (int)offset, (int)(offset+width));
1431 rtx base_term = find_base_term (XEXP (mem, 0));
1433 || (GET_CODE (base_term) == ADDRESS
1434 && GET_MODE (base_term) == Pmode
1435 && XEXP (base_term, 0) == stack_pointer_rtx))
1436 insn_info->stack_pointer_based = true;
1437 insn_info->contains_cselib_groups = true;
1439 store_info = (store_info_t) pool_alloc (cse_store_info_pool);
1443 fprintf (dump_file, " processing cselib store [%d..%d)\n",
1444 (int)offset, (int)(offset+width));
1447 const_rhs = rhs = NULL_RTX;
1448 if (GET_CODE (body) == SET
1449 /* No place to keep the value after ra. */
1450 && !reload_completed
1451 && (REG_P (SET_SRC (body))
1452 || GET_CODE (SET_SRC (body)) == SUBREG
1453 || CONSTANT_P (SET_SRC (body)))
1454 && !MEM_VOLATILE_P (mem)
1455 /* Sometimes the store and reload is used for truncation and
1457 && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
1459 rhs = SET_SRC (body);
1460 if (CONSTANT_P (rhs))
1462 else if (body == PATTERN (insn_info->insn))
1464 rtx tem = find_reg_note (insn_info->insn, REG_EQUAL, NULL_RTX);
1465 if (tem && CONSTANT_P (XEXP (tem, 0)))
1466 const_rhs = XEXP (tem, 0);
1468 if (const_rhs == NULL_RTX && REG_P (rhs))
1470 rtx tem = cselib_expand_value_rtx (rhs, scratch, 5);
1472 if (tem && CONSTANT_P (tem))
1477 /* Check to see if this stores causes some other stores to be
1479 ptr = active_local_stores;
1481 redundant_reason = NULL;
1482 mem = canon_rtx (mem);
1483 /* For alias_set != 0 canon_true_dependence should be never called. */
1484 if (spill_alias_set)
1485 mem_addr = NULL_RTX;
1489 mem_addr = base->val_rtx;
1493 = VEC_index (group_info_t, rtx_group_vec, group_id);
1494 mem_addr = group->canon_base_addr;
1497 mem_addr = plus_constant (mem_addr, offset);
1502 insn_info_t next = ptr->next_local_store;
1503 store_info_t s_info = ptr->store_rec;
1506 /* Skip the clobbers. We delete the active insn if this insn
1507 shadows the set. To have been put on the active list, it
1508 has exactly on set. */
1509 while (!s_info->is_set)
1510 s_info = s_info->next;
1512 if (s_info->alias_set != spill_alias_set)
1514 else if (s_info->alias_set)
1516 struct clear_alias_mode_holder *entry
1517 = clear_alias_set_lookup (s_info->alias_set);
1518 /* Generally, spills cannot be processed if and of the
1519 references to the slot have a different mode. But if
1520 we are in the same block and mode is exactly the same
1521 between this store and one before in the same block,
1522 we can still delete it. */
1523 if ((GET_MODE (mem) == GET_MODE (s_info->mem))
1524 && (GET_MODE (mem) == entry->mode))
1527 set_all_positions_unneeded (s_info);
1530 fprintf (dump_file, " trying spill store in insn=%d alias_set=%d\n",
1531 INSN_UID (ptr->insn), (int) s_info->alias_set);
1533 else if ((s_info->group_id == group_id)
1534 && (s_info->cse_base == base))
1538 fprintf (dump_file, " trying store in insn=%d gid=%d[%d..%d)\n",
1539 INSN_UID (ptr->insn), s_info->group_id,
1540 (int)s_info->begin, (int)s_info->end);
1542 /* Even if PTR won't be eliminated as unneeded, if both
1543 PTR and this insn store the same constant value, we might
1544 eliminate this insn instead. */
1545 if (s_info->const_rhs
1547 && offset >= s_info->begin
1548 && offset + width <= s_info->end
1549 && all_positions_needed_p (s_info, offset - s_info->begin,
1552 if (GET_MODE (mem) == BLKmode)
1554 if (GET_MODE (s_info->mem) == BLKmode
1555 && s_info->const_rhs == const_rhs)
1556 redundant_reason = ptr;
1558 else if (s_info->const_rhs == const0_rtx
1559 && const_rhs == const0_rtx)
1560 redundant_reason = ptr;
1565 val = get_stored_val (s_info, GET_MODE (mem),
1566 offset, offset + width,
1567 BLOCK_FOR_INSN (insn_info->insn),
1569 if (get_insns () != NULL)
1572 if (val && rtx_equal_p (val, const_rhs))
1573 redundant_reason = ptr;
1577 for (i = MAX (offset, s_info->begin);
1578 i < offset + width && i < s_info->end;
1580 set_position_unneeded (s_info, i - s_info->begin);
1582 else if (s_info->rhs)
1583 /* Need to see if it is possible for this store to overwrite
1584 the value of store_info. If it is, set the rhs to NULL to
1585 keep it from being used to remove a load. */
1587 if (canon_true_dependence (s_info->mem,
1588 GET_MODE (s_info->mem),
1590 mem, mem_addr, rtx_varies_p))
1593 s_info->const_rhs = NULL;
1597 /* An insn can be deleted if every position of every one of
1598 its s_infos is zero. */
1599 if (any_positions_needed_p (s_info))
1604 insn_info_t insn_to_delete = ptr;
1606 active_local_stores_len--;
1608 last->next_local_store = ptr->next_local_store;
1610 active_local_stores = ptr->next_local_store;
1612 if (!insn_to_delete->cannot_delete)
1613 delete_dead_store_insn (insn_to_delete);
1621 /* Finish filling in the store_info. */
1622 store_info->next = insn_info->store_rec;
1623 insn_info->store_rec = store_info;
1624 store_info->mem = mem;
1625 store_info->alias_set = spill_alias_set;
1626 store_info->mem_addr = mem_addr;
1627 store_info->cse_base = base;
1628 if (width > HOST_BITS_PER_WIDE_INT)
1630 store_info->is_large = true;
1631 store_info->positions_needed.large.count = 0;
1632 store_info->positions_needed.large.bmap = BITMAP_ALLOC (NULL);
1636 store_info->is_large = false;
1637 store_info->positions_needed.small_bitmask = lowpart_bitmask (width);
1639 store_info->group_id = group_id;
1640 store_info->begin = offset;
1641 store_info->end = offset + width;
1642 store_info->is_set = GET_CODE (body) == SET;
1643 store_info->rhs = rhs;
1644 store_info->const_rhs = const_rhs;
1645 store_info->redundant_reason = redundant_reason;
1647 /* If this is a clobber, we return 0. We will only be able to
1648 delete this insn if there is only one store USED store, but we
1649 can use the clobber to delete other stores earlier. */
1650 return store_info->is_set ? 1 : 0;
1655 dump_insn_info (const char * start, insn_info_t insn_info)
1657 fprintf (dump_file, "%s insn=%d %s\n", start,
1658 INSN_UID (insn_info->insn),
1659 insn_info->store_rec ? "has store" : "naked");
1663 /* If the modes are different and the value's source and target do not
1664 line up, we need to extract the value from lower part of the rhs of
1665 the store, shift it, and then put it into a form that can be shoved
1666 into the read_insn. This function generates a right SHIFT of a
1667 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The
1668 shift sequence is returned or NULL if we failed to find a
1672 find_shift_sequence (int access_size,
1673 store_info_t store_info,
1674 enum machine_mode read_mode,
1675 int shift, bool speed, bool require_cst)
1677 enum machine_mode store_mode = GET_MODE (store_info->mem);
1678 enum machine_mode new_mode;
1679 rtx read_reg = NULL;
1681 /* Some machines like the x86 have shift insns for each size of
1682 operand. Other machines like the ppc or the ia-64 may only have
1683 shift insns that shift values within 32 or 64 bit registers.
1684 This loop tries to find the smallest shift insn that will right
1685 justify the value we want to read but is available in one insn on
1688 for (new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
1690 GET_MODE_BITSIZE (new_mode) <= BITS_PER_WORD;
1691 new_mode = GET_MODE_WIDER_MODE (new_mode))
1693 rtx target, new_reg, shift_seq, insn, new_lhs;
1696 /* If a constant was stored into memory, try to simplify it here,
1697 otherwise the cost of the shift might preclude this optimization
1698 e.g. at -Os, even when no actual shift will be needed. */
1699 if (store_info->const_rhs)
1701 unsigned int byte = subreg_lowpart_offset (new_mode, store_mode);
1702 rtx ret = simplify_subreg (new_mode, store_info->const_rhs,
1704 if (ret && CONSTANT_P (ret))
1706 ret = simplify_const_binary_operation (LSHIFTRT, new_mode,
1707 ret, GEN_INT (shift));
1708 if (ret && CONSTANT_P (ret))
1710 byte = subreg_lowpart_offset (read_mode, new_mode);
1711 ret = simplify_subreg (read_mode, ret, new_mode, byte);
1712 if (ret && CONSTANT_P (ret)
1713 && rtx_cost (ret, SET, speed) <= COSTS_N_INSNS (1))
1722 /* Try a wider mode if truncating the store mode to NEW_MODE
1723 requires a real instruction. */
1724 if (GET_MODE_BITSIZE (new_mode) < GET_MODE_BITSIZE (store_mode)
1725 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (new_mode),
1726 GET_MODE_BITSIZE (store_mode)))
1729 /* Also try a wider mode if the necessary punning is either not
1730 desirable or not possible. */
1731 if (!CONSTANT_P (store_info->rhs)
1732 && !MODES_TIEABLE_P (new_mode, store_mode))
1735 new_reg = gen_reg_rtx (new_mode);
1739 /* In theory we could also check for an ashr. Ian Taylor knows
1740 of one dsp where the cost of these two was not the same. But
1741 this really is a rare case anyway. */
1742 target = expand_binop (new_mode, lshr_optab, new_reg,
1743 GEN_INT (shift), new_reg, 1, OPTAB_DIRECT);
1745 shift_seq = get_insns ();
1748 if (target != new_reg || shift_seq == NULL)
1752 for (insn = shift_seq; insn != NULL_RTX; insn = NEXT_INSN (insn))
1754 cost += insn_rtx_cost (PATTERN (insn), speed);
1756 /* The computation up to here is essentially independent
1757 of the arguments and could be precomputed. It may
1758 not be worth doing so. We could precompute if
1759 worthwhile or at least cache the results. The result
1760 technically depends on both SHIFT and ACCESS_SIZE,
1761 but in practice the answer will depend only on ACCESS_SIZE. */
1763 if (cost > COSTS_N_INSNS (1))
1766 new_lhs = extract_low_bits (new_mode, store_mode,
1767 copy_rtx (store_info->rhs));
1768 if (new_lhs == NULL_RTX)
1771 /* We found an acceptable shift. Generate a move to
1772 take the value from the store and put it into the
1773 shift pseudo, then shift it, then generate another
1774 move to put in into the target of the read. */
1775 emit_move_insn (new_reg, new_lhs);
1776 emit_insn (shift_seq);
1777 read_reg = extract_low_bits (read_mode, new_mode, new_reg);
1785 /* Call back for note_stores to find the hard regs set or clobbered by
1786 insn. Data is a bitmap of the hardregs set so far. */
1789 look_for_hardregs (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
1791 bitmap regs_set = (bitmap) data;
1794 && HARD_REGISTER_P (x))
1796 unsigned int regno = REGNO (x);
1797 bitmap_set_range (regs_set, regno,
1798 hard_regno_nregs[regno][GET_MODE (x)]);
1802 /* Helper function for replace_read and record_store.
1803 Attempt to return a value stored in STORE_INFO, from READ_BEGIN
1804 to one before READ_END bytes read in READ_MODE. Return NULL
1805 if not successful. If REQUIRE_CST is true, return always constant. */
1808 get_stored_val (store_info_t store_info, enum machine_mode read_mode,
1809 HOST_WIDE_INT read_begin, HOST_WIDE_INT read_end,
1810 basic_block bb, bool require_cst)
1812 enum machine_mode store_mode = GET_MODE (store_info->mem);
1814 int access_size; /* In bytes. */
1817 /* To get here the read is within the boundaries of the write so
1818 shift will never be negative. Start out with the shift being in
1820 if (store_mode == BLKmode)
1822 else if (BYTES_BIG_ENDIAN)
1823 shift = store_info->end - read_end;
1825 shift = read_begin - store_info->begin;
1827 access_size = shift + GET_MODE_SIZE (read_mode);
1829 /* From now on it is bits. */
1830 shift *= BITS_PER_UNIT;
1833 read_reg = find_shift_sequence (access_size, store_info, read_mode, shift,
1834 optimize_bb_for_speed_p (bb),
1836 else if (store_mode == BLKmode)
1838 /* The store is a memset (addr, const_val, const_size). */
1839 gcc_assert (CONST_INT_P (store_info->rhs));
1840 store_mode = int_mode_for_mode (read_mode);
1841 if (store_mode == BLKmode)
1842 read_reg = NULL_RTX;
1843 else if (store_info->rhs == const0_rtx)
1844 read_reg = extract_low_bits (read_mode, store_mode, const0_rtx);
1845 else if (GET_MODE_BITSIZE (store_mode) > HOST_BITS_PER_WIDE_INT
1846 || BITS_PER_UNIT >= HOST_BITS_PER_WIDE_INT)
1847 read_reg = NULL_RTX;
1850 unsigned HOST_WIDE_INT c
1851 = INTVAL (store_info->rhs)
1852 & (((HOST_WIDE_INT) 1 << BITS_PER_UNIT) - 1);
1853 int shift = BITS_PER_UNIT;
1854 while (shift < HOST_BITS_PER_WIDE_INT)
1859 read_reg = GEN_INT (trunc_int_for_mode (c, store_mode));
1860 read_reg = extract_low_bits (read_mode, store_mode, read_reg);
1863 else if (store_info->const_rhs
1865 || GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode)))
1866 read_reg = extract_low_bits (read_mode, store_mode,
1867 copy_rtx (store_info->const_rhs));
1869 read_reg = extract_low_bits (read_mode, store_mode,
1870 copy_rtx (store_info->rhs));
1871 if (require_cst && read_reg && !CONSTANT_P (read_reg))
1872 read_reg = NULL_RTX;
1876 /* Take a sequence of:
1899 Depending on the alignment and the mode of the store and
1903 The STORE_INFO and STORE_INSN are for the store and READ_INFO
1904 and READ_INSN are for the read. Return true if the replacement
1908 replace_read (store_info_t store_info, insn_info_t store_insn,
1909 read_info_t read_info, insn_info_t read_insn, rtx *loc,
1912 enum machine_mode store_mode = GET_MODE (store_info->mem);
1913 enum machine_mode read_mode = GET_MODE (read_info->mem);
1914 rtx insns, this_insn, read_reg;
1920 /* Create a sequence of instructions to set up the read register.
1921 This sequence goes immediately before the store and its result
1922 is read by the load.
1924 We need to keep this in perspective. We are replacing a read
1925 with a sequence of insns, but the read will almost certainly be
1926 in cache, so it is not going to be an expensive one. Thus, we
1927 are not willing to do a multi insn shift or worse a subroutine
1928 call to get rid of the read. */
1930 fprintf (dump_file, "trying to replace %smode load in insn %d"
1931 " from %smode store in insn %d\n",
1932 GET_MODE_NAME (read_mode), INSN_UID (read_insn->insn),
1933 GET_MODE_NAME (store_mode), INSN_UID (store_insn->insn));
1935 bb = BLOCK_FOR_INSN (read_insn->insn);
1936 read_reg = get_stored_val (store_info,
1937 read_mode, read_info->begin, read_info->end,
1939 if (read_reg == NULL_RTX)
1943 fprintf (dump_file, " -- could not extract bits of stored value\n");
1946 /* Force the value into a new register so that it won't be clobbered
1947 between the store and the load. */
1948 read_reg = copy_to_mode_reg (read_mode, read_reg);
1949 insns = get_insns ();
1952 if (insns != NULL_RTX)
1954 /* Now we have to scan the set of new instructions to see if the
1955 sequence contains and sets of hardregs that happened to be
1956 live at this point. For instance, this can happen if one of
1957 the insns sets the CC and the CC happened to be live at that
1958 point. This does occasionally happen, see PR 37922. */
1959 bitmap regs_set = BITMAP_ALLOC (NULL);
1961 for (this_insn = insns; this_insn != NULL_RTX; this_insn = NEXT_INSN (this_insn))
1962 note_stores (PATTERN (this_insn), look_for_hardregs, regs_set);
1964 bitmap_and_into (regs_set, regs_live);
1965 if (!bitmap_empty_p (regs_set))
1970 "abandoning replacement because sequence clobbers live hardregs:");
1971 df_print_regset (dump_file, regs_set);
1974 BITMAP_FREE (regs_set);
1977 BITMAP_FREE (regs_set);
1980 if (validate_change (read_insn->insn, loc, read_reg, 0))
1982 deferred_change_t deferred_change =
1983 (deferred_change_t) pool_alloc (deferred_change_pool);
1985 /* Insert this right before the store insn where it will be safe
1986 from later insns that might change it before the read. */
1987 emit_insn_before (insns, store_insn->insn);
1989 /* And now for the kludge part: cselib croaks if you just
1990 return at this point. There are two reasons for this:
1992 1) Cselib has an idea of how many pseudos there are and
1993 that does not include the new ones we just added.
1995 2) Cselib does not know about the move insn we added
1996 above the store_info, and there is no way to tell it
1997 about it, because it has "moved on".
1999 Problem (1) is fixable with a certain amount of engineering.
2000 Problem (2) is requires starting the bb from scratch. This
2003 So we are just going to have to lie. The move/extraction
2004 insns are not really an issue, cselib did not see them. But
2005 the use of the new pseudo read_insn is a real problem because
2006 cselib has not scanned this insn. The way that we solve this
2007 problem is that we are just going to put the mem back for now
2008 and when we are finished with the block, we undo this. We
2009 keep a table of mems to get rid of. At the end of the basic
2010 block we can put them back. */
2012 *loc = read_info->mem;
2013 deferred_change->next = deferred_change_list;
2014 deferred_change_list = deferred_change;
2015 deferred_change->loc = loc;
2016 deferred_change->reg = read_reg;
2018 /* Get rid of the read_info, from the point of view of the
2019 rest of dse, play like this read never happened. */
2020 read_insn->read_rec = read_info->next;
2021 pool_free (read_info_pool, read_info);
2024 fprintf (dump_file, " -- replaced the loaded MEM with ");
2025 print_simple_rtl (dump_file, read_reg);
2026 fprintf (dump_file, "\n");
2034 fprintf (dump_file, " -- replacing the loaded MEM with ");
2035 print_simple_rtl (dump_file, read_reg);
2036 fprintf (dump_file, " led to an invalid instruction\n");
2042 /* A for_each_rtx callback in which DATA is the bb_info. Check to see
2043 if LOC is a mem and if it is look at the address and kill any
2044 appropriate stores that may be active. */
2047 check_mem_read_rtx (rtx *loc, void *data)
2049 rtx mem = *loc, mem_addr;
2051 insn_info_t insn_info;
2052 HOST_WIDE_INT offset = 0;
2053 HOST_WIDE_INT width = 0;
2054 alias_set_type spill_alias_set = 0;
2055 cselib_val *base = NULL;
2057 read_info_t read_info;
2059 if (!mem || !MEM_P (mem))
2062 bb_info = (bb_info_t) data;
2063 insn_info = bb_info->last_insn;
2065 if ((MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2066 || (MEM_VOLATILE_P (mem)))
2069 fprintf (dump_file, " adding wild read, volatile or barrier.\n");
2070 add_wild_read (bb_info);
2071 insn_info->cannot_delete = true;
2075 /* If it is reading readonly mem, then there can be no conflict with
2077 if (MEM_READONLY_P (mem))
2080 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
2083 fprintf (dump_file, " adding wild read, canon_address failure.\n");
2084 add_wild_read (bb_info);
2088 if (GET_MODE (mem) == BLKmode)
2091 width = GET_MODE_SIZE (GET_MODE (mem));
2093 read_info = (read_info_t) pool_alloc (read_info_pool);
2094 read_info->group_id = group_id;
2095 read_info->mem = mem;
2096 read_info->alias_set = spill_alias_set;
2097 read_info->begin = offset;
2098 read_info->end = offset + width;
2099 read_info->next = insn_info->read_rec;
2100 insn_info->read_rec = read_info;
2101 /* For alias_set != 0 canon_true_dependence should be never called. */
2102 if (spill_alias_set)
2103 mem_addr = NULL_RTX;
2107 mem_addr = base->val_rtx;
2111 = VEC_index (group_info_t, rtx_group_vec, group_id);
2112 mem_addr = group->canon_base_addr;
2115 mem_addr = plus_constant (mem_addr, offset);
2118 /* We ignore the clobbers in store_info. The is mildly aggressive,
2119 but there really should not be a clobber followed by a read. */
2121 if (spill_alias_set)
2123 insn_info_t i_ptr = active_local_stores;
2124 insn_info_t last = NULL;
2127 fprintf (dump_file, " processing spill load %d\n",
2128 (int) spill_alias_set);
2132 store_info_t store_info = i_ptr->store_rec;
2134 /* Skip the clobbers. */
2135 while (!store_info->is_set)
2136 store_info = store_info->next;
2138 if (store_info->alias_set == spill_alias_set)
2141 dump_insn_info ("removing from active", i_ptr);
2143 active_local_stores_len--;
2145 last->next_local_store = i_ptr->next_local_store;
2147 active_local_stores = i_ptr->next_local_store;
2151 i_ptr = i_ptr->next_local_store;
2154 else if (group_id >= 0)
2156 /* This is the restricted case where the base is a constant or
2157 the frame pointer and offset is a constant. */
2158 insn_info_t i_ptr = active_local_stores;
2159 insn_info_t last = NULL;
2164 fprintf (dump_file, " processing const load gid=%d[BLK]\n",
2167 fprintf (dump_file, " processing const load gid=%d[%d..%d)\n",
2168 group_id, (int)offset, (int)(offset+width));
2173 bool remove = false;
2174 store_info_t store_info = i_ptr->store_rec;
2176 /* Skip the clobbers. */
2177 while (!store_info->is_set)
2178 store_info = store_info->next;
2180 /* There are three cases here. */
2181 if (store_info->group_id < 0)
2182 /* We have a cselib store followed by a read from a
2185 = canon_true_dependence (store_info->mem,
2186 GET_MODE (store_info->mem),
2187 store_info->mem_addr,
2188 mem, mem_addr, rtx_varies_p);
2190 else if (group_id == store_info->group_id)
2192 /* This is a block mode load. We may get lucky and
2193 canon_true_dependence may save the day. */
2196 = canon_true_dependence (store_info->mem,
2197 GET_MODE (store_info->mem),
2198 store_info->mem_addr,
2199 mem, mem_addr, rtx_varies_p);
2201 /* If this read is just reading back something that we just
2202 stored, rewrite the read. */
2206 && offset >= store_info->begin
2207 && offset + width <= store_info->end
2208 && all_positions_needed_p (store_info,
2209 offset - store_info->begin,
2211 && replace_read (store_info, i_ptr, read_info,
2212 insn_info, loc, bb_info->regs_live))
2215 /* The bases are the same, just see if the offsets
2217 if ((offset < store_info->end)
2218 && (offset + width > store_info->begin))
2224 The else case that is missing here is that the
2225 bases are constant but different. There is nothing
2226 to do here because there is no overlap. */
2231 dump_insn_info ("removing from active", i_ptr);
2233 active_local_stores_len--;
2235 last->next_local_store = i_ptr->next_local_store;
2237 active_local_stores = i_ptr->next_local_store;
2241 i_ptr = i_ptr->next_local_store;
2246 insn_info_t i_ptr = active_local_stores;
2247 insn_info_t last = NULL;
2250 fprintf (dump_file, " processing cselib load mem:");
2251 print_inline_rtx (dump_file, mem, 0);
2252 fprintf (dump_file, "\n");
2257 bool remove = false;
2258 store_info_t store_info = i_ptr->store_rec;
2261 fprintf (dump_file, " processing cselib load against insn %d\n",
2262 INSN_UID (i_ptr->insn));
2264 /* Skip the clobbers. */
2265 while (!store_info->is_set)
2266 store_info = store_info->next;
2268 /* If this read is just reading back something that we just
2269 stored, rewrite the read. */
2271 && store_info->group_id == -1
2272 && store_info->cse_base == base
2274 && offset >= store_info->begin
2275 && offset + width <= store_info->end
2276 && all_positions_needed_p (store_info,
2277 offset - store_info->begin, width)
2278 && replace_read (store_info, i_ptr, read_info, insn_info, loc,
2279 bb_info->regs_live))
2282 if (!store_info->alias_set)
2283 remove = canon_true_dependence (store_info->mem,
2284 GET_MODE (store_info->mem),
2285 store_info->mem_addr,
2286 mem, mem_addr, rtx_varies_p);
2291 dump_insn_info ("removing from active", i_ptr);
2293 active_local_stores_len--;
2295 last->next_local_store = i_ptr->next_local_store;
2297 active_local_stores = i_ptr->next_local_store;
2301 i_ptr = i_ptr->next_local_store;
2307 /* A for_each_rtx callback in which DATA points the INSN_INFO for
2308 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
2309 true for any part of *LOC. */
2312 check_mem_read_use (rtx *loc, void *data)
2314 for_each_rtx (loc, check_mem_read_rtx, data);
2318 /* Get arguments passed to CALL_INSN. Return TRUE if successful.
2319 So far it only handles arguments passed in registers. */
2322 get_call_args (rtx call_insn, tree fn, rtx *args, int nargs)
2324 CUMULATIVE_ARGS args_so_far_v;
2325 cumulative_args_t args_so_far;
2329 INIT_CUMULATIVE_ARGS (args_so_far_v, TREE_TYPE (fn), NULL_RTX, 0, 3);
2330 args_so_far = pack_cumulative_args (&args_so_far_v);
2332 arg = TYPE_ARG_TYPES (TREE_TYPE (fn));
2334 arg != void_list_node && idx < nargs;
2335 arg = TREE_CHAIN (arg), idx++)
2337 enum machine_mode mode = TYPE_MODE (TREE_VALUE (arg));
2339 reg = targetm.calls.function_arg (args_so_far, mode, NULL_TREE, true);
2340 if (!reg || !REG_P (reg) || GET_MODE (reg) != mode
2341 || GET_MODE_CLASS (mode) != MODE_INT)
2344 for (link = CALL_INSN_FUNCTION_USAGE (call_insn);
2346 link = XEXP (link, 1))
2347 if (GET_CODE (XEXP (link, 0)) == USE)
2349 args[idx] = XEXP (XEXP (link, 0), 0);
2350 if (REG_P (args[idx])
2351 && REGNO (args[idx]) == REGNO (reg)
2352 && (GET_MODE (args[idx]) == mode
2353 || (GET_MODE_CLASS (GET_MODE (args[idx])) == MODE_INT
2354 && (GET_MODE_SIZE (GET_MODE (args[idx]))
2356 && (GET_MODE_SIZE (GET_MODE (args[idx]))
2357 > GET_MODE_SIZE (mode)))))
2363 tmp = cselib_expand_value_rtx (args[idx], scratch, 5);
2364 if (GET_MODE (args[idx]) != mode)
2366 if (!tmp || !CONST_INT_P (tmp))
2368 tmp = GEN_INT (trunc_int_for_mode (INTVAL (tmp), mode));
2373 targetm.calls.function_arg_advance (args_so_far, mode, NULL_TREE, true);
2375 if (arg != void_list_node || idx != nargs)
2381 /* Apply record_store to all candidate stores in INSN. Mark INSN
2382 if some part of it is not a candidate store and assigns to a
2383 non-register target. */
2386 scan_insn (bb_info_t bb_info, rtx insn)
2389 insn_info_t insn_info = (insn_info_t) pool_alloc (insn_info_pool);
2391 memset (insn_info, 0, sizeof (struct insn_info));
2394 fprintf (dump_file, "\n**scanning insn=%d\n",
2397 insn_info->prev_insn = bb_info->last_insn;
2398 insn_info->insn = insn;
2399 bb_info->last_insn = insn_info;
2401 if (DEBUG_INSN_P (insn))
2403 insn_info->cannot_delete = true;
2407 /* Cselib clears the table for this case, so we have to essentially
2409 if (NONJUMP_INSN_P (insn)
2410 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
2411 && MEM_VOLATILE_P (PATTERN (insn)))
2413 add_wild_read (bb_info);
2414 insn_info->cannot_delete = true;
2418 /* Look at all of the uses in the insn. */
2419 note_uses (&PATTERN (insn), check_mem_read_use, bb_info);
2424 tree memset_call = NULL_TREE;
2426 insn_info->cannot_delete = true;
2428 /* Const functions cannot do anything bad i.e. read memory,
2429 however, they can read their parameters which may have
2430 been pushed onto the stack.
2431 memset and bzero don't read memory either. */
2432 const_call = RTL_CONST_CALL_P (insn);
2435 rtx call = PATTERN (insn);
2436 if (GET_CODE (call) == PARALLEL)
2437 call = XVECEXP (call, 0, 0);
2438 if (GET_CODE (call) == SET)
2439 call = SET_SRC (call);
2440 if (GET_CODE (call) == CALL
2441 && MEM_P (XEXP (call, 0))
2442 && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
2444 rtx symbol = XEXP (XEXP (call, 0), 0);
2445 if (SYMBOL_REF_DECL (symbol)
2446 && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
2448 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
2450 && (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))
2451 == BUILT_IN_MEMSET))
2452 || SYMBOL_REF_DECL (symbol) == block_clear_fn)
2453 memset_call = SYMBOL_REF_DECL (symbol);
2457 if (const_call || memset_call)
2459 insn_info_t i_ptr = active_local_stores;
2460 insn_info_t last = NULL;
2463 fprintf (dump_file, "%s call %d\n",
2464 const_call ? "const" : "memset", INSN_UID (insn));
2466 /* See the head comment of the frame_read field. */
2467 if (reload_completed)
2468 insn_info->frame_read = true;
2470 /* Loop over the active stores and remove those which are
2471 killed by the const function call. */
2474 bool remove_store = false;
2476 /* The stack pointer based stores are always killed. */
2477 if (i_ptr->stack_pointer_based)
2478 remove_store = true;
2480 /* If the frame is read, the frame related stores are killed. */
2481 else if (insn_info->frame_read)
2483 store_info_t store_info = i_ptr->store_rec;
2485 /* Skip the clobbers. */
2486 while (!store_info->is_set)
2487 store_info = store_info->next;
2489 if (store_info->group_id >= 0
2490 && VEC_index (group_info_t, rtx_group_vec,
2491 store_info->group_id)->frame_related)
2492 remove_store = true;
2498 dump_insn_info ("removing from active", i_ptr);
2500 active_local_stores_len--;
2502 last->next_local_store = i_ptr->next_local_store;
2504 active_local_stores = i_ptr->next_local_store;
2509 i_ptr = i_ptr->next_local_store;
2515 if (get_call_args (insn, memset_call, args, 3)
2516 && CONST_INT_P (args[1])
2517 && CONST_INT_P (args[2])
2518 && INTVAL (args[2]) > 0)
2520 rtx mem = gen_rtx_MEM (BLKmode, args[0]);
2521 set_mem_size (mem, args[2]);
2522 body = gen_rtx_SET (VOIDmode, mem, args[1]);
2523 mems_found += record_store (body, bb_info);
2525 fprintf (dump_file, "handling memset as BLKmode store\n");
2526 if (mems_found == 1)
2528 if (active_local_stores_len++
2529 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES))
2531 active_local_stores_len = 1;
2532 active_local_stores = NULL;
2534 insn_info->next_local_store = active_local_stores;
2535 active_local_stores = insn_info;
2542 /* Every other call, including pure functions, may read any memory
2543 that is not relative to the frame. */
2544 add_non_frame_wild_read (bb_info);
2549 /* Assuming that there are sets in these insns, we cannot delete
2551 if ((GET_CODE (PATTERN (insn)) == CLOBBER)
2552 || volatile_refs_p (PATTERN (insn))
2553 || insn_could_throw_p (insn)
2554 || (RTX_FRAME_RELATED_P (insn))
2555 || find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX))
2556 insn_info->cannot_delete = true;
2558 body = PATTERN (insn);
2559 if (GET_CODE (body) == PARALLEL)
2562 for (i = 0; i < XVECLEN (body, 0); i++)
2563 mems_found += record_store (XVECEXP (body, 0, i), bb_info);
2566 mems_found += record_store (body, bb_info);
2569 fprintf (dump_file, "mems_found = %d, cannot_delete = %s\n",
2570 mems_found, insn_info->cannot_delete ? "true" : "false");
2572 /* If we found some sets of mems, add it into the active_local_stores so
2573 that it can be locally deleted if found dead or used for
2574 replace_read and redundant constant store elimination. Otherwise mark
2575 it as cannot delete. This simplifies the processing later. */
2576 if (mems_found == 1)
2578 if (active_local_stores_len++
2579 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES))
2581 active_local_stores_len = 1;
2582 active_local_stores = NULL;
2584 insn_info->next_local_store = active_local_stores;
2585 active_local_stores = insn_info;
2588 insn_info->cannot_delete = true;
2592 /* Remove BASE from the set of active_local_stores. This is a
2593 callback from cselib that is used to get rid of the stores in
2594 active_local_stores. */
2597 remove_useless_values (cselib_val *base)
2599 insn_info_t insn_info = active_local_stores;
2600 insn_info_t last = NULL;
2604 store_info_t store_info = insn_info->store_rec;
2607 /* If ANY of the store_infos match the cselib group that is
2608 being deleted, then the insn can not be deleted. */
2611 if ((store_info->group_id == -1)
2612 && (store_info->cse_base == base))
2617 store_info = store_info->next;
2622 active_local_stores_len--;
2624 last->next_local_store = insn_info->next_local_store;
2626 active_local_stores = insn_info->next_local_store;
2627 free_store_info (insn_info);
2632 insn_info = insn_info->next_local_store;
2637 /* Do all of step 1. */
2643 bitmap regs_live = BITMAP_ALLOC (NULL);
2646 all_blocks = BITMAP_ALLOC (NULL);
2647 bitmap_set_bit (all_blocks, ENTRY_BLOCK);
2648 bitmap_set_bit (all_blocks, EXIT_BLOCK);
2653 bb_info_t bb_info = (bb_info_t) pool_alloc (bb_info_pool);
2655 memset (bb_info, 0, sizeof (struct bb_info));
2656 bitmap_set_bit (all_blocks, bb->index);
2657 bb_info->regs_live = regs_live;
2659 bitmap_copy (regs_live, DF_LR_IN (bb));
2660 df_simulate_initialize_forwards (bb, regs_live);
2662 bb_table[bb->index] = bb_info;
2663 cselib_discard_hook = remove_useless_values;
2665 if (bb->index >= NUM_FIXED_BLOCKS)
2670 = create_alloc_pool ("cse_store_info_pool",
2671 sizeof (struct store_info), 100);
2672 active_local_stores = NULL;
2673 active_local_stores_len = 0;
2674 cselib_clear_table ();
2676 /* Scan the insns. */
2677 FOR_BB_INSNS (bb, insn)
2680 scan_insn (bb_info, insn);
2681 cselib_process_insn (insn);
2683 df_simulate_one_insn_forwards (bb, insn, regs_live);
2686 /* This is something of a hack, because the global algorithm
2687 is supposed to take care of the case where stores go dead
2688 at the end of the function. However, the global
2689 algorithm must take a more conservative view of block
2690 mode reads than the local alg does. So to get the case
2691 where you have a store to the frame followed by a non
2692 overlapping block more read, we look at the active local
2693 stores at the end of the function and delete all of the
2694 frame and spill based ones. */
2695 if (stores_off_frame_dead_at_return
2696 && (EDGE_COUNT (bb->succs) == 0
2697 || (single_succ_p (bb)
2698 && single_succ (bb) == EXIT_BLOCK_PTR
2699 && ! crtl->calls_eh_return)))
2701 insn_info_t i_ptr = active_local_stores;
2704 store_info_t store_info = i_ptr->store_rec;
2706 /* Skip the clobbers. */
2707 while (!store_info->is_set)
2708 store_info = store_info->next;
2709 if (store_info->alias_set && !i_ptr->cannot_delete)
2710 delete_dead_store_insn (i_ptr);
2712 if (store_info->group_id >= 0)
2715 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
2716 if (group->frame_related && !i_ptr->cannot_delete)
2717 delete_dead_store_insn (i_ptr);
2720 i_ptr = i_ptr->next_local_store;
2724 /* Get rid of the loads that were discovered in
2725 replace_read. Cselib is finished with this block. */
2726 while (deferred_change_list)
2728 deferred_change_t next = deferred_change_list->next;
2730 /* There is no reason to validate this change. That was
2732 *deferred_change_list->loc = deferred_change_list->reg;
2733 pool_free (deferred_change_pool, deferred_change_list);
2734 deferred_change_list = next;
2737 /* Get rid of all of the cselib based store_infos in this
2738 block and mark the containing insns as not being
2740 ptr = bb_info->last_insn;
2743 if (ptr->contains_cselib_groups)
2745 store_info_t s_info = ptr->store_rec;
2746 while (s_info && !s_info->is_set)
2747 s_info = s_info->next;
2749 && s_info->redundant_reason
2750 && s_info->redundant_reason->insn
2751 && !ptr->cannot_delete)
2754 fprintf (dump_file, "Locally deleting insn %d "
2755 "because insn %d stores the "
2756 "same value and couldn't be "
2758 INSN_UID (ptr->insn),
2759 INSN_UID (s_info->redundant_reason->insn));
2760 delete_dead_store_insn (ptr);
2763 s_info->redundant_reason = NULL;
2764 free_store_info (ptr);
2768 store_info_t s_info;
2770 /* Free at least positions_needed bitmaps. */
2771 for (s_info = ptr->store_rec; s_info; s_info = s_info->next)
2772 if (s_info->is_large)
2774 BITMAP_FREE (s_info->positions_needed.large.bmap);
2775 s_info->is_large = false;
2778 ptr = ptr->prev_insn;
2781 free_alloc_pool (cse_store_info_pool);
2783 bb_info->regs_live = NULL;
2786 BITMAP_FREE (regs_live);
2788 htab_empty (rtx_group_table);
2792 /*----------------------------------------------------------------------------
2795 Assign each byte position in the stores that we are going to
2796 analyze globally to a position in the bitmaps. Returns true if
2797 there are any bit positions assigned.
2798 ----------------------------------------------------------------------------*/
2801 dse_step2_init (void)
2806 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
2808 /* For all non stack related bases, we only consider a store to
2809 be deletable if there are two or more stores for that
2810 position. This is because it takes one store to make the
2811 other store redundant. However, for the stores that are
2812 stack related, we consider them if there is only one store
2813 for the position. We do this because the stack related
2814 stores can be deleted if their is no read between them and
2815 the end of the function.
2817 To make this work in the current framework, we take the stack
2818 related bases add all of the bits from store1 into store2.
2819 This has the effect of making the eligible even if there is
2822 if (stores_off_frame_dead_at_return && group->frame_related)
2824 bitmap_ior_into (group->store2_n, group->store1_n);
2825 bitmap_ior_into (group->store2_p, group->store1_p);
2827 fprintf (dump_file, "group %d is frame related ", i);
2830 group->offset_map_size_n++;
2831 group->offset_map_n = XNEWVEC (int, group->offset_map_size_n);
2832 group->offset_map_size_p++;
2833 group->offset_map_p = XNEWVEC (int, group->offset_map_size_p);
2834 group->process_globally = false;
2837 fprintf (dump_file, "group %d(%d+%d): ", i,
2838 (int)bitmap_count_bits (group->store2_n),
2839 (int)bitmap_count_bits (group->store2_p));
2840 bitmap_print (dump_file, group->store2_n, "n ", " ");
2841 bitmap_print (dump_file, group->store2_p, "p ", "\n");
2847 /* Init the offset tables for the normal case. */
2850 dse_step2_nospill (void)
2854 /* Position 0 is unused because 0 is used in the maps to mean
2856 current_position = 1;
2857 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
2862 if (group == clear_alias_group)
2865 memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2866 memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2867 bitmap_clear (group->group_kill);
2869 EXECUTE_IF_SET_IN_BITMAP (group->store2_n, 0, j, bi)
2871 bitmap_set_bit (group->group_kill, current_position);
2872 if (bitmap_bit_p (group->escaped_n, j))
2873 bitmap_set_bit (kill_on_calls, current_position);
2874 group->offset_map_n[j] = current_position++;
2875 group->process_globally = true;
2877 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2879 bitmap_set_bit (group->group_kill, current_position);
2880 if (bitmap_bit_p (group->escaped_p, j))
2881 bitmap_set_bit (kill_on_calls, current_position);
2882 group->offset_map_p[j] = current_position++;
2883 group->process_globally = true;
2886 return current_position != 1;
2890 /* Init the offset tables for the spill case. */
2893 dse_step2_spill (void)
2896 group_info_t group = clear_alias_group;
2899 /* Position 0 is unused because 0 is used in the maps to mean
2901 current_position = 1;
2905 bitmap_print (dump_file, clear_alias_sets,
2906 "clear alias sets ", "\n");
2907 bitmap_print (dump_file, disqualified_clear_alias_sets,
2908 "disqualified clear alias sets ", "\n");
2911 memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2912 memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2913 bitmap_clear (group->group_kill);
2915 /* Remove the disqualified positions from the store2_p set. */
2916 bitmap_and_compl_into (group->store2_p, disqualified_clear_alias_sets);
2918 /* We do not need to process the store2_n set because
2919 alias_sets are always positive. */
2920 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2922 bitmap_set_bit (group->group_kill, current_position);
2923 group->offset_map_p[j] = current_position++;
2924 group->process_globally = true;
2927 return current_position != 1;
2932 /*----------------------------------------------------------------------------
2935 Build the bit vectors for the transfer functions.
2936 ----------------------------------------------------------------------------*/
2939 /* Note that this is NOT a general purpose function. Any mem that has
2940 an alias set registered here expected to be COMPLETELY unaliased:
2941 i.e it's addresses are not and need not be examined.
2943 It is known that all references to this address will have this
2944 alias set and there are NO other references to this address in the
2947 Currently the only place that is known to be clean enough to use
2948 this interface is the code that assigns the spill locations.
2950 All of the mems that have alias_sets registered are subjected to a
2951 very powerful form of dse where function calls, volatile reads and
2952 writes, and reads from random location are not taken into account.
2954 It is also assumed that these locations go dead when the function
2955 returns. This assumption could be relaxed if there were found to
2956 be places that this assumption was not correct.
2958 The MODE is passed in and saved. The mode of each load or store to
2959 a mem with ALIAS_SET is checked against MEM. If the size of that
2960 load or store is different from MODE, processing is halted on this
2961 alias set. For the vast majority of aliases sets, all of the loads
2962 and stores will use the same mode. But vectors are treated
2963 differently: the alias set is established for the entire vector,
2964 but reload will insert loads and stores for individual elements and
2965 we do not necessarily have the information to track those separate
2966 elements. So when we see a mode mismatch, we just bail. */
2970 dse_record_singleton_alias_set (alias_set_type alias_set,
2971 enum machine_mode mode)
2973 struct clear_alias_mode_holder tmp_holder;
2974 struct clear_alias_mode_holder *entry;
2977 /* If we are not going to run dse, we need to return now or there
2978 will be problems with allocating the bitmaps. */
2979 if ((!gate_dse()) || !alias_set)
2982 if (!clear_alias_sets)
2984 clear_alias_sets = BITMAP_ALLOC (NULL);
2985 disqualified_clear_alias_sets = BITMAP_ALLOC (NULL);
2986 clear_alias_mode_table = htab_create (11, clear_alias_mode_hash,
2987 clear_alias_mode_eq, NULL);
2988 clear_alias_mode_pool = create_alloc_pool ("clear_alias_mode_pool",
2989 sizeof (struct clear_alias_mode_holder), 100);
2992 bitmap_set_bit (clear_alias_sets, alias_set);
2994 tmp_holder.alias_set = alias_set;
2996 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, INSERT);
2997 gcc_assert (*slot == NULL);
3000 (struct clear_alias_mode_holder *) pool_alloc (clear_alias_mode_pool);
3001 entry->alias_set = alias_set;
3006 /* Remove ALIAS_SET from the sets of stack slots being considered. */
3009 dse_invalidate_singleton_alias_set (alias_set_type alias_set)
3011 if ((!gate_dse()) || !alias_set)
3014 bitmap_clear_bit (clear_alias_sets, alias_set);
3018 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
3022 get_bitmap_index (group_info_t group_info, HOST_WIDE_INT offset)
3026 HOST_WIDE_INT offset_p = -offset;
3027 if (offset_p >= group_info->offset_map_size_n)
3029 return group_info->offset_map_n[offset_p];
3033 if (offset >= group_info->offset_map_size_p)
3035 return group_info->offset_map_p[offset];
3040 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3044 scan_stores_nospill (store_info_t store_info, bitmap gen, bitmap kill)
3049 group_info_t group_info
3050 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
3051 if (group_info->process_globally)
3052 for (i = store_info->begin; i < store_info->end; i++)
3054 int index = get_bitmap_index (group_info, i);
3057 bitmap_set_bit (gen, index);
3059 bitmap_clear_bit (kill, index);
3062 store_info = store_info->next;
3067 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3071 scan_stores_spill (store_info_t store_info, bitmap gen, bitmap kill)
3075 if (store_info->alias_set)
3077 int index = get_bitmap_index (clear_alias_group,
3078 store_info->alias_set);
3081 bitmap_set_bit (gen, index);
3083 bitmap_clear_bit (kill, index);
3086 store_info = store_info->next;
3091 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3095 scan_reads_nospill (insn_info_t insn_info, bitmap gen, bitmap kill)
3097 read_info_t read_info = insn_info->read_rec;
3101 /* If this insn reads the frame, kill all the frame related stores. */
3102 if (insn_info->frame_read)
3104 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
3105 if (group->process_globally && group->frame_related)
3108 bitmap_ior_into (kill, group->group_kill);
3109 bitmap_and_compl_into (gen, group->group_kill);
3112 if (insn_info->non_frame_wild_read)
3114 /* Kill all non-frame related stores. Kill all stores of variables that
3117 bitmap_ior_into (kill, kill_on_calls);
3118 bitmap_and_compl_into (gen, kill_on_calls);
3119 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
3120 if (group->process_globally && !group->frame_related)
3123 bitmap_ior_into (kill, group->group_kill);
3124 bitmap_and_compl_into (gen, group->group_kill);
3129 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
3131 if (group->process_globally)
3133 if (i == read_info->group_id)
3135 if (read_info->begin > read_info->end)
3137 /* Begin > end for block mode reads. */
3139 bitmap_ior_into (kill, group->group_kill);
3140 bitmap_and_compl_into (gen, group->group_kill);
3144 /* The groups are the same, just process the
3147 for (j = read_info->begin; j < read_info->end; j++)
3149 int index = get_bitmap_index (group, j);
3153 bitmap_set_bit (kill, index);
3154 bitmap_clear_bit (gen, index);
3161 /* The groups are different, if the alias sets
3162 conflict, clear the entire group. We only need
3163 to apply this test if the read_info is a cselib
3164 read. Anything with a constant base cannot alias
3165 something else with a different constant
3167 if ((read_info->group_id < 0)
3168 && canon_true_dependence (group->base_mem,
3169 GET_MODE (group->base_mem),
3170 group->canon_base_addr,
3171 read_info->mem, NULL_RTX,
3175 bitmap_ior_into (kill, group->group_kill);
3176 bitmap_and_compl_into (gen, group->group_kill);
3182 read_info = read_info->next;
3186 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3190 scan_reads_spill (read_info_t read_info, bitmap gen, bitmap kill)
3194 if (read_info->alias_set)
3196 int index = get_bitmap_index (clear_alias_group,
3197 read_info->alias_set);
3201 bitmap_set_bit (kill, index);
3202 bitmap_clear_bit (gen, index);
3206 read_info = read_info->next;
3211 /* Return the insn in BB_INFO before the first wild read or if there
3212 are no wild reads in the block, return the last insn. */
3215 find_insn_before_first_wild_read (bb_info_t bb_info)
3217 insn_info_t insn_info = bb_info->last_insn;
3218 insn_info_t last_wild_read = NULL;
3222 if (insn_info->wild_read)
3224 last_wild_read = insn_info->prev_insn;
3225 /* Block starts with wild read. */
3226 if (!last_wild_read)
3230 insn_info = insn_info->prev_insn;
3234 return last_wild_read;
3236 return bb_info->last_insn;
3240 /* Scan the insns in BB_INFO starting at PTR and going to the top of
3241 the block in order to build the gen and kill sets for the block.
3242 We start at ptr which may be the last insn in the block or may be
3243 the first insn with a wild read. In the latter case we are able to
3244 skip the rest of the block because it just does not matter:
3245 anything that happens is hidden by the wild read. */
3248 dse_step3_scan (bool for_spills, basic_block bb)
3250 bb_info_t bb_info = bb_table[bb->index];
3251 insn_info_t insn_info;
3254 /* There are no wild reads in the spill case. */
3255 insn_info = bb_info->last_insn;
3257 insn_info = find_insn_before_first_wild_read (bb_info);
3259 /* In the spill case or in the no_spill case if there is no wild
3260 read in the block, we will need a kill set. */
3261 if (insn_info == bb_info->last_insn)
3264 bitmap_clear (bb_info->kill);
3266 bb_info->kill = BITMAP_ALLOC (NULL);
3270 BITMAP_FREE (bb_info->kill);
3274 /* There may have been code deleted by the dce pass run before
3276 if (insn_info->insn && INSN_P (insn_info->insn))
3278 /* Process the read(s) last. */
3281 scan_stores_spill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3282 scan_reads_spill (insn_info->read_rec, bb_info->gen, bb_info->kill);
3286 scan_stores_nospill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3287 scan_reads_nospill (insn_info, bb_info->gen, bb_info->kill);
3291 insn_info = insn_info->prev_insn;
3296 /* Set the gen set of the exit block, and also any block with no
3297 successors that does not have a wild read. */
3300 dse_step3_exit_block_scan (bb_info_t bb_info)
3302 /* The gen set is all 0's for the exit block except for the
3303 frame_pointer_group. */
3305 if (stores_off_frame_dead_at_return)
3310 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
3312 if (group->process_globally && group->frame_related)
3313 bitmap_ior_into (bb_info->gen, group->group_kill);
3319 /* Find all of the blocks that are not backwards reachable from the
3320 exit block or any block with no successors (BB). These are the
3321 infinite loops or infinite self loops. These blocks will still
3322 have their bits set in UNREACHABLE_BLOCKS. */
3325 mark_reachable_blocks (sbitmap unreachable_blocks, basic_block bb)
3330 if (TEST_BIT (unreachable_blocks, bb->index))
3332 RESET_BIT (unreachable_blocks, bb->index);
3333 FOR_EACH_EDGE (e, ei, bb->preds)
3335 mark_reachable_blocks (unreachable_blocks, e->src);
3340 /* Build the transfer functions for the function. */
3343 dse_step3 (bool for_spills)
3346 sbitmap unreachable_blocks = sbitmap_alloc (last_basic_block);
3347 sbitmap_iterator sbi;
3348 bitmap all_ones = NULL;
3351 sbitmap_ones (unreachable_blocks);
3355 bb_info_t bb_info = bb_table[bb->index];
3357 bitmap_clear (bb_info->gen);
3359 bb_info->gen = BITMAP_ALLOC (NULL);
3361 if (bb->index == ENTRY_BLOCK)
3363 else if (bb->index == EXIT_BLOCK)
3364 dse_step3_exit_block_scan (bb_info);
3366 dse_step3_scan (for_spills, bb);
3367 if (EDGE_COUNT (bb->succs) == 0)
3368 mark_reachable_blocks (unreachable_blocks, bb);
3370 /* If this is the second time dataflow is run, delete the old
3373 BITMAP_FREE (bb_info->in);
3375 BITMAP_FREE (bb_info->out);
3378 /* For any block in an infinite loop, we must initialize the out set
3379 to all ones. This could be expensive, but almost never occurs in
3380 practice. However, it is common in regression tests. */
3381 EXECUTE_IF_SET_IN_SBITMAP (unreachable_blocks, 0, i, sbi)
3383 if (bitmap_bit_p (all_blocks, i))
3385 bb_info_t bb_info = bb_table[i];
3391 all_ones = BITMAP_ALLOC (NULL);
3392 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, j, group)
3393 bitmap_ior_into (all_ones, group->group_kill);
3397 bb_info->out = BITMAP_ALLOC (NULL);
3398 bitmap_copy (bb_info->out, all_ones);
3404 BITMAP_FREE (all_ones);
3405 sbitmap_free (unreachable_blocks);
3410 /*----------------------------------------------------------------------------
3413 Solve the bitvector equations.
3414 ----------------------------------------------------------------------------*/
3417 /* Confluence function for blocks with no successors. Create an out
3418 set from the gen set of the exit block. This block logically has
3419 the exit block as a successor. */
3424 dse_confluence_0 (basic_block bb)
3426 bb_info_t bb_info = bb_table[bb->index];
3428 if (bb->index == EXIT_BLOCK)
3433 bb_info->out = BITMAP_ALLOC (NULL);
3434 bitmap_copy (bb_info->out, bb_table[EXIT_BLOCK]->gen);
3438 /* Propagate the information from the in set of the dest of E to the
3439 out set of the src of E. If the various in or out sets are not
3440 there, that means they are all ones. */
3443 dse_confluence_n (edge e)
3445 bb_info_t src_info = bb_table[e->src->index];
3446 bb_info_t dest_info = bb_table[e->dest->index];
3451 bitmap_and_into (src_info->out, dest_info->in);
3454 src_info->out = BITMAP_ALLOC (NULL);
3455 bitmap_copy (src_info->out, dest_info->in);
3462 /* Propagate the info from the out to the in set of BB_INDEX's basic
3463 block. There are three cases:
3465 1) The block has no kill set. In this case the kill set is all
3466 ones. It does not matter what the out set of the block is, none of
3467 the info can reach the top. The only thing that reaches the top is
3468 the gen set and we just copy the set.
3470 2) There is a kill set but no out set and bb has successors. In
3471 this case we just return. Eventually an out set will be created and
3472 it is better to wait than to create a set of ones.
3474 3) There is both a kill and out set. We apply the obvious transfer
3479 dse_transfer_function (int bb_index)
3481 bb_info_t bb_info = bb_table[bb_index];
3489 return bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3490 bb_info->out, bb_info->kill);
3493 bb_info->in = BITMAP_ALLOC (NULL);
3494 bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3495 bb_info->out, bb_info->kill);
3505 /* Case 1 above. If there is already an in set, nothing
3511 bb_info->in = BITMAP_ALLOC (NULL);
3512 bitmap_copy (bb_info->in, bb_info->gen);
3518 /* Solve the dataflow equations. */
3523 df_simple_dataflow (DF_BACKWARD, NULL, dse_confluence_0,
3524 dse_confluence_n, dse_transfer_function,
3525 all_blocks, df_get_postorder (DF_BACKWARD),
3526 df_get_n_blocks (DF_BACKWARD));
3531 fprintf (dump_file, "\n\n*** Global dataflow info after analysis.\n");
3534 bb_info_t bb_info = bb_table[bb->index];
3536 df_print_bb_index (bb, dump_file);
3538 bitmap_print (dump_file, bb_info->in, " in: ", "\n");
3540 fprintf (dump_file, " in: *MISSING*\n");
3542 bitmap_print (dump_file, bb_info->gen, " gen: ", "\n");
3544 fprintf (dump_file, " gen: *MISSING*\n");
3546 bitmap_print (dump_file, bb_info->kill, " kill: ", "\n");
3548 fprintf (dump_file, " kill: *MISSING*\n");
3550 bitmap_print (dump_file, bb_info->out, " out: ", "\n");
3552 fprintf (dump_file, " out: *MISSING*\n\n");
3559 /*----------------------------------------------------------------------------
3562 Delete the stores that can only be deleted using the global information.
3563 ----------------------------------------------------------------------------*/
3567 dse_step5_nospill (void)
3572 bb_info_t bb_info = bb_table[bb->index];
3573 insn_info_t insn_info = bb_info->last_insn;
3574 bitmap v = bb_info->out;
3578 bool deleted = false;
3579 if (dump_file && insn_info->insn)
3581 fprintf (dump_file, "starting to process insn %d\n",
3582 INSN_UID (insn_info->insn));
3583 bitmap_print (dump_file, v, " v: ", "\n");
3586 /* There may have been code deleted by the dce pass run before
3589 && INSN_P (insn_info->insn)
3590 && (!insn_info->cannot_delete)
3591 && (!bitmap_empty_p (v)))
3593 store_info_t store_info = insn_info->store_rec;
3595 /* Try to delete the current insn. */
3598 /* Skip the clobbers. */
3599 while (!store_info->is_set)
3600 store_info = store_info->next;
3602 if (store_info->alias_set)
3607 group_info_t group_info
3608 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
3610 for (i = store_info->begin; i < store_info->end; i++)
3612 int index = get_bitmap_index (group_info, i);
3615 fprintf (dump_file, "i = %d, index = %d\n", (int)i, index);
3616 if (index == 0 || !bitmap_bit_p (v, index))
3619 fprintf (dump_file, "failing at i = %d\n", (int)i);
3629 check_for_inc_dec (insn_info->insn);
3630 delete_insn (insn_info->insn);
3631 insn_info->insn = NULL;
3636 /* We do want to process the local info if the insn was
3637 deleted. For instance, if the insn did a wild read, we
3638 no longer need to trash the info. */
3640 && INSN_P (insn_info->insn)
3643 scan_stores_nospill (insn_info->store_rec, v, NULL);
3644 if (insn_info->wild_read)
3647 fprintf (dump_file, "wild read\n");
3650 else if (insn_info->read_rec
3651 || insn_info->non_frame_wild_read)
3653 if (dump_file && !insn_info->non_frame_wild_read)
3654 fprintf (dump_file, "regular read\n");
3656 fprintf (dump_file, "non-frame wild read\n");
3657 scan_reads_nospill (insn_info, v, NULL);
3661 insn_info = insn_info->prev_insn;
3668 dse_step5_spill (void)
3673 bb_info_t bb_info = bb_table[bb->index];
3674 insn_info_t insn_info = bb_info->last_insn;
3675 bitmap v = bb_info->out;
3679 bool deleted = false;
3680 /* There may have been code deleted by the dce pass run before
3683 && INSN_P (insn_info->insn)
3684 && (!insn_info->cannot_delete)
3685 && (!bitmap_empty_p (v)))
3687 /* Try to delete the current insn. */
3688 store_info_t store_info = insn_info->store_rec;
3693 if (store_info->alias_set)
3695 int index = get_bitmap_index (clear_alias_group,
3696 store_info->alias_set);
3697 if (index == 0 || !bitmap_bit_p (v, index))
3705 store_info = store_info->next;
3707 if (deleted && dbg_cnt (dse))
3710 fprintf (dump_file, "Spill deleting insn %d\n",
3711 INSN_UID (insn_info->insn));
3712 check_for_inc_dec (insn_info->insn);
3713 delete_insn (insn_info->insn);
3715 insn_info->insn = NULL;
3720 && INSN_P (insn_info->insn)
3723 scan_stores_spill (insn_info->store_rec, v, NULL);
3724 scan_reads_spill (insn_info->read_rec, v, NULL);
3727 insn_info = insn_info->prev_insn;
3734 /*----------------------------------------------------------------------------
3737 Delete stores made redundant by earlier stores (which store the same
3738 value) that couldn't be eliminated.
3739 ----------------------------------------------------------------------------*/
3748 bb_info_t bb_info = bb_table[bb->index];
3749 insn_info_t insn_info = bb_info->last_insn;
3753 /* There may have been code deleted by the dce pass run before
3756 && INSN_P (insn_info->insn)
3757 && !insn_info->cannot_delete)
3759 store_info_t s_info = insn_info->store_rec;
3761 while (s_info && !s_info->is_set)
3762 s_info = s_info->next;
3764 && s_info->redundant_reason
3765 && s_info->redundant_reason->insn
3766 && INSN_P (s_info->redundant_reason->insn))
3768 rtx rinsn = s_info->redundant_reason->insn;
3770 fprintf (dump_file, "Locally deleting insn %d "
3771 "because insn %d stores the "
3772 "same value and couldn't be "
3774 INSN_UID (insn_info->insn),
3776 delete_dead_store_insn (insn_info);
3779 insn_info = insn_info->prev_insn;
3784 /*----------------------------------------------------------------------------
3787 Destroy everything left standing.
3788 ----------------------------------------------------------------------------*/
3791 dse_step7 (bool global_done)
3797 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
3799 free (group->offset_map_n);
3800 free (group->offset_map_p);
3801 BITMAP_FREE (group->store1_n);
3802 BITMAP_FREE (group->store1_p);
3803 BITMAP_FREE (group->store2_n);
3804 BITMAP_FREE (group->store2_p);
3805 BITMAP_FREE (group->escaped_n);
3806 BITMAP_FREE (group->escaped_p);
3807 BITMAP_FREE (group->group_kill);
3813 bb_info_t bb_info = bb_table[bb->index];
3814 BITMAP_FREE (bb_info->gen);
3816 BITMAP_FREE (bb_info->kill);
3818 BITMAP_FREE (bb_info->in);
3820 BITMAP_FREE (bb_info->out);
3823 if (clear_alias_sets)
3825 BITMAP_FREE (clear_alias_sets);
3826 BITMAP_FREE (disqualified_clear_alias_sets);
3827 free_alloc_pool (clear_alias_mode_pool);
3828 htab_delete (clear_alias_mode_table);
3831 end_alias_analysis ();
3833 htab_delete (rtx_group_table);
3834 VEC_free (group_info_t, heap, rtx_group_vec);
3835 BITMAP_FREE (all_blocks);
3836 BITMAP_FREE (scratch);
3837 BITMAP_FREE (kill_on_calls);
3839 free_alloc_pool (rtx_store_info_pool);
3840 free_alloc_pool (read_info_pool);
3841 free_alloc_pool (insn_info_pool);
3842 free_alloc_pool (bb_info_pool);
3843 free_alloc_pool (rtx_group_info_pool);
3844 free_alloc_pool (deferred_change_pool);
3848 /* -------------------------------------------------------------------------
3850 ------------------------------------------------------------------------- */
3852 /* Callback for running pass_rtl_dse. */
3855 rest_of_handle_dse (void)
3857 bool did_global = false;
3859 df_set_flags (DF_DEFER_INSN_RESCAN);
3861 /* Need the notes since we must track live hardregs in the forwards
3863 df_note_add_problem ();
3869 if (dse_step2_nospill ())
3871 df_set_flags (DF_LR_RUN_DCE);
3875 fprintf (dump_file, "doing global processing\n");
3878 dse_step5_nospill ();
3881 /* For the instance of dse that runs after reload, we make a special
3882 pass to process the spills. These are special in that they are
3883 totally transparent, i.e, there is no aliasing issues that need
3884 to be considered. This means that the wild reads that kill
3885 everything else do not apply here. */
3886 if (clear_alias_sets && dse_step2_spill ())
3890 df_set_flags (DF_LR_RUN_DCE);
3895 fprintf (dump_file, "doing global spill processing\n");
3902 dse_step7 (did_global);
3905 fprintf (dump_file, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3906 locally_deleted, globally_deleted, spill_deleted);
3913 return gate_dse1 () || gate_dse2 ();
3919 return optimize > 0 && flag_dse
3926 return optimize > 0 && flag_dse
3930 struct rtl_opt_pass pass_rtl_dse1 =
3935 gate_dse1, /* gate */
3936 rest_of_handle_dse, /* execute */
3939 0, /* static_pass_number */
3940 TV_DSE1, /* tv_id */
3941 0, /* properties_required */
3942 0, /* properties_provided */
3943 0, /* properties_destroyed */
3944 0, /* todo_flags_start */
3945 TODO_df_finish | TODO_verify_rtl_sharing |
3946 TODO_ggc_collect /* todo_flags_finish */
3950 struct rtl_opt_pass pass_rtl_dse2 =
3955 gate_dse2, /* gate */
3956 rest_of_handle_dse, /* execute */
3959 0, /* static_pass_number */
3960 TV_DSE2, /* tv_id */
3961 0, /* properties_required */
3962 0, /* properties_provided */
3963 0, /* properties_destroyed */
3964 0, /* todo_flags_start */
3965 TODO_df_finish | TODO_verify_rtl_sharing |
3966 TODO_ggc_collect /* todo_flags_finish */