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