OSDN Git Service

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