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