1 /* RTL dead store elimination.
2 Copyright (C) 2005-2020 Free Software Foundation, Inc.
4 Contributed by Richard Sandiford <rsandifor@codesourcery.com>
5 and Kenneth Zadeck <zadeck@naturalbridge.com>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
27 #include "coretypes.h"
37 #include "gimple-ssa.h"
43 #include "stor-layout.h"
46 #include "tree-pass.h"
51 #include "cfgcleanup.h"
54 /* This file contains three techniques for performing Dead Store
57 * The first technique performs dse locally on any base address. It
58 is based on the cselib which is a local value numbering technique.
59 This technique is local to a basic block but deals with a fairly
62 * The second technique performs dse globally but is restricted to
63 base addresses that are either constant or are relative to the
66 * The third technique, (which is only done after register allocation)
67 processes the spill slots. This differs from the second
68 technique because it takes advantage of the fact that spilling is
69 completely free from the effects of aliasing.
71 Logically, dse is a backwards dataflow problem. A store can be
72 deleted if it if cannot be reached in the backward direction by any
73 use of the value being stored. However, the local technique uses a
74 forwards scan of the basic block because cselib requires that the
75 block be processed in that order.
77 The pass is logically broken into 7 steps:
81 1) The local algorithm, as well as scanning the insns for the two
84 2) Analysis to see if the global algs are necessary. In the case
85 of stores base on a constant address, there must be at least two
86 stores to that address, to make it possible to delete some of the
87 stores. In the case of stores off of the frame or spill related
88 stores, only one store to an address is necessary because those
89 stores die at the end of the function.
91 3) Set up the global dataflow equations based on processing the
92 info parsed in the first step.
94 4) Solve the dataflow equations.
96 5) Delete the insns that the global analysis has indicated are
99 6) Delete insns that store the same value as preceding store
100 where the earlier store couldn't be eliminated.
104 This step uses cselib and canon_rtx to build the largest expression
105 possible for each address. This pass is a forwards pass through
106 each basic block. From the point of view of the global technique,
107 the first pass could examine a block in either direction. The
108 forwards ordering is to accommodate cselib.
110 We make a simplifying assumption: addresses fall into four broad
113 1) base has rtx_varies_p == false, offset is constant.
114 2) base has rtx_varies_p == false, offset variable.
115 3) base has rtx_varies_p == true, offset constant.
116 4) base has rtx_varies_p == true, offset variable.
118 The local passes are able to process all 4 kinds of addresses. The
119 global pass only handles 1).
121 The global problem is formulated as follows:
123 A store, S1, to address A, where A is not relative to the stack
124 frame, can be eliminated if all paths from S1 to the end of the
125 function contain another store to A before a read to A.
127 If the address A is relative to the stack frame, a store S2 to A
128 can be eliminated if there are no paths from S2 that reach the
129 end of the function that read A before another store to A. In
130 this case S2 can be deleted if there are paths from S2 to the
131 end of the function that have no reads or writes to A. This
132 second case allows stores to the stack frame to be deleted that
133 would otherwise die when the function returns. This cannot be
134 done if stores_off_frame_dead_at_return is not true. See the doc
135 for that variable for when this variable is false.
137 The global problem is formulated as a backwards set union
138 dataflow problem where the stores are the gens and reads are the
139 kills. Set union problems are rare and require some special
140 handling given our representation of bitmaps. A straightforward
141 implementation requires a lot of bitmaps filled with 1s.
142 These are expensive and cumbersome in our bitmap formulation so
143 care has been taken to avoid large vectors filled with 1s. See
144 the comments in bb_info and in the dataflow confluence functions
147 There are two places for further enhancements to this algorithm:
149 1) The original dse which was embedded in a pass called flow also
150 did local address forwarding. For example in
155 flow would replace the right hand side of the second insn with a
156 reference to r100. Most of the information is available to add this
157 to this pass. It has not done it because it is a lot of work in
158 the case that either r100 is assigned to between the first and
159 second insn and/or the second insn is a load of part of the value
160 stored by the first insn.
162 insn 5 in gcc.c-torture/compile/990203-1.c simple case.
163 insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
164 insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
165 insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
167 2) The cleaning up of spill code is quite profitable. It currently
168 depends on reading tea leaves and chicken entrails left by reload.
169 This pass depends on reload creating a singleton alias set for each
170 spill slot and telling the next dse pass which of these alias sets
171 are the singletons. Rather than analyze the addresses of the
172 spills, dse's spill processing just does analysis of the loads and
173 stores that use those alias sets. There are three cases where this
176 a) Reload sometimes creates the slot for one mode of access, and
177 then inserts loads and/or stores for a smaller mode. In this
178 case, the current code just punts on the slot. The proper thing
179 to do is to back out and use one bit vector position for each
180 byte of the entity associated with the slot. This depends on
181 KNOWING that reload always generates the accesses for each of the
182 bytes in some canonical (read that easy to understand several
183 passes after reload happens) way.
185 b) Reload sometimes decides that spill slot it allocated was not
186 large enough for the mode and goes back and allocates more slots
187 with the same mode and alias set. The backout in this case is a
188 little more graceful than (a). In this case the slot is unmarked
189 as being a spill slot and if final address comes out to be based
190 off the frame pointer, the global algorithm handles this slot.
192 c) For any pass that may prespill, there is currently no
193 mechanism to tell the dse pass that the slot being used has the
194 special properties that reload uses. It may be that all that is
195 required is to have those passes make the same calls that reload
196 does, assuming that the alias sets can be manipulated in the same
199 /* There are limits to the size of constant offsets we model for the
200 global problem. There are certainly test cases, that exceed this
201 limit, however, it is unlikely that there are important programs
202 that really have constant offsets this size. */
203 #define MAX_OFFSET (64 * 1024)
205 /* Obstack for the DSE dataflow bitmaps. We don't want to put these
206 on the default obstack because these bitmaps can grow quite large
207 (~2GB for the small (!) test case of PR54146) and we'll hold on to
208 all that memory until the end of the compiler run.
209 As a bonus, delete_tree_live_info can destroy all the bitmaps by just
210 releasing the whole obstack. */
211 static bitmap_obstack dse_bitmap_obstack
;
213 /* Obstack for other data. As for above: Kinda nice to be able to
214 throw it all away at the end in one big sweep. */
215 static struct obstack dse_obstack
;
217 /* Scratch bitmap for cselib's cselib_expand_value_rtx. */
218 static bitmap scratch
= NULL
;
220 struct insn_info_type
;
222 /* This structure holds information about a candidate store. */
227 /* False means this is a clobber. */
230 /* False if a single HOST_WIDE_INT bitmap is used for positions_needed. */
233 /* The id of the mem group of the base address. If rtx_varies_p is
234 true, this is -1. Otherwise, it is the index into the group
238 /* This is the cselib value. */
239 cselib_val
*cse_base
;
241 /* This canonized mem. */
244 /* Canonized MEM address for use by canon_true_dependence. */
247 /* The offset of the first byte associated with the operation. */
250 /* The number of bytes covered by the operation. This is always exact
251 and known (rather than -1). */
256 /* A bitmask as wide as the number of bytes in the word that
257 contains a 1 if the byte may be needed. The store is unused if
258 all of the bits are 0. This is used if IS_LARGE is false. */
259 unsigned HOST_WIDE_INT small_bitmask
;
263 /* A bitmap with one bit per byte, or null if the number of
264 bytes isn't known at compile time. A cleared bit means
265 the position is needed. Used if IS_LARGE is true. */
268 /* When BITMAP is nonnull, this counts the number of set bits
269 (i.e. unneeded bytes) in the bitmap. If it is equal to
270 WIDTH, the whole store is unused.
273 - the store is definitely not needed when COUNT == 1
274 - all the store is needed when COUNT == 0 and RHS is nonnull
275 - otherwise we don't know which parts of the store are needed. */
280 /* The next store info for this insn. */
281 class store_info
*next
;
283 /* The right hand side of the store. This is used if there is a
284 subsequent reload of the mems address somewhere later in the
288 /* If rhs is or holds a constant, this contains that constant,
292 /* Set if this store stores the same constant value as REDUNDANT_REASON
293 insn stored. These aren't eliminated early, because doing that
294 might prevent the earlier larger store to be eliminated. */
295 struct insn_info_type
*redundant_reason
;
298 /* Return a bitmask with the first N low bits set. */
300 static unsigned HOST_WIDE_INT
301 lowpart_bitmask (int n
)
303 unsigned HOST_WIDE_INT mask
= HOST_WIDE_INT_M1U
;
304 return mask
>> (HOST_BITS_PER_WIDE_INT
- n
);
307 static object_allocator
<store_info
> cse_store_info_pool ("cse_store_info_pool");
309 static object_allocator
<store_info
> rtx_store_info_pool ("rtx_store_info_pool");
311 /* This structure holds information about a load. These are only
312 built for rtx bases. */
316 /* The id of the mem group of the base address. */
319 /* The offset of the first byte associated with the operation. */
322 /* The number of bytes covered by the operation, or -1 if not known. */
325 /* The mem being read. */
328 /* The next read_info for this insn. */
329 class read_info_type
*next
;
331 typedef class read_info_type
*read_info_t
;
333 static object_allocator
<read_info_type
> read_info_type_pool ("read_info_pool");
335 /* One of these records is created for each insn. */
337 struct insn_info_type
339 /* Set true if the insn contains a store but the insn itself cannot
340 be deleted. This is set if the insn is a parallel and there is
341 more than one non dead output or if the insn is in some way
345 /* This field is only used by the global algorithm. It is set true
346 if the insn contains any read of mem except for a (1). This is
347 also set if the insn is a call or has a clobber mem. If the insn
348 contains a wild read, the use_rec will be null. */
351 /* This is true only for CALL instructions which could potentially read
352 any non-frame memory location. This field is used by the global
354 bool non_frame_wild_read
;
356 /* This field is only used for the processing of const functions.
357 These functions cannot read memory, but they can read the stack
358 because that is where they may get their parms. We need to be
359 this conservative because, like the store motion pass, we don't
360 consider CALL_INSN_FUNCTION_USAGE when processing call insns.
361 Moreover, we need to distinguish two cases:
362 1. Before reload (register elimination), the stores related to
363 outgoing arguments are stack pointer based and thus deemed
364 of non-constant base in this pass. This requires special
365 handling but also means that the frame pointer based stores
366 need not be killed upon encountering a const function call.
367 2. After reload, the stores related to outgoing arguments can be
368 either stack pointer or hard frame pointer based. This means
369 that we have no other choice than also killing all the frame
370 pointer based stores upon encountering a const function call.
371 This field is set after reload for const function calls and before
372 reload for const tail function calls on targets where arg pointer
373 is the frame pointer. Having this set is less severe than a wild
374 read, it just means that all the frame related stores are killed
375 rather than all the stores. */
378 /* This field is only used for the processing of const functions.
379 It is set if the insn may contain a stack pointer based store. */
380 bool stack_pointer_based
;
382 /* This is true if any of the sets within the store contains a
383 cselib base. Such stores can only be deleted by the local
385 bool contains_cselib_groups
;
390 /* The list of mem sets or mem clobbers that are contained in this
391 insn. If the insn is deletable, it contains only one mem set.
392 But it could also contain clobbers. Insns that contain more than
393 one mem set are not deletable, but each of those mems are here in
394 order to provide info to delete other insns. */
395 store_info
*store_rec
;
397 /* The linked list of mem uses in this insn. Only the reads from
398 rtx bases are listed here. The reads to cselib bases are
399 completely processed during the first scan and so are never
401 read_info_t read_rec
;
403 /* The live fixed registers. We assume only fixed registers can
404 cause trouble by being clobbered from an expanded pattern;
405 storing only the live fixed registers (rather than all registers)
406 means less memory needs to be allocated / copied for the individual
408 regset fixed_regs_live
;
410 /* The prev insn in the basic block. */
411 struct insn_info_type
* prev_insn
;
413 /* The linked list of insns that are in consideration for removal in
414 the forwards pass through the basic block. This pointer may be
415 trash as it is not cleared when a wild read occurs. The only
416 time it is guaranteed to be correct is when the traversal starts
417 at active_local_stores. */
418 struct insn_info_type
* next_local_store
;
420 typedef struct insn_info_type
*insn_info_t
;
422 static object_allocator
<insn_info_type
> insn_info_type_pool ("insn_info_pool");
424 /* The linked list of stores that are under consideration in this
426 static insn_info_t active_local_stores
;
427 static int active_local_stores_len
;
429 struct dse_bb_info_type
431 /* Pointer to the insn info for the last insn in the block. These
432 are linked so this is how all of the insns are reached. During
433 scanning this is the current insn being scanned. */
434 insn_info_t last_insn
;
436 /* The info for the global dataflow problem. */
439 /* This is set if the transfer function should and in the wild_read
440 bitmap before applying the kill and gen sets. That vector knocks
441 out most of the bits in the bitmap and thus speeds up the
443 bool apply_wild_read
;
445 /* The following 4 bitvectors hold information about which positions
446 of which stores are live or dead. They are indexed by
449 /* The set of store positions that exist in this block before a wild read. */
452 /* The set of load positions that exist in this block above the
453 same position of a store. */
456 /* The set of stores that reach the top of the block without being
459 Do not represent the in if it is all ones. Note that this is
460 what the bitvector should logically be initialized to for a set
461 intersection problem. However, like the kill set, this is too
462 expensive. So initially, the in set will only be created for the
463 exit block and any block that contains a wild read. */
466 /* The set of stores that reach the bottom of the block from it's
469 Do not represent the in if it is all ones. Note that this is
470 what the bitvector should logically be initialized to for a set
471 intersection problem. However, like the kill and in set, this is
472 too expensive. So what is done is that the confluence operator
473 just initializes the vector from one of the out sets of the
474 successors of the block. */
477 /* The following bitvector is indexed by the reg number. It
478 contains the set of regs that are live at the current instruction
479 being processed. While it contains info for all of the
480 registers, only the hard registers are actually examined. It is used
481 to assure that shift and/or add sequences that are inserted do not
482 accidentally clobber live hard regs. */
486 typedef struct dse_bb_info_type
*bb_info_t
;
488 static object_allocator
<dse_bb_info_type
> dse_bb_info_type_pool
491 /* Table to hold all bb_infos. */
492 static bb_info_t
*bb_table
;
494 /* There is a group_info for each rtx base that is used to reference
495 memory. There are also not many of the rtx bases because they are
496 very limited in scope. */
500 /* The actual base of the address. */
503 /* The sequential id of the base. This allows us to have a
504 canonical ordering of these that is not based on addresses. */
507 /* True if there are any positions that are to be processed
509 bool process_globally
;
511 /* True if the base of this group is either the frame_pointer or
512 hard_frame_pointer. */
515 /* A mem wrapped around the base pointer for the group in order to do
516 read dependency. It must be given BLKmode in order to encompass all
517 the possible offsets from the base. */
520 /* Canonized version of base_mem's address. */
523 /* These two sets of two bitmaps are used to keep track of how many
524 stores are actually referencing that position from this base. We
525 only do this for rtx bases as this will be used to assign
526 positions in the bitmaps for the global problem. Bit N is set in
527 store1 on the first store for offset N. Bit N is set in store2
528 for the second store to offset N. This is all we need since we
529 only care about offsets that have two or more stores for them.
531 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
532 for 0 and greater offsets.
534 There is one special case here, for stores into the stack frame,
535 we will or store1 into store2 before deciding which stores look
536 at globally. This is because stores to the stack frame that have
537 no other reads before the end of the function can also be
539 bitmap store1_n
, store1_p
, store2_n
, store2_p
;
541 /* These bitmaps keep track of offsets in this group escape this function.
542 An offset escapes if it corresponds to a named variable whose
543 addressable flag is set. */
544 bitmap escaped_n
, escaped_p
;
546 /* The positions in this bitmap have the same assignments as the in,
547 out, gen and kill bitmaps. This bitmap is all zeros except for
548 the positions that are occupied by stores for this group. */
551 /* The offset_map is used to map the offsets from this base into
552 positions in the global bitmaps. It is only created after all of
553 the all of stores have been scanned and we know which ones we
555 int *offset_map_n
, *offset_map_p
;
556 int offset_map_size_n
, offset_map_size_p
;
559 static object_allocator
<group_info
> group_info_pool ("rtx_group_info_pool");
561 /* Index into the rtx_group_vec. */
562 static int rtx_group_next_id
;
565 static vec
<group_info
*> rtx_group_vec
;
568 /* This structure holds the set of changes that are being deferred
569 when removing read operation. See replace_read. */
570 struct deferred_change
573 /* The mem that is being replaced. */
576 /* The reg it is being replaced with. */
579 struct deferred_change
*next
;
582 static object_allocator
<deferred_change
> deferred_change_pool
583 ("deferred_change_pool");
585 static deferred_change
*deferred_change_list
= NULL
;
587 /* This is true except if cfun->stdarg -- i.e. we cannot do
588 this for vararg functions because they play games with the frame. */
589 static bool stores_off_frame_dead_at_return
;
591 /* Counter for stats. */
592 static int globally_deleted
;
593 static int locally_deleted
;
595 static bitmap all_blocks
;
597 /* Locations that are killed by calls in the global phase. */
598 static bitmap kill_on_calls
;
600 /* The number of bits used in the global bitmaps. */
601 static unsigned int current_position
;
603 /* Print offset range [OFFSET, OFFSET + WIDTH) to FILE. */
606 print_range (FILE *file
, poly_int64 offset
, poly_int64 width
)
609 print_dec (offset
, file
, SIGNED
);
610 fprintf (file
, "..");
611 print_dec (offset
+ width
, file
, SIGNED
);
615 /*----------------------------------------------------------------------------
619 ----------------------------------------------------------------------------*/
622 /* Hashtable callbacks for maintaining the "bases" field of
623 store_group_info, given that the addresses are function invariants. */
625 struct invariant_group_base_hasher
: nofree_ptr_hash
<group_info
>
627 static inline hashval_t
hash (const group_info
*);
628 static inline bool equal (const group_info
*, const group_info
*);
632 invariant_group_base_hasher::equal (const group_info
*gi1
,
633 const group_info
*gi2
)
635 return rtx_equal_p (gi1
->rtx_base
, gi2
->rtx_base
);
639 invariant_group_base_hasher::hash (const group_info
*gi
)
642 return hash_rtx (gi
->rtx_base
, Pmode
, &do_not_record
, NULL
, false);
645 /* Tables of group_info structures, hashed by base value. */
646 static hash_table
<invariant_group_base_hasher
> *rtx_group_table
;
649 /* Get the GROUP for BASE. Add a new group if it is not there. */
652 get_group_info (rtx base
)
654 struct group_info tmp_gi
;
658 gcc_assert (base
!= NULL_RTX
);
660 /* Find the store_base_info structure for BASE, creating a new one
662 tmp_gi
.rtx_base
= base
;
663 slot
= rtx_group_table
->find_slot (&tmp_gi
, INSERT
);
668 *slot
= gi
= group_info_pool
.allocate ();
670 gi
->id
= rtx_group_next_id
++;
671 gi
->base_mem
= gen_rtx_MEM (BLKmode
, base
);
672 gi
->canon_base_addr
= canon_rtx (base
);
673 gi
->store1_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
674 gi
->store1_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
675 gi
->store2_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
676 gi
->store2_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
677 gi
->escaped_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
678 gi
->escaped_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
679 gi
->group_kill
= BITMAP_ALLOC (&dse_bitmap_obstack
);
680 gi
->process_globally
= false;
682 (base
== frame_pointer_rtx
) || (base
== hard_frame_pointer_rtx
);
683 gi
->offset_map_size_n
= 0;
684 gi
->offset_map_size_p
= 0;
685 gi
->offset_map_n
= NULL
;
686 gi
->offset_map_p
= NULL
;
687 rtx_group_vec
.safe_push (gi
);
694 /* Initialization of data structures. */
700 globally_deleted
= 0;
702 bitmap_obstack_initialize (&dse_bitmap_obstack
);
703 gcc_obstack_init (&dse_obstack
);
705 scratch
= BITMAP_ALLOC (®_obstack
);
706 kill_on_calls
= BITMAP_ALLOC (&dse_bitmap_obstack
);
709 rtx_group_table
= new hash_table
<invariant_group_base_hasher
> (11);
711 bb_table
= XNEWVEC (bb_info_t
, last_basic_block_for_fn (cfun
));
712 rtx_group_next_id
= 0;
714 stores_off_frame_dead_at_return
= !cfun
->stdarg
;
716 init_alias_analysis ();
721 /*----------------------------------------------------------------------------
724 Scan all of the insns. Any random ordering of the blocks is fine.
725 Each block is scanned in forward order to accommodate cselib which
726 is used to remove stores with non-constant bases.
727 ----------------------------------------------------------------------------*/
729 /* Delete all of the store_info recs from INSN_INFO. */
732 free_store_info (insn_info_t insn_info
)
734 store_info
*cur
= insn_info
->store_rec
;
737 store_info
*next
= cur
->next
;
739 BITMAP_FREE (cur
->positions_needed
.large
.bmap
);
741 cse_store_info_pool
.remove (cur
);
743 rtx_store_info_pool
.remove (cur
);
747 insn_info
->cannot_delete
= true;
748 insn_info
->contains_cselib_groups
= false;
749 insn_info
->store_rec
= NULL
;
752 struct note_add_store_info
754 rtx_insn
*first
, *current
;
755 regset fixed_regs_live
;
759 /* Callback for emit_inc_dec_insn_before via note_stores.
760 Check if a register is clobbered which is live afterwards. */
763 note_add_store (rtx loc
, const_rtx expr ATTRIBUTE_UNUSED
, void *data
)
766 note_add_store_info
*info
= (note_add_store_info
*) data
;
771 /* If this register is referenced by the current or an earlier insn,
772 that's OK. E.g. this applies to the register that is being incremented
773 with this addition. */
774 for (insn
= info
->first
;
775 insn
!= NEXT_INSN (info
->current
);
776 insn
= NEXT_INSN (insn
))
777 if (reg_referenced_p (loc
, PATTERN (insn
)))
780 /* If we come here, we have a clobber of a register that's only OK
781 if that register is not live. If we don't have liveness information
782 available, fail now. */
783 if (!info
->fixed_regs_live
)
785 info
->failure
= true;
788 /* Now check if this is a live fixed register. */
789 unsigned int end_regno
= END_REGNO (loc
);
790 for (unsigned int regno
= REGNO (loc
); regno
< end_regno
; ++regno
)
791 if (REGNO_REG_SET_P (info
->fixed_regs_live
, regno
))
792 info
->failure
= true;
795 /* Callback for for_each_inc_dec that emits an INSN that sets DEST to
796 SRC + SRCOFF before insn ARG. */
799 emit_inc_dec_insn_before (rtx mem ATTRIBUTE_UNUSED
,
800 rtx op ATTRIBUTE_UNUSED
,
801 rtx dest
, rtx src
, rtx srcoff
, void *arg
)
803 insn_info_t insn_info
= (insn_info_t
) arg
;
804 rtx_insn
*insn
= insn_info
->insn
, *new_insn
, *cur
;
805 note_add_store_info info
;
807 /* We can reuse all operands without copying, because we are about
808 to delete the insn that contained it. */
812 emit_insn (gen_add3_insn (dest
, src
, srcoff
));
813 new_insn
= get_insns ();
817 new_insn
= gen_move_insn (dest
, src
);
818 info
.first
= new_insn
;
819 info
.fixed_regs_live
= insn_info
->fixed_regs_live
;
820 info
.failure
= false;
821 for (cur
= new_insn
; cur
; cur
= NEXT_INSN (cur
))
824 note_stores (cur
, note_add_store
, &info
);
827 /* If a failure was flagged above, return 1 so that for_each_inc_dec will
828 return it immediately, communicating the failure to its caller. */
832 emit_insn_before (new_insn
, insn
);
837 /* Before we delete INSN_INFO->INSN, make sure that the auto inc/dec, if it
838 is there, is split into a separate insn.
839 Return true on success (or if there was nothing to do), false on failure. */
842 check_for_inc_dec_1 (insn_info_t insn_info
)
844 rtx_insn
*insn
= insn_info
->insn
;
845 rtx note
= find_reg_note (insn
, REG_INC
, NULL_RTX
);
847 return for_each_inc_dec (PATTERN (insn
), emit_inc_dec_insn_before
,
853 /* Entry point for postreload. If you work on reload_cse, or you need this
854 anywhere else, consider if you can provide register liveness information
855 and add a parameter to this function so that it can be passed down in
856 insn_info.fixed_regs_live. */
858 check_for_inc_dec (rtx_insn
*insn
)
860 insn_info_type insn_info
;
863 insn_info
.insn
= insn
;
864 insn_info
.fixed_regs_live
= NULL
;
865 note
= find_reg_note (insn
, REG_INC
, NULL_RTX
);
867 return for_each_inc_dec (PATTERN (insn
), emit_inc_dec_insn_before
,
872 /* Delete the insn and free all of the fields inside INSN_INFO. */
875 delete_dead_store_insn (insn_info_t insn_info
)
877 read_info_t read_info
;
882 if (!check_for_inc_dec_1 (insn_info
))
884 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
885 fprintf (dump_file
, "Locally deleting insn %d\n",
886 INSN_UID (insn_info
->insn
));
888 free_store_info (insn_info
);
889 read_info
= insn_info
->read_rec
;
893 read_info_t next
= read_info
->next
;
894 read_info_type_pool
.remove (read_info
);
897 insn_info
->read_rec
= NULL
;
899 delete_insn (insn_info
->insn
);
901 insn_info
->insn
= NULL
;
903 insn_info
->wild_read
= false;
906 /* Return whether DECL, a local variable, can possibly escape the current
910 local_variable_can_escape (tree decl
)
912 if (TREE_ADDRESSABLE (decl
))
915 /* If this is a partitioned variable, we need to consider all the variables
916 in the partition. This is necessary because a store into one of them can
917 be replaced with a store into another and this may not change the outcome
918 of the escape analysis. */
919 if (cfun
->gimple_df
->decls_to_pointers
!= NULL
)
921 tree
*namep
= cfun
->gimple_df
->decls_to_pointers
->get (decl
);
923 return TREE_ADDRESSABLE (*namep
);
929 /* Return whether EXPR can possibly escape the current function scope. */
932 can_escape (tree expr
)
937 base
= get_base_address (expr
);
939 && !may_be_aliased (base
)
941 && !DECL_EXTERNAL (base
)
942 && !TREE_STATIC (base
)
943 && local_variable_can_escape (base
)))
948 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
952 set_usage_bits (group_info
*group
, poly_int64 offset
, poly_int64 width
,
955 /* Non-constant offsets and widths act as global kills, so there's no point
956 trying to use them to derive global DSE candidates. */
957 HOST_WIDE_INT i
, const_offset
, const_width
;
958 bool expr_escapes
= can_escape (expr
);
959 if (offset
.is_constant (&const_offset
)
960 && width
.is_constant (&const_width
)
961 && const_offset
> -MAX_OFFSET
962 && const_offset
+ const_width
< MAX_OFFSET
)
963 for (i
= const_offset
; i
< const_offset
+ const_width
; ++i
)
971 store1
= group
->store1_n
;
972 store2
= group
->store2_n
;
973 escaped
= group
->escaped_n
;
978 store1
= group
->store1_p
;
979 store2
= group
->store2_p
;
980 escaped
= group
->escaped_p
;
984 if (!bitmap_set_bit (store1
, ai
))
985 bitmap_set_bit (store2
, ai
);
990 if (group
->offset_map_size_n
< ai
)
991 group
->offset_map_size_n
= ai
;
995 if (group
->offset_map_size_p
< ai
)
996 group
->offset_map_size_p
= ai
;
1000 bitmap_set_bit (escaped
, ai
);
1005 reset_active_stores (void)
1007 active_local_stores
= NULL
;
1008 active_local_stores_len
= 0;
1011 /* Free all READ_REC of the LAST_INSN of BB_INFO. */
1014 free_read_records (bb_info_t bb_info
)
1016 insn_info_t insn_info
= bb_info
->last_insn
;
1017 read_info_t
*ptr
= &insn_info
->read_rec
;
1020 read_info_t next
= (*ptr
)->next
;
1021 read_info_type_pool
.remove (*ptr
);
1026 /* Set the BB_INFO so that the last insn is marked as a wild read. */
1029 add_wild_read (bb_info_t bb_info
)
1031 insn_info_t insn_info
= bb_info
->last_insn
;
1032 insn_info
->wild_read
= true;
1033 free_read_records (bb_info
);
1034 reset_active_stores ();
1037 /* Set the BB_INFO so that the last insn is marked as a wild read of
1038 non-frame locations. */
1041 add_non_frame_wild_read (bb_info_t bb_info
)
1043 insn_info_t insn_info
= bb_info
->last_insn
;
1044 insn_info
->non_frame_wild_read
= true;
1045 free_read_records (bb_info
);
1046 reset_active_stores ();
1049 /* Return true if X is a constant or one of the registers that behave
1050 as a constant over the life of a function. This is equivalent to
1051 !rtx_varies_p for memory addresses. */
1054 const_or_frame_p (rtx x
)
1059 if (GET_CODE (x
) == REG
)
1061 /* Note that we have to test for the actual rtx used for the frame
1062 and arg pointers and not just the register number in case we have
1063 eliminated the frame and/or arg pointer and are using it
1065 if (x
== frame_pointer_rtx
|| x
== hard_frame_pointer_rtx
1066 /* The arg pointer varies if it is not a fixed register. */
1067 || (x
== arg_pointer_rtx
&& fixed_regs
[ARG_POINTER_REGNUM
])
1068 || x
== pic_offset_table_rtx
)
1076 /* Take all reasonable action to put the address of MEM into the form
1077 that we can do analysis on.
1079 The gold standard is to get the address into the form: address +
1080 OFFSET where address is something that rtx_varies_p considers a
1081 constant. When we can get the address in this form, we can do
1082 global analysis on it. Note that for constant bases, address is
1083 not actually returned, only the group_id. The address can be
1086 If that fails, we try cselib to get a value we can at least use
1087 locally. If that fails we return false.
1089 The GROUP_ID is set to -1 for cselib bases and the index of the
1090 group for non_varying bases.
1092 FOR_READ is true if this is a mem read and false if not. */
1095 canon_address (rtx mem
,
1100 machine_mode address_mode
= get_address_mode (mem
);
1101 rtx mem_address
= XEXP (mem
, 0);
1102 rtx expanded_address
, address
;
1105 cselib_lookup (mem_address
, address_mode
, 1, GET_MODE (mem
));
1107 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1109 fprintf (dump_file
, " mem: ");
1110 print_inline_rtx (dump_file
, mem_address
, 0);
1111 fprintf (dump_file
, "\n");
1114 /* First see if just canon_rtx (mem_address) is const or frame,
1115 if not, try cselib_expand_value_rtx and call canon_rtx on that. */
1117 for (expanded
= 0; expanded
< 2; expanded
++)
1121 /* Use cselib to replace all of the reg references with the full
1122 expression. This will take care of the case where we have
1124 r_x = base + offset;
1129 val = *(base + offset); */
1131 expanded_address
= cselib_expand_value_rtx (mem_address
,
1134 /* If this fails, just go with the address from first
1136 if (!expanded_address
)
1140 expanded_address
= mem_address
;
1142 /* Split the address into canonical BASE + OFFSET terms. */
1143 address
= canon_rtx (expanded_address
);
1147 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1151 fprintf (dump_file
, "\n after cselib_expand address: ");
1152 print_inline_rtx (dump_file
, expanded_address
, 0);
1153 fprintf (dump_file
, "\n");
1156 fprintf (dump_file
, "\n after canon_rtx address: ");
1157 print_inline_rtx (dump_file
, address
, 0);
1158 fprintf (dump_file
, "\n");
1161 if (GET_CODE (address
) == CONST
)
1162 address
= XEXP (address
, 0);
1164 address
= strip_offset_and_add (address
, offset
);
1166 if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem
))
1167 && const_or_frame_p (address
))
1169 group_info
*group
= get_group_info (address
);
1171 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1173 fprintf (dump_file
, " gid=%d offset=", group
->id
);
1174 print_dec (*offset
, dump_file
);
1175 fprintf (dump_file
, "\n");
1178 *group_id
= group
->id
;
1183 *base
= cselib_lookup (address
, address_mode
, true, GET_MODE (mem
));
1188 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1189 fprintf (dump_file
, " no cselib val - should be a wild read.\n");
1192 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1194 fprintf (dump_file
, " varying cselib base=%u:%u offset = ",
1195 (*base
)->uid
, (*base
)->hash
);
1196 print_dec (*offset
, dump_file
);
1197 fprintf (dump_file
, "\n");
1203 /* Clear the rhs field from the active_local_stores array. */
1206 clear_rhs_from_active_local_stores (void)
1208 insn_info_t ptr
= active_local_stores
;
1212 store_info
*store_info
= ptr
->store_rec
;
1213 /* Skip the clobbers. */
1214 while (!store_info
->is_set
)
1215 store_info
= store_info
->next
;
1217 store_info
->rhs
= NULL
;
1218 store_info
->const_rhs
= NULL
;
1220 ptr
= ptr
->next_local_store
;
1225 /* Mark byte POS bytes from the beginning of store S_INFO as unneeded. */
1228 set_position_unneeded (store_info
*s_info
, int pos
)
1230 if (__builtin_expect (s_info
->is_large
, false))
1232 if (bitmap_set_bit (s_info
->positions_needed
.large
.bmap
, pos
))
1233 s_info
->positions_needed
.large
.count
++;
1236 s_info
->positions_needed
.small_bitmask
1237 &= ~(HOST_WIDE_INT_1U
<< pos
);
1240 /* Mark the whole store S_INFO as unneeded. */
1243 set_all_positions_unneeded (store_info
*s_info
)
1245 if (__builtin_expect (s_info
->is_large
, false))
1247 HOST_WIDE_INT width
;
1248 if (s_info
->width
.is_constant (&width
))
1250 bitmap_set_range (s_info
->positions_needed
.large
.bmap
, 0, width
);
1251 s_info
->positions_needed
.large
.count
= width
;
1255 gcc_checking_assert (!s_info
->positions_needed
.large
.bmap
);
1256 s_info
->positions_needed
.large
.count
= 1;
1260 s_info
->positions_needed
.small_bitmask
= HOST_WIDE_INT_0U
;
1263 /* Return TRUE if any bytes from S_INFO store are needed. */
1266 any_positions_needed_p (store_info
*s_info
)
1268 if (__builtin_expect (s_info
->is_large
, false))
1270 HOST_WIDE_INT width
;
1271 if (s_info
->width
.is_constant (&width
))
1273 gcc_checking_assert (s_info
->positions_needed
.large
.bmap
);
1274 return s_info
->positions_needed
.large
.count
< width
;
1278 gcc_checking_assert (!s_info
->positions_needed
.large
.bmap
);
1279 return s_info
->positions_needed
.large
.count
== 0;
1283 return (s_info
->positions_needed
.small_bitmask
!= HOST_WIDE_INT_0U
);
1286 /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
1287 store are known to be needed. */
1290 all_positions_needed_p (store_info
*s_info
, poly_int64 start
,
1293 gcc_assert (s_info
->rhs
);
1294 if (!s_info
->width
.is_constant ())
1296 gcc_assert (s_info
->is_large
1297 && !s_info
->positions_needed
.large
.bmap
);
1298 return s_info
->positions_needed
.large
.count
== 0;
1301 /* Otherwise, if START and WIDTH are non-constant, we're asking about
1302 a non-constant region of a constant-sized store. We can't say for
1303 sure that all positions are needed. */
1304 HOST_WIDE_INT const_start
, const_width
;
1305 if (!start
.is_constant (&const_start
)
1306 || !width
.is_constant (&const_width
))
1309 if (__builtin_expect (s_info
->is_large
, false))
1311 for (HOST_WIDE_INT i
= const_start
; i
< const_start
+ const_width
; ++i
)
1312 if (bitmap_bit_p (s_info
->positions_needed
.large
.bmap
, i
))
1318 unsigned HOST_WIDE_INT mask
1319 = lowpart_bitmask (const_width
) << const_start
;
1320 return (s_info
->positions_needed
.small_bitmask
& mask
) == mask
;
1325 static rtx
get_stored_val (store_info
*, machine_mode
, poly_int64
,
1326 poly_int64
, basic_block
, bool);
1329 /* BODY is an instruction pattern that belongs to INSN. Return 1 if
1330 there is a candidate store, after adding it to the appropriate
1331 local store group if so. */
1334 record_store (rtx body
, bb_info_t bb_info
)
1336 rtx mem
, rhs
, const_rhs
, mem_addr
;
1337 poly_int64 offset
= 0;
1338 poly_int64 width
= 0;
1339 insn_info_t insn_info
= bb_info
->last_insn
;
1340 store_info
*store_info
= NULL
;
1342 cselib_val
*base
= NULL
;
1343 insn_info_t ptr
, last
, redundant_reason
;
1344 bool store_is_unused
;
1346 if (GET_CODE (body
) != SET
&& GET_CODE (body
) != CLOBBER
)
1349 mem
= SET_DEST (body
);
1351 /* If this is not used, then this cannot be used to keep the insn
1352 from being deleted. On the other hand, it does provide something
1353 that can be used to prove that another store is dead. */
1355 = (find_reg_note (insn_info
->insn
, REG_UNUSED
, mem
) != NULL
);
1357 /* Check whether that value is a suitable memory location. */
1360 /* If the set or clobber is unused, then it does not effect our
1361 ability to get rid of the entire insn. */
1362 if (!store_is_unused
)
1363 insn_info
->cannot_delete
= true;
1367 /* At this point we know mem is a mem. */
1368 if (GET_MODE (mem
) == BLKmode
)
1370 HOST_WIDE_INT const_size
;
1371 if (GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
1373 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1374 fprintf (dump_file
, " adding wild read for (clobber (mem:BLK (scratch))\n");
1375 add_wild_read (bb_info
);
1376 insn_info
->cannot_delete
= true;
1379 /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
1380 as memset (addr, 0, 36); */
1381 else if (!MEM_SIZE_KNOWN_P (mem
)
1382 || maybe_le (MEM_SIZE (mem
), 0)
1383 /* This is a limit on the bitmap size, which is only relevant
1384 for constant-sized MEMs. */
1385 || (MEM_SIZE (mem
).is_constant (&const_size
)
1386 && const_size
> MAX_OFFSET
)
1387 || GET_CODE (body
) != SET
1388 || !CONST_INT_P (SET_SRC (body
)))
1390 if (!store_is_unused
)
1392 /* If the set or clobber is unused, then it does not effect our
1393 ability to get rid of the entire insn. */
1394 insn_info
->cannot_delete
= true;
1395 clear_rhs_from_active_local_stores ();
1401 /* We can still process a volatile mem, we just cannot delete it. */
1402 if (MEM_VOLATILE_P (mem
))
1403 insn_info
->cannot_delete
= true;
1405 if (!canon_address (mem
, &group_id
, &offset
, &base
))
1407 clear_rhs_from_active_local_stores ();
1411 if (GET_MODE (mem
) == BLKmode
)
1412 width
= MEM_SIZE (mem
);
1414 width
= GET_MODE_SIZE (GET_MODE (mem
));
1416 if (!endpoint_representable_p (offset
, width
))
1418 clear_rhs_from_active_local_stores ();
1422 if (known_eq (width
, 0))
1427 /* In the restrictive case where the base is a constant or the
1428 frame pointer we can do global analysis. */
1431 = rtx_group_vec
[group_id
];
1432 tree expr
= MEM_EXPR (mem
);
1434 store_info
= rtx_store_info_pool
.allocate ();
1435 set_usage_bits (group
, offset
, width
, expr
);
1437 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1439 fprintf (dump_file
, " processing const base store gid=%d",
1441 print_range (dump_file
, offset
, width
);
1442 fprintf (dump_file
, "\n");
1447 if (may_be_sp_based_p (XEXP (mem
, 0)))
1448 insn_info
->stack_pointer_based
= true;
1449 insn_info
->contains_cselib_groups
= true;
1451 store_info
= cse_store_info_pool
.allocate ();
1454 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1456 fprintf (dump_file
, " processing cselib store ");
1457 print_range (dump_file
, offset
, width
);
1458 fprintf (dump_file
, "\n");
1462 const_rhs
= rhs
= NULL_RTX
;
1463 if (GET_CODE (body
) == SET
1464 /* No place to keep the value after ra. */
1465 && !reload_completed
1466 && (REG_P (SET_SRC (body
))
1467 || GET_CODE (SET_SRC (body
)) == SUBREG
1468 || CONSTANT_P (SET_SRC (body
)))
1469 && !MEM_VOLATILE_P (mem
)
1470 /* Sometimes the store and reload is used for truncation and
1472 && !(FLOAT_MODE_P (GET_MODE (mem
)) && (flag_float_store
)))
1474 rhs
= SET_SRC (body
);
1475 if (CONSTANT_P (rhs
))
1477 else if (body
== PATTERN (insn_info
->insn
))
1479 rtx tem
= find_reg_note (insn_info
->insn
, REG_EQUAL
, NULL_RTX
);
1480 if (tem
&& CONSTANT_P (XEXP (tem
, 0)))
1481 const_rhs
= XEXP (tem
, 0);
1483 if (const_rhs
== NULL_RTX
&& REG_P (rhs
))
1485 rtx tem
= cselib_expand_value_rtx (rhs
, scratch
, 5);
1487 if (tem
&& CONSTANT_P (tem
))
1492 /* Check to see if this stores causes some other stores to be
1494 ptr
= active_local_stores
;
1496 redundant_reason
= NULL
;
1497 mem
= canon_rtx (mem
);
1500 mem_addr
= base
->val_rtx
;
1503 group_info
*group
= rtx_group_vec
[group_id
];
1504 mem_addr
= group
->canon_base_addr
;
1506 if (maybe_ne (offset
, 0))
1507 mem_addr
= plus_constant (get_address_mode (mem
), mem_addr
, offset
);
1511 insn_info_t next
= ptr
->next_local_store
;
1512 class store_info
*s_info
= ptr
->store_rec
;
1515 /* Skip the clobbers. We delete the active insn if this insn
1516 shadows the set. To have been put on the active list, it
1517 has exactly on set. */
1518 while (!s_info
->is_set
)
1519 s_info
= s_info
->next
;
1521 if (s_info
->group_id
== group_id
&& s_info
->cse_base
== base
)
1524 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1526 fprintf (dump_file
, " trying store in insn=%d gid=%d",
1527 INSN_UID (ptr
->insn
), s_info
->group_id
);
1528 print_range (dump_file
, s_info
->offset
, s_info
->width
);
1529 fprintf (dump_file
, "\n");
1532 /* Even if PTR won't be eliminated as unneeded, if both
1533 PTR and this insn store the same constant value, we might
1534 eliminate this insn instead. */
1535 if (s_info
->const_rhs
1537 && known_subrange_p (offset
, width
,
1538 s_info
->offset
, s_info
->width
)
1539 && all_positions_needed_p (s_info
, offset
- s_info
->offset
,
1541 /* We can only remove the later store if the earlier aliases
1542 at least all accesses the later one. */
1543 && ((MEM_ALIAS_SET (mem
) == MEM_ALIAS_SET (s_info
->mem
)
1544 || alias_set_subset_of (MEM_ALIAS_SET (mem
),
1545 MEM_ALIAS_SET (s_info
->mem
)))
1546 && (!MEM_EXPR (s_info
->mem
)
1547 || refs_same_for_tbaa_p (MEM_EXPR (s_info
->mem
),
1550 if (GET_MODE (mem
) == BLKmode
)
1552 if (GET_MODE (s_info
->mem
) == BLKmode
1553 && s_info
->const_rhs
== const_rhs
)
1554 redundant_reason
= ptr
;
1556 else if (s_info
->const_rhs
== const0_rtx
1557 && const_rhs
== const0_rtx
)
1558 redundant_reason
= ptr
;
1563 val
= get_stored_val (s_info
, GET_MODE (mem
), offset
, width
,
1564 BLOCK_FOR_INSN (insn_info
->insn
),
1566 if (get_insns () != NULL
)
1569 if (val
&& rtx_equal_p (val
, const_rhs
))
1570 redundant_reason
= ptr
;
1574 HOST_WIDE_INT begin_unneeded
, const_s_width
, const_width
;
1575 if (known_subrange_p (s_info
->offset
, s_info
->width
, offset
, width
))
1576 /* The new store touches every byte that S_INFO does. */
1577 set_all_positions_unneeded (s_info
);
1578 else if ((offset
- s_info
->offset
).is_constant (&begin_unneeded
)
1579 && s_info
->width
.is_constant (&const_s_width
)
1580 && width
.is_constant (&const_width
))
1582 HOST_WIDE_INT end_unneeded
= begin_unneeded
+ const_width
;
1583 begin_unneeded
= MAX (begin_unneeded
, 0);
1584 end_unneeded
= MIN (end_unneeded
, const_s_width
);
1585 for (i
= begin_unneeded
; i
< end_unneeded
; ++i
)
1586 set_position_unneeded (s_info
, i
);
1590 /* We don't know which parts of S_INFO are needed and
1591 which aren't, so invalidate the RHS. */
1593 s_info
->const_rhs
= NULL
;
1596 else if (s_info
->rhs
)
1597 /* Need to see if it is possible for this store to overwrite
1598 the value of store_info. If it is, set the rhs to NULL to
1599 keep it from being used to remove a load. */
1601 if (canon_output_dependence (s_info
->mem
, true,
1602 mem
, GET_MODE (mem
),
1606 s_info
->const_rhs
= NULL
;
1610 /* An insn can be deleted if every position of every one of
1611 its s_infos is zero. */
1612 if (any_positions_needed_p (s_info
))
1617 insn_info_t insn_to_delete
= ptr
;
1619 active_local_stores_len
--;
1621 last
->next_local_store
= ptr
->next_local_store
;
1623 active_local_stores
= ptr
->next_local_store
;
1625 if (!insn_to_delete
->cannot_delete
)
1626 delete_dead_store_insn (insn_to_delete
);
1634 /* Finish filling in the store_info. */
1635 store_info
->next
= insn_info
->store_rec
;
1636 insn_info
->store_rec
= store_info
;
1637 store_info
->mem
= mem
;
1638 store_info
->mem_addr
= mem_addr
;
1639 store_info
->cse_base
= base
;
1640 HOST_WIDE_INT const_width
;
1641 if (!width
.is_constant (&const_width
))
1643 store_info
->is_large
= true;
1644 store_info
->positions_needed
.large
.count
= 0;
1645 store_info
->positions_needed
.large
.bmap
= NULL
;
1647 else if (const_width
> HOST_BITS_PER_WIDE_INT
)
1649 store_info
->is_large
= true;
1650 store_info
->positions_needed
.large
.count
= 0;
1651 store_info
->positions_needed
.large
.bmap
= BITMAP_ALLOC (&dse_bitmap_obstack
);
1655 store_info
->is_large
= false;
1656 store_info
->positions_needed
.small_bitmask
1657 = lowpart_bitmask (const_width
);
1659 store_info
->group_id
= group_id
;
1660 store_info
->offset
= offset
;
1661 store_info
->width
= width
;
1662 store_info
->is_set
= GET_CODE (body
) == SET
;
1663 store_info
->rhs
= rhs
;
1664 store_info
->const_rhs
= const_rhs
;
1665 store_info
->redundant_reason
= redundant_reason
;
1667 /* If this is a clobber, we return 0. We will only be able to
1668 delete this insn if there is only one store USED store, but we
1669 can use the clobber to delete other stores earlier. */
1670 return store_info
->is_set
? 1 : 0;
1675 dump_insn_info (const char * start
, insn_info_t insn_info
)
1677 fprintf (dump_file
, "%s insn=%d %s\n", start
,
1678 INSN_UID (insn_info
->insn
),
1679 insn_info
->store_rec
? "has store" : "naked");
1683 /* If the modes are different and the value's source and target do not
1684 line up, we need to extract the value from lower part of the rhs of
1685 the store, shift it, and then put it into a form that can be shoved
1686 into the read_insn. This function generates a right SHIFT of a
1687 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The
1688 shift sequence is returned or NULL if we failed to find a
1692 find_shift_sequence (poly_int64 access_size
,
1693 store_info
*store_info
,
1694 machine_mode read_mode
,
1695 poly_int64 shift
, bool speed
, bool require_cst
)
1697 machine_mode store_mode
= GET_MODE (store_info
->mem
);
1698 scalar_int_mode new_mode
;
1699 rtx read_reg
= NULL
;
1701 /* Some machines like the x86 have shift insns for each size of
1702 operand. Other machines like the ppc or the ia-64 may only have
1703 shift insns that shift values within 32 or 64 bit registers.
1704 This loop tries to find the smallest shift insn that will right
1705 justify the value we want to read but is available in one insn on
1708 opt_scalar_int_mode new_mode_iter
;
1709 FOR_EACH_MODE_FROM (new_mode_iter
,
1710 smallest_int_mode_for_size (access_size
* BITS_PER_UNIT
))
1712 rtx target
, new_reg
, new_lhs
;
1713 rtx_insn
*shift_seq
, *insn
;
1716 new_mode
= new_mode_iter
.require ();
1717 if (GET_MODE_BITSIZE (new_mode
) > BITS_PER_WORD
)
1720 /* If a constant was stored into memory, try to simplify it here,
1721 otherwise the cost of the shift might preclude this optimization
1722 e.g. at -Os, even when no actual shift will be needed. */
1723 if (store_info
->const_rhs
)
1725 poly_uint64 byte
= subreg_lowpart_offset (new_mode
, store_mode
);
1726 rtx ret
= simplify_subreg (new_mode
, store_info
->const_rhs
,
1728 if (ret
&& CONSTANT_P (ret
))
1730 rtx shift_rtx
= gen_int_shift_amount (new_mode
, shift
);
1731 ret
= simplify_const_binary_operation (LSHIFTRT
, new_mode
,
1733 if (ret
&& CONSTANT_P (ret
))
1735 byte
= subreg_lowpart_offset (read_mode
, new_mode
);
1736 ret
= simplify_subreg (read_mode
, ret
, new_mode
, byte
);
1737 if (ret
&& CONSTANT_P (ret
)
1738 && (set_src_cost (ret
, read_mode
, speed
)
1739 <= COSTS_N_INSNS (1)))
1748 /* Try a wider mode if truncating the store mode to NEW_MODE
1749 requires a real instruction. */
1750 if (maybe_lt (GET_MODE_SIZE (new_mode
), GET_MODE_SIZE (store_mode
))
1751 && !TRULY_NOOP_TRUNCATION_MODES_P (new_mode
, store_mode
))
1754 /* Also try a wider mode if the necessary punning is either not
1755 desirable or not possible. */
1756 if (!CONSTANT_P (store_info
->rhs
)
1757 && !targetm
.modes_tieable_p (new_mode
, store_mode
))
1760 new_reg
= gen_reg_rtx (new_mode
);
1764 /* In theory we could also check for an ashr. Ian Taylor knows
1765 of one dsp where the cost of these two was not the same. But
1766 this really is a rare case anyway. */
1767 target
= expand_binop (new_mode
, lshr_optab
, new_reg
,
1768 gen_int_shift_amount (new_mode
, shift
),
1769 new_reg
, 1, OPTAB_DIRECT
);
1771 shift_seq
= get_insns ();
1774 if (target
!= new_reg
|| shift_seq
== NULL
)
1778 for (insn
= shift_seq
; insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
1780 cost
+= insn_cost (insn
, speed
);
1782 /* The computation up to here is essentially independent
1783 of the arguments and could be precomputed. It may
1784 not be worth doing so. We could precompute if
1785 worthwhile or at least cache the results. The result
1786 technically depends on both SHIFT and ACCESS_SIZE,
1787 but in practice the answer will depend only on ACCESS_SIZE. */
1789 if (cost
> COSTS_N_INSNS (1))
1792 new_lhs
= extract_low_bits (new_mode
, store_mode
,
1793 copy_rtx (store_info
->rhs
));
1794 if (new_lhs
== NULL_RTX
)
1797 /* We found an acceptable shift. Generate a move to
1798 take the value from the store and put it into the
1799 shift pseudo, then shift it, then generate another
1800 move to put in into the target of the read. */
1801 emit_move_insn (new_reg
, new_lhs
);
1802 emit_insn (shift_seq
);
1803 read_reg
= extract_low_bits (read_mode
, new_mode
, new_reg
);
1811 /* Call back for note_stores to find the hard regs set or clobbered by
1812 insn. Data is a bitmap of the hardregs set so far. */
1815 look_for_hardregs (rtx x
, const_rtx pat ATTRIBUTE_UNUSED
, void *data
)
1817 bitmap regs_set
= (bitmap
) data
;
1820 && HARD_REGISTER_P (x
))
1821 bitmap_set_range (regs_set
, REGNO (x
), REG_NREGS (x
));
1824 /* Helper function for replace_read and record_store.
1825 Attempt to return a value of mode READ_MODE stored in STORE_INFO,
1826 consisting of READ_WIDTH bytes starting from READ_OFFSET. Return NULL
1827 if not successful. If REQUIRE_CST is true, return always constant. */
1830 get_stored_val (store_info
*store_info
, machine_mode read_mode
,
1831 poly_int64 read_offset
, poly_int64 read_width
,
1832 basic_block bb
, bool require_cst
)
1834 machine_mode store_mode
= GET_MODE (store_info
->mem
);
1838 /* To get here the read is within the boundaries of the write so
1839 shift will never be negative. Start out with the shift being in
1841 if (store_mode
== BLKmode
)
1843 else if (BYTES_BIG_ENDIAN
)
1844 gap
= ((store_info
->offset
+ store_info
->width
)
1845 - (read_offset
+ read_width
));
1847 gap
= read_offset
- store_info
->offset
;
1849 if (gap
.is_constant () && maybe_ne (gap
, 0))
1851 poly_int64 shift
= gap
* BITS_PER_UNIT
;
1852 poly_int64 access_size
= GET_MODE_SIZE (read_mode
) + gap
;
1853 read_reg
= find_shift_sequence (access_size
, store_info
, read_mode
,
1854 shift
, optimize_bb_for_speed_p (bb
),
1857 else if (store_mode
== BLKmode
)
1859 /* The store is a memset (addr, const_val, const_size). */
1860 gcc_assert (CONST_INT_P (store_info
->rhs
));
1861 scalar_int_mode int_store_mode
;
1862 if (!int_mode_for_mode (read_mode
).exists (&int_store_mode
))
1863 read_reg
= NULL_RTX
;
1864 else if (store_info
->rhs
== const0_rtx
)
1865 read_reg
= extract_low_bits (read_mode
, int_store_mode
, const0_rtx
);
1866 else if (GET_MODE_BITSIZE (int_store_mode
) > HOST_BITS_PER_WIDE_INT
1867 || BITS_PER_UNIT
>= HOST_BITS_PER_WIDE_INT
)
1868 read_reg
= NULL_RTX
;
1871 unsigned HOST_WIDE_INT c
1872 = INTVAL (store_info
->rhs
)
1873 & ((HOST_WIDE_INT_1
<< BITS_PER_UNIT
) - 1);
1874 int shift
= BITS_PER_UNIT
;
1875 while (shift
< HOST_BITS_PER_WIDE_INT
)
1880 read_reg
= gen_int_mode (c
, int_store_mode
);
1881 read_reg
= extract_low_bits (read_mode
, int_store_mode
, read_reg
);
1884 else if (store_info
->const_rhs
1886 || GET_MODE_CLASS (read_mode
) != GET_MODE_CLASS (store_mode
)))
1887 read_reg
= extract_low_bits (read_mode
, store_mode
,
1888 copy_rtx (store_info
->const_rhs
));
1890 read_reg
= extract_low_bits (read_mode
, store_mode
,
1891 copy_rtx (store_info
->rhs
));
1892 if (require_cst
&& read_reg
&& !CONSTANT_P (read_reg
))
1893 read_reg
= NULL_RTX
;
1897 /* Take a sequence of:
1920 Depending on the alignment and the mode of the store and
1924 The STORE_INFO and STORE_INSN are for the store and READ_INFO
1925 and READ_INSN are for the read. Return true if the replacement
1929 replace_read (store_info
*store_info
, insn_info_t store_insn
,
1930 read_info_t read_info
, insn_info_t read_insn
, rtx
*loc
,
1933 machine_mode store_mode
= GET_MODE (store_info
->mem
);
1934 machine_mode read_mode
= GET_MODE (read_info
->mem
);
1935 rtx_insn
*insns
, *this_insn
;
1942 /* Create a sequence of instructions to set up the read register.
1943 This sequence goes immediately before the store and its result
1944 is read by the load.
1946 We need to keep this in perspective. We are replacing a read
1947 with a sequence of insns, but the read will almost certainly be
1948 in cache, so it is not going to be an expensive one. Thus, we
1949 are not willing to do a multi insn shift or worse a subroutine
1950 call to get rid of the read. */
1951 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1952 fprintf (dump_file
, "trying to replace %smode load in insn %d"
1953 " from %smode store in insn %d\n",
1954 GET_MODE_NAME (read_mode
), INSN_UID (read_insn
->insn
),
1955 GET_MODE_NAME (store_mode
), INSN_UID (store_insn
->insn
));
1957 bb
= BLOCK_FOR_INSN (read_insn
->insn
);
1958 read_reg
= get_stored_val (store_info
,
1959 read_mode
, read_info
->offset
, read_info
->width
,
1961 if (read_reg
== NULL_RTX
)
1964 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1965 fprintf (dump_file
, " -- could not extract bits of stored value\n");
1968 /* Force the value into a new register so that it won't be clobbered
1969 between the store and the load. */
1970 read_reg
= copy_to_mode_reg (read_mode
, read_reg
);
1971 insns
= get_insns ();
1974 if (insns
!= NULL_RTX
)
1976 /* Now we have to scan the set of new instructions to see if the
1977 sequence contains and sets of hardregs that happened to be
1978 live at this point. For instance, this can happen if one of
1979 the insns sets the CC and the CC happened to be live at that
1980 point. This does occasionally happen, see PR 37922. */
1981 bitmap regs_set
= BITMAP_ALLOC (®_obstack
);
1983 for (this_insn
= insns
; this_insn
!= NULL_RTX
; this_insn
= NEXT_INSN (this_insn
))
1984 note_stores (this_insn
, look_for_hardregs
, regs_set
);
1986 bitmap_and_into (regs_set
, regs_live
);
1987 if (!bitmap_empty_p (regs_set
))
1989 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1992 "abandoning replacement because sequence clobbers live hardregs:");
1993 df_print_regset (dump_file
, regs_set
);
1996 BITMAP_FREE (regs_set
);
1999 BITMAP_FREE (regs_set
);
2002 if (validate_change (read_insn
->insn
, loc
, read_reg
, 0))
2004 deferred_change
*change
= deferred_change_pool
.allocate ();
2006 /* Insert this right before the store insn where it will be safe
2007 from later insns that might change it before the read. */
2008 emit_insn_before (insns
, store_insn
->insn
);
2010 /* And now for the kludge part: cselib croaks if you just
2011 return at this point. There are two reasons for this:
2013 1) Cselib has an idea of how many pseudos there are and
2014 that does not include the new ones we just added.
2016 2) Cselib does not know about the move insn we added
2017 above the store_info, and there is no way to tell it
2018 about it, because it has "moved on".
2020 Problem (1) is fixable with a certain amount of engineering.
2021 Problem (2) is requires starting the bb from scratch. This
2024 So we are just going to have to lie. The move/extraction
2025 insns are not really an issue, cselib did not see them. But
2026 the use of the new pseudo read_insn is a real problem because
2027 cselib has not scanned this insn. The way that we solve this
2028 problem is that we are just going to put the mem back for now
2029 and when we are finished with the block, we undo this. We
2030 keep a table of mems to get rid of. At the end of the basic
2031 block we can put them back. */
2033 *loc
= read_info
->mem
;
2034 change
->next
= deferred_change_list
;
2035 deferred_change_list
= change
;
2037 change
->reg
= read_reg
;
2039 /* Get rid of the read_info, from the point of view of the
2040 rest of dse, play like this read never happened. */
2041 read_insn
->read_rec
= read_info
->next
;
2042 read_info_type_pool
.remove (read_info
);
2043 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2045 fprintf (dump_file
, " -- replaced the loaded MEM with ");
2046 print_simple_rtl (dump_file
, read_reg
);
2047 fprintf (dump_file
, "\n");
2053 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2055 fprintf (dump_file
, " -- replacing the loaded MEM with ");
2056 print_simple_rtl (dump_file
, read_reg
);
2057 fprintf (dump_file
, " led to an invalid instruction\n");
2063 /* Check the address of MEM *LOC and kill any appropriate stores that may
2067 check_mem_read_rtx (rtx
*loc
, bb_info_t bb_info
)
2069 rtx mem
= *loc
, mem_addr
;
2070 insn_info_t insn_info
;
2071 poly_int64 offset
= 0;
2072 poly_int64 width
= 0;
2073 cselib_val
*base
= NULL
;
2075 read_info_t read_info
;
2077 insn_info
= bb_info
->last_insn
;
2079 if ((MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2080 || MEM_VOLATILE_P (mem
))
2082 if (crtl
->stack_protect_guard
2083 && (MEM_EXPR (mem
) == crtl
->stack_protect_guard
2084 || (crtl
->stack_protect_guard_decl
2085 && MEM_EXPR (mem
) == crtl
->stack_protect_guard_decl
))
2086 && MEM_VOLATILE_P (mem
))
2088 /* This is either the stack protector canary on the stack,
2089 which ought to be written by a MEM_VOLATILE_P store and
2090 thus shouldn't be deleted and is read at the very end of
2091 function, but shouldn't conflict with any other store.
2092 Or it is __stack_chk_guard variable or TLS or whatever else
2093 MEM holding the canary value, which really shouldn't be
2094 ever modified in -fstack-protector* protected functions,
2095 otherwise the prologue store wouldn't match the epilogue
2097 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2098 fprintf (dump_file
, " stack protector canary read ignored.\n");
2099 insn_info
->cannot_delete
= true;
2103 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2104 fprintf (dump_file
, " adding wild read, volatile or barrier.\n");
2105 add_wild_read (bb_info
);
2106 insn_info
->cannot_delete
= true;
2110 /* If it is reading readonly mem, then there can be no conflict with
2112 if (MEM_READONLY_P (mem
))
2115 if (!canon_address (mem
, &group_id
, &offset
, &base
))
2117 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2118 fprintf (dump_file
, " adding wild read, canon_address failure.\n");
2119 add_wild_read (bb_info
);
2123 if (GET_MODE (mem
) == BLKmode
)
2126 width
= GET_MODE_SIZE (GET_MODE (mem
));
2128 if (!endpoint_representable_p (offset
, known_eq (width
, -1) ? 1 : width
))
2130 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2131 fprintf (dump_file
, " adding wild read, due to overflow.\n");
2132 add_wild_read (bb_info
);
2136 read_info
= read_info_type_pool
.allocate ();
2137 read_info
->group_id
= group_id
;
2138 read_info
->mem
= mem
;
2139 read_info
->offset
= offset
;
2140 read_info
->width
= width
;
2141 read_info
->next
= insn_info
->read_rec
;
2142 insn_info
->read_rec
= read_info
;
2144 mem_addr
= base
->val_rtx
;
2147 group_info
*group
= rtx_group_vec
[group_id
];
2148 mem_addr
= group
->canon_base_addr
;
2150 if (maybe_ne (offset
, 0))
2151 mem_addr
= plus_constant (get_address_mode (mem
), mem_addr
, offset
);
2155 /* This is the restricted case where the base is a constant or
2156 the frame pointer and offset is a constant. */
2157 insn_info_t i_ptr
= active_local_stores
;
2158 insn_info_t last
= NULL
;
2160 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2162 if (!known_size_p (width
))
2163 fprintf (dump_file
, " processing const load gid=%d[BLK]\n",
2167 fprintf (dump_file
, " processing const load gid=%d", group_id
);
2168 print_range (dump_file
, offset
, width
);
2169 fprintf (dump_file
, "\n");
2175 bool remove
= false;
2176 store_info
*store_info
= i_ptr
->store_rec
;
2178 /* Skip the clobbers. */
2179 while (!store_info
->is_set
)
2180 store_info
= store_info
->next
;
2182 /* There are three cases here. */
2183 if (store_info
->group_id
< 0)
2184 /* We have a cselib store followed by a read from a
2187 = canon_true_dependence (store_info
->mem
,
2188 GET_MODE (store_info
->mem
),
2189 store_info
->mem_addr
,
2192 else if (group_id
== store_info
->group_id
)
2194 /* This is a block mode load. We may get lucky and
2195 canon_true_dependence may save the day. */
2196 if (!known_size_p (width
))
2198 = canon_true_dependence (store_info
->mem
,
2199 GET_MODE (store_info
->mem
),
2200 store_info
->mem_addr
,
2203 /* If this read is just reading back something that we just
2204 stored, rewrite the read. */
2208 && known_subrange_p (offset
, width
, store_info
->offset
,
2210 && all_positions_needed_p (store_info
,
2211 offset
- store_info
->offset
,
2213 && replace_read (store_info
, i_ptr
, read_info
,
2214 insn_info
, loc
, bb_info
->regs_live
))
2217 /* The bases are the same, just see if the offsets
2219 if (ranges_maybe_overlap_p (offset
, width
,
2227 The else case that is missing here is that the
2228 bases are constant but different. There is nothing
2229 to do here because there is no overlap. */
2233 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2234 dump_insn_info ("removing from active", i_ptr
);
2236 active_local_stores_len
--;
2238 last
->next_local_store
= i_ptr
->next_local_store
;
2240 active_local_stores
= i_ptr
->next_local_store
;
2244 i_ptr
= i_ptr
->next_local_store
;
2249 insn_info_t i_ptr
= active_local_stores
;
2250 insn_info_t last
= NULL
;
2251 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2253 fprintf (dump_file
, " processing cselib load mem:");
2254 print_inline_rtx (dump_file
, mem
, 0);
2255 fprintf (dump_file
, "\n");
2260 bool remove
= false;
2261 store_info
*store_info
= i_ptr
->store_rec
;
2263 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2264 fprintf (dump_file
, " processing cselib load against insn %d\n",
2265 INSN_UID (i_ptr
->insn
));
2267 /* Skip the clobbers. */
2268 while (!store_info
->is_set
)
2269 store_info
= store_info
->next
;
2271 /* If this read is just reading back something that we just
2272 stored, rewrite the read. */
2274 && store_info
->group_id
== -1
2275 && store_info
->cse_base
== base
2276 && known_subrange_p (offset
, width
, store_info
->offset
,
2278 && all_positions_needed_p (store_info
,
2279 offset
- store_info
->offset
, width
)
2280 && replace_read (store_info
, i_ptr
, read_info
, insn_info
, loc
,
2281 bb_info
->regs_live
))
2284 remove
= canon_true_dependence (store_info
->mem
,
2285 GET_MODE (store_info
->mem
),
2286 store_info
->mem_addr
,
2291 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2292 dump_insn_info ("removing from active", i_ptr
);
2294 active_local_stores_len
--;
2296 last
->next_local_store
= i_ptr
->next_local_store
;
2298 active_local_stores
= i_ptr
->next_local_store
;
2302 i_ptr
= i_ptr
->next_local_store
;
2307 /* A note_uses 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 subrtx_ptr_iterator::array_type array
;
2315 FOR_EACH_SUBRTX_PTR (iter
, array
, loc
, NONCONST
)
2319 check_mem_read_rtx (loc
, (bb_info_t
) data
);
2324 /* Get arguments passed to CALL_INSN. Return TRUE if successful.
2325 So far it only handles arguments passed in registers. */
2328 get_call_args (rtx call_insn
, tree fn
, rtx
*args
, int nargs
)
2330 CUMULATIVE_ARGS args_so_far_v
;
2331 cumulative_args_t args_so_far
;
2335 INIT_CUMULATIVE_ARGS (args_so_far_v
, TREE_TYPE (fn
), NULL_RTX
, 0, 3);
2336 args_so_far
= pack_cumulative_args (&args_so_far_v
);
2338 arg
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2340 arg
!= void_list_node
&& idx
< nargs
;
2341 arg
= TREE_CHAIN (arg
), idx
++)
2343 scalar_int_mode mode
;
2346 if (!is_int_mode (TYPE_MODE (TREE_VALUE (arg
)), &mode
))
2349 function_arg_info
arg (mode
, /*named=*/true);
2350 reg
= targetm
.calls
.function_arg (args_so_far
, arg
);
2351 if (!reg
|| !REG_P (reg
) || GET_MODE (reg
) != mode
)
2354 for (link
= CALL_INSN_FUNCTION_USAGE (call_insn
);
2356 link
= XEXP (link
, 1))
2357 if (GET_CODE (XEXP (link
, 0)) == USE
)
2359 scalar_int_mode arg_mode
;
2360 args
[idx
] = XEXP (XEXP (link
, 0), 0);
2361 if (REG_P (args
[idx
])
2362 && REGNO (args
[idx
]) == REGNO (reg
)
2363 && (GET_MODE (args
[idx
]) == mode
2364 || (is_int_mode (GET_MODE (args
[idx
]), &arg_mode
)
2365 && (GET_MODE_SIZE (arg_mode
) <= UNITS_PER_WORD
)
2366 && (GET_MODE_SIZE (arg_mode
) > GET_MODE_SIZE (mode
)))))
2372 tmp
= cselib_expand_value_rtx (args
[idx
], scratch
, 5);
2373 if (GET_MODE (args
[idx
]) != mode
)
2375 if (!tmp
|| !CONST_INT_P (tmp
))
2377 tmp
= gen_int_mode (INTVAL (tmp
), mode
);
2382 targetm
.calls
.function_arg_advance (args_so_far
, arg
);
2384 if (arg
!= void_list_node
|| idx
!= nargs
)
2389 /* Return a bitmap of the fixed registers contained in IN. */
2392 copy_fixed_regs (const_bitmap in
)
2396 ret
= ALLOC_REG_SET (NULL
);
2397 bitmap_and (ret
, in
, bitmap_view
<HARD_REG_SET
> (fixed_reg_set
));
2401 /* Apply record_store to all candidate stores in INSN. Mark INSN
2402 if some part of it is not a candidate store and assigns to a
2403 non-register target. */
2406 scan_insn (bb_info_t bb_info
, rtx_insn
*insn
, int max_active_local_stores
)
2409 insn_info_type
*insn_info
= insn_info_type_pool
.allocate ();
2411 memset (insn_info
, 0, sizeof (struct insn_info_type
));
2413 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2414 fprintf (dump_file
, "\n**scanning insn=%d\n",
2417 insn_info
->prev_insn
= bb_info
->last_insn
;
2418 insn_info
->insn
= insn
;
2419 bb_info
->last_insn
= insn_info
;
2421 if (DEBUG_INSN_P (insn
))
2423 insn_info
->cannot_delete
= true;
2427 /* Look at all of the uses in the insn. */
2428 note_uses (&PATTERN (insn
), check_mem_read_use
, bb_info
);
2434 tree memset_call
= NULL_TREE
;
2436 insn_info
->cannot_delete
= true;
2438 /* Const functions cannot do anything bad i.e. read memory,
2439 however, they can read their parameters which may have
2440 been pushed onto the stack.
2441 memset and bzero don't read memory either. */
2442 const_call
= RTL_CONST_CALL_P (insn
);
2444 && (call
= get_call_rtx_from (insn
))
2445 && (sym
= XEXP (XEXP (call
, 0), 0))
2446 && GET_CODE (sym
) == SYMBOL_REF
2447 && SYMBOL_REF_DECL (sym
)
2448 && TREE_CODE (SYMBOL_REF_DECL (sym
)) == FUNCTION_DECL
2449 && fndecl_built_in_p (SYMBOL_REF_DECL (sym
), BUILT_IN_MEMSET
))
2450 memset_call
= SYMBOL_REF_DECL (sym
);
2452 if (const_call
|| memset_call
)
2454 insn_info_t i_ptr
= active_local_stores
;
2455 insn_info_t last
= NULL
;
2457 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2458 fprintf (dump_file
, "%s call %d\n",
2459 const_call
? "const" : "memset", INSN_UID (insn
));
2461 /* See the head comment of the frame_read field. */
2462 if (reload_completed
2463 /* Tail calls are storing their arguments using
2464 arg pointer. If it is a frame pointer on the target,
2465 even before reload we need to kill frame pointer based
2467 || (SIBLING_CALL_P (insn
)
2468 && HARD_FRAME_POINTER_IS_ARG_POINTER
))
2469 insn_info
->frame_read
= true;
2471 /* Loop over the active stores and remove those which are
2472 killed by the const function call. */
2475 bool remove_store
= false;
2477 /* The stack pointer based stores are always killed. */
2478 if (i_ptr
->stack_pointer_based
)
2479 remove_store
= true;
2481 /* If the frame is read, the frame related stores are killed. */
2482 else if (insn_info
->frame_read
)
2484 store_info
*store_info
= i_ptr
->store_rec
;
2486 /* Skip the clobbers. */
2487 while (!store_info
->is_set
)
2488 store_info
= store_info
->next
;
2490 if (store_info
->group_id
>= 0
2491 && rtx_group_vec
[store_info
->group_id
]->frame_related
)
2492 remove_store
= true;
2497 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
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
, INTVAL (args
[2]));
2522 body
= gen_rtx_SET (mem
, args
[1]);
2523 mems_found
+= record_store (body
, bb_info
);
2524 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2525 fprintf (dump_file
, "handling memset as BLKmode store\n");
2526 if (mems_found
== 1)
2528 if (active_local_stores_len
++ >= max_active_local_stores
)
2530 active_local_stores_len
= 1;
2531 active_local_stores
= NULL
;
2533 insn_info
->fixed_regs_live
2534 = copy_fixed_regs (bb_info
->regs_live
);
2535 insn_info
->next_local_store
= active_local_stores
;
2536 active_local_stores
= insn_info
;
2540 clear_rhs_from_active_local_stores ();
2543 else if (SIBLING_CALL_P (insn
)
2544 && (reload_completed
|| HARD_FRAME_POINTER_IS_ARG_POINTER
))
2545 /* Arguments for a sibling call that are pushed to memory are passed
2546 using the incoming argument pointer of the current function. After
2547 reload that might be (and likely is) frame pointer based. And, if
2548 it is a frame pointer on the target, even before reload we need to
2549 kill frame pointer based stores. */
2550 add_wild_read (bb_info
);
2552 /* Every other call, including pure functions, may read any memory
2553 that is not relative to the frame. */
2554 add_non_frame_wild_read (bb_info
);
2559 /* Assuming that there are sets in these insns, we cannot delete
2561 if ((GET_CODE (PATTERN (insn
)) == CLOBBER
)
2562 || volatile_refs_p (PATTERN (insn
))
2563 || (!cfun
->can_delete_dead_exceptions
&& !insn_nothrow_p (insn
))
2564 || (RTX_FRAME_RELATED_P (insn
))
2565 || find_reg_note (insn
, REG_FRAME_RELATED_EXPR
, NULL_RTX
))
2566 insn_info
->cannot_delete
= true;
2568 body
= PATTERN (insn
);
2569 if (GET_CODE (body
) == PARALLEL
)
2572 for (i
= 0; i
< XVECLEN (body
, 0); i
++)
2573 mems_found
+= record_store (XVECEXP (body
, 0, i
), bb_info
);
2576 mems_found
+= record_store (body
, bb_info
);
2578 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2579 fprintf (dump_file
, "mems_found = %d, cannot_delete = %s\n",
2580 mems_found
, insn_info
->cannot_delete
? "true" : "false");
2582 /* If we found some sets of mems, add it into the active_local_stores so
2583 that it can be locally deleted if found dead or used for
2584 replace_read and redundant constant store elimination. Otherwise mark
2585 it as cannot delete. This simplifies the processing later. */
2586 if (mems_found
== 1)
2588 if (active_local_stores_len
++ >= max_active_local_stores
)
2590 active_local_stores_len
= 1;
2591 active_local_stores
= NULL
;
2593 insn_info
->fixed_regs_live
= copy_fixed_regs (bb_info
->regs_live
);
2594 insn_info
->next_local_store
= active_local_stores
;
2595 active_local_stores
= insn_info
;
2598 insn_info
->cannot_delete
= true;
2602 /* Remove BASE from the set of active_local_stores. This is a
2603 callback from cselib that is used to get rid of the stores in
2604 active_local_stores. */
2607 remove_useless_values (cselib_val
*base
)
2609 insn_info_t insn_info
= active_local_stores
;
2610 insn_info_t last
= NULL
;
2614 store_info
*store_info
= insn_info
->store_rec
;
2617 /* If ANY of the store_infos match the cselib group that is
2618 being deleted, then the insn cannot be deleted. */
2621 if ((store_info
->group_id
== -1)
2622 && (store_info
->cse_base
== base
))
2627 store_info
= store_info
->next
;
2632 active_local_stores_len
--;
2634 last
->next_local_store
= insn_info
->next_local_store
;
2636 active_local_stores
= insn_info
->next_local_store
;
2637 free_store_info (insn_info
);
2642 insn_info
= insn_info
->next_local_store
;
2647 /* Do all of step 1. */
2653 bitmap regs_live
= BITMAP_ALLOC (®_obstack
);
2656 all_blocks
= BITMAP_ALLOC (NULL
);
2657 bitmap_set_bit (all_blocks
, ENTRY_BLOCK
);
2658 bitmap_set_bit (all_blocks
, EXIT_BLOCK
);
2660 /* For -O1 reduce the maximum number of active local stores for RTL DSE
2661 since this can consume huge amounts of memory (PR89115). */
2662 int max_active_local_stores
= param_max_dse_active_local_stores
;
2664 max_active_local_stores
/= 10;
2666 FOR_ALL_BB_FN (bb
, cfun
)
2669 bb_info_t bb_info
= dse_bb_info_type_pool
.allocate ();
2671 memset (bb_info
, 0, sizeof (dse_bb_info_type
));
2672 bitmap_set_bit (all_blocks
, bb
->index
);
2673 bb_info
->regs_live
= regs_live
;
2675 bitmap_copy (regs_live
, DF_LR_IN (bb
));
2676 df_simulate_initialize_forwards (bb
, regs_live
);
2678 bb_table
[bb
->index
] = bb_info
;
2679 cselib_discard_hook
= remove_useless_values
;
2681 if (bb
->index
>= NUM_FIXED_BLOCKS
)
2685 active_local_stores
= NULL
;
2686 active_local_stores_len
= 0;
2687 cselib_clear_table ();
2689 /* Scan the insns. */
2690 FOR_BB_INSNS (bb
, insn
)
2693 scan_insn (bb_info
, insn
, max_active_local_stores
);
2694 cselib_process_insn (insn
);
2696 df_simulate_one_insn_forwards (bb
, insn
, regs_live
);
2699 /* This is something of a hack, because the global algorithm
2700 is supposed to take care of the case where stores go dead
2701 at the end of the function. However, the global
2702 algorithm must take a more conservative view of block
2703 mode reads than the local alg does. So to get the case
2704 where you have a store to the frame followed by a non
2705 overlapping block more read, we look at the active local
2706 stores at the end of the function and delete all of the
2707 frame and spill based ones. */
2708 if (stores_off_frame_dead_at_return
2709 && (EDGE_COUNT (bb
->succs
) == 0
2710 || (single_succ_p (bb
)
2711 && single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
2712 && ! crtl
->calls_eh_return
)))
2714 insn_info_t i_ptr
= active_local_stores
;
2717 store_info
*store_info
= i_ptr
->store_rec
;
2719 /* Skip the clobbers. */
2720 while (!store_info
->is_set
)
2721 store_info
= store_info
->next
;
2722 if (store_info
->group_id
>= 0)
2724 group_info
*group
= rtx_group_vec
[store_info
->group_id
];
2725 if (group
->frame_related
&& !i_ptr
->cannot_delete
)
2726 delete_dead_store_insn (i_ptr
);
2729 i_ptr
= i_ptr
->next_local_store
;
2733 /* Get rid of the loads that were discovered in
2734 replace_read. Cselib is finished with this block. */
2735 while (deferred_change_list
)
2737 deferred_change
*next
= deferred_change_list
->next
;
2739 /* There is no reason to validate this change. That was
2741 *deferred_change_list
->loc
= deferred_change_list
->reg
;
2742 deferred_change_pool
.remove (deferred_change_list
);
2743 deferred_change_list
= next
;
2746 /* Get rid of all of the cselib based store_infos in this
2747 block and mark the containing insns as not being
2749 ptr
= bb_info
->last_insn
;
2752 if (ptr
->contains_cselib_groups
)
2754 store_info
*s_info
= ptr
->store_rec
;
2755 while (s_info
&& !s_info
->is_set
)
2756 s_info
= s_info
->next
;
2758 && s_info
->redundant_reason
2759 && s_info
->redundant_reason
->insn
2760 && !ptr
->cannot_delete
)
2762 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2763 fprintf (dump_file
, "Locally deleting insn %d "
2764 "because insn %d stores the "
2765 "same value and couldn't be "
2767 INSN_UID (ptr
->insn
),
2768 INSN_UID (s_info
->redundant_reason
->insn
));
2769 delete_dead_store_insn (ptr
);
2771 free_store_info (ptr
);
2777 /* Free at least positions_needed bitmaps. */
2778 for (s_info
= ptr
->store_rec
; s_info
; s_info
= s_info
->next
)
2779 if (s_info
->is_large
)
2781 BITMAP_FREE (s_info
->positions_needed
.large
.bmap
);
2782 s_info
->is_large
= false;
2785 ptr
= ptr
->prev_insn
;
2788 cse_store_info_pool
.release ();
2790 bb_info
->regs_live
= NULL
;
2793 BITMAP_FREE (regs_live
);
2795 rtx_group_table
->empty ();
2799 /*----------------------------------------------------------------------------
2802 Assign each byte position in the stores that we are going to
2803 analyze globally to a position in the bitmaps. Returns true if
2804 there are any bit positions assigned.
2805 ----------------------------------------------------------------------------*/
2808 dse_step2_init (void)
2813 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
2815 /* For all non stack related bases, we only consider a store to
2816 be deletable if there are two or more stores for that
2817 position. This is because it takes one store to make the
2818 other store redundant. However, for the stores that are
2819 stack related, we consider them if there is only one store
2820 for the position. We do this because the stack related
2821 stores can be deleted if their is no read between them and
2822 the end of the function.
2824 To make this work in the current framework, we take the stack
2825 related bases add all of the bits from store1 into store2.
2826 This has the effect of making the eligible even if there is
2829 if (stores_off_frame_dead_at_return
&& group
->frame_related
)
2831 bitmap_ior_into (group
->store2_n
, group
->store1_n
);
2832 bitmap_ior_into (group
->store2_p
, group
->store1_p
);
2833 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2834 fprintf (dump_file
, "group %d is frame related ", i
);
2837 group
->offset_map_size_n
++;
2838 group
->offset_map_n
= XOBNEWVEC (&dse_obstack
, int,
2839 group
->offset_map_size_n
);
2840 group
->offset_map_size_p
++;
2841 group
->offset_map_p
= XOBNEWVEC (&dse_obstack
, int,
2842 group
->offset_map_size_p
);
2843 group
->process_globally
= false;
2844 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2846 fprintf (dump_file
, "group %d(%d+%d): ", i
,
2847 (int)bitmap_count_bits (group
->store2_n
),
2848 (int)bitmap_count_bits (group
->store2_p
));
2849 bitmap_print (dump_file
, group
->store2_n
, "n ", " ");
2850 bitmap_print (dump_file
, group
->store2_p
, "p ", "\n");
2856 /* Init the offset tables. */
2863 /* Position 0 is unused because 0 is used in the maps to mean
2865 current_position
= 1;
2866 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
2871 memset (group
->offset_map_n
, 0, sizeof (int) * group
->offset_map_size_n
);
2872 memset (group
->offset_map_p
, 0, sizeof (int) * group
->offset_map_size_p
);
2873 bitmap_clear (group
->group_kill
);
2875 EXECUTE_IF_SET_IN_BITMAP (group
->store2_n
, 0, j
, bi
)
2877 bitmap_set_bit (group
->group_kill
, current_position
);
2878 if (bitmap_bit_p (group
->escaped_n
, j
))
2879 bitmap_set_bit (kill_on_calls
, current_position
);
2880 group
->offset_map_n
[j
] = current_position
++;
2881 group
->process_globally
= true;
2883 EXECUTE_IF_SET_IN_BITMAP (group
->store2_p
, 0, j
, bi
)
2885 bitmap_set_bit (group
->group_kill
, current_position
);
2886 if (bitmap_bit_p (group
->escaped_p
, j
))
2887 bitmap_set_bit (kill_on_calls
, current_position
);
2888 group
->offset_map_p
[j
] = current_position
++;
2889 group
->process_globally
= true;
2892 return current_position
!= 1;
2897 /*----------------------------------------------------------------------------
2900 Build the bit vectors for the transfer functions.
2901 ----------------------------------------------------------------------------*/
2904 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
2908 get_bitmap_index (group_info
*group_info
, HOST_WIDE_INT offset
)
2912 HOST_WIDE_INT offset_p
= -offset
;
2913 if (offset_p
>= group_info
->offset_map_size_n
)
2915 return group_info
->offset_map_n
[offset_p
];
2919 if (offset
>= group_info
->offset_map_size_p
)
2921 return group_info
->offset_map_p
[offset
];
2926 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
2930 scan_stores (store_info
*store_info
, bitmap gen
, bitmap kill
)
2934 HOST_WIDE_INT i
, offset
, width
;
2935 group_info
*group_info
2936 = rtx_group_vec
[store_info
->group_id
];
2937 /* We can (conservatively) ignore stores whose bounds aren't known;
2938 they simply don't generate new global dse opportunities. */
2939 if (group_info
->process_globally
2940 && store_info
->offset
.is_constant (&offset
)
2941 && store_info
->width
.is_constant (&width
))
2943 HOST_WIDE_INT end
= offset
+ width
;
2944 for (i
= offset
; i
< end
; i
++)
2946 int index
= get_bitmap_index (group_info
, i
);
2949 bitmap_set_bit (gen
, index
);
2951 bitmap_clear_bit (kill
, index
);
2955 store_info
= store_info
->next
;
2960 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
2964 scan_reads (insn_info_t insn_info
, bitmap gen
, bitmap kill
)
2966 read_info_t read_info
= insn_info
->read_rec
;
2970 /* If this insn reads the frame, kill all the frame related stores. */
2971 if (insn_info
->frame_read
)
2973 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
2974 if (group
->process_globally
&& group
->frame_related
)
2977 bitmap_ior_into (kill
, group
->group_kill
);
2978 bitmap_and_compl_into (gen
, group
->group_kill
);
2981 if (insn_info
->non_frame_wild_read
)
2983 /* Kill all non-frame related stores. Kill all stores of variables that
2986 bitmap_ior_into (kill
, kill_on_calls
);
2987 bitmap_and_compl_into (gen
, kill_on_calls
);
2988 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
2989 if (group
->process_globally
&& !group
->frame_related
)
2992 bitmap_ior_into (kill
, group
->group_kill
);
2993 bitmap_and_compl_into (gen
, group
->group_kill
);
2998 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3000 if (group
->process_globally
)
3002 if (i
== read_info
->group_id
)
3004 HOST_WIDE_INT offset
, width
;
3005 /* Reads with non-constant size kill all DSE opportunities
3007 if (!read_info
->offset
.is_constant (&offset
)
3008 || !read_info
->width
.is_constant (&width
)
3009 || !known_size_p (width
))
3011 /* Handle block mode reads. */
3013 bitmap_ior_into (kill
, group
->group_kill
);
3014 bitmap_and_compl_into (gen
, group
->group_kill
);
3018 /* The groups are the same, just process the
3021 HOST_WIDE_INT end
= offset
+ width
;
3022 for (j
= offset
; j
< end
; j
++)
3024 int index
= get_bitmap_index (group
, j
);
3028 bitmap_set_bit (kill
, index
);
3029 bitmap_clear_bit (gen
, index
);
3036 /* The groups are different, if the alias sets
3037 conflict, clear the entire group. We only need
3038 to apply this test if the read_info is a cselib
3039 read. Anything with a constant base cannot alias
3040 something else with a different constant
3042 if ((read_info
->group_id
< 0)
3043 && canon_true_dependence (group
->base_mem
,
3044 GET_MODE (group
->base_mem
),
3045 group
->canon_base_addr
,
3046 read_info
->mem
, NULL_RTX
))
3049 bitmap_ior_into (kill
, group
->group_kill
);
3050 bitmap_and_compl_into (gen
, group
->group_kill
);
3056 read_info
= read_info
->next
;
3061 /* Return the insn in BB_INFO before the first wild read or if there
3062 are no wild reads in the block, return the last insn. */
3065 find_insn_before_first_wild_read (bb_info_t bb_info
)
3067 insn_info_t insn_info
= bb_info
->last_insn
;
3068 insn_info_t last_wild_read
= NULL
;
3072 if (insn_info
->wild_read
)
3074 last_wild_read
= insn_info
->prev_insn
;
3075 /* Block starts with wild read. */
3076 if (!last_wild_read
)
3080 insn_info
= insn_info
->prev_insn
;
3084 return last_wild_read
;
3086 return bb_info
->last_insn
;
3090 /* Scan the insns in BB_INFO starting at PTR and going to the top of
3091 the block in order to build the gen and kill sets for the block.
3092 We start at ptr which may be the last insn in the block or may be
3093 the first insn with a wild read. In the latter case we are able to
3094 skip the rest of the block because it just does not matter:
3095 anything that happens is hidden by the wild read. */
3098 dse_step3_scan (basic_block bb
)
3100 bb_info_t bb_info
= bb_table
[bb
->index
];
3101 insn_info_t insn_info
;
3103 insn_info
= find_insn_before_first_wild_read (bb_info
);
3105 /* In the spill case or in the no_spill case if there is no wild
3106 read in the block, we will need a kill set. */
3107 if (insn_info
== bb_info
->last_insn
)
3110 bitmap_clear (bb_info
->kill
);
3112 bb_info
->kill
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3116 BITMAP_FREE (bb_info
->kill
);
3120 /* There may have been code deleted by the dce pass run before
3122 if (insn_info
->insn
&& INSN_P (insn_info
->insn
))
3124 scan_stores (insn_info
->store_rec
, bb_info
->gen
, bb_info
->kill
);
3125 scan_reads (insn_info
, bb_info
->gen
, bb_info
->kill
);
3128 insn_info
= insn_info
->prev_insn
;
3133 /* Set the gen set of the exit block, and also any block with no
3134 successors that does not have a wild read. */
3137 dse_step3_exit_block_scan (bb_info_t bb_info
)
3139 /* The gen set is all 0's for the exit block except for the
3140 frame_pointer_group. */
3142 if (stores_off_frame_dead_at_return
)
3147 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3149 if (group
->process_globally
&& group
->frame_related
)
3150 bitmap_ior_into (bb_info
->gen
, group
->group_kill
);
3156 /* Find all of the blocks that are not backwards reachable from the
3157 exit block or any block with no successors (BB). These are the
3158 infinite loops or infinite self loops. These blocks will still
3159 have their bits set in UNREACHABLE_BLOCKS. */
3162 mark_reachable_blocks (sbitmap unreachable_blocks
, basic_block bb
)
3167 if (bitmap_bit_p (unreachable_blocks
, bb
->index
))
3169 bitmap_clear_bit (unreachable_blocks
, bb
->index
);
3170 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3172 mark_reachable_blocks (unreachable_blocks
, e
->src
);
3177 /* Build the transfer functions for the function. */
3183 sbitmap_iterator sbi
;
3184 bitmap all_ones
= NULL
;
3187 auto_sbitmap
unreachable_blocks (last_basic_block_for_fn (cfun
));
3188 bitmap_ones (unreachable_blocks
);
3190 FOR_ALL_BB_FN (bb
, cfun
)
3192 bb_info_t bb_info
= bb_table
[bb
->index
];
3194 bitmap_clear (bb_info
->gen
);
3196 bb_info
->gen
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3198 if (bb
->index
== ENTRY_BLOCK
)
3200 else if (bb
->index
== EXIT_BLOCK
)
3201 dse_step3_exit_block_scan (bb_info
);
3203 dse_step3_scan (bb
);
3204 if (EDGE_COUNT (bb
->succs
) == 0)
3205 mark_reachable_blocks (unreachable_blocks
, bb
);
3207 /* If this is the second time dataflow is run, delete the old
3210 BITMAP_FREE (bb_info
->in
);
3212 BITMAP_FREE (bb_info
->out
);
3215 /* For any block in an infinite loop, we must initialize the out set
3216 to all ones. This could be expensive, but almost never occurs in
3217 practice. However, it is common in regression tests. */
3218 EXECUTE_IF_SET_IN_BITMAP (unreachable_blocks
, 0, i
, sbi
)
3220 if (bitmap_bit_p (all_blocks
, i
))
3222 bb_info_t bb_info
= bb_table
[i
];
3228 all_ones
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3229 FOR_EACH_VEC_ELT (rtx_group_vec
, j
, group
)
3230 bitmap_ior_into (all_ones
, group
->group_kill
);
3234 bb_info
->out
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3235 bitmap_copy (bb_info
->out
, all_ones
);
3241 BITMAP_FREE (all_ones
);
3246 /*----------------------------------------------------------------------------
3249 Solve the bitvector equations.
3250 ----------------------------------------------------------------------------*/
3253 /* Confluence function for blocks with no successors. Create an out
3254 set from the gen set of the exit block. This block logically has
3255 the exit block as a successor. */
3260 dse_confluence_0 (basic_block bb
)
3262 bb_info_t bb_info
= bb_table
[bb
->index
];
3264 if (bb
->index
== EXIT_BLOCK
)
3269 bb_info
->out
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3270 bitmap_copy (bb_info
->out
, bb_table
[EXIT_BLOCK
]->gen
);
3274 /* Propagate the information from the in set of the dest of E to the
3275 out set of the src of E. If the various in or out sets are not
3276 there, that means they are all ones. */
3279 dse_confluence_n (edge e
)
3281 bb_info_t src_info
= bb_table
[e
->src
->index
];
3282 bb_info_t dest_info
= bb_table
[e
->dest
->index
];
3287 bitmap_and_into (src_info
->out
, dest_info
->in
);
3290 src_info
->out
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3291 bitmap_copy (src_info
->out
, dest_info
->in
);
3298 /* Propagate the info from the out to the in set of BB_INDEX's basic
3299 block. There are three cases:
3301 1) The block has no kill set. In this case the kill set is all
3302 ones. It does not matter what the out set of the block is, none of
3303 the info can reach the top. The only thing that reaches the top is
3304 the gen set and we just copy the set.
3306 2) There is a kill set but no out set and bb has successors. In
3307 this case we just return. Eventually an out set will be created and
3308 it is better to wait than to create a set of ones.
3310 3) There is both a kill and out set. We apply the obvious transfer
3315 dse_transfer_function (int bb_index
)
3317 bb_info_t bb_info
= bb_table
[bb_index
];
3325 return bitmap_ior_and_compl (bb_info
->in
, bb_info
->gen
,
3326 bb_info
->out
, bb_info
->kill
);
3329 bb_info
->in
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3330 bitmap_ior_and_compl (bb_info
->in
, bb_info
->gen
,
3331 bb_info
->out
, bb_info
->kill
);
3341 /* Case 1 above. If there is already an in set, nothing
3347 bb_info
->in
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3348 bitmap_copy (bb_info
->in
, bb_info
->gen
);
3354 /* Solve the dataflow equations. */
3359 df_simple_dataflow (DF_BACKWARD
, NULL
, dse_confluence_0
,
3360 dse_confluence_n
, dse_transfer_function
,
3361 all_blocks
, df_get_postorder (DF_BACKWARD
),
3362 df_get_n_blocks (DF_BACKWARD
));
3363 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3367 fprintf (dump_file
, "\n\n*** Global dataflow info after analysis.\n");
3368 FOR_ALL_BB_FN (bb
, cfun
)
3370 bb_info_t bb_info
= bb_table
[bb
->index
];
3372 df_print_bb_index (bb
, dump_file
);
3374 bitmap_print (dump_file
, bb_info
->in
, " in: ", "\n");
3376 fprintf (dump_file
, " in: *MISSING*\n");
3378 bitmap_print (dump_file
, bb_info
->gen
, " gen: ", "\n");
3380 fprintf (dump_file
, " gen: *MISSING*\n");
3382 bitmap_print (dump_file
, bb_info
->kill
, " kill: ", "\n");
3384 fprintf (dump_file
, " kill: *MISSING*\n");
3386 bitmap_print (dump_file
, bb_info
->out
, " out: ", "\n");
3388 fprintf (dump_file
, " out: *MISSING*\n\n");
3395 /*----------------------------------------------------------------------------
3398 Delete the stores that can only be deleted using the global information.
3399 ----------------------------------------------------------------------------*/
3406 FOR_EACH_BB_FN (bb
, cfun
)
3408 bb_info_t bb_info
= bb_table
[bb
->index
];
3409 insn_info_t insn_info
= bb_info
->last_insn
;
3410 bitmap v
= bb_info
->out
;
3414 bool deleted
= false;
3415 if (dump_file
&& insn_info
->insn
)
3417 fprintf (dump_file
, "starting to process insn %d\n",
3418 INSN_UID (insn_info
->insn
));
3419 bitmap_print (dump_file
, v
, " v: ", "\n");
3422 /* There may have been code deleted by the dce pass run before
3425 && INSN_P (insn_info
->insn
)
3426 && (!insn_info
->cannot_delete
)
3427 && (!bitmap_empty_p (v
)))
3429 store_info
*store_info
= insn_info
->store_rec
;
3431 /* Try to delete the current insn. */
3434 /* Skip the clobbers. */
3435 while (!store_info
->is_set
)
3436 store_info
= store_info
->next
;
3438 HOST_WIDE_INT i
, offset
, width
;
3439 group_info
*group_info
= rtx_group_vec
[store_info
->group_id
];
3441 if (!store_info
->offset
.is_constant (&offset
)
3442 || !store_info
->width
.is_constant (&width
))
3446 HOST_WIDE_INT end
= offset
+ width
;
3447 for (i
= offset
; i
< end
; i
++)
3449 int index
= get_bitmap_index (group_info
, i
);
3451 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3452 fprintf (dump_file
, "i = %d, index = %d\n",
3454 if (index
== 0 || !bitmap_bit_p (v
, index
))
3456 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3457 fprintf (dump_file
, "failing at i = %d\n",
3467 && check_for_inc_dec_1 (insn_info
))
3469 delete_insn (insn_info
->insn
);
3470 insn_info
->insn
= NULL
;
3475 /* We do want to process the local info if the insn was
3476 deleted. For instance, if the insn did a wild read, we
3477 no longer need to trash the info. */
3479 && INSN_P (insn_info
->insn
)
3482 scan_stores (insn_info
->store_rec
, v
, NULL
);
3483 if (insn_info
->wild_read
)
3485 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3486 fprintf (dump_file
, "wild read\n");
3489 else if (insn_info
->read_rec
3490 || insn_info
->non_frame_wild_read
3491 || insn_info
->frame_read
)
3493 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3495 if (!insn_info
->non_frame_wild_read
3496 && !insn_info
->frame_read
)
3497 fprintf (dump_file
, "regular read\n");
3498 if (insn_info
->non_frame_wild_read
)
3499 fprintf (dump_file
, "non-frame wild read\n");
3500 if (insn_info
->frame_read
)
3501 fprintf (dump_file
, "frame read\n");
3503 scan_reads (insn_info
, v
, NULL
);
3507 insn_info
= insn_info
->prev_insn
;
3514 /*----------------------------------------------------------------------------
3517 Delete stores made redundant by earlier stores (which store the same
3518 value) that couldn't be eliminated.
3519 ----------------------------------------------------------------------------*/
3526 FOR_ALL_BB_FN (bb
, cfun
)
3528 bb_info_t bb_info
= bb_table
[bb
->index
];
3529 insn_info_t insn_info
= bb_info
->last_insn
;
3533 /* There may have been code deleted by the dce pass run before
3536 && INSN_P (insn_info
->insn
)
3537 && !insn_info
->cannot_delete
)
3539 store_info
*s_info
= insn_info
->store_rec
;
3541 while (s_info
&& !s_info
->is_set
)
3542 s_info
= s_info
->next
;
3544 && s_info
->redundant_reason
3545 && s_info
->redundant_reason
->insn
3546 && INSN_P (s_info
->redundant_reason
->insn
))
3548 rtx_insn
*rinsn
= s_info
->redundant_reason
->insn
;
3549 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3550 fprintf (dump_file
, "Locally deleting insn %d "
3551 "because insn %d stores the "
3552 "same value and couldn't be "
3554 INSN_UID (insn_info
->insn
),
3556 delete_dead_store_insn (insn_info
);
3559 insn_info
= insn_info
->prev_insn
;
3564 /*----------------------------------------------------------------------------
3567 Destroy everything left standing.
3568 ----------------------------------------------------------------------------*/
3573 bitmap_obstack_release (&dse_bitmap_obstack
);
3574 obstack_free (&dse_obstack
, NULL
);
3576 end_alias_analysis ();
3578 delete rtx_group_table
;
3579 rtx_group_table
= NULL
;
3580 rtx_group_vec
.release ();
3581 BITMAP_FREE (all_blocks
);
3582 BITMAP_FREE (scratch
);
3584 rtx_store_info_pool
.release ();
3585 read_info_type_pool
.release ();
3586 insn_info_type_pool
.release ();
3587 dse_bb_info_type_pool
.release ();
3588 group_info_pool
.release ();
3589 deferred_change_pool
.release ();
3593 /* -------------------------------------------------------------------------
3595 ------------------------------------------------------------------------- */
3597 /* Callback for running pass_rtl_dse. */
3600 rest_of_handle_dse (void)
3602 df_set_flags (DF_DEFER_INSN_RESCAN
);
3604 /* Need the notes since we must track live hardregs in the forwards
3606 df_note_add_problem ();
3614 df_set_flags (DF_LR_RUN_DCE
);
3616 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3617 fprintf (dump_file
, "doing global processing\n");
3627 fprintf (dump_file
, "dse: local deletions = %d, global deletions = %d\n",
3628 locally_deleted
, globally_deleted
);
3630 /* DSE can eliminate potentially-trapping MEMs.
3631 Remove any EH edges associated with them. */
3632 if ((locally_deleted
|| globally_deleted
)
3633 && cfun
->can_throw_non_call_exceptions
3634 && purge_all_dead_edges ())
3636 free_dominance_info (CDI_DOMINATORS
);
3645 const pass_data pass_data_rtl_dse1
=
3647 RTL_PASS
, /* type */
3649 OPTGROUP_NONE
, /* optinfo_flags */
3650 TV_DSE1
, /* tv_id */
3651 0, /* properties_required */
3652 0, /* properties_provided */
3653 0, /* properties_destroyed */
3654 0, /* todo_flags_start */
3655 TODO_df_finish
, /* todo_flags_finish */
3658 class pass_rtl_dse1
: public rtl_opt_pass
3661 pass_rtl_dse1 (gcc::context
*ctxt
)
3662 : rtl_opt_pass (pass_data_rtl_dse1
, ctxt
)
3665 /* opt_pass methods: */
3666 virtual bool gate (function
*)
3668 return optimize
> 0 && flag_dse
&& dbg_cnt (dse1
);
3671 virtual unsigned int execute (function
*) { return rest_of_handle_dse (); }
3673 }; // class pass_rtl_dse1
3678 make_pass_rtl_dse1 (gcc::context
*ctxt
)
3680 return new pass_rtl_dse1 (ctxt
);
3685 const pass_data pass_data_rtl_dse2
=
3687 RTL_PASS
, /* type */
3689 OPTGROUP_NONE
, /* optinfo_flags */
3690 TV_DSE2
, /* tv_id */
3691 0, /* properties_required */
3692 0, /* properties_provided */
3693 0, /* properties_destroyed */
3694 0, /* todo_flags_start */
3695 TODO_df_finish
, /* todo_flags_finish */
3698 class pass_rtl_dse2
: public rtl_opt_pass
3701 pass_rtl_dse2 (gcc::context
*ctxt
)
3702 : rtl_opt_pass (pass_data_rtl_dse2
, ctxt
)
3705 /* opt_pass methods: */
3706 virtual bool gate (function
*)
3708 return optimize
> 0 && flag_dse
&& dbg_cnt (dse2
);
3711 virtual unsigned int execute (function
*) { return rest_of_handle_dse (); }
3713 }; // class pass_rtl_dse2
3718 make_pass_rtl_dse2 (gcc::context
*ctxt
)
3720 return new pass_rtl_dse2 (ctxt
);