1 /* RTL dead store elimination.
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
5 Contributed by Richard Sandiford <rsandifor@codesourcery.com>
6 and Kenneth Zadeck <zadeck@naturalbridge.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
28 #include "coretypes.h"
35 #include "hard-reg-set.h"
40 #include "tree-pass.h"
41 #include "alloc-pool.h"
43 #include "insn-config.h"
51 /* This file contains three techniques for performing Dead Store
54 * The first technique performs dse locally on any base address. It
55 is based on the cselib which is a local value numbering technique.
56 This technique is local to a basic block but deals with a fairly
59 * The second technique performs dse globally but is restricted to
60 base addresses that are either constant or are relative to the
63 * The third technique, (which is only done after register allocation)
64 processes the spill spill slots. This differs from the second
65 technique because it takes advantage of the fact that spilling is
66 completely free from the effects of aliasing.
68 Logically, dse is a backwards dataflow problem. A store can be
69 deleted if it if cannot be reached in the backward direction by any
70 use of the value being stored. However, the local technique uses a
71 forwards scan of the basic block because cselib requires that the
72 block be processed in that order.
74 The pass is logically broken into 7 steps:
78 1) The local algorithm, as well as scanning the insns for the two
81 2) Analysis to see if the global algs are necessary. In the case
82 of stores base on a constant address, there must be at least two
83 stores to that address, to make it possible to delete some of the
84 stores. In the case of stores off of the frame or spill related
85 stores, only one store to an address is necessary because those
86 stores die at the end of the function.
88 3) Set up the global dataflow equations based on processing the
89 info parsed in the first step.
91 4) Solve the dataflow equations.
93 5) Delete the insns that the global analysis has indicated are
96 6) Delete insns that store the same value as preceeding store
97 where the earlier store couldn't be eliminated.
101 This step uses cselib and canon_rtx to build the largest expression
102 possible for each address. This pass is a forwards pass through
103 each basic block. From the point of view of the global technique,
104 the first pass could examine a block in either direction. The
105 forwards ordering is to accommodate cselib.
107 We a simplifying assumption: addresses fall into four broad
110 1) base has rtx_varies_p == false, offset is constant.
111 2) base has rtx_varies_p == false, offset variable.
112 3) base has rtx_varies_p == true, offset constant.
113 4) base has rtx_varies_p == true, offset variable.
115 The local passes are able to process all 4 kinds of addresses. The
116 global pass only handles (1).
118 The global problem is formulated as follows:
120 A store, S1, to address A, where A is not relative to the stack
121 frame, can be eliminated if all paths from S1 to the end of the
122 of the function contain another store to A before a read to A.
124 If the address A is relative to the stack frame, a store S2 to A
125 can be eliminated if there are no paths from S1 that reach the
126 end of the function that read A before another store to A. In
127 this case S2 can be deleted if there are paths to from S2 to the
128 end of the function that have no reads or writes to A. This
129 second case allows stores to the stack frame to be deleted that
130 would otherwise die when the function returns. This cannot be
131 done if stores_off_frame_dead_at_return is not true. See the doc
132 for that variable for when this variable is false.
134 The global problem is formulated as a backwards set union
135 dataflow problem where the stores are the gens and reads are the
136 kills. Set union problems are rare and require some special
137 handling given our representation of bitmaps. A straightforward
138 implementation of requires a lot of bitmaps filled with 1s.
139 These are expensive and cumbersome in our bitmap formulation so
140 care has been taken to avoid large vectors filled with 1s. See
141 the comments in bb_info and in the dataflow confluence functions
144 There are two places for further enhancements to this algorithm:
146 1) The original dse which was embedded in a pass called flow also
147 did local address forwarding. For example in
152 flow would replace the right hand side of the second insn with a
153 reference to r100. Most of the information is available to add this
154 to this pass. It has not done it because it is a lot of work in
155 the case that either r100 is assigned to between the first and
156 second insn and/or the second insn is a load of part of the value
157 stored by the first insn.
159 insn 5 in gcc.c-torture/compile/990203-1.c simple case.
160 insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
161 insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
162 insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
164 2) The cleaning up of spill code is quite profitable. It currently
165 depends on reading tea leaves and chicken entrails left by reload.
166 This pass depends on reload creating a singleton alias set for each
167 spill slot and telling the next dse pass which of these alias sets
168 are the singletons. Rather than analyze the addresses of the
169 spills, dse's spill processing just does analysis of the loads and
170 stores that use those alias sets. There are three cases where this
173 a) Reload sometimes creates the slot for one mode of access, and
174 then inserts loads and/or stores for a smaller mode. In this
175 case, the current code just punts on the slot. The proper thing
176 to do is to back out and use one bit vector position for each
177 byte of the entity associated with the slot. This depends on
178 KNOWING that reload always generates the accesses for each of the
179 bytes in some canonical (read that easy to understand several
180 passes after reload happens) way.
182 b) Reload sometimes decides that spill slot it allocated was not
183 large enough for the mode and goes back and allocates more slots
184 with the same mode and alias set. The backout in this case is a
185 little more graceful than (a). In this case the slot is unmarked
186 as being a spill slot and if final address comes out to be based
187 off the frame pointer, the global algorithm handles this slot.
189 c) For any pass that may prespill, there is currently no
190 mechanism to tell the dse pass that the slot being used has the
191 special properties that reload uses. It may be that all that is
192 required is to have those passes make the same calls that reload
193 does, assuming that the alias sets can be manipulated in the same
196 /* There are limits to the size of constant offsets we model for the
197 global problem. There are certainly test cases, that exceed this
198 limit, however, it is unlikely that there are important programs
199 that really have constant offsets this size. */
200 #define MAX_OFFSET (64 * 1024)
203 static bitmap scratch = NULL;
206 /* This structure holds information about a candidate store. */
210 /* False means this is a clobber. */
213 /* False if a single HOST_WIDE_INT bitmap is used for positions_needed. */
216 /* The id of the mem group of the base address. If rtx_varies_p is
217 true, this is -1. Otherwise, it is the index into the group
221 /* This is the cselib value. */
222 cselib_val *cse_base;
224 /* This canonized mem. */
227 /* Canonized MEM address for use by canon_true_dependence. */
230 /* If this is non-zero, it is the alias set of a spill location. */
231 alias_set_type alias_set;
233 /* The offset of the first and byte before the last byte associated
234 with the operation. */
235 HOST_WIDE_INT begin, end;
239 /* A bitmask as wide as the number of bytes in the word that
240 contains a 1 if the byte may be needed. The store is unused if
241 all of the bits are 0. This is used if IS_LARGE is false. */
242 unsigned HOST_WIDE_INT small_bitmask;
246 /* A bitmap with one bit per byte. Cleared bit means the position
247 is needed. Used if IS_LARGE is false. */
250 /* Number of set bits (i.e. unneeded bytes) in BITMAP. If it is
251 equal to END - BEGIN, the whole store is unused. */
256 /* The next store info for this insn. */
257 struct store_info *next;
259 /* The right hand side of the store. This is used if there is a
260 subsequent reload of the mems address somewhere later in the
264 /* If rhs is or holds a constant, this contains that constant,
268 /* Set if this store stores the same constant value as REDUNDANT_REASON
269 insn stored. These aren't eliminated early, because doing that
270 might prevent the earlier larger store to be eliminated. */
271 struct insn_info *redundant_reason;
274 /* Return a bitmask with the first N low bits set. */
276 static unsigned HOST_WIDE_INT
277 lowpart_bitmask (int n)
279 unsigned HOST_WIDE_INT mask = ~(unsigned HOST_WIDE_INT) 0;
280 return mask >> (HOST_BITS_PER_WIDE_INT - n);
283 typedef struct store_info *store_info_t;
284 static alloc_pool cse_store_info_pool;
285 static alloc_pool rtx_store_info_pool;
287 /* This structure holds information about a load. These are only
288 built for rtx bases. */
291 /* The id of the mem group of the base address. */
294 /* If this is non-zero, it is the alias set of a spill location. */
295 alias_set_type alias_set;
297 /* The offset of the first and byte after the last byte associated
298 with the operation. If begin == end == 0, the read did not have
299 a constant offset. */
302 /* The mem being read. */
305 /* The next read_info for this insn. */
306 struct read_info *next;
308 typedef struct read_info *read_info_t;
309 static alloc_pool read_info_pool;
312 /* One of these records is created for each insn. */
316 /* Set true if the insn contains a store but the insn itself cannot
317 be deleted. This is set if the insn is a parallel and there is
318 more than one non dead output or if the insn is in some way
322 /* This field is only used by the global algorithm. It is set true
323 if the insn contains any read of mem except for a (1). This is
324 also set if the insn is a call or has a clobber mem. If the insn
325 contains a wild read, the use_rec will be null. */
328 /* This field is only used for the processing of const functions.
329 These functions cannot read memory, but they can read the stack
330 because that is where they may get their parms. We need to be
331 this conservative because, like the store motion pass, we don't
332 consider CALL_INSN_FUNCTION_USAGE when processing call insns.
333 Moreover, we need to distinguish two cases:
334 1. Before reload (register elimination), the stores related to
335 outgoing arguments are stack pointer based and thus deemed
336 of non-constant base in this pass. This requires special
337 handling but also means that the frame pointer based stores
338 need not be killed upon encountering a const function call.
339 2. After reload, the stores related to outgoing arguments can be
340 either stack pointer or hard frame pointer based. This means
341 that we have no other choice than also killing all the frame
342 pointer based stores upon encountering a const function call.
343 This field is set after reload for const function calls. Having
344 this set is less severe than a wild read, it just means that all
345 the frame related stores are killed rather than all the stores. */
348 /* This field is only used for the processing of const functions.
349 It is set if the insn may contain a stack pointer based store. */
350 bool stack_pointer_based;
352 /* This is true if any of the sets within the store contains a
353 cselib base. Such stores can only be deleted by the local
355 bool contains_cselib_groups;
360 /* The list of mem sets or mem clobbers that are contained in this
361 insn. If the insn is deletable, it contains only one mem set.
362 But it could also contain clobbers. Insns that contain more than
363 one mem set are not deletable, but each of those mems are here in
364 order to provide info to delete other insns. */
365 store_info_t store_rec;
367 /* The linked list of mem uses in this insn. Only the reads from
368 rtx bases are listed here. The reads to cselib bases are
369 completely processed during the first scan and so are never
371 read_info_t read_rec;
373 /* The prev insn in the basic block. */
374 struct insn_info * prev_insn;
376 /* The linked list of insns that are in consideration for removal in
377 the forwards pass thru the basic block. This pointer may be
378 trash as it is not cleared when a wild read occurs. The only
379 time it is guaranteed to be correct is when the traversal starts
380 at active_local_stores. */
381 struct insn_info * next_local_store;
384 typedef struct insn_info *insn_info_t;
385 static alloc_pool insn_info_pool;
387 /* The linked list of stores that are under consideration in this
389 static insn_info_t active_local_stores;
394 /* Pointer to the insn info for the last insn in the block. These
395 are linked so this is how all of the insns are reached. During
396 scanning this is the current insn being scanned. */
397 insn_info_t last_insn;
399 /* The info for the global dataflow problem. */
402 /* This is set if the transfer function should and in the wild_read
403 bitmap before applying the kill and gen sets. That vector knocks
404 out most of the bits in the bitmap and thus speeds up the
406 bool apply_wild_read;
408 /* The following 4 bitvectors hold information about which positions
409 of which stores are live or dead. They are indexed by
412 /* The set of store positions that exist in this block before a wild read. */
415 /* The set of load positions that exist in this block above the
416 same position of a store. */
419 /* The set of stores that reach the top of the block without being
422 Do not represent the in if it is all ones. Note that this is
423 what the bitvector should logically be initialized to for a set
424 intersection problem. However, like the kill set, this is too
425 expensive. So initially, the in set will only be created for the
426 exit block and any block that contains a wild read. */
429 /* The set of stores that reach the bottom of the block from it's
432 Do not represent the in if it is all ones. Note that this is
433 what the bitvector should logically be initialized to for a set
434 intersection problem. However, like the kill and in set, this is
435 too expensive. So what is done is that the confluence operator
436 just initializes the vector from one of the out sets of the
437 successors of the block. */
440 /* The following bitvector is indexed by the reg number. It
441 contains the set of regs that are live at the current instruction
442 being processed. While it contains info for all of the
443 registers, only the pseudos are actually examined. It is used to
444 assure that shift sequences that are inserted do not accidently
445 clobber live hard regs. */
449 typedef struct bb_info *bb_info_t;
450 static alloc_pool bb_info_pool;
452 /* Table to hold all bb_infos. */
453 static bb_info_t *bb_table;
455 /* There is a group_info for each rtx base that is used to reference
456 memory. There are also not many of the rtx bases because they are
457 very limited in scope. */
461 /* The actual base of the address. */
464 /* The sequential id of the base. This allows us to have a
465 canonical ordering of these that is not based on addresses. */
468 /* True if there are any positions that are to be processed
470 bool process_globally;
472 /* True if the base of this group is either the frame_pointer or
473 hard_frame_pointer. */
476 /* A mem wrapped around the base pointer for the group in order to
477 do read dependency. */
480 /* Canonized version of base_mem's address. */
483 /* These two sets of two bitmaps are used to keep track of how many
484 stores are actually referencing that position from this base. We
485 only do this for rtx bases as this will be used to assign
486 positions in the bitmaps for the global problem. Bit N is set in
487 store1 on the first store for offset N. Bit N is set in store2
488 for the second store to offset N. This is all we need since we
489 only care about offsets that have two or more stores for them.
491 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
492 for 0 and greater offsets.
494 There is one special case here, for stores into the stack frame,
495 we will or store1 into store2 before deciding which stores look
496 at globally. This is because stores to the stack frame that have
497 no other reads before the end of the function can also be
499 bitmap store1_n, store1_p, store2_n, store2_p;
501 /* The positions in this bitmap have the same assignments as the in,
502 out, gen and kill bitmaps. This bitmap is all zeros except for
503 the positions that are occupied by stores for this group. */
506 /* The offset_map is used to map the offsets from this base into
507 positions in the global bitmaps. It is only created after all of
508 the all of stores have been scanned and we know which ones we
510 int *offset_map_n, *offset_map_p;
511 int offset_map_size_n, offset_map_size_p;
513 typedef struct group_info *group_info_t;
514 typedef const struct group_info *const_group_info_t;
515 static alloc_pool rtx_group_info_pool;
517 /* Tables of group_info structures, hashed by base value. */
518 static htab_t rtx_group_table;
520 /* Index into the rtx_group_vec. */
521 static int rtx_group_next_id;
523 DEF_VEC_P(group_info_t);
524 DEF_VEC_ALLOC_P(group_info_t,heap);
526 static VEC(group_info_t,heap) *rtx_group_vec;
529 /* This structure holds the set of changes that are being deferred
530 when removing read operation. See replace_read. */
531 struct deferred_change
534 /* The mem that is being replaced. */
537 /* The reg it is being replaced with. */
540 struct deferred_change *next;
543 typedef struct deferred_change *deferred_change_t;
544 static alloc_pool deferred_change_pool;
546 static deferred_change_t deferred_change_list = NULL;
548 /* This are used to hold the alias sets of spill variables. Since
549 these are never aliased and there may be a lot of them, it makes
550 sense to treat them specially. This bitvector is only allocated in
551 calls from dse_record_singleton_alias_set which currently is only
552 made during reload1. So when dse is called before reload this
553 mechanism does nothing. */
555 static bitmap clear_alias_sets = NULL;
557 /* The set of clear_alias_sets that have been disqualified because
558 there are loads or stores using a different mode than the alias set
559 was registered with. */
560 static bitmap disqualified_clear_alias_sets = NULL;
562 /* The group that holds all of the clear_alias_sets. */
563 static group_info_t clear_alias_group;
565 /* The modes of the clear_alias_sets. */
566 static htab_t clear_alias_mode_table;
568 /* Hash table element to look up the mode for an alias set. */
569 struct clear_alias_mode_holder
571 alias_set_type alias_set;
572 enum machine_mode mode;
575 static alloc_pool clear_alias_mode_pool;
577 /* This is true except if cfun->stdarg -- i.e. we cannot do
578 this for vararg functions because they play games with the frame. */
579 static bool stores_off_frame_dead_at_return;
581 /* Counter for stats. */
582 static int globally_deleted;
583 static int locally_deleted;
584 static int spill_deleted;
586 static bitmap all_blocks;
588 /* The number of bits used in the global bitmaps. */
589 static unsigned int current_position;
592 static bool gate_dse (void);
593 static bool gate_dse1 (void);
594 static bool gate_dse2 (void);
597 /*----------------------------------------------------------------------------
601 ----------------------------------------------------------------------------*/
603 /* Hashtable callbacks for maintaining the "bases" field of
604 store_group_info, given that the addresses are function invariants. */
607 clear_alias_mode_eq (const void *p1, const void *p2)
609 const struct clear_alias_mode_holder * h1
610 = (const struct clear_alias_mode_holder *) p1;
611 const struct clear_alias_mode_holder * h2
612 = (const struct clear_alias_mode_holder *) p2;
613 return h1->alias_set == h2->alias_set;
618 clear_alias_mode_hash (const void *p)
620 const struct clear_alias_mode_holder *holder
621 = (const struct clear_alias_mode_holder *) p;
622 return holder->alias_set;
626 /* Find the entry associated with ALIAS_SET. */
628 static struct clear_alias_mode_holder *
629 clear_alias_set_lookup (alias_set_type alias_set)
631 struct clear_alias_mode_holder tmp_holder;
634 tmp_holder.alias_set = alias_set;
635 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, NO_INSERT);
638 return (struct clear_alias_mode_holder *) *slot;
642 /* Hashtable callbacks for maintaining the "bases" field of
643 store_group_info, given that the addresses are function invariants. */
646 invariant_group_base_eq (const void *p1, const void *p2)
648 const_group_info_t gi1 = (const_group_info_t) p1;
649 const_group_info_t gi2 = (const_group_info_t) p2;
650 return rtx_equal_p (gi1->rtx_base, gi2->rtx_base);
655 invariant_group_base_hash (const void *p)
657 const_group_info_t gi = (const_group_info_t) p;
659 return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false);
663 /* Get the GROUP for BASE. Add a new group if it is not there. */
666 get_group_info (rtx base)
668 struct group_info tmp_gi;
674 /* Find the store_base_info structure for BASE, creating a new one
676 tmp_gi.rtx_base = base;
677 slot = htab_find_slot (rtx_group_table, &tmp_gi, INSERT);
678 gi = (group_info_t) *slot;
682 if (!clear_alias_group)
684 clear_alias_group = gi =
685 (group_info_t) pool_alloc (rtx_group_info_pool);
686 memset (gi, 0, sizeof (struct group_info));
687 gi->id = rtx_group_next_id++;
688 gi->store1_n = BITMAP_ALLOC (NULL);
689 gi->store1_p = BITMAP_ALLOC (NULL);
690 gi->store2_n = BITMAP_ALLOC (NULL);
691 gi->store2_p = BITMAP_ALLOC (NULL);
692 gi->group_kill = BITMAP_ALLOC (NULL);
693 gi->process_globally = false;
694 gi->offset_map_size_n = 0;
695 gi->offset_map_size_p = 0;
696 gi->offset_map_n = NULL;
697 gi->offset_map_p = NULL;
698 VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);
700 return clear_alias_group;
705 *slot = gi = (group_info_t) pool_alloc (rtx_group_info_pool);
707 gi->id = rtx_group_next_id++;
708 gi->base_mem = gen_rtx_MEM (QImode, base);
709 gi->canon_base_addr = canon_rtx (base);
710 gi->store1_n = BITMAP_ALLOC (NULL);
711 gi->store1_p = BITMAP_ALLOC (NULL);
712 gi->store2_n = BITMAP_ALLOC (NULL);
713 gi->store2_p = BITMAP_ALLOC (NULL);
714 gi->group_kill = BITMAP_ALLOC (NULL);
715 gi->process_globally = false;
717 (base == frame_pointer_rtx) || (base == hard_frame_pointer_rtx);
718 gi->offset_map_size_n = 0;
719 gi->offset_map_size_p = 0;
720 gi->offset_map_n = NULL;
721 gi->offset_map_p = NULL;
722 VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);
729 /* Initialization of data structures. */
735 globally_deleted = 0;
738 scratch = BITMAP_ALLOC (NULL);
741 = create_alloc_pool ("rtx_store_info_pool",
742 sizeof (struct store_info), 100);
744 = create_alloc_pool ("read_info_pool",
745 sizeof (struct read_info), 100);
747 = create_alloc_pool ("insn_info_pool",
748 sizeof (struct insn_info), 100);
750 = create_alloc_pool ("bb_info_pool",
751 sizeof (struct bb_info), 100);
753 = create_alloc_pool ("rtx_group_info_pool",
754 sizeof (struct group_info), 100);
756 = create_alloc_pool ("deferred_change_pool",
757 sizeof (struct deferred_change), 10);
759 rtx_group_table = htab_create (11, invariant_group_base_hash,
760 invariant_group_base_eq, NULL);
762 bb_table = XCNEWVEC (bb_info_t, last_basic_block);
763 rtx_group_next_id = 0;
765 stores_off_frame_dead_at_return = !cfun->stdarg;
767 init_alias_analysis ();
769 if (clear_alias_sets)
770 clear_alias_group = get_group_info (NULL);
772 clear_alias_group = NULL;
777 /*----------------------------------------------------------------------------
780 Scan all of the insns. Any random ordering of the blocks is fine.
781 Each block is scanned in forward order to accommodate cselib which
782 is used to remove stores with non-constant bases.
783 ----------------------------------------------------------------------------*/
785 /* Delete all of the store_info recs from INSN_INFO. */
788 free_store_info (insn_info_t insn_info)
790 store_info_t store_info = insn_info->store_rec;
793 store_info_t next = store_info->next;
794 if (store_info->is_large)
795 BITMAP_FREE (store_info->positions_needed.large.bmap);
796 if (store_info->cse_base)
797 pool_free (cse_store_info_pool, store_info);
799 pool_free (rtx_store_info_pool, store_info);
803 insn_info->cannot_delete = true;
804 insn_info->contains_cselib_groups = false;
805 insn_info->store_rec = NULL;
815 /* Add an insn to do the add inside a x if it is a
816 PRE/POST-INC/DEC/MODIFY. D is an structure containing the insn and
817 the size of the mode of the MEM that this is inside of. */
820 replace_inc_dec (rtx *r, void *d)
823 struct insn_size *data = (struct insn_size *)d;
824 switch (GET_CODE (x))
829 rtx r1 = XEXP (x, 0);
830 rtx c = gen_int_mode (data->size, GET_MODE (r1));
831 emit_insn_before (gen_rtx_SET (VOIDmode, r1,
832 gen_rtx_PLUS (GET_MODE (r1), r1, c)),
840 rtx r1 = XEXP (x, 0);
841 rtx c = gen_int_mode (-data->size, GET_MODE (r1));
842 emit_insn_before (gen_rtx_SET (VOIDmode, r1,
843 gen_rtx_PLUS (GET_MODE (r1), r1, c)),
851 /* We can reuse the add because we are about to delete the
852 insn that contained it. */
853 rtx add = XEXP (x, 0);
854 rtx r1 = XEXP (add, 0);
855 emit_insn_before (gen_rtx_SET (VOIDmode, r1, add), data->insn);
865 /* If X is a MEM, check the address to see if it is PRE/POST-INC/DEC/MODIFY
866 and generate an add to replace that. */
869 replace_inc_dec_mem (rtx *r, void *d)
872 if (x != NULL_RTX && MEM_P (x))
874 struct insn_size data;
876 data.size = GET_MODE_SIZE (GET_MODE (x));
879 for_each_rtx (&XEXP (x, 0), replace_inc_dec, &data);
886 /* Before we delete INSN, make sure that the auto inc/dec, if it is
887 there, is split into a separate insn. */
890 check_for_inc_dec (rtx insn)
892 rtx note = find_reg_note (insn, REG_INC, NULL_RTX);
894 for_each_rtx (&insn, replace_inc_dec_mem, insn);
898 /* Delete the insn and free all of the fields inside INSN_INFO. */
901 delete_dead_store_insn (insn_info_t insn_info)
903 read_info_t read_info;
908 check_for_inc_dec (insn_info->insn);
911 fprintf (dump_file, "Locally deleting insn %d ",
912 INSN_UID (insn_info->insn));
913 if (insn_info->store_rec->alias_set)
914 fprintf (dump_file, "alias set %d\n",
915 (int) insn_info->store_rec->alias_set);
917 fprintf (dump_file, "\n");
920 free_store_info (insn_info);
921 read_info = insn_info->read_rec;
925 read_info_t next = read_info->next;
926 pool_free (read_info_pool, read_info);
929 insn_info->read_rec = NULL;
931 delete_insn (insn_info->insn);
933 insn_info->insn = NULL;
935 insn_info->wild_read = false;
939 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
943 set_usage_bits (group_info_t group, HOST_WIDE_INT offset, HOST_WIDE_INT width)
947 if (offset > -MAX_OFFSET && offset + width < MAX_OFFSET)
948 for (i=offset; i<offset+width; i++)
955 store1 = group->store1_n;
956 store2 = group->store2_n;
961 store1 = group->store1_p;
962 store2 = group->store2_p;
966 if (!bitmap_set_bit (store1, ai))
967 bitmap_set_bit (store2, ai);
972 if (group->offset_map_size_n < ai)
973 group->offset_map_size_n = ai;
977 if (group->offset_map_size_p < ai)
978 group->offset_map_size_p = ai;
985 /* Set the BB_INFO so that the last insn is marked as a wild read. */
988 add_wild_read (bb_info_t bb_info)
990 insn_info_t insn_info = bb_info->last_insn;
991 read_info_t *ptr = &insn_info->read_rec;
995 read_info_t next = (*ptr)->next;
996 if ((*ptr)->alias_set == 0)
998 pool_free (read_info_pool, *ptr);
1002 ptr = &(*ptr)->next;
1004 insn_info->wild_read = true;
1005 active_local_stores = NULL;
1009 /* Return true if X is a constant or one of the registers that behave
1010 as a constant over the life of a function. This is equivalent to
1011 !rtx_varies_p for memory addresses. */
1014 const_or_frame_p (rtx x)
1016 switch (GET_CODE (x))
1027 /* Note that we have to test for the actual rtx used for the frame
1028 and arg pointers and not just the register number in case we have
1029 eliminated the frame and/or arg pointer and are using it
1031 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
1032 /* The arg pointer varies if it is not a fixed register. */
1033 || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
1034 || x == pic_offset_table_rtx)
1043 /* Take all reasonable action to put the address of MEM into the form
1044 that we can do analysis on.
1046 The gold standard is to get the address into the form: address +
1047 OFFSET where address is something that rtx_varies_p considers a
1048 constant. When we can get the address in this form, we can do
1049 global analysis on it. Note that for constant bases, address is
1050 not actually returned, only the group_id. The address can be
1053 If that fails, we try cselib to get a value we can at least use
1054 locally. If that fails we return false.
1056 The GROUP_ID is set to -1 for cselib bases and the index of the
1057 group for non_varying bases.
1059 FOR_READ is true if this is a mem read and false if not. */
1062 canon_address (rtx mem,
1063 alias_set_type *alias_set_out,
1065 HOST_WIDE_INT *offset,
1068 enum machine_mode address_mode
1069 = targetm.addr_space.address_mode (MEM_ADDR_SPACE (mem));
1070 rtx mem_address = XEXP (mem, 0);
1071 rtx expanded_address, address;
1074 /* Make sure that cselib is has initialized all of the operands of
1075 the address before asking it to do the subst. */
1077 if (clear_alias_sets)
1079 /* If this is a spill, do not do any further processing. */
1080 alias_set_type alias_set = MEM_ALIAS_SET (mem);
1082 fprintf (dump_file, "found alias set %d\n", (int) alias_set);
1083 if (bitmap_bit_p (clear_alias_sets, alias_set))
1085 struct clear_alias_mode_holder *entry
1086 = clear_alias_set_lookup (alias_set);
1088 /* If the modes do not match, we cannot process this set. */
1089 if (entry->mode != GET_MODE (mem))
1093 "disqualifying alias set %d, (%s) != (%s)\n",
1094 (int) alias_set, GET_MODE_NAME (entry->mode),
1095 GET_MODE_NAME (GET_MODE (mem)));
1097 bitmap_set_bit (disqualified_clear_alias_sets, alias_set);
1101 *alias_set_out = alias_set;
1102 *group_id = clear_alias_group->id;
1109 cselib_lookup (mem_address, address_mode, 1);
1113 fprintf (dump_file, " mem: ");
1114 print_inline_rtx (dump_file, mem_address, 0);
1115 fprintf (dump_file, "\n");
1118 /* First see if just canon_rtx (mem_address) is const or frame,
1119 if not, try cselib_expand_value_rtx and call canon_rtx on that. */
1121 for (expanded = 0; expanded < 2; expanded++)
1125 /* Use cselib to replace all of the reg references with the full
1126 expression. This will take care of the case where we have
1128 r_x = base + offset;
1133 val = *(base + offset); */
1135 expanded_address = cselib_expand_value_rtx (mem_address,
1138 /* If this fails, just go with the address from first
1140 if (!expanded_address)
1144 expanded_address = mem_address;
1146 /* Split the address into canonical BASE + OFFSET terms. */
1147 address = canon_rtx (expanded_address);
1155 fprintf (dump_file, "\n after cselib_expand address: ");
1156 print_inline_rtx (dump_file, expanded_address, 0);
1157 fprintf (dump_file, "\n");
1160 fprintf (dump_file, "\n after canon_rtx address: ");
1161 print_inline_rtx (dump_file, address, 0);
1162 fprintf (dump_file, "\n");
1165 if (GET_CODE (address) == CONST)
1166 address = XEXP (address, 0);
1168 if (GET_CODE (address) == PLUS
1169 && CONST_INT_P (XEXP (address, 1)))
1171 *offset = INTVAL (XEXP (address, 1));
1172 address = XEXP (address, 0);
1175 if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem))
1176 && const_or_frame_p (address))
1178 group_info_t group = get_group_info (address);
1181 fprintf (dump_file, " gid=%d offset=%d \n",
1182 group->id, (int)*offset);
1184 *group_id = group->id;
1189 *base = cselib_lookup (address, address_mode, true);
1195 fprintf (dump_file, " no cselib val - should be a wild read.\n");
1199 fprintf (dump_file, " varying cselib base=%u:%u offset = %d\n",
1200 (*base)->uid, (*base)->hash, (int)*offset);
1205 /* Clear the rhs field from the active_local_stores array. */
1208 clear_rhs_from_active_local_stores (void)
1210 insn_info_t ptr = active_local_stores;
1214 store_info_t store_info = ptr->store_rec;
1215 /* Skip the clobbers. */
1216 while (!store_info->is_set)
1217 store_info = store_info->next;
1219 store_info->rhs = NULL;
1220 store_info->const_rhs = NULL;
1222 ptr = ptr->next_local_store;
1227 /* Mark byte POS bytes from the beginning of store S_INFO as unneeded. */
1230 set_position_unneeded (store_info_t s_info, int pos)
1232 if (__builtin_expect (s_info->is_large, false))
1234 if (bitmap_set_bit (s_info->positions_needed.large.bmap, pos))
1235 s_info->positions_needed.large.count++;
1238 s_info->positions_needed.small_bitmask
1239 &= ~(((unsigned HOST_WIDE_INT) 1) << pos);
1242 /* Mark the whole store S_INFO as unneeded. */
1245 set_all_positions_unneeded (store_info_t s_info)
1247 if (__builtin_expect (s_info->is_large, false))
1249 int pos, end = s_info->end - s_info->begin;
1250 for (pos = 0; pos < end; pos++)
1251 bitmap_set_bit (s_info->positions_needed.large.bmap, pos);
1252 s_info->positions_needed.large.count = end;
1255 s_info->positions_needed.small_bitmask = (unsigned HOST_WIDE_INT) 0;
1258 /* Return TRUE if any bytes from S_INFO store are needed. */
1261 any_positions_needed_p (store_info_t s_info)
1263 if (__builtin_expect (s_info->is_large, false))
1264 return (s_info->positions_needed.large.count
1265 < s_info->end - s_info->begin);
1267 return (s_info->positions_needed.small_bitmask
1268 != (unsigned HOST_WIDE_INT) 0);
1271 /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
1272 store are needed. */
1275 all_positions_needed_p (store_info_t s_info, int start, int width)
1277 if (__builtin_expect (s_info->is_large, false))
1279 int end = start + width;
1281 if (bitmap_bit_p (s_info->positions_needed.large.bmap, start++))
1287 unsigned HOST_WIDE_INT mask = lowpart_bitmask (width) << start;
1288 return (s_info->positions_needed.small_bitmask & mask) == mask;
1293 static rtx get_stored_val (store_info_t, enum machine_mode, HOST_WIDE_INT,
1294 HOST_WIDE_INT, basic_block, bool);
1297 /* BODY is an instruction pattern that belongs to INSN. Return 1 if
1298 there is a candidate store, after adding it to the appropriate
1299 local store group if so. */
1302 record_store (rtx body, bb_info_t bb_info)
1304 rtx mem, rhs, const_rhs, mem_addr;
1305 HOST_WIDE_INT offset = 0;
1306 HOST_WIDE_INT width = 0;
1307 alias_set_type spill_alias_set;
1308 insn_info_t insn_info = bb_info->last_insn;
1309 store_info_t store_info = NULL;
1311 cselib_val *base = NULL;
1312 insn_info_t ptr, last, redundant_reason;
1313 bool store_is_unused;
1315 if (GET_CODE (body) != SET && GET_CODE (body) != CLOBBER)
1318 mem = SET_DEST (body);
1320 /* If this is not used, then this cannot be used to keep the insn
1321 from being deleted. On the other hand, it does provide something
1322 that can be used to prove that another store is dead. */
1324 = (find_reg_note (insn_info->insn, REG_UNUSED, mem) != NULL);
1326 /* Check whether that value is a suitable memory location. */
1329 /* If the set or clobber is unused, then it does not effect our
1330 ability to get rid of the entire insn. */
1331 if (!store_is_unused)
1332 insn_info->cannot_delete = true;
1336 /* At this point we know mem is a mem. */
1337 if (GET_MODE (mem) == BLKmode)
1339 if (GET_CODE (XEXP (mem, 0)) == SCRATCH)
1342 fprintf (dump_file, " adding wild read for (clobber (mem:BLK (scratch))\n");
1343 add_wild_read (bb_info);
1344 insn_info->cannot_delete = true;
1347 /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
1348 as memset (addr, 0, 36); */
1349 else if (!MEM_SIZE (mem)
1350 || !CONST_INT_P (MEM_SIZE (mem))
1351 || GET_CODE (body) != SET
1352 || INTVAL (MEM_SIZE (mem)) <= 0
1353 || INTVAL (MEM_SIZE (mem)) > MAX_OFFSET
1354 || !CONST_INT_P (SET_SRC (body)))
1356 if (!store_is_unused)
1358 /* If the set or clobber is unused, then it does not effect our
1359 ability to get rid of the entire insn. */
1360 insn_info->cannot_delete = true;
1361 clear_rhs_from_active_local_stores ();
1367 /* We can still process a volatile mem, we just cannot delete it. */
1368 if (MEM_VOLATILE_P (mem))
1369 insn_info->cannot_delete = true;
1371 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
1373 clear_rhs_from_active_local_stores ();
1377 if (GET_MODE (mem) == BLKmode)
1378 width = INTVAL (MEM_SIZE (mem));
1381 width = GET_MODE_SIZE (GET_MODE (mem));
1382 gcc_assert ((unsigned) width <= HOST_BITS_PER_WIDE_INT);
1385 if (spill_alias_set)
1387 bitmap store1 = clear_alias_group->store1_p;
1388 bitmap store2 = clear_alias_group->store2_p;
1390 gcc_assert (GET_MODE (mem) != BLKmode);
1392 if (!bitmap_set_bit (store1, spill_alias_set))
1393 bitmap_set_bit (store2, spill_alias_set);
1395 if (clear_alias_group->offset_map_size_p < spill_alias_set)
1396 clear_alias_group->offset_map_size_p = spill_alias_set;
1398 store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1401 fprintf (dump_file, " processing spill store %d(%s)\n",
1402 (int) spill_alias_set, GET_MODE_NAME (GET_MODE (mem)));
1404 else if (group_id >= 0)
1406 /* In the restrictive case where the base is a constant or the
1407 frame pointer we can do global analysis. */
1410 = VEC_index (group_info_t, rtx_group_vec, group_id);
1412 store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1413 set_usage_bits (group, offset, width);
1416 fprintf (dump_file, " processing const base store gid=%d[%d..%d)\n",
1417 group_id, (int)offset, (int)(offset+width));
1421 rtx base_term = find_base_term (XEXP (mem, 0));
1423 || (GET_CODE (base_term) == ADDRESS
1424 && GET_MODE (base_term) == Pmode
1425 && XEXP (base_term, 0) == stack_pointer_rtx))
1426 insn_info->stack_pointer_based = true;
1427 insn_info->contains_cselib_groups = true;
1429 store_info = (store_info_t) pool_alloc (cse_store_info_pool);
1433 fprintf (dump_file, " processing cselib store [%d..%d)\n",
1434 (int)offset, (int)(offset+width));
1437 const_rhs = rhs = NULL_RTX;
1438 if (GET_CODE (body) == SET
1439 /* No place to keep the value after ra. */
1440 && !reload_completed
1441 && (REG_P (SET_SRC (body))
1442 || GET_CODE (SET_SRC (body)) == SUBREG
1443 || CONSTANT_P (SET_SRC (body)))
1444 && !MEM_VOLATILE_P (mem)
1445 /* Sometimes the store and reload is used for truncation and
1447 && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
1449 rhs = SET_SRC (body);
1450 if (CONSTANT_P (rhs))
1452 else if (body == PATTERN (insn_info->insn))
1454 rtx tem = find_reg_note (insn_info->insn, REG_EQUAL, NULL_RTX);
1455 if (tem && CONSTANT_P (XEXP (tem, 0)))
1456 const_rhs = XEXP (tem, 0);
1458 if (const_rhs == NULL_RTX && REG_P (rhs))
1460 rtx tem = cselib_expand_value_rtx (rhs, scratch, 5);
1462 if (tem && CONSTANT_P (tem))
1467 /* Check to see if this stores causes some other stores to be
1469 ptr = active_local_stores;
1471 redundant_reason = NULL;
1472 mem = canon_rtx (mem);
1473 /* For alias_set != 0 canon_true_dependence should be never called. */
1474 if (spill_alias_set)
1475 mem_addr = NULL_RTX;
1479 mem_addr = base->val_rtx;
1483 = VEC_index (group_info_t, rtx_group_vec, group_id);
1484 mem_addr = group->canon_base_addr;
1487 mem_addr = plus_constant (mem_addr, offset);
1492 insn_info_t next = ptr->next_local_store;
1493 store_info_t s_info = ptr->store_rec;
1496 /* Skip the clobbers. We delete the active insn if this insn
1497 shadows the set. To have been put on the active list, it
1498 has exactly on set. */
1499 while (!s_info->is_set)
1500 s_info = s_info->next;
1502 if (s_info->alias_set != spill_alias_set)
1504 else if (s_info->alias_set)
1506 struct clear_alias_mode_holder *entry
1507 = clear_alias_set_lookup (s_info->alias_set);
1508 /* Generally, spills cannot be processed if and of the
1509 references to the slot have a different mode. But if
1510 we are in the same block and mode is exactly the same
1511 between this store and one before in the same block,
1512 we can still delete it. */
1513 if ((GET_MODE (mem) == GET_MODE (s_info->mem))
1514 && (GET_MODE (mem) == entry->mode))
1517 set_all_positions_unneeded (s_info);
1520 fprintf (dump_file, " trying spill store in insn=%d alias_set=%d\n",
1521 INSN_UID (ptr->insn), (int) s_info->alias_set);
1523 else if ((s_info->group_id == group_id)
1524 && (s_info->cse_base == base))
1528 fprintf (dump_file, " trying store in insn=%d gid=%d[%d..%d)\n",
1529 INSN_UID (ptr->insn), s_info->group_id,
1530 (int)s_info->begin, (int)s_info->end);
1532 /* Even if PTR won't be eliminated as unneeded, if both
1533 PTR and this insn store the same constant value, we might
1534 eliminate this insn instead. */
1535 if (s_info->const_rhs
1537 && offset >= s_info->begin
1538 && offset + width <= s_info->end
1539 && all_positions_needed_p (s_info, offset - s_info->begin,
1542 if (GET_MODE (mem) == BLKmode)
1544 if (GET_MODE (s_info->mem) == BLKmode
1545 && s_info->const_rhs == const_rhs)
1546 redundant_reason = ptr;
1548 else if (s_info->const_rhs == const0_rtx
1549 && const_rhs == const0_rtx)
1550 redundant_reason = ptr;
1555 val = get_stored_val (s_info, GET_MODE (mem),
1556 offset, offset + width,
1557 BLOCK_FOR_INSN (insn_info->insn),
1559 if (get_insns () != NULL)
1562 if (val && rtx_equal_p (val, const_rhs))
1563 redundant_reason = ptr;
1567 for (i = MAX (offset, s_info->begin);
1568 i < offset + width && i < s_info->end;
1570 set_position_unneeded (s_info, i - s_info->begin);
1572 else if (s_info->rhs)
1573 /* Need to see if it is possible for this store to overwrite
1574 the value of store_info. If it is, set the rhs to NULL to
1575 keep it from being used to remove a load. */
1577 if (canon_true_dependence (s_info->mem,
1578 GET_MODE (s_info->mem),
1580 mem, mem_addr, rtx_varies_p))
1583 s_info->const_rhs = NULL;
1587 /* An insn can be deleted if every position of every one of
1588 its s_infos is zero. */
1589 if (any_positions_needed_p (s_info)
1590 || ptr->cannot_delete)
1595 insn_info_t insn_to_delete = ptr;
1598 last->next_local_store = ptr->next_local_store;
1600 active_local_stores = ptr->next_local_store;
1602 delete_dead_store_insn (insn_to_delete);
1610 /* Finish filling in the store_info. */
1611 store_info->next = insn_info->store_rec;
1612 insn_info->store_rec = store_info;
1613 store_info->mem = mem;
1614 store_info->alias_set = spill_alias_set;
1615 store_info->mem_addr = mem_addr;
1616 store_info->cse_base = base;
1617 if (width > HOST_BITS_PER_WIDE_INT)
1619 store_info->is_large = true;
1620 store_info->positions_needed.large.count = 0;
1621 store_info->positions_needed.large.bmap = BITMAP_ALLOC (NULL);
1625 store_info->is_large = false;
1626 store_info->positions_needed.small_bitmask = lowpart_bitmask (width);
1628 store_info->group_id = group_id;
1629 store_info->begin = offset;
1630 store_info->end = offset + width;
1631 store_info->is_set = GET_CODE (body) == SET;
1632 store_info->rhs = rhs;
1633 store_info->const_rhs = const_rhs;
1634 store_info->redundant_reason = redundant_reason;
1636 /* If this is a clobber, we return 0. We will only be able to
1637 delete this insn if there is only one store USED store, but we
1638 can use the clobber to delete other stores earlier. */
1639 return store_info->is_set ? 1 : 0;
1644 dump_insn_info (const char * start, insn_info_t insn_info)
1646 fprintf (dump_file, "%s insn=%d %s\n", start,
1647 INSN_UID (insn_info->insn),
1648 insn_info->store_rec ? "has store" : "naked");
1652 /* If the modes are different and the value's source and target do not
1653 line up, we need to extract the value from lower part of the rhs of
1654 the store, shift it, and then put it into a form that can be shoved
1655 into the read_insn. This function generates a right SHIFT of a
1656 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The
1657 shift sequence is returned or NULL if we failed to find a
1661 find_shift_sequence (int access_size,
1662 store_info_t store_info,
1663 enum machine_mode read_mode,
1664 int shift, bool speed, bool require_cst)
1666 enum machine_mode store_mode = GET_MODE (store_info->mem);
1667 enum machine_mode new_mode;
1668 rtx read_reg = NULL;
1670 /* Some machines like the x86 have shift insns for each size of
1671 operand. Other machines like the ppc or the ia-64 may only have
1672 shift insns that shift values within 32 or 64 bit registers.
1673 This loop tries to find the smallest shift insn that will right
1674 justify the value we want to read but is available in one insn on
1677 for (new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
1679 GET_MODE_BITSIZE (new_mode) <= BITS_PER_WORD;
1680 new_mode = GET_MODE_WIDER_MODE (new_mode))
1682 rtx target, new_reg, shift_seq, insn, new_lhs;
1685 /* If a constant was stored into memory, try to simplify it here,
1686 otherwise the cost of the shift might preclude this optimization
1687 e.g. at -Os, even when no actual shift will be needed. */
1688 if (store_info->const_rhs)
1690 unsigned int byte = subreg_lowpart_offset (new_mode, store_mode);
1691 rtx ret = simplify_subreg (new_mode, store_info->const_rhs,
1693 if (ret && CONSTANT_P (ret))
1695 ret = simplify_const_binary_operation (LSHIFTRT, new_mode,
1696 ret, GEN_INT (shift));
1697 if (ret && CONSTANT_P (ret))
1699 byte = subreg_lowpart_offset (read_mode, new_mode);
1700 ret = simplify_subreg (read_mode, ret, new_mode, byte);
1701 if (ret && CONSTANT_P (ret)
1702 && rtx_cost (ret, SET, speed) <= COSTS_N_INSNS (1))
1711 /* Try a wider mode if truncating the store mode to NEW_MODE
1712 requires a real instruction. */
1713 if (GET_MODE_BITSIZE (new_mode) < GET_MODE_BITSIZE (store_mode)
1714 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (new_mode),
1715 GET_MODE_BITSIZE (store_mode)))
1718 /* Also try a wider mode if the necessary punning is either not
1719 desirable or not possible. */
1720 if (!CONSTANT_P (store_info->rhs)
1721 && !MODES_TIEABLE_P (new_mode, store_mode))
1724 new_reg = gen_reg_rtx (new_mode);
1728 /* In theory we could also check for an ashr. Ian Taylor knows
1729 of one dsp where the cost of these two was not the same. But
1730 this really is a rare case anyway. */
1731 target = expand_binop (new_mode, lshr_optab, new_reg,
1732 GEN_INT (shift), new_reg, 1, OPTAB_DIRECT);
1734 shift_seq = get_insns ();
1737 if (target != new_reg || shift_seq == NULL)
1741 for (insn = shift_seq; insn != NULL_RTX; insn = NEXT_INSN (insn))
1743 cost += insn_rtx_cost (PATTERN (insn), speed);
1745 /* The computation up to here is essentially independent
1746 of the arguments and could be precomputed. It may
1747 not be worth doing so. We could precompute if
1748 worthwhile or at least cache the results. The result
1749 technically depends on both SHIFT and ACCESS_SIZE,
1750 but in practice the answer will depend only on ACCESS_SIZE. */
1752 if (cost > COSTS_N_INSNS (1))
1755 new_lhs = extract_low_bits (new_mode, store_mode,
1756 copy_rtx (store_info->rhs));
1757 if (new_lhs == NULL_RTX)
1760 /* We found an acceptable shift. Generate a move to
1761 take the value from the store and put it into the
1762 shift pseudo, then shift it, then generate another
1763 move to put in into the target of the read. */
1764 emit_move_insn (new_reg, new_lhs);
1765 emit_insn (shift_seq);
1766 read_reg = extract_low_bits (read_mode, new_mode, new_reg);
1774 /* Call back for note_stores to find the hard regs set or clobbered by
1775 insn. Data is a bitmap of the hardregs set so far. */
1778 look_for_hardregs (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
1780 bitmap regs_set = (bitmap) data;
1783 && REGNO (x) < FIRST_PSEUDO_REGISTER)
1785 int regno = REGNO (x);
1786 int n = hard_regno_nregs[regno][GET_MODE (x)];
1788 bitmap_set_bit (regs_set, regno + n);
1792 /* Helper function for replace_read and record_store.
1793 Attempt to return a value stored in STORE_INFO, from READ_BEGIN
1794 to one before READ_END bytes read in READ_MODE. Return NULL
1795 if not successful. If REQUIRE_CST is true, return always constant. */
1798 get_stored_val (store_info_t store_info, enum machine_mode read_mode,
1799 HOST_WIDE_INT read_begin, HOST_WIDE_INT read_end,
1800 basic_block bb, bool require_cst)
1802 enum machine_mode store_mode = GET_MODE (store_info->mem);
1804 int access_size; /* In bytes. */
1807 /* To get here the read is within the boundaries of the write so
1808 shift will never be negative. Start out with the shift being in
1810 if (store_mode == BLKmode)
1812 else if (BYTES_BIG_ENDIAN)
1813 shift = store_info->end - read_end;
1815 shift = read_begin - store_info->begin;
1817 access_size = shift + GET_MODE_SIZE (read_mode);
1819 /* From now on it is bits. */
1820 shift *= BITS_PER_UNIT;
1823 read_reg = find_shift_sequence (access_size, store_info, read_mode, shift,
1824 optimize_bb_for_speed_p (bb),
1826 else if (store_mode == BLKmode)
1828 /* The store is a memset (addr, const_val, const_size). */
1829 gcc_assert (CONST_INT_P (store_info->rhs));
1830 store_mode = int_mode_for_mode (read_mode);
1831 if (store_mode == BLKmode)
1832 read_reg = NULL_RTX;
1833 else if (store_info->rhs == const0_rtx)
1834 read_reg = extract_low_bits (read_mode, store_mode, const0_rtx);
1835 else if (GET_MODE_BITSIZE (store_mode) > HOST_BITS_PER_WIDE_INT
1836 || BITS_PER_UNIT >= HOST_BITS_PER_WIDE_INT)
1837 read_reg = NULL_RTX;
1840 unsigned HOST_WIDE_INT c
1841 = INTVAL (store_info->rhs)
1842 & (((HOST_WIDE_INT) 1 << BITS_PER_UNIT) - 1);
1843 int shift = BITS_PER_UNIT;
1844 while (shift < HOST_BITS_PER_WIDE_INT)
1849 read_reg = GEN_INT (trunc_int_for_mode (c, store_mode));
1850 read_reg = extract_low_bits (read_mode, store_mode, read_reg);
1853 else if (store_info->const_rhs
1855 || GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode)))
1856 read_reg = extract_low_bits (read_mode, store_mode,
1857 copy_rtx (store_info->const_rhs));
1859 read_reg = extract_low_bits (read_mode, store_mode,
1860 copy_rtx (store_info->rhs));
1861 if (require_cst && read_reg && !CONSTANT_P (read_reg))
1862 read_reg = NULL_RTX;
1866 /* Take a sequence of:
1889 Depending on the alignment and the mode of the store and
1893 The STORE_INFO and STORE_INSN are for the store and READ_INFO
1894 and READ_INSN are for the read. Return true if the replacement
1898 replace_read (store_info_t store_info, insn_info_t store_insn,
1899 read_info_t read_info, insn_info_t read_insn, rtx *loc,
1902 enum machine_mode store_mode = GET_MODE (store_info->mem);
1903 enum machine_mode read_mode = GET_MODE (read_info->mem);
1904 rtx insns, this_insn, read_reg;
1910 /* Create a sequence of instructions to set up the read register.
1911 This sequence goes immediately before the store and its result
1912 is read by the load.
1914 We need to keep this in perspective. We are replacing a read
1915 with a sequence of insns, but the read will almost certainly be
1916 in cache, so it is not going to be an expensive one. Thus, we
1917 are not willing to do a multi insn shift or worse a subroutine
1918 call to get rid of the read. */
1920 fprintf (dump_file, "trying to replace %smode load in insn %d"
1921 " from %smode store in insn %d\n",
1922 GET_MODE_NAME (read_mode), INSN_UID (read_insn->insn),
1923 GET_MODE_NAME (store_mode), INSN_UID (store_insn->insn));
1925 bb = BLOCK_FOR_INSN (read_insn->insn);
1926 read_reg = get_stored_val (store_info,
1927 read_mode, read_info->begin, read_info->end,
1929 if (read_reg == NULL_RTX)
1933 fprintf (dump_file, " -- could not extract bits of stored value\n");
1936 /* Force the value into a new register so that it won't be clobbered
1937 between the store and the load. */
1938 read_reg = copy_to_mode_reg (read_mode, read_reg);
1939 insns = get_insns ();
1942 if (insns != NULL_RTX)
1944 /* Now we have to scan the set of new instructions to see if the
1945 sequence contains and sets of hardregs that happened to be
1946 live at this point. For instance, this can happen if one of
1947 the insns sets the CC and the CC happened to be live at that
1948 point. This does occasionally happen, see PR 37922. */
1949 bitmap regs_set = BITMAP_ALLOC (NULL);
1951 for (this_insn = insns; this_insn != NULL_RTX; this_insn = NEXT_INSN (this_insn))
1952 note_stores (PATTERN (this_insn), look_for_hardregs, regs_set);
1954 bitmap_and_into (regs_set, regs_live);
1955 if (!bitmap_empty_p (regs_set))
1960 "abandoning replacement because sequence clobbers live hardregs:");
1961 df_print_regset (dump_file, regs_set);
1964 BITMAP_FREE (regs_set);
1967 BITMAP_FREE (regs_set);
1970 if (validate_change (read_insn->insn, loc, read_reg, 0))
1972 deferred_change_t deferred_change =
1973 (deferred_change_t) pool_alloc (deferred_change_pool);
1975 /* Insert this right before the store insn where it will be safe
1976 from later insns that might change it before the read. */
1977 emit_insn_before (insns, store_insn->insn);
1979 /* And now for the kludge part: cselib croaks if you just
1980 return at this point. There are two reasons for this:
1982 1) Cselib has an idea of how many pseudos there are and
1983 that does not include the new ones we just added.
1985 2) Cselib does not know about the move insn we added
1986 above the store_info, and there is no way to tell it
1987 about it, because it has "moved on".
1989 Problem (1) is fixable with a certain amount of engineering.
1990 Problem (2) is requires starting the bb from scratch. This
1993 So we are just going to have to lie. The move/extraction
1994 insns are not really an issue, cselib did not see them. But
1995 the use of the new pseudo read_insn is a real problem because
1996 cselib has not scanned this insn. The way that we solve this
1997 problem is that we are just going to put the mem back for now
1998 and when we are finished with the block, we undo this. We
1999 keep a table of mems to get rid of. At the end of the basic
2000 block we can put them back. */
2002 *loc = read_info->mem;
2003 deferred_change->next = deferred_change_list;
2004 deferred_change_list = deferred_change;
2005 deferred_change->loc = loc;
2006 deferred_change->reg = read_reg;
2008 /* Get rid of the read_info, from the point of view of the
2009 rest of dse, play like this read never happened. */
2010 read_insn->read_rec = read_info->next;
2011 pool_free (read_info_pool, read_info);
2014 fprintf (dump_file, " -- replaced the loaded MEM with ");
2015 print_simple_rtl (dump_file, read_reg);
2016 fprintf (dump_file, "\n");
2024 fprintf (dump_file, " -- replacing the loaded MEM with ");
2025 print_simple_rtl (dump_file, read_reg);
2026 fprintf (dump_file, " led to an invalid instruction\n");
2032 /* A for_each_rtx callback in which DATA is the bb_info. Check to see
2033 if LOC is a mem and if it is look at the address and kill any
2034 appropriate stores that may be active. */
2037 check_mem_read_rtx (rtx *loc, void *data)
2039 rtx mem = *loc, mem_addr;
2041 insn_info_t insn_info;
2042 HOST_WIDE_INT offset = 0;
2043 HOST_WIDE_INT width = 0;
2044 alias_set_type spill_alias_set = 0;
2045 cselib_val *base = NULL;
2047 read_info_t read_info;
2049 if (!mem || !MEM_P (mem))
2052 bb_info = (bb_info_t) data;
2053 insn_info = bb_info->last_insn;
2055 if ((MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2056 || (MEM_VOLATILE_P (mem)))
2059 fprintf (dump_file, " adding wild read, volatile or barrier.\n");
2060 add_wild_read (bb_info);
2061 insn_info->cannot_delete = true;
2065 /* If it is reading readonly mem, then there can be no conflict with
2067 if (MEM_READONLY_P (mem))
2070 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
2073 fprintf (dump_file, " adding wild read, canon_address failure.\n");
2074 add_wild_read (bb_info);
2078 if (GET_MODE (mem) == BLKmode)
2081 width = GET_MODE_SIZE (GET_MODE (mem));
2083 read_info = (read_info_t) pool_alloc (read_info_pool);
2084 read_info->group_id = group_id;
2085 read_info->mem = mem;
2086 read_info->alias_set = spill_alias_set;
2087 read_info->begin = offset;
2088 read_info->end = offset + width;
2089 read_info->next = insn_info->read_rec;
2090 insn_info->read_rec = read_info;
2091 /* For alias_set != 0 canon_true_dependence should be never called. */
2092 if (spill_alias_set)
2093 mem_addr = NULL_RTX;
2097 mem_addr = base->val_rtx;
2101 = VEC_index (group_info_t, rtx_group_vec, group_id);
2102 mem_addr = group->canon_base_addr;
2105 mem_addr = plus_constant (mem_addr, offset);
2108 /* We ignore the clobbers in store_info. The is mildly aggressive,
2109 but there really should not be a clobber followed by a read. */
2111 if (spill_alias_set)
2113 insn_info_t i_ptr = active_local_stores;
2114 insn_info_t last = NULL;
2117 fprintf (dump_file, " processing spill load %d\n",
2118 (int) spill_alias_set);
2122 store_info_t store_info = i_ptr->store_rec;
2124 /* Skip the clobbers. */
2125 while (!store_info->is_set)
2126 store_info = store_info->next;
2128 if (store_info->alias_set == spill_alias_set)
2131 dump_insn_info ("removing from active", i_ptr);
2134 last->next_local_store = i_ptr->next_local_store;
2136 active_local_stores = i_ptr->next_local_store;
2140 i_ptr = i_ptr->next_local_store;
2143 else if (group_id >= 0)
2145 /* This is the restricted case where the base is a constant or
2146 the frame pointer and offset is a constant. */
2147 insn_info_t i_ptr = active_local_stores;
2148 insn_info_t last = NULL;
2153 fprintf (dump_file, " processing const load gid=%d[BLK]\n",
2156 fprintf (dump_file, " processing const load gid=%d[%d..%d)\n",
2157 group_id, (int)offset, (int)(offset+width));
2162 bool remove = false;
2163 store_info_t store_info = i_ptr->store_rec;
2165 /* Skip the clobbers. */
2166 while (!store_info->is_set)
2167 store_info = store_info->next;
2169 /* There are three cases here. */
2170 if (store_info->group_id < 0)
2171 /* We have a cselib store followed by a read from a
2174 = canon_true_dependence (store_info->mem,
2175 GET_MODE (store_info->mem),
2176 store_info->mem_addr,
2177 mem, mem_addr, rtx_varies_p);
2179 else if (group_id == store_info->group_id)
2181 /* This is a block mode load. We may get lucky and
2182 canon_true_dependence may save the day. */
2185 = canon_true_dependence (store_info->mem,
2186 GET_MODE (store_info->mem),
2187 store_info->mem_addr,
2188 mem, mem_addr, rtx_varies_p);
2190 /* If this read is just reading back something that we just
2191 stored, rewrite the read. */
2195 && offset >= store_info->begin
2196 && offset + width <= store_info->end
2197 && all_positions_needed_p (store_info,
2198 offset - store_info->begin,
2200 && replace_read (store_info, i_ptr, read_info,
2201 insn_info, loc, bb_info->regs_live))
2204 /* The bases are the same, just see if the offsets
2206 if ((offset < store_info->end)
2207 && (offset + width > store_info->begin))
2213 The else case that is missing here is that the
2214 bases are constant but different. There is nothing
2215 to do here because there is no overlap. */
2220 dump_insn_info ("removing from active", i_ptr);
2223 last->next_local_store = i_ptr->next_local_store;
2225 active_local_stores = i_ptr->next_local_store;
2229 i_ptr = i_ptr->next_local_store;
2234 insn_info_t i_ptr = active_local_stores;
2235 insn_info_t last = NULL;
2238 fprintf (dump_file, " processing cselib load mem:");
2239 print_inline_rtx (dump_file, mem, 0);
2240 fprintf (dump_file, "\n");
2245 bool remove = false;
2246 store_info_t store_info = i_ptr->store_rec;
2249 fprintf (dump_file, " processing cselib load against insn %d\n",
2250 INSN_UID (i_ptr->insn));
2252 /* Skip the clobbers. */
2253 while (!store_info->is_set)
2254 store_info = store_info->next;
2256 /* If this read is just reading back something that we just
2257 stored, rewrite the read. */
2259 && store_info->group_id == -1
2260 && store_info->cse_base == base
2262 && offset >= store_info->begin
2263 && offset + width <= store_info->end
2264 && all_positions_needed_p (store_info,
2265 offset - store_info->begin, width)
2266 && replace_read (store_info, i_ptr, read_info, insn_info, loc,
2267 bb_info->regs_live))
2270 if (!store_info->alias_set)
2271 remove = canon_true_dependence (store_info->mem,
2272 GET_MODE (store_info->mem),
2273 store_info->mem_addr,
2274 mem, mem_addr, rtx_varies_p);
2279 dump_insn_info ("removing from active", i_ptr);
2282 last->next_local_store = i_ptr->next_local_store;
2284 active_local_stores = i_ptr->next_local_store;
2288 i_ptr = i_ptr->next_local_store;
2294 /* A for_each_rtx callback in which DATA points the INSN_INFO for
2295 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
2296 true for any part of *LOC. */
2299 check_mem_read_use (rtx *loc, void *data)
2301 for_each_rtx (loc, check_mem_read_rtx, data);
2305 /* Get arguments passed to CALL_INSN. Return TRUE if successful.
2306 So far it only handles arguments passed in registers. */
2309 get_call_args (rtx call_insn, tree fn, rtx *args, int nargs)
2311 CUMULATIVE_ARGS args_so_far;
2315 INIT_CUMULATIVE_ARGS (args_so_far, TREE_TYPE (fn), NULL_RTX, 0, 3);
2317 arg = TYPE_ARG_TYPES (TREE_TYPE (fn));
2319 arg != void_list_node && idx < nargs;
2320 arg = TREE_CHAIN (arg), idx++)
2322 enum machine_mode mode = TYPE_MODE (TREE_VALUE (arg));
2324 reg = targetm.calls.function_arg (&args_so_far, mode, NULL_TREE, true);
2325 if (!reg || !REG_P (reg) || GET_MODE (reg) != mode
2326 || GET_MODE_CLASS (mode) != MODE_INT)
2329 for (link = CALL_INSN_FUNCTION_USAGE (call_insn);
2331 link = XEXP (link, 1))
2332 if (GET_CODE (XEXP (link, 0)) == USE)
2334 args[idx] = XEXP (XEXP (link, 0), 0);
2335 if (REG_P (args[idx])
2336 && REGNO (args[idx]) == REGNO (reg)
2337 && (GET_MODE (args[idx]) == mode
2338 || (GET_MODE_CLASS (GET_MODE (args[idx])) == MODE_INT
2339 && (GET_MODE_SIZE (GET_MODE (args[idx]))
2341 && (GET_MODE_SIZE (GET_MODE (args[idx]))
2342 > GET_MODE_SIZE (mode)))))
2348 tmp = cselib_expand_value_rtx (args[idx], scratch, 5);
2349 if (GET_MODE (args[idx]) != mode)
2351 if (!tmp || !CONST_INT_P (tmp))
2353 tmp = GEN_INT (trunc_int_for_mode (INTVAL (tmp), mode));
2358 targetm.calls.function_arg_advance (&args_so_far, mode, NULL_TREE, true);
2360 if (arg != void_list_node || idx != nargs)
2366 /* Apply record_store to all candidate stores in INSN. Mark INSN
2367 if some part of it is not a candidate store and assigns to a
2368 non-register target. */
2371 scan_insn (bb_info_t bb_info, rtx insn)
2374 insn_info_t insn_info = (insn_info_t) pool_alloc (insn_info_pool);
2376 memset (insn_info, 0, sizeof (struct insn_info));
2379 fprintf (dump_file, "\n**scanning insn=%d\n",
2382 insn_info->prev_insn = bb_info->last_insn;
2383 insn_info->insn = insn;
2384 bb_info->last_insn = insn_info;
2386 if (DEBUG_INSN_P (insn))
2388 insn_info->cannot_delete = true;
2392 /* Cselib clears the table for this case, so we have to essentially
2394 if (NONJUMP_INSN_P (insn)
2395 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
2396 && MEM_VOLATILE_P (PATTERN (insn)))
2398 add_wild_read (bb_info);
2399 insn_info->cannot_delete = true;
2403 /* Look at all of the uses in the insn. */
2404 note_uses (&PATTERN (insn), check_mem_read_use, bb_info);
2409 tree memset_call = NULL_TREE;
2411 insn_info->cannot_delete = true;
2413 /* Const functions cannot do anything bad i.e. read memory,
2414 however, they can read their parameters which may have
2415 been pushed onto the stack.
2416 memset and bzero don't read memory either. */
2417 const_call = RTL_CONST_CALL_P (insn);
2420 rtx call = PATTERN (insn);
2421 if (GET_CODE (call) == PARALLEL)
2422 call = XVECEXP (call, 0, 0);
2423 if (GET_CODE (call) == SET)
2424 call = SET_SRC (call);
2425 if (GET_CODE (call) == CALL
2426 && MEM_P (XEXP (call, 0))
2427 && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
2429 rtx symbol = XEXP (XEXP (call, 0), 0);
2430 if (SYMBOL_REF_DECL (symbol)
2431 && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
2433 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
2435 && (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))
2436 == BUILT_IN_MEMSET))
2437 || SYMBOL_REF_DECL (symbol) == block_clear_fn)
2438 memset_call = SYMBOL_REF_DECL (symbol);
2442 if (const_call || memset_call)
2444 insn_info_t i_ptr = active_local_stores;
2445 insn_info_t last = NULL;
2448 fprintf (dump_file, "%s call %d\n",
2449 const_call ? "const" : "memset", INSN_UID (insn));
2451 /* See the head comment of the frame_read field. */
2452 if (reload_completed)
2453 insn_info->frame_read = true;
2455 /* Loop over the active stores and remove those which are
2456 killed by the const function call. */
2459 bool remove_store = false;
2461 /* The stack pointer based stores are always killed. */
2462 if (i_ptr->stack_pointer_based)
2463 remove_store = true;
2465 /* If the frame is read, the frame related stores are killed. */
2466 else if (insn_info->frame_read)
2468 store_info_t store_info = i_ptr->store_rec;
2470 /* Skip the clobbers. */
2471 while (!store_info->is_set)
2472 store_info = store_info->next;
2474 if (store_info->group_id >= 0
2475 && VEC_index (group_info_t, rtx_group_vec,
2476 store_info->group_id)->frame_related)
2477 remove_store = true;
2483 dump_insn_info ("removing from active", i_ptr);
2486 last->next_local_store = i_ptr->next_local_store;
2488 active_local_stores = i_ptr->next_local_store;
2493 i_ptr = i_ptr->next_local_store;
2499 if (get_call_args (insn, memset_call, args, 3)
2500 && CONST_INT_P (args[1])
2501 && CONST_INT_P (args[2])
2502 && INTVAL (args[2]) > 0)
2504 rtx mem = gen_rtx_MEM (BLKmode, args[0]);
2505 set_mem_size (mem, args[2]);
2506 body = gen_rtx_SET (VOIDmode, mem, args[1]);
2507 mems_found += record_store (body, bb_info);
2509 fprintf (dump_file, "handling memset as BLKmode store\n");
2510 if (mems_found == 1)
2512 insn_info->next_local_store = active_local_stores;
2513 active_local_stores = insn_info;
2520 /* Every other call, including pure functions, may read memory. */
2521 add_wild_read (bb_info);
2526 /* Assuming that there are sets in these insns, we cannot delete
2528 if ((GET_CODE (PATTERN (insn)) == CLOBBER)
2529 || volatile_refs_p (PATTERN (insn))
2530 || insn_could_throw_p (insn)
2531 || (RTX_FRAME_RELATED_P (insn))
2532 || find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX))
2533 insn_info->cannot_delete = true;
2535 body = PATTERN (insn);
2536 if (GET_CODE (body) == PARALLEL)
2539 for (i = 0; i < XVECLEN (body, 0); i++)
2540 mems_found += record_store (XVECEXP (body, 0, i), bb_info);
2543 mems_found += record_store (body, bb_info);
2546 fprintf (dump_file, "mems_found = %d, cannot_delete = %s\n",
2547 mems_found, insn_info->cannot_delete ? "true" : "false");
2549 /* If we found some sets of mems, add it into the active_local_stores so
2550 that it can be locally deleted if found dead or used for
2551 replace_read and redundant constant store elimination. Otherwise mark
2552 it as cannot delete. This simplifies the processing later. */
2553 if (mems_found == 1)
2555 insn_info->next_local_store = active_local_stores;
2556 active_local_stores = insn_info;
2559 insn_info->cannot_delete = true;
2563 /* Remove BASE from the set of active_local_stores. This is a
2564 callback from cselib that is used to get rid of the stores in
2565 active_local_stores. */
2568 remove_useless_values (cselib_val *base)
2570 insn_info_t insn_info = active_local_stores;
2571 insn_info_t last = NULL;
2575 store_info_t store_info = insn_info->store_rec;
2578 /* If ANY of the store_infos match the cselib group that is
2579 being deleted, then the insn can not be deleted. */
2582 if ((store_info->group_id == -1)
2583 && (store_info->cse_base == base))
2588 store_info = store_info->next;
2594 last->next_local_store = insn_info->next_local_store;
2596 active_local_stores = insn_info->next_local_store;
2597 free_store_info (insn_info);
2602 insn_info = insn_info->next_local_store;
2607 /* Do all of step 1. */
2613 bitmap regs_live = BITMAP_ALLOC (NULL);
2616 all_blocks = BITMAP_ALLOC (NULL);
2617 bitmap_set_bit (all_blocks, ENTRY_BLOCK);
2618 bitmap_set_bit (all_blocks, EXIT_BLOCK);
2623 bb_info_t bb_info = (bb_info_t) pool_alloc (bb_info_pool);
2625 memset (bb_info, 0, sizeof (struct bb_info));
2626 bitmap_set_bit (all_blocks, bb->index);
2627 bb_info->regs_live = regs_live;
2629 bitmap_copy (regs_live, DF_LR_IN (bb));
2630 df_simulate_initialize_forwards (bb, regs_live);
2632 bb_table[bb->index] = bb_info;
2633 cselib_discard_hook = remove_useless_values;
2635 if (bb->index >= NUM_FIXED_BLOCKS)
2640 = create_alloc_pool ("cse_store_info_pool",
2641 sizeof (struct store_info), 100);
2642 active_local_stores = NULL;
2643 cselib_clear_table ();
2645 /* Scan the insns. */
2646 FOR_BB_INSNS (bb, insn)
2649 scan_insn (bb_info, insn);
2650 cselib_process_insn (insn);
2652 df_simulate_one_insn_forwards (bb, insn, regs_live);
2655 /* This is something of a hack, because the global algorithm
2656 is supposed to take care of the case where stores go dead
2657 at the end of the function. However, the global
2658 algorithm must take a more conservative view of block
2659 mode reads than the local alg does. So to get the case
2660 where you have a store to the frame followed by a non
2661 overlapping block more read, we look at the active local
2662 stores at the end of the function and delete all of the
2663 frame and spill based ones. */
2664 if (stores_off_frame_dead_at_return
2665 && (EDGE_COUNT (bb->succs) == 0
2666 || (single_succ_p (bb)
2667 && single_succ (bb) == EXIT_BLOCK_PTR
2668 && ! crtl->calls_eh_return)))
2670 insn_info_t i_ptr = active_local_stores;
2673 store_info_t store_info = i_ptr->store_rec;
2675 /* Skip the clobbers. */
2676 while (!store_info->is_set)
2677 store_info = store_info->next;
2678 if (store_info->alias_set && !i_ptr->cannot_delete)
2679 delete_dead_store_insn (i_ptr);
2681 if (store_info->group_id >= 0)
2684 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
2685 if (group->frame_related && !i_ptr->cannot_delete)
2686 delete_dead_store_insn (i_ptr);
2689 i_ptr = i_ptr->next_local_store;
2693 /* Get rid of the loads that were discovered in
2694 replace_read. Cselib is finished with this block. */
2695 while (deferred_change_list)
2697 deferred_change_t next = deferred_change_list->next;
2699 /* There is no reason to validate this change. That was
2701 *deferred_change_list->loc = deferred_change_list->reg;
2702 pool_free (deferred_change_pool, deferred_change_list);
2703 deferred_change_list = next;
2706 /* Get rid of all of the cselib based store_infos in this
2707 block and mark the containing insns as not being
2709 ptr = bb_info->last_insn;
2712 if (ptr->contains_cselib_groups)
2714 store_info_t s_info = ptr->store_rec;
2715 while (s_info && !s_info->is_set)
2716 s_info = s_info->next;
2718 && s_info->redundant_reason
2719 && s_info->redundant_reason->insn
2720 && !ptr->cannot_delete)
2723 fprintf (dump_file, "Locally deleting insn %d "
2724 "because insn %d stores the "
2725 "same value and couldn't be "
2727 INSN_UID (ptr->insn),
2728 INSN_UID (s_info->redundant_reason->insn));
2729 delete_dead_store_insn (ptr);
2732 s_info->redundant_reason = NULL;
2733 free_store_info (ptr);
2737 store_info_t s_info;
2739 /* Free at least positions_needed bitmaps. */
2740 for (s_info = ptr->store_rec; s_info; s_info = s_info->next)
2741 if (s_info->is_large)
2743 BITMAP_FREE (s_info->positions_needed.large.bmap);
2744 s_info->is_large = false;
2747 ptr = ptr->prev_insn;
2750 free_alloc_pool (cse_store_info_pool);
2752 bb_info->regs_live = NULL;
2755 BITMAP_FREE (regs_live);
2757 htab_empty (rtx_group_table);
2761 /*----------------------------------------------------------------------------
2764 Assign each byte position in the stores that we are going to
2765 analyze globally to a position in the bitmaps. Returns true if
2766 there are any bit positions assigned.
2767 ----------------------------------------------------------------------------*/
2770 dse_step2_init (void)
2775 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
2777 /* For all non stack related bases, we only consider a store to
2778 be deletable if there are two or more stores for that
2779 position. This is because it takes one store to make the
2780 other store redundant. However, for the stores that are
2781 stack related, we consider them if there is only one store
2782 for the position. We do this because the stack related
2783 stores can be deleted if their is no read between them and
2784 the end of the function.
2786 To make this work in the current framework, we take the stack
2787 related bases add all of the bits from store1 into store2.
2788 This has the effect of making the eligible even if there is
2791 if (stores_off_frame_dead_at_return && group->frame_related)
2793 bitmap_ior_into (group->store2_n, group->store1_n);
2794 bitmap_ior_into (group->store2_p, group->store1_p);
2796 fprintf (dump_file, "group %d is frame related ", i);
2799 group->offset_map_size_n++;
2800 group->offset_map_n = XNEWVEC (int, group->offset_map_size_n);
2801 group->offset_map_size_p++;
2802 group->offset_map_p = XNEWVEC (int, group->offset_map_size_p);
2803 group->process_globally = false;
2806 fprintf (dump_file, "group %d(%d+%d): ", i,
2807 (int)bitmap_count_bits (group->store2_n),
2808 (int)bitmap_count_bits (group->store2_p));
2809 bitmap_print (dump_file, group->store2_n, "n ", " ");
2810 bitmap_print (dump_file, group->store2_p, "p ", "\n");
2816 /* Init the offset tables for the normal case. */
2819 dse_step2_nospill (void)
2823 /* Position 0 is unused because 0 is used in the maps to mean
2825 current_position = 1;
2827 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
2832 if (group == clear_alias_group)
2835 memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2836 memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2837 bitmap_clear (group->group_kill);
2839 EXECUTE_IF_SET_IN_BITMAP (group->store2_n, 0, j, bi)
2841 bitmap_set_bit (group->group_kill, current_position);
2842 group->offset_map_n[j] = current_position++;
2843 group->process_globally = true;
2845 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2847 bitmap_set_bit (group->group_kill, current_position);
2848 group->offset_map_p[j] = current_position++;
2849 group->process_globally = true;
2852 return current_position != 1;
2856 /* Init the offset tables for the spill case. */
2859 dse_step2_spill (void)
2862 group_info_t group = clear_alias_group;
2865 /* Position 0 is unused because 0 is used in the maps to mean
2867 current_position = 1;
2871 bitmap_print (dump_file, clear_alias_sets,
2872 "clear alias sets ", "\n");
2873 bitmap_print (dump_file, disqualified_clear_alias_sets,
2874 "disqualified clear alias sets ", "\n");
2877 memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2878 memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2879 bitmap_clear (group->group_kill);
2881 /* Remove the disqualified positions from the store2_p set. */
2882 bitmap_and_compl_into (group->store2_p, disqualified_clear_alias_sets);
2884 /* We do not need to process the store2_n set because
2885 alias_sets are always positive. */
2886 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2888 bitmap_set_bit (group->group_kill, current_position);
2889 group->offset_map_p[j] = current_position++;
2890 group->process_globally = true;
2893 return current_position != 1;
2898 /*----------------------------------------------------------------------------
2901 Build the bit vectors for the transfer functions.
2902 ----------------------------------------------------------------------------*/
2905 /* Note that this is NOT a general purpose function. Any mem that has
2906 an alias set registered here expected to be COMPLETELY unaliased:
2907 i.e it's addresses are not and need not be examined.
2909 It is known that all references to this address will have this
2910 alias set and there are NO other references to this address in the
2913 Currently the only place that is known to be clean enough to use
2914 this interface is the code that assigns the spill locations.
2916 All of the mems that have alias_sets registered are subjected to a
2917 very powerful form of dse where function calls, volatile reads and
2918 writes, and reads from random location are not taken into account.
2920 It is also assumed that these locations go dead when the function
2921 returns. This assumption could be relaxed if there were found to
2922 be places that this assumption was not correct.
2924 The MODE is passed in and saved. The mode of each load or store to
2925 a mem with ALIAS_SET is checked against MEM. If the size of that
2926 load or store is different from MODE, processing is halted on this
2927 alias set. For the vast majority of aliases sets, all of the loads
2928 and stores will use the same mode. But vectors are treated
2929 differently: the alias set is established for the entire vector,
2930 but reload will insert loads and stores for individual elements and
2931 we do not necessarily have the information to track those separate
2932 elements. So when we see a mode mismatch, we just bail. */
2936 dse_record_singleton_alias_set (alias_set_type alias_set,
2937 enum machine_mode mode)
2939 struct clear_alias_mode_holder tmp_holder;
2940 struct clear_alias_mode_holder *entry;
2943 /* If we are not going to run dse, we need to return now or there
2944 will be problems with allocating the bitmaps. */
2945 if ((!gate_dse()) || !alias_set)
2948 if (!clear_alias_sets)
2950 clear_alias_sets = BITMAP_ALLOC (NULL);
2951 disqualified_clear_alias_sets = BITMAP_ALLOC (NULL);
2952 clear_alias_mode_table = htab_create (11, clear_alias_mode_hash,
2953 clear_alias_mode_eq, NULL);
2954 clear_alias_mode_pool = create_alloc_pool ("clear_alias_mode_pool",
2955 sizeof (struct clear_alias_mode_holder), 100);
2958 bitmap_set_bit (clear_alias_sets, alias_set);
2960 tmp_holder.alias_set = alias_set;
2962 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, INSERT);
2963 gcc_assert (*slot == NULL);
2966 (struct clear_alias_mode_holder *) pool_alloc (clear_alias_mode_pool);
2967 entry->alias_set = alias_set;
2972 /* Remove ALIAS_SET from the sets of stack slots being considered. */
2975 dse_invalidate_singleton_alias_set (alias_set_type alias_set)
2977 if ((!gate_dse()) || !alias_set)
2980 bitmap_clear_bit (clear_alias_sets, alias_set);
2984 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
2988 get_bitmap_index (group_info_t group_info, HOST_WIDE_INT offset)
2992 HOST_WIDE_INT offset_p = -offset;
2993 if (offset_p >= group_info->offset_map_size_n)
2995 return group_info->offset_map_n[offset_p];
2999 if (offset >= group_info->offset_map_size_p)
3001 return group_info->offset_map_p[offset];
3006 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3010 scan_stores_nospill (store_info_t store_info, bitmap gen, bitmap kill)
3015 group_info_t group_info
3016 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
3017 if (group_info->process_globally)
3018 for (i = store_info->begin; i < store_info->end; i++)
3020 int index = get_bitmap_index (group_info, i);
3023 bitmap_set_bit (gen, index);
3025 bitmap_clear_bit (kill, index);
3028 store_info = store_info->next;
3033 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3037 scan_stores_spill (store_info_t store_info, bitmap gen, bitmap kill)
3041 if (store_info->alias_set)
3043 int index = get_bitmap_index (clear_alias_group,
3044 store_info->alias_set);
3047 bitmap_set_bit (gen, index);
3049 bitmap_clear_bit (kill, index);
3052 store_info = store_info->next;
3057 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3061 scan_reads_nospill (insn_info_t insn_info, bitmap gen, bitmap kill)
3063 read_info_t read_info = insn_info->read_rec;
3067 /* If this insn reads the frame, kill all the frame related stores. */
3068 if (insn_info->frame_read)
3070 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
3071 if (group->process_globally && group->frame_related)
3074 bitmap_ior_into (kill, group->group_kill);
3075 bitmap_and_compl_into (gen, group->group_kill);
3081 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
3083 if (group->process_globally)
3085 if (i == read_info->group_id)
3087 if (read_info->begin > read_info->end)
3089 /* Begin > end for block mode reads. */
3091 bitmap_ior_into (kill, group->group_kill);
3092 bitmap_and_compl_into (gen, group->group_kill);
3096 /* The groups are the same, just process the
3099 for (j = read_info->begin; j < read_info->end; j++)
3101 int index = get_bitmap_index (group, j);
3105 bitmap_set_bit (kill, index);
3106 bitmap_clear_bit (gen, index);
3113 /* The groups are different, if the alias sets
3114 conflict, clear the entire group. We only need
3115 to apply this test if the read_info is a cselib
3116 read. Anything with a constant base cannot alias
3117 something else with a different constant
3119 if ((read_info->group_id < 0)
3120 && canon_true_dependence (group->base_mem,
3122 group->canon_base_addr,
3123 read_info->mem, NULL_RTX,
3127 bitmap_ior_into (kill, group->group_kill);
3128 bitmap_and_compl_into (gen, group->group_kill);
3134 read_info = read_info->next;
3138 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3142 scan_reads_spill (read_info_t read_info, bitmap gen, bitmap kill)
3146 if (read_info->alias_set)
3148 int index = get_bitmap_index (clear_alias_group,
3149 read_info->alias_set);
3153 bitmap_set_bit (kill, index);
3154 bitmap_clear_bit (gen, index);
3158 read_info = read_info->next;
3163 /* Return the insn in BB_INFO before the first wild read or if there
3164 are no wild reads in the block, return the last insn. */
3167 find_insn_before_first_wild_read (bb_info_t bb_info)
3169 insn_info_t insn_info = bb_info->last_insn;
3170 insn_info_t last_wild_read = NULL;
3174 if (insn_info->wild_read)
3176 last_wild_read = insn_info->prev_insn;
3177 /* Block starts with wild read. */
3178 if (!last_wild_read)
3182 insn_info = insn_info->prev_insn;
3186 return last_wild_read;
3188 return bb_info->last_insn;
3192 /* Scan the insns in BB_INFO starting at PTR and going to the top of
3193 the block in order to build the gen and kill sets for the block.
3194 We start at ptr which may be the last insn in the block or may be
3195 the first insn with a wild read. In the latter case we are able to
3196 skip the rest of the block because it just does not matter:
3197 anything that happens is hidden by the wild read. */
3200 dse_step3_scan (bool for_spills, basic_block bb)
3202 bb_info_t bb_info = bb_table[bb->index];
3203 insn_info_t insn_info;
3206 /* There are no wild reads in the spill case. */
3207 insn_info = bb_info->last_insn;
3209 insn_info = find_insn_before_first_wild_read (bb_info);
3211 /* In the spill case or in the no_spill case if there is no wild
3212 read in the block, we will need a kill set. */
3213 if (insn_info == bb_info->last_insn)
3216 bitmap_clear (bb_info->kill);
3218 bb_info->kill = BITMAP_ALLOC (NULL);
3222 BITMAP_FREE (bb_info->kill);
3226 /* There may have been code deleted by the dce pass run before
3228 if (insn_info->insn && INSN_P (insn_info->insn))
3230 /* Process the read(s) last. */
3233 scan_stores_spill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3234 scan_reads_spill (insn_info->read_rec, bb_info->gen, bb_info->kill);
3238 scan_stores_nospill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3239 scan_reads_nospill (insn_info, bb_info->gen, bb_info->kill);
3243 insn_info = insn_info->prev_insn;
3248 /* Set the gen set of the exit block, and also any block with no
3249 successors that does not have a wild read. */
3252 dse_step3_exit_block_scan (bb_info_t bb_info)
3254 /* The gen set is all 0's for the exit block except for the
3255 frame_pointer_group. */
3257 if (stores_off_frame_dead_at_return)
3262 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
3264 if (group->process_globally && group->frame_related)
3265 bitmap_ior_into (bb_info->gen, group->group_kill);
3271 /* Find all of the blocks that are not backwards reachable from the
3272 exit block or any block with no successors (BB). These are the
3273 infinite loops or infinite self loops. These blocks will still
3274 have their bits set in UNREACHABLE_BLOCKS. */
3277 mark_reachable_blocks (sbitmap unreachable_blocks, basic_block bb)
3282 if (TEST_BIT (unreachable_blocks, bb->index))
3284 RESET_BIT (unreachable_blocks, bb->index);
3285 FOR_EACH_EDGE (e, ei, bb->preds)
3287 mark_reachable_blocks (unreachable_blocks, e->src);
3292 /* Build the transfer functions for the function. */
3295 dse_step3 (bool for_spills)
3298 sbitmap unreachable_blocks = sbitmap_alloc (last_basic_block);
3299 sbitmap_iterator sbi;
3300 bitmap all_ones = NULL;
3303 sbitmap_ones (unreachable_blocks);
3307 bb_info_t bb_info = bb_table[bb->index];
3309 bitmap_clear (bb_info->gen);
3311 bb_info->gen = BITMAP_ALLOC (NULL);
3313 if (bb->index == ENTRY_BLOCK)
3315 else if (bb->index == EXIT_BLOCK)
3316 dse_step3_exit_block_scan (bb_info);
3318 dse_step3_scan (for_spills, bb);
3319 if (EDGE_COUNT (bb->succs) == 0)
3320 mark_reachable_blocks (unreachable_blocks, bb);
3322 /* If this is the second time dataflow is run, delete the old
3325 BITMAP_FREE (bb_info->in);
3327 BITMAP_FREE (bb_info->out);
3330 /* For any block in an infinite loop, we must initialize the out set
3331 to all ones. This could be expensive, but almost never occurs in
3332 practice. However, it is common in regression tests. */
3333 EXECUTE_IF_SET_IN_SBITMAP (unreachable_blocks, 0, i, sbi)
3335 if (bitmap_bit_p (all_blocks, i))
3337 bb_info_t bb_info = bb_table[i];
3343 all_ones = BITMAP_ALLOC (NULL);
3344 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, j, group)
3345 bitmap_ior_into (all_ones, group->group_kill);
3349 bb_info->out = BITMAP_ALLOC (NULL);
3350 bitmap_copy (bb_info->out, all_ones);
3356 BITMAP_FREE (all_ones);
3357 sbitmap_free (unreachable_blocks);
3362 /*----------------------------------------------------------------------------
3365 Solve the bitvector equations.
3366 ----------------------------------------------------------------------------*/
3369 /* Confluence function for blocks with no successors. Create an out
3370 set from the gen set of the exit block. This block logically has
3371 the exit block as a successor. */
3376 dse_confluence_0 (basic_block bb)
3378 bb_info_t bb_info = bb_table[bb->index];
3380 if (bb->index == EXIT_BLOCK)
3385 bb_info->out = BITMAP_ALLOC (NULL);
3386 bitmap_copy (bb_info->out, bb_table[EXIT_BLOCK]->gen);
3390 /* Propagate the information from the in set of the dest of E to the
3391 out set of the src of E. If the various in or out sets are not
3392 there, that means they are all ones. */
3395 dse_confluence_n (edge e)
3397 bb_info_t src_info = bb_table[e->src->index];
3398 bb_info_t dest_info = bb_table[e->dest->index];
3403 bitmap_and_into (src_info->out, dest_info->in);
3406 src_info->out = BITMAP_ALLOC (NULL);
3407 bitmap_copy (src_info->out, dest_info->in);
3414 /* Propagate the info from the out to the in set of BB_INDEX's basic
3415 block. There are three cases:
3417 1) The block has no kill set. In this case the kill set is all
3418 ones. It does not matter what the out set of the block is, none of
3419 the info can reach the top. The only thing that reaches the top is
3420 the gen set and we just copy the set.
3422 2) There is a kill set but no out set and bb has successors. In
3423 this case we just return. Eventually an out set will be created and
3424 it is better to wait than to create a set of ones.
3426 3) There is both a kill and out set. We apply the obvious transfer
3431 dse_transfer_function (int bb_index)
3433 bb_info_t bb_info = bb_table[bb_index];
3441 return bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3442 bb_info->out, bb_info->kill);
3445 bb_info->in = BITMAP_ALLOC (NULL);
3446 bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3447 bb_info->out, bb_info->kill);
3457 /* Case 1 above. If there is already an in set, nothing
3463 bb_info->in = BITMAP_ALLOC (NULL);
3464 bitmap_copy (bb_info->in, bb_info->gen);
3470 /* Solve the dataflow equations. */
3475 df_simple_dataflow (DF_BACKWARD, NULL, dse_confluence_0,
3476 dse_confluence_n, dse_transfer_function,
3477 all_blocks, df_get_postorder (DF_BACKWARD),
3478 df_get_n_blocks (DF_BACKWARD));
3483 fprintf (dump_file, "\n\n*** Global dataflow info after analysis.\n");
3486 bb_info_t bb_info = bb_table[bb->index];
3488 df_print_bb_index (bb, dump_file);
3490 bitmap_print (dump_file, bb_info->in, " in: ", "\n");
3492 fprintf (dump_file, " in: *MISSING*\n");
3494 bitmap_print (dump_file, bb_info->gen, " gen: ", "\n");
3496 fprintf (dump_file, " gen: *MISSING*\n");
3498 bitmap_print (dump_file, bb_info->kill, " kill: ", "\n");
3500 fprintf (dump_file, " kill: *MISSING*\n");
3502 bitmap_print (dump_file, bb_info->out, " out: ", "\n");
3504 fprintf (dump_file, " out: *MISSING*\n\n");
3511 /*----------------------------------------------------------------------------
3514 Delete the stores that can only be deleted using the global information.
3515 ----------------------------------------------------------------------------*/
3519 dse_step5_nospill (void)
3524 bb_info_t bb_info = bb_table[bb->index];
3525 insn_info_t insn_info = bb_info->last_insn;
3526 bitmap v = bb_info->out;
3530 bool deleted = false;
3531 if (dump_file && insn_info->insn)
3533 fprintf (dump_file, "starting to process insn %d\n",
3534 INSN_UID (insn_info->insn));
3535 bitmap_print (dump_file, v, " v: ", "\n");
3538 /* There may have been code deleted by the dce pass run before
3541 && INSN_P (insn_info->insn)
3542 && (!insn_info->cannot_delete)
3543 && (!bitmap_empty_p (v)))
3545 store_info_t store_info = insn_info->store_rec;
3547 /* Try to delete the current insn. */
3550 /* Skip the clobbers. */
3551 while (!store_info->is_set)
3552 store_info = store_info->next;
3554 if (store_info->alias_set)
3559 group_info_t group_info
3560 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
3562 for (i = store_info->begin; i < store_info->end; i++)
3564 int index = get_bitmap_index (group_info, i);
3567 fprintf (dump_file, "i = %d, index = %d\n", (int)i, index);
3568 if (index == 0 || !bitmap_bit_p (v, index))
3571 fprintf (dump_file, "failing at i = %d\n", (int)i);
3581 check_for_inc_dec (insn_info->insn);
3582 delete_insn (insn_info->insn);
3583 insn_info->insn = NULL;
3588 /* We do want to process the local info if the insn was
3589 deleted. For instance, if the insn did a wild read, we
3590 no longer need to trash the info. */
3592 && INSN_P (insn_info->insn)
3595 scan_stores_nospill (insn_info->store_rec, v, NULL);
3596 if (insn_info->wild_read)
3599 fprintf (dump_file, "wild read\n");
3602 else if (insn_info->read_rec)
3605 fprintf (dump_file, "regular read\n");
3606 scan_reads_nospill (insn_info, v, NULL);
3610 insn_info = insn_info->prev_insn;
3617 dse_step5_spill (void)
3622 bb_info_t bb_info = bb_table[bb->index];
3623 insn_info_t insn_info = bb_info->last_insn;
3624 bitmap v = bb_info->out;
3628 bool deleted = false;
3629 /* There may have been code deleted by the dce pass run before
3632 && INSN_P (insn_info->insn)
3633 && (!insn_info->cannot_delete)
3634 && (!bitmap_empty_p (v)))
3636 /* Try to delete the current insn. */
3637 store_info_t store_info = insn_info->store_rec;
3642 if (store_info->alias_set)
3644 int index = get_bitmap_index (clear_alias_group,
3645 store_info->alias_set);
3646 if (index == 0 || !bitmap_bit_p (v, index))
3654 store_info = store_info->next;
3656 if (deleted && dbg_cnt (dse))
3659 fprintf (dump_file, "Spill deleting insn %d\n",
3660 INSN_UID (insn_info->insn));
3661 check_for_inc_dec (insn_info->insn);
3662 delete_insn (insn_info->insn);
3664 insn_info->insn = NULL;
3669 && INSN_P (insn_info->insn)
3672 scan_stores_spill (insn_info->store_rec, v, NULL);
3673 scan_reads_spill (insn_info->read_rec, v, NULL);
3676 insn_info = insn_info->prev_insn;
3683 /*----------------------------------------------------------------------------
3686 Delete stores made redundant by earlier stores (which store the same
3687 value) that couldn't be eliminated.
3688 ----------------------------------------------------------------------------*/
3697 bb_info_t bb_info = bb_table[bb->index];
3698 insn_info_t insn_info = bb_info->last_insn;
3702 /* There may have been code deleted by the dce pass run before
3705 && INSN_P (insn_info->insn)
3706 && !insn_info->cannot_delete)
3708 store_info_t s_info = insn_info->store_rec;
3710 while (s_info && !s_info->is_set)
3711 s_info = s_info->next;
3713 && s_info->redundant_reason
3714 && s_info->redundant_reason->insn
3715 && INSN_P (s_info->redundant_reason->insn))
3717 rtx rinsn = s_info->redundant_reason->insn;
3719 fprintf (dump_file, "Locally deleting insn %d "
3720 "because insn %d stores the "
3721 "same value and couldn't be "
3723 INSN_UID (insn_info->insn),
3725 delete_dead_store_insn (insn_info);
3728 insn_info = insn_info->prev_insn;
3733 /*----------------------------------------------------------------------------
3736 Destroy everything left standing.
3737 ----------------------------------------------------------------------------*/
3740 dse_step7 (bool global_done)
3746 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
3748 free (group->offset_map_n);
3749 free (group->offset_map_p);
3750 BITMAP_FREE (group->store1_n);
3751 BITMAP_FREE (group->store1_p);
3752 BITMAP_FREE (group->store2_n);
3753 BITMAP_FREE (group->store2_p);
3754 BITMAP_FREE (group->group_kill);
3760 bb_info_t bb_info = bb_table[bb->index];
3761 BITMAP_FREE (bb_info->gen);
3763 BITMAP_FREE (bb_info->kill);
3765 BITMAP_FREE (bb_info->in);
3767 BITMAP_FREE (bb_info->out);
3770 if (clear_alias_sets)
3772 BITMAP_FREE (clear_alias_sets);
3773 BITMAP_FREE (disqualified_clear_alias_sets);
3774 free_alloc_pool (clear_alias_mode_pool);
3775 htab_delete (clear_alias_mode_table);
3778 end_alias_analysis ();
3780 htab_delete (rtx_group_table);
3781 VEC_free (group_info_t, heap, rtx_group_vec);
3782 BITMAP_FREE (all_blocks);
3783 BITMAP_FREE (scratch);
3785 free_alloc_pool (rtx_store_info_pool);
3786 free_alloc_pool (read_info_pool);
3787 free_alloc_pool (insn_info_pool);
3788 free_alloc_pool (bb_info_pool);
3789 free_alloc_pool (rtx_group_info_pool);
3790 free_alloc_pool (deferred_change_pool);
3794 /* -------------------------------------------------------------------------
3796 ------------------------------------------------------------------------- */
3798 /* Callback for running pass_rtl_dse. */
3801 rest_of_handle_dse (void)
3803 bool did_global = false;
3805 df_set_flags (DF_DEFER_INSN_RESCAN);
3807 /* Need the notes since we must track live hardregs in the forwards
3809 df_note_add_problem ();
3815 if (dse_step2_nospill ())
3817 df_set_flags (DF_LR_RUN_DCE);
3821 fprintf (dump_file, "doing global processing\n");
3824 dse_step5_nospill ();
3827 /* For the instance of dse that runs after reload, we make a special
3828 pass to process the spills. These are special in that they are
3829 totally transparent, i.e, there is no aliasing issues that need
3830 to be considered. This means that the wild reads that kill
3831 everything else do not apply here. */
3832 if (clear_alias_sets && dse_step2_spill ())
3836 df_set_flags (DF_LR_RUN_DCE);
3841 fprintf (dump_file, "doing global spill processing\n");
3848 dse_step7 (did_global);
3851 fprintf (dump_file, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3852 locally_deleted, globally_deleted, spill_deleted);
3859 return gate_dse1 () || gate_dse2 ();
3865 return optimize > 0 && flag_dse
3872 return optimize > 0 && flag_dse
3876 struct rtl_opt_pass pass_rtl_dse1 =
3881 gate_dse1, /* gate */
3882 rest_of_handle_dse, /* execute */
3885 0, /* static_pass_number */
3886 TV_DSE1, /* tv_id */
3887 0, /* properties_required */
3888 0, /* properties_provided */
3889 0, /* properties_destroyed */
3890 0, /* todo_flags_start */
3892 TODO_df_finish | TODO_verify_rtl_sharing |
3893 TODO_ggc_collect /* todo_flags_finish */
3897 struct rtl_opt_pass pass_rtl_dse2 =
3902 gate_dse2, /* gate */
3903 rest_of_handle_dse, /* execute */
3906 0, /* static_pass_number */
3907 TV_DSE2, /* tv_id */
3908 0, /* properties_required */
3909 0, /* properties_provided */
3910 0, /* properties_destroyed */
3911 0, /* todo_flags_start */
3913 TODO_df_finish | TODO_verify_rtl_sharing |
3914 TODO_ggc_collect /* todo_flags_finish */