1 /* RTL dead store elimination.
2 Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
4 Contributed by Richard Sandiford <rsandifor@codesourcery.com>
5 and Kenneth Zadeck <zadeck@naturalbridge.com>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 2, 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 COPYING. If not, write to the Free
21 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
28 #include "coretypes.h"
34 #include "hard-reg-set.h"
39 #include "tree-pass.h"
40 #include "alloc-pool.h"
42 #include "insn-config.h"
48 /* This file contains three techniques for performing Dead Store
51 * The first technique performs dse locally on any base address. It
52 is based on the cselib which is a local value numbering technique.
53 This technique is local to a basic block but deals with a fairly
56 * The second technique performs dse globally but is restricted to
57 base addresses that are either constant or are relative to the
60 * The third technique, (which is only done after register allocation)
61 processes the spill spill slots. This differs from the second
62 technique because it takes advantage of the fact that spilling is
63 completely free from the effects of aliasing.
65 Logically, dse is a backwards dataflow problem. A store can be
66 deleted if it if cannot be reached in the backward direction by any
67 use of the value being stored. However, the local technique uses a
68 forwards scan of the basic block because cselib requires that the
69 block be processed in that order.
71 The pass is logically broken into 7 steps:
75 1) The local algorithm, as well as scanning the insns for the two
78 2) Analysis to see if the global algs are necessary. In the case
79 of stores base on a constant address, there must be at least two
80 stores to that address, to make it possible to delete some of the
81 stores. In the case of stores off of the frame or spill related
82 stores, only one store to an address is necessary because those
83 stores die at the end of the function.
85 3) Set up the global dataflow equations based on processing the
86 info parsed in the first step.
88 4) Solve the dataflow equations.
90 5) Delete the insns that the global analysis has indicated are
95 This step uses cselib and canon_rtx to build the largest expression
96 possible for each address. This pass is a forwards pass through
97 each basic block. From the point of view of the global technique,
98 the first pass could examine a block in either direction. The
99 forwards ordering is to accomodate cselib.
101 We a simplifying assumption: addresses fall into four broad
104 1) base has rtx_varies_p == false, offset is constant.
105 2) base has rtx_varies_p == false, offset variable.
106 3) base has rtx_varies_p == true, offset constant.
107 4) base has rtx_varies_p == true, offset variable.
109 The local passes are able to process all 4 kinds of addresses. The
110 global pass only handles (1).
112 The global problem is formulated as follows:
114 A store, S1, to address A, where A is not relative to the stack
115 frame, can be eliminated if all paths from S1 to the end of the
116 of the function contain another store to A before a read to A.
118 If the address A is relative to the stack frame, a store S2 to A
119 can be eliminated if there are no paths from S1 that reach the
120 end of the function that read A before another store to A. In
121 this case S2 can be deleted if there are paths to from S2 to the
122 end of the function that have no reads or writes to A. This
123 second case allows stores to the stack frame to be deleted that
124 would otherwise die when the function returns. This cannot be
125 done if stores_off_frame_dead_at_return is not true. See the doc
126 for that variable for when this variable is false.
128 The global problem is formulated as a backwards set union
129 dataflow problem where the stores are the gens and reads are the
130 kills. Set union problems are rare and require some special
131 handling given our representation of bitmaps. A straightforward
132 implementation of requires a lot of bitmaps filled with 1s.
133 These are expensive and cumbersome in our bitmap formulation so
134 care has been taken to avoid large vectors filled with 1s. See
135 the comments in bb_info and in the dataflow confluence functions
138 There are two places for further enhancements to this algorithm:
140 1) The original dse which was embedded in a pass called flow also
141 did local address forwarding. For example in
146 flow would replace the right hand side of the second insn with a
147 reference to r100. Most of the infomation is available to add this
148 to this pass. It has not done it because it is a lot of work in
149 the case that either r100 is assigned to between the first and
150 second insn and/or the second insn is a load of part of the value
151 stored by the first insn.
153 insn 5 in gcc.c-torture/compile/990203-1.c simple case.
154 insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
155 insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
156 insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
158 2) The cleaning up of spill code is quite profitable. It currently
159 depends on reading tea leaves and chicken entrails left by reload.
160 This pass depends on reload creating a singleton alias set for each
161 spill slot and telling the next dse pass which of these alias sets
162 are the singletons. Rather than analyze the addresses of the
163 spills, dse's spill processing just does analysis of the loads and
164 stores that use those alias sets. There are three cases where this
167 a) Reload sometimes creates the slot for one mode of access, and
168 then inserts loads and/or stores for a smaller mode. In this
169 case, the current code just punts on the slot. The proper thing
170 to do is to back out and use one bit vector position for each
171 byte of the entity associated with the slot. This depends on
172 KNOWING that reload always generates the accesses for each of the
173 bytes in some canonical (read that easy to understand several
174 passes after reload happens) way.
176 b) Reload sometimes decides that spill slot it allocated was not
177 large enough for the mode and goes back and allocates more slots
178 with the same mode and alias set. The backout in this case is a
179 little more graceful than (a). In this case the slot is unmarked
180 as being a spill slot and if final address comes out to be based
181 off the frame pointer, the global algorithm handles this slot.
183 c) For any pass that may prespill, there is currently no
184 mechanism to tell the dse pass that the slot being used has the
185 special properties that reload uses. It may be that all that is
186 requirred is to have those passes make the same calls that reload
187 does, assuming that the alias sets can be manipulated in the same
190 /* There are limits to the size of constant offsets we model for the
191 global problem. There are certainly test cases, that exceed this
192 limit, however, it is unlikely that there are important programs
193 that really have constant offsets this size. */
194 #define MAX_OFFSET (64 * 1024)
197 static bitmap scratch = NULL;
200 /* This structure holds information about a candidate store. */
204 /* False means this is a clobber. */
207 /* The id of the mem group of the base address. If rtx_varies_p is
208 true, this is -1. Otherwise, it is the index into the group
212 /* This is the cselib value. */
213 cselib_val *cse_base;
215 /* This canonized mem. */
218 /* The result of get_addr on mem. */
221 /* If this is non-zero, it is the alias set of a spill location. */
222 HOST_WIDE_INT alias_set;
224 /* The offset of the first and byte before the last byte associated
225 with the operation. */
228 /* An bitmask as wide as the number of bytes in the word that
229 contains a 1 if the byte may be needed. The store is unused if
230 all of the bits are 0. */
231 long positions_needed;
233 /* The next store info for this insn. */
234 struct store_info *next;
236 /* The right hand side of the store. This is used if there is a
237 subsequent reload of the mems address somewhere later in the
242 typedef struct store_info *store_info_t;
243 static alloc_pool cse_store_info_pool;
244 static alloc_pool rtx_store_info_pool;
246 /* This structure holds information about a load. These are only
247 built for rtx bases. */
250 /* The id of the mem group of the base address. */
253 /* If this is non-zero, it is the alias set of a spill location. */
254 HOST_WIDE_INT alias_set;
256 /* The offset of the first and byte after the last byte associated
257 with the operation. If begin == end == 0, the read did not have
258 a constant offset. */
261 /* The mem being read. */
264 /* The next read_info for this insn. */
265 struct read_info *next;
267 typedef struct read_info *read_info_t;
268 static alloc_pool read_info_pool;
271 /* One of these records is created for each insn. */
275 /* Set true if the insn contains a store but the insn itself cannot
276 be deleted. This is set if the insn is a parallel and there is
277 more than one non dead output or if the insn is in some way
281 /* This field is only used by the global algorithm. It is set true
282 if the insn contains any read of mem except for a (1). This is
283 also set if the insn is a call or has a clobber mem. If the insn
284 contains a wild read, the use_rec will be null. */
287 /* This field is set for const function calls. Const functions
288 cannot read memory, but they can read the stack because that is
289 where they may get their parms. So having this set is less
290 severe than a wild read, it just means that all of the stores to
291 the stack are killed rather than all stores. */
294 /* This is true if any of the sets within the store contains a
295 cselib base. Such stores can only be deleted by the local
297 bool contains_cselib_groups;
302 /* The list of mem sets or mem clobbers that are contained in this
303 insn. If the insn is deletable, it contains only one mem set.
304 But it could also contain clobbers. Insns that contain more than
305 one mem set are not deletable, but each of those mems are here in
306 order to provied info to delete other insns. */
307 store_info_t store_rec;
309 /* The linked list of mem uses in this insn. Only the reads from
310 rtx bases are listed here. The reads to cselib bases are
311 completely processed during the first scan and so are never
313 read_info_t read_rec;
315 /* The prev insn in the basic block. */
316 struct insn_info * prev_insn;
318 /* The linked list of insns that are in consideration for removal in
319 the forwards pass thru the basic block. This pointer may be
320 trash as it is not cleared when a wild read occurs. The only
321 time it is guaranteed to be correct is when the traveral starts
322 at active_local_stores. */
323 struct insn_info * next_local_store;
326 typedef struct insn_info *insn_info_t;
327 static alloc_pool insn_info_pool;
329 /* The linked list of stores that are under consideration in this
331 static insn_info_t active_local_stores;
336 /* Pointer to the insn info for the last insn in the block. These
337 are linked so this is how all of the insns are reached. During
338 scanning this is the current insn being scanned. */
339 insn_info_t last_insn;
341 /* The info for the global dataflow problem. */
344 /* This is set if the transfer function should and in the wild_read
345 bitmap before applying the kill and gen sets. That vector knocks
346 out most of the bits in the bitmap and thus speeds up the
348 bool apply_wild_read;
350 /* The set of store positions that exist in this block before a wild read. */
353 /* The set of load positions that exist in this block above the
354 same position of a store. */
357 /* The set of stores that reach the top of the block without being
360 Do not represent the in if it is all ones. Note that this is
361 what the bitvector should logically be initialized to for a set
362 intersection problem. However, like the kill set, this is too
363 expensive. So initially, the in set will only be created for the
364 exit block and any block that contains a wild read. */
367 /* The set of stores that reach the bottom of the block from it's
370 Do not represent the in if it is all ones. Note that this is
371 what the bitvector should logically be initialized to for a set
372 intersection problem. However, like the kill and in set, this is
373 too expensive. So what is done is that the confluence operator
374 just initializes the vector from one of the out sets of the
375 successors of the block. */
379 typedef struct bb_info *bb_info_t;
380 static alloc_pool bb_info_pool;
382 /* Table to hold all bb_infos. */
383 static bb_info_t *bb_table;
385 /* There is a group_info for each rtx base that is used to reference
386 memory. There are also not many of the rtx bases because they are
387 very limited in scope. */
391 /* The actual base of the address. */
394 /* The sequential id of the base. This allows us to have a
395 canonical ordering of these that is not based on addresses. */
398 /* A mem wrapped around the base pointer for the group in order to
399 do read dependency. */
402 /* Canonized version of base_mem, most likely the same thing. */
405 /* These two sets of two bitmaps are used to keep track of how many
406 stores are actually referencing that postion from this base. We
407 only do this for rtx bases as this will be used to assign
408 postions in the bitmaps for the global problem. Bit N is set in
409 store1 on the first store for offset N. Bit N is set in store2
410 for the second store to offset N. This is all we need since we
411 only care about offsets that have two or more stores for them.
413 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
414 for 0 and greater offsets.
416 There is one special case here, for stores into the stack frame,
417 we will or store1 into store2 before deciding which stores look
418 at globally. This is because stores to the stack frame that have
419 no other reads before the end of the function can also be
421 bitmap store1_n, store1_p, store2_n, store2_p;
423 /* The postions in this bitmap have the same assignments as the in,
424 out, gen and kill bitmaps. This bitmap is all zeros except for
425 the postions that are occupied by stores for this group. */
428 /* True if there are any positions that are to be processed
430 bool process_globally;
432 /* True if the base of this group is either the frame_pointer or
433 hard_frame_pointer. */
436 /* The offset_map is used to map the offsets from this base into
437 postions in the global bitmaps. It is only created after all of
438 the all of stores have been scanned and we know which ones we
440 int *offset_map_n, *offset_map_p;
441 int offset_map_size_n, offset_map_size_p;
443 typedef struct group_info *group_info_t;
444 static alloc_pool rtx_group_info_pool;
446 /* Tables of group_info structures, hashed by base value. */
447 static htab_t rtx_group_table;
449 /* Index into the rtx_group_vec. */
450 static int rtx_group_next_id;
452 DEF_VEC_P(group_info_t);
453 DEF_VEC_ALLOC_P(group_info_t,heap);
455 static VEC(group_info_t,heap) *rtx_group_vec;
458 /* This structure holds the set of changes that are being deferred
459 when removing read operation. See replace_read. */
460 struct deferred_change
463 /* The mem that is being replaced. */
466 /* The reg it is being replaced with. */
469 struct deferred_change *next;
472 typedef struct deferred_change *deferred_change_t;
473 static alloc_pool deferred_change_pool;
475 static deferred_change_t deferred_change_list = NULL;
477 /* This are used to hold the alias sets of spill variables. Since
478 these are never aliased and there may be a lot of them, it makes
479 sense to treat them specially. This bitvector is only allocated in
480 calls from dse_record_singleton_alias_set which currently is only
481 made during reload1. So when dse is called before reload this
482 mechanism does nothing. */
484 static bitmap clear_alias_sets = NULL;
486 /* The set of clear_alias_sets that have been disqualified because
487 there are loads or stores using a different mode than the alias set
488 was registered with. */
489 static bitmap disqualified_clear_alias_sets = NULL;
491 /* The group that holds all of the clear_alias_sets. */
492 static group_info_t clear_alias_group;
494 /* The modes of the clear_alias_sets. */
495 static htab_t clear_alias_mode_table;
497 /* Hash table element to look up the mode for an alias set. */
498 struct clear_alias_mode_holder
500 HOST_WIDE_INT alias_set;
501 enum machine_mode mode;
504 static alloc_pool clear_alias_mode_pool;
506 /* This is true except for two cases:
507 (1) current_function_stdarg -- i.e. we cannot do this
508 for vararg functions because they play games with the frame.
509 (2) In ada, it is sometimes not safe to do assume that any stores
510 based off the stack frame go dead at the exit to a function. */
511 static bool stores_off_frame_dead_at_return;
513 /* Counter for stats. */
514 static int globally_deleted;
515 static int locally_deleted;
516 static int spill_deleted;
518 static bitmap all_blocks;
520 /* The number of bits used in the global bitmaps. */
521 static unsigned int current_position;
524 static bool gate_dse (void);
527 /*----------------------------------------------------------------------------
531 ----------------------------------------------------------------------------*/
533 /* Hashtable callbacks for maintaining the "bases" field of
534 store_group_info, given that the addresses are function invariants. */
537 clear_alias_mode_eq (const void *p1, const void *p2)
539 const struct clear_alias_mode_holder * h1
540 = (const struct clear_alias_mode_holder *) p1;
541 const struct clear_alias_mode_holder * h2
542 = (const struct clear_alias_mode_holder *) p2;
543 return h1->alias_set == h2->alias_set;
548 clear_alias_mode_hash (const void *p)
550 const struct clear_alias_mode_holder *holder
551 = (const struct clear_alias_mode_holder *) p;
552 return holder->alias_set;
556 /* Find the entry associated with ALIAS_SET. */
558 static struct clear_alias_mode_holder *
559 clear_alias_set_lookup (HOST_WIDE_INT alias_set)
561 struct clear_alias_mode_holder tmp_holder;
564 tmp_holder.alias_set = alias_set;
565 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, NO_INSERT);
572 /* Hashtable callbacks for maintaining the "bases" field of
573 store_group_info, given that the addresses are function invariants. */
576 invariant_group_base_eq (const void *p1, const void *p2)
578 const group_info_t gi1 = (const group_info_t) p1;
579 const group_info_t gi2 = (const group_info_t) p2;
580 return rtx_equal_p (gi1->rtx_base, gi2->rtx_base);
585 invariant_group_base_hash (const void *p)
587 const group_info_t gi = (const group_info_t) p;
589 return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false);
593 /* Get the GROUP for BASE. Add a new group if it is not there. */
596 get_group_info (rtx base)
598 struct group_info tmp_gi;
604 /* Find the store_base_info structure for BASE, creating a new one
606 tmp_gi.rtx_base = base;
607 slot = htab_find_slot (rtx_group_table, &tmp_gi, INSERT);
608 gi = (group_info_t) *slot;
612 if (!clear_alias_group)
614 clear_alias_group = gi = pool_alloc (rtx_group_info_pool);
615 memset (gi, 0, sizeof (struct group_info));
616 gi->id = rtx_group_next_id++;
617 gi->store1_n = BITMAP_ALLOC (NULL);
618 gi->store1_p = BITMAP_ALLOC (NULL);
619 gi->store2_n = BITMAP_ALLOC (NULL);
620 gi->store2_p = BITMAP_ALLOC (NULL);
621 gi->group_kill = BITMAP_ALLOC (NULL);
622 gi->process_globally = false;
623 gi->offset_map_size_n = 0;
624 gi->offset_map_size_p = 0;
625 gi->offset_map_n = NULL;
626 gi->offset_map_p = NULL;
627 VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);
629 return clear_alias_group;
634 *slot = gi = pool_alloc (rtx_group_info_pool);
636 gi->id = rtx_group_next_id++;
637 gi->base_mem = gen_rtx_MEM (QImode, base);
638 gi->canon_base_mem = canon_rtx (gi->base_mem);
639 gi->store1_n = BITMAP_ALLOC (NULL);
640 gi->store1_p = BITMAP_ALLOC (NULL);
641 gi->store2_n = BITMAP_ALLOC (NULL);
642 gi->store2_p = BITMAP_ALLOC (NULL);
643 gi->group_kill = BITMAP_ALLOC (NULL);
644 gi->process_globally = false;
646 (base == frame_pointer_rtx) || (base == hard_frame_pointer_rtx);
647 gi->offset_map_size_n = 0;
648 gi->offset_map_size_p = 0;
649 gi->offset_map_n = NULL;
650 gi->offset_map_p = NULL;
651 VEC_safe_push (group_info_t, heap, rtx_group_vec, gi);
658 /* Initialization of data structures. */
664 globally_deleted = 0;
667 scratch = BITMAP_ALLOC (NULL);
670 = create_alloc_pool ("rtx_store_info_pool",
671 sizeof (struct store_info), 100);
673 = create_alloc_pool ("read_info_pool",
674 sizeof (struct read_info), 100);
676 = create_alloc_pool ("insn_info_pool",
677 sizeof (struct insn_info), 100);
679 = create_alloc_pool ("bb_info_pool",
680 sizeof (struct bb_info), 100);
682 = create_alloc_pool ("rtx_group_info_pool",
683 sizeof (struct group_info), 100);
685 = create_alloc_pool ("deferred_change_pool",
686 sizeof (struct deferred_change), 10);
688 rtx_group_table = htab_create (11, invariant_group_base_hash,
689 invariant_group_base_eq, NULL);
691 bb_table = XCNEWVEC (bb_info_t, last_basic_block);
692 rtx_group_next_id = 0;
694 stores_off_frame_dead_at_return =
695 (!(TREE_CODE (TREE_TYPE (current_function_decl)) == FUNCTION_TYPE
696 && (TYPE_RETURNS_STACK_DEPRESSED (TREE_TYPE (current_function_decl)))))
697 && (!current_function_stdarg);
699 init_alias_analysis ();
701 if (clear_alias_sets)
702 clear_alias_group = get_group_info (NULL);
704 clear_alias_group = NULL;
709 /*----------------------------------------------------------------------------
712 Scan all of the insns. Any random ordering of the blocks is fine.
713 Each block is scanned in forward order to accomodate cselib which
714 is used to remove stores with non-constant bases.
715 ----------------------------------------------------------------------------*/
717 /* Delete all of the store_info recs from INSN_INFO. */
720 free_store_info (insn_info_t insn_info)
722 store_info_t store_info = insn_info->store_rec;
725 store_info_t next = store_info->next;
726 if (store_info->cse_base)
727 pool_free (cse_store_info_pool, store_info);
729 pool_free (rtx_store_info_pool, store_info);
733 insn_info->cannot_delete = true;
734 insn_info->contains_cselib_groups = false;
735 insn_info->store_rec = NULL;
745 /* Add an insn to do the add inside a x if it is a
746 PRE/POST-INC/DEC/MODIFY. D is an structure containing the insn and
747 the size of the mode of the MEM that this is inside of. */
750 replace_inc_dec (rtx *r, void *d)
753 struct insn_size *data = (struct insn_size *)d;
754 switch (GET_CODE (x))
759 rtx r1 = XEXP (x, 0);
760 rtx c = gen_int_mode (Pmode, data->size);
761 add_insn_before (data->insn,
762 gen_rtx_SET (Pmode, r1,
763 gen_rtx_PLUS (Pmode, r1, c)),
771 rtx r1 = XEXP (x, 0);
772 rtx c = gen_int_mode (Pmode, -data->size);
773 add_insn_before (data->insn,
774 gen_rtx_SET (Pmode, r1,
775 gen_rtx_PLUS (Pmode, r1, c)),
783 /* We can resuse the add because we are about to delete the
784 insn that contained it. */
785 rtx add = XEXP (x, 0);
786 rtx r1 = XEXP (add, 0);
787 add_insn_before (data->insn,
788 gen_rtx_SET (Pmode, r1, add), NULL);
798 /* If X is a MEM, check the address to see if it is PRE/POST-INC/DEC/MODIFY
799 and generate an add to replace that. */
802 replace_inc_dec_mem (rtx *r, void *d)
805 if (GET_CODE (x) == MEM)
807 struct insn_size data;
809 data.size = GET_MODE_SIZE (GET_MODE (x));
812 for_each_rtx (&XEXP (x, 0), replace_inc_dec, &data);
819 /* Before we delete INSN, make sure that the auto inc/dec, if it is
820 there, is split into a separate insn. */
823 check_for_inc_dec (rtx insn)
825 rtx note = find_reg_note (insn, REG_INC, NULL_RTX);
827 for_each_rtx (&insn, replace_inc_dec_mem, insn);
831 /* Delete the insn and free all of the fields inside INSN_INFO. */
834 delete_dead_store_insn (insn_info_t insn_info)
836 read_info_t read_info;
841 check_for_inc_dec (insn_info->insn);
844 fprintf (dump_file, "Locally deleting insn %d ",
845 INSN_UID (insn_info->insn));
846 if (insn_info->store_rec->alias_set)
847 fprintf (dump_file, "alias set %d\n",
848 (int)insn_info->store_rec->alias_set);
850 fprintf (dump_file, "\n");
853 free_store_info (insn_info);
854 read_info = insn_info->read_rec;
858 read_info_t next = read_info->next;
859 pool_free (read_info_pool, read_info);
862 insn_info->read_rec = NULL;
864 delete_insn (insn_info->insn);
866 insn_info->insn = NULL;
868 insn_info->wild_read = false;
872 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
876 set_usage_bits (group_info_t group, HOST_WIDE_INT offset, HOST_WIDE_INT width)
880 if ((offset > -MAX_OFFSET) && (offset < MAX_OFFSET))
881 for (i=offset; i<offset+width; i++)
888 store1 = group->store1_n;
889 store2 = group->store2_n;
894 store1 = group->store1_p;
895 store2 = group->store2_p;
899 if (bitmap_bit_p (store1, ai))
900 bitmap_set_bit (store2, ai);
903 bitmap_set_bit (store1, ai);
906 if (group->offset_map_size_n < ai)
907 group->offset_map_size_n = ai;
911 if (group->offset_map_size_p < ai)
912 group->offset_map_size_p = ai;
919 /* Set the BB_INFO so that the last insn is marked as a wild read. */
922 add_wild_read (bb_info_t bb_info)
924 insn_info_t insn_info = bb_info->last_insn;
925 read_info_t *ptr = &insn_info->read_rec;
929 read_info_t next = (*ptr)->next;
930 if ( (*ptr)->alias_set == 0 )
932 pool_free (read_info_pool, *ptr);
938 insn_info->wild_read = true;
939 active_local_stores = NULL;
943 /* Return true if X is a constant or one of the registers that behaves
944 as a constant over the life of a function. */
947 const_or_frame_p (rtx x)
949 switch (GET_CODE (x))
952 return MEM_READONLY_P (x);
963 /* Note that we have to test for the actual rtx used for the frame
964 and arg pointers and not just the register number in case we have
965 eliminated the frame and/or arg pointer and are using it
967 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
968 /* The arg pointer varies if it is not a fixed register. */
969 || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
970 || x == pic_offset_table_rtx)
979 /* Take all reasonable action to put the address of MEM into the form
980 that we can do analysis on.
982 The gold standard is to get the address into the form: address +
983 OFFSET where address is something that rtx_varies_p considers a
984 constant. When we can get the address in this form, we can do
985 global analysis on it. Note that for constant bases, address is
986 not actually returned, only the group_id. The address can be
989 If that fails, we try cselib to get a value we can at least use
990 locally. If that fails we return false.
992 The GROUP_ID is set to -1 for cselib bases and the index of the
993 group for non_varying bases.
995 FOR_READ is true if this is a mem read and false if not. */
998 canon_address (rtx mem,
999 HOST_WIDE_INT *alias_set_out,
1001 HOST_WIDE_INT *offset,
1004 rtx mem_address = XEXP (mem, 0);
1005 rtx expanded_address, address;
1006 /* Make sure that cselib is has initialized all of the operands of
1007 the address before asking it to do the subst. */
1009 if (clear_alias_sets)
1011 /* If this is a spill, do not do any further processing. */
1012 HOST_WIDE_INT alias_set = MEM_ALIAS_SET (mem);
1014 fprintf (dump_file, "found alias set %d\n", (int)alias_set);
1015 if (bitmap_bit_p (clear_alias_sets, alias_set))
1017 struct clear_alias_mode_holder *entry
1018 = clear_alias_set_lookup (alias_set);
1020 /* If the modes do not match, we cannot process this set. */
1021 if (entry->mode != GET_MODE (mem))
1025 "disqualifying alias set %d, (%s) != (%s)\n",
1026 (int)alias_set, GET_MODE_NAME (entry->mode),
1027 GET_MODE_NAME (GET_MODE (mem)));
1029 bitmap_set_bit (disqualified_clear_alias_sets, alias_set);
1033 *alias_set_out = alias_set;
1034 *group_id = clear_alias_group->id;
1041 cselib_lookup (mem_address, Pmode, 1);
1045 fprintf (dump_file, " mem: ");
1046 print_inline_rtx (dump_file, mem_address, 0);
1047 fprintf (dump_file, "\n");
1050 /* Use cselib to replace all of the reg references with the full
1051 expression. This will take care of the case where we have
1053 r_x = base + offset;
1058 val = *(base + offset);
1061 expanded_address = cselib_expand_value_rtx (mem_address, scratch, 5);
1063 /* If this fails, just go with the mem_address. */
1064 if (!expanded_address)
1065 expanded_address = mem_address;
1067 /* Split the address into canonical BASE + OFFSET terms. */
1068 address = canon_rtx (expanded_address);
1074 fprintf (dump_file, "\n after cselib_expand address: ");
1075 print_inline_rtx (dump_file, expanded_address, 0);
1076 fprintf (dump_file, "\n");
1078 fprintf (dump_file, "\n after canon_rtx address: ");
1079 print_inline_rtx (dump_file, address, 0);
1080 fprintf (dump_file, "\n");
1083 if (GET_CODE (address) == CONST)
1084 address = XEXP (address, 0);
1086 if (GET_CODE (address) == PLUS && GET_CODE (XEXP (address, 1)) == CONST_INT)
1088 *offset = INTVAL (XEXP (address, 1));
1089 address = XEXP (address, 0);
1092 if (const_or_frame_p (address))
1094 group_info_t group = get_group_info (address);
1097 fprintf (dump_file, " gid=%d offset=%d \n", group->id, (int)*offset);
1099 *group_id = group->id;
1103 *base = cselib_lookup (address, Pmode, true);
1109 fprintf (dump_file, " no cselib val - should be a wild read.\n");
1113 fprintf (dump_file, " varying cselib base=%d offset = %d\n",
1114 (*base)->value, (int)*offset);
1120 /* Clear the rhs field from the active_local_stores array. */
1123 clear_rhs_from_active_local_stores (void)
1125 insn_info_t ptr = active_local_stores;
1129 store_info_t store_info = ptr->store_rec;
1130 /* Skip the clobbers. */
1131 while (!store_info->is_set)
1132 store_info = store_info->next;
1134 store_info->rhs = NULL;
1136 ptr = ptr->next_local_store;
1141 /* BODY is an instruction pattern that belongs to INSN. Return 1 if
1142 there is a candidate store, after adding it to the appropriate
1143 local store group if so. */
1146 record_store (rtx body, bb_info_t bb_info)
1149 HOST_WIDE_INT offset = 0;
1150 HOST_WIDE_INT width = 0;
1151 HOST_WIDE_INT spill_alias_set;
1152 insn_info_t insn_info = bb_info->last_insn;
1153 store_info_t store_info = NULL;
1155 cselib_val *base = NULL;
1156 insn_info_t ptr, last;
1157 bool store_is_unused;
1159 if (GET_CODE (body) != SET && GET_CODE (body) != CLOBBER)
1162 /* If this is not used, then this cannot be used to keep the insn
1163 from being deleted. On the other hand, it does provide something
1164 that can be used to prove that another store is dead. */
1166 = (find_reg_note (insn_info->insn, REG_UNUSED, body) != NULL);
1168 /* Check whether that value is a suitable memory location. */
1169 mem = SET_DEST (body);
1172 /* If the set or clobber is unused, then it does not effect our
1173 ability to get rid of the entire insn. */
1174 if (!store_is_unused)
1175 insn_info->cannot_delete = true;
1179 /* At this point we know mem is a mem. */
1180 if (GET_MODE (mem) == BLKmode)
1182 if (GET_CODE (XEXP (mem, 0)) == SCRATCH)
1185 fprintf (dump_file, " adding wild read for (clobber (mem:BLK (scratch))\n");
1186 add_wild_read (bb_info);
1187 insn_info->cannot_delete = true;
1189 else if (!store_is_unused)
1191 /* If the set or clobber is unused, then it does not effect our
1192 ability to get rid of the entire insn. */
1193 insn_info->cannot_delete = true;
1194 clear_rhs_from_active_local_stores ();
1199 /* We can still process a volatile mem, we just cannot delete it. */
1200 if (MEM_VOLATILE_P (mem))
1201 insn_info->cannot_delete = true;
1203 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
1205 clear_rhs_from_active_local_stores ();
1209 width = GET_MODE_SIZE (GET_MODE (mem));
1211 if (spill_alias_set)
1213 bitmap store1 = clear_alias_group->store1_p;
1214 bitmap store2 = clear_alias_group->store2_p;
1216 if (bitmap_bit_p (store1, spill_alias_set))
1217 bitmap_set_bit (store2, spill_alias_set);
1219 bitmap_set_bit (store1, spill_alias_set);
1221 if (clear_alias_group->offset_map_size_p < spill_alias_set)
1222 clear_alias_group->offset_map_size_p = spill_alias_set;
1224 store_info = pool_alloc (rtx_store_info_pool);
1227 fprintf (dump_file, " processing spill store %d(%s)\n",
1228 (int)spill_alias_set, GET_MODE_NAME (GET_MODE (mem)));
1230 else if (group_id >= 0)
1232 /* In the restrictive case where the base is a constant or the
1233 frame pointer we can do global analysis. */
1236 = VEC_index (group_info_t, rtx_group_vec, group_id);
1238 store_info = pool_alloc (rtx_store_info_pool);
1239 set_usage_bits (group, offset, width);
1242 fprintf (dump_file, " processing const base store gid=%d[%d..%d)\n",
1243 group_id, (int)offset, (int)(offset+width));
1247 store_info = pool_alloc (cse_store_info_pool);
1248 insn_info->contains_cselib_groups = true;
1252 fprintf (dump_file, " processing cselib store [%d..%d)\n",
1253 (int)offset, (int)(offset+width));
1256 /* Check to see if this stores causes some other stores to be
1258 ptr = active_local_stores;
1263 insn_info_t next = ptr->next_local_store;
1264 store_info_t s_info = ptr->store_rec;
1267 /* Skip the clobbers. We delete the active insn if this insn
1268 shaddows the set. To have been put on the active list, it
1269 has exactly on set. */
1270 while (!s_info->is_set)
1271 s_info = s_info->next;
1273 if (s_info->alias_set != spill_alias_set)
1275 else if (s_info->alias_set)
1277 struct clear_alias_mode_holder *entry
1278 = clear_alias_set_lookup (s_info->alias_set);
1279 /* Generally, spills cannot be processed if and of the
1280 references to the slot have a different mode. But if
1281 we are in the same block and mode is exactly the same
1282 between this store and one before in the same block,
1283 we can still delete it. */
1284 if ((GET_MODE (mem) == GET_MODE (s_info->mem))
1285 && (GET_MODE (mem) == entry->mode))
1288 s_info->positions_needed = 0;
1291 fprintf (dump_file, " trying spill store in insn=%d alias_set=%d\n",
1292 INSN_UID (ptr->insn), (int)s_info->alias_set);
1294 else if ((s_info->group_id == group_id)
1295 && (s_info->cse_base == base))
1299 fprintf (dump_file, " trying store in insn=%d gid=%d[%d..%d)\n",
1300 INSN_UID (ptr->insn), s_info->group_id,
1301 (int)s_info->begin, (int)s_info->end);
1302 for (i = offset; i < offset+width; i++)
1303 if (i >= s_info->begin && i < s_info->end)
1304 s_info->positions_needed &= ~(1L << (i - s_info->begin));
1306 else if (s_info->rhs)
1307 /* Need to see if it is possible for this store to overwrite
1308 the value of store_info. If it is, set the rhs to NULL to
1309 keep it from being used to remove a load. */
1311 if (canon_true_dependence (s_info->mem,
1312 GET_MODE (s_info->mem),
1318 /* An insn can be deleted if every position of every one of
1319 its s_infos is zero. */
1320 if (s_info->positions_needed != 0)
1325 insn_info_t insn_to_delete = ptr;
1328 last->next_local_store = ptr->next_local_store;
1330 active_local_stores = ptr->next_local_store;
1332 delete_dead_store_insn (insn_to_delete);
1340 gcc_assert ((unsigned) width < sizeof (store_info->positions_needed) * CHAR_BIT);
1342 /* Finish filling in the store_info. */
1343 store_info->next = insn_info->store_rec;
1344 insn_info->store_rec = store_info;
1345 store_info->mem = canon_rtx (mem);
1346 store_info->alias_set = spill_alias_set;
1347 store_info->mem_addr = get_addr (XEXP (mem, 0));
1348 store_info->cse_base = base;
1349 store_info->positions_needed = (1L << width) - 1;
1350 store_info->group_id = group_id;
1351 store_info->begin = offset;
1352 store_info->end = offset + width;
1353 store_info->is_set = GET_CODE (body) == SET;
1355 if (store_info->is_set
1356 /* No place to keep the value after ra. */
1357 && !reload_completed
1358 /* The careful reviewer may wish to comment my checking that the
1359 rhs of a store is always a reg. */
1360 && REG_P (SET_SRC (body))
1361 /* Sometimes the store and reload is used for truncation and
1363 && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
1364 store_info->rhs = SET_SRC (body);
1366 store_info->rhs = NULL;
1368 /* If this is a clobber, we return 0. We will only be able to
1369 delete this insn if there is only one store USED store, but we
1370 can use the clobber to delete other stores earlier. */
1371 return store_info->is_set ? 1 : 0;
1376 dump_insn_info (const char * start, insn_info_t insn_info)
1378 fprintf (dump_file, "%s insn=%d %s\n", start,
1379 INSN_UID (insn_info->insn),
1380 insn_info->store_rec ? "has store" : "naked");
1384 /* Take a sequence of:
1395 The STORE_INFO and STORE_INFO are for the store and the READ_INFO
1396 and READ_INSN are for the read. Return true if the replacement
1400 replace_read (store_info_t store_info, insn_info_t store_insn,
1401 read_info_t read_info, insn_info_t read_insn, rtx *loc)
1407 fprintf (dump_file, "generating move to replace load at %d from store at %d\n",
1408 INSN_UID (read_insn->insn), INSN_UID (store_insn->insn));
1409 if (GET_MODE (store_info->mem) == GET_MODE (read_info->mem))
1411 rtx new_reg = gen_reg_rtx (GET_MODE (store_info->mem));
1412 if (validate_change (read_insn->insn, loc, new_reg, 0))
1415 deferred_change_t deferred_change = pool_alloc (deferred_change_pool);
1418 emit_move_insn (new_reg, store_info->rhs);
1419 insns = get_insns ();
1421 emit_insn_before (insns, store_insn->insn);
1424 fprintf (dump_file, " -- adding move insn %d: r%d = r%d\n",
1425 INSN_UID (insns), REGNO (new_reg), REGNO (store_info->rhs));
1427 /* And now for the cludge part: cselib croaks if you just
1428 return at this point. There are two reasons for this:
1430 1) Cselib has an idea of how many pseudos there are and
1431 that does not include the new one we just added.
1433 2) Cselib does not know about the move insn we added
1434 above the store_info, and there is no way to tell it
1435 about it, because it has "moved on".
1437 So we are just going to have to lie. The move insn is
1438 not really an issue, cselib did not see it. But the use
1439 of the new pseudo read_insn is a real problem. The way
1440 that we solve this problem is that we are just going to
1441 put the mem back keep a table of mems to get rid of. At
1442 the end of the basic block we can put it back. */
1444 *loc = read_info->mem;
1445 deferred_change->next = deferred_change_list;
1446 deferred_change_list = deferred_change;
1447 deferred_change->loc = loc;
1448 deferred_change->reg = new_reg;
1450 /* Get rid of the read_info, from the point of view of the
1451 rest of dse, play like this read never happened. */
1452 read_insn->read_rec = read_info->next;
1453 pool_free (read_info_pool, read_info);
1459 fprintf (dump_file, " -- validation failure\n");
1465 /* Someone with excellent rtl skills needs to fill this in. You
1466 are guaranteed that the read is of the same size or smaller
1467 than the store, and that the read does not hang off one of
1468 the ends of the store. But the offsets of each must be
1469 checked because the read does not have to line up on either
1470 end of the store so the begin fields need to be examined in
1471 both the store_info and read_info. */
1473 fprintf (dump_file, " -- complex load, currently unsupported.\n");
1479 /* A for_each_rtx callback in which DATA is the bb_info. Check to see
1480 if LOC is a mem and if it is look at the address and kill any
1481 appropriate stores that may be active. */
1484 check_mem_read_rtx (rtx *loc, void *data)
1488 insn_info_t insn_info;
1489 HOST_WIDE_INT offset = 0;
1490 HOST_WIDE_INT width = 0;
1491 HOST_WIDE_INT spill_alias_set = 0;
1492 cselib_val *base = NULL;
1494 read_info_t read_info;
1496 if (!mem || !MEM_P (mem))
1499 bb_info = (bb_info_t) data;
1500 insn_info = bb_info->last_insn;
1502 if ((MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
1503 || (MEM_VOLATILE_P (mem)))
1506 fprintf (dump_file, " adding wild read, volatile or barrier.\n");
1507 add_wild_read (bb_info);
1508 insn_info->cannot_delete = true;
1512 /* If it is reading readonly mem, then there can be no conflict with
1514 if (MEM_READONLY_P (mem))
1517 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
1520 fprintf (dump_file, " adding wild read, canon_address failure.\n");
1521 add_wild_read (bb_info);
1525 if (GET_MODE (mem) == BLKmode)
1528 width = GET_MODE_SIZE (GET_MODE (mem));
1530 read_info = pool_alloc (read_info_pool);
1531 read_info->group_id = group_id;
1532 read_info->mem = mem;
1533 read_info->alias_set = spill_alias_set;
1534 read_info->begin = offset;
1535 read_info->end = offset + width;
1536 read_info->next = insn_info->read_rec;
1537 insn_info->read_rec = read_info;
1539 /* We ignore the clobbers in store_info. The is mildly agressive,
1540 but there really should not be a clobber followed by a read. */
1542 if (spill_alias_set)
1544 insn_info_t i_ptr = active_local_stores;
1545 insn_info_t last = NULL;
1548 fprintf (dump_file, " processing spill load %d\n",
1549 (int)spill_alias_set);
1553 store_info_t store_info = i_ptr->store_rec;
1555 /* Skip the clobbers. */
1556 while (!store_info->is_set)
1557 store_info = store_info->next;
1559 if (store_info->alias_set == spill_alias_set)
1562 dump_insn_info ("removing from active", i_ptr);
1565 last->next_local_store = i_ptr->next_local_store;
1567 active_local_stores = i_ptr->next_local_store;
1571 i_ptr = i_ptr->next_local_store;
1574 else if (group_id >= 0)
1576 /* This is the restricted case where the base is a constant or
1577 the frame pointer and offset is a constant. */
1578 insn_info_t i_ptr = active_local_stores;
1579 insn_info_t last = NULL;
1584 fprintf (dump_file, " processing const load gid=%d[BLK]\n",
1587 fprintf (dump_file, " processing const load gid=%d[%d..%d)\n",
1588 group_id, (int)offset, (int)(offset+width));
1593 bool remove = false;
1594 store_info_t store_info = i_ptr->store_rec;
1596 /* Skip the clobbers. */
1597 while (!store_info->is_set)
1598 store_info = store_info->next;
1600 /* There are three cases here. */
1601 if (store_info->group_id < 0)
1602 /* We have a cselib store followed by a read from a
1605 = canon_true_dependence (store_info->mem,
1606 GET_MODE (store_info->mem),
1607 store_info->mem_addr,
1610 else if (group_id == store_info->group_id)
1612 /* This is a block mode load. We may get lucky and
1613 canon_true_dependence may save the day. */
1616 = canon_true_dependence (store_info->mem,
1617 GET_MODE (store_info->mem),
1618 store_info->mem_addr,
1621 /* If this read is just reading back something that we just
1622 stored, rewrite the read. */
1626 && (offset >= store_info->begin)
1627 && (offset + width <= store_info->end))
1629 int mask = ((1L << width) - 1) << (offset - store_info->begin);
1631 if ((store_info->positions_needed & mask) == mask
1632 && replace_read (store_info, i_ptr,
1633 read_info, insn_info, loc))
1636 /* The bases are the same, just see if the offsets
1638 if ((offset < store_info->end)
1639 && (offset + width > store_info->begin))
1645 The else case that is missing here is that the
1646 bases are constant but different. There is nothing
1647 to do here because there is no overlap. */
1652 dump_insn_info ("removing from active", i_ptr);
1655 last->next_local_store = i_ptr->next_local_store;
1657 active_local_stores = i_ptr->next_local_store;
1661 i_ptr = i_ptr->next_local_store;
1666 insn_info_t i_ptr = active_local_stores;
1667 insn_info_t last = NULL;
1670 fprintf (dump_file, " processing cselib load mem:");
1671 print_inline_rtx (dump_file, mem, 0);
1672 fprintf (dump_file, "\n");
1677 bool remove = false;
1678 store_info_t store_info = i_ptr->store_rec;
1681 fprintf (dump_file, " processing cselib load against insn %d\n",
1682 INSN_UID (i_ptr->insn));
1684 /* Skip the clobbers. */
1685 while (!store_info->is_set)
1686 store_info = store_info->next;
1688 /* If this read is just reading back something that we just
1689 stored, rewrite the read. */
1691 && store_info->group_id == -1
1692 && store_info->cse_base == base
1693 && (offset >= store_info->begin)
1694 && (offset + width <= store_info->end))
1696 int mask = ((1L << width) - 1) << (offset - store_info->begin);
1698 if ((store_info->positions_needed & mask) == mask
1699 && replace_read (store_info, i_ptr,
1700 read_info, insn_info, loc))
1704 if (!store_info->alias_set)
1705 remove = canon_true_dependence (store_info->mem,
1706 GET_MODE (store_info->mem),
1707 store_info->mem_addr,
1713 dump_insn_info ("removing from active", i_ptr);
1716 last->next_local_store = i_ptr->next_local_store;
1718 active_local_stores = i_ptr->next_local_store;
1722 i_ptr = i_ptr->next_local_store;
1728 /* A for_each_rtx callback in which DATA points the INSN_INFO for
1729 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
1730 true for any part of *LOC. */
1733 check_mem_read_use (rtx *loc, void *data)
1735 for_each_rtx (loc, check_mem_read_rtx, data);
1738 /* Apply record_store to all candidate stores in INSN. Mark INSN
1739 if some part of it is not a candidate store and assigns to a
1740 non-register target. */
1743 scan_insn (bb_info_t bb_info, rtx insn)
1746 insn_info_t insn_info = pool_alloc (insn_info_pool);
1748 memset (insn_info, 0, sizeof (struct insn_info));
1751 fprintf (dump_file, "\n**scanning insn=%d\n",
1754 insn_info->prev_insn = bb_info->last_insn;
1755 insn_info->insn = insn;
1756 bb_info->last_insn = insn_info;
1759 /* Cselib clears the table for this case, so we have to essentually
1761 if (NONJUMP_INSN_P (insn)
1762 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
1763 && MEM_VOLATILE_P (PATTERN (insn)))
1765 add_wild_read (bb_info);
1766 insn_info->cannot_delete = true;
1770 /* Look at all of the uses in the insn. */
1771 note_uses (&PATTERN (insn), check_mem_read_use, bb_info);
1775 insn_info->cannot_delete = true;
1776 /* Const functions cannot do anything bad i.e. read memory,
1777 however, they can read their parameters which may have been
1778 pushed onto the stack. */
1779 if (CONST_OR_PURE_CALL_P (insn) && !pure_call_p (insn))
1781 insn_info_t i_ptr = active_local_stores;
1782 insn_info_t last = NULL;
1785 fprintf (dump_file, "const call %d\n", INSN_UID (insn));
1789 store_info_t store_info = i_ptr->store_rec;
1791 /* Skip the clobbers. */
1792 while (!store_info->is_set)
1793 store_info = store_info->next;
1795 /* Remove the frame related stores. */
1796 if (store_info->group_id >= 0
1797 && VEC_index (group_info_t, rtx_group_vec, store_info->group_id)->frame_related)
1800 dump_insn_info ("removing from active", i_ptr);
1803 last->next_local_store = i_ptr->next_local_store;
1805 active_local_stores = i_ptr->next_local_store;
1809 i_ptr = i_ptr->next_local_store;
1812 insn_info->stack_read = true;
1817 /* Every other call, including pure functions may read memory. */
1818 add_wild_read (bb_info);
1822 /* Assuming that there are sets in these insns, we cannot delete
1824 if ((GET_CODE (PATTERN (insn)) == CLOBBER)
1825 || volatile_insn_p (PATTERN (insn))
1826 || (flag_non_call_exceptions && may_trap_p (PATTERN (insn)))
1827 || (RTX_FRAME_RELATED_P (insn))
1828 || find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX))
1829 insn_info->cannot_delete = true;
1831 body = PATTERN (insn);
1832 if (GET_CODE (body) == PARALLEL)
1835 for (i = 0; i < XVECLEN (body, 0); i++)
1836 mems_found += record_store (XVECEXP (body, 0, i), bb_info);
1839 mems_found += record_store (body, bb_info);
1842 fprintf (dump_file, "mems_found = %d, cannot_delete = %s\n",
1843 mems_found, insn_info->cannot_delete ? "true" : "false");
1845 /* If we found some sets of mems, and the insn has not been marked
1846 cannot delete, add it into the active_local_stores so that it can
1847 be locally deleted if found dead. Otherwise mark it as cannot
1848 delete. This simplifies the processing later. */
1849 if (mems_found == 1 && !insn_info->cannot_delete)
1851 insn_info->next_local_store = active_local_stores;
1852 active_local_stores = insn_info;
1855 insn_info->cannot_delete = true;
1859 /* Remove BASE from the set of active_local_stores. This is a
1860 callback from cselib that is used to get rid of the stores in
1861 active_local_stores. */
1864 remove_useless_values (cselib_val *base)
1866 insn_info_t insn_info = active_local_stores;
1867 insn_info_t last = NULL;
1871 store_info_t store_info = insn_info->store_rec;
1872 bool delete = false;
1874 /* If ANY of the store_infos match the cselib group that is
1875 being deleted, then the insn can not be deleted. */
1878 if ((store_info->group_id == -1)
1879 && (store_info->cse_base == base))
1884 store_info = store_info->next;
1890 last->next_local_store = insn_info->next_local_store;
1892 active_local_stores = insn_info->next_local_store;
1893 free_store_info (insn_info);
1898 insn_info = insn_info->next_local_store;
1903 /* Do all of step 1. */
1910 cselib_init (false);
1911 all_blocks = BITMAP_ALLOC (NULL);
1912 bitmap_set_bit (all_blocks, ENTRY_BLOCK);
1913 bitmap_set_bit (all_blocks, EXIT_BLOCK);
1918 bb_info_t bb_info = pool_alloc (bb_info_pool);
1920 memset (bb_info, 0, sizeof (struct bb_info));
1921 bitmap_set_bit (all_blocks, bb->index);
1923 bb_table[bb->index] = bb_info;
1924 cselib_discard_hook = remove_useless_values;
1926 if (bb->index >= NUM_FIXED_BLOCKS)
1931 = create_alloc_pool ("cse_store_info_pool",
1932 sizeof (struct store_info), 100);
1933 active_local_stores = NULL;
1934 cselib_clear_table ();
1936 /* Scan the insns. */
1937 FOR_BB_INSNS (bb, insn)
1940 scan_insn (bb_info, insn);
1941 cselib_process_insn (insn);
1944 /* This is something of a hack, because the global algorithm
1945 is supposed to take care of the case where stores go dead
1946 at the end of the function. However, the global
1947 algorithm must take a more conservative view of block
1948 mode reads than the local alg does. So to get the case
1949 where you have a store to the frame followed by a non
1950 overlaping block more read, we look at the active local
1951 stores at the end of the function and delete all of the
1952 frame and spill based ones. */
1953 if (stores_off_frame_dead_at_return
1954 && (EDGE_COUNT (bb->succs) == 0
1955 || (single_succ_p (bb)
1956 && single_succ (bb) == EXIT_BLOCK_PTR
1957 && ! current_function_calls_eh_return)))
1959 insn_info_t i_ptr = active_local_stores;
1962 store_info_t store_info = i_ptr->store_rec;
1964 /* Skip the clobbers. */
1965 while (!store_info->is_set)
1966 store_info = store_info->next;
1967 if (store_info->alias_set)
1968 delete_dead_store_insn (i_ptr);
1970 if (store_info->group_id >= 0)
1973 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
1974 if (group->frame_related)
1975 delete_dead_store_insn (i_ptr);
1978 i_ptr = i_ptr->next_local_store;
1982 /* Get rid of the loads that were discovered in
1983 replace_read. Cselib is finished with this block. */
1984 while (deferred_change_list)
1986 deferred_change_t next = deferred_change_list->next;
1988 /* There is no reason to validate this change. That was
1990 *deferred_change_list->loc = deferred_change_list->reg;
1991 pool_free (deferred_change_pool, deferred_change_list);
1992 deferred_change_list = next;
1995 /* Get rid of all of the cselib based store_infos in this
1996 block and mark the containing insns as not being
1998 ptr = bb_info->last_insn;
2001 if (ptr->contains_cselib_groups)
2002 free_store_info (ptr);
2003 ptr = ptr->prev_insn;
2006 free_alloc_pool (cse_store_info_pool);
2011 htab_empty (rtx_group_table);
2015 /*----------------------------------------------------------------------------
2018 Assign each byte position in the stores that we are going to
2019 analyze globally to a position in the bitmaps. Returns true if
2020 there are any bit postions assigned.
2021 ----------------------------------------------------------------------------*/
2024 dse_step2_init (void)
2029 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2031 /* For all non stack related bases, we only consider a store to
2032 be deletable if there are two or more stores for that
2033 position. This is because it takes one store to make the
2034 other store redundant. However, for the stores that are
2035 stack related, we consider them if there is only one store
2036 for the position. We do this because the stack related
2037 stores can be deleted if their is no read between them and
2038 the end of the function.
2040 To make this work in the current framework, we take the stack
2041 related bases add all of the bits from store1 into store2.
2042 This has the effect of making the eligible even if there is
2045 if (stores_off_frame_dead_at_return && group->frame_related)
2047 bitmap_ior_into (group->store2_n, group->store1_n);
2048 bitmap_ior_into (group->store2_p, group->store1_p);
2050 fprintf (dump_file, "group %d is frame related ", i);
2053 group->offset_map_size_n++;
2054 group->offset_map_n = XNEWVEC (int, group->offset_map_size_n);
2055 group->offset_map_size_p++;
2056 group->offset_map_p = XNEWVEC (int, group->offset_map_size_p);
2057 group->process_globally = false;
2060 fprintf (dump_file, "group %d(%d+%d): ", i,
2061 (int)bitmap_count_bits (group->store2_n),
2062 (int)bitmap_count_bits (group->store2_p));
2063 bitmap_print (dump_file, group->store2_n, "n ", " ");
2064 bitmap_print (dump_file, group->store2_p, "p ", "\n");
2070 /* Init the offset tables for the normal case. */
2073 dse_step2_nospill (void)
2077 /* Position 0 is unused because 0 is used in the maps to mean
2079 current_position = 1;
2081 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2086 if (group == clear_alias_group)
2089 memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2090 memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2091 bitmap_clear (group->group_kill);
2093 EXECUTE_IF_SET_IN_BITMAP (group->store2_n, 0, j, bi)
2095 bitmap_set_bit (group->group_kill, current_position);
2096 group->offset_map_n[j] = current_position++;
2097 group->process_globally = true;
2099 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2101 bitmap_set_bit (group->group_kill, current_position);
2102 group->offset_map_p[j] = current_position++;
2103 group->process_globally = true;
2106 return current_position != 1;
2110 /* Init the offset tables for the spill case. */
2113 dse_step2_spill (void)
2116 group_info_t group = clear_alias_group;
2119 /* Position 0 is unused because 0 is used in the maps to mean
2121 current_position = 1;
2125 bitmap_print (dump_file, clear_alias_sets,
2126 "clear alias sets ", "\n");
2127 bitmap_print (dump_file, disqualified_clear_alias_sets,
2128 "disqualified clear alias sets ", "\n");
2131 memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2132 memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2133 bitmap_clear (group->group_kill);
2135 /* Remove the disqualified positions from the store2_p set. */
2136 bitmap_and_compl_into (group->store2_p, disqualified_clear_alias_sets);
2138 /* We do not need to process the store2_n set because
2139 alias_sets are always positive. */
2140 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2142 bitmap_set_bit (group->group_kill, current_position);
2143 group->offset_map_p[j] = current_position++;
2144 group->process_globally = true;
2147 return current_position != 1;
2152 /*----------------------------------------------------------------------------
2155 Build the bit vectors for the transfer functions.
2156 ----------------------------------------------------------------------------*/
2159 /* Note that this is NOT a general purpose function. Any mem that has
2160 an alias set registered here expected to be COMPLETELY unaliased:
2161 i.e it's addresses are not and need not be examined.
2163 It is known that all references to this address will have this
2164 alias set and there are NO other references to this address in the
2167 Currently the only place that is known to be clean enough to use
2168 this interface is the code that assigns the spill locations.
2170 All of the mems that have alias_sets registered are subjected to a
2171 very powerful form of dse where function calls, volatile reads and
2172 writes, and reads from random location are not taken into account.
2174 It is also assumed that these locations go dead when the function
2175 returns. This assumption could be relaxed if there were found to
2176 be places that this assumption was not correct.
2178 The MODE is passed in and saved. The mode of each load or store to
2179 a mem with ALIAS_SET is checked against MEM. If the size of that
2180 load or store is different from MODE, processing is halted on this
2181 alias set. For the vast majority of aliases sets, all of the loads
2182 and stores will use the same mode. But vectors are treated
2183 differently: the alias set is established for the entire vector,
2184 but reload will insert loads and stores for individual elements and
2185 we do not necessarily have the information to track those separate
2186 elements. So when we see a mode mismatch, we just bail. */
2190 dse_record_singleton_alias_set (HOST_WIDE_INT alias_set,
2191 enum machine_mode mode)
2193 struct clear_alias_mode_holder tmp_holder;
2194 struct clear_alias_mode_holder *entry;
2197 /* If we are not going to run dse, we need to return now or there
2198 will be problems with allocating the bitmaps. */
2199 if ((!gate_dse()) || !alias_set)
2202 if (!clear_alias_sets)
2204 clear_alias_sets = BITMAP_ALLOC (NULL);
2205 disqualified_clear_alias_sets = BITMAP_ALLOC (NULL);
2206 clear_alias_mode_table = htab_create (11, clear_alias_mode_hash,
2207 clear_alias_mode_eq, NULL);
2208 clear_alias_mode_pool = create_alloc_pool ("clear_alias_mode_pool",
2209 sizeof (struct clear_alias_mode_holder), 100);
2212 bitmap_set_bit (clear_alias_sets, alias_set);
2214 tmp_holder.alias_set = alias_set;
2216 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, INSERT);
2217 gcc_assert (*slot == NULL);
2219 *slot = entry = pool_alloc (clear_alias_mode_pool);
2220 entry->alias_set = alias_set;
2225 /* Remove ALIAS_SET from the sets of stack slots being considered. */
2228 dse_invalidate_singleton_alias_set (HOST_WIDE_INT alias_set)
2230 if ((!gate_dse()) || !alias_set)
2233 bitmap_clear_bit (clear_alias_sets, alias_set);
2237 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
2241 get_bitmap_index (group_info_t group_info, HOST_WIDE_INT offset)
2245 HOST_WIDE_INT offset_p = -offset;
2246 if (offset_p >= group_info->offset_map_size_n)
2248 return group_info->offset_map_n[offset_p];
2252 if (offset >= group_info->offset_map_size_p)
2254 return group_info->offset_map_p[offset];
2259 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
2263 scan_stores_nospill (store_info_t store_info, bitmap gen, bitmap kill)
2268 group_info_t group_info
2269 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
2270 if (group_info->process_globally)
2271 for (i = store_info->begin; i < store_info->end; i++)
2273 int index = get_bitmap_index (group_info, i);
2276 bitmap_set_bit (gen, index);
2278 bitmap_clear_bit (kill, index);
2281 store_info = store_info->next;
2286 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
2290 scan_stores_spill (store_info_t store_info, bitmap gen, bitmap kill)
2294 if (store_info->alias_set)
2296 int index = get_bitmap_index (clear_alias_group,
2297 store_info->alias_set);
2300 bitmap_set_bit (gen, index);
2302 bitmap_clear_bit (kill, index);
2305 store_info = store_info->next;
2310 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
2314 scan_reads_nospill (insn_info_t insn_info, bitmap gen, bitmap kill)
2316 read_info_t read_info = insn_info->read_rec;
2320 /* For const function calls kill the stack related stores. */
2321 if (insn_info->stack_read)
2323 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2324 if (group->process_globally && group->frame_related)
2327 bitmap_ior_into (kill, group->group_kill);
2328 bitmap_and_compl_into (gen, group->group_kill);
2334 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2336 if (group->process_globally)
2338 if (i == read_info->group_id)
2340 if (read_info->begin > read_info->end)
2342 /* Begin > end for block mode reads. */
2344 bitmap_ior_into (kill, group->group_kill);
2345 bitmap_and_compl_into (gen, group->group_kill);
2349 /* The groups are the same, just process the
2352 for (j = read_info->begin; j < read_info->end; j++)
2354 int index = get_bitmap_index (group, j);
2358 bitmap_set_bit (kill, index);
2359 bitmap_clear_bit (gen, index);
2366 /* The groups are different, if the alias sets
2367 conflict, clear the entire group. We only need
2368 to apply this test if the read_info is a cselib
2369 read. Anything with a constant base cannot alias
2370 something else with a different constant
2372 if ((read_info->group_id < 0)
2373 && canon_true_dependence (group->base_mem,
2375 group->canon_base_mem,
2376 read_info->mem, rtx_varies_p))
2379 bitmap_ior_into (kill, group->group_kill);
2380 bitmap_and_compl_into (gen, group->group_kill);
2386 read_info = read_info->next;
2390 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
2394 scan_reads_spill (read_info_t read_info, bitmap gen, bitmap kill)
2398 if (read_info->alias_set)
2400 int index = get_bitmap_index (clear_alias_group,
2401 read_info->alias_set);
2405 bitmap_set_bit (kill, index);
2406 bitmap_clear_bit (gen, index);
2410 read_info = read_info->next;
2415 /* Return the insn in BB_INFO before the first wild read or if there
2416 are no wild reads in the block, return the last insn. */
2419 find_insn_before_first_wild_read (bb_info_t bb_info)
2421 insn_info_t insn_info = bb_info->last_insn;
2422 insn_info_t last_wild_read = NULL;
2426 if (insn_info->wild_read)
2428 last_wild_read = insn_info->prev_insn;
2429 /* Block starts with wild read. */
2430 if (!last_wild_read)
2434 insn_info = insn_info->prev_insn;
2438 return last_wild_read;
2440 return bb_info->last_insn;
2444 /* Scan the insns in BB_INFO starting at PTR and going to the top of
2445 the block in order to build the gen and kill sets for the block.
2446 We start at ptr which may be the last insn in the block or may be
2447 the first insn with a wild read. In the latter case we are able to
2448 skip the rest of the block because it just does not matter:
2449 anything that happens is hidden by the wild read. */
2452 dse_step3_scan (bool for_spills, basic_block bb)
2454 bb_info_t bb_info = bb_table[bb->index];
2455 insn_info_t insn_info;
2458 /* There are no wild reads in the spill case. */
2459 insn_info = bb_info->last_insn;
2461 insn_info = find_insn_before_first_wild_read (bb_info);
2463 /* In the spill case or in the no_spill case if there is no wild
2464 read in the block, we will need a kill set. */
2465 if (insn_info == bb_info->last_insn)
2468 bitmap_clear (bb_info->kill);
2470 bb_info->kill = BITMAP_ALLOC (NULL);
2474 BITMAP_FREE (bb_info->kill);
2478 /* There may have been code deleted by the dce pass run before
2480 if (insn_info->insn && INSN_P (insn_info->insn))
2482 /* Process the read(s) last. */
2485 scan_stores_spill (insn_info->store_rec, bb_info->gen, bb_info->kill);
2486 scan_reads_spill (insn_info->read_rec, bb_info->gen, bb_info->kill);
2490 scan_stores_nospill (insn_info->store_rec, bb_info->gen, bb_info->kill);
2491 scan_reads_nospill (insn_info, bb_info->gen, bb_info->kill);
2495 insn_info = insn_info->prev_insn;
2500 /* Set the gen set of the exit block, and also any block with no
2501 successors that does not have a wild read. */
2504 dse_step3_exit_block_scan (bb_info_t bb_info)
2506 /* The gen set is all 0's for the exit block except for the
2507 frame_pointer_group. */
2509 if (stores_off_frame_dead_at_return)
2514 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2516 if (group->process_globally && group->frame_related)
2517 bitmap_ior_into (bb_info->gen, group->group_kill);
2523 /* Find all of the blocks that are not backwards reachable from the
2524 exit block or any block with no successors (BB). These are the
2525 infinite loops or infinite self loops. These blocks will still
2526 have their bits set in UNREACHABLE_BLOCKS. */
2529 mark_reachable_blocks (sbitmap unreachable_blocks, basic_block bb)
2534 if (TEST_BIT (unreachable_blocks, bb->index))
2536 RESET_BIT (unreachable_blocks, bb->index);
2537 FOR_EACH_EDGE (e, ei, bb->preds)
2539 mark_reachable_blocks (unreachable_blocks, e->src);
2544 /* Build the transfer functions for the function. */
2547 dse_step3 (bool for_spills)
2550 sbitmap unreachable_blocks = sbitmap_alloc (last_basic_block);
2551 sbitmap_iterator sbi;
2552 bitmap all_ones = NULL;
2555 sbitmap_ones (unreachable_blocks);
2559 bb_info_t bb_info = bb_table[bb->index];
2561 bitmap_clear (bb_info->gen);
2563 bb_info->gen = BITMAP_ALLOC (NULL);
2565 if (bb->index == ENTRY_BLOCK)
2567 else if (bb->index == EXIT_BLOCK)
2568 dse_step3_exit_block_scan (bb_info);
2570 dse_step3_scan (for_spills, bb);
2571 if (EDGE_COUNT (bb->succs) == 0)
2572 mark_reachable_blocks (unreachable_blocks, bb);
2574 /* If this is the second time dataflow is run, delete the old
2577 BITMAP_FREE (bb_info->in);
2579 BITMAP_FREE (bb_info->out);
2582 /* For any block in an infinite loop, we must initialize the out set
2583 to all ones. This could be expensive, but almost never occurs in
2584 practice. However, it is common in regression tests. */
2585 EXECUTE_IF_SET_IN_SBITMAP (unreachable_blocks, 0, i, sbi)
2587 if (bitmap_bit_p (all_blocks, i))
2589 bb_info_t bb_info = bb_table[i];
2595 all_ones = BITMAP_ALLOC (NULL);
2596 for (j = 0; VEC_iterate (group_info_t, rtx_group_vec, j, group); j++)
2597 bitmap_ior_into (all_ones, group->group_kill);
2601 bb_info->out = BITMAP_ALLOC (NULL);
2602 bitmap_copy (bb_info->out, all_ones);
2608 BITMAP_FREE (all_ones);
2609 sbitmap_free (unreachable_blocks);
2614 /*----------------------------------------------------------------------------
2617 Solve the bitvector equations.
2618 ----------------------------------------------------------------------------*/
2621 /* Confluence function for blocks with no successors. Create an out
2622 set from the gen set of the exit block. This block logically has
2623 the exit block as a successor. */
2628 dse_confluence_0 (basic_block bb)
2630 bb_info_t bb_info = bb_table[bb->index];
2632 if (bb->index == EXIT_BLOCK)
2637 bb_info->out = BITMAP_ALLOC (NULL);
2638 bitmap_copy (bb_info->out, bb_table[EXIT_BLOCK]->gen);
2642 /* Propagate the information from the in set of the dest of E to the
2643 out set of the src of E. If the various in or out sets are not
2644 there, that means they are all ones. */
2647 dse_confluence_n (edge e)
2649 bb_info_t src_info = bb_table[e->src->index];
2650 bb_info_t dest_info = bb_table[e->dest->index];
2655 bitmap_and_into (src_info->out, dest_info->in);
2658 src_info->out = BITMAP_ALLOC (NULL);
2659 bitmap_copy (src_info->out, dest_info->in);
2665 /* Propagate the info from the out to the in set of BB_INDEX's basic
2666 block. There are three cases:
2668 1) The block has no kill set. In this case the kill set is all
2669 ones. It does not matter what the out set of the block is, none of
2670 the info can reach the top. The only thing that reaches the top is
2671 the gen set and we just copy the set.
2673 2) There is a kill set but no out set and bb has successors. In
2674 this case we just return. Eventually an out set will be created and
2675 it is better to wait than to create a set of ones.
2677 3) There is both a kill and out set. We apply the obvious transfer
2682 dse_transfer_function (int bb_index)
2684 bb_info_t bb_info = bb_table[bb_index];
2692 return bitmap_ior_and_compl (bb_info->in, bb_info->gen,
2693 bb_info->out, bb_info->kill);
2696 bb_info->in = BITMAP_ALLOC (NULL);
2697 bitmap_ior_and_compl (bb_info->in, bb_info->gen,
2698 bb_info->out, bb_info->kill);
2708 /* Case 1 above. If there is already an in set, nothing
2714 bb_info->in = BITMAP_ALLOC (NULL);
2715 bitmap_copy (bb_info->in, bb_info->gen);
2721 /* Solve the dataflow equations. */
2726 df_simple_dataflow (DF_BACKWARD, NULL, dse_confluence_0,
2727 dse_confluence_n, dse_transfer_function,
2728 all_blocks, df_get_postorder (DF_BACKWARD),
2729 df_get_n_blocks (DF_BACKWARD));
2734 fprintf (dump_file, "\n\n*** Global dataflow info after analysis.\n");
2737 bb_info_t bb_info = bb_table[bb->index];
2739 df_print_bb_index (bb, dump_file);
2741 bitmap_print (dump_file, bb_info->in, " in: ", "\n");
2743 fprintf (dump_file, " in: *MISSING*\n");
2745 bitmap_print (dump_file, bb_info->gen, " gen: ", "\n");
2747 fprintf (dump_file, " gen: *MISSING*\n");
2749 bitmap_print (dump_file, bb_info->kill, " kill: ", "\n");
2751 fprintf (dump_file, " kill: *MISSING*\n");
2753 bitmap_print (dump_file, bb_info->out, " out: ", "\n");
2755 fprintf (dump_file, " out: *MISSING*\n\n");
2762 /*----------------------------------------------------------------------------
2765 Delete the stores that can only be deleted using the global informantion.
2766 ----------------------------------------------------------------------------*/
2770 dse_step5_nospill (void)
2775 bb_info_t bb_info = bb_table[bb->index];
2776 insn_info_t insn_info = bb_info->last_insn;
2777 bitmap v = bb_info->out;
2781 bool deleted = false;
2782 if (dump_file && insn_info->insn)
2784 fprintf (dump_file, "starting to process insn %d\n",
2785 INSN_UID (insn_info->insn));
2786 bitmap_print (dump_file, v, " v: ", "\n");
2789 /* There may have been code deleted by the dce pass run before
2792 && INSN_P (insn_info->insn)
2793 && (!insn_info->cannot_delete)
2794 && (!bitmap_empty_p (v)))
2796 store_info_t store_info = insn_info->store_rec;
2798 /* Try to delete the current insn. */
2801 /* Skip the clobbers. */
2802 while (!store_info->is_set)
2803 store_info = store_info->next;
2805 if (store_info->alias_set)
2810 group_info_t group_info
2811 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id);
2813 for (i = store_info->begin; i < store_info->end; i++)
2815 int index = get_bitmap_index (group_info, i);
2818 fprintf (dump_file, "i = %d, index = %d\n", (int)i, index);
2819 if (index == 0 || !bitmap_bit_p (v, index))
2822 fprintf (dump_file, "failing at i = %d\n", (int)i);
2832 check_for_inc_dec (insn_info->insn);
2833 delete_insn (insn_info->insn);
2834 insn_info->insn = NULL;
2839 /* We do want to process the local info if the insn was
2840 deleted. For insntance, if the insn did a wild read, we
2841 no longer need to trash the info. */
2843 && INSN_P (insn_info->insn)
2846 scan_stores_nospill (insn_info->store_rec, v, NULL);
2847 if (insn_info->wild_read)
2850 fprintf (dump_file, "wild read\n");
2853 else if (insn_info->read_rec)
2856 fprintf (dump_file, "regular read\n");
2857 scan_reads_nospill (insn_info, v, NULL);
2861 insn_info = insn_info->prev_insn;
2868 dse_step5_spill (void)
2873 bb_info_t bb_info = bb_table[bb->index];
2874 insn_info_t insn_info = bb_info->last_insn;
2875 bitmap v = bb_info->out;
2879 bool deleted = false;
2880 /* There may have been code deleted by the dce pass run before
2883 && INSN_P (insn_info->insn)
2884 && (!insn_info->cannot_delete)
2885 && (!bitmap_empty_p (v)))
2887 /* Try to delete the current insn. */
2888 store_info_t store_info = insn_info->store_rec;
2893 if (store_info->alias_set)
2895 int index = get_bitmap_index (clear_alias_group,
2896 store_info->alias_set);
2897 if (index == 0 || !bitmap_bit_p (v, index))
2905 store_info = store_info->next;
2907 if (deleted && dbg_cnt (dse))
2910 fprintf (dump_file, "Spill deleting insn %d\n",
2911 INSN_UID (insn_info->insn));
2912 check_for_inc_dec (insn_info->insn);
2913 delete_insn (insn_info->insn);
2915 insn_info->insn = NULL;
2920 && INSN_P (insn_info->insn)
2923 scan_stores_spill (insn_info->store_rec, v, NULL);
2924 scan_reads_spill (insn_info->read_rec, v, NULL);
2927 insn_info = insn_info->prev_insn;
2934 /*----------------------------------------------------------------------------
2937 Destroy everything left standing.
2938 ----------------------------------------------------------------------------*/
2941 dse_step6 (bool global_done)
2949 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2951 free (group->offset_map_n);
2952 free (group->offset_map_p);
2953 BITMAP_FREE (group->store1_n);
2954 BITMAP_FREE (group->store1_p);
2955 BITMAP_FREE (group->store2_n);
2956 BITMAP_FREE (group->store2_p);
2957 BITMAP_FREE (group->group_kill);
2962 bb_info_t bb_info = bb_table[bb->index];
2963 BITMAP_FREE (bb_info->gen);
2965 BITMAP_FREE (bb_info->kill);
2967 BITMAP_FREE (bb_info->in);
2969 BITMAP_FREE (bb_info->out);
2974 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++)
2976 BITMAP_FREE (group->store1_n);
2977 BITMAP_FREE (group->store1_p);
2978 BITMAP_FREE (group->store2_n);
2979 BITMAP_FREE (group->store2_p);
2980 BITMAP_FREE (group->group_kill);
2984 if (clear_alias_sets)
2986 BITMAP_FREE (clear_alias_sets);
2987 BITMAP_FREE (disqualified_clear_alias_sets);
2988 free_alloc_pool (clear_alias_mode_pool);
2989 htab_delete (clear_alias_mode_table);
2992 end_alias_analysis ();
2994 htab_delete (rtx_group_table);
2995 VEC_free (group_info_t, heap, rtx_group_vec);
2996 BITMAP_FREE (all_blocks);
2997 BITMAP_FREE (scratch);
2999 free_alloc_pool (rtx_store_info_pool);
3000 free_alloc_pool (read_info_pool);
3001 free_alloc_pool (insn_info_pool);
3002 free_alloc_pool (bb_info_pool);
3003 free_alloc_pool (rtx_group_info_pool);
3004 free_alloc_pool (deferred_change_pool);
3009 /* -------------------------------------------------------------------------
3011 ------------------------------------------------------------------------- */
3013 /* Callback for running pass_rtl_dse. */
3016 rest_of_handle_dse (void)
3018 bool did_global = false;
3020 df_set_flags (DF_DEFER_INSN_RESCAN);
3025 if (dse_step2_nospill ())
3027 df_set_flags (DF_LR_RUN_DCE);
3031 fprintf (dump_file, "doing global processing\n");
3034 dse_step5_nospill ();
3037 /* For the instance of dse that runs after reload, we make a special
3038 pass to process the spills. These are special in that they are
3039 totally transparent, i.e, there is no aliasing issues that need
3040 to be considered. This means that the wild reads that kill
3041 everything else do not apply here. */
3042 if (clear_alias_sets && dse_step2_spill ())
3046 df_set_flags (DF_LR_RUN_DCE);
3051 fprintf (dump_file, "doing global spill processing\n");
3057 dse_step6 (did_global);
3060 fprintf (dump_file, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3061 locally_deleted, globally_deleted, spill_deleted);
3068 return optimize > 0 && flag_dse;
3071 struct tree_opt_pass pass_rtl_dse1 =
3074 gate_dse, /* gate */
3075 rest_of_handle_dse, /* execute */
3078 0, /* static_pass_number */
3079 TV_DSE1, /* tv_id */
3080 0, /* properties_required */
3081 0, /* properties_provided */
3082 0, /* properties_destroyed */
3083 0, /* todo_flags_start */
3086 TODO_ggc_collect, /* todo_flags_finish */
3090 struct tree_opt_pass pass_rtl_dse2 =
3093 gate_dse, /* gate */
3094 rest_of_handle_dse, /* execute */
3097 0, /* static_pass_number */
3098 TV_DSE2, /* tv_id */
3099 0, /* properties_required */
3100 0, /* properties_provided */
3101 0, /* properties_destroyed */
3102 0, /* todo_flags_start */
3105 TODO_ggc_collect, /* todo_flags_finish */
OSDN Git Service
