1/* RTL dead store elimination.
2 Copyright (C) 2005-2017 Free Software Foundation, Inc.
3
4 Contributed by Richard Sandiford <rsandifor@codesourcery.com>
5 and Kenneth Zadeck <zadeck@naturalbridge.com>
6
7This file is part of GCC.
8
9GCC is free software; you can redistribute it and/or modify it under
10the terms of the GNU General Public License as published by the Free
11Software Foundation; either version 3, or (at your option) any later
12version.
13
14GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15WARRANTY; without even the implied warranty of MERCHANTABILITY or
16FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17for more details.
18
19You should have received a copy of the GNU General Public License
20along with GCC; see the file COPYING3. If not see
21<http://www.gnu.org/licenses/>. */
22
23#undef BASELINE
24
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 "memmodel.h"
36#include "tm_p.h"
37#include "gimple-ssa.h"
38#include "expmed.h"
39#include "optabs.h"
40#include "emit-rtl.h"
41#include "recog.h"
42#include "alias.h"
43#include "stor-layout.h"
44#include "cfgrtl.h"
45#include "cselib.h"
46#include "tree-pass.h"
47#include "explow.h"
48#include "expr.h"
49#include "dbgcnt.h"
50#include "params.h"
51#include "rtl-iter.h"
52#include "cfgcleanup.h"
53
54/* This file contains three techniques for performing Dead Store
55 Elimination (dse).
56
57 * The first technique performs dse locally on any base address. It
58 is based on the cselib which is a local value numbering technique.
59 This technique is local to a basic block but deals with a fairly
60 general addresses.
61
62 * The second technique performs dse globally but is restricted to
63 base addresses that are either constant or are relative to the
64 frame_pointer.
65
66 * The third technique, (which is only done after register allocation)
67 processes the spill slots. This differs from the second
68 technique because it takes advantage of the fact that spilling is
69 completely free from the effects of aliasing.
70
71 Logically, dse is a backwards dataflow problem. A store can be
72 deleted if it if cannot be reached in the backward direction by any
73 use of the value being stored. However, the local technique uses a
74 forwards scan of the basic block because cselib requires that the
75 block be processed in that order.
76
77 The pass is logically broken into 7 steps:
78
79 0) Initialization.
80
81 1) The local algorithm, as well as scanning the insns for the two
82 global algorithms.
83
84 2) Analysis to see if the global algs are necessary. In the case
85 of stores base on a constant address, there must be at least two
86 stores to that address, to make it possible to delete some of the
87 stores. In the case of stores off of the frame or spill related
88 stores, only one store to an address is necessary because those
89 stores die at the end of the function.
90
91 3) Set up the global dataflow equations based on processing the
92 info parsed in the first step.
93
94 4) Solve the dataflow equations.
95
96 5) Delete the insns that the global analysis has indicated are
97 unnecessary.
98
99 6) Delete insns that store the same value as preceding store
100 where the earlier store couldn't be eliminated.
101
102 7) Cleanup.
103
104 This step uses cselib and canon_rtx to build the largest expression
105 possible for each address. This pass is a forwards pass through
106 each basic block. From the point of view of the global technique,
107 the first pass could examine a block in either direction. The
108 forwards ordering is to accommodate cselib.
109
110 We make a simplifying assumption: addresses fall into four broad
111 categories:
112
113 1) base has rtx_varies_p == false, offset is constant.
114 2) base has rtx_varies_p == false, offset variable.
115 3) base has rtx_varies_p == true, offset constant.
116 4) base has rtx_varies_p == true, offset variable.
117
118 The local passes are able to process all 4 kinds of addresses. The
119 global pass only handles 1).
120
121 The global problem is formulated as follows:
122
123 A store, S1, to address A, where A is not relative to the stack
124 frame, can be eliminated if all paths from S1 to the end of the
125 function contain another store to A before a read to A.
126
127 If the address A is relative to the stack frame, a store S2 to A
128 can be eliminated if there are no paths from S2 that reach the
129 end of the function that read A before another store to A. In
130 this case S2 can be deleted if there are paths from S2 to the
131 end of the function that have no reads or writes to A. This
132 second case allows stores to the stack frame to be deleted that
133 would otherwise die when the function returns. This cannot be
134 done if stores_off_frame_dead_at_return is not true. See the doc
135 for that variable for when this variable is false.
136
137 The global problem is formulated as a backwards set union
138 dataflow problem where the stores are the gens and reads are the
139 kills. Set union problems are rare and require some special
140 handling given our representation of bitmaps. A straightforward
141 implementation requires a lot of bitmaps filled with 1s.
142 These are expensive and cumbersome in our bitmap formulation so
143 care has been taken to avoid large vectors filled with 1s. See
144 the comments in bb_info and in the dataflow confluence functions
145 for details.
146
147 There are two places for further enhancements to this algorithm:
148
149 1) The original dse which was embedded in a pass called flow also
150 did local address forwarding. For example in
151
152 A <- r100
153 ... <- A
154
155 flow would replace the right hand side of the second insn with a
156 reference to r100. Most of the information is available to add this
157 to this pass. It has not done it because it is a lot of work in
158 the case that either r100 is assigned to between the first and
159 second insn and/or the second insn is a load of part of the value
160 stored by the first insn.
161
162 insn 5 in gcc.c-torture/compile/990203-1.c simple case.
163 insn 15 in gcc.c-torture/execute/20001017-2.c simple case.
164 insn 25 in gcc.c-torture/execute/20001026-1.c simple case.
165 insn 44 in gcc.c-torture/execute/20010910-1.c simple case.
166
167 2) The cleaning up of spill code is quite profitable. It currently
168 depends on reading tea leaves and chicken entrails left by reload.
169 This pass depends on reload creating a singleton alias set for each
170 spill slot and telling the next dse pass which of these alias sets
171 are the singletons. Rather than analyze the addresses of the
172 spills, dse's spill processing just does analysis of the loads and
173 stores that use those alias sets. There are three cases where this
174 falls short:
175
176 a) Reload sometimes creates the slot for one mode of access, and
177 then inserts loads and/or stores for a smaller mode. In this
178 case, the current code just punts on the slot. The proper thing
179 to do is to back out and use one bit vector position for each
180 byte of the entity associated with the slot. This depends on
181 KNOWING that reload always generates the accesses for each of the
182 bytes in some canonical (read that easy to understand several
183 passes after reload happens) way.
184
185 b) Reload sometimes decides that spill slot it allocated was not
186 large enough for the mode and goes back and allocates more slots
187 with the same mode and alias set. The backout in this case is a
188 little more graceful than (a). In this case the slot is unmarked
189 as being a spill slot and if final address comes out to be based
190 off the frame pointer, the global algorithm handles this slot.
191
192 c) For any pass that may prespill, there is currently no
193 mechanism to tell the dse pass that the slot being used has the
194 special properties that reload uses. It may be that all that is
195 required is to have those passes make the same calls that reload
196 does, assuming that the alias sets can be manipulated in the same
197 way. */
198
199/* There are limits to the size of constant offsets we model for the
200 global problem. There are certainly test cases, that exceed this
201 limit, however, it is unlikely that there are important programs
202 that really have constant offsets this size. */
203#define MAX_OFFSET (64 * 1024)
204
205/* Obstack for the DSE dataflow bitmaps. We don't want to put these
206 on the default obstack because these bitmaps can grow quite large
207 (~2GB for the small (!) test case of PR54146) and we'll hold on to
208 all that memory until the end of the compiler run.
209 As a bonus, delete_tree_live_info can destroy all the bitmaps by just
210 releasing the whole obstack. */
211static bitmap_obstack dse_bitmap_obstack;
212
213/* Obstack for other data. As for above: Kinda nice to be able to
214 throw it all away at the end in one big sweep. */
215static struct obstack dse_obstack;
216
217/* Scratch bitmap for cselib's cselib_expand_value_rtx. */
218static bitmap scratch = NULL;
219
220struct insn_info_type;
221
222/* This structure holds information about a candidate store. */
223struct store_info
224{
225
226 /* False means this is a clobber. */
227 bool is_set;
228
229 /* False if a single HOST_WIDE_INT bitmap is used for positions_needed. */
230 bool is_large;
231
232 /* The id of the mem group of the base address. If rtx_varies_p is
233 true, this is -1. Otherwise, it is the index into the group
234 table. */
235 int group_id;
236
237 /* This is the cselib value. */
238 cselib_val *cse_base;
239
240 /* This canonized mem. */
241 rtx mem;
242
243 /* Canonized MEM address for use by canon_true_dependence. */
244 rtx mem_addr;
245
246 /* The offset of the first and byte before the last byte associated
247 with the operation. */
248 HOST_WIDE_INT begin, end;
249
250 union
251 {
252 /* A bitmask as wide as the number of bytes in the word that
253 contains a 1 if the byte may be needed. The store is unused if
254 all of the bits are 0. This is used if IS_LARGE is false. */
255 unsigned HOST_WIDE_INT small_bitmask;
256
257 struct
258 {
259 /* A bitmap with one bit per byte. Cleared bit means the position
260 is needed. Used if IS_LARGE is false. */
261 bitmap bmap;
262
263 /* Number of set bits (i.e. unneeded bytes) in BITMAP. If it is
264 equal to END - BEGIN, the whole store is unused. */
265 int count;
266 } large;
267 } positions_needed;
268
269 /* The next store info for this insn. */
270 struct store_info *next;
271
272 /* The right hand side of the store. This is used if there is a
273 subsequent reload of the mems address somewhere later in the
274 basic block. */
275 rtx rhs;
276
277 /* If rhs is or holds a constant, this contains that constant,
278 otherwise NULL. */
279 rtx const_rhs;
280
281 /* Set if this store stores the same constant value as REDUNDANT_REASON
282 insn stored. These aren't eliminated early, because doing that
283 might prevent the earlier larger store to be eliminated. */
284 struct insn_info_type *redundant_reason;
285};
286
287/* Return a bitmask with the first N low bits set. */
288
289static unsigned HOST_WIDE_INT
290lowpart_bitmask (int n)
291{
292 unsigned HOST_WIDE_INT mask = HOST_WIDE_INT_M1U;
293 return mask >> (HOST_BITS_PER_WIDE_INT - n);
294}
295
296static object_allocator<store_info> cse_store_info_pool ("cse_store_info_pool");
297
298static object_allocator<store_info> rtx_store_info_pool ("rtx_store_info_pool");
299
300/* This structure holds information about a load. These are only
301 built for rtx bases. */
302struct read_info_type
303{
304 /* The id of the mem group of the base address. */
305 int group_id;
306
307 /* The offset of the first and byte after the last byte associated
308 with the operation. If begin == end == 0, the read did not have
309 a constant offset. */
310 int begin, end;
311
312 /* The mem being read. */
313 rtx mem;
314
315 /* The next read_info for this insn. */
316 struct read_info_type *next;
317};
318typedef struct read_info_type *read_info_t;
319
320static object_allocator<read_info_type> read_info_type_pool ("read_info_pool");
321
322/* One of these records is created for each insn. */
323
324struct insn_info_type
325{
326 /* Set true if the insn contains a store but the insn itself cannot
327 be deleted. This is set if the insn is a parallel and there is
328 more than one non dead output or if the insn is in some way
329 volatile. */
330 bool cannot_delete;
331
332 /* This field is only used by the global algorithm. It is set true
333 if the insn contains any read of mem except for a (1). This is
334 also set if the insn is a call or has a clobber mem. If the insn
335 contains a wild read, the use_rec will be null. */
336 bool wild_read;
337
338 /* This is true only for CALL instructions which could potentially read
339 any non-frame memory location. This field is used by the global
340 algorithm. */
341 bool non_frame_wild_read;
342
343 /* This field is only used for the processing of const functions.
344 These functions cannot read memory, but they can read the stack
345 because that is where they may get their parms. We need to be
346 this conservative because, like the store motion pass, we don't
347 consider CALL_INSN_FUNCTION_USAGE when processing call insns.
348 Moreover, we need to distinguish two cases:
349 1. Before reload (register elimination), the stores related to
350 outgoing arguments are stack pointer based and thus deemed
351 of non-constant base in this pass. This requires special
352 handling but also means that the frame pointer based stores
353 need not be killed upon encountering a const function call.
354 2. After reload, the stores related to outgoing arguments can be
355 either stack pointer or hard frame pointer based. This means
356 that we have no other choice than also killing all the frame
357 pointer based stores upon encountering a const function call.
358 This field is set after reload for const function calls and before
359 reload for const tail function calls on targets where arg pointer
360 is the frame pointer. Having this set is less severe than a wild
361 read, it just means that all the frame related stores are killed
362 rather than all the stores. */
363 bool frame_read;
364
365 /* This field is only used for the processing of const functions.
366 It is set if the insn may contain a stack pointer based store. */
367 bool stack_pointer_based;
368
369 /* This is true if any of the sets within the store contains a
370 cselib base. Such stores can only be deleted by the local
371 algorithm. */
372 bool contains_cselib_groups;
373
374 /* The insn. */
375 rtx_insn *insn;
376
377 /* The list of mem sets or mem clobbers that are contained in this
378 insn. If the insn is deletable, it contains only one mem set.
379 But it could also contain clobbers. Insns that contain more than
380 one mem set are not deletable, but each of those mems are here in
381 order to provide info to delete other insns. */
382 store_info *store_rec;
383
384 /* The linked list of mem uses in this insn. Only the reads from
385 rtx bases are listed here. The reads to cselib bases are
386 completely processed during the first scan and so are never
387 created. */
388 read_info_t read_rec;
389
390 /* The live fixed registers. We assume only fixed registers can
391 cause trouble by being clobbered from an expanded pattern;
392 storing only the live fixed registers (rather than all registers)
393 means less memory needs to be allocated / copied for the individual
394 stores. */
395 regset fixed_regs_live;
396
397 /* The prev insn in the basic block. */
398 struct insn_info_type * prev_insn;
399
400 /* The linked list of insns that are in consideration for removal in
401 the forwards pass through the basic block. This pointer may be
402 trash as it is not cleared when a wild read occurs. The only
403 time it is guaranteed to be correct is when the traversal starts
404 at active_local_stores. */
405 struct insn_info_type * next_local_store;
406};
407typedef struct insn_info_type *insn_info_t;
408
409static object_allocator<insn_info_type> insn_info_type_pool ("insn_info_pool");
410
411/* The linked list of stores that are under consideration in this
412 basic block. */
413static insn_info_t active_local_stores;
414static int active_local_stores_len;
415
416struct dse_bb_info_type
417{
418 /* Pointer to the insn info for the last insn in the block. These
419 are linked so this is how all of the insns are reached. During
420 scanning this is the current insn being scanned. */
421 insn_info_t last_insn;
422
423 /* The info for the global dataflow problem. */
424
425
426 /* This is set if the transfer function should and in the wild_read
427 bitmap before applying the kill and gen sets. That vector knocks
428 out most of the bits in the bitmap and thus speeds up the
429 operations. */
430 bool apply_wild_read;
431
432 /* The following 4 bitvectors hold information about which positions
433 of which stores are live or dead. They are indexed by
434 get_bitmap_index. */
435
436 /* The set of store positions that exist in this block before a wild read. */
437 bitmap gen;
438
439 /* The set of load positions that exist in this block above the
440 same position of a store. */
441 bitmap kill;
442
443 /* The set of stores that reach the top of the block without being
444 killed by a read.
445
446 Do not represent the in if it is all ones. Note that this is
447 what the bitvector should logically be initialized to for a set
448 intersection problem. However, like the kill set, this is too
449 expensive. So initially, the in set will only be created for the
450 exit block and any block that contains a wild read. */
451 bitmap in;
452
453 /* The set of stores that reach the bottom of the block from it's
454 successors.
455
456 Do not represent the in if it is all ones. Note that this is
457 what the bitvector should logically be initialized to for a set
458 intersection problem. However, like the kill and in set, this is
459 too expensive. So what is done is that the confluence operator
460 just initializes the vector from one of the out sets of the
461 successors of the block. */
462 bitmap out;
463
464 /* The following bitvector is indexed by the reg number. It
465 contains the set of regs that are live at the current instruction
466 being processed. While it contains info for all of the
467 registers, only the hard registers are actually examined. It is used
468 to assure that shift and/or add sequences that are inserted do not
469 accidentally clobber live hard regs. */
470 bitmap regs_live;
471};
472
473typedef struct dse_bb_info_type *bb_info_t;
474
475static object_allocator<dse_bb_info_type> dse_bb_info_type_pool
476 ("bb_info_pool");
477
478/* Table to hold all bb_infos. */
479static bb_info_t *bb_table;
480
481/* There is a group_info for each rtx base that is used to reference
482 memory. There are also not many of the rtx bases because they are
483 very limited in scope. */
484
485struct group_info
486{
487 /* The actual base of the address. */
488 rtx rtx_base;
489
490 /* The sequential id of the base. This allows us to have a
491 canonical ordering of these that is not based on addresses. */
492 int id;
493
494 /* True if there are any positions that are to be processed
495 globally. */
496 bool process_globally;
497
498 /* True if the base of this group is either the frame_pointer or
499 hard_frame_pointer. */
500 bool frame_related;
501
502 /* A mem wrapped around the base pointer for the group in order to do
503 read dependency. It must be given BLKmode in order to encompass all
504 the possible offsets from the base. */
505 rtx base_mem;
506
507 /* Canonized version of base_mem's address. */
508 rtx canon_base_addr;
509
510 /* These two sets of two bitmaps are used to keep track of how many
511 stores are actually referencing that position from this base. We
512 only do this for rtx bases as this will be used to assign
513 positions in the bitmaps for the global problem. Bit N is set in
514 store1 on the first store for offset N. Bit N is set in store2
515 for the second store to offset N. This is all we need since we
516 only care about offsets that have two or more stores for them.
517
518 The "_n" suffix is for offsets less than 0 and the "_p" suffix is
519 for 0 and greater offsets.
520
521 There is one special case here, for stores into the stack frame,
522 we will or store1 into store2 before deciding which stores look
523 at globally. This is because stores to the stack frame that have
524 no other reads before the end of the function can also be
525 deleted. */
526 bitmap store1_n, store1_p, store2_n, store2_p;
527
528 /* These bitmaps keep track of offsets in this group escape this function.
529 An offset escapes if it corresponds to a named variable whose
530 addressable flag is set. */
531 bitmap escaped_n, escaped_p;
532
533 /* The positions in this bitmap have the same assignments as the in,
534 out, gen and kill bitmaps. This bitmap is all zeros except for
535 the positions that are occupied by stores for this group. */
536 bitmap group_kill;
537
538 /* The offset_map is used to map the offsets from this base into
539 positions in the global bitmaps. It is only created after all of
540 the all of stores have been scanned and we know which ones we
541 care about. */
542 int *offset_map_n, *offset_map_p;
543 int offset_map_size_n, offset_map_size_p;
544};
545
546static object_allocator<group_info> group_info_pool ("rtx_group_info_pool");
547
548/* Index into the rtx_group_vec. */
549static int rtx_group_next_id;
550
551
552static vec<group_info *> rtx_group_vec;
553
554
555/* This structure holds the set of changes that are being deferred
556 when removing read operation. See replace_read. */
557struct deferred_change
558{
559
560 /* The mem that is being replaced. */
561 rtx *loc;
562
563 /* The reg it is being replaced with. */
564 rtx reg;
565
566 struct deferred_change *next;
567};
568
569static object_allocator<deferred_change> deferred_change_pool
570 ("deferred_change_pool");
571
572static deferred_change *deferred_change_list = NULL;
573
574/* This is true except if cfun->stdarg -- i.e. we cannot do
575 this for vararg functions because they play games with the frame. */
576static bool stores_off_frame_dead_at_return;
577
578/* Counter for stats. */
579static int globally_deleted;
580static int locally_deleted;
581
582static bitmap all_blocks;
583
584/* Locations that are killed by calls in the global phase. */
585static bitmap kill_on_calls;
586
587/* The number of bits used in the global bitmaps. */
588static unsigned int current_position;
589
590/*----------------------------------------------------------------------------
591 Zeroth step.
592
593 Initialization.
594----------------------------------------------------------------------------*/
595
596
597/* Hashtable callbacks for maintaining the "bases" field of
598 store_group_info, given that the addresses are function invariants. */
599
600struct invariant_group_base_hasher : nofree_ptr_hash <group_info>
601{
602 static inline hashval_t hash (const group_info *);
603 static inline bool equal (const group_info *, const group_info *);
604};
605
606inline bool
607invariant_group_base_hasher::equal (const group_info *gi1,
608 const group_info *gi2)
609{
610 return rtx_equal_p (gi1->rtx_base, gi2->rtx_base);
611}
612
613inline hashval_t
614invariant_group_base_hasher::hash (const group_info *gi)
615{
616 int do_not_record;
617 return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false);
618}
619
620/* Tables of group_info structures, hashed by base value. */
621static hash_table<invariant_group_base_hasher> *rtx_group_table;
622
623
624/* Get the GROUP for BASE. Add a new group if it is not there. */
625
626static group_info *
627get_group_info (rtx base)
628{
629 struct group_info tmp_gi;
630 group_info *gi;
631 group_info **slot;
632
633 gcc_assert (base != NULL_RTX);
634
635 /* Find the store_base_info structure for BASE, creating a new one
636 if necessary. */
637 tmp_gi.rtx_base = base;
638 slot = rtx_group_table->find_slot (&tmp_gi, INSERT);
639 gi = *slot;
640
641 if (gi == NULL)
642 {
643 *slot = gi = group_info_pool.allocate ();
644 gi->rtx_base = base;
645 gi->id = rtx_group_next_id++;
646 gi->base_mem = gen_rtx_MEM (BLKmode, base);
647 gi->canon_base_addr = canon_rtx (base);
648 gi->store1_n = BITMAP_ALLOC (&dse_bitmap_obstack);
649 gi->store1_p = BITMAP_ALLOC (&dse_bitmap_obstack);
650 gi->store2_n = BITMAP_ALLOC (&dse_bitmap_obstack);
651 gi->store2_p = BITMAP_ALLOC (&dse_bitmap_obstack);
652 gi->escaped_p = BITMAP_ALLOC (&dse_bitmap_obstack);
653 gi->escaped_n = BITMAP_ALLOC (&dse_bitmap_obstack);
654 gi->group_kill = BITMAP_ALLOC (&dse_bitmap_obstack);
655 gi->process_globally = false;
656 gi->frame_related =
657 (base == frame_pointer_rtx) || (base == hard_frame_pointer_rtx);
658 gi->offset_map_size_n = 0;
659 gi->offset_map_size_p = 0;
660 gi->offset_map_n = NULL;
661 gi->offset_map_p = NULL;
662 rtx_group_vec.safe_push (gi);
663 }
664
665 return gi;
666}
667
668
669/* Initialization of data structures. */
670
671static void
672dse_step0 (void)
673{
674 locally_deleted = 0;
675 globally_deleted = 0;
676
677 bitmap_obstack_initialize (&dse_bitmap_obstack);
678 gcc_obstack_init (&dse_obstack);
679
680 scratch = BITMAP_ALLOC (&reg_obstack);
681 kill_on_calls = BITMAP_ALLOC (&dse_bitmap_obstack);
682
683
684 rtx_group_table = new hash_table<invariant_group_base_hasher> (11);
685
686 bb_table = XNEWVEC (bb_info_t, last_basic_block_for_fn (cfun));
687 rtx_group_next_id = 0;
688
689 stores_off_frame_dead_at_return = !cfun->stdarg;
690
691 init_alias_analysis ();
692}
693
694
695
696/*----------------------------------------------------------------------------
697 First step.
698
699 Scan all of the insns. Any random ordering of the blocks is fine.
700 Each block is scanned in forward order to accommodate cselib which
701 is used to remove stores with non-constant bases.
702----------------------------------------------------------------------------*/
703
704/* Delete all of the store_info recs from INSN_INFO. */
705
706static void
707free_store_info (insn_info_t insn_info)
708{
709 store_info *cur = insn_info->store_rec;
710 while (cur)
711 {
712 store_info *next = cur->next;
713 if (cur->is_large)
714 BITMAP_FREE (cur->positions_needed.large.bmap);
715 if (cur->cse_base)
716 cse_store_info_pool.remove (cur);
717 else
718 rtx_store_info_pool.remove (cur);
719 cur = next;
720 }
721
722 insn_info->cannot_delete = true;
723 insn_info->contains_cselib_groups = false;
724 insn_info->store_rec = NULL;
725}
726
727struct note_add_store_info
728{
729 rtx_insn *first, *current;
730 regset fixed_regs_live;
731 bool failure;
732};
733
734/* Callback for emit_inc_dec_insn_before via note_stores.
735 Check if a register is clobbered which is live afterwards. */
736
737static void
738note_add_store (rtx loc, const_rtx expr ATTRIBUTE_UNUSED, void *data)
739{
740 rtx_insn *insn;
741 note_add_store_info *info = (note_add_store_info *) data;
742
743 if (!REG_P (loc))
744 return;
745
746 /* If this register is referenced by the current or an earlier insn,
747 that's OK. E.g. this applies to the register that is being incremented
748 with this addition. */
749 for (insn = info->first;
750 insn != NEXT_INSN (info->current);
751 insn = NEXT_INSN (insn))
752 if (reg_referenced_p (loc, PATTERN (insn)))
753 return;
754
755 /* If we come here, we have a clobber of a register that's only OK
756 if that register is not live. If we don't have liveness information
757 available, fail now. */
758 if (!info->fixed_regs_live)
759 {
760 info->failure = true;
761 return;
762 }
763 /* Now check if this is a live fixed register. */
764 unsigned int end_regno = END_REGNO (loc);
765 for (unsigned int regno = REGNO (loc); regno < end_regno; ++regno)
766 if (REGNO_REG_SET_P (info->fixed_regs_live, regno))
767 info->failure = true;
768}
769
770/* Callback for for_each_inc_dec that emits an INSN that sets DEST to
771 SRC + SRCOFF before insn ARG. */
772
773static int
774emit_inc_dec_insn_before (rtx mem ATTRIBUTE_UNUSED,
775 rtx op ATTRIBUTE_UNUSED,
776 rtx dest, rtx src, rtx srcoff, void *arg)
777{
778 insn_info_t insn_info = (insn_info_t) arg;
779 rtx_insn *insn = insn_info->insn, *new_insn, *cur;
780 note_add_store_info info;
781
782 /* We can reuse all operands without copying, because we are about
783 to delete the insn that contained it. */
784 if (srcoff)
785 {
786 start_sequence ();
787 emit_insn (gen_add3_insn (dest, src, srcoff));
788 new_insn = get_insns ();
789 end_sequence ();
790 }
791 else
792 new_insn = gen_move_insn (dest, src);
793 info.first = new_insn;
794 info.fixed_regs_live = insn_info->fixed_regs_live;
795 info.failure = false;
796 for (cur = new_insn; cur; cur = NEXT_INSN (cur))
797 {
798 info.current = cur;
799 note_stores (PATTERN (cur), note_add_store, &info);
800 }
801
802 /* If a failure was flagged above, return 1 so that for_each_inc_dec will
803 return it immediately, communicating the failure to its caller. */
804 if (info.failure)
805 return 1;
806
807 emit_insn_before (new_insn, insn);
808
809 return 0;
810}
811
812/* Before we delete INSN_INFO->INSN, make sure that the auto inc/dec, if it
813 is there, is split into a separate insn.
814 Return true on success (or if there was nothing to do), false on failure. */
815
816static bool
817check_for_inc_dec_1 (insn_info_t insn_info)
818{
819 rtx_insn *insn = insn_info->insn;
820 rtx note = find_reg_note (insn, REG_INC, NULL_RTX);
821 if (note)
822 return for_each_inc_dec (PATTERN (insn), emit_inc_dec_insn_before,
823 insn_info) == 0;
824 return true;
825}
826
827
828/* Entry point for postreload. If you work on reload_cse, or you need this
829 anywhere else, consider if you can provide register liveness information
830 and add a parameter to this function so that it can be passed down in
831 insn_info.fixed_regs_live. */
832bool
833check_for_inc_dec (rtx_insn *insn)
834{
835 insn_info_type insn_info;
836 rtx note;
837
838 insn_info.insn = insn;
839 insn_info.fixed_regs_live = NULL;
840 note = find_reg_note (insn, REG_INC, NULL_RTX);
841 if (note)
842 return for_each_inc_dec (PATTERN (insn), emit_inc_dec_insn_before,
843 &insn_info) == 0;
844 return true;
845}
846
847/* Delete the insn and free all of the fields inside INSN_INFO. */
848
849static void
850delete_dead_store_insn (insn_info_t insn_info)
851{
852 read_info_t read_info;
853
854 if (!dbg_cnt (dse))
855 return;
856
857 if (!check_for_inc_dec_1 (insn_info))
858 return;
859 if (dump_file && (dump_flags & TDF_DETAILS))
860 fprintf (dump_file, "Locally deleting insn %d\n",
861 INSN_UID (insn_info->insn));
862
863 free_store_info (insn_info);
864 read_info = insn_info->read_rec;
865
866 while (read_info)
867 {
868 read_info_t next = read_info->next;
869 read_info_type_pool.remove (read_info);
870 read_info = next;
871 }
872 insn_info->read_rec = NULL;
873
874 delete_insn (insn_info->insn);
875 locally_deleted++;
876 insn_info->insn = NULL;
877
878 insn_info->wild_read = false;
879}
880
881/* Return whether DECL, a local variable, can possibly escape the current
882 function scope. */
883
884static bool
885local_variable_can_escape (tree decl)
886{
887 if (TREE_ADDRESSABLE (decl))
888 return true;
889
890 /* If this is a partitioned variable, we need to consider all the variables
891 in the partition. This is necessary because a store into one of them can
892 be replaced with a store into another and this may not change the outcome
893 of the escape analysis. */
894 if (cfun->gimple_df->decls_to_pointers != NULL)
895 {
896 tree *namep = cfun->gimple_df->decls_to_pointers->get (decl);
897 if (namep)
898 return TREE_ADDRESSABLE (*namep);
899 }
900
901 return false;
902}
903
904/* Return whether EXPR can possibly escape the current function scope. */
905
906static bool
907can_escape (tree expr)
908{
909 tree base;
910 if (!expr)
911 return true;
912 base = get_base_address (expr);
913 if (DECL_P (base)
914 && !may_be_aliased (base)
915 && !(VAR_P (base)
916 && !DECL_EXTERNAL (base)
917 && !TREE_STATIC (base)
918 && local_variable_can_escape (base)))
919 return false;
920 return true;
921}
922
923/* Set the store* bitmaps offset_map_size* fields in GROUP based on
924 OFFSET and WIDTH. */
925
926static void
927set_usage_bits (group_info *group, HOST_WIDE_INT offset, HOST_WIDE_INT width,
928 tree expr)
929{
930 HOST_WIDE_INT i;
931 bool expr_escapes = can_escape (expr);
932 if (offset > -MAX_OFFSET && offset + width < MAX_OFFSET)
933 for (i=offset; i<offset+width; i++)
934 {
935 bitmap store1;
936 bitmap store2;
937 bitmap escaped;
938 int ai;
939 if (i < 0)
940 {
941 store1 = group->store1_n;
942 store2 = group->store2_n;
943 escaped = group->escaped_n;
944 ai = -i;
945 }
946 else
947 {
948 store1 = group->store1_p;
949 store2 = group->store2_p;
950 escaped = group->escaped_p;
951 ai = i;
952 }
953
954 if (!bitmap_set_bit (store1, ai))
955 bitmap_set_bit (store2, ai);
956 else
957 {
958 if (i < 0)
959 {
960 if (group->offset_map_size_n < ai)
961 group->offset_map_size_n = ai;
962 }
963 else
964 {
965 if (group->offset_map_size_p < ai)
966 group->offset_map_size_p = ai;
967 }
968 }
969 if (expr_escapes)
970 bitmap_set_bit (escaped, ai);
971 }
972}
973
974static void
975reset_active_stores (void)
976{
977 active_local_stores = NULL;
978 active_local_stores_len = 0;
979}
980
981/* Free all READ_REC of the LAST_INSN of BB_INFO. */
982
983static void
984free_read_records (bb_info_t bb_info)
985{
986 insn_info_t insn_info = bb_info->last_insn;
987 read_info_t *ptr = &insn_info->read_rec;
988 while (*ptr)
989 {
990 read_info_t next = (*ptr)->next;
991 read_info_type_pool.remove (*ptr);
992 *ptr = next;
993 }
994}
995
996/* Set the BB_INFO so that the last insn is marked as a wild read. */
997
998static void
999add_wild_read (bb_info_t bb_info)
1000{
1001 insn_info_t insn_info = bb_info->last_insn;
1002 insn_info->wild_read = true;
1003 free_read_records (bb_info);
1004 reset_active_stores ();
1005}
1006
1007/* Set the BB_INFO so that the last insn is marked as a wild read of
1008 non-frame locations. */
1009
1010static void
1011add_non_frame_wild_read (bb_info_t bb_info)
1012{
1013 insn_info_t insn_info = bb_info->last_insn;
1014 insn_info->non_frame_wild_read = true;
1015 free_read_records (bb_info);
1016 reset_active_stores ();
1017}
1018
1019/* Return true if X is a constant or one of the registers that behave
1020 as a constant over the life of a function. This is equivalent to
1021 !rtx_varies_p for memory addresses. */
1022
1023static bool
1024const_or_frame_p (rtx x)
1025{
1026 if (CONSTANT_P (x))
1027 return true;
1028
1029 if (GET_CODE (x) == REG)
1030 {
1031 /* Note that we have to test for the actual rtx used for the frame
1032 and arg pointers and not just the register number in case we have
1033 eliminated the frame and/or arg pointer and are using it
1034 for pseudos. */
1035 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
1036 /* The arg pointer varies if it is not a fixed register. */
1037 || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])
1038 || x == pic_offset_table_rtx)
1039 return true;
1040 return false;
1041 }
1042
1043 return false;
1044}
1045
1046/* Take all reasonable action to put the address of MEM into the form
1047 that we can do analysis on.
1048
1049 The gold standard is to get the address into the form: address +
1050 OFFSET where address is something that rtx_varies_p considers a
1051 constant. When we can get the address in this form, we can do
1052 global analysis on it. Note that for constant bases, address is
1053 not actually returned, only the group_id. The address can be
1054 obtained from that.
1055
1056 If that fails, we try cselib to get a value we can at least use
1057 locally. If that fails we return false.
1058
1059 The GROUP_ID is set to -1 for cselib bases and the index of the
1060 group for non_varying bases.
1061
1062 FOR_READ is true if this is a mem read and false if not. */
1063
1064static bool
1065canon_address (rtx mem,
1066 int *group_id,
1067 HOST_WIDE_INT *offset,
1068 cselib_val **base)
1069{
1070 machine_mode address_mode = get_address_mode (mem);
1071 rtx mem_address = XEXP (mem, 0);
1072 rtx expanded_address, address;
1073 int expanded;
1074
1075 cselib_lookup (mem_address, address_mode, 1, GET_MODE (mem));
1076
1077 if (dump_file && (dump_flags & TDF_DETAILS))
1078 {
1079 fprintf (dump_file, " mem: ");
1080 print_inline_rtx (dump_file, mem_address, 0);
1081 fprintf (dump_file, "\n");
1082 }
1083
1084 /* First see if just canon_rtx (mem_address) is const or frame,
1085 if not, try cselib_expand_value_rtx and call canon_rtx on that. */
1086 address = NULL_RTX;
1087 for (expanded = 0; expanded < 2; expanded++)
1088 {
1089 if (expanded)
1090 {
1091 /* Use cselib to replace all of the reg references with the full
1092 expression. This will take care of the case where we have
1093
1094 r_x = base + offset;
1095 val = *r_x;
1096
1097 by making it into
1098
1099 val = *(base + offset); */
1100
1101 expanded_address = cselib_expand_value_rtx (mem_address,
1102 scratch, 5);
1103
1104 /* If this fails, just go with the address from first
1105 iteration. */
1106 if (!expanded_address)
1107 break;
1108 }
1109 else
1110 expanded_address = mem_address;
1111
1112 /* Split the address into canonical BASE + OFFSET terms. */
1113 address = canon_rtx (expanded_address);
1114
1115 *offset = 0;
1116
1117 if (dump_file && (dump_flags & TDF_DETAILS))
1118 {
1119 if (expanded)
1120 {
1121 fprintf (dump_file, "\n after cselib_expand address: ");
1122 print_inline_rtx (dump_file, expanded_address, 0);
1123 fprintf (dump_file, "\n");
1124 }
1125
1126 fprintf (dump_file, "\n after canon_rtx address: ");
1127 print_inline_rtx (dump_file, address, 0);
1128 fprintf (dump_file, "\n");
1129 }
1130
1131 if (GET_CODE (address) == CONST)
1132 address = XEXP (address, 0);
1133
1134 if (GET_CODE (address) == PLUS
1135 && CONST_INT_P (XEXP (address, 1)))
1136 {
1137 *offset = INTVAL (XEXP (address, 1));
1138 address = XEXP (address, 0);
1139 }
1140
1141 if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem))
1142 && const_or_frame_p (address))
1143 {
1144 group_info *group = get_group_info (address);
1145
1146 if (dump_file && (dump_flags & TDF_DETAILS))
1147 fprintf (dump_file, " gid=%d offset=%d \n",
1148 group->id, (int)*offset);
1149 *base = NULL;
1150 *group_id = group->id;
1151 return true;
1152 }
1153 }
1154
1155 *base = cselib_lookup (address, address_mode, true, GET_MODE (mem));
1156 *group_id = -1;
1157
1158 if (*base == NULL)
1159 {
1160 if (dump_file && (dump_flags & TDF_DETAILS))
1161 fprintf (dump_file, " no cselib val - should be a wild read.\n");
1162 return false;
1163 }
1164 if (dump_file && (dump_flags & TDF_DETAILS))
1165 fprintf (dump_file, " varying cselib base=%u:%u offset = %d\n",
1166 (*base)->uid, (*base)->hash, (int)*offset);
1167 return true;
1168}
1169
1170
1171/* Clear the rhs field from the active_local_stores array. */
1172
1173static void
1174clear_rhs_from_active_local_stores (void)
1175{
1176 insn_info_t ptr = active_local_stores;
1177
1178 while (ptr)
1179 {
1180 store_info *store_info = ptr->store_rec;
1181 /* Skip the clobbers. */
1182 while (!store_info->is_set)
1183 store_info = store_info->next;
1184
1185 store_info->rhs = NULL;
1186 store_info->const_rhs = NULL;
1187
1188 ptr = ptr->next_local_store;
1189 }
1190}
1191
1192
1193/* Mark byte POS bytes from the beginning of store S_INFO as unneeded. */
1194
1195static inline void
1196set_position_unneeded (store_info *s_info, int pos)
1197{
1198 if (__builtin_expect (s_info->is_large, false))
1199 {
1200 if (bitmap_set_bit (s_info->positions_needed.large.bmap, pos))
1201 s_info->positions_needed.large.count++;
1202 }
1203 else
1204 s_info->positions_needed.small_bitmask
1205 &= ~(HOST_WIDE_INT_1U << pos);
1206}
1207
1208/* Mark the whole store S_INFO as unneeded. */
1209
1210static inline void
1211set_all_positions_unneeded (store_info *s_info)
1212{
1213 if (__builtin_expect (s_info->is_large, false))
1214 {
1215 int pos, end = s_info->end - s_info->begin;
1216 for (pos = 0; pos < end; pos++)
1217 bitmap_set_bit (s_info->positions_needed.large.bmap, pos);
1218 s_info->positions_needed.large.count = end;
1219 }
1220 else
1221 s_info->positions_needed.small_bitmask = HOST_WIDE_INT_0U;
1222}
1223
1224/* Return TRUE if any bytes from S_INFO store are needed. */
1225
1226static inline bool
1227any_positions_needed_p (store_info *s_info)
1228{
1229 if (__builtin_expect (s_info->is_large, false))
1230 return (s_info->positions_needed.large.count
1231 < s_info->end - s_info->begin);
1232 else
1233 return (s_info->positions_needed.small_bitmask != HOST_WIDE_INT_0U);
1234}
1235
1236/* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO
1237 store are needed. */
1238
1239static inline bool
1240all_positions_needed_p (store_info *s_info, int start, int width)
1241{
1242 if (__builtin_expect (s_info->is_large, false))
1243 {
1244 int end = start + width;
1245 while (start < end)
1246 if (bitmap_bit_p (s_info->positions_needed.large.bmap, start++))
1247 return false;
1248 return true;
1249 }
1250 else
1251 {
1252 unsigned HOST_WIDE_INT mask = lowpart_bitmask (width) << start;
1253 return (s_info->positions_needed.small_bitmask & mask) == mask;
1254 }
1255}
1256
1257
1258static rtx get_stored_val (store_info *, machine_mode, HOST_WIDE_INT,
1259 HOST_WIDE_INT, basic_block, bool);
1260
1261
1262/* BODY is an instruction pattern that belongs to INSN. Return 1 if
1263 there is a candidate store, after adding it to the appropriate
1264 local store group if so. */
1265
1266static int
1267record_store (rtx body, bb_info_t bb_info)
1268{
1269 rtx mem, rhs, const_rhs, mem_addr;
1270 HOST_WIDE_INT offset = 0;
1271 HOST_WIDE_INT width = 0;
1272 insn_info_t insn_info = bb_info->last_insn;
1273 store_info *store_info = NULL;
1274 int group_id;
1275 cselib_val *base = NULL;
1276 insn_info_t ptr, last, redundant_reason;
1277 bool store_is_unused;
1278
1279 if (GET_CODE (body) != SET && GET_CODE (body) != CLOBBER)
1280 return 0;
1281
1282 mem = SET_DEST (body);
1283
1284 /* If this is not used, then this cannot be used to keep the insn
1285 from being deleted. On the other hand, it does provide something
1286 that can be used to prove that another store is dead. */
1287 store_is_unused
1288 = (find_reg_note (insn_info->insn, REG_UNUSED, mem) != NULL);
1289
1290 /* Check whether that value is a suitable memory location. */
1291 if (!MEM_P (mem))
1292 {
1293 /* If the set or clobber is unused, then it does not effect our
1294 ability to get rid of the entire insn. */
1295 if (!store_is_unused)
1296 insn_info->cannot_delete = true;
1297 return 0;
1298 }
1299
1300 /* At this point we know mem is a mem. */
1301 if (GET_MODE (mem) == BLKmode)
1302 {
1303 if (GET_CODE (XEXP (mem, 0)) == SCRATCH)
1304 {
1305 if (dump_file && (dump_flags & TDF_DETAILS))
1306 fprintf (dump_file, " adding wild read for (clobber (mem:BLK (scratch))\n");
1307 add_wild_read (bb_info);
1308 insn_info->cannot_delete = true;
1309 return 0;
1310 }
1311 /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0))
1312 as memset (addr, 0, 36); */
1313 else if (!MEM_SIZE_KNOWN_P (mem)
1314 || MEM_SIZE (mem) <= 0
1315 || MEM_SIZE (mem) > MAX_OFFSET
1316 || GET_CODE (body) != SET
1317 || !CONST_INT_P (SET_SRC (body)))
1318 {
1319 if (!store_is_unused)
1320 {
1321 /* If the set or clobber is unused, then it does not effect our
1322 ability to get rid of the entire insn. */
1323 insn_info->cannot_delete = true;
1324 clear_rhs_from_active_local_stores ();
1325 }
1326 return 0;
1327 }
1328 }
1329
1330 /* We can still process a volatile mem, we just cannot delete it. */
1331 if (MEM_VOLATILE_P (mem))
1332 insn_info->cannot_delete = true;
1333
1334 if (!canon_address (mem, &group_id, &offset, &base))
1335 {
1336 clear_rhs_from_active_local_stores ();
1337 return 0;
1338 }
1339
1340 if (GET_MODE (mem) == BLKmode)
1341 width = MEM_SIZE (mem);
1342 else
1343 width = GET_MODE_SIZE (GET_MODE (mem));
1344
1345 if (offset > HOST_WIDE_INT_MAX - width)
1346 {
1347 clear_rhs_from_active_local_stores ();
1348 return 0;
1349 }
1350
1351 if (group_id >= 0)
1352 {
1353 /* In the restrictive case where the base is a constant or the
1354 frame pointer we can do global analysis. */
1355
1356 group_info *group
1357 = rtx_group_vec[group_id];
1358 tree expr = MEM_EXPR (mem);
1359
1360 store_info = rtx_store_info_pool.allocate ();
1361 set_usage_bits (group, offset, width, expr);
1362
1363 if (dump_file && (dump_flags & TDF_DETAILS))
1364 fprintf (dump_file, " processing const base store gid=%d[%d..%d)\n",
1365 group_id, (int)offset, (int)(offset+width));
1366 }
1367 else
1368 {
1369 if (may_be_sp_based_p (XEXP (mem, 0)))
1370 insn_info->stack_pointer_based = true;
1371 insn_info->contains_cselib_groups = true;
1372
1373 store_info = cse_store_info_pool.allocate ();
1374 group_id = -1;
1375
1376 if (dump_file && (dump_flags & TDF_DETAILS))
1377 fprintf (dump_file, " processing cselib store [%d..%d)\n",
1378 (int)offset, (int)(offset+width));
1379 }
1380
1381 const_rhs = rhs = NULL_RTX;
1382 if (GET_CODE (body) == SET
1383 /* No place to keep the value after ra. */
1384 && !reload_completed
1385 && (REG_P (SET_SRC (body))
1386 || GET_CODE (SET_SRC (body)) == SUBREG
1387 || CONSTANT_P (SET_SRC (body)))
1388 && !MEM_VOLATILE_P (mem)
1389 /* Sometimes the store and reload is used for truncation and
1390 rounding. */
1391 && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store)))
1392 {
1393 rhs = SET_SRC (body);
1394 if (CONSTANT_P (rhs))
1395 const_rhs = rhs;
1396 else if (body == PATTERN (insn_info->insn))
1397 {
1398 rtx tem = find_reg_note (insn_info->insn, REG_EQUAL, NULL_RTX);
1399 if (tem && CONSTANT_P (XEXP (tem, 0)))
1400 const_rhs = XEXP (tem, 0);
1401 }
1402 if (const_rhs == NULL_RTX && REG_P (rhs))
1403 {
1404 rtx tem = cselib_expand_value_rtx (rhs, scratch, 5);
1405
1406 if (tem && CONSTANT_P (tem))
1407 const_rhs = tem;
1408 }
1409 }
1410
1411 /* Check to see if this stores causes some other stores to be
1412 dead. */
1413 ptr = active_local_stores;
1414 last = NULL;
1415 redundant_reason = NULL;
1416 mem = canon_rtx (mem);
1417
1418 if (group_id < 0)
1419 mem_addr = base->val_rtx;
1420 else
1421 {
1422 group_info *group = rtx_group_vec[group_id];
1423 mem_addr = group->canon_base_addr;
1424 }
1425 if (offset)
1426 mem_addr = plus_constant (get_address_mode (mem), mem_addr, offset);
1427
1428 while (ptr)
1429 {
1430 insn_info_t next = ptr->next_local_store;
1431 struct store_info *s_info = ptr->store_rec;
1432 bool del = true;
1433
1434 /* Skip the clobbers. We delete the active insn if this insn
1435 shadows the set. To have been put on the active list, it
1436 has exactly on set. */
1437 while (!s_info->is_set)
1438 s_info = s_info->next;
1439
1440 if (s_info->group_id == group_id && s_info->cse_base == base)
1441 {
1442 HOST_WIDE_INT i;
1443 if (dump_file && (dump_flags & TDF_DETAILS))
1444 fprintf (dump_file, " trying store in insn=%d gid=%d[%d..%d)\n",
1445 INSN_UID (ptr->insn), s_info->group_id,
1446 (int)s_info->begin, (int)s_info->end);
1447
1448 /* Even if PTR won't be eliminated as unneeded, if both
1449 PTR and this insn store the same constant value, we might
1450 eliminate this insn instead. */
1451 if (s_info->const_rhs
1452 && const_rhs
1453 && offset >= s_info->begin
1454 && offset + width <= s_info->end
1455 && all_positions_needed_p (s_info, offset - s_info->begin,
1456 width))
1457 {
1458 if (GET_MODE (mem) == BLKmode)
1459 {
1460 if (GET_MODE (s_info->mem) == BLKmode
1461 && s_info->const_rhs == const_rhs)
1462 redundant_reason = ptr;
1463 }
1464 else if (s_info->const_rhs == const0_rtx
1465 && const_rhs == const0_rtx)
1466 redundant_reason = ptr;
1467 else
1468 {
1469 rtx val;
1470 start_sequence ();
1471 val = get_stored_val (s_info, GET_MODE (mem),
1472 offset, offset + width,
1473 BLOCK_FOR_INSN (insn_info->insn),
1474 true);
1475 if (get_insns () != NULL)
1476 val = NULL_RTX;
1477 end_sequence ();
1478 if (val && rtx_equal_p (val, const_rhs))
1479 redundant_reason = ptr;
1480 }
1481 }
1482
1483 for (i = MAX (offset, s_info->begin);
1484 i < offset + width && i < s_info->end;
1485 i++)
1486 set_position_unneeded (s_info, i - s_info->begin);
1487 }
1488 else if (s_info->rhs)
1489 /* Need to see if it is possible for this store to overwrite
1490 the value of store_info. If it is, set the rhs to NULL to
1491 keep it from being used to remove a load. */
1492 {
1493 if (canon_output_dependence (s_info->mem, true,
1494 mem, GET_MODE (mem),
1495 mem_addr))
1496 {
1497 s_info->rhs = NULL;
1498 s_info->const_rhs = NULL;
1499 }
1500 }
1501
1502 /* An insn can be deleted if every position of every one of
1503 its s_infos is zero. */
1504 if (any_positions_needed_p (s_info))
1505 del = false;
1506
1507 if (del)
1508 {
1509 insn_info_t insn_to_delete = ptr;
1510
1511 active_local_stores_len--;
1512 if (last)
1513 last->next_local_store = ptr->next_local_store;
1514 else
1515 active_local_stores = ptr->next_local_store;
1516
1517 if (!insn_to_delete->cannot_delete)
1518 delete_dead_store_insn (insn_to_delete);
1519 }
1520 else
1521 last = ptr;
1522
1523 ptr = next;
1524 }
1525
1526 /* Finish filling in the store_info. */
1527 store_info->next = insn_info->store_rec;
1528 insn_info->store_rec = store_info;
1529 store_info->mem = mem;
1530 store_info->mem_addr = mem_addr;
1531 store_info->cse_base = base;
1532 if (width > HOST_BITS_PER_WIDE_INT)
1533 {
1534 store_info->is_large = true;
1535 store_info->positions_needed.large.count = 0;
1536 store_info->positions_needed.large.bmap = BITMAP_ALLOC (&dse_bitmap_obstack);
1537 }
1538 else
1539 {
1540 store_info->is_large = false;
1541 store_info->positions_needed.small_bitmask = lowpart_bitmask (width);
1542 }
1543 store_info->group_id = group_id;
1544 store_info->begin = offset;
1545 store_info->end = offset + width;
1546 store_info->is_set = GET_CODE (body) == SET;
1547 store_info->rhs = rhs;
1548 store_info->const_rhs = const_rhs;
1549 store_info->redundant_reason = redundant_reason;
1550
1551 /* If this is a clobber, we return 0. We will only be able to
1552 delete this insn if there is only one store USED store, but we
1553 can use the clobber to delete other stores earlier. */
1554 return store_info->is_set ? 1 : 0;
1555}
1556
1557
1558static void
1559dump_insn_info (const char * start, insn_info_t insn_info)
1560{
1561 fprintf (dump_file, "%s insn=%d %s\n", start,
1562 INSN_UID (insn_info->insn),
1563 insn_info->store_rec ? "has store" : "naked");
1564}
1565
1566
1567/* If the modes are different and the value's source and target do not
1568 line up, we need to extract the value from lower part of the rhs of
1569 the store, shift it, and then put it into a form that can be shoved
1570 into the read_insn. This function generates a right SHIFT of a
1571 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The
1572 shift sequence is returned or NULL if we failed to find a
1573 shift. */
1574
1575static rtx
1576find_shift_sequence (int access_size,
1577 store_info *store_info,
1578 machine_mode read_mode,
1579 int shift, bool speed, bool require_cst)
1580{
1581 machine_mode store_mode = GET_MODE (store_info->mem);
1582 scalar_int_mode new_mode;
1583 rtx read_reg = NULL;
1584
1585 /* Some machines like the x86 have shift insns for each size of
1586 operand. Other machines like the ppc or the ia-64 may only have
1587 shift insns that shift values within 32 or 64 bit registers.
1588 This loop tries to find the smallest shift insn that will right
1589 justify the value we want to read but is available in one insn on
1590 the machine. */
1591
1592 opt_scalar_int_mode new_mode_iter;
1593 FOR_EACH_MODE_FROM (new_mode_iter,
1594 smallest_int_mode_for_size (access_size * BITS_PER_UNIT))
1595 {
1596 rtx target, new_reg, new_lhs;
1597 rtx_insn *shift_seq, *insn;
1598 int cost;
1599
1600 new_mode = new_mode_iter.require ();
1601 if (GET_MODE_BITSIZE (new_mode) > BITS_PER_WORD)
1602 break;
1603
1604 /* If a constant was stored into memory, try to simplify it here,
1605 otherwise the cost of the shift might preclude this optimization
1606 e.g. at -Os, even when no actual shift will be needed. */
1607 if (store_info->const_rhs)
1608 {
1609 unsigned int byte = subreg_lowpart_offset (new_mode, store_mode);
1610 rtx ret = simplify_subreg (new_mode, store_info->const_rhs,
1611 store_mode, byte);
1612 if (ret && CONSTANT_P (ret))
1613 {
1614 ret = simplify_const_binary_operation (LSHIFTRT, new_mode,
1615 ret, GEN_INT (shift));
1616 if (ret && CONSTANT_P (ret))
1617 {
1618 byte = subreg_lowpart_offset (read_mode, new_mode);
1619 ret = simplify_subreg (read_mode, ret, new_mode, byte);
1620 if (ret && CONSTANT_P (ret)
1621 && (set_src_cost (ret, read_mode, speed)
1622 <= COSTS_N_INSNS (1)))
1623 return ret;
1624 }
1625 }
1626 }
1627
1628 if (require_cst)
1629 return NULL_RTX;
1630
1631 /* Try a wider mode if truncating the store mode to NEW_MODE
1632 requires a real instruction. */
1633 if (GET_MODE_BITSIZE (new_mode) < GET_MODE_BITSIZE (store_mode)
1634 && !TRULY_NOOP_TRUNCATION_MODES_P (new_mode, store_mode))
1635 continue;
1636
1637 /* Also try a wider mode if the necessary punning is either not
1638 desirable or not possible. */
1639 if (!CONSTANT_P (store_info->rhs)
1640 && !targetm.modes_tieable_p (new_mode, store_mode))
1641 continue;
1642
1643 new_reg = gen_reg_rtx (new_mode);
1644
1645 start_sequence ();
1646
1647 /* In theory we could also check for an ashr. Ian Taylor knows
1648 of one dsp where the cost of these two was not the same. But
1649 this really is a rare case anyway. */
1650 target = expand_binop (new_mode, lshr_optab, new_reg,
1651 GEN_INT (shift), new_reg, 1, OPTAB_DIRECT);
1652
1653 shift_seq = get_insns ();
1654 end_sequence ();
1655
1656 if (target != new_reg || shift_seq == NULL)
1657 continue;
1658
1659 cost = 0;
1660 for (insn = shift_seq; insn != NULL_RTX; insn = NEXT_INSN (insn))
1661 if (INSN_P (insn))
1662 cost += insn_cost (insn, speed);
1663
1664 /* The computation up to here is essentially independent
1665 of the arguments and could be precomputed. It may
1666 not be worth doing so. We could precompute if
1667 worthwhile or at least cache the results. The result
1668 technically depends on both SHIFT and ACCESS_SIZE,
1669 but in practice the answer will depend only on ACCESS_SIZE. */
1670
1671 if (cost > COSTS_N_INSNS (1))
1672 continue;
1673
1674 new_lhs = extract_low_bits (new_mode, store_mode,
1675 copy_rtx (store_info->rhs));
1676 if (new_lhs == NULL_RTX)
1677 continue;
1678
1679 /* We found an acceptable shift. Generate a move to
1680 take the value from the store and put it into the
1681 shift pseudo, then shift it, then generate another
1682 move to put in into the target of the read. */
1683 emit_move_insn (new_reg, new_lhs);
1684 emit_insn (shift_seq);
1685 read_reg = extract_low_bits (read_mode, new_mode, new_reg);
1686 break;
1687 }
1688
1689 return read_reg;
1690}
1691
1692
1693/* Call back for note_stores to find the hard regs set or clobbered by
1694 insn. Data is a bitmap of the hardregs set so far. */
1695
1696static void
1697look_for_hardregs (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
1698{
1699 bitmap regs_set = (bitmap) data;
1700
1701 if (REG_P (x)
1702 && HARD_REGISTER_P (x))
1703 bitmap_set_range (regs_set, REGNO (x), REG_NREGS (x));
1704}
1705
1706/* Helper function for replace_read and record_store.
1707 Attempt to return a value stored in STORE_INFO, from READ_BEGIN
1708 to one before READ_END bytes read in READ_MODE. Return NULL
1709 if not successful. If REQUIRE_CST is true, return always constant. */
1710
1711static rtx
1712get_stored_val (store_info *store_info, machine_mode read_mode,
1713 HOST_WIDE_INT read_begin, HOST_WIDE_INT read_end,
1714 basic_block bb, bool require_cst)
1715{
1716 machine_mode store_mode = GET_MODE (store_info->mem);
1717 int shift;
1718 int access_size; /* In bytes. */
1719 rtx read_reg;
1720
1721 /* To get here the read is within the boundaries of the write so
1722 shift will never be negative. Start out with the shift being in
1723 bytes. */
1724 if (store_mode == BLKmode)
1725 shift = 0;
1726 else if (BYTES_BIG_ENDIAN)
1727 shift = store_info->end - read_end;
1728 else
1729 shift = read_begin - store_info->begin;
1730
1731 access_size = shift + GET_MODE_SIZE (read_mode);
1732
1733 /* From now on it is bits. */
1734 shift *= BITS_PER_UNIT;
1735
1736 if (shift)
1737 read_reg = find_shift_sequence (access_size, store_info, read_mode, shift,
1738 optimize_bb_for_speed_p (bb),
1739 require_cst);
1740 else if (store_mode == BLKmode)
1741 {
1742 /* The store is a memset (addr, const_val, const_size). */
1743 gcc_assert (CONST_INT_P (store_info->rhs));
1744 scalar_int_mode int_store_mode;
1745 if (!int_mode_for_mode (read_mode).exists (&int_store_mode))
1746 read_reg = NULL_RTX;
1747 else if (store_info->rhs == const0_rtx)
1748 read_reg = extract_low_bits (read_mode, int_store_mode, const0_rtx);
1749 else if (GET_MODE_BITSIZE (int_store_mode) > HOST_BITS_PER_WIDE_INT
1750 || BITS_PER_UNIT >= HOST_BITS_PER_WIDE_INT)
1751 read_reg = NULL_RTX;
1752 else
1753 {
1754 unsigned HOST_WIDE_INT c
1755 = INTVAL (store_info->rhs)
1756 & ((HOST_WIDE_INT_1 << BITS_PER_UNIT) - 1);
1757 int shift = BITS_PER_UNIT;
1758 while (shift < HOST_BITS_PER_WIDE_INT)
1759 {
1760 c |= (c << shift);
1761 shift <<= 1;
1762 }
1763 read_reg = gen_int_mode (c, int_store_mode);
1764 read_reg = extract_low_bits (read_mode, int_store_mode, read_reg);
1765 }
1766 }
1767 else if (store_info->const_rhs
1768 && (require_cst
1769 || GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode)))
1770 read_reg = extract_low_bits (read_mode, store_mode,
1771 copy_rtx (store_info->const_rhs));
1772 else
1773 read_reg = extract_low_bits (read_mode, store_mode,
1774 copy_rtx (store_info->rhs));
1775 if (require_cst && read_reg && !CONSTANT_P (read_reg))
1776 read_reg = NULL_RTX;
1777 return read_reg;
1778}
1779
1780/* Take a sequence of:
1781 A <- r1
1782 ...
1783 ... <- A
1784
1785 and change it into
1786 r2 <- r1
1787 A <- r1
1788 ...
1789 ... <- r2
1790
1791 or
1792
1793 r3 <- extract (r1)
1794 r3 <- r3 >> shift
1795 r2 <- extract (r3)
1796 ... <- r2
1797
1798 or
1799
1800 r2 <- extract (r1)
1801 ... <- r2
1802
1803 Depending on the alignment and the mode of the store and
1804 subsequent load.
1805
1806
1807 The STORE_INFO and STORE_INSN are for the store and READ_INFO
1808 and READ_INSN are for the read. Return true if the replacement
1809 went ok. */
1810
1811static bool
1812replace_read (store_info *store_info, insn_info_t store_insn,
1813 read_info_t read_info, insn_info_t read_insn, rtx *loc,
1814 bitmap regs_live)
1815{
1816 machine_mode store_mode = GET_MODE (store_info->mem);
1817 machine_mode read_mode = GET_MODE (read_info->mem);
1818 rtx_insn *insns, *this_insn;
1819 rtx read_reg;
1820 basic_block bb;
1821
1822 if (!dbg_cnt (dse))
1823 return false;
1824
1825 /* Create a sequence of instructions to set up the read register.
1826 This sequence goes immediately before the store and its result
1827 is read by the load.
1828
1829 We need to keep this in perspective. We are replacing a read
1830 with a sequence of insns, but the read will almost certainly be
1831 in cache, so it is not going to be an expensive one. Thus, we
1832 are not willing to do a multi insn shift or worse a subroutine
1833 call to get rid of the read. */
1834 if (dump_file && (dump_flags & TDF_DETAILS))
1835 fprintf (dump_file, "trying to replace %smode load in insn %d"
1836 " from %smode store in insn %d\n",
1837 GET_MODE_NAME (read_mode), INSN_UID (read_insn->insn),
1838 GET_MODE_NAME (store_mode), INSN_UID (store_insn->insn));
1839 start_sequence ();
1840 bb = BLOCK_FOR_INSN (read_insn->insn);
1841 read_reg = get_stored_val (store_info,
1842 read_mode, read_info->begin, read_info->end,
1843 bb, false);
1844 if (read_reg == NULL_RTX)
1845 {
1846 end_sequence ();
1847 if (dump_file && (dump_flags & TDF_DETAILS))
1848 fprintf (dump_file, " -- could not extract bits of stored value\n");
1849 return false;
1850 }
1851 /* Force the value into a new register so that it won't be clobbered
1852 between the store and the load. */
1853 read_reg = copy_to_mode_reg (read_mode, read_reg);
1854 insns = get_insns ();
1855 end_sequence ();
1856
1857 if (insns != NULL_RTX)
1858 {
1859 /* Now we have to scan the set of new instructions to see if the
1860 sequence contains and sets of hardregs that happened to be
1861 live at this point. For instance, this can happen if one of
1862 the insns sets the CC and the CC happened to be live at that
1863 point. This does occasionally happen, see PR 37922. */
1864 bitmap regs_set = BITMAP_ALLOC (&reg_obstack);
1865
1866 for (this_insn = insns; this_insn != NULL_RTX; this_insn = NEXT_INSN (this_insn))
1867 note_stores (PATTERN (this_insn), look_for_hardregs, regs_set);
1868
1869 bitmap_and_into (regs_set, regs_live);
1870 if (!bitmap_empty_p (regs_set))
1871 {
1872 if (dump_file && (dump_flags & TDF_DETAILS))
1873 {
1874 fprintf (dump_file,
1875 "abandoning replacement because sequence clobbers live hardregs:");
1876 df_print_regset (dump_file, regs_set);
1877 }
1878
1879 BITMAP_FREE (regs_set);
1880 return false;
1881 }
1882 BITMAP_FREE (regs_set);
1883 }
1884
1885 if (validate_change (read_insn->insn, loc, read_reg, 0))
1886 {
1887 deferred_change *change = deferred_change_pool.allocate ();
1888
1889 /* Insert this right before the store insn where it will be safe
1890 from later insns that might change it before the read. */
1891 emit_insn_before (insns, store_insn->insn);
1892
1893 /* And now for the kludge part: cselib croaks if you just
1894 return at this point. There are two reasons for this:
1895
1896 1) Cselib has an idea of how many pseudos there are and
1897 that does not include the new ones we just added.
1898
1899 2) Cselib does not know about the move insn we added
1900 above the store_info, and there is no way to tell it
1901 about it, because it has "moved on".
1902
1903 Problem (1) is fixable with a certain amount of engineering.
1904 Problem (2) is requires starting the bb from scratch. This
1905 could be expensive.
1906
1907 So we are just going to have to lie. The move/extraction
1908 insns are not really an issue, cselib did not see them. But
1909 the use of the new pseudo read_insn is a real problem because
1910 cselib has not scanned this insn. The way that we solve this
1911 problem is that we are just going to put the mem back for now
1912 and when we are finished with the block, we undo this. We
1913 keep a table of mems to get rid of. At the end of the basic
1914 block we can put them back. */
1915
1916 *loc = read_info->mem;
1917 change->next = deferred_change_list;
1918 deferred_change_list = change;
1919 change->loc = loc;
1920 change->reg = read_reg;
1921
1922 /* Get rid of the read_info, from the point of view of the
1923 rest of dse, play like this read never happened. */
1924 read_insn->read_rec = read_info->next;
1925 read_info_type_pool.remove (read_info);
1926 if (dump_file && (dump_flags & TDF_DETAILS))
1927 {
1928 fprintf (dump_file, " -- replaced the loaded MEM with ");
1929 print_simple_rtl (dump_file, read_reg);
1930 fprintf (dump_file, "\n");
1931 }
1932 return true;
1933 }
1934 else
1935 {
1936 if (dump_file && (dump_flags & TDF_DETAILS))
1937 {
1938 fprintf (dump_file, " -- replacing the loaded MEM with ");
1939 print_simple_rtl (dump_file, read_reg);
1940 fprintf (dump_file, " led to an invalid instruction\n");
1941 }
1942 return false;
1943 }
1944}
1945
1946/* Check the address of MEM *LOC and kill any appropriate stores that may
1947 be active. */
1948
1949static void
1950check_mem_read_rtx (rtx *loc, bb_info_t bb_info)
1951{
1952 rtx mem = *loc, mem_addr;
1953 insn_info_t insn_info;
1954 HOST_WIDE_INT offset = 0;
1955 HOST_WIDE_INT width = 0;
1956 cselib_val *base = NULL;
1957 int group_id;
1958 read_info_t read_info;
1959
1960 insn_info = bb_info->last_insn;
1961
1962 if ((MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER)
1963 || (MEM_VOLATILE_P (mem)))
1964 {
1965 if (dump_file && (dump_flags & TDF_DETAILS))
1966 fprintf (dump_file, " adding wild read, volatile or barrier.\n");
1967 add_wild_read (bb_info);
1968 insn_info->cannot_delete = true;
1969 return;
1970 }
1971
1972 /* If it is reading readonly mem, then there can be no conflict with
1973 another write. */
1974 if (MEM_READONLY_P (mem))
1975 return;
1976
1977 if (!canon_address (mem, &group_id, &offset, &base))
1978 {
1979 if (dump_file && (dump_flags & TDF_DETAILS))
1980 fprintf (dump_file, " adding wild read, canon_address failure.\n");
1981 add_wild_read (bb_info);
1982 return;
1983 }
1984
1985 if (GET_MODE (mem) == BLKmode)
1986 width = -1;
1987 else
1988 width = GET_MODE_SIZE (GET_MODE (mem));
1989
1990 if (width == -1
1991 ? offset == HOST_WIDE_INT_MIN
1992 : offset > HOST_WIDE_INT_MAX - width)
1993 {
1994 if (dump_file && (dump_flags & TDF_DETAILS))
1995 fprintf (dump_file, " adding wild read, due to overflow.\n");
1996 add_wild_read (bb_info);
1997 return;
1998 }
1999
2000 read_info = read_info_type_pool.allocate ();
2001 read_info->group_id = group_id;
2002 read_info->mem = mem;
2003 read_info->begin = offset;
2004 read_info->end = offset + width;
2005 read_info->next = insn_info->read_rec;
2006 insn_info->read_rec = read_info;
2007 if (group_id < 0)
2008 mem_addr = base->val_rtx;
2009 else
2010 {
2011 group_info *group = rtx_group_vec[group_id];
2012 mem_addr = group->canon_base_addr;
2013 }
2014 if (offset)
2015 mem_addr = plus_constant (get_address_mode (mem), mem_addr, offset);
2016
2017 if (group_id >= 0)
2018 {
2019 /* This is the restricted case where the base is a constant or
2020 the frame pointer and offset is a constant. */
2021 insn_info_t i_ptr = active_local_stores;
2022 insn_info_t last = NULL;
2023
2024 if (dump_file && (dump_flags & TDF_DETAILS))
2025 {
2026 if (width == -1)
2027 fprintf (dump_file, " processing const load gid=%d[BLK]\n",
2028 group_id);
2029 else
2030 fprintf (dump_file, " processing const load gid=%d[%d..%d)\n",
2031 group_id, (int)offset, (int)(offset+width));
2032 }
2033
2034 while (i_ptr)
2035 {
2036 bool remove = false;
2037 store_info *store_info = i_ptr->store_rec;
2038
2039 /* Skip the clobbers. */
2040 while (!store_info->is_set)
2041 store_info = store_info->next;
2042
2043 /* There are three cases here. */
2044 if (store_info->group_id < 0)
2045 /* We have a cselib store followed by a read from a
2046 const base. */
2047 remove
2048 = canon_true_dependence (store_info->mem,
2049 GET_MODE (store_info->mem),
2050 store_info->mem_addr,
2051 mem, mem_addr);
2052
2053 else if (group_id == store_info->group_id)
2054 {
2055 /* This is a block mode load. We may get lucky and
2056 canon_true_dependence may save the day. */
2057 if (width == -1)
2058 remove
2059 = canon_true_dependence (store_info->mem,
2060 GET_MODE (store_info->mem),
2061 store_info->mem_addr,
2062 mem, mem_addr);
2063
2064 /* If this read is just reading back something that we just
2065 stored, rewrite the read. */
2066 else
2067 {
2068 if (store_info->rhs
2069 && offset >= store_info->begin
2070 && offset + width <= store_info->end
2071 && all_positions_needed_p (store_info,
2072 offset - store_info->begin,
2073 width)
2074 && replace_read (store_info, i_ptr, read_info,
2075 insn_info, loc, bb_info->regs_live))
2076 return;
2077
2078 /* The bases are the same, just see if the offsets
2079 overlap. */
2080 if ((offset < store_info->end)
2081 && (offset + width > store_info->begin))
2082 remove = true;
2083 }
2084 }
2085
2086 /* else
2087 The else case that is missing here is that the
2088 bases are constant but different. There is nothing
2089 to do here because there is no overlap. */
2090
2091 if (remove)
2092 {
2093 if (dump_file && (dump_flags & TDF_DETAILS))
2094 dump_insn_info ("removing from active", i_ptr);
2095
2096 active_local_stores_len--;
2097 if (last)
2098 last->next_local_store = i_ptr->next_local_store;
2099 else
2100 active_local_stores = i_ptr->next_local_store;
2101 }
2102 else
2103 last = i_ptr;
2104 i_ptr = i_ptr->next_local_store;
2105 }
2106 }
2107 else
2108 {
2109 insn_info_t i_ptr = active_local_stores;
2110 insn_info_t last = NULL;
2111 if (dump_file && (dump_flags & TDF_DETAILS))
2112 {
2113 fprintf (dump_file, " processing cselib load mem:");
2114 print_inline_rtx (dump_file, mem, 0);
2115 fprintf (dump_file, "\n");
2116 }
2117
2118 while (i_ptr)
2119 {
2120 bool remove = false;
2121 store_info *store_info = i_ptr->store_rec;
2122
2123 if (dump_file && (dump_flags & TDF_DETAILS))
2124 fprintf (dump_file, " processing cselib load against insn %d\n",
2125 INSN_UID (i_ptr->insn));
2126
2127 /* Skip the clobbers. */
2128 while (!store_info->is_set)
2129 store_info = store_info->next;
2130
2131 /* If this read is just reading back something that we just
2132 stored, rewrite the read. */
2133 if (store_info->rhs
2134 && store_info->group_id == -1
2135 && store_info->cse_base == base
2136 && width != -1
2137 && offset >= store_info->begin
2138 && offset + width <= store_info->end
2139 && all_positions_needed_p (store_info,
2140 offset - store_info->begin, width)
2141 && replace_read (store_info, i_ptr, read_info, insn_info, loc,
2142 bb_info->regs_live))
2143 return;
2144
2145 remove = canon_true_dependence (store_info->mem,
2146 GET_MODE (store_info->mem),
2147 store_info->mem_addr,
2148 mem, mem_addr);
2149
2150 if (remove)
2151 {
2152 if (dump_file && (dump_flags & TDF_DETAILS))
2153 dump_insn_info ("removing from active", i_ptr);
2154
2155 active_local_stores_len--;
2156 if (last)
2157 last->next_local_store = i_ptr->next_local_store;
2158 else
2159 active_local_stores = i_ptr->next_local_store;
2160 }
2161 else
2162 last = i_ptr;
2163 i_ptr = i_ptr->next_local_store;
2164 }
2165 }
2166}
2167
2168/* A note_uses callback in which DATA points the INSN_INFO for
2169 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns
2170 true for any part of *LOC. */
2171
2172static void
2173check_mem_read_use (rtx *loc, void *data)
2174{
2175 subrtx_ptr_iterator::array_type array;
2176 FOR_EACH_SUBRTX_PTR (iter, array, loc, NONCONST)
2177 {
2178 rtx *loc = *iter;
2179 if (MEM_P (*loc))
2180 check_mem_read_rtx (loc, (bb_info_t) data);
2181 }
2182}
2183
2184
2185/* Get arguments passed to CALL_INSN. Return TRUE if successful.
2186 So far it only handles arguments passed in registers. */
2187
2188static bool
2189get_call_args (rtx call_insn, tree fn, rtx *args, int nargs)
2190{
2191 CUMULATIVE_ARGS args_so_far_v;
2192 cumulative_args_t args_so_far;
2193 tree arg;
2194 int idx;
2195
2196 INIT_CUMULATIVE_ARGS (args_so_far_v, TREE_TYPE (fn), NULL_RTX, 0, 3);
2197 args_so_far = pack_cumulative_args (&args_so_far_v);
2198
2199 arg = TYPE_ARG_TYPES (TREE_TYPE (fn));
2200 for (idx = 0;
2201 arg != void_list_node && idx < nargs;
2202 arg = TREE_CHAIN (arg), idx++)
2203 {
2204 scalar_int_mode mode;
2205 rtx reg, link, tmp;
2206
2207 if (!is_int_mode (TYPE_MODE (TREE_VALUE (arg)), &mode))
2208 return false;
2209
2210 reg = targetm.calls.function_arg (args_so_far, mode, NULL_TREE, true);
2211 if (!reg || !REG_P (reg) || GET_MODE (reg) != mode)
2212 return false;
2213
2214 for (link = CALL_INSN_FUNCTION_USAGE (call_insn);
2215 link;
2216 link = XEXP (link, 1))
2217 if (GET_CODE (XEXP (link, 0)) == USE)
2218 {
2219 scalar_int_mode arg_mode;
2220 args[idx] = XEXP (XEXP (link, 0), 0);
2221 if (REG_P (args[idx])
2222 && REGNO (args[idx]) == REGNO (reg)
2223 && (GET_MODE (args[idx]) == mode
2224 || (is_int_mode (GET_MODE (args[idx]), &arg_mode)
2225 && (GET_MODE_SIZE (arg_mode) <= UNITS_PER_WORD)
2226 && (GET_MODE_SIZE (arg_mode) > GET_MODE_SIZE (mode)))))
2227 break;
2228 }
2229 if (!link)
2230 return false;
2231
2232 tmp = cselib_expand_value_rtx (args[idx], scratch, 5);
2233 if (GET_MODE (args[idx]) != mode)
2234 {
2235 if (!tmp || !CONST_INT_P (tmp))
2236 return false;
2237 tmp = gen_int_mode (INTVAL (tmp), mode);
2238 }
2239 if (tmp)
2240 args[idx] = tmp;
2241
2242 targetm.calls.function_arg_advance (args_so_far, mode, NULL_TREE, true);
2243 }
2244 if (arg != void_list_node || idx != nargs)
2245 return false;
2246 return true;
2247}
2248
2249/* Return a bitmap of the fixed registers contained in IN. */
2250
2251static bitmap
2252copy_fixed_regs (const_bitmap in)
2253{
2254 bitmap ret;
2255
2256 ret = ALLOC_REG_SET (NULL);
2257 bitmap_and (ret, in, fixed_reg_set_regset);
2258 return ret;
2259}
2260
2261/* Apply record_store to all candidate stores in INSN. Mark INSN
2262 if some part of it is not a candidate store and assigns to a
2263 non-register target. */
2264
2265static void
2266scan_insn (bb_info_t bb_info, rtx_insn *insn)
2267{
2268 rtx body;
2269 insn_info_type *insn_info = insn_info_type_pool.allocate ();
2270 int mems_found = 0;
2271 memset (insn_info, 0, sizeof (struct insn_info_type));
2272
2273 if (dump_file && (dump_flags & TDF_DETAILS))
2274 fprintf (dump_file, "\n**scanning insn=%d\n",
2275 INSN_UID (insn));
2276
2277 insn_info->prev_insn = bb_info->last_insn;
2278 insn_info->insn = insn;
2279 bb_info->last_insn = insn_info;
2280
2281 if (DEBUG_INSN_P (insn))
2282 {
2283 insn_info->cannot_delete = true;
2284 return;
2285 }
2286
2287 /* Look at all of the uses in the insn. */
2288 note_uses (&PATTERN (insn), check_mem_read_use, bb_info);
2289
2290 if (CALL_P (insn))
2291 {
2292 bool const_call;
2293 rtx call, sym;
2294 tree memset_call = NULL_TREE;
2295
2296 insn_info->cannot_delete = true;
2297
2298 /* Const functions cannot do anything bad i.e. read memory,
2299 however, they can read their parameters which may have
2300 been pushed onto the stack.
2301 memset and bzero don't read memory either. */
2302 const_call = RTL_CONST_CALL_P (insn);
2303 if (!const_call
2304 && (call = get_call_rtx_from (insn))
2305 && (sym = XEXP (XEXP (call, 0), 0))
2306 && GET_CODE (sym) == SYMBOL_REF
2307 && SYMBOL_REF_DECL (sym)
2308 && TREE_CODE (SYMBOL_REF_DECL (sym)) == FUNCTION_DECL
2309 && DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (sym)) == BUILT_IN_NORMAL
2310 && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (sym)) == BUILT_IN_MEMSET)
2311 memset_call = SYMBOL_REF_DECL (sym);
2312
2313 if (const_call || memset_call)
2314 {
2315 insn_info_t i_ptr = active_local_stores;
2316 insn_info_t last = NULL;
2317
2318 if (dump_file && (dump_flags & TDF_DETAILS))
2319 fprintf (dump_file, "%s call %d\n",
2320 const_call ? "const" : "memset", INSN_UID (insn));
2321
2322 /* See the head comment of the frame_read field. */
2323 if (reload_completed
2324 /* Tail calls are storing their arguments using
2325 arg pointer. If it is a frame pointer on the target,
2326 even before reload we need to kill frame pointer based
2327 stores. */
2328 || (SIBLING_CALL_P (insn)
2329 && HARD_FRAME_POINTER_IS_ARG_POINTER))
2330 insn_info->frame_read = true;
2331
2332 /* Loop over the active stores and remove those which are
2333 killed by the const function call. */
2334 while (i_ptr)
2335 {
2336 bool remove_store = false;
2337
2338 /* The stack pointer based stores are always killed. */
2339 if (i_ptr->stack_pointer_based)
2340 remove_store = true;
2341
2342 /* If the frame is read, the frame related stores are killed. */
2343 else if (insn_info->frame_read)
2344 {
2345 store_info *store_info = i_ptr->store_rec;
2346
2347 /* Skip the clobbers. */
2348 while (!store_info->is_set)
2349 store_info = store_info->next;
2350
2351 if (store_info->group_id >= 0
2352 && rtx_group_vec[store_info->group_id]->frame_related)
2353 remove_store = true;
2354 }
2355
2356 if (remove_store)
2357 {
2358 if (dump_file && (dump_flags & TDF_DETAILS))
2359 dump_insn_info ("removing from active", i_ptr);
2360
2361 active_local_stores_len--;
2362 if (last)
2363 last->next_local_store = i_ptr->next_local_store;
2364 else
2365 active_local_stores = i_ptr->next_local_store;
2366 }
2367 else
2368 last = i_ptr;
2369
2370 i_ptr = i_ptr->next_local_store;
2371 }
2372
2373 if (memset_call)
2374 {
2375 rtx args[3];
2376 if (get_call_args (insn, memset_call, args, 3)
2377 && CONST_INT_P (args[1])
2378 && CONST_INT_P (args[2])
2379 && INTVAL (args[2]) > 0)
2380 {
2381 rtx mem = gen_rtx_MEM (BLKmode, args[0]);
2382 set_mem_size (mem, INTVAL (args[2]));
2383 body = gen_rtx_SET (mem, args[1]);
2384 mems_found += record_store (body, bb_info);
2385 if (dump_file && (dump_flags & TDF_DETAILS))
2386 fprintf (dump_file, "handling memset as BLKmode store\n");
2387 if (mems_found == 1)
2388 {
2389 if (active_local_stores_len++
2390 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES))
2391 {
2392 active_local_stores_len = 1;
2393 active_local_stores = NULL;
2394 }
2395 insn_info->fixed_regs_live
2396 = copy_fixed_regs (bb_info->regs_live);
2397 insn_info->next_local_store = active_local_stores;
2398 active_local_stores = insn_info;
2399 }
2400 }
2401 else
2402 clear_rhs_from_active_local_stores ();
2403 }
2404 }
2405 else if (SIBLING_CALL_P (insn) && reload_completed)
2406 /* Arguments for a sibling call that are pushed to memory are passed
2407 using the incoming argument pointer of the current function. After
2408 reload that might be (and likely is) frame pointer based. */
2409 add_wild_read (bb_info);
2410 else
2411 /* Every other call, including pure functions, may read any memory
2412 that is not relative to the frame. */
2413 add_non_frame_wild_read (bb_info);
2414
2415 return;
2416 }
2417
2418 /* Assuming that there are sets in these insns, we cannot delete
2419 them. */
2420 if ((GET_CODE (PATTERN (insn)) == CLOBBER)
2421 || volatile_refs_p (PATTERN (insn))
2422 || (!cfun->can_delete_dead_exceptions && !insn_nothrow_p (insn))
2423 || (RTX_FRAME_RELATED_P (insn))
2424 || find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX))
2425 insn_info->cannot_delete = true;
2426
2427 body = PATTERN (insn);
2428 if (GET_CODE (body) == PARALLEL)
2429 {
2430 int i;
2431 for (i = 0; i < XVECLEN (body, 0); i++)
2432 mems_found += record_store (XVECEXP (body, 0, i), bb_info);
2433 }
2434 else
2435 mems_found += record_store (body, bb_info);
2436
2437 if (dump_file && (dump_flags & TDF_DETAILS))
2438 fprintf (dump_file, "mems_found = %d, cannot_delete = %s\n",
2439 mems_found, insn_info->cannot_delete ? "true" : "false");
2440
2441 /* If we found some sets of mems, add it into the active_local_stores so
2442 that it can be locally deleted if found dead or used for
2443 replace_read and redundant constant store elimination. Otherwise mark
2444 it as cannot delete. This simplifies the processing later. */
2445 if (mems_found == 1)
2446 {
2447 if (active_local_stores_len++
2448 >= PARAM_VALUE (PARAM_MAX_DSE_ACTIVE_LOCAL_STORES))
2449 {
2450 active_local_stores_len = 1;
2451 active_local_stores = NULL;
2452 }
2453 insn_info->fixed_regs_live = copy_fixed_regs (bb_info->regs_live);
2454 insn_info->next_local_store = active_local_stores;
2455 active_local_stores = insn_info;
2456 }
2457 else
2458 insn_info->cannot_delete = true;
2459}
2460
2461
2462/* Remove BASE from the set of active_local_stores. This is a
2463 callback from cselib that is used to get rid of the stores in
2464 active_local_stores. */
2465
2466static void
2467remove_useless_values (cselib_val *base)
2468{
2469 insn_info_t insn_info = active_local_stores;
2470 insn_info_t last = NULL;
2471
2472 while (insn_info)
2473 {
2474 store_info *store_info = insn_info->store_rec;
2475 bool del = false;
2476
2477 /* If ANY of the store_infos match the cselib group that is
2478 being deleted, then the insn can not be deleted. */
2479 while (store_info)
2480 {
2481 if ((store_info->group_id == -1)
2482 && (store_info->cse_base == base))
2483 {
2484 del = true;
2485 break;
2486 }
2487 store_info = store_info->next;
2488 }
2489
2490 if (del)
2491 {
2492 active_local_stores_len--;
2493 if (last)
2494 last->next_local_store = insn_info->next_local_store;
2495 else
2496 active_local_stores = insn_info->next_local_store;
2497 free_store_info (insn_info);
2498 }
2499 else
2500 last = insn_info;
2501
2502 insn_info = insn_info->next_local_store;
2503 }
2504}
2505
2506
2507/* Do all of step 1. */
2508
2509static void
2510dse_step1 (void)
2511{
2512 basic_block bb;
2513 bitmap regs_live = BITMAP_ALLOC (&reg_obstack);
2514
2515 cselib_init (0);
2516 all_blocks = BITMAP_ALLOC (NULL);
2517 bitmap_set_bit (all_blocks, ENTRY_BLOCK);
2518 bitmap_set_bit (all_blocks, EXIT_BLOCK);
2519
2520 FOR_ALL_BB_FN (bb, cfun)
2521 {
2522 insn_info_t ptr;
2523 bb_info_t bb_info = dse_bb_info_type_pool.allocate ();
2524
2525 memset (bb_info, 0, sizeof (dse_bb_info_type));
2526 bitmap_set_bit (all_blocks, bb->index);
2527 bb_info->regs_live = regs_live;
2528
2529 bitmap_copy (regs_live, DF_LR_IN (bb));
2530 df_simulate_initialize_forwards (bb, regs_live);
2531
2532 bb_table[bb->index] = bb_info;
2533 cselib_discard_hook = remove_useless_values;
2534
2535 if (bb->index >= NUM_FIXED_BLOCKS)
2536 {
2537 rtx_insn *insn;
2538
2539 active_local_stores = NULL;
2540 active_local_stores_len = 0;
2541 cselib_clear_table ();
2542
2543 /* Scan the insns. */
2544 FOR_BB_INSNS (bb, insn)
2545 {
2546 if (INSN_P (insn))
2547 scan_insn (bb_info, insn);
2548 cselib_process_insn (insn);
2549 if (INSN_P (insn))
2550 df_simulate_one_insn_forwards (bb, insn, regs_live);
2551 }
2552
2553 /* This is something of a hack, because the global algorithm
2554 is supposed to take care of the case where stores go dead
2555 at the end of the function. However, the global
2556 algorithm must take a more conservative view of block
2557 mode reads than the local alg does. So to get the case
2558 where you have a store to the frame followed by a non
2559 overlapping block more read, we look at the active local
2560 stores at the end of the function and delete all of the
2561 frame and spill based ones. */
2562 if (stores_off_frame_dead_at_return
2563 && (EDGE_COUNT (bb->succs) == 0
2564 || (single_succ_p (bb)
2565 && single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun)
2566 && ! crtl->calls_eh_return)))
2567 {
2568 insn_info_t i_ptr = active_local_stores;
2569 while (i_ptr)
2570 {
2571 store_info *store_info = i_ptr->store_rec;
2572
2573 /* Skip the clobbers. */
2574 while (!store_info->is_set)
2575 store_info = store_info->next;
2576 if (store_info->group_id >= 0)
2577 {
2578 group_info *group = rtx_group_vec[store_info->group_id];
2579 if (group->frame_related && !i_ptr->cannot_delete)
2580 delete_dead_store_insn (i_ptr);
2581 }
2582
2583 i_ptr = i_ptr->next_local_store;
2584 }
2585 }
2586
2587 /* Get rid of the loads that were discovered in
2588 replace_read. Cselib is finished with this block. */
2589 while (deferred_change_list)
2590 {
2591 deferred_change *next = deferred_change_list->next;
2592
2593 /* There is no reason to validate this change. That was
2594 done earlier. */
2595 *deferred_change_list->loc = deferred_change_list->reg;
2596 deferred_change_pool.remove (deferred_change_list);
2597 deferred_change_list = next;
2598 }
2599
2600 /* Get rid of all of the cselib based store_infos in this
2601 block and mark the containing insns as not being
2602 deletable. */
2603 ptr = bb_info->last_insn;
2604 while (ptr)
2605 {
2606 if (ptr->contains_cselib_groups)
2607 {
2608 store_info *s_info = ptr->store_rec;
2609 while (s_info && !s_info->is_set)
2610 s_info = s_info->next;
2611 if (s_info
2612 && s_info->redundant_reason
2613 && s_info->redundant_reason->insn
2614 && !ptr->cannot_delete)
2615 {
2616 if (dump_file && (dump_flags & TDF_DETAILS))
2617 fprintf (dump_file, "Locally deleting insn %d "
2618 "because insn %d stores the "
2619 "same value and couldn't be "
2620 "eliminated\n",
2621 INSN_UID (ptr->insn),
2622 INSN_UID (s_info->redundant_reason->insn));
2623 delete_dead_store_insn (ptr);
2624 }
2625 free_store_info (ptr);
2626 }
2627 else
2628 {
2629 store_info *s_info;
2630
2631 /* Free at least positions_needed bitmaps. */
2632 for (s_info = ptr->store_rec; s_info; s_info = s_info->next)
2633 if (s_info->is_large)
2634 {
2635 BITMAP_FREE (s_info->positions_needed.large.bmap);
2636 s_info->is_large = false;
2637 }
2638 }
2639 ptr = ptr->prev_insn;
2640 }
2641
2642 cse_store_info_pool.release ();
2643 }
2644 bb_info->regs_live = NULL;
2645 }
2646
2647 BITMAP_FREE (regs_live);
2648 cselib_finish ();
2649 rtx_group_table->empty ();
2650}
2651
2652
2653/*----------------------------------------------------------------------------
2654 Second step.
2655
2656 Assign each byte position in the stores that we are going to
2657 analyze globally to a position in the bitmaps. Returns true if
2658 there are any bit positions assigned.
2659----------------------------------------------------------------------------*/
2660
2661static void
2662dse_step2_init (void)
2663{
2664 unsigned int i;
2665 group_info *group;
2666
2667 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
2668 {
2669 /* For all non stack related bases, we only consider a store to
2670 be deletable if there are two or more stores for that
2671 position. This is because it takes one store to make the
2672 other store redundant. However, for the stores that are
2673 stack related, we consider them if there is only one store
2674 for the position. We do this because the stack related
2675 stores can be deleted if their is no read between them and
2676 the end of the function.
2677
2678 To make this work in the current framework, we take the stack
2679 related bases add all of the bits from store1 into store2.
2680 This has the effect of making the eligible even if there is
2681 only one store. */
2682
2683 if (stores_off_frame_dead_at_return && group->frame_related)
2684 {
2685 bitmap_ior_into (group->store2_n, group->store1_n);
2686 bitmap_ior_into (group->store2_p, group->store1_p);
2687 if (dump_file && (dump_flags & TDF_DETAILS))
2688 fprintf (dump_file, "group %d is frame related ", i);
2689 }
2690
2691 group->offset_map_size_n++;
2692 group->offset_map_n = XOBNEWVEC (&dse_obstack, int,
2693 group->offset_map_size_n);
2694 group->offset_map_size_p++;
2695 group->offset_map_p = XOBNEWVEC (&dse_obstack, int,
2696 group->offset_map_size_p);
2697 group->process_globally = false;
2698 if (dump_file && (dump_flags & TDF_DETAILS))
2699 {
2700 fprintf (dump_file, "group %d(%d+%d): ", i,
2701 (int)bitmap_count_bits (group->store2_n),
2702 (int)bitmap_count_bits (group->store2_p));
2703 bitmap_print (dump_file, group->store2_n, "n ", " ");
2704 bitmap_print (dump_file, group->store2_p, "p ", "\n");
2705 }
2706 }
2707}
2708
2709
2710/* Init the offset tables. */
2711
2712static bool
2713dse_step2 (void)
2714{
2715 unsigned int i;
2716 group_info *group;
2717 /* Position 0 is unused because 0 is used in the maps to mean
2718 unused. */
2719 current_position = 1;
2720 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
2721 {
2722 bitmap_iterator bi;
2723 unsigned int j;
2724
2725 memset (group->offset_map_n, 0, sizeof (int) * group->offset_map_size_n);
2726 memset (group->offset_map_p, 0, sizeof (int) * group->offset_map_size_p);
2727 bitmap_clear (group->group_kill);
2728
2729 EXECUTE_IF_SET_IN_BITMAP (group->store2_n, 0, j, bi)
2730 {
2731 bitmap_set_bit (group->group_kill, current_position);
2732 if (bitmap_bit_p (group->escaped_n, j))
2733 bitmap_set_bit (kill_on_calls, current_position);
2734 group->offset_map_n[j] = current_position++;
2735 group->process_globally = true;
2736 }
2737 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi)
2738 {
2739 bitmap_set_bit (group->group_kill, current_position);
2740 if (bitmap_bit_p (group->escaped_p, j))
2741 bitmap_set_bit (kill_on_calls, current_position);
2742 group->offset_map_p[j] = current_position++;
2743 group->process_globally = true;
2744 }
2745 }
2746 return current_position != 1;
2747}
2748
2749
2750
2751/*----------------------------------------------------------------------------
2752 Third step.
2753
2754 Build the bit vectors for the transfer functions.
2755----------------------------------------------------------------------------*/
2756
2757
2758/* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not
2759 there, return 0. */
2760
2761static int
2762get_bitmap_index (group_info *group_info, HOST_WIDE_INT offset)
2763{
2764 if (offset < 0)
2765 {
2766 HOST_WIDE_INT offset_p = -offset;
2767 if (offset_p >= group_info->offset_map_size_n)
2768 return 0;
2769 return group_info->offset_map_n[offset_p];
2770 }
2771 else
2772 {
2773 if (offset >= group_info->offset_map_size_p)
2774 return 0;
2775 return group_info->offset_map_p[offset];
2776 }
2777}
2778
2779
2780/* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL
2781 may be NULL. */
2782
2783static void
2784scan_stores (store_info *store_info, bitmap gen, bitmap kill)
2785{
2786 while (store_info)
2787 {
2788 HOST_WIDE_INT i;
2789 group_info *group_info
2790 = rtx_group_vec[store_info->group_id];
2791 if (group_info->process_globally)
2792 for (i = store_info->begin; i < store_info->end; i++)
2793 {
2794 int index = get_bitmap_index (group_info, i);
2795 if (index != 0)
2796 {
2797 bitmap_set_bit (gen, index);
2798 if (kill)
2799 bitmap_clear_bit (kill, index);
2800 }
2801 }
2802 store_info = store_info->next;
2803 }
2804}
2805
2806
2807/* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL
2808 may be NULL. */
2809
2810static void
2811scan_reads (insn_info_t insn_info, bitmap gen, bitmap kill)
2812{
2813 read_info_t read_info = insn_info->read_rec;
2814 int i;
2815 group_info *group;
2816
2817 /* If this insn reads the frame, kill all the frame related stores. */
2818 if (insn_info->frame_read)
2819 {
2820 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
2821 if (group->process_globally && group->frame_related)
2822 {
2823 if (kill)
2824 bitmap_ior_into (kill, group->group_kill);
2825 bitmap_and_compl_into (gen, group->group_kill);
2826 }
2827 }
2828 if (insn_info->non_frame_wild_read)
2829 {
2830 /* Kill all non-frame related stores. Kill all stores of variables that
2831 escape. */
2832 if (kill)
2833 bitmap_ior_into (kill, kill_on_calls);
2834 bitmap_and_compl_into (gen, kill_on_calls);
2835 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
2836 if (group->process_globally && !group->frame_related)
2837 {
2838 if (kill)
2839 bitmap_ior_into (kill, group->group_kill);
2840 bitmap_and_compl_into (gen, group->group_kill);
2841 }
2842 }
2843 while (read_info)
2844 {
2845 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
2846 {
2847 if (group->process_globally)
2848 {
2849 if (i == read_info->group_id)
2850 {
2851 if (read_info->begin > read_info->end)
2852 {
2853 /* Begin > end for block mode reads. */
2854 if (kill)
2855 bitmap_ior_into (kill, group->group_kill);
2856 bitmap_and_compl_into (gen, group->group_kill);
2857 }
2858 else
2859 {
2860 /* The groups are the same, just process the
2861 offsets. */
2862 HOST_WIDE_INT j;
2863 for (j = read_info->begin; j < read_info->end; j++)
2864 {
2865 int index = get_bitmap_index (group, j);
2866 if (index != 0)
2867 {
2868 if (kill)
2869 bitmap_set_bit (kill, index);
2870 bitmap_clear_bit (gen, index);
2871 }
2872 }
2873 }
2874 }
2875 else
2876 {
2877 /* The groups are different, if the alias sets
2878 conflict, clear the entire group. We only need
2879 to apply this test if the read_info is a cselib
2880 read. Anything with a constant base cannot alias
2881 something else with a different constant
2882 base. */
2883 if ((read_info->group_id < 0)
2884 && canon_true_dependence (group->base_mem,
2885 GET_MODE (group->base_mem),
2886 group->canon_base_addr,
2887 read_info->mem, NULL_RTX))
2888 {
2889 if (kill)
2890 bitmap_ior_into (kill, group->group_kill);
2891 bitmap_and_compl_into (gen, group->group_kill);
2892 }
2893 }
2894 }
2895 }
2896
2897 read_info = read_info->next;
2898 }
2899}
2900
2901
2902/* Return the insn in BB_INFO before the first wild read or if there
2903 are no wild reads in the block, return the last insn. */
2904
2905static insn_info_t
2906find_insn_before_first_wild_read (bb_info_t bb_info)
2907{
2908 insn_info_t insn_info = bb_info->last_insn;
2909 insn_info_t last_wild_read = NULL;
2910
2911 while (insn_info)
2912 {
2913 if (insn_info->wild_read)
2914 {
2915 last_wild_read = insn_info->prev_insn;
2916 /* Block starts with wild read. */
2917 if (!last_wild_read)
2918 return NULL;
2919 }
2920
2921 insn_info = insn_info->prev_insn;
2922 }
2923
2924 if (last_wild_read)
2925 return last_wild_read;
2926 else
2927 return bb_info->last_insn;
2928}
2929
2930
2931/* Scan the insns in BB_INFO starting at PTR and going to the top of
2932 the block in order to build the gen and kill sets for the block.
2933 We start at ptr which may be the last insn in the block or may be
2934 the first insn with a wild read. In the latter case we are able to
2935 skip the rest of the block because it just does not matter:
2936 anything that happens is hidden by the wild read. */
2937
2938static void
2939dse_step3_scan (basic_block bb)
2940{
2941 bb_info_t bb_info = bb_table[bb->index];
2942 insn_info_t insn_info;
2943
2944 insn_info = find_insn_before_first_wild_read (bb_info);
2945
2946 /* In the spill case or in the no_spill case if there is no wild
2947 read in the block, we will need a kill set. */
2948 if (insn_info == bb_info->last_insn)
2949 {
2950 if (bb_info->kill)
2951 bitmap_clear (bb_info->kill);
2952 else
2953 bb_info->kill = BITMAP_ALLOC (&dse_bitmap_obstack);
2954 }
2955 else
2956 if (bb_info->kill)
2957 BITMAP_FREE (bb_info->kill);
2958
2959 while (insn_info)
2960 {
2961 /* There may have been code deleted by the dce pass run before
2962 this phase. */
2963 if (insn_info->insn && INSN_P (insn_info->insn))
2964 {
2965 scan_stores (insn_info->store_rec, bb_info->gen, bb_info->kill);
2966 scan_reads (insn_info, bb_info->gen, bb_info->kill);
2967 }
2968
2969 insn_info = insn_info->prev_insn;
2970 }
2971}
2972
2973
2974/* Set the gen set of the exit block, and also any block with no
2975 successors that does not have a wild read. */
2976
2977static void
2978dse_step3_exit_block_scan (bb_info_t bb_info)
2979{
2980 /* The gen set is all 0's for the exit block except for the
2981 frame_pointer_group. */
2982
2983 if (stores_off_frame_dead_at_return)
2984 {
2985 unsigned int i;
2986 group_info *group;
2987
2988 FOR_EACH_VEC_ELT (rtx_group_vec, i, group)
2989 {
2990 if (group->process_globally && group->frame_related)
2991 bitmap_ior_into (bb_info->gen, group->group_kill);
2992 }
2993 }
2994}
2995
2996
2997/* Find all of the blocks that are not backwards reachable from the
2998 exit block or any block with no successors (BB). These are the
2999 infinite loops or infinite self loops. These blocks will still
3000 have their bits set in UNREACHABLE_BLOCKS. */
3001
3002static void
3003mark_reachable_blocks (sbitmap unreachable_blocks, basic_block bb)
3004{
3005 edge e;
3006 edge_iterator ei;
3007
3008 if (bitmap_bit_p (unreachable_blocks, bb->index))
3009 {
3010 bitmap_clear_bit (unreachable_blocks, bb->index);
3011 FOR_EACH_EDGE (e, ei, bb->preds)
3012 {
3013 mark_reachable_blocks (unreachable_blocks, e->src);
3014 }
3015 }
3016}
3017
3018/* Build the transfer functions for the function. */
3019
3020static void
3021dse_step3 ()
3022{
3023 basic_block bb;
3024 sbitmap_iterator sbi;
3025 bitmap all_ones = NULL;
3026 unsigned int i;
3027
3028 auto_sbitmap unreachable_blocks (last_basic_block_for_fn (cfun));
3029 bitmap_ones (unreachable_blocks);
3030
3031 FOR_ALL_BB_FN (bb, cfun)
3032 {
3033 bb_info_t bb_info = bb_table[bb->index];
3034 if (bb_info->gen)
3035 bitmap_clear (bb_info->gen);
3036 else
3037 bb_info->gen = BITMAP_ALLOC (&dse_bitmap_obstack);
3038
3039 if (bb->index == ENTRY_BLOCK)
3040 ;
3041 else if (bb->index == EXIT_BLOCK)
3042 dse_step3_exit_block_scan (bb_info);
3043 else
3044 dse_step3_scan (bb);
3045 if (EDGE_COUNT (bb->succs) == 0)
3046 mark_reachable_blocks (unreachable_blocks, bb);
3047
3048 /* If this is the second time dataflow is run, delete the old
3049 sets. */
3050 if (bb_info->in)
3051 BITMAP_FREE (bb_info->in);
3052 if (bb_info->out)
3053 BITMAP_FREE (bb_info->out);
3054 }
3055
3056 /* For any block in an infinite loop, we must initialize the out set
3057 to all ones. This could be expensive, but almost never occurs in
3058 practice. However, it is common in regression tests. */
3059 EXECUTE_IF_SET_IN_BITMAP (unreachable_blocks, 0, i, sbi)
3060 {
3061 if (bitmap_bit_p (all_blocks, i))
3062 {
3063 bb_info_t bb_info = bb_table[i];
3064 if (!all_ones)
3065 {
3066 unsigned int j;
3067 group_info *group;
3068
3069 all_ones = BITMAP_ALLOC (&dse_bitmap_obstack);
3070 FOR_EACH_VEC_ELT (rtx_group_vec, j, group)
3071 bitmap_ior_into (all_ones, group->group_kill);
3072 }
3073 if (!bb_info->out)
3074 {
3075 bb_info->out = BITMAP_ALLOC (&dse_bitmap_obstack);
3076 bitmap_copy (bb_info->out, all_ones);
3077 }
3078 }
3079 }
3080
3081 if (all_ones)
3082 BITMAP_FREE (all_ones);
3083}
3084
3085
3086
3087/*----------------------------------------------------------------------------
3088 Fourth step.
3089
3090 Solve the bitvector equations.
3091----------------------------------------------------------------------------*/
3092
3093
3094/* Confluence function for blocks with no successors. Create an out
3095 set from the gen set of the exit block. This block logically has
3096 the exit block as a successor. */
3097
3098
3099
3100static void
3101dse_confluence_0 (basic_block bb)
3102{
3103 bb_info_t bb_info = bb_table[bb->index];
3104
3105 if (bb->index == EXIT_BLOCK)
3106 return;
3107
3108 if (!bb_info->out)
3109 {
3110 bb_info->out = BITMAP_ALLOC (&dse_bitmap_obstack);
3111 bitmap_copy (bb_info->out, bb_table[EXIT_BLOCK]->gen);
3112 }
3113}
3114
3115/* Propagate the information from the in set of the dest of E to the
3116 out set of the src of E. If the various in or out sets are not
3117 there, that means they are all ones. */
3118
3119static bool
3120dse_confluence_n (edge e)
3121{
3122 bb_info_t src_info = bb_table[e->src->index];
3123 bb_info_t dest_info = bb_table[e->dest->index];
3124
3125 if (dest_info->in)
3126 {
3127 if (src_info->out)
3128 bitmap_and_into (src_info->out, dest_info->in);
3129 else
3130 {
3131 src_info->out = BITMAP_ALLOC (&dse_bitmap_obstack);
3132 bitmap_copy (src_info->out, dest_info->in);
3133 }
3134 }
3135 return true;
3136}
3137
3138
3139/* Propagate the info from the out to the in set of BB_INDEX's basic
3140 block. There are three cases:
3141
3142 1) The block has no kill set. In this case the kill set is all
3143 ones. It does not matter what the out set of the block is, none of
3144 the info can reach the top. The only thing that reaches the top is
3145 the gen set and we just copy the set.
3146
3147 2) There is a kill set but no out set and bb has successors. In
3148 this case we just return. Eventually an out set will be created and
3149 it is better to wait than to create a set of ones.
3150
3151 3) There is both a kill and out set. We apply the obvious transfer
3152 function.
3153*/
3154
3155static bool
3156dse_transfer_function (int bb_index)
3157{
3158 bb_info_t bb_info = bb_table[bb_index];
3159
3160 if (bb_info->kill)
3161 {
3162 if (bb_info->out)
3163 {
3164 /* Case 3 above. */
3165 if (bb_info->in)
3166 return bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3167 bb_info->out, bb_info->kill);
3168 else
3169 {
3170 bb_info->in = BITMAP_ALLOC (&dse_bitmap_obstack);
3171 bitmap_ior_and_compl (bb_info->in, bb_info->gen,
3172 bb_info->out, bb_info->kill);
3173 return true;
3174 }
3175 }
3176 else
3177 /* Case 2 above. */
3178 return false;
3179 }
3180 else
3181 {
3182 /* Case 1 above. If there is already an in set, nothing
3183 happens. */
3184 if (bb_info->in)
3185 return false;
3186 else
3187 {
3188 bb_info->in = BITMAP_ALLOC (&dse_bitmap_obstack);
3189 bitmap_copy (bb_info->in, bb_info->gen);
3190 return true;
3191 }
3192 }
3193}
3194
3195/* Solve the dataflow equations. */
3196
3197static void
3198dse_step4 (void)
3199{
3200 df_simple_dataflow (DF_BACKWARD, NULL, dse_confluence_0,
3201 dse_confluence_n, dse_transfer_function,
3202 all_blocks, df_get_postorder (DF_BACKWARD),
3203 df_get_n_blocks (DF_BACKWARD));
3204 if (dump_file && (dump_flags & TDF_DETAILS))
3205 {
3206 basic_block bb;
3207
3208 fprintf (dump_file, "\n\n*** Global dataflow info after analysis.\n");
3209 FOR_ALL_BB_FN (bb, cfun)
3210 {
3211 bb_info_t bb_info = bb_table[bb->index];
3212
3213 df_print_bb_index (bb, dump_file);
3214 if (bb_info->in)
3215 bitmap_print (dump_file, bb_info->in, " in: ", "\n");
3216 else
3217 fprintf (dump_file, " in: *MISSING*\n");
3218 if (bb_info->gen)
3219 bitmap_print (dump_file, bb_info->gen, " gen: ", "\n");
3220 else
3221 fprintf (dump_file, " gen: *MISSING*\n");
3222 if (bb_info->kill)
3223 bitmap_print (dump_file, bb_info->kill, " kill: ", "\n");
3224 else
3225 fprintf (dump_file, " kill: *MISSING*\n");
3226 if (bb_info->out)
3227 bitmap_print (dump_file, bb_info->out, " out: ", "\n");
3228 else
3229 fprintf (dump_file, " out: *MISSING*\n\n");
3230 }
3231 }
3232}
3233
3234
3235
3236/*----------------------------------------------------------------------------
3237 Fifth step.
3238
3239 Delete the stores that can only be deleted using the global information.
3240----------------------------------------------------------------------------*/
3241
3242
3243static void
3244dse_step5 (void)
3245{
3246 basic_block bb;
3247 FOR_EACH_BB_FN (bb, cfun)
3248 {
3249 bb_info_t bb_info = bb_table[bb->index];
3250 insn_info_t insn_info = bb_info->last_insn;
3251 bitmap v = bb_info->out;
3252
3253 while (insn_info)
3254 {
3255 bool deleted = false;
3256 if (dump_file && insn_info->insn)
3257 {
3258 fprintf (dump_file, "starting to process insn %d\n",
3259 INSN_UID (insn_info->insn));
3260 bitmap_print (dump_file, v, " v: ", "\n");
3261 }
3262
3263 /* There may have been code deleted by the dce pass run before
3264 this phase. */
3265 if (insn_info->insn
3266 && INSN_P (insn_info->insn)
3267 && (!insn_info->cannot_delete)
3268 && (!bitmap_empty_p (v)))
3269 {
3270 store_info *store_info = insn_info->store_rec;
3271
3272 /* Try to delete the current insn. */
3273 deleted = true;
3274
3275 /* Skip the clobbers. */
3276 while (!store_info->is_set)
3277 store_info = store_info->next;
3278
3279 HOST_WIDE_INT i;
3280 group_info *group_info = rtx_group_vec[store_info->group_id];
3281
3282 for (i = store_info->begin; i < store_info->end; i++)
3283 {
3284 int index = get_bitmap_index (group_info, i);
3285
3286 if (dump_file && (dump_flags & TDF_DETAILS))
3287 fprintf (dump_file, "i = %d, index = %d\n", (int)i, index);
3288 if (index == 0 || !bitmap_bit_p (v, index))
3289 {
3290 if (dump_file && (dump_flags & TDF_DETAILS))
3291 fprintf (dump_file, "failing at i = %d\n", (int)i);
3292 deleted = false;
3293 break;
3294 }
3295 }
3296 if (deleted)
3297 {
3298 if (dbg_cnt (dse)
3299 && check_for_inc_dec_1 (insn_info))
3300 {
3301 delete_insn (insn_info->insn);
3302 insn_info->insn = NULL;
3303 globally_deleted++;
3304 }
3305 }
3306 }
3307 /* We do want to process the local info if the insn was
3308 deleted. For instance, if the insn did a wild read, we
3309 no longer need to trash the info. */
3310 if (insn_info->insn
3311 && INSN_P (insn_info->insn)
3312 && (!deleted))
3313 {
3314 scan_stores (insn_info->store_rec, v, NULL);
3315 if (insn_info->wild_read)
3316 {
3317 if (dump_file && (dump_flags & TDF_DETAILS))
3318 fprintf (dump_file, "wild read\n");
3319 bitmap_clear (v);
3320 }
3321 else if (insn_info->read_rec
3322 || insn_info->non_frame_wild_read
3323 || insn_info->frame_read)
3324 {
3325 if (dump_file && (dump_flags & TDF_DETAILS))
3326 {
3327 if (!insn_info->non_frame_wild_read
3328 && !insn_info->frame_read)
3329 fprintf (dump_file, "regular read\n");
3330 if (insn_info->non_frame_wild_read)
3331 fprintf (dump_file, "non-frame wild read\n");
3332 if (insn_info->frame_read)
3333 fprintf (dump_file, "frame read\n");
3334 }
3335 scan_reads (insn_info, v, NULL);
3336 }
3337 }
3338
3339 insn_info = insn_info->prev_insn;
3340 }
3341 }
3342}
3343
3344
3345
3346/*----------------------------------------------------------------------------
3347 Sixth step.
3348
3349 Delete stores made redundant by earlier stores (which store the same
3350 value) that couldn't be eliminated.
3351----------------------------------------------------------------------------*/
3352
3353static void
3354dse_step6 (void)
3355{
3356 basic_block bb;
3357
3358 FOR_ALL_BB_FN (bb, cfun)
3359 {
3360 bb_info_t bb_info = bb_table[bb->index];
3361 insn_info_t insn_info = bb_info->last_insn;
3362
3363 while (insn_info)
3364 {
3365 /* There may have been code deleted by the dce pass run before
3366 this phase. */
3367 if (insn_info->insn
3368 && INSN_P (insn_info->insn)
3369 && !insn_info->cannot_delete)
3370 {
3371 store_info *s_info = insn_info->store_rec;
3372
3373 while (s_info && !s_info->is_set)
3374 s_info = s_info->next;
3375 if (s_info
3376 && s_info->redundant_reason
3377 && s_info->redundant_reason->insn
3378 && INSN_P (s_info->redundant_reason->insn))
3379 {
3380 rtx_insn *rinsn = s_info->redundant_reason->insn;
3381 if (dump_file && (dump_flags & TDF_DETAILS))
3382 fprintf (dump_file, "Locally deleting insn %d "
3383 "because insn %d stores the "
3384 "same value and couldn't be "
3385 "eliminated\n",
3386 INSN_UID (insn_info->insn),
3387 INSN_UID (rinsn));
3388 delete_dead_store_insn (insn_info);
3389 }
3390 }
3391 insn_info = insn_info->prev_insn;
3392 }
3393 }
3394}
3395
3396/*----------------------------------------------------------------------------
3397 Seventh step.
3398
3399 Destroy everything left standing.
3400----------------------------------------------------------------------------*/
3401
3402static void
3403dse_step7 (void)
3404{
3405 bitmap_obstack_release (&dse_bitmap_obstack);
3406 obstack_free (&dse_obstack, NULL);
3407
3408 end_alias_analysis ();
3409 free (bb_table);
3410 delete rtx_group_table;
3411 rtx_group_table = NULL;
3412 rtx_group_vec.release ();
3413 BITMAP_FREE (all_blocks);
3414 BITMAP_FREE (scratch);
3415
3416 rtx_store_info_pool.release ();
3417 read_info_type_pool.release ();
3418 insn_info_type_pool.release ();
3419 dse_bb_info_type_pool.release ();
3420 group_info_pool.release ();
3421 deferred_change_pool.release ();
3422}
3423
3424
3425/* -------------------------------------------------------------------------
3426 DSE
3427 ------------------------------------------------------------------------- */
3428
3429/* Callback for running pass_rtl_dse. */
3430
3431static unsigned int
3432rest_of_handle_dse (void)
3433{
3434 df_set_flags (DF_DEFER_INSN_RESCAN);
3435
3436 /* Need the notes since we must track live hardregs in the forwards
3437 direction. */
3438 df_note_add_problem ();
3439 df_analyze ();
3440
3441 dse_step0 ();
3442 dse_step1 ();
3443 dse_step2_init ();
3444 if (dse_step2 ())
3445 {
3446 df_set_flags (DF_LR_RUN_DCE);
3447 df_analyze ();
3448 if (dump_file && (dump_flags & TDF_DETAILS))
3449 fprintf (dump_file, "doing global processing\n");
3450 dse_step3 ();
3451 dse_step4 ();
3452 dse_step5 ();
3453 }
3454
3455 dse_step6 ();
3456 dse_step7 ();
3457
3458 if (dump_file)
3459 fprintf (dump_file, "dse: local deletions = %d, global deletions = %d\n",
3460 locally_deleted, globally_deleted);
3461
3462 /* DSE can eliminate potentially-trapping MEMs.
3463 Remove any EH edges associated with them. */
3464 if ((locally_deleted || globally_deleted)
3465 && cfun->can_throw_non_call_exceptions
3466 && purge_all_dead_edges ())
3467 cleanup_cfg (0);
3468
3469 return 0;
3470}
3471
3472namespace {
3473
3474const pass_data pass_data_rtl_dse1 =
3475{
3476 RTL_PASS, /* type */
3477 "dse1", /* name */
3478 OPTGROUP_NONE, /* optinfo_flags */
3479 TV_DSE1, /* tv_id */
3480 0, /* properties_required */
3481 0, /* properties_provided */
3482 0, /* properties_destroyed */
3483 0, /* todo_flags_start */
3484 TODO_df_finish, /* todo_flags_finish */
3485};
3486
3487class pass_rtl_dse1 : public rtl_opt_pass
3488{
3489public:
3490 pass_rtl_dse1 (gcc::context *ctxt)
3491 : rtl_opt_pass (pass_data_rtl_dse1, ctxt)
3492 {}
3493
3494 /* opt_pass methods: */
3495 virtual bool gate (function *)
3496 {
3497 return optimize > 0 && flag_dse && dbg_cnt (dse1);
3498 }
3499
3500 virtual unsigned int execute (function *) { return rest_of_handle_dse (); }
3501
3502}; // class pass_rtl_dse1
3503
3504} // anon namespace
3505
3506rtl_opt_pass *
3507make_pass_rtl_dse1 (gcc::context *ctxt)
3508{
3509 return new pass_rtl_dse1 (ctxt);
3510}
3511
3512namespace {
3513
3514const pass_data pass_data_rtl_dse2 =
3515{
3516 RTL_PASS, /* type */
3517 "dse2", /* name */
3518 OPTGROUP_NONE, /* optinfo_flags */
3519 TV_DSE2, /* tv_id */
3520 0, /* properties_required */
3521 0, /* properties_provided */
3522 0, /* properties_destroyed */
3523 0, /* todo_flags_start */
3524 TODO_df_finish, /* todo_flags_finish */
3525};
3526
3527class pass_rtl_dse2 : public rtl_opt_pass
3528{
3529public:
3530 pass_rtl_dse2 (gcc::context *ctxt)
3531 : rtl_opt_pass (pass_data_rtl_dse2, ctxt)
3532 {}
3533
3534 /* opt_pass methods: */
3535 virtual bool gate (function *)
3536 {
3537 return optimize > 0 && flag_dse && dbg_cnt (dse2);
3538 }
3539
3540 virtual unsigned int execute (function *) { return rest_of_handle_dse (); }
3541
3542}; // class pass_rtl_dse2
3543
3544} // anon namespace
3545
3546rtl_opt_pass *
3547make_pass_rtl_dse2 (gcc::context *ctxt)
3548{
3549 return new pass_rtl_dse2 (ctxt);
3550}
3551