1 /* RTL dead store elimination.
2 Copyright (C) 2005, 2006, 2007, 2008 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
94 6) Delete insns that store the same value as preceeding store
95 where the earlier store couldn't be eliminated.
99 This step uses cselib and canon_rtx to build the largest expression
100 possible for each address. This pass is a forwards pass through
101 each basic block. From the point of view of the global technique,
102 the first pass could examine a block in either direction. The
103 forwards ordering is to accommodate cselib.
105 We a simplifying assumption: addresses fall into four broad
108 1) base has rtx_varies_p == false, offset is constant.
109 2) base has rtx_varies_p == false, offset variable.
110 3) base has rtx_varies_p == true, offset constant.
111 4) base has rtx_varies_p == true, offset variable.
113 The local passes are able to process all 4 kinds of addresses. The
114 global pass only handles (1).
116 The global problem is formulated as follows:
118 A store, S1, to address A, where A is not relative to the stack
119 frame, can be eliminated if all paths from S1 to the end of the
120 of the function contain another store to A before a read to A.
122 If the address A is relative to the stack frame, a store S2 to A
123 can be eliminated if there are no paths from S1 that reach the
124 end of the function that read A before another store to A. In
125 this case S2 can be deleted if there are paths to from S2 to the
126 end of the function that have no reads or writes to A. This
127 second case allows stores to the stack frame to be deleted that
128 would otherwise die when the function returns. This cannot be
129 done if stores_off_frame_dead_at_return is not true. See the doc
130 for that variable for when this variable is false.
132 The global problem is formulated as a backwards set union
133 dataflow problem where the stores are the gens and reads are the
134 kills. Set union problems are rare and require some special
135 handling given our representation of bitmaps. A straightforward
136 implementation of requires a lot of bitmaps filled with 1s.
137 These are expensive and cumbersome in our bitmap formulation so
138 care has been taken to avoid large vectors filled with 1s. See
139 the comments in bb_info and in the dataflow confluence functions
142 There are two places for further enhancements to this algorithm:
144 1) The original dse which was embedded in a pass called flow also
145 did local address forwarding. For example in
150 flow would replace the right hand side of the second insn with a
151 reference to r100. Most of the information is available to add this
152 to this pass. It has not done it because it is a lot of work in
153 the case that either r100 is assigned to between the first and
154 second insn and/or the second insn is a load of part of the value
155 stored by the first insn.
157 insn 5 in gcc.c-torture/compile/990203-1.c simple case.
158 insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
159 insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
160 insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
162 2) The cleaning up of spill code is quite profitable. It currently
163 depends on reading tea leaves and chicken entrails left by reload.
164 This pass depends on reload creating a singleton alias set for each
165 spill slot and telling the next dse pass which of these alias sets
166 are the singletons. Rather than analyze the addresses of the
167 spills, dse's spill processing just does analysis of the loads and
168 stores that use those alias sets. There are three cases where this
171 a) Reload sometimes creates the slot for one mode of access, and
172 then inserts loads and/or stores for a smaller mode. In this
173 case, the current code just punts on the slot. The proper thing
174 to do is to back out and use one bit vector position for each
175 byte of the entity associated with the slot. This depends on
176 KNOWING that reload always generates the accesses for each of the
177 bytes in some canonical (read that easy to understand several
178 passes after reload happens) way.
180 b) Reload sometimes decides that spill slot it allocated was not
181 large enough for the mode and goes back and allocates more slots
182 with the same mode and alias set. The backout in this case is a
183 little more graceful than (a). In this case the slot is unmarked
184 as being a spill slot and if final address comes out to be based
185 off the frame pointer, the global algorithm handles this slot.
187 c) For any pass that may prespill, there is currently no
188 mechanism to tell the dse pass that the slot being used has the
189 special properties that reload uses. It may be that all that is
190 required is to have those passes make the same calls that reload
191 does, assuming that the alias sets can be manipulated in the same
194 /* There are limits to the size of constant offsets we model for the
195 global problem. There are certainly test cases, that exceed this
196 limit, however, it is unlikely that there are important programs
197 that really have constant offsets this size. */
198 #define MAX_OFFSET (64 * 1024)
201 static bitmap scratch = NULL;
204 /* This structure holds information about a candidate store. */
208 /* False means this is a clobber. */
211 /* False if a single HOST_WIDE_INT bitmap is used for positions_needed. */
214 /* The id of the mem group of the base address. If rtx_varies_p is
215 true, this is -1. Otherwise, it is the index into the group
219 /* This is the cselib value. */
220 cselib_val *cse_base;
222 /* This canonized mem. */
225 /* The result of get_addr on mem. */
228 /* If this is non-zero, it is the alias set of a spill location. */
229 alias_set_type alias_set;
231 /* The offset of the first and byte before the last byte associated
232 with the operation. */
233 HOST_WIDE_INT begin, end;
237 /* A bitmask as wide as the number of bytes in the word that
238 contains a 1 if the byte may be needed. The store is unused if
239 all of the bits are 0. This is used if IS_LARGE is false. */
240 unsigned HOST_WIDE_INT small_bitmask;
244 /* A bitmap with one bit per byte. Cleared bit means the position
245 is needed. Used if IS_LARGE is false. */
248 /* Number of set bits (i.e. unneeded bytes) in BITMAP. If it is
249 equal to END - BEGIN, the whole store is unused. */
254 /* The next store info for this insn. */
255 struct store_info *next;
257 /* The right hand side of the store. This is used if there is a
258 subsequent reload of the mems address somewhere later in the
262 /* If rhs is or holds a constant, this contains that constant,
266 /* Set if this store stores the same constant value as REDUNDANT_REASON
267 insn stored. These aren't eliminated early, because doing that
268 might prevent the earlier larger store to be eliminated. */
269 struct insn_info *redundant_reason;
272 /* Return a bitmask with the first N low bits set. */
274 static unsigned HOST_WIDE_INT
275 lowpart_bitmask (int n)
277 unsigned HOST_WIDE_INT mask = ~(unsigned HOST_WIDE_INT) 0;
278 return mask >> (HOST_BITS_PER_WIDE_INT - n);
281 typedef struct store_info *store_info_t;
282 static alloc_pool cse_store_info_pool;
283 static alloc_pool rtx_store_info_pool;
285 /* This structure holds information about a load. These are only
286 built for rtx bases. */
289 /* The id of the mem group of the base address. */
292 /* If this is non-zero, it is the alias set of a spill location. */
293 alias_set_type alias_set;
295 /* The offset of the first and byte after the last byte associated
296 with the operation. If begin == end == 0, the read did not have
297 a constant offset. */
300 /* The mem being read. */
303 /* The next read_info for this insn. */
304 struct read_info *next;
306 typedef struct read_info *read_info_t;
307 static alloc_pool read_info_pool;
310 /* One of these records is created for each insn. */
314 /* Set true if the insn contains a store but the insn itself cannot
315 be deleted. This is set if the insn is a parallel and there is
316 more than one non dead output or if the insn is in some way
320 /* This field is only used by the global algorithm. It is set true
321 if the insn contains any read of mem except for a (1). This is
322 also set if the insn is a call or has a clobber mem. If the insn
323 contains a wild read, the use_rec will be null. */
326 /* This field is only used for the processing of const functions.
327 These functions cannot read memory, but they can read the stack
328 because that is where they may get their parms. We need to be
329 this conservative because, like the store motion pass, we don't
330 consider CALL_INSN_FUNCTION_USAGE when processing call insns.
331 Moreover, we need to distinguish two cases:
332 1. Before reload (register elimination), the stores related to
333 outgoing arguments are stack pointer based and thus deemed
334 of non-constant base in this pass. This requires special
335 handling but also means that the frame pointer based stores
336 need not be killed upon encountering a const function call.
337 2. After reload, the stores related to outgoing arguments can be
338 either stack pointer or hard frame pointer based. This means
339 that we have no other choice than also killing all the frame
340 pointer based stores upon encountering a const function call.
341 This field is set after reload for const function calls. Having
342 this set is less severe than a wild read, it just means that all
343 the frame related stores are killed rather than all the stores. */
346 /* This field is only used for the processing of const functions.
347 It is set if the insn may contain a stack pointer based store. */
348 bool stack_pointer_based;
350 /* This is true if any of the sets within the store contains a
351 cselib base. Such stores can only be deleted by the local
353 bool contains_cselib_groups;
358 /* The list of mem sets or mem clobbers that are contained in this
359 insn. If the insn is deletable, it contains only one mem set.
360 But it could also contain clobbers. Insns that contain more than
361 one mem set are not deletable, but each of those mems are here in
362 order to provide info to delete other insns. */
363 store_info_t store_rec;
365 /* The linked list of mem uses in this insn. Only the reads from
366 rtx bases are listed here. The reads to cselib bases are
367 completely processed during the first scan and so are never
369 read_info_t read_rec;
371 /* The prev insn in the basic block. */
372 struct insn_info * prev_insn;
374 /* The linked list of insns that are in consideration for removal in
375 the forwards pass thru the basic block. This pointer may be
376 trash as it is not cleared when a wild read occurs. The only
377 time it is guaranteed to be correct is when the traversal starts
378 at active_local_stores. */
379 struct insn_info * next_local_store;
382 typedef struct insn_info *insn_info_t;
383 static alloc_pool insn_info_pool;
385 /* The linked list of stores that are under consideration in this
387 static insn_info_t active_local_stores;
392 /* Pointer to the insn info for the last insn in the block. These
393 are linked so this is how all of the insns are reached. During
394 scanning this is the current insn being scanned. */
395 insn_info_t last_insn;
397 /* The info for the global dataflow problem. */
400 /* This is set if the transfer function should and in the wild_read
401 bitmap before applying the kill and gen sets. That vector knocks
402 out most of the bits in the bitmap and thus speeds up the
404 bool apply_wild_read;
406 /* The following 4 bitvectors hold information about which positions
407 of which stores are live or dead. They are indexed by
410 /* The set of store positions that exist in this block before a wild read. */
413 /* The set of load positions that exist in this block above the
414 same position of a store. */
417 /* The set of stores that reach the top of the block without being
420 Do not represent the in if it is all ones. Note that this is
421 what the bitvector should logically be initialized to for a set
422 intersection problem. However, like the kill set, this is too
423 expensive. So initially, the in set will only be created for the
424 exit block and any block that contains a wild read. */
427 /* The set of stores that reach the bottom of the block from it's
430 Do not represent the in if it is all ones. Note that this is
431 what the bitvector should logically be initialized to for a set
432 intersection problem. However, like the kill and in set, this is
433 too expensive. So what is done is that the confluence operator
434 just initializes the vector from one of the out sets of the
435 successors of the block. */
438 /* The following bitvector is indexed by the reg number. It
439 contains the set of regs that are live at the current instruction
440 being processed. While it contains info for all of the
441 registers, only the pseudos are actually examined. It is used to
442 assure that shift sequences that are inserted do not accidently
443 clobber live hard regs. */
447 typedef struct bb_info *bb_info_t;
448 static alloc_pool bb_info_pool;
450 /* Table to hold all bb_infos. */
451 static bb_info_t *bb_table;
453 /* There is a group_info for each rtx base that is used to reference
454 memory. There are also not many of the rtx bases because they are
455 very limited in scope. */
459 /* The actual base of the address. */
462 /* The sequential id of the base. This allows us to have a
463 canonical ordering of these that is not based on addresses. */
466 /* A mem wrapped around the base pointer for the group in order to
467 do read dependency. */
470 /* Canonized version of base_mem, most likely the same thing. */
473 /* These two sets of two bitmaps are used to keep track of how many
474 stores are actually referencing that position from this base. We
475 only do this for rtx bases as this will be used to assign
476 positions in the bitmaps for the global problem. Bit N is set in
477 store1 on the first store for offset N. Bit N is set in store2
478 for the second store to offset N. This is all we need since we
479 only care about offsets that have two or more stores for them.
481 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
482 for 0 and greater offsets.
484 There is one special case here, for stores into the stack frame,
485 we will or store1 into store2 before deciding which stores look
486 at globally. This is because stores to the stack frame that have
487 no other reads before the end of the function can also be
489 bitmap store1_n, store1_p, store2_n, store2_p;
491 /* The positions in this bitmap have the same assignments as the in,
492 out, gen and kill bitmaps. This bitmap is all zeros except for
493 the positions that are occupied by stores for this group. */
496 /* True if there are any positions that are to be processed
498 bool process_globally;
500 /* True if the base of this group is either the frame_pointer or
501 hard_frame_pointer. */
504 /* The offset_map is used to map the offsets from this base into
505 positions in the global bitmaps. It is only created after all of
506 the all of stores have been scanned and we know which ones we
508 int *offset_map_n, *offset_map_p;
509 int offset_map_size_n, offset_map_size_p;
511 typedef struct group_info *group_info_t;
512 typedef const struct group_info *const_group_info_t;
513 static alloc_pool rtx_group_info_pool;
515 /* Tables of group_info structures, hashed by base value. */
516 static htab_t rtx_group_table;
518 /* Index into the rtx_group_vec. */
519 static int rtx_group_next_id;
521 DEF_VEC_P(group_info_t);
522 DEF_VEC_ALLOC_P(group_info_t,heap);
524 static VEC(group_info_t,heap) *rtx_group_vec;
527 /* This structure holds the set of changes that are being deferred
528 when removing read operation. See replace_read. */
529 struct deferred_change
532 /* The mem that is being replaced. */
535 /* The reg it is being replaced with. */
538 struct deferred_change *next;
541 typedef struct deferred_change *deferred_change_t;
542 static alloc_pool deferred_change_pool;
544 static deferred_change_t deferred_change_list = NULL;
546 /* This are used to hold the alias sets of spill variables. Since
547 these are never aliased and there may be a lot of them, it makes
548 sense to treat them specially. This bitvector is only allocated in
549 calls from dse_record_singleton_alias_set which currently is only
550 made during reload1. So when dse is called before reload this
551 mechanism does nothing. */
553 static bitmap clear_alias_sets = NULL;
555 /* The set of clear_alias_sets that have been disqualified because
556 there are loads or stores using a different mode than the alias set
557 was registered with. */
558 static bitmap disqualified_clear_alias_sets = NULL;
560 /* The group that holds all of the clear_alias_sets. */
561 static group_info_t clear_alias_group;
563 /* The modes of the clear_alias_sets. */
564 static htab_t clear_alias_mode_table;
566 /* Hash table element to look up the mode for an alias set. */
567 struct clear_alias_mode_holder
569 alias_set_type alias_set;
570 enum machine_mode mode;
573 static alloc_pool clear_alias_mode_pool;
575 /* This is true except if cfun->stdarg -- i.e. we cannot do
576 this for vararg functions because they play games with the frame. */
577 static bool stores_off_frame_dead_at_return;
579 /* Counter for stats. */
580 static int globally_deleted;
581 static int locally_deleted;
582 static int spill_deleted;
584 static bitmap all_blocks;
586 /* The number of bits used in the global bitmaps. */
587 static unsigned int current_position;
590 static bool gate_dse (void);
591 static bool gate_dse1 (void);
592 static bool gate_dse2 (void);
595 /*----------------------------------------------------------------------------
599 ----------------------------------------------------------------------------*/
601 /* Hashtable callbacks for maintaining the "bases" field of
602 store_group_info, given that the addresses are function invariants. */
605 clear_alias_mode_eq (const void *p1, const void *p2)
607 const struct clear_alias_mode_holder * h1
608 = (const struct clear_alias_mode_holder *) p1;
609 const struct clear_alias_mode_holder * h2
610 = (const struct clear_alias_mode_holder *) p2;
611 return h1->alias_set == h2->alias_set;
616 clear_alias_mode_hash (const void *p)
618 const struct clear_alias_mode_holder *holder
619 = (const struct clear_alias_mode_holder *) p;
620 return holder->alias_set;
624 /* Find the entry associated with ALIAS_SET. */
626 static struct clear_alias_mode_holder *
627 clear_alias_set_lookup (alias_set_type alias_set)
629 struct clear_alias_mode_holder tmp_holder;
632 tmp_holder.alias_set = alias_set;
633 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, NO_INSERT);
636 return (struct clear_alias_mode_holder *) *slot;
640 /* Hashtable callbacks for maintaining the "bases" field of
641 store_group_info, given that the addresses are function invariants. */
644 invariant_group_base_eq (const void *p1, const void *p2)
646 const_group_info_t gi1 = (const_group_info_t) p1;
647 const_group_info_t gi2 = (const_group_info_t) p2;
648 return rtx_equal_p (gi1->rtx_base, gi2->rtx_base);
653 invariant_group_base_hash (const void *p)
655 const_group_info_t gi = (const_group_info_t) p;
657 return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false);
661 /* Get the GROUP for BASE. Add a new group if it is not there. */
664 get_group_info (rtx base)
666 struct group_info tmp_gi;
672 /* Find the store_base_info structure for BASE, creating a new one
674 tmp_gi.rtx_base = base;
675 slot = htab_find_slot (rtx_group_table, &tmp_gi, INSERT);
676 gi = (group_info_t) *slot;
680 if (!clear_alias_group)
682 clear_alias_group = gi =
683 (group_info_t) pool_alloc (rtx_group_info_pool);
684 memset (gi, 0, sizeof (struct group_info));
685 gi->id = rtx_group_next_id++;
686 gi->store1_n = BITMAP_ALLOC (NULL);
687 gi->store1_p = BITMAP_ALLOC (NULL);
688 gi->store2_n = BITMAP_ALLOC (NULL);
689 gi->store2_p = BITMAP_ALLOC (NULL);
690 gi->group_kill = BITMAP_ALLOC (NULL);
691 gi->process_globally = false;
692 gi->offset_map_size_n = 0;
693 gi->offset_map_size_p = 0;
694 gi->offset_map_n = NULL;
695 gi->offset_map_p = NULL;
696 VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);
698 return clear_alias_group;
703 *slot = gi = (group_info_t) pool_alloc (rtx_group_info_pool);
705 gi->id = rtx_group_next_id++;
706 gi->base_mem = gen_rtx_MEM (QImode, base);
707 gi->canon_base_mem = canon_rtx (gi->base_mem);
708 gi->store1_n = BITMAP_ALLOC (NULL);
709 gi->store1_p = BITMAP_ALLOC (NULL);
710 gi->store2_n = BITMAP_ALLOC (NULL);
711 gi->store2_p = BITMAP_ALLOC (NULL);
712 gi->group_kill = BITMAP_ALLOC (NULL);
713 gi->process_globally = false;
715 (base == frame_pointer_rtx) || (base == hard_frame_pointer_rtx);
716 gi->offset_map_size_n = 0;
717 gi->offset_map_size_p = 0;
718 gi->offset_map_n = NULL;
719 gi->offset_map_p = NULL;
720 VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);
727 /* Initialization of data structures. */
733 globally_deleted = 0;
736 scratch = BITMAP_ALLOC (NULL);
739 = create_alloc_pool ("rtx_store_info_pool",
740 sizeof (struct store_info), 100);
742 = create_alloc_pool ("read_info_pool",
743 sizeof (struct read_info), 100);
745 = create_alloc_pool ("insn_info_pool",
746 sizeof (struct insn_info), 100);
748 = create_alloc_pool ("bb_info_pool",
749 sizeof (struct bb_info), 100);
751 = create_alloc_pool ("rtx_group_info_pool",
752 sizeof (struct group_info), 100);
754 = create_alloc_pool ("deferred_change_pool",
755 sizeof (struct deferred_change), 10);
757 rtx_group_table = htab_create (11, invariant_group_base_hash,
758 invariant_group_base_eq, NULL);
760 bb_table = XCNEWVEC (bb_info_t, last_basic_block);
761 rtx_group_next_id = 0;
763 stores_off_frame_dead_at_return = !cfun->stdarg;
765 init_alias_analysis ();
767 if (clear_alias_sets)
768 clear_alias_group = get_group_info (NULL);
770 clear_alias_group = NULL;
775 /*----------------------------------------------------------------------------
778 Scan all of the insns. Any random ordering of the blocks is fine.
779 Each block is scanned in forward order to accommodate cselib which
780 is used to remove stores with non-constant bases.
781 ----------------------------------------------------------------------------*/
783 /* Delete all of the store_info recs from INSN_INFO. */
786 free_store_info (insn_info_t insn_info)
788 store_info_t store_info = insn_info->store_rec;
791 store_info_t next = store_info->next;
792 if (store_info->is_large)
793 BITMAP_FREE (store_info->positions_needed.large.bitmap);
794 if (store_info->cse_base)
795 pool_free (cse_store_info_pool, store_info);
797 pool_free (rtx_store_info_pool, store_info);
801 insn_info->cannot_delete = true;
802 insn_info->contains_cselib_groups = false;
803 insn_info->store_rec = NULL;
813 /* Add an insn to do the add inside a x if it is a
814 PRE/POST-INC/DEC/MODIFY. D is an structure containing the insn and
815 the size of the mode of the MEM that this is inside of. */
818 replace_inc_dec (rtx *r, void *d)
821 struct insn_size *data = (struct insn_size *)d;
822 switch (GET_CODE (x))
827 rtx r1 = XEXP (x, 0);
828 rtx c = gen_int_mode (Pmode, data->size);
829 emit_insn_before (gen_rtx_SET (Pmode, r1,
830 gen_rtx_PLUS (Pmode, r1, c)),
838 rtx r1 = XEXP (x, 0);
839 rtx c = gen_int_mode (Pmode, -data->size);
840 emit_insn_before (gen_rtx_SET (Pmode, r1,
841 gen_rtx_PLUS (Pmode, r1, c)),
849 /* We can reuse the add because we are about to delete the
850 insn that contained it. */
851 rtx add = XEXP (x, 0);
852 rtx r1 = XEXP (add, 0);
853 emit_insn_before (gen_rtx_SET (Pmode, r1, add), data->insn);
863 /* If X is a MEM, check the address to see if it is PRE/POST-INC/DEC/MODIFY
864 and generate an add to replace that. */
867 replace_inc_dec_mem (rtx *r, void *d)
870 if (x != NULL_RTX && MEM_P (x))
872 struct insn_size data;
874 data.size = GET_MODE_SIZE (GET_MODE (x));
877 for_each_rtx (&XEXP (x, 0), replace_inc_dec, &data);
884 /* Before we delete INSN, make sure that the auto inc/dec, if it is
885 there, is split into a separate insn. */
888 check_for_inc_dec (rtx insn)
890 rtx note = find_reg_note (insn, REG_INC, NULL_RTX);
892 for_each_rtx (&insn, replace_inc_dec_mem, insn);
896 /* Delete the insn and free all of the fields inside INSN_INFO. */
899 delete_dead_store_insn (insn_info_t insn_info)
901 read_info_t read_info;
906 check_for_inc_dec (insn_info->insn);
909 fprintf (dump_file, "Locally deleting insn %d ",
910 INSN_UID (insn_info->insn));
911 if (insn_info->store_rec->alias_set)
912 fprintf (dump_file, "alias set %d\n",
913 (int) insn_info->store_rec->alias_set);
915 fprintf (dump_file, "\n");
918 free_store_info (insn_info);
919 read_info = insn_info->read_rec;
923 read_info_t next = read_info->next;
924 pool_free (read_info_pool, read_info);
927 insn_info->read_rec = NULL;
929 delete_insn (insn_info->insn);
931 insn_info->insn = NULL;
933 insn_info->wild_read = false;
937 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
941 set_usage_bits (group_info_t group, HOST_WIDE_INT offset, HOST_WIDE_INT width)
945 if (offset > -MAX_OFFSET && offset + width < MAX_OFFSET)
946 for (i=offset; i<offset+width; i++)
953 store1 = group->store1_n;
954 store2 = group->store2_n;
959 store1 = group->store1_p;
960 store2 = group->store2_p;
964 if (bitmap_bit_p (store1, ai))
965 bitmap_set_bit (store2, ai);
968 bitmap_set_bit (store1, ai);
971 if (group->offset_map_size_n < ai)
972 group->offset_map_size_n = ai;
976 if (group->offset_map_size_p < ai)
977 group->offset_map_size_p = ai;
984 /* Set the BB_INFO so that the last insn is marked as a wild read. */
987 add_wild_read (bb_info_t bb_info)
989 insn_info_t insn_info = bb_info->last_insn;
990 read_info_t *ptr = &insn_info->read_rec;
994 read_info_t next = (*ptr)->next;
995 if ((*ptr)->alias_set == 0)
997 pool_free (read_info_pool, *ptr);
1001 ptr = &(*ptr)->next;
1003 insn_info->wild_read = true;
1004 active_local_stores = NULL;
1008 /* Return true if X is a constant or one of the registers that behave
1009 as a constant over the life of a function. This is equivalent to
1010 !rtx_varies_p for memory addresses. */
1013 const_or_frame_p (rtx x)
1015 switch (GET_CODE (x))
1018 return MEM_READONLY_P (x);
1029 /* Note that we have to test for the actual rtx used for the frame
1030 and arg pointers and not just the register number in case we have
1031 eliminated the frame and/or arg pointer and are using it
1033 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
1034 /* The arg pointer varies if it is not a fixed register. */
1035 || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
1036 || x == pic_offset_table_rtx)
1045 /* Take all reasonable action to put the address of MEM into the form
1046 that we can do analysis on.
1048 The gold standard is to get the address into the form: address +
1049 OFFSET where address is something that rtx_varies_p considers a
1050 constant. When we can get the address in this form, we can do
1051 global analysis on it. Note that for constant bases, address is
1052 not actually returned, only the group_id. The address can be
1055 If that fails, we try cselib to get a value we can at least use
1056 locally. If that fails we return false.
1058 The GROUP_ID is set to -1 for cselib bases and the index of the
1059 group for non_varying bases.
1061 FOR_READ is true if this is a mem read and false if not. */
1064 canon_address (rtx mem,
1065 alias_set_type *alias_set_out,
1067 HOST_WIDE_INT *offset,
1070 rtx mem_address = XEXP (mem, 0);
1071 rtx expanded_address, address;
1072 /* Make sure that cselib is has initialized all of the operands of
1073 the address before asking it to do the subst. */
1075 if (clear_alias_sets)
1077 /* If this is a spill, do not do any further processing. */
1078 alias_set_type alias_set = MEM_ALIAS_SET (mem);
1080 fprintf (dump_file, "found alias set %d\n", (int) alias_set);
1081 if (bitmap_bit_p (clear_alias_sets, alias_set))
1083 struct clear_alias_mode_holder *entry
1084 = clear_alias_set_lookup (alias_set);
1086 /* If the modes do not match, we cannot process this set. */
1087 if (entry->mode != GET_MODE (mem))
1091 "disqualifying alias set %d, (%s) != (%s)\n",
1092 (int) alias_set, GET_MODE_NAME (entry->mode),
1093 GET_MODE_NAME (GET_MODE (mem)));
1095 bitmap_set_bit (disqualified_clear_alias_sets, alias_set);
1099 *alias_set_out = alias_set;
1100 *group_id = clear_alias_group->id;
1107 cselib_lookup (mem_address, Pmode, 1);
1111 fprintf (dump_file, " mem: ");
1112 print_inline_rtx (dump_file, mem_address, 0);
1113 fprintf (dump_file, "\n");
1116 /* Use cselib to replace all of the reg references with the full
1117 expression. This will take care of the case where we have
1119 r_x = base + offset;
1124 val = *(base + offset);
1127 expanded_address = cselib_expand_value_rtx (mem_address, scratch, 5);
1129 /* If this fails, just go with the mem_address. */
1130 if (!expanded_address)
1131 expanded_address = mem_address;
1133 /* Split the address into canonical BASE + OFFSET terms. */
1134 address = canon_rtx (expanded_address);
1140 fprintf (dump_file, "\n after cselib_expand address: ");
1141 print_inline_rtx (dump_file, expanded_address, 0);
1142 fprintf (dump_file, "\n");
1144 fprintf (dump_file, "\n after canon_rtx address: ");
1145 print_inline_rtx (dump_file, address, 0);
1146 fprintf (dump_file, "\n");
1149 if (GET_CODE (address) == CONST)
1150 address = XEXP (address, 0);
1152 if (GET_CODE (address) == PLUS && GET_CODE (XEXP (address, 1)) == CONST_INT)
1154 *offset = INTVAL (XEXP (address, 1));
1155 address = XEXP (address, 0);
1158 if (const_or_frame_p (address))
1160 group_info_t group = get_group_info (address);
1163 fprintf (dump_file, " gid=%d offset=%d \n", group->id, (int)*offset);
1165 *group_id = group->id;
1169 *base = cselib_lookup (address, Pmode, true);
1175 fprintf (dump_file, " no cselib val - should be a wild read.\n");
1179 fprintf (dump_file, " varying cselib base=%d offset = %d\n",
1180 (*base)->value, (int)*offset);
1186 /* Clear the rhs field from the active_local_stores array. */
1189 clear_rhs_from_active_local_stores (void)
1191 insn_info_t ptr = active_local_stores;
1195 store_info_t store_info = ptr->store_rec;
1196 /* Skip the clobbers. */
1197 while (!store_info->is_set)
1198 store_info = store_info->next;
1200 store_info->rhs = NULL;
1201 store_info->const_rhs = NULL;
1203 ptr = ptr->next_local_store;
1208 /* Mark byte POS bytes from the beginning of store S_INFO as unneeded. */
1211 set_position_unneeded (store_info_t s_info, int pos)
1213 if (__builtin_expect (s_info->is_large, false))
1215 if (!bitmap_bit_p (s_info->positions_needed.large.bitmap, pos))
1217 s_info->positions_needed.large.count++;
1218 bitmap_set_bit (s_info->positions_needed.large.bitmap, pos);
1222 s_info->positions_needed.small_bitmask
1223 &= ~(((unsigned HOST_WIDE_INT) 1) << pos);
1226 /* Mark the whole store S_INFO as unneeded. */
1229 set_all_positions_unneeded (store_info_t s_info)
1231 if (__builtin_expect (s_info->is_large, false))
1233 int pos, end = s_info->end - s_info->begin;
1234 for (pos = 0; pos < end; pos++)
1235 bitmap_set_bit (s_info->positions_needed.large.bitmap, pos);
1236 s_info->positions_needed.large.count = end;
1239 s_info->positions_needed.small_bitmask = (unsigned HOST_WIDE_INT) 0;
1242 /* Return TRUE if any bytes from S_INFO store are needed. */
1245 any_positions_needed_p (store_info_t s_info)
1247 if (__builtin_expect (s_info->is_large, false))
1248 return (s_info->positions_needed.large.count
1249 < s_info->end - s_info->begin);
1251 return (s_info->positions_needed.small_bitmask
1252 != (unsigned HOST_WIDE_INT) 0);
1255 /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
1256 store are needed. */
1259 all_positions_needed_p (store_info_t s_info, int start, int width)
1261 if (__builtin_expect (s_info->is_large, false))
1263 int end = start + width;
1265 if (bitmap_bit_p (s_info->positions_needed.large.bitmap, start++))
1271 unsigned HOST_WIDE_INT mask = lowpart_bitmask (width) << start;
1272 return (s_info->positions_needed.small_bitmask & mask) == mask;
1277 static rtx get_stored_val (store_info_t, enum machine_mode, HOST_WIDE_INT,
1278 HOST_WIDE_INT, basic_block, bool);
1281 /* BODY is an instruction pattern that belongs to INSN. Return 1 if
1282 there is a candidate store, after adding it to the appropriate
1283 local store group if so. */
1286 record_store (rtx body, bb_info_t bb_info)
1288 rtx mem, rhs, const_rhs;
1289 HOST_WIDE_INT offset = 0;
1290 HOST_WIDE_INT width = 0;
1291 alias_set_type spill_alias_set;
1292 insn_info_t insn_info = bb_info->last_insn;
1293 store_info_t store_info = NULL;
1295 cselib_val *base = NULL;
1296 insn_info_t ptr, last, redundant_reason;
1297 bool store_is_unused;
1299 if (GET_CODE (body) != SET && GET_CODE (body) != CLOBBER)
1302 mem = SET_DEST (body);
1304 /* If this is not used, then this cannot be used to keep the insn
1305 from being deleted. On the other hand, it does provide something
1306 that can be used to prove that another store is dead. */
1308 = (find_reg_note (insn_info->insn, REG_UNUSED, mem) != NULL);
1310 /* Check whether that value is a suitable memory location. */
1313 /* If the set or clobber is unused, then it does not effect our
1314 ability to get rid of the entire insn. */
1315 if (!store_is_unused)
1316 insn_info->cannot_delete = true;
1320 /* At this point we know mem is a mem. */
1321 if (GET_MODE (mem) == BLKmode)
1323 if (GET_CODE (XEXP (mem, 0)) == SCRATCH)
1326 fprintf (dump_file, " adding wild read for (clobber (mem:BLK (scratch))\n");
1327 add_wild_read (bb_info);
1328 insn_info->cannot_delete = true;
1331 /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
1332 as memset (addr, 0, 36); */
1333 else if (!MEM_SIZE (mem)
1334 || !CONST_INT_P (MEM_SIZE (mem))
1335 || GET_CODE (body) != SET
1336 || INTVAL (MEM_SIZE (mem)) <= 0
1337 || INTVAL (MEM_SIZE (mem)) > MAX_OFFSET
1338 || !CONST_INT_P (SET_SRC (body)))
1340 if (!store_is_unused)
1342 /* If the set or clobber is unused, then it does not effect our
1343 ability to get rid of the entire insn. */
1344 insn_info->cannot_delete = true;
1345 clear_rhs_from_active_local_stores ();
1351 /* We can still process a volatile mem, we just cannot delete it. */
1352 if (MEM_VOLATILE_P (mem))
1353 insn_info->cannot_delete = true;
1355 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
1357 clear_rhs_from_active_local_stores ();
1361 if (GET_MODE (mem) == BLKmode)
1362 width = INTVAL (MEM_SIZE (mem));
1365 width = GET_MODE_SIZE (GET_MODE (mem));
1366 gcc_assert ((unsigned) width <= HOST_BITS_PER_WIDE_INT);
1369 if (spill_alias_set)
1371 bitmap store1 = clear_alias_group->store1_p;
1372 bitmap store2 = clear_alias_group->store2_p;
1374 gcc_assert (GET_MODE (mem) != BLKmode);
1376 if (bitmap_bit_p (store1, spill_alias_set))
1377 bitmap_set_bit (store2, spill_alias_set);
1379 bitmap_set_bit (store1, spill_alias_set);
1381 if (clear_alias_group->offset_map_size_p < spill_alias_set)
1382 clear_alias_group->offset_map_size_p = spill_alias_set;
1384 store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1387 fprintf (dump_file, " processing spill store %d(%s)\n",
1388 (int) spill_alias_set, GET_MODE_NAME (GET_MODE (mem)));
1390 else if (group_id >= 0)
1392 /* In the restrictive case where the base is a constant or the
1393 frame pointer we can do global analysis. */
1396 = VEC_index (group_info_t, rtx_group_vec, group_id);
1398 store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1399 set_usage_bits (group, offset, width);
1402 fprintf (dump_file, " processing const base store gid=%d[%d..%d)\n",
1403 group_id, (int)offset, (int)(offset+width));
1407 rtx base_term = find_base_term (XEXP (mem, 0));
1409 || (GET_CODE (base_term) == ADDRESS
1410 && GET_MODE (base_term) == Pmode
1411 && XEXP (base_term, 0) == stack_pointer_rtx))
1412 insn_info->stack_pointer_based = true;
1413 insn_info->contains_cselib_groups = true;
1415 store_info = (store_info_t) pool_alloc (cse_store_info_pool);
1419 fprintf (dump_file, " processing cselib store [%d..%d)\n",
1420 (int)offset, (int)(offset+width));
1423 const_rhs = rhs = NULL_RTX;
1424 if (GET_CODE (body) == SET
1425 /* No place to keep the value after ra. */
1426 && !reload_completed
1427 && (REG_P (SET_SRC (body))
1428 || GET_CODE (SET_SRC (body)) == SUBREG
1429 || CONSTANT_P (SET_SRC (body)))
1430 && !MEM_VOLATILE_P (mem)
1431 /* Sometimes the store and reload is used for truncation and
1433 && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
1435 rhs = SET_SRC (body);
1436 if (CONSTANT_P (rhs))
1438 else if (body == PATTERN (insn_info->insn))
1440 rtx tem = find_reg_note (insn_info->insn, REG_EQUAL, NULL_RTX);
1441 if (tem && CONSTANT_P (XEXP (tem, 0)))
1442 const_rhs = XEXP (tem, 0);
1444 if (const_rhs == NULL_RTX && REG_P (rhs))
1446 rtx tem = cselib_expand_value_rtx (rhs, scratch, 5);
1448 if (tem && CONSTANT_P (tem))
1453 /* Check to see if this stores causes some other stores to be
1455 ptr = active_local_stores;
1457 redundant_reason = NULL;
1461 insn_info_t next = ptr->next_local_store;
1462 store_info_t s_info = ptr->store_rec;
1465 /* Skip the clobbers. We delete the active insn if this insn
1466 shadows the set. To have been put on the active list, it
1467 has exactly on set. */
1468 while (!s_info->is_set)
1469 s_info = s_info->next;
1471 if (s_info->alias_set != spill_alias_set)
1473 else if (s_info->alias_set)
1475 struct clear_alias_mode_holder *entry
1476 = clear_alias_set_lookup (s_info->alias_set);
1477 /* Generally, spills cannot be processed if and of the
1478 references to the slot have a different mode. But if
1479 we are in the same block and mode is exactly the same
1480 between this store and one before in the same block,
1481 we can still delete it. */
1482 if ((GET_MODE (mem) == GET_MODE (s_info->mem))
1483 && (GET_MODE (mem) == entry->mode))
1486 set_all_positions_unneeded (s_info);
1489 fprintf (dump_file, " trying spill store in insn=%d alias_set=%d\n",
1490 INSN_UID (ptr->insn), (int) s_info->alias_set);
1492 else if ((s_info->group_id == group_id)
1493 && (s_info->cse_base == base))
1497 fprintf (dump_file, " trying store in insn=%d gid=%d[%d..%d)\n",
1498 INSN_UID (ptr->insn), s_info->group_id,
1499 (int)s_info->begin, (int)s_info->end);
1501 /* Even if PTR won't be eliminated as unneeded, if both
1502 PTR and this insn store the same constant value, we might
1503 eliminate this insn instead. */
1504 if (s_info->const_rhs
1506 && offset >= s_info->begin
1507 && offset + width <= s_info->end
1508 && all_positions_needed_p (s_info, offset - s_info->begin,
1511 if (GET_MODE (mem) == BLKmode)
1513 if (GET_MODE (s_info->mem) == BLKmode
1514 && s_info->const_rhs == const_rhs)
1515 redundant_reason = ptr;
1517 else if (s_info->const_rhs == const0_rtx
1518 && const_rhs == const0_rtx)
1519 redundant_reason = ptr;
1524 val = get_stored_val (s_info, GET_MODE (mem),
1525 offset, offset + width,
1526 BLOCK_FOR_INSN (insn_info->insn),
1528 if (get_insns () != NULL)
1531 if (val && rtx_equal_p (val, const_rhs))
1532 redundant_reason = ptr;
1536 for (i = MAX (offset, s_info->begin);
1537 i < offset + width && i < s_info->end;
1539 set_position_unneeded (s_info, i - s_info->begin);
1541 else if (s_info->rhs)
1542 /* Need to see if it is possible for this store to overwrite
1543 the value of store_info. If it is, set the rhs to NULL to
1544 keep it from being used to remove a load. */
1546 if (canon_true_dependence (s_info->mem,
1547 GET_MODE (s_info->mem),
1552 s_info->const_rhs = NULL;
1556 /* An insn can be deleted if every position of every one of
1557 its s_infos is zero. */
1558 if (any_positions_needed_p (s_info)
1559 || ptr->cannot_delete)
1564 insn_info_t insn_to_delete = ptr;
1567 last->next_local_store = ptr->next_local_store;
1569 active_local_stores = ptr->next_local_store;
1571 delete_dead_store_insn (insn_to_delete);
1579 /* Finish filling in the store_info. */
1580 store_info->next = insn_info->store_rec;
1581 insn_info->store_rec = store_info;
1582 store_info->mem = canon_rtx (mem);
1583 store_info->alias_set = spill_alias_set;
1584 store_info->mem_addr = get_addr (XEXP (mem, 0));
1585 store_info->cse_base = base;
1586 if (width > HOST_BITS_PER_WIDE_INT)
1588 store_info->is_large = true;
1589 store_info->positions_needed.large.count = 0;
1590 store_info->positions_needed.large.bitmap = BITMAP_ALLOC (NULL);
1594 store_info->is_large = false;
1595 store_info->positions_needed.small_bitmask = lowpart_bitmask (width);
1597 store_info->group_id = group_id;
1598 store_info->begin = offset;
1599 store_info->end = offset + width;
1600 store_info->is_set = GET_CODE (body) == SET;
1601 store_info->rhs = rhs;
1602 store_info->const_rhs = const_rhs;
1603 store_info->redundant_reason = redundant_reason;
1605 /* If this is a clobber, we return 0. We will only be able to
1606 delete this insn if there is only one store USED store, but we
1607 can use the clobber to delete other stores earlier. */
1608 return store_info->is_set ? 1 : 0;
1613 dump_insn_info (const char * start, insn_info_t insn_info)
1615 fprintf (dump_file, "%s insn=%d %s\n", start,
1616 INSN_UID (insn_info->insn),
1617 insn_info->store_rec ? "has store" : "naked");
1621 /* If the modes are different and the value's source and target do not
1622 line up, we need to extract the value from lower part of the rhs of
1623 the store, shift it, and then put it into a form that can be shoved
1624 into the read_insn. This function generates a right SHIFT of a
1625 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The
1626 shift sequence is returned or NULL if we failed to find a
1630 find_shift_sequence (int access_size,
1631 store_info_t store_info,
1632 enum machine_mode read_mode,
1633 int shift, bool speed, bool require_cst)
1635 enum machine_mode store_mode = GET_MODE (store_info->mem);
1636 enum machine_mode new_mode;
1637 rtx read_reg = NULL;
1639 /* Some machines like the x86 have shift insns for each size of
1640 operand. Other machines like the ppc or the ia-64 may only have
1641 shift insns that shift values within 32 or 64 bit registers.
1642 This loop tries to find the smallest shift insn that will right
1643 justify the value we want to read but is available in one insn on
1646 for (new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
1648 GET_MODE_BITSIZE (new_mode) <= BITS_PER_WORD;
1649 new_mode = GET_MODE_WIDER_MODE (new_mode))
1651 rtx target, new_reg, shift_seq, insn, new_lhs;
1654 /* If a constant was stored into memory, try to simplify it here,
1655 otherwise the cost of the shift might preclude this optimization
1656 e.g. at -Os, even when no actual shift will be needed. */
1657 if (store_info->const_rhs)
1659 unsigned int byte = subreg_lowpart_offset (new_mode, store_mode);
1660 rtx ret = simplify_subreg (new_mode, store_info->const_rhs,
1662 if (ret && CONSTANT_P (ret))
1664 ret = simplify_const_binary_operation (LSHIFTRT, new_mode,
1665 ret, GEN_INT (shift));
1666 if (ret && CONSTANT_P (ret))
1668 byte = subreg_lowpart_offset (read_mode, new_mode);
1669 ret = simplify_subreg (read_mode, ret, new_mode, byte);
1670 if (ret && CONSTANT_P (ret)
1671 && rtx_cost (ret, SET, speed) <= COSTS_N_INSNS (1))
1680 /* Try a wider mode if truncating the store mode to NEW_MODE
1681 requires a real instruction. */
1682 if (GET_MODE_BITSIZE (new_mode) < GET_MODE_BITSIZE (store_mode)
1683 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (new_mode),
1684 GET_MODE_BITSIZE (store_mode)))
1687 /* Also try a wider mode if the necessary punning is either not
1688 desirable or not possible. */
1689 if (!CONSTANT_P (store_info->rhs)
1690 && !MODES_TIEABLE_P (new_mode, store_mode))
1693 new_reg = gen_reg_rtx (new_mode);
1697 /* In theory we could also check for an ashr. Ian Taylor knows
1698 of one dsp where the cost of these two was not the same. But
1699 this really is a rare case anyway. */
1700 target = expand_binop (new_mode, lshr_optab, new_reg,
1701 GEN_INT (shift), new_reg, 1, OPTAB_DIRECT);
1703 shift_seq = get_insns ();
1706 if (target != new_reg || shift_seq == NULL)
1710 for (insn = shift_seq; insn != NULL_RTX; insn = NEXT_INSN (insn))
1712 cost += insn_rtx_cost (PATTERN (insn), speed);
1714 /* The computation up to here is essentially independent
1715 of the arguments and could be precomputed. It may
1716 not be worth doing so. We could precompute if
1717 worthwhile or at least cache the results. The result
1718 technically depends on both SHIFT and ACCESS_SIZE,
1719 but in practice the answer will depend only on ACCESS_SIZE. */
1721 if (cost > COSTS_N_INSNS (1))
1724 new_lhs = extract_low_bits (new_mode, store_mode,
1725 copy_rtx (store_info->rhs));
1726 if (new_lhs == NULL_RTX)
1729 /* We found an acceptable shift. Generate a move to
1730 take the value from the store and put it into the
1731 shift pseudo, then shift it, then generate another
1732 move to put in into the target of the read. */
1733 emit_move_insn (new_reg, new_lhs);
1734 emit_insn (shift_seq);
1735 read_reg = extract_low_bits (read_mode, new_mode, new_reg);
1743 /* Call back for note_stores to find the hard regs set or clobbered by
1744 insn. Data is a bitmap of the hardregs set so far. */
1747 look_for_hardregs (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
1749 bitmap regs_set = (bitmap) data;
1752 && REGNO (x) < FIRST_PSEUDO_REGISTER)
1754 int regno = REGNO (x);
1755 int n = hard_regno_nregs[regno][GET_MODE (x)];
1757 bitmap_set_bit (regs_set, regno + n);
1761 /* Helper function for replace_read and record_store.
1762 Attempt to return a value stored in STORE_INFO, from READ_BEGIN
1763 to one before READ_END bytes read in READ_MODE. Return NULL
1764 if not successful. If REQUIRE_CST is true, return always constant. */
1767 get_stored_val (store_info_t store_info, enum machine_mode read_mode,
1768 HOST_WIDE_INT read_begin, HOST_WIDE_INT read_end,
1769 basic_block bb, bool require_cst)
1771 enum machine_mode store_mode = GET_MODE (store_info->mem);
1773 int access_size; /* In bytes. */
1776 /* To get here the read is within the boundaries of the write so
1777 shift will never be negative. Start out with the shift being in
1779 if (store_mode == BLKmode)
1781 else if (BYTES_BIG_ENDIAN)
1782 shift = store_info->end - read_end;
1784 shift = read_begin - store_info->begin;
1786 access_size = shift + GET_MODE_SIZE (read_mode);
1788 /* From now on it is bits. */
1789 shift *= BITS_PER_UNIT;
1792 read_reg = find_shift_sequence (access_size, store_info, read_mode, shift,
1793 optimize_bb_for_speed_p (bb),
1795 else if (store_mode == BLKmode)
1797 /* The store is a memset (addr, const_val, const_size). */
1798 gcc_assert (CONST_INT_P (store_info->rhs));
1799 store_mode = int_mode_for_mode (read_mode);
1800 if (store_mode == BLKmode)
1801 read_reg = NULL_RTX;
1802 else if (store_info->rhs == const0_rtx)
1803 read_reg = extract_low_bits (read_mode, store_mode, const0_rtx);
1804 else if (GET_MODE_BITSIZE (store_mode) > HOST_BITS_PER_WIDE_INT
1805 || BITS_PER_UNIT >= HOST_BITS_PER_WIDE_INT)
1806 read_reg = NULL_RTX;
1809 unsigned HOST_WIDE_INT c
1810 = INTVAL (store_info->rhs)
1811 & (((HOST_WIDE_INT) 1 << BITS_PER_UNIT) - 1);
1812 int shift = BITS_PER_UNIT;
1813 while (shift < HOST_BITS_PER_WIDE_INT)
1818 read_reg = GEN_INT (trunc_int_for_mode (c, store_mode));
1819 read_reg = extract_low_bits (read_mode, store_mode, read_reg);
1822 else if (store_info->const_rhs
1824 || GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode)))
1825 read_reg = extract_low_bits (read_mode, store_mode,
1826 copy_rtx (store_info->const_rhs));
1828 read_reg = extract_low_bits (read_mode, store_mode,
1829 copy_rtx (store_info->rhs));
1830 if (require_cst && read_reg && !CONSTANT_P (read_reg))
1831 read_reg = NULL_RTX;
1835 /* Take a sequence of:
1858 Depending on the alignment and the mode of the store and
1862 The STORE_INFO and STORE_INSN are for the store and READ_INFO
1863 and READ_INSN are for the read. Return true if the replacement
1867 replace_read (store_info_t store_info, insn_info_t store_insn,
1868 read_info_t read_info, insn_info_t read_insn, rtx *loc,
1871 enum machine_mode store_mode = GET_MODE (store_info->mem);
1872 enum machine_mode read_mode = GET_MODE (read_info->mem);
1873 rtx insns, this_insn, read_reg;
1879 /* Create a sequence of instructions to set up the read register.
1880 This sequence goes immediately before the store and its result
1881 is read by the load.
1883 We need to keep this in perspective. We are replacing a read
1884 with a sequence of insns, but the read will almost certainly be
1885 in cache, so it is not going to be an expensive one. Thus, we
1886 are not willing to do a multi insn shift or worse a subroutine
1887 call to get rid of the read. */
1889 fprintf (dump_file, "trying to replace %smode load in insn %d"
1890 " from %smode store in insn %d\n",
1891 GET_MODE_NAME (read_mode), INSN_UID (read_insn->insn),
1892 GET_MODE_NAME (store_mode), INSN_UID (store_insn->insn));
1894 bb = BLOCK_FOR_INSN (read_insn->insn);
1895 read_reg = get_stored_val (store_info,
1896 read_mode, read_info->begin, read_info->end,
1898 if (read_reg == NULL_RTX)
1902 fprintf (dump_file, " -- could not extract bits of stored value\n");
1905 /* Force the value into a new register so that it won't be clobbered
1906 between the store and the load. */
1907 read_reg = copy_to_mode_reg (read_mode, read_reg);
1908 insns = get_insns ();
1911 if (insns != NULL_RTX)
1913 /* Now we have to scan the set of new instructions to see if the
1914 sequence contains and sets of hardregs that happened to be
1915 live at this point. For instance, this can happen if one of
1916 the insns sets the CC and the CC happened to be live at that
1917 point. This does occasionally happen, see PR 37922. */
1918 bitmap regs_set = BITMAP_ALLOC (NULL);
1920 for (this_insn = insns; this_insn != NULL_RTX; this_insn = NEXT_INSN (this_insn))
1921 note_stores (PATTERN (this_insn), look_for_hardregs, regs_set);
1923 bitmap_and_into (regs_set, regs_live);
1924 if (!bitmap_empty_p (regs_set))
1929 "abandoning replacement because sequence clobbers live hardregs:");
1930 df_print_regset (dump_file, regs_set);
1933 BITMAP_FREE (regs_set);
1936 BITMAP_FREE (regs_set);
1939 if (validate_change (read_insn->insn, loc, read_reg, 0))
1941 deferred_change_t deferred_change =
1942 (deferred_change_t) pool_alloc (deferred_change_pool);
1944 /* Insert this right before the store insn where it will be safe
1945 from later insns that might change it before the read. */
1946 emit_insn_before (insns, store_insn->insn);
1948 /* And now for the kludge part: cselib croaks if you just
1949 return at this point. There are two reasons for this:
1951 1) Cselib has an idea of how many pseudos there are and
1952 that does not include the new ones we just added.
1954 2) Cselib does not know about the move insn we added
1955 above the store_info, and there is no way to tell it
1956 about it, because it has "moved on".
1958 Problem (1) is fixable with a certain amount of engineering.
1959 Problem (2) is requires starting the bb from scratch. This
1962 So we are just going to have to lie. The move/extraction
1963 insns are not really an issue, cselib did not see them. But
1964 the use of the new pseudo read_insn is a real problem because
1965 cselib has not scanned this insn. The way that we solve this
1966 problem is that we are just going to put the mem back for now
1967 and when we are finished with the block, we undo this. We
1968 keep a table of mems to get rid of. At the end of the basic
1969 block we can put them back. */
1971 *loc = read_info->mem;
1972 deferred_change->next = deferred_change_list;
1973 deferred_change_list = deferred_change;
1974 deferred_change->loc = loc;
1975 deferred_change->reg = read_reg;
1977 /* Get rid of the read_info, from the point of view of the
1978 rest of dse, play like this read never happened. */
1979 read_insn->read_rec = read_info->next;
1980 pool_free (read_info_pool, read_info);
1983 fprintf (dump_file, " -- replaced the loaded MEM with ");
1984 print_simple_rtl (dump_file, read_reg);
1985 fprintf (dump_file, "\n");
1993 fprintf (dump_file, " -- replacing the loaded MEM with ");
1994 print_simple_rtl (dump_file, read_reg);
1995 fprintf (dump_file, " led to an invalid instruction\n");
2001 /* A for_each_rtx callback in which DATA is the bb_info. Check to see
2002 if LOC is a mem and if it is look at the address and kill any
2003 appropriate stores that may be active. */
2006 check_mem_read_rtx (rtx *loc, void *data)
2010 insn_info_t insn_info;
2011 HOST_WIDE_INT offset = 0;
2012 HOST_WIDE_INT width = 0;
2013 alias_set_type spill_alias_set = 0;
2014 cselib_val *base = NULL;
2016 read_info_t read_info;
2018 if (!mem || !MEM_P (mem))
2021 bb_info = (bb_info_t) data;
2022 insn_info = bb_info->last_insn;
2024 if ((MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2025 || (MEM_VOLATILE_P (mem)))
2028 fprintf (dump_file, " adding wild read, volatile or barrier.\n");
2029 add_wild_read (bb_info);
2030 insn_info->cannot_delete = true;
2034 /* If it is reading readonly mem, then there can be no conflict with
2036 if (MEM_READONLY_P (mem))
2039 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
2042 fprintf (dump_file, " adding wild read, canon_address failure.\n");
2043 add_wild_read (bb_info);
2047 if (GET_MODE (mem) == BLKmode)
2050 width = GET_MODE_SIZE (GET_MODE (mem));
2052 read_info = (read_info_t) pool_alloc (read_info_pool);
2053 read_info->group_id = group_id;
2054 read_info->mem = mem;
2055 read_info->alias_set = spill_alias_set;
2056 read_info->begin = offset;
2057 read_info->end = offset + width;
2058 read_info->next = insn_info->read_rec;
2059 insn_info->read_rec = read_info;
2061 /* We ignore the clobbers in store_info. The is mildly aggressive,
2062 but there really should not be a clobber followed by a read. */
2064 if (spill_alias_set)
2066 insn_info_t i_ptr = active_local_stores;
2067 insn_info_t last = NULL;
2070 fprintf (dump_file, " processing spill load %d\n",
2071 (int) spill_alias_set);
2075 store_info_t store_info = i_ptr->store_rec;
2077 /* Skip the clobbers. */
2078 while (!store_info->is_set)
2079 store_info = store_info->next;
2081 if (store_info->alias_set == spill_alias_set)
2084 dump_insn_info ("removing from active", i_ptr);
2087 last->next_local_store = i_ptr->next_local_store;
2089 active_local_stores = i_ptr->next_local_store;
2093 i_ptr = i_ptr->next_local_store;
2096 else if (group_id >= 0)
2098 /* This is the restricted case where the base is a constant or
2099 the frame pointer and offset is a constant. */
2100 insn_info_t i_ptr = active_local_stores;
2101 insn_info_t last = NULL;
2106 fprintf (dump_file, " processing const load gid=%d[BLK]\n",
2109 fprintf (dump_file, " processing const load gid=%d[%d..%d)\n",
2110 group_id, (int)offset, (int)(offset+width));
2115 bool remove = false;
2116 store_info_t store_info = i_ptr->store_rec;
2118 /* Skip the clobbers. */
2119 while (!store_info->is_set)
2120 store_info = store_info->next;
2122 /* There are three cases here. */
2123 if (store_info->group_id < 0)
2124 /* We have a cselib store followed by a read from a
2127 = canon_true_dependence (store_info->mem,
2128 GET_MODE (store_info->mem),
2129 store_info->mem_addr,
2132 else if (group_id == store_info->group_id)
2134 /* This is a block mode load. We may get lucky and
2135 canon_true_dependence may save the day. */
2138 = canon_true_dependence (store_info->mem,
2139 GET_MODE (store_info->mem),
2140 store_info->mem_addr,
2143 /* If this read is just reading back something that we just
2144 stored, rewrite the read. */
2148 && offset >= store_info->begin
2149 && offset + width <= store_info->end
2150 && all_positions_needed_p (store_info,
2151 offset - store_info->begin,
2153 && replace_read (store_info, i_ptr, read_info,
2154 insn_info, loc, bb_info->regs_live))
2157 /* The bases are the same, just see if the offsets
2159 if ((offset < store_info->end)
2160 && (offset + width > store_info->begin))
2166 The else case that is missing here is that the
2167 bases are constant but different. There is nothing
2168 to do here because there is no overlap. */
2173 dump_insn_info ("removing from active", i_ptr);
2176 last->next_local_store = i_ptr->next_local_store;
2178 active_local_stores = i_ptr->next_local_store;
2182 i_ptr = i_ptr->next_local_store;
2187 insn_info_t i_ptr = active_local_stores;
2188 insn_info_t last = NULL;
2191 fprintf (dump_file, " processing cselib load mem:");
2192 print_inline_rtx (dump_file, mem, 0);
2193 fprintf (dump_file, "\n");
2198 bool remove = false;
2199 store_info_t store_info = i_ptr->store_rec;
2202 fprintf (dump_file, " processing cselib load against insn %d\n",
2203 INSN_UID (i_ptr->insn));
2205 /* Skip the clobbers. */
2206 while (!store_info->is_set)
2207 store_info = store_info->next;
2209 /* If this read is just reading back something that we just
2210 stored, rewrite the read. */
2212 && store_info->group_id == -1
2213 && store_info->cse_base == base
2214 && offset >= store_info->begin
2215 && offset + width <= store_info->end
2216 && all_positions_needed_p (store_info,
2217 offset - store_info->begin, width)
2218 && replace_read (store_info, i_ptr, read_info, insn_info, loc,
2219 bb_info->regs_live))
2222 if (!store_info->alias_set)
2223 remove = canon_true_dependence (store_info->mem,
2224 GET_MODE (store_info->mem),
2225 store_info->mem_addr,
2231 dump_insn_info ("removing from active", i_ptr);
2234 last->next_local_store = i_ptr->next_local_store;
2236 active_local_stores = i_ptr->next_local_store;
2240 i_ptr = i_ptr->next_local_store;
2246 /* A for_each_rtx callback in which DATA points the INSN_INFO for
2247 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
2248 true for any part of *LOC. */
2251 check_mem_read_use (rtx *loc, void *data)
2253 for_each_rtx (loc, check_mem_read_rtx, data);
2257 /* Get arguments passed to CALL_INSN. Return TRUE if successful.
2258 So far it only handles arguments passed in registers. */
2261 get_call_args (rtx call_insn, tree fn, rtx *args, int nargs)
2263 CUMULATIVE_ARGS args_so_far;
2267 INIT_CUMULATIVE_ARGS (args_so_far, TREE_TYPE (fn), NULL_RTX, 0, 3);
2269 arg = TYPE_ARG_TYPES (TREE_TYPE (fn));
2271 arg != void_list_node && idx < nargs;
2272 arg = TREE_CHAIN (arg), idx++)
2274 enum machine_mode mode = TYPE_MODE (TREE_VALUE (arg));
2275 rtx reg = FUNCTION_ARG (args_so_far, mode, NULL_TREE, 1), link, tmp;
2276 if (!reg || !REG_P (reg) || GET_MODE (reg) != mode
2277 || GET_MODE_CLASS (mode) != MODE_INT)
2280 for (link = CALL_INSN_FUNCTION_USAGE (call_insn);
2282 link = XEXP (link, 1))
2283 if (GET_CODE (XEXP (link, 0)) == USE)
2285 args[idx] = XEXP (XEXP (link, 0), 0);
2286 if (REG_P (args[idx])
2287 && REGNO (args[idx]) == REGNO (reg)
2288 && (GET_MODE (args[idx]) == mode
2289 || (GET_MODE_CLASS (GET_MODE (args[idx])) == MODE_INT
2290 && (GET_MODE_SIZE (GET_MODE (args[idx]))
2292 && (GET_MODE_SIZE (GET_MODE (args[idx]))
2293 > GET_MODE_SIZE (mode)))))
2299 tmp = cselib_expand_value_rtx (args[idx], scratch, 5);
2300 if (GET_MODE (args[idx]) != mode)
2302 if (!tmp || !CONST_INT_P (tmp))
2304 tmp = GEN_INT (trunc_int_for_mode (INTVAL (tmp), mode));
2309 FUNCTION_ARG_ADVANCE (args_so_far, mode, NULL_TREE, 1);
2311 if (arg != void_list_node || idx != nargs)
2317 /* Apply record_store to all candidate stores in INSN. Mark INSN
2318 if some part of it is not a candidate store and assigns to a
2319 non-register target. */
2322 scan_insn (bb_info_t bb_info, rtx insn)
2325 insn_info_t insn_info = (insn_info_t) pool_alloc (insn_info_pool);
2327 memset (insn_info, 0, sizeof (struct insn_info));
2330 fprintf (dump_file, "\n**scanning insn=%d\n",
2333 insn_info->prev_insn = bb_info->last_insn;
2334 insn_info->insn = insn;
2335 bb_info->last_insn = insn_info;
2338 /* Cselib clears the table for this case, so we have to essentially
2340 if (NONJUMP_INSN_P (insn)
2341 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
2342 && MEM_VOLATILE_P (PATTERN (insn)))
2344 add_wild_read (bb_info);
2345 insn_info->cannot_delete = true;
2349 /* Look at all of the uses in the insn. */
2350 note_uses (&PATTERN (insn), check_mem_read_use, bb_info);
2355 tree memset_call = NULL_TREE;
2357 insn_info->cannot_delete = true;
2359 /* Const functions cannot do anything bad i.e. read memory,
2360 however, they can read their parameters which may have
2361 been pushed onto the stack.
2362 memset and bzero don't read memory either. */
2363 const_call = RTL_CONST_CALL_P (insn);
2366 rtx call = PATTERN (insn);
2367 if (GET_CODE (call) == PARALLEL)
2368 call = XVECEXP (call, 0, 0);
2369 if (GET_CODE (call) == SET)
2370 call = SET_SRC (call);
2371 if (GET_CODE (call) == CALL
2372 && MEM_P (XEXP (call, 0))
2373 && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
2375 rtx symbol = XEXP (XEXP (call, 0), 0);
2376 if (SYMBOL_REF_DECL (symbol)
2377 && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
2379 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
2381 && (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))
2382 == BUILT_IN_MEMSET))
2383 || SYMBOL_REF_DECL (symbol) == block_clear_fn)
2384 memset_call = SYMBOL_REF_DECL (symbol);
2388 if (const_call || memset_call)
2390 insn_info_t i_ptr = active_local_stores;
2391 insn_info_t last = NULL;
2394 fprintf (dump_file, "%s call %d\n",
2395 const_call ? "const" : "memset", INSN_UID (insn));
2397 /* See the head comment of the frame_read field. */
2398 if (reload_completed)
2399 insn_info->frame_read = true;
2401 /* Loop over the active stores and remove those which are
2402 killed by the const function call. */
2405 bool remove_store = false;
2407 /* The stack pointer based stores are always killed. */
2408 if (i_ptr->stack_pointer_based)
2409 remove_store = true;
2411 /* If the frame is read, the frame related stores are killed. */
2412 else if (insn_info->frame_read)
2414 store_info_t store_info = i_ptr->store_rec;
2416 /* Skip the clobbers. */
2417 while (!store_info->is_set)
2418 store_info = store_info->next;
2420 if (store_info->group_id >= 0
2421 && VEC_index (group_info_t, rtx_group_vec,
2422 store_info->group_id)->frame_related)
2423 remove_store = true;
2429 dump_insn_info ("removing from active", i_ptr);
2432 last->next_local_store = i_ptr->next_local_store;
2434 active_local_stores = i_ptr->next_local_store;
2439 i_ptr = i_ptr->next_local_store;
2445 if (get_call_args (insn, memset_call, args, 3)
2446 && CONST_INT_P (args[1])
2447 && CONST_INT_P (args[2])
2448 && INTVAL (args[2]) > 0)
2450 rtx mem = gen_rtx_MEM (BLKmode, args[0]);
2451 set_mem_size (mem, args[2]);
2452 body = gen_rtx_SET (VOIDmode, mem, args[1]);
2453 mems_found += record_store (body, bb_info);
2455 fprintf (dump_file, "handling memset as BLKmode store\n");
2456 if (mems_found == 1)
2458 insn_info->next_local_store = active_local_stores;
2459 active_local_stores = insn_info;
2466 /* Every other call, including pure functions, may read memory. */
2467 add_wild_read (bb_info);
2472 /* Assuming that there are sets in these insns, we cannot delete
2474 if ((GET_CODE (PATTERN (insn)) == CLOBBER)
2475 || volatile_refs_p (PATTERN (insn))
2476 || (flag_non_call_exceptions && may_trap_p (PATTERN (insn)))
2477 || (RTX_FRAME_RELATED_P (insn))
2478 || find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX))
2479 insn_info->cannot_delete = true;
2481 body = PATTERN (insn);
2482 if (GET_CODE (body) == PARALLEL)
2485 for (i = 0; i < XVECLEN (body, 0); i++)
2486 mems_found += record_store (XVECEXP (body, 0, i), bb_info);
2489 mems_found += record_store (body, bb_info);
2492 fprintf (dump_file, "mems_found = %d, cannot_delete = %s\n",
2493 mems_found, insn_info->cannot_delete ? "true" : "false");
2495 /* If we found some sets of mems, add it into the active_local_stores so
2496 that it can be locally deleted if found dead or used for
2497 replace_read and redundant constant store elimination. Otherwise mark
2498 it as cannot delete. This simplifies the processing later. */
2499 if (mems_found == 1)
2501 insn_info->next_local_store = active_local_stores;
2502 active_local_stores = insn_info;
2505 insn_info->cannot_delete = true;
2509 /* Remove BASE from the set of active_local_stores. This is a
2510 callback from cselib that is used to get rid of the stores in
2511 active_local_stores. */
2514 remove_useless_values (cselib_val *base)
2516 insn_info_t insn_info = active_local_stores;
2517 insn_info_t last = NULL;
2521 store_info_t store_info = insn_info->store_rec;
2524 /* If ANY of the store_infos match the cselib group that is
2525 being deleted, then the insn can not be deleted. */
2528 if ((store_info->group_id == -1)
2529 && (store_info->cse_base == base))
2534 store_info = store_info->next;
2540 last->next_local_store = insn_info->next_local_store;
2542 active_local_stores = insn_info->next_local_store;
2543 free_store_info (insn_info);
2548 insn_info = insn_info->next_local_store;
2553 /* Do all of step 1. */
2559 bitmap regs_live = BITMAP_ALLOC (NULL);
2561 cselib_init (false);
2562 all_blocks = BITMAP_ALLOC (NULL);
2563 bitmap_set_bit (all_blocks, ENTRY_BLOCK);
2564 bitmap_set_bit (all_blocks, EXIT_BLOCK);
2569 bb_info_t bb_info = (bb_info_t) pool_alloc (bb_info_pool);
2571 memset (bb_info, 0, sizeof (struct bb_info));
2572 bitmap_set_bit (all_blocks, bb->index);
2573 bb_info->regs_live = regs_live;
2575 bitmap_copy (regs_live, DF_LR_IN (bb));
2576 df_simulate_initialize_forwards (bb, regs_live);
2578 bb_table[bb->index] = bb_info;
2579 cselib_discard_hook = remove_useless_values;
2581 if (bb->index >= NUM_FIXED_BLOCKS)
2586 = create_alloc_pool ("cse_store_info_pool",
2587 sizeof (struct store_info), 100);
2588 active_local_stores = NULL;
2589 cselib_clear_table ();
2591 /* Scan the insns. */
2592 FOR_BB_INSNS (bb, insn)
2595 scan_insn (bb_info, insn);
2596 cselib_process_insn (insn);
2598 df_simulate_one_insn_forwards (bb, insn, regs_live);
2601 /* This is something of a hack, because the global algorithm
2602 is supposed to take care of the case where stores go dead
2603 at the end of the function. However, the global
2604 algorithm must take a more conservative view of block
2605 mode reads than the local alg does. So to get the case
2606 where you have a store to the frame followed by a non
2607 overlapping block more read, we look at the active local
2608 stores at the end of the function and delete all of the
2609 frame and spill based ones. */
2610 if (stores_off_frame_dead_at_return
2611 && (EDGE_COUNT (bb->succs) == 0
2612 || (single_succ_p (bb)
2613 && single_succ (bb) == EXIT_BLOCK_PTR
2614 && ! crtl->calls_eh_return)))
2616 insn_info_t i_ptr = active_local_stores;
2619 store_info_t store_info = i_ptr->store_rec;
2621 /* Skip the clobbers. */
2622 while (!store_info->is_set)
2623 store_info = store_info->next;
2624 if (store_info->alias_set && !i_ptr->cannot_delete)
2625 delete_dead_store_insn (i_ptr);
2627 if (store_info->group_id >= 0)
2630 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
2631 if (group->frame_related && !i_ptr->cannot_delete)
2632 delete_dead_store_insn (i_ptr);
2635 i_ptr = i_ptr->next_local_store;
2639 /* Get rid of the loads that were discovered in
2640 replace_read. Cselib is finished with this block. */
2641 while (deferred_change_list)
2643 deferred_change_t next = deferred_change_list->next;
2645 /* There is no reason to validate this change. That was
2647 *deferred_change_list->loc = deferred_change_list->reg;
2648 pool_free (deferred_change_pool, deferred_change_list);
2649 deferred_change_list = next;
2652 /* Get rid of all of the cselib based store_infos in this
2653 block and mark the containing insns as not being
2655 ptr = bb_info->last_insn;
2658 if (ptr->contains_cselib_groups)
2660 store_info_t s_info = ptr->store_rec;
2661 while (s_info && !s_info->is_set)
2662 s_info = s_info->next;
2664 && s_info->redundant_reason
2665 && s_info->redundant_reason->insn
2666 && !ptr->cannot_delete)
2669 fprintf (dump_file, "Locally deleting insn %d "
2670 "because insn %d stores the "
2671 "same value and couldn't be "
2673 INSN_UID (ptr->insn),
2674 INSN_UID (s_info->redundant_reason->insn));
2675 delete_dead_store_insn (ptr);
2678 s_info->redundant_reason = NULL;
2679 free_store_info (ptr);
2683 store_info_t s_info;
2685 /* Free at least positions_needed bitmaps. */
2686 for (s_info = ptr->store_rec; s_info; s_info = s_info->next)
2687 if (s_info->is_large)
2689 BITMAP_FREE (s_info->positions_needed.large.bitmap);
2690 s_info->is_large = false;
2693 ptr = ptr->prev_insn;
2696 free_alloc_pool (cse_store_info_pool);
2698 bb_info->regs_live = NULL;
2701 BITMAP_FREE (regs_live);
2703 htab_empty (rtx_group_table);
2707 /*----------------------------------------------------------------------------
2710 Assign each byte position in the stores that we are going to
2711 analyze globally to a position in the bitmaps. Returns true if
2712 there are any bit positions assigned.
2713 ----------------------------------------------------------------------------*/
2716 dse_step2_init (void)
2721 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2723 /* For all non stack related bases, we only consider a store to
2724 be deletable if there are two or more stores for that
2725 position. This is because it takes one store to make the
2726 other store redundant. However, for the stores that are
2727 stack related, we consider them if there is only one store
2728 for the position. We do this because the stack related
2729 stores can be deleted if their is no read between them and
2730 the end of the function.
2732 To make this work in the current framework, we take the stack
2733 related bases add all of the bits from store1 into store2.
2734 This has the effect of making the eligible even if there is
2737 if (stores_off_frame_dead_at_return && group->frame_related)
2739 bitmap_ior_into (group->store2_n, group->store1_n);
2740 bitmap_ior_into (group->store2_p, group->store1_p);
2742 fprintf (dump_file, "group %d is frame related ", i);
2745 group->offset_map_size_n++;
2746 group->offset_map_n = XNEWVEC (int, group->offset_map_size_n);
2747 group->offset_map_size_p++;
2748 group->offset_map_p = XNEWVEC (int, group->offset_map_size_p);
2749 group->process_globally = false;
2752 fprintf (dump_file, "group %d(%d+%d): ", i,
2753 (int)bitmap_count_bits (group->store2_n),
2754 (int)bitmap_count_bits (group->store2_p));
2755 bitmap_print (dump_file, group->store2_n, "n ", " ");
2756 bitmap_print (dump_file, group->store2_p, "p ", "\n");
2762 /* Init the offset tables for the normal case. */
2765 dse_step2_nospill (void)
2769 /* Position 0 is unused because 0 is used in the maps to mean
2771 current_position = 1;
2773 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2778 if (group == clear_alias_group)
2781 memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2782 memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2783 bitmap_clear (group->group_kill);
2785 EXECUTE_IF_SET_IN_BITMAP (group->store2_n, 0, j, bi)
2787 bitmap_set_bit (group->group_kill, current_position);
2788 group->offset_map_n[j] = current_position++;
2789 group->process_globally = true;
2791 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2793 bitmap_set_bit (group->group_kill, current_position);
2794 group->offset_map_p[j] = current_position++;
2795 group->process_globally = true;
2798 return current_position != 1;
2802 /* Init the offset tables for the spill case. */
2805 dse_step2_spill (void)
2808 group_info_t group = clear_alias_group;
2811 /* Position 0 is unused because 0 is used in the maps to mean
2813 current_position = 1;
2817 bitmap_print (dump_file, clear_alias_sets,
2818 "clear alias sets ", "\n");
2819 bitmap_print (dump_file, disqualified_clear_alias_sets,
2820 "disqualified clear alias sets ", "\n");
2823 memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2824 memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2825 bitmap_clear (group->group_kill);
2827 /* Remove the disqualified positions from the store2_p set. */
2828 bitmap_and_compl_into (group->store2_p, disqualified_clear_alias_sets);
2830 /* We do not need to process the store2_n set because
2831 alias_sets are always positive. */
2832 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2834 bitmap_set_bit (group->group_kill, current_position);
2835 group->offset_map_p[j] = current_position++;
2836 group->process_globally = true;
2839 return current_position != 1;
2844 /*----------------------------------------------------------------------------
2847 Build the bit vectors for the transfer functions.
2848 ----------------------------------------------------------------------------*/
2851 /* Note that this is NOT a general purpose function. Any mem that has
2852 an alias set registered here expected to be COMPLETELY unaliased:
2853 i.e it's addresses are not and need not be examined.
2855 It is known that all references to this address will have this
2856 alias set and there are NO other references to this address in the
2859 Currently the only place that is known to be clean enough to use
2860 this interface is the code that assigns the spill locations.
2862 All of the mems that have alias_sets registered are subjected to a
2863 very powerful form of dse where function calls, volatile reads and
2864 writes, and reads from random location are not taken into account.
2866 It is also assumed that these locations go dead when the function
2867 returns. This assumption could be relaxed if there were found to
2868 be places that this assumption was not correct.
2870 The MODE is passed in and saved. The mode of each load or store to
2871 a mem with ALIAS_SET is checked against MEM. If the size of that
2872 load or store is different from MODE, processing is halted on this
2873 alias set. For the vast majority of aliases sets, all of the loads
2874 and stores will use the same mode. But vectors are treated
2875 differently: the alias set is established for the entire vector,
2876 but reload will insert loads and stores for individual elements and
2877 we do not necessarily have the information to track those separate
2878 elements. So when we see a mode mismatch, we just bail. */
2882 dse_record_singleton_alias_set (alias_set_type alias_set,
2883 enum machine_mode mode)
2885 struct clear_alias_mode_holder tmp_holder;
2886 struct clear_alias_mode_holder *entry;
2889 /* If we are not going to run dse, we need to return now or there
2890 will be problems with allocating the bitmaps. */
2891 if ((!gate_dse()) || !alias_set)
2894 if (!clear_alias_sets)
2896 clear_alias_sets = BITMAP_ALLOC (NULL);
2897 disqualified_clear_alias_sets = BITMAP_ALLOC (NULL);
2898 clear_alias_mode_table = htab_create (11, clear_alias_mode_hash,
2899 clear_alias_mode_eq, NULL);
2900 clear_alias_mode_pool = create_alloc_pool ("clear_alias_mode_pool",
2901 sizeof (struct clear_alias_mode_holder), 100);
2904 bitmap_set_bit (clear_alias_sets, alias_set);
2906 tmp_holder.alias_set = alias_set;
2908 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, INSERT);
2909 gcc_assert (*slot == NULL);
2912 (struct clear_alias_mode_holder *) pool_alloc (clear_alias_mode_pool);
2913 entry->alias_set = alias_set;
2918 /* Remove ALIAS_SET from the sets of stack slots being considered. */
2921 dse_invalidate_singleton_alias_set (alias_set_type alias_set)
2923 if ((!gate_dse()) || !alias_set)
2926 bitmap_clear_bit (clear_alias_sets, alias_set);
2930 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
2934 get_bitmap_index (group_info_t group_info, HOST_WIDE_INT offset)
2938 HOST_WIDE_INT offset_p = -offset;
2939 if (offset_p >= group_info->offset_map_size_n)
2941 return group_info->offset_map_n[offset_p];
2945 if (offset >= group_info->offset_map_size_p)
2947 return group_info->offset_map_p[offset];
2952 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
2956 scan_stores_nospill (store_info_t store_info, bitmap gen, bitmap kill)
2961 group_info_t group_info
2962 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
2963 if (group_info->process_globally)
2964 for (i = store_info->begin; i < store_info->end; i++)
2966 int index = get_bitmap_index (group_info, i);
2969 bitmap_set_bit (gen, index);
2971 bitmap_clear_bit (kill, index);
2974 store_info = store_info->next;
2979 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
2983 scan_stores_spill (store_info_t store_info, bitmap gen, bitmap kill)
2987 if (store_info->alias_set)
2989 int index = get_bitmap_index (clear_alias_group,
2990 store_info->alias_set);
2993 bitmap_set_bit (gen, index);
2995 bitmap_clear_bit (kill, index);
2998 store_info = store_info->next;
3003 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3007 scan_reads_nospill (insn_info_t insn_info, bitmap gen, bitmap kill)
3009 read_info_t read_info = insn_info->read_rec;
3013 /* If this insn reads the frame, kill all the frame related stores. */
3014 if (insn_info->frame_read)
3016 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
3017 if (group->process_globally && group->frame_related)
3020 bitmap_ior_into (kill, group->group_kill);
3021 bitmap_and_compl_into (gen, group->group_kill);
3027 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
3029 if (group->process_globally)
3031 if (i == read_info->group_id)
3033 if (read_info->begin > read_info->end)
3035 /* Begin > end for block mode reads. */
3037 bitmap_ior_into (kill, group->group_kill);
3038 bitmap_and_compl_into (gen, group->group_kill);
3042 /* The groups are the same, just process the
3045 for (j = read_info->begin; j < read_info->end; j++)
3047 int index = get_bitmap_index (group, j);
3051 bitmap_set_bit (kill, index);
3052 bitmap_clear_bit (gen, index);
3059 /* The groups are different, if the alias sets
3060 conflict, clear the entire group. We only need
3061 to apply this test if the read_info is a cselib
3062 read. Anything with a constant base cannot alias
3063 something else with a different constant
3065 if ((read_info->group_id < 0)
3066 && canon_true_dependence (group->base_mem,
3068 group->canon_base_mem,
3069 read_info->mem, rtx_varies_p))
3072 bitmap_ior_into (kill, group->group_kill);
3073 bitmap_and_compl_into (gen, group->group_kill);
3079 read_info = read_info->next;
3083 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3087 scan_reads_spill (read_info_t read_info, bitmap gen, bitmap kill)
3091 if (read_info->alias_set)
3093 int index = get_bitmap_index (clear_alias_group,
3094 read_info->alias_set);
3098 bitmap_set_bit (kill, index);
3099 bitmap_clear_bit (gen, index);
3103 read_info = read_info->next;
3108 /* Return the insn in BB_INFO before the first wild read or if there
3109 are no wild reads in the block, return the last insn. */
3112 find_insn_before_first_wild_read (bb_info_t bb_info)
3114 insn_info_t insn_info = bb_info->last_insn;
3115 insn_info_t last_wild_read = NULL;
3119 if (insn_info->wild_read)
3121 last_wild_read = insn_info->prev_insn;
3122 /* Block starts with wild read. */
3123 if (!last_wild_read)
3127 insn_info = insn_info->prev_insn;
3131 return last_wild_read;
3133 return bb_info->last_insn;
3137 /* Scan the insns in BB_INFO starting at PTR and going to the top of
3138 the block in order to build the gen and kill sets for the block.
3139 We start at ptr which may be the last insn in the block or may be
3140 the first insn with a wild read. In the latter case we are able to
3141 skip the rest of the block because it just does not matter:
3142 anything that happens is hidden by the wild read. */
3145 dse_step3_scan (bool for_spills, basic_block bb)
3147 bb_info_t bb_info = bb_table[bb->index];
3148 insn_info_t insn_info;
3151 /* There are no wild reads in the spill case. */
3152 insn_info = bb_info->last_insn;
3154 insn_info = find_insn_before_first_wild_read (bb_info);
3156 /* In the spill case or in the no_spill case if there is no wild
3157 read in the block, we will need a kill set. */
3158 if (insn_info == bb_info->last_insn)
3161 bitmap_clear (bb_info->kill);
3163 bb_info->kill = BITMAP_ALLOC (NULL);
3167 BITMAP_FREE (bb_info->kill);
3171 /* There may have been code deleted by the dce pass run before
3173 if (insn_info->insn && INSN_P (insn_info->insn))
3175 /* Process the read(s) last. */
3178 scan_stores_spill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3179 scan_reads_spill (insn_info->read_rec, bb_info->gen, bb_info->kill);
3183 scan_stores_nospill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3184 scan_reads_nospill (insn_info, bb_info->gen, bb_info->kill);
3188 insn_info = insn_info->prev_insn;
3193 /* Set the gen set of the exit block, and also any block with no
3194 successors that does not have a wild read. */
3197 dse_step3_exit_block_scan (bb_info_t bb_info)
3199 /* The gen set is all 0's for the exit block except for the
3200 frame_pointer_group. */
3202 if (stores_off_frame_dead_at_return)
3207 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
3209 if (group->process_globally && group->frame_related)
3210 bitmap_ior_into (bb_info->gen, group->group_kill);
3216 /* Find all of the blocks that are not backwards reachable from the
3217 exit block or any block with no successors (BB). These are the
3218 infinite loops or infinite self loops. These blocks will still
3219 have their bits set in UNREACHABLE_BLOCKS. */
3222 mark_reachable_blocks (sbitmap unreachable_blocks, basic_block bb)
3227 if (TEST_BIT (unreachable_blocks, bb->index))
3229 RESET_BIT (unreachable_blocks, bb->index);
3230 FOR_EACH_EDGE (e, ei, bb->preds)
3232 mark_reachable_blocks (unreachable_blocks, e->src);
3237 /* Build the transfer functions for the function. */
3240 dse_step3 (bool for_spills)
3243 sbitmap unreachable_blocks = sbitmap_alloc (last_basic_block);
3244 sbitmap_iterator sbi;
3245 bitmap all_ones = NULL;
3248 sbitmap_ones (unreachable_blocks);
3252 bb_info_t bb_info = bb_table[bb->index];
3254 bitmap_clear (bb_info->gen);
3256 bb_info->gen = BITMAP_ALLOC (NULL);
3258 if (bb->index == ENTRY_BLOCK)
3260 else if (bb->index == EXIT_BLOCK)
3261 dse_step3_exit_block_scan (bb_info);
3263 dse_step3_scan (for_spills, bb);
3264 if (EDGE_COUNT (bb->succs) == 0)
3265 mark_reachable_blocks (unreachable_blocks, bb);
3267 /* If this is the second time dataflow is run, delete the old
3270 BITMAP_FREE (bb_info->in);
3272 BITMAP_FREE (bb_info->out);
3275 /* For any block in an infinite loop, we must initialize the out set
3276 to all ones. This could be expensive, but almost never occurs in
3277 practice. However, it is common in regression tests. */
3278 EXECUTE_IF_SET_IN_SBITMAP (unreachable_blocks, 0, i, sbi)
3280 if (bitmap_bit_p (all_blocks, i))
3282 bb_info_t bb_info = bb_table[i];
3288 all_ones = BITMAP_ALLOC (NULL);
3289 for (j = 0; VEC_iterate (group_info_t, rtx_group_vec, j, group); j++)
3290 bitmap_ior_into (all_ones, group->group_kill);
3294 bb_info->out = BITMAP_ALLOC (NULL);
3295 bitmap_copy (bb_info->out, all_ones);
3301 BITMAP_FREE (all_ones);
3302 sbitmap_free (unreachable_blocks);
3307 /*----------------------------------------------------------------------------
3310 Solve the bitvector equations.
3311 ----------------------------------------------------------------------------*/
3314 /* Confluence function for blocks with no successors. Create an out
3315 set from the gen set of the exit block. This block logically has
3316 the exit block as a successor. */
3321 dse_confluence_0 (basic_block bb)
3323 bb_info_t bb_info = bb_table[bb->index];
3325 if (bb->index == EXIT_BLOCK)
3330 bb_info->out = BITMAP_ALLOC (NULL);
3331 bitmap_copy (bb_info->out, bb_table[EXIT_BLOCK]->gen);
3335 /* Propagate the information from the in set of the dest of E to the
3336 out set of the src of E. If the various in or out sets are not
3337 there, that means they are all ones. */
3340 dse_confluence_n (edge e)
3342 bb_info_t src_info = bb_table[e->src->index];
3343 bb_info_t dest_info = bb_table[e->dest->index];
3348 bitmap_and_into (src_info->out, dest_info->in);
3351 src_info->out = BITMAP_ALLOC (NULL);
3352 bitmap_copy (src_info->out, dest_info->in);
3358 /* Propagate the info from the out to the in set of BB_INDEX's basic
3359 block. There are three cases:
3361 1) The block has no kill set. In this case the kill set is all
3362 ones. It does not matter what the out set of the block is, none of
3363 the info can reach the top. The only thing that reaches the top is
3364 the gen set and we just copy the set.
3366 2) There is a kill set but no out set and bb has successors. In
3367 this case we just return. Eventually an out set will be created and
3368 it is better to wait than to create a set of ones.
3370 3) There is both a kill and out set. We apply the obvious transfer
3375 dse_transfer_function (int bb_index)
3377 bb_info_t bb_info = bb_table[bb_index];
3385 return bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3386 bb_info->out, bb_info->kill);
3389 bb_info->in = BITMAP_ALLOC (NULL);
3390 bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3391 bb_info->out, bb_info->kill);
3401 /* Case 1 above. If there is already an in set, nothing
3407 bb_info->in = BITMAP_ALLOC (NULL);
3408 bitmap_copy (bb_info->in, bb_info->gen);
3414 /* Solve the dataflow equations. */
3419 df_simple_dataflow (DF_BACKWARD, NULL, dse_confluence_0,
3420 dse_confluence_n, dse_transfer_function,
3421 all_blocks, df_get_postorder (DF_BACKWARD),
3422 df_get_n_blocks (DF_BACKWARD));
3427 fprintf (dump_file, "\n\n*** Global dataflow info after analysis.\n");
3430 bb_info_t bb_info = bb_table[bb->index];
3432 df_print_bb_index (bb, dump_file);
3434 bitmap_print (dump_file, bb_info->in, " in: ", "\n");
3436 fprintf (dump_file, " in: *MISSING*\n");
3438 bitmap_print (dump_file, bb_info->gen, " gen: ", "\n");
3440 fprintf (dump_file, " gen: *MISSING*\n");
3442 bitmap_print (dump_file, bb_info->kill, " kill: ", "\n");
3444 fprintf (dump_file, " kill: *MISSING*\n");
3446 bitmap_print (dump_file, bb_info->out, " out: ", "\n");
3448 fprintf (dump_file, " out: *MISSING*\n\n");
3455 /*----------------------------------------------------------------------------
3458 Delete the stores that can only be deleted using the global information.
3459 ----------------------------------------------------------------------------*/
3463 dse_step5_nospill (void)
3468 bb_info_t bb_info = bb_table[bb->index];
3469 insn_info_t insn_info = bb_info->last_insn;
3470 bitmap v = bb_info->out;
3474 bool deleted = false;
3475 if (dump_file && insn_info->insn)
3477 fprintf (dump_file, "starting to process insn %d\n",
3478 INSN_UID (insn_info->insn));
3479 bitmap_print (dump_file, v, " v: ", "\n");
3482 /* There may have been code deleted by the dce pass run before
3485 && INSN_P (insn_info->insn)
3486 && (!insn_info->cannot_delete)
3487 && (!bitmap_empty_p (v)))
3489 store_info_t store_info = insn_info->store_rec;
3491 /* Try to delete the current insn. */
3494 /* Skip the clobbers. */
3495 while (!store_info->is_set)
3496 store_info = store_info->next;
3498 if (store_info->alias_set)
3503 group_info_t group_info
3504 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
3506 for (i = store_info->begin; i < store_info->end; i++)
3508 int index = get_bitmap_index (group_info, i);
3511 fprintf (dump_file, "i = %d, index = %d\n", (int)i, index);
3512 if (index == 0 || !bitmap_bit_p (v, index))
3515 fprintf (dump_file, "failing at i = %d\n", (int)i);
3525 check_for_inc_dec (insn_info->insn);
3526 delete_insn (insn_info->insn);
3527 insn_info->insn = NULL;
3532 /* We do want to process the local info if the insn was
3533 deleted. For instance, if the insn did a wild read, we
3534 no longer need to trash the info. */
3536 && INSN_P (insn_info->insn)
3539 scan_stores_nospill (insn_info->store_rec, v, NULL);
3540 if (insn_info->wild_read)
3543 fprintf (dump_file, "wild read\n");
3546 else if (insn_info->read_rec)
3549 fprintf (dump_file, "regular read\n");
3550 scan_reads_nospill (insn_info, v, NULL);
3554 insn_info = insn_info->prev_insn;
3561 dse_step5_spill (void)
3566 bb_info_t bb_info = bb_table[bb->index];
3567 insn_info_t insn_info = bb_info->last_insn;
3568 bitmap v = bb_info->out;
3572 bool deleted = false;
3573 /* There may have been code deleted by the dce pass run before
3576 && INSN_P (insn_info->insn)
3577 && (!insn_info->cannot_delete)
3578 && (!bitmap_empty_p (v)))
3580 /* Try to delete the current insn. */
3581 store_info_t store_info = insn_info->store_rec;
3586 if (store_info->alias_set)
3588 int index = get_bitmap_index (clear_alias_group,
3589 store_info->alias_set);
3590 if (index == 0 || !bitmap_bit_p (v, index))
3598 store_info = store_info->next;
3600 if (deleted && dbg_cnt (dse))
3603 fprintf (dump_file, "Spill deleting insn %d\n",
3604 INSN_UID (insn_info->insn));
3605 check_for_inc_dec (insn_info->insn);
3606 delete_insn (insn_info->insn);
3608 insn_info->insn = NULL;
3613 && INSN_P (insn_info->insn)
3616 scan_stores_spill (insn_info->store_rec, v, NULL);
3617 scan_reads_spill (insn_info->read_rec, v, NULL);
3620 insn_info = insn_info->prev_insn;
3627 /*----------------------------------------------------------------------------
3630 Delete stores made redundant by earlier stores (which store the same
3631 value) that couldn't be eliminated.
3632 ----------------------------------------------------------------------------*/
3641 bb_info_t bb_info = bb_table[bb->index];
3642 insn_info_t insn_info = bb_info->last_insn;
3646 /* There may have been code deleted by the dce pass run before
3649 && INSN_P (insn_info->insn)
3650 && !insn_info->cannot_delete)
3652 store_info_t s_info = insn_info->store_rec;
3654 while (s_info && !s_info->is_set)
3655 s_info = s_info->next;
3657 && s_info->redundant_reason
3658 && s_info->redundant_reason->insn
3659 && INSN_P (s_info->redundant_reason->insn))
3661 rtx rinsn = s_info->redundant_reason->insn;
3663 fprintf (dump_file, "Locally deleting insn %d "
3664 "because insn %d stores the "
3665 "same value and couldn't be "
3667 INSN_UID (insn_info->insn),
3669 delete_dead_store_insn (insn_info);
3672 insn_info = insn_info->prev_insn;
3677 /*----------------------------------------------------------------------------
3680 Destroy everything left standing.
3681 ----------------------------------------------------------------------------*/
3684 dse_step7 (bool global_done)
3690 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
3692 free (group->offset_map_n);
3693 free (group->offset_map_p);
3694 BITMAP_FREE (group->store1_n);
3695 BITMAP_FREE (group->store1_p);
3696 BITMAP_FREE (group->store2_n);
3697 BITMAP_FREE (group->store2_p);
3698 BITMAP_FREE (group->group_kill);
3704 bb_info_t bb_info = bb_table[bb->index];
3705 BITMAP_FREE (bb_info->gen);
3707 BITMAP_FREE (bb_info->kill);
3709 BITMAP_FREE (bb_info->in);
3711 BITMAP_FREE (bb_info->out);
3714 if (clear_alias_sets)
3716 BITMAP_FREE (clear_alias_sets);
3717 BITMAP_FREE (disqualified_clear_alias_sets);
3718 free_alloc_pool (clear_alias_mode_pool);
3719 htab_delete (clear_alias_mode_table);
3722 end_alias_analysis ();
3724 htab_delete (rtx_group_table);
3725 VEC_free (group_info_t, heap, rtx_group_vec);
3726 BITMAP_FREE (all_blocks);
3727 BITMAP_FREE (scratch);
3729 free_alloc_pool (rtx_store_info_pool);
3730 free_alloc_pool (read_info_pool);
3731 free_alloc_pool (insn_info_pool);
3732 free_alloc_pool (bb_info_pool);
3733 free_alloc_pool (rtx_group_info_pool);
3734 free_alloc_pool (deferred_change_pool);
3738 /* -------------------------------------------------------------------------
3740 ------------------------------------------------------------------------- */
3742 /* Callback for running pass_rtl_dse. */
3745 rest_of_handle_dse (void)
3747 bool did_global = false;
3749 df_set_flags (DF_DEFER_INSN_RESCAN);
3751 /* Need the notes since we must track live hardregs in the forwards
3753 df_note_add_problem ();
3759 if (dse_step2_nospill ())
3761 df_set_flags (DF_LR_RUN_DCE);
3765 fprintf (dump_file, "doing global processing\n");
3768 dse_step5_nospill ();
3771 /* For the instance of dse that runs after reload, we make a special
3772 pass to process the spills. These are special in that they are
3773 totally transparent, i.e, there is no aliasing issues that need
3774 to be considered. This means that the wild reads that kill
3775 everything else do not apply here. */
3776 if (clear_alias_sets && dse_step2_spill ())
3780 df_set_flags (DF_LR_RUN_DCE);
3785 fprintf (dump_file, "doing global spill processing\n");
3792 dse_step7 (did_global);
3795 fprintf (dump_file, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3796 locally_deleted, globally_deleted, spill_deleted);
3803 return gate_dse1 () || gate_dse2 ();
3809 return optimize > 0 && flag_dse
3816 return optimize > 0 && flag_dse
3820 struct rtl_opt_pass pass_rtl_dse1 =
3825 gate_dse1, /* gate */
3826 rest_of_handle_dse, /* execute */
3829 0, /* static_pass_number */
3830 TV_DSE1, /* tv_id */
3831 0, /* properties_required */
3832 0, /* properties_provided */
3833 0, /* properties_destroyed */
3834 0, /* todo_flags_start */
3836 TODO_df_finish | TODO_verify_rtl_sharing |
3837 TODO_ggc_collect /* todo_flags_finish */
3841 struct rtl_opt_pass pass_rtl_dse2 =
3846 gate_dse2, /* gate */
3847 rest_of_handle_dse, /* execute */
3850 0, /* static_pass_number */
3851 TV_DSE2, /* tv_id */
3852 0, /* properties_required */
3853 0, /* properties_provided */
3854 0, /* properties_destroyed */
3855 0, /* todo_flags_start */
3857 TODO_df_finish | TODO_verify_rtl_sharing |
3858 TODO_ggc_collect /* todo_flags_finish */