OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [dse.c] - Blame information for rev 429

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.