1 /* RTL dead store elimination.
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
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"
52 /* This file contains three techniques for performing Dead Store
55 * The first technique performs dse locally on any base address. It
56 is based on the cselib which is a local value numbering technique.
57 This technique is local to a basic block but deals with a fairly
60 * The second technique performs dse globally but is restricted to
61 base addresses that are either constant or are relative to the
64 * The third technique, (which is only done after register allocation)
65 processes the spill spill slots. This differs from the second
66 technique because it takes advantage of the fact that spilling is
67 completely free from the effects of aliasing.
69 Logically, dse is a backwards dataflow problem. A store can be
70 deleted if it if cannot be reached in the backward direction by any
71 use of the value being stored. However, the local technique uses a
72 forwards scan of the basic block because cselib requires that the
73 block be processed in that order.
75 The pass is logically broken into 7 steps:
79 1) The local algorithm, as well as scanning the insns for the two
82 2) Analysis to see if the global algs are necessary. In the case
83 of stores base on a constant address, there must be at least two
84 stores to that address, to make it possible to delete some of the
85 stores. In the case of stores off of the frame or spill related
86 stores, only one store to an address is necessary because those
87 stores die at the end of the function.
89 3) Set up the global dataflow equations based on processing the
90 info parsed in the first step.
92 4) Solve the dataflow equations.
94 5) Delete the insns that the global analysis has indicated are
97 6) Delete insns that store the same value as preceeding store
98 where the earlier store couldn't be eliminated.
102 This step uses cselib and canon_rtx to build the largest expression
103 possible for each address. This pass is a forwards pass through
104 each basic block. From the point of view of the global technique,
105 the first pass could examine a block in either direction. The
106 forwards ordering is to accommodate cselib.
108 We a simplifying assumption: addresses fall into four broad
111 1) base has rtx_varies_p == false, offset is constant.
112 2) base has rtx_varies_p == false, offset variable.
113 3) base has rtx_varies_p == true, offset constant.
114 4) base has rtx_varies_p == true, offset variable.
116 The local passes are able to process all 4 kinds of addresses. The
117 global pass only handles (1).
119 The global problem is formulated as follows:
121 A store, S1, to address A, where A is not relative to the stack
122 frame, can be eliminated if all paths from S1 to the end of the
123 of the function contain another store to A before a read to A.
125 If the address A is relative to the stack frame, a store S2 to A
126 can be eliminated if there are no paths from S1 that reach the
127 end of the function that read A before another store to A. In
128 this case S2 can be deleted if there are paths to from S2 to the
129 end of the function that have no reads or writes to A. This
130 second case allows stores to the stack frame to be deleted that
131 would otherwise die when the function returns. This cannot be
132 done if stores_off_frame_dead_at_return is not true. See the doc
133 for that variable for when this variable is false.
135 The global problem is formulated as a backwards set union
136 dataflow problem where the stores are the gens and reads are the
137 kills. Set union problems are rare and require some special
138 handling given our representation of bitmaps. A straightforward
139 implementation of requires a lot of bitmaps filled with 1s.
140 These are expensive and cumbersome in our bitmap formulation so
141 care has been taken to avoid large vectors filled with 1s. See
142 the comments in bb_info and in the dataflow confluence functions
145 There are two places for further enhancements to this algorithm:
147 1) The original dse which was embedded in a pass called flow also
148 did local address forwarding. For example in
153 flow would replace the right hand side of the second insn with a
154 reference to r100. Most of the information is available to add this
155 to this pass. It has not done it because it is a lot of work in
156 the case that either r100 is assigned to between the first and
157 second insn and/or the second insn is a load of part of the value
158 stored by the first insn.
160 insn 5 in gcc.c-torture/compile/990203-1.c simple case.
161 insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
162 insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
163 insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
165 2) The cleaning up of spill code is quite profitable. It currently
166 depends on reading tea leaves and chicken entrails left by reload.
167 This pass depends on reload creating a singleton alias set for each
168 spill slot and telling the next dse pass which of these alias sets
169 are the singletons. Rather than analyze the addresses of the
170 spills, dse's spill processing just does analysis of the loads and
171 stores that use those alias sets. There are three cases where this
174 a) Reload sometimes creates the slot for one mode of access, and
175 then inserts loads and/or stores for a smaller mode. In this
176 case, the current code just punts on the slot. The proper thing
177 to do is to back out and use one bit vector position for each
178 byte of the entity associated with the slot. This depends on
179 KNOWING that reload always generates the accesses for each of the
180 bytes in some canonical (read that easy to understand several
181 passes after reload happens) way.
183 b) Reload sometimes decides that spill slot it allocated was not
184 large enough for the mode and goes back and allocates more slots
185 with the same mode and alias set. The backout in this case is a
186 little more graceful than (a). In this case the slot is unmarked
187 as being a spill slot and if final address comes out to be based
188 off the frame pointer, the global algorithm handles this slot.
190 c) For any pass that may prespill, there is currently no
191 mechanism to tell the dse pass that the slot being used has the
192 special properties that reload uses. It may be that all that is
193 required is to have those passes make the same calls that reload
194 does, assuming that the alias sets can be manipulated in the same
197 /* There are limits to the size of constant offsets we model for the
198 global problem. There are certainly test cases, that exceed this
199 limit, however, it is unlikely that there are important programs
200 that really have constant offsets this size. */
201 #define MAX_OFFSET (64 * 1024)
204 static bitmap scratch = NULL;
207 /* This structure holds information about a candidate store. */
211 /* False means this is a clobber. */
214 /* False if a single HOST_WIDE_INT bitmap is used for positions_needed. */
217 /* The id of the mem group of the base address. If rtx_varies_p is
218 true, this is -1. Otherwise, it is the index into the group
222 /* This is the cselib value. */
223 cselib_val *cse_base;
225 /* This canonized mem. */
228 /* Canonized MEM address for use by canon_true_dependence. */
231 /* If this is non-zero, it is the alias set of a spill location. */
232 alias_set_type alias_set;
234 /* The offset of the first and byte before the last byte associated
235 with the operation. */
236 HOST_WIDE_INT begin, end;
240 /* A bitmask as wide as the number of bytes in the word that
241 contains a 1 if the byte may be needed. The store is unused if
242 all of the bits are 0. This is used if IS_LARGE is false. */
243 unsigned HOST_WIDE_INT small_bitmask;
247 /* A bitmap with one bit per byte. Cleared bit means the position
248 is needed. Used if IS_LARGE is false. */
251 /* Number of set bits (i.e. unneeded bytes) in BITMAP. If it is
252 equal to END - BEGIN, the whole store is unused. */
257 /* The next store info for this insn. */
258 struct store_info *next;
260 /* The right hand side of the store. This is used if there is a
261 subsequent reload of the mems address somewhere later in the
265 /* If rhs is or holds a constant, this contains that constant,
269 /* Set if this store stores the same constant value as REDUNDANT_REASON
270 insn stored. These aren't eliminated early, because doing that
271 might prevent the earlier larger store to be eliminated. */
272 struct insn_info *redundant_reason;
275 /* Return a bitmask with the first N low bits set. */
277 static unsigned HOST_WIDE_INT
278 lowpart_bitmask (int n)
280 unsigned HOST_WIDE_INT mask = ~(unsigned HOST_WIDE_INT) 0;
281 return mask >> (HOST_BITS_PER_WIDE_INT - n);
284 typedef struct store_info *store_info_t;
285 static alloc_pool cse_store_info_pool;
286 static alloc_pool rtx_store_info_pool;
288 /* This structure holds information about a load. These are only
289 built for rtx bases. */
292 /* The id of the mem group of the base address. */
295 /* If this is non-zero, it is the alias set of a spill location. */
296 alias_set_type alias_set;
298 /* The offset of the first and byte after the last byte associated
299 with the operation. If begin == end == 0, the read did not have
300 a constant offset. */
303 /* The mem being read. */
306 /* The next read_info for this insn. */
307 struct read_info *next;
309 typedef struct read_info *read_info_t;
310 static alloc_pool read_info_pool;
313 /* One of these records is created for each insn. */
317 /* Set true if the insn contains a store but the insn itself cannot
318 be deleted. This is set if the insn is a parallel and there is
319 more than one non dead output or if the insn is in some way
323 /* This field is only used by the global algorithm. It is set true
324 if the insn contains any read of mem except for a (1). This is
325 also set if the insn is a call or has a clobber mem. If the insn
326 contains a wild read, the use_rec will be null. */
329 /* This field is only used for the processing of const functions.
330 These functions cannot read memory, but they can read the stack
331 because that is where they may get their parms. We need to be
332 this conservative because, like the store motion pass, we don't
333 consider CALL_INSN_FUNCTION_USAGE when processing call insns.
334 Moreover, we need to distinguish two cases:
335 1. Before reload (register elimination), the stores related to
336 outgoing arguments are stack pointer based and thus deemed
337 of non-constant base in this pass. This requires special
338 handling but also means that the frame pointer based stores
339 need not be killed upon encountering a const function call.
340 2. After reload, the stores related to outgoing arguments can be
341 either stack pointer or hard frame pointer based. This means
342 that we have no other choice than also killing all the frame
343 pointer based stores upon encountering a const function call.
344 This field is set after reload for const function calls. Having
345 this set is less severe than a wild read, it just means that all
346 the frame related stores are killed rather than all the stores. */
349 /* This field is only used for the processing of const functions.
350 It is set if the insn may contain a stack pointer based store. */
351 bool stack_pointer_based;
353 /* This is true if any of the sets within the store contains a
354 cselib base. Such stores can only be deleted by the local
356 bool contains_cselib_groups;
361 /* The list of mem sets or mem clobbers that are contained in this
362 insn. If the insn is deletable, it contains only one mem set.
363 But it could also contain clobbers. Insns that contain more than
364 one mem set are not deletable, but each of those mems are here in
365 order to provide info to delete other insns. */
366 store_info_t store_rec;
368 /* The linked list of mem uses in this insn. Only the reads from
369 rtx bases are listed here. The reads to cselib bases are
370 completely processed during the first scan and so are never
372 read_info_t read_rec;
374 /* The prev insn in the basic block. */
375 struct insn_info * prev_insn;
377 /* The linked list of insns that are in consideration for removal in
378 the forwards pass thru the basic block. This pointer may be
379 trash as it is not cleared when a wild read occurs. The only
380 time it is guaranteed to be correct is when the traversal starts
381 at active_local_stores. */
382 struct insn_info * next_local_store;
385 typedef struct insn_info *insn_info_t;
386 static alloc_pool insn_info_pool;
388 /* The linked list of stores that are under consideration in this
390 static insn_info_t active_local_stores;
391 static int active_local_stores_len;
396 /* Pointer to the insn info for the last insn in the block. These
397 are linked so this is how all of the insns are reached. During
398 scanning this is the current insn being scanned. */
399 insn_info_t last_insn;
401 /* The info for the global dataflow problem. */
404 /* This is set if the transfer function should and in the wild_read
405 bitmap before applying the kill and gen sets. That vector knocks
406 out most of the bits in the bitmap and thus speeds up the
408 bool apply_wild_read;
410 /* The following 4 bitvectors hold information about which positions
411 of which stores are live or dead. They are indexed by
414 /* The set of store positions that exist in this block before a wild read. */
417 /* The set of load positions that exist in this block above the
418 same position of a store. */
421 /* The set of stores that reach the top of the block without being
424 Do not represent the in if it is all ones. Note that this is
425 what the bitvector should logically be initialized to for a set
426 intersection problem. However, like the kill set, this is too
427 expensive. So initially, the in set will only be created for the
428 exit block and any block that contains a wild read. */
431 /* The set of stores that reach the bottom of the block from it's
434 Do not represent the in if it is all ones. Note that this is
435 what the bitvector should logically be initialized to for a set
436 intersection problem. However, like the kill and in set, this is
437 too expensive. So what is done is that the confluence operator
438 just initializes the vector from one of the out sets of the
439 successors of the block. */
442 /* The following bitvector is indexed by the reg number. It
443 contains the set of regs that are live at the current instruction
444 being processed. While it contains info for all of the
445 registers, only the pseudos are actually examined. It is used to
446 assure that shift sequences that are inserted do not accidently
447 clobber live hard regs. */
451 typedef struct bb_info *bb_info_t;
452 static alloc_pool bb_info_pool;
454 /* Table to hold all bb_infos. */
455 static bb_info_t *bb_table;
457 /* There is a group_info for each rtx base that is used to reference
458 memory. There are also not many of the rtx bases because they are
459 very limited in scope. */
463 /* The actual base of the address. */
466 /* The sequential id of the base. This allows us to have a
467 canonical ordering of these that is not based on addresses. */
470 /* True if there are any positions that are to be processed
472 bool process_globally;
474 /* True if the base of this group is either the frame_pointer or
475 hard_frame_pointer. */
478 /* A mem wrapped around the base pointer for the group in order to do
479 read dependency. It must be given BLKmode in order to encompass all
480 the possible offsets from the base. */
483 /* Canonized version of base_mem's address. */
486 /* These two sets of two bitmaps are used to keep track of how many
487 stores are actually referencing that position from this base. We
488 only do this for rtx bases as this will be used to assign
489 positions in the bitmaps for the global problem. Bit N is set in
490 store1 on the first store for offset N. Bit N is set in store2
491 for the second store to offset N. This is all we need since we
492 only care about offsets that have two or more stores for them.
494 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
495 for 0 and greater offsets.
497 There is one special case here, for stores into the stack frame,
498 we will or store1 into store2 before deciding which stores look
499 at globally. This is because stores to the stack frame that have
500 no other reads before the end of the function can also be
502 bitmap store1_n, store1_p, store2_n, store2_p;
504 /* The positions in this bitmap have the same assignments as the in,
505 out, gen and kill bitmaps. This bitmap is all zeros except for
506 the positions that are occupied by stores for this group. */
509 /* The offset_map is used to map the offsets from this base into
510 positions in the global bitmaps. It is only created after all of
511 the all of stores have been scanned and we know which ones we
513 int *offset_map_n, *offset_map_p;
514 int offset_map_size_n, offset_map_size_p;
516 typedef struct group_info *group_info_t;
517 typedef const struct group_info *const_group_info_t;
518 static alloc_pool rtx_group_info_pool;
520 /* Tables of group_info structures, hashed by base value. */
521 static htab_t rtx_group_table;
523 /* Index into the rtx_group_vec. */
524 static int rtx_group_next_id;
526 DEF_VEC_P(group_info_t);
527 DEF_VEC_ALLOC_P(group_info_t,heap);
529 static VEC(group_info_t,heap) *rtx_group_vec;
532 /* This structure holds the set of changes that are being deferred
533 when removing read operation. See replace_read. */
534 struct deferred_change
537 /* The mem that is being replaced. */
540 /* The reg it is being replaced with. */
543 struct deferred_change *next;
546 typedef struct deferred_change *deferred_change_t;
547 static alloc_pool deferred_change_pool;
549 static deferred_change_t deferred_change_list = NULL;
551 /* This are used to hold the alias sets of spill variables. Since
552 these are never aliased and there may be a lot of them, it makes
553 sense to treat them specially. This bitvector is only allocated in
554 calls from dse_record_singleton_alias_set which currently is only
555 made during reload1. So when dse is called before reload this
556 mechanism does nothing. */
558 static bitmap clear_alias_sets = NULL;
560 /* The set of clear_alias_sets that have been disqualified because
561 there are loads or stores using a different mode than the alias set
562 was registered with. */
563 static bitmap disqualified_clear_alias_sets = NULL;
565 /* The group that holds all of the clear_alias_sets. */
566 static group_info_t clear_alias_group;
568 /* The modes of the clear_alias_sets. */
569 static htab_t clear_alias_mode_table;
571 /* Hash table element to look up the mode for an alias set. */
572 struct clear_alias_mode_holder
574 alias_set_type alias_set;
575 enum machine_mode mode;
578 static alloc_pool clear_alias_mode_pool;
580 /* This is true except if cfun->stdarg -- i.e. we cannot do
581 this for vararg functions because they play games with the frame. */
582 static bool stores_off_frame_dead_at_return;
584 /* Counter for stats. */
585 static int globally_deleted;
586 static int locally_deleted;
587 static int spill_deleted;
589 static bitmap all_blocks;
591 /* The number of bits used in the global bitmaps. */
592 static unsigned int current_position;
595 static bool gate_dse (void);
596 static bool gate_dse1 (void);
597 static bool gate_dse2 (void);
600 /*----------------------------------------------------------------------------
604 ----------------------------------------------------------------------------*/
606 /* Hashtable callbacks for maintaining the "bases" field of
607 store_group_info, given that the addresses are function invariants. */
610 clear_alias_mode_eq (const void *p1, const void *p2)
612 const struct clear_alias_mode_holder * h1
613 = (const struct clear_alias_mode_holder *) p1;
614 const struct clear_alias_mode_holder * h2
615 = (const struct clear_alias_mode_holder *) p2;
616 return h1->alias_set == h2->alias_set;
621 clear_alias_mode_hash (const void *p)
623 const struct clear_alias_mode_holder *holder
624 = (const struct clear_alias_mode_holder *) p;
625 return holder->alias_set;
629 /* Find the entry associated with ALIAS_SET. */
631 static struct clear_alias_mode_holder *
632 clear_alias_set_lookup (alias_set_type alias_set)
634 struct clear_alias_mode_holder tmp_holder;
637 tmp_holder.alias_set = alias_set;
638 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, NO_INSERT);
641 return (struct clear_alias_mode_holder *) *slot;
645 /* Hashtable callbacks for maintaining the "bases" field of
646 store_group_info, given that the addresses are function invariants. */
649 invariant_group_base_eq (const void *p1, const void *p2)
651 const_group_info_t gi1 = (const_group_info_t) p1;
652 const_group_info_t gi2 = (const_group_info_t) p2;
653 return rtx_equal_p (gi1->rtx_base, gi2->rtx_base);
658 invariant_group_base_hash (const void *p)
660 const_group_info_t gi = (const_group_info_t) p;
662 return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false);
666 /* Get the GROUP for BASE. Add a new group if it is not there. */
669 get_group_info (rtx base)
671 struct group_info tmp_gi;
677 /* Find the store_base_info structure for BASE, creating a new one
679 tmp_gi.rtx_base = base;
680 slot = htab_find_slot (rtx_group_table, &tmp_gi, INSERT);
681 gi = (group_info_t) *slot;
685 if (!clear_alias_group)
687 clear_alias_group = gi =
688 (group_info_t) pool_alloc (rtx_group_info_pool);
689 memset (gi, 0, sizeof (struct group_info));
690 gi->id = rtx_group_next_id++;
691 gi->store1_n = BITMAP_ALLOC (NULL);
692 gi->store1_p = BITMAP_ALLOC (NULL);
693 gi->store2_n = BITMAP_ALLOC (NULL);
694 gi->store2_p = BITMAP_ALLOC (NULL);
695 gi->group_kill = BITMAP_ALLOC (NULL);
696 gi->process_globally = false;
697 gi->offset_map_size_n = 0;
698 gi->offset_map_size_p = 0;
699 gi->offset_map_n = NULL;
700 gi->offset_map_p = NULL;
701 VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);
703 return clear_alias_group;
708 *slot = gi = (group_info_t) pool_alloc (rtx_group_info_pool);
710 gi->id = rtx_group_next_id++;
711 gi->base_mem = gen_rtx_MEM (BLKmode, base);
712 gi->canon_base_addr = canon_rtx (base);
713 gi->store1_n = BITMAP_ALLOC (NULL);
714 gi->store1_p = BITMAP_ALLOC (NULL);
715 gi->store2_n = BITMAP_ALLOC (NULL);
716 gi->store2_p = BITMAP_ALLOC (NULL);
717 gi->group_kill = BITMAP_ALLOC (NULL);
718 gi->process_globally = false;
720 (base == frame_pointer_rtx) || (base == hard_frame_pointer_rtx);
721 gi->offset_map_size_n = 0;
722 gi->offset_map_size_p = 0;
723 gi->offset_map_n = NULL;
724 gi->offset_map_p = NULL;
725 VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);
732 /* Initialization of data structures. */
738 globally_deleted = 0;
741 scratch = BITMAP_ALLOC (NULL);
744 = create_alloc_pool ("rtx_store_info_pool",
745 sizeof (struct store_info), 100);
747 = create_alloc_pool ("read_info_pool",
748 sizeof (struct read_info), 100);
750 = create_alloc_pool ("insn_info_pool",
751 sizeof (struct insn_info), 100);
753 = create_alloc_pool ("bb_info_pool",
754 sizeof (struct bb_info), 100);
756 = create_alloc_pool ("rtx_group_info_pool",
757 sizeof (struct group_info), 100);
759 = create_alloc_pool ("deferred_change_pool",
760 sizeof (struct deferred_change), 10);
762 rtx_group_table = htab_create (11, invariant_group_base_hash,
763 invariant_group_base_eq, NULL);
765 bb_table = XCNEWVEC (bb_info_t, last_basic_block);
766 rtx_group_next_id = 0;
768 stores_off_frame_dead_at_return = !cfun->stdarg;
770 init_alias_analysis ();
772 if (clear_alias_sets)
773 clear_alias_group = get_group_info (NULL);
775 clear_alias_group = NULL;
780 /*----------------------------------------------------------------------------
783 Scan all of the insns. Any random ordering of the blocks is fine.
784 Each block is scanned in forward order to accommodate cselib which
785 is used to remove stores with non-constant bases.
786 ----------------------------------------------------------------------------*/
788 /* Delete all of the store_info recs from INSN_INFO. */
791 free_store_info (insn_info_t insn_info)
793 store_info_t store_info = insn_info->store_rec;
796 store_info_t next = store_info->next;
797 if (store_info->is_large)
798 BITMAP_FREE (store_info->positions_needed.large.bmap);
799 if (store_info->cse_base)
800 pool_free (cse_store_info_pool, store_info);
802 pool_free (rtx_store_info_pool, store_info);
806 insn_info->cannot_delete = true;
807 insn_info->contains_cselib_groups = false;
808 insn_info->store_rec = NULL;
811 /* Callback for for_each_inc_dec that emits an INSN that sets DEST to
812 SRC + SRCOFF before insn ARG. */
815 emit_inc_dec_insn_before (rtx mem ATTRIBUTE_UNUSED,
816 rtx op ATTRIBUTE_UNUSED,
817 rtx dest, rtx src, rtx srcoff, void *arg)
822 src = gen_rtx_PLUS (GET_MODE (src), src, srcoff);
824 /* We can reuse all operands without copying, because we are about
825 to delete the insn that contained it. */
827 emit_insn_before (gen_rtx_SET (VOIDmode, dest, src), insn);
832 /* Before we delete INSN, make sure that the auto inc/dec, if it is
833 there, is split into a separate insn. */
836 check_for_inc_dec (rtx insn)
838 rtx note = find_reg_note (insn, REG_INC, NULL_RTX);
840 for_each_inc_dec (&insn, emit_inc_dec_insn_before, insn);
844 /* Delete the insn and free all of the fields inside INSN_INFO. */
847 delete_dead_store_insn (insn_info_t insn_info)
849 read_info_t read_info;
854 check_for_inc_dec (insn_info->insn);
857 fprintf (dump_file, "Locally deleting insn %d ",
858 INSN_UID (insn_info->insn));
859 if (insn_info->store_rec->alias_set)
860 fprintf (dump_file, "alias set %d\n",
861 (int) insn_info->store_rec->alias_set);
863 fprintf (dump_file, "\n");
866 free_store_info (insn_info);
867 read_info = insn_info->read_rec;
871 read_info_t next = read_info->next;
872 pool_free (read_info_pool, read_info);
875 insn_info->read_rec = NULL;
877 delete_insn (insn_info->insn);
879 insn_info->insn = NULL;
881 insn_info->wild_read = false;
885 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
889 set_usage_bits (group_info_t group, HOST_WIDE_INT offset, HOST_WIDE_INT width)
893 if (offset > -MAX_OFFSET && offset + width < MAX_OFFSET)
894 for (i=offset; i<offset+width; i++)
901 store1 = group->store1_n;
902 store2 = group->store2_n;
907 store1 = group->store1_p;
908 store2 = group->store2_p;
912 if (!bitmap_set_bit (store1, ai))
913 bitmap_set_bit (store2, ai);
918 if (group->offset_map_size_n < ai)
919 group->offset_map_size_n = ai;
923 if (group->offset_map_size_p < ai)
924 group->offset_map_size_p = ai;
931 /* Set the BB_INFO so that the last insn is marked as a wild read. */
934 add_wild_read (bb_info_t bb_info)
936 insn_info_t insn_info = bb_info->last_insn;
937 read_info_t *ptr = &insn_info->read_rec;
941 read_info_t next = (*ptr)->next;
942 if ((*ptr)->alias_set == 0)
944 pool_free (read_info_pool, *ptr);
950 insn_info->wild_read = true;
951 active_local_stores = NULL;
952 active_local_stores_len = 0;
956 /* Return true if X is a constant or one of the registers that behave
957 as a constant over the life of a function. This is equivalent to
958 !rtx_varies_p for memory addresses. */
961 const_or_frame_p (rtx x)
963 switch (GET_CODE (x))
974 /* Note that we have to test for the actual rtx used for the frame
975 and arg pointers and not just the register number in case we have
976 eliminated the frame and/or arg pointer and are using it
978 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
979 /* The arg pointer varies if it is not a fixed register. */
980 || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
981 || x == pic_offset_table_rtx)
990 /* Take all reasonable action to put the address of MEM into the form
991 that we can do analysis on.
993 The gold standard is to get the address into the form: address +
994 OFFSET where address is something that rtx_varies_p considers a
995 constant. When we can get the address in this form, we can do
996 global analysis on it. Note that for constant bases, address is
997 not actually returned, only the group_id. The address can be
1000 If that fails, we try cselib to get a value we can at least use
1001 locally. If that fails we return false.
1003 The GROUP_ID is set to -1 for cselib bases and the index of the
1004 group for non_varying bases.
1006 FOR_READ is true if this is a mem read and false if not. */
1009 canon_address (rtx mem,
1010 alias_set_type *alias_set_out,
1012 HOST_WIDE_INT *offset,
1015 enum machine_mode address_mode
1016 = targetm.addr_space.address_mode (MEM_ADDR_SPACE (mem));
1017 rtx mem_address = XEXP (mem, 0);
1018 rtx expanded_address, address;
1021 /* Make sure that cselib is has initialized all of the operands of
1022 the address before asking it to do the subst. */
1024 if (clear_alias_sets)
1026 /* If this is a spill, do not do any further processing. */
1027 alias_set_type alias_set = MEM_ALIAS_SET (mem);
1029 fprintf (dump_file, "found alias set %d\n", (int) alias_set);
1030 if (bitmap_bit_p (clear_alias_sets, alias_set))
1032 struct clear_alias_mode_holder *entry
1033 = clear_alias_set_lookup (alias_set);
1035 /* If the modes do not match, we cannot process this set. */
1036 if (entry->mode != GET_MODE (mem))
1040 "disqualifying alias set %d, (%s) != (%s)\n",
1041 (int) alias_set, GET_MODE_NAME (entry->mode),
1042 GET_MODE_NAME (GET_MODE (mem)));
1044 bitmap_set_bit (disqualified_clear_alias_sets, alias_set);
1048 *alias_set_out = alias_set;
1049 *group_id = clear_alias_group->id;
1056 cselib_lookup (mem_address, address_mode, 1, GET_MODE (mem));
1060 fprintf (dump_file, " mem: ");
1061 print_inline_rtx (dump_file, mem_address, 0);
1062 fprintf (dump_file, "\n");
1065 /* First see if just canon_rtx (mem_address) is const or frame,
1066 if not, try cselib_expand_value_rtx and call canon_rtx on that. */
1068 for (expanded = 0; expanded < 2; expanded++)
1072 /* Use cselib to replace all of the reg references with the full
1073 expression. This will take care of the case where we have
1075 r_x = base + offset;
1080 val = *(base + offset); */
1082 expanded_address = cselib_expand_value_rtx (mem_address,
1085 /* If this fails, just go with the address from first
1087 if (!expanded_address)
1091 expanded_address = mem_address;
1093 /* Split the address into canonical BASE + OFFSET terms. */
1094 address = canon_rtx (expanded_address);
1102 fprintf (dump_file, "\n after cselib_expand address: ");
1103 print_inline_rtx (dump_file, expanded_address, 0);
1104 fprintf (dump_file, "\n");
1107 fprintf (dump_file, "\n after canon_rtx address: ");
1108 print_inline_rtx (dump_file, address, 0);
1109 fprintf (dump_file, "\n");
1112 if (GET_CODE (address) == CONST)
1113 address = XEXP (address, 0);
1115 if (GET_CODE (address) == PLUS
1116 && CONST_INT_P (XEXP (address, 1)))
1118 *offset = INTVAL (XEXP (address, 1));
1119 address = XEXP (address, 0);
1122 if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem))
1123 && const_or_frame_p (address))
1125 group_info_t group = get_group_info (address);
1128 fprintf (dump_file, " gid=%d offset=%d \n",
1129 group->id, (int)*offset);
1131 *group_id = group->id;
1136 *base = cselib_lookup (address, address_mode, true, GET_MODE (mem));
1142 fprintf (dump_file, " no cselib val - should be a wild read.\n");
1146 fprintf (dump_file, " varying cselib base=%u:%u offset = %d\n",
1147 (*base)->uid, (*base)->hash, (int)*offset);
1152 /* Clear the rhs field from the active_local_stores array. */
1155 clear_rhs_from_active_local_stores (void)
1157 insn_info_t ptr = active_local_stores;
1161 store_info_t store_info = ptr->store_rec;
1162 /* Skip the clobbers. */
1163 while (!store_info->is_set)
1164 store_info = store_info->next;
1166 store_info->rhs = NULL;
1167 store_info->const_rhs = NULL;
1169 ptr = ptr->next_local_store;
1174 /* Mark byte POS bytes from the beginning of store S_INFO as unneeded. */
1177 set_position_unneeded (store_info_t s_info, int pos)
1179 if (__builtin_expect (s_info->is_large, false))
1181 if (bitmap_set_bit (s_info->positions_needed.large.bmap, pos))
1182 s_info->positions_needed.large.count++;
1185 s_info->positions_needed.small_bitmask
1186 &= ~(((unsigned HOST_WIDE_INT) 1) << pos);
1189 /* Mark the whole store S_INFO as unneeded. */
1192 set_all_positions_unneeded (store_info_t s_info)
1194 if (__builtin_expect (s_info->is_large, false))
1196 int pos, end = s_info->end - s_info->begin;
1197 for (pos = 0; pos < end; pos++)
1198 bitmap_set_bit (s_info->positions_needed.large.bmap, pos);
1199 s_info->positions_needed.large.count = end;
1202 s_info->positions_needed.small_bitmask = (unsigned HOST_WIDE_INT) 0;
1205 /* Return TRUE if any bytes from S_INFO store are needed. */
1208 any_positions_needed_p (store_info_t s_info)
1210 if (__builtin_expect (s_info->is_large, false))
1211 return (s_info->positions_needed.large.count
1212 < s_info->end - s_info->begin);
1214 return (s_info->positions_needed.small_bitmask
1215 != (unsigned HOST_WIDE_INT) 0);
1218 /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
1219 store are needed. */
1222 all_positions_needed_p (store_info_t s_info, int start, int width)
1224 if (__builtin_expect (s_info->is_large, false))
1226 int end = start + width;
1228 if (bitmap_bit_p (s_info->positions_needed.large.bmap, start++))
1234 unsigned HOST_WIDE_INT mask = lowpart_bitmask (width) << start;
1235 return (s_info->positions_needed.small_bitmask & mask) == mask;
1240 static rtx get_stored_val (store_info_t, enum machine_mode, HOST_WIDE_INT,
1241 HOST_WIDE_INT, basic_block, bool);
1244 /* BODY is an instruction pattern that belongs to INSN. Return 1 if
1245 there is a candidate store, after adding it to the appropriate
1246 local store group if so. */
1249 record_store (rtx body, bb_info_t bb_info)
1251 rtx mem, rhs, const_rhs, mem_addr;
1252 HOST_WIDE_INT offset = 0;
1253 HOST_WIDE_INT width = 0;
1254 alias_set_type spill_alias_set;
1255 insn_info_t insn_info = bb_info->last_insn;
1256 store_info_t store_info = NULL;
1258 cselib_val *base = NULL;
1259 insn_info_t ptr, last, redundant_reason;
1260 bool store_is_unused;
1262 if (GET_CODE (body) != SET && GET_CODE (body) != CLOBBER)
1265 mem = SET_DEST (body);
1267 /* If this is not used, then this cannot be used to keep the insn
1268 from being deleted. On the other hand, it does provide something
1269 that can be used to prove that another store is dead. */
1271 = (find_reg_note (insn_info->insn, REG_UNUSED, mem) != NULL);
1273 /* Check whether that value is a suitable memory location. */
1276 /* If the set or clobber is unused, then it does not effect our
1277 ability to get rid of the entire insn. */
1278 if (!store_is_unused)
1279 insn_info->cannot_delete = true;
1283 /* At this point we know mem is a mem. */
1284 if (GET_MODE (mem) == BLKmode)
1286 if (GET_CODE (XEXP (mem, 0)) == SCRATCH)
1289 fprintf (dump_file, " adding wild read for (clobber (mem:BLK (scratch))\n");
1290 add_wild_read (bb_info);
1291 insn_info->cannot_delete = true;
1294 /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
1295 as memset (addr, 0, 36); */
1296 else if (!MEM_SIZE (mem)
1297 || !CONST_INT_P (MEM_SIZE (mem))
1298 || GET_CODE (body) != SET
1299 || INTVAL (MEM_SIZE (mem)) <= 0
1300 || INTVAL (MEM_SIZE (mem)) > MAX_OFFSET
1301 || !CONST_INT_P (SET_SRC (body)))
1303 if (!store_is_unused)
1305 /* If the set or clobber is unused, then it does not effect our
1306 ability to get rid of the entire insn. */
1307 insn_info->cannot_delete = true;
1308 clear_rhs_from_active_local_stores ();
1314 /* We can still process a volatile mem, we just cannot delete it. */
1315 if (MEM_VOLATILE_P (mem))
1316 insn_info->cannot_delete = true;
1318 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
1320 clear_rhs_from_active_local_stores ();
1324 if (GET_MODE (mem) == BLKmode)
1325 width = INTVAL (MEM_SIZE (mem));
1328 width = GET_MODE_SIZE (GET_MODE (mem));
1329 gcc_assert ((unsigned) width <= HOST_BITS_PER_WIDE_INT);
1332 if (spill_alias_set)
1334 bitmap store1 = clear_alias_group->store1_p;
1335 bitmap store2 = clear_alias_group->store2_p;
1337 gcc_assert (GET_MODE (mem) != BLKmode);
1339 if (!bitmap_set_bit (store1, spill_alias_set))
1340 bitmap_set_bit (store2, spill_alias_set);
1342 if (clear_alias_group->offset_map_size_p < spill_alias_set)
1343 clear_alias_group->offset_map_size_p = spill_alias_set;
1345 store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1348 fprintf (dump_file, " processing spill store %d(%s)\n",
1349 (int) spill_alias_set, GET_MODE_NAME (GET_MODE (mem)));
1351 else if (group_id >= 0)
1353 /* In the restrictive case where the base is a constant or the
1354 frame pointer we can do global analysis. */
1357 = VEC_index (group_info_t, rtx_group_vec, group_id);
1359 store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1360 set_usage_bits (group, offset, width);
1363 fprintf (dump_file, " processing const base store gid=%d[%d..%d)\n",
1364 group_id, (int)offset, (int)(offset+width));
1368 rtx base_term = find_base_term (XEXP (mem, 0));
1370 || (GET_CODE (base_term) == ADDRESS
1371 && GET_MODE (base_term) == Pmode
1372 && XEXP (base_term, 0) == stack_pointer_rtx))
1373 insn_info->stack_pointer_based = true;
1374 insn_info->contains_cselib_groups = true;
1376 store_info = (store_info_t) pool_alloc (cse_store_info_pool);
1380 fprintf (dump_file, " processing cselib store [%d..%d)\n",
1381 (int)offset, (int)(offset+width));
1384 const_rhs = rhs = NULL_RTX;
1385 if (GET_CODE (body) == SET
1386 /* No place to keep the value after ra. */
1387 && !reload_completed
1388 && (REG_P (SET_SRC (body))
1389 || GET_CODE (SET_SRC (body)) == SUBREG
1390 || CONSTANT_P (SET_SRC (body)))
1391 && !MEM_VOLATILE_P (mem)
1392 /* Sometimes the store and reload is used for truncation and
1394 && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
1396 rhs = SET_SRC (body);
1397 if (CONSTANT_P (rhs))
1399 else if (body == PATTERN (insn_info->insn))
1401 rtx tem = find_reg_note (insn_info->insn, REG_EQUAL, NULL_RTX);
1402 if (tem && CONSTANT_P (XEXP (tem, 0)))
1403 const_rhs = XEXP (tem, 0);
1405 if (const_rhs == NULL_RTX && REG_P (rhs))
1407 rtx tem = cselib_expand_value_rtx (rhs, scratch, 5);
1409 if (tem && CONSTANT_P (tem))
1414 /* Check to see if this stores causes some other stores to be
1416 ptr = active_local_stores;
1418 redundant_reason = NULL;
1419 mem = canon_rtx (mem);
1420 /* For alias_set != 0 canon_true_dependence should be never called. */
1421 if (spill_alias_set)
1422 mem_addr = NULL_RTX;
1426 mem_addr = base->val_rtx;
1430 = VEC_index (group_info_t, rtx_group_vec, group_id);
1431 mem_addr = group->canon_base_addr;
1434 mem_addr = plus_constant (mem_addr, offset);
1439 insn_info_t next = ptr->next_local_store;
1440 store_info_t s_info = ptr->store_rec;
1443 /* Skip the clobbers. We delete the active insn if this insn
1444 shadows the set. To have been put on the active list, it
1445 has exactly on set. */
1446 while (!s_info->is_set)
1447 s_info = s_info->next;
1449 if (s_info->alias_set != spill_alias_set)
1451 else if (s_info->alias_set)
1453 struct clear_alias_mode_holder *entry
1454 = clear_alias_set_lookup (s_info->alias_set);
1455 /* Generally, spills cannot be processed if and of the
1456 references to the slot have a different mode. But if
1457 we are in the same block and mode is exactly the same
1458 between this store and one before in the same block,
1459 we can still delete it. */
1460 if ((GET_MODE (mem) == GET_MODE (s_info->mem))
1461 && (GET_MODE (mem) == entry->mode))
1464 set_all_positions_unneeded (s_info);
1467 fprintf (dump_file, " trying spill store in insn=%d alias_set=%d\n",
1468 INSN_UID (ptr->insn), (int) s_info->alias_set);
1470 else if ((s_info->group_id == group_id)
1471 && (s_info->cse_base == base))
1475 fprintf (dump_file, " trying store in insn=%d gid=%d[%d..%d)\n",
1476 INSN_UID (ptr->insn), s_info->group_id,
1477 (int)s_info->begin, (int)s_info->end);
1479 /* Even if PTR won't be eliminated as unneeded, if both
1480 PTR and this insn store the same constant value, we might
1481 eliminate this insn instead. */
1482 if (s_info->const_rhs
1484 && offset >= s_info->begin
1485 && offset + width <= s_info->end
1486 && all_positions_needed_p (s_info, offset - s_info->begin,
1489 if (GET_MODE (mem) == BLKmode)
1491 if (GET_MODE (s_info->mem) == BLKmode
1492 && s_info->const_rhs == const_rhs)
1493 redundant_reason = ptr;
1495 else if (s_info->const_rhs == const0_rtx
1496 && const_rhs == const0_rtx)
1497 redundant_reason = ptr;
1502 val = get_stored_val (s_info, GET_MODE (mem),
1503 offset, offset + width,
1504 BLOCK_FOR_INSN (insn_info->insn),
1506 if (get_insns () != NULL)
1509 if (val && rtx_equal_p (val, const_rhs))
1510 redundant_reason = ptr;
1514 for (i = MAX (offset, s_info->begin);
1515 i < offset + width && i < s_info->end;
1517 set_position_unneeded (s_info, i - s_info->begin);
1519 else if (s_info->rhs)
1520 /* Need to see if it is possible for this store to overwrite
1521 the value of store_info. If it is, set the rhs to NULL to
1522 keep it from being used to remove a load. */
1524 if (canon_true_dependence (s_info->mem,
1525 GET_MODE (s_info->mem),
1527 mem, mem_addr, rtx_varies_p))
1530 s_info->const_rhs = NULL;
1534 /* An insn can be deleted if every position of every one of
1535 its s_infos is zero. */
1536 if (any_positions_needed_p (s_info))
1541 insn_info_t insn_to_delete = ptr;
1543 active_local_stores_len--;
1545 last->next_local_store = ptr->next_local_store;
1547 active_local_stores = ptr->next_local_store;
1549 if (!insn_to_delete->cannot_delete)
1550 delete_dead_store_insn (insn_to_delete);
1558 /* Finish filling in the store_info. */
1559 store_info->next = insn_info->store_rec;
1560 insn_info->store_rec = store_info;
1561 store_info->mem = mem;
1562 store_info->alias_set = spill_alias_set;
1563 store_info->mem_addr = mem_addr;
1564 store_info->cse_base = base;
1565 if (width > HOST_BITS_PER_WIDE_INT)
1567 store_info->is_large = true;
1568 store_info->positions_needed.large.count = 0;
1569 store_info->positions_needed.large.bmap = BITMAP_ALLOC (NULL);
1573 store_info->is_large = false;
1574 store_info->positions_needed.small_bitmask = lowpart_bitmask (width);
1576 store_info->group_id = group_id;
1577 store_info->begin = offset;
1578 store_info->end = offset + width;
1579 store_info->is_set = GET_CODE (body) == SET;
1580 store_info->rhs = rhs;
1581 store_info->const_rhs = const_rhs;
1582 store_info->redundant_reason = redundant_reason;
1584 /* If this is a clobber, we return 0. We will only be able to
1585 delete this insn if there is only one store USED store, but we
1586 can use the clobber to delete other stores earlier. */
1587 return store_info->is_set ? 1 : 0;
1592 dump_insn_info (const char * start, insn_info_t insn_info)
1594 fprintf (dump_file, "%s insn=%d %s\n", start,
1595 INSN_UID (insn_info->insn),
1596 insn_info->store_rec ? "has store" : "naked");
1600 /* If the modes are different and the value's source and target do not
1601 line up, we need to extract the value from lower part of the rhs of
1602 the store, shift it, and then put it into a form that can be shoved
1603 into the read_insn. This function generates a right SHIFT of a
1604 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The
1605 shift sequence is returned or NULL if we failed to find a
1609 find_shift_sequence (int access_size,
1610 store_info_t store_info,
1611 enum machine_mode read_mode,
1612 int shift, bool speed, bool require_cst)
1614 enum machine_mode store_mode = GET_MODE (store_info->mem);
1615 enum machine_mode new_mode;
1616 rtx read_reg = NULL;
1618 /* Some machines like the x86 have shift insns for each size of
1619 operand. Other machines like the ppc or the ia-64 may only have
1620 shift insns that shift values within 32 or 64 bit registers.
1621 This loop tries to find the smallest shift insn that will right
1622 justify the value we want to read but is available in one insn on
1625 for (new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
1627 GET_MODE_BITSIZE (new_mode) <= BITS_PER_WORD;
1628 new_mode = GET_MODE_WIDER_MODE (new_mode))
1630 rtx target, new_reg, shift_seq, insn, new_lhs;
1633 /* If a constant was stored into memory, try to simplify it here,
1634 otherwise the cost of the shift might preclude this optimization
1635 e.g. at -Os, even when no actual shift will be needed. */
1636 if (store_info->const_rhs)
1638 unsigned int byte = subreg_lowpart_offset (new_mode, store_mode);
1639 rtx ret = simplify_subreg (new_mode, store_info->const_rhs,
1641 if (ret && CONSTANT_P (ret))
1643 ret = simplify_const_binary_operation (LSHIFTRT, new_mode,
1644 ret, GEN_INT (shift));
1645 if (ret && CONSTANT_P (ret))
1647 byte = subreg_lowpart_offset (read_mode, new_mode);
1648 ret = simplify_subreg (read_mode, ret, new_mode, byte);
1649 if (ret && CONSTANT_P (ret)
1650 && rtx_cost (ret, SET, speed) <= COSTS_N_INSNS (1))
1659 /* Try a wider mode if truncating the store mode to NEW_MODE
1660 requires a real instruction. */
1661 if (GET_MODE_BITSIZE (new_mode) < GET_MODE_BITSIZE (store_mode)
1662 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (new_mode),
1663 GET_MODE_BITSIZE (store_mode)))
1666 /* Also try a wider mode if the necessary punning is either not
1667 desirable or not possible. */
1668 if (!CONSTANT_P (store_info->rhs)
1669 && !MODES_TIEABLE_P (new_mode, store_mode))
1672 new_reg = gen_reg_rtx (new_mode);
1676 /* In theory we could also check for an ashr. Ian Taylor knows
1677 of one dsp where the cost of these two was not the same. But
1678 this really is a rare case anyway. */
1679 target = expand_binop (new_mode, lshr_optab, new_reg,
1680 GEN_INT (shift), new_reg, 1, OPTAB_DIRECT);
1682 shift_seq = get_insns ();
1685 if (target != new_reg || shift_seq == NULL)
1689 for (insn = shift_seq; insn != NULL_RTX; insn = NEXT_INSN (insn))
1691 cost += insn_rtx_cost (PATTERN (insn), speed);
1693 /* The computation up to here is essentially independent
1694 of the arguments and could be precomputed. It may
1695 not be worth doing so. We could precompute if
1696 worthwhile or at least cache the results. The result
1697 technically depends on both SHIFT and ACCESS_SIZE,
1698 but in practice the answer will depend only on ACCESS_SIZE. */
1700 if (cost > COSTS_N_INSNS (1))
1703 new_lhs = extract_low_bits (new_mode, store_mode,
1704 copy_rtx (store_info->rhs));
1705 if (new_lhs == NULL_RTX)
1708 /* We found an acceptable shift. Generate a move to
1709 take the value from the store and put it into the
1710 shift pseudo, then shift it, then generate another
1711 move to put in into the target of the read. */
1712 emit_move_insn (new_reg, new_lhs);
1713 emit_insn (shift_seq);
1714 read_reg = extract_low_bits (read_mode, new_mode, new_reg);
1722 /* Call back for note_stores to find the hard regs set or clobbered by
1723 insn. Data is a bitmap of the hardregs set so far. */
1726 look_for_hardregs (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
1728 bitmap regs_set = (bitmap) data;
1731 && REGNO (x) < FIRST_PSEUDO_REGISTER)
1733 int regno = REGNO (x);
1734 int n = hard_regno_nregs[regno][GET_MODE (x)];
1736 bitmap_set_bit (regs_set, regno + n);
1740 /* Helper function for replace_read and record_store.
1741 Attempt to return a value stored in STORE_INFO, from READ_BEGIN
1742 to one before READ_END bytes read in READ_MODE. Return NULL
1743 if not successful. If REQUIRE_CST is true, return always constant. */
1746 get_stored_val (store_info_t store_info, enum machine_mode read_mode,
1747 HOST_WIDE_INT read_begin, HOST_WIDE_INT read_end,
1748 basic_block bb, bool require_cst)
1750 enum machine_mode store_mode = GET_MODE (store_info->mem);
1752 int access_size; /* In bytes. */
1755 /* To get here the read is within the boundaries of the write so
1756 shift will never be negative. Start out with the shift being in
1758 if (store_mode == BLKmode)
1760 else if (BYTES_BIG_ENDIAN)
1761 shift = store_info->end - read_end;
1763 shift = read_begin - store_info->begin;
1765 access_size = shift + GET_MODE_SIZE (read_mode);
1767 /* From now on it is bits. */
1768 shift *= BITS_PER_UNIT;
1771 read_reg = find_shift_sequence (access_size, store_info, read_mode, shift,
1772 optimize_bb_for_speed_p (bb),
1774 else if (store_mode == BLKmode)
1776 /* The store is a memset (addr, const_val, const_size). */
1777 gcc_assert (CONST_INT_P (store_info->rhs));
1778 store_mode = int_mode_for_mode (read_mode);
1779 if (store_mode == BLKmode)
1780 read_reg = NULL_RTX;
1781 else if (store_info->rhs == const0_rtx)
1782 read_reg = extract_low_bits (read_mode, store_mode, const0_rtx);
1783 else if (GET_MODE_BITSIZE (store_mode) > HOST_BITS_PER_WIDE_INT
1784 || BITS_PER_UNIT >= HOST_BITS_PER_WIDE_INT)
1785 read_reg = NULL_RTX;
1788 unsigned HOST_WIDE_INT c
1789 = INTVAL (store_info->rhs)
1790 & (((HOST_WIDE_INT) 1 << BITS_PER_UNIT) - 1);
1791 int shift = BITS_PER_UNIT;
1792 while (shift < HOST_BITS_PER_WIDE_INT)
1797 read_reg = GEN_INT (trunc_int_for_mode (c, store_mode));
1798 read_reg = extract_low_bits (read_mode, store_mode, read_reg);
1801 else if (store_info->const_rhs
1803 || GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode)))
1804 read_reg = extract_low_bits (read_mode, store_mode,
1805 copy_rtx (store_info->const_rhs));
1807 read_reg = extract_low_bits (read_mode, store_mode,
1808 copy_rtx (store_info->rhs));
1809 if (require_cst && read_reg && !CONSTANT_P (read_reg))
1810 read_reg = NULL_RTX;
1814 /* Take a sequence of:
1837 Depending on the alignment and the mode of the store and
1841 The STORE_INFO and STORE_INSN are for the store and READ_INFO
1842 and READ_INSN are for the read. Return true if the replacement
1846 replace_read (store_info_t store_info, insn_info_t store_insn,
1847 read_info_t read_info, insn_info_t read_insn, rtx *loc,
1850 enum machine_mode store_mode = GET_MODE (store_info->mem);
1851 enum machine_mode read_mode = GET_MODE (read_info->mem);
1852 rtx insns, this_insn, read_reg;
1858 /* Create a sequence of instructions to set up the read register.
1859 This sequence goes immediately before the store and its result
1860 is read by the load.
1862 We need to keep this in perspective. We are replacing a read
1863 with a sequence of insns, but the read will almost certainly be
1864 in cache, so it is not going to be an expensive one. Thus, we
1865 are not willing to do a multi insn shift or worse a subroutine
1866 call to get rid of the read. */
1868 fprintf (dump_file, "trying to replace %smode load in insn %d"
1869 " from %smode store in insn %d\n",
1870 GET_MODE_NAME (read_mode), INSN_UID (read_insn->insn),
1871 GET_MODE_NAME (store_mode), INSN_UID (store_insn->insn));
1873 bb = BLOCK_FOR_INSN (read_insn->insn);
1874 read_reg = get_stored_val (store_info,
1875 read_mode, read_info->begin, read_info->end,
1877 if (read_reg == NULL_RTX)
1881 fprintf (dump_file, " -- could not extract bits of stored value\n");
1884 /* Force the value into a new register so that it won't be clobbered
1885 between the store and the load. */
1886 read_reg = copy_to_mode_reg (read_mode, read_reg);
1887 insns = get_insns ();
1890 if (insns != NULL_RTX)
1892 /* Now we have to scan the set of new instructions to see if the
1893 sequence contains and sets of hardregs that happened to be
1894 live at this point. For instance, this can happen if one of
1895 the insns sets the CC and the CC happened to be live at that
1896 point. This does occasionally happen, see PR 37922. */
1897 bitmap regs_set = BITMAP_ALLOC (NULL);
1899 for (this_insn = insns; this_insn != NULL_RTX; this_insn = NEXT_INSN (this_insn))
1900 note_stores (PATTERN (this_insn), look_for_hardregs, regs_set);
1902 bitmap_and_into (regs_set, regs_live);
1903 if (!bitmap_empty_p (regs_set))
1908 "abandoning replacement because sequence clobbers live hardregs:");
1909 df_print_regset (dump_file, regs_set);
1912 BITMAP_FREE (regs_set);
1915 BITMAP_FREE (regs_set);
1918 if (validate_change (read_insn->insn, loc, read_reg, 0))
1920 deferred_change_t deferred_change =
1921 (deferred_change_t) pool_alloc (deferred_change_pool);
1923 /* Insert this right before the store insn where it will be safe
1924 from later insns that might change it before the read. */
1925 emit_insn_before (insns, store_insn->insn);
1927 /* And now for the kludge part: cselib croaks if you just
1928 return at this point. There are two reasons for this:
1930 1) Cselib has an idea of how many pseudos there are and
1931 that does not include the new ones we just added.
1933 2) Cselib does not know about the move insn we added
1934 above the store_info, and there is no way to tell it
1935 about it, because it has "moved on".
1937 Problem (1) is fixable with a certain amount of engineering.
1938 Problem (2) is requires starting the bb from scratch. This
1941 So we are just going to have to lie. The move/extraction
1942 insns are not really an issue, cselib did not see them. But
1943 the use of the new pseudo read_insn is a real problem because
1944 cselib has not scanned this insn. The way that we solve this
1945 problem is that we are just going to put the mem back for now
1946 and when we are finished with the block, we undo this. We
1947 keep a table of mems to get rid of. At the end of the basic
1948 block we can put them back. */
1950 *loc = read_info->mem;
1951 deferred_change->next = deferred_change_list;
1952 deferred_change_list = deferred_change;
1953 deferred_change->loc = loc;
1954 deferred_change->reg = read_reg;
1956 /* Get rid of the read_info, from the point of view of the
1957 rest of dse, play like this read never happened. */
1958 read_insn->read_rec = read_info->next;
1959 pool_free (read_info_pool, read_info);
1962 fprintf (dump_file, " -- replaced the loaded MEM with ");
1963 print_simple_rtl (dump_file, read_reg);
1964 fprintf (dump_file, "\n");
1972 fprintf (dump_file, " -- replacing the loaded MEM with ");
1973 print_simple_rtl (dump_file, read_reg);
1974 fprintf (dump_file, " led to an invalid instruction\n");
1980 /* A for_each_rtx callback in which DATA is the bb_info. Check to see
1981 if LOC is a mem and if it is look at the address and kill any
1982 appropriate stores that may be active. */
1985 check_mem_read_rtx (rtx *loc, void *data)
1987 rtx mem = *loc, mem_addr;
1989 insn_info_t insn_info;
1990 HOST_WIDE_INT offset = 0;
1991 HOST_WIDE_INT width = 0;
1992 alias_set_type spill_alias_set = 0;
1993 cselib_val *base = NULL;
1995 read_info_t read_info;
1997 if (!mem || !MEM_P (mem))
2000 bb_info = (bb_info_t) data;
2001 insn_info = bb_info->last_insn;
2003 if ((MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2004 || (MEM_VOLATILE_P (mem)))
2007 fprintf (dump_file, " adding wild read, volatile or barrier.\n");
2008 add_wild_read (bb_info);
2009 insn_info->cannot_delete = true;
2013 /* If it is reading readonly mem, then there can be no conflict with
2015 if (MEM_READONLY_P (mem))
2018 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
2021 fprintf (dump_file, " adding wild read, canon_address failure.\n");
2022 add_wild_read (bb_info);
2026 if (GET_MODE (mem) == BLKmode)
2029 width = GET_MODE_SIZE (GET_MODE (mem));
2031 read_info = (read_info_t) pool_alloc (read_info_pool);
2032 read_info->group_id = group_id;
2033 read_info->mem = mem;
2034 read_info->alias_set = spill_alias_set;
2035 read_info->begin = offset;
2036 read_info->end = offset + width;
2037 read_info->next = insn_info->read_rec;
2038 insn_info->read_rec = read_info;
2039 /* For alias_set != 0 canon_true_dependence should be never called. */
2040 if (spill_alias_set)
2041 mem_addr = NULL_RTX;
2045 mem_addr = base->val_rtx;
2049 = VEC_index (group_info_t, rtx_group_vec, group_id);
2050 mem_addr = group->canon_base_addr;
2053 mem_addr = plus_constant (mem_addr, offset);
2056 /* We ignore the clobbers in store_info. The is mildly aggressive,
2057 but there really should not be a clobber followed by a read. */
2059 if (spill_alias_set)
2061 insn_info_t i_ptr = active_local_stores;
2062 insn_info_t last = NULL;
2065 fprintf (dump_file, " processing spill load %d\n",
2066 (int) spill_alias_set);
2070 store_info_t store_info = i_ptr->store_rec;
2072 /* Skip the clobbers. */
2073 while (!store_info->is_set)
2074 store_info = store_info->next;
2076 if (store_info->alias_set == spill_alias_set)
2079 dump_insn_info ("removing from active", i_ptr);
2081 active_local_stores_len--;
2083 last->next_local_store = i_ptr->next_local_store;
2085 active_local_stores = i_ptr->next_local_store;
2089 i_ptr = i_ptr->next_local_store;
2092 else if (group_id >= 0)
2094 /* This is the restricted case where the base is a constant or
2095 the frame pointer and offset is a constant. */
2096 insn_info_t i_ptr = active_local_stores;
2097 insn_info_t last = NULL;
2102 fprintf (dump_file, " processing const load gid=%d[BLK]\n",
2105 fprintf (dump_file, " processing const load gid=%d[%d..%d)\n",
2106 group_id, (int)offset, (int)(offset+width));
2111 bool remove = false;
2112 store_info_t store_info = i_ptr->store_rec;
2114 /* Skip the clobbers. */
2115 while (!store_info->is_set)
2116 store_info = store_info->next;
2118 /* There are three cases here. */
2119 if (store_info->group_id < 0)
2120 /* We have a cselib store followed by a read from a
2123 = canon_true_dependence (store_info->mem,
2124 GET_MODE (store_info->mem),
2125 store_info->mem_addr,
2126 mem, mem_addr, rtx_varies_p);
2128 else if (group_id == store_info->group_id)
2130 /* This is a block mode load. We may get lucky and
2131 canon_true_dependence may save the day. */
2134 = canon_true_dependence (store_info->mem,
2135 GET_MODE (store_info->mem),
2136 store_info->mem_addr,
2137 mem, mem_addr, rtx_varies_p);
2139 /* If this read is just reading back something that we just
2140 stored, rewrite the read. */
2144 && offset >= store_info->begin
2145 && offset + width <= store_info->end
2146 && all_positions_needed_p (store_info,
2147 offset - store_info->begin,
2149 && replace_read (store_info, i_ptr, read_info,
2150 insn_info, loc, bb_info->regs_live))
2153 /* The bases are the same, just see if the offsets
2155 if ((offset < store_info->end)
2156 && (offset + width > store_info->begin))
2162 The else case that is missing here is that the
2163 bases are constant but different. There is nothing
2164 to do here because there is no overlap. */
2169 dump_insn_info ("removing from active", i_ptr);
2171 active_local_stores_len--;
2173 last->next_local_store = i_ptr->next_local_store;
2175 active_local_stores = i_ptr->next_local_store;
2179 i_ptr = i_ptr->next_local_store;
2184 insn_info_t i_ptr = active_local_stores;
2185 insn_info_t last = NULL;
2188 fprintf (dump_file, " processing cselib load mem:");
2189 print_inline_rtx (dump_file, mem, 0);
2190 fprintf (dump_file, "\n");
2195 bool remove = false;
2196 store_info_t store_info = i_ptr->store_rec;
2199 fprintf (dump_file, " processing cselib load against insn %d\n",
2200 INSN_UID (i_ptr->insn));
2202 /* Skip the clobbers. */
2203 while (!store_info->is_set)
2204 store_info = store_info->next;
2206 /* If this read is just reading back something that we just
2207 stored, rewrite the read. */
2209 && store_info->group_id == -1
2210 && store_info->cse_base == base
2212 && offset >= store_info->begin
2213 && offset + width <= store_info->end
2214 && all_positions_needed_p (store_info,
2215 offset - store_info->begin, width)
2216 && replace_read (store_info, i_ptr, read_info, insn_info, loc,
2217 bb_info->regs_live))
2220 if (!store_info->alias_set)
2221 remove = canon_true_dependence (store_info->mem,
2222 GET_MODE (store_info->mem),
2223 store_info->mem_addr,
2224 mem, mem_addr, rtx_varies_p);
2229 dump_insn_info ("removing from active", i_ptr);
2231 active_local_stores_len--;
2233 last->next_local_store = i_ptr->next_local_store;
2235 active_local_stores = i_ptr->next_local_store;
2239 i_ptr = i_ptr->next_local_store;
2245 /* A for_each_rtx callback in which DATA points the INSN_INFO for
2246 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
2247 true for any part of *LOC. */
2250 check_mem_read_use (rtx *loc, void *data)
2252 for_each_rtx (loc, check_mem_read_rtx, data);
2256 /* Get arguments passed to CALL_INSN. Return TRUE if successful.
2257 So far it only handles arguments passed in registers. */
2260 get_call_args (rtx call_insn, tree fn, rtx *args, int nargs)
2262 CUMULATIVE_ARGS args_so_far;
2266 INIT_CUMULATIVE_ARGS (args_so_far, TREE_TYPE (fn), NULL_RTX, 0, 3);
2268 arg = TYPE_ARG_TYPES (TREE_TYPE (fn));
2270 arg != void_list_node && idx < nargs;
2271 arg = TREE_CHAIN (arg), idx++)
2273 enum machine_mode mode = TYPE_MODE (TREE_VALUE (arg));
2275 reg = targetm.calls.function_arg (&args_so_far, mode, NULL_TREE, true);
2276 if (!reg || !REG_P (reg) || GET_MODE (reg) != mode
2277 || GET_MODE_CLASS (mode) != MODE_INT)
2280 for (link = CALL_INSN_FUNCTION_USAGE (call_insn);
2282 link = XEXP (link, 1))
2283 if (GET_CODE (XEXP (link, 0)) == USE)
2285 args[idx] = XEXP (XEXP (link, 0), 0);
2286 if (REG_P (args[idx])
2287 && REGNO (args[idx]) == REGNO (reg)
2288 && (GET_MODE (args[idx]) == mode
2289 || (GET_MODE_CLASS (GET_MODE (args[idx])) == MODE_INT
2290 && (GET_MODE_SIZE (GET_MODE (args[idx]))
2292 && (GET_MODE_SIZE (GET_MODE (args[idx]))
2293 > GET_MODE_SIZE (mode)))))
2299 tmp = cselib_expand_value_rtx (args[idx], scratch, 5);
2300 if (GET_MODE (args[idx]) != mode)
2302 if (!tmp || !CONST_INT_P (tmp))
2304 tmp = GEN_INT (trunc_int_for_mode (INTVAL (tmp), mode));
2309 targetm.calls.function_arg_advance (&args_so_far, mode, NULL_TREE, true);
2311 if (arg != void_list_node || idx != nargs)
2317 /* Apply record_store to all candidate stores in INSN. Mark INSN
2318 if some part of it is not a candidate store and assigns to a
2319 non-register target. */
2322 scan_insn (bb_info_t bb_info, rtx insn)
2325 insn_info_t insn_info = (insn_info_t) pool_alloc (insn_info_pool);
2327 memset (insn_info, 0, sizeof (struct insn_info));
2330 fprintf (dump_file, "\n**scanning insn=%d\n",
2333 insn_info->prev_insn = bb_info->last_insn;
2334 insn_info->insn = insn;
2335 bb_info->last_insn = insn_info;
2337 if (DEBUG_INSN_P (insn))
2339 insn_info->cannot_delete = true;
2343 /* Cselib clears the table for this case, so we have to essentially
2345 if (NONJUMP_INSN_P (insn)
2346 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
2347 && MEM_VOLATILE_P (PATTERN (insn)))
2349 add_wild_read (bb_info);
2350 insn_info->cannot_delete = true;
2354 /* Look at all of the uses in the insn. */
2355 note_uses (&PATTERN (insn), check_mem_read_use, bb_info);
2360 tree memset_call = NULL_TREE;
2362 insn_info->cannot_delete = true;
2364 /* Const functions cannot do anything bad i.e. read memory,
2365 however, they can read their parameters which may have
2366 been pushed onto the stack.
2367 memset and bzero don't read memory either. */
2368 const_call = RTL_CONST_CALL_P (insn);
2371 rtx call = PATTERN (insn);
2372 if (GET_CODE (call) == PARALLEL)
2373 call = XVECEXP (call, 0, 0);
2374 if (GET_CODE (call) == SET)
2375 call = SET_SRC (call);
2376 if (GET_CODE (call) == CALL
2377 && MEM_P (XEXP (call, 0))
2378 && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
2380 rtx symbol = XEXP (XEXP (call, 0), 0);
2381 if (SYMBOL_REF_DECL (symbol)
2382 && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
2384 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
2386 && (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))
2387 == BUILT_IN_MEMSET))
2388 || SYMBOL_REF_DECL (symbol) == block_clear_fn)
2389 memset_call = SYMBOL_REF_DECL (symbol);
2393 if (const_call || memset_call)
2395 insn_info_t i_ptr = active_local_stores;
2396 insn_info_t last = NULL;
2399 fprintf (dump_file, "%s call %d\n",
2400 const_call ? "const" : "memset", INSN_UID (insn));
2402 /* See the head comment of the frame_read field. */
2403 if (reload_completed)
2404 insn_info->frame_read = true;
2406 /* Loop over the active stores and remove those which are
2407 killed by the const function call. */
2410 bool remove_store = false;
2412 /* The stack pointer based stores are always killed. */
2413 if (i_ptr->stack_pointer_based)
2414 remove_store = true;
2416 /* If the frame is read, the frame related stores are killed. */
2417 else if (insn_info->frame_read)
2419 store_info_t store_info = i_ptr->store_rec;
2421 /* Skip the clobbers. */
2422 while (!store_info->is_set)
2423 store_info = store_info->next;
2425 if (store_info->group_id >= 0
2426 && VEC_index (group_info_t, rtx_group_vec,
2427 store_info->group_id)->frame_related)
2428 remove_store = true;
2434 dump_insn_info ("removing from active", i_ptr);
2436 active_local_stores_len--;
2438 last->next_local_store = i_ptr->next_local_store;
2440 active_local_stores = i_ptr->next_local_store;
2445 i_ptr = i_ptr->next_local_store;
2451 if (get_call_args (insn, memset_call, args, 3)
2452 && CONST_INT_P (args[1])
2453 && CONST_INT_P (args[2])
2454 && INTVAL (args[2]) > 0)
2456 rtx mem = gen_rtx_MEM (BLKmode, args[0]);
2457 set_mem_size (mem, args[2]);
2458 body = gen_rtx_SET (VOIDmode, mem, args[1]);
2459 mems_found += record_store (body, bb_info);
2461 fprintf (dump_file, "handling memset as BLKmode store\n");
2462 if (mems_found == 1)
2464 if (active_local_stores_len++
2465 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES))
2467 active_local_stores_len = 1;
2468 active_local_stores = NULL;
2470 insn_info->next_local_store = active_local_stores;
2471 active_local_stores = insn_info;
2478 /* Every other call, including pure functions, may read memory. */
2479 add_wild_read (bb_info);
2484 /* Assuming that there are sets in these insns, we cannot delete
2486 if ((GET_CODE (PATTERN (insn)) == CLOBBER)
2487 || volatile_refs_p (PATTERN (insn))
2488 || insn_could_throw_p (insn)
2489 || (RTX_FRAME_RELATED_P (insn))
2490 || find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX))
2491 insn_info->cannot_delete = true;
2493 body = PATTERN (insn);
2494 if (GET_CODE (body) == PARALLEL)
2497 for (i = 0; i < XVECLEN (body, 0); i++)
2498 mems_found += record_store (XVECEXP (body, 0, i), bb_info);
2501 mems_found += record_store (body, bb_info);
2504 fprintf (dump_file, "mems_found = %d, cannot_delete = %s\n",
2505 mems_found, insn_info->cannot_delete ? "true" : "false");
2507 /* If we found some sets of mems, add it into the active_local_stores so
2508 that it can be locally deleted if found dead or used for
2509 replace_read and redundant constant store elimination. Otherwise mark
2510 it as cannot delete. This simplifies the processing later. */
2511 if (mems_found == 1)
2513 if (active_local_stores_len++
2514 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES))
2516 active_local_stores_len = 1;
2517 active_local_stores = NULL;
2519 insn_info->next_local_store = active_local_stores;
2520 active_local_stores = insn_info;
2523 insn_info->cannot_delete = true;
2527 /* Remove BASE from the set of active_local_stores. This is a
2528 callback from cselib that is used to get rid of the stores in
2529 active_local_stores. */
2532 remove_useless_values (cselib_val *base)
2534 insn_info_t insn_info = active_local_stores;
2535 insn_info_t last = NULL;
2539 store_info_t store_info = insn_info->store_rec;
2542 /* If ANY of the store_infos match the cselib group that is
2543 being deleted, then the insn can not be deleted. */
2546 if ((store_info->group_id == -1)
2547 && (store_info->cse_base == base))
2552 store_info = store_info->next;
2557 active_local_stores_len--;
2559 last->next_local_store = insn_info->next_local_store;
2561 active_local_stores = insn_info->next_local_store;
2562 free_store_info (insn_info);
2567 insn_info = insn_info->next_local_store;
2572 /* Do all of step 1. */
2578 bitmap regs_live = BITMAP_ALLOC (NULL);
2581 all_blocks = BITMAP_ALLOC (NULL);
2582 bitmap_set_bit (all_blocks, ENTRY_BLOCK);
2583 bitmap_set_bit (all_blocks, EXIT_BLOCK);
2588 bb_info_t bb_info = (bb_info_t) pool_alloc (bb_info_pool);
2590 memset (bb_info, 0, sizeof (struct bb_info));
2591 bitmap_set_bit (all_blocks, bb->index);
2592 bb_info->regs_live = regs_live;
2594 bitmap_copy (regs_live, DF_LR_IN (bb));
2595 df_simulate_initialize_forwards (bb, regs_live);
2597 bb_table[bb->index] = bb_info;
2598 cselib_discard_hook = remove_useless_values;
2600 if (bb->index >= NUM_FIXED_BLOCKS)
2605 = create_alloc_pool ("cse_store_info_pool",
2606 sizeof (struct store_info), 100);
2607 active_local_stores = NULL;
2608 active_local_stores_len = 0;
2609 cselib_clear_table ();
2611 /* Scan the insns. */
2612 FOR_BB_INSNS (bb, insn)
2615 scan_insn (bb_info, insn);
2616 cselib_process_insn (insn);
2618 df_simulate_one_insn_forwards (bb, insn, regs_live);
2621 /* This is something of a hack, because the global algorithm
2622 is supposed to take care of the case where stores go dead
2623 at the end of the function. However, the global
2624 algorithm must take a more conservative view of block
2625 mode reads than the local alg does. So to get the case
2626 where you have a store to the frame followed by a non
2627 overlapping block more read, we look at the active local
2628 stores at the end of the function and delete all of the
2629 frame and spill based ones. */
2630 if (stores_off_frame_dead_at_return
2631 && (EDGE_COUNT (bb->succs) == 0
2632 || (single_succ_p (bb)
2633 && single_succ (bb) == EXIT_BLOCK_PTR
2634 && ! crtl->calls_eh_return)))
2636 insn_info_t i_ptr = active_local_stores;
2639 store_info_t store_info = i_ptr->store_rec;
2641 /* Skip the clobbers. */
2642 while (!store_info->is_set)
2643 store_info = store_info->next;
2644 if (store_info->alias_set && !i_ptr->cannot_delete)
2645 delete_dead_store_insn (i_ptr);
2647 if (store_info->group_id >= 0)
2650 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
2651 if (group->frame_related && !i_ptr->cannot_delete)
2652 delete_dead_store_insn (i_ptr);
2655 i_ptr = i_ptr->next_local_store;
2659 /* Get rid of the loads that were discovered in
2660 replace_read. Cselib is finished with this block. */
2661 while (deferred_change_list)
2663 deferred_change_t next = deferred_change_list->next;
2665 /* There is no reason to validate this change. That was
2667 *deferred_change_list->loc = deferred_change_list->reg;
2668 pool_free (deferred_change_pool, deferred_change_list);
2669 deferred_change_list = next;
2672 /* Get rid of all of the cselib based store_infos in this
2673 block and mark the containing insns as not being
2675 ptr = bb_info->last_insn;
2678 if (ptr->contains_cselib_groups)
2680 store_info_t s_info = ptr->store_rec;
2681 while (s_info && !s_info->is_set)
2682 s_info = s_info->next;
2684 && s_info->redundant_reason
2685 && s_info->redundant_reason->insn
2686 && !ptr->cannot_delete)
2689 fprintf (dump_file, "Locally deleting insn %d "
2690 "because insn %d stores the "
2691 "same value and couldn't be "
2693 INSN_UID (ptr->insn),
2694 INSN_UID (s_info->redundant_reason->insn));
2695 delete_dead_store_insn (ptr);
2698 s_info->redundant_reason = NULL;
2699 free_store_info (ptr);
2703 store_info_t s_info;
2705 /* Free at least positions_needed bitmaps. */
2706 for (s_info = ptr->store_rec; s_info; s_info = s_info->next)
2707 if (s_info->is_large)
2709 BITMAP_FREE (s_info->positions_needed.large.bmap);
2710 s_info->is_large = false;
2713 ptr = ptr->prev_insn;
2716 free_alloc_pool (cse_store_info_pool);
2718 bb_info->regs_live = NULL;
2721 BITMAP_FREE (regs_live);
2723 htab_empty (rtx_group_table);
2727 /*----------------------------------------------------------------------------
2730 Assign each byte position in the stores that we are going to
2731 analyze globally to a position in the bitmaps. Returns true if
2732 there are any bit positions assigned.
2733 ----------------------------------------------------------------------------*/
2736 dse_step2_init (void)
2741 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
2743 /* For all non stack related bases, we only consider a store to
2744 be deletable if there are two or more stores for that
2745 position. This is because it takes one store to make the
2746 other store redundant. However, for the stores that are
2747 stack related, we consider them if there is only one store
2748 for the position. We do this because the stack related
2749 stores can be deleted if their is no read between them and
2750 the end of the function.
2752 To make this work in the current framework, we take the stack
2753 related bases add all of the bits from store1 into store2.
2754 This has the effect of making the eligible even if there is
2757 if (stores_off_frame_dead_at_return && group->frame_related)
2759 bitmap_ior_into (group->store2_n, group->store1_n);
2760 bitmap_ior_into (group->store2_p, group->store1_p);
2762 fprintf (dump_file, "group %d is frame related ", i);
2765 group->offset_map_size_n++;
2766 group->offset_map_n = XNEWVEC (int, group->offset_map_size_n);
2767 group->offset_map_size_p++;
2768 group->offset_map_p = XNEWVEC (int, group->offset_map_size_p);
2769 group->process_globally = false;
2772 fprintf (dump_file, "group %d(%d+%d): ", i,
2773 (int)bitmap_count_bits (group->store2_n),
2774 (int)bitmap_count_bits (group->store2_p));
2775 bitmap_print (dump_file, group->store2_n, "n ", " ");
2776 bitmap_print (dump_file, group->store2_p, "p ", "\n");
2782 /* Init the offset tables for the normal case. */
2785 dse_step2_nospill (void)
2789 /* Position 0 is unused because 0 is used in the maps to mean
2791 current_position = 1;
2793 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
2798 if (group == clear_alias_group)
2801 memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2802 memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2803 bitmap_clear (group->group_kill);
2805 EXECUTE_IF_SET_IN_BITMAP (group->store2_n, 0, j, bi)
2807 bitmap_set_bit (group->group_kill, current_position);
2808 group->offset_map_n[j] = current_position++;
2809 group->process_globally = true;
2811 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2813 bitmap_set_bit (group->group_kill, current_position);
2814 group->offset_map_p[j] = current_position++;
2815 group->process_globally = true;
2818 return current_position != 1;
2822 /* Init the offset tables for the spill case. */
2825 dse_step2_spill (void)
2828 group_info_t group = clear_alias_group;
2831 /* Position 0 is unused because 0 is used in the maps to mean
2833 current_position = 1;
2837 bitmap_print (dump_file, clear_alias_sets,
2838 "clear alias sets ", "\n");
2839 bitmap_print (dump_file, disqualified_clear_alias_sets,
2840 "disqualified clear alias sets ", "\n");
2843 memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2844 memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2845 bitmap_clear (group->group_kill);
2847 /* Remove the disqualified positions from the store2_p set. */
2848 bitmap_and_compl_into (group->store2_p, disqualified_clear_alias_sets);
2850 /* We do not need to process the store2_n set because
2851 alias_sets are always positive. */
2852 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2854 bitmap_set_bit (group->group_kill, current_position);
2855 group->offset_map_p[j] = current_position++;
2856 group->process_globally = true;
2859 return current_position != 1;
2864 /*----------------------------------------------------------------------------
2867 Build the bit vectors for the transfer functions.
2868 ----------------------------------------------------------------------------*/
2871 /* Note that this is NOT a general purpose function. Any mem that has
2872 an alias set registered here expected to be COMPLETELY unaliased:
2873 i.e it's addresses are not and need not be examined.
2875 It is known that all references to this address will have this
2876 alias set and there are NO other references to this address in the
2879 Currently the only place that is known to be clean enough to use
2880 this interface is the code that assigns the spill locations.
2882 All of the mems that have alias_sets registered are subjected to a
2883 very powerful form of dse where function calls, volatile reads and
2884 writes, and reads from random location are not taken into account.
2886 It is also assumed that these locations go dead when the function
2887 returns. This assumption could be relaxed if there were found to
2888 be places that this assumption was not correct.
2890 The MODE is passed in and saved. The mode of each load or store to
2891 a mem with ALIAS_SET is checked against MEM. If the size of that
2892 load or store is different from MODE, processing is halted on this
2893 alias set. For the vast majority of aliases sets, all of the loads
2894 and stores will use the same mode. But vectors are treated
2895 differently: the alias set is established for the entire vector,
2896 but reload will insert loads and stores for individual elements and
2897 we do not necessarily have the information to track those separate
2898 elements. So when we see a mode mismatch, we just bail. */
2902 dse_record_singleton_alias_set (alias_set_type alias_set,
2903 enum machine_mode mode)
2905 struct clear_alias_mode_holder tmp_holder;
2906 struct clear_alias_mode_holder *entry;
2909 /* If we are not going to run dse, we need to return now or there
2910 will be problems with allocating the bitmaps. */
2911 if ((!gate_dse()) || !alias_set)
2914 if (!clear_alias_sets)
2916 clear_alias_sets = BITMAP_ALLOC (NULL);
2917 disqualified_clear_alias_sets = BITMAP_ALLOC (NULL);
2918 clear_alias_mode_table = htab_create (11, clear_alias_mode_hash,
2919 clear_alias_mode_eq, NULL);
2920 clear_alias_mode_pool = create_alloc_pool ("clear_alias_mode_pool",
2921 sizeof (struct clear_alias_mode_holder), 100);
2924 bitmap_set_bit (clear_alias_sets, alias_set);
2926 tmp_holder.alias_set = alias_set;
2928 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, INSERT);
2929 gcc_assert (*slot == NULL);
2932 (struct clear_alias_mode_holder *) pool_alloc (clear_alias_mode_pool);
2933 entry->alias_set = alias_set;
2938 /* Remove ALIAS_SET from the sets of stack slots being considered. */
2941 dse_invalidate_singleton_alias_set (alias_set_type alias_set)
2943 if ((!gate_dse()) || !alias_set)
2946 bitmap_clear_bit (clear_alias_sets, alias_set);
2950 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
2954 get_bitmap_index (group_info_t group_info, HOST_WIDE_INT offset)
2958 HOST_WIDE_INT offset_p = -offset;
2959 if (offset_p >= group_info->offset_map_size_n)
2961 return group_info->offset_map_n[offset_p];
2965 if (offset >= group_info->offset_map_size_p)
2967 return group_info->offset_map_p[offset];
2972 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
2976 scan_stores_nospill (store_info_t store_info, bitmap gen, bitmap kill)
2981 group_info_t group_info
2982 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
2983 if (group_info->process_globally)
2984 for (i = store_info->begin; i < store_info->end; i++)
2986 int index = get_bitmap_index (group_info, i);
2989 bitmap_set_bit (gen, index);
2991 bitmap_clear_bit (kill, index);
2994 store_info = store_info->next;
2999 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3003 scan_stores_spill (store_info_t store_info, bitmap gen, bitmap kill)
3007 if (store_info->alias_set)
3009 int index = get_bitmap_index (clear_alias_group,
3010 store_info->alias_set);
3013 bitmap_set_bit (gen, index);
3015 bitmap_clear_bit (kill, index);
3018 store_info = store_info->next;
3023 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3027 scan_reads_nospill (insn_info_t insn_info, bitmap gen, bitmap kill)
3029 read_info_t read_info = insn_info->read_rec;
3033 /* If this insn reads the frame, kill all the frame related stores. */
3034 if (insn_info->frame_read)
3036 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
3037 if (group->process_globally && group->frame_related)
3040 bitmap_ior_into (kill, group->group_kill);
3041 bitmap_and_compl_into (gen, group->group_kill);
3047 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
3049 if (group->process_globally)
3051 if (i == read_info->group_id)
3053 if (read_info->begin > read_info->end)
3055 /* Begin > end for block mode reads. */
3057 bitmap_ior_into (kill, group->group_kill);
3058 bitmap_and_compl_into (gen, group->group_kill);
3062 /* The groups are the same, just process the
3065 for (j = read_info->begin; j < read_info->end; j++)
3067 int index = get_bitmap_index (group, j);
3071 bitmap_set_bit (kill, index);
3072 bitmap_clear_bit (gen, index);
3079 /* The groups are different, if the alias sets
3080 conflict, clear the entire group. We only need
3081 to apply this test if the read_info is a cselib
3082 read. Anything with a constant base cannot alias
3083 something else with a different constant
3085 if ((read_info->group_id < 0)
3086 && canon_true_dependence (group->base_mem,
3087 GET_MODE (group->base_mem),
3088 group->canon_base_addr,
3089 read_info->mem, NULL_RTX,
3093 bitmap_ior_into (kill, group->group_kill);
3094 bitmap_and_compl_into (gen, group->group_kill);
3100 read_info = read_info->next;
3104 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3108 scan_reads_spill (read_info_t read_info, bitmap gen, bitmap kill)
3112 if (read_info->alias_set)
3114 int index = get_bitmap_index (clear_alias_group,
3115 read_info->alias_set);
3119 bitmap_set_bit (kill, index);
3120 bitmap_clear_bit (gen, index);
3124 read_info = read_info->next;
3129 /* Return the insn in BB_INFO before the first wild read or if there
3130 are no wild reads in the block, return the last insn. */
3133 find_insn_before_first_wild_read (bb_info_t bb_info)
3135 insn_info_t insn_info = bb_info->last_insn;
3136 insn_info_t last_wild_read = NULL;
3140 if (insn_info->wild_read)
3142 last_wild_read = insn_info->prev_insn;
3143 /* Block starts with wild read. */
3144 if (!last_wild_read)
3148 insn_info = insn_info->prev_insn;
3152 return last_wild_read;
3154 return bb_info->last_insn;
3158 /* Scan the insns in BB_INFO starting at PTR and going to the top of
3159 the block in order to build the gen and kill sets for the block.
3160 We start at ptr which may be the last insn in the block or may be
3161 the first insn with a wild read. In the latter case we are able to
3162 skip the rest of the block because it just does not matter:
3163 anything that happens is hidden by the wild read. */
3166 dse_step3_scan (bool for_spills, basic_block bb)
3168 bb_info_t bb_info = bb_table[bb->index];
3169 insn_info_t insn_info;
3172 /* There are no wild reads in the spill case. */
3173 insn_info = bb_info->last_insn;
3175 insn_info = find_insn_before_first_wild_read (bb_info);
3177 /* In the spill case or in the no_spill case if there is no wild
3178 read in the block, we will need a kill set. */
3179 if (insn_info == bb_info->last_insn)
3182 bitmap_clear (bb_info->kill);
3184 bb_info->kill = BITMAP_ALLOC (NULL);
3188 BITMAP_FREE (bb_info->kill);
3192 /* There may have been code deleted by the dce pass run before
3194 if (insn_info->insn && INSN_P (insn_info->insn))
3196 /* Process the read(s) last. */
3199 scan_stores_spill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3200 scan_reads_spill (insn_info->read_rec, bb_info->gen, bb_info->kill);
3204 scan_stores_nospill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3205 scan_reads_nospill (insn_info, bb_info->gen, bb_info->kill);
3209 insn_info = insn_info->prev_insn;
3214 /* Set the gen set of the exit block, and also any block with no
3215 successors that does not have a wild read. */
3218 dse_step3_exit_block_scan (bb_info_t bb_info)
3220 /* The gen set is all 0's for the exit block except for the
3221 frame_pointer_group. */
3223 if (stores_off_frame_dead_at_return)
3228 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
3230 if (group->process_globally && group->frame_related)
3231 bitmap_ior_into (bb_info->gen, group->group_kill);
3237 /* Find all of the blocks that are not backwards reachable from the
3238 exit block or any block with no successors (BB). These are the
3239 infinite loops or infinite self loops. These blocks will still
3240 have their bits set in UNREACHABLE_BLOCKS. */
3243 mark_reachable_blocks (sbitmap unreachable_blocks, basic_block bb)
3248 if (TEST_BIT (unreachable_blocks, bb->index))
3250 RESET_BIT (unreachable_blocks, bb->index);
3251 FOR_EACH_EDGE (e, ei, bb->preds)
3253 mark_reachable_blocks (unreachable_blocks, e->src);
3258 /* Build the transfer functions for the function. */
3261 dse_step3 (bool for_spills)
3264 sbitmap unreachable_blocks = sbitmap_alloc (last_basic_block);
3265 sbitmap_iterator sbi;
3266 bitmap all_ones = NULL;
3269 sbitmap_ones (unreachable_blocks);
3273 bb_info_t bb_info = bb_table[bb->index];
3275 bitmap_clear (bb_info->gen);
3277 bb_info->gen = BITMAP_ALLOC (NULL);
3279 if (bb->index == ENTRY_BLOCK)
3281 else if (bb->index == EXIT_BLOCK)
3282 dse_step3_exit_block_scan (bb_info);
3284 dse_step3_scan (for_spills, bb);
3285 if (EDGE_COUNT (bb->succs) == 0)
3286 mark_reachable_blocks (unreachable_blocks, bb);
3288 /* If this is the second time dataflow is run, delete the old
3291 BITMAP_FREE (bb_info->in);
3293 BITMAP_FREE (bb_info->out);
3296 /* For any block in an infinite loop, we must initialize the out set
3297 to all ones. This could be expensive, but almost never occurs in
3298 practice. However, it is common in regression tests. */
3299 EXECUTE_IF_SET_IN_SBITMAP (unreachable_blocks, 0, i, sbi)
3301 if (bitmap_bit_p (all_blocks, i))
3303 bb_info_t bb_info = bb_table[i];
3309 all_ones = BITMAP_ALLOC (NULL);
3310 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, j, group)
3311 bitmap_ior_into (all_ones, group->group_kill);
3315 bb_info->out = BITMAP_ALLOC (NULL);
3316 bitmap_copy (bb_info->out, all_ones);
3322 BITMAP_FREE (all_ones);
3323 sbitmap_free (unreachable_blocks);
3328 /*----------------------------------------------------------------------------
3331 Solve the bitvector equations.
3332 ----------------------------------------------------------------------------*/
3335 /* Confluence function for blocks with no successors. Create an out
3336 set from the gen set of the exit block. This block logically has
3337 the exit block as a successor. */
3342 dse_confluence_0 (basic_block bb)
3344 bb_info_t bb_info = bb_table[bb->index];
3346 if (bb->index == EXIT_BLOCK)
3351 bb_info->out = BITMAP_ALLOC (NULL);
3352 bitmap_copy (bb_info->out, bb_table[EXIT_BLOCK]->gen);
3356 /* Propagate the information from the in set of the dest of E to the
3357 out set of the src of E. If the various in or out sets are not
3358 there, that means they are all ones. */
3361 dse_confluence_n (edge e)
3363 bb_info_t src_info = bb_table[e->src->index];
3364 bb_info_t dest_info = bb_table[e->dest->index];
3369 bitmap_and_into (src_info->out, dest_info->in);
3372 src_info->out = BITMAP_ALLOC (NULL);
3373 bitmap_copy (src_info->out, dest_info->in);
3380 /* Propagate the info from the out to the in set of BB_INDEX's basic
3381 block. There are three cases:
3383 1) The block has no kill set. In this case the kill set is all
3384 ones. It does not matter what the out set of the block is, none of
3385 the info can reach the top. The only thing that reaches the top is
3386 the gen set and we just copy the set.
3388 2) There is a kill set but no out set and bb has successors. In
3389 this case we just return. Eventually an out set will be created and
3390 it is better to wait than to create a set of ones.
3392 3) There is both a kill and out set. We apply the obvious transfer
3397 dse_transfer_function (int bb_index)
3399 bb_info_t bb_info = bb_table[bb_index];
3407 return bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3408 bb_info->out, bb_info->kill);
3411 bb_info->in = BITMAP_ALLOC (NULL);
3412 bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3413 bb_info->out, bb_info->kill);
3423 /* Case 1 above. If there is already an in set, nothing
3429 bb_info->in = BITMAP_ALLOC (NULL);
3430 bitmap_copy (bb_info->in, bb_info->gen);
3436 /* Solve the dataflow equations. */
3441 df_simple_dataflow (DF_BACKWARD, NULL, dse_confluence_0,
3442 dse_confluence_n, dse_transfer_function,
3443 all_blocks, df_get_postorder (DF_BACKWARD),
3444 df_get_n_blocks (DF_BACKWARD));
3449 fprintf (dump_file, "\n\n*** Global dataflow info after analysis.\n");
3452 bb_info_t bb_info = bb_table[bb->index];
3454 df_print_bb_index (bb, dump_file);
3456 bitmap_print (dump_file, bb_info->in, " in: ", "\n");
3458 fprintf (dump_file, " in: *MISSING*\n");
3460 bitmap_print (dump_file, bb_info->gen, " gen: ", "\n");
3462 fprintf (dump_file, " gen: *MISSING*\n");
3464 bitmap_print (dump_file, bb_info->kill, " kill: ", "\n");
3466 fprintf (dump_file, " kill: *MISSING*\n");
3468 bitmap_print (dump_file, bb_info->out, " out: ", "\n");
3470 fprintf (dump_file, " out: *MISSING*\n\n");
3477 /*----------------------------------------------------------------------------
3480 Delete the stores that can only be deleted using the global information.
3481 ----------------------------------------------------------------------------*/
3485 dse_step5_nospill (void)
3490 bb_info_t bb_info = bb_table[bb->index];
3491 insn_info_t insn_info = bb_info->last_insn;
3492 bitmap v = bb_info->out;
3496 bool deleted = false;
3497 if (dump_file && insn_info->insn)
3499 fprintf (dump_file, "starting to process insn %d\n",
3500 INSN_UID (insn_info->insn));
3501 bitmap_print (dump_file, v, " v: ", "\n");
3504 /* There may have been code deleted by the dce pass run before
3507 && INSN_P (insn_info->insn)
3508 && (!insn_info->cannot_delete)
3509 && (!bitmap_empty_p (v)))
3511 store_info_t store_info = insn_info->store_rec;
3513 /* Try to delete the current insn. */
3516 /* Skip the clobbers. */
3517 while (!store_info->is_set)
3518 store_info = store_info->next;
3520 if (store_info->alias_set)
3525 group_info_t group_info
3526 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
3528 for (i = store_info->begin; i < store_info->end; i++)
3530 int index = get_bitmap_index (group_info, i);
3533 fprintf (dump_file, "i = %d, index = %d\n", (int)i, index);
3534 if (index == 0 || !bitmap_bit_p (v, index))
3537 fprintf (dump_file, "failing at i = %d\n", (int)i);
3547 check_for_inc_dec (insn_info->insn);
3548 delete_insn (insn_info->insn);
3549 insn_info->insn = NULL;
3554 /* We do want to process the local info if the insn was
3555 deleted. For instance, if the insn did a wild read, we
3556 no longer need to trash the info. */
3558 && INSN_P (insn_info->insn)
3561 scan_stores_nospill (insn_info->store_rec, v, NULL);
3562 if (insn_info->wild_read)
3565 fprintf (dump_file, "wild read\n");
3568 else if (insn_info->read_rec)
3571 fprintf (dump_file, "regular read\n");
3572 scan_reads_nospill (insn_info, v, NULL);
3576 insn_info = insn_info->prev_insn;
3583 dse_step5_spill (void)
3588 bb_info_t bb_info = bb_table[bb->index];
3589 insn_info_t insn_info = bb_info->last_insn;
3590 bitmap v = bb_info->out;
3594 bool deleted = false;
3595 /* There may have been code deleted by the dce pass run before
3598 && INSN_P (insn_info->insn)
3599 && (!insn_info->cannot_delete)
3600 && (!bitmap_empty_p (v)))
3602 /* Try to delete the current insn. */
3603 store_info_t store_info = insn_info->store_rec;
3608 if (store_info->alias_set)
3610 int index = get_bitmap_index (clear_alias_group,
3611 store_info->alias_set);
3612 if (index == 0 || !bitmap_bit_p (v, index))
3620 store_info = store_info->next;
3622 if (deleted && dbg_cnt (dse))
3625 fprintf (dump_file, "Spill deleting insn %d\n",
3626 INSN_UID (insn_info->insn));
3627 check_for_inc_dec (insn_info->insn);
3628 delete_insn (insn_info->insn);
3630 insn_info->insn = NULL;
3635 && INSN_P (insn_info->insn)
3638 scan_stores_spill (insn_info->store_rec, v, NULL);
3639 scan_reads_spill (insn_info->read_rec, v, NULL);
3642 insn_info = insn_info->prev_insn;
3649 /*----------------------------------------------------------------------------
3652 Delete stores made redundant by earlier stores (which store the same
3653 value) that couldn't be eliminated.
3654 ----------------------------------------------------------------------------*/
3663 bb_info_t bb_info = bb_table[bb->index];
3664 insn_info_t insn_info = bb_info->last_insn;
3668 /* There may have been code deleted by the dce pass run before
3671 && INSN_P (insn_info->insn)
3672 && !insn_info->cannot_delete)
3674 store_info_t s_info = insn_info->store_rec;
3676 while (s_info && !s_info->is_set)
3677 s_info = s_info->next;
3679 && s_info->redundant_reason
3680 && s_info->redundant_reason->insn
3681 && INSN_P (s_info->redundant_reason->insn))
3683 rtx rinsn = s_info->redundant_reason->insn;
3685 fprintf (dump_file, "Locally deleting insn %d "
3686 "because insn %d stores the "
3687 "same value and couldn't be "
3689 INSN_UID (insn_info->insn),
3691 delete_dead_store_insn (insn_info);
3694 insn_info = insn_info->prev_insn;
3699 /*----------------------------------------------------------------------------
3702 Destroy everything left standing.
3703 ----------------------------------------------------------------------------*/
3706 dse_step7 (bool global_done)
3712 FOR_EACH_VEC_ELT (group_info_t, rtx_group_vec, i, group)
3714 free (group->offset_map_n);
3715 free (group->offset_map_p);
3716 BITMAP_FREE (group->store1_n);
3717 BITMAP_FREE (group->store1_p);
3718 BITMAP_FREE (group->store2_n);
3719 BITMAP_FREE (group->store2_p);
3720 BITMAP_FREE (group->group_kill);
3726 bb_info_t bb_info = bb_table[bb->index];
3727 BITMAP_FREE (bb_info->gen);
3729 BITMAP_FREE (bb_info->kill);
3731 BITMAP_FREE (bb_info->in);
3733 BITMAP_FREE (bb_info->out);
3736 if (clear_alias_sets)
3738 BITMAP_FREE (clear_alias_sets);
3739 BITMAP_FREE (disqualified_clear_alias_sets);
3740 free_alloc_pool (clear_alias_mode_pool);
3741 htab_delete (clear_alias_mode_table);
3744 end_alias_analysis ();
3746 htab_delete (rtx_group_table);
3747 VEC_free (group_info_t, heap, rtx_group_vec);
3748 BITMAP_FREE (all_blocks);
3749 BITMAP_FREE (scratch);
3751 free_alloc_pool (rtx_store_info_pool);
3752 free_alloc_pool (read_info_pool);
3753 free_alloc_pool (insn_info_pool);
3754 free_alloc_pool (bb_info_pool);
3755 free_alloc_pool (rtx_group_info_pool);
3756 free_alloc_pool (deferred_change_pool);
3760 /* -------------------------------------------------------------------------
3762 ------------------------------------------------------------------------- */
3764 /* Callback for running pass_rtl_dse. */
3767 rest_of_handle_dse (void)
3769 bool did_global = false;
3771 df_set_flags (DF_DEFER_INSN_RESCAN);
3773 /* Need the notes since we must track live hardregs in the forwards
3775 df_note_add_problem ();
3781 if (dse_step2_nospill ())
3783 df_set_flags (DF_LR_RUN_DCE);
3787 fprintf (dump_file, "doing global processing\n");
3790 dse_step5_nospill ();
3793 /* For the instance of dse that runs after reload, we make a special
3794 pass to process the spills. These are special in that they are
3795 totally transparent, i.e, there is no aliasing issues that need
3796 to be considered. This means that the wild reads that kill
3797 everything else do not apply here. */
3798 if (clear_alias_sets && dse_step2_spill ())
3802 df_set_flags (DF_LR_RUN_DCE);
3807 fprintf (dump_file, "doing global spill processing\n");
3814 dse_step7 (did_global);
3817 fprintf (dump_file, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3818 locally_deleted, globally_deleted, spill_deleted);
3825 return gate_dse1 () || gate_dse2 ();
3831 return optimize > 0 && flag_dse
3838 return optimize > 0 && flag_dse
3842 struct rtl_opt_pass pass_rtl_dse1 =
3847 gate_dse1, /* gate */
3848 rest_of_handle_dse, /* execute */
3851 0, /* static_pass_number */
3852 TV_DSE1, /* tv_id */
3853 0, /* properties_required */
3854 0, /* properties_provided */
3855 0, /* properties_destroyed */
3856 0, /* todo_flags_start */
3858 TODO_df_finish | TODO_verify_rtl_sharing |
3859 TODO_ggc_collect /* todo_flags_finish */
3863 struct rtl_opt_pass pass_rtl_dse2 =
3868 gate_dse2, /* gate */
3869 rest_of_handle_dse, /* execute */
3872 0, /* static_pass_number */
3873 TV_DSE2, /* tv_id */
3874 0, /* properties_required */
3875 0, /* properties_provided */
3876 0, /* properties_destroyed */
3877 0, /* todo_flags_start */
3879 TODO_df_finish | TODO_verify_rtl_sharing |
3880 TODO_ggc_collect /* todo_flags_finish */