* sv.po: Update.
[official-gcc.git] / gcc / dse.c
blob99f23cab413a553612d889da51f747e26e8f93a1
1 /* RTL dead store elimination.
2 Copyright (C) 2005-2016 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 "backend.h"
29 #include "target.h"
30 #include "rtl.h"
31 #include "tree.h"
32 #include "gimple.h"
33 #include "predict.h"
34 #include "df.h"
35 #include "tm_p.h"
36 #include "gimple-ssa.h"
37 #include "expmed.h"
38 #include "optabs.h"
39 #include "emit-rtl.h"
40 #include "recog.h"
41 #include "alias.h"
42 #include "stor-layout.h"
43 #include "cfgrtl.h"
44 #include "cselib.h"
45 #include "tree-pass.h"
46 #include "explow.h"
47 #include "expr.h"
48 #include "dbgcnt.h"
49 #include "params.h"
50 #include "rtl-iter.h"
51 #include "cfgcleanup.h"
53 /* This file contains three techniques for performing Dead Store
54 Elimination (dse).
56 * The first technique performs dse locally on any base address. It
57 is based on the cselib which is a local value numbering technique.
58 This technique is local to a basic block but deals with a fairly
59 general addresses.
61 * The second technique performs dse globally but is restricted to
62 base addresses that are either constant or are relative to the
63 frame_pointer.
65 * The third technique, (which is only done after register allocation)
66 processes the spill slots. This differs from the second
67 technique because it takes advantage of the fact that spilling is
68 completely free from the effects of aliasing.
70 Logically, dse is a backwards dataflow problem. A store can be
71 deleted if it if cannot be reached in the backward direction by any
72 use of the value being stored. However, the local technique uses a
73 forwards scan of the basic block because cselib requires that the
74 block be processed in that order.
76 The pass is logically broken into 7 steps:
78 0) Initialization.
80 1) The local algorithm, as well as scanning the insns for the two
81 global algorithms.
83 2) Analysis to see if the global algs are necessary. In the case
84 of stores base on a constant address, there must be at least two
85 stores to that address, to make it possible to delete some of the
86 stores. In the case of stores off of the frame or spill related
87 stores, only one store to an address is necessary because those
88 stores die at the end of the function.
90 3) Set up the global dataflow equations based on processing the
91 info parsed in the first step.
93 4) Solve the dataflow equations.
95 5) Delete the insns that the global analysis has indicated are
96 unnecessary.
98 6) Delete insns that store the same value as preceding store
99 where the earlier store couldn't be eliminated.
101 7) Cleanup.
103 This step uses cselib and canon_rtx to build the largest expression
104 possible for each address. This pass is a forwards pass through
105 each basic block. From the point of view of the global technique,
106 the first pass could examine a block in either direction. The
107 forwards ordering is to accommodate cselib.
109 We make a simplifying assumption: addresses fall into four broad
110 categories:
112 1) base has rtx_varies_p == false, offset is constant.
113 2) base has rtx_varies_p == false, offset variable.
114 3) base has rtx_varies_p == true, offset constant.
115 4) base has rtx_varies_p == true, offset variable.
117 The local passes are able to process all 4 kinds of addresses. The
118 global pass only handles 1).
120 The global problem is formulated as follows:
122 A store, S1, to address A, where A is not relative to the stack
123 frame, can be eliminated if all paths from S1 to the end of the
124 function contain another store to A before a read to A.
126 If the address A is relative to the stack frame, a store S2 to A
127 can be eliminated if there are no paths from S2 that reach the
128 end of the function that read A before another store to A. In
129 this case S2 can be deleted if there are paths from S2 to the
130 end of the function that have no reads or writes to A. This
131 second case allows stores to the stack frame to be deleted that
132 would otherwise die when the function returns. This cannot be
133 done if stores_off_frame_dead_at_return is not true. See the doc
134 for that variable for when this variable is false.
136 The global problem is formulated as a backwards set union
137 dataflow problem where the stores are the gens and reads are the
138 kills. Set union problems are rare and require some special
139 handling given our representation of bitmaps. A straightforward
140 implementation requires a lot of bitmaps filled with 1s.
141 These are expensive and cumbersome in our bitmap formulation so
142 care has been taken to avoid large vectors filled with 1s. See
143 the comments in bb_info and in the dataflow confluence functions
144 for details.
146 There are two places for further enhancements to this algorithm:
148 1) The original dse which was embedded in a pass called flow also
149 did local address forwarding. For example in
151 A <- r100
152 ... <- A
154 flow would replace the right hand side of the second insn with a
155 reference to r100. Most of the information is available to add this
156 to this pass. It has not done it because it is a lot of work in
157 the case that either r100 is assigned to between the first and
158 second insn and/or the second insn is a load of part of the value
159 stored by the first insn.
161 insn 5 in gcc.c-torture/compile/990203-1.c simple case.
162 insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
163 insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
164 insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
166 2) The cleaning up of spill code is quite profitable. It currently
167 depends on reading tea leaves and chicken entrails left by reload.
168 This pass depends on reload creating a singleton alias set for each
169 spill slot and telling the next dse pass which of these alias sets
170 are the singletons. Rather than analyze the addresses of the
171 spills, dse's spill processing just does analysis of the loads and
172 stores that use those alias sets. There are three cases where this
173 falls short:
175 a) Reload sometimes creates the slot for one mode of access, and
176 then inserts loads and/or stores for a smaller mode. In this
177 case, the current code just punts on the slot. The proper thing
178 to do is to back out and use one bit vector position for each
179 byte of the entity associated with the slot. This depends on
180 KNOWING that reload always generates the accesses for each of the
181 bytes in some canonical (read that easy to understand several
182 passes after reload happens) way.
184 b) Reload sometimes decides that spill slot it allocated was not
185 large enough for the mode and goes back and allocates more slots
186 with the same mode and alias set. The backout in this case is a
187 little more graceful than (a). In this case the slot is unmarked
188 as being a spill slot and if final address comes out to be based
189 off the frame pointer, the global algorithm handles this slot.
191 c) For any pass that may prespill, there is currently no
192 mechanism to tell the dse pass that the slot being used has the
193 special properties that reload uses. It may be that all that is
194 required is to have those passes make the same calls that reload
195 does, assuming that the alias sets can be manipulated in the same
196 way. */
198 /* There are limits to the size of constant offsets we model for the
199 global problem. There are certainly test cases, that exceed this
200 limit, however, it is unlikely that there are important programs
201 that really have constant offsets this size. */
202 #define MAX_OFFSET (64 * 1024)
204 /* Obstack for the DSE dataflow bitmaps. We don't want to put these
205 on the default obstack because these bitmaps can grow quite large
206 (~2GB for the small (!) test case of PR54146) and we'll hold on to
207 all that memory until the end of the compiler run.
208 As a bonus, delete_tree_live_info can destroy all the bitmaps by just
209 releasing the whole obstack. */
210 static bitmap_obstack dse_bitmap_obstack;
212 /* Obstack for other data. As for above: Kinda nice to be able to
213 throw it all away at the end in one big sweep. */
214 static struct obstack dse_obstack;
216 /* Scratch bitmap for cselib's cselib_expand_value_rtx. */
217 static bitmap scratch = NULL;
219 struct insn_info_type;
221 /* This structure holds information about a candidate store. */
222 struct store_info
225 /* False means this is a clobber. */
226 bool is_set;
228 /* False if a single HOST_WIDE_INT bitmap is used for positions_needed. */
229 bool is_large;
231 /* The id of the mem group of the base address. If rtx_varies_p is
232 true, this is -1. Otherwise, it is the index into the group
233 table. */
234 int group_id;
236 /* This is the cselib value. */
237 cselib_val *cse_base;
239 /* This canonized mem. */
240 rtx mem;
242 /* Canonized MEM address for use by canon_true_dependence. */
243 rtx mem_addr;
245 /* If this is non-zero, it is the alias set of a spill location. */
246 alias_set_type alias_set;
248 /* The offset of the first and byte before the last byte associated
249 with the operation. */
250 HOST_WIDE_INT begin, end;
252 union
254 /* A bitmask as wide as the number of bytes in the word that
255 contains a 1 if the byte may be needed. The store is unused if
256 all of the bits are 0. This is used if IS_LARGE is false. */
257 unsigned HOST_WIDE_INT small_bitmask;
259 struct
261 /* A bitmap with one bit per byte. Cleared bit means the position
262 is needed. Used if IS_LARGE is false. */
263 bitmap bmap;
265 /* Number of set bits (i.e. unneeded bytes) in BITMAP. If it is
266 equal to END - BEGIN, the whole store is unused. */
267 int count;
268 } large;
269 } positions_needed;
271 /* The next store info for this insn. */
272 struct store_info *next;
274 /* The right hand side of the store. This is used if there is a
275 subsequent reload of the mems address somewhere later in the
276 basic block. */
277 rtx rhs;
279 /* If rhs is or holds a constant, this contains that constant,
280 otherwise NULL. */
281 rtx const_rhs;
283 /* Set if this store stores the same constant value as REDUNDANT_REASON
284 insn stored. These aren't eliminated early, because doing that
285 might prevent the earlier larger store to be eliminated. */
286 struct insn_info_type *redundant_reason;
289 /* Return a bitmask with the first N low bits set. */
291 static unsigned HOST_WIDE_INT
292 lowpart_bitmask (int n)
294 unsigned HOST_WIDE_INT mask = ~(unsigned HOST_WIDE_INT) 0;
295 return mask >> (HOST_BITS_PER_WIDE_INT - n);
298 static object_allocator<store_info> cse_store_info_pool ("cse_store_info_pool");
300 static object_allocator<store_info> rtx_store_info_pool ("rtx_store_info_pool");
302 /* This structure holds information about a load. These are only
303 built for rtx bases. */
304 struct read_info_type
306 /* The id of the mem group of the base address. */
307 int group_id;
309 /* If this is non-zero, it is the alias set of a spill location. */
310 alias_set_type alias_set;
312 /* The offset of the first and byte after the last byte associated
313 with the operation. If begin == end == 0, the read did not have
314 a constant offset. */
315 int begin, end;
317 /* The mem being read. */
318 rtx mem;
320 /* The next read_info for this insn. */
321 struct read_info_type *next;
323 typedef struct read_info_type *read_info_t;
325 static object_allocator<read_info_type> read_info_type_pool ("read_info_pool");
327 /* One of these records is created for each insn. */
329 struct insn_info_type
331 /* Set true if the insn contains a store but the insn itself cannot
332 be deleted. This is set if the insn is a parallel and there is
333 more than one non dead output or if the insn is in some way
334 volatile. */
335 bool cannot_delete;
337 /* This field is only used by the global algorithm. It is set true
338 if the insn contains any read of mem except for a (1). This is
339 also set if the insn is a call or has a clobber mem. If the insn
340 contains a wild read, the use_rec will be null. */
341 bool wild_read;
343 /* This is true only for CALL instructions which could potentially read
344 any non-frame memory location. This field is used by the global
345 algorithm. */
346 bool non_frame_wild_read;
348 /* This field is only used for the processing of const functions.
349 These functions cannot read memory, but they can read the stack
350 because that is where they may get their parms. We need to be
351 this conservative because, like the store motion pass, we don't
352 consider CALL_INSN_FUNCTION_USAGE when processing call insns.
353 Moreover, we need to distinguish two cases:
354 1. Before reload (register elimination), the stores related to
355 outgoing arguments are stack pointer based and thus deemed
356 of non-constant base in this pass. This requires special
357 handling but also means that the frame pointer based stores
358 need not be killed upon encountering a const function call.
359 2. After reload, the stores related to outgoing arguments can be
360 either stack pointer or hard frame pointer based. This means
361 that we have no other choice than also killing all the frame
362 pointer based stores upon encountering a const function call.
363 This field is set after reload for const function calls and before
364 reload for const tail function calls on targets where arg pointer
365 is the frame pointer. Having this set is less severe than a wild
366 read, it just means that all the frame related stores are killed
367 rather than all the stores. */
368 bool frame_read;
370 /* This field is only used for the processing of const functions.
371 It is set if the insn may contain a stack pointer based store. */
372 bool stack_pointer_based;
374 /* This is true if any of the sets within the store contains a
375 cselib base. Such stores can only be deleted by the local
376 algorithm. */
377 bool contains_cselib_groups;
379 /* The insn. */
380 rtx_insn *insn;
382 /* The list of mem sets or mem clobbers that are contained in this
383 insn. If the insn is deletable, it contains only one mem set.
384 But it could also contain clobbers. Insns that contain more than
385 one mem set are not deletable, but each of those mems are here in
386 order to provide info to delete other insns. */
387 store_info *store_rec;
389 /* The linked list of mem uses in this insn. Only the reads from
390 rtx bases are listed here. The reads to cselib bases are
391 completely processed during the first scan and so are never
392 created. */
393 read_info_t read_rec;
395 /* The live fixed registers. We assume only fixed registers can
396 cause trouble by being clobbered from an expanded pattern;
397 storing only the live fixed registers (rather than all registers)
398 means less memory needs to be allocated / copied for the individual
399 stores. */
400 regset fixed_regs_live;
402 /* The prev insn in the basic block. */
403 struct insn_info_type * prev_insn;
405 /* The linked list of insns that are in consideration for removal in
406 the forwards pass through the basic block. This pointer may be
407 trash as it is not cleared when a wild read occurs. The only
408 time it is guaranteed to be correct is when the traversal starts
409 at active_local_stores. */
410 struct insn_info_type * next_local_store;
412 typedef struct insn_info_type *insn_info_t;
414 static object_allocator<insn_info_type> insn_info_type_pool ("insn_info_pool");
416 /* The linked list of stores that are under consideration in this
417 basic block. */
418 static insn_info_t active_local_stores;
419 static int active_local_stores_len;
421 struct dse_bb_info_type
423 /* Pointer to the insn info for the last insn in the block. These
424 are linked so this is how all of the insns are reached. During
425 scanning this is the current insn being scanned. */
426 insn_info_t last_insn;
428 /* The info for the global dataflow problem. */
431 /* This is set if the transfer function should and in the wild_read
432 bitmap before applying the kill and gen sets. That vector knocks
433 out most of the bits in the bitmap and thus speeds up the
434 operations. */
435 bool apply_wild_read;
437 /* The following 4 bitvectors hold information about which positions
438 of which stores are live or dead. They are indexed by
439 get_bitmap_index. */
441 /* The set of store positions that exist in this block before a wild read. */
442 bitmap gen;
444 /* The set of load positions that exist in this block above the
445 same position of a store. */
446 bitmap kill;
448 /* The set of stores that reach the top of the block without being
449 killed by a read.
451 Do not represent the in if it is all ones. Note that this is
452 what the bitvector should logically be initialized to for a set
453 intersection problem. However, like the kill set, this is too
454 expensive. So initially, the in set will only be created for the
455 exit block and any block that contains a wild read. */
456 bitmap in;
458 /* The set of stores that reach the bottom of the block from it's
459 successors.
461 Do not represent the in if it is all ones. Note that this is
462 what the bitvector should logically be initialized to for a set
463 intersection problem. However, like the kill and in set, this is
464 too expensive. So what is done is that the confluence operator
465 just initializes the vector from one of the out sets of the
466 successors of the block. */
467 bitmap out;
469 /* The following bitvector is indexed by the reg number. It
470 contains the set of regs that are live at the current instruction
471 being processed. While it contains info for all of the
472 registers, only the hard registers are actually examined. It is used
473 to assure that shift and/or add sequences that are inserted do not
474 accidentally clobber live hard regs. */
475 bitmap regs_live;
478 typedef struct dse_bb_info_type *bb_info_t;
480 static object_allocator<dse_bb_info_type> dse_bb_info_type_pool
481 ("bb_info_pool");
483 /* Table to hold all bb_infos. */
484 static bb_info_t *bb_table;
486 /* There is a group_info for each rtx base that is used to reference
487 memory. There are also not many of the rtx bases because they are
488 very limited in scope. */
490 struct group_info
492 /* The actual base of the address. */
493 rtx rtx_base;
495 /* The sequential id of the base. This allows us to have a
496 canonical ordering of these that is not based on addresses. */
497 int id;
499 /* True if there are any positions that are to be processed
500 globally. */
501 bool process_globally;
503 /* True if the base of this group is either the frame_pointer or
504 hard_frame_pointer. */
505 bool frame_related;
507 /* A mem wrapped around the base pointer for the group in order to do
508 read dependency. It must be given BLKmode in order to encompass all
509 the possible offsets from the base. */
510 rtx base_mem;
512 /* Canonized version of base_mem's address. */
513 rtx canon_base_addr;
515 /* These two sets of two bitmaps are used to keep track of how many
516 stores are actually referencing that position from this base. We
517 only do this for rtx bases as this will be used to assign
518 positions in the bitmaps for the global problem. Bit N is set in
519 store1 on the first store for offset N. Bit N is set in store2
520 for the second store to offset N. This is all we need since we
521 only care about offsets that have two or more stores for them.
523 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
524 for 0 and greater offsets.
526 There is one special case here, for stores into the stack frame,
527 we will or store1 into store2 before deciding which stores look
528 at globally. This is because stores to the stack frame that have
529 no other reads before the end of the function can also be
530 deleted. */
531 bitmap store1_n, store1_p, store2_n, store2_p;
533 /* These bitmaps keep track of offsets in this group escape this function.
534 An offset escapes if it corresponds to a named variable whose
535 addressable flag is set. */
536 bitmap escaped_n, escaped_p;
538 /* The positions in this bitmap have the same assignments as the in,
539 out, gen and kill bitmaps. This bitmap is all zeros except for
540 the positions that are occupied by stores for this group. */
541 bitmap group_kill;
543 /* The offset_map is used to map the offsets from this base into
544 positions in the global bitmaps. It is only created after all of
545 the all of stores have been scanned and we know which ones we
546 care about. */
547 int *offset_map_n, *offset_map_p;
548 int offset_map_size_n, offset_map_size_p;
551 static object_allocator<group_info> group_info_pool ("rtx_group_info_pool");
553 /* Index into the rtx_group_vec. */
554 static int rtx_group_next_id;
557 static vec<group_info *> rtx_group_vec;
560 /* This structure holds the set of changes that are being deferred
561 when removing read operation. See replace_read. */
562 struct deferred_change
565 /* The mem that is being replaced. */
566 rtx *loc;
568 /* The reg it is being replaced with. */
569 rtx reg;
571 struct deferred_change *next;
574 static object_allocator<deferred_change> deferred_change_pool
575 ("deferred_change_pool");
577 static deferred_change *deferred_change_list = NULL;
579 /* The group that holds all of the clear_alias_sets. */
580 static group_info *clear_alias_group;
582 /* The modes of the clear_alias_sets. */
583 static htab_t clear_alias_mode_table;
585 /* Hash table element to look up the mode for an alias set. */
586 struct clear_alias_mode_holder
588 alias_set_type alias_set;
589 machine_mode mode;
592 /* This is true except if cfun->stdarg -- i.e. we cannot do
593 this for vararg functions because they play games with the frame. */
594 static bool stores_off_frame_dead_at_return;
596 /* Counter for stats. */
597 static int globally_deleted;
598 static int locally_deleted;
599 static int spill_deleted;
601 static bitmap all_blocks;
603 /* Locations that are killed by calls in the global phase. */
604 static bitmap kill_on_calls;
606 /* The number of bits used in the global bitmaps. */
607 static unsigned int current_position;
609 /*----------------------------------------------------------------------------
610 Zeroth step.
612 Initialization.
613 ----------------------------------------------------------------------------*/
616 /* Find the entry associated with ALIAS_SET. */
618 static struct clear_alias_mode_holder *
619 clear_alias_set_lookup (alias_set_type alias_set)
621 struct clear_alias_mode_holder tmp_holder;
622 void **slot;
624 tmp_holder.alias_set = alias_set;
625 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, NO_INSERT);
626 gcc_assert (*slot);
628 return (struct clear_alias_mode_holder *) *slot;
632 /* Hashtable callbacks for maintaining the "bases" field of
633 store_group_info, given that the addresses are function invariants. */
635 struct invariant_group_base_hasher : nofree_ptr_hash <group_info>
637 static inline hashval_t hash (const group_info *);
638 static inline bool equal (const group_info *, const group_info *);
641 inline bool
642 invariant_group_base_hasher::equal (const group_info *gi1,
643 const group_info *gi2)
645 return rtx_equal_p (gi1->rtx_base, gi2->rtx_base);
648 inline hashval_t
649 invariant_group_base_hasher::hash (const group_info *gi)
651 int do_not_record;
652 return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false);
655 /* Tables of group_info structures, hashed by base value. */
656 static hash_table<invariant_group_base_hasher> *rtx_group_table;
659 /* Get the GROUP for BASE. Add a new group if it is not there. */
661 static group_info *
662 get_group_info (rtx base)
664 struct group_info tmp_gi;
665 group_info *gi;
666 group_info **slot;
668 if (base)
670 /* Find the store_base_info structure for BASE, creating a new one
671 if necessary. */
672 tmp_gi.rtx_base = base;
673 slot = rtx_group_table->find_slot (&tmp_gi, INSERT);
674 gi = *slot;
676 else
678 if (!clear_alias_group)
680 clear_alias_group = gi = group_info_pool.allocate ();
681 memset (gi, 0, sizeof (struct group_info));
682 gi->id = rtx_group_next_id++;
683 gi->store1_n = BITMAP_ALLOC (&dse_bitmap_obstack);
684 gi->store1_p = BITMAP_ALLOC (&dse_bitmap_obstack);
685 gi->store2_n = BITMAP_ALLOC (&dse_bitmap_obstack);
686 gi->store2_p = BITMAP_ALLOC (&dse_bitmap_obstack);
687 gi->escaped_p = BITMAP_ALLOC (&dse_bitmap_obstack);
688 gi->escaped_n = BITMAP_ALLOC (&dse_bitmap_obstack);
689 gi->group_kill = BITMAP_ALLOC (&dse_bitmap_obstack);
690 gi->process_globally = false;
691 gi->offset_map_size_n = 0;
692 gi->offset_map_size_p = 0;
693 gi->offset_map_n = NULL;
694 gi->offset_map_p = NULL;
695 rtx_group_vec.safe_push (gi);
697 return clear_alias_group;
700 if (gi == NULL)
702 *slot = gi = group_info_pool.allocate ();
703 gi->rtx_base = base;
704 gi->id = rtx_group_next_id++;
705 gi->base_mem = gen_rtx_MEM (BLKmode, base);
706 gi->canon_base_addr = canon_rtx (base);
707 gi->store1_n = BITMAP_ALLOC (&dse_bitmap_obstack);
708 gi->store1_p = BITMAP_ALLOC (&dse_bitmap_obstack);
709 gi->store2_n = BITMAP_ALLOC (&dse_bitmap_obstack);
710 gi->store2_p = BITMAP_ALLOC (&dse_bitmap_obstack);
711 gi->escaped_p = BITMAP_ALLOC (&dse_bitmap_obstack);
712 gi->escaped_n = BITMAP_ALLOC (&dse_bitmap_obstack);
713 gi->group_kill = BITMAP_ALLOC (&dse_bitmap_obstack);
714 gi->process_globally = false;
715 gi->frame_related =
716 (base == frame_pointer_rtx) || (base == hard_frame_pointer_rtx);
717 gi->offset_map_size_n = 0;
718 gi->offset_map_size_p = 0;
719 gi->offset_map_n = NULL;
720 gi->offset_map_p = NULL;
721 rtx_group_vec.safe_push (gi);
724 return gi;
728 /* Initialization of data structures. */
730 static void
731 dse_step0 (void)
733 locally_deleted = 0;
734 globally_deleted = 0;
735 spill_deleted = 0;
737 bitmap_obstack_initialize (&dse_bitmap_obstack);
738 gcc_obstack_init (&dse_obstack);
740 scratch = BITMAP_ALLOC (&reg_obstack);
741 kill_on_calls = BITMAP_ALLOC (&dse_bitmap_obstack);
744 rtx_group_table = new hash_table<invariant_group_base_hasher> (11);
746 bb_table = XNEWVEC (bb_info_t, last_basic_block_for_fn (cfun));
747 rtx_group_next_id = 0;
749 stores_off_frame_dead_at_return = !cfun->stdarg;
751 init_alias_analysis ();
753 clear_alias_group = NULL;
758 /*----------------------------------------------------------------------------
759 First step.
761 Scan all of the insns. Any random ordering of the blocks is fine.
762 Each block is scanned in forward order to accommodate cselib which
763 is used to remove stores with non-constant bases.
764 ----------------------------------------------------------------------------*/
766 /* Delete all of the store_info recs from INSN_INFO. */
768 static void
769 free_store_info (insn_info_t insn_info)
771 store_info *cur = insn_info->store_rec;
772 while (cur)
774 store_info *next = cur->next;
775 if (cur->is_large)
776 BITMAP_FREE (cur->positions_needed.large.bmap);
777 if (cur->cse_base)
778 cse_store_info_pool.remove (cur);
779 else
780 rtx_store_info_pool.remove (cur);
781 cur = next;
784 insn_info->cannot_delete = true;
785 insn_info->contains_cselib_groups = false;
786 insn_info->store_rec = NULL;
789 struct note_add_store_info
791 rtx_insn *first, *current;
792 regset fixed_regs_live;
793 bool failure;
796 /* Callback for emit_inc_dec_insn_before via note_stores.
797 Check if a register is clobbered which is live afterwards. */
799 static void
800 note_add_store (rtx loc, const_rtx expr ATTRIBUTE_UNUSED, void *data)
802 rtx_insn *insn;
803 note_add_store_info *info = (note_add_store_info *) data;
805 if (!REG_P (loc))
806 return;
808 /* If this register is referenced by the current or an earlier insn,
809 that's OK. E.g. this applies to the register that is being incremented
810 with this addition. */
811 for (insn = info->first;
812 insn != NEXT_INSN (info->current);
813 insn = NEXT_INSN (insn))
814 if (reg_referenced_p (loc, PATTERN (insn)))
815 return;
817 /* If we come here, we have a clobber of a register that's only OK
818 if that register is not live. If we don't have liveness information
819 available, fail now. */
820 if (!info->fixed_regs_live)
822 info->failure = true;
823 return;
825 /* Now check if this is a live fixed register. */
826 unsigned int end_regno = END_REGNO (loc);
827 for (unsigned int regno = REGNO (loc); regno < end_regno; ++regno)
828 if (REGNO_REG_SET_P (info->fixed_regs_live, regno))
829 info->failure = true;
832 /* Callback for for_each_inc_dec that emits an INSN that sets DEST to
833 SRC + SRCOFF before insn ARG. */
835 static int
836 emit_inc_dec_insn_before (rtx mem ATTRIBUTE_UNUSED,
837 rtx op ATTRIBUTE_UNUSED,
838 rtx dest, rtx src, rtx srcoff, void *arg)
840 insn_info_t insn_info = (insn_info_t) arg;
841 rtx_insn *insn = insn_info->insn, *new_insn, *cur;
842 note_add_store_info info;
844 /* We can reuse all operands without copying, because we are about
845 to delete the insn that contained it. */
846 if (srcoff)
848 start_sequence ();
849 emit_insn (gen_add3_insn (dest, src, srcoff));
850 new_insn = get_insns ();
851 end_sequence ();
853 else
854 new_insn = gen_move_insn (dest, src);
855 info.first = new_insn;
856 info.fixed_regs_live = insn_info->fixed_regs_live;
857 info.failure = false;
858 for (cur = new_insn; cur; cur = NEXT_INSN (cur))
860 info.current = cur;
861 note_stores (PATTERN (cur), note_add_store, &info);
864 /* If a failure was flagged above, return 1 so that for_each_inc_dec will
865 return it immediately, communicating the failure to its caller. */
866 if (info.failure)
867 return 1;
869 emit_insn_before (new_insn, insn);
871 return 0;
874 /* Before we delete INSN_INFO->INSN, make sure that the auto inc/dec, if it
875 is there, is split into a separate insn.
876 Return true on success (or if there was nothing to do), false on failure. */
878 static bool
879 check_for_inc_dec_1 (insn_info_t insn_info)
881 rtx_insn *insn = insn_info->insn;
882 rtx note = find_reg_note (insn, REG_INC, NULL_RTX);
883 if (note)
884 return for_each_inc_dec (PATTERN (insn), emit_inc_dec_insn_before,
885 insn_info) == 0;
886 return true;
890 /* Entry point for postreload. If you work on reload_cse, or you need this
891 anywhere else, consider if you can provide register liveness information
892 and add a parameter to this function so that it can be passed down in
893 insn_info.fixed_regs_live. */
894 bool
895 check_for_inc_dec (rtx_insn *insn)
897 insn_info_type insn_info;
898 rtx note;
900 insn_info.insn = insn;
901 insn_info.fixed_regs_live = NULL;
902 note = find_reg_note (insn, REG_INC, NULL_RTX);
903 if (note)
904 return for_each_inc_dec (PATTERN (insn), emit_inc_dec_insn_before,
905 &insn_info) == 0;
906 return true;
909 /* Delete the insn and free all of the fields inside INSN_INFO. */
911 static void
912 delete_dead_store_insn (insn_info_t insn_info)
914 read_info_t read_info;
916 if (!dbg_cnt (dse))
917 return;
919 if (!check_for_inc_dec_1 (insn_info))
920 return;
921 if (dump_file && (dump_flags & TDF_DETAILS))
923 fprintf (dump_file, "Locally deleting insn %d ",
924 INSN_UID (insn_info->insn));
925 if (insn_info->store_rec->alias_set)
926 fprintf (dump_file, "alias set %d\n",
927 (int) insn_info->store_rec->alias_set);
928 else
929 fprintf (dump_file, "\n");
932 free_store_info (insn_info);
933 read_info = insn_info->read_rec;
935 while (read_info)
937 read_info_t next = read_info->next;
938 read_info_type_pool.remove (read_info);
939 read_info = next;
941 insn_info->read_rec = NULL;
943 delete_insn (insn_info->insn);
944 locally_deleted++;
945 insn_info->insn = NULL;
947 insn_info->wild_read = false;
950 /* Return whether DECL, a local variable, can possibly escape the current
951 function scope. */
953 static bool
954 local_variable_can_escape (tree decl)
956 if (TREE_ADDRESSABLE (decl))
957 return true;
959 /* If this is a partitioned variable, we need to consider all the variables
960 in the partition. This is necessary because a store into one of them can
961 be replaced with a store into another and this may not change the outcome
962 of the escape analysis. */
963 if (cfun->gimple_df->decls_to_pointers != NULL)
965 tree *namep = cfun->gimple_df->decls_to_pointers->get (decl);
966 if (namep)
967 return TREE_ADDRESSABLE (*namep);
970 return false;
973 /* Return whether EXPR can possibly escape the current function scope. */
975 static bool
976 can_escape (tree expr)
978 tree base;
979 if (!expr)
980 return true;
981 base = get_base_address (expr);
982 if (DECL_P (base)
983 && !may_be_aliased (base)
984 && !(TREE_CODE (base) == VAR_DECL
985 && !DECL_EXTERNAL (base)
986 && !TREE_STATIC (base)
987 && local_variable_can_escape (base)))
988 return false;
989 return true;
992 /* Set the store* bitmaps offset_map_size* fields in GROUP based on
993 OFFSET and WIDTH. */
995 static void
996 set_usage_bits (group_info *group, HOST_WIDE_INT offset, HOST_WIDE_INT width,
997 tree expr)
999 HOST_WIDE_INT i;
1000 bool expr_escapes = can_escape (expr);
1001 if (offset > -MAX_OFFSET && offset + width < MAX_OFFSET)
1002 for (i=offset; i<offset+width; i++)
1004 bitmap store1;
1005 bitmap store2;
1006 bitmap escaped;
1007 int ai;
1008 if (i < 0)
1010 store1 = group->store1_n;
1011 store2 = group->store2_n;
1012 escaped = group->escaped_n;
1013 ai = -i;
1015 else
1017 store1 = group->store1_p;
1018 store2 = group->store2_p;
1019 escaped = group->escaped_p;
1020 ai = i;
1023 if (!bitmap_set_bit (store1, ai))
1024 bitmap_set_bit (store2, ai);
1025 else
1027 if (i < 0)
1029 if (group->offset_map_size_n < ai)
1030 group->offset_map_size_n = ai;
1032 else
1034 if (group->offset_map_size_p < ai)
1035 group->offset_map_size_p = ai;
1038 if (expr_escapes)
1039 bitmap_set_bit (escaped, ai);
1043 static void
1044 reset_active_stores (void)
1046 active_local_stores = NULL;
1047 active_local_stores_len = 0;
1050 /* Free all READ_REC of the LAST_INSN of BB_INFO. */
1052 static void
1053 free_read_records (bb_info_t bb_info)
1055 insn_info_t insn_info = bb_info->last_insn;
1056 read_info_t *ptr = &insn_info->read_rec;
1057 while (*ptr)
1059 read_info_t next = (*ptr)->next;
1060 if ((*ptr)->alias_set == 0)
1062 read_info_type_pool.remove (*ptr);
1063 *ptr = next;
1065 else
1066 ptr = &(*ptr)->next;
1070 /* Set the BB_INFO so that the last insn is marked as a wild read. */
1072 static void
1073 add_wild_read (bb_info_t bb_info)
1075 insn_info_t insn_info = bb_info->last_insn;
1076 insn_info->wild_read = true;
1077 free_read_records (bb_info);
1078 reset_active_stores ();
1081 /* Set the BB_INFO so that the last insn is marked as a wild read of
1082 non-frame locations. */
1084 static void
1085 add_non_frame_wild_read (bb_info_t bb_info)
1087 insn_info_t insn_info = bb_info->last_insn;
1088 insn_info->non_frame_wild_read = true;
1089 free_read_records (bb_info);
1090 reset_active_stores ();
1093 /* Return true if X is a constant or one of the registers that behave
1094 as a constant over the life of a function. This is equivalent to
1095 !rtx_varies_p for memory addresses. */
1097 static bool
1098 const_or_frame_p (rtx x)
1100 if (CONSTANT_P (x))
1101 return true;
1103 if (GET_CODE (x) == REG)
1105 /* Note that we have to test for the actual rtx used for the frame
1106 and arg pointers and not just the register number in case we have
1107 eliminated the frame and/or arg pointer and are using it
1108 for pseudos. */
1109 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
1110 /* The arg pointer varies if it is not a fixed register. */
1111 || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
1112 || x == pic_offset_table_rtx)
1113 return true;
1114 return false;
1117 return false;
1120 /* Take all reasonable action to put the address of MEM into the form
1121 that we can do analysis on.
1123 The gold standard is to get the address into the form: address +
1124 OFFSET where address is something that rtx_varies_p considers a
1125 constant. When we can get the address in this form, we can do
1126 global analysis on it. Note that for constant bases, address is
1127 not actually returned, only the group_id. The address can be
1128 obtained from that.
1130 If that fails, we try cselib to get a value we can at least use
1131 locally. If that fails we return false.
1133 The GROUP_ID is set to -1 for cselib bases and the index of the
1134 group for non_varying bases.
1136 FOR_READ is true if this is a mem read and false if not. */
1138 static bool
1139 canon_address (rtx mem,
1140 alias_set_type *alias_set_out,
1141 int *group_id,
1142 HOST_WIDE_INT *offset,
1143 cselib_val **base)
1145 machine_mode address_mode = get_address_mode (mem);
1146 rtx mem_address = XEXP (mem, 0);
1147 rtx expanded_address, address;
1148 int expanded;
1150 *alias_set_out = 0;
1152 cselib_lookup (mem_address, address_mode, 1, GET_MODE (mem));
1154 if (dump_file && (dump_flags & TDF_DETAILS))
1156 fprintf (dump_file, " mem: ");
1157 print_inline_rtx (dump_file, mem_address, 0);
1158 fprintf (dump_file, "\n");
1161 /* First see if just canon_rtx (mem_address) is const or frame,
1162 if not, try cselib_expand_value_rtx and call canon_rtx on that. */
1163 address = NULL_RTX;
1164 for (expanded = 0; expanded < 2; expanded++)
1166 if (expanded)
1168 /* Use cselib to replace all of the reg references with the full
1169 expression. This will take care of the case where we have
1171 r_x = base + offset;
1172 val = *r_x;
1174 by making it into
1176 val = *(base + offset); */
1178 expanded_address = cselib_expand_value_rtx (mem_address,
1179 scratch, 5);
1181 /* If this fails, just go with the address from first
1182 iteration. */
1183 if (!expanded_address)
1184 break;
1186 else
1187 expanded_address = mem_address;
1189 /* Split the address into canonical BASE + OFFSET terms. */
1190 address = canon_rtx (expanded_address);
1192 *offset = 0;
1194 if (dump_file && (dump_flags & TDF_DETAILS))
1196 if (expanded)
1198 fprintf (dump_file, "\n after cselib_expand address: ");
1199 print_inline_rtx (dump_file, expanded_address, 0);
1200 fprintf (dump_file, "\n");
1203 fprintf (dump_file, "\n after canon_rtx address: ");
1204 print_inline_rtx (dump_file, address, 0);
1205 fprintf (dump_file, "\n");
1208 if (GET_CODE (address) == CONST)
1209 address = XEXP (address, 0);
1211 if (GET_CODE (address) == PLUS
1212 && CONST_INT_P (XEXP (address, 1)))
1214 *offset = INTVAL (XEXP (address, 1));
1215 address = XEXP (address, 0);
1218 if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem))
1219 && const_or_frame_p (address))
1221 group_info *group = get_group_info (address);
1223 if (dump_file && (dump_flags & TDF_DETAILS))
1224 fprintf (dump_file, " gid=%d offset=%d \n",
1225 group->id, (int)*offset);
1226 *base = NULL;
1227 *group_id = group->id;
1228 return true;
1232 *base = cselib_lookup (address, address_mode, true, GET_MODE (mem));
1233 *group_id = -1;
1235 if (*base == NULL)
1237 if (dump_file && (dump_flags & TDF_DETAILS))
1238 fprintf (dump_file, " no cselib val - should be a wild read.\n");
1239 return false;
1241 if (dump_file && (dump_flags & TDF_DETAILS))
1242 fprintf (dump_file, " varying cselib base=%u:%u offset = %d\n",
1243 (*base)->uid, (*base)->hash, (int)*offset);
1244 return true;
1248 /* Clear the rhs field from the active_local_stores array. */
1250 static void
1251 clear_rhs_from_active_local_stores (void)
1253 insn_info_t ptr = active_local_stores;
1255 while (ptr)
1257 store_info *store_info = ptr->store_rec;
1258 /* Skip the clobbers. */
1259 while (!store_info->is_set)
1260 store_info = store_info->next;
1262 store_info->rhs = NULL;
1263 store_info->const_rhs = NULL;
1265 ptr = ptr->next_local_store;
1270 /* Mark byte POS bytes from the beginning of store S_INFO as unneeded. */
1272 static inline void
1273 set_position_unneeded (store_info *s_info, int pos)
1275 if (__builtin_expect (s_info->is_large, false))
1277 if (bitmap_set_bit (s_info->positions_needed.large.bmap, pos))
1278 s_info->positions_needed.large.count++;
1280 else
1281 s_info->positions_needed.small_bitmask
1282 &= ~(((unsigned HOST_WIDE_INT) 1) << pos);
1285 /* Mark the whole store S_INFO as unneeded. */
1287 static inline void
1288 set_all_positions_unneeded (store_info *s_info)
1290 if (__builtin_expect (s_info->is_large, false))
1292 int pos, end = s_info->end - s_info->begin;
1293 for (pos = 0; pos < end; pos++)
1294 bitmap_set_bit (s_info->positions_needed.large.bmap, pos);
1295 s_info->positions_needed.large.count = end;
1297 else
1298 s_info->positions_needed.small_bitmask = (unsigned HOST_WIDE_INT) 0;
1301 /* Return TRUE if any bytes from S_INFO store are needed. */
1303 static inline bool
1304 any_positions_needed_p (store_info *s_info)
1306 if (__builtin_expect (s_info->is_large, false))
1307 return (s_info->positions_needed.large.count
1308 < s_info->end - s_info->begin);
1309 else
1310 return (s_info->positions_needed.small_bitmask
1311 != (unsigned HOST_WIDE_INT) 0);
1314 /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
1315 store are needed. */
1317 static inline bool
1318 all_positions_needed_p (store_info *s_info, int start, int width)
1320 if (__builtin_expect (s_info->is_large, false))
1322 int end = start + width;
1323 while (start < end)
1324 if (bitmap_bit_p (s_info->positions_needed.large.bmap, start++))
1325 return false;
1326 return true;
1328 else
1330 unsigned HOST_WIDE_INT mask = lowpart_bitmask (width) << start;
1331 return (s_info->positions_needed.small_bitmask & mask) == mask;
1336 static rtx get_stored_val (store_info *, machine_mode, HOST_WIDE_INT,
1337 HOST_WIDE_INT, basic_block, bool);
1340 /* BODY is an instruction pattern that belongs to INSN. Return 1 if
1341 there is a candidate store, after adding it to the appropriate
1342 local store group if so. */
1344 static int
1345 record_store (rtx body, bb_info_t bb_info)
1347 rtx mem, rhs, const_rhs, mem_addr;
1348 HOST_WIDE_INT offset = 0;
1349 HOST_WIDE_INT width = 0;
1350 alias_set_type spill_alias_set;
1351 insn_info_t insn_info = bb_info->last_insn;
1352 store_info *store_info = NULL;
1353 int group_id;
1354 cselib_val *base = NULL;
1355 insn_info_t ptr, last, redundant_reason;
1356 bool store_is_unused;
1358 if (GET_CODE (body) != SET && GET_CODE (body) != CLOBBER)
1359 return 0;
1361 mem = SET_DEST (body);
1363 /* If this is not used, then this cannot be used to keep the insn
1364 from being deleted. On the other hand, it does provide something
1365 that can be used to prove that another store is dead. */
1366 store_is_unused
1367 = (find_reg_note (insn_info->insn, REG_UNUSED, mem) != NULL);
1369 /* Check whether that value is a suitable memory location. */
1370 if (!MEM_P (mem))
1372 /* If the set or clobber is unused, then it does not effect our
1373 ability to get rid of the entire insn. */
1374 if (!store_is_unused)
1375 insn_info->cannot_delete = true;
1376 return 0;
1379 /* At this point we know mem is a mem. */
1380 if (GET_MODE (mem) == BLKmode)
1382 if (GET_CODE (XEXP (mem, 0)) == SCRATCH)
1384 if (dump_file && (dump_flags & TDF_DETAILS))
1385 fprintf (dump_file, " adding wild read for (clobber (mem:BLK (scratch))\n");
1386 add_wild_read (bb_info);
1387 insn_info->cannot_delete = true;
1388 return 0;
1390 /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
1391 as memset (addr, 0, 36); */
1392 else if (!MEM_SIZE_KNOWN_P (mem)
1393 || MEM_SIZE (mem) <= 0
1394 || MEM_SIZE (mem) > MAX_OFFSET
1395 || GET_CODE (body) != SET
1396 || !CONST_INT_P (SET_SRC (body)))
1398 if (!store_is_unused)
1400 /* If the set or clobber is unused, then it does not effect our
1401 ability to get rid of the entire insn. */
1402 insn_info->cannot_delete = true;
1403 clear_rhs_from_active_local_stores ();
1405 return 0;
1409 /* We can still process a volatile mem, we just cannot delete it. */
1410 if (MEM_VOLATILE_P (mem))
1411 insn_info->cannot_delete = true;
1413 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
1415 clear_rhs_from_active_local_stores ();
1416 return 0;
1419 if (GET_MODE (mem) == BLKmode)
1420 width = MEM_SIZE (mem);
1421 else
1422 width = GET_MODE_SIZE (GET_MODE (mem));
1424 if (spill_alias_set)
1426 bitmap store1 = clear_alias_group->store1_p;
1427 bitmap store2 = clear_alias_group->store2_p;
1429 gcc_assert (GET_MODE (mem) != BLKmode);
1431 if (!bitmap_set_bit (store1, spill_alias_set))
1432 bitmap_set_bit (store2, spill_alias_set);
1434 if (clear_alias_group->offset_map_size_p < spill_alias_set)
1435 clear_alias_group->offset_map_size_p = spill_alias_set;
1437 store_info = rtx_store_info_pool.allocate ();
1439 if (dump_file && (dump_flags & TDF_DETAILS))
1440 fprintf (dump_file, " processing spill store %d(%s)\n",
1441 (int) spill_alias_set, GET_MODE_NAME (GET_MODE (mem)));
1443 else if (group_id >= 0)
1445 /* In the restrictive case where the base is a constant or the
1446 frame pointer we can do global analysis. */
1448 group_info *group
1449 = rtx_group_vec[group_id];
1450 tree expr = MEM_EXPR (mem);
1452 store_info = rtx_store_info_pool.allocate ();
1453 set_usage_bits (group, offset, width, expr);
1455 if (dump_file && (dump_flags & TDF_DETAILS))
1456 fprintf (dump_file, " processing const base store gid=%d[%d..%d)\n",
1457 group_id, (int)offset, (int)(offset+width));
1459 else
1461 if (may_be_sp_based_p (XEXP (mem, 0)))
1462 insn_info->stack_pointer_based = true;
1463 insn_info->contains_cselib_groups = true;
1465 store_info = cse_store_info_pool.allocate ();
1466 group_id = -1;
1468 if (dump_file && (dump_flags & TDF_DETAILS))
1469 fprintf (dump_file, " processing cselib store [%d..%d)\n",
1470 (int)offset, (int)(offset+width));
1473 const_rhs = rhs = NULL_RTX;
1474 if (GET_CODE (body) == SET
1475 /* No place to keep the value after ra. */
1476 && !reload_completed
1477 && (REG_P (SET_SRC (body))
1478 || GET_CODE (SET_SRC (body)) == SUBREG
1479 || CONSTANT_P (SET_SRC (body)))
1480 && !MEM_VOLATILE_P (mem)
1481 /* Sometimes the store and reload is used for truncation and
1482 rounding. */
1483 && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
1485 rhs = SET_SRC (body);
1486 if (CONSTANT_P (rhs))
1487 const_rhs = rhs;
1488 else if (body == PATTERN (insn_info->insn))
1490 rtx tem = find_reg_note (insn_info->insn, REG_EQUAL, NULL_RTX);
1491 if (tem && CONSTANT_P (XEXP (tem, 0)))
1492 const_rhs = XEXP (tem, 0);
1494 if (const_rhs == NULL_RTX && REG_P (rhs))
1496 rtx tem = cselib_expand_value_rtx (rhs, scratch, 5);
1498 if (tem && CONSTANT_P (tem))
1499 const_rhs = tem;
1503 /* Check to see if this stores causes some other stores to be
1504 dead. */
1505 ptr = active_local_stores;
1506 last = NULL;
1507 redundant_reason = NULL;
1508 mem = canon_rtx (mem);
1509 /* For alias_set != 0 canon_true_dependence should be never called. */
1510 if (spill_alias_set)
1511 mem_addr = NULL_RTX;
1512 else
1514 if (group_id < 0)
1515 mem_addr = base->val_rtx;
1516 else
1518 group_info *group = rtx_group_vec[group_id];
1519 mem_addr = group->canon_base_addr;
1521 if (offset)
1522 mem_addr = plus_constant (get_address_mode (mem), mem_addr, offset);
1525 while (ptr)
1527 insn_info_t next = ptr->next_local_store;
1528 struct store_info *s_info = ptr->store_rec;
1529 bool del = true;
1531 /* Skip the clobbers. We delete the active insn if this insn
1532 shadows the set. To have been put on the active list, it
1533 has exactly on set. */
1534 while (!s_info->is_set)
1535 s_info = s_info->next;
1537 if (s_info->alias_set != spill_alias_set)
1538 del = false;
1539 else if (s_info->alias_set)
1541 struct clear_alias_mode_holder *entry
1542 = clear_alias_set_lookup (s_info->alias_set);
1543 /* Generally, spills cannot be processed if and of the
1544 references to the slot have a different mode. But if
1545 we are in the same block and mode is exactly the same
1546 between this store and one before in the same block,
1547 we can still delete it. */
1548 if ((GET_MODE (mem) == GET_MODE (s_info->mem))
1549 && (GET_MODE (mem) == entry->mode))
1551 del = true;
1552 set_all_positions_unneeded (s_info);
1554 if (dump_file && (dump_flags & TDF_DETAILS))
1555 fprintf (dump_file, " trying spill store in insn=%d alias_set=%d\n",
1556 INSN_UID (ptr->insn), (int) s_info->alias_set);
1558 else if ((s_info->group_id == group_id)
1559 && (s_info->cse_base == base))
1561 HOST_WIDE_INT i;
1562 if (dump_file && (dump_flags & TDF_DETAILS))
1563 fprintf (dump_file, " trying store in insn=%d gid=%d[%d..%d)\n",
1564 INSN_UID (ptr->insn), s_info->group_id,
1565 (int)s_info->begin, (int)s_info->end);
1567 /* Even if PTR won't be eliminated as unneeded, if both
1568 PTR and this insn store the same constant value, we might
1569 eliminate this insn instead. */
1570 if (s_info->const_rhs
1571 && const_rhs
1572 && offset >= s_info->begin
1573 && offset + width <= s_info->end
1574 && all_positions_needed_p (s_info, offset - s_info->begin,
1575 width))
1577 if (GET_MODE (mem) == BLKmode)
1579 if (GET_MODE (s_info->mem) == BLKmode
1580 && s_info->const_rhs == const_rhs)
1581 redundant_reason = ptr;
1583 else if (s_info->const_rhs == const0_rtx
1584 && const_rhs == const0_rtx)
1585 redundant_reason = ptr;
1586 else
1588 rtx val;
1589 start_sequence ();
1590 val = get_stored_val (s_info, GET_MODE (mem),
1591 offset, offset + width,
1592 BLOCK_FOR_INSN (insn_info->insn),
1593 true);
1594 if (get_insns () != NULL)
1595 val = NULL_RTX;
1596 end_sequence ();
1597 if (val && rtx_equal_p (val, const_rhs))
1598 redundant_reason = ptr;
1602 for (i = MAX (offset, s_info->begin);
1603 i < offset + width && i < s_info->end;
1604 i++)
1605 set_position_unneeded (s_info, i - s_info->begin);
1607 else if (s_info->rhs)
1608 /* Need to see if it is possible for this store to overwrite
1609 the value of store_info. If it is, set the rhs to NULL to
1610 keep it from being used to remove a load. */
1612 if (canon_true_dependence (s_info->mem,
1613 GET_MODE (s_info->mem),
1614 s_info->mem_addr,
1615 mem, mem_addr))
1617 s_info->rhs = NULL;
1618 s_info->const_rhs = NULL;
1622 /* An insn can be deleted if every position of every one of
1623 its s_infos is zero. */
1624 if (any_positions_needed_p (s_info))
1625 del = false;
1627 if (del)
1629 insn_info_t insn_to_delete = ptr;
1631 active_local_stores_len--;
1632 if (last)
1633 last->next_local_store = ptr->next_local_store;
1634 else
1635 active_local_stores = ptr->next_local_store;
1637 if (!insn_to_delete->cannot_delete)
1638 delete_dead_store_insn (insn_to_delete);
1640 else
1641 last = ptr;
1643 ptr = next;
1646 /* Finish filling in the store_info. */
1647 store_info->next = insn_info->store_rec;
1648 insn_info->store_rec = store_info;
1649 store_info->mem = mem;
1650 store_info->alias_set = spill_alias_set;
1651 store_info->mem_addr = mem_addr;
1652 store_info->cse_base = base;
1653 if (width > HOST_BITS_PER_WIDE_INT)
1655 store_info->is_large = true;
1656 store_info->positions_needed.large.count = 0;
1657 store_info->positions_needed.large.bmap = BITMAP_ALLOC (&dse_bitmap_obstack);
1659 else
1661 store_info->is_large = false;
1662 store_info->positions_needed.small_bitmask = lowpart_bitmask (width);
1664 store_info->group_id = group_id;
1665 store_info->begin = offset;
1666 store_info->end = offset + width;
1667 store_info->is_set = GET_CODE (body) == SET;
1668 store_info->rhs = rhs;
1669 store_info->const_rhs = const_rhs;
1670 store_info->redundant_reason = redundant_reason;
1672 /* If this is a clobber, we return 0. We will only be able to
1673 delete this insn if there is only one store USED store, but we
1674 can use the clobber to delete other stores earlier. */
1675 return store_info->is_set ? 1 : 0;
1679 static void
1680 dump_insn_info (const char * start, insn_info_t insn_info)
1682 fprintf (dump_file, "%s insn=%d %s\n", start,
1683 INSN_UID (insn_info->insn),
1684 insn_info->store_rec ? "has store" : "naked");
1688 /* If the modes are different and the value's source and target do not
1689 line up, we need to extract the value from lower part of the rhs of
1690 the store, shift it, and then put it into a form that can be shoved
1691 into the read_insn. This function generates a right SHIFT of a
1692 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The
1693 shift sequence is returned or NULL if we failed to find a
1694 shift. */
1696 static rtx
1697 find_shift_sequence (int access_size,
1698 store_info *store_info,
1699 machine_mode read_mode,
1700 int shift, bool speed, bool require_cst)
1702 machine_mode store_mode = GET_MODE (store_info->mem);
1703 machine_mode new_mode;
1704 rtx read_reg = NULL;
1706 /* Some machines like the x86 have shift insns for each size of
1707 operand. Other machines like the ppc or the ia-64 may only have
1708 shift insns that shift values within 32 or 64 bit registers.
1709 This loop tries to find the smallest shift insn that will right
1710 justify the value we want to read but is available in one insn on
1711 the machine. */
1713 for (new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT,
1714 MODE_INT);
1715 GET_MODE_BITSIZE (new_mode) <= BITS_PER_WORD;
1716 new_mode = GET_MODE_WIDER_MODE (new_mode))
1718 rtx target, new_reg, new_lhs;
1719 rtx_insn *shift_seq, *insn;
1720 int cost;
1722 /* If a constant was stored into memory, try to simplify it here,
1723 otherwise the cost of the shift might preclude this optimization
1724 e.g. at -Os, even when no actual shift will be needed. */
1725 if (store_info->const_rhs)
1727 unsigned int byte = subreg_lowpart_offset (new_mode, store_mode);
1728 rtx ret = simplify_subreg (new_mode, store_info->const_rhs,
1729 store_mode, byte);
1730 if (ret && CONSTANT_P (ret))
1732 ret = simplify_const_binary_operation (LSHIFTRT, new_mode,
1733 ret, GEN_INT (shift));
1734 if (ret && CONSTANT_P (ret))
1736 byte = subreg_lowpart_offset (read_mode, new_mode);
1737 ret = simplify_subreg (read_mode, ret, new_mode, byte);
1738 if (ret && CONSTANT_P (ret)
1739 && (set_src_cost (ret, read_mode, speed)
1740 <= COSTS_N_INSNS (1)))
1741 return ret;
1746 if (require_cst)
1747 return NULL_RTX;
1749 /* Try a wider mode if truncating the store mode to NEW_MODE
1750 requires a real instruction. */
1751 if (GET_MODE_BITSIZE (new_mode) < GET_MODE_BITSIZE (store_mode)
1752 && !TRULY_NOOP_TRUNCATION_MODES_P (new_mode, store_mode))
1753 continue;
1755 /* Also try a wider mode if the necessary punning is either not
1756 desirable or not possible. */
1757 if (!CONSTANT_P (store_info->rhs)
1758 && !MODES_TIEABLE_P (new_mode, store_mode))
1759 continue;
1761 new_reg = gen_reg_rtx (new_mode);
1763 start_sequence ();
1765 /* In theory we could also check for an ashr. Ian Taylor knows
1766 of one dsp where the cost of these two was not the same. But
1767 this really is a rare case anyway. */
1768 target = expand_binop (new_mode, lshr_optab, new_reg,
1769 GEN_INT (shift), new_reg, 1, OPTAB_DIRECT);
1771 shift_seq = get_insns ();
1772 end_sequence ();
1774 if (target != new_reg || shift_seq == NULL)
1775 continue;
1777 cost = 0;
1778 for (insn = shift_seq; insn != NULL_RTX; insn = NEXT_INSN (insn))
1779 if (INSN_P (insn))
1780 cost += insn_rtx_cost (PATTERN (insn), speed);
1782 /* The computation up to here is essentially independent
1783 of the arguments and could be precomputed. It may
1784 not be worth doing so. We could precompute if
1785 worthwhile or at least cache the results. The result
1786 technically depends on both SHIFT and ACCESS_SIZE,
1787 but in practice the answer will depend only on ACCESS_SIZE. */
1789 if (cost > COSTS_N_INSNS (1))
1790 continue;
1792 new_lhs = extract_low_bits (new_mode, store_mode,
1793 copy_rtx (store_info->rhs));
1794 if (new_lhs == NULL_RTX)
1795 continue;
1797 /* We found an acceptable shift. Generate a move to
1798 take the value from the store and put it into the
1799 shift pseudo, then shift it, then generate another
1800 move to put in into the target of the read. */
1801 emit_move_insn (new_reg, new_lhs);
1802 emit_insn (shift_seq);
1803 read_reg = extract_low_bits (read_mode, new_mode, new_reg);
1804 break;
1807 return read_reg;
1811 /* Call back for note_stores to find the hard regs set or clobbered by
1812 insn. Data is a bitmap of the hardregs set so far. */
1814 static void
1815 look_for_hardregs (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
1817 bitmap regs_set = (bitmap) data;
1819 if (REG_P (x)
1820 && HARD_REGISTER_P (x))
1821 bitmap_set_range (regs_set, REGNO (x), REG_NREGS (x));
1824 /* Helper function for replace_read and record_store.
1825 Attempt to return a value stored in STORE_INFO, from READ_BEGIN
1826 to one before READ_END bytes read in READ_MODE. Return NULL
1827 if not successful. If REQUIRE_CST is true, return always constant. */
1829 static rtx
1830 get_stored_val (store_info *store_info, machine_mode read_mode,
1831 HOST_WIDE_INT read_begin, HOST_WIDE_INT read_end,
1832 basic_block bb, bool require_cst)
1834 machine_mode store_mode = GET_MODE (store_info->mem);
1835 int shift;
1836 int access_size; /* In bytes. */
1837 rtx read_reg;
1839 /* To get here the read is within the boundaries of the write so
1840 shift will never be negative. Start out with the shift being in
1841 bytes. */
1842 if (store_mode == BLKmode)
1843 shift = 0;
1844 else if (BYTES_BIG_ENDIAN)
1845 shift = store_info->end - read_end;
1846 else
1847 shift = read_begin - store_info->begin;
1849 access_size = shift + GET_MODE_SIZE (read_mode);
1851 /* From now on it is bits. */
1852 shift *= BITS_PER_UNIT;
1854 if (shift)
1855 read_reg = find_shift_sequence (access_size, store_info, read_mode, shift,
1856 optimize_bb_for_speed_p (bb),
1857 require_cst);
1858 else if (store_mode == BLKmode)
1860 /* The store is a memset (addr, const_val, const_size). */
1861 gcc_assert (CONST_INT_P (store_info->rhs));
1862 store_mode = int_mode_for_mode (read_mode);
1863 if (store_mode == BLKmode)
1864 read_reg = NULL_RTX;
1865 else if (store_info->rhs == const0_rtx)
1866 read_reg = extract_low_bits (read_mode, store_mode, const0_rtx);
1867 else if (GET_MODE_BITSIZE (store_mode) > HOST_BITS_PER_WIDE_INT
1868 || BITS_PER_UNIT >= HOST_BITS_PER_WIDE_INT)
1869 read_reg = NULL_RTX;
1870 else
1872 unsigned HOST_WIDE_INT c
1873 = INTVAL (store_info->rhs)
1874 & (((HOST_WIDE_INT) 1 << BITS_PER_UNIT) - 1);
1875 int shift = BITS_PER_UNIT;
1876 while (shift < HOST_BITS_PER_WIDE_INT)
1878 c |= (c << shift);
1879 shift <<= 1;
1881 read_reg = gen_int_mode (c, store_mode);
1882 read_reg = extract_low_bits (read_mode, store_mode, read_reg);
1885 else if (store_info->const_rhs
1886 && (require_cst
1887 || GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode)))
1888 read_reg = extract_low_bits (read_mode, store_mode,
1889 copy_rtx (store_info->const_rhs));
1890 else
1891 read_reg = extract_low_bits (read_mode, store_mode,
1892 copy_rtx (store_info->rhs));
1893 if (require_cst && read_reg && !CONSTANT_P (read_reg))
1894 read_reg = NULL_RTX;
1895 return read_reg;
1898 /* Take a sequence of:
1899 A <- r1
1901 ... <- A
1903 and change it into
1904 r2 <- r1
1905 A <- r1
1907 ... <- r2
1911 r3 <- extract (r1)
1912 r3 <- r3 >> shift
1913 r2 <- extract (r3)
1914 ... <- r2
1918 r2 <- extract (r1)
1919 ... <- r2
1921 Depending on the alignment and the mode of the store and
1922 subsequent load.
1925 The STORE_INFO and STORE_INSN are for the store and READ_INFO
1926 and READ_INSN are for the read. Return true if the replacement
1927 went ok. */
1929 static bool
1930 replace_read (store_info *store_info, insn_info_t store_insn,
1931 read_info_t read_info, insn_info_t read_insn, rtx *loc,
1932 bitmap regs_live)
1934 machine_mode store_mode = GET_MODE (store_info->mem);
1935 machine_mode read_mode = GET_MODE (read_info->mem);
1936 rtx_insn *insns, *this_insn;
1937 rtx read_reg;
1938 basic_block bb;
1940 if (!dbg_cnt (dse))
1941 return false;
1943 /* Create a sequence of instructions to set up the read register.
1944 This sequence goes immediately before the store and its result
1945 is read by the load.
1947 We need to keep this in perspective. We are replacing a read
1948 with a sequence of insns, but the read will almost certainly be
1949 in cache, so it is not going to be an expensive one. Thus, we
1950 are not willing to do a multi insn shift or worse a subroutine
1951 call to get rid of the read. */
1952 if (dump_file && (dump_flags & TDF_DETAILS))
1953 fprintf (dump_file, "trying to replace %smode load in insn %d"
1954 " from %smode store in insn %d\n",
1955 GET_MODE_NAME (read_mode), INSN_UID (read_insn->insn),
1956 GET_MODE_NAME (store_mode), INSN_UID (store_insn->insn));
1957 start_sequence ();
1958 bb = BLOCK_FOR_INSN (read_insn->insn);
1959 read_reg = get_stored_val (store_info,
1960 read_mode, read_info->begin, read_info->end,
1961 bb, false);
1962 if (read_reg == NULL_RTX)
1964 end_sequence ();
1965 if (dump_file && (dump_flags & TDF_DETAILS))
1966 fprintf (dump_file, " -- could not extract bits of stored value\n");
1967 return false;
1969 /* Force the value into a new register so that it won't be clobbered
1970 between the store and the load. */
1971 read_reg = copy_to_mode_reg (read_mode, read_reg);
1972 insns = get_insns ();
1973 end_sequence ();
1975 if (insns != NULL_RTX)
1977 /* Now we have to scan the set of new instructions to see if the
1978 sequence contains and sets of hardregs that happened to be
1979 live at this point. For instance, this can happen if one of
1980 the insns sets the CC and the CC happened to be live at that
1981 point. This does occasionally happen, see PR 37922. */
1982 bitmap regs_set = BITMAP_ALLOC (&reg_obstack);
1984 for (this_insn = insns; this_insn != NULL_RTX; this_insn = NEXT_INSN (this_insn))
1985 note_stores (PATTERN (this_insn), look_for_hardregs, regs_set);
1987 bitmap_and_into (regs_set, regs_live);
1988 if (!bitmap_empty_p (regs_set))
1990 if (dump_file && (dump_flags & TDF_DETAILS))
1992 fprintf (dump_file,
1993 "abandoning replacement because sequence clobbers live hardregs:");
1994 df_print_regset (dump_file, regs_set);
1997 BITMAP_FREE (regs_set);
1998 return false;
2000 BITMAP_FREE (regs_set);
2003 if (validate_change (read_insn->insn, loc, read_reg, 0))
2005 deferred_change *change = deferred_change_pool.allocate ();
2007 /* Insert this right before the store insn where it will be safe
2008 from later insns that might change it before the read. */
2009 emit_insn_before (insns, store_insn->insn);
2011 /* And now for the kludge part: cselib croaks if you just
2012 return at this point. There are two reasons for this:
2014 1) Cselib has an idea of how many pseudos there are and
2015 that does not include the new ones we just added.
2017 2) Cselib does not know about the move insn we added
2018 above the store_info, and there is no way to tell it
2019 about it, because it has "moved on".
2021 Problem (1) is fixable with a certain amount of engineering.
2022 Problem (2) is requires starting the bb from scratch. This
2023 could be expensive.
2025 So we are just going to have to lie. The move/extraction
2026 insns are not really an issue, cselib did not see them. But
2027 the use of the new pseudo read_insn is a real problem because
2028 cselib has not scanned this insn. The way that we solve this
2029 problem is that we are just going to put the mem back for now
2030 and when we are finished with the block, we undo this. We
2031 keep a table of mems to get rid of. At the end of the basic
2032 block we can put them back. */
2034 *loc = read_info->mem;
2035 change->next = deferred_change_list;
2036 deferred_change_list = change;
2037 change->loc = loc;
2038 change->reg = read_reg;
2040 /* Get rid of the read_info, from the point of view of the
2041 rest of dse, play like this read never happened. */
2042 read_insn->read_rec = read_info->next;
2043 read_info_type_pool.remove (read_info);
2044 if (dump_file && (dump_flags & TDF_DETAILS))
2046 fprintf (dump_file, " -- replaced the loaded MEM with ");
2047 print_simple_rtl (dump_file, read_reg);
2048 fprintf (dump_file, "\n");
2050 return true;
2052 else
2054 if (dump_file && (dump_flags & TDF_DETAILS))
2056 fprintf (dump_file, " -- replacing the loaded MEM with ");
2057 print_simple_rtl (dump_file, read_reg);
2058 fprintf (dump_file, " led to an invalid instruction\n");
2060 return false;
2064 /* Check the address of MEM *LOC and kill any appropriate stores that may
2065 be active. */
2067 static void
2068 check_mem_read_rtx (rtx *loc, bb_info_t bb_info)
2070 rtx mem = *loc, mem_addr;
2071 insn_info_t insn_info;
2072 HOST_WIDE_INT offset = 0;
2073 HOST_WIDE_INT width = 0;
2074 alias_set_type spill_alias_set = 0;
2075 cselib_val *base = NULL;
2076 int group_id;
2077 read_info_t read_info;
2079 insn_info = bb_info->last_insn;
2081 if ((MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
2082 || (MEM_VOLATILE_P (mem)))
2084 if (dump_file && (dump_flags & TDF_DETAILS))
2085 fprintf (dump_file, " adding wild read, volatile or barrier.\n");
2086 add_wild_read (bb_info);
2087 insn_info->cannot_delete = true;
2088 return;
2091 /* If it is reading readonly mem, then there can be no conflict with
2092 another write. */
2093 if (MEM_READONLY_P (mem))
2094 return;
2096 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base))
2098 if (dump_file && (dump_flags & TDF_DETAILS))
2099 fprintf (dump_file, " adding wild read, canon_address failure.\n");
2100 add_wild_read (bb_info);
2101 return;
2104 if (GET_MODE (mem) == BLKmode)
2105 width = -1;
2106 else
2107 width = GET_MODE_SIZE (GET_MODE (mem));
2109 read_info = read_info_type_pool.allocate ();
2110 read_info->group_id = group_id;
2111 read_info->mem = mem;
2112 read_info->alias_set = spill_alias_set;
2113 read_info->begin = offset;
2114 read_info->end = offset + width;
2115 read_info->next = insn_info->read_rec;
2116 insn_info->read_rec = read_info;
2117 /* For alias_set != 0 canon_true_dependence should be never called. */
2118 if (spill_alias_set)
2119 mem_addr = NULL_RTX;
2120 else
2122 if (group_id < 0)
2123 mem_addr = base->val_rtx;
2124 else
2126 group_info *group = rtx_group_vec[group_id];
2127 mem_addr = group->canon_base_addr;
2129 if (offset)
2130 mem_addr = plus_constant (get_address_mode (mem), mem_addr, offset);
2133 /* We ignore the clobbers in store_info. The is mildly aggressive,
2134 but there really should not be a clobber followed by a read. */
2136 if (spill_alias_set)
2138 insn_info_t i_ptr = active_local_stores;
2139 insn_info_t last = NULL;
2141 if (dump_file && (dump_flags & TDF_DETAILS))
2142 fprintf (dump_file, " processing spill load %d\n",
2143 (int) spill_alias_set);
2145 while (i_ptr)
2147 store_info *store_info = i_ptr->store_rec;
2149 /* Skip the clobbers. */
2150 while (!store_info->is_set)
2151 store_info = store_info->next;
2153 if (store_info->alias_set == spill_alias_set)
2155 if (dump_file && (dump_flags & TDF_DETAILS))
2156 dump_insn_info ("removing from active", i_ptr);
2158 active_local_stores_len--;
2159 if (last)
2160 last->next_local_store = i_ptr->next_local_store;
2161 else
2162 active_local_stores = i_ptr->next_local_store;
2164 else
2165 last = i_ptr;
2166 i_ptr = i_ptr->next_local_store;
2169 else if (group_id >= 0)
2171 /* This is the restricted case where the base is a constant or
2172 the frame pointer and offset is a constant. */
2173 insn_info_t i_ptr = active_local_stores;
2174 insn_info_t last = NULL;
2176 if (dump_file && (dump_flags & TDF_DETAILS))
2178 if (width == -1)
2179 fprintf (dump_file, " processing const load gid=%d[BLK]\n",
2180 group_id);
2181 else
2182 fprintf (dump_file, " processing const load gid=%d[%d..%d)\n",
2183 group_id, (int)offset, (int)(offset+width));
2186 while (i_ptr)
2188 bool remove = false;
2189 store_info *store_info = i_ptr->store_rec;
2191 /* Skip the clobbers. */
2192 while (!store_info->is_set)
2193 store_info = store_info->next;
2195 /* There are three cases here. */
2196 if (store_info->group_id < 0)
2197 /* We have a cselib store followed by a read from a
2198 const base. */
2199 remove
2200 = canon_true_dependence (store_info->mem,
2201 GET_MODE (store_info->mem),
2202 store_info->mem_addr,
2203 mem, mem_addr);
2205 else if (group_id == store_info->group_id)
2207 /* This is a block mode load. We may get lucky and
2208 canon_true_dependence may save the day. */
2209 if (width == -1)
2210 remove
2211 = canon_true_dependence (store_info->mem,
2212 GET_MODE (store_info->mem),
2213 store_info->mem_addr,
2214 mem, mem_addr);
2216 /* If this read is just reading back something that we just
2217 stored, rewrite the read. */
2218 else
2220 if (store_info->rhs
2221 && offset >= store_info->begin
2222 && offset + width <= store_info->end
2223 && all_positions_needed_p (store_info,
2224 offset - store_info->begin,
2225 width)
2226 && replace_read (store_info, i_ptr, read_info,
2227 insn_info, loc, bb_info->regs_live))
2228 return;
2230 /* The bases are the same, just see if the offsets
2231 overlap. */
2232 if ((offset < store_info->end)
2233 && (offset + width > store_info->begin))
2234 remove = true;
2238 /* else
2239 The else case that is missing here is that the
2240 bases are constant but different. There is nothing
2241 to do here because there is no overlap. */
2243 if (remove)
2245 if (dump_file && (dump_flags & TDF_DETAILS))
2246 dump_insn_info ("removing from active", i_ptr);
2248 active_local_stores_len--;
2249 if (last)
2250 last->next_local_store = i_ptr->next_local_store;
2251 else
2252 active_local_stores = i_ptr->next_local_store;
2254 else
2255 last = i_ptr;
2256 i_ptr = i_ptr->next_local_store;
2259 else
2261 insn_info_t i_ptr = active_local_stores;
2262 insn_info_t last = NULL;
2263 if (dump_file && (dump_flags & TDF_DETAILS))
2265 fprintf (dump_file, " processing cselib load mem:");
2266 print_inline_rtx (dump_file, mem, 0);
2267 fprintf (dump_file, "\n");
2270 while (i_ptr)
2272 bool remove = false;
2273 store_info *store_info = i_ptr->store_rec;
2275 if (dump_file && (dump_flags & TDF_DETAILS))
2276 fprintf (dump_file, " processing cselib load against insn %d\n",
2277 INSN_UID (i_ptr->insn));
2279 /* Skip the clobbers. */
2280 while (!store_info->is_set)
2281 store_info = store_info->next;
2283 /* If this read is just reading back something that we just
2284 stored, rewrite the read. */
2285 if (store_info->rhs
2286 && store_info->group_id == -1
2287 && store_info->cse_base == base
2288 && width != -1
2289 && offset >= store_info->begin
2290 && offset + width <= store_info->end
2291 && all_positions_needed_p (store_info,
2292 offset - store_info->begin, width)
2293 && replace_read (store_info, i_ptr, read_info, insn_info, loc,
2294 bb_info->regs_live))
2295 return;
2297 if (!store_info->alias_set)
2298 remove = canon_true_dependence (store_info->mem,
2299 GET_MODE (store_info->mem),
2300 store_info->mem_addr,
2301 mem, mem_addr);
2303 if (remove)
2305 if (dump_file && (dump_flags & TDF_DETAILS))
2306 dump_insn_info ("removing from active", i_ptr);
2308 active_local_stores_len--;
2309 if (last)
2310 last->next_local_store = i_ptr->next_local_store;
2311 else
2312 active_local_stores = i_ptr->next_local_store;
2314 else
2315 last = i_ptr;
2316 i_ptr = i_ptr->next_local_store;
2321 /* A note_uses callback in which DATA points the INSN_INFO for
2322 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
2323 true for any part of *LOC. */
2325 static void
2326 check_mem_read_use (rtx *loc, void *data)
2328 subrtx_ptr_iterator::array_type array;
2329 FOR_EACH_SUBRTX_PTR (iter, array, loc, NONCONST)
2331 rtx *loc = *iter;
2332 if (MEM_P (*loc))
2333 check_mem_read_rtx (loc, (bb_info_t) data);
2338 /* Get arguments passed to CALL_INSN. Return TRUE if successful.
2339 So far it only handles arguments passed in registers. */
2341 static bool
2342 get_call_args (rtx call_insn, tree fn, rtx *args, int nargs)
2344 CUMULATIVE_ARGS args_so_far_v;
2345 cumulative_args_t args_so_far;
2346 tree arg;
2347 int idx;
2349 INIT_CUMULATIVE_ARGS (args_so_far_v, TREE_TYPE (fn), NULL_RTX, 0, 3);
2350 args_so_far = pack_cumulative_args (&args_so_far_v);
2352 arg = TYPE_ARG_TYPES (TREE_TYPE (fn));
2353 for (idx = 0;
2354 arg != void_list_node && idx < nargs;
2355 arg = TREE_CHAIN (arg), idx++)
2357 machine_mode mode = TYPE_MODE (TREE_VALUE (arg));
2358 rtx reg, link, tmp;
2359 reg = targetm.calls.function_arg (args_so_far, mode, NULL_TREE, true);
2360 if (!reg || !REG_P (reg) || GET_MODE (reg) != mode
2361 || GET_MODE_CLASS (mode) != MODE_INT)
2362 return false;
2364 for (link = CALL_INSN_FUNCTION_USAGE (call_insn);
2365 link;
2366 link = XEXP (link, 1))
2367 if (GET_CODE (XEXP (link, 0)) == USE)
2369 args[idx] = XEXP (XEXP (link, 0), 0);
2370 if (REG_P (args[idx])
2371 && REGNO (args[idx]) == REGNO (reg)
2372 && (GET_MODE (args[idx]) == mode
2373 || (GET_MODE_CLASS (GET_MODE (args[idx])) == MODE_INT
2374 && (GET_MODE_SIZE (GET_MODE (args[idx]))
2375 <= UNITS_PER_WORD)
2376 && (GET_MODE_SIZE (GET_MODE (args[idx]))
2377 > GET_MODE_SIZE (mode)))))
2378 break;
2380 if (!link)
2381 return false;
2383 tmp = cselib_expand_value_rtx (args[idx], scratch, 5);
2384 if (GET_MODE (args[idx]) != mode)
2386 if (!tmp || !CONST_INT_P (tmp))
2387 return false;
2388 tmp = gen_int_mode (INTVAL (tmp), mode);
2390 if (tmp)
2391 args[idx] = tmp;
2393 targetm.calls.function_arg_advance (args_so_far, mode, NULL_TREE, true);
2395 if (arg != void_list_node || idx != nargs)
2396 return false;
2397 return true;
2400 /* Return a bitmap of the fixed registers contained in IN. */
2402 static bitmap
2403 copy_fixed_regs (const_bitmap in)
2405 bitmap ret;
2407 ret = ALLOC_REG_SET (NULL);
2408 bitmap_and (ret, in, fixed_reg_set_regset);
2409 return ret;
2412 /* Apply record_store to all candidate stores in INSN. Mark INSN
2413 if some part of it is not a candidate store and assigns to a
2414 non-register target. */
2416 static void
2417 scan_insn (bb_info_t bb_info, rtx_insn *insn)
2419 rtx body;
2420 insn_info_type *insn_info = insn_info_type_pool.allocate ();
2421 int mems_found = 0;
2422 memset (insn_info, 0, sizeof (struct insn_info_type));
2424 if (dump_file && (dump_flags & TDF_DETAILS))
2425 fprintf (dump_file, "\n**scanning insn=%d\n",
2426 INSN_UID (insn));
2428 insn_info->prev_insn = bb_info->last_insn;
2429 insn_info->insn = insn;
2430 bb_info->last_insn = insn_info;
2432 if (DEBUG_INSN_P (insn))
2434 insn_info->cannot_delete = true;
2435 return;
2438 /* Look at all of the uses in the insn. */
2439 note_uses (&PATTERN (insn), check_mem_read_use, bb_info);
2441 if (CALL_P (insn))
2443 bool const_call;
2444 tree memset_call = NULL_TREE;
2446 insn_info->cannot_delete = true;
2448 /* Const functions cannot do anything bad i.e. read memory,
2449 however, they can read their parameters which may have
2450 been pushed onto the stack.
2451 memset and bzero don't read memory either. */
2452 const_call = RTL_CONST_CALL_P (insn);
2453 if (!const_call)
2455 rtx call = get_call_rtx_from (insn);
2456 if (call && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
2458 rtx symbol = XEXP (XEXP (call, 0), 0);
2459 if (SYMBOL_REF_DECL (symbol)
2460 && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
2462 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
2463 == BUILT_IN_NORMAL
2464 && (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))
2465 == BUILT_IN_MEMSET))
2466 || SYMBOL_REF_DECL (symbol) == block_clear_fn)
2467 memset_call = SYMBOL_REF_DECL (symbol);
2471 if (const_call || memset_call)
2473 insn_info_t i_ptr = active_local_stores;
2474 insn_info_t last = NULL;
2476 if (dump_file && (dump_flags & TDF_DETAILS))
2477 fprintf (dump_file, "%s call %d\n",
2478 const_call ? "const" : "memset", INSN_UID (insn));
2480 /* See the head comment of the frame_read field. */
2481 if (reload_completed
2482 /* Tail calls are storing their arguments using
2483 arg pointer. If it is a frame pointer on the target,
2484 even before reload we need to kill frame pointer based
2485 stores. */
2486 || (SIBLING_CALL_P (insn)
2487 && HARD_FRAME_POINTER_IS_ARG_POINTER))
2488 insn_info->frame_read = true;
2490 /* Loop over the active stores and remove those which are
2491 killed by the const function call. */
2492 while (i_ptr)
2494 bool remove_store = false;
2496 /* The stack pointer based stores are always killed. */
2497 if (i_ptr->stack_pointer_based)
2498 remove_store = true;
2500 /* If the frame is read, the frame related stores are killed. */
2501 else if (insn_info->frame_read)
2503 store_info *store_info = i_ptr->store_rec;
2505 /* Skip the clobbers. */
2506 while (!store_info->is_set)
2507 store_info = store_info->next;
2509 if (store_info->group_id >= 0
2510 && rtx_group_vec[store_info->group_id]->frame_related)
2511 remove_store = true;
2514 if (remove_store)
2516 if (dump_file && (dump_flags & TDF_DETAILS))
2517 dump_insn_info ("removing from active", i_ptr);
2519 active_local_stores_len--;
2520 if (last)
2521 last->next_local_store = i_ptr->next_local_store;
2522 else
2523 active_local_stores = i_ptr->next_local_store;
2525 else
2526 last = i_ptr;
2528 i_ptr = i_ptr->next_local_store;
2531 if (memset_call)
2533 rtx args[3];
2534 if (get_call_args (insn, memset_call, args, 3)
2535 && CONST_INT_P (args[1])
2536 && CONST_INT_P (args[2])
2537 && INTVAL (args[2]) > 0)
2539 rtx mem = gen_rtx_MEM (BLKmode, args[0]);
2540 set_mem_size (mem, INTVAL (args[2]));
2541 body = gen_rtx_SET (mem, args[1]);
2542 mems_found += record_store (body, bb_info);
2543 if (dump_file && (dump_flags & TDF_DETAILS))
2544 fprintf (dump_file, "handling memset as BLKmode store\n");
2545 if (mems_found == 1)
2547 if (active_local_stores_len++
2548 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES))
2550 active_local_stores_len = 1;
2551 active_local_stores = NULL;
2553 insn_info->fixed_regs_live
2554 = copy_fixed_regs (bb_info->regs_live);
2555 insn_info->next_local_store = active_local_stores;
2556 active_local_stores = insn_info;
2561 else if (SIBLING_CALL_P (insn) && reload_completed)
2562 /* Arguments for a sibling call that are pushed to memory are passed
2563 using the incoming argument pointer of the current function. After
2564 reload that might be (and likely is) frame pointer based. */
2565 add_wild_read (bb_info);
2566 else
2567 /* Every other call, including pure functions, may read any memory
2568 that is not relative to the frame. */
2569 add_non_frame_wild_read (bb_info);
2571 return;
2574 /* Assuming that there are sets in these insns, we cannot delete
2575 them. */
2576 if ((GET_CODE (PATTERN (insn)) == CLOBBER)
2577 || volatile_refs_p (PATTERN (insn))
2578 || (!cfun->can_delete_dead_exceptions && !insn_nothrow_p (insn))
2579 || (RTX_FRAME_RELATED_P (insn))
2580 || find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX))
2581 insn_info->cannot_delete = true;
2583 body = PATTERN (insn);
2584 if (GET_CODE (body) == PARALLEL)
2586 int i;
2587 for (i = 0; i < XVECLEN (body, 0); i++)
2588 mems_found += record_store (XVECEXP (body, 0, i), bb_info);
2590 else
2591 mems_found += record_store (body, bb_info);
2593 if (dump_file && (dump_flags & TDF_DETAILS))
2594 fprintf (dump_file, "mems_found = %d, cannot_delete = %s\n",
2595 mems_found, insn_info->cannot_delete ? "true" : "false");
2597 /* If we found some sets of mems, add it into the active_local_stores so
2598 that it can be locally deleted if found dead or used for
2599 replace_read and redundant constant store elimination. Otherwise mark
2600 it as cannot delete. This simplifies the processing later. */
2601 if (mems_found == 1)
2603 if (active_local_stores_len++
2604 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES))
2606 active_local_stores_len = 1;
2607 active_local_stores = NULL;
2609 insn_info->fixed_regs_live = copy_fixed_regs (bb_info->regs_live);
2610 insn_info->next_local_store = active_local_stores;
2611 active_local_stores = insn_info;
2613 else
2614 insn_info->cannot_delete = true;
2618 /* Remove BASE from the set of active_local_stores. This is a
2619 callback from cselib that is used to get rid of the stores in
2620 active_local_stores. */
2622 static void
2623 remove_useless_values (cselib_val *base)
2625 insn_info_t insn_info = active_local_stores;
2626 insn_info_t last = NULL;
2628 while (insn_info)
2630 store_info *store_info = insn_info->store_rec;
2631 bool del = false;
2633 /* If ANY of the store_infos match the cselib group that is
2634 being deleted, then the insn can not be deleted. */
2635 while (store_info)
2637 if ((store_info->group_id == -1)
2638 && (store_info->cse_base == base))
2640 del = true;
2641 break;
2643 store_info = store_info->next;
2646 if (del)
2648 active_local_stores_len--;
2649 if (last)
2650 last->next_local_store = insn_info->next_local_store;
2651 else
2652 active_local_stores = insn_info->next_local_store;
2653 free_store_info (insn_info);
2655 else
2656 last = insn_info;
2658 insn_info = insn_info->next_local_store;
2663 /* Do all of step 1. */
2665 static void
2666 dse_step1 (void)
2668 basic_block bb;
2669 bitmap regs_live = BITMAP_ALLOC (&reg_obstack);
2671 cselib_init (0);
2672 all_blocks = BITMAP_ALLOC (NULL);
2673 bitmap_set_bit (all_blocks, ENTRY_BLOCK);
2674 bitmap_set_bit (all_blocks, EXIT_BLOCK);
2676 FOR_ALL_BB_FN (bb, cfun)
2678 insn_info_t ptr;
2679 bb_info_t bb_info = dse_bb_info_type_pool.allocate ();
2681 memset (bb_info, 0, sizeof (dse_bb_info_type));
2682 bitmap_set_bit (all_blocks, bb->index);
2683 bb_info->regs_live = regs_live;
2685 bitmap_copy (regs_live, DF_LR_IN (bb));
2686 df_simulate_initialize_forwards (bb, regs_live);
2688 bb_table[bb->index] = bb_info;
2689 cselib_discard_hook = remove_useless_values;
2691 if (bb->index >= NUM_FIXED_BLOCKS)
2693 rtx_insn *insn;
2695 active_local_stores = NULL;
2696 active_local_stores_len = 0;
2697 cselib_clear_table ();
2699 /* Scan the insns. */
2700 FOR_BB_INSNS (bb, insn)
2702 if (INSN_P (insn))
2703 scan_insn (bb_info, insn);
2704 cselib_process_insn (insn);
2705 if (INSN_P (insn))
2706 df_simulate_one_insn_forwards (bb, insn, regs_live);
2709 /* This is something of a hack, because the global algorithm
2710 is supposed to take care of the case where stores go dead
2711 at the end of the function. However, the global
2712 algorithm must take a more conservative view of block
2713 mode reads than the local alg does. So to get the case
2714 where you have a store to the frame followed by a non
2715 overlapping block more read, we look at the active local
2716 stores at the end of the function and delete all of the
2717 frame and spill based ones. */
2718 if (stores_off_frame_dead_at_return
2719 && (EDGE_COUNT (bb->succs) == 0
2720 || (single_succ_p (bb)
2721 && single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
2722 && ! crtl->calls_eh_return)))
2724 insn_info_t i_ptr = active_local_stores;
2725 while (i_ptr)
2727 store_info *store_info = i_ptr->store_rec;
2729 /* Skip the clobbers. */
2730 while (!store_info->is_set)
2731 store_info = store_info->next;
2732 if (store_info->alias_set && !i_ptr->cannot_delete)
2733 delete_dead_store_insn (i_ptr);
2734 else
2735 if (store_info->group_id >= 0)
2737 group_info *group
2738 = rtx_group_vec[store_info->group_id];
2739 if (group->frame_related && !i_ptr->cannot_delete)
2740 delete_dead_store_insn (i_ptr);
2743 i_ptr = i_ptr->next_local_store;
2747 /* Get rid of the loads that were discovered in
2748 replace_read. Cselib is finished with this block. */
2749 while (deferred_change_list)
2751 deferred_change *next = deferred_change_list->next;
2753 /* There is no reason to validate this change. That was
2754 done earlier. */
2755 *deferred_change_list->loc = deferred_change_list->reg;
2756 deferred_change_pool.remove (deferred_change_list);
2757 deferred_change_list = next;
2760 /* Get rid of all of the cselib based store_infos in this
2761 block and mark the containing insns as not being
2762 deletable. */
2763 ptr = bb_info->last_insn;
2764 while (ptr)
2766 if (ptr->contains_cselib_groups)
2768 store_info *s_info = ptr->store_rec;
2769 while (s_info && !s_info->is_set)
2770 s_info = s_info->next;
2771 if (s_info
2772 && s_info->redundant_reason
2773 && s_info->redundant_reason->insn
2774 && !ptr->cannot_delete)
2776 if (dump_file && (dump_flags & TDF_DETAILS))
2777 fprintf (dump_file, "Locally deleting insn %d "
2778 "because insn %d stores the "
2779 "same value and couldn't be "
2780 "eliminated\n",
2781 INSN_UID (ptr->insn),
2782 INSN_UID (s_info->redundant_reason->insn));
2783 delete_dead_store_insn (ptr);
2785 free_store_info (ptr);
2787 else
2789 store_info *s_info;
2791 /* Free at least positions_needed bitmaps. */
2792 for (s_info = ptr->store_rec; s_info; s_info = s_info->next)
2793 if (s_info->is_large)
2795 BITMAP_FREE (s_info->positions_needed.large.bmap);
2796 s_info->is_large = false;
2799 ptr = ptr->prev_insn;
2802 cse_store_info_pool.release ();
2804 bb_info->regs_live = NULL;
2807 BITMAP_FREE (regs_live);
2808 cselib_finish ();
2809 rtx_group_table->empty ();
2813 /*----------------------------------------------------------------------------
2814 Second step.
2816 Assign each byte position in the stores that we are going to
2817 analyze globally to a position in the bitmaps. Returns true if
2818 there are any bit positions assigned.
2819 ----------------------------------------------------------------------------*/
2821 static void
2822 dse_step2_init (void)
2824 unsigned int i;
2825 group_info *group;
2827 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
2829 /* For all non stack related bases, we only consider a store to
2830 be deletable if there are two or more stores for that
2831 position. This is because it takes one store to make the
2832 other store redundant. However, for the stores that are
2833 stack related, we consider them if there is only one store
2834 for the position. We do this because the stack related
2835 stores can be deleted if their is no read between them and
2836 the end of the function.
2838 To make this work in the current framework, we take the stack
2839 related bases add all of the bits from store1 into store2.
2840 This has the effect of making the eligible even if there is
2841 only one store. */
2843 if (stores_off_frame_dead_at_return && group->frame_related)
2845 bitmap_ior_into (group->store2_n, group->store1_n);
2846 bitmap_ior_into (group->store2_p, group->store1_p);
2847 if (dump_file && (dump_flags & TDF_DETAILS))
2848 fprintf (dump_file, "group %d is frame related ", i);
2851 group->offset_map_size_n++;
2852 group->offset_map_n = XOBNEWVEC (&dse_obstack, int,
2853 group->offset_map_size_n);
2854 group->offset_map_size_p++;
2855 group->offset_map_p = XOBNEWVEC (&dse_obstack, int,
2856 group->offset_map_size_p);
2857 group->process_globally = false;
2858 if (dump_file && (dump_flags & TDF_DETAILS))
2860 fprintf (dump_file, "group %d(%d+%d): ", i,
2861 (int)bitmap_count_bits (group->store2_n),
2862 (int)bitmap_count_bits (group->store2_p));
2863 bitmap_print (dump_file, group->store2_n, "n ", " ");
2864 bitmap_print (dump_file, group->store2_p, "p ", "\n");
2870 /* Init the offset tables for the normal case. */
2872 static bool
2873 dse_step2_nospill (void)
2875 unsigned int i;
2876 group_info *group;
2877 /* Position 0 is unused because 0 is used in the maps to mean
2878 unused. */
2879 current_position = 1;
2880 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
2882 bitmap_iterator bi;
2883 unsigned int j;
2885 if (group == clear_alias_group)
2886 continue;
2888 memset (group->offset_map_n, 0, sizeof (int) * group->offset_map_size_n);
2889 memset (group->offset_map_p, 0, sizeof (int) * group->offset_map_size_p);
2890 bitmap_clear (group->group_kill);
2892 EXECUTE_IF_SET_IN_BITMAP (group->store2_n, 0, j, bi)
2894 bitmap_set_bit (group->group_kill, current_position);
2895 if (bitmap_bit_p (group->escaped_n, j))
2896 bitmap_set_bit (kill_on_calls, current_position);
2897 group->offset_map_n[j] = current_position++;
2898 group->process_globally = true;
2900 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2902 bitmap_set_bit (group->group_kill, current_position);
2903 if (bitmap_bit_p (group->escaped_p, j))
2904 bitmap_set_bit (kill_on_calls, current_position);
2905 group->offset_map_p[j] = current_position++;
2906 group->process_globally = true;
2909 return current_position != 1;
2914 /*----------------------------------------------------------------------------
2915 Third step.
2917 Build the bit vectors for the transfer functions.
2918 ----------------------------------------------------------------------------*/
2921 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
2922 there, return 0. */
2924 static int
2925 get_bitmap_index (group_info *group_info, HOST_WIDE_INT offset)
2927 if (offset < 0)
2929 HOST_WIDE_INT offset_p = -offset;
2930 if (offset_p >= group_info->offset_map_size_n)
2931 return 0;
2932 return group_info->offset_map_n[offset_p];
2934 else
2936 if (offset >= group_info->offset_map_size_p)
2937 return 0;
2938 return group_info->offset_map_p[offset];
2943 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
2944 may be NULL. */
2946 static void
2947 scan_stores_nospill (store_info *store_info, bitmap gen, bitmap kill)
2949 while (store_info)
2951 HOST_WIDE_INT i;
2952 group_info *group_info
2953 = rtx_group_vec[store_info->group_id];
2954 if (group_info->process_globally)
2955 for (i = store_info->begin; i < store_info->end; i++)
2957 int index = get_bitmap_index (group_info, i);
2958 if (index != 0)
2960 bitmap_set_bit (gen, index);
2961 if (kill)
2962 bitmap_clear_bit (kill, index);
2965 store_info = store_info->next;
2970 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
2971 may be NULL. */
2973 static void
2974 scan_stores_spill (store_info *store_info, bitmap gen, bitmap kill)
2976 while (store_info)
2978 if (store_info->alias_set)
2980 int index = get_bitmap_index (clear_alias_group,
2981 store_info->alias_set);
2982 if (index != 0)
2984 bitmap_set_bit (gen, index);
2985 if (kill)
2986 bitmap_clear_bit (kill, index);
2989 store_info = store_info->next;
2994 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
2995 may be NULL. */
2997 static void
2998 scan_reads_nospill (insn_info_t insn_info, bitmap gen, bitmap kill)
3000 read_info_t read_info = insn_info->read_rec;
3001 int i;
3002 group_info *group;
3004 /* If this insn reads the frame, kill all the frame related stores. */
3005 if (insn_info->frame_read)
3007 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
3008 if (group->process_globally && group->frame_related)
3010 if (kill)
3011 bitmap_ior_into (kill, group->group_kill);
3012 bitmap_and_compl_into (gen, group->group_kill);
3015 if (insn_info->non_frame_wild_read)
3017 /* Kill all non-frame related stores. Kill all stores of variables that
3018 escape. */
3019 if (kill)
3020 bitmap_ior_into (kill, kill_on_calls);
3021 bitmap_and_compl_into (gen, kill_on_calls);
3022 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
3023 if (group->process_globally && !group->frame_related)
3025 if (kill)
3026 bitmap_ior_into (kill, group->group_kill);
3027 bitmap_and_compl_into (gen, group->group_kill);
3030 while (read_info)
3032 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
3034 if (group->process_globally)
3036 if (i == read_info->group_id)
3038 if (read_info->begin > read_info->end)
3040 /* Begin > end for block mode reads. */
3041 if (kill)
3042 bitmap_ior_into (kill, group->group_kill);
3043 bitmap_and_compl_into (gen, group->group_kill);
3045 else
3047 /* The groups are the same, just process the
3048 offsets. */
3049 HOST_WIDE_INT j;
3050 for (j = read_info->begin; j < read_info->end; j++)
3052 int index = get_bitmap_index (group, j);
3053 if (index != 0)
3055 if (kill)
3056 bitmap_set_bit (kill, index);
3057 bitmap_clear_bit (gen, index);
3062 else
3064 /* The groups are different, if the alias sets
3065 conflict, clear the entire group. We only need
3066 to apply this test if the read_info is a cselib
3067 read. Anything with a constant base cannot alias
3068 something else with a different constant
3069 base. */
3070 if ((read_info->group_id < 0)
3071 && canon_true_dependence (group->base_mem,
3072 GET_MODE (group->base_mem),
3073 group->canon_base_addr,
3074 read_info->mem, NULL_RTX))
3076 if (kill)
3077 bitmap_ior_into (kill, group->group_kill);
3078 bitmap_and_compl_into (gen, group->group_kill);
3084 read_info = read_info->next;
3088 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
3089 may be NULL. */
3091 static void
3092 scan_reads_spill (read_info_t read_info, bitmap gen, bitmap kill)
3094 while (read_info)
3096 if (read_info->alias_set)
3098 int index = get_bitmap_index (clear_alias_group,
3099 read_info->alias_set);
3100 if (index != 0)
3102 if (kill)
3103 bitmap_set_bit (kill, index);
3104 bitmap_clear_bit (gen, index);
3108 read_info = read_info->next;
3113 /* Return the insn in BB_INFO before the first wild read or if there
3114 are no wild reads in the block, return the last insn. */
3116 static insn_info_t
3117 find_insn_before_first_wild_read (bb_info_t bb_info)
3119 insn_info_t insn_info = bb_info->last_insn;
3120 insn_info_t last_wild_read = NULL;
3122 while (insn_info)
3124 if (insn_info->wild_read)
3126 last_wild_read = insn_info->prev_insn;
3127 /* Block starts with wild read. */
3128 if (!last_wild_read)
3129 return NULL;
3132 insn_info = insn_info->prev_insn;
3135 if (last_wild_read)
3136 return last_wild_read;
3137 else
3138 return bb_info->last_insn;
3142 /* Scan the insns in BB_INFO starting at PTR and going to the top of
3143 the block in order to build the gen and kill sets for the block.
3144 We start at ptr which may be the last insn in the block or may be
3145 the first insn with a wild read. In the latter case we are able to
3146 skip the rest of the block because it just does not matter:
3147 anything that happens is hidden by the wild read. */
3149 static void
3150 dse_step3_scan (bool for_spills, basic_block bb)
3152 bb_info_t bb_info = bb_table[bb->index];
3153 insn_info_t insn_info;
3155 if (for_spills)
3156 /* There are no wild reads in the spill case. */
3157 insn_info = bb_info->last_insn;
3158 else
3159 insn_info = find_insn_before_first_wild_read (bb_info);
3161 /* In the spill case or in the no_spill case if there is no wild
3162 read in the block, we will need a kill set. */
3163 if (insn_info == bb_info->last_insn)
3165 if (bb_info->kill)
3166 bitmap_clear (bb_info->kill);
3167 else
3168 bb_info->kill = BITMAP_ALLOC (&dse_bitmap_obstack);
3170 else
3171 if (bb_info->kill)
3172 BITMAP_FREE (bb_info->kill);
3174 while (insn_info)
3176 /* There may have been code deleted by the dce pass run before
3177 this phase. */
3178 if (insn_info->insn && INSN_P (insn_info->insn))
3180 /* Process the read(s) last. */
3181 if (for_spills)
3183 scan_stores_spill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3184 scan_reads_spill (insn_info->read_rec, bb_info->gen, bb_info->kill);
3186 else
3188 scan_stores_nospill (insn_info->store_rec, bb_info->gen, bb_info->kill);
3189 scan_reads_nospill (insn_info, bb_info->gen, bb_info->kill);
3193 insn_info = insn_info->prev_insn;
3198 /* Set the gen set of the exit block, and also any block with no
3199 successors that does not have a wild read. */
3201 static void
3202 dse_step3_exit_block_scan (bb_info_t bb_info)
3204 /* The gen set is all 0's for the exit block except for the
3205 frame_pointer_group. */
3207 if (stores_off_frame_dead_at_return)
3209 unsigned int i;
3210 group_info *group;
3212 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
3214 if (group->process_globally && group->frame_related)
3215 bitmap_ior_into (bb_info->gen, group->group_kill);
3221 /* Find all of the blocks that are not backwards reachable from the
3222 exit block or any block with no successors (BB). These are the
3223 infinite loops or infinite self loops. These blocks will still
3224 have their bits set in UNREACHABLE_BLOCKS. */
3226 static void
3227 mark_reachable_blocks (sbitmap unreachable_blocks, basic_block bb)
3229 edge e;
3230 edge_iterator ei;
3232 if (bitmap_bit_p (unreachable_blocks, bb->index))
3234 bitmap_clear_bit (unreachable_blocks, bb->index);
3235 FOR_EACH_EDGE (e, ei, bb->preds)
3237 mark_reachable_blocks (unreachable_blocks, e->src);
3242 /* Build the transfer functions for the function. */
3244 static void
3245 dse_step3 (bool for_spills)
3247 basic_block bb;
3248 sbitmap unreachable_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
3249 sbitmap_iterator sbi;
3250 bitmap all_ones = NULL;
3251 unsigned int i;
3253 bitmap_ones (unreachable_blocks);
3255 FOR_ALL_BB_FN (bb, cfun)
3257 bb_info_t bb_info = bb_table[bb->index];
3258 if (bb_info->gen)
3259 bitmap_clear (bb_info->gen);
3260 else
3261 bb_info->gen = BITMAP_ALLOC (&dse_bitmap_obstack);
3263 if (bb->index == ENTRY_BLOCK)
3265 else if (bb->index == EXIT_BLOCK)
3266 dse_step3_exit_block_scan (bb_info);
3267 else
3268 dse_step3_scan (for_spills, bb);
3269 if (EDGE_COUNT (bb->succs) == 0)
3270 mark_reachable_blocks (unreachable_blocks, bb);
3272 /* If this is the second time dataflow is run, delete the old
3273 sets. */
3274 if (bb_info->in)
3275 BITMAP_FREE (bb_info->in);
3276 if (bb_info->out)
3277 BITMAP_FREE (bb_info->out);
3280 /* For any block in an infinite loop, we must initialize the out set
3281 to all ones. This could be expensive, but almost never occurs in
3282 practice. However, it is common in regression tests. */
3283 EXECUTE_IF_SET_IN_BITMAP (unreachable_blocks, 0, i, sbi)
3285 if (bitmap_bit_p (all_blocks, i))
3287 bb_info_t bb_info = bb_table[i];
3288 if (!all_ones)
3290 unsigned int j;
3291 group_info *group;
3293 all_ones = BITMAP_ALLOC (&dse_bitmap_obstack);
3294 FOR_EACH_VEC_ELT (rtx_group_vec, j, group)
3295 bitmap_ior_into (all_ones, group->group_kill);
3297 if (!bb_info->out)
3299 bb_info->out = BITMAP_ALLOC (&dse_bitmap_obstack);
3300 bitmap_copy (bb_info->out, all_ones);
3305 if (all_ones)
3306 BITMAP_FREE (all_ones);
3307 sbitmap_free (unreachable_blocks);
3312 /*----------------------------------------------------------------------------
3313 Fourth step.
3315 Solve the bitvector equations.
3316 ----------------------------------------------------------------------------*/
3319 /* Confluence function for blocks with no successors. Create an out
3320 set from the gen set of the exit block. This block logically has
3321 the exit block as a successor. */
3325 static void
3326 dse_confluence_0 (basic_block bb)
3328 bb_info_t bb_info = bb_table[bb->index];
3330 if (bb->index == EXIT_BLOCK)
3331 return;
3333 if (!bb_info->out)
3335 bb_info->out = BITMAP_ALLOC (&dse_bitmap_obstack);
3336 bitmap_copy (bb_info->out, bb_table[EXIT_BLOCK]->gen);
3340 /* Propagate the information from the in set of the dest of E to the
3341 out set of the src of E. If the various in or out sets are not
3342 there, that means they are all ones. */
3344 static bool
3345 dse_confluence_n (edge e)
3347 bb_info_t src_info = bb_table[e->src->index];
3348 bb_info_t dest_info = bb_table[e->dest->index];
3350 if (dest_info->in)
3352 if (src_info->out)
3353 bitmap_and_into (src_info->out, dest_info->in);
3354 else
3356 src_info->out = BITMAP_ALLOC (&dse_bitmap_obstack);
3357 bitmap_copy (src_info->out, dest_info->in);
3360 return true;
3364 /* Propagate the info from the out to the in set of BB_INDEX's basic
3365 block. There are three cases:
3367 1) The block has no kill set. In this case the kill set is all
3368 ones. It does not matter what the out set of the block is, none of
3369 the info can reach the top. The only thing that reaches the top is
3370 the gen set and we just copy the set.
3372 2) There is a kill set but no out set and bb has successors. In
3373 this case we just return. Eventually an out set will be created and
3374 it is better to wait than to create a set of ones.
3376 3) There is both a kill and out set. We apply the obvious transfer
3377 function.
3380 static bool
3381 dse_transfer_function (int bb_index)
3383 bb_info_t bb_info = bb_table[bb_index];
3385 if (bb_info->kill)
3387 if (bb_info->out)
3389 /* Case 3 above. */
3390 if (bb_info->in)
3391 return bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3392 bb_info->out, bb_info->kill);
3393 else
3395 bb_info->in = BITMAP_ALLOC (&dse_bitmap_obstack);
3396 bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3397 bb_info->out, bb_info->kill);
3398 return true;
3401 else
3402 /* Case 2 above. */
3403 return false;
3405 else
3407 /* Case 1 above. If there is already an in set, nothing
3408 happens. */
3409 if (bb_info->in)
3410 return false;
3411 else
3413 bb_info->in = BITMAP_ALLOC (&dse_bitmap_obstack);
3414 bitmap_copy (bb_info->in, bb_info->gen);
3415 return true;
3420 /* Solve the dataflow equations. */
3422 static void
3423 dse_step4 (void)
3425 df_simple_dataflow (DF_BACKWARD, NULL, dse_confluence_0,
3426 dse_confluence_n, dse_transfer_function,
3427 all_blocks, df_get_postorder (DF_BACKWARD),
3428 df_get_n_blocks (DF_BACKWARD));
3429 if (dump_file && (dump_flags & TDF_DETAILS))
3431 basic_block bb;
3433 fprintf (dump_file, "\n\n*** Global dataflow info after analysis.\n");
3434 FOR_ALL_BB_FN (bb, cfun)
3436 bb_info_t bb_info = bb_table[bb->index];
3438 df_print_bb_index (bb, dump_file);
3439 if (bb_info->in)
3440 bitmap_print (dump_file, bb_info->in, " in: ", "\n");
3441 else
3442 fprintf (dump_file, " in: *MISSING*\n");
3443 if (bb_info->gen)
3444 bitmap_print (dump_file, bb_info->gen, " gen: ", "\n");
3445 else
3446 fprintf (dump_file, " gen: *MISSING*\n");
3447 if (bb_info->kill)
3448 bitmap_print (dump_file, bb_info->kill, " kill: ", "\n");
3449 else
3450 fprintf (dump_file, " kill: *MISSING*\n");
3451 if (bb_info->out)
3452 bitmap_print (dump_file, bb_info->out, " out: ", "\n");
3453 else
3454 fprintf (dump_file, " out: *MISSING*\n\n");
3461 /*----------------------------------------------------------------------------
3462 Fifth step.
3464 Delete the stores that can only be deleted using the global information.
3465 ----------------------------------------------------------------------------*/
3468 static void
3469 dse_step5_nospill (void)
3471 basic_block bb;
3472 FOR_EACH_BB_FN (bb, cfun)
3474 bb_info_t bb_info = bb_table[bb->index];
3475 insn_info_t insn_info = bb_info->last_insn;
3476 bitmap v = bb_info->out;
3478 while (insn_info)
3480 bool deleted = false;
3481 if (dump_file && insn_info->insn)
3483 fprintf (dump_file, "starting to process insn %d\n",
3484 INSN_UID (insn_info->insn));
3485 bitmap_print (dump_file, v, " v: ", "\n");
3488 /* There may have been code deleted by the dce pass run before
3489 this phase. */
3490 if (insn_info->insn
3491 && INSN_P (insn_info->insn)
3492 && (!insn_info->cannot_delete)
3493 && (!bitmap_empty_p (v)))
3495 store_info *store_info = insn_info->store_rec;
3497 /* Try to delete the current insn. */
3498 deleted = true;
3500 /* Skip the clobbers. */
3501 while (!store_info->is_set)
3502 store_info = store_info->next;
3504 if (store_info->alias_set)
3505 deleted = false;
3506 else
3508 HOST_WIDE_INT i;
3509 group_info *group_info
3510 = rtx_group_vec[store_info->group_id];
3512 for (i = store_info->begin; i < store_info->end; i++)
3514 int index = get_bitmap_index (group_info, i);
3516 if (dump_file && (dump_flags & TDF_DETAILS))
3517 fprintf (dump_file, "i = %d, index = %d\n", (int)i, index);
3518 if (index == 0 || !bitmap_bit_p (v, index))
3520 if (dump_file && (dump_flags & TDF_DETAILS))
3521 fprintf (dump_file, "failing at i = %d\n", (int)i);
3522 deleted = false;
3523 break;
3527 if (deleted)
3529 if (dbg_cnt (dse)
3530 && check_for_inc_dec_1 (insn_info))
3532 delete_insn (insn_info->insn);
3533 insn_info->insn = NULL;
3534 globally_deleted++;
3538 /* We do want to process the local info if the insn was
3539 deleted. For instance, if the insn did a wild read, we
3540 no longer need to trash the info. */
3541 if (insn_info->insn
3542 && INSN_P (insn_info->insn)
3543 && (!deleted))
3545 scan_stores_nospill (insn_info->store_rec, v, NULL);
3546 if (insn_info->wild_read)
3548 if (dump_file && (dump_flags & TDF_DETAILS))
3549 fprintf (dump_file, "wild read\n");
3550 bitmap_clear (v);
3552 else if (insn_info->read_rec
3553 || insn_info->non_frame_wild_read)
3555 if (dump_file && !insn_info->non_frame_wild_read)
3556 fprintf (dump_file, "regular read\n");
3557 else if (dump_file && (dump_flags & TDF_DETAILS))
3558 fprintf (dump_file, "non-frame wild read\n");
3559 scan_reads_nospill (insn_info, v, NULL);
3563 insn_info = insn_info->prev_insn;
3570 /*----------------------------------------------------------------------------
3571 Sixth step.
3573 Delete stores made redundant by earlier stores (which store the same
3574 value) that couldn't be eliminated.
3575 ----------------------------------------------------------------------------*/
3577 static void
3578 dse_step6 (void)
3580 basic_block bb;
3582 FOR_ALL_BB_FN (bb, cfun)
3584 bb_info_t bb_info = bb_table[bb->index];
3585 insn_info_t insn_info = bb_info->last_insn;
3587 while (insn_info)
3589 /* There may have been code deleted by the dce pass run before
3590 this phase. */
3591 if (insn_info->insn
3592 && INSN_P (insn_info->insn)
3593 && !insn_info->cannot_delete)
3595 store_info *s_info = insn_info->store_rec;
3597 while (s_info && !s_info->is_set)
3598 s_info = s_info->next;
3599 if (s_info
3600 && s_info->redundant_reason
3601 && s_info->redundant_reason->insn
3602 && INSN_P (s_info->redundant_reason->insn))
3604 rtx_insn *rinsn = s_info->redundant_reason->insn;
3605 if (dump_file && (dump_flags & TDF_DETAILS))
3606 fprintf (dump_file, "Locally deleting insn %d "
3607 "because insn %d stores the "
3608 "same value and couldn't be "
3609 "eliminated\n",
3610 INSN_UID (insn_info->insn),
3611 INSN_UID (rinsn));
3612 delete_dead_store_insn (insn_info);
3615 insn_info = insn_info->prev_insn;
3620 /*----------------------------------------------------------------------------
3621 Seventh step.
3623 Destroy everything left standing.
3624 ----------------------------------------------------------------------------*/
3626 static void
3627 dse_step7 (void)
3629 bitmap_obstack_release (&dse_bitmap_obstack);
3630 obstack_free (&dse_obstack, NULL);
3632 end_alias_analysis ();
3633 free (bb_table);
3634 delete rtx_group_table;
3635 rtx_group_table = NULL;
3636 rtx_group_vec.release ();
3637 BITMAP_FREE (all_blocks);
3638 BITMAP_FREE (scratch);
3640 rtx_store_info_pool.release ();
3641 read_info_type_pool.release ();
3642 insn_info_type_pool.release ();
3643 dse_bb_info_type_pool.release ();
3644 group_info_pool.release ();
3645 deferred_change_pool.release ();
3649 /* -------------------------------------------------------------------------
3651 ------------------------------------------------------------------------- */
3653 /* Callback for running pass_rtl_dse. */
3655 static unsigned int
3656 rest_of_handle_dse (void)
3658 df_set_flags (DF_DEFER_INSN_RESCAN);
3660 /* Need the notes since we must track live hardregs in the forwards
3661 direction. */
3662 df_note_add_problem ();
3663 df_analyze ();
3665 dse_step0 ();
3666 dse_step1 ();
3667 dse_step2_init ();
3668 if (dse_step2_nospill ())
3670 df_set_flags (DF_LR_RUN_DCE);
3671 df_analyze ();
3672 if (dump_file && (dump_flags & TDF_DETAILS))
3673 fprintf (dump_file, "doing global processing\n");
3674 dse_step3 (false);
3675 dse_step4 ();
3676 dse_step5_nospill ();
3679 dse_step6 ();
3680 dse_step7 ();
3682 if (dump_file)
3683 fprintf (dump_file, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n",
3684 locally_deleted, globally_deleted, spill_deleted);
3686 /* DSE can eliminate potentially-trapping MEMs.
3687 Remove any EH edges associated with them. */
3688 if ((locally_deleted || globally_deleted)
3689 && cfun->can_throw_non_call_exceptions
3690 && purge_all_dead_edges ())
3691 cleanup_cfg (0);
3693 return 0;
3696 namespace {
3698 const pass_data pass_data_rtl_dse1 =
3700 RTL_PASS, /* type */
3701 "dse1", /* name */
3702 OPTGROUP_NONE, /* optinfo_flags */
3703 TV_DSE1, /* tv_id */
3704 0, /* properties_required */
3705 0, /* properties_provided */
3706 0, /* properties_destroyed */
3707 0, /* todo_flags_start */
3708 TODO_df_finish, /* todo_flags_finish */
3711 class pass_rtl_dse1 : public rtl_opt_pass
3713 public:
3714 pass_rtl_dse1 (gcc::context *ctxt)
3715 : rtl_opt_pass (pass_data_rtl_dse1, ctxt)
3718 /* opt_pass methods: */
3719 virtual bool gate (function *)
3721 return optimize > 0 && flag_dse && dbg_cnt (dse1);
3724 virtual unsigned int execute (function *) { return rest_of_handle_dse (); }
3726 }; // class pass_rtl_dse1
3728 } // anon namespace
3730 rtl_opt_pass *
3731 make_pass_rtl_dse1 (gcc::context *ctxt)
3733 return new pass_rtl_dse1 (ctxt);
3736 namespace {
3738 const pass_data pass_data_rtl_dse2 =
3740 RTL_PASS, /* type */
3741 "dse2", /* name */
3742 OPTGROUP_NONE, /* optinfo_flags */
3743 TV_DSE2, /* tv_id */
3744 0, /* properties_required */
3745 0, /* properties_provided */
3746 0, /* properties_destroyed */
3747 0, /* todo_flags_start */
3748 TODO_df_finish, /* todo_flags_finish */
3751 class pass_rtl_dse2 : public rtl_opt_pass
3753 public:
3754 pass_rtl_dse2 (gcc::context *ctxt)
3755 : rtl_opt_pass (pass_data_rtl_dse2, ctxt)
3758 /* opt_pass methods: */
3759 virtual bool gate (function *)
3761 return optimize > 0 && flag_dse && dbg_cnt (dse2);
3764 virtual unsigned int execute (function *) { return rest_of_handle_dse (); }
3766 }; // class pass_rtl_dse2
3768 } // anon namespace
3770 rtl_opt_pass *
3771 make_pass_rtl_dse2 (gcc::context *ctxt)
3773 return new pass_rtl_dse2 (ctxt);