OSDN Git Service

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