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"
85 /* This file contains three techniques for performing Dead Store
88 * The first technique performs dse locally on any base address. It
89 is based on the cselib which is a local value numbering technique.
90 This technique is local to a basic block but deals with a fairly
93 * The second technique performs dse globally but is restricted to
94 base addresses that are either constant or are relative to the
97 * The third technique, (which is only done after register allocation)
98 processes the spill spill slots. This differs from the second
99 technique because it takes advantage of the fact that spilling is
100 completely free from the effects of aliasing.
102 Logically, dse is a backwards dataflow problem. A store can be
103 deleted if it if cannot be reached in the backward direction by any
104 use of the value being stored. However, the local technique uses a
105 forwards scan of the basic block because cselib requires that the
106 block be processed in that order.
108 The pass is logically broken into 7 steps:
112 1) The local algorithm, as well as scanning the insns for the two
115 2) Analysis to see if the global algs are necessary. In the case
116 of stores base on a constant address, there must be at least two
117 stores to that address, to make it possible to delete some of the
118 stores. In the case of stores off of the frame or spill related
119 stores, only one store to an address is necessary because those
120 stores die at the end of the function.
122 3) Set up the global dataflow equations based on processing the
123 info parsed in the first step.
125 4) Solve the dataflow equations.
127 5) Delete the insns that the global analysis has indicated are
130 6) Delete insns that store the same value as preceding store
131 where the earlier store couldn't be eliminated.
135 This step uses cselib and canon_rtx to build the largest expression
136 possible for each address. This pass is a forwards pass through
137 each basic block. From the point of view of the global technique,
138 the first pass could examine a block in either direction. The
139 forwards ordering is to accommodate cselib.
141 We make a simplifying assumption: addresses fall into four broad
144 1) base has rtx_varies_p == false, offset is constant.
145 2) base has rtx_varies_p == false, offset variable.
146 3) base has rtx_varies_p == true, offset constant.
147 4) base has rtx_varies_p == true, offset variable.
149 The local passes are able to process all 4 kinds of addresses. The
150 global pass only handles 1).
152 The global problem is formulated as follows:
154 A store, S1, to address A, where A is not relative to the stack
155 frame, can be eliminated if all paths from S1 to the end of the
156 function contain another store to A before a read to A.
158 If the address A is relative to the stack frame, a store S2 to A
159 can be eliminated if there are no paths from S2 that reach the
160 end of the function that read A before another store to A. In
161 this case S2 can be deleted if there are paths from S2 to the
162 end of the function that have no reads or writes to A. This
163 second case allows stores to the stack frame to be deleted that
164 would otherwise die when the function returns. This cannot be
165 done if stores_off_frame_dead_at_return is not true. See the doc
166 for that variable for when this variable is false.
168 The global problem is formulated as a backwards set union
169 dataflow problem where the stores are the gens and reads are the
170 kills. Set union problems are rare and require some special
171 handling given our representation of bitmaps. A straightforward
172 implementation requires a lot of bitmaps filled with 1s.
173 These are expensive and cumbersome in our bitmap formulation so
174 care has been taken to avoid large vectors filled with 1s. See
175 the comments in bb_info and in the dataflow confluence functions
178 There are two places for further enhancements to this algorithm:
180 1) The original dse which was embedded in a pass called flow also
181 did local address forwarding. For example in
186 flow would replace the right hand side of the second insn with a
187 reference to r100. Most of the information is available to add this
188 to this pass. It has not done it because it is a lot of work in
189 the case that either r100 is assigned to between the first and
190 second insn and/or the second insn is a load of part of the value
191 stored by the first insn.
193 insn 5 in gcc.c-torture/compile/990203-1.c simple case.
194 insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
195 insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
196 insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
198 2) The cleaning up of spill code is quite profitable. It currently
199 depends on reading tea leaves and chicken entrails left by reload.
200 This pass depends on reload creating a singleton alias set for each
201 spill slot and telling the next dse pass which of these alias sets
202 are the singletons. Rather than analyze the addresses of the
203 spills, dse's spill processing just does analysis of the loads and
204 stores that use those alias sets. There are three cases where this
207 a) Reload sometimes creates the slot for one mode of access, and
208 then inserts loads and/or stores for a smaller mode. In this
209 case, the current code just punts on the slot. The proper thing
210 to do is to back out and use one bit vector position for each
211 byte of the entity associated with the slot. This depends on
212 KNOWING that reload always generates the accesses for each of the
213 bytes in some canonical (read that easy to understand several
214 passes after reload happens) way.
216 b) Reload sometimes decides that spill slot it allocated was not
217 large enough for the mode and goes back and allocates more slots
218 with the same mode and alias set. The backout in this case is a
219 little more graceful than (a). In this case the slot is unmarked
220 as being a spill slot and if final address comes out to be based
221 off the frame pointer, the global algorithm handles this slot.
223 c) For any pass that may prespill, there is currently no
224 mechanism to tell the dse pass that the slot being used has the
225 special properties that reload uses. It may be that all that is
226 required is to have those passes make the same calls that reload
227 does, assuming that the alias sets can be manipulated in the same
230 /* There are limits to the size of constant offsets we model for the
231 global problem. There are certainly test cases, that exceed this
232 limit, however, it is unlikely that there are important programs
233 that really have constant offsets this size. */
234 #define MAX_OFFSET (64 * 1024)
236 /* Obstack for the DSE dataflow bitmaps. We don't want to put these
237 on the default obstack because these bitmaps can grow quite large
238 (~2GB for the small (!) test case of PR54146) and we'll hold on to
239 all that memory until the end of the compiler run.
240 As a bonus, delete_tree_live_info can destroy all the bitmaps by just
241 releasing the whole obstack. */
242 static bitmap_obstack dse_bitmap_obstack
;
244 /* Obstack for other data. As for above: Kinda nice to be able to
245 throw it all away at the end in one big sweep. */
246 static struct obstack dse_obstack
;
248 /* Scratch bitmap for cselib's cselib_expand_value_rtx. */
249 static bitmap scratch
= NULL
;
253 /* This structure holds information about a candidate store. */
257 /* False means this is a clobber. */
260 /* False if a single HOST_WIDE_INT bitmap is used for positions_needed. */
263 /* The id of the mem group of the base address. If rtx_varies_p is
264 true, this is -1. Otherwise, it is the index into the group
268 /* This is the cselib value. */
269 cselib_val
*cse_base
;
271 /* This canonized mem. */
274 /* Canonized MEM address for use by canon_true_dependence. */
277 /* If this is non-zero, it is the alias set of a spill location. */
278 alias_set_type alias_set
;
280 /* The offset of the first and byte before the last byte associated
281 with the operation. */
282 HOST_WIDE_INT begin
, end
;
286 /* A bitmask as wide as the number of bytes in the word that
287 contains a 1 if the byte may be needed. The store is unused if
288 all of the bits are 0. This is used if IS_LARGE is false. */
289 unsigned HOST_WIDE_INT small_bitmask
;
293 /* A bitmap with one bit per byte. Cleared bit means the position
294 is needed. Used if IS_LARGE is false. */
297 /* Number of set bits (i.e. unneeded bytes) in BITMAP. If it is
298 equal to END - BEGIN, the whole store is unused. */
303 /* The next store info for this insn. */
304 struct store_info
*next
;
306 /* The right hand side of the store. This is used if there is a
307 subsequent reload of the mems address somewhere later in the
311 /* If rhs is or holds a constant, this contains that constant,
315 /* Set if this store stores the same constant value as REDUNDANT_REASON
316 insn stored. These aren't eliminated early, because doing that
317 might prevent the earlier larger store to be eliminated. */
318 struct insn_info
*redundant_reason
;
321 /* Return a bitmask with the first N low bits set. */
323 static unsigned HOST_WIDE_INT
324 lowpart_bitmask (int n
)
326 unsigned HOST_WIDE_INT mask
= ~(unsigned HOST_WIDE_INT
) 0;
327 return mask
>> (HOST_BITS_PER_WIDE_INT
- n
);
330 typedef struct store_info
*store_info_t
;
331 static alloc_pool cse_store_info_pool
;
332 static alloc_pool rtx_store_info_pool
;
334 /* This structure holds information about a load. These are only
335 built for rtx bases. */
338 /* The id of the mem group of the base address. */
341 /* If this is non-zero, it is the alias set of a spill location. */
342 alias_set_type alias_set
;
344 /* The offset of the first and byte after the last byte associated
345 with the operation. If begin == end == 0, the read did not have
346 a constant offset. */
349 /* The mem being read. */
352 /* The next read_info for this insn. */
353 struct read_info
*next
;
355 typedef struct read_info
*read_info_t
;
356 static alloc_pool read_info_pool
;
359 /* One of these records is created for each insn. */
363 /* Set true if the insn contains a store but the insn itself cannot
364 be deleted. This is set if the insn is a parallel and there is
365 more than one non dead output or if the insn is in some way
369 /* This field is only used by the global algorithm. It is set true
370 if the insn contains any read of mem except for a (1). This is
371 also set if the insn is a call or has a clobber mem. If the insn
372 contains a wild read, the use_rec will be null. */
375 /* This is true only for CALL instructions which could potentially read
376 any non-frame memory location. This field is used by the global
378 bool non_frame_wild_read
;
380 /* This field is only used for the processing of const functions.
381 These functions cannot read memory, but they can read the stack
382 because that is where they may get their parms. We need to be
383 this conservative because, like the store motion pass, we don't
384 consider CALL_INSN_FUNCTION_USAGE when processing call insns.
385 Moreover, we need to distinguish two cases:
386 1. Before reload (register elimination), the stores related to
387 outgoing arguments are stack pointer based and thus deemed
388 of non-constant base in this pass. This requires special
389 handling but also means that the frame pointer based stores
390 need not be killed upon encountering a const function call.
391 2. After reload, the stores related to outgoing arguments can be
392 either stack pointer or hard frame pointer based. This means
393 that we have no other choice than also killing all the frame
394 pointer based stores upon encountering a const function call.
395 This field is set after reload for const function calls and before
396 reload for const tail function calls on targets where arg pointer
397 is the frame pointer. Having this set is less severe than a wild
398 read, it just means that all the frame related stores are killed
399 rather than all the stores. */
402 /* This field is only used for the processing of const functions.
403 It is set if the insn may contain a stack pointer based store. */
404 bool stack_pointer_based
;
406 /* This is true if any of the sets within the store contains a
407 cselib base. Such stores can only be deleted by the local
409 bool contains_cselib_groups
;
414 /* The list of mem sets or mem clobbers that are contained in this
415 insn. If the insn is deletable, it contains only one mem set.
416 But it could also contain clobbers. Insns that contain more than
417 one mem set are not deletable, but each of those mems are here in
418 order to provide info to delete other insns. */
419 store_info_t store_rec
;
421 /* The linked list of mem uses in this insn. Only the reads from
422 rtx bases are listed here. The reads to cselib bases are
423 completely processed during the first scan and so are never
425 read_info_t read_rec
;
427 /* The live fixed registers. We assume only fixed registers can
428 cause trouble by being clobbered from an expanded pattern;
429 storing only the live fixed registers (rather than all registers)
430 means less memory needs to be allocated / copied for the individual
432 regset fixed_regs_live
;
434 /* The prev insn in the basic block. */
435 struct insn_info
* prev_insn
;
437 /* The linked list of insns that are in consideration for removal in
438 the forwards pass through the basic block. This pointer may be
439 trash as it is not cleared when a wild read occurs. The only
440 time it is guaranteed to be correct is when the traversal starts
441 at active_local_stores. */
442 struct insn_info
* next_local_store
;
445 typedef struct insn_info
*insn_info_t
;
446 static alloc_pool insn_info_pool
;
448 /* The linked list of stores that are under consideration in this
450 static insn_info_t active_local_stores
;
451 static int active_local_stores_len
;
456 /* Pointer to the insn info for the last insn in the block. These
457 are linked so this is how all of the insns are reached. During
458 scanning this is the current insn being scanned. */
459 insn_info_t last_insn
;
461 /* The info for the global dataflow problem. */
464 /* This is set if the transfer function should and in the wild_read
465 bitmap before applying the kill and gen sets. That vector knocks
466 out most of the bits in the bitmap and thus speeds up the
468 bool apply_wild_read
;
470 /* The following 4 bitvectors hold information about which positions
471 of which stores are live or dead. They are indexed by
474 /* The set of store positions that exist in this block before a wild read. */
477 /* The set of load positions that exist in this block above the
478 same position of a store. */
481 /* The set of stores that reach the top of the block without being
484 Do not represent the in if it is all ones. Note that this is
485 what the bitvector should logically be initialized to for a set
486 intersection problem. However, like the kill set, this is too
487 expensive. So initially, the in set will only be created for the
488 exit block and any block that contains a wild read. */
491 /* The set of stores that reach the bottom of the block from it's
494 Do not represent the in if it is all ones. Note that this is
495 what the bitvector should logically be initialized to for a set
496 intersection problem. However, like the kill and in set, this is
497 too expensive. So what is done is that the confluence operator
498 just initializes the vector from one of the out sets of the
499 successors of the block. */
502 /* The following bitvector is indexed by the reg number. It
503 contains the set of regs that are live at the current instruction
504 being processed. While it contains info for all of the
505 registers, only the hard registers are actually examined. It is used
506 to assure that shift and/or add sequences that are inserted do not
507 accidentally clobber live hard regs. */
511 typedef struct dse_bb_info
*bb_info_t
;
512 static alloc_pool bb_info_pool
;
514 /* Table to hold all bb_infos. */
515 static bb_info_t
*bb_table
;
517 /* There is a group_info for each rtx base that is used to reference
518 memory. There are also not many of the rtx bases because they are
519 very limited in scope. */
523 /* The actual base of the address. */
526 /* The sequential id of the base. This allows us to have a
527 canonical ordering of these that is not based on addresses. */
530 /* True if there are any positions that are to be processed
532 bool process_globally
;
534 /* True if the base of this group is either the frame_pointer or
535 hard_frame_pointer. */
538 /* A mem wrapped around the base pointer for the group in order to do
539 read dependency. It must be given BLKmode in order to encompass all
540 the possible offsets from the base. */
543 /* Canonized version of base_mem's address. */
546 /* These two sets of two bitmaps are used to keep track of how many
547 stores are actually referencing that position from this base. We
548 only do this for rtx bases as this will be used to assign
549 positions in the bitmaps for the global problem. Bit N is set in
550 store1 on the first store for offset N. Bit N is set in store2
551 for the second store to offset N. This is all we need since we
552 only care about offsets that have two or more stores for them.
554 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
555 for 0 and greater offsets.
557 There is one special case here, for stores into the stack frame,
558 we will or store1 into store2 before deciding which stores look
559 at globally. This is because stores to the stack frame that have
560 no other reads before the end of the function can also be
562 bitmap store1_n
, store1_p
, store2_n
, store2_p
;
564 /* These bitmaps keep track of offsets in this group escape this function.
565 An offset escapes if it corresponds to a named variable whose
566 addressable flag is set. */
567 bitmap escaped_n
, escaped_p
;
569 /* The positions in this bitmap have the same assignments as the in,
570 out, gen and kill bitmaps. This bitmap is all zeros except for
571 the positions that are occupied by stores for this group. */
574 /* The offset_map is used to map the offsets from this base into
575 positions in the global bitmaps. It is only created after all of
576 the all of stores have been scanned and we know which ones we
578 int *offset_map_n
, *offset_map_p
;
579 int offset_map_size_n
, offset_map_size_p
;
581 typedef struct group_info
*group_info_t
;
582 typedef const struct group_info
*const_group_info_t
;
583 static alloc_pool rtx_group_info_pool
;
585 /* Index into the rtx_group_vec. */
586 static int rtx_group_next_id
;
589 static vec
<group_info_t
> rtx_group_vec
;
592 /* This structure holds the set of changes that are being deferred
593 when removing read operation. See replace_read. */
594 struct deferred_change
597 /* The mem that is being replaced. */
600 /* The reg it is being replaced with. */
603 struct deferred_change
*next
;
606 typedef struct deferred_change
*deferred_change_t
;
607 static alloc_pool deferred_change_pool
;
609 static deferred_change_t deferred_change_list
= NULL
;
611 /* The group that holds all of the clear_alias_sets. */
612 static group_info_t clear_alias_group
;
614 /* The modes of the clear_alias_sets. */
615 static htab_t clear_alias_mode_table
;
617 /* Hash table element to look up the mode for an alias set. */
618 struct clear_alias_mode_holder
620 alias_set_type alias_set
;
624 /* This is true except if cfun->stdarg -- i.e. we cannot do
625 this for vararg functions because they play games with the frame. */
626 static bool stores_off_frame_dead_at_return
;
628 /* Counter for stats. */
629 static int globally_deleted
;
630 static int locally_deleted
;
631 static int spill_deleted
;
633 static bitmap all_blocks
;
635 /* Locations that are killed by calls in the global phase. */
636 static bitmap kill_on_calls
;
638 /* The number of bits used in the global bitmaps. */
639 static unsigned int current_position
;
641 /*----------------------------------------------------------------------------
645 ----------------------------------------------------------------------------*/
648 /* Find the entry associated with ALIAS_SET. */
650 static struct clear_alias_mode_holder
*
651 clear_alias_set_lookup (alias_set_type alias_set
)
653 struct clear_alias_mode_holder tmp_holder
;
656 tmp_holder
.alias_set
= alias_set
;
657 slot
= htab_find_slot (clear_alias_mode_table
, &tmp_holder
, NO_INSERT
);
660 return (struct clear_alias_mode_holder
*) *slot
;
664 /* Hashtable callbacks for maintaining the "bases" field of
665 store_group_info, given that the addresses are function invariants. */
667 struct invariant_group_base_hasher
: typed_noop_remove
<group_info
>
669 typedef group_info value_type
;
670 typedef group_info compare_type
;
671 static inline hashval_t
hash (const value_type
*);
672 static inline bool equal (const value_type
*, const compare_type
*);
676 invariant_group_base_hasher::equal (const value_type
*gi1
,
677 const compare_type
*gi2
)
679 return rtx_equal_p (gi1
->rtx_base
, gi2
->rtx_base
);
683 invariant_group_base_hasher::hash (const value_type
*gi
)
686 return hash_rtx (gi
->rtx_base
, Pmode
, &do_not_record
, NULL
, false);
689 /* Tables of group_info structures, hashed by base value. */
690 static hash_table
<invariant_group_base_hasher
> *rtx_group_table
;
693 /* Get the GROUP for BASE. Add a new group if it is not there. */
696 get_group_info (rtx base
)
698 struct group_info tmp_gi
;
704 /* Find the store_base_info structure for BASE, creating a new one
706 tmp_gi
.rtx_base
= base
;
707 slot
= rtx_group_table
->find_slot (&tmp_gi
, INSERT
);
708 gi
= (group_info_t
) *slot
;
712 if (!clear_alias_group
)
714 clear_alias_group
= gi
=
715 (group_info_t
) pool_alloc (rtx_group_info_pool
);
716 memset (gi
, 0, sizeof (struct group_info
));
717 gi
->id
= rtx_group_next_id
++;
718 gi
->store1_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
719 gi
->store1_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
720 gi
->store2_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
721 gi
->store2_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
722 gi
->escaped_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
723 gi
->escaped_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
724 gi
->group_kill
= BITMAP_ALLOC (&dse_bitmap_obstack
);
725 gi
->process_globally
= false;
726 gi
->offset_map_size_n
= 0;
727 gi
->offset_map_size_p
= 0;
728 gi
->offset_map_n
= NULL
;
729 gi
->offset_map_p
= NULL
;
730 rtx_group_vec
.safe_push (gi
);
732 return clear_alias_group
;
737 *slot
= gi
= (group_info_t
) pool_alloc (rtx_group_info_pool
);
739 gi
->id
= rtx_group_next_id
++;
740 gi
->base_mem
= gen_rtx_MEM (BLKmode
, base
);
741 gi
->canon_base_addr
= canon_rtx (base
);
742 gi
->store1_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
743 gi
->store1_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
744 gi
->store2_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
745 gi
->store2_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
746 gi
->escaped_p
= BITMAP_ALLOC (&dse_bitmap_obstack
);
747 gi
->escaped_n
= BITMAP_ALLOC (&dse_bitmap_obstack
);
748 gi
->group_kill
= BITMAP_ALLOC (&dse_bitmap_obstack
);
749 gi
->process_globally
= false;
751 (base
== frame_pointer_rtx
) || (base
== hard_frame_pointer_rtx
);
752 gi
->offset_map_size_n
= 0;
753 gi
->offset_map_size_p
= 0;
754 gi
->offset_map_n
= NULL
;
755 gi
->offset_map_p
= NULL
;
756 rtx_group_vec
.safe_push (gi
);
763 /* Initialization of data structures. */
769 globally_deleted
= 0;
772 bitmap_obstack_initialize (&dse_bitmap_obstack
);
773 gcc_obstack_init (&dse_obstack
);
775 scratch
= BITMAP_ALLOC (®_obstack
);
776 kill_on_calls
= BITMAP_ALLOC (&dse_bitmap_obstack
);
779 = create_alloc_pool ("rtx_store_info_pool",
780 sizeof (struct store_info
), 100);
782 = create_alloc_pool ("read_info_pool",
783 sizeof (struct read_info
), 100);
785 = create_alloc_pool ("insn_info_pool",
786 sizeof (struct insn_info
), 100);
788 = create_alloc_pool ("bb_info_pool",
789 sizeof (struct dse_bb_info
), 100);
791 = create_alloc_pool ("rtx_group_info_pool",
792 sizeof (struct group_info
), 100);
794 = create_alloc_pool ("deferred_change_pool",
795 sizeof (struct deferred_change
), 10);
797 rtx_group_table
= new hash_table
<invariant_group_base_hasher
> (11);
799 bb_table
= XNEWVEC (bb_info_t
, last_basic_block_for_fn (cfun
));
800 rtx_group_next_id
= 0;
802 stores_off_frame_dead_at_return
= !cfun
->stdarg
;
804 init_alias_analysis ();
806 clear_alias_group
= NULL
;
811 /*----------------------------------------------------------------------------
814 Scan all of the insns. Any random ordering of the blocks is fine.
815 Each block is scanned in forward order to accommodate cselib which
816 is used to remove stores with non-constant bases.
817 ----------------------------------------------------------------------------*/
819 /* Delete all of the store_info recs from INSN_INFO. */
822 free_store_info (insn_info_t insn_info
)
824 store_info_t store_info
= insn_info
->store_rec
;
827 store_info_t next
= store_info
->next
;
828 if (store_info
->is_large
)
829 BITMAP_FREE (store_info
->positions_needed
.large
.bmap
);
830 if (store_info
->cse_base
)
831 pool_free (cse_store_info_pool
, store_info
);
833 pool_free (rtx_store_info_pool
, store_info
);
837 insn_info
->cannot_delete
= true;
838 insn_info
->contains_cselib_groups
= false;
839 insn_info
->store_rec
= NULL
;
844 rtx_insn
*first
, *current
;
845 regset fixed_regs_live
;
847 } note_add_store_info
;
849 /* Callback for emit_inc_dec_insn_before via note_stores.
850 Check if a register is clobbered which is live afterwards. */
853 note_add_store (rtx loc
, const_rtx expr ATTRIBUTE_UNUSED
, void *data
)
856 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. */
881 n
= hard_regno_nregs
[r
][GET_MODE (loc
)];
883 if (REGNO_REG_SET_P (info
->fixed_regs_live
, r
+n
))
884 info
->failure
= true;
887 /* Callback for for_each_inc_dec that emits an INSN that sets DEST to
888 SRC + SRCOFF before insn ARG. */
891 emit_inc_dec_insn_before (rtx mem ATTRIBUTE_UNUSED
,
892 rtx op ATTRIBUTE_UNUSED
,
893 rtx dest
, rtx src
, rtx srcoff
, void *arg
)
895 insn_info_t insn_info
= (insn_info_t
) arg
;
896 rtx_insn
*insn
= insn_info
->insn
, *new_insn
, *cur
;
897 note_add_store_info info
;
899 /* We can reuse all operands without copying, because we are about
900 to delete the insn that contained it. */
904 emit_insn (gen_add3_insn (dest
, src
, srcoff
));
905 new_insn
= get_insns ();
909 new_insn
= as_a
<rtx_insn
*> (gen_move_insn (dest
, src
));
910 info
.first
= new_insn
;
911 info
.fixed_regs_live
= insn_info
->fixed_regs_live
;
912 info
.failure
= false;
913 for (cur
= new_insn
; cur
; cur
= NEXT_INSN (cur
))
916 note_stores (PATTERN (cur
), note_add_store
, &info
);
919 /* If a failure was flagged above, return 1 so that for_each_inc_dec will
920 return it immediately, communicating the failure to its caller. */
924 emit_insn_before (new_insn
, insn
);
929 /* Before we delete INSN_INFO->INSN, make sure that the auto inc/dec, if it
930 is there, is split into a separate insn.
931 Return true on success (or if there was nothing to do), false on failure. */
934 check_for_inc_dec_1 (insn_info_t insn_info
)
936 rtx_insn
*insn
= insn_info
->insn
;
937 rtx note
= find_reg_note (insn
, REG_INC
, NULL_RTX
);
939 return for_each_inc_dec (PATTERN (insn
), emit_inc_dec_insn_before
,
945 /* Entry point for postreload. If you work on reload_cse, or you need this
946 anywhere else, consider if you can provide register liveness information
947 and add a parameter to this function so that it can be passed down in
948 insn_info.fixed_regs_live. */
950 check_for_inc_dec (rtx_insn
*insn
)
952 struct insn_info insn_info
;
955 insn_info
.insn
= insn
;
956 insn_info
.fixed_regs_live
= NULL
;
957 note
= find_reg_note (insn
, REG_INC
, NULL_RTX
);
959 return for_each_inc_dec (PATTERN (insn
), emit_inc_dec_insn_before
,
964 /* Delete the insn and free all of the fields inside INSN_INFO. */
967 delete_dead_store_insn (insn_info_t insn_info
)
969 read_info_t read_info
;
974 if (!check_for_inc_dec_1 (insn_info
))
976 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
978 fprintf (dump_file
, "Locally deleting insn %d ",
979 INSN_UID (insn_info
->insn
));
980 if (insn_info
->store_rec
->alias_set
)
981 fprintf (dump_file
, "alias set %d\n",
982 (int) insn_info
->store_rec
->alias_set
);
984 fprintf (dump_file
, "\n");
987 free_store_info (insn_info
);
988 read_info
= insn_info
->read_rec
;
992 read_info_t next
= read_info
->next
;
993 pool_free (read_info_pool
, read_info
);
996 insn_info
->read_rec
= NULL
;
998 delete_insn (insn_info
->insn
);
1000 insn_info
->insn
= NULL
;
1002 insn_info
->wild_read
= false;
1005 /* Return whether DECL, a local variable, can possibly escape the current
1009 local_variable_can_escape (tree decl
)
1011 if (TREE_ADDRESSABLE (decl
))
1014 /* If this is a partitioned variable, we need to consider all the variables
1015 in the partition. This is necessary because a store into one of them can
1016 be replaced with a store into another and this may not change the outcome
1017 of the escape analysis. */
1018 if (cfun
->gimple_df
->decls_to_pointers
!= NULL
)
1020 tree
*namep
= cfun
->gimple_df
->decls_to_pointers
->get (decl
);
1022 return TREE_ADDRESSABLE (*namep
);
1028 /* Return whether EXPR can possibly escape the current function scope. */
1031 can_escape (tree expr
)
1036 base
= get_base_address (expr
);
1038 && !may_be_aliased (base
)
1039 && !(TREE_CODE (base
) == VAR_DECL
1040 && !DECL_EXTERNAL (base
)
1041 && !TREE_STATIC (base
)
1042 && local_variable_can_escape (base
)))
1047 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
1048 OFFSET and WIDTH. */
1051 set_usage_bits (group_info_t group
, HOST_WIDE_INT offset
, HOST_WIDE_INT width
,
1055 bool expr_escapes
= can_escape (expr
);
1056 if (offset
> -MAX_OFFSET
&& offset
+ width
< MAX_OFFSET
)
1057 for (i
=offset
; i
<offset
+width
; i
++)
1065 store1
= group
->store1_n
;
1066 store2
= group
->store2_n
;
1067 escaped
= group
->escaped_n
;
1072 store1
= group
->store1_p
;
1073 store2
= group
->store2_p
;
1074 escaped
= group
->escaped_p
;
1078 if (!bitmap_set_bit (store1
, ai
))
1079 bitmap_set_bit (store2
, ai
);
1084 if (group
->offset_map_size_n
< ai
)
1085 group
->offset_map_size_n
= ai
;
1089 if (group
->offset_map_size_p
< ai
)
1090 group
->offset_map_size_p
= ai
;
1094 bitmap_set_bit (escaped
, ai
);
1099 reset_active_stores (void)
1101 active_local_stores
= NULL
;
1102 active_local_stores_len
= 0;
1105 /* Free all READ_REC of the LAST_INSN of BB_INFO. */
1108 free_read_records (bb_info_t bb_info
)
1110 insn_info_t insn_info
= bb_info
->last_insn
;
1111 read_info_t
*ptr
= &insn_info
->read_rec
;
1114 read_info_t next
= (*ptr
)->next
;
1115 if ((*ptr
)->alias_set
== 0)
1117 pool_free (read_info_pool
, *ptr
);
1121 ptr
= &(*ptr
)->next
;
1125 /* Set the BB_INFO so that the last insn is marked as a wild read. */
1128 add_wild_read (bb_info_t bb_info
)
1130 insn_info_t insn_info
= bb_info
->last_insn
;
1131 insn_info
->wild_read
= true;
1132 free_read_records (bb_info
);
1133 reset_active_stores ();
1136 /* Set the BB_INFO so that the last insn is marked as a wild read of
1137 non-frame locations. */
1140 add_non_frame_wild_read (bb_info_t bb_info
)
1142 insn_info_t insn_info
= bb_info
->last_insn
;
1143 insn_info
->non_frame_wild_read
= true;
1144 free_read_records (bb_info
);
1145 reset_active_stores ();
1148 /* Return true if X is a constant or one of the registers that behave
1149 as a constant over the life of a function. This is equivalent to
1150 !rtx_varies_p for memory addresses. */
1153 const_or_frame_p (rtx x
)
1158 if (GET_CODE (x
) == REG
)
1160 /* Note that we have to test for the actual rtx used for the frame
1161 and arg pointers and not just the register number in case we have
1162 eliminated the frame and/or arg pointer and are using it
1164 if (x
== frame_pointer_rtx
|| x
== hard_frame_pointer_rtx
1165 /* The arg pointer varies if it is not a fixed register. */
1166 || (x
== arg_pointer_rtx
&& fixed_regs
[ARG_POINTER_REGNUM
])
1167 || x
== pic_offset_table_rtx
)
1175 /* Take all reasonable action to put the address of MEM into the form
1176 that we can do analysis on.
1178 The gold standard is to get the address into the form: address +
1179 OFFSET where address is something that rtx_varies_p considers a
1180 constant. When we can get the address in this form, we can do
1181 global analysis on it. Note that for constant bases, address is
1182 not actually returned, only the group_id. The address can be
1185 If that fails, we try cselib to get a value we can at least use
1186 locally. If that fails we return false.
1188 The GROUP_ID is set to -1 for cselib bases and the index of the
1189 group for non_varying bases.
1191 FOR_READ is true if this is a mem read and false if not. */
1194 canon_address (rtx mem
,
1195 alias_set_type
*alias_set_out
,
1197 HOST_WIDE_INT
*offset
,
1200 machine_mode address_mode
= get_address_mode (mem
);
1201 rtx mem_address
= XEXP (mem
, 0);
1202 rtx expanded_address
, address
;
1207 cselib_lookup (mem_address
, address_mode
, 1, GET_MODE (mem
));
1209 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1211 fprintf (dump_file
, " mem: ");
1212 print_inline_rtx (dump_file
, mem_address
, 0);
1213 fprintf (dump_file
, "\n");
1216 /* First see if just canon_rtx (mem_address) is const or frame,
1217 if not, try cselib_expand_value_rtx and call canon_rtx on that. */
1219 for (expanded
= 0; expanded
< 2; expanded
++)
1223 /* Use cselib to replace all of the reg references with the full
1224 expression. This will take care of the case where we have
1226 r_x = base + offset;
1231 val = *(base + offset); */
1233 expanded_address
= cselib_expand_value_rtx (mem_address
,
1236 /* If this fails, just go with the address from first
1238 if (!expanded_address
)
1242 expanded_address
= mem_address
;
1244 /* Split the address into canonical BASE + OFFSET terms. */
1245 address
= canon_rtx (expanded_address
);
1249 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1253 fprintf (dump_file
, "\n after cselib_expand address: ");
1254 print_inline_rtx (dump_file
, expanded_address
, 0);
1255 fprintf (dump_file
, "\n");
1258 fprintf (dump_file
, "\n after canon_rtx address: ");
1259 print_inline_rtx (dump_file
, address
, 0);
1260 fprintf (dump_file
, "\n");
1263 if (GET_CODE (address
) == CONST
)
1264 address
= XEXP (address
, 0);
1266 if (GET_CODE (address
) == PLUS
1267 && CONST_INT_P (XEXP (address
, 1)))
1269 *offset
= INTVAL (XEXP (address
, 1));
1270 address
= XEXP (address
, 0);
1273 if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem
))
1274 && const_or_frame_p (address
))
1276 group_info_t group
= get_group_info (address
);
1278 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1279 fprintf (dump_file
, " gid=%d offset=%d \n",
1280 group
->id
, (int)*offset
);
1282 *group_id
= group
->id
;
1287 *base
= cselib_lookup (address
, address_mode
, true, GET_MODE (mem
));
1292 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1293 fprintf (dump_file
, " no cselib val - should be a wild read.\n");
1296 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1297 fprintf (dump_file
, " varying cselib base=%u:%u offset = %d\n",
1298 (*base
)->uid
, (*base
)->hash
, (int)*offset
);
1303 /* Clear the rhs field from the active_local_stores array. */
1306 clear_rhs_from_active_local_stores (void)
1308 insn_info_t ptr
= active_local_stores
;
1312 store_info_t store_info
= ptr
->store_rec
;
1313 /* Skip the clobbers. */
1314 while (!store_info
->is_set
)
1315 store_info
= store_info
->next
;
1317 store_info
->rhs
= NULL
;
1318 store_info
->const_rhs
= NULL
;
1320 ptr
= ptr
->next_local_store
;
1325 /* Mark byte POS bytes from the beginning of store S_INFO as unneeded. */
1328 set_position_unneeded (store_info_t s_info
, int pos
)
1330 if (__builtin_expect (s_info
->is_large
, false))
1332 if (bitmap_set_bit (s_info
->positions_needed
.large
.bmap
, pos
))
1333 s_info
->positions_needed
.large
.count
++;
1336 s_info
->positions_needed
.small_bitmask
1337 &= ~(((unsigned HOST_WIDE_INT
) 1) << pos
);
1340 /* Mark the whole store S_INFO as unneeded. */
1343 set_all_positions_unneeded (store_info_t s_info
)
1345 if (__builtin_expect (s_info
->is_large
, false))
1347 int pos
, end
= s_info
->end
- s_info
->begin
;
1348 for (pos
= 0; pos
< end
; pos
++)
1349 bitmap_set_bit (s_info
->positions_needed
.large
.bmap
, pos
);
1350 s_info
->positions_needed
.large
.count
= end
;
1353 s_info
->positions_needed
.small_bitmask
= (unsigned HOST_WIDE_INT
) 0;
1356 /* Return TRUE if any bytes from S_INFO store are needed. */
1359 any_positions_needed_p (store_info_t s_info
)
1361 if (__builtin_expect (s_info
->is_large
, false))
1362 return (s_info
->positions_needed
.large
.count
1363 < s_info
->end
- s_info
->begin
);
1365 return (s_info
->positions_needed
.small_bitmask
1366 != (unsigned HOST_WIDE_INT
) 0);
1369 /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
1370 store are needed. */
1373 all_positions_needed_p (store_info_t s_info
, int start
, int width
)
1375 if (__builtin_expect (s_info
->is_large
, false))
1377 int end
= start
+ width
;
1379 if (bitmap_bit_p (s_info
->positions_needed
.large
.bmap
, start
++))
1385 unsigned HOST_WIDE_INT mask
= lowpart_bitmask (width
) << start
;
1386 return (s_info
->positions_needed
.small_bitmask
& mask
) == mask
;
1391 static rtx
get_stored_val (store_info_t
, machine_mode
, HOST_WIDE_INT
,
1392 HOST_WIDE_INT
, basic_block
, bool);
1395 /* BODY is an instruction pattern that belongs to INSN. Return 1 if
1396 there is a candidate store, after adding it to the appropriate
1397 local store group if so. */
1400 record_store (rtx body
, bb_info_t bb_info
)
1402 rtx mem
, rhs
, const_rhs
, mem_addr
;
1403 HOST_WIDE_INT offset
= 0;
1404 HOST_WIDE_INT width
= 0;
1405 alias_set_type spill_alias_set
;
1406 insn_info_t insn_info
= bb_info
->last_insn
;
1407 store_info_t store_info
= NULL
;
1409 cselib_val
*base
= NULL
;
1410 insn_info_t ptr
, last
, redundant_reason
;
1411 bool store_is_unused
;
1413 if (GET_CODE (body
) != SET
&& GET_CODE (body
) != CLOBBER
)
1416 mem
= SET_DEST (body
);
1418 /* If this is not used, then this cannot be used to keep the insn
1419 from being deleted. On the other hand, it does provide something
1420 that can be used to prove that another store is dead. */
1422 = (find_reg_note (insn_info
->insn
, REG_UNUSED
, mem
) != NULL
);
1424 /* Check whether that value is a suitable memory location. */
1427 /* If the set or clobber is unused, then it does not effect our
1428 ability to get rid of the entire insn. */
1429 if (!store_is_unused
)
1430 insn_info
->cannot_delete
= true;
1434 /* At this point we know mem is a mem. */
1435 if (GET_MODE (mem
) == BLKmode
)
1437 if (GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
1439 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1440 fprintf (dump_file
, " adding wild read for (clobber (mem:BLK (scratch))\n");
1441 add_wild_read (bb_info
);
1442 insn_info
->cannot_delete
= true;
1445 /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
1446 as memset (addr, 0, 36); */
1447 else if (!MEM_SIZE_KNOWN_P (mem
)
1448 || MEM_SIZE (mem
) <= 0
1449 || MEM_SIZE (mem
) > MAX_OFFSET
1450 || GET_CODE (body
) != SET
1451 || !CONST_INT_P (SET_SRC (body
)))
1453 if (!store_is_unused
)
1455 /* If the set or clobber is unused, then it does not effect our
1456 ability to get rid of the entire insn. */
1457 insn_info
->cannot_delete
= true;
1458 clear_rhs_from_active_local_stores ();
1464 /* We can still process a volatile mem, we just cannot delete it. */
1465 if (MEM_VOLATILE_P (mem
))
1466 insn_info
->cannot_delete
= true;
1468 if (!canon_address (mem
, &spill_alias_set
, &group_id
, &offset
, &base
))
1470 clear_rhs_from_active_local_stores ();
1474 if (GET_MODE (mem
) == BLKmode
)
1475 width
= MEM_SIZE (mem
);
1477 width
= GET_MODE_SIZE (GET_MODE (mem
));
1479 if (spill_alias_set
)
1481 bitmap store1
= clear_alias_group
->store1_p
;
1482 bitmap store2
= clear_alias_group
->store2_p
;
1484 gcc_assert (GET_MODE (mem
) != BLKmode
);
1486 if (!bitmap_set_bit (store1
, spill_alias_set
))
1487 bitmap_set_bit (store2
, spill_alias_set
);
1489 if (clear_alias_group
->offset_map_size_p
< spill_alias_set
)
1490 clear_alias_group
->offset_map_size_p
= spill_alias_set
;
1492 store_info
= (store_info_t
) pool_alloc (rtx_store_info_pool
);
1494 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1495 fprintf (dump_file
, " processing spill store %d(%s)\n",
1496 (int) spill_alias_set
, GET_MODE_NAME (GET_MODE (mem
)));
1498 else if (group_id
>= 0)
1500 /* In the restrictive case where the base is a constant or the
1501 frame pointer we can do global analysis. */
1504 = rtx_group_vec
[group_id
];
1505 tree expr
= MEM_EXPR (mem
);
1507 store_info
= (store_info_t
) pool_alloc (rtx_store_info_pool
);
1508 set_usage_bits (group
, offset
, width
, expr
);
1510 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1511 fprintf (dump_file
, " processing const base store gid=%d[%d..%d)\n",
1512 group_id
, (int)offset
, (int)(offset
+width
));
1516 if (may_be_sp_based_p (XEXP (mem
, 0)))
1517 insn_info
->stack_pointer_based
= true;
1518 insn_info
->contains_cselib_groups
= true;
1520 store_info
= (store_info_t
) pool_alloc (cse_store_info_pool
);
1523 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1524 fprintf (dump_file
, " processing cselib store [%d..%d)\n",
1525 (int)offset
, (int)(offset
+width
));
1528 const_rhs
= rhs
= NULL_RTX
;
1529 if (GET_CODE (body
) == SET
1530 /* No place to keep the value after ra. */
1531 && !reload_completed
1532 && (REG_P (SET_SRC (body
))
1533 || GET_CODE (SET_SRC (body
)) == SUBREG
1534 || CONSTANT_P (SET_SRC (body
)))
1535 && !MEM_VOLATILE_P (mem
)
1536 /* Sometimes the store and reload is used for truncation and
1538 && !(FLOAT_MODE_P (GET_MODE (mem
)) && (flag_float_store
)))
1540 rhs
= SET_SRC (body
);
1541 if (CONSTANT_P (rhs
))
1543 else if (body
== PATTERN (insn_info
->insn
))
1545 rtx tem
= find_reg_note (insn_info
->insn
, REG_EQUAL
, NULL_RTX
);
1546 if (tem
&& CONSTANT_P (XEXP (tem
, 0)))
1547 const_rhs
= XEXP (tem
, 0);
1549 if (const_rhs
== NULL_RTX
&& REG_P (rhs
))
1551 rtx tem
= cselib_expand_value_rtx (rhs
, scratch
, 5);
1553 if (tem
&& CONSTANT_P (tem
))
1558 /* Check to see if this stores causes some other stores to be
1560 ptr
= active_local_stores
;
1562 redundant_reason
= NULL
;
1563 mem
= canon_rtx (mem
);
1564 /* For alias_set != 0 canon_true_dependence should be never called. */
1565 if (spill_alias_set
)
1566 mem_addr
= NULL_RTX
;
1570 mem_addr
= base
->val_rtx
;
1574 = rtx_group_vec
[group_id
];
1575 mem_addr
= group
->canon_base_addr
;
1578 mem_addr
= plus_constant (get_address_mode (mem
), mem_addr
, offset
);
1583 insn_info_t next
= ptr
->next_local_store
;
1584 store_info_t s_info
= ptr
->store_rec
;
1587 /* Skip the clobbers. We delete the active insn if this insn
1588 shadows the set. To have been put on the active list, it
1589 has exactly on set. */
1590 while (!s_info
->is_set
)
1591 s_info
= s_info
->next
;
1593 if (s_info
->alias_set
!= spill_alias_set
)
1595 else if (s_info
->alias_set
)
1597 struct clear_alias_mode_holder
*entry
1598 = clear_alias_set_lookup (s_info
->alias_set
);
1599 /* Generally, spills cannot be processed if and of the
1600 references to the slot have a different mode. But if
1601 we are in the same block and mode is exactly the same
1602 between this store and one before in the same block,
1603 we can still delete it. */
1604 if ((GET_MODE (mem
) == GET_MODE (s_info
->mem
))
1605 && (GET_MODE (mem
) == entry
->mode
))
1608 set_all_positions_unneeded (s_info
);
1610 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1611 fprintf (dump_file
, " trying spill store in insn=%d alias_set=%d\n",
1612 INSN_UID (ptr
->insn
), (int) s_info
->alias_set
);
1614 else if ((s_info
->group_id
== group_id
)
1615 && (s_info
->cse_base
== base
))
1618 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1619 fprintf (dump_file
, " trying store in insn=%d gid=%d[%d..%d)\n",
1620 INSN_UID (ptr
->insn
), s_info
->group_id
,
1621 (int)s_info
->begin
, (int)s_info
->end
);
1623 /* Even if PTR won't be eliminated as unneeded, if both
1624 PTR and this insn store the same constant value, we might
1625 eliminate this insn instead. */
1626 if (s_info
->const_rhs
1628 && offset
>= s_info
->begin
1629 && offset
+ width
<= s_info
->end
1630 && all_positions_needed_p (s_info
, offset
- s_info
->begin
,
1633 if (GET_MODE (mem
) == BLKmode
)
1635 if (GET_MODE (s_info
->mem
) == BLKmode
1636 && s_info
->const_rhs
== const_rhs
)
1637 redundant_reason
= ptr
;
1639 else if (s_info
->const_rhs
== const0_rtx
1640 && const_rhs
== const0_rtx
)
1641 redundant_reason
= ptr
;
1646 val
= get_stored_val (s_info
, GET_MODE (mem
),
1647 offset
, offset
+ width
,
1648 BLOCK_FOR_INSN (insn_info
->insn
),
1650 if (get_insns () != NULL
)
1653 if (val
&& rtx_equal_p (val
, const_rhs
))
1654 redundant_reason
= ptr
;
1658 for (i
= MAX (offset
, s_info
->begin
);
1659 i
< offset
+ width
&& i
< s_info
->end
;
1661 set_position_unneeded (s_info
, i
- s_info
->begin
);
1663 else if (s_info
->rhs
)
1664 /* Need to see if it is possible for this store to overwrite
1665 the value of store_info. If it is, set the rhs to NULL to
1666 keep it from being used to remove a load. */
1668 if (canon_true_dependence (s_info
->mem
,
1669 GET_MODE (s_info
->mem
),
1674 s_info
->const_rhs
= NULL
;
1678 /* An insn can be deleted if every position of every one of
1679 its s_infos is zero. */
1680 if (any_positions_needed_p (s_info
))
1685 insn_info_t insn_to_delete
= ptr
;
1687 active_local_stores_len
--;
1689 last
->next_local_store
= ptr
->next_local_store
;
1691 active_local_stores
= ptr
->next_local_store
;
1693 if (!insn_to_delete
->cannot_delete
)
1694 delete_dead_store_insn (insn_to_delete
);
1702 /* Finish filling in the store_info. */
1703 store_info
->next
= insn_info
->store_rec
;
1704 insn_info
->store_rec
= store_info
;
1705 store_info
->mem
= mem
;
1706 store_info
->alias_set
= spill_alias_set
;
1707 store_info
->mem_addr
= mem_addr
;
1708 store_info
->cse_base
= base
;
1709 if (width
> HOST_BITS_PER_WIDE_INT
)
1711 store_info
->is_large
= true;
1712 store_info
->positions_needed
.large
.count
= 0;
1713 store_info
->positions_needed
.large
.bmap
= BITMAP_ALLOC (&dse_bitmap_obstack
);
1717 store_info
->is_large
= false;
1718 store_info
->positions_needed
.small_bitmask
= lowpart_bitmask (width
);
1720 store_info
->group_id
= group_id
;
1721 store_info
->begin
= offset
;
1722 store_info
->end
= offset
+ width
;
1723 store_info
->is_set
= GET_CODE (body
) == SET
;
1724 store_info
->rhs
= rhs
;
1725 store_info
->const_rhs
= const_rhs
;
1726 store_info
->redundant_reason
= redundant_reason
;
1728 /* If this is a clobber, we return 0. We will only be able to
1729 delete this insn if there is only one store USED store, but we
1730 can use the clobber to delete other stores earlier. */
1731 return store_info
->is_set
? 1 : 0;
1736 dump_insn_info (const char * start
, insn_info_t insn_info
)
1738 fprintf (dump_file
, "%s insn=%d %s\n", start
,
1739 INSN_UID (insn_info
->insn
),
1740 insn_info
->store_rec
? "has store" : "naked");
1744 /* If the modes are different and the value's source and target do not
1745 line up, we need to extract the value from lower part of the rhs of
1746 the store, shift it, and then put it into a form that can be shoved
1747 into the read_insn. This function generates a right SHIFT of a
1748 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The
1749 shift sequence is returned or NULL if we failed to find a
1753 find_shift_sequence (int access_size
,
1754 store_info_t store_info
,
1755 machine_mode read_mode
,
1756 int shift
, bool speed
, bool require_cst
)
1758 machine_mode store_mode
= GET_MODE (store_info
->mem
);
1759 machine_mode new_mode
;
1760 rtx read_reg
= NULL
;
1762 /* Some machines like the x86 have shift insns for each size of
1763 operand. Other machines like the ppc or the ia-64 may only have
1764 shift insns that shift values within 32 or 64 bit registers.
1765 This loop tries to find the smallest shift insn that will right
1766 justify the value we want to read but is available in one insn on
1769 for (new_mode
= smallest_mode_for_size (access_size
* BITS_PER_UNIT
,
1771 GET_MODE_BITSIZE (new_mode
) <= BITS_PER_WORD
;
1772 new_mode
= GET_MODE_WIDER_MODE (new_mode
))
1774 rtx target
, new_reg
, new_lhs
;
1775 rtx_insn
*shift_seq
, *insn
;
1778 /* If a constant was stored into memory, try to simplify it here,
1779 otherwise the cost of the shift might preclude this optimization
1780 e.g. at -Os, even when no actual shift will be needed. */
1781 if (store_info
->const_rhs
)
1783 unsigned int byte
= subreg_lowpart_offset (new_mode
, store_mode
);
1784 rtx ret
= simplify_subreg (new_mode
, store_info
->const_rhs
,
1786 if (ret
&& CONSTANT_P (ret
))
1788 ret
= simplify_const_binary_operation (LSHIFTRT
, new_mode
,
1789 ret
, GEN_INT (shift
));
1790 if (ret
&& CONSTANT_P (ret
))
1792 byte
= subreg_lowpart_offset (read_mode
, new_mode
);
1793 ret
= simplify_subreg (read_mode
, ret
, new_mode
, byte
);
1794 if (ret
&& CONSTANT_P (ret
)
1795 && set_src_cost (ret
, speed
) <= COSTS_N_INSNS (1))
1804 /* Try a wider mode if truncating the store mode to NEW_MODE
1805 requires a real instruction. */
1806 if (GET_MODE_BITSIZE (new_mode
) < GET_MODE_BITSIZE (store_mode
)
1807 && !TRULY_NOOP_TRUNCATION_MODES_P (new_mode
, store_mode
))
1810 /* Also try a wider mode if the necessary punning is either not
1811 desirable or not possible. */
1812 if (!CONSTANT_P (store_info
->rhs
)
1813 && !MODES_TIEABLE_P (new_mode
, store_mode
))
1816 new_reg
= gen_reg_rtx (new_mode
);
1820 /* In theory we could also check for an ashr. Ian Taylor knows
1821 of one dsp where the cost of these two was not the same. But
1822 this really is a rare case anyway. */
1823 target
= expand_binop (new_mode
, lshr_optab
, new_reg
,
1824 GEN_INT (shift
), new_reg
, 1, OPTAB_DIRECT
);
1826 shift_seq
= get_insns ();
1829 if (target
!= new_reg
|| shift_seq
== NULL
)
1833 for (insn
= shift_seq
; insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
1835 cost
+= insn_rtx_cost (PATTERN (insn
), speed
);
1837 /* The computation up to here is essentially independent
1838 of the arguments and could be precomputed. It may
1839 not be worth doing so. We could precompute if
1840 worthwhile or at least cache the results. The result
1841 technically depends on both SHIFT and ACCESS_SIZE,
1842 but in practice the answer will depend only on ACCESS_SIZE. */
1844 if (cost
> COSTS_N_INSNS (1))
1847 new_lhs
= extract_low_bits (new_mode
, store_mode
,
1848 copy_rtx (store_info
->rhs
));
1849 if (new_lhs
== NULL_RTX
)
1852 /* We found an acceptable shift. Generate a move to
1853 take the value from the store and put it into the
1854 shift pseudo, then shift it, then generate another
1855 move to put in into the target of the read. */
1856 emit_move_insn (new_reg
, new_lhs
);
1857 emit_insn (shift_seq
);
1858 read_reg
= extract_low_bits (read_mode
, new_mode
, new_reg
);
1866 /* Call back for note_stores to find the hard regs set or clobbered by
1867 insn. Data is a bitmap of the hardregs set so far. */
1870 look_for_hardregs (rtx x
, const_rtx pat ATTRIBUTE_UNUSED
, void *data
)
1872 bitmap regs_set
= (bitmap
) data
;
1875 && HARD_REGISTER_P (x
))
1877 unsigned int regno
= REGNO (x
);
1878 bitmap_set_range (regs_set
, regno
,
1879 hard_regno_nregs
[regno
][GET_MODE (x
)]);
1883 /* Helper function for replace_read and record_store.
1884 Attempt to return a value stored in STORE_INFO, from READ_BEGIN
1885 to one before READ_END bytes read in READ_MODE. Return NULL
1886 if not successful. If REQUIRE_CST is true, return always constant. */
1889 get_stored_val (store_info_t store_info
, machine_mode read_mode
,
1890 HOST_WIDE_INT read_begin
, HOST_WIDE_INT read_end
,
1891 basic_block bb
, bool require_cst
)
1893 machine_mode store_mode
= GET_MODE (store_info
->mem
);
1895 int access_size
; /* In bytes. */
1898 /* To get here the read is within the boundaries of the write so
1899 shift will never be negative. Start out with the shift being in
1901 if (store_mode
== BLKmode
)
1903 else if (BYTES_BIG_ENDIAN
)
1904 shift
= store_info
->end
- read_end
;
1906 shift
= read_begin
- store_info
->begin
;
1908 access_size
= shift
+ GET_MODE_SIZE (read_mode
);
1910 /* From now on it is bits. */
1911 shift
*= BITS_PER_UNIT
;
1914 read_reg
= find_shift_sequence (access_size
, store_info
, read_mode
, shift
,
1915 optimize_bb_for_speed_p (bb
),
1917 else if (store_mode
== BLKmode
)
1919 /* The store is a memset (addr, const_val, const_size). */
1920 gcc_assert (CONST_INT_P (store_info
->rhs
));
1921 store_mode
= int_mode_for_mode (read_mode
);
1922 if (store_mode
== BLKmode
)
1923 read_reg
= NULL_RTX
;
1924 else if (store_info
->rhs
== const0_rtx
)
1925 read_reg
= extract_low_bits (read_mode
, store_mode
, const0_rtx
);
1926 else if (GET_MODE_BITSIZE (store_mode
) > HOST_BITS_PER_WIDE_INT
1927 || BITS_PER_UNIT
>= HOST_BITS_PER_WIDE_INT
)
1928 read_reg
= NULL_RTX
;
1931 unsigned HOST_WIDE_INT c
1932 = INTVAL (store_info
->rhs
)
1933 & (((HOST_WIDE_INT
) 1 << BITS_PER_UNIT
) - 1);
1934 int shift
= BITS_PER_UNIT
;
1935 while (shift
< HOST_BITS_PER_WIDE_INT
)
1940 read_reg
= gen_int_mode (c
, store_mode
);
1941 read_reg
= extract_low_bits (read_mode
, store_mode
, read_reg
);
1944 else if (store_info
->const_rhs
1946 || GET_MODE_CLASS (read_mode
) != GET_MODE_CLASS (store_mode
)))
1947 read_reg
= extract_low_bits (read_mode
, store_mode
,
1948 copy_rtx (store_info
->const_rhs
));
1950 read_reg
= extract_low_bits (read_mode
, store_mode
,
1951 copy_rtx (store_info
->rhs
));
1952 if (require_cst
&& read_reg
&& !CONSTANT_P (read_reg
))
1953 read_reg
= NULL_RTX
;
1957 /* Take a sequence of:
1980 Depending on the alignment and the mode of the store and
1984 The STORE_INFO and STORE_INSN are for the store and READ_INFO
1985 and READ_INSN are for the read. Return true if the replacement
1989 replace_read (store_info_t store_info
, insn_info_t store_insn
,
1990 read_info_t read_info
, insn_info_t read_insn
, rtx
*loc
,
1993 machine_mode store_mode
= GET_MODE (store_info
->mem
);
1994 machine_mode read_mode
= GET_MODE (read_info
->mem
);
1995 rtx_insn
*insns
, *this_insn
;
2002 /* Create a sequence of instructions to set up the read register.
2003 This sequence goes immediately before the store and its result
2004 is read by the load.
2006 We need to keep this in perspective. We are replacing a read
2007 with a sequence of insns, but the read will almost certainly be
2008 in cache, so it is not going to be an expensive one. Thus, we
2009 are not willing to do a multi insn shift or worse a subroutine
2010 call to get rid of the read. */
2011 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2012 fprintf (dump_file
, "trying to replace %smode load in insn %d"
2013 " from %smode store in insn %d\n",
2014 GET_MODE_NAME (read_mode
), INSN_UID (read_insn
->insn
),
2015 GET_MODE_NAME (store_mode
), INSN_UID (store_insn
->insn
));
2017 bb
= BLOCK_FOR_INSN (read_insn
->insn
);
2018 read_reg
= get_stored_val (store_info
,
2019 read_mode
, read_info
->begin
, read_info
->end
,
2021 if (read_reg
== NULL_RTX
)
2024 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2025 fprintf (dump_file
, " -- could not extract bits of stored value\n");
2028 /* Force the value into a new register so that it won't be clobbered
2029 between the store and the load. */
2030 read_reg
= copy_to_mode_reg (read_mode
, read_reg
);
2031 insns
= get_insns ();
2034 if (insns
!= NULL_RTX
)
2036 /* Now we have to scan the set of new instructions to see if the
2037 sequence contains and sets of hardregs that happened to be
2038 live at this point. For instance, this can happen if one of
2039 the insns sets the CC and the CC happened to be live at that
2040 point. This does occasionally happen, see PR 37922. */
2041 bitmap regs_set
= BITMAP_ALLOC (®_obstack
);
2043 for (this_insn
= insns
; this_insn
!= NULL_RTX
; this_insn
= NEXT_INSN (this_insn
))
2044 note_stores (PATTERN (this_insn
), look_for_hardregs
, regs_set
);
2046 bitmap_and_into (regs_set
, regs_live
);
2047 if (!bitmap_empty_p (regs_set
))
2049 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2052 "abandoning replacement because sequence clobbers live hardregs:");
2053 df_print_regset (dump_file
, regs_set
);
2056 BITMAP_FREE (regs_set
);
2059 BITMAP_FREE (regs_set
);
2062 if (validate_change (read_insn
->insn
, loc
, read_reg
, 0))
2064 deferred_change_t deferred_change
=
2065 (deferred_change_t
) pool_alloc (deferred_change_pool
);
2067 /* Insert this right before the store insn where it will be safe
2068 from later insns that might change it before the read. */
2069 emit_insn_before (insns
, store_insn
->insn
);
2071 /* And now for the kludge part: cselib croaks if you just
2072 return at this point. There are two reasons for this:
2074 1) Cselib has an idea of how many pseudos there are and
2075 that does not include the new ones we just added.
2077 2) Cselib does not know about the move insn we added
2078 above the store_info, and there is no way to tell it
2079 about it, because it has "moved on".
2081 Problem (1) is fixable with a certain amount of engineering.
2082 Problem (2) is requires starting the bb from scratch. This
2085 So we are just going to have to lie. The move/extraction
2086 insns are not really an issue, cselib did not see them. But
2087 the use of the new pseudo read_insn is a real problem because
2088 cselib has not scanned this insn. The way that we solve this
2089 problem is that we are just going to put the mem back for now
2090 and when we are finished with the block, we undo this. We
2091 keep a table of mems to get rid of. At the end of the basic
2092 block we can put them back. */
2094 *loc
= read_info
->mem
;
2095 deferred_change
->next
= deferred_change_list
;
2096 deferred_change_list
= deferred_change
;
2097 deferred_change
->loc
= loc
;
2098 deferred_change
->reg
= read_reg
;
2100 /* Get rid of the read_info, from the point of view of the
2101 rest of dse, play like this read never happened. */
2102 read_insn
->read_rec
= read_info
->next
;
2103 pool_free (read_info_pool
, read_info
);
2104 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2106 fprintf (dump_file
, " -- replaced the loaded MEM with ");
2107 print_simple_rtl (dump_file
, read_reg
);
2108 fprintf (dump_file
, "\n");
2114 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2116 fprintf (dump_file
, " -- replacing the loaded MEM with ");
2117 print_simple_rtl (dump_file
, read_reg
);
2118 fprintf (dump_file
, " led to an invalid instruction\n");
2124 /* Check the address of MEM *LOC and kill any appropriate stores that may
2128 check_mem_read_rtx (rtx
*loc
, bb_info_t bb_info
)
2130 rtx mem
= *loc
, mem_addr
;
2131 insn_info_t insn_info
;
2132 HOST_WIDE_INT offset
= 0;
2133 HOST_WIDE_INT width
= 0;
2134 alias_set_type spill_alias_set
= 0;
2135 cselib_val
*base
= NULL
;
2137 read_info_t read_info
;
2139 insn_info
= bb_info
->last_insn
;
2141 if ((MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2142 || (MEM_VOLATILE_P (mem
)))
2144 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2145 fprintf (dump_file
, " adding wild read, volatile or barrier.\n");
2146 add_wild_read (bb_info
);
2147 insn_info
->cannot_delete
= true;
2151 /* If it is reading readonly mem, then there can be no conflict with
2153 if (MEM_READONLY_P (mem
))
2156 if (!canon_address (mem
, &spill_alias_set
, &group_id
, &offset
, &base
))
2158 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2159 fprintf (dump_file
, " adding wild read, canon_address failure.\n");
2160 add_wild_read (bb_info
);
2164 if (GET_MODE (mem
) == BLKmode
)
2167 width
= GET_MODE_SIZE (GET_MODE (mem
));
2169 read_info
= (read_info_t
) pool_alloc (read_info_pool
);
2170 read_info
->group_id
= group_id
;
2171 read_info
->mem
= mem
;
2172 read_info
->alias_set
= spill_alias_set
;
2173 read_info
->begin
= offset
;
2174 read_info
->end
= offset
+ width
;
2175 read_info
->next
= insn_info
->read_rec
;
2176 insn_info
->read_rec
= read_info
;
2177 /* For alias_set != 0 canon_true_dependence should be never called. */
2178 if (spill_alias_set
)
2179 mem_addr
= NULL_RTX
;
2183 mem_addr
= base
->val_rtx
;
2187 = rtx_group_vec
[group_id
];
2188 mem_addr
= group
->canon_base_addr
;
2191 mem_addr
= plus_constant (get_address_mode (mem
), mem_addr
, offset
);
2194 /* We ignore the clobbers in store_info. The is mildly aggressive,
2195 but there really should not be a clobber followed by a read. */
2197 if (spill_alias_set
)
2199 insn_info_t i_ptr
= active_local_stores
;
2200 insn_info_t last
= NULL
;
2202 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2203 fprintf (dump_file
, " processing spill load %d\n",
2204 (int) spill_alias_set
);
2208 store_info_t store_info
= i_ptr
->store_rec
;
2210 /* Skip the clobbers. */
2211 while (!store_info
->is_set
)
2212 store_info
= store_info
->next
;
2214 if (store_info
->alias_set
== spill_alias_set
)
2216 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2217 dump_insn_info ("removing from active", i_ptr
);
2219 active_local_stores_len
--;
2221 last
->next_local_store
= i_ptr
->next_local_store
;
2223 active_local_stores
= i_ptr
->next_local_store
;
2227 i_ptr
= i_ptr
->next_local_store
;
2230 else if (group_id
>= 0)
2232 /* This is the restricted case where the base is a constant or
2233 the frame pointer and offset is a constant. */
2234 insn_info_t i_ptr
= active_local_stores
;
2235 insn_info_t last
= NULL
;
2237 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2240 fprintf (dump_file
, " processing const load gid=%d[BLK]\n",
2243 fprintf (dump_file
, " processing const load gid=%d[%d..%d)\n",
2244 group_id
, (int)offset
, (int)(offset
+width
));
2249 bool remove
= false;
2250 store_info_t store_info
= i_ptr
->store_rec
;
2252 /* Skip the clobbers. */
2253 while (!store_info
->is_set
)
2254 store_info
= store_info
->next
;
2256 /* There are three cases here. */
2257 if (store_info
->group_id
< 0)
2258 /* We have a cselib store followed by a read from a
2261 = canon_true_dependence (store_info
->mem
,
2262 GET_MODE (store_info
->mem
),
2263 store_info
->mem_addr
,
2266 else if (group_id
== store_info
->group_id
)
2268 /* This is a block mode load. We may get lucky and
2269 canon_true_dependence may save the day. */
2272 = canon_true_dependence (store_info
->mem
,
2273 GET_MODE (store_info
->mem
),
2274 store_info
->mem_addr
,
2277 /* If this read is just reading back something that we just
2278 stored, rewrite the read. */
2282 && offset
>= store_info
->begin
2283 && offset
+ width
<= store_info
->end
2284 && all_positions_needed_p (store_info
,
2285 offset
- store_info
->begin
,
2287 && replace_read (store_info
, i_ptr
, read_info
,
2288 insn_info
, loc
, bb_info
->regs_live
))
2291 /* The bases are the same, just see if the offsets
2293 if ((offset
< store_info
->end
)
2294 && (offset
+ width
> store_info
->begin
))
2300 The else case that is missing here is that the
2301 bases are constant but different. There is nothing
2302 to do here because there is no overlap. */
2306 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2307 dump_insn_info ("removing from active", i_ptr
);
2309 active_local_stores_len
--;
2311 last
->next_local_store
= i_ptr
->next_local_store
;
2313 active_local_stores
= i_ptr
->next_local_store
;
2317 i_ptr
= i_ptr
->next_local_store
;
2322 insn_info_t i_ptr
= active_local_stores
;
2323 insn_info_t last
= NULL
;
2324 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2326 fprintf (dump_file
, " processing cselib load mem:");
2327 print_inline_rtx (dump_file
, mem
, 0);
2328 fprintf (dump_file
, "\n");
2333 bool remove
= false;
2334 store_info_t store_info
= i_ptr
->store_rec
;
2336 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2337 fprintf (dump_file
, " processing cselib load against insn %d\n",
2338 INSN_UID (i_ptr
->insn
));
2340 /* Skip the clobbers. */
2341 while (!store_info
->is_set
)
2342 store_info
= store_info
->next
;
2344 /* If this read is just reading back something that we just
2345 stored, rewrite the read. */
2347 && store_info
->group_id
== -1
2348 && store_info
->cse_base
== base
2350 && offset
>= store_info
->begin
2351 && offset
+ width
<= store_info
->end
2352 && all_positions_needed_p (store_info
,
2353 offset
- store_info
->begin
, width
)
2354 && replace_read (store_info
, i_ptr
, read_info
, insn_info
, loc
,
2355 bb_info
->regs_live
))
2358 if (!store_info
->alias_set
)
2359 remove
= canon_true_dependence (store_info
->mem
,
2360 GET_MODE (store_info
->mem
),
2361 store_info
->mem_addr
,
2366 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2367 dump_insn_info ("removing from active", i_ptr
);
2369 active_local_stores_len
--;
2371 last
->next_local_store
= i_ptr
->next_local_store
;
2373 active_local_stores
= i_ptr
->next_local_store
;
2377 i_ptr
= i_ptr
->next_local_store
;
2382 /* A note_uses callback in which DATA points the INSN_INFO for
2383 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
2384 true for any part of *LOC. */
2387 check_mem_read_use (rtx
*loc
, void *data
)
2389 subrtx_ptr_iterator::array_type array
;
2390 FOR_EACH_SUBRTX_PTR (iter
, array
, loc
, NONCONST
)
2394 check_mem_read_rtx (loc
, (bb_info_t
) data
);
2399 /* Get arguments passed to CALL_INSN. Return TRUE if successful.
2400 So far it only handles arguments passed in registers. */
2403 get_call_args (rtx call_insn
, tree fn
, rtx
*args
, int nargs
)
2405 CUMULATIVE_ARGS args_so_far_v
;
2406 cumulative_args_t args_so_far
;
2410 INIT_CUMULATIVE_ARGS (args_so_far_v
, TREE_TYPE (fn
), NULL_RTX
, 0, 3);
2411 args_so_far
= pack_cumulative_args (&args_so_far_v
);
2413 arg
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2415 arg
!= void_list_node
&& idx
< nargs
;
2416 arg
= TREE_CHAIN (arg
), idx
++)
2418 machine_mode mode
= TYPE_MODE (TREE_VALUE (arg
));
2420 reg
= targetm
.calls
.function_arg (args_so_far
, mode
, NULL_TREE
, true);
2421 if (!reg
|| !REG_P (reg
) || GET_MODE (reg
) != mode
2422 || GET_MODE_CLASS (mode
) != MODE_INT
)
2425 for (link
= CALL_INSN_FUNCTION_USAGE (call_insn
);
2427 link
= XEXP (link
, 1))
2428 if (GET_CODE (XEXP (link
, 0)) == USE
)
2430 args
[idx
] = XEXP (XEXP (link
, 0), 0);
2431 if (REG_P (args
[idx
])
2432 && REGNO (args
[idx
]) == REGNO (reg
)
2433 && (GET_MODE (args
[idx
]) == mode
2434 || (GET_MODE_CLASS (GET_MODE (args
[idx
])) == MODE_INT
2435 && (GET_MODE_SIZE (GET_MODE (args
[idx
]))
2437 && (GET_MODE_SIZE (GET_MODE (args
[idx
]))
2438 > GET_MODE_SIZE (mode
)))))
2444 tmp
= cselib_expand_value_rtx (args
[idx
], scratch
, 5);
2445 if (GET_MODE (args
[idx
]) != mode
)
2447 if (!tmp
|| !CONST_INT_P (tmp
))
2449 tmp
= gen_int_mode (INTVAL (tmp
), mode
);
2454 targetm
.calls
.function_arg_advance (args_so_far
, mode
, NULL_TREE
, true);
2456 if (arg
!= void_list_node
|| idx
!= nargs
)
2461 /* Return a bitmap of the fixed registers contained in IN. */
2464 copy_fixed_regs (const_bitmap in
)
2468 ret
= ALLOC_REG_SET (NULL
);
2469 bitmap_and (ret
, in
, fixed_reg_set_regset
);
2473 /* Apply record_store to all candidate stores in INSN. Mark INSN
2474 if some part of it is not a candidate store and assigns to a
2475 non-register target. */
2478 scan_insn (bb_info_t bb_info
, rtx_insn
*insn
)
2481 insn_info_t insn_info
= (insn_info_t
) pool_alloc (insn_info_pool
);
2483 memset (insn_info
, 0, sizeof (struct insn_info
));
2485 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2486 fprintf (dump_file
, "\n**scanning insn=%d\n",
2489 insn_info
->prev_insn
= bb_info
->last_insn
;
2490 insn_info
->insn
= insn
;
2491 bb_info
->last_insn
= insn_info
;
2493 if (DEBUG_INSN_P (insn
))
2495 insn_info
->cannot_delete
= true;
2499 /* Look at all of the uses in the insn. */
2500 note_uses (&PATTERN (insn
), check_mem_read_use
, bb_info
);
2505 tree memset_call
= NULL_TREE
;
2507 insn_info
->cannot_delete
= true;
2509 /* Const functions cannot do anything bad i.e. read memory,
2510 however, they can read their parameters which may have
2511 been pushed onto the stack.
2512 memset and bzero don't read memory either. */
2513 const_call
= RTL_CONST_CALL_P (insn
);
2516 rtx call
= get_call_rtx_from (insn
);
2517 if (call
&& GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
2519 rtx symbol
= XEXP (XEXP (call
, 0), 0);
2520 if (SYMBOL_REF_DECL (symbol
)
2521 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
2523 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
2525 && (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
))
2526 == BUILT_IN_MEMSET
))
2527 || SYMBOL_REF_DECL (symbol
) == block_clear_fn
)
2528 memset_call
= SYMBOL_REF_DECL (symbol
);
2532 if (const_call
|| memset_call
)
2534 insn_info_t i_ptr
= active_local_stores
;
2535 insn_info_t last
= NULL
;
2537 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2538 fprintf (dump_file
, "%s call %d\n",
2539 const_call
? "const" : "memset", INSN_UID (insn
));
2541 /* See the head comment of the frame_read field. */
2542 if (reload_completed
2543 /* Tail calls are storing their arguments using
2544 arg pointer. If it is a frame pointer on the target,
2545 even before reload we need to kill frame pointer based
2547 || (SIBLING_CALL_P (insn
)
2548 && HARD_FRAME_POINTER_IS_ARG_POINTER
))
2549 insn_info
->frame_read
= true;
2551 /* Loop over the active stores and remove those which are
2552 killed by the const function call. */
2555 bool remove_store
= false;
2557 /* The stack pointer based stores are always killed. */
2558 if (i_ptr
->stack_pointer_based
)
2559 remove_store
= true;
2561 /* If the frame is read, the frame related stores are killed. */
2562 else if (insn_info
->frame_read
)
2564 store_info_t store_info
= i_ptr
->store_rec
;
2566 /* Skip the clobbers. */
2567 while (!store_info
->is_set
)
2568 store_info
= store_info
->next
;
2570 if (store_info
->group_id
>= 0
2571 && rtx_group_vec
[store_info
->group_id
]->frame_related
)
2572 remove_store
= true;
2577 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2578 dump_insn_info ("removing from active", i_ptr
);
2580 active_local_stores_len
--;
2582 last
->next_local_store
= i_ptr
->next_local_store
;
2584 active_local_stores
= i_ptr
->next_local_store
;
2589 i_ptr
= i_ptr
->next_local_store
;
2595 if (get_call_args (insn
, memset_call
, args
, 3)
2596 && CONST_INT_P (args
[1])
2597 && CONST_INT_P (args
[2])
2598 && INTVAL (args
[2]) > 0)
2600 rtx mem
= gen_rtx_MEM (BLKmode
, args
[0]);
2601 set_mem_size (mem
, INTVAL (args
[2]));
2602 body
= gen_rtx_SET (VOIDmode
, mem
, args
[1]);
2603 mems_found
+= record_store (body
, bb_info
);
2604 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2605 fprintf (dump_file
, "handling memset as BLKmode store\n");
2606 if (mems_found
== 1)
2608 if (active_local_stores_len
++
2609 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES
))
2611 active_local_stores_len
= 1;
2612 active_local_stores
= NULL
;
2614 insn_info
->fixed_regs_live
2615 = copy_fixed_regs (bb_info
->regs_live
);
2616 insn_info
->next_local_store
= active_local_stores
;
2617 active_local_stores
= insn_info
;
2622 else if (SIBLING_CALL_P (insn
) && reload_completed
)
2623 /* Arguments for a sibling call that are pushed to memory are passed
2624 using the incoming argument pointer of the current function. After
2625 reload that might be (and likely is) frame pointer based. */
2626 add_wild_read (bb_info
);
2628 /* Every other call, including pure functions, may read any memory
2629 that is not relative to the frame. */
2630 add_non_frame_wild_read (bb_info
);
2635 /* Assuming that there are sets in these insns, we cannot delete
2637 if ((GET_CODE (PATTERN (insn
)) == CLOBBER
)
2638 || volatile_refs_p (PATTERN (insn
))
2639 || (!cfun
->can_delete_dead_exceptions
&& !insn_nothrow_p (insn
))
2640 || (RTX_FRAME_RELATED_P (insn
))
2641 || find_reg_note (insn
, REG_FRAME_RELATED_EXPR
, NULL_RTX
))
2642 insn_info
->cannot_delete
= true;
2644 body
= PATTERN (insn
);
2645 if (GET_CODE (body
) == PARALLEL
)
2648 for (i
= 0; i
< XVECLEN (body
, 0); i
++)
2649 mems_found
+= record_store (XVECEXP (body
, 0, i
), bb_info
);
2652 mems_found
+= record_store (body
, bb_info
);
2654 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2655 fprintf (dump_file
, "mems_found = %d, cannot_delete = %s\n",
2656 mems_found
, insn_info
->cannot_delete
? "true" : "false");
2658 /* If we found some sets of mems, add it into the active_local_stores so
2659 that it can be locally deleted if found dead or used for
2660 replace_read and redundant constant store elimination. Otherwise mark
2661 it as cannot delete. This simplifies the processing later. */
2662 if (mems_found
== 1)
2664 if (active_local_stores_len
++
2665 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES
))
2667 active_local_stores_len
= 1;
2668 active_local_stores
= NULL
;
2670 insn_info
->fixed_regs_live
= copy_fixed_regs (bb_info
->regs_live
);
2671 insn_info
->next_local_store
= active_local_stores
;
2672 active_local_stores
= insn_info
;
2675 insn_info
->cannot_delete
= true;
2679 /* Remove BASE from the set of active_local_stores. This is a
2680 callback from cselib that is used to get rid of the stores in
2681 active_local_stores. */
2684 remove_useless_values (cselib_val
*base
)
2686 insn_info_t insn_info
= active_local_stores
;
2687 insn_info_t last
= NULL
;
2691 store_info_t store_info
= insn_info
->store_rec
;
2694 /* If ANY of the store_infos match the cselib group that is
2695 being deleted, then the insn can not be deleted. */
2698 if ((store_info
->group_id
== -1)
2699 && (store_info
->cse_base
== base
))
2704 store_info
= store_info
->next
;
2709 active_local_stores_len
--;
2711 last
->next_local_store
= insn_info
->next_local_store
;
2713 active_local_stores
= insn_info
->next_local_store
;
2714 free_store_info (insn_info
);
2719 insn_info
= insn_info
->next_local_store
;
2724 /* Do all of step 1. */
2730 bitmap regs_live
= BITMAP_ALLOC (®_obstack
);
2733 all_blocks
= BITMAP_ALLOC (NULL
);
2734 bitmap_set_bit (all_blocks
, ENTRY_BLOCK
);
2735 bitmap_set_bit (all_blocks
, EXIT_BLOCK
);
2737 FOR_ALL_BB_FN (bb
, cfun
)
2740 bb_info_t bb_info
= (bb_info_t
) pool_alloc (bb_info_pool
);
2742 memset (bb_info
, 0, sizeof (struct dse_bb_info
));
2743 bitmap_set_bit (all_blocks
, bb
->index
);
2744 bb_info
->regs_live
= regs_live
;
2746 bitmap_copy (regs_live
, DF_LR_IN (bb
));
2747 df_simulate_initialize_forwards (bb
, regs_live
);
2749 bb_table
[bb
->index
] = bb_info
;
2750 cselib_discard_hook
= remove_useless_values
;
2752 if (bb
->index
>= NUM_FIXED_BLOCKS
)
2757 = create_alloc_pool ("cse_store_info_pool",
2758 sizeof (struct store_info
), 100);
2759 active_local_stores
= NULL
;
2760 active_local_stores_len
= 0;
2761 cselib_clear_table ();
2763 /* Scan the insns. */
2764 FOR_BB_INSNS (bb
, insn
)
2767 scan_insn (bb_info
, insn
);
2768 cselib_process_insn (insn
);
2770 df_simulate_one_insn_forwards (bb
, insn
, regs_live
);
2773 /* This is something of a hack, because the global algorithm
2774 is supposed to take care of the case where stores go dead
2775 at the end of the function. However, the global
2776 algorithm must take a more conservative view of block
2777 mode reads than the local alg does. So to get the case
2778 where you have a store to the frame followed by a non
2779 overlapping block more read, we look at the active local
2780 stores at the end of the function and delete all of the
2781 frame and spill based ones. */
2782 if (stores_off_frame_dead_at_return
2783 && (EDGE_COUNT (bb
->succs
) == 0
2784 || (single_succ_p (bb
)
2785 && single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
2786 && ! crtl
->calls_eh_return
)))
2788 insn_info_t i_ptr
= active_local_stores
;
2791 store_info_t store_info
= i_ptr
->store_rec
;
2793 /* Skip the clobbers. */
2794 while (!store_info
->is_set
)
2795 store_info
= store_info
->next
;
2796 if (store_info
->alias_set
&& !i_ptr
->cannot_delete
)
2797 delete_dead_store_insn (i_ptr
);
2799 if (store_info
->group_id
>= 0)
2802 = rtx_group_vec
[store_info
->group_id
];
2803 if (group
->frame_related
&& !i_ptr
->cannot_delete
)
2804 delete_dead_store_insn (i_ptr
);
2807 i_ptr
= i_ptr
->next_local_store
;
2811 /* Get rid of the loads that were discovered in
2812 replace_read. Cselib is finished with this block. */
2813 while (deferred_change_list
)
2815 deferred_change_t next
= deferred_change_list
->next
;
2817 /* There is no reason to validate this change. That was
2819 *deferred_change_list
->loc
= deferred_change_list
->reg
;
2820 pool_free (deferred_change_pool
, deferred_change_list
);
2821 deferred_change_list
= next
;
2824 /* Get rid of all of the cselib based store_infos in this
2825 block and mark the containing insns as not being
2827 ptr
= bb_info
->last_insn
;
2830 if (ptr
->contains_cselib_groups
)
2832 store_info_t s_info
= ptr
->store_rec
;
2833 while (s_info
&& !s_info
->is_set
)
2834 s_info
= s_info
->next
;
2836 && s_info
->redundant_reason
2837 && s_info
->redundant_reason
->insn
2838 && !ptr
->cannot_delete
)
2840 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2841 fprintf (dump_file
, "Locally deleting insn %d "
2842 "because insn %d stores the "
2843 "same value and couldn't be "
2845 INSN_UID (ptr
->insn
),
2846 INSN_UID (s_info
->redundant_reason
->insn
));
2847 delete_dead_store_insn (ptr
);
2849 free_store_info (ptr
);
2853 store_info_t s_info
;
2855 /* Free at least positions_needed bitmaps. */
2856 for (s_info
= ptr
->store_rec
; s_info
; s_info
= s_info
->next
)
2857 if (s_info
->is_large
)
2859 BITMAP_FREE (s_info
->positions_needed
.large
.bmap
);
2860 s_info
->is_large
= false;
2863 ptr
= ptr
->prev_insn
;
2866 free_alloc_pool (cse_store_info_pool
);
2868 bb_info
->regs_live
= NULL
;
2871 BITMAP_FREE (regs_live
);
2873 rtx_group_table
->empty ();
2877 /*----------------------------------------------------------------------------
2880 Assign each byte position in the stores that we are going to
2881 analyze globally to a position in the bitmaps. Returns true if
2882 there are any bit positions assigned.
2883 ----------------------------------------------------------------------------*/
2886 dse_step2_init (void)
2891 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
2893 /* For all non stack related bases, we only consider a store to
2894 be deletable if there are two or more stores for that
2895 position. This is because it takes one store to make the
2896 other store redundant. However, for the stores that are
2897 stack related, we consider them if there is only one store
2898 for the position. We do this because the stack related
2899 stores can be deleted if their is no read between them and
2900 the end of the function.
2902 To make this work in the current framework, we take the stack
2903 related bases add all of the bits from store1 into store2.
2904 This has the effect of making the eligible even if there is
2907 if (stores_off_frame_dead_at_return
&& group
->frame_related
)
2909 bitmap_ior_into (group
->store2_n
, group
->store1_n
);
2910 bitmap_ior_into (group
->store2_p
, group
->store1_p
);
2911 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2912 fprintf (dump_file
, "group %d is frame related ", i
);
2915 group
->offset_map_size_n
++;
2916 group
->offset_map_n
= XOBNEWVEC (&dse_obstack
, int,
2917 group
->offset_map_size_n
);
2918 group
->offset_map_size_p
++;
2919 group
->offset_map_p
= XOBNEWVEC (&dse_obstack
, int,
2920 group
->offset_map_size_p
);
2921 group
->process_globally
= false;
2922 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2924 fprintf (dump_file
, "group %d(%d+%d): ", i
,
2925 (int)bitmap_count_bits (group
->store2_n
),
2926 (int)bitmap_count_bits (group
->store2_p
));
2927 bitmap_print (dump_file
, group
->store2_n
, "n ", " ");
2928 bitmap_print (dump_file
, group
->store2_p
, "p ", "\n");
2934 /* Init the offset tables for the normal case. */
2937 dse_step2_nospill (void)
2941 /* Position 0 is unused because 0 is used in the maps to mean
2943 current_position
= 1;
2944 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
2949 if (group
== clear_alias_group
)
2952 memset (group
->offset_map_n
, 0, sizeof (int) * group
->offset_map_size_n
);
2953 memset (group
->offset_map_p
, 0, sizeof (int) * group
->offset_map_size_p
);
2954 bitmap_clear (group
->group_kill
);
2956 EXECUTE_IF_SET_IN_BITMAP (group
->store2_n
, 0, j
, bi
)
2958 bitmap_set_bit (group
->group_kill
, current_position
);
2959 if (bitmap_bit_p (group
->escaped_n
, j
))
2960 bitmap_set_bit (kill_on_calls
, current_position
);
2961 group
->offset_map_n
[j
] = current_position
++;
2962 group
->process_globally
= true;
2964 EXECUTE_IF_SET_IN_BITMAP (group
->store2_p
, 0, j
, bi
)
2966 bitmap_set_bit (group
->group_kill
, current_position
);
2967 if (bitmap_bit_p (group
->escaped_p
, j
))
2968 bitmap_set_bit (kill_on_calls
, current_position
);
2969 group
->offset_map_p
[j
] = current_position
++;
2970 group
->process_globally
= true;
2973 return current_position
!= 1;
2978 /*----------------------------------------------------------------------------
2981 Build the bit vectors for the transfer functions.
2982 ----------------------------------------------------------------------------*/
2985 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
2989 get_bitmap_index (group_info_t group_info
, HOST_WIDE_INT offset
)
2993 HOST_WIDE_INT offset_p
= -offset
;
2994 if (offset_p
>= group_info
->offset_map_size_n
)
2996 return group_info
->offset_map_n
[offset_p
];
3000 if (offset
>= group_info
->offset_map_size_p
)
3002 return group_info
->offset_map_p
[offset
];
3007 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3011 scan_stores_nospill (store_info_t store_info
, bitmap gen
, bitmap kill
)
3016 group_info_t group_info
3017 = rtx_group_vec
[store_info
->group_id
];
3018 if (group_info
->process_globally
)
3019 for (i
= store_info
->begin
; i
< store_info
->end
; i
++)
3021 int index
= get_bitmap_index (group_info
, i
);
3024 bitmap_set_bit (gen
, index
);
3026 bitmap_clear_bit (kill
, index
);
3029 store_info
= store_info
->next
;
3034 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3038 scan_stores_spill (store_info_t store_info
, bitmap gen
, bitmap kill
)
3042 if (store_info
->alias_set
)
3044 int index
= get_bitmap_index (clear_alias_group
,
3045 store_info
->alias_set
);
3048 bitmap_set_bit (gen
, index
);
3050 bitmap_clear_bit (kill
, index
);
3053 store_info
= store_info
->next
;
3058 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3062 scan_reads_nospill (insn_info_t insn_info
, bitmap gen
, bitmap kill
)
3064 read_info_t read_info
= insn_info
->read_rec
;
3068 /* If this insn reads the frame, kill all the frame related stores. */
3069 if (insn_info
->frame_read
)
3071 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3072 if (group
->process_globally
&& group
->frame_related
)
3075 bitmap_ior_into (kill
, group
->group_kill
);
3076 bitmap_and_compl_into (gen
, group
->group_kill
);
3079 if (insn_info
->non_frame_wild_read
)
3081 /* Kill all non-frame related stores. Kill all stores of variables that
3084 bitmap_ior_into (kill
, kill_on_calls
);
3085 bitmap_and_compl_into (gen
, kill_on_calls
);
3086 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3087 if (group
->process_globally
&& !group
->frame_related
)
3090 bitmap_ior_into (kill
, group
->group_kill
);
3091 bitmap_and_compl_into (gen
, group
->group_kill
);
3096 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3098 if (group
->process_globally
)
3100 if (i
== read_info
->group_id
)
3102 if (read_info
->begin
> read_info
->end
)
3104 /* Begin > end for block mode reads. */
3106 bitmap_ior_into (kill
, group
->group_kill
);
3107 bitmap_and_compl_into (gen
, group
->group_kill
);
3111 /* The groups are the same, just process the
3114 for (j
= read_info
->begin
; j
< read_info
->end
; j
++)
3116 int index
= get_bitmap_index (group
, j
);
3120 bitmap_set_bit (kill
, index
);
3121 bitmap_clear_bit (gen
, index
);
3128 /* The groups are different, if the alias sets
3129 conflict, clear the entire group. We only need
3130 to apply this test if the read_info is a cselib
3131 read. Anything with a constant base cannot alias
3132 something else with a different constant
3134 if ((read_info
->group_id
< 0)
3135 && canon_true_dependence (group
->base_mem
,
3136 GET_MODE (group
->base_mem
),
3137 group
->canon_base_addr
,
3138 read_info
->mem
, NULL_RTX
))
3141 bitmap_ior_into (kill
, group
->group_kill
);
3142 bitmap_and_compl_into (gen
, group
->group_kill
);
3148 read_info
= read_info
->next
;
3152 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3156 scan_reads_spill (read_info_t read_info
, bitmap gen
, bitmap kill
)
3160 if (read_info
->alias_set
)
3162 int index
= get_bitmap_index (clear_alias_group
,
3163 read_info
->alias_set
);
3167 bitmap_set_bit (kill
, index
);
3168 bitmap_clear_bit (gen
, index
);
3172 read_info
= read_info
->next
;
3177 /* Return the insn in BB_INFO before the first wild read or if there
3178 are no wild reads in the block, return the last insn. */
3181 find_insn_before_first_wild_read (bb_info_t bb_info
)
3183 insn_info_t insn_info
= bb_info
->last_insn
;
3184 insn_info_t last_wild_read
= NULL
;
3188 if (insn_info
->wild_read
)
3190 last_wild_read
= insn_info
->prev_insn
;
3191 /* Block starts with wild read. */
3192 if (!last_wild_read
)
3196 insn_info
= insn_info
->prev_insn
;
3200 return last_wild_read
;
3202 return bb_info
->last_insn
;
3206 /* Scan the insns in BB_INFO starting at PTR and going to the top of
3207 the block in order to build the gen and kill sets for the block.
3208 We start at ptr which may be the last insn in the block or may be
3209 the first insn with a wild read. In the latter case we are able to
3210 skip the rest of the block because it just does not matter:
3211 anything that happens is hidden by the wild read. */
3214 dse_step3_scan (bool for_spills
, basic_block bb
)
3216 bb_info_t bb_info
= bb_table
[bb
->index
];
3217 insn_info_t insn_info
;
3220 /* There are no wild reads in the spill case. */
3221 insn_info
= bb_info
->last_insn
;
3223 insn_info
= find_insn_before_first_wild_read (bb_info
);
3225 /* In the spill case or in the no_spill case if there is no wild
3226 read in the block, we will need a kill set. */
3227 if (insn_info
== bb_info
->last_insn
)
3230 bitmap_clear (bb_info
->kill
);
3232 bb_info
->kill
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3236 BITMAP_FREE (bb_info
->kill
);
3240 /* There may have been code deleted by the dce pass run before
3242 if (insn_info
->insn
&& INSN_P (insn_info
->insn
))
3244 /* Process the read(s) last. */
3247 scan_stores_spill (insn_info
->store_rec
, bb_info
->gen
, bb_info
->kill
);
3248 scan_reads_spill (insn_info
->read_rec
, bb_info
->gen
, bb_info
->kill
);
3252 scan_stores_nospill (insn_info
->store_rec
, bb_info
->gen
, bb_info
->kill
);
3253 scan_reads_nospill (insn_info
, bb_info
->gen
, bb_info
->kill
);
3257 insn_info
= insn_info
->prev_insn
;
3262 /* Set the gen set of the exit block, and also any block with no
3263 successors that does not have a wild read. */
3266 dse_step3_exit_block_scan (bb_info_t bb_info
)
3268 /* The gen set is all 0's for the exit block except for the
3269 frame_pointer_group. */
3271 if (stores_off_frame_dead_at_return
)
3276 FOR_EACH_VEC_ELT (rtx_group_vec
, i
, group
)
3278 if (group
->process_globally
&& group
->frame_related
)
3279 bitmap_ior_into (bb_info
->gen
, group
->group_kill
);
3285 /* Find all of the blocks that are not backwards reachable from the
3286 exit block or any block with no successors (BB). These are the
3287 infinite loops or infinite self loops. These blocks will still
3288 have their bits set in UNREACHABLE_BLOCKS. */
3291 mark_reachable_blocks (sbitmap unreachable_blocks
, basic_block bb
)
3296 if (bitmap_bit_p (unreachable_blocks
, bb
->index
))
3298 bitmap_clear_bit (unreachable_blocks
, bb
->index
);
3299 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3301 mark_reachable_blocks (unreachable_blocks
, e
->src
);
3306 /* Build the transfer functions for the function. */
3309 dse_step3 (bool for_spills
)
3312 sbitmap unreachable_blocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
3313 sbitmap_iterator sbi
;
3314 bitmap all_ones
= NULL
;
3317 bitmap_ones (unreachable_blocks
);
3319 FOR_ALL_BB_FN (bb
, cfun
)
3321 bb_info_t bb_info
= bb_table
[bb
->index
];
3323 bitmap_clear (bb_info
->gen
);
3325 bb_info
->gen
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3327 if (bb
->index
== ENTRY_BLOCK
)
3329 else if (bb
->index
== EXIT_BLOCK
)
3330 dse_step3_exit_block_scan (bb_info
);
3332 dse_step3_scan (for_spills
, bb
);
3333 if (EDGE_COUNT (bb
->succs
) == 0)
3334 mark_reachable_blocks (unreachable_blocks
, bb
);
3336 /* If this is the second time dataflow is run, delete the old
3339 BITMAP_FREE (bb_info
->in
);
3341 BITMAP_FREE (bb_info
->out
);
3344 /* For any block in an infinite loop, we must initialize the out set
3345 to all ones. This could be expensive, but almost never occurs in
3346 practice. However, it is common in regression tests. */
3347 EXECUTE_IF_SET_IN_BITMAP (unreachable_blocks
, 0, i
, sbi
)
3349 if (bitmap_bit_p (all_blocks
, i
))
3351 bb_info_t bb_info
= bb_table
[i
];
3357 all_ones
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3358 FOR_EACH_VEC_ELT (rtx_group_vec
, j
, group
)
3359 bitmap_ior_into (all_ones
, group
->group_kill
);
3363 bb_info
->out
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3364 bitmap_copy (bb_info
->out
, all_ones
);
3370 BITMAP_FREE (all_ones
);
3371 sbitmap_free (unreachable_blocks
);
3376 /*----------------------------------------------------------------------------
3379 Solve the bitvector equations.
3380 ----------------------------------------------------------------------------*/
3383 /* Confluence function for blocks with no successors. Create an out
3384 set from the gen set of the exit block. This block logically has
3385 the exit block as a successor. */
3390 dse_confluence_0 (basic_block bb
)
3392 bb_info_t bb_info
= bb_table
[bb
->index
];
3394 if (bb
->index
== EXIT_BLOCK
)
3399 bb_info
->out
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3400 bitmap_copy (bb_info
->out
, bb_table
[EXIT_BLOCK
]->gen
);
3404 /* Propagate the information from the in set of the dest of E to the
3405 out set of the src of E. If the various in or out sets are not
3406 there, that means they are all ones. */
3409 dse_confluence_n (edge e
)
3411 bb_info_t src_info
= bb_table
[e
->src
->index
];
3412 bb_info_t dest_info
= bb_table
[e
->dest
->index
];
3417 bitmap_and_into (src_info
->out
, dest_info
->in
);
3420 src_info
->out
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3421 bitmap_copy (src_info
->out
, dest_info
->in
);
3428 /* Propagate the info from the out to the in set of BB_INDEX's basic
3429 block. There are three cases:
3431 1) The block has no kill set. In this case the kill set is all
3432 ones. It does not matter what the out set of the block is, none of
3433 the info can reach the top. The only thing that reaches the top is
3434 the gen set and we just copy the set.
3436 2) There is a kill set but no out set and bb has successors. In
3437 this case we just return. Eventually an out set will be created and
3438 it is better to wait than to create a set of ones.
3440 3) There is both a kill and out set. We apply the obvious transfer
3445 dse_transfer_function (int bb_index
)
3447 bb_info_t bb_info
= bb_table
[bb_index
];
3455 return bitmap_ior_and_compl (bb_info
->in
, bb_info
->gen
,
3456 bb_info
->out
, bb_info
->kill
);
3459 bb_info
->in
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3460 bitmap_ior_and_compl (bb_info
->in
, bb_info
->gen
,
3461 bb_info
->out
, bb_info
->kill
);
3471 /* Case 1 above. If there is already an in set, nothing
3477 bb_info
->in
= BITMAP_ALLOC (&dse_bitmap_obstack
);
3478 bitmap_copy (bb_info
->in
, bb_info
->gen
);
3484 /* Solve the dataflow equations. */
3489 df_simple_dataflow (DF_BACKWARD
, NULL
, dse_confluence_0
,
3490 dse_confluence_n
, dse_transfer_function
,
3491 all_blocks
, df_get_postorder (DF_BACKWARD
),
3492 df_get_n_blocks (DF_BACKWARD
));
3493 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3497 fprintf (dump_file
, "\n\n*** Global dataflow info after analysis.\n");
3498 FOR_ALL_BB_FN (bb
, cfun
)
3500 bb_info_t bb_info
= bb_table
[bb
->index
];
3502 df_print_bb_index (bb
, dump_file
);
3504 bitmap_print (dump_file
, bb_info
->in
, " in: ", "\n");
3506 fprintf (dump_file
, " in: *MISSING*\n");
3508 bitmap_print (dump_file
, bb_info
->gen
, " gen: ", "\n");
3510 fprintf (dump_file
, " gen: *MISSING*\n");
3512 bitmap_print (dump_file
, bb_info
->kill
, " kill: ", "\n");
3514 fprintf (dump_file
, " kill: *MISSING*\n");
3516 bitmap_print (dump_file
, bb_info
->out
, " out: ", "\n");
3518 fprintf (dump_file
, " out: *MISSING*\n\n");
3525 /*----------------------------------------------------------------------------
3528 Delete the stores that can only be deleted using the global information.
3529 ----------------------------------------------------------------------------*/
3533 dse_step5_nospill (void)
3536 FOR_EACH_BB_FN (bb
, cfun
)
3538 bb_info_t bb_info
= bb_table
[bb
->index
];
3539 insn_info_t insn_info
= bb_info
->last_insn
;
3540 bitmap v
= bb_info
->out
;
3544 bool deleted
= false;
3545 if (dump_file
&& insn_info
->insn
)
3547 fprintf (dump_file
, "starting to process insn %d\n",
3548 INSN_UID (insn_info
->insn
));
3549 bitmap_print (dump_file
, v
, " v: ", "\n");
3552 /* There may have been code deleted by the dce pass run before
3555 && INSN_P (insn_info
->insn
)
3556 && (!insn_info
->cannot_delete
)
3557 && (!bitmap_empty_p (v
)))
3559 store_info_t store_info
= insn_info
->store_rec
;
3561 /* Try to delete the current insn. */
3564 /* Skip the clobbers. */
3565 while (!store_info
->is_set
)
3566 store_info
= store_info
->next
;
3568 if (store_info
->alias_set
)
3573 group_info_t group_info
3574 = rtx_group_vec
[store_info
->group_id
];
3576 for (i
= store_info
->begin
; i
< store_info
->end
; i
++)
3578 int index
= get_bitmap_index (group_info
, i
);
3580 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3581 fprintf (dump_file
, "i = %d, index = %d\n", (int)i
, index
);
3582 if (index
== 0 || !bitmap_bit_p (v
, index
))
3584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3585 fprintf (dump_file
, "failing at i = %d\n", (int)i
);
3594 && check_for_inc_dec_1 (insn_info
))
3596 delete_insn (insn_info
->insn
);
3597 insn_info
->insn
= NULL
;
3602 /* We do want to process the local info if the insn was
3603 deleted. For instance, if the insn did a wild read, we
3604 no longer need to trash the info. */
3606 && INSN_P (insn_info
->insn
)
3609 scan_stores_nospill (insn_info
->store_rec
, v
, NULL
);
3610 if (insn_info
->wild_read
)
3612 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3613 fprintf (dump_file
, "wild read\n");
3616 else if (insn_info
->read_rec
3617 || insn_info
->non_frame_wild_read
)
3619 if (dump_file
&& !insn_info
->non_frame_wild_read
)
3620 fprintf (dump_file
, "regular read\n");
3621 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3622 fprintf (dump_file
, "non-frame wild read\n");
3623 scan_reads_nospill (insn_info
, v
, NULL
);
3627 insn_info
= insn_info
->prev_insn
;
3634 /*----------------------------------------------------------------------------
3637 Delete stores made redundant by earlier stores (which store the same
3638 value) that couldn't be eliminated.
3639 ----------------------------------------------------------------------------*/
3646 FOR_ALL_BB_FN (bb
, cfun
)
3648 bb_info_t bb_info
= bb_table
[bb
->index
];
3649 insn_info_t insn_info
= bb_info
->last_insn
;
3653 /* There may have been code deleted by the dce pass run before
3656 && INSN_P (insn_info
->insn
)
3657 && !insn_info
->cannot_delete
)
3659 store_info_t s_info
= insn_info
->store_rec
;
3661 while (s_info
&& !s_info
->is_set
)
3662 s_info
= s_info
->next
;
3664 && s_info
->redundant_reason
3665 && s_info
->redundant_reason
->insn
3666 && INSN_P (s_info
->redundant_reason
->insn
))
3668 rtx_insn
*rinsn
= s_info
->redundant_reason
->insn
;
3669 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3670 fprintf (dump_file
, "Locally deleting insn %d "
3671 "because insn %d stores the "
3672 "same value and couldn't be "
3674 INSN_UID (insn_info
->insn
),
3676 delete_dead_store_insn (insn_info
);
3679 insn_info
= insn_info
->prev_insn
;
3684 /*----------------------------------------------------------------------------
3687 Destroy everything left standing.
3688 ----------------------------------------------------------------------------*/
3693 bitmap_obstack_release (&dse_bitmap_obstack
);
3694 obstack_free (&dse_obstack
, NULL
);
3696 end_alias_analysis ();
3698 delete rtx_group_table
;
3699 rtx_group_table
= NULL
;
3700 rtx_group_vec
.release ();
3701 BITMAP_FREE (all_blocks
);
3702 BITMAP_FREE (scratch
);
3704 free_alloc_pool (rtx_store_info_pool
);
3705 free_alloc_pool (read_info_pool
);
3706 free_alloc_pool (insn_info_pool
);
3707 free_alloc_pool (bb_info_pool
);
3708 free_alloc_pool (rtx_group_info_pool
);
3709 free_alloc_pool (deferred_change_pool
);
3713 /* -------------------------------------------------------------------------
3715 ------------------------------------------------------------------------- */
3717 /* Callback for running pass_rtl_dse. */
3720 rest_of_handle_dse (void)
3722 df_set_flags (DF_DEFER_INSN_RESCAN
);
3724 /* Need the notes since we must track live hardregs in the forwards
3726 df_note_add_problem ();
3732 if (dse_step2_nospill ())
3734 df_set_flags (DF_LR_RUN_DCE
);
3736 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3737 fprintf (dump_file
, "doing global processing\n");
3740 dse_step5_nospill ();
3747 fprintf (dump_file
, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3748 locally_deleted
, globally_deleted
, spill_deleted
);
3754 const pass_data pass_data_rtl_dse1
=
3756 RTL_PASS
, /* type */
3758 OPTGROUP_NONE
, /* optinfo_flags */
3759 TV_DSE1
, /* tv_id */
3760 0, /* properties_required */
3761 0, /* properties_provided */
3762 0, /* properties_destroyed */
3763 0, /* todo_flags_start */
3764 TODO_df_finish
, /* todo_flags_finish */
3767 class pass_rtl_dse1
: public rtl_opt_pass
3770 pass_rtl_dse1 (gcc::context
*ctxt
)
3771 : rtl_opt_pass (pass_data_rtl_dse1
, ctxt
)
3774 /* opt_pass methods: */
3775 virtual bool gate (function
*)
3777 return optimize
> 0 && flag_dse
&& dbg_cnt (dse1
);
3780 virtual unsigned int execute (function
*) { return rest_of_handle_dse (); }
3782 }; // class pass_rtl_dse1
3787 make_pass_rtl_dse1 (gcc::context
*ctxt
)
3789 return new pass_rtl_dse1 (ctxt
);
3794 const pass_data pass_data_rtl_dse2
=
3796 RTL_PASS
, /* type */
3798 OPTGROUP_NONE
, /* optinfo_flags */
3799 TV_DSE2
, /* tv_id */
3800 0, /* properties_required */
3801 0, /* properties_provided */
3802 0, /* properties_destroyed */
3803 0, /* todo_flags_start */
3804 TODO_df_finish
, /* todo_flags_finish */
3807 class pass_rtl_dse2
: public rtl_opt_pass
3810 pass_rtl_dse2 (gcc::context
*ctxt
)
3811 : rtl_opt_pass (pass_data_rtl_dse2
, ctxt
)
3814 /* opt_pass methods: */
3815 virtual bool gate (function
*)
3817 return optimize
> 0 && flag_dse
&& dbg_cnt (dse2
);
3820 virtual unsigned int execute (function
*) { return rest_of_handle_dse (); }
3822 }; // class pass_rtl_dse2
3827 make_pass_rtl_dse2 (gcc::context
*ctxt
)
3829 return new pass_rtl_dse2 (ctxt
);