gcc/
[official-gcc.git] / gcc / store-motion.c
blob530766f800d2e6075800ef0a9909642c3da5f18a
1 /* Store motion via Lazy Code Motion on the reverse CFG.
2 Copyright (C) 1997-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
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"
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"
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. */
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.
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. */
96 struct st_expr
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;
118 /* Head of the list of load/store memory refs. */
119 static struct st_expr * store_motion_mems = NULL;
121 /* These bitmaps will hold the local dataflow properties per basic block. */
122 static sbitmap *st_kill, *st_avloc, *st_antloc, *st_transp;
124 /* Nonzero for expressions which should be inserted on a specific edge. */
125 static sbitmap *st_insert_map;
127 /* Nonzero for expressions which should be deleted in a specific block. */
128 static sbitmap *st_delete_map;
130 /* Global holding the number of store expressions we are dealing with. */
131 static int num_stores;
133 /* Contains the edge_list returned by pre_edge_lcm. */
134 static struct edge_list *edge_list;
136 /* Hashtable helpers. */
138 struct st_expr_hasher : typed_noop_remove <st_expr>
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 *);
146 inline hashval_t
147 st_expr_hasher::hash (const value_type *x)
149 int do_not_record_p = 0;
150 return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
153 inline bool
154 st_expr_hasher::equal (const value_type *ptr1, const compare_type *ptr2)
156 return exp_equiv_p (ptr1->pattern, ptr2->pattern, 0, true);
159 /* Hashtable for the load/store memory refs. */
160 static hash_table<st_expr_hasher> *store_motion_mems_table;
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. */
165 static struct st_expr *
166 st_expr_entry (rtx x)
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;
174 hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
175 NULL, /*have_reg_qty=*/false);
177 e.pattern = x;
178 slot = store_motion_mems_table->find_slot_with_hash (&e, hash, INSERT);
179 if (*slot)
180 return *slot;
182 ptr = XNEW (struct st_expr);
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;
195 return ptr;
198 /* Free up an individual st_expr entry. */
200 static void
201 free_st_expr_entry (struct st_expr * ptr)
203 free_INSN_LIST_list (& ptr->antic_stores);
204 free_INSN_LIST_list (& ptr->avail_stores);
206 free (ptr);
209 /* Free up all memory associated with the st_expr list. */
211 static void
212 free_store_motion_mems (void)
214 delete store_motion_mems_table;
215 store_motion_mems_table = NULL;
217 while (store_motion_mems)
219 struct st_expr * tmp = store_motion_mems;
220 store_motion_mems = store_motion_mems->next;
221 free_st_expr_entry (tmp);
223 store_motion_mems = NULL;
226 /* Assign each element of the list of mems a monotonically increasing value. */
228 static int
229 enumerate_store_motion_mems (void)
231 struct st_expr * ptr;
232 int n = 0;
234 for (ptr = store_motion_mems; ptr != NULL; ptr = ptr->next)
235 ptr->index = n++;
237 return n;
240 /* Return first item in the list. */
242 static inline struct st_expr *
243 first_st_expr (void)
245 return store_motion_mems;
248 /* Return the next item in the list after the specified one. */
250 static inline struct st_expr *
251 next_st_expr (struct st_expr * ptr)
253 return ptr->next;
256 /* Dump debugging info about the store_motion_mems list. */
258 static void
259 print_store_motion_mems (FILE * file)
261 struct st_expr * ptr;
263 fprintf (dump_file, "STORE_MOTION list of MEM exprs considered:\n");
265 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
267 fprintf (file, " Pattern (%3d): ", ptr->index);
269 print_rtl (file, ptr->pattern);
271 fprintf (file, "\n ANTIC stores : ");
273 if (ptr->antic_stores)
274 print_rtl (file, ptr->antic_stores);
275 else
276 fprintf (file, "(nil)");
278 fprintf (file, "\n AVAIL stores : ");
280 if (ptr->avail_stores)
281 print_rtl (file, ptr->avail_stores);
282 else
283 fprintf (file, "(nil)");
285 fprintf (file, "\n\n");
288 fprintf (file, "\n");
291 /* Return zero if some of the registers in list X are killed
292 due to set of registers in bitmap REGS_SET. */
294 static bool
295 store_ops_ok (const_rtx x, int *regs_set)
297 const_rtx reg;
299 for (; x; x = XEXP (x, 1))
301 reg = XEXP (x, 0);
302 if (regs_set[REGNO (reg)])
303 return false;
306 return true;
309 /* Returns a list of registers mentioned in X.
310 FIXME: A regset would be prettier and less expensive. */
312 static rtx
313 extract_mentioned_regs (rtx x)
315 rtx mentioned_regs = NULL;
316 subrtx_var_iterator::array_type array;
317 FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
319 rtx x = *iter;
320 if (REG_P (x))
321 mentioned_regs = alloc_EXPR_LIST (0, x, mentioned_regs);
323 return mentioned_regs;
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. */
330 static bool
331 load_kills_store (const_rtx x, const_rtx store_pattern, int after)
333 if (after)
334 return anti_dependence (x, store_pattern);
335 else
336 return true_dependence (store_pattern, GET_MODE (store_pattern), x);
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. */
344 static bool
345 find_loads (const_rtx x, const_rtx store_pattern, int after)
347 const char * fmt;
348 int i, j;
349 int ret = false;
351 if (!x)
352 return false;
354 if (GET_CODE (x) == SET)
355 x = SET_SRC (x);
357 if (MEM_P (x))
359 if (load_kills_store (x, store_pattern, after))
360 return true;
363 /* Recursively process the insn. */
364 fmt = GET_RTX_FORMAT (GET_CODE (x));
366 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
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);
374 return ret;
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. */
382 static inline bool
383 store_killed_in_pat (const_rtx x, const_rtx pat, int after)
385 if (GET_CODE (pat) == SET)
387 rtx dest = SET_DEST (pat);
389 if (GET_CODE (dest) == ZERO_EXTRACT)
390 dest = XEXP (dest, 0);
392 /* Check for memory stores to aliased objects. */
393 if (MEM_P (dest)
394 && !exp_equiv_p (dest, x, 0, true))
396 if (after)
398 if (output_dependence (dest, x))
399 return true;
401 else
403 if (output_dependence (x, dest))
404 return true;
409 if (find_loads (pat, x, after))
410 return true;
412 return false;
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. */
419 static bool
420 store_killed_in_insn (const_rtx x, const_rtx x_regs, const rtx_insn *insn, int after)
422 const_rtx reg, note, pat;
424 if (! NONDEBUG_INSN_P (insn))
425 return false;
427 if (CALL_P (insn))
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;
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;
440 return false;
443 pat = PATTERN (insn);
444 if (GET_CODE (pat) == SET)
446 if (store_killed_in_pat (x, pat, after))
447 return true;
449 else if (GET_CODE (pat) == PARALLEL)
451 int i;
453 for (i = 0; i < XVECLEN (pat, 0); i++)
454 if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
455 return true;
457 else if (find_loads (PATTERN (insn), x, after))
458 return true;
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);
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;
472 /* See if there are any aliased loads in the note. */
473 return find_loads (note, x, after);
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. */
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)
486 rtx_insn *last = BB_END (bb), *act;
488 if (!store_ops_ok (x_regs, regs_set_after))
490 /* We do not know where it will happen. */
491 if (fail_insn)
492 *fail_insn = NULL_RTX;
493 return true;
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))
500 if (fail_insn)
501 *fail_insn = act;
502 return true;
505 return false;
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)
515 rtx_insn *first = BB_HEAD (bb);
517 if (!store_ops_ok (x_regs, regs_set_before))
518 return true;
520 for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
521 if (store_killed_in_insn (x, x_regs, insn, true))
522 return true;
524 return false;
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)
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.
544 The results are stored this way:
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).
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.
560 static void
561 find_moveable_store (rtx_insn *insn, int *regs_set_before, int *regs_set_after)
563 struct st_expr * ptr;
564 rtx dest, set;
565 int check_anticipatable, check_available;
566 basic_block bb = BLOCK_FOR_INSN (insn);
568 set = single_set (insn);
569 if (!set)
570 return;
572 dest = SET_DEST (set);
574 if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
575 || GET_MODE (dest) == BLKmode)
576 return;
578 if (side_effects_p (dest))
579 return;
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;
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;
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;
600 ptr = st_expr_entry (dest);
601 if (!ptr->pattern_regs)
602 ptr->pattern_regs = extract_mentioned_regs (dest);
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
611 rtx_insn *tmp = ptr->antic_stores->insn ();
612 if (tmp != NULL_RTX
613 && BLOCK_FOR_INSN (tmp) != bb)
614 check_anticipatable = 1;
616 if (check_anticipatable)
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);
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
634 rtx_insn *tmp = ptr->avail_stores->insn ();
635 if (BLOCK_FOR_INSN (tmp) != bb)
636 check_available = 1;
638 if (check_available)
640 /* Check that we have already reached the insn at that the check
641 failed last time. */
642 if (LAST_AVAIL_CHECK_FAILURE (ptr))
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;
652 else
653 check_available = store_killed_after (dest, ptr->pattern_regs, insn,
654 bb, regs_set_after,
655 &LAST_AVAIL_CHECK_FAILURE (ptr));
657 if (!check_available)
658 ptr->avail_stores = alloc_INSN_LIST (insn, ptr->avail_stores);
661 /* Find available and anticipatable stores. */
663 static int
664 compute_store_table (void)
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 ();
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);
683 /* Find all the stores we care about. */
684 FOR_EACH_BB_FN (bb, cfun)
686 /* First compute the registers set in this block. */
687 FOR_BB_INSNS (bb, insn)
690 if (! NONDEBUG_INSN_P (insn))
691 continue;
693 FOR_EACH_INSN_DEF (def, insn)
694 last_set_in[DF_REF_REGNO (def)] = INSN_UID (insn);
697 /* Now find the stores. */
698 memset (already_set, 0, sizeof (int) * max_gcse_regno);
699 FOR_BB_INSNS (bb, insn)
701 if (! NONDEBUG_INSN_P (insn))
702 continue;
704 FOR_EACH_INSN_DEF (def, insn)
705 already_set[DF_REF_REGNO (def)] = INSN_UID (insn);
707 /* Now that we've marked regs, look for stores. */
708 find_moveable_store (insn, already_set, last_set_in);
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;
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
722 /* Clear temporary marks. */
723 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
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 ();
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)
738 if (! ptr->avail_stores)
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);
744 else
745 prev_next_ptr_ptr = &ptr->next;
748 ret = enumerate_store_motion_mems ();
750 if (dump_file)
751 print_store_motion_mems (dump_file);
753 free (last_set_in);
754 free (already_set);
755 return ret;
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
763 /* Insert an instruction at the beginning of a basic block, and update
764 the BB_HEAD if needed. */
766 static void
767 insert_insn_start_basic_block (rtx_insn *insn, basic_block bb)
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)
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);
783 insn = emit_insn_after_noloc (insn, prev, bb);
785 if (dump_file)
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");
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. */
798 static int
799 insert_store (struct st_expr * expr, edge e)
801 rtx reg;
802 rtx_insn *insn;
803 basic_block bb;
804 edge tmp;
805 edge_iterator ei;
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;
812 if (e->flags & EDGE_FAKE)
813 return 0;
815 reg = expr->reaching_reg;
816 insn = as_a <rtx_insn *> (gen_move_insn (copy_rtx (expr->pattern), reg));
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))
825 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
827 gcc_assert (index != EDGE_INDEX_NO_EDGE);
828 if (! bitmap_bit_p (st_insert_map[index], expr->index))
829 break;
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))
836 FOR_EACH_EDGE (tmp, ei, e->dest->preds)
838 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
839 bitmap_clear_bit (st_insert_map[index], expr->index);
841 insert_insn_start_basic_block (insn, bb);
842 return 0;
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));
849 insert_insn_on_edge (insn, e);
851 if (dump_file)
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");
859 return 1;
862 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
863 memory location in SMEXPR set in basic block BB.
865 This could be rather expensive. */
867 static void
868 remove_reachable_equiv_notes (basic_block bb, struct st_expr *smexpr)
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;
878 stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun));
879 sp = 0;
880 ei = ei_start (bb->succs);
882 bitmap_clear (visited);
884 act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
885 while (1)
887 if (!act)
889 if (!sp)
891 free (stack);
892 sbitmap_free (visited);
893 return;
895 act = ei_edge (stack[--sp]);
897 bb = act->dest;
899 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
900 || bitmap_bit_p (visited, bb->index))
902 if (!ei_end_p (ei))
903 ei_next (&ei);
904 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
905 continue;
907 bitmap_set_bit (visited, bb->index);
909 if (bitmap_bit_p (st_antloc[bb->index], smexpr->index))
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);
917 else
918 last = NEXT_INSN (BB_END (bb));
920 for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
921 if (NONDEBUG_INSN_P (insn))
923 note = find_reg_equal_equiv_note (insn);
924 if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
925 continue;
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);
933 if (!ei_end_p (ei))
934 ei_next (&ei);
935 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
937 if (EDGE_COUNT (bb->succs) > 0)
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);
947 /* This routine will replace a store with a SET to a specified register. */
949 static void
950 replace_store_insn (rtx reg, rtx_insn *del, basic_block bb,
951 struct st_expr *smexpr)
953 rtx_insn *insn;
954 rtx mem, note, set, ptr;
956 mem = smexpr->pattern;
957 insn = as_a <rtx_insn *> (gen_move_insn (reg, SET_SRC (single_set (del))));
959 for (ptr = smexpr->antic_stores; ptr; ptr = XEXP (ptr, 1))
960 if (XEXP (ptr, 0) == del)
962 XEXP (ptr, 0) = insn;
963 break;
966 /* Move the notes from the deleted insn to its replacement. */
967 REG_NOTES (insn) = REG_NOTES (del);
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);
973 if (dump_file)
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");
983 delete_insn (del);
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))
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;
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);
1005 remove_reachable_equiv_notes (bb, smexpr);
1009 /* Delete a store, but copy the value that would have been stored into
1010 the reaching_reg for later storing. */
1012 static void
1013 delete_store (struct st_expr * expr, basic_block bb)
1015 rtx reg;
1017 if (expr->reaching_reg == NULL_RTX)
1018 expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
1020 reg = expr->reaching_reg;
1022 for (rtx_insn_list *i = expr->avail_stores; i; i = i->next ())
1024 rtx_insn *del = i->insn ();
1025 if (BLOCK_FOR_INSN (del) == bb)
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;
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)
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 ();
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));
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));
1057 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1059 for (st = ptr->avail_stores; st != NULL; st = st->next ())
1061 insn = st->insn ();
1062 bb = BLOCK_FOR_INSN (insn);
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))
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;
1076 bitmap_set_bit (st_avloc[bb->index], ptr->index);
1079 for (st = ptr->antic_stores; st != NULL; st = st->next ())
1081 insn = st->insn ();
1082 bb = BLOCK_FOR_INSN (insn);
1083 bitmap_set_bit (st_antloc[bb->index], ptr->index);
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));
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);
1094 FOR_EACH_BB_FN (bb, cfun)
1096 memset (regs_set_in_block, 0, sizeof (int) * max_gcse_regno);
1098 FOR_BB_INSNS (bb, insn)
1099 if (NONDEBUG_INSN_P (insn))
1101 df_ref def;
1102 FOR_EACH_INSN_DEF (def, insn)
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;
1110 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1112 if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
1113 bb, regs_set_in_block, NULL))
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);
1121 else
1122 bitmap_set_bit (st_transp[bb->index], ptr->index);
1126 free (regs_set_in_block);
1128 if (dump_file)
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));
1141 /* Free memory used by store motion. */
1143 static void
1144 free_store_memory (void)
1146 free_store_motion_mems ();
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);
1161 st_avloc = st_kill = st_transp = st_antloc = NULL;
1162 st_insert_map = st_delete_map = NULL;
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. */
1169 static int
1170 one_store_motion_pass (void)
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;
1179 init_alias_analysis ();
1181 /* Find all the available and anticipatable stores. */
1182 num_stores = compute_store_table ();
1183 if (num_stores == 0)
1185 delete store_motion_mems_table;
1186 store_motion_mems_table = NULL;
1187 end_alias_analysis ();
1188 return 0;
1191 /* Now compute kill & transp vectors. */
1192 build_store_vectors ();
1193 add_noreturn_fake_exit_edges ();
1194 connect_infinite_loops_to_exit ();
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);
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))
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;
1210 if (x >= 0)
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;
1220 /* Now we want to insert the new stores which are going to be needed. */
1222 FOR_EACH_BB_FN (bb, cfun)
1223 if (bitmap_bit_p (st_delete_map[bb->index], ptr->index))
1225 delete_store (ptr, bb);
1226 n_stores_deleted++;
1229 for (x = 0; x < NUM_EDGES (edge_list); x++)
1230 if (bitmap_bit_p (st_insert_map[x], ptr->index))
1232 did_edge_inserts |= insert_store (ptr, INDEX_EDGE (edge_list, x));
1233 n_stores_created++;
1237 if (did_edge_inserts)
1238 commit_edge_insertions ();
1240 free_store_memory ();
1241 free_edge_list (edge_list);
1242 remove_fake_exit_edges ();
1243 end_alias_analysis ();
1245 if (dump_file)
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);
1253 return (n_stores_deleted > 0 || n_stores_created > 0);
1257 static unsigned int
1258 execute_rtl_store_motion (void)
1260 delete_unreachable_blocks ();
1261 df_analyze ();
1262 flag_rerun_cse_after_global_opts |= one_store_motion_pass ();
1263 return 0;
1266 namespace {
1268 const pass_data pass_data_rtl_store_motion =
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 */
1281 class pass_rtl_store_motion : public rtl_opt_pass
1283 public:
1284 pass_rtl_store_motion (gcc::context *ctxt)
1285 : rtl_opt_pass (pass_data_rtl_store_motion, ctxt)
1288 /* opt_pass methods: */
1289 virtual bool gate (function *);
1290 virtual unsigned int execute (function *)
1292 return execute_rtl_store_motion ();
1295 }; // class pass_rtl_store_motion
1297 bool
1298 pass_rtl_store_motion::gate (function *fun)
1300 return optimize > 0 && flag_gcse_sm
1301 && !fun->calls_setjmp
1302 && optimize_function_for_speed_p (fun)
1303 && dbg_cnt (store_motion);
1306 } // anon namespace
1308 rtl_opt_pass *
1309 make_pass_rtl_store_motion (gcc::context *ctxt)
1311 return new pass_rtl_store_motion (ctxt);