Daily bump.
[official-gcc.git] / gcc / store-motion.c
blob85870f6815b509d818b17c4be8c421de1758c7f0
1 /* Store motion via Lazy Code Motion on the reverse CFG.
2 Copyright (C) 1997-2014 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 "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 "hash-table.h"
43 #include "df.h"
44 #include "dbgcnt.h"
45 #include "rtl-iter.h"
47 /* This pass implements downward store motion.
48 As of May 1, 2009, the pass is not enabled by default on any target,
49 but bootstrap completes on ia64 and x86_64 with the pass enabled. */
51 /* TODO:
52 - remove_reachable_equiv_notes is an incomprehensible pile of goo and
53 a compile time hog that needs a rewrite (maybe cache st_exprs to
54 invalidate REG_EQUAL/REG_EQUIV notes for?).
55 - pattern_regs in st_expr should be a regset (on its own obstack).
56 - antic_stores and avail_stores should be VECs instead of lists.
57 - store_motion_mems should be a vec instead of a list.
58 - there should be an alloc pool for struct st_expr objects.
59 - investigate whether it is helpful to make the address of an st_expr
60 a cselib VALUE.
61 - when GIMPLE alias information is exported, the effectiveness of this
62 pass should be re-evaluated.
65 /* This is a list of store expressions (MEMs). The structure is used
66 as an expression table to track stores which look interesting, and
67 might be moveable towards the exit block. */
69 struct st_expr
71 /* Pattern of this mem. */
72 rtx pattern;
73 /* List of registers mentioned by the mem. */
74 rtx pattern_regs;
75 /* INSN list of stores that are locally anticipatable. */
76 rtx_insn_list *antic_stores;
77 /* INSN list of stores that are locally available. */
78 rtx_insn_list *avail_stores;
79 /* Next in the list. */
80 struct st_expr * next;
81 /* Store ID in the dataflow bitmaps. */
82 int index;
83 /* Hash value for the hash table. */
84 unsigned int hash_index;
85 /* Register holding the stored expression when a store is moved.
86 This field is also used as a cache in find_moveable_store, see
87 LAST_AVAIL_CHECK_FAILURE below. */
88 rtx reaching_reg;
91 /* Head of the list of load/store memory refs. */
92 static struct st_expr * store_motion_mems = NULL;
94 /* These bitmaps will hold the local dataflow properties per basic block. */
95 static sbitmap *st_kill, *st_avloc, *st_antloc, *st_transp;
97 /* Nonzero for expressions which should be inserted on a specific edge. */
98 static sbitmap *st_insert_map;
100 /* Nonzero for expressions which should be deleted in a specific block. */
101 static sbitmap *st_delete_map;
103 /* Global holding the number of store expressions we are dealing with. */
104 static int num_stores;
106 /* Contains the edge_list returned by pre_edge_lcm. */
107 static struct edge_list *edge_list;
109 /* Hashtable helpers. */
111 struct st_expr_hasher : typed_noop_remove <st_expr>
113 typedef st_expr value_type;
114 typedef st_expr compare_type;
115 static inline hashval_t hash (const value_type *);
116 static inline bool equal (const value_type *, const compare_type *);
119 inline hashval_t
120 st_expr_hasher::hash (const value_type *x)
122 int do_not_record_p = 0;
123 return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
126 inline bool
127 st_expr_hasher::equal (const value_type *ptr1, const compare_type *ptr2)
129 return exp_equiv_p (ptr1->pattern, ptr2->pattern, 0, true);
132 /* Hashtable for the load/store memory refs. */
133 static hash_table<st_expr_hasher> *store_motion_mems_table;
135 /* This will search the st_expr list for a matching expression. If it
136 doesn't find one, we create one and initialize it. */
138 static struct st_expr *
139 st_expr_entry (rtx x)
141 int do_not_record_p = 0;
142 struct st_expr * ptr;
143 unsigned int hash;
144 st_expr **slot;
145 struct st_expr e;
147 hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
148 NULL, /*have_reg_qty=*/false);
150 e.pattern = x;
151 slot = store_motion_mems_table->find_slot_with_hash (&e, hash, INSERT);
152 if (*slot)
153 return *slot;
155 ptr = XNEW (struct st_expr);
157 ptr->next = store_motion_mems;
158 ptr->pattern = x;
159 ptr->pattern_regs = NULL_RTX;
160 ptr->antic_stores = NULL;
161 ptr->avail_stores = NULL;
162 ptr->reaching_reg = NULL_RTX;
163 ptr->index = 0;
164 ptr->hash_index = hash;
165 store_motion_mems = ptr;
166 *slot = ptr;
168 return ptr;
171 /* Free up an individual st_expr entry. */
173 static void
174 free_st_expr_entry (struct st_expr * ptr)
176 free_INSN_LIST_list (& ptr->antic_stores);
177 free_INSN_LIST_list (& ptr->avail_stores);
179 free (ptr);
182 /* Free up all memory associated with the st_expr list. */
184 static void
185 free_store_motion_mems (void)
187 delete store_motion_mems_table;
188 store_motion_mems_table = NULL;
190 while (store_motion_mems)
192 struct st_expr * tmp = store_motion_mems;
193 store_motion_mems = store_motion_mems->next;
194 free_st_expr_entry (tmp);
196 store_motion_mems = NULL;
199 /* Assign each element of the list of mems a monotonically increasing value. */
201 static int
202 enumerate_store_motion_mems (void)
204 struct st_expr * ptr;
205 int n = 0;
207 for (ptr = store_motion_mems; ptr != NULL; ptr = ptr->next)
208 ptr->index = n++;
210 return n;
213 /* Return first item in the list. */
215 static inline struct st_expr *
216 first_st_expr (void)
218 return store_motion_mems;
221 /* Return the next item in the list after the specified one. */
223 static inline struct st_expr *
224 next_st_expr (struct st_expr * ptr)
226 return ptr->next;
229 /* Dump debugging info about the store_motion_mems list. */
231 static void
232 print_store_motion_mems (FILE * file)
234 struct st_expr * ptr;
236 fprintf (dump_file, "STORE_MOTION list of MEM exprs considered:\n");
238 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
240 fprintf (file, " Pattern (%3d): ", ptr->index);
242 print_rtl (file, ptr->pattern);
244 fprintf (file, "\n ANTIC stores : ");
246 if (ptr->antic_stores)
247 print_rtl (file, ptr->antic_stores);
248 else
249 fprintf (file, "(nil)");
251 fprintf (file, "\n AVAIL stores : ");
253 if (ptr->avail_stores)
254 print_rtl (file, ptr->avail_stores);
255 else
256 fprintf (file, "(nil)");
258 fprintf (file, "\n\n");
261 fprintf (file, "\n");
264 /* Return zero if some of the registers in list X are killed
265 due to set of registers in bitmap REGS_SET. */
267 static bool
268 store_ops_ok (const_rtx x, int *regs_set)
270 const_rtx reg;
272 for (; x; x = XEXP (x, 1))
274 reg = XEXP (x, 0);
275 if (regs_set[REGNO (reg)])
276 return false;
279 return true;
282 /* Returns a list of registers mentioned in X.
283 FIXME: A regset would be prettier and less expensive. */
285 static rtx
286 extract_mentioned_regs (rtx x)
288 rtx mentioned_regs = NULL;
289 subrtx_var_iterator::array_type array;
290 FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
292 rtx x = *iter;
293 if (REG_P (x))
294 mentioned_regs = alloc_EXPR_LIST (0, x, mentioned_regs);
296 return mentioned_regs;
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. */
303 static bool
304 load_kills_store (const_rtx x, const_rtx store_pattern, int after)
306 if (after)
307 return anti_dependence (x, store_pattern);
308 else
309 return true_dependence (store_pattern, GET_MODE (store_pattern), x);
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. */
317 static bool
318 find_loads (const_rtx x, const_rtx store_pattern, int after)
320 const char * fmt;
321 int i, j;
322 int ret = false;
324 if (!x)
325 return false;
327 if (GET_CODE (x) == SET)
328 x = SET_SRC (x);
330 if (MEM_P (x))
332 if (load_kills_store (x, store_pattern, after))
333 return true;
336 /* Recursively process the insn. */
337 fmt = GET_RTX_FORMAT (GET_CODE (x));
339 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
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);
347 return ret;
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. */
355 static inline bool
356 store_killed_in_pat (const_rtx x, const_rtx pat, int after)
358 if (GET_CODE (pat) == SET)
360 rtx dest = SET_DEST (pat);
362 if (GET_CODE (dest) == ZERO_EXTRACT)
363 dest = XEXP (dest, 0);
365 /* Check for memory stores to aliased objects. */
366 if (MEM_P (dest)
367 && !exp_equiv_p (dest, x, 0, true))
369 if (after)
371 if (output_dependence (dest, x))
372 return true;
374 else
376 if (output_dependence (x, dest))
377 return true;
382 if (find_loads (pat, x, after))
383 return true;
385 return false;
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. */
392 static bool
393 store_killed_in_insn (const_rtx x, const_rtx x_regs, const rtx_insn *insn, int after)
395 const_rtx reg, note, pat;
397 if (! NONDEBUG_INSN_P (insn))
398 return false;
400 if (CALL_P (insn))
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;
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;
413 return false;
416 pat = PATTERN (insn);
417 if (GET_CODE (pat) == SET)
419 if (store_killed_in_pat (x, pat, after))
420 return true;
422 else if (GET_CODE (pat) == PARALLEL)
424 int i;
426 for (i = 0; i < XVECLEN (pat, 0); i++)
427 if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
428 return true;
430 else if (find_loads (PATTERN (insn), x, after))
431 return true;
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);
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;
445 /* See if there are any aliased loads in the note. */
446 return find_loads (note, x, after);
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. */
454 static bool
455 store_killed_after (const_rtx x, const_rtx x_regs, const rtx_insn *insn,
456 const_basic_block bb,
457 int *regs_set_after, rtx *fail_insn)
459 rtx_insn *last = BB_END (bb), *act;
461 if (!store_ops_ok (x_regs, regs_set_after))
463 /* We do not know where it will happen. */
464 if (fail_insn)
465 *fail_insn = NULL_RTX;
466 return true;
469 /* Scan from the end, so that fail_insn is determined correctly. */
470 for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
471 if (store_killed_in_insn (x, x_regs, act, false))
473 if (fail_insn)
474 *fail_insn = act;
475 return true;
478 return false;
481 /* Returns true if the expression X is loaded or clobbered on or before INSN
482 within basic block BB. X_REGS is list of registers mentioned in X.
483 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
484 static bool
485 store_killed_before (const_rtx x, const_rtx x_regs, const rtx_insn *insn,
486 const_basic_block bb, int *regs_set_before)
488 rtx_insn *first = BB_HEAD (bb);
490 if (!store_ops_ok (x_regs, regs_set_before))
491 return true;
493 for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
494 if (store_killed_in_insn (x, x_regs, insn, true))
495 return true;
497 return false;
500 /* The last insn in the basic block that compute_store_table is processing,
501 where store_killed_after is true for X.
502 Since we go through the basic block from BB_END to BB_HEAD, this is
503 also the available store at the end of the basic block. Therefore
504 this is in effect a cache, to avoid calling store_killed_after for
505 equivalent aliasing store expressions.
506 This value is only meaningful during the computation of the store
507 table. We hi-jack the REACHING_REG field of struct st_expr to save
508 a bit of memory. */
509 #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
511 /* Determine whether INSN is MEM store pattern that we will consider moving.
512 REGS_SET_BEFORE is bitmap of registers set before (and including) the
513 current insn, REGS_SET_AFTER is bitmap of registers set after (and
514 including) the insn in this basic block. We must be passing through BB from
515 head to end, as we are using this fact to speed things up.
517 The results are stored this way:
519 -- the first anticipatable expression is added into ANTIC_STORES
520 -- if the processed expression is not anticipatable, NULL_RTX is added
521 there instead, so that we can use it as indicator that no further
522 expression of this type may be anticipatable
523 -- if the expression is available, it is added as head of AVAIL_STORES;
524 consequently, all of them but this head are dead and may be deleted.
525 -- if the expression is not available, the insn due to that it fails to be
526 available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
528 The things are complicated a bit by fact that there already may be stores
529 to the same MEM from other blocks; also caller must take care of the
530 necessary cleanup of the temporary markers after end of the basic block.
533 static void
534 find_moveable_store (rtx_insn *insn, int *regs_set_before, int *regs_set_after)
536 struct st_expr * ptr;
537 rtx dest, set;
538 int check_anticipatable, check_available;
539 basic_block bb = BLOCK_FOR_INSN (insn);
541 set = single_set (insn);
542 if (!set)
543 return;
545 dest = SET_DEST (set);
547 if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
548 || GET_MODE (dest) == BLKmode)
549 return;
551 if (side_effects_p (dest))
552 return;
554 /* If we are handling exceptions, we must be careful with memory references
555 that may trap. If we are not, the behavior is undefined, so we may just
556 continue. */
557 if (cfun->can_throw_non_call_exceptions && may_trap_p (dest))
558 return;
560 /* Even if the destination cannot trap, the source may. In this case we'd
561 need to handle updating the REG_EH_REGION note. */
562 if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
563 return;
565 /* Make sure that the SET_SRC of this store insns can be assigned to
566 a register, or we will fail later on in replace_store_insn, which
567 assumes that we can do this. But sometimes the target machine has
568 oddities like MEM read-modify-write instruction. See for example
569 PR24257. */
570 if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set)))
571 return;
573 ptr = st_expr_entry (dest);
574 if (!ptr->pattern_regs)
575 ptr->pattern_regs = extract_mentioned_regs (dest);
577 /* Do not check for anticipatability if we either found one anticipatable
578 store already, or tested for one and found out that it was killed. */
579 check_anticipatable = 0;
580 if (!ptr->antic_stores)
581 check_anticipatable = 1;
582 else
584 rtx_insn *tmp = ptr->antic_stores->insn ();
585 if (tmp != NULL_RTX
586 && BLOCK_FOR_INSN (tmp) != bb)
587 check_anticipatable = 1;
589 if (check_anticipatable)
591 rtx_insn *tmp;
592 if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before))
593 tmp = NULL;
594 else
595 tmp = insn;
596 ptr->antic_stores = alloc_INSN_LIST (tmp, ptr->antic_stores);
599 /* It is not necessary to check whether store is available if we did
600 it successfully before; if we failed before, do not bother to check
601 until we reach the insn that caused us to fail. */
602 check_available = 0;
603 if (!ptr->avail_stores)
604 check_available = 1;
605 else
607 rtx_insn *tmp = ptr->avail_stores->insn ();
608 if (BLOCK_FOR_INSN (tmp) != bb)
609 check_available = 1;
611 if (check_available)
613 /* Check that we have already reached the insn at that the check
614 failed last time. */
615 if (LAST_AVAIL_CHECK_FAILURE (ptr))
617 rtx_insn *tmp;
618 for (tmp = BB_END (bb);
619 tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
620 tmp = PREV_INSN (tmp))
621 continue;
622 if (tmp == insn)
623 check_available = 0;
625 else
626 check_available = store_killed_after (dest, ptr->pattern_regs, insn,
627 bb, regs_set_after,
628 &LAST_AVAIL_CHECK_FAILURE (ptr));
630 if (!check_available)
631 ptr->avail_stores = alloc_INSN_LIST (insn, ptr->avail_stores);
634 /* Find available and anticipatable stores. */
636 static int
637 compute_store_table (void)
639 int ret;
640 basic_block bb;
641 #ifdef ENABLE_CHECKING
642 unsigned regno;
643 #endif
644 rtx_insn *insn;
645 rtx_insn *tmp;
646 df_ref def;
647 int *last_set_in, *already_set;
648 struct st_expr * ptr, **prev_next_ptr_ptr;
649 unsigned int max_gcse_regno = max_reg_num ();
651 store_motion_mems = NULL;
652 store_motion_mems_table = new hash_table<st_expr_hasher> (13);
653 last_set_in = XCNEWVEC (int, max_gcse_regno);
654 already_set = XNEWVEC (int, max_gcse_regno);
656 /* Find all the stores we care about. */
657 FOR_EACH_BB_FN (bb, cfun)
659 /* First compute the registers set in this block. */
660 FOR_BB_INSNS (bb, insn)
663 if (! NONDEBUG_INSN_P (insn))
664 continue;
666 FOR_EACH_INSN_DEF (def, insn)
667 last_set_in[DF_REF_REGNO (def)] = INSN_UID (insn);
670 /* Now find the stores. */
671 memset (already_set, 0, sizeof (int) * max_gcse_regno);
672 FOR_BB_INSNS (bb, insn)
674 if (! NONDEBUG_INSN_P (insn))
675 continue;
677 FOR_EACH_INSN_DEF (def, insn)
678 already_set[DF_REF_REGNO (def)] = INSN_UID (insn);
680 /* Now that we've marked regs, look for stores. */
681 find_moveable_store (insn, already_set, last_set_in);
683 /* Unmark regs that are no longer set. */
684 FOR_EACH_INSN_DEF (def, insn)
685 if (last_set_in[DF_REF_REGNO (def)] == INSN_UID (insn))
686 last_set_in[DF_REF_REGNO (def)] = 0;
689 #ifdef ENABLE_CHECKING
690 /* last_set_in should now be all-zero. */
691 for (regno = 0; regno < max_gcse_regno; regno++)
692 gcc_assert (!last_set_in[regno]);
693 #endif
695 /* Clear temporary marks. */
696 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
698 LAST_AVAIL_CHECK_FAILURE (ptr) = NULL_RTX;
699 if (ptr->antic_stores
700 && (tmp = ptr->antic_stores->insn ()) == NULL_RTX)
701 ptr->antic_stores = ptr->antic_stores->next ();
705 /* Remove the stores that are not available anywhere, as there will
706 be no opportunity to optimize them. */
707 for (ptr = store_motion_mems, prev_next_ptr_ptr = &store_motion_mems;
708 ptr != NULL;
709 ptr = *prev_next_ptr_ptr)
711 if (! ptr->avail_stores)
713 *prev_next_ptr_ptr = ptr->next;
714 store_motion_mems_table->remove_elt_with_hash (ptr, ptr->hash_index);
715 free_st_expr_entry (ptr);
717 else
718 prev_next_ptr_ptr = &ptr->next;
721 ret = enumerate_store_motion_mems ();
723 if (dump_file)
724 print_store_motion_mems (dump_file);
726 free (last_set_in);
727 free (already_set);
728 return ret;
731 /* In all code following after this, REACHING_REG has its original
732 meaning again. Avoid confusion, and undef the accessor macro for
733 the temporary marks usage in compute_store_table. */
734 #undef LAST_AVAIL_CHECK_FAILURE
736 /* Insert an instruction at the beginning of a basic block, and update
737 the BB_HEAD if needed. */
739 static void
740 insert_insn_start_basic_block (rtx_insn *insn, basic_block bb)
742 /* Insert at start of successor block. */
743 rtx_insn *prev = PREV_INSN (BB_HEAD (bb));
744 rtx_insn *before = BB_HEAD (bb);
745 while (before != 0)
747 if (! LABEL_P (before)
748 && !NOTE_INSN_BASIC_BLOCK_P (before))
749 break;
750 prev = before;
751 if (prev == BB_END (bb))
752 break;
753 before = NEXT_INSN (before);
756 insn = emit_insn_after_noloc (insn, prev, bb);
758 if (dump_file)
760 fprintf (dump_file, "STORE_MOTION insert store at start of BB %d:\n",
761 bb->index);
762 print_inline_rtx (dump_file, insn, 6);
763 fprintf (dump_file, "\n");
767 /* This routine will insert a store on an edge. EXPR is the st_expr entry for
768 the memory reference, and E is the edge to insert it on. Returns nonzero
769 if an edge insertion was performed. */
771 static int
772 insert_store (struct st_expr * expr, edge e)
774 rtx reg;
775 rtx_insn *insn;
776 basic_block bb;
777 edge tmp;
778 edge_iterator ei;
780 /* We did all the deleted before this insert, so if we didn't delete a
781 store, then we haven't set the reaching reg yet either. */
782 if (expr->reaching_reg == NULL_RTX)
783 return 0;
785 if (e->flags & EDGE_FAKE)
786 return 0;
788 reg = expr->reaching_reg;
789 insn = as_a <rtx_insn *> (gen_move_insn (copy_rtx (expr->pattern), reg));
791 /* If we are inserting this expression on ALL predecessor edges of a BB,
792 insert it at the start of the BB, and reset the insert bits on the other
793 edges so we don't try to insert it on the other edges. */
794 bb = e->dest;
795 FOR_EACH_EDGE (tmp, ei, e->dest->preds)
796 if (!(tmp->flags & EDGE_FAKE))
798 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
800 gcc_assert (index != EDGE_INDEX_NO_EDGE);
801 if (! bitmap_bit_p (st_insert_map[index], expr->index))
802 break;
805 /* If tmp is NULL, we found an insertion on every edge, blank the
806 insertion vector for these edges, and insert at the start of the BB. */
807 if (!tmp && bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
809 FOR_EACH_EDGE (tmp, ei, e->dest->preds)
811 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
812 bitmap_clear_bit (st_insert_map[index], expr->index);
814 insert_insn_start_basic_block (insn, bb);
815 return 0;
818 /* We can't put stores in the front of blocks pointed to by abnormal
819 edges since that may put a store where one didn't used to be. */
820 gcc_assert (!(e->flags & EDGE_ABNORMAL));
822 insert_insn_on_edge (insn, e);
824 if (dump_file)
826 fprintf (dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
827 e->src->index, e->dest->index);
828 print_inline_rtx (dump_file, insn, 6);
829 fprintf (dump_file, "\n");
832 return 1;
835 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
836 memory location in SMEXPR set in basic block BB.
838 This could be rather expensive. */
840 static void
841 remove_reachable_equiv_notes (basic_block bb, struct st_expr *smexpr)
843 edge_iterator *stack, ei;
844 int sp;
845 edge act;
846 sbitmap visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
847 rtx last, note;
848 rtx_insn *insn;
849 rtx mem = smexpr->pattern;
851 stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun));
852 sp = 0;
853 ei = ei_start (bb->succs);
855 bitmap_clear (visited);
857 act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
858 while (1)
860 if (!act)
862 if (!sp)
864 free (stack);
865 sbitmap_free (visited);
866 return;
868 act = ei_edge (stack[--sp]);
870 bb = act->dest;
872 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
873 || bitmap_bit_p (visited, bb->index))
875 if (!ei_end_p (ei))
876 ei_next (&ei);
877 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
878 continue;
880 bitmap_set_bit (visited, bb->index);
882 if (bitmap_bit_p (st_antloc[bb->index], smexpr->index))
884 for (last = smexpr->antic_stores;
885 BLOCK_FOR_INSN (XEXP (last, 0)) != bb;
886 last = XEXP (last, 1))
887 continue;
888 last = XEXP (last, 0);
890 else
891 last = NEXT_INSN (BB_END (bb));
893 for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
894 if (NONDEBUG_INSN_P (insn))
896 note = find_reg_equal_equiv_note (insn);
897 if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
898 continue;
900 if (dump_file)
901 fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
902 INSN_UID (insn));
903 remove_note (insn, note);
906 if (!ei_end_p (ei))
907 ei_next (&ei);
908 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
910 if (EDGE_COUNT (bb->succs) > 0)
912 if (act)
913 stack[sp++] = ei;
914 ei = ei_start (bb->succs);
915 act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
920 /* This routine will replace a store with a SET to a specified register. */
922 static void
923 replace_store_insn (rtx reg, rtx_insn *del, basic_block bb,
924 struct st_expr *smexpr)
926 rtx_insn *insn;
927 rtx mem, note, set, ptr;
929 mem = smexpr->pattern;
930 insn = as_a <rtx_insn *> (gen_move_insn (reg, SET_SRC (single_set (del))));
932 for (ptr = smexpr->antic_stores; ptr; ptr = XEXP (ptr, 1))
933 if (XEXP (ptr, 0) == del)
935 XEXP (ptr, 0) = insn;
936 break;
939 /* Move the notes from the deleted insn to its replacement. */
940 REG_NOTES (insn) = REG_NOTES (del);
942 /* Emit the insn AFTER all the notes are transferred.
943 This is cheaper since we avoid df rescanning for the note change. */
944 insn = emit_insn_after (insn, del);
946 if (dump_file)
948 fprintf (dump_file,
949 "STORE_MOTION delete insn in BB %d:\n ", bb->index);
950 print_inline_rtx (dump_file, del, 6);
951 fprintf (dump_file, "\nSTORE_MOTION replaced with insn:\n ");
952 print_inline_rtx (dump_file, insn, 6);
953 fprintf (dump_file, "\n");
956 delete_insn (del);
958 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
959 they are no longer accurate provided that they are reached by this
960 definition, so drop them. */
961 for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn))
962 if (NONDEBUG_INSN_P (insn))
964 set = single_set (insn);
965 if (!set)
966 continue;
967 if (exp_equiv_p (SET_DEST (set), mem, 0, true))
968 return;
969 note = find_reg_equal_equiv_note (insn);
970 if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
971 continue;
973 if (dump_file)
974 fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
975 INSN_UID (insn));
976 remove_note (insn, note);
978 remove_reachable_equiv_notes (bb, smexpr);
982 /* Delete a store, but copy the value that would have been stored into
983 the reaching_reg for later storing. */
985 static void
986 delete_store (struct st_expr * expr, basic_block bb)
988 rtx reg;
990 if (expr->reaching_reg == NULL_RTX)
991 expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
993 reg = expr->reaching_reg;
995 for (rtx_insn_list *i = expr->avail_stores; i; i = i->next ())
997 rtx_insn *del = i->insn ();
998 if (BLOCK_FOR_INSN (del) == bb)
1000 /* We know there is only one since we deleted redundant
1001 ones during the available computation. */
1002 replace_store_insn (reg, del, bb, expr);
1003 break;
1008 /* Fill in available, anticipatable, transparent and kill vectors in
1009 STORE_DATA, based on lists of available and anticipatable stores. */
1010 static void
1011 build_store_vectors (void)
1013 basic_block bb;
1014 int *regs_set_in_block;
1015 rtx_insn *insn;
1016 rtx_insn_list *st;
1017 struct st_expr * ptr;
1018 unsigned int max_gcse_regno = max_reg_num ();
1020 /* Build the gen_vector. This is any store in the table which is not killed
1021 by aliasing later in its block. */
1022 st_avloc = sbitmap_vector_alloc (last_basic_block_for_fn (cfun),
1023 num_stores);
1024 bitmap_vector_clear (st_avloc, last_basic_block_for_fn (cfun));
1026 st_antloc = sbitmap_vector_alloc (last_basic_block_for_fn (cfun),
1027 num_stores);
1028 bitmap_vector_clear (st_antloc, last_basic_block_for_fn (cfun));
1030 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1032 for (st = ptr->avail_stores; st != NULL; st = st->next ())
1034 insn = st->insn ();
1035 bb = BLOCK_FOR_INSN (insn);
1037 /* If we've already seen an available expression in this block,
1038 we can delete this one (It occurs earlier in the block). We'll
1039 copy the SRC expression to an unused register in case there
1040 are any side effects. */
1041 if (bitmap_bit_p (st_avloc[bb->index], ptr->index))
1043 rtx r = gen_reg_rtx_and_attrs (ptr->pattern);
1044 if (dump_file)
1045 fprintf (dump_file, "Removing redundant store:\n");
1046 replace_store_insn (r, st->insn (), bb, ptr);
1047 continue;
1049 bitmap_set_bit (st_avloc[bb->index], ptr->index);
1052 for (st = ptr->antic_stores; st != NULL; st = st->next ())
1054 insn = st->insn ();
1055 bb = BLOCK_FOR_INSN (insn);
1056 bitmap_set_bit (st_antloc[bb->index], ptr->index);
1060 st_kill = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), num_stores);
1061 bitmap_vector_clear (st_kill, last_basic_block_for_fn (cfun));
1063 st_transp = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), num_stores);
1064 bitmap_vector_clear (st_transp, last_basic_block_for_fn (cfun));
1065 regs_set_in_block = XNEWVEC (int, max_gcse_regno);
1067 FOR_EACH_BB_FN (bb, cfun)
1069 memset (regs_set_in_block, 0, sizeof (int) * max_gcse_regno);
1071 FOR_BB_INSNS (bb, insn)
1072 if (NONDEBUG_INSN_P (insn))
1074 df_ref def;
1075 FOR_EACH_INSN_DEF (def, insn)
1077 unsigned int ref_regno = DF_REF_REGNO (def);
1078 if (ref_regno < max_gcse_regno)
1079 regs_set_in_block[DF_REF_REGNO (def)] = 1;
1083 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1085 if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
1086 bb, regs_set_in_block, NULL))
1088 /* It should not be necessary to consider the expression
1089 killed if it is both anticipatable and available. */
1090 if (!bitmap_bit_p (st_antloc[bb->index], ptr->index)
1091 || !bitmap_bit_p (st_avloc[bb->index], ptr->index))
1092 bitmap_set_bit (st_kill[bb->index], ptr->index);
1094 else
1095 bitmap_set_bit (st_transp[bb->index], ptr->index);
1099 free (regs_set_in_block);
1101 if (dump_file)
1103 dump_bitmap_vector (dump_file, "st_antloc", "", st_antloc,
1104 last_basic_block_for_fn (cfun));
1105 dump_bitmap_vector (dump_file, "st_kill", "", st_kill,
1106 last_basic_block_for_fn (cfun));
1107 dump_bitmap_vector (dump_file, "st_transp", "", st_transp,
1108 last_basic_block_for_fn (cfun));
1109 dump_bitmap_vector (dump_file, "st_avloc", "", st_avloc,
1110 last_basic_block_for_fn (cfun));
1114 /* Free memory used by store motion. */
1116 static void
1117 free_store_memory (void)
1119 free_store_motion_mems ();
1121 if (st_avloc)
1122 sbitmap_vector_free (st_avloc);
1123 if (st_kill)
1124 sbitmap_vector_free (st_kill);
1125 if (st_transp)
1126 sbitmap_vector_free (st_transp);
1127 if (st_antloc)
1128 sbitmap_vector_free (st_antloc);
1129 if (st_insert_map)
1130 sbitmap_vector_free (st_insert_map);
1131 if (st_delete_map)
1132 sbitmap_vector_free (st_delete_map);
1134 st_avloc = st_kill = st_transp = st_antloc = NULL;
1135 st_insert_map = st_delete_map = NULL;
1138 /* Perform store motion. Much like gcse, except we move expressions the
1139 other way by looking at the flowgraph in reverse.
1140 Return non-zero if transformations are performed by the pass. */
1142 static int
1143 one_store_motion_pass (void)
1145 basic_block bb;
1146 int x;
1147 struct st_expr * ptr;
1148 int did_edge_inserts = 0;
1149 int n_stores_deleted = 0;
1150 int n_stores_created = 0;
1152 init_alias_analysis ();
1154 /* Find all the available and anticipatable stores. */
1155 num_stores = compute_store_table ();
1156 if (num_stores == 0)
1158 delete store_motion_mems_table;
1159 store_motion_mems_table = NULL;
1160 end_alias_analysis ();
1161 return 0;
1164 /* Now compute kill & transp vectors. */
1165 build_store_vectors ();
1166 add_noreturn_fake_exit_edges ();
1167 connect_infinite_loops_to_exit ();
1169 edge_list = pre_edge_rev_lcm (num_stores, st_transp, st_avloc,
1170 st_antloc, st_kill, &st_insert_map,
1171 &st_delete_map);
1173 /* Now we want to insert the new stores which are going to be needed. */
1174 for (ptr = first_st_expr (); ptr != NULL; ptr = next_st_expr (ptr))
1176 /* If any of the edges we have above are abnormal, we can't move this
1177 store. */
1178 for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
1179 if (bitmap_bit_p (st_insert_map[x], ptr->index)
1180 && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
1181 break;
1183 if (x >= 0)
1185 if (dump_file != NULL)
1186 fprintf (dump_file,
1187 "Can't replace store %d: abnormal edge from %d to %d\n",
1188 ptr->index, INDEX_EDGE (edge_list, x)->src->index,
1189 INDEX_EDGE (edge_list, x)->dest->index);
1190 continue;
1193 /* Now we want to insert the new stores which are going to be needed. */
1195 FOR_EACH_BB_FN (bb, cfun)
1196 if (bitmap_bit_p (st_delete_map[bb->index], ptr->index))
1198 delete_store (ptr, bb);
1199 n_stores_deleted++;
1202 for (x = 0; x < NUM_EDGES (edge_list); x++)
1203 if (bitmap_bit_p (st_insert_map[x], ptr->index))
1205 did_edge_inserts |= insert_store (ptr, INDEX_EDGE (edge_list, x));
1206 n_stores_created++;
1210 if (did_edge_inserts)
1211 commit_edge_insertions ();
1213 free_store_memory ();
1214 free_edge_list (edge_list);
1215 remove_fake_exit_edges ();
1216 end_alias_analysis ();
1218 if (dump_file)
1220 fprintf (dump_file, "STORE_MOTION of %s, %d basic blocks, ",
1221 current_function_name (), n_basic_blocks_for_fn (cfun));
1222 fprintf (dump_file, "%d insns deleted, %d insns created\n",
1223 n_stores_deleted, n_stores_created);
1226 return (n_stores_deleted > 0 || n_stores_created > 0);
1230 static unsigned int
1231 execute_rtl_store_motion (void)
1233 delete_unreachable_blocks ();
1234 df_analyze ();
1235 flag_rerun_cse_after_global_opts |= one_store_motion_pass ();
1236 return 0;
1239 namespace {
1241 const pass_data pass_data_rtl_store_motion =
1243 RTL_PASS, /* type */
1244 "store_motion", /* name */
1245 OPTGROUP_NONE, /* optinfo_flags */
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_flags_finish */
1254 class pass_rtl_store_motion : public rtl_opt_pass
1256 public:
1257 pass_rtl_store_motion (gcc::context *ctxt)
1258 : rtl_opt_pass (pass_data_rtl_store_motion, ctxt)
1261 /* opt_pass methods: */
1262 virtual bool gate (function *);
1263 virtual unsigned int execute (function *)
1265 return execute_rtl_store_motion ();
1268 }; // class pass_rtl_store_motion
1270 bool
1271 pass_rtl_store_motion::gate (function *fun)
1273 return optimize > 0 && flag_gcse_sm
1274 && !fun->calls_setjmp
1275 && optimize_function_for_speed_p (fun)
1276 && dbg_cnt (store_motion);
1279 } // anon namespace
1281 rtl_opt_pass *
1282 make_pass_rtl_store_motion (gcc::context *ctxt)
1284 return new pass_rtl_store_motion (ctxt);