1 /* RTL dead store elimination.
2 Copyright (C) 2005-2015 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"
28 #include "hash-table.h"
38 #include "fold-const.h"
39 #include "stor-layout.h"
42 #include "hard-reg-set.h"
45 #include "dominance.h"
49 #include "basic-block.h"
52 #include "tree-pass.h"
53 #include "alloc-pool.h"
54 #include "insn-config.h"
57 #include "statistics.h"
67 #include "insn-codes.h"
72 #include "tree-ssa-alias.h"
73 #include "internal-fn.h"
74 #include "gimple-expr.h"
77 #include "gimple-ssa.h"
79 #include "cfgcleanup.h"
81 /* This file contains three techniques for performing Dead Store
84 * The first technique performs dse locally on any base address. It
85 is based on the cselib which is a local value numbering technique.
86 This technique is local to a basic block but deals with a fairly
89 * The second technique performs dse globally but is restricted to
90 base addresses that are either constant or are relative to the
93 * The third technique, (which is only done after register allocation)
94 processes the spill spill slots. This differs from the second
95 technique because it takes advantage of the fact that spilling is
96 completely free from the effects of aliasing.
98 Logically, dse is a backwards dataflow problem. A store can be
99 deleted if it if cannot be reached in the backward direction by any
100 use of the value being stored. However, the local technique uses a
101 forwards scan of the basic block because cselib requires that the
102 block be processed in that order.
104 The pass is logically broken into 7 steps:
108 1) The local algorithm, as well as scanning the insns for the two
111 2) Analysis to see if the global algs are necessary. In the case
112 of stores base on a constant address, there must be at least two
113 stores to that address, to make it possible to delete some of the
114 stores. In the case of stores off of the frame or spill related
115 stores, only one store to an address is necessary because those
116 stores die at the end of the function.
118 3) Set up the global dataflow equations based on processing the
119 info parsed in the first step.
121 4) Solve the dataflow equations.
123 5) Delete the insns that the global analysis has indicated are
126 6) Delete insns that store the same value as preceding store
127 where the earlier store couldn't be eliminated.
131 This step uses cselib and canon_rtx to build the largest expression
132 possible for each address. This pass is a forwards pass through
133 each basic block. From the point of view of the global technique,
134 the first pass could examine a block in either direction. The
135 forwards ordering is to accommodate cselib.
137 We make a simplifying assumption: addresses fall into four broad
140 1) base has rtx_varies_p == false, offset is constant.
141 2) base has rtx_varies_p == false, offset variable.
142 3) base has rtx_varies_p == true, offset constant.
143 4) base has rtx_varies_p == true, offset variable.
145 The local passes are able to process all 4 kinds of addresses. The
146 global pass only handles 1).
148 The global problem is formulated as follows:
150 A store, S1, to address A, where A is not relative to the stack
151 frame, can be eliminated if all paths from S1 to the end of the
152 function contain another store to A before a read to A.
154 If the address A is relative to the stack frame, a store S2 to A
155 can be eliminated if there are no paths from S2 that reach the
156 end of the function that read A before another store to A. In
157 this case S2 can be deleted if there are paths from S2 to the
158 end of the function that have no reads or writes to A. This
159 second case allows stores to the stack frame to be deleted that
160 would otherwise die when the function returns. This cannot be
161 done if stores_off_frame_dead_at_return is not true. See the doc
162 for that variable for when this variable is false.
164 The global problem is formulated as a backwards set union
165 dataflow problem where the stores are the gens and reads are the
166 kills. Set union problems are rare and require some special
167 handling given our representation of bitmaps. A straightforward
168 implementation requires a lot of bitmaps filled with 1s.
169 These are expensive and cumbersome in our bitmap formulation so
170 care has been taken to avoid large vectors filled with 1s. See
171 the comments in bb_info and in the dataflow confluence functions
174 There are two places for further enhancements to this algorithm:
176 1) The original dse which was embedded in a pass called flow also
177 did local address forwarding. For example in
182 flow would replace the right hand side of the second insn with a
183 reference to r100. Most of the information is available to add this
184 to this pass. It has not done it because it is a lot of work in
185 the case that either r100 is assigned to between the first and
186 second insn and/or the second insn is a load of part of the value
187 stored by the first insn.
189 insn 5 in gcc.c-torture/compile/990203-1.c simple case.
190 insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
191 insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
192 insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
194 2) The cleaning up of spill code is quite profitable. It currently
195 depends on reading tea leaves and chicken entrails left by reload.
196 This pass depends on reload creating a singleton alias set for each
197 spill slot and telling the next dse pass which of these alias sets
198 are the singletons. Rather than analyze the addresses of the
199 spills, dse's spill processing just does analysis of the loads and
200 stores that use those alias sets. There are three cases where this
203 a) Reload sometimes creates the slot for one mode of access, and
204 then inserts loads and/or stores for a smaller mode. In this
205 case, the current code just punts on the slot. The proper thing
206 to do is to back out and use one bit vector position for each
207 byte of the entity associated with the slot. This depends on
208 KNOWING that reload always generates the accesses for each of the
209 bytes in some canonical (read that easy to understand several
210 passes after reload happens) way.
212 b) Reload sometimes decides that spill slot it allocated was not
213 large enough for the mode and goes back and allocates more slots
214 with the same mode and alias set. The backout in this case is a
215 little more graceful than (a). In this case the slot is unmarked
216 as being a spill slot and if final address comes out to be based
217 off the frame pointer, the global algorithm handles this slot.
219 c) For any pass that may prespill, there is currently no
220 mechanism to tell the dse pass that the slot being used has the
221 special properties that reload uses. It may be that all that is
222 required is to have those passes make the same calls that reload
223 does, assuming that the alias sets can be manipulated in the same
226 /* There are limits to the size of constant offsets we model for the
227 global problem. There are certainly test cases, that exceed this
228 limit, however, it is unlikely that there are important programs
229 that really have constant offsets this size. */
230 #define MAX_OFFSET (64 * 1024)
232 /* Obstack for the DSE dataflow bitmaps. We don't want to put these
233 on the default obstack because these bitmaps can grow quite large
234 (~2GB for the small (!) test case of PR54146) and we'll hold on to
235 all that memory until the end of the compiler run.
236 As a bonus, delete_tree_live_info can destroy all the bitmaps by just
237 releasing the whole obstack. */
238 static bitmap_obstack dse_bitmap_obstack
;
240 /* Obstack for other data. As for above: Kinda nice to be able to
241 throw it all away at the end in one big sweep. */
242 static struct obstack dse_obstack
;
244 /* Scratch bitmap for cselib's cselib_expand_value_rtx. */
245 static bitmap scratch
= NULL
;
247 struct insn_info_type
;
249 /* This structure holds information about a candidate store. */
253 /* False means this is a clobber. */
256 /* False if a single HOST_WIDE_INT bitmap is used for positions_needed. */
259 /* The id of the mem group of the base address. If rtx_varies_p is
260 true, this is -1. Otherwise, it is the index into the group
264 /* This is the cselib value. */
265 cselib_val
*cse_base
;
267 /* This canonized mem. */
270 /* Canonized MEM address for use by canon_true_dependence. */
273 /* If this is non-zero, it is the alias set of a spill location. */
274 alias_set_type alias_set
;
276 /* The offset of the first and byte before the last byte associated
277 with the operation. */
278 HOST_WIDE_INT begin
, end
;
282 /* A bitmask as wide as the number of bytes in the word that
283 contains a 1 if the byte may be needed. The store is unused if
284 all of the bits are 0. This is used if IS_LARGE is false. */
285 unsigned HOST_WIDE_INT small_bitmask
;
289 /* A bitmap with one bit per byte. Cleared bit means the position
290 is needed. Used if IS_LARGE is false. */
293 /* Number of set bits (i.e. unneeded bytes) in BITMAP. If it is
294 equal to END - BEGIN, the whole store is unused. */
299 /* The next store info for this insn. */
300 struct store_info
*next
;
302 /* The right hand side of the store. This is used if there is a
303 subsequent reload of the mems address somewhere later in the
307 /* If rhs is or holds a constant, this contains that constant,
311 /* Set if this store stores the same constant value as REDUNDANT_REASON
312 insn stored. These aren't eliminated early, because doing that
313 might prevent the earlier larger store to be eliminated. */
314 struct insn_info_type
*redundant_reason
;
317 /* Return a bitmask with the first N low bits set. */
319 static unsigned HOST_WIDE_INT
320 lowpart_bitmask (int n
)
322 unsigned HOST_WIDE_INT mask
= ~(unsigned HOST_WIDE_INT
) 0;
323 return mask
>> (HOST_BITS_PER_WIDE_INT
- n
);
326 typedef struct store_info
*store_info_t
;
327 static pool_allocator
<store_info
> cse_store_info_pool ("cse_store_info_pool",
330 static pool_allocator
<store_info
> rtx_store_info_pool ("rtx_store_info_pool",
333 /* This structure holds information about a load. These are only
334 built for rtx bases. */
335 struct read_info_type
337 /* The id of the mem group of the base address. */
340 /* If this is non-zero, it is the alias set of a spill location. */
341 alias_set_type alias_set
;
343 /* The offset of the first and byte after the last byte associated
344 with the operation. If begin == end == 0, the read did not have
345 a constant offset. */
348 /* The mem being read. */
351 /* The next read_info for this insn. */
352 struct read_info_type
*next
;
354 /* Pool allocation new operator. */
355 inline void *operator new (size_t)
357 return pool
.allocate ();
360 /* Delete operator utilizing pool allocation. */
361 inline void operator delete (void *ptr
)
363 pool
.remove ((read_info_type
*) ptr
);
366 /* Memory allocation pool. */
367 static pool_allocator
<read_info_type
> pool
;
369 typedef struct read_info_type
*read_info_t
;
371 pool_allocator
<read_info_type
> read_info_type::pool ("read_info_pool", 100);
373 /* One of these records is created for each insn. */
375 struct insn_info_type
377 /* Set true if the insn contains a store but the insn itself cannot
378 be deleted. This is set if the insn is a parallel and there is
379 more than one non dead output or if the insn is in some way
383 /* This field is only used by the global algorithm. It is set true
384 if the insn contains any read of mem except for a (1). This is
385 also set if the insn is a call or has a clobber mem. If the insn
386 contains a wild read, the use_rec will be null. */
389 /* This is true only for CALL instructions which could potentially read
390 any non-frame memory location. This field is used by the global
392 bool non_frame_wild_read
;
394 /* This field is only used for the processing of const functions.
395 These functions cannot read memory, but they can read the stack
396 because that is where they may get their parms. We need to be
397 this conservative because, like the store motion pass, we don't
398 consider CALL_INSN_FUNCTION_USAGE when processing call insns.
399 Moreover, we need to distinguish two cases:
400 1. Before reload (register elimination), the stores related to
401 outgoing arguments are stack pointer based and thus deemed
402 of non-constant base in this pass. This requires special
403 handling but also means that the frame pointer based stores
404 need not be killed upon encountering a const function call.
405 2. After reload, the stores related to outgoing arguments can be
406 either stack pointer or hard frame pointer based. This means
407 that we have no other choice than also killing all the frame
408 pointer based stores upon encountering a const function call.
409 This field is set after reload for const function calls and before
410 reload for const tail function calls on targets where arg pointer
411 is the frame pointer. Having this set is less severe than a wild
412 read, it just means that all the frame related stores are killed
413 rather than all the stores. */
416 /* This field is only used for the processing of const functions.
417 It is set if the insn may contain a stack pointer based store. */
418 bool stack_pointer_based
;
420 /* This is true if any of the sets within the store contains a
421 cselib base. Such stores can only be deleted by the local
423 bool contains_cselib_groups
;
428 /* The list of mem sets or mem clobbers that are contained in this
429 insn. If the insn is deletable, it contains only one mem set.
430 But it could also contain clobbers. Insns that contain more than
431 one mem set are not deletable, but each of those mems are here in
432 order to provide info to delete other insns. */
433 store_info_t store_rec
;
435 /* The linked list of mem uses in this insn. Only the reads from
436 rtx bases are listed here. The reads to cselib bases are
437 completely processed during the first scan and so are never
439 read_info_t read_rec
;
441 /* The live fixed registers. We assume only fixed registers can
442 cause trouble by being clobbered from an expanded pattern;
443 storing only the live fixed registers (rather than all registers)
444 means less memory needs to be allocated / copied for the individual
446 regset fixed_regs_live
;
448 /* The prev insn in the basic block. */
449 struct insn_info_type
* prev_insn
;
451 /* The linked list of insns that are in consideration for removal in
452 the forwards pass through the basic block. This pointer may be
453 trash as it is not cleared when a wild read occurs. The only
454 time it is guaranteed to be correct is when the traversal starts
455 at active_local_stores. */
456 struct insn_info_type
* next_local_store
;
458 /* Pool allocation new operator. */
459 inline void *operator new (size_t)
461 return pool
.allocate ();
464 /* Delete operator utilizing pool allocation. */
465 inline void operator delete (void *ptr
)
467 pool
.remove ((insn_info_type
*) ptr
);
470 /* Memory allocation pool. */
471 static pool_allocator
<insn_info_type
> pool
;
473 typedef struct insn_info_type
*insn_info_t
;
475 pool_allocator
<insn_info_type
> insn_info_type::pool ("insn_info_pool", 100);
477 /* The linked list of stores that are under consideration in this
479 static insn_info_t active_local_stores
;
480 static int active_local_stores_len
;
482 struct dse_bb_info_type
484 /* Pointer to the insn info for the last insn in the block. These
485 are linked so this is how all of the insns are reached. During
486 scanning this is the current insn being scanned. */
487 insn_info_t last_insn
;
489 /* The info for the global dataflow problem. */
492 /* This is set if the transfer function should and in the wild_read
493 bitmap before applying the kill and gen sets. That vector knocks
494 out most of the bits in the bitmap and thus speeds up the
496 bool apply_wild_read
;
498 /* The following 4 bitvectors hold information about which positions
499 of which stores are live or dead. They are indexed by
502 /* The set of store positions that exist in this block before a wild read. */
505 /* The set of load positions that exist in this block above the
506 same position of a store. */
509 /* The set of stores that reach the top of the block without being
512 Do not represent the in if it is all ones. Note that this is
513 what the bitvector should logically be initialized to for a set
514 intersection problem. However, like the kill set, this is too
515 expensive. So initially, the in set will only be created for the
516 exit block and any block that contains a wild read. */
519 /* The set of stores that reach the bottom of the block from it's
522 Do not represent the in if it is all ones. Note that this is
523 what the bitvector should logically be initialized to for a set
524 intersection problem. However, like the kill and in set, this is
525 too expensive. So what is done is that the confluence operator
526 just initializes the vector from one of the out sets of the
527 successors of the block. */
530 /* The following bitvector is indexed by the reg number. It
531 contains the set of regs that are live at the current instruction
532 being processed. While it contains info for all of the
533 registers, only the hard registers are actually examined. It is used
534 to assure that shift and/or add sequences that are inserted do not
535 accidentally clobber live hard regs. */
538 /* Pool allocation new operator. */
539 inline void *operator new (size_t)
541 return pool
.allocate ();
544 /* Delete operator utilizing pool allocation. */
545 inline void operator delete (void *ptr
)
547 pool
.remove ((dse_bb_info_type
*) ptr
);
550 /* Memory allocation pool. */
551 static pool_allocator
<dse_bb_info_type
> pool
;
554 typedef struct dse_bb_info_type
*bb_info_t
;
555 pool_allocator
<dse_bb_info_type
> dse_bb_info_type::pool ("bb_info_pool", 100);
557 /* Table to hold all bb_infos. */
558 static bb_info_t
*bb_table
;
560 /* There is a group_info for each rtx base that is used to reference
561 memory. There are also not many of the rtx bases because they are
562 very limited in scope. */
566 /* The actual base of the address. */
569 /* The sequential id of the base. This allows us to have a
570 canonical ordering of these that is not based on addresses. */
573 /* True if there are any positions that are to be processed
575 bool process_globally
;
577 /* True if the base of this group is either the frame_pointer or
578 hard_frame_pointer. */
581 /* A mem wrapped around the base pointer for the group in order to do
582 read dependency. It must be given BLKmode in order to encompass all
583 the possible offsets from the base. */
586 /* Canonized version of base_mem's address. */
589 /* These two sets of two bitmaps are used to keep track of how many
590 stores are actually referencing that position from this base. We
591 only do this for rtx bases as this will be used to assign
592 positions in the bitmaps for the global problem. Bit N is set in
593 store1 on the first store for offset N. Bit N is set in store2
594 for the second store to offset N. This is all we need since we
595 only care about offsets that have two or more stores for them.
597 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
598 for 0 and greater offsets.
600 There is one special case here, for stores into the stack frame,
601 we will or store1 into store2 before deciding which stores look
602 at globally. This is because stores to the stack frame that have
603 no other reads before the end of the function can also be
605 bitmap store1_n
, store1_p
, store2_n
, store2_p
;
607 /* These bitmaps keep track of offsets in this group escape this function.
608 An offset escapes if it corresponds to a named variable whose
609 addressable flag is set. */
610 bitmap escaped_n
, escaped_p
;
612 /* The positions in this bitmap have the same assignments as the in,
613 out, gen and kill bitmaps. This bitmap is all zeros except for
614 the positions that are occupied by stores for this group. */
617 /* The offset_map is used to map the offsets from this base into
618 positions in the global bitmaps. It is only created after all of
619 the all of stores have been scanned and we know which ones we
621 int *offset_map_n
, *offset_map_p
;
622 int offset_map_size_n
, offset_map_size_p
;
624 /* Pool allocation new operator. */
625 inline void *operator new (size_t)
627 return pool
.allocate ();
630 /* Delete operator utilizing pool allocation. */
631 inline void operator delete (void *ptr
)
633 pool
.remove ((group_info
*) ptr
);
636 /* Memory allocation pool. */
637 static pool_allocator
<group_info
> pool
;
639 typedef struct group_info
*group_info_t
;
640 typedef const struct group_info
*const_group_info_t
;
642 pool_allocator
<group_info
> group_info::pool ("rtx_group_info_pool", 100);
644 /* Index into the rtx_group_vec. */
645 static int rtx_group_next_id
;
648 static vec
<group_info_t
> rtx_group_vec
;
651 /* This structure holds the set of changes that are being deferred
652 when removing read operation. See replace_read. */
653 struct deferred_change
656 /* The mem that is being replaced. */
659 /* The reg it is being replaced with. */
662 struct deferred_change
*next
;
664 /* Pool allocation new operator. */
665 inline void *operator new (size_t)
667 return pool
.allocate ();
670 /* Delete operator utilizing pool allocation. */
671 inline void operator delete (void *ptr
)
673 pool
.remove ((deferred_change
*) ptr
);
676 /* Memory allocation pool. */
677 static pool_allocator
<deferred_change
> pool
;
680 typedef struct deferred_change
*deferred_change_t
;
682 pool_allocator
<deferred_change
> deferred_change::pool
683 ("deferred_change_pool", 10);
685 static deferred_change_t deferred_change_list
= NULL
;
687 /* The group that holds all of the clear_alias_sets. */
688 static group_info_t clear_alias_group
;
690 /* The modes of the clear_alias_sets. */
691 static htab_t clear_alias_mode_table
;
693 /* Hash table element to look up the mode for an alias set. */
694 struct clear_alias_mode_holder
696 alias_set_type alias_set
;
700 /* This is true except if cfun->stdarg -- i.e. we cannot do
701 this for vararg functions because they play games with the frame. */
702 static bool stores_off_frame_dead_at_return
;
704 /* Counter for stats. */
705 static int globally_deleted
;
706 static int locally_deleted
;
707 static int spill_deleted
;
709 static bitmap all_blocks
;
711 /* Locations that are killed by calls in the global phase. */
712 static bitmap kill_on_calls
;
714 /* The number of bits used in the global bitmaps. */
715 static unsigned int current_position
;
717 /*----------------------------------------------------------------------------
721 ----------------------------------------------------------------------------*/
724 /* Find the entry associated with ALIAS_SET. */
726 static struct clear_alias_mode_holder
*
727 clear_alias_set_lookup (alias_set_type alias_set
)
729 struct clear_alias_mode_holder tmp_holder
;
732 tmp_holder
.alias_set
= alias_set
;
733 slot
= htab_find_slot (clear_alias_mode_table
, &tmp_holder
, NO_INSERT
);
736 return (struct clear_alias_mode_holder
*) *slot
;
740 /* Hashtable callbacks for maintaining the "bases" field of
741 store_group_info, given that the addresses are function invariants. */
743 struct invariant_group_base_hasher
: typed_noop_remove
<group_info
>
745 typedef group_info
*value_type
;
746 typedef group_info
*compare_type
;
747 static inline hashval_t
hash (const group_info
*);
748 static inline bool equal (const group_info
*, const group_info
*);
752 invariant_group_base_hasher::equal (const group_info
*gi1
,
753 const group_info
*gi2
)
755 return rtx_equal_p (gi1
->rtx_base
, gi2
->rtx_base
);
759 invariant_group_base_hasher::hash (const group_info
*gi
)
762 return hash_rtx (gi
->rtx_base
, Pmode
, &do_not_record
, NULL
, false);
765 /* Tables of group_info structures, hashed by base value. */
766 static hash_table
<invariant_group_base_hasher
> *rtx_group_table
;
769 /* Get the GROUP for BASE. Add a new group if it is not there. */
772 get_group_info (rtx base
)
774 struct group_info tmp_gi
;
780 /* Find the store_base_info structure for BASE, creating a new one
782 tmp_gi
.rtx_base
= base
;
783 slot
= rtx_group_table
->find_slot (&tmp_gi
, INSERT
);
784 gi
= (group_info_t
) *slot
;
788 if (!clear_alias_group
)
790 clear_alias_group
= gi
= new group_info
;
791 memset (gi
, 0, sizeof (struct group_info
));
792 gi
->id
= rtx_group_next_id
++;
793 gi
->store1_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
794 gi
->store1_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
795 gi
->store2_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
796 gi
->store2_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
797 gi
->escaped_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
798 gi
->escaped_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
799 gi
->group_kill
= BITMAP_ALLOC (&dse_bitmap_obstack
);
800 gi
->process_globally
= false;
801 gi
->offset_map_size_n
= 0;
802 gi
->offset_map_size_p
= 0;
803 gi
->offset_map_n
= NULL
;
804 gi
->offset_map_p
= NULL
;
805 rtx_group_vec
.safe_push (gi
);
807 return clear_alias_group
;
812 *slot
= gi
= new group_info
;
814 gi
->id
= rtx_group_next_id
++;
815 gi
->base_mem
= gen_rtx_MEM (BLKmode
, base
);
816 gi
->canon_base_addr
= canon_rtx (base
);
817 gi
->store1_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
818 gi
->store1_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
819 gi
->store2_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
820 gi
->store2_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
821 gi
->escaped_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
822 gi
->escaped_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
823 gi
->group_kill
= BITMAP_ALLOC (&dse_bitmap_obstack
);
824 gi
->process_globally
= false;
826 (base
== frame_pointer_rtx
) || (base
== hard_frame_pointer_rtx
);
827 gi
->offset_map_size_n
= 0;
828 gi
->offset_map_size_p
= 0;
829 gi
->offset_map_n
= NULL
;
830 gi
->offset_map_p
= NULL
;
831 rtx_group_vec
.safe_push (gi
);
838 /* Initialization of data structures. */
844 globally_deleted
= 0;
847 bitmap_obstack_initialize (&dse_bitmap_obstack
);
848 gcc_obstack_init (&dse_obstack
);
850 scratch
= BITMAP_ALLOC (®_obstack
);
851 kill_on_calls
= BITMAP_ALLOC (&dse_bitmap_obstack
);
854 rtx_group_table
= new hash_table
<invariant_group_base_hasher
> (11);
856 bb_table
= XNEWVEC (bb_info_t
, last_basic_block_for_fn (cfun
));
857 rtx_group_next_id
= 0;
859 stores_off_frame_dead_at_return
= !cfun
->stdarg
;
861 init_alias_analysis ();
863 clear_alias_group
= NULL
;
868 /*----------------------------------------------------------------------------
871 Scan all of the insns. Any random ordering of the blocks is fine.
872 Each block is scanned in forward order to accommodate cselib which
873 is used to remove stores with non-constant bases.
874 ----------------------------------------------------------------------------*/
876 /* Delete all of the store_info recs from INSN_INFO. */
879 free_store_info (insn_info_t insn_info
)
881 store_info_t store_info
= insn_info
->store_rec
;
884 store_info_t next
= store_info
->next
;
885 if (store_info
->is_large
)
886 BITMAP_FREE (store_info
->positions_needed
.large
.bmap
);
887 if (store_info
->cse_base
)
888 cse_store_info_pool
.remove (store_info
);
890 rtx_store_info_pool
.remove (store_info
);
894 insn_info
->cannot_delete
= true;
895 insn_info
->contains_cselib_groups
= false;
896 insn_info
->store_rec
= NULL
;
901 rtx_insn
*first
, *current
;
902 regset fixed_regs_live
;
904 } note_add_store_info
;
906 /* Callback for emit_inc_dec_insn_before via note_stores.
907 Check if a register is clobbered which is live afterwards. */
910 note_add_store (rtx loc
, const_rtx expr ATTRIBUTE_UNUSED
, void *data
)
913 note_add_store_info
*info
= (note_add_store_info
*) data
;
918 /* If this register is referenced by the current or an earlier insn,
919 that's OK. E.g. this applies to the register that is being incremented
920 with this addition. */
921 for (insn
= info
->first
;
922 insn
!= NEXT_INSN (info
->current
);
923 insn
= NEXT_INSN (insn
))
924 if (reg_referenced_p (loc
, PATTERN (insn
)))
927 /* If we come here, we have a clobber of a register that's only OK
928 if that register is not live. If we don't have liveness information
929 available, fail now. */
930 if (!info
->fixed_regs_live
)
932 info
->failure
= true;
935 /* Now check if this is a live fixed register. */
936 unsigned int end_regno
= END_REGNO (loc
);
937 for (unsigned int regno
= REGNO (loc
); regno
< end_regno
; ++regno
)
938 if (REGNO_REG_SET_P (info
->fixed_regs_live
, regno
))
939 info
->failure
= true;
942 /* Callback for for_each_inc_dec that emits an INSN that sets DEST to
943 SRC + SRCOFF before insn ARG. */
946 emit_inc_dec_insn_before (rtx mem ATTRIBUTE_UNUSED
,
947 rtx op ATTRIBUTE_UNUSED
,
948 rtx dest
, rtx src
, rtx srcoff
, void *arg
)
950 insn_info_t insn_info
= (insn_info_t
) arg
;
951 rtx_insn
*insn
= insn_info
->insn
, *new_insn
, *cur
;
952 note_add_store_info info
;
954 /* We can reuse all operands without copying, because we are about
955 to delete the insn that contained it. */
959 emit_insn (gen_add3_insn (dest
, src
, srcoff
));
960 new_insn
= get_insns ();
964 new_insn
= gen_move_insn (dest
, src
);
965 info
.first
= new_insn
;
966 info
.fixed_regs_live
= insn_info
->fixed_regs_live
;
967 info
.failure
= false;
968 for (cur
= new_insn
; cur
; cur
= NEXT_INSN (cur
))
971 note_stores (PATTERN (cur
), note_add_store
, &info
);
974 /* If a failure was flagged above, return 1 so that for_each_inc_dec will
975 return it immediately, communicating the failure to its caller. */
979 emit_insn_before (new_insn
, insn
);
984 /* Before we delete INSN_INFO->INSN, make sure that the auto inc/dec, if it
985 is there, is split into a separate insn.
986 Return true on success (or if there was nothing to do), false on failure. */
989 check_for_inc_dec_1 (insn_info_t insn_info
)
991 rtx_insn
*insn
= insn_info
->insn
;
992 rtx note
= find_reg_note (insn
, REG_INC
, NULL_RTX
);
994 return for_each_inc_dec (PATTERN (insn
), emit_inc_dec_insn_before
,
1000 /* Entry point for postreload. If you work on reload_cse, or you need this
1001 anywhere else, consider if you can provide register liveness information
1002 and add a parameter to this function so that it can be passed down in
1003 insn_info.fixed_regs_live. */
1005 check_for_inc_dec (rtx_insn
*insn
)
1007 insn_info_type insn_info
;
1010 insn_info
.insn
= insn
;
1011 insn_info
.fixed_regs_live
= NULL
;
1012 note
= find_reg_note (insn
, REG_INC
, NULL_RTX
);
1014 return for_each_inc_dec (PATTERN (insn
), emit_inc_dec_insn_before
,
1019 /* Delete the insn and free all of the fields inside INSN_INFO. */
1022 delete_dead_store_insn (insn_info_t insn_info
)
1024 read_info_t read_info
;
1029 if (!check_for_inc_dec_1 (insn_info
))
1031 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1033 fprintf (dump_file
, "Locally deleting insn %d ",
1034 INSN_UID (insn_info
->insn
));
1035 if (insn_info
->store_rec
->alias_set
)
1036 fprintf (dump_file
, "alias set %d\n",
1037 (int) insn_info
->store_rec
->alias_set
);
1039 fprintf (dump_file
, "\n");
1042 free_store_info (insn_info
);
1043 read_info
= insn_info
->read_rec
;
1047 read_info_t next
= read_info
->next
;
1051 insn_info
->read_rec
= NULL
;
1053 delete_insn (insn_info
->insn
);
1055 insn_info
->insn
= NULL
;
1057 insn_info
->wild_read
= false;
1060 /* Return whether DECL, a local variable, can possibly escape the current
1064 local_variable_can_escape (tree decl
)
1066 if (TREE_ADDRESSABLE (decl
))
1069 /* If this is a partitioned variable, we need to consider all the variables
1070 in the partition. This is necessary because a store into one of them can
1071 be replaced with a store into another and this may not change the outcome
1072 of the escape analysis. */
1073 if (cfun
->gimple_df
->decls_to_pointers
!= NULL
)
1075 tree
*namep
= cfun
->gimple_df
->decls_to_pointers
->get (decl
);
1077 return TREE_ADDRESSABLE (*namep
);
1083 /* Return whether EXPR can possibly escape the current function scope. */
1086 can_escape (tree expr
)
1091 base
= get_base_address (expr
);
1093 && !may_be_aliased (base
)
1094 && !(TREE_CODE (base
) == VAR_DECL
1095 && !DECL_EXTERNAL (base
)
1096 && !TREE_STATIC (base
)
1097 && local_variable_can_escape (base
)))
1102 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
1103 OFFSET and WIDTH. */
1106 set_usage_bits (group_info_t group
, HOST_WIDE_INT offset
, HOST_WIDE_INT width
,
1110 bool expr_escapes
= can_escape (expr
);
1111 if (offset
> -MAX_OFFSET
&& offset
+ width
< MAX_OFFSET
)
1112 for (i
=offset
; i
<offset
+width
; i
++)
1120 store1
= group
->store1_n
;
1121 store2
= group
->store2_n
;
1122 escaped
= group
->escaped_n
;
1127 store1
= group
->store1_p
;
1128 store2
= group
->store2_p
;
1129 escaped
= group
->escaped_p
;
1133 if (!bitmap_set_bit (store1
, ai
))
1134 bitmap_set_bit (store2
, ai
);
1139 if (group
->offset_map_size_n
< ai
)
1140 group
->offset_map_size_n
= ai
;
1144 if (group
->offset_map_size_p
< ai
)
1145 group
->offset_map_size_p
= ai
;
1149 bitmap_set_bit (escaped
, ai
);
1154 reset_active_stores (void)
1156 active_local_stores
= NULL
;
1157 active_local_stores_len
= 0;
1160 /* Free all READ_REC of the LAST_INSN of BB_INFO. */
1163 free_read_records (bb_info_t bb_info
)
1165 insn_info_t insn_info
= bb_info
->last_insn
;
1166 read_info_t
*ptr
= &insn_info
->read_rec
;
1169 read_info_t next
= (*ptr
)->next
;
1170 if ((*ptr
)->alias_set
== 0)
1176 ptr
= &(*ptr
)->next
;
1180 /* Set the BB_INFO so that the last insn is marked as a wild read. */
1183 add_wild_read (bb_info_t bb_info
)
1185 insn_info_t insn_info
= bb_info
->last_insn
;
1186 insn_info
->wild_read
= true;
1187 free_read_records (bb_info
);
1188 reset_active_stores ();
1191 /* Set the BB_INFO so that the last insn is marked as a wild read of
1192 non-frame locations. */
1195 add_non_frame_wild_read (bb_info_t bb_info
)
1197 insn_info_t insn_info
= bb_info
->last_insn
;
1198 insn_info
->non_frame_wild_read
= true;
1199 free_read_records (bb_info
);
1200 reset_active_stores ();
1203 /* Return true if X is a constant or one of the registers that behave
1204 as a constant over the life of a function. This is equivalent to
1205 !rtx_varies_p for memory addresses. */
1208 const_or_frame_p (rtx x
)
1213 if (GET_CODE (x
) == REG
)
1215 /* Note that we have to test for the actual rtx used for the frame
1216 and arg pointers and not just the register number in case we have
1217 eliminated the frame and/or arg pointer and are using it
1219 if (x
== frame_pointer_rtx
|| x
== hard_frame_pointer_rtx
1220 /* The arg pointer varies if it is not a fixed register. */
1221 || (x
== arg_pointer_rtx
&& fixed_regs
[ARG_POINTER_REGNUM
])
1222 || x
== pic_offset_table_rtx
)
1230 /* Take all reasonable action to put the address of MEM into the form
1231 that we can do analysis on.
1233 The gold standard is to get the address into the form: address +
1234 OFFSET where address is something that rtx_varies_p considers a
1235 constant. When we can get the address in this form, we can do
1236 global analysis on it. Note that for constant bases, address is
1237 not actually returned, only the group_id. The address can be
1240 If that fails, we try cselib to get a value we can at least use
1241 locally. If that fails we return false.
1243 The GROUP_ID is set to -1 for cselib bases and the index of the
1244 group for non_varying bases.
1246 FOR_READ is true if this is a mem read and false if not. */
1249 canon_address (rtx mem
,
1250 alias_set_type
*alias_set_out
,
1252 HOST_WIDE_INT
*offset
,
1255 machine_mode address_mode
= get_address_mode (mem
);
1256 rtx mem_address
= XEXP (mem
, 0);
1257 rtx expanded_address
, address
;
1262 cselib_lookup (mem_address
, address_mode
, 1, GET_MODE (mem
));
1264 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1266 fprintf (dump_file
, " mem: ");
1267 print_inline_rtx (dump_file
, mem_address
, 0);
1268 fprintf (dump_file
, "\n");
1271 /* First see if just canon_rtx (mem_address) is const or frame,
1272 if not, try cselib_expand_value_rtx and call canon_rtx on that. */
1274 for (expanded
= 0; expanded
< 2; expanded
++)
1278 /* Use cselib to replace all of the reg references with the full
1279 expression. This will take care of the case where we have
1281 r_x = base + offset;
1286 val = *(base + offset); */
1288 expanded_address
= cselib_expand_value_rtx (mem_address
,
1291 /* If this fails, just go with the address from first
1293 if (!expanded_address
)
1297 expanded_address
= mem_address
;
1299 /* Split the address into canonical BASE + OFFSET terms. */
1300 address
= canon_rtx (expanded_address
);
1304 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1308 fprintf (dump_file
, "\n after cselib_expand address: ");
1309 print_inline_rtx (dump_file
, expanded_address
, 0);
1310 fprintf (dump_file
, "\n");
1313 fprintf (dump_file
, "\n after canon_rtx address: ");
1314 print_inline_rtx (dump_file
, address
, 0);
1315 fprintf (dump_file
, "\n");
1318 if (GET_CODE (address
) == CONST
)
1319 address
= XEXP (address
, 0);
1321 if (GET_CODE (address
) == PLUS
1322 && CONST_INT_P (XEXP (address
, 1)))
1324 *offset
= INTVAL (XEXP (address
, 1));
1325 address
= XEXP (address
, 0);
1328 if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem
))
1329 && const_or_frame_p (address
))
1331 group_info_t group
= get_group_info (address
);
1333 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1334 fprintf (dump_file
, " gid=%d offset=%d \n",
1335 group
->id
, (int)*offset
);
1337 *group_id
= group
->id
;
1342 *base
= cselib_lookup (address
, address_mode
, true, GET_MODE (mem
));
1347 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1348 fprintf (dump_file
, " no cselib val - should be a wild read.\n");
1351 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1352 fprintf (dump_file
, " varying cselib base=%u:%u offset = %d\n",
1353 (*base
)->uid
, (*base
)->hash
, (int)*offset
);
1358 /* Clear the rhs field from the active_local_stores array. */
1361 clear_rhs_from_active_local_stores (void)
1363 insn_info_t ptr
= active_local_stores
;
1367 store_info_t store_info
= ptr
->store_rec
;
1368 /* Skip the clobbers. */
1369 while (!store_info
->is_set
)
1370 store_info
= store_info
->next
;
1372 store_info
->rhs
= NULL
;
1373 store_info
->const_rhs
= NULL
;
1375 ptr
= ptr
->next_local_store
;
1380 /* Mark byte POS bytes from the beginning of store S_INFO as unneeded. */
1383 set_position_unneeded (store_info_t s_info
, int pos
)
1385 if (__builtin_expect (s_info
->is_large
, false))
1387 if (bitmap_set_bit (s_info
->positions_needed
.large
.bmap
, pos
))
1388 s_info
->positions_needed
.large
.count
++;
1391 s_info
->positions_needed
.small_bitmask
1392 &= ~(((unsigned HOST_WIDE_INT
) 1) << pos
);
1395 /* Mark the whole store S_INFO as unneeded. */
1398 set_all_positions_unneeded (store_info_t s_info
)
1400 if (__builtin_expect (s_info
->is_large
, false))
1402 int pos
, end
= s_info
->end
- s_info
->begin
;
1403 for (pos
= 0; pos
< end
; pos
++)
1404 bitmap_set_bit (s_info
->positions_needed
.large
.bmap
, pos
);
1405 s_info
->positions_needed
.large
.count
= end
;
1408 s_info
->positions_needed
.small_bitmask
= (unsigned HOST_WIDE_INT
) 0;
1411 /* Return TRUE if any bytes from S_INFO store are needed. */
1414 any_positions_needed_p (store_info_t s_info
)
1416 if (__builtin_expect (s_info
->is_large
, false))
1417 return (s_info
->positions_needed
.large
.count
1418 < s_info
->end
- s_info
->begin
);
1420 return (s_info
->positions_needed
.small_bitmask
1421 != (unsigned HOST_WIDE_INT
) 0);
1424 /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
1425 store are needed. */
1428 all_positions_needed_p (store_info_t s_info
, int start
, int width
)
1430 if (__builtin_expect (s_info
->is_large
, false))
1432 int end
= start
+ width
;
1434 if (bitmap_bit_p (s_info
->positions_needed
.large
.bmap
, start
++))
1440 unsigned HOST_WIDE_INT mask
= lowpart_bitmask (width
) << start
;
1441 return (s_info
->positions_needed
.small_bitmask
& mask
) == mask
;
1446 static rtx
get_stored_val (store_info_t
, machine_mode
, HOST_WIDE_INT
,
1447 HOST_WIDE_INT
, basic_block
, bool);
1450 /* BODY is an instruction pattern that belongs to INSN. Return 1 if
1451 there is a candidate store, after adding it to the appropriate
1452 local store group if so. */
1455 record_store (rtx body
, bb_info_t bb_info
)
1457 rtx mem
, rhs
, const_rhs
, mem_addr
;
1458 HOST_WIDE_INT offset
= 0;
1459 HOST_WIDE_INT width
= 0;
1460 alias_set_type spill_alias_set
;
1461 insn_info_t insn_info
= bb_info
->last_insn
;
1462 store_info_t store_info
= NULL
;
1464 cselib_val
*base
= NULL
;
1465 insn_info_t ptr
, last
, redundant_reason
;
1466 bool store_is_unused
;
1468 if (GET_CODE (body
) != SET
&& GET_CODE (body
) != CLOBBER
)
1471 mem
= SET_DEST (body
);
1473 /* If this is not used, then this cannot be used to keep the insn
1474 from being deleted. On the other hand, it does provide something
1475 that can be used to prove that another store is dead. */
1477 = (find_reg_note (insn_info
->insn
, REG_UNUSED
, mem
) != NULL
);
1479 /* Check whether that value is a suitable memory location. */
1482 /* If the set or clobber is unused, then it does not effect our
1483 ability to get rid of the entire insn. */
1484 if (!store_is_unused
)
1485 insn_info
->cannot_delete
= true;
1489 /* At this point we know mem is a mem. */
1490 if (GET_MODE (mem
) == BLKmode
)
1492 if (GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
1494 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1495 fprintf (dump_file
, " adding wild read for (clobber (mem:BLK (scratch))\n");
1496 add_wild_read (bb_info
);
1497 insn_info
->cannot_delete
= true;
1500 /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
1501 as memset (addr, 0, 36); */
1502 else if (!MEM_SIZE_KNOWN_P (mem
)
1503 || MEM_SIZE (mem
) <= 0
1504 || MEM_SIZE (mem
) > MAX_OFFSET
1505 || GET_CODE (body
) != SET
1506 || !CONST_INT_P (SET_SRC (body
)))
1508 if (!store_is_unused
)
1510 /* If the set or clobber is unused, then it does not effect our
1511 ability to get rid of the entire insn. */
1512 insn_info
->cannot_delete
= true;
1513 clear_rhs_from_active_local_stores ();
1519 /* We can still process a volatile mem, we just cannot delete it. */
1520 if (MEM_VOLATILE_P (mem
))
1521 insn_info
->cannot_delete
= true;
1523 if (!canon_address (mem
, &spill_alias_set
, &group_id
, &offset
, &base
))
1525 clear_rhs_from_active_local_stores ();
1529 if (GET_MODE (mem
) == BLKmode
)
1530 width
= MEM_SIZE (mem
);
1532 width
= GET_MODE_SIZE (GET_MODE (mem
));
1534 if (spill_alias_set
)
1536 bitmap store1
= clear_alias_group
->store1_p
;
1537 bitmap store2
= clear_alias_group
->store2_p
;
1539 gcc_assert (GET_MODE (mem
) != BLKmode
);
1541 if (!bitmap_set_bit (store1
, spill_alias_set
))
1542 bitmap_set_bit (store2
, spill_alias_set
);
1544 if (clear_alias_group
->offset_map_size_p
< spill_alias_set
)
1545 clear_alias_group
->offset_map_size_p
= spill_alias_set
;
1547 store_info
= rtx_store_info_pool
.allocate ();
1549 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1550 fprintf (dump_file
, " processing spill store %d(%s)\n",
1551 (int) spill_alias_set
, GET_MODE_NAME (GET_MODE (mem
)));
1553 else if (group_id
>= 0)
1555 /* In the restrictive case where the base is a constant or the
1556 frame pointer we can do global analysis. */
1559 = rtx_group_vec
[group_id
];
1560 tree expr
= MEM_EXPR (mem
);
1562 store_info
= rtx_store_info_pool
.allocate ();
1563 set_usage_bits (group
, offset
, width
, expr
);
1565 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1566 fprintf (dump_file
, " processing const base store gid=%d[%d..%d)\n",
1567 group_id
, (int)offset
, (int)(offset
+width
));
1571 if (may_be_sp_based_p (XEXP (mem
, 0)))
1572 insn_info
->stack_pointer_based
= true;
1573 insn_info
->contains_cselib_groups
= true;
1575 store_info
= cse_store_info_pool
.allocate ();
1578 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1579 fprintf (dump_file
, " processing cselib store [%d..%d)\n",
1580 (int)offset
, (int)(offset
+width
));
1583 const_rhs
= rhs
= NULL_RTX
;
1584 if (GET_CODE (body
) == SET
1585 /* No place to keep the value after ra. */
1586 && !reload_completed
1587 && (REG_P (SET_SRC (body
))
1588 || GET_CODE (SET_SRC (body
)) == SUBREG
1589 || CONSTANT_P (SET_SRC (body
)))
1590 && !MEM_VOLATILE_P (mem
)
1591 /* Sometimes the store and reload is used for truncation and
1593 && !(FLOAT_MODE_P (GET_MODE (mem
)) && (flag_float_store
)))
1595 rhs
= SET_SRC (body
);
1596 if (CONSTANT_P (rhs
))
1598 else if (body
== PATTERN (insn_info
->insn
))
1600 rtx tem
= find_reg_note (insn_info
->insn
, REG_EQUAL
, NULL_RTX
);
1601 if (tem
&& CONSTANT_P (XEXP (tem
, 0)))
1602 const_rhs
= XEXP (tem
, 0);
1604 if (const_rhs
== NULL_RTX
&& REG_P (rhs
))
1606 rtx tem
= cselib_expand_value_rtx (rhs
, scratch
, 5);
1608 if (tem
&& CONSTANT_P (tem
))
1613 /* Check to see if this stores causes some other stores to be
1615 ptr
= active_local_stores
;
1617 redundant_reason
= NULL
;
1618 mem
= canon_rtx (mem
);
1619 /* For alias_set != 0 canon_true_dependence should be never called. */
1620 if (spill_alias_set
)
1621 mem_addr
= NULL_RTX
;
1625 mem_addr
= base
->val_rtx
;
1629 = rtx_group_vec
[group_id
];
1630 mem_addr
= group
->canon_base_addr
;
1632 /* get_addr can only handle VALUE but cannot handle expr like:
1633 VALUE + OFFSET, so call get_addr to get original addr for
1634 mem_addr before plus_constant. */
1635 mem_addr
= get_addr (mem_addr
);
1637 mem_addr
= plus_constant (get_address_mode (mem
), mem_addr
, offset
);
1642 insn_info_t next
= ptr
->next_local_store
;
1643 store_info_t s_info
= ptr
->store_rec
;
1646 /* Skip the clobbers. We delete the active insn if this insn
1647 shadows the set. To have been put on the active list, it
1648 has exactly on set. */
1649 while (!s_info
->is_set
)
1650 s_info
= s_info
->next
;
1652 if (s_info
->alias_set
!= spill_alias_set
)
1654 else if (s_info
->alias_set
)
1656 struct clear_alias_mode_holder
*entry
1657 = clear_alias_set_lookup (s_info
->alias_set
);
1658 /* Generally, spills cannot be processed if and of the
1659 references to the slot have a different mode. But if
1660 we are in the same block and mode is exactly the same
1661 between this store and one before in the same block,
1662 we can still delete it. */
1663 if ((GET_MODE (mem
) == GET_MODE (s_info
->mem
))
1664 && (GET_MODE (mem
) == entry
->mode
))
1667 set_all_positions_unneeded (s_info
);
1669 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1670 fprintf (dump_file
, " trying spill store in insn=%d alias_set=%d\n",
1671 INSN_UID (ptr
->insn
), (int) s_info
->alias_set
);
1673 else if ((s_info
->group_id
== group_id
)
1674 && (s_info
->cse_base
== base
))
1677 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1678 fprintf (dump_file
, " trying store in insn=%d gid=%d[%d..%d)\n",
1679 INSN_UID (ptr
->insn
), s_info
->group_id
,
1680 (int)s_info
->begin
, (int)s_info
->end
);
1682 /* Even if PTR won't be eliminated as unneeded, if both
1683 PTR and this insn store the same constant value, we might
1684 eliminate this insn instead. */
1685 if (s_info
->const_rhs
1687 && offset
>= s_info
->begin
1688 && offset
+ width
<= s_info
->end
1689 && all_positions_needed_p (s_info
, offset
- s_info
->begin
,
1692 if (GET_MODE (mem
) == BLKmode
)
1694 if (GET_MODE (s_info
->mem
) == BLKmode
1695 && s_info
->const_rhs
== const_rhs
)
1696 redundant_reason
= ptr
;
1698 else if (s_info
->const_rhs
== const0_rtx
1699 && const_rhs
== const0_rtx
)
1700 redundant_reason
= ptr
;
1705 val
= get_stored_val (s_info
, GET_MODE (mem
),
1706 offset
, offset
+ width
,
1707 BLOCK_FOR_INSN (insn_info
->insn
),
1709 if (get_insns () != NULL
)
1712 if (val
&& rtx_equal_p (val
, const_rhs
))
1713 redundant_reason
= ptr
;
1717 for (i
= MAX (offset
, s_info
->begin
);
1718 i
< offset
+ width
&& i
< s_info
->end
;
1720 set_position_unneeded (s_info
, i
- s_info
->begin
);
1722 else if (s_info
->rhs
)
1723 /* Need to see if it is possible for this store to overwrite
1724 the value of store_info. If it is, set the rhs to NULL to
1725 keep it from being used to remove a load. */
1727 if (canon_true_dependence (s_info
->mem
,
1728 GET_MODE (s_info
->mem
),
1733 s_info
->const_rhs
= NULL
;
1737 /* An insn can be deleted if every position of every one of
1738 its s_infos is zero. */
1739 if (any_positions_needed_p (s_info
))
1744 insn_info_t insn_to_delete
= ptr
;
1746 active_local_stores_len
--;
1748 last
->next_local_store
= ptr
->next_local_store
;
1750 active_local_stores
= ptr
->next_local_store
;
1752 if (!insn_to_delete
->cannot_delete
)
1753 delete_dead_store_insn (insn_to_delete
);
1761 /* Finish filling in the store_info. */
1762 store_info
->next
= insn_info
->store_rec
;
1763 insn_info
->store_rec
= store_info
;
1764 store_info
->mem
= mem
;
1765 store_info
->alias_set
= spill_alias_set
;
1766 store_info
->mem_addr
= mem_addr
;
1767 store_info
->cse_base
= base
;
1768 if (width
> HOST_BITS_PER_WIDE_INT
)
1770 store_info
->is_large
= true;
1771 store_info
->positions_needed
.large
.count
= 0;
1772 store_info
->positions_needed
.large
.bmap
= BITMAP_ALLOC (&dse_bitmap_obstack
);
1776 store_info
->is_large
= false;
1777 store_info
->positions_needed
.small_bitmask
= lowpart_bitmask (width
);
1779 store_info
->group_id
= group_id
;
1780 store_info
->begin
= offset
;
1781 store_info
->end
= offset
+ width
;
1782 store_info
->is_set
= GET_CODE (body
) == SET
;
1783 store_info
->rhs
= rhs
;
1784 store_info
->const_rhs
= const_rhs
;
1785 store_info
->redundant_reason
= redundant_reason
;
1787 /* If this is a clobber, we return 0. We will only be able to
1788 delete this insn if there is only one store USED store, but we
1789 can use the clobber to delete other stores earlier. */
1790 return store_info
->is_set
? 1 : 0;
1795 dump_insn_info (const char * start
, insn_info_t insn_info
)
1797 fprintf (dump_file
, "%s insn=%d %s\n", start
,
1798 INSN_UID (insn_info
->insn
),
1799 insn_info
->store_rec
? "has store" : "naked");
1803 /* If the modes are different and the value's source and target do not
1804 line up, we need to extract the value from lower part of the rhs of
1805 the store, shift it, and then put it into a form that can be shoved
1806 into the read_insn. This function generates a right SHIFT of a
1807 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The
1808 shift sequence is returned or NULL if we failed to find a
1812 find_shift_sequence (int access_size
,
1813 store_info_t store_info
,
1814 machine_mode read_mode
,
1815 int shift
, bool speed
, bool require_cst
)
1817 machine_mode store_mode
= GET_MODE (store_info
->mem
);
1818 machine_mode new_mode
;
1819 rtx read_reg
= NULL
;
1821 /* Some machines like the x86 have shift insns for each size of
1822 operand. Other machines like the ppc or the ia-64 may only have
1823 shift insns that shift values within 32 or 64 bit registers.
1824 This loop tries to find the smallest shift insn that will right
1825 justify the value we want to read but is available in one insn on
1828 for (new_mode
= smallest_mode_for_size (access_size
* BITS_PER_UNIT
,
1830 GET_MODE_BITSIZE (new_mode
) <= BITS_PER_WORD
;
1831 new_mode
= GET_MODE_WIDER_MODE (new_mode
))
1833 rtx target
, new_reg
, new_lhs
;
1834 rtx_insn
*shift_seq
, *insn
;
1837 /* If a constant was stored into memory, try to simplify it here,
1838 otherwise the cost of the shift might preclude this optimization
1839 e.g. at -Os, even when no actual shift will be needed. */
1840 if (store_info
->const_rhs
)
1842 unsigned int byte
= subreg_lowpart_offset (new_mode
, store_mode
);
1843 rtx ret
= simplify_subreg (new_mode
, store_info
->const_rhs
,
1845 if (ret
&& CONSTANT_P (ret
))
1847 ret
= simplify_const_binary_operation (LSHIFTRT
, new_mode
,
1848 ret
, GEN_INT (shift
));
1849 if (ret
&& CONSTANT_P (ret
))
1851 byte
= subreg_lowpart_offset (read_mode
, new_mode
);
1852 ret
= simplify_subreg (read_mode
, ret
, new_mode
, byte
);
1853 if (ret
&& CONSTANT_P (ret
)
1854 && set_src_cost (ret
, speed
) <= COSTS_N_INSNS (1))
1863 /* Try a wider mode if truncating the store mode to NEW_MODE
1864 requires a real instruction. */
1865 if (GET_MODE_BITSIZE (new_mode
) < GET_MODE_BITSIZE (store_mode
)
1866 && !TRULY_NOOP_TRUNCATION_MODES_P (new_mode
, store_mode
))
1869 /* Also try a wider mode if the necessary punning is either not
1870 desirable or not possible. */
1871 if (!CONSTANT_P (store_info
->rhs
)
1872 && !MODES_TIEABLE_P (new_mode
, store_mode
))
1875 new_reg
= gen_reg_rtx (new_mode
);
1879 /* In theory we could also check for an ashr. Ian Taylor knows
1880 of one dsp where the cost of these two was not the same. But
1881 this really is a rare case anyway. */
1882 target
= expand_binop (new_mode
, lshr_optab
, new_reg
,
1883 GEN_INT (shift
), new_reg
, 1, OPTAB_DIRECT
);
1885 shift_seq
= get_insns ();
1888 if (target
!= new_reg
|| shift_seq
== NULL
)
1892 for (insn
= shift_seq
; insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
1894 cost
+= insn_rtx_cost (PATTERN (insn
), speed
);
1896 /* The computation up to here is essentially independent
1897 of the arguments and could be precomputed. It may
1898 not be worth doing so. We could precompute if
1899 worthwhile or at least cache the results. The result
1900 technically depends on both SHIFT and ACCESS_SIZE,
1901 but in practice the answer will depend only on ACCESS_SIZE. */
1903 if (cost
> COSTS_N_INSNS (1))
1906 new_lhs
= extract_low_bits (new_mode
, store_mode
,
1907 copy_rtx (store_info
->rhs
));
1908 if (new_lhs
== NULL_RTX
)
1911 /* We found an acceptable shift. Generate a move to
1912 take the value from the store and put it into the
1913 shift pseudo, then shift it, then generate another
1914 move to put in into the target of the read. */
1915 emit_move_insn (new_reg
, new_lhs
);
1916 emit_insn (shift_seq
);
1917 read_reg
= extract_low_bits (read_mode
, new_mode
, new_reg
);
1925 /* Call back for note_stores to find the hard regs set or clobbered by
1926 insn. Data is a bitmap of the hardregs set so far. */
1929 look_for_hardregs (rtx x
, const_rtx pat ATTRIBUTE_UNUSED
, void *data
)
1931 bitmap regs_set
= (bitmap
) data
;
1934 && HARD_REGISTER_P (x
))
1935 bitmap_set_range (regs_set
, REGNO (x
), REG_NREGS (x
));
1938 /* Helper function for replace_read and record_store.
1939 Attempt to return a value stored in STORE_INFO, from READ_BEGIN
1940 to one before READ_END bytes read in READ_MODE. Return NULL
1941 if not successful. If REQUIRE_CST is true, return always constant. */
1944 get_stored_val (store_info_t store_info
, machine_mode read_mode
,
1945 HOST_WIDE_INT read_begin
, HOST_WIDE_INT read_end
,
1946 basic_block bb
, bool require_cst
)
1948 machine_mode store_mode
= GET_MODE (store_info
->mem
);
1950 int access_size
; /* In bytes. */
1953 /* To get here the read is within the boundaries of the write so
1954 shift will never be negative. Start out with the shift being in
1956 if (store_mode
== BLKmode
)
1958 else if (BYTES_BIG_ENDIAN
)
1959 shift
= store_info
->end
- read_end
;
1961 shift
= read_begin
- store_info
->begin
;
1963 access_size
= shift
+ GET_MODE_SIZE (read_mode
);
1965 /* From now on it is bits. */
1966 shift
*= BITS_PER_UNIT
;
1969 read_reg
= find_shift_sequence (access_size
, store_info
, read_mode
, shift
,
1970 optimize_bb_for_speed_p (bb
),
1972 else if (store_mode
== BLKmode
)
1974 /* The store is a memset (addr, const_val, const_size). */
1975 gcc_assert (CONST_INT_P (store_info
->rhs
));
1976 store_mode
= int_mode_for_mode (read_mode
);
1977 if (store_mode
== BLKmode
)
1978 read_reg
= NULL_RTX
;
1979 else if (store_info
->rhs
== const0_rtx
)
1980 read_reg
= extract_low_bits (read_mode
, store_mode
, const0_rtx
);
1981 else if (GET_MODE_BITSIZE (store_mode
) > HOST_BITS_PER_WIDE_INT
1982 || BITS_PER_UNIT
>= HOST_BITS_PER_WIDE_INT
)
1983 read_reg
= NULL_RTX
;
1986 unsigned HOST_WIDE_INT c
1987 = INTVAL (store_info
->rhs
)
1988 & (((HOST_WIDE_INT
) 1 << BITS_PER_UNIT
) - 1);
1989 int shift
= BITS_PER_UNIT
;
1990 while (shift
< HOST_BITS_PER_WIDE_INT
)
1995 read_reg
= gen_int_mode (c
, store_mode
);
1996 read_reg
= extract_low_bits (read_mode
, store_mode
, read_reg
);
1999 else if (store_info
->const_rhs
2001 || GET_MODE_CLASS (read_mode
) != GET_MODE_CLASS (store_mode
)))
2002 read_reg
= extract_low_bits (read_mode
, store_mode
,
2003 copy_rtx (store_info
->const_rhs
));
2005 read_reg
= extract_low_bits (read_mode
, store_mode
,
2006 copy_rtx (store_info
->rhs
));
2007 if (require_cst
&& read_reg
&& !CONSTANT_P (read_reg
))
2008 read_reg
= NULL_RTX
;
2012 /* Take a sequence of:
2035 Depending on the alignment and the mode of the store and
2039 The STORE_INFO and STORE_INSN are for the store and READ_INFO
2040 and READ_INSN are for the read. Return true if the replacement
2044 replace_read (store_info_t store_info
, insn_info_t store_insn
,
2045 read_info_t read_info
, insn_info_t read_insn
, rtx
*loc
,
2048 machine_mode store_mode
= GET_MODE (store_info
->mem
);
2049 machine_mode read_mode
= GET_MODE (read_info
->mem
);
2050 rtx_insn
*insns
, *this_insn
;
2057 /* Create a sequence of instructions to set up the read register.
2058 This sequence goes immediately before the store and its result
2059 is read by the load.
2061 We need to keep this in perspective. We are replacing a read
2062 with a sequence of insns, but the read will almost certainly be
2063 in cache, so it is not going to be an expensive one. Thus, we
2064 are not willing to do a multi insn shift or worse a subroutine
2065 call to get rid of the read. */
2066 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2067 fprintf (dump_file
, "trying to replace %smode load in insn %d"
2068 " from %smode store in insn %d\n",
2069 GET_MODE_NAME (read_mode
), INSN_UID (read_insn
->insn
),
2070 GET_MODE_NAME (store_mode
), INSN_UID (store_insn
->insn
));
2072 bb
= BLOCK_FOR_INSN (read_insn
->insn
);
2073 read_reg
= get_stored_val (store_info
,
2074 read_mode
, read_info
->begin
, read_info
->end
,
2076 if (read_reg
== NULL_RTX
)
2079 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2080 fprintf (dump_file
, " -- could not extract bits of stored value\n");
2083 /* Force the value into a new register so that it won't be clobbered
2084 between the store and the load. */
2085 read_reg
= copy_to_mode_reg (read_mode
, read_reg
);
2086 insns
= get_insns ();
2089 if (insns
!= NULL_RTX
)
2091 /* Now we have to scan the set of new instructions to see if the
2092 sequence contains and sets of hardregs that happened to be
2093 live at this point. For instance, this can happen if one of
2094 the insns sets the CC and the CC happened to be live at that
2095 point. This does occasionally happen, see PR 37922. */
2096 bitmap regs_set
= BITMAP_ALLOC (®_obstack
);
2098 for (this_insn
= insns
; this_insn
!= NULL_RTX
; this_insn
= NEXT_INSN (this_insn
))
2099 note_stores (PATTERN (this_insn
), look_for_hardregs
, regs_set
);
2101 bitmap_and_into (regs_set
, regs_live
);
2102 if (!bitmap_empty_p (regs_set
))
2104 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2107 "abandoning replacement because sequence clobbers live hardregs:");
2108 df_print_regset (dump_file
, regs_set
);
2111 BITMAP_FREE (regs_set
);
2114 BITMAP_FREE (regs_set
);
2117 if (validate_change (read_insn
->insn
, loc
, read_reg
, 0))
2119 deferred_change_t change
= new deferred_change
;
2121 /* Insert this right before the store insn where it will be safe
2122 from later insns that might change it before the read. */
2123 emit_insn_before (insns
, store_insn
->insn
);
2125 /* And now for the kludge part: cselib croaks if you just
2126 return at this point. There are two reasons for this:
2128 1) Cselib has an idea of how many pseudos there are and
2129 that does not include the new ones we just added.
2131 2) Cselib does not know about the move insn we added
2132 above the store_info, and there is no way to tell it
2133 about it, because it has "moved on".
2135 Problem (1) is fixable with a certain amount of engineering.
2136 Problem (2) is requires starting the bb from scratch. This
2139 So we are just going to have to lie. The move/extraction
2140 insns are not really an issue, cselib did not see them. But
2141 the use of the new pseudo read_insn is a real problem because
2142 cselib has not scanned this insn. The way that we solve this
2143 problem is that we are just going to put the mem back for now
2144 and when we are finished with the block, we undo this. We
2145 keep a table of mems to get rid of. At the end of the basic
2146 block we can put them back. */
2148 *loc
= read_info
->mem
;
2149 change
->next
= deferred_change_list
;
2150 deferred_change_list
= change
;
2152 change
->reg
= read_reg
;
2154 /* Get rid of the read_info, from the point of view of the
2155 rest of dse, play like this read never happened. */
2156 read_insn
->read_rec
= read_info
->next
;
2158 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2160 fprintf (dump_file
, " -- replaced the loaded MEM with ");
2161 print_simple_rtl (dump_file
, read_reg
);
2162 fprintf (dump_file
, "\n");
2168 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2170 fprintf (dump_file
, " -- replacing the loaded MEM with ");
2171 print_simple_rtl (dump_file
, read_reg
);
2172 fprintf (dump_file
, " led to an invalid instruction\n");
2178 /* Check the address of MEM *LOC and kill any appropriate stores that may
2182 check_mem_read_rtx (rtx
*loc
, bb_info_t bb_info
)
2184 rtx mem
= *loc
, mem_addr
;
2185 insn_info_t insn_info
;
2186 HOST_WIDE_INT offset
= 0;
2187 HOST_WIDE_INT width
= 0;
2188 alias_set_type spill_alias_set
= 0;
2189 cselib_val
*base
= NULL
;
2191 read_info_t read_info
;
2193 insn_info
= bb_info
->last_insn
;
2195 if ((MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2196 || (MEM_VOLATILE_P (mem
)))
2198 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2199 fprintf (dump_file
, " adding wild read, volatile or barrier.\n");
2200 add_wild_read (bb_info
);
2201 insn_info
->cannot_delete
= true;
2205 /* If it is reading readonly mem, then there can be no conflict with
2207 if (MEM_READONLY_P (mem
))
2210 if (!canon_address (mem
, &spill_alias_set
, &group_id
, &offset
, &base
))
2212 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2213 fprintf (dump_file
, " adding wild read, canon_address failure.\n");
2214 add_wild_read (bb_info
);
2218 if (GET_MODE (mem
) == BLKmode
)
2221 width
= GET_MODE_SIZE (GET_MODE (mem
));
2223 read_info
= new read_info_type
;
2224 read_info
->group_id
= group_id
;
2225 read_info
->mem
= mem
;
2226 read_info
->alias_set
= spill_alias_set
;
2227 read_info
->begin
= offset
;
2228 read_info
->end
= offset
+ width
;
2229 read_info
->next
= insn_info
->read_rec
;
2230 insn_info
->read_rec
= read_info
;
2231 /* For alias_set != 0 canon_true_dependence should be never called. */
2232 if (spill_alias_set
)
2233 mem_addr
= NULL_RTX
;
2237 mem_addr
= base
->val_rtx
;
2241 = rtx_group_vec
[group_id
];
2242 mem_addr
= group
->canon_base_addr
;
2244 /* get_addr can only handle VALUE but cannot handle expr like:
2245 VALUE + OFFSET, so call get_addr to get original addr for
2246 mem_addr before plus_constant. */
2247 mem_addr
= get_addr (mem_addr
);
2249 mem_addr
= plus_constant (get_address_mode (mem
), mem_addr
, offset
);
2252 /* We ignore the clobbers in store_info. The is mildly aggressive,
2253 but there really should not be a clobber followed by a read. */
2255 if (spill_alias_set
)
2257 insn_info_t i_ptr
= active_local_stores
;
2258 insn_info_t last
= NULL
;
2260 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2261 fprintf (dump_file
, " processing spill load %d\n",
2262 (int) spill_alias_set
);
2266 store_info_t store_info
= i_ptr
->store_rec
;
2268 /* Skip the clobbers. */
2269 while (!store_info
->is_set
)
2270 store_info
= store_info
->next
;
2272 if (store_info
->alias_set
== spill_alias_set
)
2274 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2275 dump_insn_info ("removing from active", i_ptr
);
2277 active_local_stores_len
--;
2279 last
->next_local_store
= i_ptr
->next_local_store
;
2281 active_local_stores
= i_ptr
->next_local_store
;
2285 i_ptr
= i_ptr
->next_local_store
;
2288 else if (group_id
>= 0)
2290 /* This is the restricted case where the base is a constant or
2291 the frame pointer and offset is a constant. */
2292 insn_info_t i_ptr
= active_local_stores
;
2293 insn_info_t last
= NULL
;
2295 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2298 fprintf (dump_file
, " processing const load gid=%d[BLK]\n",
2301 fprintf (dump_file
, " processing const load gid=%d[%d..%d)\n",
2302 group_id
, (int)offset
, (int)(offset
+width
));
2307 bool remove
= false;
2308 store_info_t store_info
= i_ptr
->store_rec
;
2310 /* Skip the clobbers. */
2311 while (!store_info
->is_set
)
2312 store_info
= store_info
->next
;
2314 /* There are three cases here. */
2315 if (store_info
->group_id
< 0)
2316 /* We have a cselib store followed by a read from a
2319 = canon_true_dependence (store_info
->mem
,
2320 GET_MODE (store_info
->mem
),
2321 store_info
->mem_addr
,
2324 else if (group_id
== store_info
->group_id
)
2326 /* This is a block mode load. We may get lucky and
2327 canon_true_dependence may save the day. */
2330 = canon_true_dependence (store_info
->mem
,
2331 GET_MODE (store_info
->mem
),
2332 store_info
->mem_addr
,
2335 /* If this read is just reading back something that we just
2336 stored, rewrite the read. */
2340 && offset
>= store_info
->begin
2341 && offset
+ width
<= store_info
->end
2342 && all_positions_needed_p (store_info
,
2343 offset
- store_info
->begin
,
2345 && replace_read (store_info
, i_ptr
, read_info
,
2346 insn_info
, loc
, bb_info
->regs_live
))
2349 /* The bases are the same, just see if the offsets
2351 if ((offset
< store_info
->end
)
2352 && (offset
+ width
> store_info
->begin
))
2358 The else case that is missing here is that the
2359 bases are constant but different. There is nothing
2360 to do here because there is no overlap. */
2364 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2365 dump_insn_info ("removing from active", i_ptr
);
2367 active_local_stores_len
--;
2369 last
->next_local_store
= i_ptr
->next_local_store
;
2371 active_local_stores
= i_ptr
->next_local_store
;
2375 i_ptr
= i_ptr
->next_local_store
;
2380 insn_info_t i_ptr
= active_local_stores
;
2381 insn_info_t last
= NULL
;
2382 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2384 fprintf (dump_file
, " processing cselib load mem:");
2385 print_inline_rtx (dump_file
, mem
, 0);
2386 fprintf (dump_file
, "\n");
2391 bool remove
= false;
2392 store_info_t store_info
= i_ptr
->store_rec
;
2394 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2395 fprintf (dump_file
, " processing cselib load against insn %d\n",
2396 INSN_UID (i_ptr
->insn
));
2398 /* Skip the clobbers. */
2399 while (!store_info
->is_set
)
2400 store_info
= store_info
->next
;
2402 /* If this read is just reading back something that we just
2403 stored, rewrite the read. */
2405 && store_info
->group_id
== -1
2406 && store_info
->cse_base
== base
2408 && offset
>= store_info
->begin
2409 && offset
+ width
<= store_info
->end
2410 && all_positions_needed_p (store_info
,
2411 offset
- store_info
->begin
, width
)
2412 && replace_read (store_info
, i_ptr
, read_info
, insn_info
, loc
,
2413 bb_info
->regs_live
))
2416 if (!store_info
->alias_set
)
2417 remove
= canon_true_dependence (store_info
->mem
,
2418 GET_MODE (store_info
->mem
),
2419 store_info
->mem_addr
,
2424 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2425 dump_insn_info ("removing from active", i_ptr
);
2427 active_local_stores_len
--;
2429 last
->next_local_store
= i_ptr
->next_local_store
;
2431 active_local_stores
= i_ptr
->next_local_store
;
2435 i_ptr
= i_ptr
->next_local_store
;
2440 /* A note_uses callback in which DATA points the INSN_INFO for
2441 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
2442 true for any part of *LOC. */
2445 check_mem_read_use (rtx
*loc
, void *data
)
2447 subrtx_ptr_iterator::array_type array
;
2448 FOR_EACH_SUBRTX_PTR (iter
, array
, loc
, NONCONST
)
2452 check_mem_read_rtx (loc
, (bb_info_t
) data
);
2457 /* Get arguments passed to CALL_INSN. Return TRUE if successful.
2458 So far it only handles arguments passed in registers. */
2461 get_call_args (rtx call_insn
, tree fn
, rtx
*args
, int nargs
)
2463 CUMULATIVE_ARGS args_so_far_v
;
2464 cumulative_args_t args_so_far
;
2468 INIT_CUMULATIVE_ARGS (args_so_far_v
, TREE_TYPE (fn
), NULL_RTX
, 0, 3);
2469 args_so_far
= pack_cumulative_args (&args_so_far_v
);
2471 arg
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2473 arg
!= void_list_node
&& idx
< nargs
;
2474 arg
= TREE_CHAIN (arg
), idx
++)
2476 machine_mode mode
= TYPE_MODE (TREE_VALUE (arg
));
2478 reg
= targetm
.calls
.function_arg (args_so_far
, mode
, NULL_TREE
, true);
2479 if (!reg
|| !REG_P (reg
) || GET_MODE (reg
) != mode
2480 || GET_MODE_CLASS (mode
) != MODE_INT
)
2483 for (link
= CALL_INSN_FUNCTION_USAGE (call_insn
);
2485 link
= XEXP (link
, 1))
2486 if (GET_CODE (XEXP (link
, 0)) == USE
)
2488 args
[idx
] = XEXP (XEXP (link
, 0), 0);
2489 if (REG_P (args
[idx
])
2490 && REGNO (args
[idx
]) == REGNO (reg
)
2491 && (GET_MODE (args
[idx
]) == mode
2492 || (GET_MODE_CLASS (GET_MODE (args
[idx
])) == MODE_INT
2493 && (GET_MODE_SIZE (GET_MODE (args
[idx
]))
2495 && (GET_MODE_SIZE (GET_MODE (args
[idx
]))
2496 > GET_MODE_SIZE (mode
)))))
2502 tmp
= cselib_expand_value_rtx (args
[idx
], scratch
, 5);
2503 if (GET_MODE (args
[idx
]) != mode
)
2505 if (!tmp
|| !CONST_INT_P (tmp
))
2507 tmp
= gen_int_mode (INTVAL (tmp
), mode
);
2512 targetm
.calls
.function_arg_advance (args_so_far
, mode
, NULL_TREE
, true);
2514 if (arg
!= void_list_node
|| idx
!= nargs
)
2519 /* Return a bitmap of the fixed registers contained in IN. */
2522 copy_fixed_regs (const_bitmap in
)
2526 ret
= ALLOC_REG_SET (NULL
);
2527 bitmap_and (ret
, in
, fixed_reg_set_regset
);
2531 /* Apply record_store to all candidate stores in INSN. Mark INSN
2532 if some part of it is not a candidate store and assigns to a
2533 non-register target. */
2536 scan_insn (bb_info_t bb_info
, rtx_insn
*insn
)
2539 insn_info_type
*insn_info
= new insn_info_type
;
2541 memset (insn_info
, 0, sizeof (struct insn_info_type
));
2543 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2544 fprintf (dump_file
, "\n**scanning insn=%d\n",
2547 insn_info
->prev_insn
= bb_info
->last_insn
;
2548 insn_info
->insn
= insn
;
2549 bb_info
->last_insn
= insn_info
;
2551 if (DEBUG_INSN_P (insn
))
2553 insn_info
->cannot_delete
= true;
2557 /* Look at all of the uses in the insn. */
2558 note_uses (&PATTERN (insn
), check_mem_read_use
, bb_info
);
2563 tree memset_call
= NULL_TREE
;
2565 insn_info
->cannot_delete
= true;
2567 /* Const functions cannot do anything bad i.e. read memory,
2568 however, they can read their parameters which may have
2569 been pushed onto the stack.
2570 memset and bzero don't read memory either. */
2571 const_call
= RTL_CONST_CALL_P (insn
);
2574 rtx call
= get_call_rtx_from (insn
);
2575 if (call
&& GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
2577 rtx symbol
= XEXP (XEXP (call
, 0), 0);
2578 if (SYMBOL_REF_DECL (symbol
)
2579 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
2581 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
2583 && (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
))
2584 == BUILT_IN_MEMSET
))
2585 || SYMBOL_REF_DECL (symbol
) == block_clear_fn
)
2586 memset_call
= SYMBOL_REF_DECL (symbol
);
2590 if (const_call
|| memset_call
)
2592 insn_info_t i_ptr
= active_local_stores
;
2593 insn_info_t last
= NULL
;
2595 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2596 fprintf (dump_file
, "%s call %d\n",
2597 const_call
? "const" : "memset", INSN_UID (insn
));
2599 /* See the head comment of the frame_read field. */
2600 if (reload_completed
2601 /* Tail calls are storing their arguments using
2602 arg pointer. If it is a frame pointer on the target,
2603 even before reload we need to kill frame pointer based
2605 || (SIBLING_CALL_P (insn
)
2606 && HARD_FRAME_POINTER_IS_ARG_POINTER
))
2607 insn_info
->frame_read
= true;
2609 /* Loop over the active stores and remove those which are
2610 killed by the const function call. */
2613 bool remove_store
= false;
2615 /* The stack pointer based stores are always killed. */
2616 if (i_ptr
->stack_pointer_based
)
2617 remove_store
= true;
2619 /* If the frame is read, the frame related stores are killed. */
2620 else if (insn_info
->frame_read
)
2622 store_info_t store_info
= i_ptr
->store_rec
;
2624 /* Skip the clobbers. */
2625 while (!store_info
->is_set
)
2626 store_info
= store_info
->next
;
2628 if (store_info
->group_id
>= 0
2629 && rtx_group_vec
[store_info
->group_id
]->frame_related
)
2630 remove_store
= true;
2635 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2636 dump_insn_info ("removing from active", i_ptr
);
2638 active_local_stores_len
--;
2640 last
->next_local_store
= i_ptr
->next_local_store
;
2642 active_local_stores
= i_ptr
->next_local_store
;
2647 i_ptr
= i_ptr
->next_local_store
;
2653 if (get_call_args (insn
, memset_call
, args
, 3)
2654 && CONST_INT_P (args
[1])
2655 && CONST_INT_P (args
[2])
2656 && INTVAL (args
[2]) > 0)
2658 rtx mem
= gen_rtx_MEM (BLKmode
, args
[0]);
2659 set_mem_size (mem
, INTVAL (args
[2]));
2660 body
= gen_rtx_SET (mem
, args
[1]);
2661 mems_found
+= record_store (body
, bb_info
);
2662 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2663 fprintf (dump_file
, "handling memset as BLKmode store\n");
2664 if (mems_found
== 1)
2666 if (active_local_stores_len
++
2667 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES
))
2669 active_local_stores_len
= 1;
2670 active_local_stores
= NULL
;
2672 insn_info
->fixed_regs_live
2673 = copy_fixed_regs (bb_info
->regs_live
);
2674 insn_info
->next_local_store
= active_local_stores
;
2675 active_local_stores
= insn_info
;
2680 else if (SIBLING_CALL_P (insn
) && reload_completed
)
2681 /* Arguments for a sibling call that are pushed to memory are passed
2682 using the incoming argument pointer of the current function. After
2683 reload that might be (and likely is) frame pointer based. */
2684 add_wild_read (bb_info
);
2686 /* Every other call, including pure functions, may read any memory
2687 that is not relative to the frame. */
2688 add_non_frame_wild_read (bb_info
);
2693 /* Assuming that there are sets in these insns, we cannot delete
2695 if ((GET_CODE (PATTERN (insn
)) == CLOBBER
)
2696 || volatile_refs_p (PATTERN (insn
))
2697 || (!cfun
->can_delete_dead_exceptions
&& !insn_nothrow_p (insn
))
2698 || (RTX_FRAME_RELATED_P (insn
))
2699 || find_reg_note (insn
, REG_FRAME_RELATED_EXPR
, NULL_RTX
))
2700 insn_info
->cannot_delete
= true;
2702 body
= PATTERN (insn
);
2703 if (GET_CODE (body
) == PARALLEL
)
2706 for (i
= 0; i
< XVECLEN (body
, 0); i
++)
2707 mems_found
+= record_store (XVECEXP (body
, 0, i
), bb_info
);
2710 mems_found
+= record_store (body
, bb_info
);
2712 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2713 fprintf (dump_file
, "mems_found = %d, cannot_delete = %s\n",
2714 mems_found
, insn_info
->cannot_delete
? "true" : "false");
2716 /* If we found some sets of mems, add it into the active_local_stores so
2717 that it can be locally deleted if found dead or used for
2718 replace_read and redundant constant store elimination. Otherwise mark
2719 it as cannot delete. This simplifies the processing later. */
2720 if (mems_found
== 1)
2722 if (active_local_stores_len
++
2723 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES
))
2725 active_local_stores_len
= 1;
2726 active_local_stores
= NULL
;
2728 insn_info
->fixed_regs_live
= copy_fixed_regs (bb_info
->regs_live
);
2729 insn_info
->next_local_store
= active_local_stores
;
2730 active_local_stores
= insn_info
;
2733 insn_info
->cannot_delete
= true;
2737 /* Remove BASE from the set of active_local_stores. This is a
2738 callback from cselib that is used to get rid of the stores in
2739 active_local_stores. */
2742 remove_useless_values (cselib_val
*base
)
2744 insn_info_t insn_info
= active_local_stores
;
2745 insn_info_t last
= NULL
;
2749 store_info_t store_info
= insn_info
->store_rec
;
2752 /* If ANY of the store_infos match the cselib group that is
2753 being deleted, then the insn can not be deleted. */
2756 if ((store_info
->group_id
== -1)
2757 && (store_info
->cse_base
== base
))
2762 store_info
= store_info
->next
;
2767 active_local_stores_len
--;
2769 last
->next_local_store
= insn_info
->next_local_store
;
2771 active_local_stores
= insn_info
->next_local_store
;
2772 free_store_info (insn_info
);
2777 insn_info
= insn_info
->next_local_store
;
2782 /* Do all of step 1. */
2788 bitmap regs_live
= BITMAP_ALLOC (®_obstack
);
2791 all_blocks
= BITMAP_ALLOC (NULL
);
2792 bitmap_set_bit (all_blocks
, ENTRY_BLOCK
);
2793 bitmap_set_bit (all_blocks
, EXIT_BLOCK
);
2795 FOR_ALL_BB_FN (bb
, cfun
)
2798 bb_info_t bb_info
= new dse_bb_info_type
;
2800 memset (bb_info
, 0, sizeof (dse_bb_info_type
));
2801 bitmap_set_bit (all_blocks
, bb
->index
);
2802 bb_info
->regs_live
= regs_live
;
2804 bitmap_copy (regs_live
, DF_LR_IN (bb
));
2805 df_simulate_initialize_forwards (bb
, regs_live
);
2807 bb_table
[bb
->index
] = bb_info
;
2808 cselib_discard_hook
= remove_useless_values
;
2810 if (bb
->index
>= NUM_FIXED_BLOCKS
)
2814 active_local_stores
= NULL
;
2815 active_local_stores_len
= 0;
2816 cselib_clear_table ();
2818 /* Scan the insns. */
2819 FOR_BB_INSNS (bb
, insn
)
2822 scan_insn (bb_info
, insn
);
2823 cselib_process_insn (insn
);
2825 df_simulate_one_insn_forwards (bb
, insn
, regs_live
);
2828 /* This is something of a hack, because the global algorithm
2829 is supposed to take care of the case where stores go dead
2830 at the end of the function. However, the global
2831 algorithm must take a more conservative view of block
2832 mode reads than the local alg does. So to get the case
2833 where you have a store to the frame followed by a non
2834 overlapping block more read, we look at the active local
2835 stores at the end of the function and delete all of the
2836 frame and spill based ones. */
2837 if (stores_off_frame_dead_at_return
2838 && (EDGE_COUNT (bb
->succs
) == 0
2839 || (single_succ_p (bb
)
2840 && single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
2841 && ! crtl
->calls_eh_return
)))
2843 insn_info_t i_ptr
= active_local_stores
;
2846 store_info_t store_info
= i_ptr
->store_rec
;
2848 /* Skip the clobbers. */
2849 while (!store_info
->is_set
)
2850 store_info
= store_info
->next
;
2851 if (store_info
->alias_set
&& !i_ptr
->cannot_delete
)
2852 delete_dead_store_insn (i_ptr
);
2854 if (store_info
->group_id
>= 0)
2857 = rtx_group_vec
[store_info
->group_id
];
2858 if (group
->frame_related
&& !i_ptr
->cannot_delete
)
2859 delete_dead_store_insn (i_ptr
);
2862 i_ptr
= i_ptr
->next_local_store
;
2866 /* Get rid of the loads that were discovered in
2867 replace_read. Cselib is finished with this block. */
2868 while (deferred_change_list
)
2870 deferred_change_t next
= deferred_change_list
->next
;
2872 /* There is no reason to validate this change. That was
2874 *deferred_change_list
->loc
= deferred_change_list
->reg
;
2875 delete deferred_change_list
;
2876 deferred_change_list
= next
;
2879 /* Get rid of all of the cselib based store_infos in this
2880 block and mark the containing insns as not being
2882 ptr
= bb_info
->last_insn
;
2885 if (ptr
->contains_cselib_groups
)
2887 store_info_t s_info
= ptr
->store_rec
;
2888 while (s_info
&& !s_info
->is_set
)
2889 s_info
= s_info
->next
;
2891 && s_info
->redundant_reason
2892 && s_info
->redundant_reason
->insn
2893 && !ptr
->cannot_delete
)
2895 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2896 fprintf (dump_file
, "Locally deleting insn %d "
2897 "because insn %d stores the "
2898 "same value and couldn't be "
2900 INSN_UID (ptr
->insn
),
2901 INSN_UID (s_info
->redundant_reason
->insn
));
2902 delete_dead_store_insn (ptr
);
2904 free_store_info (ptr
);
2908 store_info_t s_info
;
2910 /* Free at least positions_needed bitmaps. */
2911 for (s_info
= ptr
->store_rec
; s_info
; s_info
= s_info
->next
)
2912 if (s_info
->is_large
)
2914 BITMAP_FREE (s_info
->positions_needed
.large
.bmap
);
2915 s_info
->is_large
= false;
2918 ptr
= ptr
->prev_insn
;
2921 cse_store_info_pool
.release ();
2923 bb_info
->regs_live
= NULL
;
2926 BITMAP_FREE (regs_live
);
2928 rtx_group_table
->empty ();
2932 /*----------------------------------------------------------------------------
2935 Assign each byte position in the stores that we are going to
2936 analyze globally to a position in the bitmaps. Returns true if
2937 there are any bit positions assigned.
2938 ----------------------------------------------------------------------------*/
2941 dse_step2_init (void)
2946 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
2948 /* For all non stack related bases, we only consider a store to
2949 be deletable if there are two or more stores for that
2950 position. This is because it takes one store to make the
2951 other store redundant. However, for the stores that are
2952 stack related, we consider them if there is only one store
2953 for the position. We do this because the stack related
2954 stores can be deleted if their is no read between them and
2955 the end of the function.
2957 To make this work in the current framework, we take the stack
2958 related bases add all of the bits from store1 into store2.
2959 This has the effect of making the eligible even if there is
2962 if (stores_off_frame_dead_at_return
&& group
->frame_related
)
2964 bitmap_ior_into (group
->store2_n
, group
->store1_n
);
2965 bitmap_ior_into (group
->store2_p
, group
->store1_p
);
2966 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2967 fprintf (dump_file
, "group %d is frame related ", i
);
2970 group
->offset_map_size_n
++;
2971 group
->offset_map_n
= XOBNEWVEC (&dse_obstack
, int,
2972 group
->offset_map_size_n
);
2973 group
->offset_map_size_p
++;
2974 group
->offset_map_p
= XOBNEWVEC (&dse_obstack
, int,
2975 group
->offset_map_size_p
);
2976 group
->process_globally
= false;
2977 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2979 fprintf (dump_file
, "group %d(%d+%d): ", i
,
2980 (int)bitmap_count_bits (group
->store2_n
),
2981 (int)bitmap_count_bits (group
->store2_p
));
2982 bitmap_print (dump_file
, group
->store2_n
, "n ", " ");
2983 bitmap_print (dump_file
, group
->store2_p
, "p ", "\n");
2989 /* Init the offset tables for the normal case. */
2992 dse_step2_nospill (void)
2996 /* Position 0 is unused because 0 is used in the maps to mean
2998 current_position
= 1;
2999 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3004 if (group
== clear_alias_group
)
3007 memset (group
->offset_map_n
, 0, sizeof (int) * group
->offset_map_size_n
);
3008 memset (group
->offset_map_p
, 0, sizeof (int) * group
->offset_map_size_p
);
3009 bitmap_clear (group
->group_kill
);
3011 EXECUTE_IF_SET_IN_BITMAP (group
->store2_n
, 0, j
, bi
)
3013 bitmap_set_bit (group
->group_kill
, current_position
);
3014 if (bitmap_bit_p (group
->escaped_n
, j
))
3015 bitmap_set_bit (kill_on_calls
, current_position
);
3016 group
->offset_map_n
[j
] = current_position
++;
3017 group
->process_globally
= true;
3019 EXECUTE_IF_SET_IN_BITMAP (group
->store2_p
, 0, j
, bi
)
3021 bitmap_set_bit (group
->group_kill
, current_position
);
3022 if (bitmap_bit_p (group
->escaped_p
, j
))
3023 bitmap_set_bit (kill_on_calls
, current_position
);
3024 group
->offset_map_p
[j
] = current_position
++;
3025 group
->process_globally
= true;
3028 return current_position
!= 1;
3033 /*----------------------------------------------------------------------------
3036 Build the bit vectors for the transfer functions.
3037 ----------------------------------------------------------------------------*/
3040 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
3044 get_bitmap_index (group_info_t group_info
, HOST_WIDE_INT offset
)
3048 HOST_WIDE_INT offset_p
= -offset
;
3049 if (offset_p
>= group_info
->offset_map_size_n
)
3051 return group_info
->offset_map_n
[offset_p
];
3055 if (offset
>= group_info
->offset_map_size_p
)
3057 return group_info
->offset_map_p
[offset
];
3062 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3066 scan_stores_nospill (store_info_t store_info
, bitmap gen
, bitmap kill
)
3071 group_info_t group_info
3072 = rtx_group_vec
[store_info
->group_id
];
3073 if (group_info
->process_globally
)
3074 for (i
= store_info
->begin
; i
< store_info
->end
; i
++)
3076 int index
= get_bitmap_index (group_info
, i
);
3079 bitmap_set_bit (gen
, index
);
3081 bitmap_clear_bit (kill
, index
);
3084 store_info
= store_info
->next
;
3089 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3093 scan_stores_spill (store_info_t store_info
, bitmap gen
, bitmap kill
)
3097 if (store_info
->alias_set
)
3099 int index
= get_bitmap_index (clear_alias_group
,
3100 store_info
->alias_set
);
3103 bitmap_set_bit (gen
, index
);
3105 bitmap_clear_bit (kill
, index
);
3108 store_info
= store_info
->next
;
3113 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3117 scan_reads_nospill (insn_info_t insn_info
, bitmap gen
, bitmap kill
)
3119 read_info_t read_info
= insn_info
->read_rec
;
3123 /* If this insn reads the frame, kill all the frame related stores. */
3124 if (insn_info
->frame_read
)
3126 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3127 if (group
->process_globally
&& group
->frame_related
)
3130 bitmap_ior_into (kill
, group
->group_kill
);
3131 bitmap_and_compl_into (gen
, group
->group_kill
);
3134 if (insn_info
->non_frame_wild_read
)
3136 /* Kill all non-frame related stores. Kill all stores of variables that
3139 bitmap_ior_into (kill
, kill_on_calls
);
3140 bitmap_and_compl_into (gen
, kill_on_calls
);
3141 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3142 if (group
->process_globally
&& !group
->frame_related
)
3145 bitmap_ior_into (kill
, group
->group_kill
);
3146 bitmap_and_compl_into (gen
, group
->group_kill
);
3151 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3153 if (group
->process_globally
)
3155 if (i
== read_info
->group_id
)
3157 if (read_info
->begin
> read_info
->end
)
3159 /* Begin > end for block mode reads. */
3161 bitmap_ior_into (kill
, group
->group_kill
);
3162 bitmap_and_compl_into (gen
, group
->group_kill
);
3166 /* The groups are the same, just process the
3169 for (j
= read_info
->begin
; j
< read_info
->end
; j
++)
3171 int index
= get_bitmap_index (group
, j
);
3175 bitmap_set_bit (kill
, index
);
3176 bitmap_clear_bit (gen
, index
);
3183 /* The groups are different, if the alias sets
3184 conflict, clear the entire group. We only need
3185 to apply this test if the read_info is a cselib
3186 read. Anything with a constant base cannot alias
3187 something else with a different constant
3189 if ((read_info
->group_id
< 0)
3190 && canon_true_dependence (group
->base_mem
,
3191 GET_MODE (group
->base_mem
),
3192 group
->canon_base_addr
,
3193 read_info
->mem
, NULL_RTX
))
3196 bitmap_ior_into (kill
, group
->group_kill
);
3197 bitmap_and_compl_into (gen
, group
->group_kill
);
3203 read_info
= read_info
->next
;
3207 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3211 scan_reads_spill (read_info_t read_info
, bitmap gen
, bitmap kill
)
3215 if (read_info
->alias_set
)
3217 int index
= get_bitmap_index (clear_alias_group
,
3218 read_info
->alias_set
);
3222 bitmap_set_bit (kill
, index
);
3223 bitmap_clear_bit (gen
, index
);
3227 read_info
= read_info
->next
;
3232 /* Return the insn in BB_INFO before the first wild read or if there
3233 are no wild reads in the block, return the last insn. */
3236 find_insn_before_first_wild_read (bb_info_t bb_info
)
3238 insn_info_t insn_info
= bb_info
->last_insn
;
3239 insn_info_t last_wild_read
= NULL
;
3243 if (insn_info
->wild_read
)
3245 last_wild_read
= insn_info
->prev_insn
;
3246 /* Block starts with wild read. */
3247 if (!last_wild_read
)
3251 insn_info
= insn_info
->prev_insn
;
3255 return last_wild_read
;
3257 return bb_info
->last_insn
;
3261 /* Scan the insns in BB_INFO starting at PTR and going to the top of
3262 the block in order to build the gen and kill sets for the block.
3263 We start at ptr which may be the last insn in the block or may be
3264 the first insn with a wild read. In the latter case we are able to
3265 skip the rest of the block because it just does not matter:
3266 anything that happens is hidden by the wild read. */
3269 dse_step3_scan (bool for_spills
, basic_block bb
)
3271 bb_info_t bb_info
= bb_table
[bb
->index
];
3272 insn_info_t insn_info
;
3275 /* There are no wild reads in the spill case. */
3276 insn_info
= bb_info
->last_insn
;
3278 insn_info
= find_insn_before_first_wild_read (bb_info
);
3280 /* In the spill case or in the no_spill case if there is no wild
3281 read in the block, we will need a kill set. */
3282 if (insn_info
== bb_info
->last_insn
)
3285 bitmap_clear (bb_info
->kill
);
3287 bb_info
->kill
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3291 BITMAP_FREE (bb_info
->kill
);
3295 /* There may have been code deleted by the dce pass run before
3297 if (insn_info
->insn
&& INSN_P (insn_info
->insn
))
3299 /* Process the read(s) last. */
3302 scan_stores_spill (insn_info
->store_rec
, bb_info
->gen
, bb_info
->kill
);
3303 scan_reads_spill (insn_info
->read_rec
, bb_info
->gen
, bb_info
->kill
);
3307 scan_stores_nospill (insn_info
->store_rec
, bb_info
->gen
, bb_info
->kill
);
3308 scan_reads_nospill (insn_info
, bb_info
->gen
, bb_info
->kill
);
3312 insn_info
= insn_info
->prev_insn
;
3317 /* Set the gen set of the exit block, and also any block with no
3318 successors that does not have a wild read. */
3321 dse_step3_exit_block_scan (bb_info_t bb_info
)
3323 /* The gen set is all 0's for the exit block except for the
3324 frame_pointer_group. */
3326 if (stores_off_frame_dead_at_return
)
3331 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3333 if (group
->process_globally
&& group
->frame_related
)
3334 bitmap_ior_into (bb_info
->gen
, group
->group_kill
);
3340 /* Find all of the blocks that are not backwards reachable from the
3341 exit block or any block with no successors (BB). These are the
3342 infinite loops or infinite self loops. These blocks will still
3343 have their bits set in UNREACHABLE_BLOCKS. */
3346 mark_reachable_blocks (sbitmap unreachable_blocks
, basic_block bb
)
3351 if (bitmap_bit_p (unreachable_blocks
, bb
->index
))
3353 bitmap_clear_bit (unreachable_blocks
, bb
->index
);
3354 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3356 mark_reachable_blocks (unreachable_blocks
, e
->src
);
3361 /* Build the transfer functions for the function. */
3364 dse_step3 (bool for_spills
)
3367 sbitmap unreachable_blocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
3368 sbitmap_iterator sbi
;
3369 bitmap all_ones
= NULL
;
3372 bitmap_ones (unreachable_blocks
);
3374 FOR_ALL_BB_FN (bb
, cfun
)
3376 bb_info_t bb_info
= bb_table
[bb
->index
];
3378 bitmap_clear (bb_info
->gen
);
3380 bb_info
->gen
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3382 if (bb
->index
== ENTRY_BLOCK
)
3384 else if (bb
->index
== EXIT_BLOCK
)
3385 dse_step3_exit_block_scan (bb_info
);
3387 dse_step3_scan (for_spills
, bb
);
3388 if (EDGE_COUNT (bb
->succs
) == 0)
3389 mark_reachable_blocks (unreachable_blocks
, bb
);
3391 /* If this is the second time dataflow is run, delete the old
3394 BITMAP_FREE (bb_info
->in
);
3396 BITMAP_FREE (bb_info
->out
);
3399 /* For any block in an infinite loop, we must initialize the out set
3400 to all ones. This could be expensive, but almost never occurs in
3401 practice. However, it is common in regression tests. */
3402 EXECUTE_IF_SET_IN_BITMAP (unreachable_blocks
, 0, i
, sbi
)
3404 if (bitmap_bit_p (all_blocks
, i
))
3406 bb_info_t bb_info
= bb_table
[i
];
3412 all_ones
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3413 FOR_EACH_VEC_ELT (rtx_group_vec
, j
, group
)
3414 bitmap_ior_into (all_ones
, group
->group_kill
);
3418 bb_info
->out
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3419 bitmap_copy (bb_info
->out
, all_ones
);
3425 BITMAP_FREE (all_ones
);
3426 sbitmap_free (unreachable_blocks
);
3431 /*----------------------------------------------------------------------------
3434 Solve the bitvector equations.
3435 ----------------------------------------------------------------------------*/
3438 /* Confluence function for blocks with no successors. Create an out
3439 set from the gen set of the exit block. This block logically has
3440 the exit block as a successor. */
3445 dse_confluence_0 (basic_block bb
)
3447 bb_info_t bb_info
= bb_table
[bb
->index
];
3449 if (bb
->index
== EXIT_BLOCK
)
3454 bb_info
->out
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3455 bitmap_copy (bb_info
->out
, bb_table
[EXIT_BLOCK
]->gen
);
3459 /* Propagate the information from the in set of the dest of E to the
3460 out set of the src of E. If the various in or out sets are not
3461 there, that means they are all ones. */
3464 dse_confluence_n (edge e
)
3466 bb_info_t src_info
= bb_table
[e
->src
->index
];
3467 bb_info_t dest_info
= bb_table
[e
->dest
->index
];
3472 bitmap_and_into (src_info
->out
, dest_info
->in
);
3475 src_info
->out
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3476 bitmap_copy (src_info
->out
, dest_info
->in
);
3483 /* Propagate the info from the out to the in set of BB_INDEX's basic
3484 block. There are three cases:
3486 1) The block has no kill set. In this case the kill set is all
3487 ones. It does not matter what the out set of the block is, none of
3488 the info can reach the top. The only thing that reaches the top is
3489 the gen set and we just copy the set.
3491 2) There is a kill set but no out set and bb has successors. In
3492 this case we just return. Eventually an out set will be created and
3493 it is better to wait than to create a set of ones.
3495 3) There is both a kill and out set. We apply the obvious transfer
3500 dse_transfer_function (int bb_index
)
3502 bb_info_t bb_info
= bb_table
[bb_index
];
3510 return bitmap_ior_and_compl (bb_info
->in
, bb_info
->gen
,
3511 bb_info
->out
, bb_info
->kill
);
3514 bb_info
->in
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3515 bitmap_ior_and_compl (bb_info
->in
, bb_info
->gen
,
3516 bb_info
->out
, bb_info
->kill
);
3526 /* Case 1 above. If there is already an in set, nothing
3532 bb_info
->in
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3533 bitmap_copy (bb_info
->in
, bb_info
->gen
);
3539 /* Solve the dataflow equations. */
3544 df_simple_dataflow (DF_BACKWARD
, NULL
, dse_confluence_0
,
3545 dse_confluence_n
, dse_transfer_function
,
3546 all_blocks
, df_get_postorder (DF_BACKWARD
),
3547 df_get_n_blocks (DF_BACKWARD
));
3548 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3552 fprintf (dump_file
, "\n\n*** Global dataflow info after analysis.\n");
3553 FOR_ALL_BB_FN (bb
, cfun
)
3555 bb_info_t bb_info
= bb_table
[bb
->index
];
3557 df_print_bb_index (bb
, dump_file
);
3559 bitmap_print (dump_file
, bb_info
->in
, " in: ", "\n");
3561 fprintf (dump_file
, " in: *MISSING*\n");
3563 bitmap_print (dump_file
, bb_info
->gen
, " gen: ", "\n");
3565 fprintf (dump_file
, " gen: *MISSING*\n");
3567 bitmap_print (dump_file
, bb_info
->kill
, " kill: ", "\n");
3569 fprintf (dump_file
, " kill: *MISSING*\n");
3571 bitmap_print (dump_file
, bb_info
->out
, " out: ", "\n");
3573 fprintf (dump_file
, " out: *MISSING*\n\n");
3580 /*----------------------------------------------------------------------------
3583 Delete the stores that can only be deleted using the global information.
3584 ----------------------------------------------------------------------------*/
3588 dse_step5_nospill (void)
3591 FOR_EACH_BB_FN (bb
, cfun
)
3593 bb_info_t bb_info
= bb_table
[bb
->index
];
3594 insn_info_t insn_info
= bb_info
->last_insn
;
3595 bitmap v
= bb_info
->out
;
3599 bool deleted
= false;
3600 if (dump_file
&& insn_info
->insn
)
3602 fprintf (dump_file
, "starting to process insn %d\n",
3603 INSN_UID (insn_info
->insn
));
3604 bitmap_print (dump_file
, v
, " v: ", "\n");
3607 /* There may have been code deleted by the dce pass run before
3610 && INSN_P (insn_info
->insn
)
3611 && (!insn_info
->cannot_delete
)
3612 && (!bitmap_empty_p (v
)))
3614 store_info_t store_info
= insn_info
->store_rec
;
3616 /* Try to delete the current insn. */
3619 /* Skip the clobbers. */
3620 while (!store_info
->is_set
)
3621 store_info
= store_info
->next
;
3623 if (store_info
->alias_set
)
3628 group_info_t group_info
3629 = rtx_group_vec
[store_info
->group_id
];
3631 for (i
= store_info
->begin
; i
< store_info
->end
; i
++)
3633 int index
= get_bitmap_index (group_info
, i
);
3635 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3636 fprintf (dump_file
, "i = %d, index = %d\n", (int)i
, index
);
3637 if (index
== 0 || !bitmap_bit_p (v
, index
))
3639 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3640 fprintf (dump_file
, "failing at i = %d\n", (int)i
);
3649 && check_for_inc_dec_1 (insn_info
))
3651 delete_insn (insn_info
->insn
);
3652 insn_info
->insn
= NULL
;
3657 /* We do want to process the local info if the insn was
3658 deleted. For instance, if the insn did a wild read, we
3659 no longer need to trash the info. */
3661 && INSN_P (insn_info
->insn
)
3664 scan_stores_nospill (insn_info
->store_rec
, v
, NULL
);
3665 if (insn_info
->wild_read
)
3667 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3668 fprintf (dump_file
, "wild read\n");
3671 else if (insn_info
->read_rec
3672 || insn_info
->non_frame_wild_read
)
3674 if (dump_file
&& !insn_info
->non_frame_wild_read
)
3675 fprintf (dump_file
, "regular read\n");
3676 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3677 fprintf (dump_file
, "non-frame wild read\n");
3678 scan_reads_nospill (insn_info
, v
, NULL
);
3682 insn_info
= insn_info
->prev_insn
;
3689 /*----------------------------------------------------------------------------
3692 Delete stores made redundant by earlier stores (which store the same
3693 value) that couldn't be eliminated.
3694 ----------------------------------------------------------------------------*/
3701 FOR_ALL_BB_FN (bb
, cfun
)
3703 bb_info_t bb_info
= bb_table
[bb
->index
];
3704 insn_info_t insn_info
= bb_info
->last_insn
;
3708 /* There may have been code deleted by the dce pass run before
3711 && INSN_P (insn_info
->insn
)
3712 && !insn_info
->cannot_delete
)
3714 store_info_t s_info
= insn_info
->store_rec
;
3716 while (s_info
&& !s_info
->is_set
)
3717 s_info
= s_info
->next
;
3719 && s_info
->redundant_reason
3720 && s_info
->redundant_reason
->insn
3721 && INSN_P (s_info
->redundant_reason
->insn
))
3723 rtx_insn
*rinsn
= s_info
->redundant_reason
->insn
;
3724 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3725 fprintf (dump_file
, "Locally deleting insn %d "
3726 "because insn %d stores the "
3727 "same value and couldn't be "
3729 INSN_UID (insn_info
->insn
),
3731 delete_dead_store_insn (insn_info
);
3734 insn_info
= insn_info
->prev_insn
;
3739 /*----------------------------------------------------------------------------
3742 Destroy everything left standing.
3743 ----------------------------------------------------------------------------*/
3748 bitmap_obstack_release (&dse_bitmap_obstack
);
3749 obstack_free (&dse_obstack
, NULL
);
3751 end_alias_analysis ();
3753 delete rtx_group_table
;
3754 rtx_group_table
= NULL
;
3755 rtx_group_vec
.release ();
3756 BITMAP_FREE (all_blocks
);
3757 BITMAP_FREE (scratch
);
3759 rtx_store_info_pool
.release ();
3760 read_info_type::pool
.release ();
3761 insn_info_type::pool
.release ();
3762 dse_bb_info_type::pool
.release ();
3763 group_info::pool
.release ();
3764 deferred_change::pool
.release ();
3768 /* -------------------------------------------------------------------------
3770 ------------------------------------------------------------------------- */
3772 /* Callback for running pass_rtl_dse. */
3775 rest_of_handle_dse (void)
3777 df_set_flags (DF_DEFER_INSN_RESCAN
);
3779 /* Need the notes since we must track live hardregs in the forwards
3781 df_note_add_problem ();
3787 if (dse_step2_nospill ())
3789 df_set_flags (DF_LR_RUN_DCE
);
3791 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3792 fprintf (dump_file
, "doing global processing\n");
3795 dse_step5_nospill ();
3802 fprintf (dump_file
, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3803 locally_deleted
, globally_deleted
, spill_deleted
);
3805 /* DSE can eliminate potentially-trapping MEMs.
3806 Remove any EH edges associated with them. */
3807 if ((locally_deleted
|| globally_deleted
)
3808 && cfun
->can_throw_non_call_exceptions
3809 && purge_all_dead_edges ())
3817 const pass_data pass_data_rtl_dse1
=
3819 RTL_PASS
, /* type */
3821 OPTGROUP_NONE
, /* optinfo_flags */
3822 TV_DSE1
, /* tv_id */
3823 0, /* properties_required */
3824 0, /* properties_provided */
3825 0, /* properties_destroyed */
3826 0, /* todo_flags_start */
3827 TODO_df_finish
, /* todo_flags_finish */
3830 class pass_rtl_dse1
: public rtl_opt_pass
3833 pass_rtl_dse1 (gcc::context
*ctxt
)
3834 : rtl_opt_pass (pass_data_rtl_dse1
, ctxt
)
3837 /* opt_pass methods: */
3838 virtual bool gate (function
*)
3840 return optimize
> 0 && flag_dse
&& dbg_cnt (dse1
);
3843 virtual unsigned int execute (function
*) { return rest_of_handle_dse (); }
3845 }; // class pass_rtl_dse1
3850 make_pass_rtl_dse1 (gcc::context
*ctxt
)
3852 return new pass_rtl_dse1 (ctxt
);
3857 const pass_data pass_data_rtl_dse2
=
3859 RTL_PASS
, /* type */
3861 OPTGROUP_NONE
, /* optinfo_flags */
3862 TV_DSE2
, /* tv_id */
3863 0, /* properties_required */
3864 0, /* properties_provided */
3865 0, /* properties_destroyed */
3866 0, /* todo_flags_start */
3867 TODO_df_finish
, /* todo_flags_finish */
3870 class pass_rtl_dse2
: public rtl_opt_pass
3873 pass_rtl_dse2 (gcc::context
*ctxt
)
3874 : rtl_opt_pass (pass_data_rtl_dse2
, ctxt
)
3877 /* opt_pass methods: */
3878 virtual bool gate (function
*)
3880 return optimize
> 0 && flag_dse
&& dbg_cnt (dse2
);
3883 virtual unsigned int execute (function
*) { return rest_of_handle_dse (); }
3885 }; // class pass_rtl_dse2
3890 make_pass_rtl_dse2 (gcc::context
*ctxt
)
3892 return new pass_rtl_dse2 (ctxt
);