re PR testsuite/40567 (Revision 149002 caused many failures)
[official-gcc.git] / gcc / store-motion.c
blob64260ac165f0d1799ef11c77906bde639b68544f
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.
5 This file is part of GCC.
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.
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.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "toplev.h"
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"
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. */
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.
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. */
71 struct st_expr
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;
93 /* Head of the list of load/store memory refs. */
94 static struct st_expr * store_motion_mems = NULL;
96 /* Hashtable for the load/store memory refs. */
97 static htab_t store_motion_mems_table = NULL;
99 /* These bitmaps will hold the local dataflow properties per basic block. */
100 static sbitmap *st_kill, *st_avloc, *st_antloc, *st_transp;
102 /* Nonzero for expressions which should be inserted on a specific edge. */
103 static sbitmap *st_insert_map;
105 /* Nonzero for expressions which should be deleted in a specific block. */
106 static sbitmap *st_delete_map;
108 /* Global holding the number of store expressions we are dealing with. */
109 static int num_stores;
111 /* Contains the edge_list returned by pre_edge_lcm. */
112 static struct edge_list *edge_list;
114 static hashval_t
115 pre_st_expr_hash (const void *p)
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);
122 static int
123 pre_st_expr_eq (const void *p1, const void *p2)
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);
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. */
133 static struct st_expr *
134 st_expr_entry (rtx x)
136 int do_not_record_p = 0;
137 struct st_expr * ptr;
138 unsigned int hash;
139 void **slot;
140 struct st_expr e;
142 hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
143 NULL, /*have_reg_qty=*/false);
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;
150 ptr = XNEW (struct st_expr);
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;
163 return ptr;
166 /* Free up an individual st_expr entry. */
168 static void
169 free_st_expr_entry (struct st_expr * ptr)
171 free_INSN_LIST_list (& ptr->antic_stores);
172 free_INSN_LIST_list (& ptr->avail_stores);
174 free (ptr);
177 /* Free up all memory associated with the st_expr list. */
179 static void
180 free_store_motion_mems (void)
182 if (store_motion_mems_table)
183 htab_delete (store_motion_mems_table);
184 store_motion_mems_table = NULL;
186 while (store_motion_mems)
188 struct st_expr * tmp = store_motion_mems;
189 store_motion_mems = store_motion_mems->next;
190 free_st_expr_entry (tmp);
192 store_motion_mems = NULL;
195 /* Assign each element of the list of mems a monotonically increasing value. */
197 static int
198 enumerate_store_motion_mems (void)
200 struct st_expr * ptr;
201 int n = 0;
203 for (ptr = store_motion_mems; ptr != NULL; ptr = ptr->next)
204 ptr->index = n++;
206 return n;
209 /* Return first item in the list. */
211 static inline struct st_expr *
212 first_st_expr (void)
214 return store_motion_mems;
217 /* Return the next item in the list after the specified one. */
219 static inline struct st_expr *
220 next_st_expr (struct st_expr * ptr)
222 return ptr->next;
225 /* Dump debugging info about the store_motion_mems list. */
227 static void
228 print_store_motion_mems (FILE * file)
230 struct st_expr * ptr;
232 fprintf (dump_file, "STORE_MOTION list of MEM exprs considered:\n");
234 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
236 fprintf (file, " Pattern (%3d): ", ptr->index);
238 print_rtl (file, ptr->pattern);
240 fprintf (file, "\n ANTIC stores : ");
242 if (ptr->antic_stores)
243 print_rtl (file, ptr->antic_stores);
244 else
245 fprintf (file, "(nil)");
247 fprintf (file, "\n AVAIL stores : ");
249 if (ptr->avail_stores)
250 print_rtl (file, ptr->avail_stores);
251 else
252 fprintf (file, "(nil)");
254 fprintf (file, "\n\n");
257 fprintf (file, "\n");
260 /* Return zero if some of the registers in list X are killed
261 due to set of registers in bitmap REGS_SET. */
263 static bool
264 store_ops_ok (const_rtx x, int *regs_set)
266 const_rtx reg;
268 for (; x; x = XEXP (x, 1))
270 reg = XEXP (x, 0);
271 if (regs_set[REGNO(reg)])
272 return false;
275 return true;
278 /* Helper for extract_mentioned_regs. */
280 static int
281 extract_mentioned_regs_1 (rtx *loc, void *data)
283 rtx *mentioned_regs_p = (rtx *) data;
285 if (REG_P (*loc))
286 *mentioned_regs_p = alloc_EXPR_LIST (0, *loc, *mentioned_regs_p);
288 return 0;
291 /* Returns a list of registers mentioned in X.
292 FIXME: A regset would be prettier and less expensive. */
294 static rtx
295 extract_mentioned_regs (rtx x)
297 rtx mentioned_regs = NULL;
298 for_each_rtx (&x, extract_mentioned_regs_1, &mentioned_regs);
299 return mentioned_regs;
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. */
306 static bool
307 load_kills_store (const_rtx x, const_rtx store_pattern, int after)
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);
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. */
321 static bool
322 find_loads (const_rtx x, const_rtx store_pattern, int after)
324 const char * fmt;
325 int i, j;
326 int ret = false;
328 if (!x)
329 return false;
331 if (GET_CODE (x) == SET)
332 x = SET_SRC (x);
334 if (MEM_P (x))
336 if (load_kills_store (x, store_pattern, after))
337 return true;
340 /* Recursively process the insn. */
341 fmt = GET_RTX_FORMAT (GET_CODE (x));
343 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
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);
351 return ret;
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. */
359 static inline bool
360 store_killed_in_pat (const_rtx x, const_rtx pat, int after)
362 if (GET_CODE (pat) == SET)
364 rtx dest = SET_DEST (pat);
366 if (GET_CODE (dest) == ZERO_EXTRACT)
367 dest = XEXP (dest, 0);
369 /* Check for memory stores to aliased objects. */
370 if (MEM_P (dest)
371 && !exp_equiv_p (dest, x, 0, true))
373 if (after)
375 if (output_dependence (dest, x))
376 return true;
378 else
380 if (output_dependence (x, dest))
381 return true;
386 if (find_loads (pat, x, after))
387 return true;
389 return false;
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. */
396 static bool
397 store_killed_in_insn (const_rtx x, const_rtx x_regs, const_rtx insn, int after)
399 const_rtx reg, base, note, pat;
401 if (!INSN_P (insn))
402 return false;
404 if (CALL_P (insn))
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;
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))
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;
423 return false;
426 pat = PATTERN (insn);
427 if (GET_CODE (pat) == SET)
429 if (store_killed_in_pat (x, pat, after))
430 return true;
432 else if (GET_CODE (pat) == PARALLEL)
434 int i;
436 for (i = 0; i < XVECLEN (pat, 0); i++)
437 if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
438 return true;
440 else if (find_loads (PATTERN (insn), x, after))
441 return true;
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);
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;
455 /* See if there are any aliased loads in the note. */
456 return find_loads (note, x, after);
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. */
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)
468 rtx last = BB_END (bb), act;
470 if (!store_ops_ok (x_regs, regs_set_after))
472 /* We do not know where it will happen. */
473 if (fail_insn)
474 *fail_insn = NULL_RTX;
475 return true;
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))
482 if (fail_insn)
483 *fail_insn = act;
484 return true;
487 return false;
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)
497 rtx first = BB_HEAD (bb);
499 if (!store_ops_ok (x_regs, regs_set_before))
500 return true;
502 for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
503 if (store_killed_in_insn (x, x_regs, insn, true))
504 return true;
506 return false;
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)
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.
526 The results are stored this way:
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).
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.
542 static void
543 find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after)
545 struct st_expr * ptr;
546 rtx dest, set, tmp;
547 int check_anticipatable, check_available;
548 basic_block bb = BLOCK_FOR_INSN (insn);
550 set = single_set (insn);
551 if (!set)
552 return;
554 dest = SET_DEST (set);
556 if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
557 || GET_MODE (dest) == BLKmode)
558 return;
560 if (side_effects_p (dest))
561 return;
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;
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;
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;
582 ptr = st_expr_entry (dest);
583 if (!ptr->pattern_regs)
584 ptr->pattern_regs = extract_mentioned_regs (dest);
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
593 tmp = XEXP (ptr->antic_stores, 0);
594 if (tmp != NULL_RTX
595 && BLOCK_FOR_INSN (tmp) != bb)
596 check_anticipatable = 1;
598 if (check_anticipatable)
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);
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
615 tmp = XEXP (ptr->avail_stores, 0);
616 if (BLOCK_FOR_INSN (tmp) != bb)
617 check_available = 1;
619 if (check_available)
621 /* Check that we have already reached the insn at that the check
622 failed last time. */
623 if (LAST_AVAIL_CHECK_FAILURE (ptr))
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;
632 else
633 check_available = store_killed_after (dest, ptr->pattern_regs, insn,
634 bb, regs_set_after,
635 &LAST_AVAIL_CHECK_FAILURE (ptr));
637 if (!check_available)
638 ptr->avail_stores = alloc_INSN_LIST (insn, ptr->avail_stores);
641 /* Find available and anticipatable stores. */
643 static int
644 compute_store_table (void)
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 ();
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);
663 /* Find all the stores we care about. */
664 FOR_EACH_BB (bb)
666 /* First compute the registers set in this block. */
667 FOR_BB_INSNS (bb, insn)
670 if (! INSN_P (insn))
671 continue;
673 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
674 last_set_in[DF_REF_REGNO (*def_rec)] = INSN_UID (insn);
677 /* Now find the stores. */
678 memset (already_set, 0, sizeof (int) * max_gcse_regno);
679 FOR_BB_INSNS (bb, insn)
681 if (! INSN_P (insn))
682 continue;
684 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
685 already_set[DF_REF_REGNO (*def_rec)] = INSN_UID (insn);
687 /* Now that we've marked regs, look for stores. */
688 find_moveable_store (insn, already_set, last_set_in);
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;
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
702 /* Clear temporary marks. */
703 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
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);
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)
718 if (! ptr->avail_stores)
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);
725 else
726 prev_next_ptr_ptr = &ptr->next;
729 ret = enumerate_store_motion_mems ();
731 if (dump_file)
732 print_store_motion_mems (dump_file);
734 free (last_set_in);
735 free (already_set);
736 return ret;
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
744 /* Insert an instruction at the beginning of a basic block, and update
745 the BB_HEAD if needed. */
747 static void
748 insert_insn_start_basic_block (rtx insn, basic_block bb)
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)
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);
764 insn = emit_insn_after_noloc (insn, prev, bb);
766 if (dump_file)
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");
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. */
779 static int
780 insert_store (struct st_expr * expr, edge e)
782 rtx reg, insn;
783 basic_block bb;
784 edge tmp;
785 edge_iterator ei;
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;
792 if (e->flags & EDGE_FAKE)
793 return 0;
795 reg = expr->reaching_reg;
796 insn = gen_move_insn (copy_rtx (expr->pattern), reg);
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))
805 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
807 gcc_assert (index != EDGE_INDEX_NO_EDGE);
808 if (! TEST_BIT (st_insert_map[index], expr->index))
809 break;
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)
816 FOR_EACH_EDGE (tmp, ei, e->dest->preds)
818 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
819 RESET_BIT (st_insert_map[index], expr->index);
821 insert_insn_start_basic_block (insn, bb);
822 return 0;
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));
829 insert_insn_on_edge (insn, e);
831 if (dump_file)
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");
839 return 1;
842 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
843 memory location in SMEXPR set in basic block BB.
845 This could be rather expensive. */
847 static void
848 remove_reachable_equiv_notes (basic_block bb, struct st_expr *smexpr)
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;
857 stack = XNEWVEC (edge_iterator, n_basic_blocks);
858 sp = 0;
859 ei = ei_start (bb->succs);
861 sbitmap_zero (visited);
863 act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
864 while (1)
866 if (!act)
868 if (!sp)
870 free (stack);
871 sbitmap_free (visited);
872 return;
874 act = ei_edge (stack[--sp]);
876 bb = act->dest;
878 if (bb == EXIT_BLOCK_PTR
879 || TEST_BIT (visited, bb->index))
881 if (!ei_end_p (ei))
882 ei_next (&ei);
883 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
884 continue;
886 SET_BIT (visited, bb->index);
888 if (TEST_BIT (st_antloc[bb->index], smexpr->index))
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);
896 else
897 last = NEXT_INSN (BB_END (bb));
899 for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
900 if (INSN_P (insn))
902 note = find_reg_equal_equiv_note (insn);
903 if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
904 continue;
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);
912 if (!ei_end_p (ei))
913 ei_next (&ei);
914 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
916 if (EDGE_COUNT (bb->succs) > 0)
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);
926 /* This routine will replace a store with a SET to a specified register. */
928 static void
929 replace_store_insn (rtx reg, rtx del, basic_block bb, struct st_expr *smexpr)
931 rtx insn, mem, note, set, ptr;
933 mem = smexpr->pattern;
934 insn = gen_move_insn (reg, SET_SRC (single_set (del)));
936 for (ptr = smexpr->antic_stores; ptr; ptr = XEXP (ptr, 1))
937 if (XEXP (ptr, 0) == del)
939 XEXP (ptr, 0) = insn;
940 break;
943 /* Move the notes from the deleted insn to its replacement. */
944 REG_NOTES (insn) = REG_NOTES (del);
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);
950 if (dump_file)
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");
960 delete_insn (del);
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 (INSN_P (insn))
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;
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);
982 remove_reachable_equiv_notes (bb, smexpr);
986 /* Delete a store, but copy the value that would have been stored into
987 the reaching_reg for later storing. */
989 static void
990 delete_store (struct st_expr * expr, basic_block bb)
992 rtx reg, i, del;
994 if (expr->reaching_reg == NULL_RTX)
995 expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
997 reg = expr->reaching_reg;
999 for (i = expr->avail_stores; i; i = XEXP (i, 1))
1001 del = XEXP (i, 0);
1002 if (BLOCK_FOR_INSN (del) == bb)
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;
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)
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 ();
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);
1028 st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores);
1029 sbitmap_vector_zero (st_antloc, last_basic_block);
1031 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1033 for (st = ptr->avail_stores; st != NULL; st = XEXP (st, 1))
1035 insn = XEXP (st, 0);
1036 bb = BLOCK_FOR_INSN (insn);
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))
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;
1050 SET_BIT (st_avloc[bb->index], ptr->index);
1053 for (st = ptr->antic_stores; st != NULL; st = XEXP (st, 1))
1055 insn = XEXP (st, 0);
1056 bb = BLOCK_FOR_INSN (insn);
1057 SET_BIT (st_antloc[bb->index], ptr->index);
1061 st_kill = sbitmap_vector_alloc (last_basic_block, num_stores);
1062 sbitmap_vector_zero (st_kill, last_basic_block);
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);
1068 FOR_EACH_BB (bb)
1070 FOR_BB_INSNS (bb, insn)
1071 if (INSN_P (insn))
1073 df_ref *def_rec;
1074 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1076 unsigned int ref_regno = DF_REF_REGNO (*def_rec);
1077 if (ref_regno < max_gcse_regno)
1078 regs_set_in_block[DF_REF_REGNO (*def_rec)] = 1;
1082 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1084 if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
1085 bb, regs_set_in_block, NULL))
1087 /* It should not be necessary to consider the expression
1088 killed if it is both anticipatable and available. */
1089 if (!TEST_BIT (st_antloc[bb->index], ptr->index)
1090 || !TEST_BIT (st_avloc[bb->index], ptr->index))
1091 SET_BIT (st_kill[bb->index], ptr->index);
1093 else
1094 SET_BIT (st_transp[bb->index], ptr->index);
1098 free (regs_set_in_block);
1100 if (dump_file)
1102 dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
1103 dump_sbitmap_vector (dump_file, "st_kill", "", st_kill, last_basic_block);
1104 dump_sbitmap_vector (dump_file, "st_transp", "", st_transp, last_basic_block);
1105 dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block);
1109 /* Free memory used by store motion. */
1111 static void
1112 free_store_memory (void)
1114 free_store_motion_mems ();
1116 if (st_avloc)
1117 sbitmap_vector_free (st_avloc);
1118 if (st_kill)
1119 sbitmap_vector_free (st_kill);
1120 if (st_transp)
1121 sbitmap_vector_free (st_transp);
1122 if (st_antloc)
1123 sbitmap_vector_free (st_antloc);
1124 if (st_insert_map)
1125 sbitmap_vector_free (st_insert_map);
1126 if (st_delete_map)
1127 sbitmap_vector_free (st_delete_map);
1129 st_avloc = st_kill = st_transp = st_antloc = NULL;
1130 st_insert_map = st_delete_map = NULL;
1133 /* Perform store motion. Much like gcse, except we move expressions the
1134 other way by looking at the flowgraph in reverse.
1135 Return non-zero if transformations are performed by the pass. */
1137 static int
1138 one_store_motion_pass (void)
1140 basic_block bb;
1141 int x;
1142 struct st_expr * ptr;
1143 int did_edge_inserts = 0;
1144 int n_stores_deleted = 0;
1145 int n_stores_created = 0;
1147 init_alias_analysis ();
1149 /* Find all the available and anticipatable stores. */
1150 num_stores = compute_store_table ();
1151 if (num_stores == 0)
1153 htab_delete (store_motion_mems_table);
1154 store_motion_mems_table = NULL;
1155 end_alias_analysis ();
1156 return 0;
1159 /* Now compute kill & transp vectors. */
1160 build_store_vectors ();
1161 add_noreturn_fake_exit_edges ();
1162 connect_infinite_loops_to_exit ();
1164 edge_list = pre_edge_rev_lcm (num_stores, st_transp, st_avloc,
1165 st_antloc, st_kill, &st_insert_map,
1166 &st_delete_map);
1168 /* Now we want to insert the new stores which are going to be needed. */
1169 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1171 /* If any of the edges we have above are abnormal, we can't move this
1172 store. */
1173 for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
1174 if (TEST_BIT (st_insert_map[x], ptr->index)
1175 && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
1176 break;
1178 if (x >= 0)
1180 if (dump_file != NULL)
1181 fprintf (dump_file,
1182 "Can't replace store %d: abnormal edge from %d to %d\n",
1183 ptr->index, INDEX_EDGE (edge_list, x)->src->index,
1184 INDEX_EDGE (edge_list, x)->dest->index);
1185 continue;
1188 /* Now we want to insert the new stores which are going to be needed. */
1190 FOR_EACH_BB (bb)
1191 if (TEST_BIT (st_delete_map[bb->index], ptr->index))
1193 delete_store (ptr, bb);
1194 n_stores_deleted++;
1197 for (x = 0; x < NUM_EDGES (edge_list); x++)
1198 if (TEST_BIT (st_insert_map[x], ptr->index))
1200 did_edge_inserts |= insert_store (ptr, INDEX_EDGE (edge_list, x));
1201 n_stores_created++;
1205 if (did_edge_inserts)
1206 commit_edge_insertions ();
1208 free_store_memory ();
1209 free_edge_list (edge_list);
1210 remove_fake_exit_edges ();
1211 end_alias_analysis ();
1213 if (dump_file)
1215 fprintf (dump_file, "STORE_MOTION of %s, %d basic blocks, ",
1216 current_function_name (), n_basic_blocks);
1217 fprintf (dump_file, "%d insns deleted, %d insns created\n",
1218 n_stores_deleted, n_stores_created);
1221 return (n_stores_deleted > 0 || n_stores_created > 0);
1225 static bool
1226 gate_rtl_store_motion (void)
1228 return optimize > 0 && flag_gcse_sm
1229 && !cfun->calls_setjmp
1230 && optimize_function_for_speed_p (cfun)
1231 && dbg_cnt (store_motion);
1234 static unsigned int
1235 execute_rtl_store_motion (void)
1237 delete_unreachable_blocks ();
1238 df_note_add_problem ();
1239 df_analyze ();
1240 flag_rerun_cse_after_global_opts |= one_store_motion_pass ();
1241 return 0;
1244 struct rtl_opt_pass pass_rtl_store_motion =
1247 RTL_PASS,
1248 "store_motion", /* name */
1249 gate_rtl_store_motion, /* gate */
1250 execute_rtl_store_motion, /* execute */
1251 NULL, /* sub */
1252 NULL, /* next */
1253 0, /* static_pass_number */
1254 TV_LSM, /* tv_id */
1255 PROP_cfglayout, /* properties_required */
1256 0, /* properties_provided */
1257 0, /* properties_destroyed */
1258 0, /* todo_flags_start */
1259 TODO_df_finish | TODO_verify_rtl_sharing |
1260 TODO_dump_func |
1261 TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */