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