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
;
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
*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 alloc_pool cse_store_info_pool
;
333 static alloc_pool rtx_store_info_pool
;
335 /* This structure holds information about a load. These are only
336 built for rtx bases. */
339 /* The id of the mem group of the base address. */
342 /* If this is non-zero, it is the alias set of a spill location. */
343 alias_set_type alias_set
;
345 /* The offset of the first and byte after the last byte associated
346 with the operation. If begin == end == 0, the read did not have
347 a constant offset. */
350 /* The mem being read. */
353 /* The next read_info for this insn. */
354 struct read_info
*next
;
356 typedef struct read_info
*read_info_t
;
357 static alloc_pool read_info_pool
;
360 /* One of these records is created for each insn. */
364 /* Set true if the insn contains a store but the insn itself cannot
365 be deleted. This is set if the insn is a parallel and there is
366 more than one non dead output or if the insn is in some way
370 /* This field is only used by the global algorithm. It is set true
371 if the insn contains any read of mem except for a (1). This is
372 also set if the insn is a call or has a clobber mem. If the insn
373 contains a wild read, the use_rec will be null. */
376 /* This is true only for CALL instructions which could potentially read
377 any non-frame memory location. This field is used by the global
379 bool non_frame_wild_read
;
381 /* This field is only used for the processing of const functions.
382 These functions cannot read memory, but they can read the stack
383 because that is where they may get their parms. We need to be
384 this conservative because, like the store motion pass, we don't
385 consider CALL_INSN_FUNCTION_USAGE when processing call insns.
386 Moreover, we need to distinguish two cases:
387 1. Before reload (register elimination), the stores related to
388 outgoing arguments are stack pointer based and thus deemed
389 of non-constant base in this pass. This requires special
390 handling but also means that the frame pointer based stores
391 need not be killed upon encountering a const function call.
392 2. After reload, the stores related to outgoing arguments can be
393 either stack pointer or hard frame pointer based. This means
394 that we have no other choice than also killing all the frame
395 pointer based stores upon encountering a const function call.
396 This field is set after reload for const function calls and before
397 reload for const tail function calls on targets where arg pointer
398 is the frame pointer. Having this set is less severe than a wild
399 read, it just means that all the frame related stores are killed
400 rather than all the stores. */
403 /* This field is only used for the processing of const functions.
404 It is set if the insn may contain a stack pointer based store. */
405 bool stack_pointer_based
;
407 /* This is true if any of the sets within the store contains a
408 cselib base. Such stores can only be deleted by the local
410 bool contains_cselib_groups
;
415 /* The list of mem sets or mem clobbers that are contained in this
416 insn. If the insn is deletable, it contains only one mem set.
417 But it could also contain clobbers. Insns that contain more than
418 one mem set are not deletable, but each of those mems are here in
419 order to provide info to delete other insns. */
420 store_info_t store_rec
;
422 /* The linked list of mem uses in this insn. Only the reads from
423 rtx bases are listed here. The reads to cselib bases are
424 completely processed during the first scan and so are never
426 read_info_t read_rec
;
428 /* The live fixed registers. We assume only fixed registers can
429 cause trouble by being clobbered from an expanded pattern;
430 storing only the live fixed registers (rather than all registers)
431 means less memory needs to be allocated / copied for the individual
433 regset fixed_regs_live
;
435 /* The prev insn in the basic block. */
436 struct insn_info
* prev_insn
;
438 /* The linked list of insns that are in consideration for removal in
439 the forwards pass through the basic block. This pointer may be
440 trash as it is not cleared when a wild read occurs. The only
441 time it is guaranteed to be correct is when the traversal starts
442 at active_local_stores. */
443 struct insn_info
* next_local_store
;
446 typedef struct insn_info
*insn_info_t
;
447 static alloc_pool insn_info_pool
;
449 /* The linked list of stores that are under consideration in this
451 static insn_info_t active_local_stores
;
452 static int active_local_stores_len
;
457 /* Pointer to the insn info for the last insn in the block. These
458 are linked so this is how all of the insns are reached. During
459 scanning this is the current insn being scanned. */
460 insn_info_t last_insn
;
462 /* The info for the global dataflow problem. */
465 /* This is set if the transfer function should and in the wild_read
466 bitmap before applying the kill and gen sets. That vector knocks
467 out most of the bits in the bitmap and thus speeds up the
469 bool apply_wild_read
;
471 /* The following 4 bitvectors hold information about which positions
472 of which stores are live or dead. They are indexed by
475 /* The set of store positions that exist in this block before a wild read. */
478 /* The set of load positions that exist in this block above the
479 same position of a store. */
482 /* The set of stores that reach the top of the block without being
485 Do not represent the in if it is all ones. Note that this is
486 what the bitvector should logically be initialized to for a set
487 intersection problem. However, like the kill set, this is too
488 expensive. So initially, the in set will only be created for the
489 exit block and any block that contains a wild read. */
492 /* The set of stores that reach the bottom of the block from it's
495 Do not represent the in if it is all ones. Note that this is
496 what the bitvector should logically be initialized to for a set
497 intersection problem. However, like the kill and in set, this is
498 too expensive. So what is done is that the confluence operator
499 just initializes the vector from one of the out sets of the
500 successors of the block. */
503 /* The following bitvector is indexed by the reg number. It
504 contains the set of regs that are live at the current instruction
505 being processed. While it contains info for all of the
506 registers, only the hard registers are actually examined. It is used
507 to assure that shift and/or add sequences that are inserted do not
508 accidentally clobber live hard regs. */
512 typedef struct dse_bb_info
*bb_info_t
;
513 static alloc_pool bb_info_pool
;
515 /* Table to hold all bb_infos. */
516 static bb_info_t
*bb_table
;
518 /* There is a group_info for each rtx base that is used to reference
519 memory. There are also not many of the rtx bases because they are
520 very limited in scope. */
524 /* The actual base of the address. */
527 /* The sequential id of the base. This allows us to have a
528 canonical ordering of these that is not based on addresses. */
531 /* True if there are any positions that are to be processed
533 bool process_globally
;
535 /* True if the base of this group is either the frame_pointer or
536 hard_frame_pointer. */
539 /* A mem wrapped around the base pointer for the group in order to do
540 read dependency. It must be given BLKmode in order to encompass all
541 the possible offsets from the base. */
544 /* Canonized version of base_mem's address. */
547 /* These two sets of two bitmaps are used to keep track of how many
548 stores are actually referencing that position from this base. We
549 only do this for rtx bases as this will be used to assign
550 positions in the bitmaps for the global problem. Bit N is set in
551 store1 on the first store for offset N. Bit N is set in store2
552 for the second store to offset N. This is all we need since we
553 only care about offsets that have two or more stores for them.
555 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
556 for 0 and greater offsets.
558 There is one special case here, for stores into the stack frame,
559 we will or store1 into store2 before deciding which stores look
560 at globally. This is because stores to the stack frame that have
561 no other reads before the end of the function can also be
563 bitmap store1_n
, store1_p
, store2_n
, store2_p
;
565 /* These bitmaps keep track of offsets in this group escape this function.
566 An offset escapes if it corresponds to a named variable whose
567 addressable flag is set. */
568 bitmap escaped_n
, escaped_p
;
570 /* The positions in this bitmap have the same assignments as the in,
571 out, gen and kill bitmaps. This bitmap is all zeros except for
572 the positions that are occupied by stores for this group. */
575 /* The offset_map is used to map the offsets from this base into
576 positions in the global bitmaps. It is only created after all of
577 the all of stores have been scanned and we know which ones we
579 int *offset_map_n
, *offset_map_p
;
580 int offset_map_size_n
, offset_map_size_p
;
582 typedef struct group_info
*group_info_t
;
583 typedef const struct group_info
*const_group_info_t
;
584 static alloc_pool rtx_group_info_pool
;
586 /* Index into the rtx_group_vec. */
587 static int rtx_group_next_id
;
590 static vec
<group_info_t
> rtx_group_vec
;
593 /* This structure holds the set of changes that are being deferred
594 when removing read operation. See replace_read. */
595 struct deferred_change
598 /* The mem that is being replaced. */
601 /* The reg it is being replaced with. */
604 struct deferred_change
*next
;
607 typedef struct deferred_change
*deferred_change_t
;
608 static alloc_pool deferred_change_pool
;
610 static deferred_change_t deferred_change_list
= NULL
;
612 /* The group that holds all of the clear_alias_sets. */
613 static group_info_t clear_alias_group
;
615 /* The modes of the clear_alias_sets. */
616 static htab_t clear_alias_mode_table
;
618 /* Hash table element to look up the mode for an alias set. */
619 struct clear_alias_mode_holder
621 alias_set_type alias_set
;
625 /* This is true except if cfun->stdarg -- i.e. we cannot do
626 this for vararg functions because they play games with the frame. */
627 static bool stores_off_frame_dead_at_return
;
629 /* Counter for stats. */
630 static int globally_deleted
;
631 static int locally_deleted
;
632 static int spill_deleted
;
634 static bitmap all_blocks
;
636 /* Locations that are killed by calls in the global phase. */
637 static bitmap kill_on_calls
;
639 /* The number of bits used in the global bitmaps. */
640 static unsigned int current_position
;
642 /*----------------------------------------------------------------------------
646 ----------------------------------------------------------------------------*/
649 /* Find the entry associated with ALIAS_SET. */
651 static struct clear_alias_mode_holder
*
652 clear_alias_set_lookup (alias_set_type alias_set
)
654 struct clear_alias_mode_holder tmp_holder
;
657 tmp_holder
.alias_set
= alias_set
;
658 slot
= htab_find_slot (clear_alias_mode_table
, &tmp_holder
, NO_INSERT
);
661 return (struct clear_alias_mode_holder
*) *slot
;
665 /* Hashtable callbacks for maintaining the "bases" field of
666 store_group_info, given that the addresses are function invariants. */
668 struct invariant_group_base_hasher
: typed_noop_remove
<group_info
>
670 typedef group_info
*value_type
;
671 typedef group_info
*compare_type
;
672 static inline hashval_t
hash (const group_info
*);
673 static inline bool equal (const group_info
*, const group_info
*);
677 invariant_group_base_hasher::equal (const group_info
*gi1
,
678 const group_info
*gi2
)
680 return rtx_equal_p (gi1
->rtx_base
, gi2
->rtx_base
);
684 invariant_group_base_hasher::hash (const group_info
*gi
)
687 return hash_rtx (gi
->rtx_base
, Pmode
, &do_not_record
, NULL
, false);
690 /* Tables of group_info structures, hashed by base value. */
691 static hash_table
<invariant_group_base_hasher
> *rtx_group_table
;
694 /* Get the GROUP for BASE. Add a new group if it is not there. */
697 get_group_info (rtx base
)
699 struct group_info tmp_gi
;
705 /* Find the store_base_info structure for BASE, creating a new one
707 tmp_gi
.rtx_base
= base
;
708 slot
= rtx_group_table
->find_slot (&tmp_gi
, INSERT
);
709 gi
= (group_info_t
) *slot
;
713 if (!clear_alias_group
)
715 clear_alias_group
= gi
=
716 (group_info_t
) pool_alloc (rtx_group_info_pool
);
717 memset (gi
, 0, sizeof (struct group_info
));
718 gi
->id
= rtx_group_next_id
++;
719 gi
->store1_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
720 gi
->store1_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
721 gi
->store2_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
722 gi
->store2_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
723 gi
->escaped_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
724 gi
->escaped_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
725 gi
->group_kill
= BITMAP_ALLOC (&dse_bitmap_obstack
);
726 gi
->process_globally
= false;
727 gi
->offset_map_size_n
= 0;
728 gi
->offset_map_size_p
= 0;
729 gi
->offset_map_n
= NULL
;
730 gi
->offset_map_p
= NULL
;
731 rtx_group_vec
.safe_push (gi
);
733 return clear_alias_group
;
738 *slot
= gi
= (group_info_t
) pool_alloc (rtx_group_info_pool
);
740 gi
->id
= rtx_group_next_id
++;
741 gi
->base_mem
= gen_rtx_MEM (BLKmode
, base
);
742 gi
->canon_base_addr
= canon_rtx (base
);
743 gi
->store1_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
744 gi
->store1_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
745 gi
->store2_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
746 gi
->store2_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
747 gi
->escaped_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
748 gi
->escaped_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
749 gi
->group_kill
= BITMAP_ALLOC (&dse_bitmap_obstack
);
750 gi
->process_globally
= false;
752 (base
== frame_pointer_rtx
) || (base
== hard_frame_pointer_rtx
);
753 gi
->offset_map_size_n
= 0;
754 gi
->offset_map_size_p
= 0;
755 gi
->offset_map_n
= NULL
;
756 gi
->offset_map_p
= NULL
;
757 rtx_group_vec
.safe_push (gi
);
764 /* Initialization of data structures. */
770 globally_deleted
= 0;
773 bitmap_obstack_initialize (&dse_bitmap_obstack
);
774 gcc_obstack_init (&dse_obstack
);
776 scratch
= BITMAP_ALLOC (®_obstack
);
777 kill_on_calls
= BITMAP_ALLOC (&dse_bitmap_obstack
);
780 = create_alloc_pool ("rtx_store_info_pool",
781 sizeof (struct store_info
), 100);
783 = create_alloc_pool ("read_info_pool",
784 sizeof (struct read_info
), 100);
786 = create_alloc_pool ("insn_info_pool",
787 sizeof (struct insn_info
), 100);
789 = create_alloc_pool ("bb_info_pool",
790 sizeof (struct dse_bb_info
), 100);
792 = create_alloc_pool ("rtx_group_info_pool",
793 sizeof (struct group_info
), 100);
795 = create_alloc_pool ("deferred_change_pool",
796 sizeof (struct deferred_change
), 10);
798 rtx_group_table
= new hash_table
<invariant_group_base_hasher
> (11);
800 bb_table
= XNEWVEC (bb_info_t
, last_basic_block_for_fn (cfun
));
801 rtx_group_next_id
= 0;
803 stores_off_frame_dead_at_return
= !cfun
->stdarg
;
805 init_alias_analysis ();
807 clear_alias_group
= NULL
;
812 /*----------------------------------------------------------------------------
815 Scan all of the insns. Any random ordering of the blocks is fine.
816 Each block is scanned in forward order to accommodate cselib which
817 is used to remove stores with non-constant bases.
818 ----------------------------------------------------------------------------*/
820 /* Delete all of the store_info recs from INSN_INFO. */
823 free_store_info (insn_info_t insn_info
)
825 store_info_t store_info
= insn_info
->store_rec
;
828 store_info_t next
= store_info
->next
;
829 if (store_info
->is_large
)
830 BITMAP_FREE (store_info
->positions_needed
.large
.bmap
);
831 if (store_info
->cse_base
)
832 pool_free (cse_store_info_pool
, store_info
);
834 pool_free (rtx_store_info_pool
, store_info
);
838 insn_info
->cannot_delete
= true;
839 insn_info
->contains_cselib_groups
= false;
840 insn_info
->store_rec
= NULL
;
845 rtx_insn
*first
, *current
;
846 regset fixed_regs_live
;
848 } note_add_store_info
;
850 /* Callback for emit_inc_dec_insn_before via note_stores.
851 Check if a register is clobbered which is live afterwards. */
854 note_add_store (rtx loc
, const_rtx expr ATTRIBUTE_UNUSED
, void *data
)
857 note_add_store_info
*info
= (note_add_store_info
*) data
;
862 /* If this register is referenced by the current or an earlier insn,
863 that's OK. E.g. this applies to the register that is being incremented
864 with this addition. */
865 for (insn
= info
->first
;
866 insn
!= NEXT_INSN (info
->current
);
867 insn
= NEXT_INSN (insn
))
868 if (reg_referenced_p (loc
, PATTERN (insn
)))
871 /* If we come here, we have a clobber of a register that's only OK
872 if that register is not live. If we don't have liveness information
873 available, fail now. */
874 if (!info
->fixed_regs_live
)
876 info
->failure
= true;
879 /* Now check if this is a live fixed register. */
880 unsigned int end_regno
= END_REGNO (loc
);
881 for (unsigned int regno
= REGNO (loc
); regno
< end_regno
; ++regno
)
882 if (REGNO_REG_SET_P (info
->fixed_regs_live
, regno
))
883 info
->failure
= true;
886 /* Callback for for_each_inc_dec that emits an INSN that sets DEST to
887 SRC + SRCOFF before insn ARG. */
890 emit_inc_dec_insn_before (rtx mem ATTRIBUTE_UNUSED
,
891 rtx op ATTRIBUTE_UNUSED
,
892 rtx dest
, rtx src
, rtx srcoff
, void *arg
)
894 insn_info_t insn_info
= (insn_info_t
) arg
;
895 rtx_insn
*insn
= insn_info
->insn
, *new_insn
, *cur
;
896 note_add_store_info info
;
898 /* We can reuse all operands without copying, because we are about
899 to delete the insn that contained it. */
903 emit_insn (gen_add3_insn (dest
, src
, srcoff
));
904 new_insn
= get_insns ();
908 new_insn
= gen_move_insn (dest
, src
);
909 info
.first
= new_insn
;
910 info
.fixed_regs_live
= insn_info
->fixed_regs_live
;
911 info
.failure
= false;
912 for (cur
= new_insn
; cur
; cur
= NEXT_INSN (cur
))
915 note_stores (PATTERN (cur
), note_add_store
, &info
);
918 /* If a failure was flagged above, return 1 so that for_each_inc_dec will
919 return it immediately, communicating the failure to its caller. */
923 emit_insn_before (new_insn
, insn
);
928 /* Before we delete INSN_INFO->INSN, make sure that the auto inc/dec, if it
929 is there, is split into a separate insn.
930 Return true on success (or if there was nothing to do), false on failure. */
933 check_for_inc_dec_1 (insn_info_t insn_info
)
935 rtx_insn
*insn
= insn_info
->insn
;
936 rtx note
= find_reg_note (insn
, REG_INC
, NULL_RTX
);
938 return for_each_inc_dec (PATTERN (insn
), emit_inc_dec_insn_before
,
944 /* Entry point for postreload. If you work on reload_cse, or you need this
945 anywhere else, consider if you can provide register liveness information
946 and add a parameter to this function so that it can be passed down in
947 insn_info.fixed_regs_live. */
949 check_for_inc_dec (rtx_insn
*insn
)
951 struct insn_info insn_info
;
954 insn_info
.insn
= insn
;
955 insn_info
.fixed_regs_live
= NULL
;
956 note
= find_reg_note (insn
, REG_INC
, NULL_RTX
);
958 return for_each_inc_dec (PATTERN (insn
), emit_inc_dec_insn_before
,
963 /* Delete the insn and free all of the fields inside INSN_INFO. */
966 delete_dead_store_insn (insn_info_t insn_info
)
968 read_info_t read_info
;
973 if (!check_for_inc_dec_1 (insn_info
))
975 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
977 fprintf (dump_file
, "Locally deleting insn %d ",
978 INSN_UID (insn_info
->insn
));
979 if (insn_info
->store_rec
->alias_set
)
980 fprintf (dump_file
, "alias set %d\n",
981 (int) insn_info
->store_rec
->alias_set
);
983 fprintf (dump_file
, "\n");
986 free_store_info (insn_info
);
987 read_info
= insn_info
->read_rec
;
991 read_info_t next
= read_info
->next
;
992 pool_free (read_info_pool
, read_info
);
995 insn_info
->read_rec
= NULL
;
997 delete_insn (insn_info
->insn
);
999 insn_info
->insn
= NULL
;
1001 insn_info
->wild_read
= false;
1004 /* Return whether DECL, a local variable, can possibly escape the current
1008 local_variable_can_escape (tree decl
)
1010 if (TREE_ADDRESSABLE (decl
))
1013 /* If this is a partitioned variable, we need to consider all the variables
1014 in the partition. This is necessary because a store into one of them can
1015 be replaced with a store into another and this may not change the outcome
1016 of the escape analysis. */
1017 if (cfun
->gimple_df
->decls_to_pointers
!= NULL
)
1019 tree
*namep
= cfun
->gimple_df
->decls_to_pointers
->get (decl
);
1021 return TREE_ADDRESSABLE (*namep
);
1027 /* Return whether EXPR can possibly escape the current function scope. */
1030 can_escape (tree expr
)
1035 base
= get_base_address (expr
);
1037 && !may_be_aliased (base
)
1038 && !(TREE_CODE (base
) == VAR_DECL
1039 && !DECL_EXTERNAL (base
)
1040 && !TREE_STATIC (base
)
1041 && local_variable_can_escape (base
)))
1046 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
1047 OFFSET and WIDTH. */
1050 set_usage_bits (group_info_t group
, HOST_WIDE_INT offset
, HOST_WIDE_INT width
,
1054 bool expr_escapes
= can_escape (expr
);
1055 if (offset
> -MAX_OFFSET
&& offset
+ width
< MAX_OFFSET
)
1056 for (i
=offset
; i
<offset
+width
; i
++)
1064 store1
= group
->store1_n
;
1065 store2
= group
->store2_n
;
1066 escaped
= group
->escaped_n
;
1071 store1
= group
->store1_p
;
1072 store2
= group
->store2_p
;
1073 escaped
= group
->escaped_p
;
1077 if (!bitmap_set_bit (store1
, ai
))
1078 bitmap_set_bit (store2
, ai
);
1083 if (group
->offset_map_size_n
< ai
)
1084 group
->offset_map_size_n
= ai
;
1088 if (group
->offset_map_size_p
< ai
)
1089 group
->offset_map_size_p
= ai
;
1093 bitmap_set_bit (escaped
, ai
);
1098 reset_active_stores (void)
1100 active_local_stores
= NULL
;
1101 active_local_stores_len
= 0;
1104 /* Free all READ_REC of the LAST_INSN of BB_INFO. */
1107 free_read_records (bb_info_t bb_info
)
1109 insn_info_t insn_info
= bb_info
->last_insn
;
1110 read_info_t
*ptr
= &insn_info
->read_rec
;
1113 read_info_t next
= (*ptr
)->next
;
1114 if ((*ptr
)->alias_set
== 0)
1116 pool_free (read_info_pool
, *ptr
);
1120 ptr
= &(*ptr
)->next
;
1124 /* Set the BB_INFO so that the last insn is marked as a wild read. */
1127 add_wild_read (bb_info_t bb_info
)
1129 insn_info_t insn_info
= bb_info
->last_insn
;
1130 insn_info
->wild_read
= true;
1131 free_read_records (bb_info
);
1132 reset_active_stores ();
1135 /* Set the BB_INFO so that the last insn is marked as a wild read of
1136 non-frame locations. */
1139 add_non_frame_wild_read (bb_info_t bb_info
)
1141 insn_info_t insn_info
= bb_info
->last_insn
;
1142 insn_info
->non_frame_wild_read
= true;
1143 free_read_records (bb_info
);
1144 reset_active_stores ();
1147 /* Return true if X is a constant or one of the registers that behave
1148 as a constant over the life of a function. This is equivalent to
1149 !rtx_varies_p for memory addresses. */
1152 const_or_frame_p (rtx x
)
1157 if (GET_CODE (x
) == REG
)
1159 /* Note that we have to test for the actual rtx used for the frame
1160 and arg pointers and not just the register number in case we have
1161 eliminated the frame and/or arg pointer and are using it
1163 if (x
== frame_pointer_rtx
|| x
== hard_frame_pointer_rtx
1164 /* The arg pointer varies if it is not a fixed register. */
1165 || (x
== arg_pointer_rtx
&& fixed_regs
[ARG_POINTER_REGNUM
])
1166 || x
== pic_offset_table_rtx
)
1174 /* Take all reasonable action to put the address of MEM into the form
1175 that we can do analysis on.
1177 The gold standard is to get the address into the form: address +
1178 OFFSET where address is something that rtx_varies_p considers a
1179 constant. When we can get the address in this form, we can do
1180 global analysis on it. Note that for constant bases, address is
1181 not actually returned, only the group_id. The address can be
1184 If that fails, we try cselib to get a value we can at least use
1185 locally. If that fails we return false.
1187 The GROUP_ID is set to -1 for cselib bases and the index of the
1188 group for non_varying bases.
1190 FOR_READ is true if this is a mem read and false if not. */
1193 canon_address (rtx mem
,
1194 alias_set_type
*alias_set_out
,
1196 HOST_WIDE_INT
*offset
,
1199 machine_mode address_mode
= get_address_mode (mem
);
1200 rtx mem_address
= XEXP (mem
, 0);
1201 rtx expanded_address
, address
;
1206 cselib_lookup (mem_address
, address_mode
, 1, GET_MODE (mem
));
1208 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1210 fprintf (dump_file
, " mem: ");
1211 print_inline_rtx (dump_file
, mem_address
, 0);
1212 fprintf (dump_file
, "\n");
1215 /* First see if just canon_rtx (mem_address) is const or frame,
1216 if not, try cselib_expand_value_rtx and call canon_rtx on that. */
1218 for (expanded
= 0; expanded
< 2; expanded
++)
1222 /* Use cselib to replace all of the reg references with the full
1223 expression. This will take care of the case where we have
1225 r_x = base + offset;
1230 val = *(base + offset); */
1232 expanded_address
= cselib_expand_value_rtx (mem_address
,
1235 /* If this fails, just go with the address from first
1237 if (!expanded_address
)
1241 expanded_address
= mem_address
;
1243 /* Split the address into canonical BASE + OFFSET terms. */
1244 address
= canon_rtx (expanded_address
);
1248 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1252 fprintf (dump_file
, "\n after cselib_expand address: ");
1253 print_inline_rtx (dump_file
, expanded_address
, 0);
1254 fprintf (dump_file
, "\n");
1257 fprintf (dump_file
, "\n after canon_rtx address: ");
1258 print_inline_rtx (dump_file
, address
, 0);
1259 fprintf (dump_file
, "\n");
1262 if (GET_CODE (address
) == CONST
)
1263 address
= XEXP (address
, 0);
1265 if (GET_CODE (address
) == PLUS
1266 && CONST_INT_P (XEXP (address
, 1)))
1268 *offset
= INTVAL (XEXP (address
, 1));
1269 address
= XEXP (address
, 0);
1272 if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem
))
1273 && const_or_frame_p (address
))
1275 group_info_t group
= get_group_info (address
);
1277 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1278 fprintf (dump_file
, " gid=%d offset=%d \n",
1279 group
->id
, (int)*offset
);
1281 *group_id
= group
->id
;
1286 *base
= cselib_lookup (address
, address_mode
, true, GET_MODE (mem
));
1291 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1292 fprintf (dump_file
, " no cselib val - should be a wild read.\n");
1295 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1296 fprintf (dump_file
, " varying cselib base=%u:%u offset = %d\n",
1297 (*base
)->uid
, (*base
)->hash
, (int)*offset
);
1302 /* Clear the rhs field from the active_local_stores array. */
1305 clear_rhs_from_active_local_stores (void)
1307 insn_info_t ptr
= active_local_stores
;
1311 store_info_t store_info
= ptr
->store_rec
;
1312 /* Skip the clobbers. */
1313 while (!store_info
->is_set
)
1314 store_info
= store_info
->next
;
1316 store_info
->rhs
= NULL
;
1317 store_info
->const_rhs
= NULL
;
1319 ptr
= ptr
->next_local_store
;
1324 /* Mark byte POS bytes from the beginning of store S_INFO as unneeded. */
1327 set_position_unneeded (store_info_t s_info
, int pos
)
1329 if (__builtin_expect (s_info
->is_large
, false))
1331 if (bitmap_set_bit (s_info
->positions_needed
.large
.bmap
, pos
))
1332 s_info
->positions_needed
.large
.count
++;
1335 s_info
->positions_needed
.small_bitmask
1336 &= ~(((unsigned HOST_WIDE_INT
) 1) << pos
);
1339 /* Mark the whole store S_INFO as unneeded. */
1342 set_all_positions_unneeded (store_info_t s_info
)
1344 if (__builtin_expect (s_info
->is_large
, false))
1346 int pos
, end
= s_info
->end
- s_info
->begin
;
1347 for (pos
= 0; pos
< end
; pos
++)
1348 bitmap_set_bit (s_info
->positions_needed
.large
.bmap
, pos
);
1349 s_info
->positions_needed
.large
.count
= end
;
1352 s_info
->positions_needed
.small_bitmask
= (unsigned HOST_WIDE_INT
) 0;
1355 /* Return TRUE if any bytes from S_INFO store are needed. */
1358 any_positions_needed_p (store_info_t s_info
)
1360 if (__builtin_expect (s_info
->is_large
, false))
1361 return (s_info
->positions_needed
.large
.count
1362 < s_info
->end
- s_info
->begin
);
1364 return (s_info
->positions_needed
.small_bitmask
1365 != (unsigned HOST_WIDE_INT
) 0);
1368 /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
1369 store are needed. */
1372 all_positions_needed_p (store_info_t s_info
, int start
, int width
)
1374 if (__builtin_expect (s_info
->is_large
, false))
1376 int end
= start
+ width
;
1378 if (bitmap_bit_p (s_info
->positions_needed
.large
.bmap
, start
++))
1384 unsigned HOST_WIDE_INT mask
= lowpart_bitmask (width
) << start
;
1385 return (s_info
->positions_needed
.small_bitmask
& mask
) == mask
;
1390 static rtx
get_stored_val (store_info_t
, machine_mode
, HOST_WIDE_INT
,
1391 HOST_WIDE_INT
, basic_block
, bool);
1394 /* BODY is an instruction pattern that belongs to INSN. Return 1 if
1395 there is a candidate store, after adding it to the appropriate
1396 local store group if so. */
1399 record_store (rtx body
, bb_info_t bb_info
)
1401 rtx mem
, rhs
, const_rhs
, mem_addr
;
1402 HOST_WIDE_INT offset
= 0;
1403 HOST_WIDE_INT width
= 0;
1404 alias_set_type spill_alias_set
;
1405 insn_info_t insn_info
= bb_info
->last_insn
;
1406 store_info_t store_info
= NULL
;
1408 cselib_val
*base
= NULL
;
1409 insn_info_t ptr
, last
, redundant_reason
;
1410 bool store_is_unused
;
1412 if (GET_CODE (body
) != SET
&& GET_CODE (body
) != CLOBBER
)
1415 mem
= SET_DEST (body
);
1417 /* If this is not used, then this cannot be used to keep the insn
1418 from being deleted. On the other hand, it does provide something
1419 that can be used to prove that another store is dead. */
1421 = (find_reg_note (insn_info
->insn
, REG_UNUSED
, mem
) != NULL
);
1423 /* Check whether that value is a suitable memory location. */
1426 /* If the set or clobber is unused, then it does not effect our
1427 ability to get rid of the entire insn. */
1428 if (!store_is_unused
)
1429 insn_info
->cannot_delete
= true;
1433 /* At this point we know mem is a mem. */
1434 if (GET_MODE (mem
) == BLKmode
)
1436 if (GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
1438 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1439 fprintf (dump_file
, " adding wild read for (clobber (mem:BLK (scratch))\n");
1440 add_wild_read (bb_info
);
1441 insn_info
->cannot_delete
= true;
1444 /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
1445 as memset (addr, 0, 36); */
1446 else if (!MEM_SIZE_KNOWN_P (mem
)
1447 || MEM_SIZE (mem
) <= 0
1448 || MEM_SIZE (mem
) > MAX_OFFSET
1449 || GET_CODE (body
) != SET
1450 || !CONST_INT_P (SET_SRC (body
)))
1452 if (!store_is_unused
)
1454 /* If the set or clobber is unused, then it does not effect our
1455 ability to get rid of the entire insn. */
1456 insn_info
->cannot_delete
= true;
1457 clear_rhs_from_active_local_stores ();
1463 /* We can still process a volatile mem, we just cannot delete it. */
1464 if (MEM_VOLATILE_P (mem
))
1465 insn_info
->cannot_delete
= true;
1467 if (!canon_address (mem
, &spill_alias_set
, &group_id
, &offset
, &base
))
1469 clear_rhs_from_active_local_stores ();
1473 if (GET_MODE (mem
) == BLKmode
)
1474 width
= MEM_SIZE (mem
);
1476 width
= GET_MODE_SIZE (GET_MODE (mem
));
1478 if (spill_alias_set
)
1480 bitmap store1
= clear_alias_group
->store1_p
;
1481 bitmap store2
= clear_alias_group
->store2_p
;
1483 gcc_assert (GET_MODE (mem
) != BLKmode
);
1485 if (!bitmap_set_bit (store1
, spill_alias_set
))
1486 bitmap_set_bit (store2
, spill_alias_set
);
1488 if (clear_alias_group
->offset_map_size_p
< spill_alias_set
)
1489 clear_alias_group
->offset_map_size_p
= spill_alias_set
;
1491 store_info
= (store_info_t
) pool_alloc (rtx_store_info_pool
);
1493 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1494 fprintf (dump_file
, " processing spill store %d(%s)\n",
1495 (int) spill_alias_set
, GET_MODE_NAME (GET_MODE (mem
)));
1497 else if (group_id
>= 0)
1499 /* In the restrictive case where the base is a constant or the
1500 frame pointer we can do global analysis. */
1503 = rtx_group_vec
[group_id
];
1504 tree expr
= MEM_EXPR (mem
);
1506 store_info
= (store_info_t
) pool_alloc (rtx_store_info_pool
);
1507 set_usage_bits (group
, offset
, width
, expr
);
1509 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1510 fprintf (dump_file
, " processing const base store gid=%d[%d..%d)\n",
1511 group_id
, (int)offset
, (int)(offset
+width
));
1515 if (may_be_sp_based_p (XEXP (mem
, 0)))
1516 insn_info
->stack_pointer_based
= true;
1517 insn_info
->contains_cselib_groups
= true;
1519 store_info
= (store_info_t
) pool_alloc (cse_store_info_pool
);
1522 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1523 fprintf (dump_file
, " processing cselib store [%d..%d)\n",
1524 (int)offset
, (int)(offset
+width
));
1527 const_rhs
= rhs
= NULL_RTX
;
1528 if (GET_CODE (body
) == SET
1529 /* No place to keep the value after ra. */
1530 && !reload_completed
1531 && (REG_P (SET_SRC (body
))
1532 || GET_CODE (SET_SRC (body
)) == SUBREG
1533 || CONSTANT_P (SET_SRC (body
)))
1534 && !MEM_VOLATILE_P (mem
)
1535 /* Sometimes the store and reload is used for truncation and
1537 && !(FLOAT_MODE_P (GET_MODE (mem
)) && (flag_float_store
)))
1539 rhs
= SET_SRC (body
);
1540 if (CONSTANT_P (rhs
))
1542 else if (body
== PATTERN (insn_info
->insn
))
1544 rtx tem
= find_reg_note (insn_info
->insn
, REG_EQUAL
, NULL_RTX
);
1545 if (tem
&& CONSTANT_P (XEXP (tem
, 0)))
1546 const_rhs
= XEXP (tem
, 0);
1548 if (const_rhs
== NULL_RTX
&& REG_P (rhs
))
1550 rtx tem
= cselib_expand_value_rtx (rhs
, scratch
, 5);
1552 if (tem
&& CONSTANT_P (tem
))
1557 /* Check to see if this stores causes some other stores to be
1559 ptr
= active_local_stores
;
1561 redundant_reason
= NULL
;
1562 mem
= canon_rtx (mem
);
1563 /* For alias_set != 0 canon_true_dependence should be never called. */
1564 if (spill_alias_set
)
1565 mem_addr
= NULL_RTX
;
1569 mem_addr
= base
->val_rtx
;
1573 = rtx_group_vec
[group_id
];
1574 mem_addr
= group
->canon_base_addr
;
1576 /* get_addr can only handle VALUE but cannot handle expr like:
1577 VALUE + OFFSET, so call get_addr to get original addr for
1578 mem_addr before plus_constant. */
1579 mem_addr
= get_addr (mem_addr
);
1581 mem_addr
= plus_constant (get_address_mode (mem
), mem_addr
, offset
);
1586 insn_info_t next
= ptr
->next_local_store
;
1587 store_info_t s_info
= ptr
->store_rec
;
1590 /* Skip the clobbers. We delete the active insn if this insn
1591 shadows the set. To have been put on the active list, it
1592 has exactly on set. */
1593 while (!s_info
->is_set
)
1594 s_info
= s_info
->next
;
1596 if (s_info
->alias_set
!= spill_alias_set
)
1598 else if (s_info
->alias_set
)
1600 struct clear_alias_mode_holder
*entry
1601 = clear_alias_set_lookup (s_info
->alias_set
);
1602 /* Generally, spills cannot be processed if and of the
1603 references to the slot have a different mode. But if
1604 we are in the same block and mode is exactly the same
1605 between this store and one before in the same block,
1606 we can still delete it. */
1607 if ((GET_MODE (mem
) == GET_MODE (s_info
->mem
))
1608 && (GET_MODE (mem
) == entry
->mode
))
1611 set_all_positions_unneeded (s_info
);
1613 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1614 fprintf (dump_file
, " trying spill store in insn=%d alias_set=%d\n",
1615 INSN_UID (ptr
->insn
), (int) s_info
->alias_set
);
1617 else if ((s_info
->group_id
== group_id
)
1618 && (s_info
->cse_base
== base
))
1621 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1622 fprintf (dump_file
, " trying store in insn=%d gid=%d[%d..%d)\n",
1623 INSN_UID (ptr
->insn
), s_info
->group_id
,
1624 (int)s_info
->begin
, (int)s_info
->end
);
1626 /* Even if PTR won't be eliminated as unneeded, if both
1627 PTR and this insn store the same constant value, we might
1628 eliminate this insn instead. */
1629 if (s_info
->const_rhs
1631 && offset
>= s_info
->begin
1632 && offset
+ width
<= s_info
->end
1633 && all_positions_needed_p (s_info
, offset
- s_info
->begin
,
1636 if (GET_MODE (mem
) == BLKmode
)
1638 if (GET_MODE (s_info
->mem
) == BLKmode
1639 && s_info
->const_rhs
== const_rhs
)
1640 redundant_reason
= ptr
;
1642 else if (s_info
->const_rhs
== const0_rtx
1643 && const_rhs
== const0_rtx
)
1644 redundant_reason
= ptr
;
1649 val
= get_stored_val (s_info
, GET_MODE (mem
),
1650 offset
, offset
+ width
,
1651 BLOCK_FOR_INSN (insn_info
->insn
),
1653 if (get_insns () != NULL
)
1656 if (val
&& rtx_equal_p (val
, const_rhs
))
1657 redundant_reason
= ptr
;
1661 for (i
= MAX (offset
, s_info
->begin
);
1662 i
< offset
+ width
&& i
< s_info
->end
;
1664 set_position_unneeded (s_info
, i
- s_info
->begin
);
1666 else if (s_info
->rhs
)
1667 /* Need to see if it is possible for this store to overwrite
1668 the value of store_info. If it is, set the rhs to NULL to
1669 keep it from being used to remove a load. */
1671 if (canon_true_dependence (s_info
->mem
,
1672 GET_MODE (s_info
->mem
),
1677 s_info
->const_rhs
= NULL
;
1681 /* An insn can be deleted if every position of every one of
1682 its s_infos is zero. */
1683 if (any_positions_needed_p (s_info
))
1688 insn_info_t insn_to_delete
= ptr
;
1690 active_local_stores_len
--;
1692 last
->next_local_store
= ptr
->next_local_store
;
1694 active_local_stores
= ptr
->next_local_store
;
1696 if (!insn_to_delete
->cannot_delete
)
1697 delete_dead_store_insn (insn_to_delete
);
1705 /* Finish filling in the store_info. */
1706 store_info
->next
= insn_info
->store_rec
;
1707 insn_info
->store_rec
= store_info
;
1708 store_info
->mem
= mem
;
1709 store_info
->alias_set
= spill_alias_set
;
1710 store_info
->mem_addr
= mem_addr
;
1711 store_info
->cse_base
= base
;
1712 if (width
> HOST_BITS_PER_WIDE_INT
)
1714 store_info
->is_large
= true;
1715 store_info
->positions_needed
.large
.count
= 0;
1716 store_info
->positions_needed
.large
.bmap
= BITMAP_ALLOC (&dse_bitmap_obstack
);
1720 store_info
->is_large
= false;
1721 store_info
->positions_needed
.small_bitmask
= lowpart_bitmask (width
);
1723 store_info
->group_id
= group_id
;
1724 store_info
->begin
= offset
;
1725 store_info
->end
= offset
+ width
;
1726 store_info
->is_set
= GET_CODE (body
) == SET
;
1727 store_info
->rhs
= rhs
;
1728 store_info
->const_rhs
= const_rhs
;
1729 store_info
->redundant_reason
= redundant_reason
;
1731 /* If this is a clobber, we return 0. We will only be able to
1732 delete this insn if there is only one store USED store, but we
1733 can use the clobber to delete other stores earlier. */
1734 return store_info
->is_set
? 1 : 0;
1739 dump_insn_info (const char * start
, insn_info_t insn_info
)
1741 fprintf (dump_file
, "%s insn=%d %s\n", start
,
1742 INSN_UID (insn_info
->insn
),
1743 insn_info
->store_rec
? "has store" : "naked");
1747 /* If the modes are different and the value's source and target do not
1748 line up, we need to extract the value from lower part of the rhs of
1749 the store, shift it, and then put it into a form that can be shoved
1750 into the read_insn. This function generates a right SHIFT of a
1751 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The
1752 shift sequence is returned or NULL if we failed to find a
1756 find_shift_sequence (int access_size
,
1757 store_info_t store_info
,
1758 machine_mode read_mode
,
1759 int shift
, bool speed
, bool require_cst
)
1761 machine_mode store_mode
= GET_MODE (store_info
->mem
);
1762 machine_mode new_mode
;
1763 rtx read_reg
= NULL
;
1765 /* Some machines like the x86 have shift insns for each size of
1766 operand. Other machines like the ppc or the ia-64 may only have
1767 shift insns that shift values within 32 or 64 bit registers.
1768 This loop tries to find the smallest shift insn that will right
1769 justify the value we want to read but is available in one insn on
1772 for (new_mode
= smallest_mode_for_size (access_size
* BITS_PER_UNIT
,
1774 GET_MODE_BITSIZE (new_mode
) <= BITS_PER_WORD
;
1775 new_mode
= GET_MODE_WIDER_MODE (new_mode
))
1777 rtx target
, new_reg
, new_lhs
;
1778 rtx_insn
*shift_seq
, *insn
;
1781 /* If a constant was stored into memory, try to simplify it here,
1782 otherwise the cost of the shift might preclude this optimization
1783 e.g. at -Os, even when no actual shift will be needed. */
1784 if (store_info
->const_rhs
)
1786 unsigned int byte
= subreg_lowpart_offset (new_mode
, store_mode
);
1787 rtx ret
= simplify_subreg (new_mode
, store_info
->const_rhs
,
1789 if (ret
&& CONSTANT_P (ret
))
1791 ret
= simplify_const_binary_operation (LSHIFTRT
, new_mode
,
1792 ret
, GEN_INT (shift
));
1793 if (ret
&& CONSTANT_P (ret
))
1795 byte
= subreg_lowpart_offset (read_mode
, new_mode
);
1796 ret
= simplify_subreg (read_mode
, ret
, new_mode
, byte
);
1797 if (ret
&& CONSTANT_P (ret
)
1798 && set_src_cost (ret
, speed
) <= COSTS_N_INSNS (1))
1807 /* Try a wider mode if truncating the store mode to NEW_MODE
1808 requires a real instruction. */
1809 if (GET_MODE_BITSIZE (new_mode
) < GET_MODE_BITSIZE (store_mode
)
1810 && !TRULY_NOOP_TRUNCATION_MODES_P (new_mode
, store_mode
))
1813 /* Also try a wider mode if the necessary punning is either not
1814 desirable or not possible. */
1815 if (!CONSTANT_P (store_info
->rhs
)
1816 && !MODES_TIEABLE_P (new_mode
, store_mode
))
1819 new_reg
= gen_reg_rtx (new_mode
);
1823 /* In theory we could also check for an ashr. Ian Taylor knows
1824 of one dsp where the cost of these two was not the same. But
1825 this really is a rare case anyway. */
1826 target
= expand_binop (new_mode
, lshr_optab
, new_reg
,
1827 GEN_INT (shift
), new_reg
, 1, OPTAB_DIRECT
);
1829 shift_seq
= get_insns ();
1832 if (target
!= new_reg
|| shift_seq
== NULL
)
1836 for (insn
= shift_seq
; insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
1838 cost
+= insn_rtx_cost (PATTERN (insn
), speed
);
1840 /* The computation up to here is essentially independent
1841 of the arguments and could be precomputed. It may
1842 not be worth doing so. We could precompute if
1843 worthwhile or at least cache the results. The result
1844 technically depends on both SHIFT and ACCESS_SIZE,
1845 but in practice the answer will depend only on ACCESS_SIZE. */
1847 if (cost
> COSTS_N_INSNS (1))
1850 new_lhs
= extract_low_bits (new_mode
, store_mode
,
1851 copy_rtx (store_info
->rhs
));
1852 if (new_lhs
== NULL_RTX
)
1855 /* We found an acceptable shift. Generate a move to
1856 take the value from the store and put it into the
1857 shift pseudo, then shift it, then generate another
1858 move to put in into the target of the read. */
1859 emit_move_insn (new_reg
, new_lhs
);
1860 emit_insn (shift_seq
);
1861 read_reg
= extract_low_bits (read_mode
, new_mode
, new_reg
);
1869 /* Call back for note_stores to find the hard regs set or clobbered by
1870 insn. Data is a bitmap of the hardregs set so far. */
1873 look_for_hardregs (rtx x
, const_rtx pat ATTRIBUTE_UNUSED
, void *data
)
1875 bitmap regs_set
= (bitmap
) data
;
1878 && HARD_REGISTER_P (x
))
1879 bitmap_set_range (regs_set
, REGNO (x
), REG_NREGS (x
));
1882 /* Helper function for replace_read and record_store.
1883 Attempt to return a value stored in STORE_INFO, from READ_BEGIN
1884 to one before READ_END bytes read in READ_MODE. Return NULL
1885 if not successful. If REQUIRE_CST is true, return always constant. */
1888 get_stored_val (store_info_t store_info
, machine_mode read_mode
,
1889 HOST_WIDE_INT read_begin
, HOST_WIDE_INT read_end
,
1890 basic_block bb
, bool require_cst
)
1892 machine_mode store_mode
= GET_MODE (store_info
->mem
);
1894 int access_size
; /* In bytes. */
1897 /* To get here the read is within the boundaries of the write so
1898 shift will never be negative. Start out with the shift being in
1900 if (store_mode
== BLKmode
)
1902 else if (BYTES_BIG_ENDIAN
)
1903 shift
= store_info
->end
- read_end
;
1905 shift
= read_begin
- store_info
->begin
;
1907 access_size
= shift
+ GET_MODE_SIZE (read_mode
);
1909 /* From now on it is bits. */
1910 shift
*= BITS_PER_UNIT
;
1913 read_reg
= find_shift_sequence (access_size
, store_info
, read_mode
, shift
,
1914 optimize_bb_for_speed_p (bb
),
1916 else if (store_mode
== BLKmode
)
1918 /* The store is a memset (addr, const_val, const_size). */
1919 gcc_assert (CONST_INT_P (store_info
->rhs
));
1920 store_mode
= int_mode_for_mode (read_mode
);
1921 if (store_mode
== BLKmode
)
1922 read_reg
= NULL_RTX
;
1923 else if (store_info
->rhs
== const0_rtx
)
1924 read_reg
= extract_low_bits (read_mode
, store_mode
, const0_rtx
);
1925 else if (GET_MODE_BITSIZE (store_mode
) > HOST_BITS_PER_WIDE_INT
1926 || BITS_PER_UNIT
>= HOST_BITS_PER_WIDE_INT
)
1927 read_reg
= NULL_RTX
;
1930 unsigned HOST_WIDE_INT c
1931 = INTVAL (store_info
->rhs
)
1932 & (((HOST_WIDE_INT
) 1 << BITS_PER_UNIT
) - 1);
1933 int shift
= BITS_PER_UNIT
;
1934 while (shift
< HOST_BITS_PER_WIDE_INT
)
1939 read_reg
= gen_int_mode (c
, store_mode
);
1940 read_reg
= extract_low_bits (read_mode
, store_mode
, read_reg
);
1943 else if (store_info
->const_rhs
1945 || GET_MODE_CLASS (read_mode
) != GET_MODE_CLASS (store_mode
)))
1946 read_reg
= extract_low_bits (read_mode
, store_mode
,
1947 copy_rtx (store_info
->const_rhs
));
1949 read_reg
= extract_low_bits (read_mode
, store_mode
,
1950 copy_rtx (store_info
->rhs
));
1951 if (require_cst
&& read_reg
&& !CONSTANT_P (read_reg
))
1952 read_reg
= NULL_RTX
;
1956 /* Take a sequence of:
1979 Depending on the alignment and the mode of the store and
1983 The STORE_INFO and STORE_INSN are for the store and READ_INFO
1984 and READ_INSN are for the read. Return true if the replacement
1988 replace_read (store_info_t store_info
, insn_info_t store_insn
,
1989 read_info_t read_info
, insn_info_t read_insn
, rtx
*loc
,
1992 machine_mode store_mode
= GET_MODE (store_info
->mem
);
1993 machine_mode read_mode
= GET_MODE (read_info
->mem
);
1994 rtx_insn
*insns
, *this_insn
;
2001 /* Create a sequence of instructions to set up the read register.
2002 This sequence goes immediately before the store and its result
2003 is read by the load.
2005 We need to keep this in perspective. We are replacing a read
2006 with a sequence of insns, but the read will almost certainly be
2007 in cache, so it is not going to be an expensive one. Thus, we
2008 are not willing to do a multi insn shift or worse a subroutine
2009 call to get rid of the read. */
2010 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2011 fprintf (dump_file
, "trying to replace %smode load in insn %d"
2012 " from %smode store in insn %d\n",
2013 GET_MODE_NAME (read_mode
), INSN_UID (read_insn
->insn
),
2014 GET_MODE_NAME (store_mode
), INSN_UID (store_insn
->insn
));
2016 bb
= BLOCK_FOR_INSN (read_insn
->insn
);
2017 read_reg
= get_stored_val (store_info
,
2018 read_mode
, read_info
->begin
, read_info
->end
,
2020 if (read_reg
== NULL_RTX
)
2023 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2024 fprintf (dump_file
, " -- could not extract bits of stored value\n");
2027 /* Force the value into a new register so that it won't be clobbered
2028 between the store and the load. */
2029 read_reg
= copy_to_mode_reg (read_mode
, read_reg
);
2030 insns
= get_insns ();
2033 if (insns
!= NULL_RTX
)
2035 /* Now we have to scan the set of new instructions to see if the
2036 sequence contains and sets of hardregs that happened to be
2037 live at this point. For instance, this can happen if one of
2038 the insns sets the CC and the CC happened to be live at that
2039 point. This does occasionally happen, see PR 37922. */
2040 bitmap regs_set
= BITMAP_ALLOC (®_obstack
);
2042 for (this_insn
= insns
; this_insn
!= NULL_RTX
; this_insn
= NEXT_INSN (this_insn
))
2043 note_stores (PATTERN (this_insn
), look_for_hardregs
, regs_set
);
2045 bitmap_and_into (regs_set
, regs_live
);
2046 if (!bitmap_empty_p (regs_set
))
2048 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2051 "abandoning replacement because sequence clobbers live hardregs:");
2052 df_print_regset (dump_file
, regs_set
);
2055 BITMAP_FREE (regs_set
);
2058 BITMAP_FREE (regs_set
);
2061 if (validate_change (read_insn
->insn
, loc
, read_reg
, 0))
2063 deferred_change_t deferred_change
=
2064 (deferred_change_t
) pool_alloc (deferred_change_pool
);
2066 /* Insert this right before the store insn where it will be safe
2067 from later insns that might change it before the read. */
2068 emit_insn_before (insns
, store_insn
->insn
);
2070 /* And now for the kludge part: cselib croaks if you just
2071 return at this point. There are two reasons for this:
2073 1) Cselib has an idea of how many pseudos there are and
2074 that does not include the new ones we just added.
2076 2) Cselib does not know about the move insn we added
2077 above the store_info, and there is no way to tell it
2078 about it, because it has "moved on".
2080 Problem (1) is fixable with a certain amount of engineering.
2081 Problem (2) is requires starting the bb from scratch. This
2084 So we are just going to have to lie. The move/extraction
2085 insns are not really an issue, cselib did not see them. But
2086 the use of the new pseudo read_insn is a real problem because
2087 cselib has not scanned this insn. The way that we solve this
2088 problem is that we are just going to put the mem back for now
2089 and when we are finished with the block, we undo this. We
2090 keep a table of mems to get rid of. At the end of the basic
2091 block we can put them back. */
2093 *loc
= read_info
->mem
;
2094 deferred_change
->next
= deferred_change_list
;
2095 deferred_change_list
= deferred_change
;
2096 deferred_change
->loc
= loc
;
2097 deferred_change
->reg
= read_reg
;
2099 /* Get rid of the read_info, from the point of view of the
2100 rest of dse, play like this read never happened. */
2101 read_insn
->read_rec
= read_info
->next
;
2102 pool_free (read_info_pool
, read_info
);
2103 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2105 fprintf (dump_file
, " -- replaced the loaded MEM with ");
2106 print_simple_rtl (dump_file
, read_reg
);
2107 fprintf (dump_file
, "\n");
2113 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2115 fprintf (dump_file
, " -- replacing the loaded MEM with ");
2116 print_simple_rtl (dump_file
, read_reg
);
2117 fprintf (dump_file
, " led to an invalid instruction\n");
2123 /* Check the address of MEM *LOC and kill any appropriate stores that may
2127 check_mem_read_rtx (rtx
*loc
, bb_info_t bb_info
)
2129 rtx mem
= *loc
, mem_addr
;
2130 insn_info_t insn_info
;
2131 HOST_WIDE_INT offset
= 0;
2132 HOST_WIDE_INT width
= 0;
2133 alias_set_type spill_alias_set
= 0;
2134 cselib_val
*base
= NULL
;
2136 read_info_t read_info
;
2138 insn_info
= bb_info
->last_insn
;
2140 if ((MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2141 || (MEM_VOLATILE_P (mem
)))
2143 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2144 fprintf (dump_file
, " adding wild read, volatile or barrier.\n");
2145 add_wild_read (bb_info
);
2146 insn_info
->cannot_delete
= true;
2150 /* If it is reading readonly mem, then there can be no conflict with
2152 if (MEM_READONLY_P (mem
))
2155 if (!canon_address (mem
, &spill_alias_set
, &group_id
, &offset
, &base
))
2157 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2158 fprintf (dump_file
, " adding wild read, canon_address failure.\n");
2159 add_wild_read (bb_info
);
2163 if (GET_MODE (mem
) == BLKmode
)
2166 width
= GET_MODE_SIZE (GET_MODE (mem
));
2168 read_info
= (read_info_t
) pool_alloc (read_info_pool
);
2169 read_info
->group_id
= group_id
;
2170 read_info
->mem
= mem
;
2171 read_info
->alias_set
= spill_alias_set
;
2172 read_info
->begin
= offset
;
2173 read_info
->end
= offset
+ width
;
2174 read_info
->next
= insn_info
->read_rec
;
2175 insn_info
->read_rec
= read_info
;
2176 /* For alias_set != 0 canon_true_dependence should be never called. */
2177 if (spill_alias_set
)
2178 mem_addr
= NULL_RTX
;
2182 mem_addr
= base
->val_rtx
;
2186 = rtx_group_vec
[group_id
];
2187 mem_addr
= group
->canon_base_addr
;
2189 /* get_addr can only handle VALUE but cannot handle expr like:
2190 VALUE + OFFSET, so call get_addr to get original addr for
2191 mem_addr before plus_constant. */
2192 mem_addr
= get_addr (mem_addr
);
2194 mem_addr
= plus_constant (get_address_mode (mem
), mem_addr
, offset
);
2197 /* We ignore the clobbers in store_info. The is mildly aggressive,
2198 but there really should not be a clobber followed by a read. */
2200 if (spill_alias_set
)
2202 insn_info_t i_ptr
= active_local_stores
;
2203 insn_info_t last
= NULL
;
2205 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2206 fprintf (dump_file
, " processing spill load %d\n",
2207 (int) spill_alias_set
);
2211 store_info_t store_info
= i_ptr
->store_rec
;
2213 /* Skip the clobbers. */
2214 while (!store_info
->is_set
)
2215 store_info
= store_info
->next
;
2217 if (store_info
->alias_set
== spill_alias_set
)
2219 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2220 dump_insn_info ("removing from active", i_ptr
);
2222 active_local_stores_len
--;
2224 last
->next_local_store
= i_ptr
->next_local_store
;
2226 active_local_stores
= i_ptr
->next_local_store
;
2230 i_ptr
= i_ptr
->next_local_store
;
2233 else if (group_id
>= 0)
2235 /* This is the restricted case where the base is a constant or
2236 the frame pointer and offset is a constant. */
2237 insn_info_t i_ptr
= active_local_stores
;
2238 insn_info_t last
= NULL
;
2240 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2243 fprintf (dump_file
, " processing const load gid=%d[BLK]\n",
2246 fprintf (dump_file
, " processing const load gid=%d[%d..%d)\n",
2247 group_id
, (int)offset
, (int)(offset
+width
));
2252 bool remove
= false;
2253 store_info_t store_info
= i_ptr
->store_rec
;
2255 /* Skip the clobbers. */
2256 while (!store_info
->is_set
)
2257 store_info
= store_info
->next
;
2259 /* There are three cases here. */
2260 if (store_info
->group_id
< 0)
2261 /* We have a cselib store followed by a read from a
2264 = canon_true_dependence (store_info
->mem
,
2265 GET_MODE (store_info
->mem
),
2266 store_info
->mem_addr
,
2269 else if (group_id
== store_info
->group_id
)
2271 /* This is a block mode load. We may get lucky and
2272 canon_true_dependence may save the day. */
2275 = canon_true_dependence (store_info
->mem
,
2276 GET_MODE (store_info
->mem
),
2277 store_info
->mem_addr
,
2280 /* If this read is just reading back something that we just
2281 stored, rewrite the read. */
2285 && offset
>= store_info
->begin
2286 && offset
+ width
<= store_info
->end
2287 && all_positions_needed_p (store_info
,
2288 offset
- store_info
->begin
,
2290 && replace_read (store_info
, i_ptr
, read_info
,
2291 insn_info
, loc
, bb_info
->regs_live
))
2294 /* The bases are the same, just see if the offsets
2296 if ((offset
< store_info
->end
)
2297 && (offset
+ width
> store_info
->begin
))
2303 The else case that is missing here is that the
2304 bases are constant but different. There is nothing
2305 to do here because there is no overlap. */
2309 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2310 dump_insn_info ("removing from active", i_ptr
);
2312 active_local_stores_len
--;
2314 last
->next_local_store
= i_ptr
->next_local_store
;
2316 active_local_stores
= i_ptr
->next_local_store
;
2320 i_ptr
= i_ptr
->next_local_store
;
2325 insn_info_t i_ptr
= active_local_stores
;
2326 insn_info_t last
= NULL
;
2327 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2329 fprintf (dump_file
, " processing cselib load mem:");
2330 print_inline_rtx (dump_file
, mem
, 0);
2331 fprintf (dump_file
, "\n");
2336 bool remove
= false;
2337 store_info_t store_info
= i_ptr
->store_rec
;
2339 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2340 fprintf (dump_file
, " processing cselib load against insn %d\n",
2341 INSN_UID (i_ptr
->insn
));
2343 /* Skip the clobbers. */
2344 while (!store_info
->is_set
)
2345 store_info
= store_info
->next
;
2347 /* If this read is just reading back something that we just
2348 stored, rewrite the read. */
2350 && store_info
->group_id
== -1
2351 && store_info
->cse_base
== base
2353 && offset
>= store_info
->begin
2354 && offset
+ width
<= store_info
->end
2355 && all_positions_needed_p (store_info
,
2356 offset
- store_info
->begin
, width
)
2357 && replace_read (store_info
, i_ptr
, read_info
, insn_info
, loc
,
2358 bb_info
->regs_live
))
2361 if (!store_info
->alias_set
)
2362 remove
= canon_true_dependence (store_info
->mem
,
2363 GET_MODE (store_info
->mem
),
2364 store_info
->mem_addr
,
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 /* A note_uses callback in which DATA points the INSN_INFO for
2386 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
2387 true for any part of *LOC. */
2390 check_mem_read_use (rtx
*loc
, void *data
)
2392 subrtx_ptr_iterator::array_type array
;
2393 FOR_EACH_SUBRTX_PTR (iter
, array
, loc
, NONCONST
)
2397 check_mem_read_rtx (loc
, (bb_info_t
) data
);
2402 /* Get arguments passed to CALL_INSN. Return TRUE if successful.
2403 So far it only handles arguments passed in registers. */
2406 get_call_args (rtx call_insn
, tree fn
, rtx
*args
, int nargs
)
2408 CUMULATIVE_ARGS args_so_far_v
;
2409 cumulative_args_t args_so_far
;
2413 INIT_CUMULATIVE_ARGS (args_so_far_v
, TREE_TYPE (fn
), NULL_RTX
, 0, 3);
2414 args_so_far
= pack_cumulative_args (&args_so_far_v
);
2416 arg
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2418 arg
!= void_list_node
&& idx
< nargs
;
2419 arg
= TREE_CHAIN (arg
), idx
++)
2421 machine_mode mode
= TYPE_MODE (TREE_VALUE (arg
));
2423 reg
= targetm
.calls
.function_arg (args_so_far
, mode
, NULL_TREE
, true);
2424 if (!reg
|| !REG_P (reg
) || GET_MODE (reg
) != mode
2425 || GET_MODE_CLASS (mode
) != MODE_INT
)
2428 for (link
= CALL_INSN_FUNCTION_USAGE (call_insn
);
2430 link
= XEXP (link
, 1))
2431 if (GET_CODE (XEXP (link
, 0)) == USE
)
2433 args
[idx
] = XEXP (XEXP (link
, 0), 0);
2434 if (REG_P (args
[idx
])
2435 && REGNO (args
[idx
]) == REGNO (reg
)
2436 && (GET_MODE (args
[idx
]) == mode
2437 || (GET_MODE_CLASS (GET_MODE (args
[idx
])) == MODE_INT
2438 && (GET_MODE_SIZE (GET_MODE (args
[idx
]))
2440 && (GET_MODE_SIZE (GET_MODE (args
[idx
]))
2441 > GET_MODE_SIZE (mode
)))))
2447 tmp
= cselib_expand_value_rtx (args
[idx
], scratch
, 5);
2448 if (GET_MODE (args
[idx
]) != mode
)
2450 if (!tmp
|| !CONST_INT_P (tmp
))
2452 tmp
= gen_int_mode (INTVAL (tmp
), mode
);
2457 targetm
.calls
.function_arg_advance (args_so_far
, mode
, NULL_TREE
, true);
2459 if (arg
!= void_list_node
|| idx
!= nargs
)
2464 /* Return a bitmap of the fixed registers contained in IN. */
2467 copy_fixed_regs (const_bitmap in
)
2471 ret
= ALLOC_REG_SET (NULL
);
2472 bitmap_and (ret
, in
, fixed_reg_set_regset
);
2476 /* Apply record_store to all candidate stores in INSN. Mark INSN
2477 if some part of it is not a candidate store and assigns to a
2478 non-register target. */
2481 scan_insn (bb_info_t bb_info
, rtx_insn
*insn
)
2484 insn_info_t insn_info
= (insn_info_t
) pool_alloc (insn_info_pool
);
2486 memset (insn_info
, 0, sizeof (struct insn_info
));
2488 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2489 fprintf (dump_file
, "\n**scanning insn=%d\n",
2492 insn_info
->prev_insn
= bb_info
->last_insn
;
2493 insn_info
->insn
= insn
;
2494 bb_info
->last_insn
= insn_info
;
2496 if (DEBUG_INSN_P (insn
))
2498 insn_info
->cannot_delete
= true;
2502 /* Look at all of the uses in the insn. */
2503 note_uses (&PATTERN (insn
), check_mem_read_use
, bb_info
);
2508 tree memset_call
= NULL_TREE
;
2510 insn_info
->cannot_delete
= true;
2512 /* Const functions cannot do anything bad i.e. read memory,
2513 however, they can read their parameters which may have
2514 been pushed onto the stack.
2515 memset and bzero don't read memory either. */
2516 const_call
= RTL_CONST_CALL_P (insn
);
2519 rtx call
= get_call_rtx_from (insn
);
2520 if (call
&& GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
2522 rtx symbol
= XEXP (XEXP (call
, 0), 0);
2523 if (SYMBOL_REF_DECL (symbol
)
2524 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
2526 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
2528 && (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
))
2529 == BUILT_IN_MEMSET
))
2530 || SYMBOL_REF_DECL (symbol
) == block_clear_fn
)
2531 memset_call
= SYMBOL_REF_DECL (symbol
);
2535 if (const_call
|| memset_call
)
2537 insn_info_t i_ptr
= active_local_stores
;
2538 insn_info_t last
= NULL
;
2540 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2541 fprintf (dump_file
, "%s call %d\n",
2542 const_call
? "const" : "memset", INSN_UID (insn
));
2544 /* See the head comment of the frame_read field. */
2545 if (reload_completed
2546 /* Tail calls are storing their arguments using
2547 arg pointer. If it is a frame pointer on the target,
2548 even before reload we need to kill frame pointer based
2550 || (SIBLING_CALL_P (insn
)
2551 && HARD_FRAME_POINTER_IS_ARG_POINTER
))
2552 insn_info
->frame_read
= true;
2554 /* Loop over the active stores and remove those which are
2555 killed by the const function call. */
2558 bool remove_store
= false;
2560 /* The stack pointer based stores are always killed. */
2561 if (i_ptr
->stack_pointer_based
)
2562 remove_store
= true;
2564 /* If the frame is read, the frame related stores are killed. */
2565 else if (insn_info
->frame_read
)
2567 store_info_t store_info
= i_ptr
->store_rec
;
2569 /* Skip the clobbers. */
2570 while (!store_info
->is_set
)
2571 store_info
= store_info
->next
;
2573 if (store_info
->group_id
>= 0
2574 && rtx_group_vec
[store_info
->group_id
]->frame_related
)
2575 remove_store
= true;
2580 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2581 dump_insn_info ("removing from active", i_ptr
);
2583 active_local_stores_len
--;
2585 last
->next_local_store
= i_ptr
->next_local_store
;
2587 active_local_stores
= i_ptr
->next_local_store
;
2592 i_ptr
= i_ptr
->next_local_store
;
2598 if (get_call_args (insn
, memset_call
, args
, 3)
2599 && CONST_INT_P (args
[1])
2600 && CONST_INT_P (args
[2])
2601 && INTVAL (args
[2]) > 0)
2603 rtx mem
= gen_rtx_MEM (BLKmode
, args
[0]);
2604 set_mem_size (mem
, INTVAL (args
[2]));
2605 body
= gen_rtx_SET (mem
, args
[1]);
2606 mems_found
+= record_store (body
, bb_info
);
2607 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2608 fprintf (dump_file
, "handling memset as BLKmode store\n");
2609 if (mems_found
== 1)
2611 if (active_local_stores_len
++
2612 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES
))
2614 active_local_stores_len
= 1;
2615 active_local_stores
= NULL
;
2617 insn_info
->fixed_regs_live
2618 = copy_fixed_regs (bb_info
->regs_live
);
2619 insn_info
->next_local_store
= active_local_stores
;
2620 active_local_stores
= insn_info
;
2625 else if (SIBLING_CALL_P (insn
) && reload_completed
)
2626 /* Arguments for a sibling call that are pushed to memory are passed
2627 using the incoming argument pointer of the current function. After
2628 reload that might be (and likely is) frame pointer based. */
2629 add_wild_read (bb_info
);
2631 /* Every other call, including pure functions, may read any memory
2632 that is not relative to the frame. */
2633 add_non_frame_wild_read (bb_info
);
2638 /* Assuming that there are sets in these insns, we cannot delete
2640 if ((GET_CODE (PATTERN (insn
)) == CLOBBER
)
2641 || volatile_refs_p (PATTERN (insn
))
2642 || (!cfun
->can_delete_dead_exceptions
&& !insn_nothrow_p (insn
))
2643 || (RTX_FRAME_RELATED_P (insn
))
2644 || find_reg_note (insn
, REG_FRAME_RELATED_EXPR
, NULL_RTX
))
2645 insn_info
->cannot_delete
= true;
2647 body
= PATTERN (insn
);
2648 if (GET_CODE (body
) == PARALLEL
)
2651 for (i
= 0; i
< XVECLEN (body
, 0); i
++)
2652 mems_found
+= record_store (XVECEXP (body
, 0, i
), bb_info
);
2655 mems_found
+= record_store (body
, bb_info
);
2657 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2658 fprintf (dump_file
, "mems_found = %d, cannot_delete = %s\n",
2659 mems_found
, insn_info
->cannot_delete
? "true" : "false");
2661 /* If we found some sets of mems, add it into the active_local_stores so
2662 that it can be locally deleted if found dead or used for
2663 replace_read and redundant constant store elimination. Otherwise mark
2664 it as cannot delete. This simplifies the processing later. */
2665 if (mems_found
== 1)
2667 if (active_local_stores_len
++
2668 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES
))
2670 active_local_stores_len
= 1;
2671 active_local_stores
= NULL
;
2673 insn_info
->fixed_regs_live
= copy_fixed_regs (bb_info
->regs_live
);
2674 insn_info
->next_local_store
= active_local_stores
;
2675 active_local_stores
= insn_info
;
2678 insn_info
->cannot_delete
= true;
2682 /* Remove BASE from the set of active_local_stores. This is a
2683 callback from cselib that is used to get rid of the stores in
2684 active_local_stores. */
2687 remove_useless_values (cselib_val
*base
)
2689 insn_info_t insn_info
= active_local_stores
;
2690 insn_info_t last
= NULL
;
2694 store_info_t store_info
= insn_info
->store_rec
;
2697 /* If ANY of the store_infos match the cselib group that is
2698 being deleted, then the insn can not be deleted. */
2701 if ((store_info
->group_id
== -1)
2702 && (store_info
->cse_base
== base
))
2707 store_info
= store_info
->next
;
2712 active_local_stores_len
--;
2714 last
->next_local_store
= insn_info
->next_local_store
;
2716 active_local_stores
= insn_info
->next_local_store
;
2717 free_store_info (insn_info
);
2722 insn_info
= insn_info
->next_local_store
;
2727 /* Do all of step 1. */
2733 bitmap regs_live
= BITMAP_ALLOC (®_obstack
);
2736 all_blocks
= BITMAP_ALLOC (NULL
);
2737 bitmap_set_bit (all_blocks
, ENTRY_BLOCK
);
2738 bitmap_set_bit (all_blocks
, EXIT_BLOCK
);
2740 FOR_ALL_BB_FN (bb
, cfun
)
2743 bb_info_t bb_info
= (bb_info_t
) pool_alloc (bb_info_pool
);
2745 memset (bb_info
, 0, sizeof (struct dse_bb_info
));
2746 bitmap_set_bit (all_blocks
, bb
->index
);
2747 bb_info
->regs_live
= regs_live
;
2749 bitmap_copy (regs_live
, DF_LR_IN (bb
));
2750 df_simulate_initialize_forwards (bb
, regs_live
);
2752 bb_table
[bb
->index
] = bb_info
;
2753 cselib_discard_hook
= remove_useless_values
;
2755 if (bb
->index
>= NUM_FIXED_BLOCKS
)
2760 = create_alloc_pool ("cse_store_info_pool",
2761 sizeof (struct store_info
), 100);
2762 active_local_stores
= NULL
;
2763 active_local_stores_len
= 0;
2764 cselib_clear_table ();
2766 /* Scan the insns. */
2767 FOR_BB_INSNS (bb
, insn
)
2770 scan_insn (bb_info
, insn
);
2771 cselib_process_insn (insn
);
2773 df_simulate_one_insn_forwards (bb
, insn
, regs_live
);
2776 /* This is something of a hack, because the global algorithm
2777 is supposed to take care of the case where stores go dead
2778 at the end of the function. However, the global
2779 algorithm must take a more conservative view of block
2780 mode reads than the local alg does. So to get the case
2781 where you have a store to the frame followed by a non
2782 overlapping block more read, we look at the active local
2783 stores at the end of the function and delete all of the
2784 frame and spill based ones. */
2785 if (stores_off_frame_dead_at_return
2786 && (EDGE_COUNT (bb
->succs
) == 0
2787 || (single_succ_p (bb
)
2788 && single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
2789 && ! crtl
->calls_eh_return
)))
2791 insn_info_t i_ptr
= active_local_stores
;
2794 store_info_t store_info
= i_ptr
->store_rec
;
2796 /* Skip the clobbers. */
2797 while (!store_info
->is_set
)
2798 store_info
= store_info
->next
;
2799 if (store_info
->alias_set
&& !i_ptr
->cannot_delete
)
2800 delete_dead_store_insn (i_ptr
);
2802 if (store_info
->group_id
>= 0)
2805 = rtx_group_vec
[store_info
->group_id
];
2806 if (group
->frame_related
&& !i_ptr
->cannot_delete
)
2807 delete_dead_store_insn (i_ptr
);
2810 i_ptr
= i_ptr
->next_local_store
;
2814 /* Get rid of the loads that were discovered in
2815 replace_read. Cselib is finished with this block. */
2816 while (deferred_change_list
)
2818 deferred_change_t next
= deferred_change_list
->next
;
2820 /* There is no reason to validate this change. That was
2822 *deferred_change_list
->loc
= deferred_change_list
->reg
;
2823 pool_free (deferred_change_pool
, deferred_change_list
);
2824 deferred_change_list
= next
;
2827 /* Get rid of all of the cselib based store_infos in this
2828 block and mark the containing insns as not being
2830 ptr
= bb_info
->last_insn
;
2833 if (ptr
->contains_cselib_groups
)
2835 store_info_t s_info
= ptr
->store_rec
;
2836 while (s_info
&& !s_info
->is_set
)
2837 s_info
= s_info
->next
;
2839 && s_info
->redundant_reason
2840 && s_info
->redundant_reason
->insn
2841 && !ptr
->cannot_delete
)
2843 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2844 fprintf (dump_file
, "Locally deleting insn %d "
2845 "because insn %d stores the "
2846 "same value and couldn't be "
2848 INSN_UID (ptr
->insn
),
2849 INSN_UID (s_info
->redundant_reason
->insn
));
2850 delete_dead_store_insn (ptr
);
2852 free_store_info (ptr
);
2856 store_info_t s_info
;
2858 /* Free at least positions_needed bitmaps. */
2859 for (s_info
= ptr
->store_rec
; s_info
; s_info
= s_info
->next
)
2860 if (s_info
->is_large
)
2862 BITMAP_FREE (s_info
->positions_needed
.large
.bmap
);
2863 s_info
->is_large
= false;
2866 ptr
= ptr
->prev_insn
;
2869 free_alloc_pool (cse_store_info_pool
);
2871 bb_info
->regs_live
= NULL
;
2874 BITMAP_FREE (regs_live
);
2876 rtx_group_table
->empty ();
2880 /*----------------------------------------------------------------------------
2883 Assign each byte position in the stores that we are going to
2884 analyze globally to a position in the bitmaps. Returns true if
2885 there are any bit positions assigned.
2886 ----------------------------------------------------------------------------*/
2889 dse_step2_init (void)
2894 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
2896 /* For all non stack related bases, we only consider a store to
2897 be deletable if there are two or more stores for that
2898 position. This is because it takes one store to make the
2899 other store redundant. However, for the stores that are
2900 stack related, we consider them if there is only one store
2901 for the position. We do this because the stack related
2902 stores can be deleted if their is no read between them and
2903 the end of the function.
2905 To make this work in the current framework, we take the stack
2906 related bases add all of the bits from store1 into store2.
2907 This has the effect of making the eligible even if there is
2910 if (stores_off_frame_dead_at_return
&& group
->frame_related
)
2912 bitmap_ior_into (group
->store2_n
, group
->store1_n
);
2913 bitmap_ior_into (group
->store2_p
, group
->store1_p
);
2914 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2915 fprintf (dump_file
, "group %d is frame related ", i
);
2918 group
->offset_map_size_n
++;
2919 group
->offset_map_n
= XOBNEWVEC (&dse_obstack
, int,
2920 group
->offset_map_size_n
);
2921 group
->offset_map_size_p
++;
2922 group
->offset_map_p
= XOBNEWVEC (&dse_obstack
, int,
2923 group
->offset_map_size_p
);
2924 group
->process_globally
= false;
2925 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2927 fprintf (dump_file
, "group %d(%d+%d): ", i
,
2928 (int)bitmap_count_bits (group
->store2_n
),
2929 (int)bitmap_count_bits (group
->store2_p
));
2930 bitmap_print (dump_file
, group
->store2_n
, "n ", " ");
2931 bitmap_print (dump_file
, group
->store2_p
, "p ", "\n");
2937 /* Init the offset tables for the normal case. */
2940 dse_step2_nospill (void)
2944 /* Position 0 is unused because 0 is used in the maps to mean
2946 current_position
= 1;
2947 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
2952 if (group
== clear_alias_group
)
2955 memset (group
->offset_map_n
, 0, sizeof (int) * group
->offset_map_size_n
);
2956 memset (group
->offset_map_p
, 0, sizeof (int) * group
->offset_map_size_p
);
2957 bitmap_clear (group
->group_kill
);
2959 EXECUTE_IF_SET_IN_BITMAP (group
->store2_n
, 0, j
, bi
)
2961 bitmap_set_bit (group
->group_kill
, current_position
);
2962 if (bitmap_bit_p (group
->escaped_n
, j
))
2963 bitmap_set_bit (kill_on_calls
, current_position
);
2964 group
->offset_map_n
[j
] = current_position
++;
2965 group
->process_globally
= true;
2967 EXECUTE_IF_SET_IN_BITMAP (group
->store2_p
, 0, j
, bi
)
2969 bitmap_set_bit (group
->group_kill
, current_position
);
2970 if (bitmap_bit_p (group
->escaped_p
, j
))
2971 bitmap_set_bit (kill_on_calls
, current_position
);
2972 group
->offset_map_p
[j
] = current_position
++;
2973 group
->process_globally
= true;
2976 return current_position
!= 1;
2981 /*----------------------------------------------------------------------------
2984 Build the bit vectors for the transfer functions.
2985 ----------------------------------------------------------------------------*/
2988 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
2992 get_bitmap_index (group_info_t group_info
, HOST_WIDE_INT offset
)
2996 HOST_WIDE_INT offset_p
= -offset
;
2997 if (offset_p
>= group_info
->offset_map_size_n
)
2999 return group_info
->offset_map_n
[offset_p
];
3003 if (offset
>= group_info
->offset_map_size_p
)
3005 return group_info
->offset_map_p
[offset
];
3010 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3014 scan_stores_nospill (store_info_t store_info
, bitmap gen
, bitmap kill
)
3019 group_info_t group_info
3020 = rtx_group_vec
[store_info
->group_id
];
3021 if (group_info
->process_globally
)
3022 for (i
= store_info
->begin
; i
< store_info
->end
; i
++)
3024 int index
= get_bitmap_index (group_info
, i
);
3027 bitmap_set_bit (gen
, index
);
3029 bitmap_clear_bit (kill
, index
);
3032 store_info
= store_info
->next
;
3037 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3041 scan_stores_spill (store_info_t store_info
, bitmap gen
, bitmap kill
)
3045 if (store_info
->alias_set
)
3047 int index
= get_bitmap_index (clear_alias_group
,
3048 store_info
->alias_set
);
3051 bitmap_set_bit (gen
, index
);
3053 bitmap_clear_bit (kill
, index
);
3056 store_info
= store_info
->next
;
3061 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3065 scan_reads_nospill (insn_info_t insn_info
, bitmap gen
, bitmap kill
)
3067 read_info_t read_info
= insn_info
->read_rec
;
3071 /* If this insn reads the frame, kill all the frame related stores. */
3072 if (insn_info
->frame_read
)
3074 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3075 if (group
->process_globally
&& group
->frame_related
)
3078 bitmap_ior_into (kill
, group
->group_kill
);
3079 bitmap_and_compl_into (gen
, group
->group_kill
);
3082 if (insn_info
->non_frame_wild_read
)
3084 /* Kill all non-frame related stores. Kill all stores of variables that
3087 bitmap_ior_into (kill
, kill_on_calls
);
3088 bitmap_and_compl_into (gen
, kill_on_calls
);
3089 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3090 if (group
->process_globally
&& !group
->frame_related
)
3093 bitmap_ior_into (kill
, group
->group_kill
);
3094 bitmap_and_compl_into (gen
, group
->group_kill
);
3099 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3101 if (group
->process_globally
)
3103 if (i
== read_info
->group_id
)
3105 if (read_info
->begin
> read_info
->end
)
3107 /* Begin > end for block mode reads. */
3109 bitmap_ior_into (kill
, group
->group_kill
);
3110 bitmap_and_compl_into (gen
, group
->group_kill
);
3114 /* The groups are the same, just process the
3117 for (j
= read_info
->begin
; j
< read_info
->end
; j
++)
3119 int index
= get_bitmap_index (group
, j
);
3123 bitmap_set_bit (kill
, index
);
3124 bitmap_clear_bit (gen
, index
);
3131 /* The groups are different, if the alias sets
3132 conflict, clear the entire group. We only need
3133 to apply this test if the read_info is a cselib
3134 read. Anything with a constant base cannot alias
3135 something else with a different constant
3137 if ((read_info
->group_id
< 0)
3138 && canon_true_dependence (group
->base_mem
,
3139 GET_MODE (group
->base_mem
),
3140 group
->canon_base_addr
,
3141 read_info
->mem
, NULL_RTX
))
3144 bitmap_ior_into (kill
, group
->group_kill
);
3145 bitmap_and_compl_into (gen
, group
->group_kill
);
3151 read_info
= read_info
->next
;
3155 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3159 scan_reads_spill (read_info_t read_info
, bitmap gen
, bitmap kill
)
3163 if (read_info
->alias_set
)
3165 int index
= get_bitmap_index (clear_alias_group
,
3166 read_info
->alias_set
);
3170 bitmap_set_bit (kill
, index
);
3171 bitmap_clear_bit (gen
, index
);
3175 read_info
= read_info
->next
;
3180 /* Return the insn in BB_INFO before the first wild read or if there
3181 are no wild reads in the block, return the last insn. */
3184 find_insn_before_first_wild_read (bb_info_t bb_info
)
3186 insn_info_t insn_info
= bb_info
->last_insn
;
3187 insn_info_t last_wild_read
= NULL
;
3191 if (insn_info
->wild_read
)
3193 last_wild_read
= insn_info
->prev_insn
;
3194 /* Block starts with wild read. */
3195 if (!last_wild_read
)
3199 insn_info
= insn_info
->prev_insn
;
3203 return last_wild_read
;
3205 return bb_info
->last_insn
;
3209 /* Scan the insns in BB_INFO starting at PTR and going to the top of
3210 the block in order to build the gen and kill sets for the block.
3211 We start at ptr which may be the last insn in the block or may be
3212 the first insn with a wild read. In the latter case we are able to
3213 skip the rest of the block because it just does not matter:
3214 anything that happens is hidden by the wild read. */
3217 dse_step3_scan (bool for_spills
, basic_block bb
)
3219 bb_info_t bb_info
= bb_table
[bb
->index
];
3220 insn_info_t insn_info
;
3223 /* There are no wild reads in the spill case. */
3224 insn_info
= bb_info
->last_insn
;
3226 insn_info
= find_insn_before_first_wild_read (bb_info
);
3228 /* In the spill case or in the no_spill case if there is no wild
3229 read in the block, we will need a kill set. */
3230 if (insn_info
== bb_info
->last_insn
)
3233 bitmap_clear (bb_info
->kill
);
3235 bb_info
->kill
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3239 BITMAP_FREE (bb_info
->kill
);
3243 /* There may have been code deleted by the dce pass run before
3245 if (insn_info
->insn
&& INSN_P (insn_info
->insn
))
3247 /* Process the read(s) last. */
3250 scan_stores_spill (insn_info
->store_rec
, bb_info
->gen
, bb_info
->kill
);
3251 scan_reads_spill (insn_info
->read_rec
, bb_info
->gen
, bb_info
->kill
);
3255 scan_stores_nospill (insn_info
->store_rec
, bb_info
->gen
, bb_info
->kill
);
3256 scan_reads_nospill (insn_info
, bb_info
->gen
, bb_info
->kill
);
3260 insn_info
= insn_info
->prev_insn
;
3265 /* Set the gen set of the exit block, and also any block with no
3266 successors that does not have a wild read. */
3269 dse_step3_exit_block_scan (bb_info_t bb_info
)
3271 /* The gen set is all 0's for the exit block except for the
3272 frame_pointer_group. */
3274 if (stores_off_frame_dead_at_return
)
3279 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3281 if (group
->process_globally
&& group
->frame_related
)
3282 bitmap_ior_into (bb_info
->gen
, group
->group_kill
);
3288 /* Find all of the blocks that are not backwards reachable from the
3289 exit block or any block with no successors (BB). These are the
3290 infinite loops or infinite self loops. These blocks will still
3291 have their bits set in UNREACHABLE_BLOCKS. */
3294 mark_reachable_blocks (sbitmap unreachable_blocks
, basic_block bb
)
3299 if (bitmap_bit_p (unreachable_blocks
, bb
->index
))
3301 bitmap_clear_bit (unreachable_blocks
, bb
->index
);
3302 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3304 mark_reachable_blocks (unreachable_blocks
, e
->src
);
3309 /* Build the transfer functions for the function. */
3312 dse_step3 (bool for_spills
)
3315 sbitmap unreachable_blocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
3316 sbitmap_iterator sbi
;
3317 bitmap all_ones
= NULL
;
3320 bitmap_ones (unreachable_blocks
);
3322 FOR_ALL_BB_FN (bb
, cfun
)
3324 bb_info_t bb_info
= bb_table
[bb
->index
];
3326 bitmap_clear (bb_info
->gen
);
3328 bb_info
->gen
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3330 if (bb
->index
== ENTRY_BLOCK
)
3332 else if (bb
->index
== EXIT_BLOCK
)
3333 dse_step3_exit_block_scan (bb_info
);
3335 dse_step3_scan (for_spills
, bb
);
3336 if (EDGE_COUNT (bb
->succs
) == 0)
3337 mark_reachable_blocks (unreachable_blocks
, bb
);
3339 /* If this is the second time dataflow is run, delete the old
3342 BITMAP_FREE (bb_info
->in
);
3344 BITMAP_FREE (bb_info
->out
);
3347 /* For any block in an infinite loop, we must initialize the out set
3348 to all ones. This could be expensive, but almost never occurs in
3349 practice. However, it is common in regression tests. */
3350 EXECUTE_IF_SET_IN_BITMAP (unreachable_blocks
, 0, i
, sbi
)
3352 if (bitmap_bit_p (all_blocks
, i
))
3354 bb_info_t bb_info
= bb_table
[i
];
3360 all_ones
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3361 FOR_EACH_VEC_ELT (rtx_group_vec
, j
, group
)
3362 bitmap_ior_into (all_ones
, group
->group_kill
);
3366 bb_info
->out
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3367 bitmap_copy (bb_info
->out
, all_ones
);
3373 BITMAP_FREE (all_ones
);
3374 sbitmap_free (unreachable_blocks
);
3379 /*----------------------------------------------------------------------------
3382 Solve the bitvector equations.
3383 ----------------------------------------------------------------------------*/
3386 /* Confluence function for blocks with no successors. Create an out
3387 set from the gen set of the exit block. This block logically has
3388 the exit block as a successor. */
3393 dse_confluence_0 (basic_block bb
)
3395 bb_info_t bb_info
= bb_table
[bb
->index
];
3397 if (bb
->index
== EXIT_BLOCK
)
3402 bb_info
->out
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3403 bitmap_copy (bb_info
->out
, bb_table
[EXIT_BLOCK
]->gen
);
3407 /* Propagate the information from the in set of the dest of E to the
3408 out set of the src of E. If the various in or out sets are not
3409 there, that means they are all ones. */
3412 dse_confluence_n (edge e
)
3414 bb_info_t src_info
= bb_table
[e
->src
->index
];
3415 bb_info_t dest_info
= bb_table
[e
->dest
->index
];
3420 bitmap_and_into (src_info
->out
, dest_info
->in
);
3423 src_info
->out
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3424 bitmap_copy (src_info
->out
, dest_info
->in
);
3431 /* Propagate the info from the out to the in set of BB_INDEX's basic
3432 block. There are three cases:
3434 1) The block has no kill set. In this case the kill set is all
3435 ones. It does not matter what the out set of the block is, none of
3436 the info can reach the top. The only thing that reaches the top is
3437 the gen set and we just copy the set.
3439 2) There is a kill set but no out set and bb has successors. In
3440 this case we just return. Eventually an out set will be created and
3441 it is better to wait than to create a set of ones.
3443 3) There is both a kill and out set. We apply the obvious transfer
3448 dse_transfer_function (int bb_index
)
3450 bb_info_t bb_info
= bb_table
[bb_index
];
3458 return bitmap_ior_and_compl (bb_info
->in
, bb_info
->gen
,
3459 bb_info
->out
, bb_info
->kill
);
3462 bb_info
->in
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3463 bitmap_ior_and_compl (bb_info
->in
, bb_info
->gen
,
3464 bb_info
->out
, bb_info
->kill
);
3474 /* Case 1 above. If there is already an in set, nothing
3480 bb_info
->in
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3481 bitmap_copy (bb_info
->in
, bb_info
->gen
);
3487 /* Solve the dataflow equations. */
3492 df_simple_dataflow (DF_BACKWARD
, NULL
, dse_confluence_0
,
3493 dse_confluence_n
, dse_transfer_function
,
3494 all_blocks
, df_get_postorder (DF_BACKWARD
),
3495 df_get_n_blocks (DF_BACKWARD
));
3496 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3500 fprintf (dump_file
, "\n\n*** Global dataflow info after analysis.\n");
3501 FOR_ALL_BB_FN (bb
, cfun
)
3503 bb_info_t bb_info
= bb_table
[bb
->index
];
3505 df_print_bb_index (bb
, dump_file
);
3507 bitmap_print (dump_file
, bb_info
->in
, " in: ", "\n");
3509 fprintf (dump_file
, " in: *MISSING*\n");
3511 bitmap_print (dump_file
, bb_info
->gen
, " gen: ", "\n");
3513 fprintf (dump_file
, " gen: *MISSING*\n");
3515 bitmap_print (dump_file
, bb_info
->kill
, " kill: ", "\n");
3517 fprintf (dump_file
, " kill: *MISSING*\n");
3519 bitmap_print (dump_file
, bb_info
->out
, " out: ", "\n");
3521 fprintf (dump_file
, " out: *MISSING*\n\n");
3528 /*----------------------------------------------------------------------------
3531 Delete the stores that can only be deleted using the global information.
3532 ----------------------------------------------------------------------------*/
3536 dse_step5_nospill (void)
3539 FOR_EACH_BB_FN (bb
, cfun
)
3541 bb_info_t bb_info
= bb_table
[bb
->index
];
3542 insn_info_t insn_info
= bb_info
->last_insn
;
3543 bitmap v
= bb_info
->out
;
3547 bool deleted
= false;
3548 if (dump_file
&& insn_info
->insn
)
3550 fprintf (dump_file
, "starting to process insn %d\n",
3551 INSN_UID (insn_info
->insn
));
3552 bitmap_print (dump_file
, v
, " v: ", "\n");
3555 /* There may have been code deleted by the dce pass run before
3558 && INSN_P (insn_info
->insn
)
3559 && (!insn_info
->cannot_delete
)
3560 && (!bitmap_empty_p (v
)))
3562 store_info_t store_info
= insn_info
->store_rec
;
3564 /* Try to delete the current insn. */
3567 /* Skip the clobbers. */
3568 while (!store_info
->is_set
)
3569 store_info
= store_info
->next
;
3571 if (store_info
->alias_set
)
3576 group_info_t group_info
3577 = rtx_group_vec
[store_info
->group_id
];
3579 for (i
= store_info
->begin
; i
< store_info
->end
; i
++)
3581 int index
= get_bitmap_index (group_info
, i
);
3583 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3584 fprintf (dump_file
, "i = %d, index = %d\n", (int)i
, index
);
3585 if (index
== 0 || !bitmap_bit_p (v
, index
))
3587 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3588 fprintf (dump_file
, "failing at i = %d\n", (int)i
);
3597 && check_for_inc_dec_1 (insn_info
))
3599 delete_insn (insn_info
->insn
);
3600 insn_info
->insn
= NULL
;
3605 /* We do want to process the local info if the insn was
3606 deleted. For instance, if the insn did a wild read, we
3607 no longer need to trash the info. */
3609 && INSN_P (insn_info
->insn
)
3612 scan_stores_nospill (insn_info
->store_rec
, v
, NULL
);
3613 if (insn_info
->wild_read
)
3615 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3616 fprintf (dump_file
, "wild read\n");
3619 else if (insn_info
->read_rec
3620 || insn_info
->non_frame_wild_read
)
3622 if (dump_file
&& !insn_info
->non_frame_wild_read
)
3623 fprintf (dump_file
, "regular read\n");
3624 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3625 fprintf (dump_file
, "non-frame wild read\n");
3626 scan_reads_nospill (insn_info
, v
, NULL
);
3630 insn_info
= insn_info
->prev_insn
;
3637 /*----------------------------------------------------------------------------
3640 Delete stores made redundant by earlier stores (which store the same
3641 value) that couldn't be eliminated.
3642 ----------------------------------------------------------------------------*/
3649 FOR_ALL_BB_FN (bb
, cfun
)
3651 bb_info_t bb_info
= bb_table
[bb
->index
];
3652 insn_info_t insn_info
= bb_info
->last_insn
;
3656 /* There may have been code deleted by the dce pass run before
3659 && INSN_P (insn_info
->insn
)
3660 && !insn_info
->cannot_delete
)
3662 store_info_t s_info
= insn_info
->store_rec
;
3664 while (s_info
&& !s_info
->is_set
)
3665 s_info
= s_info
->next
;
3667 && s_info
->redundant_reason
3668 && s_info
->redundant_reason
->insn
3669 && INSN_P (s_info
->redundant_reason
->insn
))
3671 rtx_insn
*rinsn
= s_info
->redundant_reason
->insn
;
3672 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3673 fprintf (dump_file
, "Locally deleting insn %d "
3674 "because insn %d stores the "
3675 "same value and couldn't be "
3677 INSN_UID (insn_info
->insn
),
3679 delete_dead_store_insn (insn_info
);
3682 insn_info
= insn_info
->prev_insn
;
3687 /*----------------------------------------------------------------------------
3690 Destroy everything left standing.
3691 ----------------------------------------------------------------------------*/
3696 bitmap_obstack_release (&dse_bitmap_obstack
);
3697 obstack_free (&dse_obstack
, NULL
);
3699 end_alias_analysis ();
3701 delete rtx_group_table
;
3702 rtx_group_table
= NULL
;
3703 rtx_group_vec
.release ();
3704 BITMAP_FREE (all_blocks
);
3705 BITMAP_FREE (scratch
);
3707 free_alloc_pool (rtx_store_info_pool
);
3708 free_alloc_pool (read_info_pool
);
3709 free_alloc_pool (insn_info_pool
);
3710 free_alloc_pool (bb_info_pool
);
3711 free_alloc_pool (rtx_group_info_pool
);
3712 free_alloc_pool (deferred_change_pool
);
3716 /* -------------------------------------------------------------------------
3718 ------------------------------------------------------------------------- */
3720 /* Callback for running pass_rtl_dse. */
3723 rest_of_handle_dse (void)
3725 df_set_flags (DF_DEFER_INSN_RESCAN
);
3727 /* Need the notes since we must track live hardregs in the forwards
3729 df_note_add_problem ();
3735 if (dse_step2_nospill ())
3737 df_set_flags (DF_LR_RUN_DCE
);
3739 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3740 fprintf (dump_file
, "doing global processing\n");
3743 dse_step5_nospill ();
3750 fprintf (dump_file
, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3751 locally_deleted
, globally_deleted
, spill_deleted
);
3753 /* DSE can eliminate potentially-trapping MEMs.
3754 Remove any EH edges associated with them. */
3755 if ((locally_deleted
|| globally_deleted
)
3756 && cfun
->can_throw_non_call_exceptions
3757 && purge_all_dead_edges ())
3765 const pass_data pass_data_rtl_dse1
=
3767 RTL_PASS
, /* type */
3769 OPTGROUP_NONE
, /* optinfo_flags */
3770 TV_DSE1
, /* tv_id */
3771 0, /* properties_required */
3772 0, /* properties_provided */
3773 0, /* properties_destroyed */
3774 0, /* todo_flags_start */
3775 TODO_df_finish
, /* todo_flags_finish */
3778 class pass_rtl_dse1
: public rtl_opt_pass
3781 pass_rtl_dse1 (gcc::context
*ctxt
)
3782 : rtl_opt_pass (pass_data_rtl_dse1
, ctxt
)
3785 /* opt_pass methods: */
3786 virtual bool gate (function
*)
3788 return optimize
> 0 && flag_dse
&& dbg_cnt (dse1
);
3791 virtual unsigned int execute (function
*) { return rest_of_handle_dse (); }
3793 }; // class pass_rtl_dse1
3798 make_pass_rtl_dse1 (gcc::context
*ctxt
)
3800 return new pass_rtl_dse1 (ctxt
);
3805 const pass_data pass_data_rtl_dse2
=
3807 RTL_PASS
, /* type */
3809 OPTGROUP_NONE
, /* optinfo_flags */
3810 TV_DSE2
, /* tv_id */
3811 0, /* properties_required */
3812 0, /* properties_provided */
3813 0, /* properties_destroyed */
3814 0, /* todo_flags_start */
3815 TODO_df_finish
, /* todo_flags_finish */
3818 class pass_rtl_dse2
: public rtl_opt_pass
3821 pass_rtl_dse2 (gcc::context
*ctxt
)
3822 : rtl_opt_pass (pass_data_rtl_dse2
, ctxt
)
3825 /* opt_pass methods: */
3826 virtual bool gate (function
*)
3828 return optimize
> 0 && flag_dse
&& dbg_cnt (dse2
);
3831 virtual unsigned int execute (function
*) { return rest_of_handle_dse (); }
3833 }; // class pass_rtl_dse2
3838 make_pass_rtl_dse2 (gcc::context
*ctxt
)
3840 return new pass_rtl_dse2 (ctxt
);