1 /* RTL dead store elimination.
2 Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
4 Contributed by Richard Sandiford <rsandifor@codesourcery.com>
5 and Kenneth Zadeck <zadeck@naturalbridge.com>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
27 #include "coretypes.h"
34 #include "hard-reg-set.h"
39 #include "tree-pass.h"
40 #include "alloc-pool.h"
42 #include "insn-config.h"
49 /* This file contains three techniques for performing Dead Store
52 * The first technique performs dse locally on any base address. It
53 is based on the cselib which is a local value numbering technique.
54 This technique is local to a basic block but deals with a fairly
57 * The second technique performs dse globally but is restricted to
58 base addresses that are either constant or are relative to the
61 * The third technique, (which is only done after register allocation)
62 processes the spill spill slots. This differs from the second
63 technique because it takes advantage of the fact that spilling is
64 completely free from the effects of aliasing.
66 Logically, dse is a backwards dataflow problem. A store can be
67 deleted if it if cannot be reached in the backward direction by any
68 use of the value being stored. However, the local technique uses a
69 forwards scan of the basic block because cselib requires that the
70 block be processed in that order.
72 The pass is logically broken into 7 steps:
76 1) The local algorithm, as well as scanning the insns for the two
79 2) Analysis to see if the global algs are necessary. In the case
80 of stores base on a constant address, there must be at least two
81 stores to that address, to make it possible to delete some of the
82 stores. In the case of stores off of the frame or spill related
83 stores, only one store to an address is necessary because those
84 stores die at the end of the function.
86 3) Set up the global dataflow equations based on processing the
87 info parsed in the first step.
89 4) Solve the dataflow equations.
91 5) Delete the insns that the global analysis has indicated are
96 This step uses cselib and canon_rtx to build the largest expression
97 possible for each address. This pass is a forwards pass through
98 each basic block. From the point of view of the global technique,
99 the first pass could examine a block in either direction. The
100 forwards ordering is to accommodate cselib.
102 We a simplifying assumption: addresses fall into four broad
105 1) base has rtx_varies_p == false, offset is constant.
106 2) base has rtx_varies_p == false, offset variable.
107 3) base has rtx_varies_p == true, offset constant.
108 4) base has rtx_varies_p == true, offset variable.
110 The local passes are able to process all 4 kinds of addresses. The
111 global pass only handles (1).
113 The global problem is formulated as follows:
115 A store, S1, to address A, where A is not relative to the stack
116 frame, can be eliminated if all paths from S1 to the end of the
117 of the function contain another store to A before a read to A.
119 If the address A is relative to the stack frame, a store S2 to A
120 can be eliminated if there are no paths from S1 that reach the
121 end of the function that read A before another store to A. In
122 this case S2 can be deleted if there are paths to from S2 to the
123 end of the function that have no reads or writes to A. This
124 second case allows stores to the stack frame to be deleted that
125 would otherwise die when the function returns. This cannot be
126 done if stores_off_frame_dead_at_return is not true. See the doc
127 for that variable for when this variable is false.
129 The global problem is formulated as a backwards set union
130 dataflow problem where the stores are the gens and reads are the
131 kills. Set union problems are rare and require some special
132 handling given our representation of bitmaps. A straightforward
133 implementation of requires a lot of bitmaps filled with 1s.
134 These are expensive and cumbersome in our bitmap formulation so
135 care has been taken to avoid large vectors filled with 1s. See
136 the comments in bb_info and in the dataflow confluence functions
139 There are two places for further enhancements to this algorithm:
141 1) The original dse which was embedded in a pass called flow also
142 did local address forwarding. For example in
147 flow would replace the right hand side of the second insn with a
148 reference to r100. Most of the information is available to add this
149 to this pass. It has not done it because it is a lot of work in
150 the case that either r100 is assigned to between the first and
151 second insn and/or the second insn is a load of part of the value
152 stored by the first insn.
154 insn 5 in gcc.c-torture/compile/990203-1.c simple case.
155 insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
156 insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
157 insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
159 2) The cleaning up of spill code is quite profitable. It currently
160 depends on reading tea leaves and chicken entrails left by reload.
161 This pass depends on reload creating a singleton alias set for each
162 spill slot and telling the next dse pass which of these alias sets
163 are the singletons. Rather than analyze the addresses of the
164 spills, dse's spill processing just does analysis of the loads and
165 stores that use those alias sets. There are three cases where this
168 a) Reload sometimes creates the slot for one mode of access, and
169 then inserts loads and/or stores for a smaller mode. In this
170 case, the current code just punts on the slot. The proper thing
171 to do is to back out and use one bit vector position for each
172 byte of the entity associated with the slot. This depends on
173 KNOWING that reload always generates the accesses for each of the
174 bytes in some canonical (read that easy to understand several
175 passes after reload happens) way.
177 b) Reload sometimes decides that spill slot it allocated was not
178 large enough for the mode and goes back and allocates more slots
179 with the same mode and alias set. The backout in this case is a
180 little more graceful than (a). In this case the slot is unmarked
181 as being a spill slot and if final address comes out to be based
182 off the frame pointer, the global algorithm handles this slot.
184 c) For any pass that may prespill, there is currently no
185 mechanism to tell the dse pass that the slot being used has the
186 special properties that reload uses. It may be that all that is
187 required is to have those passes make the same calls that reload
188 does, assuming that the alias sets can be manipulated in the same
191 /* There are limits to the size of constant offsets we model for the
192 global problem. There are certainly test cases, that exceed this
193 limit, however, it is unlikely that there are important programs
194 that really have constant offsets this size. */
195 #define MAX_OFFSET (64 * 1024)
198 static bitmap scratch
= NULL
;
201 /* This structure holds information about a candidate store. */
205 /* False means this is a clobber. */
208 /* The id of the mem group of the base address. If rtx_varies_p is
209 true, this is -1. Otherwise, it is the index into the group
213 /* This is the cselib value. */
214 cselib_val
*cse_base
;
216 /* This canonized mem. */
219 /* The result of get_addr on mem. */
222 /* If this is non-zero, it is the alias set of a spill location. */
223 alias_set_type alias_set
;
225 /* The offset of the first and byte before the last byte associated
226 with the operation. */
229 /* An bitmask as wide as the number of bytes in the word that
230 contains a 1 if the byte may be needed. The store is unused if
231 all of the bits are 0. */
232 unsigned HOST_WIDE_INT positions_needed
;
234 /* The next store info for this insn. */
235 struct store_info
*next
;
237 /* The right hand side of the store. This is used if there is a
238 subsequent reload of the mems address somewhere later in the
243 /* Return a bitmask with the first N low bits set. */
245 static unsigned HOST_WIDE_INT
246 lowpart_bitmask (int n
)
248 unsigned HOST_WIDE_INT mask
= ~(unsigned HOST_WIDE_INT
) 0;
249 return mask
>> (HOST_BITS_PER_WIDE_INT
- n
);
252 typedef struct store_info
*store_info_t
;
253 static alloc_pool cse_store_info_pool
;
254 static alloc_pool rtx_store_info_pool
;
256 /* This structure holds information about a load. These are only
257 built for rtx bases. */
260 /* The id of the mem group of the base address. */
263 /* If this is non-zero, it is the alias set of a spill location. */
264 alias_set_type alias_set
;
266 /* The offset of the first and byte after the last byte associated
267 with the operation. If begin == end == 0, the read did not have
268 a constant offset. */
271 /* The mem being read. */
274 /* The next read_info for this insn. */
275 struct read_info
*next
;
277 typedef struct read_info
*read_info_t
;
278 static alloc_pool read_info_pool
;
281 /* One of these records is created for each insn. */
285 /* Set true if the insn contains a store but the insn itself cannot
286 be deleted. This is set if the insn is a parallel and there is
287 more than one non dead output or if the insn is in some way
291 /* This field is only used by the global algorithm. It is set true
292 if the insn contains any read of mem except for a (1). This is
293 also set if the insn is a call or has a clobber mem. If the insn
294 contains a wild read, the use_rec will be null. */
297 /* This field is only used for the processing of const functions.
298 These functions cannot read memory, but they can read the stack
299 because that is where they may get their parms. We need to be
300 this conservative because, like the store motion pass, we don't
301 consider CALL_INSN_FUNCTION_USAGE when processing call insns.
302 Moreover, we need to distinguish two cases:
303 1. Before reload (register elimination), the stores related to
304 outgoing arguments are stack pointer based and thus deemed
305 of non-constant base in this pass. This requires special
306 handling but also means that the frame pointer based stores
307 need not be killed upon encountering a const function call.
308 2. After reload, the stores related to outgoing arguments can be
309 either stack pointer or hard frame pointer based. This means
310 that we have no other choice than also killing all the frame
311 pointer based stores upon encountering a const function call.
312 This field is set after reload for const function calls. Having
313 this set is less severe than a wild read, it just means that all
314 the frame related stores are killed rather than all the stores. */
317 /* This field is only used for the processing of const functions.
318 It is set if the insn may contain a stack pointer based store. */
319 bool stack_pointer_based
;
321 /* This is true if any of the sets within the store contains a
322 cselib base. Such stores can only be deleted by the local
324 bool contains_cselib_groups
;
329 /* The list of mem sets or mem clobbers that are contained in this
330 insn. If the insn is deletable, it contains only one mem set.
331 But it could also contain clobbers. Insns that contain more than
332 one mem set are not deletable, but each of those mems are here in
333 order to provide info to delete other insns. */
334 store_info_t store_rec
;
336 /* The linked list of mem uses in this insn. Only the reads from
337 rtx bases are listed here. The reads to cselib bases are
338 completely processed during the first scan and so are never
340 read_info_t read_rec
;
342 /* The prev insn in the basic block. */
343 struct insn_info
* prev_insn
;
345 /* The linked list of insns that are in consideration for removal in
346 the forwards pass thru the basic block. This pointer may be
347 trash as it is not cleared when a wild read occurs. The only
348 time it is guaranteed to be correct is when the traveral starts
349 at active_local_stores. */
350 struct insn_info
* next_local_store
;
353 typedef struct insn_info
*insn_info_t
;
354 static alloc_pool insn_info_pool
;
356 /* The linked list of stores that are under consideration in this
358 static insn_info_t active_local_stores
;
363 /* Pointer to the insn info for the last insn in the block. These
364 are linked so this is how all of the insns are reached. During
365 scanning this is the current insn being scanned. */
366 insn_info_t last_insn
;
368 /* The info for the global dataflow problem. */
371 /* This is set if the transfer function should and in the wild_read
372 bitmap before applying the kill and gen sets. That vector knocks
373 out most of the bits in the bitmap and thus speeds up the
375 bool apply_wild_read
;
377 /* The set of store positions that exist in this block before a wild read. */
380 /* The set of load positions that exist in this block above the
381 same position of a store. */
384 /* The set of stores that reach the top of the block without being
387 Do not represent the in if it is all ones. Note that this is
388 what the bitvector should logically be initialized to for a set
389 intersection problem. However, like the kill set, this is too
390 expensive. So initially, the in set will only be created for the
391 exit block and any block that contains a wild read. */
394 /* The set of stores that reach the bottom of the block from it's
397 Do not represent the in if it is all ones. Note that this is
398 what the bitvector should logically be initialized to for a set
399 intersection problem. However, like the kill and in set, this is
400 too expensive. So what is done is that the confluence operator
401 just initializes the vector from one of the out sets of the
402 successors of the block. */
406 typedef struct bb_info
*bb_info_t
;
407 static alloc_pool bb_info_pool
;
409 /* Table to hold all bb_infos. */
410 static bb_info_t
*bb_table
;
412 /* There is a group_info for each rtx base that is used to reference
413 memory. There are also not many of the rtx bases because they are
414 very limited in scope. */
418 /* The actual base of the address. */
421 /* The sequential id of the base. This allows us to have a
422 canonical ordering of these that is not based on addresses. */
425 /* A mem wrapped around the base pointer for the group in order to
426 do read dependency. */
429 /* Canonized version of base_mem, most likely the same thing. */
432 /* These two sets of two bitmaps are used to keep track of how many
433 stores are actually referencing that position from this base. We
434 only do this for rtx bases as this will be used to assign
435 positions in the bitmaps for the global problem. Bit N is set in
436 store1 on the first store for offset N. Bit N is set in store2
437 for the second store to offset N. This is all we need since we
438 only care about offsets that have two or more stores for them.
440 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
441 for 0 and greater offsets.
443 There is one special case here, for stores into the stack frame,
444 we will or store1 into store2 before deciding which stores look
445 at globally. This is because stores to the stack frame that have
446 no other reads before the end of the function can also be
448 bitmap store1_n
, store1_p
, store2_n
, store2_p
;
450 /* The positions in this bitmap have the same assignments as the in,
451 out, gen and kill bitmaps. This bitmap is all zeros except for
452 the positions that are occupied by stores for this group. */
455 /* True if there are any positions that are to be processed
457 bool process_globally
;
459 /* True if the base of this group is either the frame_pointer or
460 hard_frame_pointer. */
463 /* The offset_map is used to map the offsets from this base into
464 positions in the global bitmaps. It is only created after all of
465 the all of stores have been scanned and we know which ones we
467 int *offset_map_n
, *offset_map_p
;
468 int offset_map_size_n
, offset_map_size_p
;
470 typedef struct group_info
*group_info_t
;
471 typedef const struct group_info
*const_group_info_t
;
472 static alloc_pool rtx_group_info_pool
;
474 /* Tables of group_info structures, hashed by base value. */
475 static htab_t rtx_group_table
;
477 /* Index into the rtx_group_vec. */
478 static int rtx_group_next_id
;
480 DEF_VEC_P(group_info_t
);
481 DEF_VEC_ALLOC_P(group_info_t
,heap
);
483 static VEC(group_info_t
,heap
) *rtx_group_vec
;
486 /* This structure holds the set of changes that are being deferred
487 when removing read operation. See replace_read. */
488 struct deferred_change
491 /* The mem that is being replaced. */
494 /* The reg it is being replaced with. */
497 struct deferred_change
*next
;
500 typedef struct deferred_change
*deferred_change_t
;
501 static alloc_pool deferred_change_pool
;
503 static deferred_change_t deferred_change_list
= NULL
;
505 /* This are used to hold the alias sets of spill variables. Since
506 these are never aliased and there may be a lot of them, it makes
507 sense to treat them specially. This bitvector is only allocated in
508 calls from dse_record_singleton_alias_set which currently is only
509 made during reload1. So when dse is called before reload this
510 mechanism does nothing. */
512 static bitmap clear_alias_sets
= NULL
;
514 /* The set of clear_alias_sets that have been disqualified because
515 there are loads or stores using a different mode than the alias set
516 was registered with. */
517 static bitmap disqualified_clear_alias_sets
= NULL
;
519 /* The group that holds all of the clear_alias_sets. */
520 static group_info_t clear_alias_group
;
522 /* The modes of the clear_alias_sets. */
523 static htab_t clear_alias_mode_table
;
525 /* Hash table element to look up the mode for an alias set. */
526 struct clear_alias_mode_holder
528 alias_set_type alias_set
;
529 enum machine_mode mode
;
532 static alloc_pool clear_alias_mode_pool
;
534 /* This is true except if cfun->stdarg -- i.e. we cannot do
535 this for vararg functions because they play games with the frame. */
536 static bool stores_off_frame_dead_at_return
;
538 /* Counter for stats. */
539 static int globally_deleted
;
540 static int locally_deleted
;
541 static int spill_deleted
;
543 static bitmap all_blocks
;
545 /* The number of bits used in the global bitmaps. */
546 static unsigned int current_position
;
549 static bool gate_dse (void);
550 static bool gate_dse1 (void);
551 static bool gate_dse2 (void);
554 /*----------------------------------------------------------------------------
558 ----------------------------------------------------------------------------*/
560 /* Hashtable callbacks for maintaining the "bases" field of
561 store_group_info, given that the addresses are function invariants. */
564 clear_alias_mode_eq (const void *p1
, const void *p2
)
566 const struct clear_alias_mode_holder
* h1
567 = (const struct clear_alias_mode_holder
*) p1
;
568 const struct clear_alias_mode_holder
* h2
569 = (const struct clear_alias_mode_holder
*) p2
;
570 return h1
->alias_set
== h2
->alias_set
;
575 clear_alias_mode_hash (const void *p
)
577 const struct clear_alias_mode_holder
*holder
578 = (const struct clear_alias_mode_holder
*) p
;
579 return holder
->alias_set
;
583 /* Find the entry associated with ALIAS_SET. */
585 static struct clear_alias_mode_holder
*
586 clear_alias_set_lookup (alias_set_type alias_set
)
588 struct clear_alias_mode_holder tmp_holder
;
591 tmp_holder
.alias_set
= alias_set
;
592 slot
= htab_find_slot (clear_alias_mode_table
, &tmp_holder
, NO_INSERT
);
599 /* Hashtable callbacks for maintaining the "bases" field of
600 store_group_info, given that the addresses are function invariants. */
603 invariant_group_base_eq (const void *p1
, const void *p2
)
605 const_group_info_t gi1
= (const_group_info_t
) p1
;
606 const_group_info_t gi2
= (const_group_info_t
) p2
;
607 return rtx_equal_p (gi1
->rtx_base
, gi2
->rtx_base
);
612 invariant_group_base_hash (const void *p
)
614 const_group_info_t gi
= (const_group_info_t
) p
;
616 return hash_rtx (gi
->rtx_base
, Pmode
, &do_not_record
, NULL
, false);
620 /* Get the GROUP for BASE. Add a new group if it is not there. */
623 get_group_info (rtx base
)
625 struct group_info tmp_gi
;
631 /* Find the store_base_info structure for BASE, creating a new one
633 tmp_gi
.rtx_base
= base
;
634 slot
= htab_find_slot (rtx_group_table
, &tmp_gi
, INSERT
);
635 gi
= (group_info_t
) *slot
;
639 if (!clear_alias_group
)
641 clear_alias_group
= gi
= pool_alloc (rtx_group_info_pool
);
642 memset (gi
, 0, sizeof (struct group_info
));
643 gi
->id
= rtx_group_next_id
++;
644 gi
->store1_n
= BITMAP_ALLOC (NULL
);
645 gi
->store1_p
= BITMAP_ALLOC (NULL
);
646 gi
->store2_n
= BITMAP_ALLOC (NULL
);
647 gi
->store2_p
= BITMAP_ALLOC (NULL
);
648 gi
->group_kill
= BITMAP_ALLOC (NULL
);
649 gi
->process_globally
= false;
650 gi
->offset_map_size_n
= 0;
651 gi
->offset_map_size_p
= 0;
652 gi
->offset_map_n
= NULL
;
653 gi
->offset_map_p
= NULL
;
654 VEC_safe_push (group_info_t
, heap
, rtx_group_vec
, gi
);
656 return clear_alias_group
;
661 *slot
= gi
= pool_alloc (rtx_group_info_pool
);
663 gi
->id
= rtx_group_next_id
++;
664 gi
->base_mem
= gen_rtx_MEM (QImode
, base
);
665 gi
->canon_base_mem
= canon_rtx (gi
->base_mem
);
666 gi
->store1_n
= BITMAP_ALLOC (NULL
);
667 gi
->store1_p
= BITMAP_ALLOC (NULL
);
668 gi
->store2_n
= BITMAP_ALLOC (NULL
);
669 gi
->store2_p
= BITMAP_ALLOC (NULL
);
670 gi
->group_kill
= BITMAP_ALLOC (NULL
);
671 gi
->process_globally
= false;
673 (base
== frame_pointer_rtx
) || (base
== hard_frame_pointer_rtx
);
674 gi
->offset_map_size_n
= 0;
675 gi
->offset_map_size_p
= 0;
676 gi
->offset_map_n
= NULL
;
677 gi
->offset_map_p
= NULL
;
678 VEC_safe_push (group_info_t
, heap
, rtx_group_vec
, gi
);
685 /* Initialization of data structures. */
691 globally_deleted
= 0;
694 scratch
= BITMAP_ALLOC (NULL
);
697 = create_alloc_pool ("rtx_store_info_pool",
698 sizeof (struct store_info
), 100);
700 = create_alloc_pool ("read_info_pool",
701 sizeof (struct read_info
), 100);
703 = create_alloc_pool ("insn_info_pool",
704 sizeof (struct insn_info
), 100);
706 = create_alloc_pool ("bb_info_pool",
707 sizeof (struct bb_info
), 100);
709 = create_alloc_pool ("rtx_group_info_pool",
710 sizeof (struct group_info
), 100);
712 = create_alloc_pool ("deferred_change_pool",
713 sizeof (struct deferred_change
), 10);
715 rtx_group_table
= htab_create (11, invariant_group_base_hash
,
716 invariant_group_base_eq
, NULL
);
718 bb_table
= XCNEWVEC (bb_info_t
, last_basic_block
);
719 rtx_group_next_id
= 0;
721 stores_off_frame_dead_at_return
= !cfun
->stdarg
;
723 init_alias_analysis ();
725 if (clear_alias_sets
)
726 clear_alias_group
= get_group_info (NULL
);
728 clear_alias_group
= NULL
;
733 /*----------------------------------------------------------------------------
736 Scan all of the insns. Any random ordering of the blocks is fine.
737 Each block is scanned in forward order to accommodate cselib which
738 is used to remove stores with non-constant bases.
739 ----------------------------------------------------------------------------*/
741 /* Delete all of the store_info recs from INSN_INFO. */
744 free_store_info (insn_info_t insn_info
)
746 store_info_t store_info
= insn_info
->store_rec
;
749 store_info_t next
= store_info
->next
;
750 if (store_info
->cse_base
)
751 pool_free (cse_store_info_pool
, store_info
);
753 pool_free (rtx_store_info_pool
, store_info
);
757 insn_info
->cannot_delete
= true;
758 insn_info
->contains_cselib_groups
= false;
759 insn_info
->store_rec
= NULL
;
769 /* Add an insn to do the add inside a x if it is a
770 PRE/POST-INC/DEC/MODIFY. D is an structure containing the insn and
771 the size of the mode of the MEM that this is inside of. */
774 replace_inc_dec (rtx
*r
, void *d
)
777 struct insn_size
*data
= (struct insn_size
*)d
;
778 switch (GET_CODE (x
))
783 rtx r1
= XEXP (x
, 0);
784 rtx c
= gen_int_mode (Pmode
, data
->size
);
785 add_insn_before (data
->insn
,
786 gen_rtx_SET (Pmode
, r1
,
787 gen_rtx_PLUS (Pmode
, r1
, c
)),
795 rtx r1
= XEXP (x
, 0);
796 rtx c
= gen_int_mode (Pmode
, -data
->size
);
797 add_insn_before (data
->insn
,
798 gen_rtx_SET (Pmode
, r1
,
799 gen_rtx_PLUS (Pmode
, r1
, c
)),
807 /* We can reuse the add because we are about to delete the
808 insn that contained it. */
809 rtx add
= XEXP (x
, 0);
810 rtx r1
= XEXP (add
, 0);
811 add_insn_before (data
->insn
,
812 gen_rtx_SET (Pmode
, r1
, add
), NULL
);
822 /* If X is a MEM, check the address to see if it is PRE/POST-INC/DEC/MODIFY
823 and generate an add to replace that. */
826 replace_inc_dec_mem (rtx
*r
, void *d
)
829 if (GET_CODE (x
) == MEM
)
831 struct insn_size data
;
833 data
.size
= GET_MODE_SIZE (GET_MODE (x
));
836 for_each_rtx (&XEXP (x
, 0), replace_inc_dec
, &data
);
843 /* Before we delete INSN, make sure that the auto inc/dec, if it is
844 there, is split into a separate insn. */
847 check_for_inc_dec (rtx insn
)
849 rtx note
= find_reg_note (insn
, REG_INC
, NULL_RTX
);
851 for_each_rtx (&insn
, replace_inc_dec_mem
, insn
);
855 /* Delete the insn and free all of the fields inside INSN_INFO. */
858 delete_dead_store_insn (insn_info_t insn_info
)
860 read_info_t read_info
;
865 check_for_inc_dec (insn_info
->insn
);
868 fprintf (dump_file
, "Locally deleting insn %d ",
869 INSN_UID (insn_info
->insn
));
870 if (insn_info
->store_rec
->alias_set
)
871 fprintf (dump_file
, "alias set %d\n",
872 (int) insn_info
->store_rec
->alias_set
);
874 fprintf (dump_file
, "\n");
877 free_store_info (insn_info
);
878 read_info
= insn_info
->read_rec
;
882 read_info_t next
= read_info
->next
;
883 pool_free (read_info_pool
, read_info
);
886 insn_info
->read_rec
= NULL
;
888 delete_insn (insn_info
->insn
);
890 insn_info
->insn
= NULL
;
892 insn_info
->wild_read
= false;
896 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
900 set_usage_bits (group_info_t group
, HOST_WIDE_INT offset
, HOST_WIDE_INT width
)
904 if ((offset
> -MAX_OFFSET
) && (offset
< MAX_OFFSET
))
905 for (i
=offset
; i
<offset
+width
; i
++)
912 store1
= group
->store1_n
;
913 store2
= group
->store2_n
;
918 store1
= group
->store1_p
;
919 store2
= group
->store2_p
;
923 if (bitmap_bit_p (store1
, ai
))
924 bitmap_set_bit (store2
, ai
);
927 bitmap_set_bit (store1
, ai
);
930 if (group
->offset_map_size_n
< ai
)
931 group
->offset_map_size_n
= ai
;
935 if (group
->offset_map_size_p
< ai
)
936 group
->offset_map_size_p
= ai
;
943 /* Set the BB_INFO so that the last insn is marked as a wild read. */
946 add_wild_read (bb_info_t bb_info
)
948 insn_info_t insn_info
= bb_info
->last_insn
;
949 read_info_t
*ptr
= &insn_info
->read_rec
;
953 read_info_t next
= (*ptr
)->next
;
954 if ((*ptr
)->alias_set
== 0)
956 pool_free (read_info_pool
, *ptr
);
962 insn_info
->wild_read
= true;
963 active_local_stores
= NULL
;
967 /* Return true if X is a constant or one of the registers that behave
968 as a constant over the life of a function. This is equivalent to
969 !rtx_varies_p for memory addresses. */
972 const_or_frame_p (rtx x
)
974 switch (GET_CODE (x
))
977 return MEM_READONLY_P (x
);
988 /* Note that we have to test for the actual rtx used for the frame
989 and arg pointers and not just the register number in case we have
990 eliminated the frame and/or arg pointer and are using it
992 if (x
== frame_pointer_rtx
|| x
== hard_frame_pointer_rtx
993 /* The arg pointer varies if it is not a fixed register. */
994 || (x
== arg_pointer_rtx
&& fixed_regs
[ARG_POINTER_REGNUM
])
995 || x
== pic_offset_table_rtx
)
1004 /* Take all reasonable action to put the address of MEM into the form
1005 that we can do analysis on.
1007 The gold standard is to get the address into the form: address +
1008 OFFSET where address is something that rtx_varies_p considers a
1009 constant. When we can get the address in this form, we can do
1010 global analysis on it. Note that for constant bases, address is
1011 not actually returned, only the group_id. The address can be
1014 If that fails, we try cselib to get a value we can at least use
1015 locally. If that fails we return false.
1017 The GROUP_ID is set to -1 for cselib bases and the index of the
1018 group for non_varying bases.
1020 FOR_READ is true if this is a mem read and false if not. */
1023 canon_address (rtx mem
,
1024 alias_set_type
*alias_set_out
,
1026 HOST_WIDE_INT
*offset
,
1029 rtx mem_address
= XEXP (mem
, 0);
1030 rtx expanded_address
, address
;
1031 /* Make sure that cselib is has initialized all of the operands of
1032 the address before asking it to do the subst. */
1034 if (clear_alias_sets
)
1036 /* If this is a spill, do not do any further processing. */
1037 alias_set_type alias_set
= MEM_ALIAS_SET (mem
);
1039 fprintf (dump_file
, "found alias set %d\n", (int) alias_set
);
1040 if (bitmap_bit_p (clear_alias_sets
, alias_set
))
1042 struct clear_alias_mode_holder
*entry
1043 = clear_alias_set_lookup (alias_set
);
1045 /* If the modes do not match, we cannot process this set. */
1046 if (entry
->mode
!= GET_MODE (mem
))
1050 "disqualifying alias set %d, (%s) != (%s)\n",
1051 (int) alias_set
, GET_MODE_NAME (entry
->mode
),
1052 GET_MODE_NAME (GET_MODE (mem
)));
1054 bitmap_set_bit (disqualified_clear_alias_sets
, alias_set
);
1058 *alias_set_out
= alias_set
;
1059 *group_id
= clear_alias_group
->id
;
1066 cselib_lookup (mem_address
, Pmode
, 1);
1070 fprintf (dump_file
, " mem: ");
1071 print_inline_rtx (dump_file
, mem_address
, 0);
1072 fprintf (dump_file
, "\n");
1075 /* Use cselib to replace all of the reg references with the full
1076 expression. This will take care of the case where we have
1078 r_x = base + offset;
1083 val = *(base + offset);
1086 expanded_address
= cselib_expand_value_rtx (mem_address
, scratch
, 5);
1088 /* If this fails, just go with the mem_address. */
1089 if (!expanded_address
)
1090 expanded_address
= mem_address
;
1092 /* Split the address into canonical BASE + OFFSET terms. */
1093 address
= canon_rtx (expanded_address
);
1099 fprintf (dump_file
, "\n after cselib_expand address: ");
1100 print_inline_rtx (dump_file
, expanded_address
, 0);
1101 fprintf (dump_file
, "\n");
1103 fprintf (dump_file
, "\n after canon_rtx address: ");
1104 print_inline_rtx (dump_file
, address
, 0);
1105 fprintf (dump_file
, "\n");
1108 if (GET_CODE (address
) == CONST
)
1109 address
= XEXP (address
, 0);
1111 if (GET_CODE (address
) == PLUS
&& GET_CODE (XEXP (address
, 1)) == CONST_INT
)
1113 *offset
= INTVAL (XEXP (address
, 1));
1114 address
= XEXP (address
, 0);
1117 if (const_or_frame_p (address
))
1119 group_info_t group
= get_group_info (address
);
1122 fprintf (dump_file
, " gid=%d offset=%d \n", group
->id
, (int)*offset
);
1124 *group_id
= group
->id
;
1128 *base
= cselib_lookup (address
, Pmode
, true);
1134 fprintf (dump_file
, " no cselib val - should be a wild read.\n");
1138 fprintf (dump_file
, " varying cselib base=%d offset = %d\n",
1139 (*base
)->value
, (int)*offset
);
1145 /* Clear the rhs field from the active_local_stores array. */
1148 clear_rhs_from_active_local_stores (void)
1150 insn_info_t ptr
= active_local_stores
;
1154 store_info_t store_info
= ptr
->store_rec
;
1155 /* Skip the clobbers. */
1156 while (!store_info
->is_set
)
1157 store_info
= store_info
->next
;
1159 store_info
->rhs
= NULL
;
1161 ptr
= ptr
->next_local_store
;
1166 /* BODY is an instruction pattern that belongs to INSN. Return 1 if
1167 there is a candidate store, after adding it to the appropriate
1168 local store group if so. */
1171 record_store (rtx body
, bb_info_t bb_info
)
1174 HOST_WIDE_INT offset
= 0;
1175 HOST_WIDE_INT width
= 0;
1176 alias_set_type spill_alias_set
;
1177 insn_info_t insn_info
= bb_info
->last_insn
;
1178 store_info_t store_info
= NULL
;
1180 cselib_val
*base
= NULL
;
1181 insn_info_t ptr
, last
;
1182 bool store_is_unused
;
1184 if (GET_CODE (body
) != SET
&& GET_CODE (body
) != CLOBBER
)
1187 /* If this is not used, then this cannot be used to keep the insn
1188 from being deleted. On the other hand, it does provide something
1189 that can be used to prove that another store is dead. */
1191 = (find_reg_note (insn_info
->insn
, REG_UNUSED
, body
) != NULL
);
1193 /* Check whether that value is a suitable memory location. */
1194 mem
= SET_DEST (body
);
1197 /* If the set or clobber is unused, then it does not effect our
1198 ability to get rid of the entire insn. */
1199 if (!store_is_unused
)
1200 insn_info
->cannot_delete
= true;
1204 /* At this point we know mem is a mem. */
1205 if (GET_MODE (mem
) == BLKmode
)
1207 if (GET_CODE (XEXP (mem
, 0)) == SCRATCH
)
1210 fprintf (dump_file
, " adding wild read for (clobber (mem:BLK (scratch))\n");
1211 add_wild_read (bb_info
);
1212 insn_info
->cannot_delete
= true;
1214 else if (!store_is_unused
)
1216 /* If the set or clobber is unused, then it does not effect our
1217 ability to get rid of the entire insn. */
1218 insn_info
->cannot_delete
= true;
1219 clear_rhs_from_active_local_stores ();
1224 /* We can still process a volatile mem, we just cannot delete it. */
1225 if (MEM_VOLATILE_P (mem
))
1226 insn_info
->cannot_delete
= true;
1228 if (!canon_address (mem
, &spill_alias_set
, &group_id
, &offset
, &base
))
1230 clear_rhs_from_active_local_stores ();
1234 width
= GET_MODE_SIZE (GET_MODE (mem
));
1236 if (spill_alias_set
)
1238 bitmap store1
= clear_alias_group
->store1_p
;
1239 bitmap store2
= clear_alias_group
->store2_p
;
1241 if (bitmap_bit_p (store1
, spill_alias_set
))
1242 bitmap_set_bit (store2
, spill_alias_set
);
1244 bitmap_set_bit (store1
, spill_alias_set
);
1246 if (clear_alias_group
->offset_map_size_p
< spill_alias_set
)
1247 clear_alias_group
->offset_map_size_p
= spill_alias_set
;
1249 store_info
= pool_alloc (rtx_store_info_pool
);
1252 fprintf (dump_file
, " processing spill store %d(%s)\n",
1253 (int) spill_alias_set
, GET_MODE_NAME (GET_MODE (mem
)));
1255 else if (group_id
>= 0)
1257 /* In the restrictive case where the base is a constant or the
1258 frame pointer we can do global analysis. */
1261 = VEC_index (group_info_t
, rtx_group_vec
, group_id
);
1263 store_info
= pool_alloc (rtx_store_info_pool
);
1264 set_usage_bits (group
, offset
, width
);
1267 fprintf (dump_file
, " processing const base store gid=%d[%d..%d)\n",
1268 group_id
, (int)offset
, (int)(offset
+width
));
1272 rtx base_term
= find_base_term (XEXP (mem
, 0));
1274 || (GET_CODE (base_term
) == ADDRESS
1275 && GET_MODE (base_term
) == Pmode
1276 && XEXP (base_term
, 0) == stack_pointer_rtx
))
1277 insn_info
->stack_pointer_based
= true;
1278 insn_info
->contains_cselib_groups
= true;
1280 store_info
= pool_alloc (cse_store_info_pool
);
1284 fprintf (dump_file
, " processing cselib store [%d..%d)\n",
1285 (int)offset
, (int)(offset
+width
));
1288 /* Check to see if this stores causes some other stores to be
1290 ptr
= active_local_stores
;
1295 insn_info_t next
= ptr
->next_local_store
;
1296 store_info_t s_info
= ptr
->store_rec
;
1299 /* Skip the clobbers. We delete the active insn if this insn
1300 shadows the set. To have been put on the active list, it
1301 has exactly on set. */
1302 while (!s_info
->is_set
)
1303 s_info
= s_info
->next
;
1305 if (s_info
->alias_set
!= spill_alias_set
)
1307 else if (s_info
->alias_set
)
1309 struct clear_alias_mode_holder
*entry
1310 = clear_alias_set_lookup (s_info
->alias_set
);
1311 /* Generally, spills cannot be processed if and of the
1312 references to the slot have a different mode. But if
1313 we are in the same block and mode is exactly the same
1314 between this store and one before in the same block,
1315 we can still delete it. */
1316 if ((GET_MODE (mem
) == GET_MODE (s_info
->mem
))
1317 && (GET_MODE (mem
) == entry
->mode
))
1320 s_info
->positions_needed
= (unsigned HOST_WIDE_INT
) 0;
1323 fprintf (dump_file
, " trying spill store in insn=%d alias_set=%d\n",
1324 INSN_UID (ptr
->insn
), (int) s_info
->alias_set
);
1326 else if ((s_info
->group_id
== group_id
)
1327 && (s_info
->cse_base
== base
))
1331 fprintf (dump_file
, " trying store in insn=%d gid=%d[%d..%d)\n",
1332 INSN_UID (ptr
->insn
), s_info
->group_id
,
1333 (int)s_info
->begin
, (int)s_info
->end
);
1334 for (i
= offset
; i
< offset
+width
; i
++)
1335 if (i
>= s_info
->begin
&& i
< s_info
->end
)
1336 s_info
->positions_needed
1337 &= ~(((unsigned HOST_WIDE_INT
) 1) << (i
- s_info
->begin
));
1339 else if (s_info
->rhs
)
1340 /* Need to see if it is possible for this store to overwrite
1341 the value of store_info. If it is, set the rhs to NULL to
1342 keep it from being used to remove a load. */
1344 if (canon_true_dependence (s_info
->mem
,
1345 GET_MODE (s_info
->mem
),
1351 /* An insn can be deleted if every position of every one of
1352 its s_infos is zero. */
1353 if (s_info
->positions_needed
!= (unsigned HOST_WIDE_INT
) 0)
1358 insn_info_t insn_to_delete
= ptr
;
1361 last
->next_local_store
= ptr
->next_local_store
;
1363 active_local_stores
= ptr
->next_local_store
;
1365 delete_dead_store_insn (insn_to_delete
);
1373 gcc_assert ((unsigned) width
<= HOST_BITS_PER_WIDE_INT
);
1375 /* Finish filling in the store_info. */
1376 store_info
->next
= insn_info
->store_rec
;
1377 insn_info
->store_rec
= store_info
;
1378 store_info
->mem
= canon_rtx (mem
);
1379 store_info
->alias_set
= spill_alias_set
;
1380 store_info
->mem_addr
= get_addr (XEXP (mem
, 0));
1381 store_info
->cse_base
= base
;
1382 store_info
->positions_needed
= lowpart_bitmask (width
);
1383 store_info
->group_id
= group_id
;
1384 store_info
->begin
= offset
;
1385 store_info
->end
= offset
+ width
;
1386 store_info
->is_set
= GET_CODE (body
) == SET
;
1388 if (store_info
->is_set
1389 /* No place to keep the value after ra. */
1390 && !reload_completed
1391 && (REG_P (SET_SRC (body
))
1392 || GET_CODE (SET_SRC (body
)) == SUBREG
1393 || CONSTANT_P (SET_SRC (body
)))
1394 /* Sometimes the store and reload is used for truncation and
1396 && !(FLOAT_MODE_P (GET_MODE (mem
)) && (flag_float_store
)))
1397 store_info
->rhs
= SET_SRC (body
);
1399 store_info
->rhs
= NULL
;
1401 /* If this is a clobber, we return 0. We will only be able to
1402 delete this insn if there is only one store USED store, but we
1403 can use the clobber to delete other stores earlier. */
1404 return store_info
->is_set
? 1 : 0;
1409 dump_insn_info (const char * start
, insn_info_t insn_info
)
1411 fprintf (dump_file
, "%s insn=%d %s\n", start
,
1412 INSN_UID (insn_info
->insn
),
1413 insn_info
->store_rec
? "has store" : "naked");
1417 /* If the modes are different and the value's source and target do not
1418 line up, we need to extract the value from lower part of the rhs of
1419 the store, shift it, and then put it into a form that can be shoved
1420 into the read_insn. This function generates a right SHIFT of a
1421 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The
1422 shift sequence is returned or NULL if we failed to find a
1426 find_shift_sequence (int access_size
,
1427 store_info_t store_info
,
1428 read_info_t read_info
,
1431 enum machine_mode store_mode
= GET_MODE (store_info
->mem
);
1432 enum machine_mode read_mode
= GET_MODE (read_info
->mem
);
1433 enum machine_mode new_mode
;
1434 rtx read_reg
= NULL
;
1436 /* Some machines like the x86 have shift insns for each size of
1437 operand. Other machines like the ppc or the ia-64 may only have
1438 shift insns that shift values within 32 or 64 bit registers.
1439 This loop tries to find the smallest shift insn that will right
1440 justify the value we want to read but is available in one insn on
1443 for (new_mode
= smallest_mode_for_size (access_size
* BITS_PER_UNIT
,
1445 GET_MODE_BITSIZE (new_mode
) <= BITS_PER_WORD
;
1446 new_mode
= GET_MODE_WIDER_MODE (new_mode
))
1448 rtx target
, new_reg
, shift_seq
, insn
, new_lhs
;
1451 /* Try a wider mode if truncating the store mode to NEW_MODE
1452 requires a real instruction. */
1453 if (GET_MODE_BITSIZE (new_mode
) < GET_MODE_BITSIZE (store_mode
)
1454 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (new_mode
),
1455 GET_MODE_BITSIZE (store_mode
)))
1458 /* Also try a wider mode if the necessary punning is either not
1459 desirable or not possible. */
1460 if (!CONSTANT_P (store_info
->rhs
)
1461 && !MODES_TIEABLE_P (new_mode
, store_mode
))
1463 offset
= subreg_lowpart_offset (new_mode
, store_mode
);
1464 new_lhs
= simplify_gen_subreg (new_mode
, copy_rtx (store_info
->rhs
),
1465 store_mode
, offset
);
1466 if (new_lhs
== NULL_RTX
)
1469 new_reg
= gen_reg_rtx (new_mode
);
1473 /* In theory we could also check for an ashr. Ian Taylor knows
1474 of one dsp where the cost of these two was not the same. But
1475 this really is a rare case anyway. */
1476 target
= expand_binop (new_mode
, lshr_optab
, new_reg
,
1477 GEN_INT (shift
), new_reg
, 1, OPTAB_DIRECT
);
1479 shift_seq
= get_insns ();
1482 if (target
!= new_reg
|| shift_seq
== NULL
)
1486 for (insn
= shift_seq
; insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
1488 cost
+= insn_rtx_cost (PATTERN (insn
));
1490 /* The computation up to here is essentially independent
1491 of the arguments and could be precomputed. It may
1492 not be worth doing so. We could precompute if
1493 worthwhile or at least cache the results. The result
1494 technically depends on both SHIFT and ACCESS_SIZE,
1495 but in practice the answer will depend only on ACCESS_SIZE. */
1497 if (cost
> COSTS_N_INSNS (1))
1500 /* We found an acceptable shift. Generate a move to
1501 take the value from the store and put it into the
1502 shift pseudo, then shift it, then generate another
1503 move to put in into the target of the read. */
1504 emit_move_insn (new_reg
, new_lhs
);
1505 emit_insn (shift_seq
);
1506 read_reg
= extract_low_bits (read_mode
, new_mode
, new_reg
);
1514 /* Take a sequence of:
1537 Depending on the alignment and the mode of the store and
1541 The STORE_INFO and STORE_INSN are for the store and READ_INFO
1542 and READ_INSN are for the read. Return true if the replacement
1546 replace_read (store_info_t store_info
, insn_info_t store_insn
,
1547 read_info_t read_info
, insn_info_t read_insn
, rtx
*loc
)
1549 enum machine_mode store_mode
= GET_MODE (store_info
->mem
);
1550 enum machine_mode read_mode
= GET_MODE (read_info
->mem
);
1552 int access_size
; /* In bytes. */
1553 rtx insns
, read_reg
;
1558 /* To get here the read is within the boundaries of the write so
1559 shift will never be negative. Start out with the shift being in
1561 if (BYTES_BIG_ENDIAN
)
1562 shift
= store_info
->end
- read_info
->end
;
1564 shift
= read_info
->begin
- store_info
->begin
;
1566 access_size
= shift
+ GET_MODE_SIZE (read_mode
);
1568 /* From now on it is bits. */
1569 shift
*= BITS_PER_UNIT
;
1571 /* Create a sequence of instructions to set up the read register.
1572 This sequence goes immediately before the store and its result
1573 is read by the load.
1575 We need to keep this in perspective. We are replacing a read
1576 with a sequence of insns, but the read will almost certainly be
1577 in cache, so it is not going to be an expensive one. Thus, we
1578 are not willing to do a multi insn shift or worse a subroutine
1579 call to get rid of the read. */
1581 fprintf (dump_file
, "trying to replace %smode load in insn %d"
1582 " from %smode store in insn %d\n",
1583 GET_MODE_NAME (read_mode
), INSN_UID (read_insn
->insn
),
1584 GET_MODE_NAME (store_mode
), INSN_UID (store_insn
->insn
));
1587 read_reg
= find_shift_sequence (access_size
, store_info
, read_info
, shift
);
1589 read_reg
= extract_low_bits (read_mode
, store_mode
,
1590 copy_rtx (store_info
->rhs
));
1591 if (read_reg
== NULL_RTX
)
1595 fprintf (dump_file
, " -- could not extract bits of stored value\n");
1598 /* Force the value into a new register so that it won't be clobbered
1599 between the store and the load. */
1600 read_reg
= copy_to_mode_reg (read_mode
, read_reg
);
1601 insns
= get_insns ();
1604 if (validate_change (read_insn
->insn
, loc
, read_reg
, 0))
1606 deferred_change_t deferred_change
= pool_alloc (deferred_change_pool
);
1608 /* Insert this right before the store insn where it will be safe
1609 from later insns that might change it before the read. */
1610 emit_insn_before (insns
, store_insn
->insn
);
1612 /* And now for the kludge part: cselib croaks if you just
1613 return at this point. There are two reasons for this:
1615 1) Cselib has an idea of how many pseudos there are and
1616 that does not include the new ones we just added.
1618 2) Cselib does not know about the move insn we added
1619 above the store_info, and there is no way to tell it
1620 about it, because it has "moved on".
1622 Problem (1) is fixable with a certain amount of engineering.
1623 Problem (2) is requires starting the bb from scratch. This
1626 So we are just going to have to lie. The move/extraction
1627 insns are not really an issue, cselib did not see them. But
1628 the use of the new pseudo read_insn is a real problem because
1629 cselib has not scanned this insn. The way that we solve this
1630 problem is that we are just going to put the mem back for now
1631 and when we are finished with the block, we undo this. We
1632 keep a table of mems to get rid of. At the end of the basic
1633 block we can put them back. */
1635 *loc
= read_info
->mem
;
1636 deferred_change
->next
= deferred_change_list
;
1637 deferred_change_list
= deferred_change
;
1638 deferred_change
->loc
= loc
;
1639 deferred_change
->reg
= read_reg
;
1641 /* Get rid of the read_info, from the point of view of the
1642 rest of dse, play like this read never happened. */
1643 read_insn
->read_rec
= read_info
->next
;
1644 pool_free (read_info_pool
, read_info
);
1647 fprintf (dump_file
, " -- replaced the loaded MEM with ");
1648 print_simple_rtl (dump_file
, read_reg
);
1649 fprintf (dump_file
, "\n");
1657 fprintf (dump_file
, " -- replacing the loaded MEM with ");
1658 print_simple_rtl (dump_file
, read_reg
);
1659 fprintf (dump_file
, " led to an invalid instruction\n");
1665 /* A for_each_rtx callback in which DATA is the bb_info. Check to see
1666 if LOC is a mem and if it is look at the address and kill any
1667 appropriate stores that may be active. */
1670 check_mem_read_rtx (rtx
*loc
, void *data
)
1674 insn_info_t insn_info
;
1675 HOST_WIDE_INT offset
= 0;
1676 HOST_WIDE_INT width
= 0;
1677 alias_set_type spill_alias_set
= 0;
1678 cselib_val
*base
= NULL
;
1680 read_info_t read_info
;
1682 if (!mem
|| !MEM_P (mem
))
1685 bb_info
= (bb_info_t
) data
;
1686 insn_info
= bb_info
->last_insn
;
1688 if ((MEM_ALIAS_SET (mem
) == ALIAS_SET_MEMORY_BARRIER
)
1689 || (MEM_VOLATILE_P (mem
)))
1692 fprintf (dump_file
, " adding wild read, volatile or barrier.\n");
1693 add_wild_read (bb_info
);
1694 insn_info
->cannot_delete
= true;
1698 /* If it is reading readonly mem, then there can be no conflict with
1700 if (MEM_READONLY_P (mem
))
1703 if (!canon_address (mem
, &spill_alias_set
, &group_id
, &offset
, &base
))
1706 fprintf (dump_file
, " adding wild read, canon_address failure.\n");
1707 add_wild_read (bb_info
);
1711 if (GET_MODE (mem
) == BLKmode
)
1714 width
= GET_MODE_SIZE (GET_MODE (mem
));
1716 read_info
= pool_alloc (read_info_pool
);
1717 read_info
->group_id
= group_id
;
1718 read_info
->mem
= mem
;
1719 read_info
->alias_set
= spill_alias_set
;
1720 read_info
->begin
= offset
;
1721 read_info
->end
= offset
+ width
;
1722 read_info
->next
= insn_info
->read_rec
;
1723 insn_info
->read_rec
= read_info
;
1725 /* We ignore the clobbers in store_info. The is mildly aggressive,
1726 but there really should not be a clobber followed by a read. */
1728 if (spill_alias_set
)
1730 insn_info_t i_ptr
= active_local_stores
;
1731 insn_info_t last
= NULL
;
1734 fprintf (dump_file
, " processing spill load %d\n",
1735 (int) spill_alias_set
);
1739 store_info_t store_info
= i_ptr
->store_rec
;
1741 /* Skip the clobbers. */
1742 while (!store_info
->is_set
)
1743 store_info
= store_info
->next
;
1745 if (store_info
->alias_set
== spill_alias_set
)
1748 dump_insn_info ("removing from active", i_ptr
);
1751 last
->next_local_store
= i_ptr
->next_local_store
;
1753 active_local_stores
= i_ptr
->next_local_store
;
1757 i_ptr
= i_ptr
->next_local_store
;
1760 else if (group_id
>= 0)
1762 /* This is the restricted case where the base is a constant or
1763 the frame pointer and offset is a constant. */
1764 insn_info_t i_ptr
= active_local_stores
;
1765 insn_info_t last
= NULL
;
1770 fprintf (dump_file
, " processing const load gid=%d[BLK]\n",
1773 fprintf (dump_file
, " processing const load gid=%d[%d..%d)\n",
1774 group_id
, (int)offset
, (int)(offset
+width
));
1779 bool remove
= false;
1780 store_info_t store_info
= i_ptr
->store_rec
;
1782 /* Skip the clobbers. */
1783 while (!store_info
->is_set
)
1784 store_info
= store_info
->next
;
1786 /* There are three cases here. */
1787 if (store_info
->group_id
< 0)
1788 /* We have a cselib store followed by a read from a
1791 = canon_true_dependence (store_info
->mem
,
1792 GET_MODE (store_info
->mem
),
1793 store_info
->mem_addr
,
1796 else if (group_id
== store_info
->group_id
)
1798 /* This is a block mode load. We may get lucky and
1799 canon_true_dependence may save the day. */
1802 = canon_true_dependence (store_info
->mem
,
1803 GET_MODE (store_info
->mem
),
1804 store_info
->mem_addr
,
1807 /* If this read is just reading back something that we just
1808 stored, rewrite the read. */
1812 && (offset
>= store_info
->begin
)
1813 && (offset
+ width
<= store_info
->end
))
1815 unsigned HOST_WIDE_INT mask
1816 = (lowpart_bitmask (width
)
1817 << (offset
- store_info
->begin
));
1819 if ((store_info
->positions_needed
& mask
) == mask
1820 && replace_read (store_info
, i_ptr
,
1821 read_info
, insn_info
, loc
))
1824 /* The bases are the same, just see if the offsets
1826 if ((offset
< store_info
->end
)
1827 && (offset
+ width
> store_info
->begin
))
1833 The else case that is missing here is that the
1834 bases are constant but different. There is nothing
1835 to do here because there is no overlap. */
1840 dump_insn_info ("removing from active", i_ptr
);
1843 last
->next_local_store
= i_ptr
->next_local_store
;
1845 active_local_stores
= i_ptr
->next_local_store
;
1849 i_ptr
= i_ptr
->next_local_store
;
1854 insn_info_t i_ptr
= active_local_stores
;
1855 insn_info_t last
= NULL
;
1858 fprintf (dump_file
, " processing cselib load mem:");
1859 print_inline_rtx (dump_file
, mem
, 0);
1860 fprintf (dump_file
, "\n");
1865 bool remove
= false;
1866 store_info_t store_info
= i_ptr
->store_rec
;
1869 fprintf (dump_file
, " processing cselib load against insn %d\n",
1870 INSN_UID (i_ptr
->insn
));
1872 /* Skip the clobbers. */
1873 while (!store_info
->is_set
)
1874 store_info
= store_info
->next
;
1876 /* If this read is just reading back something that we just
1877 stored, rewrite the read. */
1879 && store_info
->group_id
== -1
1880 && store_info
->cse_base
== base
1881 && (offset
>= store_info
->begin
)
1882 && (offset
+ width
<= store_info
->end
))
1884 unsigned HOST_WIDE_INT mask
1885 = (lowpart_bitmask (width
)
1886 << (offset
- store_info
->begin
));
1888 if ((store_info
->positions_needed
& mask
) == mask
1889 && replace_read (store_info
, i_ptr
,
1890 read_info
, insn_info
, loc
))
1894 if (!store_info
->alias_set
)
1895 remove
= canon_true_dependence (store_info
->mem
,
1896 GET_MODE (store_info
->mem
),
1897 store_info
->mem_addr
,
1903 dump_insn_info ("removing from active", i_ptr
);
1906 last
->next_local_store
= i_ptr
->next_local_store
;
1908 active_local_stores
= i_ptr
->next_local_store
;
1912 i_ptr
= i_ptr
->next_local_store
;
1918 /* A for_each_rtx callback in which DATA points the INSN_INFO for
1919 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
1920 true for any part of *LOC. */
1923 check_mem_read_use (rtx
*loc
, void *data
)
1925 for_each_rtx (loc
, check_mem_read_rtx
, data
);
1928 /* Apply record_store to all candidate stores in INSN. Mark INSN
1929 if some part of it is not a candidate store and assigns to a
1930 non-register target. */
1933 scan_insn (bb_info_t bb_info
, rtx insn
)
1936 insn_info_t insn_info
= pool_alloc (insn_info_pool
);
1938 memset (insn_info
, 0, sizeof (struct insn_info
));
1941 fprintf (dump_file
, "\n**scanning insn=%d\n",
1944 insn_info
->prev_insn
= bb_info
->last_insn
;
1945 insn_info
->insn
= insn
;
1946 bb_info
->last_insn
= insn_info
;
1949 /* Cselib clears the table for this case, so we have to essentially
1951 if (NONJUMP_INSN_P (insn
)
1952 && GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
1953 && MEM_VOLATILE_P (PATTERN (insn
)))
1955 add_wild_read (bb_info
);
1956 insn_info
->cannot_delete
= true;
1960 /* Look at all of the uses in the insn. */
1961 note_uses (&PATTERN (insn
), check_mem_read_use
, bb_info
);
1965 insn_info
->cannot_delete
= true;
1967 /* Const functions cannot do anything bad i.e. read memory,
1968 however, they can read their parameters which may have
1969 been pushed onto the stack. */
1970 if (CONST_OR_PURE_CALL_P (insn
) && !pure_call_p (insn
))
1972 insn_info_t i_ptr
= active_local_stores
;
1973 insn_info_t last
= NULL
;
1976 fprintf (dump_file
, "const call %d\n", INSN_UID (insn
));
1978 /* See the head comment of the frame_read field. */
1979 if (reload_completed
)
1980 insn_info
->frame_read
= true;
1982 /* Loop over the active stores and remove those which are
1983 killed by the const function call. */
1986 bool remove_store
= false;
1988 /* The stack pointer based stores are always killed. */
1989 if (i_ptr
->stack_pointer_based
)
1990 remove_store
= true;
1992 /* If the frame is read, the frame related stores are killed. */
1993 else if (insn_info
->frame_read
)
1995 store_info_t store_info
= i_ptr
->store_rec
;
1997 /* Skip the clobbers. */
1998 while (!store_info
->is_set
)
1999 store_info
= store_info
->next
;
2001 if (store_info
->group_id
>= 0
2002 && VEC_index (group_info_t
, rtx_group_vec
,
2003 store_info
->group_id
)->frame_related
)
2004 remove_store
= true;
2010 dump_insn_info ("removing from active", i_ptr
);
2013 last
->next_local_store
= i_ptr
->next_local_store
;
2015 active_local_stores
= i_ptr
->next_local_store
;
2020 i_ptr
= i_ptr
->next_local_store
;
2025 /* Every other call, including pure functions, may read memory. */
2026 add_wild_read (bb_info
);
2031 /* Assuming that there are sets in these insns, we cannot delete
2033 if ((GET_CODE (PATTERN (insn
)) == CLOBBER
)
2034 || volatile_refs_p (PATTERN (insn
))
2035 || (flag_non_call_exceptions
&& may_trap_p (PATTERN (insn
)))
2036 || (RTX_FRAME_RELATED_P (insn
))
2037 || find_reg_note (insn
, REG_FRAME_RELATED_EXPR
, NULL_RTX
))
2038 insn_info
->cannot_delete
= true;
2040 body
= PATTERN (insn
);
2041 if (GET_CODE (body
) == PARALLEL
)
2044 for (i
= 0; i
< XVECLEN (body
, 0); i
++)
2045 mems_found
+= record_store (XVECEXP (body
, 0, i
), bb_info
);
2048 mems_found
+= record_store (body
, bb_info
);
2051 fprintf (dump_file
, "mems_found = %d, cannot_delete = %s\n",
2052 mems_found
, insn_info
->cannot_delete
? "true" : "false");
2054 /* If we found some sets of mems, and the insn has not been marked
2055 cannot delete, add it into the active_local_stores so that it can
2056 be locally deleted if found dead. Otherwise mark it as cannot
2057 delete. This simplifies the processing later. */
2058 if (mems_found
== 1 && !insn_info
->cannot_delete
)
2060 insn_info
->next_local_store
= active_local_stores
;
2061 active_local_stores
= insn_info
;
2064 insn_info
->cannot_delete
= true;
2068 /* Remove BASE from the set of active_local_stores. This is a
2069 callback from cselib that is used to get rid of the stores in
2070 active_local_stores. */
2073 remove_useless_values (cselib_val
*base
)
2075 insn_info_t insn_info
= active_local_stores
;
2076 insn_info_t last
= NULL
;
2080 store_info_t store_info
= insn_info
->store_rec
;
2081 bool delete = false;
2083 /* If ANY of the store_infos match the cselib group that is
2084 being deleted, then the insn can not be deleted. */
2087 if ((store_info
->group_id
== -1)
2088 && (store_info
->cse_base
== base
))
2093 store_info
= store_info
->next
;
2099 last
->next_local_store
= insn_info
->next_local_store
;
2101 active_local_stores
= insn_info
->next_local_store
;
2102 free_store_info (insn_info
);
2107 insn_info
= insn_info
->next_local_store
;
2112 /* Do all of step 1. */
2119 cselib_init (false);
2120 all_blocks
= BITMAP_ALLOC (NULL
);
2121 bitmap_set_bit (all_blocks
, ENTRY_BLOCK
);
2122 bitmap_set_bit (all_blocks
, EXIT_BLOCK
);
2127 bb_info_t bb_info
= pool_alloc (bb_info_pool
);
2129 memset (bb_info
, 0, sizeof (struct bb_info
));
2130 bitmap_set_bit (all_blocks
, bb
->index
);
2132 bb_table
[bb
->index
] = bb_info
;
2133 cselib_discard_hook
= remove_useless_values
;
2135 if (bb
->index
>= NUM_FIXED_BLOCKS
)
2140 = create_alloc_pool ("cse_store_info_pool",
2141 sizeof (struct store_info
), 100);
2142 active_local_stores
= NULL
;
2143 cselib_clear_table ();
2145 /* Scan the insns. */
2146 FOR_BB_INSNS (bb
, insn
)
2149 scan_insn (bb_info
, insn
);
2150 cselib_process_insn (insn
);
2153 /* This is something of a hack, because the global algorithm
2154 is supposed to take care of the case where stores go dead
2155 at the end of the function. However, the global
2156 algorithm must take a more conservative view of block
2157 mode reads than the local alg does. So to get the case
2158 where you have a store to the frame followed by a non
2159 overlapping block more read, we look at the active local
2160 stores at the end of the function and delete all of the
2161 frame and spill based ones. */
2162 if (stores_off_frame_dead_at_return
2163 && (EDGE_COUNT (bb
->succs
) == 0
2164 || (single_succ_p (bb
)
2165 && single_succ (bb
) == EXIT_BLOCK_PTR
2166 && ! crtl
->calls_eh_return
)))
2168 insn_info_t i_ptr
= active_local_stores
;
2171 store_info_t store_info
= i_ptr
->store_rec
;
2173 /* Skip the clobbers. */
2174 while (!store_info
->is_set
)
2175 store_info
= store_info
->next
;
2176 if (store_info
->alias_set
)
2177 delete_dead_store_insn (i_ptr
);
2179 if (store_info
->group_id
>= 0)
2182 = VEC_index (group_info_t
, rtx_group_vec
, store_info
->group_id
);
2183 if (group
->frame_related
)
2184 delete_dead_store_insn (i_ptr
);
2187 i_ptr
= i_ptr
->next_local_store
;
2191 /* Get rid of the loads that were discovered in
2192 replace_read. Cselib is finished with this block. */
2193 while (deferred_change_list
)
2195 deferred_change_t next
= deferred_change_list
->next
;
2197 /* There is no reason to validate this change. That was
2199 *deferred_change_list
->loc
= deferred_change_list
->reg
;
2200 pool_free (deferred_change_pool
, deferred_change_list
);
2201 deferred_change_list
= next
;
2204 /* Get rid of all of the cselib based store_infos in this
2205 block and mark the containing insns as not being
2207 ptr
= bb_info
->last_insn
;
2210 if (ptr
->contains_cselib_groups
)
2211 free_store_info (ptr
);
2212 ptr
= ptr
->prev_insn
;
2215 free_alloc_pool (cse_store_info_pool
);
2220 htab_empty (rtx_group_table
);
2224 /*----------------------------------------------------------------------------
2227 Assign each byte position in the stores that we are going to
2228 analyze globally to a position in the bitmaps. Returns true if
2229 there are any bit positions assigned.
2230 ----------------------------------------------------------------------------*/
2233 dse_step2_init (void)
2238 for (i
= 0; VEC_iterate (group_info_t
, rtx_group_vec
, i
, group
); i
++)
2240 /* For all non stack related bases, we only consider a store to
2241 be deletable if there are two or more stores for that
2242 position. This is because it takes one store to make the
2243 other store redundant. However, for the stores that are
2244 stack related, we consider them if there is only one store
2245 for the position. We do this because the stack related
2246 stores can be deleted if their is no read between them and
2247 the end of the function.
2249 To make this work in the current framework, we take the stack
2250 related bases add all of the bits from store1 into store2.
2251 This has the effect of making the eligible even if there is
2254 if (stores_off_frame_dead_at_return
&& group
->frame_related
)
2256 bitmap_ior_into (group
->store2_n
, group
->store1_n
);
2257 bitmap_ior_into (group
->store2_p
, group
->store1_p
);
2259 fprintf (dump_file
, "group %d is frame related ", i
);
2262 group
->offset_map_size_n
++;
2263 group
->offset_map_n
= XNEWVEC (int, group
->offset_map_size_n
);
2264 group
->offset_map_size_p
++;
2265 group
->offset_map_p
= XNEWVEC (int, group
->offset_map_size_p
);
2266 group
->process_globally
= false;
2269 fprintf (dump_file
, "group %d(%d+%d): ", i
,
2270 (int)bitmap_count_bits (group
->store2_n
),
2271 (int)bitmap_count_bits (group
->store2_p
));
2272 bitmap_print (dump_file
, group
->store2_n
, "n ", " ");
2273 bitmap_print (dump_file
, group
->store2_p
, "p ", "\n");
2279 /* Init the offset tables for the normal case. */
2282 dse_step2_nospill (void)
2286 /* Position 0 is unused because 0 is used in the maps to mean
2288 current_position
= 1;
2290 for (i
= 0; VEC_iterate (group_info_t
, rtx_group_vec
, i
, group
); i
++)
2295 if (group
== clear_alias_group
)
2298 memset (group
->offset_map_n
, 0, sizeof(int) * group
->offset_map_size_n
);
2299 memset (group
->offset_map_p
, 0, sizeof(int) * group
->offset_map_size_p
);
2300 bitmap_clear (group
->group_kill
);
2302 EXECUTE_IF_SET_IN_BITMAP (group
->store2_n
, 0, j
, bi
)
2304 bitmap_set_bit (group
->group_kill
, current_position
);
2305 group
->offset_map_n
[j
] = current_position
++;
2306 group
->process_globally
= true;
2308 EXECUTE_IF_SET_IN_BITMAP (group
->store2_p
, 0, j
, bi
)
2310 bitmap_set_bit (group
->group_kill
, current_position
);
2311 group
->offset_map_p
[j
] = current_position
++;
2312 group
->process_globally
= true;
2315 return current_position
!= 1;
2319 /* Init the offset tables for the spill case. */
2322 dse_step2_spill (void)
2325 group_info_t group
= clear_alias_group
;
2328 /* Position 0 is unused because 0 is used in the maps to mean
2330 current_position
= 1;
2334 bitmap_print (dump_file
, clear_alias_sets
,
2335 "clear alias sets ", "\n");
2336 bitmap_print (dump_file
, disqualified_clear_alias_sets
,
2337 "disqualified clear alias sets ", "\n");
2340 memset (group
->offset_map_n
, 0, sizeof(int) * group
->offset_map_size_n
);
2341 memset (group
->offset_map_p
, 0, sizeof(int) * group
->offset_map_size_p
);
2342 bitmap_clear (group
->group_kill
);
2344 /* Remove the disqualified positions from the store2_p set. */
2345 bitmap_and_compl_into (group
->store2_p
, disqualified_clear_alias_sets
);
2347 /* We do not need to process the store2_n set because
2348 alias_sets are always positive. */
2349 EXECUTE_IF_SET_IN_BITMAP (group
->store2_p
, 0, j
, bi
)
2351 bitmap_set_bit (group
->group_kill
, current_position
);
2352 group
->offset_map_p
[j
] = current_position
++;
2353 group
->process_globally
= true;
2356 return current_position
!= 1;
2361 /*----------------------------------------------------------------------------
2364 Build the bit vectors for the transfer functions.
2365 ----------------------------------------------------------------------------*/
2368 /* Note that this is NOT a general purpose function. Any mem that has
2369 an alias set registered here expected to be COMPLETELY unaliased:
2370 i.e it's addresses are not and need not be examined.
2372 It is known that all references to this address will have this
2373 alias set and there are NO other references to this address in the
2376 Currently the only place that is known to be clean enough to use
2377 this interface is the code that assigns the spill locations.
2379 All of the mems that have alias_sets registered are subjected to a
2380 very powerful form of dse where function calls, volatile reads and
2381 writes, and reads from random location are not taken into account.
2383 It is also assumed that these locations go dead when the function
2384 returns. This assumption could be relaxed if there were found to
2385 be places that this assumption was not correct.
2387 The MODE is passed in and saved. The mode of each load or store to
2388 a mem with ALIAS_SET is checked against MEM. If the size of that
2389 load or store is different from MODE, processing is halted on this
2390 alias set. For the vast majority of aliases sets, all of the loads
2391 and stores will use the same mode. But vectors are treated
2392 differently: the alias set is established for the entire vector,
2393 but reload will insert loads and stores for individual elements and
2394 we do not necessarily have the information to track those separate
2395 elements. So when we see a mode mismatch, we just bail. */
2399 dse_record_singleton_alias_set (alias_set_type alias_set
,
2400 enum machine_mode mode
)
2402 struct clear_alias_mode_holder tmp_holder
;
2403 struct clear_alias_mode_holder
*entry
;
2406 /* If we are not going to run dse, we need to return now or there
2407 will be problems with allocating the bitmaps. */
2408 if ((!gate_dse()) || !alias_set
)
2411 if (!clear_alias_sets
)
2413 clear_alias_sets
= BITMAP_ALLOC (NULL
);
2414 disqualified_clear_alias_sets
= BITMAP_ALLOC (NULL
);
2415 clear_alias_mode_table
= htab_create (11, clear_alias_mode_hash
,
2416 clear_alias_mode_eq
, NULL
);
2417 clear_alias_mode_pool
= create_alloc_pool ("clear_alias_mode_pool",
2418 sizeof (struct clear_alias_mode_holder
), 100);
2421 bitmap_set_bit (clear_alias_sets
, alias_set
);
2423 tmp_holder
.alias_set
= alias_set
;
2425 slot
= htab_find_slot (clear_alias_mode_table
, &tmp_holder
, INSERT
);
2426 gcc_assert (*slot
== NULL
);
2428 *slot
= entry
= pool_alloc (clear_alias_mode_pool
);
2429 entry
->alias_set
= alias_set
;
2434 /* Remove ALIAS_SET from the sets of stack slots being considered. */
2437 dse_invalidate_singleton_alias_set (alias_set_type alias_set
)
2439 if ((!gate_dse()) || !alias_set
)
2442 bitmap_clear_bit (clear_alias_sets
, alias_set
);
2446 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
2450 get_bitmap_index (group_info_t group_info
, HOST_WIDE_INT offset
)
2454 HOST_WIDE_INT offset_p
= -offset
;
2455 if (offset_p
>= group_info
->offset_map_size_n
)
2457 return group_info
->offset_map_n
[offset_p
];
2461 if (offset
>= group_info
->offset_map_size_p
)
2463 return group_info
->offset_map_p
[offset
];
2468 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
2472 scan_stores_nospill (store_info_t store_info
, bitmap gen
, bitmap kill
)
2477 group_info_t group_info
2478 = VEC_index (group_info_t
, rtx_group_vec
, store_info
->group_id
);
2479 if (group_info
->process_globally
)
2480 for (i
= store_info
->begin
; i
< store_info
->end
; i
++)
2482 int index
= get_bitmap_index (group_info
, i
);
2485 bitmap_set_bit (gen
, index
);
2487 bitmap_clear_bit (kill
, index
);
2490 store_info
= store_info
->next
;
2495 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
2499 scan_stores_spill (store_info_t store_info
, bitmap gen
, bitmap kill
)
2503 if (store_info
->alias_set
)
2505 int index
= get_bitmap_index (clear_alias_group
,
2506 store_info
->alias_set
);
2509 bitmap_set_bit (gen
, index
);
2511 bitmap_clear_bit (kill
, index
);
2514 store_info
= store_info
->next
;
2519 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
2523 scan_reads_nospill (insn_info_t insn_info
, bitmap gen
, bitmap kill
)
2525 read_info_t read_info
= insn_info
->read_rec
;
2529 /* If this insn reads the frame, kill all the frame related stores. */
2530 if (insn_info
->frame_read
)
2532 for (i
= 0; VEC_iterate (group_info_t
, rtx_group_vec
, i
, group
); i
++)
2533 if (group
->process_globally
&& group
->frame_related
)
2536 bitmap_ior_into (kill
, group
->group_kill
);
2537 bitmap_and_compl_into (gen
, group
->group_kill
);
2543 for (i
= 0; VEC_iterate (group_info_t
, rtx_group_vec
, i
, group
); i
++)
2545 if (group
->process_globally
)
2547 if (i
== read_info
->group_id
)
2549 if (read_info
->begin
> read_info
->end
)
2551 /* Begin > end for block mode reads. */
2553 bitmap_ior_into (kill
, group
->group_kill
);
2554 bitmap_and_compl_into (gen
, group
->group_kill
);
2558 /* The groups are the same, just process the
2561 for (j
= read_info
->begin
; j
< read_info
->end
; j
++)
2563 int index
= get_bitmap_index (group
, j
);
2567 bitmap_set_bit (kill
, index
);
2568 bitmap_clear_bit (gen
, index
);
2575 /* The groups are different, if the alias sets
2576 conflict, clear the entire group. We only need
2577 to apply this test if the read_info is a cselib
2578 read. Anything with a constant base cannot alias
2579 something else with a different constant
2581 if ((read_info
->group_id
< 0)
2582 && canon_true_dependence (group
->base_mem
,
2584 group
->canon_base_mem
,
2585 read_info
->mem
, rtx_varies_p
))
2588 bitmap_ior_into (kill
, group
->group_kill
);
2589 bitmap_and_compl_into (gen
, group
->group_kill
);
2595 read_info
= read_info
->next
;
2599 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
2603 scan_reads_spill (read_info_t read_info
, bitmap gen
, bitmap kill
)
2607 if (read_info
->alias_set
)
2609 int index
= get_bitmap_index (clear_alias_group
,
2610 read_info
->alias_set
);
2614 bitmap_set_bit (kill
, index
);
2615 bitmap_clear_bit (gen
, index
);
2619 read_info
= read_info
->next
;
2624 /* Return the insn in BB_INFO before the first wild read or if there
2625 are no wild reads in the block, return the last insn. */
2628 find_insn_before_first_wild_read (bb_info_t bb_info
)
2630 insn_info_t insn_info
= bb_info
->last_insn
;
2631 insn_info_t last_wild_read
= NULL
;
2635 if (insn_info
->wild_read
)
2637 last_wild_read
= insn_info
->prev_insn
;
2638 /* Block starts with wild read. */
2639 if (!last_wild_read
)
2643 insn_info
= insn_info
->prev_insn
;
2647 return last_wild_read
;
2649 return bb_info
->last_insn
;
2653 /* Scan the insns in BB_INFO starting at PTR and going to the top of
2654 the block in order to build the gen and kill sets for the block.
2655 We start at ptr which may be the last insn in the block or may be
2656 the first insn with a wild read. In the latter case we are able to
2657 skip the rest of the block because it just does not matter:
2658 anything that happens is hidden by the wild read. */
2661 dse_step3_scan (bool for_spills
, basic_block bb
)
2663 bb_info_t bb_info
= bb_table
[bb
->index
];
2664 insn_info_t insn_info
;
2667 /* There are no wild reads in the spill case. */
2668 insn_info
= bb_info
->last_insn
;
2670 insn_info
= find_insn_before_first_wild_read (bb_info
);
2672 /* In the spill case or in the no_spill case if there is no wild
2673 read in the block, we will need a kill set. */
2674 if (insn_info
== bb_info
->last_insn
)
2677 bitmap_clear (bb_info
->kill
);
2679 bb_info
->kill
= BITMAP_ALLOC (NULL
);
2683 BITMAP_FREE (bb_info
->kill
);
2687 /* There may have been code deleted by the dce pass run before
2689 if (insn_info
->insn
&& INSN_P (insn_info
->insn
))
2691 /* Process the read(s) last. */
2694 scan_stores_spill (insn_info
->store_rec
, bb_info
->gen
, bb_info
->kill
);
2695 scan_reads_spill (insn_info
->read_rec
, bb_info
->gen
, bb_info
->kill
);
2699 scan_stores_nospill (insn_info
->store_rec
, bb_info
->gen
, bb_info
->kill
);
2700 scan_reads_nospill (insn_info
, bb_info
->gen
, bb_info
->kill
);
2704 insn_info
= insn_info
->prev_insn
;
2709 /* Set the gen set of the exit block, and also any block with no
2710 successors that does not have a wild read. */
2713 dse_step3_exit_block_scan (bb_info_t bb_info
)
2715 /* The gen set is all 0's for the exit block except for the
2716 frame_pointer_group. */
2718 if (stores_off_frame_dead_at_return
)
2723 for (i
= 0; VEC_iterate (group_info_t
, rtx_group_vec
, i
, group
); i
++)
2725 if (group
->process_globally
&& group
->frame_related
)
2726 bitmap_ior_into (bb_info
->gen
, group
->group_kill
);
2732 /* Find all of the blocks that are not backwards reachable from the
2733 exit block or any block with no successors (BB). These are the
2734 infinite loops or infinite self loops. These blocks will still
2735 have their bits set in UNREACHABLE_BLOCKS. */
2738 mark_reachable_blocks (sbitmap unreachable_blocks
, basic_block bb
)
2743 if (TEST_BIT (unreachable_blocks
, bb
->index
))
2745 RESET_BIT (unreachable_blocks
, bb
->index
);
2746 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2748 mark_reachable_blocks (unreachable_blocks
, e
->src
);
2753 /* Build the transfer functions for the function. */
2756 dse_step3 (bool for_spills
)
2759 sbitmap unreachable_blocks
= sbitmap_alloc (last_basic_block
);
2760 sbitmap_iterator sbi
;
2761 bitmap all_ones
= NULL
;
2764 sbitmap_ones (unreachable_blocks
);
2768 bb_info_t bb_info
= bb_table
[bb
->index
];
2770 bitmap_clear (bb_info
->gen
);
2772 bb_info
->gen
= BITMAP_ALLOC (NULL
);
2774 if (bb
->index
== ENTRY_BLOCK
)
2776 else if (bb
->index
== EXIT_BLOCK
)
2777 dse_step3_exit_block_scan (bb_info
);
2779 dse_step3_scan (for_spills
, bb
);
2780 if (EDGE_COUNT (bb
->succs
) == 0)
2781 mark_reachable_blocks (unreachable_blocks
, bb
);
2783 /* If this is the second time dataflow is run, delete the old
2786 BITMAP_FREE (bb_info
->in
);
2788 BITMAP_FREE (bb_info
->out
);
2791 /* For any block in an infinite loop, we must initialize the out set
2792 to all ones. This could be expensive, but almost never occurs in
2793 practice. However, it is common in regression tests. */
2794 EXECUTE_IF_SET_IN_SBITMAP (unreachable_blocks
, 0, i
, sbi
)
2796 if (bitmap_bit_p (all_blocks
, i
))
2798 bb_info_t bb_info
= bb_table
[i
];
2804 all_ones
= BITMAP_ALLOC (NULL
);
2805 for (j
= 0; VEC_iterate (group_info_t
, rtx_group_vec
, j
, group
); j
++)
2806 bitmap_ior_into (all_ones
, group
->group_kill
);
2810 bb_info
->out
= BITMAP_ALLOC (NULL
);
2811 bitmap_copy (bb_info
->out
, all_ones
);
2817 BITMAP_FREE (all_ones
);
2818 sbitmap_free (unreachable_blocks
);
2823 /*----------------------------------------------------------------------------
2826 Solve the bitvector equations.
2827 ----------------------------------------------------------------------------*/
2830 /* Confluence function for blocks with no successors. Create an out
2831 set from the gen set of the exit block. This block logically has
2832 the exit block as a successor. */
2837 dse_confluence_0 (basic_block bb
)
2839 bb_info_t bb_info
= bb_table
[bb
->index
];
2841 if (bb
->index
== EXIT_BLOCK
)
2846 bb_info
->out
= BITMAP_ALLOC (NULL
);
2847 bitmap_copy (bb_info
->out
, bb_table
[EXIT_BLOCK
]->gen
);
2851 /* Propagate the information from the in set of the dest of E to the
2852 out set of the src of E. If the various in or out sets are not
2853 there, that means they are all ones. */
2856 dse_confluence_n (edge e
)
2858 bb_info_t src_info
= bb_table
[e
->src
->index
];
2859 bb_info_t dest_info
= bb_table
[e
->dest
->index
];
2864 bitmap_and_into (src_info
->out
, dest_info
->in
);
2867 src_info
->out
= BITMAP_ALLOC (NULL
);
2868 bitmap_copy (src_info
->out
, dest_info
->in
);
2874 /* Propagate the info from the out to the in set of BB_INDEX's basic
2875 block. There are three cases:
2877 1) The block has no kill set. In this case the kill set is all
2878 ones. It does not matter what the out set of the block is, none of
2879 the info can reach the top. The only thing that reaches the top is
2880 the gen set and we just copy the set.
2882 2) There is a kill set but no out set and bb has successors. In
2883 this case we just return. Eventually an out set will be created and
2884 it is better to wait than to create a set of ones.
2886 3) There is both a kill and out set. We apply the obvious transfer
2891 dse_transfer_function (int bb_index
)
2893 bb_info_t bb_info
= bb_table
[bb_index
];
2901 return bitmap_ior_and_compl (bb_info
->in
, bb_info
->gen
,
2902 bb_info
->out
, bb_info
->kill
);
2905 bb_info
->in
= BITMAP_ALLOC (NULL
);
2906 bitmap_ior_and_compl (bb_info
->in
, bb_info
->gen
,
2907 bb_info
->out
, bb_info
->kill
);
2917 /* Case 1 above. If there is already an in set, nothing
2923 bb_info
->in
= BITMAP_ALLOC (NULL
);
2924 bitmap_copy (bb_info
->in
, bb_info
->gen
);
2930 /* Solve the dataflow equations. */
2935 df_simple_dataflow (DF_BACKWARD
, NULL
, dse_confluence_0
,
2936 dse_confluence_n
, dse_transfer_function
,
2937 all_blocks
, df_get_postorder (DF_BACKWARD
),
2938 df_get_n_blocks (DF_BACKWARD
));
2943 fprintf (dump_file
, "\n\n*** Global dataflow info after analysis.\n");
2946 bb_info_t bb_info
= bb_table
[bb
->index
];
2948 df_print_bb_index (bb
, dump_file
);
2950 bitmap_print (dump_file
, bb_info
->in
, " in: ", "\n");
2952 fprintf (dump_file
, " in: *MISSING*\n");
2954 bitmap_print (dump_file
, bb_info
->gen
, " gen: ", "\n");
2956 fprintf (dump_file
, " gen: *MISSING*\n");
2958 bitmap_print (dump_file
, bb_info
->kill
, " kill: ", "\n");
2960 fprintf (dump_file
, " kill: *MISSING*\n");
2962 bitmap_print (dump_file
, bb_info
->out
, " out: ", "\n");
2964 fprintf (dump_file
, " out: *MISSING*\n\n");
2971 /*----------------------------------------------------------------------------
2974 Delete the stores that can only be deleted using the global information.
2975 ----------------------------------------------------------------------------*/
2979 dse_step5_nospill (void)
2984 bb_info_t bb_info
= bb_table
[bb
->index
];
2985 insn_info_t insn_info
= bb_info
->last_insn
;
2986 bitmap v
= bb_info
->out
;
2990 bool deleted
= false;
2991 if (dump_file
&& insn_info
->insn
)
2993 fprintf (dump_file
, "starting to process insn %d\n",
2994 INSN_UID (insn_info
->insn
));
2995 bitmap_print (dump_file
, v
, " v: ", "\n");
2998 /* There may have been code deleted by the dce pass run before
3001 && INSN_P (insn_info
->insn
)
3002 && (!insn_info
->cannot_delete
)
3003 && (!bitmap_empty_p (v
)))
3005 store_info_t store_info
= insn_info
->store_rec
;
3007 /* Try to delete the current insn. */
3010 /* Skip the clobbers. */
3011 while (!store_info
->is_set
)
3012 store_info
= store_info
->next
;
3014 if (store_info
->alias_set
)
3019 group_info_t group_info
3020 = VEC_index (group_info_t
, rtx_group_vec
, store_info
->group_id
);
3022 for (i
= store_info
->begin
; i
< store_info
->end
; i
++)
3024 int index
= get_bitmap_index (group_info
, i
);
3027 fprintf (dump_file
, "i = %d, index = %d\n", (int)i
, index
);
3028 if (index
== 0 || !bitmap_bit_p (v
, index
))
3031 fprintf (dump_file
, "failing at i = %d\n", (int)i
);
3041 check_for_inc_dec (insn_info
->insn
);
3042 delete_insn (insn_info
->insn
);
3043 insn_info
->insn
= NULL
;
3048 /* We do want to process the local info if the insn was
3049 deleted. For instance, if the insn did a wild read, we
3050 no longer need to trash the info. */
3052 && INSN_P (insn_info
->insn
)
3055 scan_stores_nospill (insn_info
->store_rec
, v
, NULL
);
3056 if (insn_info
->wild_read
)
3059 fprintf (dump_file
, "wild read\n");
3062 else if (insn_info
->read_rec
)
3065 fprintf (dump_file
, "regular read\n");
3066 scan_reads_nospill (insn_info
, v
, NULL
);
3070 insn_info
= insn_info
->prev_insn
;
3077 dse_step5_spill (void)
3082 bb_info_t bb_info
= bb_table
[bb
->index
];
3083 insn_info_t insn_info
= bb_info
->last_insn
;
3084 bitmap v
= bb_info
->out
;
3088 bool deleted
= false;
3089 /* There may have been code deleted by the dce pass run before
3092 && INSN_P (insn_info
->insn
)
3093 && (!insn_info
->cannot_delete
)
3094 && (!bitmap_empty_p (v
)))
3096 /* Try to delete the current insn. */
3097 store_info_t store_info
= insn_info
->store_rec
;
3102 if (store_info
->alias_set
)
3104 int index
= get_bitmap_index (clear_alias_group
,
3105 store_info
->alias_set
);
3106 if (index
== 0 || !bitmap_bit_p (v
, index
))
3114 store_info
= store_info
->next
;
3116 if (deleted
&& dbg_cnt (dse
))
3119 fprintf (dump_file
, "Spill deleting insn %d\n",
3120 INSN_UID (insn_info
->insn
));
3121 check_for_inc_dec (insn_info
->insn
);
3122 delete_insn (insn_info
->insn
);
3124 insn_info
->insn
= NULL
;
3129 && INSN_P (insn_info
->insn
)
3132 scan_stores_spill (insn_info
->store_rec
, v
, NULL
);
3133 scan_reads_spill (insn_info
->read_rec
, v
, NULL
);
3136 insn_info
= insn_info
->prev_insn
;
3143 /*----------------------------------------------------------------------------
3146 Destroy everything left standing.
3147 ----------------------------------------------------------------------------*/
3150 dse_step6 (bool global_done
)
3158 for (i
= 0; VEC_iterate (group_info_t
, rtx_group_vec
, i
, group
); i
++)
3160 free (group
->offset_map_n
);
3161 free (group
->offset_map_p
);
3162 BITMAP_FREE (group
->store1_n
);
3163 BITMAP_FREE (group
->store1_p
);
3164 BITMAP_FREE (group
->store2_n
);
3165 BITMAP_FREE (group
->store2_p
);
3166 BITMAP_FREE (group
->group_kill
);
3171 bb_info_t bb_info
= bb_table
[bb
->index
];
3172 BITMAP_FREE (bb_info
->gen
);
3174 BITMAP_FREE (bb_info
->kill
);
3176 BITMAP_FREE (bb_info
->in
);
3178 BITMAP_FREE (bb_info
->out
);
3183 for (i
= 0; VEC_iterate (group_info_t
, rtx_group_vec
, i
, group
); i
++)
3185 BITMAP_FREE (group
->store1_n
);
3186 BITMAP_FREE (group
->store1_p
);
3187 BITMAP_FREE (group
->store2_n
);
3188 BITMAP_FREE (group
->store2_p
);
3189 BITMAP_FREE (group
->group_kill
);
3193 if (clear_alias_sets
)
3195 BITMAP_FREE (clear_alias_sets
);
3196 BITMAP_FREE (disqualified_clear_alias_sets
);
3197 free_alloc_pool (clear_alias_mode_pool
);
3198 htab_delete (clear_alias_mode_table
);
3201 end_alias_analysis ();
3203 htab_delete (rtx_group_table
);
3204 VEC_free (group_info_t
, heap
, rtx_group_vec
);
3205 BITMAP_FREE (all_blocks
);
3206 BITMAP_FREE (scratch
);
3208 free_alloc_pool (rtx_store_info_pool
);
3209 free_alloc_pool (read_info_pool
);
3210 free_alloc_pool (insn_info_pool
);
3211 free_alloc_pool (bb_info_pool
);
3212 free_alloc_pool (rtx_group_info_pool
);
3213 free_alloc_pool (deferred_change_pool
);
3218 /* -------------------------------------------------------------------------
3220 ------------------------------------------------------------------------- */
3222 /* Callback for running pass_rtl_dse. */
3225 rest_of_handle_dse (void)
3227 bool did_global
= false;
3229 df_set_flags (DF_DEFER_INSN_RESCAN
);
3234 if (dse_step2_nospill ())
3236 df_set_flags (DF_LR_RUN_DCE
);
3240 fprintf (dump_file
, "doing global processing\n");
3243 dse_step5_nospill ();
3246 /* For the instance of dse that runs after reload, we make a special
3247 pass to process the spills. These are special in that they are
3248 totally transparent, i.e, there is no aliasing issues that need
3249 to be considered. This means that the wild reads that kill
3250 everything else do not apply here. */
3251 if (clear_alias_sets
&& dse_step2_spill ())
3255 df_set_flags (DF_LR_RUN_DCE
);
3260 fprintf (dump_file
, "doing global spill processing\n");
3266 dse_step6 (did_global
);
3269 fprintf (dump_file
, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3270 locally_deleted
, globally_deleted
, spill_deleted
);
3277 return gate_dse1 () || gate_dse2 ();
3283 return optimize
> 0 && flag_dse
3290 return optimize
> 0 && flag_dse
3294 struct rtl_opt_pass pass_rtl_dse1
=
3299 gate_dse1
, /* gate */
3300 rest_of_handle_dse
, /* execute */
3303 0, /* static_pass_number */
3304 TV_DSE1
, /* tv_id */
3305 0, /* properties_required */
3306 0, /* properties_provided */
3307 0, /* properties_destroyed */
3308 0, /* todo_flags_start */
3310 TODO_df_finish
| TODO_verify_rtl_sharing
|
3311 TODO_ggc_collect
/* todo_flags_finish */
3315 struct rtl_opt_pass pass_rtl_dse2
=
3320 gate_dse2
, /* gate */
3321 rest_of_handle_dse
, /* execute */
3324 0, /* static_pass_number */
3325 TV_DSE2
, /* tv_id */
3326 0, /* properties_required */
3327 0, /* properties_provided */
3328 0, /* properties_destroyed */
3329 0, /* todo_flags_start */
3331 TODO_df_finish
| TODO_verify_rtl_sharing
|
3332 TODO_ggc_collect
/* todo_flags_finish */