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