OSDN Git Service

* store-motion.c: Many cleanups to make this pass a first-class
[pf3gnuchains/gcc-fork.git] / gcc / store-motion.c
1 /* Store motion via Lazy Code Motion on the reverse CFG.
2    Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
3    2006, 2007, 2008, 2009 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "toplev.h"
26
27 #include "rtl.h"
28 #include "tree.h"
29 #include "tm_p.h"
30 #include "regs.h"
31 #include "hard-reg-set.h"
32 #include "flags.h"
33 #include "real.h"
34 #include "insn-config.h"
35 #include "recog.h"
36 #include "basic-block.h"
37 #include "output.h"
38 #include "function.h"
39 #include "expr.h"
40 #include "except.h"
41 #include "ggc.h"
42 #include "params.h"
43 #include "intl.h"
44 #include "timevar.h"
45 #include "tree-pass.h"
46 #include "hashtab.h"
47 #include "df.h"
48 #include "dbgcnt.h"
49
50 /* This pass implements downward store motion.
51    As of May 1, 2009, the pass is not enabled by default on any target,
52    but bootstrap completes on ia64 and x86_64 with the pass enabled.  */
53
54 /* TODO:
55    - remove_reachable_equiv_notes is an incomprehensible pile of goo and
56      a compile time hog that needs a rewrite (maybe cache st_exprs to
57      invalidate REG_EQUAL/REG_EQUIV notes for?).
58    - pattern_regs in st_expr should be a regset (on its own obstack).
59    - antic_stores and avail_stores should be VECs instead of lists.
60    - store_motion_mems should be a VEC instead of a list.
61    - there should be an alloc pool for struct st_expr objects.
62    - investigate whether it is helpful to make the address of an st_expr
63      a cselib VALUE.
64    - when GIMPLE alias information is exported, the effectiveness of this
65      pass should be re-evaluated.
66 */
67
68 /* This is a list of store expressions (MEMs).  The structure is used
69    as an expression table to track stores which look interesting, and
70    might be moveable towards the exit block.  */
71
72 struct st_expr
73 {
74   /* Pattern of this mem.  */
75   rtx pattern;
76   /* List of registers mentioned by the mem.  */
77   rtx pattern_regs;
78   /* INSN list of stores that are locally anticipatable.  */
79   rtx antic_stores;
80   /* INSN list of stores that are locally available.  */
81   rtx avail_stores;
82   /* Next in the list.  */
83   struct st_expr * next;
84   /* Store ID in the dataflow bitmaps.  */
85   int index;
86   /* Hash value for the hash table.  */
87   unsigned int hash_index;
88   /* Register holding the stored expression when a store is moved.
89      This field is also used as a cache in find_moveable_store, see
90      LAST_AVAIL_CHECK_FAILURE below.  */
91   rtx reaching_reg;
92 };
93
94 /* Head of the list of load/store memory refs.  */
95 static struct st_expr * store_motion_mems = NULL;
96
97 /* Hashtable for the load/store memory refs.  */
98 static htab_t store_motion_mems_table = NULL;
99
100 /* These bitmaps will hold the local dataflow properties per basic block.  */
101 static sbitmap *st_kill, *st_avloc, *st_antloc, *st_transp;
102
103 /* Nonzero for expressions which should be inserted on a specific edge.  */
104 static sbitmap *st_insert_map;
105
106 /* Nonzero for expressions which should be deleted in a specific block.  */
107 static sbitmap *st_delete_map;
108
109 /* Global holding the number of store expressions we are dealing with.  */
110 static int num_stores;
111
112 /* Contains the edge_list returned by pre_edge_lcm.  */
113 static struct edge_list *edge_list;
114
115 static hashval_t
116 pre_st_expr_hash (const void *p)
117 {
118   int do_not_record_p = 0;
119   const struct st_expr *const x = (const struct st_expr *) p;
120   return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
121 }
122
123 static int
124 pre_st_expr_eq (const void *p1, const void *p2)
125 {
126   const struct st_expr *const ptr1 = (const struct st_expr *) p1,
127     *const ptr2 = (const struct st_expr *) p2;
128   return exp_equiv_p (ptr1->pattern, ptr2->pattern, 0, true);
129 }
130
131 /* This will search the st_expr list for a matching expression. If it
132    doesn't find one, we create one and initialize it.  */
133
134 static struct st_expr *
135 st_expr_entry (rtx x)
136 {
137   int do_not_record_p = 0;
138   struct st_expr * ptr;
139   unsigned int hash;
140   void **slot;
141   struct st_expr e;
142
143   hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
144                    NULL,  /*have_reg_qty=*/false);
145
146   e.pattern = x;
147   slot = htab_find_slot_with_hash (store_motion_mems_table, &e, hash, INSERT);
148   if (*slot)
149     return (struct st_expr *)*slot;
150
151   ptr = XNEW (struct st_expr);
152
153   ptr->next         = store_motion_mems;
154   ptr->pattern      = x;
155   ptr->pattern_regs = NULL_RTX;
156   ptr->antic_stores = NULL_RTX;
157   ptr->avail_stores = NULL_RTX;
158   ptr->reaching_reg = NULL_RTX;
159   ptr->index        = 0;
160   ptr->hash_index   = hash;
161   store_motion_mems = ptr;
162   *slot = ptr;
163
164   return ptr;
165 }
166
167 /* Free up an individual st_expr entry.  */
168
169 static void
170 free_st_expr_entry (struct st_expr * ptr)
171 {
172   free_INSN_LIST_list (& ptr->antic_stores);
173   free_INSN_LIST_list (& ptr->avail_stores);
174
175   free (ptr);
176 }
177
178 /* Free up all memory associated with the st_expr list.  */
179
180 static void
181 free_store_motion_mems (void)
182 {
183   if (store_motion_mems_table)
184     htab_delete (store_motion_mems_table);
185   store_motion_mems_table = NULL;
186
187   while (store_motion_mems)
188     {
189       struct st_expr * tmp = store_motion_mems;
190       store_motion_mems = store_motion_mems->next;
191       free_st_expr_entry (tmp);
192     }
193   store_motion_mems = NULL;
194 }
195
196 /* Assign each element of the list of mems a monotonically increasing value.  */
197
198 static int
199 enumerate_store_motion_mems (void)
200 {
201   struct st_expr * ptr;
202   int n = 0;
203
204   for (ptr = store_motion_mems; ptr != NULL; ptr = ptr->next)
205     ptr->index = n++;
206
207   return n;
208 }
209
210 /* Return first item in the list.  */
211
212 static inline struct st_expr *
213 first_st_expr (void)
214 {
215   return store_motion_mems;
216 }
217
218 /* Return the next item in the list after the specified one.  */
219
220 static inline struct st_expr *
221 next_st_expr (struct st_expr * ptr)
222 {
223   return ptr->next;
224 }
225
226 /* Dump debugging info about the store_motion_mems list.  */
227
228 static void
229 print_store_motion_mems (FILE * file)
230 {
231   struct st_expr * ptr;
232
233   fprintf (dump_file, "STORE_MOTION list of MEM exprs considered:\n");
234
235   for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
236     {
237       fprintf (file, "  Pattern (%3d): ", ptr->index);
238
239       print_rtl (file, ptr->pattern);
240
241       fprintf (file, "\n         ANTIC stores : ");
242
243       if (ptr->antic_stores)
244         print_rtl (file, ptr->antic_stores);
245       else
246         fprintf (file, "(nil)");
247
248       fprintf (file, "\n         AVAIL stores : ");
249
250       if (ptr->avail_stores)
251         print_rtl (file, ptr->avail_stores);
252       else
253         fprintf (file, "(nil)");
254
255       fprintf (file, "\n\n");
256     }
257
258   fprintf (file, "\n");
259 }
260 \f
261 /* Return zero if some of the registers in list X are killed
262    due to set of registers in bitmap REGS_SET.  */
263
264 static bool
265 store_ops_ok (const_rtx x, int *regs_set)
266 {
267   const_rtx reg;
268
269   for (; x; x = XEXP (x, 1))
270     {
271       reg = XEXP (x, 0);
272       if (regs_set[REGNO(reg)])
273         return false;
274     }
275
276   return true;
277 }
278
279 /* Helper for extract_mentioned_regs.  */
280  
281 static int
282 extract_mentioned_regs_1 (rtx *loc, void *data)
283 {
284   rtx *mentioned_regs_p = (rtx *) data;
285
286   if (REG_P (*loc))
287     *mentioned_regs_p = alloc_EXPR_LIST (0, *loc, *mentioned_regs_p);
288
289   return 0;
290 }
291
292 /* Returns a list of registers mentioned in X.
293    FIXME: A regset would be prettier and less expensive.  */
294
295 static rtx
296 extract_mentioned_regs (rtx x)
297 {
298   rtx mentioned_regs = NULL;
299   for_each_rtx (&x, extract_mentioned_regs_1, &mentioned_regs);
300   return mentioned_regs;
301 }
302
303 /* Check to see if the load X is aliased with STORE_PATTERN.
304    AFTER is true if we are checking the case when STORE_PATTERN occurs
305    after the X.  */
306
307 static bool
308 load_kills_store (const_rtx x, const_rtx store_pattern, int after)
309 {
310   if (after)
311     return anti_dependence (x, store_pattern);
312   else
313     return true_dependence (store_pattern, GET_MODE (store_pattern), x,
314                             rtx_addr_varies_p);
315 }
316
317 /* Go through the entire rtx X, looking for any loads which might alias
318    STORE_PATTERN.  Return true if found.
319    AFTER is true if we are checking the case when STORE_PATTERN occurs
320    after the insn X.  */
321
322 static bool
323 find_loads (const_rtx x, const_rtx store_pattern, int after)
324 {
325   const char * fmt;
326   int i, j;
327   int ret = false;
328
329   if (!x)
330     return false;
331
332   if (GET_CODE (x) == SET)
333     x = SET_SRC (x);
334
335   if (MEM_P (x))
336     {
337       if (load_kills_store (x, store_pattern, after))
338         return true;
339     }
340
341   /* Recursively process the insn.  */
342   fmt = GET_RTX_FORMAT (GET_CODE (x));
343
344   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
345     {
346       if (fmt[i] == 'e')
347         ret |= find_loads (XEXP (x, i), store_pattern, after);
348       else if (fmt[i] == 'E')
349         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
350           ret |= find_loads (XVECEXP (x, i, j), store_pattern, after);
351     }
352   return ret;
353 }
354
355 /* Go through pattern PAT looking for any loads which might kill the
356    store in X.  Return true if found.
357    AFTER is true if we are checking the case when loads kill X occurs
358    after the insn for PAT.  */
359
360 static inline bool
361 store_killed_in_pat (const_rtx x, const_rtx pat, int after)
362 {
363   if (GET_CODE (pat) == SET)
364     {
365       rtx dest = SET_DEST (pat);
366
367       if (GET_CODE (dest) == ZERO_EXTRACT)
368         dest = XEXP (dest, 0);
369
370       /* Check for memory stores to aliased objects.  */
371       if (MEM_P (dest)
372           && !exp_equiv_p (dest, x, 0, true))
373         {
374           if (after)
375             {
376               if (output_dependence (dest, x))
377                 return true;
378             }
379           else
380             {
381               if (output_dependence (x, dest))
382                 return true;
383             }
384         }
385     }
386
387   if (find_loads (pat, x, after))
388     return true;
389
390   return false;
391 }
392
393 /* Check if INSN kills the store pattern X (is aliased with it).
394    AFTER is true if we are checking the case when store X occurs
395    after the insn.  Return true if it does.  */
396
397 static bool
398 store_killed_in_insn (const_rtx x, const_rtx x_regs, const_rtx insn, int after)
399 {
400   const_rtx reg, base, note, pat;
401
402   if (!INSN_P (insn))
403     return false;
404
405   if (CALL_P (insn))
406     {
407       /* A normal or pure call might read from pattern,
408          but a const call will not.  */
409       if (!RTL_CONST_CALL_P (insn))
410         return true;
411
412       /* But even a const call reads its parameters.  Check whether the
413          base of some of registers used in mem is stack pointer.  */
414       for (reg = x_regs; reg; reg = XEXP (reg, 1))
415         {
416           base = find_base_term (XEXP (reg, 0));
417           if (!base
418               || (GET_CODE (base) == ADDRESS
419                   && GET_MODE (base) == Pmode
420                   && XEXP (base, 0) == stack_pointer_rtx))
421             return true;
422         }
423
424       return false;
425     }
426
427   pat = PATTERN (insn);
428   if (GET_CODE (pat) == SET)
429     {
430       if (store_killed_in_pat (x, pat, after))
431         return true;
432     }
433   else if (GET_CODE (pat) == PARALLEL)
434     {
435       int i;
436
437       for (i = 0; i < XVECLEN (pat, 0); i++)
438         if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
439           return true;
440     }
441   else if (find_loads (PATTERN (insn), x, after))
442     return true;
443
444   /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
445      location aliased with X, then this insn kills X.  */
446   note = find_reg_equal_equiv_note (insn);
447   if (! note)
448     return false;
449   note = XEXP (note, 0);
450
451   /* However, if the note represents a must alias rather than a may
452      alias relationship, then it does not kill X.  */
453   if (exp_equiv_p (note, x, 0, true))
454     return false;
455
456   /* See if there are any aliased loads in the note.  */
457   return find_loads (note, x, after);
458 }
459
460 /* Returns true if the expression X is loaded or clobbered on or after INSN
461    within basic block BB.  REGS_SET_AFTER is bitmap of registers set in
462    or after the insn.  X_REGS is list of registers mentioned in X. If the store
463    is killed, return the last insn in that it occurs in FAIL_INSN.  */
464
465 static bool
466 store_killed_after (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
467                     int *regs_set_after, rtx *fail_insn)
468 {
469   rtx last = BB_END (bb), act;
470
471   if (!store_ops_ok (x_regs, regs_set_after))
472     {
473       /* We do not know where it will happen.  */
474       if (fail_insn)
475         *fail_insn = NULL_RTX;
476       return true;
477     }
478
479   /* Scan from the end, so that fail_insn is determined correctly.  */
480   for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
481     if (store_killed_in_insn (x, x_regs, act, false))
482       {
483         if (fail_insn)
484           *fail_insn = act;
485         return true;
486       }
487
488   return false;
489 }
490
491 /* Returns true if the expression X is loaded or clobbered on or before INSN
492    within basic block BB. X_REGS is list of registers mentioned in X.
493    REGS_SET_BEFORE is bitmap of registers set before or in this insn.  */
494 static bool
495 store_killed_before (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
496                      int *regs_set_before)
497 {
498   rtx first = BB_HEAD (bb);
499
500   if (!store_ops_ok (x_regs, regs_set_before))
501     return true;
502
503   for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
504     if (store_killed_in_insn (x, x_regs, insn, true))
505       return true;
506
507   return false;
508 }
509
510 /* The last insn in the basic block that compute_store_table is processing,
511    where store_killed_after is true for X.
512    Since we go through the basic block from BB_END to BB_HEAD, this is
513    also the available store at the end of the basic block.  Therefore
514    this is in effect a cache, to avoid calling store_killed_after for
515    equivalent aliasing store expressions.
516    This value is only meaningful during the computation of the store
517    table.  We hi-jack the REACHING_REG field of struct st_expr to save
518    a bit of memory.  */
519 #define LAST_AVAIL_CHECK_FAILURE(x)     ((x)->reaching_reg)
520
521 /* Determine whether INSN is MEM store pattern that we will consider moving.
522    REGS_SET_BEFORE is bitmap of registers set before (and including) the
523    current insn, REGS_SET_AFTER is bitmap of registers set after (and
524    including) the insn in this basic block.  We must be passing through BB from
525    head to end, as we are using this fact to speed things up.
526
527    The results are stored this way:
528
529    -- the first anticipatable expression is added into ANTIC_STORES
530    -- if the processed expression is not anticipatable, NULL_RTX is added
531       there instead, so that we can use it as indicator that no further
532       expression of this type may be anticipatable
533    -- if the expression is available, it is added as head of AVAIL_STORES;
534       consequently, all of them but this head are dead and may be deleted.
535    -- if the expression is not available, the insn due to that it fails to be
536       available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
537
538    The things are complicated a bit by fact that there already may be stores
539    to the same MEM from other blocks; also caller must take care of the
540    necessary cleanup of the temporary markers after end of the basic block.
541    */
542
543 static void
544 find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after)
545 {
546   struct st_expr * ptr;
547   rtx dest, set, tmp;
548   int check_anticipatable, check_available;
549   basic_block bb = BLOCK_FOR_INSN (insn);
550
551   set = single_set (insn);
552   if (!set)
553     return;
554
555   dest = SET_DEST (set);
556
557   if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
558       || GET_MODE (dest) == BLKmode)
559     return;
560
561   if (side_effects_p (dest))
562     return;
563
564   /* If we are handling exceptions, we must be careful with memory references
565      that may trap. If we are not, the behavior is undefined, so we may just
566      continue.  */
567   if (flag_non_call_exceptions && may_trap_p (dest))
568     return;
569
570   /* Even if the destination cannot trap, the source may.  In this case we'd
571      need to handle updating the REG_EH_REGION note.  */
572   if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
573     return;
574
575   /* Make sure that the SET_SRC of this store insns can be assigned to
576      a register, or we will fail later on in replace_store_insn, which
577      assumes that we can do this.  But sometimes the target machine has
578      oddities like MEM read-modify-write instruction.  See for example
579      PR24257.  */
580   if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set)))
581     return;
582
583   ptr = st_expr_entry (dest);
584   if (!ptr->pattern_regs)
585     ptr->pattern_regs = extract_mentioned_regs (dest);
586
587   /* Do not check for anticipatability if we either found one anticipatable
588      store already, or tested for one and found out that it was killed.  */
589   check_anticipatable = 0;
590   if (!ptr->antic_stores)
591     check_anticipatable = 1;
592   else
593     {
594       tmp = XEXP (ptr->antic_stores, 0);
595       if (tmp != NULL_RTX
596           && BLOCK_FOR_INSN (tmp) != bb)
597         check_anticipatable = 1;
598     }
599   if (check_anticipatable)
600     {
601       if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before))
602         tmp = NULL_RTX;
603       else
604         tmp = insn;
605       ptr->antic_stores = alloc_INSN_LIST (tmp, ptr->antic_stores);
606     }
607
608   /* It is not necessary to check whether store is available if we did
609      it successfully before; if we failed before, do not bother to check
610      until we reach the insn that caused us to fail.  */
611   check_available = 0;
612   if (!ptr->avail_stores)
613     check_available = 1;
614   else
615     {
616       tmp = XEXP (ptr->avail_stores, 0);
617       if (BLOCK_FOR_INSN (tmp) != bb)
618         check_available = 1;
619     }
620   if (check_available)
621     {
622       /* Check that we have already reached the insn at that the check
623          failed last time.  */
624       if (LAST_AVAIL_CHECK_FAILURE (ptr))
625         {
626           for (tmp = BB_END (bb);
627                tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
628                tmp = PREV_INSN (tmp))
629             continue;
630           if (tmp == insn)
631             check_available = 0;
632         }
633       else
634         check_available = store_killed_after (dest, ptr->pattern_regs, insn,
635                                               bb, regs_set_after,
636                                               &LAST_AVAIL_CHECK_FAILURE (ptr));
637     }
638   if (!check_available)
639     ptr->avail_stores = alloc_INSN_LIST (insn, ptr->avail_stores);
640 }
641
642 /* Find available and anticipatable stores.  */
643
644 static int
645 compute_store_table (void)
646 {
647   int ret;
648   basic_block bb;
649   unsigned regno;
650   rtx insn, tmp;
651   df_ref *def_rec;
652   int *last_set_in, *already_set;
653   struct st_expr * ptr, **prev_next_ptr_ptr;
654   unsigned int max_gcse_regno = max_reg_num ();
655
656   store_motion_mems = NULL;
657   store_motion_mems_table = htab_create (13, pre_st_expr_hash,
658                                          pre_st_expr_eq, NULL);
659   last_set_in = XCNEWVEC (int, max_gcse_regno);
660   already_set = XNEWVEC (int, max_gcse_regno);
661
662   /* Find all the stores we care about.  */
663   FOR_EACH_BB (bb)
664     {
665       /* First compute the registers set in this block.  */
666       FOR_BB_INSNS (bb, insn)
667         {
668
669           if (! INSN_P (insn))
670             continue;
671
672           for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
673             last_set_in[DF_REF_REGNO (*def_rec)] = INSN_UID (insn);
674         }
675
676       /* Now find the stores.  */
677       memset (already_set, 0, sizeof (int) * max_gcse_regno);
678       FOR_BB_INSNS (bb, insn)
679         {
680           if (! INSN_P (insn))
681             continue;
682
683           for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
684             already_set[DF_REF_REGNO (*def_rec)] = INSN_UID (insn);
685
686           /* Now that we've marked regs, look for stores.  */
687           find_moveable_store (insn, already_set, last_set_in);
688
689           /* Unmark regs that are no longer set.  */
690           for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
691             if (last_set_in[DF_REF_REGNO (*def_rec)] == INSN_UID (insn))
692               last_set_in[DF_REF_REGNO (*def_rec)] = 0;
693         }
694
695 #ifdef ENABLE_CHECKING
696       /* last_set_in should now be all-zero.  */
697       for (regno = 0; regno < max_gcse_regno; regno++)
698         gcc_assert (!last_set_in[regno]);
699 #endif
700
701       /* Clear temporary marks.  */
702       for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
703         {
704           LAST_AVAIL_CHECK_FAILURE (ptr) = NULL_RTX;
705           if (ptr->antic_stores
706               && (tmp = XEXP (ptr->antic_stores, 0)) == NULL_RTX)
707             ptr->antic_stores = XEXP (ptr->antic_stores, 1);
708         }
709     }
710
711   /* Remove the stores that are not available anywhere, as there will
712      be no opportunity to optimize them.  */
713   for (ptr = store_motion_mems, prev_next_ptr_ptr = &store_motion_mems;
714        ptr != NULL;
715        ptr = *prev_next_ptr_ptr)
716     {
717       if (! ptr->avail_stores)
718         {
719           *prev_next_ptr_ptr = ptr->next;
720           htab_remove_elt_with_hash (store_motion_mems_table,
721                                      ptr, ptr->hash_index);
722           free_st_expr_entry (ptr);
723         }
724       else
725         prev_next_ptr_ptr = &ptr->next;
726     }
727
728   ret = enumerate_store_motion_mems ();
729
730   if (dump_file)
731     print_store_motion_mems (dump_file);
732
733   free (last_set_in);
734   free (already_set);
735   return ret;
736 }
737
738 /* In all code following after this, REACHING_REG has its original
739    meaning again.  Avoid confusion, and undef the accessor macro for
740    the temporary marks usage in compute_store_table.  */
741 #undef LAST_AVAIL_CHECK_FAILURE
742
743 /* Insert an instruction at the beginning of a basic block, and update
744    the BB_HEAD if needed.  */
745
746 static void
747 insert_insn_start_basic_block (rtx insn, basic_block bb)
748 {
749   /* Insert at start of successor block.  */
750   rtx prev = PREV_INSN (BB_HEAD (bb));
751   rtx before = BB_HEAD (bb);
752   while (before != 0)
753     {
754       if (! LABEL_P (before)
755           && !NOTE_INSN_BASIC_BLOCK_P (before))
756         break;
757       prev = before;
758       if (prev == BB_END (bb))
759         break;
760       before = NEXT_INSN (before);
761     }
762
763   insn = emit_insn_after_noloc (insn, prev, bb);
764
765   if (dump_file)
766     {
767       fprintf (dump_file, "STORE_MOTION  insert store at start of BB %d:\n",
768                bb->index);
769       print_inline_rtx (dump_file, insn, 6);
770       fprintf (dump_file, "\n");
771     }
772 }
773
774 /* This routine will insert a store on an edge. EXPR is the st_expr entry for
775    the memory reference, and E is the edge to insert it on.  Returns nonzero
776    if an edge insertion was performed.  */
777
778 static int
779 insert_store (struct st_expr * expr, edge e)
780 {
781   rtx reg, insn;
782   basic_block bb;
783   edge tmp;
784   edge_iterator ei;
785
786   /* We did all the deleted before this insert, so if we didn't delete a
787      store, then we haven't set the reaching reg yet either.  */
788   if (expr->reaching_reg == NULL_RTX)
789     return 0;
790
791   if (e->flags & EDGE_FAKE)
792     return 0;
793
794   reg = expr->reaching_reg;
795   insn = gen_move_insn (copy_rtx (expr->pattern), reg);
796
797   /* If we are inserting this expression on ALL predecessor edges of a BB,
798      insert it at the start of the BB, and reset the insert bits on the other
799      edges so we don't try to insert it on the other edges.  */
800   bb = e->dest;
801   FOR_EACH_EDGE (tmp, ei, e->dest->preds)
802     if (!(tmp->flags & EDGE_FAKE))
803       {
804         int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
805         
806         gcc_assert (index != EDGE_INDEX_NO_EDGE);
807         if (! TEST_BIT (st_insert_map[index], expr->index))
808           break;
809       }
810
811   /* If tmp is NULL, we found an insertion on every edge, blank the
812      insertion vector for these edges, and insert at the start of the BB.  */
813   if (!tmp && bb != EXIT_BLOCK_PTR)
814     {
815       FOR_EACH_EDGE (tmp, ei, e->dest->preds)
816         {
817           int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
818           RESET_BIT (st_insert_map[index], expr->index);
819         }
820       insert_insn_start_basic_block (insn, bb);
821       return 0;
822     }
823
824   /* We can't put stores in the front of blocks pointed to by abnormal
825      edges since that may put a store where one didn't used to be.  */
826   gcc_assert (!(e->flags & EDGE_ABNORMAL));
827
828   insert_insn_on_edge (insn, e);
829
830   if (dump_file)
831     {
832       fprintf (dump_file, "STORE_MOTION  insert insn on edge (%d, %d):\n",
833                e->src->index, e->dest->index);
834       print_inline_rtx (dump_file, insn, 6);
835       fprintf (dump_file, "\n");
836     }
837
838   return 1;
839 }
840
841 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
842    memory location in SMEXPR set in basic block BB.
843
844    This could be rather expensive.  */
845
846 static void
847 remove_reachable_equiv_notes (basic_block bb, struct st_expr *smexpr)
848 {
849   edge_iterator *stack, ei;
850   int sp;
851   edge act;
852   sbitmap visited = sbitmap_alloc (last_basic_block);
853   rtx last, insn, note;
854   rtx mem = smexpr->pattern;
855
856   stack = XNEWVEC (edge_iterator, n_basic_blocks);
857   sp = 0;
858   ei = ei_start (bb->succs);
859
860   sbitmap_zero (visited);
861
862   act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
863   while (1)
864     {
865       if (!act)
866         {
867           if (!sp)
868             {
869               free (stack);
870               sbitmap_free (visited);
871               return;
872             }
873           act = ei_edge (stack[--sp]);
874         }
875       bb = act->dest;
876
877       if (bb == EXIT_BLOCK_PTR
878           || TEST_BIT (visited, bb->index))
879         {
880           if (!ei_end_p (ei))
881               ei_next (&ei);
882           act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
883           continue;
884         }
885       SET_BIT (visited, bb->index);
886
887       if (TEST_BIT (st_antloc[bb->index], smexpr->index))
888         {
889           for (last = smexpr->antic_stores;
890                BLOCK_FOR_INSN (XEXP (last, 0)) != bb;
891                last = XEXP (last, 1))
892             continue;
893           last = XEXP (last, 0);
894         }
895       else
896         last = NEXT_INSN (BB_END (bb));
897
898       for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
899         if (INSN_P (insn))
900           {
901             note = find_reg_equal_equiv_note (insn);
902             if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
903               continue;
904
905             if (dump_file)
906               fprintf (dump_file, "STORE_MOTION  drop REG_EQUAL note at insn %d:\n",
907                        INSN_UID (insn));
908             remove_note (insn, note);
909           }
910
911       if (!ei_end_p (ei))
912         ei_next (&ei);
913       act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
914
915       if (EDGE_COUNT (bb->succs) > 0)
916         {
917           if (act)
918             stack[sp++] = ei;
919           ei = ei_start (bb->succs);
920           act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
921         }
922     }
923 }
924
925 /* This routine will replace a store with a SET to a specified register.  */
926
927 static void
928 replace_store_insn (rtx reg, rtx del, basic_block bb, struct st_expr *smexpr)
929 {
930   rtx insn, mem, note, set, ptr;
931
932   mem = smexpr->pattern;
933   insn = gen_move_insn (reg, SET_SRC (single_set (del)));
934
935   for (ptr = smexpr->antic_stores; ptr; ptr = XEXP (ptr, 1))
936     if (XEXP (ptr, 0) == del)
937       {
938         XEXP (ptr, 0) = insn;
939         break;
940       }
941
942   /* Move the notes from the deleted insn to its replacement.  */
943   REG_NOTES (insn) = REG_NOTES (del);
944
945   /* Emit the insn AFTER all the notes are transferred.
946      This is cheaper since we avoid df rescanning for the note change.  */
947   insn = emit_insn_after (insn, del);
948
949   if (dump_file)
950     {
951       fprintf (dump_file,
952                "STORE_MOTION  delete insn in BB %d:\n      ", bb->index);
953       print_inline_rtx (dump_file, del, 6);
954       fprintf (dump_file, "\nSTORE_MOTION  replaced with insn:\n      ");
955       print_inline_rtx (dump_file, insn, 6);
956       fprintf (dump_file, "\n");
957     }
958
959   delete_insn (del);
960
961   /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
962      they are no longer accurate provided that they are reached by this
963      definition, so drop them.  */
964   for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn))
965     if (INSN_P (insn))
966       {
967         set = single_set (insn);
968         if (!set)
969           continue;
970         if (exp_equiv_p (SET_DEST (set), mem, 0, true))
971           return;
972         note = find_reg_equal_equiv_note (insn);
973         if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
974           continue;
975
976         if (dump_file)
977           fprintf (dump_file, "STORE_MOTION  drop REG_EQUAL note at insn %d:\n",
978                    INSN_UID (insn));
979         remove_note (insn, note);
980       }
981   remove_reachable_equiv_notes (bb, smexpr);
982 }
983
984
985 /* Delete a store, but copy the value that would have been stored into
986    the reaching_reg for later storing.  */
987
988 static void
989 delete_store (struct st_expr * expr, basic_block bb)
990 {
991   rtx reg, i, del;
992
993   if (expr->reaching_reg == NULL_RTX)
994     expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
995
996   reg = expr->reaching_reg;
997
998   for (i = expr->avail_stores; i; i = XEXP (i, 1))
999     {
1000       del = XEXP (i, 0);
1001       if (BLOCK_FOR_INSN (del) == bb)
1002         {
1003           /* We know there is only one since we deleted redundant
1004              ones during the available computation.  */
1005           replace_store_insn (reg, del, bb, expr);
1006           break;
1007         }
1008     }
1009 }
1010
1011 /* Fill in available, anticipatable, transparent and kill vectors in
1012    STORE_DATA, based on lists of available and anticipatable stores.  */
1013 static void
1014 build_store_vectors (void)
1015 {
1016   basic_block bb;
1017   int *regs_set_in_block;
1018   rtx insn, st;
1019   struct st_expr * ptr;
1020   unsigned int max_gcse_regno = max_reg_num ();
1021
1022   /* Build the gen_vector. This is any store in the table which is not killed
1023      by aliasing later in its block.  */
1024   st_avloc = sbitmap_vector_alloc (last_basic_block, num_stores);
1025   sbitmap_vector_zero (st_avloc, last_basic_block);
1026
1027   st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores);
1028   sbitmap_vector_zero (st_antloc, last_basic_block);
1029
1030   for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1031     {
1032       for (st = ptr->avail_stores; st != NULL; st = XEXP (st, 1))
1033         {
1034           insn = XEXP (st, 0);
1035           bb = BLOCK_FOR_INSN (insn);
1036
1037           /* If we've already seen an available expression in this block,
1038              we can delete this one (It occurs earlier in the block). We'll
1039              copy the SRC expression to an unused register in case there
1040              are any side effects.  */
1041           if (TEST_BIT (st_avloc[bb->index], ptr->index))
1042             {
1043               rtx r = gen_reg_rtx_and_attrs (ptr->pattern);
1044               if (dump_file)
1045                 fprintf (dump_file, "Removing redundant store:\n");
1046               replace_store_insn (r, XEXP (st, 0), bb, ptr);
1047               continue;
1048             }
1049           SET_BIT (st_avloc[bb->index], ptr->index);
1050         }
1051
1052       for (st = ptr->antic_stores; st != NULL; st = XEXP (st, 1))
1053         {
1054           insn = XEXP (st, 0);
1055           bb = BLOCK_FOR_INSN (insn);
1056           SET_BIT (st_antloc[bb->index], ptr->index);
1057         }
1058     }
1059
1060   st_kill = sbitmap_vector_alloc (last_basic_block, num_stores);
1061   sbitmap_vector_zero (st_kill, last_basic_block);
1062
1063   st_transp = sbitmap_vector_alloc (last_basic_block, num_stores);
1064   sbitmap_vector_zero (st_transp, last_basic_block);
1065   regs_set_in_block = XNEWVEC (int, max_gcse_regno);
1066
1067   FOR_EACH_BB (bb)
1068     {
1069       FOR_BB_INSNS (bb, insn)
1070         if (INSN_P (insn))
1071           {
1072             df_ref *def_rec;
1073             for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1074               {
1075                 unsigned int ref_regno = DF_REF_REGNO (*def_rec);
1076                 if (ref_regno < max_gcse_regno)
1077                   regs_set_in_block[DF_REF_REGNO (*def_rec)] = 1;
1078               }
1079           }
1080
1081       for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1082         {
1083           if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
1084                                   bb, regs_set_in_block, NULL))
1085             {
1086               /* It should not be necessary to consider the expression
1087                  killed if it is both anticipatable and available.  */
1088               if (!TEST_BIT (st_antloc[bb->index], ptr->index)
1089                   || !TEST_BIT (st_avloc[bb->index], ptr->index))
1090                 SET_BIT (st_kill[bb->index], ptr->index);
1091             }
1092           else
1093             SET_BIT (st_transp[bb->index], ptr->index);
1094         }
1095     }
1096
1097   free (regs_set_in_block);
1098
1099   if (dump_file)
1100     {
1101       dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
1102       dump_sbitmap_vector (dump_file, "st_kill", "", st_kill, last_basic_block);
1103       dump_sbitmap_vector (dump_file, "st_transp", "", st_transp, last_basic_block);
1104       dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block);
1105     }
1106 }
1107
1108 /* Free memory used by store motion.  */
1109
1110 static void
1111 free_store_memory (void)
1112 {
1113   free_store_motion_mems ();
1114
1115   if (st_avloc)
1116     sbitmap_vector_free (st_avloc);
1117   if (st_kill)
1118     sbitmap_vector_free (st_kill);
1119   if (st_transp)
1120     sbitmap_vector_free (st_transp);
1121   if (st_antloc)
1122     sbitmap_vector_free (st_antloc);
1123   if (st_insert_map)
1124     sbitmap_vector_free (st_insert_map);
1125   if (st_delete_map)
1126     sbitmap_vector_free (st_delete_map);
1127
1128   st_avloc = st_kill = st_transp = st_antloc = NULL;
1129   st_insert_map = st_delete_map = NULL;
1130 }
1131
1132 /* Perform store motion. Much like gcse, except we move expressions the
1133    other way by looking at the flowgraph in reverse.
1134    Return non-zero if transformations are performed by the pass.  */
1135
1136 static int
1137 one_store_motion_pass (void)
1138 {
1139   basic_block bb;
1140   int x;
1141   struct st_expr * ptr;
1142   int did_edge_inserts = 0;
1143   int n_stores_deleted = 0;
1144   int n_stores_created = 0;
1145
1146   init_alias_analysis ();
1147
1148   /* Find all the available and anticipatable stores.  */
1149   num_stores = compute_store_table ();
1150   if (num_stores == 0)
1151     {
1152       htab_delete (store_motion_mems_table);
1153       store_motion_mems_table = NULL;
1154       end_alias_analysis ();
1155       return 0;
1156     }
1157
1158   /* Now compute kill & transp vectors.  */
1159   build_store_vectors ();
1160   add_noreturn_fake_exit_edges ();
1161   connect_infinite_loops_to_exit ();
1162
1163   edge_list = pre_edge_rev_lcm (num_stores, st_transp, st_avloc,
1164                                 st_antloc, st_kill, &st_insert_map,
1165                                 &st_delete_map);
1166
1167   /* Now we want to insert the new stores which are going to be needed.  */
1168   for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1169     {
1170       /* If any of the edges we have above are abnormal, we can't move this
1171          store.  */
1172       for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
1173         if (TEST_BIT (st_insert_map[x], ptr->index)
1174             && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
1175           break;
1176
1177       if (x >= 0)
1178         {
1179           if (dump_file != NULL)
1180             fprintf (dump_file,
1181                      "Can't replace store %d: abnormal edge from %d to %d\n",
1182                      ptr->index, INDEX_EDGE (edge_list, x)->src->index,
1183                      INDEX_EDGE (edge_list, x)->dest->index);
1184           continue;
1185         }
1186                       
1187       /* Now we want to insert the new stores which are going to be needed.  */
1188
1189       FOR_EACH_BB (bb)
1190         if (TEST_BIT (st_delete_map[bb->index], ptr->index))
1191           {
1192             delete_store (ptr, bb);
1193             n_stores_deleted++;
1194           }
1195
1196       for (x = 0; x < NUM_EDGES (edge_list); x++)
1197         if (TEST_BIT (st_insert_map[x], ptr->index))
1198           {
1199             did_edge_inserts |= insert_store (ptr, INDEX_EDGE (edge_list, x));
1200             n_stores_created++;
1201           }
1202     }
1203
1204   if (did_edge_inserts)
1205     commit_edge_insertions ();
1206
1207   free_store_memory ();
1208   free_edge_list (edge_list);
1209   remove_fake_exit_edges ();
1210   end_alias_analysis ();
1211
1212   if (dump_file)
1213     {
1214       fprintf (dump_file, "STORE_MOTION of %s, %d basic blocks, ",
1215                current_function_name (), n_basic_blocks);
1216       fprintf (dump_file, "%d insns deleted, %d insns created\n",
1217                n_stores_deleted, n_stores_created);
1218     }
1219
1220   return (n_stores_deleted > 0 || n_stores_created > 0);
1221 }
1222
1223 \f
1224 static bool
1225 gate_rtl_store_motion (void)
1226 {
1227   return optimize > 0 && flag_gcse_sm
1228     && !cfun->calls_setjmp
1229     && optimize_function_for_speed_p (cfun)
1230     && dbg_cnt (store_motion);
1231 }
1232
1233 static unsigned int
1234 execute_rtl_store_motion (void)
1235 {
1236   delete_unreachable_blocks ();
1237   df_note_add_problem ();
1238   df_analyze ();
1239   flag_rerun_cse_after_global_opts |= one_store_motion_pass ();
1240   return 0;
1241 }
1242
1243 struct rtl_opt_pass pass_rtl_store_motion =
1244 {
1245  {
1246   RTL_PASS,
1247   "store_motion",                       /* name */
1248   gate_rtl_store_motion,                /* gate */   
1249   execute_rtl_store_motion,             /* execute */       
1250   NULL,                                 /* sub */
1251   NULL,                                 /* next */
1252   0,                                    /* static_pass_number */
1253   TV_LSM,                               /* tv_id */
1254   PROP_cfglayout,                       /* properties_required */
1255   0,                                    /* properties_provided */
1256   0,                                    /* properties_destroyed */
1257   0,                                    /* todo_flags_start */
1258   TODO_df_finish | TODO_verify_rtl_sharing |
1259   TODO_dump_func |
1260   TODO_verify_flow | TODO_ggc_collect   /* todo_flags_finish */
1261  }
1262 };
1263