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
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
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/>. */
23 #include "coretypes.h"
31 #include "hard-reg-set.h"
34 #include "insn-config.h"
36 #include "basic-block.h"
45 #include "tree-pass.h"
51 /* This is a list of expressions which are MEMs and will be used by load
53 Load motion tracks MEMs which aren't killed by
54 anything except itself. (i.e., loads and stores to a single location).
55 We can then allow movement of these MEM refs with a little special
56 allowance. (all stores copy the same value to the reaching reg used
57 for the loads). This means all values used to store into memory must have
58 no side effects so we can re-issue the setter value.
59 Store Motion uses this structure as an expression table to track stores
60 which look interesting, and might be moveable towards the exit block. */
64 rtx pattern; /* Pattern of this mem. */
65 rtx pattern_regs; /* List of registers mentioned by the mem. */
66 rtx loads; /* INSN list of loads seen. */
67 rtx stores; /* INSN list of stores seen. */
68 struct ls_expr * next; /* Next in the list. */
69 int invalid; /* Invalid for some reason. */
70 int index; /* If it maps to a bitmap index. */
71 unsigned int hash_index; /* Index when in a hash table. */
72 rtx reaching_reg; /* Register to use when re-writing. */
75 /* Head of the list of load/store memory refs. */
76 static struct ls_expr * pre_ldst_mems = NULL;
78 /* Hashtable for the load/store memory refs. */
79 static htab_t pre_ldst_table = NULL;
81 /* Various variables for statistics gathering. */
83 /* GCSE substitutions made. */
84 static int gcse_subst_count;
85 /* Number of copy instructions created. */
86 static int gcse_create_count;
87 /* For available exprs */
88 static sbitmap *ae_kill, *ae_gen;
90 /* Nonzero for expressions that are transparent in the block. */
91 static sbitmap *transp;
93 /* Nonzero for expressions which should be inserted on a specific edge. */
94 static sbitmap *pre_insert_map;
96 /* Nonzero for expressions which should be deleted in a specific block. */
97 static sbitmap *pre_delete_map;
99 /* Contains the edge_list returned by pre_edge_lcm. */
100 static struct edge_list *edge_list;
102 /* Here we provide the things required to do store motion towards
103 the exit. In order for this to be effective, PRE load motion also needed
104 to be taught how to move a load when it is kill only by a store to itself.
109 void foo(float scale)
115 'i' is both loaded and stored to in the loop. Normally, gcse cannot move
116 the load out since its live around the loop, and stored at the bottom
119 The 'Load Motion' referred to and implemented in this file is
120 an enhancement to gcse which when using edge based lcm, recognizes
121 this situation and allows gcse to move the load out of the loop.
123 Once gcse has hoisted the load, store motion can then push this
124 load towards the exit, and we end up with no loads or stores of 'i'
128 pre_ldst_expr_hash (const void *p)
130 int do_not_record_p = 0;
131 const struct ls_expr *const x = (const struct ls_expr *) p;
132 return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
136 pre_ldst_expr_eq (const void *p1, const void *p2)
138 const struct ls_expr *const ptr1 = (const struct ls_expr *) p1,
139 *const ptr2 = (const struct ls_expr *) p2;
140 return exp_equiv_p (ptr1->pattern, ptr2->pattern, 0, true);
143 /* This will search the ldst list for a matching expression. If it
144 doesn't find one, we create one and initialize it. */
146 static struct ls_expr *
149 int do_not_record_p = 0;
150 struct ls_expr * ptr;
155 hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
156 NULL, /*have_reg_qty=*/false);
159 slot = htab_find_slot_with_hash (pre_ldst_table, &e, hash, INSERT);
161 return (struct ls_expr *)*slot;
163 ptr = XNEW (struct ls_expr);
165 ptr->next = pre_ldst_mems;
167 ptr->pattern_regs = NULL_RTX;
168 ptr->loads = NULL_RTX;
169 ptr->stores = NULL_RTX;
170 ptr->reaching_reg = NULL_RTX;
173 ptr->hash_index = hash;
180 /* Free up an individual ldst entry. */
183 free_ldst_entry (struct ls_expr * ptr)
185 free_INSN_LIST_list (& ptr->loads);
186 free_INSN_LIST_list (& ptr->stores);
191 /* Free up all memory associated with the ldst list. */
194 free_ldst_mems (void)
197 htab_delete (pre_ldst_table);
198 pre_ldst_table = NULL;
200 while (pre_ldst_mems)
202 struct ls_expr * tmp = pre_ldst_mems;
204 pre_ldst_mems = pre_ldst_mems->next;
206 free_ldst_entry (tmp);
209 pre_ldst_mems = NULL;
212 /* Assign each element of the list of mems a monotonically increasing value. */
215 enumerate_ldsts (void)
217 struct ls_expr * ptr;
220 for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
226 /* Return first item in the list. */
228 static inline struct ls_expr *
231 return pre_ldst_mems;
234 /* Return the next item in the list after the specified one. */
236 static inline struct ls_expr *
237 next_ls_expr (struct ls_expr * ptr)
242 /* Dump debugging info about the ldst list. */
245 print_ldst_list (FILE * file)
247 struct ls_expr * ptr;
249 fprintf (file, "LDST list: \n");
251 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
253 fprintf (file, " Pattern (%3d): ", ptr->index);
255 print_rtl (file, ptr->pattern);
257 fprintf (file, "\n Loads : ");
260 print_rtl (file, ptr->loads);
262 fprintf (file, "(nil)");
264 fprintf (file, "\n Stores : ");
267 print_rtl (file, ptr->stores);
269 fprintf (file, "(nil)");
271 fprintf (file, "\n\n");
274 fprintf (file, "\n");
277 /* Store motion code. */
279 #define ANTIC_STORE_LIST(x) ((x)->loads)
280 #define AVAIL_STORE_LIST(x) ((x)->stores)
281 #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
283 /* This is used to communicate the target bitvector we want to use in the
284 reg_set_info routine when called via the note_stores mechanism. */
287 /* And current insn, for the same routine. */
288 static rtx compute_store_table_current_insn;
290 /* Used in computing the reverse edge graph bit vectors. */
291 static sbitmap * st_antloc;
293 /* Global holding the number of store expressions we are dealing with. */
294 static int num_stores;
296 /* Checks to set if we need to mark a register set. Called from
300 reg_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
301 void *data ATTRIBUTE_UNUSED)
303 if (GET_CODE (dest) == SUBREG)
304 dest = SUBREG_REG (dest);
307 regvec[REGNO (dest)] = INSN_UID (compute_store_table_current_insn);
310 /* Clear any mark that says that this insn sets dest. Called from
314 reg_clear_last_set (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
317 int *dead_vec = (int *) data;
319 if (GET_CODE (dest) == SUBREG)
320 dest = SUBREG_REG (dest);
323 dead_vec[REGNO (dest)] == INSN_UID (compute_store_table_current_insn))
324 dead_vec[REGNO (dest)] = 0;
327 /* Return zero if some of the registers in list X are killed
328 due to set of registers in bitmap REGS_SET. */
331 store_ops_ok (const_rtx x, int *regs_set)
335 for (; x; x = XEXP (x, 1))
338 if (regs_set[REGNO(reg)])
345 /* Helper for extract_mentioned_regs; ACCUM is used to accumulate used
348 extract_mentioned_regs_helper (rtx x, rtx accum)
354 /* Repeat is used to turn tail-recursion into iteration. */
364 return alloc_EXPR_LIST (0, x, accum);
376 /* We do not run this function with arguments having side effects. */
396 i = GET_RTX_LENGTH (code) - 1;
397 fmt = GET_RTX_FORMAT (code);
403 rtx tem = XEXP (x, i);
405 /* If we are about to do the last recursive call
406 needed at this level, change it into iteration. */
413 accum = extract_mentioned_regs_helper (tem, accum);
415 else if (fmt[i] == 'E')
419 for (j = 0; j < XVECLEN (x, i); j++)
420 accum = extract_mentioned_regs_helper (XVECEXP (x, i, j), accum);
427 /* Returns a list of registers mentioned in X. */
428 /* ??? Reimplement with for_each_rtx? */
430 extract_mentioned_regs (rtx x)
432 return extract_mentioned_regs_helper (x, NULL_RTX);
435 /* Check to see if the load X is aliased with STORE_PATTERN.
436 AFTER is true if we are checking the case when STORE_PATTERN occurs
440 load_kills_store (const_rtx x, const_rtx store_pattern, int after)
443 return anti_dependence (x, store_pattern);
445 return true_dependence (store_pattern, GET_MODE (store_pattern), x,
449 /* Go through the entire insn X, looking for any loads which might alias
450 STORE_PATTERN. Return true if found.
451 AFTER is true if we are checking the case when STORE_PATTERN occurs
455 find_loads (const_rtx x, const_rtx store_pattern, int after)
464 if (GET_CODE (x) == SET)
469 if (load_kills_store (x, store_pattern, after))
473 /* Recursively process the insn. */
474 fmt = GET_RTX_FORMAT (GET_CODE (x));
476 for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
479 ret |= find_loads (XEXP (x, i), store_pattern, after);
480 else if (fmt[i] == 'E')
481 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
482 ret |= find_loads (XVECEXP (x, i, j), store_pattern, after);
487 /* Go through pattern PAT looking for any loads which might kill the
488 store in X. Return true if found.
489 AFTER is true if we are checking the case when loads kill X occurs
490 after the insn for PAT. */
493 store_killed_in_pat (const_rtx x, const_rtx pat, int after)
495 if (GET_CODE (pat) == SET)
497 rtx dest = SET_DEST (pat);
499 if (GET_CODE (dest) == ZERO_EXTRACT)
500 dest = XEXP (dest, 0);
502 /* Check for memory stores to aliased objects. */
504 && !exp_equiv_p (dest, x, 0, true))
508 if (output_dependence (dest, x))
513 if (output_dependence (x, dest))
519 if (find_loads (pat, x, after))
525 /* Check if INSN kills the store pattern X (is aliased with it).
526 AFTER is true if we are checking the case when store X occurs
527 after the insn. Return true if it does. */
530 store_killed_in_insn (const_rtx x, const_rtx x_regs, const_rtx insn, int after)
532 const_rtx reg, base, note, pat;
539 /* A normal or pure call might read from pattern,
540 but a const call will not. */
541 if (!RTL_CONST_CALL_P (insn))
544 /* But even a const call reads its parameters. Check whether the
545 base of some of registers used in mem is stack pointer. */
546 for (reg = x_regs; reg; reg = XEXP (reg, 1))
548 base = find_base_term (XEXP (reg, 0));
550 || (GET_CODE (base) == ADDRESS
551 && GET_MODE (base) == Pmode
552 && XEXP (base, 0) == stack_pointer_rtx))
559 pat = PATTERN (insn);
560 if (GET_CODE (pat) == SET)
562 if (store_killed_in_pat (x, pat, after))
565 else if (GET_CODE (pat) == PARALLEL)
569 for (i = 0; i < XVECLEN (pat, 0); i++)
570 if (store_killed_in_pat (x, XVECEXP (pat, 0, i), after))
573 else if (find_loads (PATTERN (insn), x, after))
576 /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
577 location aliased with X, then this insn kills X. */
578 note = find_reg_equal_equiv_note (insn);
581 note = XEXP (note, 0);
583 /* However, if the note represents a must alias rather than a may
584 alias relationship, then it does not kill X. */
585 if (exp_equiv_p (note, x, 0, true))
588 /* See if there are any aliased loads in the note. */
589 return find_loads (note, x, after);
592 /* Returns true if the expression X is loaded or clobbered on or after INSN
593 within basic block BB. REGS_SET_AFTER is bitmap of registers set in
594 or after the insn. X_REGS is list of registers mentioned in X. If the store
595 is killed, return the last insn in that it occurs in FAIL_INSN. */
598 store_killed_after (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
599 int *regs_set_after, rtx *fail_insn)
601 rtx last = BB_END (bb), act;
603 if (!store_ops_ok (x_regs, regs_set_after))
605 /* We do not know where it will happen. */
607 *fail_insn = NULL_RTX;
611 /* Scan from the end, so that fail_insn is determined correctly. */
612 for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
613 if (store_killed_in_insn (x, x_regs, act, false))
623 /* Returns true if the expression X is loaded or clobbered on or before INSN
624 within basic block BB. X_REGS is list of registers mentioned in X.
625 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
627 store_killed_before (const_rtx x, const_rtx x_regs, const_rtx insn, const_basic_block bb,
628 int *regs_set_before)
630 rtx first = BB_HEAD (bb);
632 if (!store_ops_ok (x_regs, regs_set_before))
635 for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
636 if (store_killed_in_insn (x, x_regs, insn, true))
642 /* Determine whether INSN is MEM store pattern that we will consider moving.
643 REGS_SET_BEFORE is bitmap of registers set before (and including) the
644 current insn, REGS_SET_AFTER is bitmap of registers set after (and
645 including) the insn in this basic block. We must be passing through BB from
646 head to end, as we are using this fact to speed things up.
648 The results are stored this way:
650 -- the first anticipatable expression is added into ANTIC_STORE_LIST
651 -- if the processed expression is not anticipatable, NULL_RTX is added
652 there instead, so that we can use it as indicator that no further
653 expression of this type may be anticipatable
654 -- if the expression is available, it is added as head of AVAIL_STORE_LIST;
655 consequently, all of them but this head are dead and may be deleted.
656 -- if the expression is not available, the insn due to that it fails to be
657 available is stored in reaching_reg.
659 The things are complicated a bit by fact that there already may be stores
660 to the same MEM from other blocks; also caller must take care of the
661 necessary cleanup of the temporary markers after end of the basic block.
665 find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after)
667 struct ls_expr * ptr;
669 int check_anticipatable, check_available;
670 basic_block bb = BLOCK_FOR_INSN (insn);
672 set = single_set (insn);
676 dest = SET_DEST (set);
678 if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
679 || GET_MODE (dest) == BLKmode)
682 if (side_effects_p (dest))
685 /* If we are handling exceptions, we must be careful with memory references
686 that may trap. If we are not, the behavior is undefined, so we may just
688 if (flag_non_call_exceptions && may_trap_p (dest))
691 /* Even if the destination cannot trap, the source may. In this case we'd
692 need to handle updating the REG_EH_REGION note. */
693 if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
696 /* Make sure that the SET_SRC of this store insns can be assigned to
697 a register, or we will fail later on in replace_store_insn, which
698 assumes that we can do this. But sometimes the target machine has
699 oddities like MEM read-modify-write instruction. See for example
701 if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set)))
704 ptr = ldst_entry (dest);
705 if (!ptr->pattern_regs)
706 ptr->pattern_regs = extract_mentioned_regs (dest);
708 /* Do not check for anticipatability if we either found one anticipatable
709 store already, or tested for one and found out that it was killed. */
710 check_anticipatable = 0;
711 if (!ANTIC_STORE_LIST (ptr))
712 check_anticipatable = 1;
715 tmp = XEXP (ANTIC_STORE_LIST (ptr), 0);
717 && BLOCK_FOR_INSN (tmp) != bb)
718 check_anticipatable = 1;
720 if (check_anticipatable)
722 if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before))
726 ANTIC_STORE_LIST (ptr) = alloc_INSN_LIST (tmp,
727 ANTIC_STORE_LIST (ptr));
730 /* It is not necessary to check whether store is available if we did
731 it successfully before; if we failed before, do not bother to check
732 until we reach the insn that caused us to fail. */
734 if (!AVAIL_STORE_LIST (ptr))
738 tmp = XEXP (AVAIL_STORE_LIST (ptr), 0);
739 if (BLOCK_FOR_INSN (tmp) != bb)
744 /* Check that we have already reached the insn at that the check
746 if (LAST_AVAIL_CHECK_FAILURE (ptr))
748 for (tmp = BB_END (bb);
749 tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
750 tmp = PREV_INSN (tmp))
756 check_available = store_killed_after (dest, ptr->pattern_regs, insn,
758 &LAST_AVAIL_CHECK_FAILURE (ptr));
760 if (!check_available)
761 AVAIL_STORE_LIST (ptr) = alloc_INSN_LIST (insn, AVAIL_STORE_LIST (ptr));
764 /* Find available and anticipatable stores. */
767 compute_store_table (void)
773 int *last_set_in, *already_set;
774 struct ls_expr * ptr, **prev_next_ptr_ptr;
775 unsigned int max_gcse_regno = max_reg_num ();
778 pre_ldst_table = htab_create (13, pre_ldst_expr_hash,
779 pre_ldst_expr_eq, NULL);
780 last_set_in = XCNEWVEC (int, max_gcse_regno);
781 already_set = XNEWVEC (int, max_gcse_regno);
783 /* Find all the stores we care about. */
786 /* First compute the registers set in this block. */
787 regvec = last_set_in;
789 FOR_BB_INSNS (bb, insn)
796 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
797 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
798 last_set_in[regno] = INSN_UID (insn);
801 pat = PATTERN (insn);
802 compute_store_table_current_insn = insn;
803 note_stores (pat, reg_set_info, NULL);
806 /* Now find the stores. */
807 memset (already_set, 0, sizeof (int) * max_gcse_regno);
808 regvec = already_set;
809 FOR_BB_INSNS (bb, insn)
816 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
817 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
818 already_set[regno] = 1;
821 pat = PATTERN (insn);
822 note_stores (pat, reg_set_info, NULL);
824 /* Now that we've marked regs, look for stores. */
825 find_moveable_store (insn, already_set, last_set_in);
827 /* Unmark regs that are no longer set. */
828 compute_store_table_current_insn = insn;
829 note_stores (pat, reg_clear_last_set, last_set_in);
832 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
833 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)
834 && last_set_in[regno] == INSN_UID (insn))
835 last_set_in[regno] = 0;
839 #ifdef ENABLE_CHECKING
840 /* last_set_in should now be all-zero. */
841 for (regno = 0; regno < max_gcse_regno; regno++)
842 gcc_assert (!last_set_in[regno]);
845 /* Clear temporary marks. */
846 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
848 LAST_AVAIL_CHECK_FAILURE(ptr) = NULL_RTX;
849 if (ANTIC_STORE_LIST (ptr)
850 && (tmp = XEXP (ANTIC_STORE_LIST (ptr), 0)) == NULL_RTX)
851 ANTIC_STORE_LIST (ptr) = XEXP (ANTIC_STORE_LIST (ptr), 1);
855 /* Remove the stores that are not available anywhere, as there will
856 be no opportunity to optimize them. */
857 for (ptr = pre_ldst_mems, prev_next_ptr_ptr = &pre_ldst_mems;
859 ptr = *prev_next_ptr_ptr)
861 if (!AVAIL_STORE_LIST (ptr))
863 *prev_next_ptr_ptr = ptr->next;
864 htab_remove_elt_with_hash (pre_ldst_table, ptr, ptr->hash_index);
865 free_ldst_entry (ptr);
868 prev_next_ptr_ptr = &ptr->next;
871 ret = enumerate_ldsts ();
875 fprintf (dump_file, "ST_avail and ST_antic (shown under loads..)\n");
876 print_ldst_list (dump_file);
884 /* Insert an instruction at the beginning of a basic block, and update
885 the BB_HEAD if needed. */
888 insert_insn_start_basic_block (rtx insn, basic_block bb)
890 /* Insert at start of successor block. */
891 rtx prev = PREV_INSN (BB_HEAD (bb));
892 rtx before = BB_HEAD (bb);
895 if (! LABEL_P (before)
896 && !NOTE_INSN_BASIC_BLOCK_P (before))
899 if (prev == BB_END (bb))
901 before = NEXT_INSN (before);
904 insn = emit_insn_after_noloc (insn, prev, bb);
908 fprintf (dump_file, "STORE_MOTION insert store at start of BB %d:\n",
910 print_inline_rtx (dump_file, insn, 6);
911 fprintf (dump_file, "\n");
915 /* This routine will insert a store on an edge. EXPR is the ldst entry for
916 the memory reference, and E is the edge to insert it on. Returns nonzero
917 if an edge insertion was performed. */
920 insert_store (struct ls_expr * expr, edge e)
927 /* We did all the deleted before this insert, so if we didn't delete a
928 store, then we haven't set the reaching reg yet either. */
929 if (expr->reaching_reg == NULL_RTX)
932 if (e->flags & EDGE_FAKE)
935 reg = expr->reaching_reg;
936 insn = gen_move_insn (copy_rtx (expr->pattern), reg);
938 /* If we are inserting this expression on ALL predecessor edges of a BB,
939 insert it at the start of the BB, and reset the insert bits on the other
940 edges so we don't try to insert it on the other edges. */
942 FOR_EACH_EDGE (tmp, ei, e->dest->preds)
943 if (!(tmp->flags & EDGE_FAKE))
945 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
947 gcc_assert (index != EDGE_INDEX_NO_EDGE);
948 if (! TEST_BIT (pre_insert_map[index], expr->index))
952 /* If tmp is NULL, we found an insertion on every edge, blank the
953 insertion vector for these edges, and insert at the start of the BB. */
954 if (!tmp && bb != EXIT_BLOCK_PTR)
956 FOR_EACH_EDGE (tmp, ei, e->dest->preds)
958 int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
959 RESET_BIT (pre_insert_map[index], expr->index);
961 insert_insn_start_basic_block (insn, bb);
965 /* We can't put stores in the front of blocks pointed to by abnormal
966 edges since that may put a store where one didn't used to be. */
967 gcc_assert (!(e->flags & EDGE_ABNORMAL));
969 insert_insn_on_edge (insn, e);
973 fprintf (dump_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
974 e->src->index, e->dest->index);
975 print_inline_rtx (dump_file, insn, 6);
976 fprintf (dump_file, "\n");
982 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
983 memory location in SMEXPR set in basic block BB.
985 This could be rather expensive. */
988 remove_reachable_equiv_notes (basic_block bb, struct ls_expr *smexpr)
990 edge_iterator *stack, ei;
993 sbitmap visited = sbitmap_alloc (last_basic_block);
994 rtx last, insn, note;
995 rtx mem = smexpr->pattern;
997 stack = XNEWVEC (edge_iterator, n_basic_blocks);
999 ei = ei_start (bb->succs);
1001 sbitmap_zero (visited);
1003 act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
1011 sbitmap_free (visited);
1014 act = ei_edge (stack[--sp]);
1018 if (bb == EXIT_BLOCK_PTR
1019 || TEST_BIT (visited, bb->index))
1023 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
1026 SET_BIT (visited, bb->index);
1028 if (TEST_BIT (st_antloc[bb->index], smexpr->index))
1030 for (last = ANTIC_STORE_LIST (smexpr);
1031 BLOCK_FOR_INSN (XEXP (last, 0)) != bb;
1032 last = XEXP (last, 1))
1034 last = XEXP (last, 0);
1037 last = NEXT_INSN (BB_END (bb));
1039 for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
1042 note = find_reg_equal_equiv_note (insn);
1043 if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
1047 fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
1049 remove_note (insn, note);
1054 act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
1056 if (EDGE_COUNT (bb->succs) > 0)
1060 ei = ei_start (bb->succs);
1061 act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
1066 /* This routine will replace a store with a SET to a specified register. */
1069 replace_store_insn (rtx reg, rtx del, basic_block bb, struct ls_expr *smexpr)
1071 rtx insn, mem, note, set, ptr;
1073 mem = smexpr->pattern;
1074 insn = gen_move_insn (reg, SET_SRC (single_set (del)));
1076 for (ptr = ANTIC_STORE_LIST (smexpr); ptr; ptr = XEXP (ptr, 1))
1077 if (XEXP (ptr, 0) == del)
1079 XEXP (ptr, 0) = insn;
1083 /* Move the notes from the deleted insn to its replacement. */
1084 REG_NOTES (insn) = REG_NOTES (del);
1086 /* Emit the insn AFTER all the notes are transferred.
1087 This is cheaper since we avoid df rescanning for the note change. */
1088 insn = emit_insn_after (insn, del);
1093 "STORE_MOTION delete insn in BB %d:\n ", bb->index);
1094 print_inline_rtx (dump_file, del, 6);
1095 fprintf (dump_file, "\nSTORE_MOTION replaced with insn:\n ");
1096 print_inline_rtx (dump_file, insn, 6);
1097 fprintf (dump_file, "\n");
1102 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
1103 they are no longer accurate provided that they are reached by this
1104 definition, so drop them. */
1105 for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn))
1108 set = single_set (insn);
1111 if (exp_equiv_p (SET_DEST (set), mem, 0, true))
1113 note = find_reg_equal_equiv_note (insn);
1114 if (!note || !exp_equiv_p (XEXP (note, 0), mem, 0, true))
1118 fprintf (dump_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
1120 remove_note (insn, note);
1122 remove_reachable_equiv_notes (bb, smexpr);
1126 /* Delete a store, but copy the value that would have been stored into
1127 the reaching_reg for later storing. */
1130 delete_store (struct ls_expr * expr, basic_block bb)
1134 if (expr->reaching_reg == NULL_RTX)
1135 expr->reaching_reg = gen_reg_rtx_and_attrs (expr->pattern);
1137 reg = expr->reaching_reg;
1139 for (i = AVAIL_STORE_LIST (expr); i; i = XEXP (i, 1))
1142 if (BLOCK_FOR_INSN (del) == bb)
1144 /* We know there is only one since we deleted redundant
1145 ones during the available computation. */
1146 replace_store_insn (reg, del, bb, expr);
1152 /* Fill in available, anticipatable, transparent and kill vectors in
1153 STORE_DATA, based on lists of available and anticipatable stores. */
1155 build_store_vectors (void)
1158 int *regs_set_in_block;
1160 struct ls_expr * ptr;
1161 unsigned int max_gcse_regno = max_reg_num ();
1163 /* Build the gen_vector. This is any store in the table which is not killed
1164 by aliasing later in its block. */
1165 ae_gen = sbitmap_vector_alloc (last_basic_block, num_stores);
1166 sbitmap_vector_zero (ae_gen, last_basic_block);
1168 st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores);
1169 sbitmap_vector_zero (st_antloc, last_basic_block);
1171 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
1173 for (st = AVAIL_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1))
1175 insn = XEXP (st, 0);
1176 bb = BLOCK_FOR_INSN (insn);
1178 /* If we've already seen an available expression in this block,
1179 we can delete this one (It occurs earlier in the block). We'll
1180 copy the SRC expression to an unused register in case there
1181 are any side effects. */
1182 if (TEST_BIT (ae_gen[bb->index], ptr->index))
1184 rtx r = gen_reg_rtx_and_attrs (ptr->pattern);
1186 fprintf (dump_file, "Removing redundant store:\n");
1187 replace_store_insn (r, XEXP (st, 0), bb, ptr);
1190 SET_BIT (ae_gen[bb->index], ptr->index);
1193 for (st = ANTIC_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1))
1195 insn = XEXP (st, 0);
1196 bb = BLOCK_FOR_INSN (insn);
1197 SET_BIT (st_antloc[bb->index], ptr->index);
1201 ae_kill = sbitmap_vector_alloc (last_basic_block, num_stores);
1202 sbitmap_vector_zero (ae_kill, last_basic_block);
1204 transp = sbitmap_vector_alloc (last_basic_block, num_stores);
1205 sbitmap_vector_zero (transp, last_basic_block);
1206 regs_set_in_block = XNEWVEC (int, max_gcse_regno);
1210 FOR_BB_INSNS (bb, insn)
1214 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1216 unsigned int ref_regno = DF_REF_REGNO (*def_rec);
1217 if (ref_regno < max_gcse_regno)
1218 regs_set_in_block[DF_REF_REGNO (*def_rec)] = 1;
1222 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
1224 if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
1225 bb, regs_set_in_block, NULL))
1227 /* It should not be necessary to consider the expression
1228 killed if it is both anticipatable and available. */
1229 if (!TEST_BIT (st_antloc[bb->index], ptr->index)
1230 || !TEST_BIT (ae_gen[bb->index], ptr->index))
1231 SET_BIT (ae_kill[bb->index], ptr->index);
1234 SET_BIT (transp[bb->index], ptr->index);
1238 free (regs_set_in_block);
1242 dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
1243 dump_sbitmap_vector (dump_file, "st_kill", "", ae_kill, last_basic_block);
1244 dump_sbitmap_vector (dump_file, "Transpt", "", transp, last_basic_block);
1245 dump_sbitmap_vector (dump_file, "st_avloc", "", ae_gen, last_basic_block);
1249 /* Free memory used by store motion. */
1252 free_store_memory (void)
1257 sbitmap_vector_free (ae_gen);
1259 sbitmap_vector_free (ae_kill);
1261 sbitmap_vector_free (transp);
1263 sbitmap_vector_free (st_antloc);
1265 sbitmap_vector_free (pre_insert_map);
1267 sbitmap_vector_free (pre_delete_map);
1269 ae_gen = ae_kill = transp = st_antloc = NULL;
1270 pre_insert_map = pre_delete_map = NULL;
1273 /* Perform store motion. Much like gcse, except we move expressions the
1274 other way by looking at the flowgraph in reverse.
1275 Return non-zero if transformations are performed by the pass. */
1278 one_store_motion_pass (void)
1282 struct ls_expr * ptr;
1283 int update_flow = 0;
1285 gcse_subst_count = 0;
1286 gcse_create_count = 0;
1288 init_alias_analysis ();
1290 /* Find all the available and anticipatable stores. */
1291 num_stores = compute_store_table ();
1292 if (num_stores == 0)
1294 htab_delete (pre_ldst_table);
1295 pre_ldst_table = NULL;
1296 end_alias_analysis ();
1300 /* Now compute kill & transp vectors. */
1301 build_store_vectors ();
1302 add_noreturn_fake_exit_edges ();
1303 connect_infinite_loops_to_exit ();
1305 edge_list = pre_edge_rev_lcm (num_stores, transp, ae_gen,
1306 st_antloc, ae_kill, &pre_insert_map,
1309 /* Now we want to insert the new stores which are going to be needed. */
1310 for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
1312 /* If any of the edges we have above are abnormal, we can't move this
1314 for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
1315 if (TEST_BIT (pre_insert_map[x], ptr->index)
1316 && (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
1321 if (dump_file != NULL)
1323 "Can't replace store %d: abnormal edge from %d to %d\n",
1324 ptr->index, INDEX_EDGE (edge_list, x)->src->index,
1325 INDEX_EDGE (edge_list, x)->dest->index);
1329 /* Now we want to insert the new stores which are going to be needed. */
1332 if (TEST_BIT (pre_delete_map[bb->index], ptr->index))
1334 delete_store (ptr, bb);
1338 for (x = 0; x < NUM_EDGES (edge_list); x++)
1339 if (TEST_BIT (pre_insert_map[x], ptr->index))
1341 update_flow |= insert_store (ptr, INDEX_EDGE (edge_list, x));
1342 gcse_create_count++;
1347 commit_edge_insertions ();
1349 free_store_memory ();
1350 free_edge_list (edge_list);
1351 remove_fake_exit_edges ();
1352 end_alias_analysis ();
1356 fprintf (dump_file, "STORE_MOTION of %s, %d basic blocks, ",
1357 current_function_name (), n_basic_blocks);
1358 fprintf (dump_file, "%d substs, %d insns created\n",
1359 gcse_subst_count, gcse_create_count);
1362 return (gcse_subst_count > 0 || gcse_create_count > 0);
1367 gate_rtl_store_motion (void)
1369 return optimize > 0 && flag_gcse_sm
1370 && !cfun->calls_setjmp
1371 && optimize_function_for_speed_p (cfun)
1372 && dbg_cnt (store_motion);
1376 execute_rtl_store_motion (void)
1378 delete_unreachable_blocks ();
1379 df_note_add_problem ();
1381 flag_rerun_cse_after_global_opts |= one_store_motion_pass ();
1385 struct rtl_opt_pass pass_rtl_store_motion =
1389 "store_motion", /* name */
1390 gate_rtl_store_motion, /* gate */
1391 execute_rtl_store_motion, /* execute */
1394 0, /* static_pass_number */
1396 PROP_cfglayout, /* properties_required */
1397 0, /* properties_provided */
1398 0, /* properties_destroyed */
1399 0, /* todo_flags_start */
1400 TODO_df_finish | TODO_verify_rtl_sharing |
1402 TODO_verify_flow | TODO_ggc_collect /* todo_flags_finish */