1 /* RTL dead store elimination.
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
5 Contributed by Richard Sandiford <rsandifor@codesourcery.com>
6 and Kenneth Zadeck <zadeck@naturalbridge.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
28 #include "coretypes.h"
35 #include "hard-reg-set.h"
41 #include "tree-pass.h"
42 #include "alloc-pool.h"
44 #include "insn-config.h"
51 #include "tree-flow.h"
53 /* This file contains three techniques for performing Dead Store
56 * The first technique performs dse locally on any base address. It
57 is based on the cselib which is a local value numbering technique.
58 This technique is local to a basic block but deals with a fairly
61 * The second technique performs dse globally but is restricted to
62 base addresses that are either constant or are relative to the
65 * The third technique, (which is only done after register allocation)
66 processes the spill spill slots. This differs from the second
67 technique because it takes advantage of the fact that spilling is
68 completely free from the effects of aliasing.
70 Logically, dse is a backwards dataflow problem. A store can be
71 deleted if it if cannot be reached in the backward direction by any
72 use of the value being stored. However, the local technique uses a
73 forwards scan of the basic block because cselib requires that the
74 block be processed in that order.
76 The pass is logically broken into 7 steps:
80 1) The local algorithm, as well as scanning the insns for the two
83 2) Analysis to see if the global algs are necessary. In the case
84 of stores base on a constant address, there must be at least two
85 stores to that address, to make it possible to delete some of the
86 stores. In the case of stores off of the frame or spill related
87 stores, only one store to an address is necessary because those
88 stores die at the end of the function.
90 3) Set up the global dataflow equations based on processing the
91 info parsed in the first step.
93 4) Solve the dataflow equations.
95 5) Delete the insns that the global analysis has indicated are
98 6) Delete insns that store the same value as preceeding store
99 where the earlier store couldn't be eliminated.
103 This step uses cselib and canon_rtx to build the largest expression
104 possible for each address. This pass is a forwards pass through
105 each basic block. From the point of view of the global technique,
106 the first pass could examine a block in either direction. The
107 forwards ordering is to accommodate cselib.
109 We a simplifying assumption: addresses fall into four broad
112 1) base has rtx_varies_p == false, offset is constant.
113 2) base has rtx_varies_p == false, offset variable.
114 3) base has rtx_varies_p == true, offset constant.
115 4) base has rtx_varies_p == true, offset variable.
117 The local passes are able to process all 4 kinds of addresses. The
118 global pass only handles (1).
120 The global problem is formulated as follows:
122 A store, S1, to address A, where A is not relative to the stack
123 frame, can be eliminated if all paths from S1 to the end of the
124 of the function contain another store to A before a read to A.
126 If the address A is relative to the stack frame, a store S2 to A
127 can be eliminated if there are no paths from S1 that reach the
128 end of the function that read A before another store to A. In
129 this case S2 can be deleted if there are paths to from S2 to the
130 end of the function that have no reads or writes to A. This
131 second case allows stores to the stack frame to be deleted that
132 would otherwise die when the function returns. This cannot be
133 done if stores_off_frame_dead_at_return is not true. See the doc
134 for that variable for when this variable is false.
136 The global problem is formulated as a backwards set union
137 dataflow problem where the stores are the gens and reads are the
138 kills. Set union problems are rare and require some special
139 handling given our representation of bitmaps. A straightforward
140 implementation of requires a lot of bitmaps filled with 1s.
141 These are expensive and cumbersome in our bitmap formulation so
142 care has been taken to avoid large vectors filled with 1s. See
143 the comments in bb_info and in the dataflow confluence functions
146 There are two places for further enhancements to this algorithm:
148 1) The original dse which was embedded in a pass called flow also
149 did local address forwarding. For example in
154 flow would replace the right hand side of the second insn with a
155 reference to r100. Most of the information is available to add this
156 to this pass. It has not done it because it is a lot of work in
157 the case that either r100 is assigned to between the first and
158 second insn and/or the second insn is a load of part of the value
159 stored by the first insn.
161 insn 5 in gcc.c-torture/compile/990203-1.c simple case.
162 insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
163 insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
164 insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
166 2) The cleaning up of spill code is quite profitable. It currently
167 depends on reading tea leaves and chicken entrails left by reload.
168 This pass depends on reload creating a singleton alias set for each
169 spill slot and telling the next dse pass which of these alias sets
170 are the singletons. Rather than analyze the addresses of the
171 spills, dse's spill processing just does analysis of the loads and
172 stores that use those alias sets. There are three cases where this
175 a) Reload sometimes creates the slot for one mode of access, and
176 then inserts loads and/or stores for a smaller mode. In this
177 case, the current code just punts on the slot. The proper thing
178 to do is to back out and use one bit vector position for each
179 byte of the entity associated with the slot. This depends on
180 KNOWING that reload always generates the accesses for each of the
181 bytes in some canonical (read that easy to understand several
182 passes after reload happens) way.
184 b) Reload sometimes decides that spill slot it allocated was not
185 large enough for the mode and goes back and allocates more slots
186 with the same mode and alias set. The backout in this case is a
187 little more graceful than (a). In this case the slot is unmarked
188 as being a spill slot and if final address comes out to be based
189 off the frame pointer, the global algorithm handles this slot.
191 c) For any pass that may prespill, there is currently no
192 mechanism to tell the dse pass that the slot being used has the
193 special properties that reload uses. It may be that all that is
194 required is to have those passes make the same calls that reload
195 does, assuming that the alias sets can be manipulated in the same
198 /* There are limits to the size of constant offsets we model for the
199 global problem. There are certainly test cases, that exceed this
200 limit, however, it is unlikely that there are important programs
201 that really have constant offsets this size. */
202 #define MAX_OFFSET (64 * 1024)
205 static bitmap scratch
= NULL
;
208 /* This structure holds information about a candidate store. */
212 /* False means this is a clobber. */
215 /* False if a single HOST_WIDE_INT bitmap is used for positions_needed. */
218 /* The id of the mem group of the base address. If rtx_varies_p is
219 true, this is -1. Otherwise, it is the index into the group
223 /* This is the cselib value. */
224 cselib_val
*cse_base
;
226 /* This canonized mem. */
229 /* Canonized MEM address for use by canon_true_dependence. */
232 /* If this is non-zero, it is the alias set of a spill location. */
233 alias_set_type alias_set
;
235 /* The offset of the first and byte before the last byte associated
236 with the operation. */
237 HOST_WIDE_INT begin
, end
;
241 /* A bitmask as wide as the number of bytes in the word that
242 contains a 1 if the byte may be needed. The store is unused if
243 all of the bits are 0. This is used if IS_LARGE is false. */
244 unsigned HOST_WIDE_INT small_bitmask
;
248 /* A bitmap with one bit per byte. Cleared bit means the position
249 is needed. Used if IS_LARGE is false. */
252 /* Number of set bits (i.e. unneeded bytes) in BITMAP. If it is
253 equal to END - BEGIN, the whole store is unused. */
258 /* The next store info for this insn. */
259 struct store_info
*next
;
261 /* The right hand side of the store. This is used if there is a
262 subsequent reload of the mems address somewhere later in the
266 /* If rhs is or holds a constant, this contains that constant,
270 /* Set if this store stores the same constant value as REDUNDANT_REASON
271 insn stored. These aren't eliminated early, because doing that
272 might prevent the earlier larger store to be eliminated. */
273 struct insn_info
*redundant_reason
;
276 /* Return a bitmask with the first N low bits set. */
278 static unsigned HOST_WIDE_INT
279 lowpart_bitmask (int n
)
281 unsigned HOST_WIDE_INT mask
= ~(unsigned HOST_WIDE_INT
) 0;
282 return mask
>> (HOST_BITS_PER_WIDE_INT
- n
);
285 typedef struct store_info
*store_info_t
;
286 static alloc_pool cse_store_info_pool
;
287 static alloc_pool rtx_store_info_pool
;
289 /* This structure holds information about a load. These are only
290 built for rtx bases. */
293 /* The id of the mem group of the base address. */
296 /* If this is non-zero, it is the alias set of a spill location. */
297 alias_set_type alias_set
;
299 /* The offset of the first and byte after the last byte associated
300 with the operation. If begin == end == 0, the read did not have
301 a constant offset. */
304 /* The mem being read. */
307 /* The next read_info for this insn. */
308 struct read_info
*next
;
310 typedef struct read_info
*read_info_t
;
311 static alloc_pool read_info_pool
;
314 /* One of these records is created for each insn. */
318 /* Set true if the insn contains a store but the insn itself cannot
319 be deleted. This is set if the insn is a parallel and there is
320 more than one non dead output or if the insn is in some way
324 /* This field is only used by the global algorithm. It is set true
325 if the insn contains any read of mem except for a (1). This is
326 also set if the insn is a call or has a clobber mem. If the insn
327 contains a wild read, the use_rec will be null. */
330 /* This is true only for CALL instructions which could potentially read
331 any non-frame memory location. This field is used by the global
333 bool non_frame_wild_read
;
335 /* This field is only used for the processing of const functions.
336 These functions cannot read memory, but they can read the stack
337 because that is where they may get their parms. We need to be
338 this conservative because, like the store motion pass, we don't
339 consider CALL_INSN_FUNCTION_USAGE when processing call insns.
340 Moreover, we need to distinguish two cases:
341 1. Before reload (register elimination), the stores related to
342 outgoing arguments are stack pointer based and thus deemed
343 of non-constant base in this pass. This requires special
344 handling but also means that the frame pointer based stores
345 need not be killed upon encountering a const function call.
346 2. After reload, the stores related to outgoing arguments can be
347 either stack pointer or hard frame pointer based. This means
348 that we have no other choice than also killing all the frame
349 pointer based stores upon encountering a const function call.
350 This field is set after reload for const function calls. Having
351 this set is less severe than a wild read, it just means that all
352 the frame related stores are killed rather than all the stores. */
355 /* This field is only used for the processing of const functions.
356 It is set if the insn may contain a stack pointer based store. */
357 bool stack_pointer_based
;
359 /* This is true if any of the sets within the store contains a
360 cselib base. Such stores can only be deleted by the local
362 bool contains_cselib_groups
;
367 /* The list of mem sets or mem clobbers that are contained in this
368 insn. If the insn is deletable, it contains only one mem set.
369 But it could also contain clobbers. Insns that contain more than
370 one mem set are not deletable, but each of those mems are here in
371 order to provide info to delete other insns. */
372 store_info_t store_rec
;
374 /* The linked list of mem uses in this insn. Only the reads from
375 rtx bases are listed here. The reads to cselib bases are
376 completely processed during the first scan and so are never
378 read_info_t read_rec
;
380 /* The live fixed registers. We assume only fixed registers can
381 cause trouble by being clobbered from an expanded pattern;
382 storing only the live fixed registers (rather than all registers)
383 means less memory needs to be allocated / copied for the individual
385 regset fixed_regs_live
;
387 /* The prev insn in the basic block. */
388 struct insn_info
* prev_insn
;
390 /* The linked list of insns that are in consideration for removal in
391 the forwards pass thru the basic block. This pointer may be
392 trash as it is not cleared when a wild read occurs. The only
393 time it is guaranteed to be correct is when the traversal starts
394 at active_local_stores. */
395 struct insn_info
* next_local_store
;
398 typedef struct insn_info
*insn_info_t
;
399 static alloc_pool insn_info_pool
;
401 /* The linked list of stores that are under consideration in this
403 static insn_info_t active_local_stores
;
404 static int active_local_stores_len
;
409 /* Pointer to the insn info for the last insn in the block. These
410 are linked so this is how all of the insns are reached. During
411 scanning this is the current insn being scanned. */
412 insn_info_t last_insn
;
414 /* The info for the global dataflow problem. */
417 /* This is set if the transfer function should and in the wild_read
418 bitmap before applying the kill and gen sets. That vector knocks
419 out most of the bits in the bitmap and thus speeds up the
421 bool apply_wild_read
;
423 /* The following 4 bitvectors hold information about which positions
424 of which stores are live or dead. They are indexed by
427 /* The set of store positions that exist in this block before a wild read. */
430 /* The set of load positions that exist in this block above the
431 same position of a store. */
434 /* The set of stores that reach the top of the block without being
437 Do not represent the in if it is all ones. Note that this is
438 what the bitvector should logically be initialized to for a set
439 intersection problem. However, like the kill set, this is too
440 expensive. So initially, the in set will only be created for the
441 exit block and any block that contains a wild read. */
444 /* The set of stores that reach the bottom of the block from it's
447 Do not represent the in if it is all ones. Note that this is
448 what the bitvector should logically be initialized to for a set
449 intersection problem. However, like the kill and in set, this is
450 too expensive. So what is done is that the confluence operator
451 just initializes the vector from one of the out sets of the
452 successors of the block. */
455 /* The following bitvector is indexed by the reg number. It
456 contains the set of regs that are live at the current instruction
457 being processed. While it contains info for all of the
458 registers, only the hard registers are actually examined. It is used
459 to assure that shift and/or add sequences that are inserted do not
460 accidently clobber live hard regs. */
464 typedef struct bb_info
*bb_info_t
;
465 static alloc_pool bb_info_pool
;
467 /* Table to hold all bb_infos. */
468 static bb_info_t
*bb_table
;
470 /* There is a group_info for each rtx base that is used to reference
471 memory. There are also not many of the rtx bases because they are
472 very limited in scope. */
476 /* The actual base of the address. */
479 /* The sequential id of the base. This allows us to have a
480 canonical ordering of these that is not based on addresses. */
483 /* True if there are any positions that are to be processed
485 bool process_globally
;
487 /* True if the base of this group is either the frame_pointer or
488 hard_frame_pointer. */
491 /* A mem wrapped around the base pointer for the group in order to do
492 read dependency. It must be given BLKmode in order to encompass all
493 the possible offsets from the base. */
496 /* Canonized version of base_mem's address. */
499 /* These two sets of two bitmaps are used to keep track of how many
500 stores are actually referencing that position from this base. We
501 only do this for rtx bases as this will be used to assign
502 positions in the bitmaps for the global problem. Bit N is set in
503 store1 on the first store for offset N. Bit N is set in store2
504 for the second store to offset N. This is all we need since we
505 only care about offsets that have two or more stores for them.
507 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
508 for 0 and greater offsets.
510 There is one special case here, for stores into the stack frame,
511 we will or store1 into store2 before deciding which stores look
512 at globally. This is because stores to the stack frame that have
513 no other reads before the end of the function can also be
515 bitmap store1_n
, store1_p
, store2_n
, store2_p
;
517 /* These bitmaps keep track of offsets in this group escape this function.
518 An offset escapes if it corresponds to a named variable whose
519 addressable flag is set. */
520 bitmap escaped_n
, escaped_p
;
522 /* The positions in this bitmap have the same assignments as the in,
523 out, gen and kill bitmaps. This bitmap is all zeros except for
524 the positions that are occupied by stores for this group. */
527 /* The offset_map is used to map the offsets from this base into
528 positions in the global bitmaps. It is only created after all of
529 the all of stores have been scanned and we know which ones we
531 int *offset_map_n
, *offset_map_p
;
532 int offset_map_size_n
, offset_map_size_p
;
534 typedef struct group_info
*group_info_t
;
535 typedef const struct group_info
*const_group_info_t
;
536 static alloc_pool rtx_group_info_pool
;
538 /* Tables of group_info structures, hashed by base value. */
539 static htab_t rtx_group_table
;
541 /* Index into the rtx_group_vec. */
542 static int rtx_group_next_id
;
544 DEF_VEC_P(group_info_t
);
545 DEF_VEC_ALLOC_P(group_info_t
,heap
);
547 static VEC(group_info_t
,heap
) *rtx_group_vec
;
550 /* This structure holds the set of changes that are being deferred
551 when removing read operation. See replace_read. */
552 struct deferred_change
555 /* The mem that is being replaced. */
558 /* The reg it is being replaced with. */
561 struct deferred_change
*next
;
564 typedef struct deferred_change
*deferred_change_t
;
565 static alloc_pool deferred_change_pool
;
567 static deferred_change_t deferred_change_list
= NULL
;
569 /* This are used to hold the alias sets of spill variables. Since
570 these are never aliased and there may be a lot of them, it makes
571 sense to treat them specially. This bitvector is only allocated in
572 calls from dse_record_singleton_alias_set which currently is only
573 made during reload1. So when dse is called before reload this
574 mechanism does nothing. */
576 static bitmap clear_alias_sets
= NULL
;
578 /* The set of clear_alias_sets that have been disqualified because
579 there are loads or stores using a different mode than the alias set
580 was registered with. */
581 static bitmap disqualified_clear_alias_sets
= NULL
;
583 /* The group that holds all of the clear_alias_sets. */
584 static group_info_t clear_alias_group
;
586 /* The modes of the clear_alias_sets. */
587 static htab_t clear_alias_mode_table
;
589 /* Hash table element to look up the mode for an alias set. */
590 struct clear_alias_mode_holder
592 alias_set_type alias_set
;
593 enum machine_mode mode
;
596 static alloc_pool clear_alias_mode_pool
;
598 /* This is true except if cfun->stdarg -- i.e. we cannot do
599 this for vararg functions because they play games with the frame. */
600 static bool stores_off_frame_dead_at_return
;
602 /* Counter for stats. */
603 static int globally_deleted
;
604 static int locally_deleted
;
605 static int spill_deleted
;
607 static bitmap all_blocks
;
609 /* Locations that are killed by calls in the global phase. */
610 static bitmap kill_on_calls
;
612 /* The number of bits used in the global bitmaps. */
613 static unsigned int current_position
;
616 static bool gate_dse1 (void);
617 static bool gate_dse2 (void);
620 /*----------------------------------------------------------------------------
624 ----------------------------------------------------------------------------*/
627 /* Find the entry associated with ALIAS_SET. */
629 static struct clear_alias_mode_holder
*
630 clear_alias_set_lookup (alias_set_type alias_set
)
632 struct clear_alias_mode_holder tmp_holder
;
635 tmp_holder
.alias_set
= alias_set
;
636 slot
= htab_find_slot (clear_alias_mode_table
, &tmp_holder
, NO_INSERT
);
639 return (struct clear_alias_mode_holder
*) *slot
;
643 /* Hashtable callbacks for maintaining the "bases" field of
644 store_group_info, given that the addresses are function invariants. */
647 invariant_group_base_eq (const void *p1
, const void *p2
)
649 const_group_info_t gi1
= (const_group_info_t
) p1
;
650 const_group_info_t gi2
= (const_group_info_t
) p2
;
651 return rtx_equal_p (gi1
->rtx_base
, gi2
->rtx_base
);
656 invariant_group_base_hash (const void *p
)
658 const_group_info_t gi
= (const_group_info_t
) p
;
660 return hash_rtx (gi
->rtx_base
, Pmode
, &do_not_record
, NULL
, false);
664 /* Get the GROUP for BASE. Add a new group if it is not there. */
667 get_group_info (rtx base
)
669 struct group_info tmp_gi
;
675 /* Find the store_base_info structure for BASE, creating a new one
677 tmp_gi
.rtx_base
= base
;
678 slot
= htab_find_slot (rtx_group_table
, &tmp_gi
, INSERT
);
679 gi
= (group_info_t
) *slot
;
683 if (!clear_alias_group
)
685 clear_alias_group
= gi
=
686 (group_info_t
) pool_alloc (rtx_group_info_pool
);
687 memset (gi
, 0, sizeof (struct group_info
));
688 gi
->id
= rtx_group_next_id
++;
689 gi
->store1_n
= BITMAP_ALLOC (NULL
);
690 gi
->store1_p
= BITMAP_ALLOC (NULL
);
691 gi
->store2_n
= BITMAP_ALLOC (NULL
);
692 gi
->store2_p
= BITMAP_ALLOC (NULL
);
693 gi
->escaped_p
= BITMAP_ALLOC (NULL
);
694 gi
->escaped_n
= BITMAP_ALLOC (NULL
);
695 gi
->group_kill
= BITMAP_ALLOC (NULL
);
696 gi
->process_globally
= false;
697 gi
->offset_map_size_n
= 0;
698 gi
->offset_map_size_p
= 0;
699 gi
->offset_map_n
= NULL
;
700 gi
->offset_map_p
= NULL
;
701 VEC_safe_push (group_info_t
, heap
, rtx_group_vec
, gi
);
703 return clear_alias_group
;
708 *slot
= gi
= (group_info_t
) pool_alloc (rtx_group_info_pool
);
710 gi
->id
= rtx_group_next_id
++;
711 gi
->base_mem
= gen_rtx_MEM (BLKmode
, base
);
712 gi
->canon_base_addr
= canon_rtx (base
);
713 gi
->store1_n
= BITMAP_ALLOC (NULL
);
714 gi
->store1_p
= BITMAP_ALLOC (NULL
);
715 gi
->store2_n
= BITMAP_ALLOC (NULL
);
716 gi
->store2_p
= BITMAP_ALLOC (NULL
);
717 gi
->escaped_p
= BITMAP_ALLOC (NULL
);
718 gi
->escaped_n
= BITMAP_ALLOC (NULL
);
719 gi
->group_kill
= BITMAP_ALLOC (NULL
);
720 gi
->process_globally
= false;
722 (base
== frame_pointer_rtx
) || (base
== hard_frame_pointer_rtx
);
723 gi
->offset_map_size_n
= 0;
724 gi
->offset_map_size_p
= 0;
725 gi
->offset_map_n
= NULL
;
726 gi
->offset_map_p
= NULL
;
727 VEC_safe_push (group_info_t
, heap
, rtx_group_vec
, gi
);
734 /* Initialization of data structures. */
740 globally_deleted
= 0;
743 scratch
= BITMAP_ALLOC (NULL
);
744 kill_on_calls
= BITMAP_ALLOC (NULL
);
747 = create_alloc_pool ("rtx_store_info_pool",
748 sizeof (struct store_info
), 100);
750 = create_alloc_pool ("read_info_pool",
751 sizeof (struct read_info
), 100);
753 = create_alloc_pool ("insn_info_pool",
754 sizeof (struct insn_info
), 100);
756 = create_alloc_pool ("bb_info_pool",
757 sizeof (struct bb_info
), 100);
759 = create_alloc_pool ("rtx_group_info_pool",
760 sizeof (struct group_info
), 100);
762 = create_alloc_pool ("deferred_change_pool",
763 sizeof (struct deferred_change
), 10);
765 rtx_group_table
= htab_create (11, invariant_group_base_hash
,
766 invariant_group_base_eq
, NULL
);
768 bb_table
= XCNEWVEC (bb_info_t
, last_basic_block
);
769 rtx_group_next_id
= 0;
771 stores_off_frame_dead_at_return
= !cfun
->stdarg
;
773 init_alias_analysis ();
775 if (clear_alias_sets
)
776 clear_alias_group
= get_group_info (NULL
);
778 clear_alias_group
= NULL
;
783 /*----------------------------------------------------------------------------
786 Scan all of the insns. Any random ordering of the blocks is fine.
787 Each block is scanned in forward order to accommodate cselib which
788 is used to remove stores with non-constant bases.
789 ----------------------------------------------------------------------------*/
791 /* Delete all of the store_info recs from INSN_INFO. */
794 free_store_info (insn_info_t insn_info
)
796 store_info_t store_info
= insn_info
->store_rec
;
799 store_info_t next
= store_info
->next
;
800 if (store_info
->is_large
)
801 BITMAP_FREE (store_info
->positions_needed
.large
.bmap
);
802 if (store_info
->cse_base
)
803 pool_free (cse_store_info_pool
, store_info
);
805 pool_free (rtx_store_info_pool
, store_info
);
809 insn_info
->cannot_delete
= true;
810 insn_info
->contains_cselib_groups
= false;
811 insn_info
->store_rec
= NULL
;
817 regset fixed_regs_live
;
819 } note_add_store_info
;
821 /* Callback for emit_inc_dec_insn_before via note_stores.
822 Check if a register is clobbered which is live afterwards. */
825 note_add_store (rtx loc
, const_rtx expr ATTRIBUTE_UNUSED
, void *data
)
828 note_add_store_info
*info
= (note_add_store_info
*) data
;
834 /* If this register is referenced by the current or an earlier insn,
835 that's OK. E.g. this applies to the register that is being incremented
836 with this addition. */
837 for (insn
= info
->first
;
838 insn
!= NEXT_INSN (info
->current
);
839 insn
= NEXT_INSN (insn
))
840 if (reg_referenced_p (loc
, PATTERN (insn
)))
843 /* If we come here, we have a clobber of a register that's only OK
844 if that register is not live. If we don't have liveness information
845 available, fail now. */
846 if (!info
->fixed_regs_live
)
848 info
->failure
= true;
851 /* Now check if this is a live fixed register. */
853 n
= hard_regno_nregs
[r
][GET_MODE (loc
)];
855 if (REGNO_REG_SET_P (info
->fixed_regs_live
, r
+n
))
856 info
->failure
= true;
859 /* Callback for for_each_inc_dec that emits an INSN that sets DEST to
860 SRC + SRCOFF before insn ARG. */
863 emit_inc_dec_insn_before (rtx mem ATTRIBUTE_UNUSED
,
864 rtx op ATTRIBUTE_UNUSED
,
865 rtx dest
, rtx src
, rtx srcoff
, void *arg
)
867 insn_info_t insn_info
= (insn_info_t
) arg
;
868 rtx insn
= insn_info
->insn
, new_insn
, cur
;
869 note_add_store_info info
;
871 /* We can reuse all operands without copying, because we are about
872 to delete the insn that contained it. */
876 emit_insn (gen_add3_insn (dest
, src
, srcoff
));
877 new_insn
= get_insns ();
881 new_insn
= gen_move_insn (dest
, src
);
882 info
.first
= new_insn
;
883 info
.fixed_regs_live
= insn_info
->fixed_regs_live
;
884 info
.failure
= false;
885 for (cur
= new_insn
; cur
; cur
= NEXT_INSN (cur
))
888 note_stores (PATTERN (cur
), note_add_store
, &info
);
891 /* If a failure was flagged above, return 1 so that for_each_inc_dec will
892 return it immediately, communicating the failure to its caller. */
896 emit_insn_before (new_insn
, insn
);
901 /* Before we delete INSN_INFO->INSN, make sure that the auto inc/dec, if it
902 is there, is split into a separate insn.
903 Return true on success (or if there was nothing to do), false on failure. */
906 check_for_inc_dec_1 (insn_info_t insn_info
)
908 rtx insn
= insn_info
->insn
;
909 rtx note
= find_reg_note (insn
, REG_INC
, NULL_RTX
);
911 return for_each_inc_dec (&insn
, emit_inc_dec_insn_before
, insn_info
) == 0;
916 /* Entry point for postreload. If you work on reload_cse, or you need this
917 anywhere else, consider if you can provide register liveness information
918 and add a parameter to this function so that it can be passed down in
919 insn_info.fixed_regs_live. */
921 check_for_inc_dec (rtx insn
)
923 struct insn_info insn_info
;
926 insn_info
.insn
= insn
;
927 insn_info
.fixed_regs_live
= NULL
;
928 note
= find_reg_note (insn
, REG_INC
, NULL_RTX
);
930 return for_each_inc_dec (&insn
, emit_inc_dec_insn_before
, &insn_info
) == 0;
934 /* Delete the insn and free all of the fields inside INSN_INFO. */
937 delete_dead_store_insn (insn_info_t insn_info
)
939 read_info_t read_info
;
944 if (!check_for_inc_dec_1 (insn_info
))
948 fprintf (dump_file
, "Locally deleting insn %d ",
949 INSN_UID (insn_info
->insn
));
950 if (insn_info
->store_rec
->alias_set
)
951 fprintf (dump_file
, "alias set %d\n",
952 (int) insn_info
->store_rec
->alias_set
);
954 fprintf (dump_file
, "\n");
957 free_store_info (insn_info
);
958 read_info
= insn_info
->read_rec
;
962 read_info_t next
= read_info
->next
;
963 pool_free (read_info_pool
, read_info
);
966 insn_info
->read_rec
= NULL
;
968 delete_insn (insn_info
->insn
);
970 insn_info
->insn
= NULL
;
972 insn_info
->wild_read
= false;
975 /* Check if EXPR can possibly escape the current function scope. */
977 can_escape (tree expr
)
982 base
= get_base_address (expr
);
984 && !may_be_aliased (base
))
989 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
993 set_usage_bits (group_info_t group
, HOST_WIDE_INT offset
, HOST_WIDE_INT width
,
997 bool expr_escapes
= can_escape (expr
);
998 if (offset
> -MAX_OFFSET
&& offset
+ width
< MAX_OFFSET
)
999 for (i
=offset
; i
<offset
+width
; i
++)
1007 store1
= group
->store1_n
;
1008 store2
= group
->store2_n
;
1009 escaped
= group
->escaped_n
;
1014 store1
= group
->store1_p
;
1015 store2
= group
->store2_p
;
1016 escaped
= group
->escaped_p
;
1020 if (!bitmap_set_bit (store1
, ai
))
1021 bitmap_set_bit (store2
, ai
);
1026 if (group
->offset_map_size_n
< ai
)
1027 group
->offset_map_size_n
= ai
;
1031 if (group
->offset_map_size_p
< ai
)
1032 group
->offset_map_size_p
= ai
;
1036 bitmap_set_bit (escaped
, ai
);
1041 reset_active_stores (void)
1043 active_local_stores
= NULL
;
1044 active_local_stores_len
= 0;
1047 /* Free all READ_REC of the LAST_INSN of BB_INFO. */
1050 free_read_records (bb_info_t bb_info
)
1052 insn_info_t insn_info
= bb_info
->last_insn
;
1053 read_info_t
*ptr
= &insn_info
->read_rec
;
1056 read_info_t next
= (*ptr
)->next
;
1057 if ((*ptr
)->alias_set
== 0)
1059 pool_free (read_info_pool
, *ptr
);
1063 ptr
= &(*ptr
)->next
;
1067 /* Set the BB_INFO so that the last insn is marked as a wild read. */
1070 add_wild_read (bb_info_t bb_info
)
1072 insn_info_t insn_info
= bb_info
->last_insn
;
1073 insn_info
->wild_read
= true;
1074 free_read_records (bb_info
);
1075 reset_active_stores ();
1078 /* Set the BB_INFO so that the last insn is marked as a wild read of
1079 non-frame locations. */
1082 add_non_frame_wild_read (bb_info_t bb_info
)
1084 insn_info_t insn_info
= bb_info
->last_insn
;
1085 insn_info
->non_frame_wild_read
= true;
1086 free_read_records (bb_info
);
1087 reset_active_stores ();
1090 /* Return true if X is a constant or one of the registers that behave
1091 as a constant over the life of a function. This is equivalent to
1092 !rtx_varies_p for memory addresses. */
1095 const_or_frame_p (rtx x
)
1097 switch (GET_CODE (x
))
1108 /* Note that we have to test for the actual rtx used for the frame
1109 and arg pointers and not just the register number in case we have
1110 eliminated the frame and/or arg pointer and are using it
1112 if (x
== frame_pointer_rtx
|| x
== hard_frame_pointer_rtx
1113 /* The arg pointer varies if it is not a fixed register. */
1114 || (x
== arg_pointer_rtx
&& fixed_regs
[ARG_POINTER_REGNUM
])
1115 || x
== pic_offset_table_rtx
)
1124 /* Take all reasonable action to put the address of MEM into the form
1125 that we can do analysis on.
1127 The gold standard is to get the address into the form: address +
1128 OFFSET where address is something that rtx_varies_p considers a
1129 constant. When we can get the address in this form, we can do
1130 global analysis on it. Note that for constant bases, address is
1131 not actually returned, only the group_id. The address can be
1134 If that fails, we try cselib to get a value we can at least use
1135 locally. If that fails we return false.
1137 The GROUP_ID is set to -1 for cselib bases and the index of the
1138 group for non_varying bases.
1140 FOR_READ is true if this is a mem read and false if not. */
1143 canon_address (rtx mem
,
1144 alias_set_type
*alias_set_out
,
1146 HOST_WIDE_INT
*offset
,
1149 enum machine_mode address_mode
1150 = targetm
.addr_space
.address_mode (MEM_ADDR_SPACE (mem
));
1151 rtx mem_address
= XEXP (mem
, 0);
1152 rtx expanded_address
, address
;
1155 /* Make sure that cselib is has initialized all of the operands of
1156 the address before asking it to do the subst. */
1158 if (clear_alias_sets
)
1160 /* If this is a spill, do not do any further processing. */
1161 alias_set_type alias_set
= MEM_ALIAS_SET (mem
);
1163 fprintf (dump_file
, "found alias set %d\n", (int) alias_set
);
1164 if (bitmap_bit_p (clear_alias_sets
, alias_set
))
1166 struct clear_alias_mode_holder
*entry
1167 = clear_alias_set_lookup (alias_set
);
1169 /* If the modes do not match, we cannot process this set. */
1170 if (entry
->mode
!= GET_MODE (mem
))
1174 "disqualifying alias set %d, (%s) != (%s)\n",
1175 (int) alias_set
, GET_MODE_NAME (entry
->mode
),
1176 GET_MODE_NAME (GET_MODE (mem
)));
1178 bitmap_set_bit (disqualified_clear_alias_sets
, alias_set
);
1182 *alias_set_out
= alias_set
;
1183 *group_id
= clear_alias_group
->id
;
1190 cselib_lookup (mem_address
, address_mode
, 1, GET_MODE (mem
));
1194 fprintf (dump_file
, " mem: ");
1195 print_inline_rtx (dump_file
, mem_address
, 0);
1196 fprintf (dump_file
, "\n");
1199 /* First see if just canon_rtx (mem_address) is const or frame,
1200 if not, try cselib_expand_value_rtx and call canon_rtx on that. */
1202 for (expanded
= 0; expanded
< 2; expanded
++)
1206 /* Use cselib to replace all of the reg references with the full
1207 expression. This will take care of the case where we have
1209 r_x = base + offset;
1214 val = *(base + offset); */
1216 expanded_address
= cselib_expand_value_rtx (mem_address
,
1219 /* If this fails, just go with the address from first
1221 if (!expanded_address
)
1225 expanded_address
= mem_address
;
1227 /* Split the address into canonical BASE + OFFSET terms. */
1228 address
= canon_rtx (expanded_address
);
1236 fprintf (dump_file
, "\n after cselib_expand address: ");
1237 print_inline_rtx (dump_file
, expanded_address
, 0);
1238 fprintf (dump_file
, "\n");
1241 fprintf (dump_file
, "\n after canon_rtx address: ");
1242 print_inline_rtx (dump_file
, address
, 0);
1243 fprintf (dump_file
, "\n");
1246 if (GET_CODE (address
) == CONST
)
1247 address
= XEXP (address
, 0);
1249 if (GET_CODE (address
) == PLUS
1250 && CONST_INT_P (XEXP (address
, 1)))
1252 *offset
= INTVAL (XEXP (address
, 1));
1253 address
= XEXP (address
, 0);
1256 if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem
))
1257 && const_or_frame_p (address
))
1259 group_info_t group
= get_group_info (address
);
1262 fprintf (dump_file
, " gid=%d offset=%d \n",
1263 group
->id
, (int)*offset
);
1265 *group_id
= group
->id
;
1270 *base
= cselib_lookup (address
, address_mode
, true, GET_MODE (mem
));
1276 fprintf (dump_file
, " no cselib val - should be a wild read.\n");
1280 fprintf (dump_file
, " varying cselib base=%u:%u offset = %d\n",
1281 (*base
)->uid
, (*base
)->hash
, (int)*offset
);
1286 /* Clear the rhs field from the active_local_stores array. */
1289 clear_rhs_from_active_local_stores (void)
1291 insn_info_t ptr
= active_local_stores
;
1295 store_info_t store_info
= ptr
->store_rec
;
1296 /* Skip the clobbers. */
1297 while (!store_info
->is_set
)
1298 store_info
= store_info
->next
;
1300 store_info
->rhs
= NULL
;
1301 store_info
->const_rhs
= NULL
;
1303 ptr
= ptr
->next_local_store
;
1308 /* Mark byte POS bytes from the beginning of store S_INFO as unneeded. */
1311 set_position_unneeded (store_info_t s_info
, int pos
)
1313 if (__builtin_expect (s_info
->is_large
, false))
1315 if (bitmap_set_bit (s_info
->positions_needed
.large
.bmap
, pos
))
1316 s_info
->positions_needed
.large
.count
++;
1319 s_info
->positions_needed
.small_bitmask
1320 &= ~(((unsigned HOST_WIDE_INT
) 1) << pos
);
1323 /* Mark the whole store S_INFO as unneeded. */
1326 set_all_positions_unneeded (store_info_t s_info
)
1328 if (__builtin_expect (s_info
->is_large
, false))
1330 int pos
, end
= s_info
->end
- s_info
->begin
;
1331 for (pos
= 0; pos
< end
; pos
++)
1332 bitmap_set_bit (s_info
->positions_needed
.large
.bmap
, pos
);
1333 s_info
->positions_needed
.large
.count
= end
;
1336 s_info
->positions_needed
.small_bitmask
= (unsigned HOST_WIDE_INT
) 0;
1339 /* Return TRUE if any bytes from S_INFO store are needed. */
1342 any_positions_needed_p (store_info_t s_info
)
1344 if (__builtin_expect (s_info
->is_large
, false))
1345 return (s_info
->positions_needed
.large
.count
1346 < s_info
->end
- s_info
->begin
);
1348 return (s_info
->positions_needed
.small_bitmask
1349 != (unsigned HOST_WIDE_INT
) 0);
1352 /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
1353 store are needed. */
1356 all_positions_needed_p (store_info_t s_info
, int start
, int width
)
1358 if (__builtin_expect (s_info
->is_large
, false))
1360 int end
= start
+ width
;
1362 if (bitmap_bit_p (s_info
->positions_needed
.large
.bmap
, start
++))
1368 unsigned HOST_WIDE_INT mask
= lowpart_bitmask (width
) << start
;
1369 return (s_info
->positions_needed
.small_bitmask
& mask
) == mask
;
1374 static rtx
get_stored_val (store_info_t
, enum machine_mode
, HOST_WIDE_INT
,
1375 HOST_WIDE_INT
, basic_block
, bool);
1378 /* BODY is an instruction pattern that belongs to INSN. Return 1 if
1379 there is a candidate store, after adding it to the appropriate
1380 local store group if so. */
1383 record_store (rtx body
, bb_info_t bb_info
)
1385 rtx mem
, rhs
, const_rhs
, mem_addr
;
1386 HOST_WIDE_INT offset
= 0;
1387 HOST_WIDE_INT width
= 0;
1388 alias_set_type spill_alias_set
;
1389 insn_info_t insn_info
= bb_info
->last_insn
;
1390 store_info_t store_info
= NULL
;
1392 cselib_val
*base
= NULL
;
1393 insn_info_t ptr
, last
, redundant_reason
;
1394 bool store_is_unused
;
1396 if (GET_CODE (body
) != SET
&& GET_CODE (body
) != CLOBBER
)
1399 mem
= SET_DEST (body
);
1401 /* If this is not used, then this cannot be used to keep the insn
1402 from being deleted. On the other hand, it does provide something
1403 that can be used to prove that another store is dead. */
1405 = (find_reg_note (insn_info
->insn
, REG_UNUSED
, mem
) != NULL
);
1407 /* Check whether that value is a suitable memory location. */
1410 /* If the set or clobber is unused, then it does not effect our
1411 ability to get rid of the entire insn. */
1412 if (!store_is_unused
)
1413 insn_info
->cannot_delete
= true;
1417 /* At this point we know mem is a mem. */
1418 if (GET_MODE (mem
) == BLKmode
)
1420 if (GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
1423 fprintf (dump_file
, " adding wild read for (clobber (mem:BLK (scratch))\n");
1424 add_wild_read (bb_info
);
1425 insn_info
->cannot_delete
= true;
1428 /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
1429 as memset (addr, 0, 36); */
1430 else if (!MEM_SIZE_KNOWN_P (mem
)
1431 || MEM_SIZE (mem
) <= 0
1432 || MEM_SIZE (mem
) > MAX_OFFSET
1433 || GET_CODE (body
) != SET
1434 || !CONST_INT_P (SET_SRC (body
)))
1436 if (!store_is_unused
)
1438 /* If the set or clobber is unused, then it does not effect our
1439 ability to get rid of the entire insn. */
1440 insn_info
->cannot_delete
= true;
1441 clear_rhs_from_active_local_stores ();
1447 /* We can still process a volatile mem, we just cannot delete it. */
1448 if (MEM_VOLATILE_P (mem
))
1449 insn_info
->cannot_delete
= true;
1451 if (!canon_address (mem
, &spill_alias_set
, &group_id
, &offset
, &base
))
1453 clear_rhs_from_active_local_stores ();
1457 if (GET_MODE (mem
) == BLKmode
)
1458 width
= MEM_SIZE (mem
);
1461 width
= GET_MODE_SIZE (GET_MODE (mem
));
1462 gcc_assert ((unsigned) width
<= HOST_BITS_PER_WIDE_INT
);
1465 if (spill_alias_set
)
1467 bitmap store1
= clear_alias_group
->store1_p
;
1468 bitmap store2
= clear_alias_group
->store2_p
;
1470 gcc_assert (GET_MODE (mem
) != BLKmode
);
1472 if (!bitmap_set_bit (store1
, spill_alias_set
))
1473 bitmap_set_bit (store2
, spill_alias_set
);
1475 if (clear_alias_group
->offset_map_size_p
< spill_alias_set
)
1476 clear_alias_group
->offset_map_size_p
= spill_alias_set
;
1478 store_info
= (store_info_t
) pool_alloc (rtx_store_info_pool
);
1481 fprintf (dump_file
, " processing spill store %d(%s)\n",
1482 (int) spill_alias_set
, GET_MODE_NAME (GET_MODE (mem
)));
1484 else if (group_id
>= 0)
1486 /* In the restrictive case where the base is a constant or the
1487 frame pointer we can do global analysis. */
1490 = VEC_index (group_info_t
, rtx_group_vec
, group_id
);
1491 tree expr
= MEM_EXPR (mem
);
1493 store_info
= (store_info_t
) pool_alloc (rtx_store_info_pool
);
1494 set_usage_bits (group
, offset
, width
, expr
);
1497 fprintf (dump_file
, " processing const base store gid=%d[%d..%d)\n",
1498 group_id
, (int)offset
, (int)(offset
+width
));
1502 rtx base_term
= find_base_term (XEXP (mem
, 0));
1504 || (GET_CODE (base_term
) == ADDRESS
1505 && GET_MODE (base_term
) == Pmode
1506 && XWINT (base_term
, 0) == UNIQUE_BASE_VALUE_SP
))
1507 insn_info
->stack_pointer_based
= true;
1508 insn_info
->contains_cselib_groups
= true;
1510 store_info
= (store_info_t
) pool_alloc (cse_store_info_pool
);
1514 fprintf (dump_file
, " processing cselib store [%d..%d)\n",
1515 (int)offset
, (int)(offset
+width
));
1518 const_rhs
= rhs
= NULL_RTX
;
1519 if (GET_CODE (body
) == SET
1520 /* No place to keep the value after ra. */
1521 && !reload_completed
1522 && (REG_P (SET_SRC (body
))
1523 || GET_CODE (SET_SRC (body
)) == SUBREG
1524 || CONSTANT_P (SET_SRC (body
)))
1525 && !MEM_VOLATILE_P (mem
)
1526 /* Sometimes the store and reload is used for truncation and
1528 && !(FLOAT_MODE_P (GET_MODE (mem
)) && (flag_float_store
)))
1530 rhs
= SET_SRC (body
);
1531 if (CONSTANT_P (rhs
))
1533 else if (body
== PATTERN (insn_info
->insn
))
1535 rtx tem
= find_reg_note (insn_info
->insn
, REG_EQUAL
, NULL_RTX
);
1536 if (tem
&& CONSTANT_P (XEXP (tem
, 0)))
1537 const_rhs
= XEXP (tem
, 0);
1539 if (const_rhs
== NULL_RTX
&& REG_P (rhs
))
1541 rtx tem
= cselib_expand_value_rtx (rhs
, scratch
, 5);
1543 if (tem
&& CONSTANT_P (tem
))
1548 /* Check to see if this stores causes some other stores to be
1550 ptr
= active_local_stores
;
1552 redundant_reason
= NULL
;
1553 mem
= canon_rtx (mem
);
1554 /* For alias_set != 0 canon_true_dependence should be never called. */
1555 if (spill_alias_set
)
1556 mem_addr
= NULL_RTX
;
1560 mem_addr
= base
->val_rtx
;
1564 = VEC_index (group_info_t
, rtx_group_vec
, group_id
);
1565 mem_addr
= group
->canon_base_addr
;
1568 mem_addr
= plus_constant (mem_addr
, offset
);
1573 insn_info_t next
= ptr
->next_local_store
;
1574 store_info_t s_info
= ptr
->store_rec
;
1577 /* Skip the clobbers. We delete the active insn if this insn
1578 shadows the set. To have been put on the active list, it
1579 has exactly on set. */
1580 while (!s_info
->is_set
)
1581 s_info
= s_info
->next
;
1583 if (s_info
->alias_set
!= spill_alias_set
)
1585 else if (s_info
->alias_set
)
1587 struct clear_alias_mode_holder
*entry
1588 = clear_alias_set_lookup (s_info
->alias_set
);
1589 /* Generally, spills cannot be processed if and of the
1590 references to the slot have a different mode. But if
1591 we are in the same block and mode is exactly the same
1592 between this store and one before in the same block,
1593 we can still delete it. */
1594 if ((GET_MODE (mem
) == GET_MODE (s_info
->mem
))
1595 && (GET_MODE (mem
) == entry
->mode
))
1598 set_all_positions_unneeded (s_info
);
1601 fprintf (dump_file
, " trying spill store in insn=%d alias_set=%d\n",
1602 INSN_UID (ptr
->insn
), (int) s_info
->alias_set
);
1604 else if ((s_info
->group_id
== group_id
)
1605 && (s_info
->cse_base
== base
))
1609 fprintf (dump_file
, " trying store in insn=%d gid=%d[%d..%d)\n",
1610 INSN_UID (ptr
->insn
), s_info
->group_id
,
1611 (int)s_info
->begin
, (int)s_info
->end
);
1613 /* Even if PTR won't be eliminated as unneeded, if both
1614 PTR and this insn store the same constant value, we might
1615 eliminate this insn instead. */
1616 if (s_info
->const_rhs
1618 && offset
>= s_info
->begin
1619 && offset
+ width
<= s_info
->end
1620 && all_positions_needed_p (s_info
, offset
- s_info
->begin
,
1623 if (GET_MODE (mem
) == BLKmode
)
1625 if (GET_MODE (s_info
->mem
) == BLKmode
1626 && s_info
->const_rhs
== const_rhs
)
1627 redundant_reason
= ptr
;
1629 else if (s_info
->const_rhs
== const0_rtx
1630 && const_rhs
== const0_rtx
)
1631 redundant_reason
= ptr
;
1636 val
= get_stored_val (s_info
, GET_MODE (mem
),
1637 offset
, offset
+ width
,
1638 BLOCK_FOR_INSN (insn_info
->insn
),
1640 if (get_insns () != NULL
)
1643 if (val
&& rtx_equal_p (val
, const_rhs
))
1644 redundant_reason
= ptr
;
1648 for (i
= MAX (offset
, s_info
->begin
);
1649 i
< offset
+ width
&& i
< s_info
->end
;
1651 set_position_unneeded (s_info
, i
- s_info
->begin
);
1653 else if (s_info
->rhs
)
1654 /* Need to see if it is possible for this store to overwrite
1655 the value of store_info. If it is, set the rhs to NULL to
1656 keep it from being used to remove a load. */
1658 if (canon_true_dependence (s_info
->mem
,
1659 GET_MODE (s_info
->mem
),
1664 s_info
->const_rhs
= NULL
;
1668 /* An insn can be deleted if every position of every one of
1669 its s_infos is zero. */
1670 if (any_positions_needed_p (s_info
))
1675 insn_info_t insn_to_delete
= ptr
;
1677 active_local_stores_len
--;
1679 last
->next_local_store
= ptr
->next_local_store
;
1681 active_local_stores
= ptr
->next_local_store
;
1683 if (!insn_to_delete
->cannot_delete
)
1684 delete_dead_store_insn (insn_to_delete
);
1692 /* Finish filling in the store_info. */
1693 store_info
->next
= insn_info
->store_rec
;
1694 insn_info
->store_rec
= store_info
;
1695 store_info
->mem
= mem
;
1696 store_info
->alias_set
= spill_alias_set
;
1697 store_info
->mem_addr
= mem_addr
;
1698 store_info
->cse_base
= base
;
1699 if (width
> HOST_BITS_PER_WIDE_INT
)
1701 store_info
->is_large
= true;
1702 store_info
->positions_needed
.large
.count
= 0;
1703 store_info
->positions_needed
.large
.bmap
= BITMAP_ALLOC (NULL
);
1707 store_info
->is_large
= false;
1708 store_info
->positions_needed
.small_bitmask
= lowpart_bitmask (width
);
1710 store_info
->group_id
= group_id
;
1711 store_info
->begin
= offset
;
1712 store_info
->end
= offset
+ width
;
1713 store_info
->is_set
= GET_CODE (body
) == SET
;
1714 store_info
->rhs
= rhs
;
1715 store_info
->const_rhs
= const_rhs
;
1716 store_info
->redundant_reason
= redundant_reason
;
1718 /* If this is a clobber, we return 0. We will only be able to
1719 delete this insn if there is only one store USED store, but we
1720 can use the clobber to delete other stores earlier. */
1721 return store_info
->is_set
? 1 : 0;
1726 dump_insn_info (const char * start
, insn_info_t insn_info
)
1728 fprintf (dump_file
, "%s insn=%d %s\n", start
,
1729 INSN_UID (insn_info
->insn
),
1730 insn_info
->store_rec
? "has store" : "naked");
1734 /* If the modes are different and the value's source and target do not
1735 line up, we need to extract the value from lower part of the rhs of
1736 the store, shift it, and then put it into a form that can be shoved
1737 into the read_insn. This function generates a right SHIFT of a
1738 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The
1739 shift sequence is returned or NULL if we failed to find a
1743 find_shift_sequence (int access_size
,
1744 store_info_t store_info
,
1745 enum machine_mode read_mode
,
1746 int shift
, bool speed
, bool require_cst
)
1748 enum machine_mode store_mode
= GET_MODE (store_info
->mem
);
1749 enum machine_mode new_mode
;
1750 rtx read_reg
= NULL
;
1752 /* Some machines like the x86 have shift insns for each size of
1753 operand. Other machines like the ppc or the ia-64 may only have
1754 shift insns that shift values within 32 or 64 bit registers.
1755 This loop tries to find the smallest shift insn that will right
1756 justify the value we want to read but is available in one insn on
1759 for (new_mode
= smallest_mode_for_size (access_size
* BITS_PER_UNIT
,
1761 GET_MODE_BITSIZE (new_mode
) <= BITS_PER_WORD
;
1762 new_mode
= GET_MODE_WIDER_MODE (new_mode
))
1764 rtx target
, new_reg
, shift_seq
, insn
, new_lhs
;
1767 /* If a constant was stored into memory, try to simplify it here,
1768 otherwise the cost of the shift might preclude this optimization
1769 e.g. at -Os, even when no actual shift will be needed. */
1770 if (store_info
->const_rhs
)
1772 unsigned int byte
= subreg_lowpart_offset (new_mode
, store_mode
);
1773 rtx ret
= simplify_subreg (new_mode
, store_info
->const_rhs
,
1775 if (ret
&& CONSTANT_P (ret
))
1777 ret
= simplify_const_binary_operation (LSHIFTRT
, new_mode
,
1778 ret
, GEN_INT (shift
));
1779 if (ret
&& CONSTANT_P (ret
))
1781 byte
= subreg_lowpart_offset (read_mode
, new_mode
);
1782 ret
= simplify_subreg (read_mode
, ret
, new_mode
, byte
);
1783 if (ret
&& CONSTANT_P (ret
)
1784 && set_src_cost (ret
, speed
) <= COSTS_N_INSNS (1))
1793 /* Try a wider mode if truncating the store mode to NEW_MODE
1794 requires a real instruction. */
1795 if (GET_MODE_BITSIZE (new_mode
) < GET_MODE_BITSIZE (store_mode
)
1796 && !TRULY_NOOP_TRUNCATION_MODES_P (new_mode
, store_mode
))
1799 /* Also try a wider mode if the necessary punning is either not
1800 desirable or not possible. */
1801 if (!CONSTANT_P (store_info
->rhs
)
1802 && !MODES_TIEABLE_P (new_mode
, store_mode
))
1805 new_reg
= gen_reg_rtx (new_mode
);
1809 /* In theory we could also check for an ashr. Ian Taylor knows
1810 of one dsp where the cost of these two was not the same. But
1811 this really is a rare case anyway. */
1812 target
= expand_binop (new_mode
, lshr_optab
, new_reg
,
1813 GEN_INT (shift
), new_reg
, 1, OPTAB_DIRECT
);
1815 shift_seq
= get_insns ();
1818 if (target
!= new_reg
|| shift_seq
== NULL
)
1822 for (insn
= shift_seq
; insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
1824 cost
+= insn_rtx_cost (PATTERN (insn
), speed
);
1826 /* The computation up to here is essentially independent
1827 of the arguments and could be precomputed. It may
1828 not be worth doing so. We could precompute if
1829 worthwhile or at least cache the results. The result
1830 technically depends on both SHIFT and ACCESS_SIZE,
1831 but in practice the answer will depend only on ACCESS_SIZE. */
1833 if (cost
> COSTS_N_INSNS (1))
1836 new_lhs
= extract_low_bits (new_mode
, store_mode
,
1837 copy_rtx (store_info
->rhs
));
1838 if (new_lhs
== NULL_RTX
)
1841 /* We found an acceptable shift. Generate a move to
1842 take the value from the store and put it into the
1843 shift pseudo, then shift it, then generate another
1844 move to put in into the target of the read. */
1845 emit_move_insn (new_reg
, new_lhs
);
1846 emit_insn (shift_seq
);
1847 read_reg
= extract_low_bits (read_mode
, new_mode
, new_reg
);
1855 /* Call back for note_stores to find the hard regs set or clobbered by
1856 insn. Data is a bitmap of the hardregs set so far. */
1859 look_for_hardregs (rtx x
, const_rtx pat ATTRIBUTE_UNUSED
, void *data
)
1861 bitmap regs_set
= (bitmap
) data
;
1864 && HARD_REGISTER_P (x
))
1866 unsigned int regno
= REGNO (x
);
1867 bitmap_set_range (regs_set
, regno
,
1868 hard_regno_nregs
[regno
][GET_MODE (x
)]);
1872 /* Helper function for replace_read and record_store.
1873 Attempt to return a value stored in STORE_INFO, from READ_BEGIN
1874 to one before READ_END bytes read in READ_MODE. Return NULL
1875 if not successful. If REQUIRE_CST is true, return always constant. */
1878 get_stored_val (store_info_t store_info
, enum machine_mode read_mode
,
1879 HOST_WIDE_INT read_begin
, HOST_WIDE_INT read_end
,
1880 basic_block bb
, bool require_cst
)
1882 enum machine_mode store_mode
= GET_MODE (store_info
->mem
);
1884 int access_size
; /* In bytes. */
1887 /* To get here the read is within the boundaries of the write so
1888 shift will never be negative. Start out with the shift being in
1890 if (store_mode
== BLKmode
)
1892 else if (BYTES_BIG_ENDIAN
)
1893 shift
= store_info
->end
- read_end
;
1895 shift
= read_begin
- store_info
->begin
;
1897 access_size
= shift
+ GET_MODE_SIZE (read_mode
);
1899 /* From now on it is bits. */
1900 shift
*= BITS_PER_UNIT
;
1903 read_reg
= find_shift_sequence (access_size
, store_info
, read_mode
, shift
,
1904 optimize_bb_for_speed_p (bb
),
1906 else if (store_mode
== BLKmode
)
1908 /* The store is a memset (addr, const_val, const_size). */
1909 gcc_assert (CONST_INT_P (store_info
->rhs
));
1910 store_mode
= int_mode_for_mode (read_mode
);
1911 if (store_mode
== BLKmode
)
1912 read_reg
= NULL_RTX
;
1913 else if (store_info
->rhs
== const0_rtx
)
1914 read_reg
= extract_low_bits (read_mode
, store_mode
, const0_rtx
);
1915 else if (GET_MODE_BITSIZE (store_mode
) > HOST_BITS_PER_WIDE_INT
1916 || BITS_PER_UNIT
>= HOST_BITS_PER_WIDE_INT
)
1917 read_reg
= NULL_RTX
;
1920 unsigned HOST_WIDE_INT c
1921 = INTVAL (store_info
->rhs
)
1922 & (((HOST_WIDE_INT
) 1 << BITS_PER_UNIT
) - 1);
1923 int shift
= BITS_PER_UNIT
;
1924 while (shift
< HOST_BITS_PER_WIDE_INT
)
1929 read_reg
= gen_int_mode (c
, store_mode
);
1930 read_reg
= extract_low_bits (read_mode
, store_mode
, read_reg
);
1933 else if (store_info
->const_rhs
1935 || GET_MODE_CLASS (read_mode
) != GET_MODE_CLASS (store_mode
)))
1936 read_reg
= extract_low_bits (read_mode
, store_mode
,
1937 copy_rtx (store_info
->const_rhs
));
1939 read_reg
= extract_low_bits (read_mode
, store_mode
,
1940 copy_rtx (store_info
->rhs
));
1941 if (require_cst
&& read_reg
&& !CONSTANT_P (read_reg
))
1942 read_reg
= NULL_RTX
;
1946 /* Take a sequence of:
1969 Depending on the alignment and the mode of the store and
1973 The STORE_INFO and STORE_INSN are for the store and READ_INFO
1974 and READ_INSN are for the read. Return true if the replacement
1978 replace_read (store_info_t store_info
, insn_info_t store_insn
,
1979 read_info_t read_info
, insn_info_t read_insn
, rtx
*loc
,
1982 enum machine_mode store_mode
= GET_MODE (store_info
->mem
);
1983 enum machine_mode read_mode
= GET_MODE (read_info
->mem
);
1984 rtx insns
, this_insn
, read_reg
;
1990 /* Create a sequence of instructions to set up the read register.
1991 This sequence goes immediately before the store and its result
1992 is read by the load.
1994 We need to keep this in perspective. We are replacing a read
1995 with a sequence of insns, but the read will almost certainly be
1996 in cache, so it is not going to be an expensive one. Thus, we
1997 are not willing to do a multi insn shift or worse a subroutine
1998 call to get rid of the read. */
2000 fprintf (dump_file
, "trying to replace %smode load in insn %d"
2001 " from %smode store in insn %d\n",
2002 GET_MODE_NAME (read_mode
), INSN_UID (read_insn
->insn
),
2003 GET_MODE_NAME (store_mode
), INSN_UID (store_insn
->insn
));
2005 bb
= BLOCK_FOR_INSN (read_insn
->insn
);
2006 read_reg
= get_stored_val (store_info
,
2007 read_mode
, read_info
->begin
, read_info
->end
,
2009 if (read_reg
== NULL_RTX
)
2013 fprintf (dump_file
, " -- could not extract bits of stored value\n");
2016 /* Force the value into a new register so that it won't be clobbered
2017 between the store and the load. */
2018 read_reg
= copy_to_mode_reg (read_mode
, read_reg
);
2019 insns
= get_insns ();
2022 if (insns
!= NULL_RTX
)
2024 /* Now we have to scan the set of new instructions to see if the
2025 sequence contains and sets of hardregs that happened to be
2026 live at this point. For instance, this can happen if one of
2027 the insns sets the CC and the CC happened to be live at that
2028 point. This does occasionally happen, see PR 37922. */
2029 bitmap regs_set
= BITMAP_ALLOC (NULL
);
2031 for (this_insn
= insns
; this_insn
!= NULL_RTX
; this_insn
= NEXT_INSN (this_insn
))
2032 note_stores (PATTERN (this_insn
), look_for_hardregs
, regs_set
);
2034 bitmap_and_into (regs_set
, regs_live
);
2035 if (!bitmap_empty_p (regs_set
))
2040 "abandoning replacement because sequence clobbers live hardregs:");
2041 df_print_regset (dump_file
, regs_set
);
2044 BITMAP_FREE (regs_set
);
2047 BITMAP_FREE (regs_set
);
2050 if (validate_change (read_insn
->insn
, loc
, read_reg
, 0))
2052 deferred_change_t deferred_change
=
2053 (deferred_change_t
) pool_alloc (deferred_change_pool
);
2055 /* Insert this right before the store insn where it will be safe
2056 from later insns that might change it before the read. */
2057 emit_insn_before (insns
, store_insn
->insn
);
2059 /* And now for the kludge part: cselib croaks if you just
2060 return at this point. There are two reasons for this:
2062 1) Cselib has an idea of how many pseudos there are and
2063 that does not include the new ones we just added.
2065 2) Cselib does not know about the move insn we added
2066 above the store_info, and there is no way to tell it
2067 about it, because it has "moved on".
2069 Problem (1) is fixable with a certain amount of engineering.
2070 Problem (2) is requires starting the bb from scratch. This
2073 So we are just going to have to lie. The move/extraction
2074 insns are not really an issue, cselib did not see them. But
2075 the use of the new pseudo read_insn is a real problem because
2076 cselib has not scanned this insn. The way that we solve this
2077 problem is that we are just going to put the mem back for now
2078 and when we are finished with the block, we undo this. We
2079 keep a table of mems to get rid of. At the end of the basic
2080 block we can put them back. */
2082 *loc
= read_info
->mem
;
2083 deferred_change
->next
= deferred_change_list
;
2084 deferred_change_list
= deferred_change
;
2085 deferred_change
->loc
= loc
;
2086 deferred_change
->reg
= read_reg
;
2088 /* Get rid of the read_info, from the point of view of the
2089 rest of dse, play like this read never happened. */
2090 read_insn
->read_rec
= read_info
->next
;
2091 pool_free (read_info_pool
, read_info
);
2094 fprintf (dump_file
, " -- replaced the loaded MEM with ");
2095 print_simple_rtl (dump_file
, read_reg
);
2096 fprintf (dump_file
, "\n");
2104 fprintf (dump_file
, " -- replacing the loaded MEM with ");
2105 print_simple_rtl (dump_file
, read_reg
);
2106 fprintf (dump_file
, " led to an invalid instruction\n");
2112 /* A for_each_rtx callback in which DATA is the bb_info. Check to see
2113 if LOC is a mem and if it is look at the address and kill any
2114 appropriate stores that may be active. */
2117 check_mem_read_rtx (rtx
*loc
, void *data
)
2119 rtx mem
= *loc
, mem_addr
;
2121 insn_info_t insn_info
;
2122 HOST_WIDE_INT offset
= 0;
2123 HOST_WIDE_INT width
= 0;
2124 alias_set_type spill_alias_set
= 0;
2125 cselib_val
*base
= NULL
;
2127 read_info_t read_info
;
2129 if (!mem
|| !MEM_P (mem
))
2132 bb_info
= (bb_info_t
) data
;
2133 insn_info
= bb_info
->last_insn
;
2135 if ((MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
2136 || (MEM_VOLATILE_P (mem
)))
2139 fprintf (dump_file
, " adding wild read, volatile or barrier.\n");
2140 add_wild_read (bb_info
);
2141 insn_info
->cannot_delete
= true;
2145 /* If it is reading readonly mem, then there can be no conflict with
2147 if (MEM_READONLY_P (mem
))
2150 if (!canon_address (mem
, &spill_alias_set
, &group_id
, &offset
, &base
))
2153 fprintf (dump_file
, " adding wild read, canon_address failure.\n");
2154 add_wild_read (bb_info
);
2158 if (GET_MODE (mem
) == BLKmode
)
2161 width
= GET_MODE_SIZE (GET_MODE (mem
));
2163 read_info
= (read_info_t
) pool_alloc (read_info_pool
);
2164 read_info
->group_id
= group_id
;
2165 read_info
->mem
= mem
;
2166 read_info
->alias_set
= spill_alias_set
;
2167 read_info
->begin
= offset
;
2168 read_info
->end
= offset
+ width
;
2169 read_info
->next
= insn_info
->read_rec
;
2170 insn_info
->read_rec
= read_info
;
2171 /* For alias_set != 0 canon_true_dependence should be never called. */
2172 if (spill_alias_set
)
2173 mem_addr
= NULL_RTX
;
2177 mem_addr
= base
->val_rtx
;
2181 = VEC_index (group_info_t
, rtx_group_vec
, group_id
);
2182 mem_addr
= group
->canon_base_addr
;
2185 mem_addr
= plus_constant (mem_addr
, offset
);
2188 /* We ignore the clobbers in store_info. The is mildly aggressive,
2189 but there really should not be a clobber followed by a read. */
2191 if (spill_alias_set
)
2193 insn_info_t i_ptr
= active_local_stores
;
2194 insn_info_t last
= NULL
;
2197 fprintf (dump_file
, " processing spill load %d\n",
2198 (int) spill_alias_set
);
2202 store_info_t store_info
= i_ptr
->store_rec
;
2204 /* Skip the clobbers. */
2205 while (!store_info
->is_set
)
2206 store_info
= store_info
->next
;
2208 if (store_info
->alias_set
== spill_alias_set
)
2211 dump_insn_info ("removing from active", i_ptr
);
2213 active_local_stores_len
--;
2215 last
->next_local_store
= i_ptr
->next_local_store
;
2217 active_local_stores
= i_ptr
->next_local_store
;
2221 i_ptr
= i_ptr
->next_local_store
;
2224 else if (group_id
>= 0)
2226 /* This is the restricted case where the base is a constant or
2227 the frame pointer and offset is a constant. */
2228 insn_info_t i_ptr
= active_local_stores
;
2229 insn_info_t last
= NULL
;
2234 fprintf (dump_file
, " processing const load gid=%d[BLK]\n",
2237 fprintf (dump_file
, " processing const load gid=%d[%d..%d)\n",
2238 group_id
, (int)offset
, (int)(offset
+width
));
2243 bool remove
= false;
2244 store_info_t store_info
= i_ptr
->store_rec
;
2246 /* Skip the clobbers. */
2247 while (!store_info
->is_set
)
2248 store_info
= store_info
->next
;
2250 /* There are three cases here. */
2251 if (store_info
->group_id
< 0)
2252 /* We have a cselib store followed by a read from a
2255 = canon_true_dependence (store_info
->mem
,
2256 GET_MODE (store_info
->mem
),
2257 store_info
->mem_addr
,
2260 else if (group_id
== store_info
->group_id
)
2262 /* This is a block mode load. We may get lucky and
2263 canon_true_dependence may save the day. */
2266 = canon_true_dependence (store_info
->mem
,
2267 GET_MODE (store_info
->mem
),
2268 store_info
->mem_addr
,
2271 /* If this read is just reading back something that we just
2272 stored, rewrite the read. */
2276 && offset
>= store_info
->begin
2277 && offset
+ width
<= store_info
->end
2278 && all_positions_needed_p (store_info
,
2279 offset
- store_info
->begin
,
2281 && replace_read (store_info
, i_ptr
, read_info
,
2282 insn_info
, loc
, bb_info
->regs_live
))
2285 /* The bases are the same, just see if the offsets
2287 if ((offset
< store_info
->end
)
2288 && (offset
+ width
> store_info
->begin
))
2294 The else case that is missing here is that the
2295 bases are constant but different. There is nothing
2296 to do here because there is no overlap. */
2301 dump_insn_info ("removing from active", i_ptr
);
2303 active_local_stores_len
--;
2305 last
->next_local_store
= i_ptr
->next_local_store
;
2307 active_local_stores
= i_ptr
->next_local_store
;
2311 i_ptr
= i_ptr
->next_local_store
;
2316 insn_info_t i_ptr
= active_local_stores
;
2317 insn_info_t last
= NULL
;
2320 fprintf (dump_file
, " processing cselib load mem:");
2321 print_inline_rtx (dump_file
, mem
, 0);
2322 fprintf (dump_file
, "\n");
2327 bool remove
= false;
2328 store_info_t store_info
= i_ptr
->store_rec
;
2331 fprintf (dump_file
, " processing cselib load against insn %d\n",
2332 INSN_UID (i_ptr
->insn
));
2334 /* Skip the clobbers. */
2335 while (!store_info
->is_set
)
2336 store_info
= store_info
->next
;
2338 /* If this read is just reading back something that we just
2339 stored, rewrite the read. */
2341 && store_info
->group_id
== -1
2342 && store_info
->cse_base
== base
2344 && offset
>= store_info
->begin
2345 && offset
+ width
<= store_info
->end
2346 && all_positions_needed_p (store_info
,
2347 offset
- store_info
->begin
, width
)
2348 && replace_read (store_info
, i_ptr
, read_info
, insn_info
, loc
,
2349 bb_info
->regs_live
))
2352 if (!store_info
->alias_set
)
2353 remove
= canon_true_dependence (store_info
->mem
,
2354 GET_MODE (store_info
->mem
),
2355 store_info
->mem_addr
,
2361 dump_insn_info ("removing from active", i_ptr
);
2363 active_local_stores_len
--;
2365 last
->next_local_store
= i_ptr
->next_local_store
;
2367 active_local_stores
= i_ptr
->next_local_store
;
2371 i_ptr
= i_ptr
->next_local_store
;
2377 /* A for_each_rtx callback in which DATA points the INSN_INFO for
2378 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
2379 true for any part of *LOC. */
2382 check_mem_read_use (rtx
*loc
, void *data
)
2384 for_each_rtx (loc
, check_mem_read_rtx
, data
);
2388 /* Get arguments passed to CALL_INSN. Return TRUE if successful.
2389 So far it only handles arguments passed in registers. */
2392 get_call_args (rtx call_insn
, tree fn
, rtx
*args
, int nargs
)
2394 CUMULATIVE_ARGS args_so_far_v
;
2395 cumulative_args_t args_so_far
;
2399 INIT_CUMULATIVE_ARGS (args_so_far_v
, TREE_TYPE (fn
), NULL_RTX
, 0, 3);
2400 args_so_far
= pack_cumulative_args (&args_so_far_v
);
2402 arg
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2404 arg
!= void_list_node
&& idx
< nargs
;
2405 arg
= TREE_CHAIN (arg
), idx
++)
2407 enum machine_mode mode
= TYPE_MODE (TREE_VALUE (arg
));
2409 reg
= targetm
.calls
.function_arg (args_so_far
, mode
, NULL_TREE
, true);
2410 if (!reg
|| !REG_P (reg
) || GET_MODE (reg
) != mode
2411 || GET_MODE_CLASS (mode
) != MODE_INT
)
2414 for (link
= CALL_INSN_FUNCTION_USAGE (call_insn
);
2416 link
= XEXP (link
, 1))
2417 if (GET_CODE (XEXP (link
, 0)) == USE
)
2419 args
[idx
] = XEXP (XEXP (link
, 0), 0);
2420 if (REG_P (args
[idx
])
2421 && REGNO (args
[idx
]) == REGNO (reg
)
2422 && (GET_MODE (args
[idx
]) == mode
2423 || (GET_MODE_CLASS (GET_MODE (args
[idx
])) == MODE_INT
2424 && (GET_MODE_SIZE (GET_MODE (args
[idx
]))
2426 && (GET_MODE_SIZE (GET_MODE (args
[idx
]))
2427 > GET_MODE_SIZE (mode
)))))
2433 tmp
= cselib_expand_value_rtx (args
[idx
], scratch
, 5);
2434 if (GET_MODE (args
[idx
]) != mode
)
2436 if (!tmp
|| !CONST_INT_P (tmp
))
2438 tmp
= gen_int_mode (INTVAL (tmp
), mode
);
2443 targetm
.calls
.function_arg_advance (args_so_far
, mode
, NULL_TREE
, true);
2445 if (arg
!= void_list_node
|| idx
!= nargs
)
2450 /* Return a bitmap of the fixed registers contained in IN. */
2453 copy_fixed_regs (const_bitmap in
)
2457 ret
= ALLOC_REG_SET (NULL
);
2458 bitmap_and (ret
, in
, fixed_reg_set_regset
);
2462 /* Apply record_store to all candidate stores in INSN. Mark INSN
2463 if some part of it is not a candidate store and assigns to a
2464 non-register target. */
2467 scan_insn (bb_info_t bb_info
, rtx insn
)
2470 insn_info_t insn_info
= (insn_info_t
) pool_alloc (insn_info_pool
);
2472 memset (insn_info
, 0, sizeof (struct insn_info
));
2475 fprintf (dump_file
, "\n**scanning insn=%d\n",
2478 insn_info
->prev_insn
= bb_info
->last_insn
;
2479 insn_info
->insn
= insn
;
2480 bb_info
->last_insn
= insn_info
;
2482 if (DEBUG_INSN_P (insn
))
2484 insn_info
->cannot_delete
= true;
2488 /* Cselib clears the table for this case, so we have to essentially
2490 if (NONJUMP_INSN_P (insn
)
2491 && GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
2492 && MEM_VOLATILE_P (PATTERN (insn
)))
2494 add_wild_read (bb_info
);
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
= PATTERN (insn
);
2517 if (GET_CODE (call
) == PARALLEL
)
2518 call
= XVECEXP (call
, 0, 0);
2519 if (GET_CODE (call
) == SET
)
2520 call
= SET_SRC (call
);
2521 if (GET_CODE (call
) == CALL
2522 && MEM_P (XEXP (call
, 0))
2523 && GET_CODE (XEXP (XEXP (call
, 0), 0)) == SYMBOL_REF
)
2525 rtx symbol
= XEXP (XEXP (call
, 0), 0);
2526 if (SYMBOL_REF_DECL (symbol
)
2527 && TREE_CODE (SYMBOL_REF_DECL (symbol
)) == FUNCTION_DECL
)
2529 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol
))
2531 && (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol
))
2532 == BUILT_IN_MEMSET
))
2533 || SYMBOL_REF_DECL (symbol
) == block_clear_fn
)
2534 memset_call
= SYMBOL_REF_DECL (symbol
);
2538 if (const_call
|| memset_call
)
2540 insn_info_t i_ptr
= active_local_stores
;
2541 insn_info_t last
= NULL
;
2544 fprintf (dump_file
, "%s call %d\n",
2545 const_call
? "const" : "memset", INSN_UID (insn
));
2547 /* See the head comment of the frame_read field. */
2548 if (reload_completed
)
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 && VEC_index (group_info_t
, rtx_group_vec
,
2572 store_info
->group_id
)->frame_related
)
2573 remove_store
= true;
2579 dump_insn_info ("removing from active", i_ptr
);
2581 active_local_stores_len
--;
2583 last
->next_local_store
= i_ptr
->next_local_store
;
2585 active_local_stores
= i_ptr
->next_local_store
;
2590 i_ptr
= i_ptr
->next_local_store
;
2596 if (get_call_args (insn
, memset_call
, args
, 3)
2597 && CONST_INT_P (args
[1])
2598 && CONST_INT_P (args
[2])
2599 && INTVAL (args
[2]) > 0)
2601 rtx mem
= gen_rtx_MEM (BLKmode
, args
[0]);
2602 set_mem_size (mem
, INTVAL (args
[2]));
2603 body
= gen_rtx_SET (VOIDmode
, mem
, args
[1]);
2604 mems_found
+= record_store (body
, bb_info
);
2606 fprintf (dump_file
, "handling memset as BLKmode store\n");
2607 if (mems_found
== 1)
2609 if (active_local_stores_len
++
2610 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES
))
2612 active_local_stores_len
= 1;
2613 active_local_stores
= NULL
;
2615 insn_info
->fixed_regs_live
2616 = copy_fixed_regs (bb_info
->regs_live
);
2617 insn_info
->next_local_store
= active_local_stores
;
2618 active_local_stores
= insn_info
;
2625 /* Every other call, including pure functions, may read any memory
2626 that is not relative to the frame. */
2627 add_non_frame_wild_read (bb_info
);
2632 /* Assuming that there are sets in these insns, we cannot delete
2634 if ((GET_CODE (PATTERN (insn
)) == CLOBBER
)
2635 || volatile_refs_p (PATTERN (insn
))
2636 || insn_could_throw_p (insn
)
2637 || (RTX_FRAME_RELATED_P (insn
))
2638 || find_reg_note (insn
, REG_FRAME_RELATED_EXPR
, NULL_RTX
))
2639 insn_info
->cannot_delete
= true;
2641 body
= PATTERN (insn
);
2642 if (GET_CODE (body
) == PARALLEL
)
2645 for (i
= 0; i
< XVECLEN (body
, 0); i
++)
2646 mems_found
+= record_store (XVECEXP (body
, 0, i
), bb_info
);
2649 mems_found
+= record_store (body
, bb_info
);
2652 fprintf (dump_file
, "mems_found = %d, cannot_delete = %s\n",
2653 mems_found
, insn_info
->cannot_delete
? "true" : "false");
2655 /* If we found some sets of mems, add it into the active_local_stores so
2656 that it can be locally deleted if found dead or used for
2657 replace_read and redundant constant store elimination. Otherwise mark
2658 it as cannot delete. This simplifies the processing later. */
2659 if (mems_found
== 1)
2661 if (active_local_stores_len
++
2662 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES
))
2664 active_local_stores_len
= 1;
2665 active_local_stores
= NULL
;
2667 insn_info
->fixed_regs_live
= copy_fixed_regs (bb_info
->regs_live
);
2668 insn_info
->next_local_store
= active_local_stores
;
2669 active_local_stores
= insn_info
;
2672 insn_info
->cannot_delete
= true;
2676 /* Remove BASE from the set of active_local_stores. This is a
2677 callback from cselib that is used to get rid of the stores in
2678 active_local_stores. */
2681 remove_useless_values (cselib_val
*base
)
2683 insn_info_t insn_info
= active_local_stores
;
2684 insn_info_t last
= NULL
;
2688 store_info_t store_info
= insn_info
->store_rec
;
2691 /* If ANY of the store_infos match the cselib group that is
2692 being deleted, then the insn can not be deleted. */
2695 if ((store_info
->group_id
== -1)
2696 && (store_info
->cse_base
== base
))
2701 store_info
= store_info
->next
;
2706 active_local_stores_len
--;
2708 last
->next_local_store
= insn_info
->next_local_store
;
2710 active_local_stores
= insn_info
->next_local_store
;
2711 free_store_info (insn_info
);
2716 insn_info
= insn_info
->next_local_store
;
2721 /* Do all of step 1. */
2727 bitmap regs_live
= BITMAP_ALLOC (NULL
);
2730 all_blocks
= BITMAP_ALLOC (NULL
);
2731 bitmap_set_bit (all_blocks
, ENTRY_BLOCK
);
2732 bitmap_set_bit (all_blocks
, EXIT_BLOCK
);
2737 bb_info_t bb_info
= (bb_info_t
) pool_alloc (bb_info_pool
);
2739 memset (bb_info
, 0, sizeof (struct bb_info
));
2740 bitmap_set_bit (all_blocks
, bb
->index
);
2741 bb_info
->regs_live
= regs_live
;
2743 bitmap_copy (regs_live
, DF_LR_IN (bb
));
2744 df_simulate_initialize_forwards (bb
, regs_live
);
2746 bb_table
[bb
->index
] = bb_info
;
2747 cselib_discard_hook
= remove_useless_values
;
2749 if (bb
->index
>= NUM_FIXED_BLOCKS
)
2754 = create_alloc_pool ("cse_store_info_pool",
2755 sizeof (struct store_info
), 100);
2756 active_local_stores
= NULL
;
2757 active_local_stores_len
= 0;
2758 cselib_clear_table ();
2760 /* Scan the insns. */
2761 FOR_BB_INSNS (bb
, insn
)
2764 scan_insn (bb_info
, insn
);
2765 cselib_process_insn (insn
);
2767 df_simulate_one_insn_forwards (bb
, insn
, regs_live
);
2770 /* This is something of a hack, because the global algorithm
2771 is supposed to take care of the case where stores go dead
2772 at the end of the function. However, the global
2773 algorithm must take a more conservative view of block
2774 mode reads than the local alg does. So to get the case
2775 where you have a store to the frame followed by a non
2776 overlapping block more read, we look at the active local
2777 stores at the end of the function and delete all of the
2778 frame and spill based ones. */
2779 if (stores_off_frame_dead_at_return
2780 && (EDGE_COUNT (bb
->succs
) == 0
2781 || (single_succ_p (bb
)
2782 && single_succ (bb
) == EXIT_BLOCK_PTR
2783 && ! crtl
->calls_eh_return
)))
2785 insn_info_t i_ptr
= active_local_stores
;
2788 store_info_t store_info
= i_ptr
->store_rec
;
2790 /* Skip the clobbers. */
2791 while (!store_info
->is_set
)
2792 store_info
= store_info
->next
;
2793 if (store_info
->alias_set
&& !i_ptr
->cannot_delete
)
2794 delete_dead_store_insn (i_ptr
);
2796 if (store_info
->group_id
>= 0)
2799 = VEC_index (group_info_t
, rtx_group_vec
, store_info
->group_id
);
2800 if (group
->frame_related
&& !i_ptr
->cannot_delete
)
2801 delete_dead_store_insn (i_ptr
);
2804 i_ptr
= i_ptr
->next_local_store
;
2808 /* Get rid of the loads that were discovered in
2809 replace_read. Cselib is finished with this block. */
2810 while (deferred_change_list
)
2812 deferred_change_t next
= deferred_change_list
->next
;
2814 /* There is no reason to validate this change. That was
2816 *deferred_change_list
->loc
= deferred_change_list
->reg
;
2817 pool_free (deferred_change_pool
, deferred_change_list
);
2818 deferred_change_list
= next
;
2821 /* Get rid of all of the cselib based store_infos in this
2822 block and mark the containing insns as not being
2824 ptr
= bb_info
->last_insn
;
2827 if (ptr
->contains_cselib_groups
)
2829 store_info_t s_info
= ptr
->store_rec
;
2830 while (s_info
&& !s_info
->is_set
)
2831 s_info
= s_info
->next
;
2833 && s_info
->redundant_reason
2834 && s_info
->redundant_reason
->insn
2835 && !ptr
->cannot_delete
)
2838 fprintf (dump_file
, "Locally deleting insn %d "
2839 "because insn %d stores the "
2840 "same value and couldn't be "
2842 INSN_UID (ptr
->insn
),
2843 INSN_UID (s_info
->redundant_reason
->insn
));
2844 delete_dead_store_insn (ptr
);
2847 s_info
->redundant_reason
= NULL
;
2848 free_store_info (ptr
);
2852 store_info_t s_info
;
2854 /* Free at least positions_needed bitmaps. */
2855 for (s_info
= ptr
->store_rec
; s_info
; s_info
= s_info
->next
)
2856 if (s_info
->is_large
)
2858 BITMAP_FREE (s_info
->positions_needed
.large
.bmap
);
2859 s_info
->is_large
= false;
2862 ptr
= ptr
->prev_insn
;
2865 free_alloc_pool (cse_store_info_pool
);
2867 bb_info
->regs_live
= NULL
;
2870 BITMAP_FREE (regs_live
);
2872 htab_empty (rtx_group_table
);
2876 /*----------------------------------------------------------------------------
2879 Assign each byte position in the stores that we are going to
2880 analyze globally to a position in the bitmaps. Returns true if
2881 there are any bit positions assigned.
2882 ----------------------------------------------------------------------------*/
2885 dse_step2_init (void)
2890 FOR_EACH_VEC_ELT (group_info_t
, rtx_group_vec
, i
, group
)
2892 /* For all non stack related bases, we only consider a store to
2893 be deletable if there are two or more stores for that
2894 position. This is because it takes one store to make the
2895 other store redundant. However, for the stores that are
2896 stack related, we consider them if there is only one store
2897 for the position. We do this because the stack related
2898 stores can be deleted if their is no read between them and
2899 the end of the function.
2901 To make this work in the current framework, we take the stack
2902 related bases add all of the bits from store1 into store2.
2903 This has the effect of making the eligible even if there is
2906 if (stores_off_frame_dead_at_return
&& group
->frame_related
)
2908 bitmap_ior_into (group
->store2_n
, group
->store1_n
);
2909 bitmap_ior_into (group
->store2_p
, group
->store1_p
);
2911 fprintf (dump_file
, "group %d is frame related ", i
);
2914 group
->offset_map_size_n
++;
2915 group
->offset_map_n
= XNEWVEC (int, group
->offset_map_size_n
);
2916 group
->offset_map_size_p
++;
2917 group
->offset_map_p
= XNEWVEC (int, group
->offset_map_size_p
);
2918 group
->process_globally
= false;
2921 fprintf (dump_file
, "group %d(%d+%d): ", i
,
2922 (int)bitmap_count_bits (group
->store2_n
),
2923 (int)bitmap_count_bits (group
->store2_p
));
2924 bitmap_print (dump_file
, group
->store2_n
, "n ", " ");
2925 bitmap_print (dump_file
, group
->store2_p
, "p ", "\n");
2931 /* Init the offset tables for the normal case. */
2934 dse_step2_nospill (void)
2938 /* Position 0 is unused because 0 is used in the maps to mean
2940 current_position
= 1;
2941 FOR_EACH_VEC_ELT (group_info_t
, rtx_group_vec
, i
, group
)
2946 if (group
== clear_alias_group
)
2949 memset (group
->offset_map_n
, 0, sizeof(int) * group
->offset_map_size_n
);
2950 memset (group
->offset_map_p
, 0, sizeof(int) * group
->offset_map_size_p
);
2951 bitmap_clear (group
->group_kill
);
2953 EXECUTE_IF_SET_IN_BITMAP (group
->store2_n
, 0, j
, bi
)
2955 bitmap_set_bit (group
->group_kill
, current_position
);
2956 if (bitmap_bit_p (group
->escaped_n
, j
))
2957 bitmap_set_bit (kill_on_calls
, current_position
);
2958 group
->offset_map_n
[j
] = current_position
++;
2959 group
->process_globally
= true;
2961 EXECUTE_IF_SET_IN_BITMAP (group
->store2_p
, 0, j
, bi
)
2963 bitmap_set_bit (group
->group_kill
, current_position
);
2964 if (bitmap_bit_p (group
->escaped_p
, j
))
2965 bitmap_set_bit (kill_on_calls
, current_position
);
2966 group
->offset_map_p
[j
] = current_position
++;
2967 group
->process_globally
= true;
2970 return current_position
!= 1;
2974 /* Init the offset tables for the spill case. */
2977 dse_step2_spill (void)
2980 group_info_t group
= clear_alias_group
;
2983 /* Position 0 is unused because 0 is used in the maps to mean
2985 current_position
= 1;
2989 bitmap_print (dump_file
, clear_alias_sets
,
2990 "clear alias sets ", "\n");
2991 bitmap_print (dump_file
, disqualified_clear_alias_sets
,
2992 "disqualified clear alias sets ", "\n");
2995 memset (group
->offset_map_n
, 0, sizeof(int) * group
->offset_map_size_n
);
2996 memset (group
->offset_map_p
, 0, sizeof(int) * group
->offset_map_size_p
);
2997 bitmap_clear (group
->group_kill
);
2999 /* Remove the disqualified positions from the store2_p set. */
3000 bitmap_and_compl_into (group
->store2_p
, disqualified_clear_alias_sets
);
3002 /* We do not need to process the store2_n set because
3003 alias_sets are always positive. */
3004 EXECUTE_IF_SET_IN_BITMAP (group
->store2_p
, 0, j
, bi
)
3006 bitmap_set_bit (group
->group_kill
, current_position
);
3007 group
->offset_map_p
[j
] = current_position
++;
3008 group
->process_globally
= true;
3011 return current_position
!= 1;
3016 /*----------------------------------------------------------------------------
3019 Build the bit vectors for the transfer functions.
3020 ----------------------------------------------------------------------------*/
3023 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
3027 get_bitmap_index (group_info_t group_info
, HOST_WIDE_INT offset
)
3031 HOST_WIDE_INT offset_p
= -offset
;
3032 if (offset_p
>= group_info
->offset_map_size_n
)
3034 return group_info
->offset_map_n
[offset_p
];
3038 if (offset
>= group_info
->offset_map_size_p
)
3040 return group_info
->offset_map_p
[offset
];
3045 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3049 scan_stores_nospill (store_info_t store_info
, bitmap gen
, bitmap kill
)
3054 group_info_t group_info
3055 = VEC_index (group_info_t
, rtx_group_vec
, store_info
->group_id
);
3056 if (group_info
->process_globally
)
3057 for (i
= store_info
->begin
; i
< store_info
->end
; i
++)
3059 int index
= get_bitmap_index (group_info
, i
);
3062 bitmap_set_bit (gen
, index
);
3064 bitmap_clear_bit (kill
, index
);
3067 store_info
= store_info
->next
;
3072 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3076 scan_stores_spill (store_info_t store_info
, bitmap gen
, bitmap kill
)
3080 if (store_info
->alias_set
)
3082 int index
= get_bitmap_index (clear_alias_group
,
3083 store_info
->alias_set
);
3086 bitmap_set_bit (gen
, index
);
3088 bitmap_clear_bit (kill
, index
);
3091 store_info
= store_info
->next
;
3096 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3100 scan_reads_nospill (insn_info_t insn_info
, bitmap gen
, bitmap kill
)
3102 read_info_t read_info
= insn_info
->read_rec
;
3106 /* If this insn reads the frame, kill all the frame related stores. */
3107 if (insn_info
->frame_read
)
3109 FOR_EACH_VEC_ELT (group_info_t
, rtx_group_vec
, i
, group
)
3110 if (group
->process_globally
&& group
->frame_related
)
3113 bitmap_ior_into (kill
, group
->group_kill
);
3114 bitmap_and_compl_into (gen
, group
->group_kill
);
3117 if (insn_info
->non_frame_wild_read
)
3119 /* Kill all non-frame related stores. Kill all stores of variables that
3122 bitmap_ior_into (kill
, kill_on_calls
);
3123 bitmap_and_compl_into (gen
, kill_on_calls
);
3124 FOR_EACH_VEC_ELT (group_info_t
, rtx_group_vec
, i
, group
)
3125 if (group
->process_globally
&& !group
->frame_related
)
3128 bitmap_ior_into (kill
, group
->group_kill
);
3129 bitmap_and_compl_into (gen
, group
->group_kill
);
3134 FOR_EACH_VEC_ELT (group_info_t
, rtx_group_vec
, i
, group
)
3136 if (group
->process_globally
)
3138 if (i
== read_info
->group_id
)
3140 if (read_info
->begin
> read_info
->end
)
3142 /* Begin > end for block mode reads. */
3144 bitmap_ior_into (kill
, group
->group_kill
);
3145 bitmap_and_compl_into (gen
, group
->group_kill
);
3149 /* The groups are the same, just process the
3152 for (j
= read_info
->begin
; j
< read_info
->end
; j
++)
3154 int index
= get_bitmap_index (group
, j
);
3158 bitmap_set_bit (kill
, index
);
3159 bitmap_clear_bit (gen
, index
);
3166 /* The groups are different, if the alias sets
3167 conflict, clear the entire group. We only need
3168 to apply this test if the read_info is a cselib
3169 read. Anything with a constant base cannot alias
3170 something else with a different constant
3172 if ((read_info
->group_id
< 0)
3173 && canon_true_dependence (group
->base_mem
,
3174 GET_MODE (group
->base_mem
),
3175 group
->canon_base_addr
,
3176 read_info
->mem
, NULL_RTX
))
3179 bitmap_ior_into (kill
, group
->group_kill
);
3180 bitmap_and_compl_into (gen
, group
->group_kill
);
3186 read_info
= read_info
->next
;
3190 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3194 scan_reads_spill (read_info_t read_info
, bitmap gen
, bitmap kill
)
3198 if (read_info
->alias_set
)
3200 int index
= get_bitmap_index (clear_alias_group
,
3201 read_info
->alias_set
);
3205 bitmap_set_bit (kill
, index
);
3206 bitmap_clear_bit (gen
, index
);
3210 read_info
= read_info
->next
;
3215 /* Return the insn in BB_INFO before the first wild read or if there
3216 are no wild reads in the block, return the last insn. */
3219 find_insn_before_first_wild_read (bb_info_t bb_info
)
3221 insn_info_t insn_info
= bb_info
->last_insn
;
3222 insn_info_t last_wild_read
= NULL
;
3226 if (insn_info
->wild_read
)
3228 last_wild_read
= insn_info
->prev_insn
;
3229 /* Block starts with wild read. */
3230 if (!last_wild_read
)
3234 insn_info
= insn_info
->prev_insn
;
3238 return last_wild_read
;
3240 return bb_info
->last_insn
;
3244 /* Scan the insns in BB_INFO starting at PTR and going to the top of
3245 the block in order to build the gen and kill sets for the block.
3246 We start at ptr which may be the last insn in the block or may be
3247 the first insn with a wild read. In the latter case we are able to
3248 skip the rest of the block because it just does not matter:
3249 anything that happens is hidden by the wild read. */
3252 dse_step3_scan (bool for_spills
, basic_block bb
)
3254 bb_info_t bb_info
= bb_table
[bb
->index
];
3255 insn_info_t insn_info
;
3258 /* There are no wild reads in the spill case. */
3259 insn_info
= bb_info
->last_insn
;
3261 insn_info
= find_insn_before_first_wild_read (bb_info
);
3263 /* In the spill case or in the no_spill case if there is no wild
3264 read in the block, we will need a kill set. */
3265 if (insn_info
== bb_info
->last_insn
)
3268 bitmap_clear (bb_info
->kill
);
3270 bb_info
->kill
= BITMAP_ALLOC (NULL
);
3274 BITMAP_FREE (bb_info
->kill
);
3278 /* There may have been code deleted by the dce pass run before
3280 if (insn_info
->insn
&& INSN_P (insn_info
->insn
))
3282 /* Process the read(s) last. */
3285 scan_stores_spill (insn_info
->store_rec
, bb_info
->gen
, bb_info
->kill
);
3286 scan_reads_spill (insn_info
->read_rec
, bb_info
->gen
, bb_info
->kill
);
3290 scan_stores_nospill (insn_info
->store_rec
, bb_info
->gen
, bb_info
->kill
);
3291 scan_reads_nospill (insn_info
, bb_info
->gen
, bb_info
->kill
);
3295 insn_info
= insn_info
->prev_insn
;
3300 /* Set the gen set of the exit block, and also any block with no
3301 successors that does not have a wild read. */
3304 dse_step3_exit_block_scan (bb_info_t bb_info
)
3306 /* The gen set is all 0's for the exit block except for the
3307 frame_pointer_group. */
3309 if (stores_off_frame_dead_at_return
)
3314 FOR_EACH_VEC_ELT (group_info_t
, rtx_group_vec
, i
, group
)
3316 if (group
->process_globally
&& group
->frame_related
)
3317 bitmap_ior_into (bb_info
->gen
, group
->group_kill
);
3323 /* Find all of the blocks that are not backwards reachable from the
3324 exit block or any block with no successors (BB). These are the
3325 infinite loops or infinite self loops. These blocks will still
3326 have their bits set in UNREACHABLE_BLOCKS. */
3329 mark_reachable_blocks (sbitmap unreachable_blocks
, basic_block bb
)
3334 if (TEST_BIT (unreachable_blocks
, bb
->index
))
3336 RESET_BIT (unreachable_blocks
, bb
->index
);
3337 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3339 mark_reachable_blocks (unreachable_blocks
, e
->src
);
3344 /* Build the transfer functions for the function. */
3347 dse_step3 (bool for_spills
)
3350 sbitmap unreachable_blocks
= sbitmap_alloc (last_basic_block
);
3351 sbitmap_iterator sbi
;
3352 bitmap all_ones
= NULL
;
3355 sbitmap_ones (unreachable_blocks
);
3359 bb_info_t bb_info
= bb_table
[bb
->index
];
3361 bitmap_clear (bb_info
->gen
);
3363 bb_info
->gen
= BITMAP_ALLOC (NULL
);
3365 if (bb
->index
== ENTRY_BLOCK
)
3367 else if (bb
->index
== EXIT_BLOCK
)
3368 dse_step3_exit_block_scan (bb_info
);
3370 dse_step3_scan (for_spills
, bb
);
3371 if (EDGE_COUNT (bb
->succs
) == 0)
3372 mark_reachable_blocks (unreachable_blocks
, bb
);
3374 /* If this is the second time dataflow is run, delete the old
3377 BITMAP_FREE (bb_info
->in
);
3379 BITMAP_FREE (bb_info
->out
);
3382 /* For any block in an infinite loop, we must initialize the out set
3383 to all ones. This could be expensive, but almost never occurs in
3384 practice. However, it is common in regression tests. */
3385 EXECUTE_IF_SET_IN_SBITMAP (unreachable_blocks
, 0, i
, sbi
)
3387 if (bitmap_bit_p (all_blocks
, i
))
3389 bb_info_t bb_info
= bb_table
[i
];
3395 all_ones
= BITMAP_ALLOC (NULL
);
3396 FOR_EACH_VEC_ELT (group_info_t
, rtx_group_vec
, j
, group
)
3397 bitmap_ior_into (all_ones
, group
->group_kill
);
3401 bb_info
->out
= BITMAP_ALLOC (NULL
);
3402 bitmap_copy (bb_info
->out
, all_ones
);
3408 BITMAP_FREE (all_ones
);
3409 sbitmap_free (unreachable_blocks
);
3414 /*----------------------------------------------------------------------------
3417 Solve the bitvector equations.
3418 ----------------------------------------------------------------------------*/
3421 /* Confluence function for blocks with no successors. Create an out
3422 set from the gen set of the exit block. This block logically has
3423 the exit block as a successor. */
3428 dse_confluence_0 (basic_block bb
)
3430 bb_info_t bb_info
= bb_table
[bb
->index
];
3432 if (bb
->index
== EXIT_BLOCK
)
3437 bb_info
->out
= BITMAP_ALLOC (NULL
);
3438 bitmap_copy (bb_info
->out
, bb_table
[EXIT_BLOCK
]->gen
);
3442 /* Propagate the information from the in set of the dest of E to the
3443 out set of the src of E. If the various in or out sets are not
3444 there, that means they are all ones. */
3447 dse_confluence_n (edge e
)
3449 bb_info_t src_info
= bb_table
[e
->src
->index
];
3450 bb_info_t dest_info
= bb_table
[e
->dest
->index
];
3455 bitmap_and_into (src_info
->out
, dest_info
->in
);
3458 src_info
->out
= BITMAP_ALLOC (NULL
);
3459 bitmap_copy (src_info
->out
, dest_info
->in
);
3466 /* Propagate the info from the out to the in set of BB_INDEX's basic
3467 block. There are three cases:
3469 1) The block has no kill set. In this case the kill set is all
3470 ones. It does not matter what the out set of the block is, none of
3471 the info can reach the top. The only thing that reaches the top is
3472 the gen set and we just copy the set.
3474 2) There is a kill set but no out set and bb has successors. In
3475 this case we just return. Eventually an out set will be created and
3476 it is better to wait than to create a set of ones.
3478 3) There is both a kill and out set. We apply the obvious transfer
3483 dse_transfer_function (int bb_index
)
3485 bb_info_t bb_info
= bb_table
[bb_index
];
3493 return bitmap_ior_and_compl (bb_info
->in
, bb_info
->gen
,
3494 bb_info
->out
, bb_info
->kill
);
3497 bb_info
->in
= BITMAP_ALLOC (NULL
);
3498 bitmap_ior_and_compl (bb_info
->in
, bb_info
->gen
,
3499 bb_info
->out
, bb_info
->kill
);
3509 /* Case 1 above. If there is already an in set, nothing
3515 bb_info
->in
= BITMAP_ALLOC (NULL
);
3516 bitmap_copy (bb_info
->in
, bb_info
->gen
);
3522 /* Solve the dataflow equations. */
3527 df_simple_dataflow (DF_BACKWARD
, NULL
, dse_confluence_0
,
3528 dse_confluence_n
, dse_transfer_function
,
3529 all_blocks
, df_get_postorder (DF_BACKWARD
),
3530 df_get_n_blocks (DF_BACKWARD
));
3535 fprintf (dump_file
, "\n\n*** Global dataflow info after analysis.\n");
3538 bb_info_t bb_info
= bb_table
[bb
->index
];
3540 df_print_bb_index (bb
, dump_file
);
3542 bitmap_print (dump_file
, bb_info
->in
, " in: ", "\n");
3544 fprintf (dump_file
, " in: *MISSING*\n");
3546 bitmap_print (dump_file
, bb_info
->gen
, " gen: ", "\n");
3548 fprintf (dump_file
, " gen: *MISSING*\n");
3550 bitmap_print (dump_file
, bb_info
->kill
, " kill: ", "\n");
3552 fprintf (dump_file
, " kill: *MISSING*\n");
3554 bitmap_print (dump_file
, bb_info
->out
, " out: ", "\n");
3556 fprintf (dump_file
, " out: *MISSING*\n\n");
3563 /*----------------------------------------------------------------------------
3566 Delete the stores that can only be deleted using the global information.
3567 ----------------------------------------------------------------------------*/
3571 dse_step5_nospill (void)
3576 bb_info_t bb_info
= bb_table
[bb
->index
];
3577 insn_info_t insn_info
= bb_info
->last_insn
;
3578 bitmap v
= bb_info
->out
;
3582 bool deleted
= false;
3583 if (dump_file
&& insn_info
->insn
)
3585 fprintf (dump_file
, "starting to process insn %d\n",
3586 INSN_UID (insn_info
->insn
));
3587 bitmap_print (dump_file
, v
, " v: ", "\n");
3590 /* There may have been code deleted by the dce pass run before
3593 && INSN_P (insn_info
->insn
)
3594 && (!insn_info
->cannot_delete
)
3595 && (!bitmap_empty_p (v
)))
3597 store_info_t store_info
= insn_info
->store_rec
;
3599 /* Try to delete the current insn. */
3602 /* Skip the clobbers. */
3603 while (!store_info
->is_set
)
3604 store_info
= store_info
->next
;
3606 if (store_info
->alias_set
)
3611 group_info_t group_info
3612 = VEC_index (group_info_t
, rtx_group_vec
, store_info
->group_id
);
3614 for (i
= store_info
->begin
; i
< store_info
->end
; i
++)
3616 int index
= get_bitmap_index (group_info
, i
);
3619 fprintf (dump_file
, "i = %d, index = %d\n", (int)i
, index
);
3620 if (index
== 0 || !bitmap_bit_p (v
, index
))
3623 fprintf (dump_file
, "failing at i = %d\n", (int)i
);
3632 && check_for_inc_dec_1 (insn_info
))
3634 delete_insn (insn_info
->insn
);
3635 insn_info
->insn
= NULL
;
3640 /* We do want to process the local info if the insn was
3641 deleted. For instance, if the insn did a wild read, we
3642 no longer need to trash the info. */
3644 && INSN_P (insn_info
->insn
)
3647 scan_stores_nospill (insn_info
->store_rec
, v
, NULL
);
3648 if (insn_info
->wild_read
)
3651 fprintf (dump_file
, "wild read\n");
3654 else if (insn_info
->read_rec
3655 || insn_info
->non_frame_wild_read
)
3657 if (dump_file
&& !insn_info
->non_frame_wild_read
)
3658 fprintf (dump_file
, "regular read\n");
3660 fprintf (dump_file
, "non-frame wild read\n");
3661 scan_reads_nospill (insn_info
, v
, NULL
);
3665 insn_info
= insn_info
->prev_insn
;
3672 dse_step5_spill (void)
3677 bb_info_t bb_info
= bb_table
[bb
->index
];
3678 insn_info_t insn_info
= bb_info
->last_insn
;
3679 bitmap v
= bb_info
->out
;
3683 bool deleted
= false;
3684 /* There may have been code deleted by the dce pass run before
3687 && INSN_P (insn_info
->insn
)
3688 && (!insn_info
->cannot_delete
)
3689 && (!bitmap_empty_p (v
)))
3691 /* Try to delete the current insn. */
3692 store_info_t store_info
= insn_info
->store_rec
;
3697 if (store_info
->alias_set
)
3699 int index
= get_bitmap_index (clear_alias_group
,
3700 store_info
->alias_set
);
3701 if (index
== 0 || !bitmap_bit_p (v
, index
))
3709 store_info
= store_info
->next
;
3711 if (deleted
&& dbg_cnt (dse
)
3712 && check_for_inc_dec_1 (insn_info
))
3715 fprintf (dump_file
, "Spill deleting insn %d\n",
3716 INSN_UID (insn_info
->insn
));
3717 delete_insn (insn_info
->insn
);
3719 insn_info
->insn
= NULL
;
3724 && INSN_P (insn_info
->insn
)
3727 scan_stores_spill (insn_info
->store_rec
, v
, NULL
);
3728 scan_reads_spill (insn_info
->read_rec
, v
, NULL
);
3731 insn_info
= insn_info
->prev_insn
;
3738 /*----------------------------------------------------------------------------
3741 Delete stores made redundant by earlier stores (which store the same
3742 value) that couldn't be eliminated.
3743 ----------------------------------------------------------------------------*/
3752 bb_info_t bb_info
= bb_table
[bb
->index
];
3753 insn_info_t insn_info
= bb_info
->last_insn
;
3757 /* There may have been code deleted by the dce pass run before
3760 && INSN_P (insn_info
->insn
)
3761 && !insn_info
->cannot_delete
)
3763 store_info_t s_info
= insn_info
->store_rec
;
3765 while (s_info
&& !s_info
->is_set
)
3766 s_info
= s_info
->next
;
3768 && s_info
->redundant_reason
3769 && s_info
->redundant_reason
->insn
3770 && INSN_P (s_info
->redundant_reason
->insn
))
3772 rtx rinsn
= s_info
->redundant_reason
->insn
;
3774 fprintf (dump_file
, "Locally deleting insn %d "
3775 "because insn %d stores the "
3776 "same value and couldn't be "
3778 INSN_UID (insn_info
->insn
),
3780 delete_dead_store_insn (insn_info
);
3783 insn_info
= insn_info
->prev_insn
;
3788 /*----------------------------------------------------------------------------
3791 Destroy everything left standing.
3792 ----------------------------------------------------------------------------*/
3795 dse_step7 (bool global_done
)
3801 FOR_EACH_VEC_ELT (group_info_t
, rtx_group_vec
, i
, group
)
3803 free (group
->offset_map_n
);
3804 free (group
->offset_map_p
);
3805 BITMAP_FREE (group
->store1_n
);
3806 BITMAP_FREE (group
->store1_p
);
3807 BITMAP_FREE (group
->store2_n
);
3808 BITMAP_FREE (group
->store2_p
);
3809 BITMAP_FREE (group
->escaped_n
);
3810 BITMAP_FREE (group
->escaped_p
);
3811 BITMAP_FREE (group
->group_kill
);
3817 bb_info_t bb_info
= bb_table
[bb
->index
];
3818 BITMAP_FREE (bb_info
->gen
);
3820 BITMAP_FREE (bb_info
->kill
);
3822 BITMAP_FREE (bb_info
->in
);
3824 BITMAP_FREE (bb_info
->out
);
3827 if (clear_alias_sets
)
3829 BITMAP_FREE (clear_alias_sets
);
3830 BITMAP_FREE (disqualified_clear_alias_sets
);
3831 free_alloc_pool (clear_alias_mode_pool
);
3832 htab_delete (clear_alias_mode_table
);
3835 end_alias_analysis ();
3837 htab_delete (rtx_group_table
);
3838 VEC_free (group_info_t
, heap
, rtx_group_vec
);
3839 BITMAP_FREE (all_blocks
);
3840 BITMAP_FREE (scratch
);
3841 BITMAP_FREE (kill_on_calls
);
3843 free_alloc_pool (rtx_store_info_pool
);
3844 free_alloc_pool (read_info_pool
);
3845 free_alloc_pool (insn_info_pool
);
3846 free_alloc_pool (bb_info_pool
);
3847 free_alloc_pool (rtx_group_info_pool
);
3848 free_alloc_pool (deferred_change_pool
);
3852 /* -------------------------------------------------------------------------
3854 ------------------------------------------------------------------------- */
3856 /* Callback for running pass_rtl_dse. */
3859 rest_of_handle_dse (void)
3861 bool did_global
= false;
3863 df_set_flags (DF_DEFER_INSN_RESCAN
);
3865 /* Need the notes since we must track live hardregs in the forwards
3867 df_note_add_problem ();
3873 if (dse_step2_nospill ())
3875 df_set_flags (DF_LR_RUN_DCE
);
3879 fprintf (dump_file
, "doing global processing\n");
3882 dse_step5_nospill ();
3885 /* For the instance of dse that runs after reload, we make a special
3886 pass to process the spills. These are special in that they are
3887 totally transparent, i.e, there is no aliasing issues that need
3888 to be considered. This means that the wild reads that kill
3889 everything else do not apply here. */
3890 if (clear_alias_sets
&& dse_step2_spill ())
3894 df_set_flags (DF_LR_RUN_DCE
);
3899 fprintf (dump_file
, "doing global spill processing\n");
3906 dse_step7 (did_global
);
3909 fprintf (dump_file
, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3910 locally_deleted
, globally_deleted
, spill_deleted
);
3917 return optimize
> 0 && flag_dse
3924 return optimize
> 0 && flag_dse
3928 struct rtl_opt_pass pass_rtl_dse1
=
3933 gate_dse1
, /* gate */
3934 rest_of_handle_dse
, /* execute */
3937 0, /* static_pass_number */
3938 TV_DSE1
, /* tv_id */
3939 0, /* properties_required */
3940 0, /* properties_provided */
3941 0, /* properties_destroyed */
3942 0, /* todo_flags_start */
3943 TODO_df_finish
| TODO_verify_rtl_sharing
|
3944 TODO_ggc_collect
/* todo_flags_finish */
3948 struct rtl_opt_pass pass_rtl_dse2
=
3953 gate_dse2
, /* gate */
3954 rest_of_handle_dse
, /* execute */
3957 0, /* static_pass_number */
3958 TV_DSE2
, /* tv_id */
3959 0, /* properties_required */
3960 0, /* properties_provided */
3961 0, /* properties_destroyed */
3962 0, /* todo_flags_start */
3963 TODO_df_finish
| TODO_verify_rtl_sharing
|
3964 TODO_ggc_collect
/* todo_flags_finish */