2013-08-14 Paolo Carlini <paolo.carlini@oracle.com>
[official-gcc.git] / gcc / dse.c
blob8b132eb2c91031c83dd2cb031a74b20247bf0000
1 /* RTL dead store elimination.
2 Copyright (C) 2005-2013 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
12 version.
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
17 for more details.
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/>. */
23 #undef BASELINE
25 #include "config.h"
26 #include "system.h"
27 #include "coretypes.h"
28 #include "hash-table.h"
29 #include "tm.h"
30 #include "rtl.h"
31 #include "tree.h"
32 #include "tm_p.h"
33 #include "regs.h"
34 #include "hard-reg-set.h"
35 #include "regset.h"
36 #include "flags.h"
37 #include "df.h"
38 #include "cselib.h"
39 #include "tree-pass.h"
40 #include "alloc-pool.h"
41 #include "alias.h"
42 #include "insn-config.h"
43 #include "expr.h"
44 #include "recog.h"
45 #include "optabs.h"
46 #include "dbgcnt.h"
47 #include "target.h"
48 #include "params.h"
49 #include "tree-flow.h" /* for may_be_aliased */
51 /* This file contains three techniques for performing Dead Store
52 Elimination (dse).
54 * The first technique performs dse locally on any base address. It
55 is based on the cselib which is a local value numbering technique.
56 This technique is local to a basic block but deals with a fairly
57 general addresses.
59 * The second technique performs dse globally but is restricted to
60 base addresses that are either constant or are relative to the
61 frame_pointer.
63 * The third technique, (which is only done after register allocation)
64 processes the spill spill slots. This differs from the second
65 technique because it takes advantage of the fact that spilling is
66 completely free from the effects of aliasing.
68 Logically, dse is a backwards dataflow problem. A store can be
69 deleted if it if cannot be reached in the backward direction by any
70 use of the value being stored. However, the local technique uses a
71 forwards scan of the basic block because cselib requires that the
72 block be processed in that order.
74 The pass is logically broken into 7 steps:
76 0) Initialization.
78 1) The local algorithm, as well as scanning the insns for the two
79 global algorithms.
81 2) Analysis to see if the global algs are necessary. In the case
82 of stores base on a constant address, there must be at least two
83 stores to that address, to make it possible to delete some of the
84 stores. In the case of stores off of the frame or spill related
85 stores, only one store to an address is necessary because those
86 stores die at the end of the function.
88 3) Set up the global dataflow equations based on processing the
89 info parsed in the first step.
91 4) Solve the dataflow equations.
93 5) Delete the insns that the global analysis has indicated are
94 unnecessary.
96 6) Delete insns that store the same value as preceding store
97 where the earlier store couldn't be eliminated.
99 7) Cleanup.
101 This step uses cselib and canon_rtx to build the largest expression
102 possible for each address. This pass is a forwards pass through
103 each basic block. From the point of view of the global technique,
104 the first pass could examine a block in either direction. The
105 forwards ordering is to accommodate cselib.
107 We make a simplifying assumption: addresses fall into four broad
108 categories:
110 1) base has rtx_varies_p == false, offset is constant.
111 2) base has rtx_varies_p == false, offset variable.
112 3) base has rtx_varies_p == true, offset constant.
113 4) base has rtx_varies_p == true, offset variable.
115 The local passes are able to process all 4 kinds of addresses. The
116 global pass only handles 1).
118 The global problem is formulated as follows:
120 A store, S1, to address A, where A is not relative to the stack
121 frame, can be eliminated if all paths from S1 to the end of the
122 function contain another store to A before a read to A.
124 If the address A is relative to the stack frame, a store S2 to A
125 can be eliminated if there are no paths from S2 that reach the
126 end of the function that read A before another store to A. In
127 this case S2 can be deleted if there are paths from S2 to the
128 end of the function that have no reads or writes to A. This
129 second case allows stores to the stack frame to be deleted that
130 would otherwise die when the function returns. This cannot be
131 done if stores_off_frame_dead_at_return is not true. See the doc
132 for that variable for when this variable is false.
134 The global problem is formulated as a backwards set union
135 dataflow problem where the stores are the gens and reads are the
136 kills. Set union problems are rare and require some special
137 handling given our representation of bitmaps. A straightforward
138 implementation requires a lot of bitmaps filled with 1s.
139 These are expensive and cumbersome in our bitmap formulation so
140 care has been taken to avoid large vectors filled with 1s. See
141 the comments in bb_info and in the dataflow confluence functions
142 for details.
144 There are two places for further enhancements to this algorithm:
146 1) The original dse which was embedded in a pass called flow also
147 did local address forwarding. For example in
149 A <- r100
150 ... <- A
152 flow would replace the right hand side of the second insn with a
153 reference to r100. Most of the information is available to add this
154 to this pass. It has not done it because it is a lot of work in
155 the case that either r100 is assigned to between the first and
156 second insn and/or the second insn is a load of part of the value
157 stored by the first insn.
159 insn 5 in gcc.c-torture/compile/990203-1.c simple case.
160 insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
161 insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
162 insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
164 2) The cleaning up of spill code is quite profitable. It currently
165 depends on reading tea leaves and chicken entrails left by reload.
166 This pass depends on reload creating a singleton alias set for each
167 spill slot and telling the next dse pass which of these alias sets
168 are the singletons. Rather than analyze the addresses of the
169 spills, dse's spill processing just does analysis of the loads and
170 stores that use those alias sets. There are three cases where this
171 falls short:
173 a) Reload sometimes creates the slot for one mode of access, and
174 then inserts loads and/or stores for a smaller mode. In this
175 case, the current code just punts on the slot. The proper thing
176 to do is to back out and use one bit vector position for each
177 byte of the entity associated with the slot. This depends on
178 KNOWING that reload always generates the accesses for each of the
179 bytes in some canonical (read that easy to understand several
180 passes after reload happens) way.
182 b) Reload sometimes decides that spill slot it allocated was not
183 large enough for the mode and goes back and allocates more slots
184 with the same mode and alias set. The backout in this case is a
185 little more graceful than (a). In this case the slot is unmarked
186 as being a spill slot and if final address comes out to be based
187 off the frame pointer, the global algorithm handles this slot.
189 c) For any pass that may prespill, there is currently no
190 mechanism to tell the dse pass that the slot being used has the
191 special properties that reload uses. It may be that all that is
192 required is to have those passes make the same calls that reload
193 does, assuming that the alias sets can be manipulated in the same
194 way. */
196 /* There are limits to the size of constant offsets we model for the
197 global problem. There are certainly test cases, that exceed this
198 limit, however, it is unlikely that there are important programs
199 that really have constant offsets this size. */
200 #define MAX_OFFSET (64 * 1024)
202 /* Obstack for the DSE dataflow bitmaps. We don't want to put these
203 on the default obstack because these bitmaps can grow quite large
204 (~2GB for the small (!) test case of PR54146) and we'll hold on to
205 all that memory until the end of the compiler run.
206 As a bonus, delete_tree_live_info can destroy all the bitmaps by just
207 releasing the whole obstack. */
208 static bitmap_obstack dse_bitmap_obstack;
210 /* Obstack for other data. As for above: Kinda nice to be able to
211 throw it all away at the end in one big sweep. */
212 static struct obstack dse_obstack;
214 /* Scratch bitmap for cselib's cselib_expand_value_rtx. */
215 static bitmap scratch = NULL;
217 struct insn_info;
219 /* This structure holds information about a candidate store. */
220 struct store_info
223 /* False means this is a clobber. */
224 bool is_set;
226 /* False if a single HOST_WIDE_INT bitmap is used for positions_needed. */
227 bool is_large;
229 /* The id of the mem group of the base address. If rtx_varies_p is
230 true, this is -1. Otherwise, it is the index into the group
231 table. */
232 int group_id;
234 /* This is the cselib value. */
235 cselib_val *cse_base;
237 /* This canonized mem. */
238 rtx mem;
240 /* Canonized MEM address for use by canon_true_dependence. */
241 rtx mem_addr;
243 /* If this is non-zero, it is the alias set of a spill location. */
244 alias_set_type alias_set;
246 /* The offset of the first and byte before the last byte associated
247 with the operation. */
248 HOST_WIDE_INT begin, end;
250 union
252 /* A bitmask as wide as the number of bytes in the word that
253 contains a 1 if the byte may be needed. The store is unused if
254 all of the bits are 0. This is used if IS_LARGE is false. */
255 unsigned HOST_WIDE_INT small_bitmask;
257 struct
259 /* A bitmap with one bit per byte. Cleared bit means the position
260 is needed. Used if IS_LARGE is false. */
261 bitmap bmap;
263 /* Number of set bits (i.e. unneeded bytes) in BITMAP. If it is
264 equal to END - BEGIN, the whole store is unused. */
265 int count;
266 } large;
267 } positions_needed;
269 /* The next store info for this insn. */
270 struct store_info *next;
272 /* The right hand side of the store. This is used if there is a
273 subsequent reload of the mems address somewhere later in the
274 basic block. */
275 rtx rhs;
277 /* If rhs is or holds a constant, this contains that constant,
278 otherwise NULL. */
279 rtx const_rhs;
281 /* Set if this store stores the same constant value as REDUNDANT_REASON
282 insn stored. These aren't eliminated early, because doing that
283 might prevent the earlier larger store to be eliminated. */
284 struct insn_info *redundant_reason;
287 /* Return a bitmask with the first N low bits set. */
289 static unsigned HOST_WIDE_INT
290 lowpart_bitmask (int n)
292 unsigned HOST_WIDE_INT mask = ~(unsigned HOST_WIDE_INT) 0;
293 return mask >> (HOST_BITS_PER_WIDE_INT - n);
296 typedef struct store_info *store_info_t;
297 static alloc_pool cse_store_info_pool;
298 static alloc_pool rtx_store_info_pool;
300 /* This structure holds information about a load. These are only
301 built for rtx bases. */
302 struct read_info
304 /* The id of the mem group of the base address. */
305 int group_id;
307 /* If this is non-zero, it is the alias set of a spill location. */
308 alias_set_type alias_set;
310 /* The offset of the first and byte after the last byte associated
311 with the operation. If begin == end == 0, the read did not have
312 a constant offset. */
313 int begin, end;
315 /* The mem being read. */
316 rtx mem;
318 /* The next read_info for this insn. */
319 struct read_info *next;
321 typedef struct read_info *read_info_t;
322 static alloc_pool read_info_pool;
325 /* One of these records is created for each insn. */
327 struct insn_info
329 /* Set true if the insn contains a store but the insn itself cannot
330 be deleted. This is set if the insn is a parallel and there is
331 more than one non dead output or if the insn is in some way
332 volatile. */
333 bool cannot_delete;
335 /* This field is only used by the global algorithm. It is set true
336 if the insn contains any read of mem except for a (1). This is
337 also set if the insn is a call or has a clobber mem. If the insn
338 contains a wild read, the use_rec will be null. */
339 bool wild_read;
341 /* This is true only for CALL instructions which could potentially read
342 any non-frame memory location. This field is used by the global
343 algorithm. */
344 bool non_frame_wild_read;
346 /* This field is only used for the processing of const functions.
347 These functions cannot read memory, but they can read the stack
348 because that is where they may get their parms. We need to be
349 this conservative because, like the store motion pass, we don't
350 consider CALL_INSN_FUNCTION_USAGE when processing call insns.
351 Moreover, we need to distinguish two cases:
352 1. Before reload (register elimination), the stores related to
353 outgoing arguments are stack pointer based and thus deemed
354 of non-constant base in this pass. This requires special
355 handling but also means that the frame pointer based stores
356 need not be killed upon encountering a const function call.
357 2. After reload, the stores related to outgoing arguments can be
358 either stack pointer or hard frame pointer based. This means
359 that we have no other choice than also killing all the frame
360 pointer based stores upon encountering a const function call.
361 This field is set after reload for const function calls. Having
362 this set is less severe than a wild read, it just means that all
363 the frame related stores are killed rather than all the stores. */
364 bool frame_read;
366 /* This field is only used for the processing of const functions.
367 It is set if the insn may contain a stack pointer based store. */
368 bool stack_pointer_based;
370 /* This is true if any of the sets within the store contains a
371 cselib base. Such stores can only be deleted by the local
372 algorithm. */
373 bool contains_cselib_groups;
375 /* The insn. */
376 rtx insn;
378 /* The list of mem sets or mem clobbers that are contained in this
379 insn. If the insn is deletable, it contains only one mem set.
380 But it could also contain clobbers. Insns that contain more than
381 one mem set are not deletable, but each of those mems are here in
382 order to provide info to delete other insns. */
383 store_info_t store_rec;
385 /* The linked list of mem uses in this insn. Only the reads from
386 rtx bases are listed here. The reads to cselib bases are
387 completely processed during the first scan and so are never
388 created. */
389 read_info_t read_rec;
391 /* The live fixed registers. We assume only fixed registers can
392 cause trouble by being clobbered from an expanded pattern;
393 storing only the live fixed registers (rather than all registers)
394 means less memory needs to be allocated / copied for the individual
395 stores. */
396 regset fixed_regs_live;
398 /* The prev insn in the basic block. */
399 struct insn_info * prev_insn;
401 /* The linked list of insns that are in consideration for removal in
402 the forwards pass through the basic block. This pointer may be
403 trash as it is not cleared when a wild read occurs. The only
404 time it is guaranteed to be correct is when the traversal starts
405 at active_local_stores. */
406 struct insn_info * next_local_store;
409 typedef struct insn_info *insn_info_t;
410 static alloc_pool insn_info_pool;
412 /* The linked list of stores that are under consideration in this
413 basic block. */
414 static insn_info_t active_local_stores;
415 static int active_local_stores_len;
417 struct bb_info
420 /* Pointer to the insn info for the last insn in the block. These
421 are linked so this is how all of the insns are reached. During
422 scanning this is the current insn being scanned. */
423 insn_info_t last_insn;
425 /* The info for the global dataflow problem. */
428 /* This is set if the transfer function should and in the wild_read
429 bitmap before applying the kill and gen sets. That vector knocks
430 out most of the bits in the bitmap and thus speeds up the
431 operations. */
432 bool apply_wild_read;
434 /* The following 4 bitvectors hold information about which positions
435 of which stores are live or dead. They are indexed by
436 get_bitmap_index. */
438 /* The set of store positions that exist in this block before a wild read. */
439 bitmap gen;
441 /* The set of load positions that exist in this block above the
442 same position of a store. */
443 bitmap kill;
445 /* The set of stores that reach the top of the block without being
446 killed by a read.
448 Do not represent the in if it is all ones. Note that this is
449 what the bitvector should logically be initialized to for a set
450 intersection problem. However, like the kill set, this is too
451 expensive. So initially, the in set will only be created for the
452 exit block and any block that contains a wild read. */
453 bitmap in;
455 /* The set of stores that reach the bottom of the block from it's
456 successors.
458 Do not represent the in if it is all ones. Note that this is
459 what the bitvector should logically be initialized to for a set
460 intersection problem. However, like the kill and in set, this is
461 too expensive. So what is done is that the confluence operator
462 just initializes the vector from one of the out sets of the
463 successors of the block. */
464 bitmap out;
466 /* The following bitvector is indexed by the reg number. It
467 contains the set of regs that are live at the current instruction
468 being processed. While it contains info for all of the
469 registers, only the hard registers are actually examined. It is used
470 to assure that shift and/or add sequences that are inserted do not
471 accidentally clobber live hard regs. */
472 bitmap regs_live;
475 typedef struct bb_info *bb_info_t;
476 static alloc_pool bb_info_pool;
478 /* Table to hold all bb_infos. */
479 static bb_info_t *bb_table;
481 /* There is a group_info for each rtx base that is used to reference
482 memory. There are also not many of the rtx bases because they are
483 very limited in scope. */
485 struct group_info
487 /* The actual base of the address. */
488 rtx rtx_base;
490 /* The sequential id of the base. This allows us to have a
491 canonical ordering of these that is not based on addresses. */
492 int id;
494 /* True if there are any positions that are to be processed
495 globally. */
496 bool process_globally;
498 /* True if the base of this group is either the frame_pointer or
499 hard_frame_pointer. */
500 bool frame_related;
502 /* A mem wrapped around the base pointer for the group in order to do
503 read dependency. It must be given BLKmode in order to encompass all
504 the possible offsets from the base. */
505 rtx base_mem;
507 /* Canonized version of base_mem's address. */
508 rtx canon_base_addr;
510 /* These two sets of two bitmaps are used to keep track of how many
511 stores are actually referencing that position from this base. We
512 only do this for rtx bases as this will be used to assign
513 positions in the bitmaps for the global problem. Bit N is set in
514 store1 on the first store for offset N. Bit N is set in store2
515 for the second store to offset N. This is all we need since we
516 only care about offsets that have two or more stores for them.
518 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
519 for 0 and greater offsets.
521 There is one special case here, for stores into the stack frame,
522 we will or store1 into store2 before deciding which stores look
523 at globally. This is because stores to the stack frame that have
524 no other reads before the end of the function can also be
525 deleted. */
526 bitmap store1_n, store1_p, store2_n, store2_p;
528 /* These bitmaps keep track of offsets in this group escape this function.
529 An offset escapes if it corresponds to a named variable whose
530 addressable flag is set. */
531 bitmap escaped_n, escaped_p;
533 /* The positions in this bitmap have the same assignments as the in,
534 out, gen and kill bitmaps. This bitmap is all zeros except for
535 the positions that are occupied by stores for this group. */
536 bitmap group_kill;
538 /* The offset_map is used to map the offsets from this base into
539 positions in the global bitmaps. It is only created after all of
540 the all of stores have been scanned and we know which ones we
541 care about. */
542 int *offset_map_n, *offset_map_p;
543 int offset_map_size_n, offset_map_size_p;
545 typedef struct group_info *group_info_t;
546 typedef const struct group_info *const_group_info_t;
547 static alloc_pool rtx_group_info_pool;
549 /* Index into the rtx_group_vec. */
550 static int rtx_group_next_id;
553 static vec<group_info_t> rtx_group_vec;
556 /* This structure holds the set of changes that are being deferred
557 when removing read operation. See replace_read. */
558 struct deferred_change
561 /* The mem that is being replaced. */
562 rtx *loc;
564 /* The reg it is being replaced with. */
565 rtx reg;
567 struct deferred_change *next;
570 typedef struct deferred_change *deferred_change_t;
571 static alloc_pool deferred_change_pool;
573 static deferred_change_t deferred_change_list = NULL;
575 /* The group that holds all of the clear_alias_sets. */
576 static group_info_t clear_alias_group;
578 /* The modes of the clear_alias_sets. */
579 static htab_t clear_alias_mode_table;
581 /* Hash table element to look up the mode for an alias set. */
582 struct clear_alias_mode_holder
584 alias_set_type alias_set;
585 enum machine_mode mode;
588 /* This is true except if cfun->stdarg -- i.e. we cannot do
589 this for vararg functions because they play games with the frame. */
590 static bool stores_off_frame_dead_at_return;
592 /* Counter for stats. */
593 static int globally_deleted;
594 static int locally_deleted;
595 static int spill_deleted;
597 static bitmap all_blocks;
599 /* Locations that are killed by calls in the global phase. */
600 static bitmap kill_on_calls;
602 /* The number of bits used in the global bitmaps. */
603 static unsigned int current_position;
606 static bool gate_dse1 (void);
607 static bool gate_dse2 (void);
610 /*----------------------------------------------------------------------------
611 Zeroth step.
613 Initialization.
614 ----------------------------------------------------------------------------*/
617 /* Find the entry associated with ALIAS_SET. */
619 static struct clear_alias_mode_holder *
620 clear_alias_set_lookup (alias_set_type alias_set)
622 struct clear_alias_mode_holder tmp_holder;
623 void **slot;
625 tmp_holder.alias_set = alias_set;
626 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, NO_INSERT);
627 gcc_assert (*slot);
629 return (struct clear_alias_mode_holder *) *slot;
633 /* Hashtable callbacks for maintaining the "bases" field of
634 store_group_info, given that the addresses are function invariants. */
636 struct invariant_group_base_hasher : typed_noop_remove <group_info>
638 typedef group_info value_type;
639 typedef group_info compare_type;
640 static inline hashval_t hash (const value_type *);
641 static inline bool equal (const value_type *, const compare_type *);
644 inline bool
645 invariant_group_base_hasher::equal (const value_type *gi1,
646 const compare_type *gi2)
648 return rtx_equal_p (gi1->rtx_base, gi2->rtx_base);
651 inline hashval_t
652 invariant_group_base_hasher::hash (const value_type *gi)
654 int do_not_record;
655 return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false);
658 /* Tables of group_info structures, hashed by base value. */
659 static hash_table <invariant_group_base_hasher> rtx_group_table;
662 /* Get the GROUP for BASE. Add a new group if it is not there. */
664 static group_info_t
665 get_group_info (rtx base)
667 struct group_info tmp_gi;
668 group_info_t gi;
669 group_info **slot;
671 if (base)
673 /* Find the store_base_info structure for BASE, creating a new one
674 if necessary. */
675 tmp_gi.rtx_base = base;
676 slot = rtx_group_table.find_slot (&tmp_gi, INSERT);
677 gi = (group_info_t) *slot;
679 else
681 if (!clear_alias_group)
683 clear_alias_group = gi =
684 (group_info_t) pool_alloc (rtx_group_info_pool);
685 memset (gi, 0, sizeof (struct group_info));
686 gi->id = rtx_group_next_id++;
687 gi->store1_n = BITMAP_ALLOC (&dse_bitmap_obstack);
688 gi->store1_p = BITMAP_ALLOC (&dse_bitmap_obstack);
689 gi->store2_n = BITMAP_ALLOC (&dse_bitmap_obstack);
690 gi->store2_p = BITMAP_ALLOC (&dse_bitmap_obstack);
691 gi->escaped_p = BITMAP_ALLOC (&dse_bitmap_obstack);
692 gi->escaped_n = BITMAP_ALLOC (&dse_bitmap_obstack);
693 gi->group_kill = BITMAP_ALLOC (&dse_bitmap_obstack);
694 gi->process_globally = false;
695 gi->offset_map_size_n = 0;
696 gi->offset_map_size_p = 0;
697 gi->offset_map_n = NULL;
698 gi->offset_map_p = NULL;
699 rtx_group_vec.safe_push (gi);
701 return clear_alias_group;
704 if (gi == NULL)
706 *slot = gi = (group_info_t) pool_alloc (rtx_group_info_pool);
707 gi->rtx_base = base;
708 gi->id = rtx_group_next_id++;
709 gi->base_mem = gen_rtx_MEM (BLKmode, base);
710 gi->canon_base_addr = canon_rtx (base);
711 gi->store1_n = BITMAP_ALLOC (&dse_bitmap_obstack);
712 gi->store1_p = BITMAP_ALLOC (&dse_bitmap_obstack);
713 gi->store2_n = BITMAP_ALLOC (&dse_bitmap_obstack);
714 gi->store2_p = BITMAP_ALLOC (&dse_bitmap_obstack);
715 gi->escaped_p = BITMAP_ALLOC (&dse_bitmap_obstack);
716 gi->escaped_n = BITMAP_ALLOC (&dse_bitmap_obstack);
717 gi->group_kill = BITMAP_ALLOC (&dse_bitmap_obstack);
718 gi->process_globally = false;
719 gi->frame_related =
720 (base == frame_pointer_rtx) || (base == hard_frame_pointer_rtx);
721 gi->offset_map_size_n = 0;
722 gi->offset_map_size_p = 0;
723 gi->offset_map_n = NULL;
724 gi->offset_map_p = NULL;
725 rtx_group_vec.safe_push (gi);
728 return gi;
732 /* Initialization of data structures. */
734 static void
735 dse_step0 (void)
737 locally_deleted = 0;
738 globally_deleted = 0;
739 spill_deleted = 0;
741 bitmap_obstack_initialize (&dse_bitmap_obstack);
742 gcc_obstack_init (&dse_obstack);
744 scratch = BITMAP_ALLOC (&reg_obstack);
745 kill_on_calls = BITMAP_ALLOC (&dse_bitmap_obstack);
747 rtx_store_info_pool
748 = create_alloc_pool ("rtx_store_info_pool",
749 sizeof (struct store_info), 100);
750 read_info_pool
751 = create_alloc_pool ("read_info_pool",
752 sizeof (struct read_info), 100);
753 insn_info_pool
754 = create_alloc_pool ("insn_info_pool",
755 sizeof (struct insn_info), 100);
756 bb_info_pool
757 = create_alloc_pool ("bb_info_pool",
758 sizeof (struct bb_info), 100);
759 rtx_group_info_pool
760 = create_alloc_pool ("rtx_group_info_pool",
761 sizeof (struct group_info), 100);
762 deferred_change_pool
763 = create_alloc_pool ("deferred_change_pool",
764 sizeof (struct deferred_change), 10);
766 rtx_group_table.create (11);
768 bb_table = XNEWVEC (bb_info_t, last_basic_block);
769 rtx_group_next_id = 0;
771 stores_off_frame_dead_at_return = !cfun->stdarg;
773 init_alias_analysis ();
775 clear_alias_group = NULL;
780 /*----------------------------------------------------------------------------
781 First step.
783 Scan all of the insns. Any random ordering of the blocks is fine.
784 Each block is scanned in forward order to accommodate cselib which
785 is used to remove stores with non-constant bases.
786 ----------------------------------------------------------------------------*/
788 /* Delete all of the store_info recs from INSN_INFO. */
790 static void
791 free_store_info (insn_info_t insn_info)
793 store_info_t store_info = insn_info->store_rec;
794 while (store_info)
796 store_info_t next = store_info->next;
797 if (store_info->is_large)
798 BITMAP_FREE (store_info->positions_needed.large.bmap);
799 if (store_info->cse_base)
800 pool_free (cse_store_info_pool, store_info);
801 else
802 pool_free (rtx_store_info_pool, store_info);
803 store_info = next;
806 insn_info->cannot_delete = true;
807 insn_info->contains_cselib_groups = false;
808 insn_info->store_rec = NULL;
811 typedef struct
813 rtx first, current;
814 regset fixed_regs_live;
815 bool failure;
816 } note_add_store_info;
818 /* Callback for emit_inc_dec_insn_before via note_stores.
819 Check if a register is clobbered which is live afterwards. */
821 static void
822 note_add_store (rtx loc, const_rtx expr ATTRIBUTE_UNUSED, void *data)
824 rtx insn;
825 note_add_store_info *info = (note_add_store_info *) data;
826 int r, n;
828 if (!REG_P (loc))
829 return;
831 /* If this register is referenced by the current or an earlier insn,
832 that's OK. E.g. this applies to the register that is being incremented
833 with this addition. */
834 for (insn = info->first;
835 insn != NEXT_INSN (info->current);
836 insn = NEXT_INSN (insn))
837 if (reg_referenced_p (loc, PATTERN (insn)))
838 return;
840 /* If we come here, we have a clobber of a register that's only OK
841 if that register is not live. If we don't have liveness information
842 available, fail now. */
843 if (!info->fixed_regs_live)
845 info->failure = true;
846 return;
848 /* Now check if this is a live fixed register. */
849 r = REGNO (loc);
850 n = hard_regno_nregs[r][GET_MODE (loc)];
851 while (--n >= 0)
852 if (REGNO_REG_SET_P (info->fixed_regs_live, r+n))
853 info->failure = true;
856 /* Callback for for_each_inc_dec that emits an INSN that sets DEST to
857 SRC + SRCOFF before insn ARG. */
859 static int
860 emit_inc_dec_insn_before (rtx mem ATTRIBUTE_UNUSED,
861 rtx op ATTRIBUTE_UNUSED,
862 rtx dest, rtx src, rtx srcoff, void *arg)
864 insn_info_t insn_info = (insn_info_t) arg;
865 rtx insn = insn_info->insn, new_insn, cur;
866 note_add_store_info info;
868 /* We can reuse all operands without copying, because we are about
869 to delete the insn that contained it. */
870 if (srcoff)
872 start_sequence ();
873 emit_insn (gen_add3_insn (dest, src, srcoff));
874 new_insn = get_insns ();
875 end_sequence ();
877 else
878 new_insn = gen_move_insn (dest, src);
879 info.first = new_insn;
880 info.fixed_regs_live = insn_info->fixed_regs_live;
881 info.failure = false;
882 for (cur = new_insn; cur; cur = NEXT_INSN (cur))
884 info.current = cur;
885 note_stores (PATTERN (cur), note_add_store, &info);
888 /* If a failure was flagged above, return 1 so that for_each_inc_dec will
889 return it immediately, communicating the failure to its caller. */
890 if (info.failure)
891 return 1;
893 emit_insn_before (new_insn, insn);
895 return -1;
898 /* Before we delete INSN_INFO->INSN, make sure that the auto inc/dec, if it
899 is there, is split into a separate insn.
900 Return true on success (or if there was nothing to do), false on failure. */
902 static bool
903 check_for_inc_dec_1 (insn_info_t insn_info)
905 rtx insn = insn_info->insn;
906 rtx note = find_reg_note (insn, REG_INC, NULL_RTX);
907 if (note)
908 return for_each_inc_dec (&insn, emit_inc_dec_insn_before, insn_info) == 0;
909 return true;
913 /* Entry point for postreload. If you work on reload_cse, or you need this
914 anywhere else, consider if you can provide register liveness information
915 and add a parameter to this function so that it can be passed down in
916 insn_info.fixed_regs_live. */
917 bool
918 check_for_inc_dec (rtx insn)
920 struct insn_info insn_info;
921 rtx note;
923 insn_info.insn = insn;
924 insn_info.fixed_regs_live = NULL;
925 note = find_reg_note (insn, REG_INC, NULL_RTX);
926 if (note)
927 return for_each_inc_dec (&insn, emit_inc_dec_insn_before, &insn_info) == 0;
928 return true;
931 /* Delete the insn and free all of the fields inside INSN_INFO. */
933 static void
934 delete_dead_store_insn (insn_info_t insn_info)
936 read_info_t read_info;
938 if (!dbg_cnt (dse))
939 return;
941 if (!check_for_inc_dec_1 (insn_info))
942 return;
943 if (dump_file && (dump_flags & TDF_DETAILS))
945 fprintf (dump_file, "Locally deleting insn %d ",
946 INSN_UID (insn_info->insn));
947 if (insn_info->store_rec->alias_set)
948 fprintf (dump_file, "alias set %d\n",
949 (int) insn_info->store_rec->alias_set);
950 else
951 fprintf (dump_file, "\n");
954 free_store_info (insn_info);
955 read_info = insn_info->read_rec;
957 while (read_info)
959 read_info_t next = read_info->next;
960 pool_free (read_info_pool, read_info);
961 read_info = next;
963 insn_info->read_rec = NULL;
965 delete_insn (insn_info->insn);
966 locally_deleted++;
967 insn_info->insn = NULL;
969 insn_info->wild_read = false;
972 /* Return whether DECL, a local variable, can possibly escape the current
973 function scope. */
975 static bool
976 local_variable_can_escape (tree decl)
978 if (TREE_ADDRESSABLE (decl))
979 return true;
981 /* If this is a partitioned variable, we need to consider all the variables
982 in the partition. This is necessary because a store into one of them can
983 be replaced with a store into another and this may not change the outcome
984 of the escape analysis. */
985 if (cfun->gimple_df->decls_to_pointers != NULL)
987 void *namep
988 = pointer_map_contains (cfun->gimple_df->decls_to_pointers, decl);
989 if (namep)
990 return TREE_ADDRESSABLE (*(tree *)namep);
993 return false;
996 /* Return whether EXPR can possibly escape the current function scope. */
998 static bool
999 can_escape (tree expr)
1001 tree base;
1002 if (!expr)
1003 return true;
1004 base = get_base_address (expr);
1005 if (DECL_P (base)
1006 && !may_be_aliased (base)
1007 && !(TREE_CODE (base) == VAR_DECL
1008 && !DECL_EXTERNAL (base)
1009 && !TREE_STATIC (base)
1010 && local_variable_can_escape (base)))
1011 return false;
1012 return true;
1015 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
1016 OFFSET and WIDTH. */
1018 static void
1019 set_usage_bits (group_info_t group, HOST_WIDE_INT offset, HOST_WIDE_INT width,
1020 tree expr)
1022 HOST_WIDE_INT i;
1023 bool expr_escapes = can_escape (expr);
1024 if (offset > -MAX_OFFSET && offset + width < MAX_OFFSET)
1025 for (i=offset; i<offset+width; i++)
1027 bitmap store1;
1028 bitmap store2;
1029 bitmap escaped;
1030 int ai;
1031 if (i < 0)
1033 store1 = group->store1_n;
1034 store2 = group->store2_n;
1035 escaped = group->escaped_n;
1036 ai = -i;
1038 else
1040 store1 = group->store1_p;
1041 store2 = group->store2_p;
1042 escaped = group->escaped_p;
1043 ai = i;
1046 if (!bitmap_set_bit (store1, ai))
1047 bitmap_set_bit (store2, ai);
1048 else
1050 if (i < 0)
1052 if (group->offset_map_size_n < ai)
1053 group->offset_map_size_n = ai;
1055 else
1057 if (group->offset_map_size_p < ai)
1058 group->offset_map_size_p = ai;
1061 if (expr_escapes)
1062 bitmap_set_bit (escaped, ai);
1066 static void
1067 reset_active_stores (void)
1069 active_local_stores = NULL;
1070 active_local_stores_len = 0;
1073 /* Free all READ_REC of the LAST_INSN of BB_INFO. */
1075 static void
1076 free_read_records (bb_info_t bb_info)
1078 insn_info_t insn_info = bb_info->last_insn;
1079 read_info_t *ptr = &insn_info->read_rec;
1080 while (*ptr)
1082 read_info_t next = (*ptr)->next;
1083 if ((*ptr)->alias_set == 0)
1085 pool_free (read_info_pool, *ptr);
1086 *ptr = next;
1088 else
1089 ptr = &(*ptr)->next;
1093 /* Set the BB_INFO so that the last insn is marked as a wild read. */
1095 static void
1096 add_wild_read (bb_info_t bb_info)
1098 insn_info_t insn_info = bb_info->last_insn;
1099 insn_info->wild_read = true;
1100 free_read_records (bb_info);
1101 reset_active_stores ();
1104 /* Set the BB_INFO so that the last insn is marked as a wild read of
1105 non-frame locations. */
1107 static void
1108 add_non_frame_wild_read (bb_info_t bb_info)
1110 insn_info_t insn_info = bb_info->last_insn;
1111 insn_info->non_frame_wild_read = true;
1112 free_read_records (bb_info);
1113 reset_active_stores ();
1116 /* Return true if X is a constant or one of the registers that behave
1117 as a constant over the life of a function. This is equivalent to
1118 !rtx_varies_p for memory addresses. */
1120 static bool
1121 const_or_frame_p (rtx x)
1123 if (CONSTANT_P (x))
1124 return true;
1126 if (GET_CODE (x) == REG)
1128 /* Note that we have to test for the actual rtx used for the frame
1129 and arg pointers and not just the register number in case we have
1130 eliminated the frame and/or arg pointer and are using it
1131 for pseudos. */
1132 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
1133 /* The arg pointer varies if it is not a fixed register. */
1134 || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
1135 || x == pic_offset_table_rtx)
1136 return true;
1137 return false;
1140 return false;
1143 /* Take all reasonable action to put the address of MEM into the form
1144 that we can do analysis on.
1146 The gold standard is to get the address into the form: address +
1147 OFFSET where address is something that rtx_varies_p considers a
1148 constant. When we can get the address in this form, we can do
1149 global analysis on it. Note that for constant bases, address is
1150 not actually returned, only the group_id. The address can be
1151 obtained from that.
1153 If that fails, we try cselib to get a value we can at least use
1154 locally. If that fails we return false.
1156 The GROUP_ID is set to -1 for cselib bases and the index of the
1157 group for non_varying bases.
1159 FOR_READ is true if this is a mem read and false if not. */
1161 static bool
1162 canon_address (rtx mem,
1163 alias_set_type *alias_set_out,
1164 int *group_id,
1165 HOST_WIDE_INT *offset,
1166 cselib_val **base)
1168 enum machine_mode address_mode = get_address_mode (mem);
1169 rtx mem_address = XEXP (mem, 0);
1170 rtx expanded_address, address;
1171 int expanded;
1173 *alias_set_out = 0;
1175 cselib_lookup (mem_address, address_mode, 1, GET_MODE (mem));
1177 if (dump_file && (dump_flags & TDF_DETAILS))
1179 fprintf (dump_file, " mem: ");
1180 print_inline_rtx (dump_file, mem_address, 0);
1181 fprintf (dump_file, "\n");
1184 /* First see if just canon_rtx (mem_address) is const or frame,
1185 if not, try cselib_expand_value_rtx and call canon_rtx on that. */
1186 address = NULL_RTX;
1187 for (expanded = 0; expanded < 2; expanded++)
1189 if (expanded)
1191 /* Use cselib to replace all of the reg references with the full
1192 expression. This will take care of the case where we have
1194 r_x = base + offset;
1195 val = *r_x;
1197 by making it into
1199 val = *(base + offset); */
1201 expanded_address = cselib_expand_value_rtx (mem_address,
1202 scratch, 5);
1204 /* If this fails, just go with the address from first
1205 iteration. */
1206 if (!expanded_address)
1207 break;
1209 else
1210 expanded_address = mem_address;
1212 /* Split the address into canonical BASE + OFFSET terms. */
1213 address = canon_rtx (expanded_address);
1215 *offset = 0;
1217 if (dump_file && (dump_flags & TDF_DETAILS))
1219 if (expanded)
1221 fprintf (dump_file, "\n after cselib_expand address: ");
1222 print_inline_rtx (dump_file, expanded_address, 0);
1223 fprintf (dump_file, "\n");
1226 fprintf (dump_file, "\n after canon_rtx address: ");
1227 print_inline_rtx (dump_file, address, 0);
1228 fprintf (dump_file, "\n");
1231 if (GET_CODE (address) == CONST)
1232 address = XEXP (address, 0);
1234 if (GET_CODE (address) == PLUS
1235 && CONST_INT_P (XEXP (address, 1)))
1237 *offset = INTVAL (XEXP (address, 1));
1238 address = XEXP (address, 0);
1241 if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem))
1242 && const_or_frame_p (address))
1244 group_info_t group = get_group_info (address);
1246 if (dump_file && (dump_flags & TDF_DETAILS))
1247 fprintf (dump_file, " gid=%d offset=%d \n",
1248 group->id, (int)*offset);
1249 *base = NULL;
1250 *group_id = group->id;
1251 return true;
1255 *base = cselib_lookup (address, address_mode, true, GET_MODE (mem));
1256 *group_id = -1;
1258 if (*base == NULL)
1260 if (dump_file && (dump_flags & TDF_DETAILS))
1261 fprintf (dump_file, " no cselib val - should be a wild read.\n");
1262 return false;
1264 if (dump_file && (dump_flags & TDF_DETAILS))
1265 fprintf (dump_file, " varying cselib base=%u:%u offset = %d\n",
1266 (*base)->uid, (*base)->hash, (int)*offset);
1267 return true;
1271 /* Clear the rhs field from the active_local_stores array. */
1273 static void
1274 clear_rhs_from_active_local_stores (void)
1276 insn_info_t ptr = active_local_stores;
1278 while (ptr)
1280 store_info_t store_info = ptr->store_rec;
1281 /* Skip the clobbers. */
1282 while (!store_info->is_set)
1283 store_info = store_info->next;
1285 store_info->rhs = NULL;
1286 store_info->const_rhs = NULL;
1288 ptr = ptr->next_local_store;
1293 /* Mark byte POS bytes from the beginning of store S_INFO as unneeded. */
1295 static inline void
1296 set_position_unneeded (store_info_t s_info, int pos)
1298 if (__builtin_expect (s_info->is_large, false))
1300 if (bitmap_set_bit (s_info->positions_needed.large.bmap, pos))
1301 s_info->positions_needed.large.count++;
1303 else
1304 s_info->positions_needed.small_bitmask
1305 &= ~(((unsigned HOST_WIDE_INT) 1) << pos);
1308 /* Mark the whole store S_INFO as unneeded. */
1310 static inline void
1311 set_all_positions_unneeded (store_info_t s_info)
1313 if (__builtin_expect (s_info->is_large, false))
1315 int pos, end = s_info->end - s_info->begin;
1316 for (pos = 0; pos < end; pos++)
1317 bitmap_set_bit (s_info->positions_needed.large.bmap, pos);
1318 s_info->positions_needed.large.count = end;
1320 else
1321 s_info->positions_needed.small_bitmask = (unsigned HOST_WIDE_INT) 0;
1324 /* Return TRUE if any bytes from S_INFO store are needed. */
1326 static inline bool
1327 any_positions_needed_p (store_info_t s_info)
1329 if (__builtin_expect (s_info->is_large, false))
1330 return (s_info->positions_needed.large.count
1331 < s_info->end - s_info->begin);
1332 else
1333 return (s_info->positions_needed.small_bitmask
1334 != (unsigned HOST_WIDE_INT) 0);
1337 /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
1338 store are needed. */
1340 static inline bool
1341 all_positions_needed_p (store_info_t s_info, int start, int width)
1343 if (__builtin_expect (s_info->is_large, false))
1345 int end = start + width;
1346 while (start < end)
1347 if (bitmap_bit_p (s_info->positions_needed.large.bmap, start++))
1348 return false;
1349 return true;
1351 else
1353 unsigned HOST_WIDE_INT mask = lowpart_bitmask (width) << start;
1354 return (s_info->positions_needed.small_bitmask & mask) == mask;
1359 static rtx get_stored_val (store_info_t, enum machine_mode, HOST_WIDE_INT,
1360 HOST_WIDE_INT, basic_block, bool);
1363 /* BODY is an instruction pattern that belongs to INSN. Return 1 if
1364 there is a candidate store, after adding it to the appropriate
1365 local store group if so. */
1367 static int
1368 record_store (rtx body, bb_info_t bb_info)
1370 rtx mem, rhs, const_rhs, mem_addr;
1371 HOST_WIDE_INT offset = 0;
1372 HOST_WIDE_INT width = 0;
1373 alias_set_type spill_alias_set;
1374 insn_info_t insn_info = bb_info->last_insn;
1375 store_info_t store_info = NULL;
1376 int group_id;
1377 cselib_val *base = NULL;
1378 insn_info_t ptr, last, redundant_reason;
1379 bool store_is_unused;
1381 if (GET_CODE (body) != SET && GET_CODE (body) != CLOBBER)
1382 return 0;
1384 mem = SET_DEST (body);
1386 /* If this is not used, then this cannot be used to keep the insn
1387 from being deleted. On the other hand, it does provide something
1388 that can be used to prove that another store is dead. */
1389 store_is_unused
1390 = (find_reg_note (insn_info->insn, REG_UNUSED, mem) != NULL);
1392 /* Check whether that value is a suitable memory location. */
1393 if (!MEM_P (mem))
1395 /* If the set or clobber is unused, then it does not effect our
1396 ability to get rid of the entire insn. */
1397 if (!store_is_unused)
1398 insn_info->cannot_delete = true;
1399 return 0;
1402 /* At this point we know mem is a mem. */
1403 if (GET_MODE (mem) == BLKmode)
1405 if (GET_CODE (XEXP (mem, 0)) == SCRATCH)
1407 if (dump_file && (dump_flags & TDF_DETAILS))
1408 fprintf (dump_file, " adding wild read for (clobber (mem:BLK (scratch))\n");
1409 add_wild_read (bb_info);
1410 insn_info->cannot_delete = true;
1411 return 0;
1413 /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
1414 as memset (addr, 0, 36); */
1415 else if (!MEM_SIZE_KNOWN_P (mem)
1416 || MEM_SIZE (mem) <= 0
1417 || MEM_SIZE (mem) > MAX_OFFSET
1418 || GET_CODE (body) != SET
1419 || !CONST_INT_P (SET_SRC (body)))
1421 if (!store_is_unused)
1423 /* If the set or clobber is unused, then it does not effect our
1424 ability to get rid of the entire insn. */
1425 insn_info->cannot_delete = true;
1426 clear_rhs_from_active_local_stores ();
1428 return 0;
1432 /* We can still process a volatile mem, we just cannot delete it. */
1433 if (MEM_VOLATILE_P (mem))
1434 insn_info->cannot_delete = true;
1436 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
1438 clear_rhs_from_active_local_stores ();
1439 return 0;
1442 if (GET_MODE (mem) == BLKmode)
1443 width = MEM_SIZE (mem);
1444 else
1445 width = GET_MODE_SIZE (GET_MODE (mem));
1447 if (spill_alias_set)
1449 bitmap store1 = clear_alias_group->store1_p;
1450 bitmap store2 = clear_alias_group->store2_p;
1452 gcc_assert (GET_MODE (mem) != BLKmode);
1454 if (!bitmap_set_bit (store1, spill_alias_set))
1455 bitmap_set_bit (store2, spill_alias_set);
1457 if (clear_alias_group->offset_map_size_p < spill_alias_set)
1458 clear_alias_group->offset_map_size_p = spill_alias_set;
1460 store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1462 if (dump_file && (dump_flags & TDF_DETAILS))
1463 fprintf (dump_file, " processing spill store %d(%s)\n",
1464 (int) spill_alias_set, GET_MODE_NAME (GET_MODE (mem)));
1466 else if (group_id >= 0)
1468 /* In the restrictive case where the base is a constant or the
1469 frame pointer we can do global analysis. */
1471 group_info_t group
1472 = rtx_group_vec[group_id];
1473 tree expr = MEM_EXPR (mem);
1475 store_info = (store_info_t) pool_alloc (rtx_store_info_pool);
1476 set_usage_bits (group, offset, width, expr);
1478 if (dump_file && (dump_flags & TDF_DETAILS))
1479 fprintf (dump_file, " processing const base store gid=%d[%d..%d)\n",
1480 group_id, (int)offset, (int)(offset+width));
1482 else
1484 if (may_be_sp_based_p (XEXP (mem, 0)))
1485 insn_info->stack_pointer_based = true;
1486 insn_info->contains_cselib_groups = true;
1488 store_info = (store_info_t) pool_alloc (cse_store_info_pool);
1489 group_id = -1;
1491 if (dump_file && (dump_flags & TDF_DETAILS))
1492 fprintf (dump_file, " processing cselib store [%d..%d)\n",
1493 (int)offset, (int)(offset+width));
1496 const_rhs = rhs = NULL_RTX;
1497 if (GET_CODE (body) == SET
1498 /* No place to keep the value after ra. */
1499 && !reload_completed
1500 && (REG_P (SET_SRC (body))
1501 || GET_CODE (SET_SRC (body)) == SUBREG
1502 || CONSTANT_P (SET_SRC (body)))
1503 && !MEM_VOLATILE_P (mem)
1504 /* Sometimes the store and reload is used for truncation and
1505 rounding. */
1506 && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
1508 rhs = SET_SRC (body);
1509 if (CONSTANT_P (rhs))
1510 const_rhs = rhs;
1511 else if (body == PATTERN (insn_info->insn))
1513 rtx tem = find_reg_note (insn_info->insn, REG_EQUAL, NULL_RTX);
1514 if (tem && CONSTANT_P (XEXP (tem, 0)))
1515 const_rhs = XEXP (tem, 0);
1517 if (const_rhs == NULL_RTX && REG_P (rhs))
1519 rtx tem = cselib_expand_value_rtx (rhs, scratch, 5);
1521 if (tem && CONSTANT_P (tem))
1522 const_rhs = tem;
1526 /* Check to see if this stores causes some other stores to be
1527 dead. */
1528 ptr = active_local_stores;
1529 last = NULL;
1530 redundant_reason = NULL;
1531 mem = canon_rtx (mem);
1532 /* For alias_set != 0 canon_true_dependence should be never called. */
1533 if (spill_alias_set)
1534 mem_addr = NULL_RTX;
1535 else
1537 if (group_id < 0)
1538 mem_addr = base->val_rtx;
1539 else
1541 group_info_t group
1542 = rtx_group_vec[group_id];
1543 mem_addr = group->canon_base_addr;
1545 if (offset)
1546 mem_addr = plus_constant (get_address_mode (mem), mem_addr, offset);
1549 while (ptr)
1551 insn_info_t next = ptr->next_local_store;
1552 store_info_t s_info = ptr->store_rec;
1553 bool del = true;
1555 /* Skip the clobbers. We delete the active insn if this insn
1556 shadows the set. To have been put on the active list, it
1557 has exactly on set. */
1558 while (!s_info->is_set)
1559 s_info = s_info->next;
1561 if (s_info->alias_set != spill_alias_set)
1562 del = false;
1563 else if (s_info->alias_set)
1565 struct clear_alias_mode_holder *entry
1566 = clear_alias_set_lookup (s_info->alias_set);
1567 /* Generally, spills cannot be processed if and of the
1568 references to the slot have a different mode. But if
1569 we are in the same block and mode is exactly the same
1570 between this store and one before in the same block,
1571 we can still delete it. */
1572 if ((GET_MODE (mem) == GET_MODE (s_info->mem))
1573 && (GET_MODE (mem) == entry->mode))
1575 del = true;
1576 set_all_positions_unneeded (s_info);
1578 if (dump_file && (dump_flags & TDF_DETAILS))
1579 fprintf (dump_file, " trying spill store in insn=%d alias_set=%d\n",
1580 INSN_UID (ptr->insn), (int) s_info->alias_set);
1582 else if ((s_info->group_id == group_id)
1583 && (s_info->cse_base == base))
1585 HOST_WIDE_INT i;
1586 if (dump_file && (dump_flags & TDF_DETAILS))
1587 fprintf (dump_file, " trying store in insn=%d gid=%d[%d..%d)\n",
1588 INSN_UID (ptr->insn), s_info->group_id,
1589 (int)s_info->begin, (int)s_info->end);
1591 /* Even if PTR won't be eliminated as unneeded, if both
1592 PTR and this insn store the same constant value, we might
1593 eliminate this insn instead. */
1594 if (s_info->const_rhs
1595 && const_rhs
1596 && offset >= s_info->begin
1597 && offset + width <= s_info->end
1598 && all_positions_needed_p (s_info, offset - s_info->begin,
1599 width))
1601 if (GET_MODE (mem) == BLKmode)
1603 if (GET_MODE (s_info->mem) == BLKmode
1604 && s_info->const_rhs == const_rhs)
1605 redundant_reason = ptr;
1607 else if (s_info->const_rhs == const0_rtx
1608 && const_rhs == const0_rtx)
1609 redundant_reason = ptr;
1610 else
1612 rtx val;
1613 start_sequence ();
1614 val = get_stored_val (s_info, GET_MODE (mem),
1615 offset, offset + width,
1616 BLOCK_FOR_INSN (insn_info->insn),
1617 true);
1618 if (get_insns () != NULL)
1619 val = NULL_RTX;
1620 end_sequence ();
1621 if (val && rtx_equal_p (val, const_rhs))
1622 redundant_reason = ptr;
1626 for (i = MAX (offset, s_info->begin);
1627 i < offset + width && i < s_info->end;
1628 i++)
1629 set_position_unneeded (s_info, i - s_info->begin);
1631 else if (s_info->rhs)
1632 /* Need to see if it is possible for this store to overwrite
1633 the value of store_info. If it is, set the rhs to NULL to
1634 keep it from being used to remove a load. */
1636 if (canon_true_dependence (s_info->mem,
1637 GET_MODE (s_info->mem),
1638 s_info->mem_addr,
1639 mem, mem_addr))
1641 s_info->rhs = NULL;
1642 s_info->const_rhs = NULL;
1646 /* An insn can be deleted if every position of every one of
1647 its s_infos is zero. */
1648 if (any_positions_needed_p (s_info))
1649 del = false;
1651 if (del)
1653 insn_info_t insn_to_delete = ptr;
1655 active_local_stores_len--;
1656 if (last)
1657 last->next_local_store = ptr->next_local_store;
1658 else
1659 active_local_stores = ptr->next_local_store;
1661 if (!insn_to_delete->cannot_delete)
1662 delete_dead_store_insn (insn_to_delete);
1664 else
1665 last = ptr;
1667 ptr = next;
1670 /* Finish filling in the store_info. */
1671 store_info->next = insn_info->store_rec;
1672 insn_info->store_rec = store_info;
1673 store_info->mem = mem;
1674 store_info->alias_set = spill_alias_set;
1675 store_info->mem_addr = mem_addr;
1676 store_info->cse_base = base;
1677 if (width > HOST_BITS_PER_WIDE_INT)
1679 store_info->is_large = true;
1680 store_info->positions_needed.large.count = 0;
1681 store_info->positions_needed.large.bmap = BITMAP_ALLOC (&dse_bitmap_obstack);
1683 else
1685 store_info->is_large = false;
1686 store_info->positions_needed.small_bitmask = lowpart_bitmask (width);
1688 store_info->group_id = group_id;
1689 store_info->begin = offset;
1690 store_info->end = offset + width;
1691 store_info->is_set = GET_CODE (body) == SET;
1692 store_info->rhs = rhs;
1693 store_info->const_rhs = const_rhs;
1694 store_info->redundant_reason = redundant_reason;
1696 /* If this is a clobber, we return 0. We will only be able to
1697 delete this insn if there is only one store USED store, but we
1698 can use the clobber to delete other stores earlier. */
1699 return store_info->is_set ? 1 : 0;
1703 static void
1704 dump_insn_info (const char * start, insn_info_t insn_info)
1706 fprintf (dump_file, "%s insn=%d %s\n", start,
1707 INSN_UID (insn_info->insn),
1708 insn_info->store_rec ? "has store" : "naked");
1712 /* If the modes are different and the value's source and target do not
1713 line up, we need to extract the value from lower part of the rhs of
1714 the store, shift it, and then put it into a form that can be shoved
1715 into the read_insn. This function generates a right SHIFT of a
1716 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The
1717 shift sequence is returned or NULL if we failed to find a
1718 shift. */
1720 static rtx
1721 find_shift_sequence (int access_size,
1722 store_info_t store_info,
1723 enum machine_mode read_mode,
1724 int shift, bool speed, bool require_cst)
1726 enum machine_mode store_mode = GET_MODE (store_info->mem);
1727 enum machine_mode new_mode;
1728 rtx read_reg = NULL;
1730 /* Some machines like the x86 have shift insns for each size of
1731 operand. Other machines like the ppc or the ia-64 may only have
1732 shift insns that shift values within 32 or 64 bit registers.
1733 This loop tries to find the smallest shift insn that will right
1734 justify the value we want to read but is available in one insn on
1735 the machine. */
1737 for (new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
1738 MODE_INT);
1739 GET_MODE_BITSIZE (new_mode) <= BITS_PER_WORD;
1740 new_mode = GET_MODE_WIDER_MODE (new_mode))
1742 rtx target, new_reg, shift_seq, insn, new_lhs;
1743 int cost;
1745 /* If a constant was stored into memory, try to simplify it here,
1746 otherwise the cost of the shift might preclude this optimization
1747 e.g. at -Os, even when no actual shift will be needed. */
1748 if (store_info->const_rhs)
1750 unsigned int byte = subreg_lowpart_offset (new_mode, store_mode);
1751 rtx ret = simplify_subreg (new_mode, store_info->const_rhs,
1752 store_mode, byte);
1753 if (ret && CONSTANT_P (ret))
1755 ret = simplify_const_binary_operation (LSHIFTRT, new_mode,
1756 ret, GEN_INT (shift));
1757 if (ret && CONSTANT_P (ret))
1759 byte = subreg_lowpart_offset (read_mode, new_mode);
1760 ret = simplify_subreg (read_mode, ret, new_mode, byte);
1761 if (ret && CONSTANT_P (ret)
1762 && set_src_cost (ret, speed) <= COSTS_N_INSNS (1))
1763 return ret;
1768 if (require_cst)
1769 return NULL_RTX;
1771 /* Try a wider mode if truncating the store mode to NEW_MODE
1772 requires a real instruction. */
1773 if (GET_MODE_BITSIZE (new_mode) < GET_MODE_BITSIZE (store_mode)
1774 && !TRULY_NOOP_TRUNCATION_MODES_P (new_mode, store_mode))
1775 continue;
1777 /* Also try a wider mode if the necessary punning is either not
1778 desirable or not possible. */
1779 if (!CONSTANT_P (store_info->rhs)
1780 && !MODES_TIEABLE_P (new_mode, store_mode))
1781 continue;
1783 new_reg = gen_reg_rtx (new_mode);
1785 start_sequence ();
1787 /* In theory we could also check for an ashr. Ian Taylor knows
1788 of one dsp where the cost of these two was not the same. But
1789 this really is a rare case anyway. */
1790 target = expand_binop (new_mode, lshr_optab, new_reg,
1791 GEN_INT (shift), new_reg, 1, OPTAB_DIRECT);
1793 shift_seq = get_insns ();
1794 end_sequence ();
1796 if (target != new_reg || shift_seq == NULL)
1797 continue;
1799 cost = 0;
1800 for (insn = shift_seq; insn != NULL_RTX; insn = NEXT_INSN (insn))
1801 if (INSN_P (insn))
1802 cost += insn_rtx_cost (PATTERN (insn), speed);
1804 /* The computation up to here is essentially independent
1805 of the arguments and could be precomputed. It may
1806 not be worth doing so. We could precompute if
1807 worthwhile or at least cache the results. The result
1808 technically depends on both SHIFT and ACCESS_SIZE,
1809 but in practice the answer will depend only on ACCESS_SIZE. */
1811 if (cost > COSTS_N_INSNS (1))
1812 continue;
1814 new_lhs = extract_low_bits (new_mode, store_mode,
1815 copy_rtx (store_info->rhs));
1816 if (new_lhs == NULL_RTX)
1817 continue;
1819 /* We found an acceptable shift. Generate a move to
1820 take the value from the store and put it into the
1821 shift pseudo, then shift it, then generate another
1822 move to put in into the target of the read. */
1823 emit_move_insn (new_reg, new_lhs);
1824 emit_insn (shift_seq);
1825 read_reg = extract_low_bits (read_mode, new_mode, new_reg);
1826 break;
1829 return read_reg;
1833 /* Call back for note_stores to find the hard regs set or clobbered by
1834 insn. Data is a bitmap of the hardregs set so far. */
1836 static void
1837 look_for_hardregs (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
1839 bitmap regs_set = (bitmap) data;
1841 if (REG_P (x)
1842 && HARD_REGISTER_P (x))
1844 unsigned int regno = REGNO (x);
1845 bitmap_set_range (regs_set, regno,
1846 hard_regno_nregs[regno][GET_MODE (x)]);
1850 /* Helper function for replace_read and record_store.
1851 Attempt to return a value stored in STORE_INFO, from READ_BEGIN
1852 to one before READ_END bytes read in READ_MODE. Return NULL
1853 if not successful. If REQUIRE_CST is true, return always constant. */
1855 static rtx
1856 get_stored_val (store_info_t store_info, enum machine_mode read_mode,
1857 HOST_WIDE_INT read_begin, HOST_WIDE_INT read_end,
1858 basic_block bb, bool require_cst)
1860 enum machine_mode store_mode = GET_MODE (store_info->mem);
1861 int shift;
1862 int access_size; /* In bytes. */
1863 rtx read_reg;
1865 /* To get here the read is within the boundaries of the write so
1866 shift will never be negative. Start out with the shift being in
1867 bytes. */
1868 if (store_mode == BLKmode)
1869 shift = 0;
1870 else if (BYTES_BIG_ENDIAN)
1871 shift = store_info->end - read_end;
1872 else
1873 shift = read_begin - store_info->begin;
1875 access_size = shift + GET_MODE_SIZE (read_mode);
1877 /* From now on it is bits. */
1878 shift *= BITS_PER_UNIT;
1880 if (shift)
1881 read_reg = find_shift_sequence (access_size, store_info, read_mode, shift,
1882 optimize_bb_for_speed_p (bb),
1883 require_cst);
1884 else if (store_mode == BLKmode)
1886 /* The store is a memset (addr, const_val, const_size). */
1887 gcc_assert (CONST_INT_P (store_info->rhs));
1888 store_mode = int_mode_for_mode (read_mode);
1889 if (store_mode == BLKmode)
1890 read_reg = NULL_RTX;
1891 else if (store_info->rhs == const0_rtx)
1892 read_reg = extract_low_bits (read_mode, store_mode, const0_rtx);
1893 else if (GET_MODE_BITSIZE (store_mode) > HOST_BITS_PER_WIDE_INT
1894 || BITS_PER_UNIT >= HOST_BITS_PER_WIDE_INT)
1895 read_reg = NULL_RTX;
1896 else
1898 unsigned HOST_WIDE_INT c
1899 = INTVAL (store_info->rhs)
1900 & (((HOST_WIDE_INT) 1 << BITS_PER_UNIT) - 1);
1901 int shift = BITS_PER_UNIT;
1902 while (shift < HOST_BITS_PER_WIDE_INT)
1904 c |= (c << shift);
1905 shift <<= 1;
1907 read_reg = gen_int_mode (c, store_mode);
1908 read_reg = extract_low_bits (read_mode, store_mode, read_reg);
1911 else if (store_info->const_rhs
1912 && (require_cst
1913 || GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode)))
1914 read_reg = extract_low_bits (read_mode, store_mode,
1915 copy_rtx (store_info->const_rhs));
1916 else
1917 read_reg = extract_low_bits (read_mode, store_mode,
1918 copy_rtx (store_info->rhs));
1919 if (require_cst && read_reg && !CONSTANT_P (read_reg))
1920 read_reg = NULL_RTX;
1921 return read_reg;
1924 /* Take a sequence of:
1925 A <- r1
1927 ... <- A
1929 and change it into
1930 r2 <- r1
1931 A <- r1
1933 ... <- r2
1937 r3 <- extract (r1)
1938 r3 <- r3 >> shift
1939 r2 <- extract (r3)
1940 ... <- r2
1944 r2 <- extract (r1)
1945 ... <- r2
1947 Depending on the alignment and the mode of the store and
1948 subsequent load.
1951 The STORE_INFO and STORE_INSN are for the store and READ_INFO
1952 and READ_INSN are for the read. Return true if the replacement
1953 went ok. */
1955 static bool
1956 replace_read (store_info_t store_info, insn_info_t store_insn,
1957 read_info_t read_info, insn_info_t read_insn, rtx *loc,
1958 bitmap regs_live)
1960 enum machine_mode store_mode = GET_MODE (store_info->mem);
1961 enum machine_mode read_mode = GET_MODE (read_info->mem);
1962 rtx insns, this_insn, read_reg;
1963 basic_block bb;
1965 if (!dbg_cnt (dse))
1966 return false;
1968 /* Create a sequence of instructions to set up the read register.
1969 This sequence goes immediately before the store and its result
1970 is read by the load.
1972 We need to keep this in perspective. We are replacing a read
1973 with a sequence of insns, but the read will almost certainly be
1974 in cache, so it is not going to be an expensive one. Thus, we
1975 are not willing to do a multi insn shift or worse a subroutine
1976 call to get rid of the read. */
1977 if (dump_file && (dump_flags & TDF_DETAILS))
1978 fprintf (dump_file, "trying to replace %smode load in insn %d"
1979 " from %smode store in insn %d\n",
1980 GET_MODE_NAME (read_mode), INSN_UID (read_insn->insn),
1981 GET_MODE_NAME (store_mode), INSN_UID (store_insn->insn));
1982 start_sequence ();
1983 bb = BLOCK_FOR_INSN (read_insn->insn);
1984 read_reg = get_stored_val (store_info,
1985 read_mode, read_info->begin, read_info->end,
1986 bb, false);
1987 if (read_reg == NULL_RTX)
1989 end_sequence ();
1990 if (dump_file && (dump_flags & TDF_DETAILS))
1991 fprintf (dump_file, " -- could not extract bits of stored value\n");
1992 return false;
1994 /* Force the value into a new register so that it won't be clobbered
1995 between the store and the load. */
1996 read_reg = copy_to_mode_reg (read_mode, read_reg);
1997 insns = get_insns ();
1998 end_sequence ();
2000 if (insns != NULL_RTX)
2002 /* Now we have to scan the set of new instructions to see if the
2003 sequence contains and sets of hardregs that happened to be
2004 live at this point. For instance, this can happen if one of
2005 the insns sets the CC and the CC happened to be live at that
2006 point. This does occasionally happen, see PR 37922. */
2007 bitmap regs_set = BITMAP_ALLOC (&reg_obstack);
2009 for (this_insn = insns; this_insn != NULL_RTX; this_insn = NEXT_INSN (this_insn))
2010 note_stores (PATTERN (this_insn), look_for_hardregs, regs_set);
2012 bitmap_and_into (regs_set, regs_live);
2013 if (!bitmap_empty_p (regs_set))
2015 if (dump_file && (dump_flags & TDF_DETAILS))
2017 fprintf (dump_file,
2018 "abandoning replacement because sequence clobbers live hardregs:");
2019 df_print_regset (dump_file, regs_set);
2022 BITMAP_FREE (regs_set);
2023 return false;
2025 BITMAP_FREE (regs_set);
2028 if (validate_change (read_insn->insn, loc, read_reg, 0))
2030 deferred_change_t deferred_change =
2031 (deferred_change_t) pool_alloc (deferred_change_pool);
2033 /* Insert this right before the store insn where it will be safe
2034 from later insns that might change it before the read. */
2035 emit_insn_before (insns, store_insn->insn);
2037 /* And now for the kludge part: cselib croaks if you just
2038 return at this point. There are two reasons for this:
2040 1) Cselib has an idea of how many pseudos there are and
2041 that does not include the new ones we just added.
2043 2) Cselib does not know about the move insn we added
2044 above the store_info, and there is no way to tell it
2045 about it, because it has "moved on".
2047 Problem (1) is fixable with a certain amount of engineering.
2048 Problem (2) is requires starting the bb from scratch. This
2049 could be expensive.
2051 So we are just going to have to lie. The move/extraction
2052 insns are not really an issue, cselib did not see them. But
2053 the use of the new pseudo read_insn is a real problem because
2054 cselib has not scanned this insn. The way that we solve this
2055 problem is that we are just going to put the mem back for now
2056 and when we are finished with the block, we undo this. We
2057 keep a table of mems to get rid of. At the end of the basic
2058 block we can put them back. */
2060 *loc = read_info->mem;
2061 deferred_change->next = deferred_change_list;
2062 deferred_change_list = deferred_change;
2063 deferred_change->loc = loc;
2064 deferred_change->reg = read_reg;
2066 /* Get rid of the read_info, from the point of view of the
2067 rest of dse, play like this read never happened. */
2068 read_insn->read_rec = read_info->next;
2069 pool_free (read_info_pool, read_info);
2070 if (dump_file && (dump_flags & TDF_DETAILS))
2072 fprintf (dump_file, " -- replaced the loaded MEM with ");
2073 print_simple_rtl (dump_file, read_reg);
2074 fprintf (dump_file, "\n");
2076 return true;
2078 else
2080 if (dump_file && (dump_flags & TDF_DETAILS))
2082 fprintf (dump_file, " -- replacing the loaded MEM with ");
2083 print_simple_rtl (dump_file, read_reg);
2084 fprintf (dump_file, " led to an invalid instruction\n");
2086 return false;
2090 /* A for_each_rtx callback in which DATA is the bb_info. Check to see
2091 if LOC is a mem and if it is look at the address and kill any
2092 appropriate stores that may be active. */
2094 static int
2095 check_mem_read_rtx (rtx *loc, void *data)
2097 rtx mem = *loc, mem_addr;
2098 bb_info_t bb_info;
2099 insn_info_t insn_info;
2100 HOST_WIDE_INT offset = 0;
2101 HOST_WIDE_INT width = 0;
2102 alias_set_type spill_alias_set = 0;
2103 cselib_val *base = NULL;
2104 int group_id;
2105 read_info_t read_info;
2107 if (!mem || !MEM_P (mem))
2108 return 0;
2110 bb_info = (bb_info_t) data;
2111 insn_info = bb_info->last_insn;
2113 if ((MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2114 || (MEM_VOLATILE_P (mem)))
2116 if (dump_file && (dump_flags & TDF_DETAILS))
2117 fprintf (dump_file, " adding wild read, volatile or barrier.\n");
2118 add_wild_read (bb_info);
2119 insn_info->cannot_delete = true;
2120 return 0;
2123 /* If it is reading readonly mem, then there can be no conflict with
2124 another write. */
2125 if (MEM_READONLY_P (mem))
2126 return 0;
2128 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
2130 if (dump_file && (dump_flags & TDF_DETAILS))
2131 fprintf (dump_file, " adding wild read, canon_address failure.\n");
2132 add_wild_read (bb_info);
2133 return 0;
2136 if (GET_MODE (mem) == BLKmode)
2137 width = -1;
2138 else
2139 width = GET_MODE_SIZE (GET_MODE (mem));
2141 read_info = (read_info_t) pool_alloc (read_info_pool);
2142 read_info->group_id = group_id;
2143 read_info->mem = mem;
2144 read_info->alias_set = spill_alias_set;
2145 read_info->begin = offset;
2146 read_info->end = offset + width;
2147 read_info->next = insn_info->read_rec;
2148 insn_info->read_rec = read_info;
2149 /* For alias_set != 0 canon_true_dependence should be never called. */
2150 if (spill_alias_set)
2151 mem_addr = NULL_RTX;
2152 else
2154 if (group_id < 0)
2155 mem_addr = base->val_rtx;
2156 else
2158 group_info_t group
2159 = rtx_group_vec[group_id];
2160 mem_addr = group->canon_base_addr;
2162 if (offset)
2163 mem_addr = plus_constant (get_address_mode (mem), mem_addr, offset);
2166 /* We ignore the clobbers in store_info. The is mildly aggressive,
2167 but there really should not be a clobber followed by a read. */
2169 if (spill_alias_set)
2171 insn_info_t i_ptr = active_local_stores;
2172 insn_info_t last = NULL;
2174 if (dump_file && (dump_flags & TDF_DETAILS))
2175 fprintf (dump_file, " processing spill load %d\n",
2176 (int) spill_alias_set);
2178 while (i_ptr)
2180 store_info_t store_info = i_ptr->store_rec;
2182 /* Skip the clobbers. */
2183 while (!store_info->is_set)
2184 store_info = store_info->next;
2186 if (store_info->alias_set == spill_alias_set)
2188 if (dump_file && (dump_flags & TDF_DETAILS))
2189 dump_insn_info ("removing from active", i_ptr);
2191 active_local_stores_len--;
2192 if (last)
2193 last->next_local_store = i_ptr->next_local_store;
2194 else
2195 active_local_stores = i_ptr->next_local_store;
2197 else
2198 last = i_ptr;
2199 i_ptr = i_ptr->next_local_store;
2202 else if (group_id >= 0)
2204 /* This is the restricted case where the base is a constant or
2205 the frame pointer and offset is a constant. */
2206 insn_info_t i_ptr = active_local_stores;
2207 insn_info_t last = NULL;
2209 if (dump_file && (dump_flags & TDF_DETAILS))
2211 if (width == -1)
2212 fprintf (dump_file, " processing const load gid=%d[BLK]\n",
2213 group_id);
2214 else
2215 fprintf (dump_file, " processing const load gid=%d[%d..%d)\n",
2216 group_id, (int)offset, (int)(offset+width));
2219 while (i_ptr)
2221 bool remove = false;
2222 store_info_t store_info = i_ptr->store_rec;
2224 /* Skip the clobbers. */
2225 while (!store_info->is_set)
2226 store_info = store_info->next;
2228 /* There are three cases here. */
2229 if (store_info->group_id < 0)
2230 /* We have a cselib store followed by a read from a
2231 const base. */
2232 remove
2233 = canon_true_dependence (store_info->mem,
2234 GET_MODE (store_info->mem),
2235 store_info->mem_addr,
2236 mem, mem_addr);
2238 else if (group_id == store_info->group_id)
2240 /* This is a block mode load. We may get lucky and
2241 canon_true_dependence may save the day. */
2242 if (width == -1)
2243 remove
2244 = canon_true_dependence (store_info->mem,
2245 GET_MODE (store_info->mem),
2246 store_info->mem_addr,
2247 mem, mem_addr);
2249 /* If this read is just reading back something that we just
2250 stored, rewrite the read. */
2251 else
2253 if (store_info->rhs
2254 && offset >= store_info->begin
2255 && offset + width <= store_info->end
2256 && all_positions_needed_p (store_info,
2257 offset - store_info->begin,
2258 width)
2259 && replace_read (store_info, i_ptr, read_info,
2260 insn_info, loc, bb_info->regs_live))
2261 return 0;
2263 /* The bases are the same, just see if the offsets
2264 overlap. */
2265 if ((offset < store_info->end)
2266 && (offset + width > store_info->begin))
2267 remove = true;
2271 /* else
2272 The else case that is missing here is that the
2273 bases are constant but different. There is nothing
2274 to do here because there is no overlap. */
2276 if (remove)
2278 if (dump_file && (dump_flags & TDF_DETAILS))
2279 dump_insn_info ("removing from active", i_ptr);
2281 active_local_stores_len--;
2282 if (last)
2283 last->next_local_store = i_ptr->next_local_store;
2284 else
2285 active_local_stores = i_ptr->next_local_store;
2287 else
2288 last = i_ptr;
2289 i_ptr = i_ptr->next_local_store;
2292 else
2294 insn_info_t i_ptr = active_local_stores;
2295 insn_info_t last = NULL;
2296 if (dump_file && (dump_flags & TDF_DETAILS))
2298 fprintf (dump_file, " processing cselib load mem:");
2299 print_inline_rtx (dump_file, mem, 0);
2300 fprintf (dump_file, "\n");
2303 while (i_ptr)
2305 bool remove = false;
2306 store_info_t store_info = i_ptr->store_rec;
2308 if (dump_file && (dump_flags & TDF_DETAILS))
2309 fprintf (dump_file, " processing cselib load against insn %d\n",
2310 INSN_UID (i_ptr->insn));
2312 /* Skip the clobbers. */
2313 while (!store_info->is_set)
2314 store_info = store_info->next;
2316 /* If this read is just reading back something that we just
2317 stored, rewrite the read. */
2318 if (store_info->rhs
2319 && store_info->group_id == -1
2320 && store_info->cse_base == base
2321 && width != -1
2322 && offset >= store_info->begin
2323 && offset + width <= store_info->end
2324 && all_positions_needed_p (store_info,
2325 offset - store_info->begin, width)
2326 && replace_read (store_info, i_ptr, read_info, insn_info, loc,
2327 bb_info->regs_live))
2328 return 0;
2330 if (!store_info->alias_set)
2331 remove = canon_true_dependence (store_info->mem,
2332 GET_MODE (store_info->mem),
2333 store_info->mem_addr,
2334 mem, mem_addr);
2336 if (remove)
2338 if (dump_file && (dump_flags & TDF_DETAILS))
2339 dump_insn_info ("removing from active", i_ptr);
2341 active_local_stores_len--;
2342 if (last)
2343 last->next_local_store = i_ptr->next_local_store;
2344 else
2345 active_local_stores = i_ptr->next_local_store;
2347 else
2348 last = i_ptr;
2349 i_ptr = i_ptr->next_local_store;
2352 return 0;
2355 /* A for_each_rtx callback in which DATA points the INSN_INFO for
2356 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
2357 true for any part of *LOC. */
2359 static void
2360 check_mem_read_use (rtx *loc, void *data)
2362 for_each_rtx (loc, check_mem_read_rtx, data);
2366 /* Get arguments passed to CALL_INSN. Return TRUE if successful.
2367 So far it only handles arguments passed in registers. */
2369 static bool
2370 get_call_args (rtx call_insn, tree fn, rtx *args, int nargs)
2372 CUMULATIVE_ARGS args_so_far_v;
2373 cumulative_args_t args_so_far;
2374 tree arg;
2375 int idx;
2377 INIT_CUMULATIVE_ARGS (args_so_far_v, TREE_TYPE (fn), NULL_RTX, 0, 3);
2378 args_so_far = pack_cumulative_args (&args_so_far_v);
2380 arg = TYPE_ARG_TYPES (TREE_TYPE (fn));
2381 for (idx = 0;
2382 arg != void_list_node && idx < nargs;
2383 arg = TREE_CHAIN (arg), idx++)
2385 enum machine_mode mode = TYPE_MODE (TREE_VALUE (arg));
2386 rtx reg, link, tmp;
2387 reg = targetm.calls.function_arg (args_so_far, mode, NULL_TREE, true);
2388 if (!reg || !REG_P (reg) || GET_MODE (reg) != mode
2389 || GET_MODE_CLASS (mode) != MODE_INT)
2390 return false;
2392 for (link = CALL_INSN_FUNCTION_USAGE (call_insn);
2393 link;
2394 link = XEXP (link, 1))
2395 if (GET_CODE (XEXP (link, 0)) == USE)
2397 args[idx] = XEXP (XEXP (link, 0), 0);
2398 if (REG_P (args[idx])
2399 && REGNO (args[idx]) == REGNO (reg)
2400 && (GET_MODE (args[idx]) == mode
2401 || (GET_MODE_CLASS (GET_MODE (args[idx])) == MODE_INT
2402 && (GET_MODE_SIZE (GET_MODE (args[idx]))
2403 <= UNITS_PER_WORD)
2404 && (GET_MODE_SIZE (GET_MODE (args[idx]))
2405 > GET_MODE_SIZE (mode)))))
2406 break;
2408 if (!link)
2409 return false;
2411 tmp = cselib_expand_value_rtx (args[idx], scratch, 5);
2412 if (GET_MODE (args[idx]) != mode)
2414 if (!tmp || !CONST_INT_P (tmp))
2415 return false;
2416 tmp = gen_int_mode (INTVAL (tmp), mode);
2418 if (tmp)
2419 args[idx] = tmp;
2421 targetm.calls.function_arg_advance (args_so_far, mode, NULL_TREE, true);
2423 if (arg != void_list_node || idx != nargs)
2424 return false;
2425 return true;
2428 /* Return a bitmap of the fixed registers contained in IN. */
2430 static bitmap
2431 copy_fixed_regs (const_bitmap in)
2433 bitmap ret;
2435 ret = ALLOC_REG_SET (NULL);
2436 bitmap_and (ret, in, fixed_reg_set_regset);
2437 return ret;
2440 /* Apply record_store to all candidate stores in INSN. Mark INSN
2441 if some part of it is not a candidate store and assigns to a
2442 non-register target. */
2444 static void
2445 scan_insn (bb_info_t bb_info, rtx insn)
2447 rtx body;
2448 insn_info_t insn_info = (insn_info_t) pool_alloc (insn_info_pool);
2449 int mems_found = 0;
2450 memset (insn_info, 0, sizeof (struct insn_info));
2452 if (dump_file && (dump_flags & TDF_DETAILS))
2453 fprintf (dump_file, "\n**scanning insn=%d\n",
2454 INSN_UID (insn));
2456 insn_info->prev_insn = bb_info->last_insn;
2457 insn_info->insn = insn;
2458 bb_info->last_insn = insn_info;
2460 if (DEBUG_INSN_P (insn))
2462 insn_info->cannot_delete = true;
2463 return;
2466 /* Cselib clears the table for this case, so we have to essentially
2467 do the same. */
2468 if (NONJUMP_INSN_P (insn)
2469 && volatile_insn_p (PATTERN (insn)))
2471 add_wild_read (bb_info);
2472 insn_info->cannot_delete = true;
2473 return;
2476 /* Look at all of the uses in the insn. */
2477 note_uses (&PATTERN (insn), check_mem_read_use, bb_info);
2479 if (CALL_P (insn))
2481 bool const_call;
2482 tree memset_call = NULL_TREE;
2484 insn_info->cannot_delete = true;
2486 /* Const functions cannot do anything bad i.e. read memory,
2487 however, they can read their parameters which may have
2488 been pushed onto the stack.
2489 memset and bzero don't read memory either. */
2490 const_call = RTL_CONST_CALL_P (insn);
2491 if (!const_call)
2493 rtx call = get_call_rtx_from (insn);
2494 if (call && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
2496 rtx symbol = XEXP (XEXP (call, 0), 0);
2497 if (SYMBOL_REF_DECL (symbol)
2498 && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
2500 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
2501 == BUILT_IN_NORMAL
2502 && (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))
2503 == BUILT_IN_MEMSET))
2504 || SYMBOL_REF_DECL (symbol) == block_clear_fn)
2505 memset_call = SYMBOL_REF_DECL (symbol);
2509 if (const_call || memset_call)
2511 insn_info_t i_ptr = active_local_stores;
2512 insn_info_t last = NULL;
2514 if (dump_file && (dump_flags & TDF_DETAILS))
2515 fprintf (dump_file, "%s call %d\n",
2516 const_call ? "const" : "memset", INSN_UID (insn));
2518 /* See the head comment of the frame_read field. */
2519 if (reload_completed)
2520 insn_info->frame_read = true;
2522 /* Loop over the active stores and remove those which are
2523 killed by the const function call. */
2524 while (i_ptr)
2526 bool remove_store = false;
2528 /* The stack pointer based stores are always killed. */
2529 if (i_ptr->stack_pointer_based)
2530 remove_store = true;
2532 /* If the frame is read, the frame related stores are killed. */
2533 else if (insn_info->frame_read)
2535 store_info_t store_info = i_ptr->store_rec;
2537 /* Skip the clobbers. */
2538 while (!store_info->is_set)
2539 store_info = store_info->next;
2541 if (store_info->group_id >= 0
2542 && rtx_group_vec[store_info->group_id]->frame_related)
2543 remove_store = true;
2546 if (remove_store)
2548 if (dump_file && (dump_flags & TDF_DETAILS))
2549 dump_insn_info ("removing from active", i_ptr);
2551 active_local_stores_len--;
2552 if (last)
2553 last->next_local_store = i_ptr->next_local_store;
2554 else
2555 active_local_stores = i_ptr->next_local_store;
2557 else
2558 last = i_ptr;
2560 i_ptr = i_ptr->next_local_store;
2563 if (memset_call)
2565 rtx args[3];
2566 if (get_call_args (insn, memset_call, args, 3)
2567 && CONST_INT_P (args[1])
2568 && CONST_INT_P (args[2])
2569 && INTVAL (args[2]) > 0)
2571 rtx mem = gen_rtx_MEM (BLKmode, args[0]);
2572 set_mem_size (mem, INTVAL (args[2]));
2573 body = gen_rtx_SET (VOIDmode, mem, args[1]);
2574 mems_found += record_store (body, bb_info);
2575 if (dump_file && (dump_flags & TDF_DETAILS))
2576 fprintf (dump_file, "handling memset as BLKmode store\n");
2577 if (mems_found == 1)
2579 if (active_local_stores_len++
2580 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES))
2582 active_local_stores_len = 1;
2583 active_local_stores = NULL;
2585 insn_info->fixed_regs_live
2586 = copy_fixed_regs (bb_info->regs_live);
2587 insn_info->next_local_store = active_local_stores;
2588 active_local_stores = insn_info;
2594 else
2595 /* Every other call, including pure functions, may read any memory
2596 that is not relative to the frame. */
2597 add_non_frame_wild_read (bb_info);
2599 return;
2602 /* Assuming that there are sets in these insns, we cannot delete
2603 them. */
2604 if ((GET_CODE (PATTERN (insn)) == CLOBBER)
2605 || volatile_refs_p (PATTERN (insn))
2606 || (!cfun->can_delete_dead_exceptions && !insn_nothrow_p (insn))
2607 || (RTX_FRAME_RELATED_P (insn))
2608 || find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX))
2609 insn_info->cannot_delete = true;
2611 body = PATTERN (insn);
2612 if (GET_CODE (body) == PARALLEL)
2614 int i;
2615 for (i = 0; i < XVECLEN (body, 0); i++)
2616 mems_found += record_store (XVECEXP (body, 0, i), bb_info);
2618 else
2619 mems_found += record_store (body, bb_info);
2621 if (dump_file && (dump_flags & TDF_DETAILS))
2622 fprintf (dump_file, "mems_found = %d, cannot_delete = %s\n",
2623 mems_found, insn_info->cannot_delete ? "true" : "false");
2625 /* If we found some sets of mems, add it into the active_local_stores so
2626 that it can be locally deleted if found dead or used for
2627 replace_read and redundant constant store elimination. Otherwise mark
2628 it as cannot delete. This simplifies the processing later. */
2629 if (mems_found == 1)
2631 if (active_local_stores_len++
2632 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES))
2634 active_local_stores_len = 1;
2635 active_local_stores = NULL;
2637 insn_info->fixed_regs_live = copy_fixed_regs (bb_info->regs_live);
2638 insn_info->next_local_store = active_local_stores;
2639 active_local_stores = insn_info;
2641 else
2642 insn_info->cannot_delete = true;
2646 /* Remove BASE from the set of active_local_stores. This is a
2647 callback from cselib that is used to get rid of the stores in
2648 active_local_stores. */
2650 static void
2651 remove_useless_values (cselib_val *base)
2653 insn_info_t insn_info = active_local_stores;
2654 insn_info_t last = NULL;
2656 while (insn_info)
2658 store_info_t store_info = insn_info->store_rec;
2659 bool del = false;
2661 /* If ANY of the store_infos match the cselib group that is
2662 being deleted, then the insn can not be deleted. */
2663 while (store_info)
2665 if ((store_info->group_id == -1)
2666 && (store_info->cse_base == base))
2668 del = true;
2669 break;
2671 store_info = store_info->next;
2674 if (del)
2676 active_local_stores_len--;
2677 if (last)
2678 last->next_local_store = insn_info->next_local_store;
2679 else
2680 active_local_stores = insn_info->next_local_store;
2681 free_store_info (insn_info);
2683 else
2684 last = insn_info;
2686 insn_info = insn_info->next_local_store;
2691 /* Do all of step 1. */
2693 static void
2694 dse_step1 (void)
2696 basic_block bb;
2697 bitmap regs_live = BITMAP_ALLOC (&reg_obstack);
2699 cselib_init (0);
2700 all_blocks = BITMAP_ALLOC (NULL);
2701 bitmap_set_bit (all_blocks, ENTRY_BLOCK);
2702 bitmap_set_bit (all_blocks, EXIT_BLOCK);
2704 FOR_ALL_BB (bb)
2706 insn_info_t ptr;
2707 bb_info_t bb_info = (bb_info_t) pool_alloc (bb_info_pool);
2709 memset (bb_info, 0, sizeof (struct bb_info));
2710 bitmap_set_bit (all_blocks, bb->index);
2711 bb_info->regs_live = regs_live;
2713 bitmap_copy (regs_live, DF_LR_IN (bb));
2714 df_simulate_initialize_forwards (bb, regs_live);
2716 bb_table[bb->index] = bb_info;
2717 cselib_discard_hook = remove_useless_values;
2719 if (bb->index >= NUM_FIXED_BLOCKS)
2721 rtx insn;
2723 cse_store_info_pool
2724 = create_alloc_pool ("cse_store_info_pool",
2725 sizeof (struct store_info), 100);
2726 active_local_stores = NULL;
2727 active_local_stores_len = 0;
2728 cselib_clear_table ();
2730 /* Scan the insns. */
2731 FOR_BB_INSNS (bb, insn)
2733 if (INSN_P (insn))
2734 scan_insn (bb_info, insn);
2735 cselib_process_insn (insn);
2736 if (INSN_P (insn))
2737 df_simulate_one_insn_forwards (bb, insn, regs_live);
2740 /* This is something of a hack, because the global algorithm
2741 is supposed to take care of the case where stores go dead
2742 at the end of the function. However, the global
2743 algorithm must take a more conservative view of block
2744 mode reads than the local alg does. So to get the case
2745 where you have a store to the frame followed by a non
2746 overlapping block more read, we look at the active local
2747 stores at the end of the function and delete all of the
2748 frame and spill based ones. */
2749 if (stores_off_frame_dead_at_return
2750 && (EDGE_COUNT (bb->succs) == 0
2751 || (single_succ_p (bb)
2752 && single_succ (bb) == EXIT_BLOCK_PTR
2753 && ! crtl->calls_eh_return)))
2755 insn_info_t i_ptr = active_local_stores;
2756 while (i_ptr)
2758 store_info_t store_info = i_ptr->store_rec;
2760 /* Skip the clobbers. */
2761 while (!store_info->is_set)
2762 store_info = store_info->next;
2763 if (store_info->alias_set && !i_ptr->cannot_delete)
2764 delete_dead_store_insn (i_ptr);
2765 else
2766 if (store_info->group_id >= 0)
2768 group_info_t group
2769 = rtx_group_vec[store_info->group_id];
2770 if (group->frame_related && !i_ptr->cannot_delete)
2771 delete_dead_store_insn (i_ptr);
2774 i_ptr = i_ptr->next_local_store;
2778 /* Get rid of the loads that were discovered in
2779 replace_read. Cselib is finished with this block. */
2780 while (deferred_change_list)
2782 deferred_change_t next = deferred_change_list->next;
2784 /* There is no reason to validate this change. That was
2785 done earlier. */
2786 *deferred_change_list->loc = deferred_change_list->reg;
2787 pool_free (deferred_change_pool, deferred_change_list);
2788 deferred_change_list = next;
2791 /* Get rid of all of the cselib based store_infos in this
2792 block and mark the containing insns as not being
2793 deletable. */
2794 ptr = bb_info->last_insn;
2795 while (ptr)
2797 if (ptr->contains_cselib_groups)
2799 store_info_t s_info = ptr->store_rec;
2800 while (s_info && !s_info->is_set)
2801 s_info = s_info->next;
2802 if (s_info
2803 && s_info->redundant_reason
2804 && s_info->redundant_reason->insn
2805 && !ptr->cannot_delete)
2807 if (dump_file && (dump_flags & TDF_DETAILS))
2808 fprintf (dump_file, "Locally deleting insn %d "
2809 "because insn %d stores the "
2810 "same value and couldn't be "
2811 "eliminated\n",
2812 INSN_UID (ptr->insn),
2813 INSN_UID (s_info->redundant_reason->insn));
2814 delete_dead_store_insn (ptr);
2816 free_store_info (ptr);
2818 else
2820 store_info_t s_info;
2822 /* Free at least positions_needed bitmaps. */
2823 for (s_info = ptr->store_rec; s_info; s_info = s_info->next)
2824 if (s_info->is_large)
2826 BITMAP_FREE (s_info->positions_needed.large.bmap);
2827 s_info->is_large = false;
2830 ptr = ptr->prev_insn;
2833 free_alloc_pool (cse_store_info_pool);
2835 bb_info->regs_live = NULL;
2838 BITMAP_FREE (regs_live);
2839 cselib_finish ();
2840 rtx_group_table.empty ();
2844 /*----------------------------------------------------------------------------
2845 Second step.
2847 Assign each byte position in the stores that we are going to
2848 analyze globally to a position in the bitmaps. Returns true if
2849 there are any bit positions assigned.
2850 ----------------------------------------------------------------------------*/
2852 static void
2853 dse_step2_init (void)
2855 unsigned int i;
2856 group_info_t group;
2858 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
2860 /* For all non stack related bases, we only consider a store to
2861 be deletable if there are two or more stores for that
2862 position. This is because it takes one store to make the
2863 other store redundant. However, for the stores that are
2864 stack related, we consider them if there is only one store
2865 for the position. We do this because the stack related
2866 stores can be deleted if their is no read between them and
2867 the end of the function.
2869 To make this work in the current framework, we take the stack
2870 related bases add all of the bits from store1 into store2.
2871 This has the effect of making the eligible even if there is
2872 only one store. */
2874 if (stores_off_frame_dead_at_return && group->frame_related)
2876 bitmap_ior_into (group->store2_n, group->store1_n);
2877 bitmap_ior_into (group->store2_p, group->store1_p);
2878 if (dump_file && (dump_flags & TDF_DETAILS))
2879 fprintf (dump_file, "group %d is frame related ", i);
2882 group->offset_map_size_n++;
2883 group->offset_map_n = XOBNEWVEC (&dse_obstack, int,
2884 group->offset_map_size_n);
2885 group->offset_map_size_p++;
2886 group->offset_map_p = XOBNEWVEC (&dse_obstack, int,
2887 group->offset_map_size_p);
2888 group->process_globally = false;
2889 if (dump_file && (dump_flags & TDF_DETAILS))
2891 fprintf (dump_file, "group %d(%d+%d): ", i,
2892 (int)bitmap_count_bits (group->store2_n),
2893 (int)bitmap_count_bits (group->store2_p));
2894 bitmap_print (dump_file, group->store2_n, "n ", " ");
2895 bitmap_print (dump_file, group->store2_p, "p ", "\n");
2901 /* Init the offset tables for the normal case. */
2903 static bool
2904 dse_step2_nospill (void)
2906 unsigned int i;
2907 group_info_t group;
2908 /* Position 0 is unused because 0 is used in the maps to mean
2909 unused. */
2910 current_position = 1;
2911 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
2913 bitmap_iterator bi;
2914 unsigned int j;
2916 if (group == clear_alias_group)
2917 continue;
2919 memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n);
2920 memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p);
2921 bitmap_clear (group->group_kill);
2923 EXECUTE_IF_SET_IN_BITMAP (group->store2_n, 0, j, bi)
2925 bitmap_set_bit (group->group_kill, current_position);
2926 if (bitmap_bit_p (group->escaped_n, j))
2927 bitmap_set_bit (kill_on_calls, current_position);
2928 group->offset_map_n[j] = current_position++;
2929 group->process_globally = true;
2931 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2933 bitmap_set_bit (group->group_kill, current_position);
2934 if (bitmap_bit_p (group->escaped_p, j))
2935 bitmap_set_bit (kill_on_calls, current_position);
2936 group->offset_map_p[j] = current_position++;
2937 group->process_globally = true;
2940 return current_position != 1;
2945 /*----------------------------------------------------------------------------
2946 Third step.
2948 Build the bit vectors for the transfer functions.
2949 ----------------------------------------------------------------------------*/
2952 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
2953 there, return 0. */
2955 static int
2956 get_bitmap_index (group_info_t group_info, HOST_WIDE_INT offset)
2958 if (offset < 0)
2960 HOST_WIDE_INT offset_p = -offset;
2961 if (offset_p >= group_info->offset_map_size_n)
2962 return 0;
2963 return group_info->offset_map_n[offset_p];
2965 else
2967 if (offset >= group_info->offset_map_size_p)
2968 return 0;
2969 return group_info->offset_map_p[offset];
2974 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
2975 may be NULL. */
2977 static void
2978 scan_stores_nospill (store_info_t store_info, bitmap gen, bitmap kill)
2980 while (store_info)
2982 HOST_WIDE_INT i;
2983 group_info_t group_info
2984 = rtx_group_vec[store_info->group_id];
2985 if (group_info->process_globally)
2986 for (i = store_info->begin; i < store_info->end; i++)
2988 int index = get_bitmap_index (group_info, i);
2989 if (index != 0)
2991 bitmap_set_bit (gen, index);
2992 if (kill)
2993 bitmap_clear_bit (kill, index);
2996 store_info = store_info->next;
3001 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
3002 may be NULL. */
3004 static void
3005 scan_stores_spill (store_info_t store_info, bitmap gen, bitmap kill)
3007 while (store_info)
3009 if (store_info->alias_set)
3011 int index = get_bitmap_index (clear_alias_group,
3012 store_info->alias_set);
3013 if (index != 0)
3015 bitmap_set_bit (gen, index);
3016 if (kill)
3017 bitmap_clear_bit (kill, index);
3020 store_info = store_info->next;
3025 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3026 may be NULL. */
3028 static void
3029 scan_reads_nospill (insn_info_t insn_info, bitmap gen, bitmap kill)
3031 read_info_t read_info = insn_info->read_rec;
3032 int i;
3033 group_info_t group;
3035 /* If this insn reads the frame, kill all the frame related stores. */
3036 if (insn_info->frame_read)
3038 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
3039 if (group->process_globally && group->frame_related)
3041 if (kill)
3042 bitmap_ior_into (kill, group->group_kill);
3043 bitmap_and_compl_into (gen, group->group_kill);
3046 if (insn_info->non_frame_wild_read)
3048 /* Kill all non-frame related stores. Kill all stores of variables that
3049 escape. */
3050 if (kill)
3051 bitmap_ior_into (kill, kill_on_calls);
3052 bitmap_and_compl_into (gen, kill_on_calls);
3053 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
3054 if (group->process_globally && !group->frame_related)
3056 if (kill)
3057 bitmap_ior_into (kill, group->group_kill);
3058 bitmap_and_compl_into (gen, group->group_kill);
3061 while (read_info)
3063 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
3065 if (group->process_globally)
3067 if (i == read_info->group_id)
3069 if (read_info->begin > read_info->end)
3071 /* Begin > end for block mode reads. */
3072 if (kill)
3073 bitmap_ior_into (kill, group->group_kill);
3074 bitmap_and_compl_into (gen, group->group_kill);
3076 else
3078 /* The groups are the same, just process the
3079 offsets. */
3080 HOST_WIDE_INT j;
3081 for (j = read_info->begin; j < read_info->end; j++)
3083 int index = get_bitmap_index (group, j);
3084 if (index != 0)
3086 if (kill)
3087 bitmap_set_bit (kill, index);
3088 bitmap_clear_bit (gen, index);
3093 else
3095 /* The groups are different, if the alias sets
3096 conflict, clear the entire group. We only need
3097 to apply this test if the read_info is a cselib
3098 read. Anything with a constant base cannot alias
3099 something else with a different constant
3100 base. */
3101 if ((read_info->group_id < 0)
3102 && canon_true_dependence (group->base_mem,
3103 GET_MODE (group->base_mem),
3104 group->canon_base_addr,
3105 read_info->mem, NULL_RTX))
3107 if (kill)
3108 bitmap_ior_into (kill, group->group_kill);
3109 bitmap_and_compl_into (gen, group->group_kill);
3115 read_info = read_info->next;
3119 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3120 may be NULL. */
3122 static void
3123 scan_reads_spill (read_info_t read_info, bitmap gen, bitmap kill)
3125 while (read_info)
3127 if (read_info->alias_set)
3129 int index = get_bitmap_index (clear_alias_group,
3130 read_info->alias_set);
3131 if (index != 0)
3133 if (kill)
3134 bitmap_set_bit (kill, index);
3135 bitmap_clear_bit (gen, index);
3139 read_info = read_info->next;
3144 /* Return the insn in BB_INFO before the first wild read or if there
3145 are no wild reads in the block, return the last insn. */
3147 static insn_info_t
3148 find_insn_before_first_wild_read (bb_info_t bb_info)
3150 insn_info_t insn_info = bb_info->last_insn;
3151 insn_info_t last_wild_read = NULL;
3153 while (insn_info)
3155 if (insn_info->wild_read)
3157 last_wild_read = insn_info->prev_insn;
3158 /* Block starts with wild read. */
3159 if (!last_wild_read)
3160 return NULL;
3163 insn_info = insn_info->prev_insn;
3166 if (last_wild_read)
3167 return last_wild_read;
3168 else
3169 return bb_info->last_insn;
3173 /* Scan the insns in BB_INFO starting at PTR and going to the top of
3174 the block in order to build the gen and kill sets for the block.
3175 We start at ptr which may be the last insn in the block or may be
3176 the first insn with a wild read. In the latter case we are able to
3177 skip the rest of the block because it just does not matter:
3178 anything that happens is hidden by the wild read. */
3180 static void
3181 dse_step3_scan (bool for_spills, basic_block bb)
3183 bb_info_t bb_info = bb_table[bb->index];
3184 insn_info_t insn_info;
3186 if (for_spills)
3187 /* There are no wild reads in the spill case. */
3188 insn_info = bb_info->last_insn;
3189 else
3190 insn_info = find_insn_before_first_wild_read (bb_info);
3192 /* In the spill case or in the no_spill case if there is no wild
3193 read in the block, we will need a kill set. */
3194 if (insn_info == bb_info->last_insn)
3196 if (bb_info->kill)
3197 bitmap_clear (bb_info->kill);
3198 else
3199 bb_info->kill = BITMAP_ALLOC (&dse_bitmap_obstack);
3201 else
3202 if (bb_info->kill)
3203 BITMAP_FREE (bb_info->kill);
3205 while (insn_info)
3207 /* There may have been code deleted by the dce pass run before
3208 this phase. */
3209 if (insn_info->insn && INSN_P (insn_info->insn))
3211 /* Process the read(s) last. */
3212 if (for_spills)
3214 scan_stores_spill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3215 scan_reads_spill (insn_info->read_rec, bb_info->gen, bb_info->kill);
3217 else
3219 scan_stores_nospill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3220 scan_reads_nospill (insn_info, bb_info->gen, bb_info->kill);
3224 insn_info = insn_info->prev_insn;
3229 /* Set the gen set of the exit block, and also any block with no
3230 successors that does not have a wild read. */
3232 static void
3233 dse_step3_exit_block_scan (bb_info_t bb_info)
3235 /* The gen set is all 0's for the exit block except for the
3236 frame_pointer_group. */
3238 if (stores_off_frame_dead_at_return)
3240 unsigned int i;
3241 group_info_t group;
3243 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
3245 if (group->process_globally && group->frame_related)
3246 bitmap_ior_into (bb_info->gen, group->group_kill);
3252 /* Find all of the blocks that are not backwards reachable from the
3253 exit block or any block with no successors (BB). These are the
3254 infinite loops or infinite self loops. These blocks will still
3255 have their bits set in UNREACHABLE_BLOCKS. */
3257 static void
3258 mark_reachable_blocks (sbitmap unreachable_blocks, basic_block bb)
3260 edge e;
3261 edge_iterator ei;
3263 if (bitmap_bit_p (unreachable_blocks, bb->index))
3265 bitmap_clear_bit (unreachable_blocks, bb->index);
3266 FOR_EACH_EDGE (e, ei, bb->preds)
3268 mark_reachable_blocks (unreachable_blocks, e->src);
3273 /* Build the transfer functions for the function. */
3275 static void
3276 dse_step3 (bool for_spills)
3278 basic_block bb;
3279 sbitmap unreachable_blocks = sbitmap_alloc (last_basic_block);
3280 sbitmap_iterator sbi;
3281 bitmap all_ones = NULL;
3282 unsigned int i;
3284 bitmap_ones (unreachable_blocks);
3286 FOR_ALL_BB (bb)
3288 bb_info_t bb_info = bb_table[bb->index];
3289 if (bb_info->gen)
3290 bitmap_clear (bb_info->gen);
3291 else
3292 bb_info->gen = BITMAP_ALLOC (&dse_bitmap_obstack);
3294 if (bb->index == ENTRY_BLOCK)
3296 else if (bb->index == EXIT_BLOCK)
3297 dse_step3_exit_block_scan (bb_info);
3298 else
3299 dse_step3_scan (for_spills, bb);
3300 if (EDGE_COUNT (bb->succs) == 0)
3301 mark_reachable_blocks (unreachable_blocks, bb);
3303 /* If this is the second time dataflow is run, delete the old
3304 sets. */
3305 if (bb_info->in)
3306 BITMAP_FREE (bb_info->in);
3307 if (bb_info->out)
3308 BITMAP_FREE (bb_info->out);
3311 /* For any block in an infinite loop, we must initialize the out set
3312 to all ones. This could be expensive, but almost never occurs in
3313 practice. However, it is common in regression tests. */
3314 EXECUTE_IF_SET_IN_BITMAP (unreachable_blocks, 0, i, sbi)
3316 if (bitmap_bit_p (all_blocks, i))
3318 bb_info_t bb_info = bb_table[i];
3319 if (!all_ones)
3321 unsigned int j;
3322 group_info_t group;
3324 all_ones = BITMAP_ALLOC (&dse_bitmap_obstack);
3325 FOR_EACH_VEC_ELT (rtx_group_vec, j, group)
3326 bitmap_ior_into (all_ones, group->group_kill);
3328 if (!bb_info->out)
3330 bb_info->out = BITMAP_ALLOC (&dse_bitmap_obstack);
3331 bitmap_copy (bb_info->out, all_ones);
3336 if (all_ones)
3337 BITMAP_FREE (all_ones);
3338 sbitmap_free (unreachable_blocks);
3343 /*----------------------------------------------------------------------------
3344 Fourth step.
3346 Solve the bitvector equations.
3347 ----------------------------------------------------------------------------*/
3350 /* Confluence function for blocks with no successors. Create an out
3351 set from the gen set of the exit block. This block logically has
3352 the exit block as a successor. */
3356 static void
3357 dse_confluence_0 (basic_block bb)
3359 bb_info_t bb_info = bb_table[bb->index];
3361 if (bb->index == EXIT_BLOCK)
3362 return;
3364 if (!bb_info->out)
3366 bb_info->out = BITMAP_ALLOC (&dse_bitmap_obstack);
3367 bitmap_copy (bb_info->out, bb_table[EXIT_BLOCK]->gen);
3371 /* Propagate the information from the in set of the dest of E to the
3372 out set of the src of E. If the various in or out sets are not
3373 there, that means they are all ones. */
3375 static bool
3376 dse_confluence_n (edge e)
3378 bb_info_t src_info = bb_table[e->src->index];
3379 bb_info_t dest_info = bb_table[e->dest->index];
3381 if (dest_info->in)
3383 if (src_info->out)
3384 bitmap_and_into (src_info->out, dest_info->in);
3385 else
3387 src_info->out = BITMAP_ALLOC (&dse_bitmap_obstack);
3388 bitmap_copy (src_info->out, dest_info->in);
3391 return true;
3395 /* Propagate the info from the out to the in set of BB_INDEX's basic
3396 block. There are three cases:
3398 1) The block has no kill set. In this case the kill set is all
3399 ones. It does not matter what the out set of the block is, none of
3400 the info can reach the top. The only thing that reaches the top is
3401 the gen set and we just copy the set.
3403 2) There is a kill set but no out set and bb has successors. In
3404 this case we just return. Eventually an out set will be created and
3405 it is better to wait than to create a set of ones.
3407 3) There is both a kill and out set. We apply the obvious transfer
3408 function.
3411 static bool
3412 dse_transfer_function (int bb_index)
3414 bb_info_t bb_info = bb_table[bb_index];
3416 if (bb_info->kill)
3418 if (bb_info->out)
3420 /* Case 3 above. */
3421 if (bb_info->in)
3422 return bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3423 bb_info->out, bb_info->kill);
3424 else
3426 bb_info->in = BITMAP_ALLOC (&dse_bitmap_obstack);
3427 bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3428 bb_info->out, bb_info->kill);
3429 return true;
3432 else
3433 /* Case 2 above. */
3434 return false;
3436 else
3438 /* Case 1 above. If there is already an in set, nothing
3439 happens. */
3440 if (bb_info->in)
3441 return false;
3442 else
3444 bb_info->in = BITMAP_ALLOC (&dse_bitmap_obstack);
3445 bitmap_copy (bb_info->in, bb_info->gen);
3446 return true;
3451 /* Solve the dataflow equations. */
3453 static void
3454 dse_step4 (void)
3456 df_simple_dataflow (DF_BACKWARD, NULL, dse_confluence_0,
3457 dse_confluence_n, dse_transfer_function,
3458 all_blocks, df_get_postorder (DF_BACKWARD),
3459 df_get_n_blocks (DF_BACKWARD));
3460 if (dump_file && (dump_flags & TDF_DETAILS))
3462 basic_block bb;
3464 fprintf (dump_file, "\n\n*** Global dataflow info after analysis.\n");
3465 FOR_ALL_BB (bb)
3467 bb_info_t bb_info = bb_table[bb->index];
3469 df_print_bb_index (bb, dump_file);
3470 if (bb_info->in)
3471 bitmap_print (dump_file, bb_info->in, " in: ", "\n");
3472 else
3473 fprintf (dump_file, " in: *MISSING*\n");
3474 if (bb_info->gen)
3475 bitmap_print (dump_file, bb_info->gen, " gen: ", "\n");
3476 else
3477 fprintf (dump_file, " gen: *MISSING*\n");
3478 if (bb_info->kill)
3479 bitmap_print (dump_file, bb_info->kill, " kill: ", "\n");
3480 else
3481 fprintf (dump_file, " kill: *MISSING*\n");
3482 if (bb_info->out)
3483 bitmap_print (dump_file, bb_info->out, " out: ", "\n");
3484 else
3485 fprintf (dump_file, " out: *MISSING*\n\n");
3492 /*----------------------------------------------------------------------------
3493 Fifth step.
3495 Delete the stores that can only be deleted using the global information.
3496 ----------------------------------------------------------------------------*/
3499 static void
3500 dse_step5_nospill (void)
3502 basic_block bb;
3503 FOR_EACH_BB (bb)
3505 bb_info_t bb_info = bb_table[bb->index];
3506 insn_info_t insn_info = bb_info->last_insn;
3507 bitmap v = bb_info->out;
3509 while (insn_info)
3511 bool deleted = false;
3512 if (dump_file && insn_info->insn)
3514 fprintf (dump_file, "starting to process insn %d\n",
3515 INSN_UID (insn_info->insn));
3516 bitmap_print (dump_file, v, " v: ", "\n");
3519 /* There may have been code deleted by the dce pass run before
3520 this phase. */
3521 if (insn_info->insn
3522 && INSN_P (insn_info->insn)
3523 && (!insn_info->cannot_delete)
3524 && (!bitmap_empty_p (v)))
3526 store_info_t store_info = insn_info->store_rec;
3528 /* Try to delete the current insn. */
3529 deleted = true;
3531 /* Skip the clobbers. */
3532 while (!store_info->is_set)
3533 store_info = store_info->next;
3535 if (store_info->alias_set)
3536 deleted = false;
3537 else
3539 HOST_WIDE_INT i;
3540 group_info_t group_info
3541 = rtx_group_vec[store_info->group_id];
3543 for (i = store_info->begin; i < store_info->end; i++)
3545 int index = get_bitmap_index (group_info, i);
3547 if (dump_file && (dump_flags & TDF_DETAILS))
3548 fprintf (dump_file, "i = %d, index = %d\n", (int)i, index);
3549 if (index == 0 || !bitmap_bit_p (v, index))
3551 if (dump_file && (dump_flags & TDF_DETAILS))
3552 fprintf (dump_file, "failing at i = %d\n", (int)i);
3553 deleted = false;
3554 break;
3558 if (deleted)
3560 if (dbg_cnt (dse)
3561 && check_for_inc_dec_1 (insn_info))
3563 delete_insn (insn_info->insn);
3564 insn_info->insn = NULL;
3565 globally_deleted++;
3569 /* We do want to process the local info if the insn was
3570 deleted. For instance, if the insn did a wild read, we
3571 no longer need to trash the info. */
3572 if (insn_info->insn
3573 && INSN_P (insn_info->insn)
3574 && (!deleted))
3576 scan_stores_nospill (insn_info->store_rec, v, NULL);
3577 if (insn_info->wild_read)
3579 if (dump_file && (dump_flags & TDF_DETAILS))
3580 fprintf (dump_file, "wild read\n");
3581 bitmap_clear (v);
3583 else if (insn_info->read_rec
3584 || insn_info->non_frame_wild_read)
3586 if (dump_file && !insn_info->non_frame_wild_read)
3587 fprintf (dump_file, "regular read\n");
3588 else if (dump_file && (dump_flags & TDF_DETAILS))
3589 fprintf (dump_file, "non-frame wild read\n");
3590 scan_reads_nospill (insn_info, v, NULL);
3594 insn_info = insn_info->prev_insn;
3601 /*----------------------------------------------------------------------------
3602 Sixth step.
3604 Delete stores made redundant by earlier stores (which store the same
3605 value) that couldn't be eliminated.
3606 ----------------------------------------------------------------------------*/
3608 static void
3609 dse_step6 (void)
3611 basic_block bb;
3613 FOR_ALL_BB (bb)
3615 bb_info_t bb_info = bb_table[bb->index];
3616 insn_info_t insn_info = bb_info->last_insn;
3618 while (insn_info)
3620 /* There may have been code deleted by the dce pass run before
3621 this phase. */
3622 if (insn_info->insn
3623 && INSN_P (insn_info->insn)
3624 && !insn_info->cannot_delete)
3626 store_info_t s_info = insn_info->store_rec;
3628 while (s_info && !s_info->is_set)
3629 s_info = s_info->next;
3630 if (s_info
3631 && s_info->redundant_reason
3632 && s_info->redundant_reason->insn
3633 && INSN_P (s_info->redundant_reason->insn))
3635 rtx rinsn = s_info->redundant_reason->insn;
3636 if (dump_file && (dump_flags & TDF_DETAILS))
3637 fprintf (dump_file, "Locally deleting insn %d "
3638 "because insn %d stores the "
3639 "same value and couldn't be "
3640 "eliminated\n",
3641 INSN_UID (insn_info->insn),
3642 INSN_UID (rinsn));
3643 delete_dead_store_insn (insn_info);
3646 insn_info = insn_info->prev_insn;
3651 /*----------------------------------------------------------------------------
3652 Seventh step.
3654 Destroy everything left standing.
3655 ----------------------------------------------------------------------------*/
3657 static void
3658 dse_step7 (void)
3660 bitmap_obstack_release (&dse_bitmap_obstack);
3661 obstack_free (&dse_obstack, NULL);
3663 end_alias_analysis ();
3664 free (bb_table);
3665 rtx_group_table.dispose ();
3666 rtx_group_vec.release ();
3667 BITMAP_FREE (all_blocks);
3668 BITMAP_FREE (scratch);
3670 free_alloc_pool (rtx_store_info_pool);
3671 free_alloc_pool (read_info_pool);
3672 free_alloc_pool (insn_info_pool);
3673 free_alloc_pool (bb_info_pool);
3674 free_alloc_pool (rtx_group_info_pool);
3675 free_alloc_pool (deferred_change_pool);
3679 /* -------------------------------------------------------------------------
3681 ------------------------------------------------------------------------- */
3683 /* Callback for running pass_rtl_dse. */
3685 static unsigned int
3686 rest_of_handle_dse (void)
3688 df_set_flags (DF_DEFER_INSN_RESCAN);
3690 /* Need the notes since we must track live hardregs in the forwards
3691 direction. */
3692 df_note_add_problem ();
3693 df_analyze ();
3695 dse_step0 ();
3696 dse_step1 ();
3697 dse_step2_init ();
3698 if (dse_step2_nospill ())
3700 df_set_flags (DF_LR_RUN_DCE);
3701 df_analyze ();
3702 if (dump_file && (dump_flags & TDF_DETAILS))
3703 fprintf (dump_file, "doing global processing\n");
3704 dse_step3 (false);
3705 dse_step4 ();
3706 dse_step5_nospill ();
3709 dse_step6 ();
3710 dse_step7 ();
3712 if (dump_file)
3713 fprintf (dump_file, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3714 locally_deleted, globally_deleted, spill_deleted);
3715 return 0;
3718 static bool
3719 gate_dse1 (void)
3721 return optimize > 0 && flag_dse
3722 && dbg_cnt (dse1);
3725 static bool
3726 gate_dse2 (void)
3728 return optimize > 0 && flag_dse
3729 && dbg_cnt (dse2);
3732 namespace {
3734 const pass_data pass_data_rtl_dse1 =
3736 RTL_PASS, /* type */
3737 "dse1", /* name */
3738 OPTGROUP_NONE, /* optinfo_flags */
3739 true, /* has_gate */
3740 true, /* has_execute */
3741 TV_DSE1, /* tv_id */
3742 0, /* properties_required */
3743 0, /* properties_provided */
3744 0, /* properties_destroyed */
3745 0, /* todo_flags_start */
3746 ( TODO_df_finish | TODO_verify_rtl_sharing ), /* todo_flags_finish */
3749 class pass_rtl_dse1 : public rtl_opt_pass
3751 public:
3752 pass_rtl_dse1(gcc::context *ctxt)
3753 : rtl_opt_pass(pass_data_rtl_dse1, ctxt)
3756 /* opt_pass methods: */
3757 bool gate () { return gate_dse1 (); }
3758 unsigned int execute () { return rest_of_handle_dse (); }
3760 }; // class pass_rtl_dse1
3762 } // anon namespace
3764 rtl_opt_pass *
3765 make_pass_rtl_dse1 (gcc::context *ctxt)
3767 return new pass_rtl_dse1 (ctxt);
3770 namespace {
3772 const pass_data pass_data_rtl_dse2 =
3774 RTL_PASS, /* type */
3775 "dse2", /* name */
3776 OPTGROUP_NONE, /* optinfo_flags */
3777 true, /* has_gate */
3778 true, /* has_execute */
3779 TV_DSE2, /* tv_id */
3780 0, /* properties_required */
3781 0, /* properties_provided */
3782 0, /* properties_destroyed */
3783 0, /* todo_flags_start */
3784 ( TODO_df_finish | TODO_verify_rtl_sharing ), /* todo_flags_finish */
3787 class pass_rtl_dse2 : public rtl_opt_pass
3789 public:
3790 pass_rtl_dse2(gcc::context *ctxt)
3791 : rtl_opt_pass(pass_data_rtl_dse2, ctxt)
3794 /* opt_pass methods: */
3795 bool gate () { return gate_dse2 (); }
3796 unsigned int execute () { return rest_of_handle_dse (); }
3798 }; // class pass_rtl_dse2
3800 } // anon namespace
3802 rtl_opt_pass *
3803 make_pass_rtl_dse2 (gcc::context *ctxt)
3805 return new pass_rtl_dse2 (ctxt);