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