1 /* RTL dead store elimination.
2 Copyright (C) 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
4 Contributed by Richard Sandiford <rsandifor@codesourcery.com>
5 and Kenneth Zadeck <zadeck@naturalbridge.com>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
27 #include "coretypes.h"
34 #include "hard-reg-set.h"
39 #include "tree-pass.h"
40 #include "alloc-pool.h"
42 #include "insn-config.h"
49 /* This file contains three techniques for performing Dead Store
52 * The first technique performs dse locally on any base address. It
53 is based on the cselib which is a local value numbering technique.
54 This technique is local to a basic block but deals with a fairly
57 * The second technique performs dse globally but is restricted to
58 base addresses that are either constant or are relative to the
61 * The third technique, (which is only done after register allocation)
62 processes the spill spill slots. This differs from the second
63 technique because it takes advantage of the fact that spilling is
64 completely free from the effects of aliasing.
66 Logically, dse is a backwards dataflow problem. A store can be
67 deleted if it if cannot be reached in the backward direction by any
68 use of the value being stored. However, the local technique uses a
69 forwards scan of the basic block because cselib requires that the
70 block be processed in that order.
72 The pass is logically broken into 7 steps:
76 1) The local algorithm, as well as scanning the insns for the two
79 2) Analysis to see if the global algs are necessary. In the case
80 of stores base on a constant address, there must be at least two
81 stores to that address, to make it possible to delete some of the
82 stores. In the case of stores off of the frame or spill related
83 stores, only one store to an address is necessary because those
84 stores die at the end of the function.
86 3) Set up the global dataflow equations based on processing the
87 info parsed in the first step.
89 4) Solve the dataflow equations.
91 5) Delete the insns that the global analysis has indicated are
96 This step uses cselib and canon_rtx to build the largest expression
97 possible for each address. This pass is a forwards pass through
98 each basic block. From the point of view of the global technique,
99 the first pass could examine a block in either direction. The
100 forwards ordering is to accommodate cselib.
102 We a simplifying assumption: addresses fall into four broad
105 1) base has rtx_varies_p == false, offset is constant.
106 2) base has rtx_varies_p == false, offset variable.
107 3) base has rtx_varies_p == true, offset constant.
108 4) base has rtx_varies_p == true, offset variable.
110 The local passes are able to process all 4 kinds of addresses. The
111 global pass only handles (1).
113 The global problem is formulated as follows:
115 A store, S1, to address A, where A is not relative to the stack
116 frame, can be eliminated if all paths from S1 to the end of the
117 of the function contain another store to A before a read to A.
119 If the address A is relative to the stack frame, a store S2 to A
120 can be eliminated if there are no paths from S1 that reach the
121 end of the function that read A before another store to A. In
122 this case S2 can be deleted if there are paths to from S2 to the
123 end of the function that have no reads or writes to A. This
124 second case allows stores to the stack frame to be deleted that
125 would otherwise die when the function returns. This cannot be
126 done if stores_off_frame_dead_at_return is not true. See the doc
127 for that variable for when this variable is false.
129 The global problem is formulated as a backwards set union
130 dataflow problem where the stores are the gens and reads are the
131 kills. Set union problems are rare and require some special
132 handling given our representation of bitmaps. A straightforward
133 implementation of requires a lot of bitmaps filled with 1s.
134 These are expensive and cumbersome in our bitmap formulation so
135 care has been taken to avoid large vectors filled with 1s. See
136 the comments in bb_info and in the dataflow confluence functions
139 There are two places for further enhancements to this algorithm:
141 1) The original dse which was embedded in a pass called flow also
142 did local address forwarding. For example in
147 flow would replace the right hand side of the second insn with a
148 reference to r100. Most of the information is available to add this
149 to this pass. It has not done it because it is a lot of work in
150 the case that either r100 is assigned to between the first and
151 second insn and/or the second insn is a load of part of the value
152 stored by the first insn.
154 insn 5 in gcc.c-torture/compile/990203-1.c simple case.
155 insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
156 insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
157 insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
159 2) The cleaning up of spill code is quite profitable. It currently
160 depends on reading tea leaves and chicken entrails left by reload.
161 This pass depends on reload creating a singleton alias set for each
162 spill slot and telling the next dse pass which of these alias sets
163 are the singletons. Rather than analyze the addresses of the
164 spills, dse's spill processing just does analysis of the loads and
165 stores that use those alias sets. There are three cases where this
168 a) Reload sometimes creates the slot for one mode of access, and
169 then inserts loads and/or stores for a smaller mode. In this
170 case, the current code just punts on the slot. The proper thing
171 to do is to back out and use one bit vector position for each
172 byte of the entity associated with the slot. This depends on
173 KNOWING that reload always generates the accesses for each of the
174 bytes in some canonical (read that easy to understand several
175 passes after reload happens) way.
177 b) Reload sometimes decides that spill slot it allocated was not
178 large enough for the mode and goes back and allocates more slots
179 with the same mode and alias set. The backout in this case is a
180 little more graceful than (a). In this case the slot is unmarked
181 as being a spill slot and if final address comes out to be based
182 off the frame pointer, the global algorithm handles this slot.
184 c) For any pass that may prespill, there is currently no
185 mechanism to tell the dse pass that the slot being used has the
186 special properties that reload uses. It may be that all that is
187 required is to have those passes make the same calls that reload
188 does, assuming that the alias sets can be manipulated in the same
191 /* There are limits to the size of constant offsets we model for the
192 global problem. There are certainly test cases, that exceed this
193 limit, however, it is unlikely that there are important programs
194 that really have constant offsets this size. */
195 #define MAX_OFFSET (64 * 1024)
198 static bitmap scratch = NULL;
201 /* This structure holds information about a candidate store. */
205 /* False means this is a clobber. */
208 /* The id of the mem group of the base address. If rtx_varies_p is
209 true, this is -1. Otherwise, it is the index into the group
213 /* This is the cselib value. */
214 cselib_val *cse_base;
216 /* This canonized mem. */
219 /* The result of get_addr on mem. */
222 /* If this is non-zero, it is the alias set of a spill location. */
223 alias_set_type alias_set;
225 /* The offset of the first and byte before the last byte associated
226 with the operation. */
229 /* An bitmask as wide as the number of bytes in the word that
230 contains a 1 if the byte may be needed. The store is unused if
231 all of the bits are 0. */
232 unsigned HOST_WIDE_INT positions_needed;
234 /* The next store info for this insn. */
235 struct store_info *next;
237 /* The right hand side of the store. This is used if there is a
238 subsequent reload of the mems address somewhere later in the
243 /* Return a bitmask with the first N low bits set. */
245 static unsigned HOST_WIDE_INT
246 lowpart_bitmask (int n)
248 unsigned HOST_WIDE_INT mask = ~(unsigned HOST_WIDE_INT) 0;
249 return mask >> (HOST_BITS_PER_WIDE_INT - n);
252 typedef struct store_info *store_info_t;
253 static alloc_pool cse_store_info_pool;
254 static alloc_pool rtx_store_info_pool;
256 /* This structure holds information about a load. These are only
257 built for rtx bases. */
260 /* The id of the mem group of the base address. */
263 /* If this is non-zero, it is the alias set of a spill location. */
264 alias_set_type alias_set;
266 /* The offset of the first and byte after the last byte associated
267 with the operation. If begin == end == 0, the read did not have
268 a constant offset. */
271 /* The mem being read. */
274 /* The next read_info for this insn. */
275 struct read_info *next;
277 typedef struct read_info *read_info_t;
278 static alloc_pool read_info_pool;
281 /* One of these records is created for each insn. */
285 /* Set true if the insn contains a store but the insn itself cannot
286 be deleted. This is set if the insn is a parallel and there is
287 more than one non dead output or if the insn is in some way
291 /* This field is only used by the global algorithm. It is set true
292 if the insn contains any read of mem except for a (1). This is
293 also set if the insn is a call or has a clobber mem. If the insn
294 contains a wild read, the use_rec will be null. */
297 /* This field is only used for the processing of const functions.
298 These functions cannot read memory, but they can read the stack
299 because that is where they may get their parms. We need to be
300 this conservative because, like the store motion pass, we don't
301 consider CALL_INSN_FUNCTION_USAGE when processing call insns.
302 Moreover, we need to distinguish two cases:
303 1. Before reload (register elimination), the stores related to
304 outgoing arguments are stack pointer based and thus deemed
305 of non-constant base in this pass. This requires special
306 handling but also means that the frame pointer based stores
307 need not be killed upon encountering a const function call.
308 2. After reload, the stores related to outgoing arguments can be
309 either stack pointer or hard frame pointer based. This means
310 that we have no other choice than also killing all the frame
311 pointer based stores upon encountering a const function call.
312 This field is set after reload for const function calls. Having
313 this set is less severe than a wild read, it just means that all
314 the frame related stores are killed rather than all the stores. */
317 /* This field is only used for the processing of const functions.
318 It is set if the insn may contain a stack pointer based store. */
319 bool stack_pointer_based;
321 /* This is true if any of the sets within the store contains a
322 cselib base. Such stores can only be deleted by the local
324 bool contains_cselib_groups;
329 /* The list of mem sets or mem clobbers that are contained in this
330 insn. If the insn is deletable, it contains only one mem set.
331 But it could also contain clobbers. Insns that contain more than
332 one mem set are not deletable, but each of those mems are here in
333 order to provide info to delete other insns. */
334 store_info_t store_rec;
336 /* The linked list of mem uses in this insn. Only the reads from
337 rtx bases are listed here. The reads to cselib bases are
338 completely processed during the first scan and so are never
340 read_info_t read_rec;
342 /* The prev insn in the basic block. */
343 struct insn_info * prev_insn;
345 /* The linked list of insns that are in consideration for removal in
346 the forwards pass thru the basic block. This pointer may be
347 trash as it is not cleared when a wild read occurs. The only
348 time it is guaranteed to be correct is when the traversal starts
349 at active_local_stores. */
350 struct insn_info * next_local_store;
353 typedef struct insn_info *insn_info_t;
354 static alloc_pool insn_info_pool;
356 /* The linked list of stores that are under consideration in this
358 static insn_info_t active_local_stores;
363 /* Pointer to the insn info for the last insn in the block. These
364 are linked so this is how all of the insns are reached. During
365 scanning this is the current insn being scanned. */
366 insn_info_t last_insn;
368 /* The info for the global dataflow problem. */
371 /* This is set if the transfer function should and in the wild_read
372 bitmap before applying the kill and gen sets. That vector knocks
373 out most of the bits in the bitmap and thus speeds up the
375 bool apply_wild_read;
377 /* The following 4 bitvectors hold information about which positions
378 of which stores are live or dead. They are indexed by
381 /* The set of store positions that exist in this block before a wild read. */
384 /* The set of load positions that exist in this block above the
385 same position of a store. */
388 /* The set of stores that reach the top of the block without being
391 Do not represent the in if it is all ones. Note that this is
392 what the bitvector should logically be initialized to for a set
393 intersection problem. However, like the kill set, this is too
394 expensive. So initially, the in set will only be created for the
395 exit block and any block that contains a wild read. */
398 /* The set of stores that reach the bottom of the block from it's
401 Do not represent the in if it is all ones. Note that this is
402 what the bitvector should logically be initialized to for a set
403 intersection problem. However, like the kill and in set, this is
404 too expensive. So what is done is that the confluence operator
405 just initializes the vector from one of the out sets of the
406 successors of the block. */
409 /* The following bitvector is indexed by the reg number. It
410 contains the set of regs that are live at the current instruction
411 being processed. While it contains info for all of the
412 registers, only the pseudos are actually examined. It is used to
413 assure that shift sequences that are inserted do not accidently
414 clobber live hard regs. */
418 typedef struct bb_info *bb_info_t;
419 static alloc_pool bb_info_pool;
421 /* Table to hold all bb_infos. */
422 static bb_info_t *bb_table;
424 /* There is a group_info for each rtx base that is used to reference
425 memory. There are also not many of the rtx bases because they are
426 very limited in scope. */
430 /* The actual base of the address. */
433 /* The sequential id of the base. This allows us to have a
434 canonical ordering of these that is not based on addresses. */
437 /* A mem wrapped around the base pointer for the group in order to
438 do read dependency. */
441 /* Canonized version of base_mem, most likely the same thing. */
444 /* These two sets of two bitmaps are used to keep track of how many
445 stores are actually referencing that position from this base. We
446 only do this for rtx bases as this will be used to assign
447 positions in the bitmaps for the global problem. Bit N is set in
448 store1 on the first store for offset N. Bit N is set in store2
449 for the second store to offset N. This is all we need since we
450 only care about offsets that have two or more stores for them.
452 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
453 for 0 and greater offsets.
455 There is one special case here, for stores into the stack frame,
456 we will or store1 into store2 before deciding which stores look
457 at globally. This is because stores to the stack frame that have
458 no other reads before the end of the function can also be
460 bitmap store1_n, store1_p, store2_n, store2_p;
462 /* The positions in this bitmap have the same assignments as the in,
463 out, gen and kill bitmaps. This bitmap is all zeros except for
464 the positions that are occupied by stores for this group. */
467 /* True if there are any positions that are to be processed
469 bool process_globally;
471 /* True if the base of this group is either the frame_pointer or
472 hard_frame_pointer. */
475 /* The offset_map is used to map the offsets from this base into
476 positions in the global bitmaps. It is only created after all of
477 the all of stores have been scanned and we know which ones we
479 int *offset_map_n, *offset_map_p;
480 int offset_map_size_n, offset_map_size_p;
482 typedef struct group_info *group_info_t;
483 typedef const struct group_info *const_group_info_t;
484 static alloc_pool rtx_group_info_pool;
486 /* Tables of group_info structures, hashed by base value. */
487 static htab_t rtx_group_table;
489 /* Index into the rtx_group_vec. */
490 static int rtx_group_next_id;
492 DEF_VEC_P(group_info_t);
493 DEF_VEC_ALLOC_P(group_info_t,heap);
495 static VEC(group_info_t,heap) *rtx_group_vec;
498 /* This structure holds the set of changes that are being deferred
499 when removing read operation. See replace_read. */
500 struct deferred_change
503 /* The mem that is being replaced. */
506 /* The reg it is being replaced with. */
509 struct deferred_change *next;
512 typedef struct deferred_change *deferred_change_t;
513 static alloc_pool deferred_change_pool;
515 static deferred_change_t deferred_change_list = NULL;
517 /* This are used to hold the alias sets of spill variables. Since
518 these are never aliased and there may be a lot of them, it makes
519 sense to treat them specially. This bitvector is only allocated in
520 calls from dse_record_singleton_alias_set which currently is only
521 made during reload1. So when dse is called before reload this
522 mechanism does nothing. */
524 static bitmap clear_alias_sets = NULL;
526 /* The set of clear_alias_sets that have been disqualified because
527 there are loads or stores using a different mode than the alias set
528 was registered with. */
529 static bitmap disqualified_clear_alias_sets = NULL;
531 /* The group that holds all of the clear_alias_sets. */
532 static group_info_t clear_alias_group;
534 /* The modes of the clear_alias_sets. */
535 static htab_t clear_alias_mode_table;
537 /* Hash table element to look up the mode for an alias set. */
538 struct clear_alias_mode_holder
540 alias_set_type alias_set;
541 enum machine_mode mode;
544 static alloc_pool clear_alias_mode_pool;
546 /* This is true except if cfun->stdarg -- i.e. we cannot do
547 this for vararg functions because they play games with the frame. */
548 static bool stores_off_frame_dead_at_return;
550 /* Counter for stats. */
551 static int globally_deleted;
552 static int locally_deleted;
553 static int spill_deleted;
555 static bitmap all_blocks;
557 /* The number of bits used in the global bitmaps. */
558 static unsigned int current_position;
561 static bool gate_dse (void);
562 static bool gate_dse1 (void);
563 static bool gate_dse2 (void);
566 /*----------------------------------------------------------------------------
570 ----------------------------------------------------------------------------*/
572 /* Hashtable callbacks for maintaining the "bases" field of
573 store_group_info, given that the addresses are function invariants. */
576 clear_alias_mode_eq (const void *p1, const void *p2)
578 const struct clear_alias_mode_holder * h1
579 = (const struct clear_alias_mode_holder *) p1;
580 const struct clear_alias_mode_holder * h2
581 = (const struct clear_alias_mode_holder *) p2;
582 return h1->alias_set == h2->alias_set;
587 clear_alias_mode_hash (const void *p)
589 const struct clear_alias_mode_holder *holder
590 = (const struct clear_alias_mode_holder *) p;
591 return holder->alias_set;
595 /* Find the entry associated with ALIAS_SET. */
597 static struct clear_alias_mode_holder *
598 clear_alias_set_lookup (alias_set_type alias_set)
600 struct clear_alias_mode_holder tmp_holder;
603 tmp_holder.alias_set = alias_set;
604 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, NO_INSERT);
607 return (struct clear_alias_mode_holder *) *slot;
611 /* Hashtable callbacks for maintaining the "bases" field of
612 store_group_info, given that the addresses are function invariants. */
615 invariant_group_base_eq (const void *p1, const void *p2)
617 const_group_info_t gi1 = (const_group_info_t) p1;
618 const_group_info_t gi2 = (const_group_info_t) p2;
619 return rtx_equal_p (gi1->rtx_base, gi2->rtx_base);
624 invariant_group_base_hash (const void *p)
626 const_group_info_t gi = (const_group_info_t) p;
628 return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false);
632 /* Get the GROUP for BASE. Add a new group if it is not there. */
635 get_group_info (rtx base)
637 struct group_info tmp_gi;
643 /* Find the store_base_info structure for BASE, creating a new one
645 tmp_gi.rtx_base = base;
646 slot = htab_find_slot (rtx_group_table, &tmp_gi, INSERT);
647 gi = (group_info_t) *slot;
651 if (!clear_alias_group)
653 clear_alias_group = gi =
654 (group_info_t) pool_alloc (rtx_group_info_pool);
655 memset (gi, 0, sizeof (struct group_info));
656 gi->id = rtx_group_next_id++;
657 gi->store1_n = BITMAP_ALLOC (NULL);
658 gi->store1_p = BITMAP_ALLOC (NULL);
659 gi->store2_n = BITMAP_ALLOC (NULL);
660 gi->store2_p = BITMAP_ALLOC (NULL);
661 gi->group_kill = BITMAP_ALLOC (NULL);
662 gi->process_globally = false;
663 gi->offset_map_size_n = 0;
664 gi->offset_map_size_p = 0;
665 gi->offset_map_n = NULL;
666 gi->offset_map_p = NULL;
667 VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);
669 return clear_alias_group;
674 *slot = gi = (group_info_t) pool_alloc (rtx_group_info_pool);
676 gi->id = rtx_group_next_id++;
677 gi->base_mem = gen_rtx_MEM (QImode, base);
678 gi->canon_base_mem = canon_rtx (gi->base_mem);
679 gi->store1_n = BITMAP_ALLOC (NULL);
680 gi->store1_p = BITMAP_ALLOC (NULL);
681 gi->store2_n = BITMAP_ALLOC (NULL);
682 gi->store2_p = BITMAP_ALLOC (NULL);
683 gi->group_kill = BITMAP_ALLOC (NULL);
684 gi->process_globally = false;
686 (base == frame_pointer_rtx) || (base == hard_frame_pointer_rtx);
687 gi->offset_map_size_n = 0;
688 gi->offset_map_size_p = 0;
689 gi->offset_map_n = NULL;
690 gi->offset_map_p = NULL;
691 VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);
698 /* Initialization of data structures. */
704 globally_deleted = 0;
707 scratch = BITMAP_ALLOC (NULL);
710 = create_alloc_pool ("rtx_store_info_pool",
711 sizeof (struct store_info), 100);
713 = create_alloc_pool ("read_info_pool",
714 sizeof (struct read_info), 100);
716 = create_alloc_pool ("insn_info_pool",
717 sizeof (struct insn_info), 100);
719 = create_alloc_pool ("bb_info_pool",
720 sizeof (struct bb_info), 100);
722 = create_alloc_pool ("rtx_group_info_pool",
723 sizeof (struct group_info), 100);
725 = create_alloc_pool ("deferred_change_pool",
726 sizeof (struct deferred_change), 10);
728 rtx_group_table = htab_create (11, invariant_group_base_hash,
729 invariant_group_base_eq, NULL);
731 bb_table = XCNEWVEC (bb_info_t, last_basic_block);
732 rtx_group_next_id = 0;
734 stores_off_frame_dead_at_return = !cfun->stdarg;
736 init_alias_analysis ();
738 if (clear_alias_sets)
739 clear_alias_group = get_group_info (NULL);
741 clear_alias_group = NULL;
746 /*----------------------------------------------------------------------------
749 Scan all of the insns. Any random ordering of the blocks is fine.
750 Each block is scanned in forward order to accommodate cselib which
751 is used to remove stores with non-constant bases.
752 ----------------------------------------------------------------------------*/
754 /* Delete all of the store_info recs from INSN_INFO. */
757 free_store_info (insn_info_t insn_info)
759 store_info_t store_info = insn_info->store_rec;
762 store_info_t next = store_info->next;
763 if (store_info->cse_base)
764 pool_free (cse_store_info_pool, store_info);
766 pool_free (rtx_store_info_pool, store_info);
770 insn_info->cannot_delete = true;
771 insn_info->contains_cselib_groups = false;
772 insn_info->store_rec = NULL;
782 /* Add an insn to do the add inside a x if it is a
783 PRE/POST-INC/DEC/MODIFY. D is an structure containing the insn and
784 the size of the mode of the MEM that this is inside of. */
787 replace_inc_dec (rtx *r, void *d)
790 struct insn_size *data = (struct insn_size *)d;
791 switch (GET_CODE (x))
796 rtx r1 = XEXP (x, 0);
797 rtx c = gen_int_mode (Pmode, data->size);
798 emit_insn_before (gen_rtx_SET (Pmode, r1,
799 gen_rtx_PLUS (Pmode, r1, c)),
807 rtx r1 = XEXP (x, 0);
808 rtx c = gen_int_mode (Pmode, -data->size);
809 emit_insn_before (gen_rtx_SET (Pmode, r1,
810 gen_rtx_PLUS (Pmode, r1, c)),
818 /* We can reuse the add because we are about to delete the
819 insn that contained it. */
820 rtx add = XEXP (x, 0);
821 rtx r1 = XEXP (add, 0);
822 emit_insn_before (gen_rtx_SET (Pmode, r1, add), data->insn);
832 /* If X is a MEM, check the address to see if it is PRE/POST-INC/DEC/MODIFY
833 and generate an add to replace that. */
836 replace_inc_dec_mem (rtx *r, void *d)
839 if (x != NULL_RTX && MEM_P (x))
841 struct insn_size data;
843 data.size = GET_MODE_SIZE (GET_MODE (x));
846 for_each_rtx (&XEXP (x, 0), replace_inc_dec, &data);
853 /* Before we delete INSN, make sure that the auto inc/dec, if it is
854 there, is split into a separate insn. */
857 check_for_inc_dec (rtx insn)
859 rtx note = find_reg_note (insn, REG_INC, NULL_RTX);
861 for_each_rtx (&insn, replace_inc_dec_mem, insn);
865 /* Delete the insn and free all of the fields inside INSN_INFO. */
868 delete_dead_store_insn (insn_info_t insn_info)
870 read_info_t read_info;
875 check_for_inc_dec (insn_info->insn);
878 fprintf (dump_file, "Locally deleting insn %d ",
879 INSN_UID (insn_info->insn));
880 if (insn_info->store_rec->alias_set)
881 fprintf (dump_file, "alias set %d\n",
882 (int) insn_info->store_rec->alias_set);
884 fprintf (dump_file, "\n");
887 free_store_info (insn_info);
888 read_info = insn_info->read_rec;
892 read_info_t next = read_info->next;
893 pool_free (read_info_pool, read_info);
896 insn_info->read_rec = NULL;
898 delete_insn (insn_info->insn);
900 insn_info->insn = NULL;
902 insn_info->wild_read = false;
906 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
910 set_usage_bits (group_info_t group, HOST_WIDE_INT offset, HOST_WIDE_INT width)
914 if ((offset > -MAX_OFFSET) && (offset < MAX_OFFSET))
915 for (i=offset; i<offset+width; i++)
922 store1 = group->store1_n;
923 store2 = group->store2_n;
928 store1 = group->store1_p;
929 store2 = group->store2_p;
933 if (bitmap_bit_p (store1, ai))
934 bitmap_set_bit (store2, ai);
937 bitmap_set_bit (store1, ai);
940 if (group->offset_map_size_n < ai)
941 group->offset_map_size_n = ai;
945 if (group->offset_map_size_p < ai)
946 group->offset_map_size_p = ai;
953 /* Set the BB_INFO so that the last insn is marked as a wild read. */
956 add_wild_read (bb_info_t bb_info)
958 insn_info_t insn_info = bb_info->last_insn;
959 read_info_t *ptr = &insn_info->read_rec;
963 read_info_t next = (*ptr)->next;
964 if ((*ptr)->alias_set == 0)
966 pool_free (read_info_pool, *ptr);
972 insn_info->wild_read = true;
973 active_local_stores = NULL;
977 /* Return true if X is a constant or one of the registers that behave
978 as a constant over the life of a function. This is equivalent to
979 !rtx_varies_p for memory addresses. */
982 const_or_frame_p (rtx x)
984 switch (GET_CODE (x))
987 return MEM_READONLY_P (x);
998 /* Note that we have to test for the actual rtx used for the frame
999 and arg pointers and not just the register number in case we have
1000 eliminated the frame and/or arg pointer and are using it
1002 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
1003 /* The arg pointer varies if it is not a fixed register. */
1004 || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
1005 || x == pic_offset_table_rtx)
1014 /* Take all reasonable action to put the address of MEM into the form
1015 that we can do analysis on.
1017 The gold standard is to get the address into the form: address +
1018 OFFSET where address is something that rtx_varies_p considers a
1019 constant. When we can get the address in this form, we can do
1020 global analysis on it. Note that for constant bases, address is
1021 not actually returned, only the group_id. The address can be
1024 If that fails, we try cselib to get a value we can at least use
1025 locally. If that fails we return false.
1027 The GROUP_ID is set to -1 for cselib bases and the index of the
1028 group for non_varying bases.
1030 FOR_READ is true if this is a mem read and false if not. */
1033 canon_address (rtx mem,
1034 alias_set_type *alias_set_out,
1036 HOST_WIDE_INT *offset,
1039 rtx mem_address = XEXP (mem, 0);
1040 rtx expanded_address, address;
1041 /* Make sure that cselib is has initialized all of the operands of
1042 the address before asking it to do the subst. */
1044 if (clear_alias_sets)
1046 /* If this is a spill, do not do any further processing. */
1047 alias_set_type alias_set = MEM_ALIAS_SET (mem);
1049 fprintf (dump_file, "found alias set %d\n", (int) alias_set);
1050 if (bitmap_bit_p (clear_alias_sets, alias_set))
1052 struct clear_alias_mode_holder *entry
1053 = clear_alias_set_lookup (alias_set);
1055 /* If the modes do not match, we cannot process this set. */
1056 if (entry->mode != GET_MODE (mem))
1060 "disqualifying alias set %d, (%s) != (%s)\n",
1061 (int) alias_set, GET_MODE_NAME (entry->mode),
1062 GET_MODE_NAME (GET_MODE (mem)));
1064 bitmap_set_bit (disqualified_clear_alias_sets, alias_set);
1068 *alias_set_out = alias_set;
1069 *group_id = clear_alias_group->id;
1076 cselib_lookup (mem_address, Pmode, 1);
1080 fprintf (dump_file, " mem: ");
1081 print_inline_rtx (dump_file, mem_address, 0);
1082 fprintf (dump_file, "\n");
1085 /* Use cselib to replace all of the reg references with the full
1086 expression. This will take care of the case where we have
1088 r_x = base + offset;
1093 val = *(base + offset);
1096 expanded_address = cselib_expand_value_rtx (mem_address, scratch, 5);
1098 /* If this fails, just go with the mem_address. */
1099 if (!expanded_address)
1100 expanded_address = mem_address;
1102 /* Split the address into canonical BASE + OFFSET terms. */
1103 address = canon_rtx (expanded_address);
1109 fprintf (dump_file, "\n after cselib_expand address: ");
1110 print_inline_rtx (dump_file, expanded_address, 0);
1111 fprintf (dump_file, "\n");
1113 fprintf (dump_file, "\n after canon_rtx address: ");
1114 print_inline_rtx (dump_file, address, 0);
1115 fprintf (dump_file, "\n");
1118 if (GET_CODE (address) == CONST)
1119 address = XEXP (address, 0);
1121 if (GET_CODE (address) == PLUS && GET_CODE (XEXP (address, 1)) == CONST_INT)
1123 *offset = INTVAL (XEXP (address, 1));
1124 address = XEXP (address, 0);
1127 if (const_or_frame_p (address))
1129 group_info_t group = get_group_info (address);
1132 fprintf (dump_file, " gid=%d offset=%d \n", group->id, (int)*offset);
1134 *group_id = group->id;
1138 *base = cselib_lookup (address, Pmode, true);
1144 fprintf (dump_file, " no cselib val - should be a wild read.\n");
1148 fprintf (dump_file, " varying cselib base=%d offset = %d\n",
1149 (*base)->value, (int)*offset);
1155 /* Clear the rhs field from the active_local_stores array. */
1158 clear_rhs_from_active_local_stores (void)
1160 insn_info_t ptr = active_local_stores;
1164 store_info_t store_info = ptr->store_rec;
1165 /* Skip the clobbers. */
1166 while (!store_info->is_set)
1167 store_info = store_info->next;
1169 store_info->rhs = NULL;
1171 ptr = ptr->next_local_store;
1176 /* BODY is an instruction pattern that belongs to INSN. Return 1 if
1177 there is a candidate store, after adding it to the appropriate
1178 local store group if so. */
1181 record_store (rtx body, bb_info_t bb_info)
1184 HOST_WIDE_INT offset = 0;
1185 HOST_WIDE_INT width = 0;
1186 alias_set_type spill_alias_set;
1187 insn_info_t insn_info = bb_info->last_insn;
1188 store_info_t store_info = NULL;
1190 cselib_val *base = NULL;
1191 insn_info_t ptr, last;
1192 bool store_is_unused;
1194 if (GET_CODE (body) != SET && GET_CODE (body) != CLOBBER)
1197 /* If this is not used, then this cannot be used to keep the insn
1198 from being deleted. On the other hand, it does provide something
1199 that can be used to prove that another store is dead. */
1201 = (find_reg_note (insn_info->insn, REG_UNUSED, body) != NULL);
1203 /* Check whether that value is a suitable memory location. */
1204 mem = SET_DEST (body);
1207 /* If the set or clobber is unused, then it does not effect our
1208 ability to get rid of the entire insn. */
1209 if (!store_is_unused)
1210 insn_info->cannot_delete = true;
1214 /* At this point we know mem is a mem. */
1215 if (GET_MODE (mem) == BLKmode)
1217 if (GET_CODE (XEXP (mem, 0)) == SCRATCH)
1220 fprintf (dump_file, " adding wild read for (clobber (mem:BLK (scratch))\n");
1221 add_wild_read (bb_info);
1222 insn_info->cannot_delete = true;
1224 else if (!store_is_unused)
1226 /* If the set or clobber is unused, then it does not effect our
1227 ability to get rid of the entire insn. */
1228 insn_info->cannot_delete = true;
1229 clear_rhs_from_active_local_stores ();
1234 /* We can still process a volatile mem, we just cannot delete it. */
1235 if (MEM_VOLATILE_P (mem))
1236 insn_info->cannot_delete = true;
1238 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
1240 clear_rhs_from_active_local_stores ();
1244 width = GET_MODE_SIZE (GET_MODE (mem));
1246 if (spill_alias_set)
1248 bitmap store1 = clear_alias_group->store1_p;
1249 bitmap store2 = clear_alias_group->store2_p;
1251 if (bitmap_bit_p (store1, spill_alias_set))
1252 bitmap_set_bit (store2, spill_alias_set);
1254 bitmap_set_bit (store1, spill_alias_set);
1256 if (clear_alias_group->offset_map_size_p < spill_alias_set)
1257 clear_alias_group->offset_map_size_p = spill_alias_set;
1259 store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1262 fprintf (dump_file, " processing spill store %d(%s)\n",
1263 (int) spill_alias_set, GET_MODE_NAME (GET_MODE (mem)));
1265 else if (group_id >= 0)
1267 /* In the restrictive case where the base is a constant or the
1268 frame pointer we can do global analysis. */
1271 = VEC_index (group_info_t, rtx_group_vec, group_id);
1273 store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1274 set_usage_bits (group, offset, width);
1277 fprintf (dump_file, " processing const base store gid=%d[%d..%d)\n",
1278 group_id, (int)offset, (int)(offset+width));
1282 rtx base_term = find_base_term (XEXP (mem, 0));
1284 || (GET_CODE (base_term) == ADDRESS
1285 && GET_MODE (base_term) == Pmode
1286 && XEXP (base_term, 0) == stack_pointer_rtx))
1287 insn_info->stack_pointer_based = true;
1288 insn_info->contains_cselib_groups = true;
1290 store_info = (store_info_t) pool_alloc (cse_store_info_pool);
1294 fprintf (dump_file, " processing cselib store [%d..%d)\n",
1295 (int)offset, (int)(offset+width));
1298 /* Check to see if this stores causes some other stores to be
1300 ptr = active_local_stores;
1305 insn_info_t next = ptr->next_local_store;
1306 store_info_t s_info = ptr->store_rec;
1309 /* Skip the clobbers. We delete the active insn if this insn
1310 shadows the set. To have been put on the active list, it
1311 has exactly on set. */
1312 while (!s_info->is_set)
1313 s_info = s_info->next;
1315 if (s_info->alias_set != spill_alias_set)
1317 else if (s_info->alias_set)
1319 struct clear_alias_mode_holder *entry
1320 = clear_alias_set_lookup (s_info->alias_set);
1321 /* Generally, spills cannot be processed if and of the
1322 references to the slot have a different mode. But if
1323 we are in the same block and mode is exactly the same
1324 between this store and one before in the same block,
1325 we can still delete it. */
1326 if ((GET_MODE (mem) == GET_MODE (s_info->mem))
1327 && (GET_MODE (mem) == entry->mode))
1330 s_info->positions_needed = (unsigned HOST_WIDE_INT) 0;
1333 fprintf (dump_file, " trying spill store in insn=%d alias_set=%d\n",
1334 INSN_UID (ptr->insn), (int) s_info->alias_set);
1336 else if ((s_info->group_id == group_id)
1337 && (s_info->cse_base == base))
1341 fprintf (dump_file, " trying store in insn=%d gid=%d[%d..%d)\n",
1342 INSN_UID (ptr->insn), s_info->group_id,
1343 (int)s_info->begin, (int)s_info->end);
1344 for (i = offset; i < offset+width; i++)
1345 if (i >= s_info->begin && i < s_info->end)
1346 s_info->positions_needed
1347 &= ~(((unsigned HOST_WIDE_INT) 1) << (i - s_info->begin));
1349 else if (s_info->rhs)
1350 /* Need to see if it is possible for this store to overwrite
1351 the value of store_info. If it is, set the rhs to NULL to
1352 keep it from being used to remove a load. */
1354 if (canon_true_dependence (s_info->mem,
1355 GET_MODE (s_info->mem),
1361 /* An insn can be deleted if every position of every one of
1362 its s_infos is zero. */
1363 if (s_info->positions_needed != (unsigned HOST_WIDE_INT) 0)
1368 insn_info_t insn_to_delete = ptr;
1371 last->next_local_store = ptr->next_local_store;
1373 active_local_stores = ptr->next_local_store;
1375 delete_dead_store_insn (insn_to_delete);
1383 gcc_assert ((unsigned) width <= HOST_BITS_PER_WIDE_INT);
1385 /* Finish filling in the store_info. */
1386 store_info->next = insn_info->store_rec;
1387 insn_info->store_rec = store_info;
1388 store_info->mem = canon_rtx (mem);
1389 store_info->alias_set = spill_alias_set;
1390 store_info->mem_addr = get_addr (XEXP (mem, 0));
1391 store_info->cse_base = base;
1392 store_info->positions_needed = lowpart_bitmask (width);
1393 store_info->group_id = group_id;
1394 store_info->begin = offset;
1395 store_info->end = offset + width;
1396 store_info->is_set = GET_CODE (body) == SET;
1398 if (store_info->is_set
1399 /* No place to keep the value after ra. */
1400 && !reload_completed
1401 && (REG_P (SET_SRC (body))
1402 || GET_CODE (SET_SRC (body)) == SUBREG
1403 || CONSTANT_P (SET_SRC (body)))
1404 /* Sometimes the store and reload is used for truncation and
1406 && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
1407 store_info->rhs = SET_SRC (body);
1409 store_info->rhs = NULL;
1411 /* If this is a clobber, we return 0. We will only be able to
1412 delete this insn if there is only one store USED store, but we
1413 can use the clobber to delete other stores earlier. */
1414 return store_info->is_set ? 1 : 0;
1419 dump_insn_info (const char * start, insn_info_t insn_info)
1421 fprintf (dump_file, "%s insn=%d %s\n", start,
1422 INSN_UID (insn_info->insn),
1423 insn_info->store_rec ? "has store" : "naked");
1427 /* If the modes are different and the value's source and target do not
1428 line up, we need to extract the value from lower part of the rhs of
1429 the store, shift it, and then put it into a form that can be shoved
1430 into the read_insn. This function generates a right SHIFT of a
1431 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The
1432 shift sequence is returned or NULL if we failed to find a
1436 find_shift_sequence (int access_size,
1437 store_info_t store_info,
1438 read_info_t read_info,
1442 enum machine_mode store_mode = GET_MODE (store_info->mem);
1443 enum machine_mode read_mode = GET_MODE (read_info->mem);
1444 enum machine_mode new_mode;
1445 rtx read_reg = NULL;
1447 /* Some machines like the x86 have shift insns for each size of
1448 operand. Other machines like the ppc or the ia-64 may only have
1449 shift insns that shift values within 32 or 64 bit registers.
1450 This loop tries to find the smallest shift insn that will right
1451 justify the value we want to read but is available in one insn on
1454 for (new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
1456 GET_MODE_BITSIZE (new_mode) <= BITS_PER_WORD;
1457 new_mode = GET_MODE_WIDER_MODE (new_mode))
1459 rtx target, new_reg, shift_seq, insn, new_lhs;
1462 /* If a constant was stored into memory, try to simplify it here,
1463 otherwise the cost of the shift might preclude this optimization
1464 e.g. at -Os, even when no actual shift will be needed. */
1465 if (CONSTANT_P (store_info->rhs))
1467 unsigned int byte = subreg_lowpart_offset (new_mode, store_mode);
1468 rtx ret = simplify_subreg (new_mode, store_info->rhs, store_mode,
1470 if (ret && CONSTANT_P (ret))
1472 ret = simplify_const_binary_operation (LSHIFTRT, new_mode,
1473 ret, GEN_INT (shift));
1474 if (ret && CONSTANT_P (ret))
1476 byte = subreg_lowpart_offset (read_mode, new_mode);
1477 ret = simplify_subreg (read_mode, ret, new_mode, byte);
1478 if (ret && CONSTANT_P (ret)
1479 && rtx_cost (ret, SET, speed) <= COSTS_N_INSNS (1))
1485 /* Try a wider mode if truncating the store mode to NEW_MODE
1486 requires a real instruction. */
1487 if (GET_MODE_BITSIZE (new_mode) < GET_MODE_BITSIZE (store_mode)
1488 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (new_mode),
1489 GET_MODE_BITSIZE (store_mode)))
1492 /* Also try a wider mode if the necessary punning is either not
1493 desirable or not possible. */
1494 if (!CONSTANT_P (store_info->rhs)
1495 && !MODES_TIEABLE_P (new_mode, store_mode))
1498 new_reg = gen_reg_rtx (new_mode);
1502 /* In theory we could also check for an ashr. Ian Taylor knows
1503 of one dsp where the cost of these two was not the same. But
1504 this really is a rare case anyway. */
1505 target = expand_binop (new_mode, lshr_optab, new_reg,
1506 GEN_INT (shift), new_reg, 1, OPTAB_DIRECT);
1508 shift_seq = get_insns ();
1511 if (target != new_reg || shift_seq == NULL)
1515 for (insn = shift_seq; insn != NULL_RTX; insn = NEXT_INSN (insn))
1517 cost += insn_rtx_cost (PATTERN (insn), speed);
1519 /* The computation up to here is essentially independent
1520 of the arguments and could be precomputed. It may
1521 not be worth doing so. We could precompute if
1522 worthwhile or at least cache the results. The result
1523 technically depends on both SHIFT and ACCESS_SIZE,
1524 but in practice the answer will depend only on ACCESS_SIZE. */
1526 if (cost > COSTS_N_INSNS (1))
1529 new_lhs = extract_low_bits (new_mode, store_mode,
1530 copy_rtx (store_info->rhs));
1531 if (new_lhs == NULL_RTX)
1534 /* We found an acceptable shift. Generate a move to
1535 take the value from the store and put it into the
1536 shift pseudo, then shift it, then generate another
1537 move to put in into the target of the read. */
1538 emit_move_insn (new_reg, new_lhs);
1539 emit_insn (shift_seq);
1540 read_reg = extract_low_bits (read_mode, new_mode, new_reg);
1548 /* Call back for note_stores to find the hard regs set or clobbered by
1549 insn. Data is a bitmap of the hardregs set so far. */
1552 look_for_hardregs (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
1554 bitmap regs_set = (bitmap) data;
1557 && REGNO (x) < FIRST_PSEUDO_REGISTER)
1559 int regno = REGNO (x);
1560 int n = hard_regno_nregs[regno][GET_MODE (x)];
1562 bitmap_set_bit (regs_set, regno + n);
1567 /* Take a sequence of:
1590 Depending on the alignment and the mode of the store and
1594 The STORE_INFO and STORE_INSN are for the store and READ_INFO
1595 and READ_INSN are for the read. Return true if the replacement
1599 replace_read (store_info_t store_info, insn_info_t store_insn,
1600 read_info_t read_info, insn_info_t read_insn, rtx *loc, bitmap regs_live)
1602 enum machine_mode store_mode = GET_MODE (store_info->mem);
1603 enum machine_mode read_mode = GET_MODE (read_info->mem);
1605 int access_size; /* In bytes. */
1606 rtx insns, this_insn, read_reg;
1611 /* To get here the read is within the boundaries of the write so
1612 shift will never be negative. Start out with the shift being in
1614 if (BYTES_BIG_ENDIAN)
1615 shift = store_info->end - read_info->end;
1617 shift = read_info->begin - store_info->begin;
1619 access_size = shift + GET_MODE_SIZE (read_mode);
1621 /* From now on it is bits. */
1622 shift *= BITS_PER_UNIT;
1624 /* Create a sequence of instructions to set up the read register.
1625 This sequence goes immediately before the store and its result
1626 is read by the load.
1628 We need to keep this in perspective. We are replacing a read
1629 with a sequence of insns, but the read will almost certainly be
1630 in cache, so it is not going to be an expensive one. Thus, we
1631 are not willing to do a multi insn shift or worse a subroutine
1632 call to get rid of the read. */
1634 fprintf (dump_file, "trying to replace %smode load in insn %d"
1635 " from %smode store in insn %d\n",
1636 GET_MODE_NAME (read_mode), INSN_UID (read_insn->insn),
1637 GET_MODE_NAME (store_mode), INSN_UID (store_insn->insn));
1640 read_reg = find_shift_sequence (access_size, store_info, read_info, shift,
1641 optimize_bb_for_speed_p (BLOCK_FOR_INSN (read_insn->insn)));
1643 read_reg = extract_low_bits (read_mode, store_mode,
1644 copy_rtx (store_info->rhs));
1645 if (read_reg == NULL_RTX)
1649 fprintf (dump_file, " -- could not extract bits of stored value\n");
1652 /* Force the value into a new register so that it won't be clobbered
1653 between the store and the load. */
1654 read_reg = copy_to_mode_reg (read_mode, read_reg);
1655 insns = get_insns ();
1658 if (insns != NULL_RTX)
1660 /* Now we have to scan the set of new instructions to see if the
1661 sequence contains and sets of hardregs that happened to be
1662 live at this point. For instance, this can happen if one of
1663 the insns sets the CC and the CC happened to be live at that
1664 point. This does occasionally happen, see PR 37922. */
1665 bitmap regs_set = BITMAP_ALLOC (NULL);
1667 for (this_insn = insns; this_insn != NULL_RTX; this_insn = NEXT_INSN (this_insn))
1668 note_stores (PATTERN (this_insn), look_for_hardregs, regs_set);
1670 bitmap_and_into (regs_set, regs_live);
1671 if (!bitmap_empty_p (regs_set))
1676 "abandoning replacement because sequence clobbers live hardregs:");
1677 df_print_regset (dump_file, regs_set);
1680 BITMAP_FREE (regs_set);
1683 BITMAP_FREE (regs_set);
1686 if (validate_change (read_insn->insn, loc, read_reg, 0))
1688 deferred_change_t deferred_change =
1689 (deferred_change_t) pool_alloc (deferred_change_pool);
1691 /* Insert this right before the store insn where it will be safe
1692 from later insns that might change it before the read. */
1693 emit_insn_before (insns, store_insn->insn);
1695 /* And now for the kludge part: cselib croaks if you just
1696 return at this point. There are two reasons for this:
1698 1) Cselib has an idea of how many pseudos there are and
1699 that does not include the new ones we just added.
1701 2) Cselib does not know about the move insn we added
1702 above the store_info, and there is no way to tell it
1703 about it, because it has "moved on".
1705 Problem (1) is fixable with a certain amount of engineering.
1706 Problem (2) is requires starting the bb from scratch. This
1709 So we are just going to have to lie. The move/extraction
1710 insns are not really an issue, cselib did not see them. But
1711 the use of the new pseudo read_insn is a real problem because
1712 cselib has not scanned this insn. The way that we solve this
1713 problem is that we are just going to put the mem back for now
1714 and when we are finished with the block, we undo this. We
1715 keep a table of mems to get rid of. At the end of the basic
1716 block we can put them back. */
1718 *loc = read_info->mem;
1719 deferred_change->next = deferred_change_list;
1720 deferred_change_list = deferred_change;
1721 deferred_change->loc = loc;
1722 deferred_change->reg = read_reg;
1724 /* Get rid of the read_info, from the point of view of the
1725 rest of dse, play like this read never happened. */
1726 read_insn->read_rec = read_info->next;
1727 pool_free (read_info_pool, read_info);
1730 fprintf (dump_file, " -- replaced the loaded MEM with ");
1731 print_simple_rtl (dump_file, read_reg);
1732 fprintf (dump_file, "\n");
1740 fprintf (dump_file, " -- replacing the loaded MEM with ");
1741 print_simple_rtl (dump_file, read_reg);
1742 fprintf (dump_file, " led to an invalid instruction\n");
1748 /* A for_each_rtx callback in which DATA is the bb_info. Check to see
1749 if LOC is a mem and if it is look at the address and kill any
1750 appropriate stores that may be active. */
1753 check_mem_read_rtx (rtx *loc, void *data)
1757 insn_info_t insn_info;
1758 HOST_WIDE_INT offset = 0;
1759 HOST_WIDE_INT width = 0;
1760 alias_set_type spill_alias_set = 0;
1761 cselib_val *base = NULL;
1763 read_info_t read_info;
1765 if (!mem || !MEM_P (mem))
1768 bb_info = (bb_info_t) data;
1769 insn_info = bb_info->last_insn;
1771 if ((MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
1772 || (MEM_VOLATILE_P (mem)))
1775 fprintf (dump_file, " adding wild read, volatile or barrier.\n");
1776 add_wild_read (bb_info);
1777 insn_info->cannot_delete = true;
1781 /* If it is reading readonly mem, then there can be no conflict with
1783 if (MEM_READONLY_P (mem))
1786 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
1789 fprintf (dump_file, " adding wild read, canon_address failure.\n");
1790 add_wild_read (bb_info);
1794 if (GET_MODE (mem) == BLKmode)
1797 width = GET_MODE_SIZE (GET_MODE (mem));
1799 read_info = (read_info_t) pool_alloc (read_info_pool);
1800 read_info->group_id = group_id;
1801 read_info->mem = mem;
1802 read_info->alias_set = spill_alias_set;
1803 read_info->begin = offset;
1804 read_info->end = offset + width;
1805 read_info->next = insn_info->read_rec;
1806 insn_info->read_rec = read_info;
1808 /* We ignore the clobbers in store_info. The is mildly aggressive,
1809 but there really should not be a clobber followed by a read. */
1811 if (spill_alias_set)
1813 insn_info_t i_ptr = active_local_stores;
1814 insn_info_t last = NULL;
1817 fprintf (dump_file, " processing spill load %d\n",
1818 (int) spill_alias_set);
1822 store_info_t store_info = i_ptr->store_rec;
1824 /* Skip the clobbers. */
1825 while (!store_info->is_set)
1826 store_info = store_info->next;
1828 if (store_info->alias_set == spill_alias_set)
1831 dump_insn_info ("removing from active", i_ptr);
1834 last->next_local_store = i_ptr->next_local_store;
1836 active_local_stores = i_ptr->next_local_store;
1840 i_ptr = i_ptr->next_local_store;
1843 else if (group_id >= 0)
1845 /* This is the restricted case where the base is a constant or
1846 the frame pointer and offset is a constant. */
1847 insn_info_t i_ptr = active_local_stores;
1848 insn_info_t last = NULL;
1853 fprintf (dump_file, " processing const load gid=%d[BLK]\n",
1856 fprintf (dump_file, " processing const load gid=%d[%d..%d)\n",
1857 group_id, (int)offset, (int)(offset+width));
1862 bool remove = false;
1863 store_info_t store_info = i_ptr->store_rec;
1865 /* Skip the clobbers. */
1866 while (!store_info->is_set)
1867 store_info = store_info->next;
1869 /* There are three cases here. */
1870 if (store_info->group_id < 0)
1871 /* We have a cselib store followed by a read from a
1874 = canon_true_dependence (store_info->mem,
1875 GET_MODE (store_info->mem),
1876 store_info->mem_addr,
1879 else if (group_id == store_info->group_id)
1881 /* This is a block mode load. We may get lucky and
1882 canon_true_dependence may save the day. */
1885 = canon_true_dependence (store_info->mem,
1886 GET_MODE (store_info->mem),
1887 store_info->mem_addr,
1890 /* If this read is just reading back something that we just
1891 stored, rewrite the read. */
1895 && (offset >= store_info->begin)
1896 && (offset + width <= store_info->end))
1898 unsigned HOST_WIDE_INT mask
1899 = (lowpart_bitmask (width)
1900 << (offset - store_info->begin));
1902 if ((store_info->positions_needed & mask) == mask
1903 && replace_read (store_info, i_ptr,
1904 read_info, insn_info, loc, bb_info->regs_live))
1907 /* The bases are the same, just see if the offsets
1909 if ((offset < store_info->end)
1910 && (offset + width > store_info->begin))
1916 The else case that is missing here is that the
1917 bases are constant but different. There is nothing
1918 to do here because there is no overlap. */
1923 dump_insn_info ("removing from active", i_ptr);
1926 last->next_local_store = i_ptr->next_local_store;
1928 active_local_stores = i_ptr->next_local_store;
1932 i_ptr = i_ptr->next_local_store;
1937 insn_info_t i_ptr = active_local_stores;
1938 insn_info_t last = NULL;
1941 fprintf (dump_file, " processing cselib load mem:");
1942 print_inline_rtx (dump_file, mem, 0);
1943 fprintf (dump_file, "\n");
1948 bool remove = false;
1949 store_info_t store_info = i_ptr->store_rec;
1952 fprintf (dump_file, " processing cselib load against insn %d\n",
1953 INSN_UID (i_ptr->insn));
1955 /* Skip the clobbers. */
1956 while (!store_info->is_set)
1957 store_info = store_info->next;
1959 /* If this read is just reading back something that we just
1960 stored, rewrite the read. */
1962 && store_info->group_id == -1
1963 && store_info->cse_base == base
1964 && (offset >= store_info->begin)
1965 && (offset + width <= store_info->end))
1967 unsigned HOST_WIDE_INT mask
1968 = (lowpart_bitmask (width)
1969 << (offset - store_info->begin));
1971 if ((store_info->positions_needed & mask) == mask
1972 && replace_read (store_info, i_ptr,
1973 read_info, insn_info, loc, bb_info->regs_live))
1977 if (!store_info->alias_set)
1978 remove = canon_true_dependence (store_info->mem,
1979 GET_MODE (store_info->mem),
1980 store_info->mem_addr,
1986 dump_insn_info ("removing from active", i_ptr);
1989 last->next_local_store = i_ptr->next_local_store;
1991 active_local_stores = i_ptr->next_local_store;
1995 i_ptr = i_ptr->next_local_store;
2001 /* A for_each_rtx callback in which DATA points the INSN_INFO for
2002 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
2003 true for any part of *LOC. */
2006 check_mem_read_use (rtx *loc, void *data)
2008 for_each_rtx (loc, check_mem_read_rtx, data);
2011 /* Apply record_store to all candidate stores in INSN. Mark INSN
2012 if some part of it is not a candidate store and assigns to a
2013 non-register target. */
2016 scan_insn (bb_info_t bb_info, rtx insn)
2019 insn_info_t insn_info = (insn_info_t) pool_alloc (insn_info_pool);
2021 memset (insn_info, 0, sizeof (struct insn_info));
2024 fprintf (dump_file, "\n**scanning insn=%d\n",
2027 insn_info->prev_insn = bb_info->last_insn;
2028 insn_info->insn = insn;
2029 bb_info->last_insn = insn_info;
2032 /* Cselib clears the table for this case, so we have to essentially
2034 if (NONJUMP_INSN_P (insn)
2035 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
2036 && MEM_VOLATILE_P (PATTERN (insn)))
2038 add_wild_read (bb_info);
2039 insn_info->cannot_delete = true;
2043 /* Look at all of the uses in the insn. */
2044 note_uses (&PATTERN (insn), check_mem_read_use, bb_info);
2048 insn_info->cannot_delete = true;
2050 /* Const functions cannot do anything bad i.e. read memory,
2051 however, they can read their parameters which may have
2052 been pushed onto the stack. */
2053 if (RTL_CONST_CALL_P (insn))
2055 insn_info_t i_ptr = active_local_stores;
2056 insn_info_t last = NULL;
2059 fprintf (dump_file, "const call %d\n", INSN_UID (insn));
2061 /* See the head comment of the frame_read field. */
2062 if (reload_completed)
2063 insn_info->frame_read = true;
2065 /* Loop over the active stores and remove those which are
2066 killed by the const function call. */
2069 bool remove_store = false;
2071 /* The stack pointer based stores are always killed. */
2072 if (i_ptr->stack_pointer_based)
2073 remove_store = true;
2075 /* If the frame is read, the frame related stores are killed. */
2076 else if (insn_info->frame_read)
2078 store_info_t store_info = i_ptr->store_rec;
2080 /* Skip the clobbers. */
2081 while (!store_info->is_set)
2082 store_info = store_info->next;
2084 if (store_info->group_id >= 0
2085 && VEC_index (group_info_t, rtx_group_vec,
2086 store_info->group_id)->frame_related)
2087 remove_store = true;
2093 dump_insn_info ("removing from active", i_ptr);
2096 last->next_local_store = i_ptr->next_local_store;
2098 active_local_stores = i_ptr->next_local_store;
2103 i_ptr = i_ptr->next_local_store;
2108 /* Every other call, including pure functions, may read memory. */
2109 add_wild_read (bb_info);
2114 /* Assuming that there are sets in these insns, we cannot delete
2116 if ((GET_CODE (PATTERN (insn)) == CLOBBER)
2117 || volatile_refs_p (PATTERN (insn))
2118 || (flag_non_call_exceptions && may_trap_p (PATTERN (insn)))
2119 || (RTX_FRAME_RELATED_P (insn))
2120 || find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX))
2121 insn_info->cannot_delete = true;
2123 body = PATTERN (insn);
2124 if (GET_CODE (body) == PARALLEL)
2127 for (i = 0; i < XVECLEN (body, 0); i++)
2128 mems_found += record_store (XVECEXP (body, 0, i), bb_info);
2131 mems_found += record_store (body, bb_info);
2134 fprintf (dump_file, "mems_found = %d, cannot_delete = %s\n",
2135 mems_found, insn_info->cannot_delete ? "true" : "false");
2137 /* If we found some sets of mems, and the insn has not been marked
2138 cannot delete, add it into the active_local_stores so that it can
2139 be locally deleted if found dead. Otherwise mark it as cannot
2140 delete. This simplifies the processing later. */
2141 if (mems_found == 1 && !insn_info->cannot_delete)
2143 insn_info->next_local_store = active_local_stores;
2144 active_local_stores = insn_info;
2147 insn_info->cannot_delete = true;
2151 /* Remove BASE from the set of active_local_stores. This is a
2152 callback from cselib that is used to get rid of the stores in
2153 active_local_stores. */
2156 remove_useless_values (cselib_val *base)
2158 insn_info_t insn_info = active_local_stores;
2159 insn_info_t last = NULL;
2163 store_info_t store_info = insn_info->store_rec;
2166 /* If ANY of the store_infos match the cselib group that is
2167 being deleted, then the insn can not be deleted. */
2170 if ((store_info->group_id == -1)
2171 && (store_info->cse_base == base))
2176 store_info = store_info->next;
2182 last->next_local_store = insn_info->next_local_store;
2184 active_local_stores = insn_info->next_local_store;
2185 free_store_info (insn_info);
2190 insn_info = insn_info->next_local_store;
2195 /* Do all of step 1. */
2201 bitmap regs_live = BITMAP_ALLOC (NULL);
2203 cselib_init (false);
2204 all_blocks = BITMAP_ALLOC (NULL);
2205 bitmap_set_bit (all_blocks, ENTRY_BLOCK);
2206 bitmap_set_bit (all_blocks, EXIT_BLOCK);
2211 bb_info_t bb_info = (bb_info_t) pool_alloc (bb_info_pool);
2213 memset (bb_info, 0, sizeof (struct bb_info));
2214 bitmap_set_bit (all_blocks, bb->index);
2215 bb_info->regs_live = regs_live;
2217 bitmap_copy (regs_live, DF_LR_IN (bb));
2218 df_simulate_initialize_forwards (bb, regs_live);
2220 bb_table[bb->index] = bb_info;
2221 cselib_discard_hook = remove_useless_values;
2223 if (bb->index >= NUM_FIXED_BLOCKS)
2228 = create_alloc_pool ("cse_store_info_pool",
2229 sizeof (struct store_info), 100);
2230 active_local_stores = NULL;
2231 cselib_clear_table ();
2233 /* Scan the insns. */
2234 FOR_BB_INSNS (bb, insn)
2237 scan_insn (bb_info, insn);
2238 cselib_process_insn (insn);
2240 df_simulate_one_insn_forwards (bb, insn, regs_live);
2243 /* This is something of a hack, because the global algorithm
2244 is supposed to take care of the case where stores go dead
2245 at the end of the function. However, the global
2246 algorithm must take a more conservative view of block
2247 mode reads than the local alg does. So to get the case
2248 where you have a store to the frame followed by a non
2249 overlapping block more read, we look at the active local
2250 stores at the end of the function and delete all of the
2251 frame and spill based ones. */
2252 if (stores_off_frame_dead_at_return
2253 && (EDGE_COUNT (bb->succs) == 0
2254 || (single_succ_p (bb)
2255 && single_succ (bb) == EXIT_BLOCK_PTR
2256 && ! crtl->calls_eh_return)))
2258 insn_info_t i_ptr = active_local_stores;
2261 store_info_t store_info = i_ptr->store_rec;
2263 /* Skip the clobbers. */
2264 while (!store_info->is_set)
2265 store_info = store_info->next;
2266 if (store_info->alias_set)
2267 delete_dead_store_insn (i_ptr);
2269 if (store_info->group_id >= 0)
2272 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
2273 if (group->frame_related)
2274 delete_dead_store_insn (i_ptr);
2277 i_ptr = i_ptr->next_local_store;
2281 /* Get rid of the loads that were discovered in
2282 replace_read. Cselib is finished with this block. */
2283 while (deferred_change_list)
2285 deferred_change_t next = deferred_change_list->next;
2287 /* There is no reason to validate this change. That was
2289 *deferred_change_list->loc = deferred_change_list->reg;
2290 pool_free (deferred_change_pool, deferred_change_list);
2291 deferred_change_list = next;
2294 /* Get rid of all of the cselib based store_infos in this
2295 block and mark the containing insns as not being
2297 ptr = bb_info->last_insn;
2300 if (ptr->contains_cselib_groups)
2301 free_store_info (ptr);
2302 ptr = ptr->prev_insn;
2305 free_alloc_pool (cse_store_info_pool);
2307 bb_info->regs_live = NULL;
2310 BITMAP_FREE (regs_live);
2312 htab_empty (rtx_group_table);
2316 /*----------------------------------------------------------------------------
2319 Assign each byte position in the stores that we are going to
2320 analyze globally to a position in the bitmaps. Returns true if
2321 there are any bit positions assigned.
2322 ----------------------------------------------------------------------------*/
2325 dse_step2_init (void)
2330 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2332 /* For all non stack related bases, we only consider a store to
2333 be deletable if there are two or more stores for that
2334 position. This is because it takes one store to make the
2335 other store redundant. However, for the stores that are
2336 stack related, we consider them if there is only one store
2337 for the position. We do this because the stack related
2338 stores can be deleted if their is no read between them and
2339 the end of the function.
2341 To make this work in the current framework, we take the stack
2342 related bases add all of the bits from store1 into store2.
2343 This has the effect of making the eligible even if there is
2346 if (stores_off_frame_dead_at_return && group->frame_related)
2348 bitmap_ior_into (group->store2_n, group->store1_n);
2349 bitmap_ior_into (group->store2_p, group->store1_p);
2351 fprintf (dump_file, "group %d is frame related ", i);
2354 group->offset_map_size_n++;
2355 group->offset_map_n = XNEWVEC (int, group->offset_map_size_n);
2356 group->offset_map_size_p++;
2357 group->offset_map_p = XNEWVEC (int, group->offset_map_size_p);
2358 group->process_globally = false;
2361 fprintf (dump_file, "group %d(%d+%d): ", i,
2362 (int)bitmap_count_bits (group->store2_n),
2363 (int)bitmap_count_bits (group->store2_p));
2364 bitmap_print (dump_file, group->store2_n, "n ", " ");
2365 bitmap_print (dump_file, group->store2_p, "p ", "\n");
2371 /* Init the offset tables for the normal case. */
2374 dse_step2_nospill (void)
2378 /* Position 0 is unused because 0 is used in the maps to mean
2380 current_position = 1;
2382 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2387 if (group == clear_alias_group)
2390 memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2391 memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2392 bitmap_clear (group->group_kill);
2394 EXECUTE_IF_SET_IN_BITMAP (group->store2_n, 0, j, bi)
2396 bitmap_set_bit (group->group_kill, current_position);
2397 group->offset_map_n[j] = current_position++;
2398 group->process_globally = true;
2400 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2402 bitmap_set_bit (group->group_kill, current_position);
2403 group->offset_map_p[j] = current_position++;
2404 group->process_globally = true;
2407 return current_position != 1;
2411 /* Init the offset tables for the spill case. */
2414 dse_step2_spill (void)
2417 group_info_t group = clear_alias_group;
2420 /* Position 0 is unused because 0 is used in the maps to mean
2422 current_position = 1;
2426 bitmap_print (dump_file, clear_alias_sets,
2427 "clear alias sets ", "\n");
2428 bitmap_print (dump_file, disqualified_clear_alias_sets,
2429 "disqualified clear alias sets ", "\n");
2432 memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2433 memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2434 bitmap_clear (group->group_kill);
2436 /* Remove the disqualified positions from the store2_p set. */
2437 bitmap_and_compl_into (group->store2_p, disqualified_clear_alias_sets);
2439 /* We do not need to process the store2_n set because
2440 alias_sets are always positive. */
2441 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2443 bitmap_set_bit (group->group_kill, current_position);
2444 group->offset_map_p[j] = current_position++;
2445 group->process_globally = true;
2448 return current_position != 1;
2453 /*----------------------------------------------------------------------------
2456 Build the bit vectors for the transfer functions.
2457 ----------------------------------------------------------------------------*/
2460 /* Note that this is NOT a general purpose function. Any mem that has
2461 an alias set registered here expected to be COMPLETELY unaliased:
2462 i.e it's addresses are not and need not be examined.
2464 It is known that all references to this address will have this
2465 alias set and there are NO other references to this address in the
2468 Currently the only place that is known to be clean enough to use
2469 this interface is the code that assigns the spill locations.
2471 All of the mems that have alias_sets registered are subjected to a
2472 very powerful form of dse where function calls, volatile reads and
2473 writes, and reads from random location are not taken into account.
2475 It is also assumed that these locations go dead when the function
2476 returns. This assumption could be relaxed if there were found to
2477 be places that this assumption was not correct.
2479 The MODE is passed in and saved. The mode of each load or store to
2480 a mem with ALIAS_SET is checked against MEM. If the size of that
2481 load or store is different from MODE, processing is halted on this
2482 alias set. For the vast majority of aliases sets, all of the loads
2483 and stores will use the same mode. But vectors are treated
2484 differently: the alias set is established for the entire vector,
2485 but reload will insert loads and stores for individual elements and
2486 we do not necessarily have the information to track those separate
2487 elements. So when we see a mode mismatch, we just bail. */
2491 dse_record_singleton_alias_set (alias_set_type alias_set,
2492 enum machine_mode mode)
2494 struct clear_alias_mode_holder tmp_holder;
2495 struct clear_alias_mode_holder *entry;
2498 /* If we are not going to run dse, we need to return now or there
2499 will be problems with allocating the bitmaps. */
2500 if ((!gate_dse()) || !alias_set)
2503 if (!clear_alias_sets)
2505 clear_alias_sets = BITMAP_ALLOC (NULL);
2506 disqualified_clear_alias_sets = BITMAP_ALLOC (NULL);
2507 clear_alias_mode_table = htab_create (11, clear_alias_mode_hash,
2508 clear_alias_mode_eq, NULL);
2509 clear_alias_mode_pool = create_alloc_pool ("clear_alias_mode_pool",
2510 sizeof (struct clear_alias_mode_holder), 100);
2513 bitmap_set_bit (clear_alias_sets, alias_set);
2515 tmp_holder.alias_set = alias_set;
2517 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, INSERT);
2518 gcc_assert (*slot == NULL);
2521 (struct clear_alias_mode_holder *) pool_alloc (clear_alias_mode_pool);
2522 entry->alias_set = alias_set;
2527 /* Remove ALIAS_SET from the sets of stack slots being considered. */
2530 dse_invalidate_singleton_alias_set (alias_set_type alias_set)
2532 if ((!gate_dse()) || !alias_set)
2535 bitmap_clear_bit (clear_alias_sets, alias_set);
2539 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
2543 get_bitmap_index (group_info_t group_info, HOST_WIDE_INT offset)
2547 HOST_WIDE_INT offset_p = -offset;
2548 if (offset_p >= group_info->offset_map_size_n)
2550 return group_info->offset_map_n[offset_p];
2554 if (offset >= group_info->offset_map_size_p)
2556 return group_info->offset_map_p[offset];
2561 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
2565 scan_stores_nospill (store_info_t store_info, bitmap gen, bitmap kill)
2570 group_info_t group_info
2571 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
2572 if (group_info->process_globally)
2573 for (i = store_info->begin; i < store_info->end; i++)
2575 int index = get_bitmap_index (group_info, i);
2578 bitmap_set_bit (gen, index);
2580 bitmap_clear_bit (kill, index);
2583 store_info = store_info->next;
2588 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
2592 scan_stores_spill (store_info_t store_info, bitmap gen, bitmap kill)
2596 if (store_info->alias_set)
2598 int index = get_bitmap_index (clear_alias_group,
2599 store_info->alias_set);
2602 bitmap_set_bit (gen, index);
2604 bitmap_clear_bit (kill, index);
2607 store_info = store_info->next;
2612 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
2616 scan_reads_nospill (insn_info_t insn_info, bitmap gen, bitmap kill)
2618 read_info_t read_info = insn_info->read_rec;
2622 /* If this insn reads the frame, kill all the frame related stores. */
2623 if (insn_info->frame_read)
2625 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2626 if (group->process_globally && group->frame_related)
2629 bitmap_ior_into (kill, group->group_kill);
2630 bitmap_and_compl_into (gen, group->group_kill);
2636 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2638 if (group->process_globally)
2640 if (i == read_info->group_id)
2642 if (read_info->begin > read_info->end)
2644 /* Begin > end for block mode reads. */
2646 bitmap_ior_into (kill, group->group_kill);
2647 bitmap_and_compl_into (gen, group->group_kill);
2651 /* The groups are the same, just process the
2654 for (j = read_info->begin; j < read_info->end; j++)
2656 int index = get_bitmap_index (group, j);
2660 bitmap_set_bit (kill, index);
2661 bitmap_clear_bit (gen, index);
2668 /* The groups are different, if the alias sets
2669 conflict, clear the entire group. We only need
2670 to apply this test if the read_info is a cselib
2671 read. Anything with a constant base cannot alias
2672 something else with a different constant
2674 if ((read_info->group_id < 0)
2675 && canon_true_dependence (group->base_mem,
2677 group->canon_base_mem,
2678 read_info->mem, rtx_varies_p))
2681 bitmap_ior_into (kill, group->group_kill);
2682 bitmap_and_compl_into (gen, group->group_kill);
2688 read_info = read_info->next;
2692 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
2696 scan_reads_spill (read_info_t read_info, bitmap gen, bitmap kill)
2700 if (read_info->alias_set)
2702 int index = get_bitmap_index (clear_alias_group,
2703 read_info->alias_set);
2707 bitmap_set_bit (kill, index);
2708 bitmap_clear_bit (gen, index);
2712 read_info = read_info->next;
2717 /* Return the insn in BB_INFO before the first wild read or if there
2718 are no wild reads in the block, return the last insn. */
2721 find_insn_before_first_wild_read (bb_info_t bb_info)
2723 insn_info_t insn_info = bb_info->last_insn;
2724 insn_info_t last_wild_read = NULL;
2728 if (insn_info->wild_read)
2730 last_wild_read = insn_info->prev_insn;
2731 /* Block starts with wild read. */
2732 if (!last_wild_read)
2736 insn_info = insn_info->prev_insn;
2740 return last_wild_read;
2742 return bb_info->last_insn;
2746 /* Scan the insns in BB_INFO starting at PTR and going to the top of
2747 the block in order to build the gen and kill sets for the block.
2748 We start at ptr which may be the last insn in the block or may be
2749 the first insn with a wild read. In the latter case we are able to
2750 skip the rest of the block because it just does not matter:
2751 anything that happens is hidden by the wild read. */
2754 dse_step3_scan (bool for_spills, basic_block bb)
2756 bb_info_t bb_info = bb_table[bb->index];
2757 insn_info_t insn_info;
2760 /* There are no wild reads in the spill case. */
2761 insn_info = bb_info->last_insn;
2763 insn_info = find_insn_before_first_wild_read (bb_info);
2765 /* In the spill case or in the no_spill case if there is no wild
2766 read in the block, we will need a kill set. */
2767 if (insn_info == bb_info->last_insn)
2770 bitmap_clear (bb_info->kill);
2772 bb_info->kill = BITMAP_ALLOC (NULL);
2776 BITMAP_FREE (bb_info->kill);
2780 /* There may have been code deleted by the dce pass run before
2782 if (insn_info->insn && INSN_P (insn_info->insn))
2784 /* Process the read(s) last. */
2787 scan_stores_spill (insn_info->store_rec, bb_info->gen, bb_info->kill);
2788 scan_reads_spill (insn_info->read_rec, bb_info->gen, bb_info->kill);
2792 scan_stores_nospill (insn_info->store_rec, bb_info->gen, bb_info->kill);
2793 scan_reads_nospill (insn_info, bb_info->gen, bb_info->kill);
2797 insn_info = insn_info->prev_insn;
2802 /* Set the gen set of the exit block, and also any block with no
2803 successors that does not have a wild read. */
2806 dse_step3_exit_block_scan (bb_info_t bb_info)
2808 /* The gen set is all 0's for the exit block except for the
2809 frame_pointer_group. */
2811 if (stores_off_frame_dead_at_return)
2816 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2818 if (group->process_globally && group->frame_related)
2819 bitmap_ior_into (bb_info->gen, group->group_kill);
2825 /* Find all of the blocks that are not backwards reachable from the
2826 exit block or any block with no successors (BB). These are the
2827 infinite loops or infinite self loops. These blocks will still
2828 have their bits set in UNREACHABLE_BLOCKS. */
2831 mark_reachable_blocks (sbitmap unreachable_blocks, basic_block bb)
2836 if (TEST_BIT (unreachable_blocks, bb->index))
2838 RESET_BIT (unreachable_blocks, bb->index);
2839 FOR_EACH_EDGE (e, ei, bb->preds)
2841 mark_reachable_blocks (unreachable_blocks, e->src);
2846 /* Build the transfer functions for the function. */
2849 dse_step3 (bool for_spills)
2852 sbitmap unreachable_blocks = sbitmap_alloc (last_basic_block);
2853 sbitmap_iterator sbi;
2854 bitmap all_ones = NULL;
2857 sbitmap_ones (unreachable_blocks);
2861 bb_info_t bb_info = bb_table[bb->index];
2863 bitmap_clear (bb_info->gen);
2865 bb_info->gen = BITMAP_ALLOC (NULL);
2867 if (bb->index == ENTRY_BLOCK)
2869 else if (bb->index == EXIT_BLOCK)
2870 dse_step3_exit_block_scan (bb_info);
2872 dse_step3_scan (for_spills, bb);
2873 if (EDGE_COUNT (bb->succs) == 0)
2874 mark_reachable_blocks (unreachable_blocks, bb);
2876 /* If this is the second time dataflow is run, delete the old
2879 BITMAP_FREE (bb_info->in);
2881 BITMAP_FREE (bb_info->out);
2884 /* For any block in an infinite loop, we must initialize the out set
2885 to all ones. This could be expensive, but almost never occurs in
2886 practice. However, it is common in regression tests. */
2887 EXECUTE_IF_SET_IN_SBITMAP (unreachable_blocks, 0, i, sbi)
2889 if (bitmap_bit_p (all_blocks, i))
2891 bb_info_t bb_info = bb_table[i];
2897 all_ones = BITMAP_ALLOC (NULL);
2898 for (j = 0; VEC_iterate (group_info_t, rtx_group_vec, j, group); j++)
2899 bitmap_ior_into (all_ones, group->group_kill);
2903 bb_info->out = BITMAP_ALLOC (NULL);
2904 bitmap_copy (bb_info->out, all_ones);
2910 BITMAP_FREE (all_ones);
2911 sbitmap_free (unreachable_blocks);
2916 /*----------------------------------------------------------------------------
2919 Solve the bitvector equations.
2920 ----------------------------------------------------------------------------*/
2923 /* Confluence function for blocks with no successors. Create an out
2924 set from the gen set of the exit block. This block logically has
2925 the exit block as a successor. */
2930 dse_confluence_0 (basic_block bb)
2932 bb_info_t bb_info = bb_table[bb->index];
2934 if (bb->index == EXIT_BLOCK)
2939 bb_info->out = BITMAP_ALLOC (NULL);
2940 bitmap_copy (bb_info->out, bb_table[EXIT_BLOCK]->gen);
2944 /* Propagate the information from the in set of the dest of E to the
2945 out set of the src of E. If the various in or out sets are not
2946 there, that means they are all ones. */
2949 dse_confluence_n (edge e)
2951 bb_info_t src_info = bb_table[e->src->index];
2952 bb_info_t dest_info = bb_table[e->dest->index];
2957 bitmap_and_into (src_info->out, dest_info->in);
2960 src_info->out = BITMAP_ALLOC (NULL);
2961 bitmap_copy (src_info->out, dest_info->in);
2967 /* Propagate the info from the out to the in set of BB_INDEX's basic
2968 block. There are three cases:
2970 1) The block has no kill set. In this case the kill set is all
2971 ones. It does not matter what the out set of the block is, none of
2972 the info can reach the top. The only thing that reaches the top is
2973 the gen set and we just copy the set.
2975 2) There is a kill set but no out set and bb has successors. In
2976 this case we just return. Eventually an out set will be created and
2977 it is better to wait than to create a set of ones.
2979 3) There is both a kill and out set. We apply the obvious transfer
2984 dse_transfer_function (int bb_index)
2986 bb_info_t bb_info = bb_table[bb_index];
2994 return bitmap_ior_and_compl (bb_info->in, bb_info->gen,
2995 bb_info->out, bb_info->kill);
2998 bb_info->in = BITMAP_ALLOC (NULL);
2999 bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3000 bb_info->out, bb_info->kill);
3010 /* Case 1 above. If there is already an in set, nothing
3016 bb_info->in = BITMAP_ALLOC (NULL);
3017 bitmap_copy (bb_info->in, bb_info->gen);
3023 /* Solve the dataflow equations. */
3028 df_simple_dataflow (DF_BACKWARD, NULL, dse_confluence_0,
3029 dse_confluence_n, dse_transfer_function,
3030 all_blocks, df_get_postorder (DF_BACKWARD),
3031 df_get_n_blocks (DF_BACKWARD));
3036 fprintf (dump_file, "\n\n*** Global dataflow info after analysis.\n");
3039 bb_info_t bb_info = bb_table[bb->index];
3041 df_print_bb_index (bb, dump_file);
3043 bitmap_print (dump_file, bb_info->in, " in: ", "\n");
3045 fprintf (dump_file, " in: *MISSING*\n");
3047 bitmap_print (dump_file, bb_info->gen, " gen: ", "\n");
3049 fprintf (dump_file, " gen: *MISSING*\n");
3051 bitmap_print (dump_file, bb_info->kill, " kill: ", "\n");
3053 fprintf (dump_file, " kill: *MISSING*\n");
3055 bitmap_print (dump_file, bb_info->out, " out: ", "\n");
3057 fprintf (dump_file, " out: *MISSING*\n\n");
3064 /*----------------------------------------------------------------------------
3067 Delete the stores that can only be deleted using the global information.
3068 ----------------------------------------------------------------------------*/
3072 dse_step5_nospill (void)
3077 bb_info_t bb_info = bb_table[bb->index];
3078 insn_info_t insn_info = bb_info->last_insn;
3079 bitmap v = bb_info->out;
3083 bool deleted = false;
3084 if (dump_file && insn_info->insn)
3086 fprintf (dump_file, "starting to process insn %d\n",
3087 INSN_UID (insn_info->insn));
3088 bitmap_print (dump_file, v, " v: ", "\n");
3091 /* There may have been code deleted by the dce pass run before
3094 && INSN_P (insn_info->insn)
3095 && (!insn_info->cannot_delete)
3096 && (!bitmap_empty_p (v)))
3098 store_info_t store_info = insn_info->store_rec;
3100 /* Try to delete the current insn. */
3103 /* Skip the clobbers. */
3104 while (!store_info->is_set)
3105 store_info = store_info->next;
3107 if (store_info->alias_set)
3112 group_info_t group_info
3113 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
3115 for (i = store_info->begin; i < store_info->end; i++)
3117 int index = get_bitmap_index (group_info, i);
3120 fprintf (dump_file, "i = %d, index = %d\n", (int)i, index);
3121 if (index == 0 || !bitmap_bit_p (v, index))
3124 fprintf (dump_file, "failing at i = %d\n", (int)i);
3134 check_for_inc_dec (insn_info->insn);
3135 delete_insn (insn_info->insn);
3136 insn_info->insn = NULL;
3141 /* We do want to process the local info if the insn was
3142 deleted. For instance, if the insn did a wild read, we
3143 no longer need to trash the info. */
3145 && INSN_P (insn_info->insn)
3148 scan_stores_nospill (insn_info->store_rec, v, NULL);
3149 if (insn_info->wild_read)
3152 fprintf (dump_file, "wild read\n");
3155 else if (insn_info->read_rec)
3158 fprintf (dump_file, "regular read\n");
3159 scan_reads_nospill (insn_info, v, NULL);
3163 insn_info = insn_info->prev_insn;
3170 dse_step5_spill (void)
3175 bb_info_t bb_info = bb_table[bb->index];
3176 insn_info_t insn_info = bb_info->last_insn;
3177 bitmap v = bb_info->out;
3181 bool deleted = false;
3182 /* There may have been code deleted by the dce pass run before
3185 && INSN_P (insn_info->insn)
3186 && (!insn_info->cannot_delete)
3187 && (!bitmap_empty_p (v)))
3189 /* Try to delete the current insn. */
3190 store_info_t store_info = insn_info->store_rec;
3195 if (store_info->alias_set)
3197 int index = get_bitmap_index (clear_alias_group,
3198 store_info->alias_set);
3199 if (index == 0 || !bitmap_bit_p (v, index))
3207 store_info = store_info->next;
3209 if (deleted && dbg_cnt (dse))
3212 fprintf (dump_file, "Spill deleting insn %d\n",
3213 INSN_UID (insn_info->insn));
3214 check_for_inc_dec (insn_info->insn);
3215 delete_insn (insn_info->insn);
3217 insn_info->insn = NULL;
3222 && INSN_P (insn_info->insn)
3225 scan_stores_spill (insn_info->store_rec, v, NULL);
3226 scan_reads_spill (insn_info->read_rec, v, NULL);
3229 insn_info = insn_info->prev_insn;
3236 /*----------------------------------------------------------------------------
3239 Destroy everything left standing.
3240 ----------------------------------------------------------------------------*/
3243 dse_step6 (bool global_done)
3249 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
3251 free (group->offset_map_n);
3252 free (group->offset_map_p);
3253 BITMAP_FREE (group->store1_n);
3254 BITMAP_FREE (group->store1_p);
3255 BITMAP_FREE (group->store2_n);
3256 BITMAP_FREE (group->store2_p);
3257 BITMAP_FREE (group->group_kill);
3263 bb_info_t bb_info = bb_table[bb->index];
3264 BITMAP_FREE (bb_info->gen);
3266 BITMAP_FREE (bb_info->kill);
3268 BITMAP_FREE (bb_info->in);
3270 BITMAP_FREE (bb_info->out);
3273 if (clear_alias_sets)
3275 BITMAP_FREE (clear_alias_sets);
3276 BITMAP_FREE (disqualified_clear_alias_sets);
3277 free_alloc_pool (clear_alias_mode_pool);
3278 htab_delete (clear_alias_mode_table);
3281 end_alias_analysis ();
3283 htab_delete (rtx_group_table);
3284 VEC_free (group_info_t, heap, rtx_group_vec);
3285 BITMAP_FREE (all_blocks);
3286 BITMAP_FREE (scratch);
3288 free_alloc_pool (rtx_store_info_pool);
3289 free_alloc_pool (read_info_pool);
3290 free_alloc_pool (insn_info_pool);
3291 free_alloc_pool (bb_info_pool);
3292 free_alloc_pool (rtx_group_info_pool);
3293 free_alloc_pool (deferred_change_pool);
3297 /* -------------------------------------------------------------------------
3299 ------------------------------------------------------------------------- */
3301 /* Callback for running pass_rtl_dse. */
3304 rest_of_handle_dse (void)
3306 bool did_global = false;
3308 df_set_flags (DF_DEFER_INSN_RESCAN);
3310 /* Need the notes since we must track live hardregs in the forwards
3312 df_note_add_problem ();
3318 if (dse_step2_nospill ())
3320 df_set_flags (DF_LR_RUN_DCE);
3324 fprintf (dump_file, "doing global processing\n");
3327 dse_step5_nospill ();
3330 /* For the instance of dse that runs after reload, we make a special
3331 pass to process the spills. These are special in that they are
3332 totally transparent, i.e, there is no aliasing issues that need
3333 to be considered. This means that the wild reads that kill
3334 everything else do not apply here. */
3335 if (clear_alias_sets && dse_step2_spill ())
3339 df_set_flags (DF_LR_RUN_DCE);
3344 fprintf (dump_file, "doing global spill processing\n");
3350 dse_step6 (did_global);
3353 fprintf (dump_file, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3354 locally_deleted, globally_deleted, spill_deleted);
3361 return gate_dse1 () || gate_dse2 ();
3367 return optimize > 0 && flag_dse
3374 return optimize > 0 && flag_dse
3378 struct rtl_opt_pass pass_rtl_dse1 =
3383 gate_dse1, /* gate */
3384 rest_of_handle_dse, /* execute */
3387 0, /* static_pass_number */
3388 TV_DSE1, /* tv_id */
3389 0, /* properties_required */
3390 0, /* properties_provided */
3391 0, /* properties_destroyed */
3392 0, /* todo_flags_start */
3394 TODO_df_finish | TODO_verify_rtl_sharing |
3395 TODO_ggc_collect /* todo_flags_finish */
3399 struct rtl_opt_pass pass_rtl_dse2 =
3404 gate_dse2, /* gate */
3405 rest_of_handle_dse, /* execute */
3408 0, /* static_pass_number */
3409 TV_DSE2, /* tv_id */
3410 0, /* properties_required */
3411 0, /* properties_provided */
3412 0, /* properties_destroyed */
3413 0, /* todo_flags_start */
3415 TODO_df_finish | TODO_verify_rtl_sharing |
3416 TODO_ggc_collect /* todo_flags_finish */