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"
34 #include "double-int.h"
42 #include "fold-const.h"
43 #include "stor-layout.h"
46 #include "hard-reg-set.h"
49 #include "dominance.h"
53 #include "basic-block.h"
56 #include "tree-pass.h"
57 #include "alloc-pool.h"
58 #include "insn-config.h"
61 #include "statistics.h"
62 #include "fixed-value.h"
72 #include "insn-codes.h"
77 #include "tree-ssa-alias.h"
78 #include "internal-fn.h"
79 #include "gimple-expr.h"
82 #include "gimple-ssa.h"
84 #include "cfgcleanup.h"
86 /* This file contains three techniques for performing Dead Store
89 * The first technique performs dse locally on any base address. It
90 is based on the cselib which is a local value numbering technique.
91 This technique is local to a basic block but deals with a fairly
94 * The second technique performs dse globally but is restricted to
95 base addresses that are either constant or are relative to the
98 * The third technique, (which is only done after register allocation)
99 processes the spill spill slots. This differs from the second
100 technique because it takes advantage of the fact that spilling is
101 completely free from the effects of aliasing.
103 Logically, dse is a backwards dataflow problem. A store can be
104 deleted if it if cannot be reached in the backward direction by any
105 use of the value being stored. However, the local technique uses a
106 forwards scan of the basic block because cselib requires that the
107 block be processed in that order.
109 The pass is logically broken into 7 steps:
113 1) The local algorithm, as well as scanning the insns for the two
116 2) Analysis to see if the global algs are necessary. In the case
117 of stores base on a constant address, there must be at least two
118 stores to that address, to make it possible to delete some of the
119 stores. In the case of stores off of the frame or spill related
120 stores, only one store to an address is necessary because those
121 stores die at the end of the function.
123 3) Set up the global dataflow equations based on processing the
124 info parsed in the first step.
126 4) Solve the dataflow equations.
128 5) Delete the insns that the global analysis has indicated are
131 6) Delete insns that store the same value as preceding store
132 where the earlier store couldn't be eliminated.
136 This step uses cselib and canon_rtx to build the largest expression
137 possible for each address. This pass is a forwards pass through
138 each basic block. From the point of view of the global technique,
139 the first pass could examine a block in either direction. The
140 forwards ordering is to accommodate cselib.
142 We make a simplifying assumption: addresses fall into four broad
145 1) base has rtx_varies_p == false, offset is constant.
146 2) base has rtx_varies_p == false, offset variable.
147 3) base has rtx_varies_p == true, offset constant.
148 4) base has rtx_varies_p == true, offset variable.
150 The local passes are able to process all 4 kinds of addresses. The
151 global pass only handles 1).
153 The global problem is formulated as follows:
155 A store, S1, to address A, where A is not relative to the stack
156 frame, can be eliminated if all paths from S1 to the end of the
157 function contain another store to A before a read to A.
159 If the address A is relative to the stack frame, a store S2 to A
160 can be eliminated if there are no paths from S2 that reach the
161 end of the function that read A before another store to A. In
162 this case S2 can be deleted if there are paths from S2 to the
163 end of the function that have no reads or writes to A. This
164 second case allows stores to the stack frame to be deleted that
165 would otherwise die when the function returns. This cannot be
166 done if stores_off_frame_dead_at_return is not true. See the doc
167 for that variable for when this variable is false.
169 The global problem is formulated as a backwards set union
170 dataflow problem where the stores are the gens and reads are the
171 kills. Set union problems are rare and require some special
172 handling given our representation of bitmaps. A straightforward
173 implementation requires a lot of bitmaps filled with 1s.
174 These are expensive and cumbersome in our bitmap formulation so
175 care has been taken to avoid large vectors filled with 1s. See
176 the comments in bb_info and in the dataflow confluence functions
179 There are two places for further enhancements to this algorithm:
181 1) The original dse which was embedded in a pass called flow also
182 did local address forwarding. For example in
187 flow would replace the right hand side of the second insn with a
188 reference to r100. Most of the information is available to add this
189 to this pass. It has not done it because it is a lot of work in
190 the case that either r100 is assigned to between the first and
191 second insn and/or the second insn is a load of part of the value
192 stored by the first insn.
194 insn 5 in gcc.c-torture/compile/990203-1.c simple case.
195 insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
196 insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
197 insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
199 2) The cleaning up of spill code is quite profitable. It currently
200 depends on reading tea leaves and chicken entrails left by reload.
201 This pass depends on reload creating a singleton alias set for each
202 spill slot and telling the next dse pass which of these alias sets
203 are the singletons. Rather than analyze the addresses of the
204 spills, dse's spill processing just does analysis of the loads and
205 stores that use those alias sets. There are three cases where this
208 a) Reload sometimes creates the slot for one mode of access, and
209 then inserts loads and/or stores for a smaller mode. In this
210 case, the current code just punts on the slot. The proper thing
211 to do is to back out and use one bit vector position for each
212 byte of the entity associated with the slot. This depends on
213 KNOWING that reload always generates the accesses for each of the
214 bytes in some canonical (read that easy to understand several
215 passes after reload happens) way.
217 b) Reload sometimes decides that spill slot it allocated was not
218 large enough for the mode and goes back and allocates more slots
219 with the same mode and alias set. The backout in this case is a
220 little more graceful than (a). In this case the slot is unmarked
221 as being a spill slot and if final address comes out to be based
222 off the frame pointer, the global algorithm handles this slot.
224 c) For any pass that may prespill, there is currently no
225 mechanism to tell the dse pass that the slot being used has the
226 special properties that reload uses. It may be that all that is
227 required is to have those passes make the same calls that reload
228 does, assuming that the alias sets can be manipulated in the same
231 /* There are limits to the size of constant offsets we model for the
232 global problem. There are certainly test cases, that exceed this
233 limit, however, it is unlikely that there are important programs
234 that really have constant offsets this size. */
235 #define MAX_OFFSET (64 * 1024)
237 /* Obstack for the DSE dataflow bitmaps. We don't want to put these
238 on the default obstack because these bitmaps can grow quite large
239 (~2GB for the small (!) test case of PR54146) and we'll hold on to
240 all that memory until the end of the compiler run.
241 As a bonus, delete_tree_live_info can destroy all the bitmaps by just
242 releasing the whole obstack. */
243 static bitmap_obstack dse_bitmap_obstack
;
245 /* Obstack for other data. As for above: Kinda nice to be able to
246 throw it all away at the end in one big sweep. */
247 static struct obstack dse_obstack
;
249 /* Scratch bitmap for cselib's cselib_expand_value_rtx. */
250 static bitmap scratch
= NULL
;
252 struct insn_info_type
;
254 /* This structure holds information about a candidate store. */
258 /* False means this is a clobber. */
261 /* False if a single HOST_WIDE_INT bitmap is used for positions_needed. */
264 /* The id of the mem group of the base address. If rtx_varies_p is
265 true, this is -1. Otherwise, it is the index into the group
269 /* This is the cselib value. */
270 cselib_val
*cse_base
;
272 /* This canonized mem. */
275 /* Canonized MEM address for use by canon_true_dependence. */
278 /* If this is non-zero, it is the alias set of a spill location. */
279 alias_set_type alias_set
;
281 /* The offset of the first and byte before the last byte associated
282 with the operation. */
283 HOST_WIDE_INT begin
, end
;
287 /* A bitmask as wide as the number of bytes in the word that
288 contains a 1 if the byte may be needed. The store is unused if
289 all of the bits are 0. This is used if IS_LARGE is false. */
290 unsigned HOST_WIDE_INT small_bitmask
;
294 /* A bitmap with one bit per byte. Cleared bit means the position
295 is needed. Used if IS_LARGE is false. */
298 /* Number of set bits (i.e. unneeded bytes) in BITMAP. If it is
299 equal to END - BEGIN, the whole store is unused. */
304 /* The next store info for this insn. */
305 struct store_info
*next
;
307 /* The right hand side of the store. This is used if there is a
308 subsequent reload of the mems address somewhere later in the
312 /* If rhs is or holds a constant, this contains that constant,
316 /* Set if this store stores the same constant value as REDUNDANT_REASON
317 insn stored. These aren't eliminated early, because doing that
318 might prevent the earlier larger store to be eliminated. */
319 struct insn_info_type
*redundant_reason
;
322 /* Return a bitmask with the first N low bits set. */
324 static unsigned HOST_WIDE_INT
325 lowpart_bitmask (int n
)
327 unsigned HOST_WIDE_INT mask
= ~(unsigned HOST_WIDE_INT
) 0;
328 return mask
>> (HOST_BITS_PER_WIDE_INT
- n
);
331 typedef struct store_info
*store_info_t
;
332 static pool_allocator
<store_info
> cse_store_info_pool ("cse_store_info_pool",
335 static pool_allocator
<store_info
> rtx_store_info_pool ("rtx_store_info_pool",
338 /* This structure holds information about a load. These are only
339 built for rtx bases. */
340 struct read_info_type
342 /* The id of the mem group of the base address. */
345 /* If this is non-zero, it is the alias set of a spill location. */
346 alias_set_type alias_set
;
348 /* The offset of the first and byte after the last byte associated
349 with the operation. If begin == end == 0, the read did not have
350 a constant offset. */
353 /* The mem being read. */
356 /* The next read_info for this insn. */
357 struct read_info_type
*next
;
359 /* Pool allocation new operator. */
360 inline void *operator new (size_t)
362 return pool
.allocate ();
365 /* Delete operator utilizing pool allocation. */
366 inline void operator delete (void *ptr
)
368 pool
.remove ((read_info_type
*) ptr
);
371 /* Memory allocation pool. */
372 static pool_allocator
<read_info_type
> pool
;
374 typedef struct read_info_type
*read_info_t
;
376 pool_allocator
<read_info_type
> read_info_type::pool ("read_info_pool", 100);
378 /* One of these records is created for each insn. */
380 struct insn_info_type
382 /* Set true if the insn contains a store but the insn itself cannot
383 be deleted. This is set if the insn is a parallel and there is
384 more than one non dead output or if the insn is in some way
388 /* This field is only used by the global algorithm. It is set true
389 if the insn contains any read of mem except for a (1). This is
390 also set if the insn is a call or has a clobber mem. If the insn
391 contains a wild read, the use_rec will be null. */
394 /* This is true only for CALL instructions which could potentially read
395 any non-frame memory location. This field is used by the global
397 bool non_frame_wild_read
;
399 /* This field is only used for the processing of const functions.
400 These functions cannot read memory, but they can read the stack
401 because that is where they may get their parms. We need to be
402 this conservative because, like the store motion pass, we don't
403 consider CALL_INSN_FUNCTION_USAGE when processing call insns.
404 Moreover, we need to distinguish two cases:
405 1. Before reload (register elimination), the stores related to
406 outgoing arguments are stack pointer based and thus deemed
407 of non-constant base in this pass. This requires special
408 handling but also means that the frame pointer based stores
409 need not be killed upon encountering a const function call.
410 2. After reload, the stores related to outgoing arguments can be
411 either stack pointer or hard frame pointer based. This means
412 that we have no other choice than also killing all the frame
413 pointer based stores upon encountering a const function call.
414 This field is set after reload for const function calls and before
415 reload for const tail function calls on targets where arg pointer
416 is the frame pointer. Having this set is less severe than a wild
417 read, it just means that all the frame related stores are killed
418 rather than all the stores. */
421 /* This field is only used for the processing of const functions.
422 It is set if the insn may contain a stack pointer based store. */
423 bool stack_pointer_based
;
425 /* This is true if any of the sets within the store contains a
426 cselib base. Such stores can only be deleted by the local
428 bool contains_cselib_groups
;
433 /* The list of mem sets or mem clobbers that are contained in this
434 insn. If the insn is deletable, it contains only one mem set.
435 But it could also contain clobbers. Insns that contain more than
436 one mem set are not deletable, but each of those mems are here in
437 order to provide info to delete other insns. */
438 store_info_t store_rec
;
440 /* The linked list of mem uses in this insn. Only the reads from
441 rtx bases are listed here. The reads to cselib bases are
442 completely processed during the first scan and so are never
444 read_info_t read_rec
;
446 /* The live fixed registers. We assume only fixed registers can
447 cause trouble by being clobbered from an expanded pattern;
448 storing only the live fixed registers (rather than all registers)
449 means less memory needs to be allocated / copied for the individual
451 regset fixed_regs_live
;
453 /* The prev insn in the basic block. */
454 struct insn_info_type
* prev_insn
;
456 /* The linked list of insns that are in consideration for removal in
457 the forwards pass through the basic block. This pointer may be
458 trash as it is not cleared when a wild read occurs. The only
459 time it is guaranteed to be correct is when the traversal starts
460 at active_local_stores. */
461 struct insn_info_type
* next_local_store
;
463 /* Pool allocation new operator. */
464 inline void *operator new (size_t)
466 return pool
.allocate ();
469 /* Delete operator utilizing pool allocation. */
470 inline void operator delete (void *ptr
)
472 pool
.remove ((insn_info_type
*) ptr
);
475 /* Memory allocation pool. */
476 static pool_allocator
<insn_info_type
> pool
;
478 typedef struct insn_info_type
*insn_info_t
;
480 pool_allocator
<insn_info_type
> insn_info_type::pool ("insn_info_pool", 100);
482 /* The linked list of stores that are under consideration in this
484 static insn_info_t active_local_stores
;
485 static int active_local_stores_len
;
487 struct dse_bb_info_type
489 /* Pointer to the insn info for the last insn in the block. These
490 are linked so this is how all of the insns are reached. During
491 scanning this is the current insn being scanned. */
492 insn_info_t last_insn
;
494 /* The info for the global dataflow problem. */
497 /* This is set if the transfer function should and in the wild_read
498 bitmap before applying the kill and gen sets. That vector knocks
499 out most of the bits in the bitmap and thus speeds up the
501 bool apply_wild_read
;
503 /* The following 4 bitvectors hold information about which positions
504 of which stores are live or dead. They are indexed by
507 /* The set of store positions that exist in this block before a wild read. */
510 /* The set of load positions that exist in this block above the
511 same position of a store. */
514 /* The set of stores that reach the top of the block without being
517 Do not represent the in if it is all ones. Note that this is
518 what the bitvector should logically be initialized to for a set
519 intersection problem. However, like the kill set, this is too
520 expensive. So initially, the in set will only be created for the
521 exit block and any block that contains a wild read. */
524 /* The set of stores that reach the bottom of the block from it's
527 Do not represent the in if it is all ones. Note that this is
528 what the bitvector should logically be initialized to for a set
529 intersection problem. However, like the kill and in set, this is
530 too expensive. So what is done is that the confluence operator
531 just initializes the vector from one of the out sets of the
532 successors of the block. */
535 /* The following bitvector is indexed by the reg number. It
536 contains the set of regs that are live at the current instruction
537 being processed. While it contains info for all of the
538 registers, only the hard registers are actually examined. It is used
539 to assure that shift and/or add sequences that are inserted do not
540 accidentally clobber live hard regs. */
543 /* Pool allocation new operator. */
544 inline void *operator new (size_t)
546 return pool
.allocate ();
549 /* Delete operator utilizing pool allocation. */
550 inline void operator delete (void *ptr
)
552 pool
.remove ((dse_bb_info_type
*) ptr
);
555 /* Memory allocation pool. */
556 static pool_allocator
<dse_bb_info_type
> pool
;
559 typedef struct dse_bb_info_type
*bb_info_t
;
560 pool_allocator
<dse_bb_info_type
> dse_bb_info_type::pool ("bb_info_pool", 100);
562 /* Table to hold all bb_infos. */
563 static bb_info_t
*bb_table
;
565 /* There is a group_info for each rtx base that is used to reference
566 memory. There are also not many of the rtx bases because they are
567 very limited in scope. */
571 /* The actual base of the address. */
574 /* The sequential id of the base. This allows us to have a
575 canonical ordering of these that is not based on addresses. */
578 /* True if there are any positions that are to be processed
580 bool process_globally
;
582 /* True if the base of this group is either the frame_pointer or
583 hard_frame_pointer. */
586 /* A mem wrapped around the base pointer for the group in order to do
587 read dependency. It must be given BLKmode in order to encompass all
588 the possible offsets from the base. */
591 /* Canonized version of base_mem's address. */
594 /* These two sets of two bitmaps are used to keep track of how many
595 stores are actually referencing that position from this base. We
596 only do this for rtx bases as this will be used to assign
597 positions in the bitmaps for the global problem. Bit N is set in
598 store1 on the first store for offset N. Bit N is set in store2
599 for the second store to offset N. This is all we need since we
600 only care about offsets that have two or more stores for them.
602 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
603 for 0 and greater offsets.
605 There is one special case here, for stores into the stack frame,
606 we will or store1 into store2 before deciding which stores look
607 at globally. This is because stores to the stack frame that have
608 no other reads before the end of the function can also be
610 bitmap store1_n
, store1_p
, store2_n
, store2_p
;
612 /* These bitmaps keep track of offsets in this group escape this function.
613 An offset escapes if it corresponds to a named variable whose
614 addressable flag is set. */
615 bitmap escaped_n
, escaped_p
;
617 /* The positions in this bitmap have the same assignments as the in,
618 out, gen and kill bitmaps. This bitmap is all zeros except for
619 the positions that are occupied by stores for this group. */
622 /* The offset_map is used to map the offsets from this base into
623 positions in the global bitmaps. It is only created after all of
624 the all of stores have been scanned and we know which ones we
626 int *offset_map_n
, *offset_map_p
;
627 int offset_map_size_n
, offset_map_size_p
;
629 /* Pool allocation new operator. */
630 inline void *operator new (size_t)
632 return pool
.allocate ();
635 /* Delete operator utilizing pool allocation. */
636 inline void operator delete (void *ptr
)
638 pool
.remove ((group_info
*) ptr
);
641 /* Memory allocation pool. */
642 static pool_allocator
<group_info
> pool
;
644 typedef struct group_info
*group_info_t
;
645 typedef const struct group_info
*const_group_info_t
;
647 pool_allocator
<group_info
> group_info::pool ("rtx_group_info_pool", 100);
649 /* Index into the rtx_group_vec. */
650 static int rtx_group_next_id
;
653 static vec
<group_info_t
> rtx_group_vec
;
656 /* This structure holds the set of changes that are being deferred
657 when removing read operation. See replace_read. */
658 struct deferred_change
661 /* The mem that is being replaced. */
664 /* The reg it is being replaced with. */
667 struct deferred_change
*next
;
669 /* Pool allocation new operator. */
670 inline void *operator new (size_t)
672 return pool
.allocate ();
675 /* Delete operator utilizing pool allocation. */
676 inline void operator delete (void *ptr
)
678 pool
.remove ((deferred_change
*) ptr
);
681 /* Memory allocation pool. */
682 static pool_allocator
<deferred_change
> pool
;
685 typedef struct deferred_change
*deferred_change_t
;
687 pool_allocator
<deferred_change
> deferred_change::pool
688 ("deferred_change_pool", 10);
690 static deferred_change_t deferred_change_list
= NULL
;
692 /* The group that holds all of the clear_alias_sets. */
693 static group_info_t clear_alias_group
;
695 /* The modes of the clear_alias_sets. */
696 static htab_t clear_alias_mode_table
;
698 /* Hash table element to look up the mode for an alias set. */
699 struct clear_alias_mode_holder
701 alias_set_type alias_set
;
705 /* This is true except if cfun->stdarg -- i.e. we cannot do
706 this for vararg functions because they play games with the frame. */
707 static bool stores_off_frame_dead_at_return
;
709 /* Counter for stats. */
710 static int globally_deleted
;
711 static int locally_deleted
;
712 static int spill_deleted
;
714 static bitmap all_blocks
;
716 /* Locations that are killed by calls in the global phase. */
717 static bitmap kill_on_calls
;
719 /* The number of bits used in the global bitmaps. */
720 static unsigned int current_position
;
722 /*----------------------------------------------------------------------------
726 ----------------------------------------------------------------------------*/
729 /* Find the entry associated with ALIAS_SET. */
731 static struct clear_alias_mode_holder
*
732 clear_alias_set_lookup (alias_set_type alias_set
)
734 struct clear_alias_mode_holder tmp_holder
;
737 tmp_holder
.alias_set
= alias_set
;
738 slot
= htab_find_slot (clear_alias_mode_table
, &tmp_holder
, NO_INSERT
);
741 return (struct clear_alias_mode_holder
*) *slot
;
745 /* Hashtable callbacks for maintaining the "bases" field of
746 store_group_info, given that the addresses are function invariants. */
748 struct invariant_group_base_hasher
: typed_noop_remove
<group_info
>
750 typedef group_info
*value_type
;
751 typedef group_info
*compare_type
;
752 static inline hashval_t
hash (const group_info
*);
753 static inline bool equal (const group_info
*, const group_info
*);
757 invariant_group_base_hasher::equal (const group_info
*gi1
,
758 const group_info
*gi2
)
760 return rtx_equal_p (gi1
->rtx_base
, gi2
->rtx_base
);
764 invariant_group_base_hasher::hash (const group_info
*gi
)
767 return hash_rtx (gi
->rtx_base
, Pmode
, &do_not_record
, NULL
, false);
770 /* Tables of group_info structures, hashed by base value. */
771 static hash_table
<invariant_group_base_hasher
> *rtx_group_table
;
774 /* Get the GROUP for BASE. Add a new group if it is not there. */
777 get_group_info (rtx base
)
779 struct group_info tmp_gi
;
785 /* Find the store_base_info structure for BASE, creating a new one
787 tmp_gi
.rtx_base
= base
;
788 slot
= rtx_group_table
->find_slot (&tmp_gi
, INSERT
);
789 gi
= (group_info_t
) *slot
;
793 if (!clear_alias_group
)
795 clear_alias_group
= gi
= new group_info
;
796 memset (gi
, 0, sizeof (struct group_info
));
797 gi
->id
= rtx_group_next_id
++;
798 gi
->store1_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
799 gi
->store1_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
800 gi
->store2_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
801 gi
->store2_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
802 gi
->escaped_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
803 gi
->escaped_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
804 gi
->group_kill
= BITMAP_ALLOC (&dse_bitmap_obstack
);
805 gi
->process_globally
= false;
806 gi
->offset_map_size_n
= 0;
807 gi
->offset_map_size_p
= 0;
808 gi
->offset_map_n
= NULL
;
809 gi
->offset_map_p
= NULL
;
810 rtx_group_vec
.safe_push (gi
);
812 return clear_alias_group
;
817 *slot
= gi
= new group_info
;
819 gi
->id
= rtx_group_next_id
++;
820 gi
->base_mem
= gen_rtx_MEM (BLKmode
, base
);
821 gi
->canon_base_addr
= canon_rtx (base
);
822 gi
->store1_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
823 gi
->store1_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
824 gi
->store2_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
825 gi
->store2_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
826 gi
->escaped_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
827 gi
->escaped_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
828 gi
->group_kill
= BITMAP_ALLOC (&dse_bitmap_obstack
);
829 gi
->process_globally
= false;
831 (base
== frame_pointer_rtx
) || (base
== hard_frame_pointer_rtx
);
832 gi
->offset_map_size_n
= 0;
833 gi
->offset_map_size_p
= 0;
834 gi
->offset_map_n
= NULL
;
835 gi
->offset_map_p
= NULL
;
836 rtx_group_vec
.safe_push (gi
);
843 /* Initialization of data structures. */
849 globally_deleted
= 0;
852 bitmap_obstack_initialize (&dse_bitmap_obstack
);
853 gcc_obstack_init (&dse_obstack
);
855 scratch
= BITMAP_ALLOC (®_obstack
);
856 kill_on_calls
= BITMAP_ALLOC (&dse_bitmap_obstack
);
859 rtx_group_table
= new hash_table
<invariant_group_base_hasher
> (11);
861 bb_table
= XNEWVEC (bb_info_t
, last_basic_block_for_fn (cfun
));
862 rtx_group_next_id
= 0;
864 stores_off_frame_dead_at_return
= !cfun
->stdarg
;
866 init_alias_analysis ();
868 clear_alias_group
= NULL
;
873 /*----------------------------------------------------------------------------
876 Scan all of the insns. Any random ordering of the blocks is fine.
877 Each block is scanned in forward order to accommodate cselib which
878 is used to remove stores with non-constant bases.
879 ----------------------------------------------------------------------------*/
881 /* Delete all of the store_info recs from INSN_INFO. */
884 free_store_info (insn_info_t insn_info
)
886 store_info_t store_info
= insn_info
->store_rec
;
889 store_info_t next
= store_info
->next
;
890 if (store_info
->is_large
)
891 BITMAP_FREE (store_info
->positions_needed
.large
.bmap
);
892 if (store_info
->cse_base
)
893 cse_store_info_pool
.remove (store_info
);
895 rtx_store_info_pool
.remove (store_info
);
899 insn_info
->cannot_delete
= true;
900 insn_info
->contains_cselib_groups
= false;
901 insn_info
->store_rec
= NULL
;
906 rtx_insn
*first
, *current
;
907 regset fixed_regs_live
;
909 } note_add_store_info
;
911 /* Callback for emit_inc_dec_insn_before via note_stores.
912 Check if a register is clobbered which is live afterwards. */
915 note_add_store (rtx loc
, const_rtx expr ATTRIBUTE_UNUSED
, void *data
)
918 note_add_store_info
*info
= (note_add_store_info
*) data
;
923 /* If this register is referenced by the current or an earlier insn,
924 that's OK. E.g. this applies to the register that is being incremented
925 with this addition. */
926 for (insn
= info
->first
;
927 insn
!= NEXT_INSN (info
->current
);
928 insn
= NEXT_INSN (insn
))
929 if (reg_referenced_p (loc
, PATTERN (insn
)))
932 /* If we come here, we have a clobber of a register that's only OK
933 if that register is not live. If we don't have liveness information
934 available, fail now. */
935 if (!info
->fixed_regs_live
)
937 info
->failure
= true;
940 /* Now check if this is a live fixed register. */
941 unsigned int end_regno
= END_REGNO (loc
);
942 for (unsigned int regno
= REGNO (loc
); regno
< end_regno
; ++regno
)
943 if (REGNO_REG_SET_P (info
->fixed_regs_live
, regno
))
944 info
->failure
= true;
947 /* Callback for for_each_inc_dec that emits an INSN that sets DEST to
948 SRC + SRCOFF before insn ARG. */
951 emit_inc_dec_insn_before (rtx mem ATTRIBUTE_UNUSED
,
952 rtx op ATTRIBUTE_UNUSED
,
953 rtx dest
, rtx src
, rtx srcoff
, void *arg
)
955 insn_info_t insn_info
= (insn_info_t
) arg
;
956 rtx_insn
*insn
= insn_info
->insn
, *new_insn
, *cur
;
957 note_add_store_info info
;
959 /* We can reuse all operands without copying, because we are about
960 to delete the insn that contained it. */
964 emit_insn (gen_add3_insn (dest
, src
, srcoff
));
965 new_insn
= get_insns ();
969 new_insn
= gen_move_insn (dest
, src
);
970 info
.first
= new_insn
;
971 info
.fixed_regs_live
= insn_info
->fixed_regs_live
;
972 info
.failure
= false;
973 for (cur
= new_insn
; cur
; cur
= NEXT_INSN (cur
))
976 note_stores (PATTERN (cur
), note_add_store
, &info
);
979 /* If a failure was flagged above, return 1 so that for_each_inc_dec will
980 return it immediately, communicating the failure to its caller. */
984 emit_insn_before (new_insn
, insn
);
989 /* Before we delete INSN_INFO->INSN, make sure that the auto inc/dec, if it
990 is there, is split into a separate insn.
991 Return true on success (or if there was nothing to do), false on failure. */
994 check_for_inc_dec_1 (insn_info_t insn_info
)
996 rtx_insn
*insn
= insn_info
->insn
;
997 rtx note
= find_reg_note (insn
, REG_INC
, NULL_RTX
);
999 return for_each_inc_dec (PATTERN (insn
), emit_inc_dec_insn_before
,
1005 /* Entry point for postreload. If you work on reload_cse, or you need this
1006 anywhere else, consider if you can provide register liveness information
1007 and add a parameter to this function so that it can be passed down in
1008 insn_info.fixed_regs_live. */
1010 check_for_inc_dec (rtx_insn
*insn
)
1012 insn_info_type insn_info
;
1015 insn_info
.insn
= insn
;
1016 insn_info
.fixed_regs_live
= NULL
;
1017 note
= find_reg_note (insn
, REG_INC
, NULL_RTX
);
1019 return for_each_inc_dec (PATTERN (insn
), emit_inc_dec_insn_before
,
1024 /* Delete the insn and free all of the fields inside INSN_INFO. */
1027 delete_dead_store_insn (insn_info_t insn_info
)
1029 read_info_t read_info
;
1034 if (!check_for_inc_dec_1 (insn_info
))
1036 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1038 fprintf (dump_file
, "Locally deleting insn %d ",
1039 INSN_UID (insn_info
->insn
));
1040 if (insn_info
->store_rec
->alias_set
)
1041 fprintf (dump_file
, "alias set %d\n",
1042 (int) insn_info
->store_rec
->alias_set
);
1044 fprintf (dump_file
, "\n");
1047 free_store_info (insn_info
);
1048 read_info
= insn_info
->read_rec
;
1052 read_info_t next
= read_info
->next
;
1056 insn_info
->read_rec
= NULL
;
1058 delete_insn (insn_info
->insn
);
1060 insn_info
->insn
= NULL
;
1062 insn_info
->wild_read
= false;
1065 /* Return whether DECL, a local variable, can possibly escape the current
1069 local_variable_can_escape (tree decl
)
1071 if (TREE_ADDRESSABLE (decl
))
1074 /* If this is a partitioned variable, we need to consider all the variables
1075 in the partition. This is necessary because a store into one of them can
1076 be replaced with a store into another and this may not change the outcome
1077 of the escape analysis. */
1078 if (cfun
->gimple_df
->decls_to_pointers
!= NULL
)
1080 tree
*namep
= cfun
->gimple_df
->decls_to_pointers
->get (decl
);
1082 return TREE_ADDRESSABLE (*namep
);
1088 /* Return whether EXPR can possibly escape the current function scope. */
1091 can_escape (tree expr
)
1096 base
= get_base_address (expr
);
1098 && !may_be_aliased (base
)
1099 && !(TREE_CODE (base
) == VAR_DECL
1100 && !DECL_EXTERNAL (base
)
1101 && !TREE_STATIC (base
)
1102 && local_variable_can_escape (base
)))
1107 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
1108 OFFSET and WIDTH. */
1111 set_usage_bits (group_info_t group
, HOST_WIDE_INT offset
, HOST_WIDE_INT width
,
1115 bool expr_escapes
= can_escape (expr
);
1116 if (offset
> -MAX_OFFSET
&& offset
+ width
< MAX_OFFSET
)
1117 for (i
=offset
; i
<offset
+width
; i
++)
1125 store1
= group
->store1_n
;
1126 store2
= group
->store2_n
;
1127 escaped
= group
->escaped_n
;
1132 store1
= group
->store1_p
;
1133 store2
= group
->store2_p
;
1134 escaped
= group
->escaped_p
;
1138 if (!bitmap_set_bit (store1
, ai
))
1139 bitmap_set_bit (store2
, ai
);
1144 if (group
->offset_map_size_n
< ai
)
1145 group
->offset_map_size_n
= ai
;
1149 if (group
->offset_map_size_p
< ai
)
1150 group
->offset_map_size_p
= ai
;
1154 bitmap_set_bit (escaped
, ai
);
1159 reset_active_stores (void)
1161 active_local_stores
= NULL
;
1162 active_local_stores_len
= 0;
1165 /* Free all READ_REC of the LAST_INSN of BB_INFO. */
1168 free_read_records (bb_info_t bb_info
)
1170 insn_info_t insn_info
= bb_info
->last_insn
;
1171 read_info_t
*ptr
= &insn_info
->read_rec
;
1174 read_info_t next
= (*ptr
)->next
;
1175 if ((*ptr
)->alias_set
== 0)
1181 ptr
= &(*ptr
)->next
;
1185 /* Set the BB_INFO so that the last insn is marked as a wild read. */
1188 add_wild_read (bb_info_t bb_info
)
1190 insn_info_t insn_info
= bb_info
->last_insn
;
1191 insn_info
->wild_read
= true;
1192 free_read_records (bb_info
);
1193 reset_active_stores ();
1196 /* Set the BB_INFO so that the last insn is marked as a wild read of
1197 non-frame locations. */
1200 add_non_frame_wild_read (bb_info_t bb_info
)
1202 insn_info_t insn_info
= bb_info
->last_insn
;
1203 insn_info
->non_frame_wild_read
= true;
1204 free_read_records (bb_info
);
1205 reset_active_stores ();
1208 /* Return true if X is a constant or one of the registers that behave
1209 as a constant over the life of a function. This is equivalent to
1210 !rtx_varies_p for memory addresses. */
1213 const_or_frame_p (rtx x
)
1218 if (GET_CODE (x
) == REG
)
1220 /* Note that we have to test for the actual rtx used for the frame
1221 and arg pointers and not just the register number in case we have
1222 eliminated the frame and/or arg pointer and are using it
1224 if (x
== frame_pointer_rtx
|| x
== hard_frame_pointer_rtx
1225 /* The arg pointer varies if it is not a fixed register. */
1226 || (x
== arg_pointer_rtx
&& fixed_regs
[ARG_POINTER_REGNUM
])
1227 || x
== pic_offset_table_rtx
)
1235 /* Take all reasonable action to put the address of MEM into the form
1236 that we can do analysis on.
1238 The gold standard is to get the address into the form: address +
1239 OFFSET where address is something that rtx_varies_p considers a
1240 constant. When we can get the address in this form, we can do
1241 global analysis on it. Note that for constant bases, address is
1242 not actually returned, only the group_id. The address can be
1245 If that fails, we try cselib to get a value we can at least use
1246 locally. If that fails we return false.
1248 The GROUP_ID is set to -1 for cselib bases and the index of the
1249 group for non_varying bases.
1251 FOR_READ is true if this is a mem read and false if not. */
1254 canon_address (rtx mem
,
1255 alias_set_type
*alias_set_out
,
1257 HOST_WIDE_INT
*offset
,
1260 machine_mode address_mode
= get_address_mode (mem
);
1261 rtx mem_address
= XEXP (mem
, 0);
1262 rtx expanded_address
, address
;
1267 cselib_lookup (mem_address
, address_mode
, 1, GET_MODE (mem
));
1269 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1271 fprintf (dump_file
, " mem: ");
1272 print_inline_rtx (dump_file
, mem_address
, 0);
1273 fprintf (dump_file
, "\n");
1276 /* First see if just canon_rtx (mem_address) is const or frame,
1277 if not, try cselib_expand_value_rtx and call canon_rtx on that. */
1279 for (expanded
= 0; expanded
< 2; expanded
++)
1283 /* Use cselib to replace all of the reg references with the full
1284 expression. This will take care of the case where we have
1286 r_x = base + offset;
1291 val = *(base + offset); */
1293 expanded_address
= cselib_expand_value_rtx (mem_address
,
1296 /* If this fails, just go with the address from first
1298 if (!expanded_address
)
1302 expanded_address
= mem_address
;
1304 /* Split the address into canonical BASE + OFFSET terms. */
1305 address
= canon_rtx (expanded_address
);
1309 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1313 fprintf (dump_file
, "\n after cselib_expand address: ");
1314 print_inline_rtx (dump_file
, expanded_address
, 0);
1315 fprintf (dump_file
, "\n");
1318 fprintf (dump_file
, "\n after canon_rtx address: ");
1319 print_inline_rtx (dump_file
, address
, 0);
1320 fprintf (dump_file
, "\n");
1323 if (GET_CODE (address
) == CONST
)
1324 address
= XEXP (address
, 0);
1326 if (GET_CODE (address
) == PLUS
1327 && CONST_INT_P (XEXP (address
, 1)))
1329 *offset
= INTVAL (XEXP (address
, 1));
1330 address
= XEXP (address
, 0);
1333 if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem
))
1334 && const_or_frame_p (address
))
1336 group_info_t group
= get_group_info (address
);
1338 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1339 fprintf (dump_file
, " gid=%d offset=%d \n",
1340 group
->id
, (int)*offset
);
1342 *group_id
= group
->id
;
1347 *base
= cselib_lookup (address
, address_mode
, true, GET_MODE (mem
));
1352 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1353 fprintf (dump_file
, " no cselib val - should be a wild read.\n");
1356 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1357 fprintf (dump_file
, " varying cselib base=%u:%u offset = %d\n",
1358 (*base
)->uid
, (*base
)->hash
, (int)*offset
);
1363 /* Clear the rhs field from the active_local_stores array. */
1366 clear_rhs_from_active_local_stores (void)
1368 insn_info_t ptr
= active_local_stores
;
1372 store_info_t store_info
= ptr
->store_rec
;
1373 /* Skip the clobbers. */
1374 while (!store_info
->is_set
)
1375 store_info
= store_info
->next
;
1377 store_info
->rhs
= NULL
;
1378 store_info
->const_rhs
= NULL
;
1380 ptr
= ptr
->next_local_store
;
1385 /* Mark byte POS bytes from the beginning of store S_INFO as unneeded. */
1388 set_position_unneeded (store_info_t s_info
, int pos
)
1390 if (__builtin_expect (s_info
->is_large
, false))
1392 if (bitmap_set_bit (s_info
->positions_needed
.large
.bmap
, pos
))
1393 s_info
->positions_needed
.large
.count
++;
1396 s_info
->positions_needed
.small_bitmask
1397 &= ~(((unsigned HOST_WIDE_INT
) 1) << pos
);
1400 /* Mark the whole store S_INFO as unneeded. */
1403 set_all_positions_unneeded (store_info_t s_info
)
1405 if (__builtin_expect (s_info
->is_large
, false))
1407 int pos
, end
= s_info
->end
- s_info
->begin
;
1408 for (pos
= 0; pos
< end
; pos
++)
1409 bitmap_set_bit (s_info
->positions_needed
.large
.bmap
, pos
);
1410 s_info
->positions_needed
.large
.count
= end
;
1413 s_info
->positions_needed
.small_bitmask
= (unsigned HOST_WIDE_INT
) 0;
1416 /* Return TRUE if any bytes from S_INFO store are needed. */
1419 any_positions_needed_p (store_info_t s_info
)
1421 if (__builtin_expect (s_info
->is_large
, false))
1422 return (s_info
->positions_needed
.large
.count
1423 < s_info
->end
- s_info
->begin
);
1425 return (s_info
->positions_needed
.small_bitmask
1426 != (unsigned HOST_WIDE_INT
) 0);
1429 /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
1430 store are needed. */
1433 all_positions_needed_p (store_info_t s_info
, int start
, int width
)
1435 if (__builtin_expect (s_info
->is_large
, false))
1437 int end
= start
+ width
;
1439 if (bitmap_bit_p (s_info
->positions_needed
.large
.bmap
, start
++))
1445 unsigned HOST_WIDE_INT mask
= lowpart_bitmask (width
) << start
;
1446 return (s_info
->positions_needed
.small_bitmask
& mask
) == mask
;
1451 static rtx
get_stored_val (store_info_t
, machine_mode
, HOST_WIDE_INT
,
1452 HOST_WIDE_INT
, basic_block
, bool);
1455 /* BODY is an instruction pattern that belongs to INSN. Return 1 if
1456 there is a candidate store, after adding it to the appropriate
1457 local store group if so. */
1460 record_store (rtx body
, bb_info_t bb_info
)
1462 rtx mem
, rhs
, const_rhs
, mem_addr
;
1463 HOST_WIDE_INT offset
= 0;
1464 HOST_WIDE_INT width
= 0;
1465 alias_set_type spill_alias_set
;
1466 insn_info_t insn_info
= bb_info
->last_insn
;
1467 store_info_t store_info
= NULL
;
1469 cselib_val
*base
= NULL
;
1470 insn_info_t ptr
, last
, redundant_reason
;
1471 bool store_is_unused
;
1473 if (GET_CODE (body
) != SET
&& GET_CODE (body
) != CLOBBER
)
1476 mem
= SET_DEST (body
);
1478 /* If this is not used, then this cannot be used to keep the insn
1479 from being deleted. On the other hand, it does provide something
1480 that can be used to prove that another store is dead. */
1482 = (find_reg_note (insn_info
->insn
, REG_UNUSED
, mem
) != NULL
);
1484 /* Check whether that value is a suitable memory location. */
1487 /* If the set or clobber is unused, then it does not effect our
1488 ability to get rid of the entire insn. */
1489 if (!store_is_unused
)
1490 insn_info
->cannot_delete
= true;
1494 /* At this point we know mem is a mem. */
1495 if (GET_MODE (mem
) == BLKmode
)
1497 if (GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
1499 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1500 fprintf (dump_file
, " adding wild read for (clobber (mem:BLK (scratch))\n");
1501 add_wild_read (bb_info
);
1502 insn_info
->cannot_delete
= true;
1505 /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
1506 as memset (addr, 0, 36); */
1507 else if (!MEM_SIZE_KNOWN_P (mem
)
1508 || MEM_SIZE (mem
) <= 0
1509 || MEM_SIZE (mem
) > MAX_OFFSET
1510 || GET_CODE (body
) != SET
1511 || !CONST_INT_P (SET_SRC (body
)))
1513 if (!store_is_unused
)
1515 /* If the set or clobber is unused, then it does not effect our
1516 ability to get rid of the entire insn. */
1517 insn_info
->cannot_delete
= true;
1518 clear_rhs_from_active_local_stores ();
1524 /* We can still process a volatile mem, we just cannot delete it. */
1525 if (MEM_VOLATILE_P (mem
))
1526 insn_info
->cannot_delete
= true;
1528 if (!canon_address (mem
, &spill_alias_set
, &group_id
, &offset
, &base
))
1530 clear_rhs_from_active_local_stores ();
1534 if (GET_MODE (mem
) == BLKmode
)
1535 width
= MEM_SIZE (mem
);
1537 width
= GET_MODE_SIZE (GET_MODE (mem
));
1539 if (spill_alias_set
)
1541 bitmap store1
= clear_alias_group
->store1_p
;
1542 bitmap store2
= clear_alias_group
->store2_p
;
1544 gcc_assert (GET_MODE (mem
) != BLKmode
);
1546 if (!bitmap_set_bit (store1
, spill_alias_set
))
1547 bitmap_set_bit (store2
, spill_alias_set
);
1549 if (clear_alias_group
->offset_map_size_p
< spill_alias_set
)
1550 clear_alias_group
->offset_map_size_p
= spill_alias_set
;
1552 store_info
= rtx_store_info_pool
.allocate ();
1554 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1555 fprintf (dump_file
, " processing spill store %d(%s)\n",
1556 (int) spill_alias_set
, GET_MODE_NAME (GET_MODE (mem
)));
1558 else if (group_id
>= 0)
1560 /* In the restrictive case where the base is a constant or the
1561 frame pointer we can do global analysis. */
1564 = rtx_group_vec
[group_id
];
1565 tree expr
= MEM_EXPR (mem
);
1567 store_info
= rtx_store_info_pool
.allocate ();
1568 set_usage_bits (group
, offset
, width
, expr
);
1570 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1571 fprintf (dump_file
, " processing const base store gid=%d[%d..%d)\n",
1572 group_id
, (int)offset
, (int)(offset
+width
));
1576 if (may_be_sp_based_p (XEXP (mem
, 0)))
1577 insn_info
->stack_pointer_based
= true;
1578 insn_info
->contains_cselib_groups
= true;
1580 store_info
= cse_store_info_pool
.allocate ();
1583 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1584 fprintf (dump_file
, " processing cselib store [%d..%d)\n",
1585 (int)offset
, (int)(offset
+width
));
1588 const_rhs
= rhs
= NULL_RTX
;
1589 if (GET_CODE (body
) == SET
1590 /* No place to keep the value after ra. */
1591 && !reload_completed
1592 && (REG_P (SET_SRC (body
))
1593 || GET_CODE (SET_SRC (body
)) == SUBREG
1594 || CONSTANT_P (SET_SRC (body
)))
1595 && !MEM_VOLATILE_P (mem
)
1596 /* Sometimes the store and reload is used for truncation and
1598 && !(FLOAT_MODE_P (GET_MODE (mem
)) && (flag_float_store
)))
1600 rhs
= SET_SRC (body
);
1601 if (CONSTANT_P (rhs
))
1603 else if (body
== PATTERN (insn_info
->insn
))
1605 rtx tem
= find_reg_note (insn_info
->insn
, REG_EQUAL
, NULL_RTX
);
1606 if (tem
&& CONSTANT_P (XEXP (tem
, 0)))
1607 const_rhs
= XEXP (tem
, 0);
1609 if (const_rhs
== NULL_RTX
&& REG_P (rhs
))
1611 rtx tem
= cselib_expand_value_rtx (rhs
, scratch
, 5);
1613 if (tem
&& CONSTANT_P (tem
))
1618 /* Check to see if this stores causes some other stores to be
1620 ptr
= active_local_stores
;
1622 redundant_reason
= NULL
;
1623 mem
= canon_rtx (mem
);
1624 /* For alias_set != 0 canon_true_dependence should be never called. */
1625 if (spill_alias_set
)
1626 mem_addr
= NULL_RTX
;
1630 mem_addr
= base
->val_rtx
;
1634 = rtx_group_vec
[group_id
];
1635 mem_addr
= group
->canon_base_addr
;
1637 /* get_addr can only handle VALUE but cannot handle expr like:
1638 VALUE + OFFSET, so call get_addr to get original addr for
1639 mem_addr before plus_constant. */
1640 mem_addr
= get_addr (mem_addr
);
1642 mem_addr
= plus_constant (get_address_mode (mem
), mem_addr
, offset
);
1647 insn_info_t next
= ptr
->next_local_store
;
1648 store_info_t s_info
= ptr
->store_rec
;
1651 /* Skip the clobbers. We delete the active insn if this insn
1652 shadows the set. To have been put on the active list, it
1653 has exactly on set. */
1654 while (!s_info
->is_set
)
1655 s_info
= s_info
->next
;
1657 if (s_info
->alias_set
!= spill_alias_set
)
1659 else if (s_info
->alias_set
)
1661 struct clear_alias_mode_holder
*entry
1662 = clear_alias_set_lookup (s_info
->alias_set
);
1663 /* Generally, spills cannot be processed if and of the
1664 references to the slot have a different mode. But if
1665 we are in the same block and mode is exactly the same
1666 between this store and one before in the same block,
1667 we can still delete it. */
1668 if ((GET_MODE (mem
) == GET_MODE (s_info
->mem
))
1669 && (GET_MODE (mem
) == entry
->mode
))
1672 set_all_positions_unneeded (s_info
);
1674 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1675 fprintf (dump_file
, " trying spill store in insn=%d alias_set=%d\n",
1676 INSN_UID (ptr
->insn
), (int) s_info
->alias_set
);
1678 else if ((s_info
->group_id
== group_id
)
1679 && (s_info
->cse_base
== base
))
1682 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1683 fprintf (dump_file
, " trying store in insn=%d gid=%d[%d..%d)\n",
1684 INSN_UID (ptr
->insn
), s_info
->group_id
,
1685 (int)s_info
->begin
, (int)s_info
->end
);
1687 /* Even if PTR won't be eliminated as unneeded, if both
1688 PTR and this insn store the same constant value, we might
1689 eliminate this insn instead. */
1690 if (s_info
->const_rhs
1692 && offset
>= s_info
->begin
1693 && offset
+ width
<= s_info
->end
1694 && all_positions_needed_p (s_info
, offset
- s_info
->begin
,
1697 if (GET_MODE (mem
) == BLKmode
)
1699 if (GET_MODE (s_info
->mem
) == BLKmode
1700 && s_info
->const_rhs
== const_rhs
)
1701 redundant_reason
= ptr
;
1703 else if (s_info
->const_rhs
== const0_rtx
1704 && const_rhs
== const0_rtx
)
1705 redundant_reason
= ptr
;
1710 val
= get_stored_val (s_info
, GET_MODE (mem
),
1711 offset
, offset
+ width
,
1712 BLOCK_FOR_INSN (insn_info
->insn
),
1714 if (get_insns () != NULL
)
1717 if (val
&& rtx_equal_p (val
, const_rhs
))
1718 redundant_reason
= ptr
;
1722 for (i
= MAX (offset
, s_info
->begin
);
1723 i
< offset
+ width
&& i
< s_info
->end
;
1725 set_position_unneeded (s_info
, i
- s_info
->begin
);
1727 else if (s_info
->rhs
)
1728 /* Need to see if it is possible for this store to overwrite
1729 the value of store_info. If it is, set the rhs to NULL to
1730 keep it from being used to remove a load. */
1732 if (canon_true_dependence (s_info
->mem
,
1733 GET_MODE (s_info
->mem
),
1738 s_info
->const_rhs
= NULL
;
1742 /* An insn can be deleted if every position of every one of
1743 its s_infos is zero. */
1744 if (any_positions_needed_p (s_info
))
1749 insn_info_t insn_to_delete
= ptr
;
1751 active_local_stores_len
--;
1753 last
->next_local_store
= ptr
->next_local_store
;
1755 active_local_stores
= ptr
->next_local_store
;
1757 if (!insn_to_delete
->cannot_delete
)
1758 delete_dead_store_insn (insn_to_delete
);
1766 /* Finish filling in the store_info. */
1767 store_info
->next
= insn_info
->store_rec
;
1768 insn_info
->store_rec
= store_info
;
1769 store_info
->mem
= mem
;
1770 store_info
->alias_set
= spill_alias_set
;
1771 store_info
->mem_addr
= mem_addr
;
1772 store_info
->cse_base
= base
;
1773 if (width
> HOST_BITS_PER_WIDE_INT
)
1775 store_info
->is_large
= true;
1776 store_info
->positions_needed
.large
.count
= 0;
1777 store_info
->positions_needed
.large
.bmap
= BITMAP_ALLOC (&dse_bitmap_obstack
);
1781 store_info
->is_large
= false;
1782 store_info
->positions_needed
.small_bitmask
= lowpart_bitmask (width
);
1784 store_info
->group_id
= group_id
;
1785 store_info
->begin
= offset
;
1786 store_info
->end
= offset
+ width
;
1787 store_info
->is_set
= GET_CODE (body
) == SET
;
1788 store_info
->rhs
= rhs
;
1789 store_info
->const_rhs
= const_rhs
;
1790 store_info
->redundant_reason
= redundant_reason
;
1792 /* If this is a clobber, we return 0. We will only be able to
1793 delete this insn if there is only one store USED store, but we
1794 can use the clobber to delete other stores earlier. */
1795 return store_info
->is_set
? 1 : 0;
1800 dump_insn_info (const char * start
, insn_info_t insn_info
)
1802 fprintf (dump_file
, "%s insn=%d %s\n", start
,
1803 INSN_UID (insn_info
->insn
),
1804 insn_info
->store_rec
? "has store" : "naked");
1808 /* If the modes are different and the value's source and target do not
1809 line up, we need to extract the value from lower part of the rhs of
1810 the store, shift it, and then put it into a form that can be shoved
1811 into the read_insn. This function generates a right SHIFT of a
1812 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The
1813 shift sequence is returned or NULL if we failed to find a
1817 find_shift_sequence (int access_size
,
1818 store_info_t store_info
,
1819 machine_mode read_mode
,
1820 int shift
, bool speed
, bool require_cst
)
1822 machine_mode store_mode
= GET_MODE (store_info
->mem
);
1823 machine_mode new_mode
;
1824 rtx read_reg
= NULL
;
1826 /* Some machines like the x86 have shift insns for each size of
1827 operand. Other machines like the ppc or the ia-64 may only have
1828 shift insns that shift values within 32 or 64 bit registers.
1829 This loop tries to find the smallest shift insn that will right
1830 justify the value we want to read but is available in one insn on
1833 for (new_mode
= smallest_mode_for_size (access_size
* BITS_PER_UNIT
,
1835 GET_MODE_BITSIZE (new_mode
) <= BITS_PER_WORD
;
1836 new_mode
= GET_MODE_WIDER_MODE (new_mode
))
1838 rtx target
, new_reg
, new_lhs
;
1839 rtx_insn
*shift_seq
, *insn
;
1842 /* If a constant was stored into memory, try to simplify it here,
1843 otherwise the cost of the shift might preclude this optimization
1844 e.g. at -Os, even when no actual shift will be needed. */
1845 if (store_info
->const_rhs
)
1847 unsigned int byte
= subreg_lowpart_offset (new_mode
, store_mode
);
1848 rtx ret
= simplify_subreg (new_mode
, store_info
->const_rhs
,
1850 if (ret
&& CONSTANT_P (ret
))
1852 ret
= simplify_const_binary_operation (LSHIFTRT
, new_mode
,
1853 ret
, GEN_INT (shift
));
1854 if (ret
&& CONSTANT_P (ret
))
1856 byte
= subreg_lowpart_offset (read_mode
, new_mode
);
1857 ret
= simplify_subreg (read_mode
, ret
, new_mode
, byte
);
1858 if (ret
&& CONSTANT_P (ret
)
1859 && set_src_cost (ret
, speed
) <= COSTS_N_INSNS (1))
1868 /* Try a wider mode if truncating the store mode to NEW_MODE
1869 requires a real instruction. */
1870 if (GET_MODE_BITSIZE (new_mode
) < GET_MODE_BITSIZE (store_mode
)
1871 && !TRULY_NOOP_TRUNCATION_MODES_P (new_mode
, store_mode
))
1874 /* Also try a wider mode if the necessary punning is either not
1875 desirable or not possible. */
1876 if (!CONSTANT_P (store_info
->rhs
)
1877 && !MODES_TIEABLE_P (new_mode
, store_mode
))
1880 new_reg
= gen_reg_rtx (new_mode
);
1884 /* In theory we could also check for an ashr. Ian Taylor knows
1885 of one dsp where the cost of these two was not the same. But
1886 this really is a rare case anyway. */
1887 target
= expand_binop (new_mode
, lshr_optab
, new_reg
,
1888 GEN_INT (shift
), new_reg
, 1, OPTAB_DIRECT
);
1890 shift_seq
= get_insns ();
1893 if (target
!= new_reg
|| shift_seq
== NULL
)
1897 for (insn
= shift_seq
; insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
1899 cost
+= insn_rtx_cost (PATTERN (insn
), speed
);
1901 /* The computation up to here is essentially independent
1902 of the arguments and could be precomputed. It may
1903 not be worth doing so. We could precompute if
1904 worthwhile or at least cache the results. The result
1905 technically depends on both SHIFT and ACCESS_SIZE,
1906 but in practice the answer will depend only on ACCESS_SIZE. */
1908 if (cost
> COSTS_N_INSNS (1))
1911 new_lhs
= extract_low_bits (new_mode
, store_mode
,
1912 copy_rtx (store_info
->rhs
));
1913 if (new_lhs
== NULL_RTX
)
1916 /* We found an acceptable shift. Generate a move to
1917 take the value from the store and put it into the
1918 shift pseudo, then shift it, then generate another
1919 move to put in into the target of the read. */
1920 emit_move_insn (new_reg
, new_lhs
);
1921 emit_insn (shift_seq
);
1922 read_reg
= extract_low_bits (read_mode
, new_mode
, new_reg
);
1930 /* Call back for note_stores to find the hard regs set or clobbered by
1931 insn. Data is a bitmap of the hardregs set so far. */
1934 look_for_hardregs (rtx x
, const_rtx pat ATTRIBUTE_UNUSED
, void *data
)
1936 bitmap regs_set
= (bitmap
) data
;
1939 && HARD_REGISTER_P (x
))
1940 bitmap_set_range (regs_set
, REGNO (x
), REG_NREGS (x
));
1943 /* Helper function for replace_read and record_store.
1944 Attempt to return a value stored in STORE_INFO, from READ_BEGIN
1945 to one before READ_END bytes read in READ_MODE. Return NULL
1946 if not successful. If REQUIRE_CST is true, return always constant. */
1949 get_stored_val (store_info_t store_info
, machine_mode read_mode
,
1950 HOST_WIDE_INT read_begin
, HOST_WIDE_INT read_end
,
1951 basic_block bb
, bool require_cst
)
1953 machine_mode store_mode
= GET_MODE (store_info
->mem
);
1955 int access_size
; /* In bytes. */
1958 /* To get here the read is within the boundaries of the write so
1959 shift will never be negative. Start out with the shift being in
1961 if (store_mode
== BLKmode
)
1963 else if (BYTES_BIG_ENDIAN
)
1964 shift
= store_info
->end
- read_end
;
1966 shift
= read_begin
- store_info
->begin
;
1968 access_size
= shift
+ GET_MODE_SIZE (read_mode
);
1970 /* From now on it is bits. */
1971 shift
*= BITS_PER_UNIT
;
1974 read_reg
= find_shift_sequence (access_size
, store_info
, read_mode
, shift
,
1975 optimize_bb_for_speed_p (bb
),
1977 else if (store_mode
== BLKmode
)
1979 /* The store is a memset (addr, const_val, const_size). */
1980 gcc_assert (CONST_INT_P (store_info
->rhs
));
1981 store_mode
= int_mode_for_mode (read_mode
);
1982 if (store_mode
== BLKmode
)
1983 read_reg
= NULL_RTX
;
1984 else if (store_info
->rhs
== const0_rtx
)
1985 read_reg
= extract_low_bits (read_mode
, store_mode
, const0_rtx
);
1986 else if (GET_MODE_BITSIZE (store_mode
) > HOST_BITS_PER_WIDE_INT
1987 || BITS_PER_UNIT
>= HOST_BITS_PER_WIDE_INT
)
1988 read_reg
= NULL_RTX
;
1991 unsigned HOST_WIDE_INT c
1992 = INTVAL (store_info
->rhs
)
1993 & (((HOST_WIDE_INT
) 1 << BITS_PER_UNIT
) - 1);
1994 int shift
= BITS_PER_UNIT
;
1995 while (shift
< HOST_BITS_PER_WIDE_INT
)
2000 read_reg
= gen_int_mode (c
, store_mode
);
2001 read_reg
= extract_low_bits (read_mode
, store_mode
, read_reg
);
2004 else if (store_info
->const_rhs
2006 || GET_MODE_CLASS (read_mode
) != GET_MODE_CLASS (store_mode
)))
2007 read_reg
= extract_low_bits (read_mode
, store_mode
,
2008 copy_rtx (store_info
->const_rhs
));
2010 read_reg
= extract_low_bits (read_mode
, store_mode
,
2011 copy_rtx (store_info
->rhs
));
2012 if (require_cst
&& read_reg
&& !CONSTANT_P (read_reg
))
2013 read_reg
= NULL_RTX
;
2017 /* Take a sequence of:
2040 Depending on the alignment and the mode of the store and
2044 The STORE_INFO and STORE_INSN are for the store and READ_INFO
2045 and READ_INSN are for the read. Return true if the replacement
2049 replace_read (store_info_t store_info
, insn_info_t store_insn
,
2050 read_info_t read_info
, insn_info_t read_insn
, rtx
*loc
,
2053 machine_mode store_mode
= GET_MODE (store_info
->mem
);
2054 machine_mode read_mode
= GET_MODE (read_info
->mem
);
2055 rtx_insn
*insns
, *this_insn
;
2062 /* Create a sequence of instructions to set up the read register.
2063 This sequence goes immediately before the store and its result
2064 is read by the load.
2066 We need to keep this in perspective. We are replacing a read
2067 with a sequence of insns, but the read will almost certainly be
2068 in cache, so it is not going to be an expensive one. Thus, we
2069 are not willing to do a multi insn shift or worse a subroutine
2070 call to get rid of the read. */
2071 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2072 fprintf (dump_file
, "trying to replace %smode load in insn %d"
2073 " from %smode store in insn %d\n",
2074 GET_MODE_NAME (read_mode
), INSN_UID (read_insn
->insn
),
2075 GET_MODE_NAME (store_mode
), INSN_UID (store_insn
->insn
));
2077 bb
= BLOCK_FOR_INSN (read_insn
->insn
);
2078 read_reg
= get_stored_val (store_info
,
2079 read_mode
, read_info
->begin
, read_info
->end
,
2081 if (read_reg
== NULL_RTX
)
2084 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2085 fprintf (dump_file
, " -- could not extract bits of stored value\n");
2088 /* Force the value into a new register so that it won't be clobbered
2089 between the store and the load. */
2090 read_reg
= copy_to_mode_reg (read_mode
, read_reg
);
2091 insns
= get_insns ();
2094 if (insns
!= NULL_RTX
)
2096 /* Now we have to scan the set of new instructions to see if the
2097 sequence contains and sets of hardregs that happened to be
2098 live at this point. For instance, this can happen if one of
2099 the insns sets the CC and the CC happened to be live at that
2100 point. This does occasionally happen, see PR 37922. */
2101 bitmap regs_set
= BITMAP_ALLOC (®_obstack
);
2103 for (this_insn
= insns
; this_insn
!= NULL_RTX
; this_insn
= NEXT_INSN (this_insn
))
2104 note_stores (PATTERN (this_insn
), look_for_hardregs
, regs_set
);
2106 bitmap_and_into (regs_set
, regs_live
);
2107 if (!bitmap_empty_p (regs_set
))
2109 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2112 "abandoning replacement because sequence clobbers live hardregs:");
2113 df_print_regset (dump_file
, regs_set
);
2116 BITMAP_FREE (regs_set
);
2119 BITMAP_FREE (regs_set
);
2122 if (validate_change (read_insn
->insn
, loc
, read_reg
, 0))
2124 deferred_change_t change
= new deferred_change
;
2126 /* Insert this right before the store insn where it will be safe
2127 from later insns that might change it before the read. */
2128 emit_insn_before (insns
, store_insn
->insn
);
2130 /* And now for the kludge part: cselib croaks if you just
2131 return at this point. There are two reasons for this:
2133 1) Cselib has an idea of how many pseudos there are and
2134 that does not include the new ones we just added.
2136 2) Cselib does not know about the move insn we added
2137 above the store_info, and there is no way to tell it
2138 about it, because it has "moved on".
2140 Problem (1) is fixable with a certain amount of engineering.
2141 Problem (2) is requires starting the bb from scratch. This
2144 So we are just going to have to lie. The move/extraction
2145 insns are not really an issue, cselib did not see them. But
2146 the use of the new pseudo read_insn is a real problem because
2147 cselib has not scanned this insn. The way that we solve this
2148 problem is that we are just going to put the mem back for now
2149 and when we are finished with the block, we undo this. We
2150 keep a table of mems to get rid of. At the end of the basic
2151 block we can put them back. */
2153 *loc
= read_info
->mem
;
2154 change
->next
= deferred_change_list
;
2155 deferred_change_list
= change
;
2157 change
->reg
= read_reg
;
2159 /* Get rid of the read_info, from the point of view of the
2160 rest of dse, play like this read never happened. */
2161 read_insn
->read_rec
= read_info
->next
;
2163 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2165 fprintf (dump_file
, " -- replaced the loaded MEM with ");
2166 print_simple_rtl (dump_file
, read_reg
);
2167 fprintf (dump_file
, "\n");
2173 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2175 fprintf (dump_file
, " -- replacing the loaded MEM with ");
2176 print_simple_rtl (dump_file
, read_reg
);
2177 fprintf (dump_file
, " led to an invalid instruction\n");
2183 /* Check the address of MEM *LOC and kill any appropriate stores that may
2187 check_mem_read_rtx (rtx
*loc
, bb_info_t bb_info
)
2189 rtx mem
= *loc
, mem_addr
;
2190 insn_info_t insn_info
;
2191 HOST_WIDE_INT offset
= 0;
2192 HOST_WIDE_INT width
= 0;
2193 alias_set_type spill_alias_set
= 0;
2194 cselib_val
*base
= NULL
;
2196 read_info_t read_info
;
2198 insn_info
= bb_info
->last_insn
;
2200 if ((MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2201 || (MEM_VOLATILE_P (mem
)))
2203 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2204 fprintf (dump_file
, " adding wild read, volatile or barrier.\n");
2205 add_wild_read (bb_info
);
2206 insn_info
->cannot_delete
= true;
2210 /* If it is reading readonly mem, then there can be no conflict with
2212 if (MEM_READONLY_P (mem
))
2215 if (!canon_address (mem
, &spill_alias_set
, &group_id
, &offset
, &base
))
2217 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2218 fprintf (dump_file
, " adding wild read, canon_address failure.\n");
2219 add_wild_read (bb_info
);
2223 if (GET_MODE (mem
) == BLKmode
)
2226 width
= GET_MODE_SIZE (GET_MODE (mem
));
2228 read_info
= new read_info_type
;
2229 read_info
->group_id
= group_id
;
2230 read_info
->mem
= mem
;
2231 read_info
->alias_set
= spill_alias_set
;
2232 read_info
->begin
= offset
;
2233 read_info
->end
= offset
+ width
;
2234 read_info
->next
= insn_info
->read_rec
;
2235 insn_info
->read_rec
= read_info
;
2236 /* For alias_set != 0 canon_true_dependence should be never called. */
2237 if (spill_alias_set
)
2238 mem_addr
= NULL_RTX
;
2242 mem_addr
= base
->val_rtx
;
2246 = rtx_group_vec
[group_id
];
2247 mem_addr
= group
->canon_base_addr
;
2249 /* get_addr can only handle VALUE but cannot handle expr like:
2250 VALUE + OFFSET, so call get_addr to get original addr for
2251 mem_addr before plus_constant. */
2252 mem_addr
= get_addr (mem_addr
);
2254 mem_addr
= plus_constant (get_address_mode (mem
), mem_addr
, offset
);
2257 /* We ignore the clobbers in store_info. The is mildly aggressive,
2258 but there really should not be a clobber followed by a read. */
2260 if (spill_alias_set
)
2262 insn_info_t i_ptr
= active_local_stores
;
2263 insn_info_t last
= NULL
;
2265 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2266 fprintf (dump_file
, " processing spill load %d\n",
2267 (int) spill_alias_set
);
2271 store_info_t store_info
= i_ptr
->store_rec
;
2273 /* Skip the clobbers. */
2274 while (!store_info
->is_set
)
2275 store_info
= store_info
->next
;
2277 if (store_info
->alias_set
== spill_alias_set
)
2279 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2280 dump_insn_info ("removing from active", i_ptr
);
2282 active_local_stores_len
--;
2284 last
->next_local_store
= i_ptr
->next_local_store
;
2286 active_local_stores
= i_ptr
->next_local_store
;
2290 i_ptr
= i_ptr
->next_local_store
;
2293 else if (group_id
>= 0)
2295 /* This is the restricted case where the base is a constant or
2296 the frame pointer and offset is a constant. */
2297 insn_info_t i_ptr
= active_local_stores
;
2298 insn_info_t last
= NULL
;
2300 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2303 fprintf (dump_file
, " processing const load gid=%d[BLK]\n",
2306 fprintf (dump_file
, " processing const load gid=%d[%d..%d)\n",
2307 group_id
, (int)offset
, (int)(offset
+width
));
2312 bool remove
= false;
2313 store_info_t store_info
= i_ptr
->store_rec
;
2315 /* Skip the clobbers. */
2316 while (!store_info
->is_set
)
2317 store_info
= store_info
->next
;
2319 /* There are three cases here. */
2320 if (store_info
->group_id
< 0)
2321 /* We have a cselib store followed by a read from a
2324 = canon_true_dependence (store_info
->mem
,
2325 GET_MODE (store_info
->mem
),
2326 store_info
->mem_addr
,
2329 else if (group_id
== store_info
->group_id
)
2331 /* This is a block mode load. We may get lucky and
2332 canon_true_dependence may save the day. */
2335 = canon_true_dependence (store_info
->mem
,
2336 GET_MODE (store_info
->mem
),
2337 store_info
->mem_addr
,
2340 /* If this read is just reading back something that we just
2341 stored, rewrite the read. */
2345 && offset
>= store_info
->begin
2346 && offset
+ width
<= store_info
->end
2347 && all_positions_needed_p (store_info
,
2348 offset
- store_info
->begin
,
2350 && replace_read (store_info
, i_ptr
, read_info
,
2351 insn_info
, loc
, bb_info
->regs_live
))
2354 /* The bases are the same, just see if the offsets
2356 if ((offset
< store_info
->end
)
2357 && (offset
+ width
> store_info
->begin
))
2363 The else case that is missing here is that the
2364 bases are constant but different. There is nothing
2365 to do here because there is no overlap. */
2369 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2370 dump_insn_info ("removing from active", i_ptr
);
2372 active_local_stores_len
--;
2374 last
->next_local_store
= i_ptr
->next_local_store
;
2376 active_local_stores
= i_ptr
->next_local_store
;
2380 i_ptr
= i_ptr
->next_local_store
;
2385 insn_info_t i_ptr
= active_local_stores
;
2386 insn_info_t last
= NULL
;
2387 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2389 fprintf (dump_file
, " processing cselib load mem:");
2390 print_inline_rtx (dump_file
, mem
, 0);
2391 fprintf (dump_file
, "\n");
2396 bool remove
= false;
2397 store_info_t store_info
= i_ptr
->store_rec
;
2399 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2400 fprintf (dump_file
, " processing cselib load against insn %d\n",
2401 INSN_UID (i_ptr
->insn
));
2403 /* Skip the clobbers. */
2404 while (!store_info
->is_set
)
2405 store_info
= store_info
->next
;
2407 /* If this read is just reading back something that we just
2408 stored, rewrite the read. */
2410 && store_info
->group_id
== -1
2411 && store_info
->cse_base
== base
2413 && offset
>= store_info
->begin
2414 && offset
+ width
<= store_info
->end
2415 && all_positions_needed_p (store_info
,
2416 offset
- store_info
->begin
, width
)
2417 && replace_read (store_info
, i_ptr
, read_info
, insn_info
, loc
,
2418 bb_info
->regs_live
))
2421 if (!store_info
->alias_set
)
2422 remove
= canon_true_dependence (store_info
->mem
,
2423 GET_MODE (store_info
->mem
),
2424 store_info
->mem_addr
,
2429 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2430 dump_insn_info ("removing from active", i_ptr
);
2432 active_local_stores_len
--;
2434 last
->next_local_store
= i_ptr
->next_local_store
;
2436 active_local_stores
= i_ptr
->next_local_store
;
2440 i_ptr
= i_ptr
->next_local_store
;
2445 /* A note_uses callback in which DATA points the INSN_INFO for
2446 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
2447 true for any part of *LOC. */
2450 check_mem_read_use (rtx
*loc
, void *data
)
2452 subrtx_ptr_iterator::array_type array
;
2453 FOR_EACH_SUBRTX_PTR (iter
, array
, loc
, NONCONST
)
2457 check_mem_read_rtx (loc
, (bb_info_t
) data
);
2462 /* Get arguments passed to CALL_INSN. Return TRUE if successful.
2463 So far it only handles arguments passed in registers. */
2466 get_call_args (rtx call_insn
, tree fn
, rtx
*args
, int nargs
)
2468 CUMULATIVE_ARGS args_so_far_v
;
2469 cumulative_args_t args_so_far
;
2473 INIT_CUMULATIVE_ARGS (args_so_far_v
, TREE_TYPE (fn
), NULL_RTX
, 0, 3);
2474 args_so_far
= pack_cumulative_args (&args_so_far_v
);
2476 arg
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2478 arg
!= void_list_node
&& idx
< nargs
;
2479 arg
= TREE_CHAIN (arg
), idx
++)
2481 machine_mode mode
= TYPE_MODE (TREE_VALUE (arg
));
2483 reg
= targetm
.calls
.function_arg (args_so_far
, mode
, NULL_TREE
, true);
2484 if (!reg
|| !REG_P (reg
) || GET_MODE (reg
) != mode
2485 || GET_MODE_CLASS (mode
) != MODE_INT
)
2488 for (link
= CALL_INSN_FUNCTION_USAGE (call_insn
);
2490 link
= XEXP (link
, 1))
2491 if (GET_CODE (XEXP (link
, 0)) == USE
)
2493 args
[idx
] = XEXP (XEXP (link
, 0), 0);
2494 if (REG_P (args
[idx
])
2495 && REGNO (args
[idx
]) == REGNO (reg
)
2496 && (GET_MODE (args
[idx
]) == mode
2497 || (GET_MODE_CLASS (GET_MODE (args
[idx
])) == MODE_INT
2498 && (GET_MODE_SIZE (GET_MODE (args
[idx
]))
2500 && (GET_MODE_SIZE (GET_MODE (args
[idx
]))
2501 > GET_MODE_SIZE (mode
)))))
2507 tmp
= cselib_expand_value_rtx (args
[idx
], scratch
, 5);
2508 if (GET_MODE (args
[idx
]) != mode
)
2510 if (!tmp
|| !CONST_INT_P (tmp
))
2512 tmp
= gen_int_mode (INTVAL (tmp
), mode
);
2517 targetm
.calls
.function_arg_advance (args_so_far
, mode
, NULL_TREE
, true);
2519 if (arg
!= void_list_node
|| idx
!= nargs
)
2524 /* Return a bitmap of the fixed registers contained in IN. */
2527 copy_fixed_regs (const_bitmap in
)
2531 ret
= ALLOC_REG_SET (NULL
);
2532 bitmap_and (ret
, in
, fixed_reg_set_regset
);
2536 /* Apply record_store to all candidate stores in INSN. Mark INSN
2537 if some part of it is not a candidate store and assigns to a
2538 non-register target. */
2541 scan_insn (bb_info_t bb_info
, rtx_insn
*insn
)
2544 insn_info_type
*insn_info
= new insn_info_type
;
2546 memset (insn_info
, 0, sizeof (struct insn_info_type
));
2548 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2549 fprintf (dump_file
, "\n**scanning insn=%d\n",
2552 insn_info
->prev_insn
= bb_info
->last_insn
;
2553 insn_info
->insn
= insn
;
2554 bb_info
->last_insn
= insn_info
;
2556 if (DEBUG_INSN_P (insn
))
2558 insn_info
->cannot_delete
= true;
2562 /* Look at all of the uses in the insn. */
2563 note_uses (&PATTERN (insn
), check_mem_read_use
, bb_info
);
2568 tree memset_call
= NULL_TREE
;
2570 insn_info
->cannot_delete
= true;
2572 /* Const functions cannot do anything bad i.e. read memory,
2573 however, they can read their parameters which may have
2574 been pushed onto the stack.
2575 memset and bzero don't read memory either. */
2576 const_call
= RTL_CONST_CALL_P (insn
);
2579 rtx call
= get_call_rtx_from (insn
);
2580 if (call
&& GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
2582 rtx symbol
= XEXP (XEXP (call
, 0), 0);
2583 if (SYMBOL_REF_DECL (symbol
)
2584 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
2586 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
2588 && (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
))
2589 == BUILT_IN_MEMSET
))
2590 || SYMBOL_REF_DECL (symbol
) == block_clear_fn
)
2591 memset_call
= SYMBOL_REF_DECL (symbol
);
2595 if (const_call
|| memset_call
)
2597 insn_info_t i_ptr
= active_local_stores
;
2598 insn_info_t last
= NULL
;
2600 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2601 fprintf (dump_file
, "%s call %d\n",
2602 const_call
? "const" : "memset", INSN_UID (insn
));
2604 /* See the head comment of the frame_read field. */
2605 if (reload_completed
2606 /* Tail calls are storing their arguments using
2607 arg pointer. If it is a frame pointer on the target,
2608 even before reload we need to kill frame pointer based
2610 || (SIBLING_CALL_P (insn
)
2611 && HARD_FRAME_POINTER_IS_ARG_POINTER
))
2612 insn_info
->frame_read
= true;
2614 /* Loop over the active stores and remove those which are
2615 killed by the const function call. */
2618 bool remove_store
= false;
2620 /* The stack pointer based stores are always killed. */
2621 if (i_ptr
->stack_pointer_based
)
2622 remove_store
= true;
2624 /* If the frame is read, the frame related stores are killed. */
2625 else if (insn_info
->frame_read
)
2627 store_info_t store_info
= i_ptr
->store_rec
;
2629 /* Skip the clobbers. */
2630 while (!store_info
->is_set
)
2631 store_info
= store_info
->next
;
2633 if (store_info
->group_id
>= 0
2634 && rtx_group_vec
[store_info
->group_id
]->frame_related
)
2635 remove_store
= true;
2640 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2641 dump_insn_info ("removing from active", i_ptr
);
2643 active_local_stores_len
--;
2645 last
->next_local_store
= i_ptr
->next_local_store
;
2647 active_local_stores
= i_ptr
->next_local_store
;
2652 i_ptr
= i_ptr
->next_local_store
;
2658 if (get_call_args (insn
, memset_call
, args
, 3)
2659 && CONST_INT_P (args
[1])
2660 && CONST_INT_P (args
[2])
2661 && INTVAL (args
[2]) > 0)
2663 rtx mem
= gen_rtx_MEM (BLKmode
, args
[0]);
2664 set_mem_size (mem
, INTVAL (args
[2]));
2665 body
= gen_rtx_SET (mem
, args
[1]);
2666 mems_found
+= record_store (body
, bb_info
);
2667 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2668 fprintf (dump_file
, "handling memset as BLKmode store\n");
2669 if (mems_found
== 1)
2671 if (active_local_stores_len
++
2672 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES
))
2674 active_local_stores_len
= 1;
2675 active_local_stores
= NULL
;
2677 insn_info
->fixed_regs_live
2678 = copy_fixed_regs (bb_info
->regs_live
);
2679 insn_info
->next_local_store
= active_local_stores
;
2680 active_local_stores
= insn_info
;
2685 else if (SIBLING_CALL_P (insn
) && reload_completed
)
2686 /* Arguments for a sibling call that are pushed to memory are passed
2687 using the incoming argument pointer of the current function. After
2688 reload that might be (and likely is) frame pointer based. */
2689 add_wild_read (bb_info
);
2691 /* Every other call, including pure functions, may read any memory
2692 that is not relative to the frame. */
2693 add_non_frame_wild_read (bb_info
);
2698 /* Assuming that there are sets in these insns, we cannot delete
2700 if ((GET_CODE (PATTERN (insn
)) == CLOBBER
)
2701 || volatile_refs_p (PATTERN (insn
))
2702 || (!cfun
->can_delete_dead_exceptions
&& !insn_nothrow_p (insn
))
2703 || (RTX_FRAME_RELATED_P (insn
))
2704 || find_reg_note (insn
, REG_FRAME_RELATED_EXPR
, NULL_RTX
))
2705 insn_info
->cannot_delete
= true;
2707 body
= PATTERN (insn
);
2708 if (GET_CODE (body
) == PARALLEL
)
2711 for (i
= 0; i
< XVECLEN (body
, 0); i
++)
2712 mems_found
+= record_store (XVECEXP (body
, 0, i
), bb_info
);
2715 mems_found
+= record_store (body
, bb_info
);
2717 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2718 fprintf (dump_file
, "mems_found = %d, cannot_delete = %s\n",
2719 mems_found
, insn_info
->cannot_delete
? "true" : "false");
2721 /* If we found some sets of mems, add it into the active_local_stores so
2722 that it can be locally deleted if found dead or used for
2723 replace_read and redundant constant store elimination. Otherwise mark
2724 it as cannot delete. This simplifies the processing later. */
2725 if (mems_found
== 1)
2727 if (active_local_stores_len
++
2728 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES
))
2730 active_local_stores_len
= 1;
2731 active_local_stores
= NULL
;
2733 insn_info
->fixed_regs_live
= copy_fixed_regs (bb_info
->regs_live
);
2734 insn_info
->next_local_store
= active_local_stores
;
2735 active_local_stores
= insn_info
;
2738 insn_info
->cannot_delete
= true;
2742 /* Remove BASE from the set of active_local_stores. This is a
2743 callback from cselib that is used to get rid of the stores in
2744 active_local_stores. */
2747 remove_useless_values (cselib_val
*base
)
2749 insn_info_t insn_info
= active_local_stores
;
2750 insn_info_t last
= NULL
;
2754 store_info_t store_info
= insn_info
->store_rec
;
2757 /* If ANY of the store_infos match the cselib group that is
2758 being deleted, then the insn can not be deleted. */
2761 if ((store_info
->group_id
== -1)
2762 && (store_info
->cse_base
== base
))
2767 store_info
= store_info
->next
;
2772 active_local_stores_len
--;
2774 last
->next_local_store
= insn_info
->next_local_store
;
2776 active_local_stores
= insn_info
->next_local_store
;
2777 free_store_info (insn_info
);
2782 insn_info
= insn_info
->next_local_store
;
2787 /* Do all of step 1. */
2793 bitmap regs_live
= BITMAP_ALLOC (®_obstack
);
2796 all_blocks
= BITMAP_ALLOC (NULL
);
2797 bitmap_set_bit (all_blocks
, ENTRY_BLOCK
);
2798 bitmap_set_bit (all_blocks
, EXIT_BLOCK
);
2800 FOR_ALL_BB_FN (bb
, cfun
)
2803 bb_info_t bb_info
= new dse_bb_info_type
;
2805 memset (bb_info
, 0, sizeof (dse_bb_info_type
));
2806 bitmap_set_bit (all_blocks
, bb
->index
);
2807 bb_info
->regs_live
= regs_live
;
2809 bitmap_copy (regs_live
, DF_LR_IN (bb
));
2810 df_simulate_initialize_forwards (bb
, regs_live
);
2812 bb_table
[bb
->index
] = bb_info
;
2813 cselib_discard_hook
= remove_useless_values
;
2815 if (bb
->index
>= NUM_FIXED_BLOCKS
)
2819 active_local_stores
= NULL
;
2820 active_local_stores_len
= 0;
2821 cselib_clear_table ();
2823 /* Scan the insns. */
2824 FOR_BB_INSNS (bb
, insn
)
2827 scan_insn (bb_info
, insn
);
2828 cselib_process_insn (insn
);
2830 df_simulate_one_insn_forwards (bb
, insn
, regs_live
);
2833 /* This is something of a hack, because the global algorithm
2834 is supposed to take care of the case where stores go dead
2835 at the end of the function. However, the global
2836 algorithm must take a more conservative view of block
2837 mode reads than the local alg does. So to get the case
2838 where you have a store to the frame followed by a non
2839 overlapping block more read, we look at the active local
2840 stores at the end of the function and delete all of the
2841 frame and spill based ones. */
2842 if (stores_off_frame_dead_at_return
2843 && (EDGE_COUNT (bb
->succs
) == 0
2844 || (single_succ_p (bb
)
2845 && single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
2846 && ! crtl
->calls_eh_return
)))
2848 insn_info_t i_ptr
= active_local_stores
;
2851 store_info_t store_info
= i_ptr
->store_rec
;
2853 /* Skip the clobbers. */
2854 while (!store_info
->is_set
)
2855 store_info
= store_info
->next
;
2856 if (store_info
->alias_set
&& !i_ptr
->cannot_delete
)
2857 delete_dead_store_insn (i_ptr
);
2859 if (store_info
->group_id
>= 0)
2862 = rtx_group_vec
[store_info
->group_id
];
2863 if (group
->frame_related
&& !i_ptr
->cannot_delete
)
2864 delete_dead_store_insn (i_ptr
);
2867 i_ptr
= i_ptr
->next_local_store
;
2871 /* Get rid of the loads that were discovered in
2872 replace_read. Cselib is finished with this block. */
2873 while (deferred_change_list
)
2875 deferred_change_t next
= deferred_change_list
->next
;
2877 /* There is no reason to validate this change. That was
2879 *deferred_change_list
->loc
= deferred_change_list
->reg
;
2880 delete deferred_change_list
;
2881 deferred_change_list
= next
;
2884 /* Get rid of all of the cselib based store_infos in this
2885 block and mark the containing insns as not being
2887 ptr
= bb_info
->last_insn
;
2890 if (ptr
->contains_cselib_groups
)
2892 store_info_t s_info
= ptr
->store_rec
;
2893 while (s_info
&& !s_info
->is_set
)
2894 s_info
= s_info
->next
;
2896 && s_info
->redundant_reason
2897 && s_info
->redundant_reason
->insn
2898 && !ptr
->cannot_delete
)
2900 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2901 fprintf (dump_file
, "Locally deleting insn %d "
2902 "because insn %d stores the "
2903 "same value and couldn't be "
2905 INSN_UID (ptr
->insn
),
2906 INSN_UID (s_info
->redundant_reason
->insn
));
2907 delete_dead_store_insn (ptr
);
2909 free_store_info (ptr
);
2913 store_info_t s_info
;
2915 /* Free at least positions_needed bitmaps. */
2916 for (s_info
= ptr
->store_rec
; s_info
; s_info
= s_info
->next
)
2917 if (s_info
->is_large
)
2919 BITMAP_FREE (s_info
->positions_needed
.large
.bmap
);
2920 s_info
->is_large
= false;
2923 ptr
= ptr
->prev_insn
;
2926 cse_store_info_pool
.release ();
2928 bb_info
->regs_live
= NULL
;
2931 BITMAP_FREE (regs_live
);
2933 rtx_group_table
->empty ();
2937 /*----------------------------------------------------------------------------
2940 Assign each byte position in the stores that we are going to
2941 analyze globally to a position in the bitmaps. Returns true if
2942 there are any bit positions assigned.
2943 ----------------------------------------------------------------------------*/
2946 dse_step2_init (void)
2951 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
2953 /* For all non stack related bases, we only consider a store to
2954 be deletable if there are two or more stores for that
2955 position. This is because it takes one store to make the
2956 other store redundant. However, for the stores that are
2957 stack related, we consider them if there is only one store
2958 for the position. We do this because the stack related
2959 stores can be deleted if their is no read between them and
2960 the end of the function.
2962 To make this work in the current framework, we take the stack
2963 related bases add all of the bits from store1 into store2.
2964 This has the effect of making the eligible even if there is
2967 if (stores_off_frame_dead_at_return
&& group
->frame_related
)
2969 bitmap_ior_into (group
->store2_n
, group
->store1_n
);
2970 bitmap_ior_into (group
->store2_p
, group
->store1_p
);
2971 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2972 fprintf (dump_file
, "group %d is frame related ", i
);
2975 group
->offset_map_size_n
++;
2976 group
->offset_map_n
= XOBNEWVEC (&dse_obstack
, int,
2977 group
->offset_map_size_n
);
2978 group
->offset_map_size_p
++;
2979 group
->offset_map_p
= XOBNEWVEC (&dse_obstack
, int,
2980 group
->offset_map_size_p
);
2981 group
->process_globally
= false;
2982 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2984 fprintf (dump_file
, "group %d(%d+%d): ", i
,
2985 (int)bitmap_count_bits (group
->store2_n
),
2986 (int)bitmap_count_bits (group
->store2_p
));
2987 bitmap_print (dump_file
, group
->store2_n
, "n ", " ");
2988 bitmap_print (dump_file
, group
->store2_p
, "p ", "\n");
2994 /* Init the offset tables for the normal case. */
2997 dse_step2_nospill (void)
3001 /* Position 0 is unused because 0 is used in the maps to mean
3003 current_position
= 1;
3004 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3009 if (group
== clear_alias_group
)
3012 memset (group
->offset_map_n
, 0, sizeof (int) * group
->offset_map_size_n
);
3013 memset (group
->offset_map_p
, 0, sizeof (int) * group
->offset_map_size_p
);
3014 bitmap_clear (group
->group_kill
);
3016 EXECUTE_IF_SET_IN_BITMAP (group
->store2_n
, 0, j
, bi
)
3018 bitmap_set_bit (group
->group_kill
, current_position
);
3019 if (bitmap_bit_p (group
->escaped_n
, j
))
3020 bitmap_set_bit (kill_on_calls
, current_position
);
3021 group
->offset_map_n
[j
] = current_position
++;
3022 group
->process_globally
= true;
3024 EXECUTE_IF_SET_IN_BITMAP (group
->store2_p
, 0, j
, bi
)
3026 bitmap_set_bit (group
->group_kill
, current_position
);
3027 if (bitmap_bit_p (group
->escaped_p
, j
))
3028 bitmap_set_bit (kill_on_calls
, current_position
);
3029 group
->offset_map_p
[j
] = current_position
++;
3030 group
->process_globally
= true;
3033 return current_position
!= 1;
3038 /*----------------------------------------------------------------------------
3041 Build the bit vectors for the transfer functions.
3042 ----------------------------------------------------------------------------*/
3045 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
3049 get_bitmap_index (group_info_t group_info
, HOST_WIDE_INT offset
)
3053 HOST_WIDE_INT offset_p
= -offset
;
3054 if (offset_p
>= group_info
->offset_map_size_n
)
3056 return group_info
->offset_map_n
[offset_p
];
3060 if (offset
>= group_info
->offset_map_size_p
)
3062 return group_info
->offset_map_p
[offset
];
3067 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3071 scan_stores_nospill (store_info_t store_info
, bitmap gen
, bitmap kill
)
3076 group_info_t group_info
3077 = rtx_group_vec
[store_info
->group_id
];
3078 if (group_info
->process_globally
)
3079 for (i
= store_info
->begin
; i
< store_info
->end
; i
++)
3081 int index
= get_bitmap_index (group_info
, i
);
3084 bitmap_set_bit (gen
, index
);
3086 bitmap_clear_bit (kill
, index
);
3089 store_info
= store_info
->next
;
3094 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3098 scan_stores_spill (store_info_t store_info
, bitmap gen
, bitmap kill
)
3102 if (store_info
->alias_set
)
3104 int index
= get_bitmap_index (clear_alias_group
,
3105 store_info
->alias_set
);
3108 bitmap_set_bit (gen
, index
);
3110 bitmap_clear_bit (kill
, index
);
3113 store_info
= store_info
->next
;
3118 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3122 scan_reads_nospill (insn_info_t insn_info
, bitmap gen
, bitmap kill
)
3124 read_info_t read_info
= insn_info
->read_rec
;
3128 /* If this insn reads the frame, kill all the frame related stores. */
3129 if (insn_info
->frame_read
)
3131 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3132 if (group
->process_globally
&& group
->frame_related
)
3135 bitmap_ior_into (kill
, group
->group_kill
);
3136 bitmap_and_compl_into (gen
, group
->group_kill
);
3139 if (insn_info
->non_frame_wild_read
)
3141 /* Kill all non-frame related stores. Kill all stores of variables that
3144 bitmap_ior_into (kill
, kill_on_calls
);
3145 bitmap_and_compl_into (gen
, kill_on_calls
);
3146 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3147 if (group
->process_globally
&& !group
->frame_related
)
3150 bitmap_ior_into (kill
, group
->group_kill
);
3151 bitmap_and_compl_into (gen
, group
->group_kill
);
3156 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3158 if (group
->process_globally
)
3160 if (i
== read_info
->group_id
)
3162 if (read_info
->begin
> read_info
->end
)
3164 /* Begin > end for block mode reads. */
3166 bitmap_ior_into (kill
, group
->group_kill
);
3167 bitmap_and_compl_into (gen
, group
->group_kill
);
3171 /* The groups are the same, just process the
3174 for (j
= read_info
->begin
; j
< read_info
->end
; j
++)
3176 int index
= get_bitmap_index (group
, j
);
3180 bitmap_set_bit (kill
, index
);
3181 bitmap_clear_bit (gen
, index
);
3188 /* The groups are different, if the alias sets
3189 conflict, clear the entire group. We only need
3190 to apply this test if the read_info is a cselib
3191 read. Anything with a constant base cannot alias
3192 something else with a different constant
3194 if ((read_info
->group_id
< 0)
3195 && canon_true_dependence (group
->base_mem
,
3196 GET_MODE (group
->base_mem
),
3197 group
->canon_base_addr
,
3198 read_info
->mem
, NULL_RTX
))
3201 bitmap_ior_into (kill
, group
->group_kill
);
3202 bitmap_and_compl_into (gen
, group
->group_kill
);
3208 read_info
= read_info
->next
;
3212 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3216 scan_reads_spill (read_info_t read_info
, bitmap gen
, bitmap kill
)
3220 if (read_info
->alias_set
)
3222 int index
= get_bitmap_index (clear_alias_group
,
3223 read_info
->alias_set
);
3227 bitmap_set_bit (kill
, index
);
3228 bitmap_clear_bit (gen
, index
);
3232 read_info
= read_info
->next
;
3237 /* Return the insn in BB_INFO before the first wild read or if there
3238 are no wild reads in the block, return the last insn. */
3241 find_insn_before_first_wild_read (bb_info_t bb_info
)
3243 insn_info_t insn_info
= bb_info
->last_insn
;
3244 insn_info_t last_wild_read
= NULL
;
3248 if (insn_info
->wild_read
)
3250 last_wild_read
= insn_info
->prev_insn
;
3251 /* Block starts with wild read. */
3252 if (!last_wild_read
)
3256 insn_info
= insn_info
->prev_insn
;
3260 return last_wild_read
;
3262 return bb_info
->last_insn
;
3266 /* Scan the insns in BB_INFO starting at PTR and going to the top of
3267 the block in order to build the gen and kill sets for the block.
3268 We start at ptr which may be the last insn in the block or may be
3269 the first insn with a wild read. In the latter case we are able to
3270 skip the rest of the block because it just does not matter:
3271 anything that happens is hidden by the wild read. */
3274 dse_step3_scan (bool for_spills
, basic_block bb
)
3276 bb_info_t bb_info
= bb_table
[bb
->index
];
3277 insn_info_t insn_info
;
3280 /* There are no wild reads in the spill case. */
3281 insn_info
= bb_info
->last_insn
;
3283 insn_info
= find_insn_before_first_wild_read (bb_info
);
3285 /* In the spill case or in the no_spill case if there is no wild
3286 read in the block, we will need a kill set. */
3287 if (insn_info
== bb_info
->last_insn
)
3290 bitmap_clear (bb_info
->kill
);
3292 bb_info
->kill
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3296 BITMAP_FREE (bb_info
->kill
);
3300 /* There may have been code deleted by the dce pass run before
3302 if (insn_info
->insn
&& INSN_P (insn_info
->insn
))
3304 /* Process the read(s) last. */
3307 scan_stores_spill (insn_info
->store_rec
, bb_info
->gen
, bb_info
->kill
);
3308 scan_reads_spill (insn_info
->read_rec
, bb_info
->gen
, bb_info
->kill
);
3312 scan_stores_nospill (insn_info
->store_rec
, bb_info
->gen
, bb_info
->kill
);
3313 scan_reads_nospill (insn_info
, bb_info
->gen
, bb_info
->kill
);
3317 insn_info
= insn_info
->prev_insn
;
3322 /* Set the gen set of the exit block, and also any block with no
3323 successors that does not have a wild read. */
3326 dse_step3_exit_block_scan (bb_info_t bb_info
)
3328 /* The gen set is all 0's for the exit block except for the
3329 frame_pointer_group. */
3331 if (stores_off_frame_dead_at_return
)
3336 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3338 if (group
->process_globally
&& group
->frame_related
)
3339 bitmap_ior_into (bb_info
->gen
, group
->group_kill
);
3345 /* Find all of the blocks that are not backwards reachable from the
3346 exit block or any block with no successors (BB). These are the
3347 infinite loops or infinite self loops. These blocks will still
3348 have their bits set in UNREACHABLE_BLOCKS. */
3351 mark_reachable_blocks (sbitmap unreachable_blocks
, basic_block bb
)
3356 if (bitmap_bit_p (unreachable_blocks
, bb
->index
))
3358 bitmap_clear_bit (unreachable_blocks
, bb
->index
);
3359 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3361 mark_reachable_blocks (unreachable_blocks
, e
->src
);
3366 /* Build the transfer functions for the function. */
3369 dse_step3 (bool for_spills
)
3372 sbitmap unreachable_blocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
3373 sbitmap_iterator sbi
;
3374 bitmap all_ones
= NULL
;
3377 bitmap_ones (unreachable_blocks
);
3379 FOR_ALL_BB_FN (bb
, cfun
)
3381 bb_info_t bb_info
= bb_table
[bb
->index
];
3383 bitmap_clear (bb_info
->gen
);
3385 bb_info
->gen
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3387 if (bb
->index
== ENTRY_BLOCK
)
3389 else if (bb
->index
== EXIT_BLOCK
)
3390 dse_step3_exit_block_scan (bb_info
);
3392 dse_step3_scan (for_spills
, bb
);
3393 if (EDGE_COUNT (bb
->succs
) == 0)
3394 mark_reachable_blocks (unreachable_blocks
, bb
);
3396 /* If this is the second time dataflow is run, delete the old
3399 BITMAP_FREE (bb_info
->in
);
3401 BITMAP_FREE (bb_info
->out
);
3404 /* For any block in an infinite loop, we must initialize the out set
3405 to all ones. This could be expensive, but almost never occurs in
3406 practice. However, it is common in regression tests. */
3407 EXECUTE_IF_SET_IN_BITMAP (unreachable_blocks
, 0, i
, sbi
)
3409 if (bitmap_bit_p (all_blocks
, i
))
3411 bb_info_t bb_info
= bb_table
[i
];
3417 all_ones
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3418 FOR_EACH_VEC_ELT (rtx_group_vec
, j
, group
)
3419 bitmap_ior_into (all_ones
, group
->group_kill
);
3423 bb_info
->out
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3424 bitmap_copy (bb_info
->out
, all_ones
);
3430 BITMAP_FREE (all_ones
);
3431 sbitmap_free (unreachable_blocks
);
3436 /*----------------------------------------------------------------------------
3439 Solve the bitvector equations.
3440 ----------------------------------------------------------------------------*/
3443 /* Confluence function for blocks with no successors. Create an out
3444 set from the gen set of the exit block. This block logically has
3445 the exit block as a successor. */
3450 dse_confluence_0 (basic_block bb
)
3452 bb_info_t bb_info
= bb_table
[bb
->index
];
3454 if (bb
->index
== EXIT_BLOCK
)
3459 bb_info
->out
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3460 bitmap_copy (bb_info
->out
, bb_table
[EXIT_BLOCK
]->gen
);
3464 /* Propagate the information from the in set of the dest of E to the
3465 out set of the src of E. If the various in or out sets are not
3466 there, that means they are all ones. */
3469 dse_confluence_n (edge e
)
3471 bb_info_t src_info
= bb_table
[e
->src
->index
];
3472 bb_info_t dest_info
= bb_table
[e
->dest
->index
];
3477 bitmap_and_into (src_info
->out
, dest_info
->in
);
3480 src_info
->out
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3481 bitmap_copy (src_info
->out
, dest_info
->in
);
3488 /* Propagate the info from the out to the in set of BB_INDEX's basic
3489 block. There are three cases:
3491 1) The block has no kill set. In this case the kill set is all
3492 ones. It does not matter what the out set of the block is, none of
3493 the info can reach the top. The only thing that reaches the top is
3494 the gen set and we just copy the set.
3496 2) There is a kill set but no out set and bb has successors. In
3497 this case we just return. Eventually an out set will be created and
3498 it is better to wait than to create a set of ones.
3500 3) There is both a kill and out set. We apply the obvious transfer
3505 dse_transfer_function (int bb_index
)
3507 bb_info_t bb_info
= bb_table
[bb_index
];
3515 return bitmap_ior_and_compl (bb_info
->in
, bb_info
->gen
,
3516 bb_info
->out
, bb_info
->kill
);
3519 bb_info
->in
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3520 bitmap_ior_and_compl (bb_info
->in
, bb_info
->gen
,
3521 bb_info
->out
, bb_info
->kill
);
3531 /* Case 1 above. If there is already an in set, nothing
3537 bb_info
->in
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3538 bitmap_copy (bb_info
->in
, bb_info
->gen
);
3544 /* Solve the dataflow equations. */
3549 df_simple_dataflow (DF_BACKWARD
, NULL
, dse_confluence_0
,
3550 dse_confluence_n
, dse_transfer_function
,
3551 all_blocks
, df_get_postorder (DF_BACKWARD
),
3552 df_get_n_blocks (DF_BACKWARD
));
3553 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3557 fprintf (dump_file
, "\n\n*** Global dataflow info after analysis.\n");
3558 FOR_ALL_BB_FN (bb
, cfun
)
3560 bb_info_t bb_info
= bb_table
[bb
->index
];
3562 df_print_bb_index (bb
, dump_file
);
3564 bitmap_print (dump_file
, bb_info
->in
, " in: ", "\n");
3566 fprintf (dump_file
, " in: *MISSING*\n");
3568 bitmap_print (dump_file
, bb_info
->gen
, " gen: ", "\n");
3570 fprintf (dump_file
, " gen: *MISSING*\n");
3572 bitmap_print (dump_file
, bb_info
->kill
, " kill: ", "\n");
3574 fprintf (dump_file
, " kill: *MISSING*\n");
3576 bitmap_print (dump_file
, bb_info
->out
, " out: ", "\n");
3578 fprintf (dump_file
, " out: *MISSING*\n\n");
3585 /*----------------------------------------------------------------------------
3588 Delete the stores that can only be deleted using the global information.
3589 ----------------------------------------------------------------------------*/
3593 dse_step5_nospill (void)
3596 FOR_EACH_BB_FN (bb
, cfun
)
3598 bb_info_t bb_info
= bb_table
[bb
->index
];
3599 insn_info_t insn_info
= bb_info
->last_insn
;
3600 bitmap v
= bb_info
->out
;
3604 bool deleted
= false;
3605 if (dump_file
&& insn_info
->insn
)
3607 fprintf (dump_file
, "starting to process insn %d\n",
3608 INSN_UID (insn_info
->insn
));
3609 bitmap_print (dump_file
, v
, " v: ", "\n");
3612 /* There may have been code deleted by the dce pass run before
3615 && INSN_P (insn_info
->insn
)
3616 && (!insn_info
->cannot_delete
)
3617 && (!bitmap_empty_p (v
)))
3619 store_info_t store_info
= insn_info
->store_rec
;
3621 /* Try to delete the current insn. */
3624 /* Skip the clobbers. */
3625 while (!store_info
->is_set
)
3626 store_info
= store_info
->next
;
3628 if (store_info
->alias_set
)
3633 group_info_t group_info
3634 = rtx_group_vec
[store_info
->group_id
];
3636 for (i
= store_info
->begin
; i
< store_info
->end
; i
++)
3638 int index
= get_bitmap_index (group_info
, i
);
3640 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3641 fprintf (dump_file
, "i = %d, index = %d\n", (int)i
, index
);
3642 if (index
== 0 || !bitmap_bit_p (v
, index
))
3644 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3645 fprintf (dump_file
, "failing at i = %d\n", (int)i
);
3654 && check_for_inc_dec_1 (insn_info
))
3656 delete_insn (insn_info
->insn
);
3657 insn_info
->insn
= NULL
;
3662 /* We do want to process the local info if the insn was
3663 deleted. For instance, if the insn did a wild read, we
3664 no longer need to trash the info. */
3666 && INSN_P (insn_info
->insn
)
3669 scan_stores_nospill (insn_info
->store_rec
, v
, NULL
);
3670 if (insn_info
->wild_read
)
3672 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3673 fprintf (dump_file
, "wild read\n");
3676 else if (insn_info
->read_rec
3677 || insn_info
->non_frame_wild_read
)
3679 if (dump_file
&& !insn_info
->non_frame_wild_read
)
3680 fprintf (dump_file
, "regular read\n");
3681 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3682 fprintf (dump_file
, "non-frame wild read\n");
3683 scan_reads_nospill (insn_info
, v
, NULL
);
3687 insn_info
= insn_info
->prev_insn
;
3694 /*----------------------------------------------------------------------------
3697 Delete stores made redundant by earlier stores (which store the same
3698 value) that couldn't be eliminated.
3699 ----------------------------------------------------------------------------*/
3706 FOR_ALL_BB_FN (bb
, cfun
)
3708 bb_info_t bb_info
= bb_table
[bb
->index
];
3709 insn_info_t insn_info
= bb_info
->last_insn
;
3713 /* There may have been code deleted by the dce pass run before
3716 && INSN_P (insn_info
->insn
)
3717 && !insn_info
->cannot_delete
)
3719 store_info_t s_info
= insn_info
->store_rec
;
3721 while (s_info
&& !s_info
->is_set
)
3722 s_info
= s_info
->next
;
3724 && s_info
->redundant_reason
3725 && s_info
->redundant_reason
->insn
3726 && INSN_P (s_info
->redundant_reason
->insn
))
3728 rtx_insn
*rinsn
= s_info
->redundant_reason
->insn
;
3729 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3730 fprintf (dump_file
, "Locally deleting insn %d "
3731 "because insn %d stores the "
3732 "same value and couldn't be "
3734 INSN_UID (insn_info
->insn
),
3736 delete_dead_store_insn (insn_info
);
3739 insn_info
= insn_info
->prev_insn
;
3744 /*----------------------------------------------------------------------------
3747 Destroy everything left standing.
3748 ----------------------------------------------------------------------------*/
3753 bitmap_obstack_release (&dse_bitmap_obstack
);
3754 obstack_free (&dse_obstack
, NULL
);
3756 end_alias_analysis ();
3758 delete rtx_group_table
;
3759 rtx_group_table
= NULL
;
3760 rtx_group_vec
.release ();
3761 BITMAP_FREE (all_blocks
);
3762 BITMAP_FREE (scratch
);
3764 rtx_store_info_pool
.release ();
3765 read_info_type::pool
.release ();
3766 insn_info_type::pool
.release ();
3767 dse_bb_info_type::pool
.release ();
3768 group_info::pool
.release ();
3769 deferred_change::pool
.release ();
3773 /* -------------------------------------------------------------------------
3775 ------------------------------------------------------------------------- */
3777 /* Callback for running pass_rtl_dse. */
3780 rest_of_handle_dse (void)
3782 df_set_flags (DF_DEFER_INSN_RESCAN
);
3784 /* Need the notes since we must track live hardregs in the forwards
3786 df_note_add_problem ();
3792 if (dse_step2_nospill ())
3794 df_set_flags (DF_LR_RUN_DCE
);
3796 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3797 fprintf (dump_file
, "doing global processing\n");
3800 dse_step5_nospill ();
3807 fprintf (dump_file
, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3808 locally_deleted
, globally_deleted
, spill_deleted
);
3810 /* DSE can eliminate potentially-trapping MEMs.
3811 Remove any EH edges associated with them. */
3812 if ((locally_deleted
|| globally_deleted
)
3813 && cfun
->can_throw_non_call_exceptions
3814 && purge_all_dead_edges ())
3822 const pass_data pass_data_rtl_dse1
=
3824 RTL_PASS
, /* type */
3826 OPTGROUP_NONE
, /* optinfo_flags */
3827 TV_DSE1
, /* tv_id */
3828 0, /* properties_required */
3829 0, /* properties_provided */
3830 0, /* properties_destroyed */
3831 0, /* todo_flags_start */
3832 TODO_df_finish
, /* todo_flags_finish */
3835 class pass_rtl_dse1
: public rtl_opt_pass
3838 pass_rtl_dse1 (gcc::context
*ctxt
)
3839 : rtl_opt_pass (pass_data_rtl_dse1
, ctxt
)
3842 /* opt_pass methods: */
3843 virtual bool gate (function
*)
3845 return optimize
> 0 && flag_dse
&& dbg_cnt (dse1
);
3848 virtual unsigned int execute (function
*) { return rest_of_handle_dse (); }
3850 }; // class pass_rtl_dse1
3855 make_pass_rtl_dse1 (gcc::context
*ctxt
)
3857 return new pass_rtl_dse1 (ctxt
);
3862 const pass_data pass_data_rtl_dse2
=
3864 RTL_PASS
, /* type */
3866 OPTGROUP_NONE
, /* optinfo_flags */
3867 TV_DSE2
, /* tv_id */
3868 0, /* properties_required */
3869 0, /* properties_provided */
3870 0, /* properties_destroyed */
3871 0, /* todo_flags_start */
3872 TODO_df_finish
, /* todo_flags_finish */
3875 class pass_rtl_dse2
: public rtl_opt_pass
3878 pass_rtl_dse2 (gcc::context
*ctxt
)
3879 : rtl_opt_pass (pass_data_rtl_dse2
, ctxt
)
3882 /* opt_pass methods: */
3883 virtual bool gate (function
*)
3885 return optimize
> 0 && flag_dse
&& dbg_cnt (dse2
);
3888 virtual unsigned int execute (function
*) { return rest_of_handle_dse (); }
3890 }; // class pass_rtl_dse2
3895 make_pass_rtl_dse2 (gcc::context
*ctxt
)
3897 return new pass_rtl_dse2 (ctxt
);