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"
44 #include "tree-pass.h"
49 /* This pass implements downward store motion.
50 As of May 1, 2009, the pass is not enabled by default on any target,
51 but bootstrap completes on ia64 and x86_64 with the pass enabled. */
54 - remove_reachable_equiv_notes is an incomprehensible pile of goo and
55 a compile time hog that needs a rewrite (maybe cache st_exprs to
56 invalidate REG_EQUAL/REG_EQUIV notes for?).
57 - pattern_regs in st_expr should be a regset (on its own obstack).
58 - antic_stores and avail_stores should be VECs instead of lists.
59 - store_motion_mems should be a VEC instead of a list.
60 - there should be an alloc pool for struct st_expr objects.
61 - investigate whether it is helpful to make the address of an st_expr
63 - when GIMPLE alias information is exported, the effectiveness of this
64 pass should be re-evaluated.
67 /* This is a list of store expressions (MEMs). The structure is used
68 as an expression table to track stores which look interesting, and
69 might be moveable towards the exit block. */
73 /* Pattern of this mem. */
75 /* List of registers mentioned by the mem. */
77 /* INSN list of stores that are locally anticipatable. */
79 /* INSN list of stores that are locally available. */
81 /* Next in the list. */
82 struct st_expr
* next
;
83 /* Store ID in the dataflow bitmaps. */
85 /* Hash value for the hash table. */
86 unsigned int hash_index
;
87 /* Register holding the stored expression when a store is moved.
88 This field is also used as a cache in find_moveable_store, see
89 LAST_AVAIL_CHECK_FAILURE below. */
93 /* Head of the list of load/store memory refs. */
94 static struct st_expr
* store_motion_mems
= NULL
;
96 /* Hashtable for the load/store memory refs. */
97 static htab_t store_motion_mems_table
= NULL
;
99 /* These bitmaps will hold the local dataflow properties per basic block. */
100 static sbitmap
*st_kill
, *st_avloc
, *st_antloc
, *st_transp
;
102 /* Nonzero for expressions which should be inserted on a specific edge. */
103 static sbitmap
*st_insert_map
;
105 /* Nonzero for expressions which should be deleted in a specific block. */
106 static sbitmap
*st_delete_map
;
108 /* Global holding the number of store expressions we are dealing with. */
109 static int num_stores
;
111 /* Contains the edge_list returned by pre_edge_lcm. */
112 static struct edge_list
*edge_list
;
115 pre_st_expr_hash (const void *p
)
117 int do_not_record_p
= 0;
118 const struct st_expr
*const x
= (const struct st_expr
*) p
;
119 return hash_rtx (x
->pattern
, GET_MODE (x
->pattern
), &do_not_record_p
, NULL
, false);
123 pre_st_expr_eq (const void *p1
, const void *p2
)
125 const struct st_expr
*const ptr1
= (const struct st_expr
*) p1
,
126 *const ptr2
= (const struct st_expr
*) p2
;
127 return exp_equiv_p (ptr1
->pattern
, ptr2
->pattern
, 0, true);
130 /* This will search the st_expr list for a matching expression. If it
131 doesn't find one, we create one and initialize it. */
133 static struct st_expr
*
134 st_expr_entry (rtx x
)
136 int do_not_record_p
= 0;
137 struct st_expr
* ptr
;
142 hash
= hash_rtx (x
, GET_MODE (x
), &do_not_record_p
,
143 NULL
, /*have_reg_qty=*/false);
146 slot
= htab_find_slot_with_hash (store_motion_mems_table
, &e
, hash
, INSERT
);
148 return (struct st_expr
*)*slot
;
150 ptr
= XNEW (struct st_expr
);
152 ptr
->next
= store_motion_mems
;
154 ptr
->pattern_regs
= NULL_RTX
;
155 ptr
->antic_stores
= NULL_RTX
;
156 ptr
->avail_stores
= NULL_RTX
;
157 ptr
->reaching_reg
= NULL_RTX
;
159 ptr
->hash_index
= hash
;
160 store_motion_mems
= ptr
;
166 /* Free up an individual st_expr entry. */
169 free_st_expr_entry (struct st_expr
* ptr
)
171 free_INSN_LIST_list (& ptr
->antic_stores
);
172 free_INSN_LIST_list (& ptr
->avail_stores
);
177 /* Free up all memory associated with the st_expr list. */
180 free_store_motion_mems (void)
182 if (store_motion_mems_table
)
183 htab_delete (store_motion_mems_table
);
184 store_motion_mems_table
= NULL
;
186 while (store_motion_mems
)
188 struct st_expr
* tmp
= store_motion_mems
;
189 store_motion_mems
= store_motion_mems
->next
;
190 free_st_expr_entry (tmp
);
192 store_motion_mems
= NULL
;
195 /* Assign each element of the list of mems a monotonically increasing value. */
198 enumerate_store_motion_mems (void)
200 struct st_expr
* ptr
;
203 for (ptr
= store_motion_mems
; ptr
!= NULL
; ptr
= ptr
->next
)
209 /* Return first item in the list. */
211 static inline struct st_expr
*
214 return store_motion_mems
;
217 /* Return the next item in the list after the specified one. */
219 static inline struct st_expr
*
220 next_st_expr (struct st_expr
* ptr
)
225 /* Dump debugging info about the store_motion_mems list. */
228 print_store_motion_mems (FILE * file
)
230 struct st_expr
* ptr
;
232 fprintf (dump_file
, "STORE_MOTION list of MEM exprs considered:\n");
234 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
236 fprintf (file
, " Pattern (%3d): ", ptr
->index
);
238 print_rtl (file
, ptr
->pattern
);
240 fprintf (file
, "\n ANTIC stores : ");
242 if (ptr
->antic_stores
)
243 print_rtl (file
, ptr
->antic_stores
);
245 fprintf (file
, "(nil)");
247 fprintf (file
, "\n AVAIL stores : ");
249 if (ptr
->avail_stores
)
250 print_rtl (file
, ptr
->avail_stores
);
252 fprintf (file
, "(nil)");
254 fprintf (file
, "\n\n");
257 fprintf (file
, "\n");
260 /* Return zero if some of the registers in list X are killed
261 due to set of registers in bitmap REGS_SET. */
264 store_ops_ok (const_rtx x
, int *regs_set
)
268 for (; x
; x
= XEXP (x
, 1))
271 if (regs_set
[REGNO(reg
)])
278 /* Helper for extract_mentioned_regs. */
281 extract_mentioned_regs_1 (rtx
*loc
, void *data
)
283 rtx
*mentioned_regs_p
= (rtx
*) data
;
286 *mentioned_regs_p
= alloc_EXPR_LIST (0, *loc
, *mentioned_regs_p
);
291 /* Returns a list of registers mentioned in X.
292 FIXME: A regset would be prettier and less expensive. */
295 extract_mentioned_regs (rtx x
)
297 rtx mentioned_regs
= NULL
;
298 for_each_rtx (&x
, extract_mentioned_regs_1
, &mentioned_regs
);
299 return mentioned_regs
;
302 /* Check to see if the load X is aliased with STORE_PATTERN.
303 AFTER is true if we are checking the case when STORE_PATTERN occurs
307 load_kills_store (const_rtx x
, const_rtx store_pattern
, int after
)
310 return anti_dependence (x
, store_pattern
);
312 return true_dependence (store_pattern
, GET_MODE (store_pattern
), x
,
316 /* Go through the entire rtx X, looking for any loads which might alias
317 STORE_PATTERN. Return true if found.
318 AFTER is true if we are checking the case when STORE_PATTERN occurs
322 find_loads (const_rtx x
, const_rtx store_pattern
, int after
)
331 if (GET_CODE (x
) == SET
)
336 if (load_kills_store (x
, store_pattern
, after
))
340 /* Recursively process the insn. */
341 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
343 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0 && !ret
; i
--)
346 ret
|= find_loads (XEXP (x
, i
), store_pattern
, after
);
347 else if (fmt
[i
] == 'E')
348 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
349 ret
|= find_loads (XVECEXP (x
, i
, j
), store_pattern
, after
);
354 /* Go through pattern PAT looking for any loads which might kill the
355 store in X. Return true if found.
356 AFTER is true if we are checking the case when loads kill X occurs
357 after the insn for PAT. */
360 store_killed_in_pat (const_rtx x
, const_rtx pat
, int after
)
362 if (GET_CODE (pat
) == SET
)
364 rtx dest
= SET_DEST (pat
);
366 if (GET_CODE (dest
) == ZERO_EXTRACT
)
367 dest
= XEXP (dest
, 0);
369 /* Check for memory stores to aliased objects. */
371 && !exp_equiv_p (dest
, x
, 0, true))
375 if (output_dependence (dest
, x
))
380 if (output_dependence (x
, dest
))
386 if (find_loads (pat
, x
, after
))
392 /* Check if INSN kills the store pattern X (is aliased with it).
393 AFTER is true if we are checking the case when store X occurs
394 after the insn. Return true if it does. */
397 store_killed_in_insn (const_rtx x
, const_rtx x_regs
, const_rtx insn
, int after
)
399 const_rtx reg
, base
, note
, pat
;
406 /* A normal or pure call might read from pattern,
407 but a const call will not. */
408 if (!RTL_CONST_CALL_P (insn
))
411 /* But even a const call reads its parameters. Check whether the
412 base of some of registers used in mem is stack pointer. */
413 for (reg
= x_regs
; reg
; reg
= XEXP (reg
, 1))
415 base
= find_base_term (XEXP (reg
, 0));
417 || (GET_CODE (base
) == ADDRESS
418 && GET_MODE (base
) == Pmode
419 && XEXP (base
, 0) == stack_pointer_rtx
))
426 pat
= PATTERN (insn
);
427 if (GET_CODE (pat
) == SET
)
429 if (store_killed_in_pat (x
, pat
, after
))
432 else if (GET_CODE (pat
) == PARALLEL
)
436 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
437 if (store_killed_in_pat (x
, XVECEXP (pat
, 0, i
), after
))
440 else if (find_loads (PATTERN (insn
), x
, after
))
443 /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
444 location aliased with X, then this insn kills X. */
445 note
= find_reg_equal_equiv_note (insn
);
448 note
= XEXP (note
, 0);
450 /* However, if the note represents a must alias rather than a may
451 alias relationship, then it does not kill X. */
452 if (exp_equiv_p (note
, x
, 0, true))
455 /* See if there are any aliased loads in the note. */
456 return find_loads (note
, x
, after
);
459 /* Returns true if the expression X is loaded or clobbered on or after INSN
460 within basic block BB. REGS_SET_AFTER is bitmap of registers set in
461 or after the insn. X_REGS is list of registers mentioned in X. If the store
462 is killed, return the last insn in that it occurs in FAIL_INSN. */
465 store_killed_after (const_rtx x
, const_rtx x_regs
, const_rtx insn
, const_basic_block bb
,
466 int *regs_set_after
, rtx
*fail_insn
)
468 rtx last
= BB_END (bb
), act
;
470 if (!store_ops_ok (x_regs
, regs_set_after
))
472 /* We do not know where it will happen. */
474 *fail_insn
= NULL_RTX
;
478 /* Scan from the end, so that fail_insn is determined correctly. */
479 for (act
= last
; act
!= PREV_INSN (insn
); act
= PREV_INSN (act
))
480 if (store_killed_in_insn (x
, x_regs
, act
, false))
490 /* Returns true if the expression X is loaded or clobbered on or before INSN
491 within basic block BB. X_REGS is list of registers mentioned in X.
492 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
494 store_killed_before (const_rtx x
, const_rtx x_regs
, const_rtx insn
, const_basic_block bb
,
495 int *regs_set_before
)
497 rtx first
= BB_HEAD (bb
);
499 if (!store_ops_ok (x_regs
, regs_set_before
))
502 for ( ; insn
!= PREV_INSN (first
); insn
= PREV_INSN (insn
))
503 if (store_killed_in_insn (x
, x_regs
, insn
, true))
509 /* The last insn in the basic block that compute_store_table is processing,
510 where store_killed_after is true for X.
511 Since we go through the basic block from BB_END to BB_HEAD, this is
512 also the available store at the end of the basic block. Therefore
513 this is in effect a cache, to avoid calling store_killed_after for
514 equivalent aliasing store expressions.
515 This value is only meaningful during the computation of the store
516 table. We hi-jack the REACHING_REG field of struct st_expr to save
518 #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
520 /* Determine whether INSN is MEM store pattern that we will consider moving.
521 REGS_SET_BEFORE is bitmap of registers set before (and including) the
522 current insn, REGS_SET_AFTER is bitmap of registers set after (and
523 including) the insn in this basic block. We must be passing through BB from
524 head to end, as we are using this fact to speed things up.
526 The results are stored this way:
528 -- the first anticipatable expression is added into ANTIC_STORES
529 -- if the processed expression is not anticipatable, NULL_RTX is added
530 there instead, so that we can use it as indicator that no further
531 expression of this type may be anticipatable
532 -- if the expression is available, it is added as head of AVAIL_STORES;
533 consequently, all of them but this head are dead and may be deleted.
534 -- if the expression is not available, the insn due to that it fails to be
535 available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
537 The things are complicated a bit by fact that there already may be stores
538 to the same MEM from other blocks; also caller must take care of the
539 necessary cleanup of the temporary markers after end of the basic block.
543 find_moveable_store (rtx insn
, int *regs_set_before
, int *regs_set_after
)
545 struct st_expr
* ptr
;
547 int check_anticipatable
, check_available
;
548 basic_block bb
= BLOCK_FOR_INSN (insn
);
550 set
= single_set (insn
);
554 dest
= SET_DEST (set
);
556 if (! MEM_P (dest
) || MEM_VOLATILE_P (dest
)
557 || GET_MODE (dest
) == BLKmode
)
560 if (side_effects_p (dest
))
563 /* If we are handling exceptions, we must be careful with memory references
564 that may trap. If we are not, the behavior is undefined, so we may just
566 if (flag_non_call_exceptions
&& may_trap_p (dest
))
569 /* Even if the destination cannot trap, the source may. In this case we'd
570 need to handle updating the REG_EH_REGION note. */
571 if (find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
))
574 /* Make sure that the SET_SRC of this store insns can be assigned to
575 a register, or we will fail later on in replace_store_insn, which
576 assumes that we can do this. But sometimes the target machine has
577 oddities like MEM read-modify-write instruction. See for example
579 if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set
)))
582 ptr
= st_expr_entry (dest
);
583 if (!ptr
->pattern_regs
)
584 ptr
->pattern_regs
= extract_mentioned_regs (dest
);
586 /* Do not check for anticipatability if we either found one anticipatable
587 store already, or tested for one and found out that it was killed. */
588 check_anticipatable
= 0;
589 if (!ptr
->antic_stores
)
590 check_anticipatable
= 1;
593 tmp
= XEXP (ptr
->antic_stores
, 0);
595 && BLOCK_FOR_INSN (tmp
) != bb
)
596 check_anticipatable
= 1;
598 if (check_anticipatable
)
600 if (store_killed_before (dest
, ptr
->pattern_regs
, insn
, bb
, regs_set_before
))
604 ptr
->antic_stores
= alloc_INSN_LIST (tmp
, ptr
->antic_stores
);
607 /* It is not necessary to check whether store is available if we did
608 it successfully before; if we failed before, do not bother to check
609 until we reach the insn that caused us to fail. */
611 if (!ptr
->avail_stores
)
615 tmp
= XEXP (ptr
->avail_stores
, 0);
616 if (BLOCK_FOR_INSN (tmp
) != bb
)
621 /* Check that we have already reached the insn at that the check
623 if (LAST_AVAIL_CHECK_FAILURE (ptr
))
625 for (tmp
= BB_END (bb
);
626 tmp
!= insn
&& tmp
!= LAST_AVAIL_CHECK_FAILURE (ptr
);
627 tmp
= PREV_INSN (tmp
))
633 check_available
= store_killed_after (dest
, ptr
->pattern_regs
, insn
,
635 &LAST_AVAIL_CHECK_FAILURE (ptr
));
637 if (!check_available
)
638 ptr
->avail_stores
= alloc_INSN_LIST (insn
, ptr
->avail_stores
);
641 /* Find available and anticipatable stores. */
644 compute_store_table (void)
648 #ifdef ENABLE_CHECKING
653 int *last_set_in
, *already_set
;
654 struct st_expr
* ptr
, **prev_next_ptr_ptr
;
655 unsigned int max_gcse_regno
= max_reg_num ();
657 store_motion_mems
= NULL
;
658 store_motion_mems_table
= htab_create (13, pre_st_expr_hash
,
659 pre_st_expr_eq
, NULL
);
660 last_set_in
= XCNEWVEC (int, max_gcse_regno
);
661 already_set
= XNEWVEC (int, max_gcse_regno
);
663 /* Find all the stores we care about. */
666 /* First compute the registers set in this block. */
667 FOR_BB_INSNS (bb
, insn
)
673 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
674 last_set_in
[DF_REF_REGNO (*def_rec
)] = INSN_UID (insn
);
677 /* Now find the stores. */
678 memset (already_set
, 0, sizeof (int) * max_gcse_regno
);
679 FOR_BB_INSNS (bb
, insn
)
684 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
685 already_set
[DF_REF_REGNO (*def_rec
)] = INSN_UID (insn
);
687 /* Now that we've marked regs, look for stores. */
688 find_moveable_store (insn
, already_set
, last_set_in
);
690 /* Unmark regs that are no longer set. */
691 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
692 if (last_set_in
[DF_REF_REGNO (*def_rec
)] == INSN_UID (insn
))
693 last_set_in
[DF_REF_REGNO (*def_rec
)] = 0;
696 #ifdef ENABLE_CHECKING
697 /* last_set_in should now be all-zero. */
698 for (regno
= 0; regno
< max_gcse_regno
; regno
++)
699 gcc_assert (!last_set_in
[regno
]);
702 /* Clear temporary marks. */
703 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
705 LAST_AVAIL_CHECK_FAILURE (ptr
) = NULL_RTX
;
706 if (ptr
->antic_stores
707 && (tmp
= XEXP (ptr
->antic_stores
, 0)) == NULL_RTX
)
708 ptr
->antic_stores
= XEXP (ptr
->antic_stores
, 1);
712 /* Remove the stores that are not available anywhere, as there will
713 be no opportunity to optimize them. */
714 for (ptr
= store_motion_mems
, prev_next_ptr_ptr
= &store_motion_mems
;
716 ptr
= *prev_next_ptr_ptr
)
718 if (! ptr
->avail_stores
)
720 *prev_next_ptr_ptr
= ptr
->next
;
721 htab_remove_elt_with_hash (store_motion_mems_table
,
722 ptr
, ptr
->hash_index
);
723 free_st_expr_entry (ptr
);
726 prev_next_ptr_ptr
= &ptr
->next
;
729 ret
= enumerate_store_motion_mems ();
732 print_store_motion_mems (dump_file
);
739 /* In all code following after this, REACHING_REG has its original
740 meaning again. Avoid confusion, and undef the accessor macro for
741 the temporary marks usage in compute_store_table. */
742 #undef LAST_AVAIL_CHECK_FAILURE
744 /* Insert an instruction at the beginning of a basic block, and update
745 the BB_HEAD if needed. */
748 insert_insn_start_basic_block (rtx insn
, basic_block bb
)
750 /* Insert at start of successor block. */
751 rtx prev
= PREV_INSN (BB_HEAD (bb
));
752 rtx before
= BB_HEAD (bb
);
755 if (! LABEL_P (before
)
756 && !NOTE_INSN_BASIC_BLOCK_P (before
))
759 if (prev
== BB_END (bb
))
761 before
= NEXT_INSN (before
);
764 insn
= emit_insn_after_noloc (insn
, prev
, bb
);
768 fprintf (dump_file
, "STORE_MOTION insert store at start of BB %d:\n",
770 print_inline_rtx (dump_file
, insn
, 6);
771 fprintf (dump_file
, "\n");
775 /* This routine will insert a store on an edge. EXPR is the st_expr entry for
776 the memory reference, and E is the edge to insert it on. Returns nonzero
777 if an edge insertion was performed. */
780 insert_store (struct st_expr
* expr
, edge e
)
787 /* We did all the deleted before this insert, so if we didn't delete a
788 store, then we haven't set the reaching reg yet either. */
789 if (expr
->reaching_reg
== NULL_RTX
)
792 if (e
->flags
& EDGE_FAKE
)
795 reg
= expr
->reaching_reg
;
796 insn
= gen_move_insn (copy_rtx (expr
->pattern
), reg
);
798 /* If we are inserting this expression on ALL predecessor edges of a BB,
799 insert it at the start of the BB, and reset the insert bits on the other
800 edges so we don't try to insert it on the other edges. */
802 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
803 if (!(tmp
->flags
& EDGE_FAKE
))
805 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
807 gcc_assert (index
!= EDGE_INDEX_NO_EDGE
);
808 if (! TEST_BIT (st_insert_map
[index
], expr
->index
))
812 /* If tmp is NULL, we found an insertion on every edge, blank the
813 insertion vector for these edges, and insert at the start of the BB. */
814 if (!tmp
&& bb
!= EXIT_BLOCK_PTR
)
816 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
818 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
819 RESET_BIT (st_insert_map
[index
], expr
->index
);
821 insert_insn_start_basic_block (insn
, bb
);
825 /* We can't put stores in the front of blocks pointed to by abnormal
826 edges since that may put a store where one didn't used to be. */
827 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
829 insert_insn_on_edge (insn
, e
);
833 fprintf (dump_file
, "STORE_MOTION insert insn on edge (%d, %d):\n",
834 e
->src
->index
, e
->dest
->index
);
835 print_inline_rtx (dump_file
, insn
, 6);
836 fprintf (dump_file
, "\n");
842 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
843 memory location in SMEXPR set in basic block BB.
845 This could be rather expensive. */
848 remove_reachable_equiv_notes (basic_block bb
, struct st_expr
*smexpr
)
850 edge_iterator
*stack
, ei
;
853 sbitmap visited
= sbitmap_alloc (last_basic_block
);
854 rtx last
, insn
, note
;
855 rtx mem
= smexpr
->pattern
;
857 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
);
859 ei
= ei_start (bb
->succs
);
861 sbitmap_zero (visited
);
863 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
871 sbitmap_free (visited
);
874 act
= ei_edge (stack
[--sp
]);
878 if (bb
== EXIT_BLOCK_PTR
879 || TEST_BIT (visited
, bb
->index
))
883 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
886 SET_BIT (visited
, bb
->index
);
888 if (TEST_BIT (st_antloc
[bb
->index
], smexpr
->index
))
890 for (last
= smexpr
->antic_stores
;
891 BLOCK_FOR_INSN (XEXP (last
, 0)) != bb
;
892 last
= XEXP (last
, 1))
894 last
= XEXP (last
, 0);
897 last
= NEXT_INSN (BB_END (bb
));
899 for (insn
= BB_HEAD (bb
); insn
!= last
; insn
= NEXT_INSN (insn
))
902 note
= find_reg_equal_equiv_note (insn
);
903 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
907 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
909 remove_note (insn
, note
);
914 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
916 if (EDGE_COUNT (bb
->succs
) > 0)
920 ei
= ei_start (bb
->succs
);
921 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
926 /* This routine will replace a store with a SET to a specified register. */
929 replace_store_insn (rtx reg
, rtx del
, basic_block bb
, struct st_expr
*smexpr
)
931 rtx insn
, mem
, note
, set
, ptr
;
933 mem
= smexpr
->pattern
;
934 insn
= gen_move_insn (reg
, SET_SRC (single_set (del
)));
936 for (ptr
= smexpr
->antic_stores
; ptr
; ptr
= XEXP (ptr
, 1))
937 if (XEXP (ptr
, 0) == del
)
939 XEXP (ptr
, 0) = insn
;
943 /* Move the notes from the deleted insn to its replacement. */
944 REG_NOTES (insn
) = REG_NOTES (del
);
946 /* Emit the insn AFTER all the notes are transferred.
947 This is cheaper since we avoid df rescanning for the note change. */
948 insn
= emit_insn_after (insn
, del
);
953 "STORE_MOTION delete insn in BB %d:\n ", bb
->index
);
954 print_inline_rtx (dump_file
, del
, 6);
955 fprintf (dump_file
, "\nSTORE_MOTION replaced with insn:\n ");
956 print_inline_rtx (dump_file
, insn
, 6);
957 fprintf (dump_file
, "\n");
962 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
963 they are no longer accurate provided that they are reached by this
964 definition, so drop them. */
965 for (; insn
!= NEXT_INSN (BB_END (bb
)); insn
= NEXT_INSN (insn
))
968 set
= single_set (insn
);
971 if (exp_equiv_p (SET_DEST (set
), mem
, 0, true))
973 note
= find_reg_equal_equiv_note (insn
);
974 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
978 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
980 remove_note (insn
, note
);
982 remove_reachable_equiv_notes (bb
, smexpr
);
986 /* Delete a store, but copy the value that would have been stored into
987 the reaching_reg for later storing. */
990 delete_store (struct st_expr
* expr
, basic_block bb
)
994 if (expr
->reaching_reg
== NULL_RTX
)
995 expr
->reaching_reg
= gen_reg_rtx_and_attrs (expr
->pattern
);
997 reg
= expr
->reaching_reg
;
999 for (i
= expr
->avail_stores
; i
; i
= XEXP (i
, 1))
1002 if (BLOCK_FOR_INSN (del
) == bb
)
1004 /* We know there is only one since we deleted redundant
1005 ones during the available computation. */
1006 replace_store_insn (reg
, del
, bb
, expr
);
1012 /* Fill in available, anticipatable, transparent and kill vectors in
1013 STORE_DATA, based on lists of available and anticipatable stores. */
1015 build_store_vectors (void)
1018 int *regs_set_in_block
;
1020 struct st_expr
* ptr
;
1021 unsigned int max_gcse_regno
= max_reg_num ();
1023 /* Build the gen_vector. This is any store in the table which is not killed
1024 by aliasing later in its block. */
1025 st_avloc
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
1026 sbitmap_vector_zero (st_avloc
, last_basic_block
);
1028 st_antloc
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
1029 sbitmap_vector_zero (st_antloc
, last_basic_block
);
1031 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1033 for (st
= ptr
->avail_stores
; st
!= NULL
; st
= XEXP (st
, 1))
1035 insn
= XEXP (st
, 0);
1036 bb
= BLOCK_FOR_INSN (insn
);
1038 /* If we've already seen an available expression in this block,
1039 we can delete this one (It occurs earlier in the block). We'll
1040 copy the SRC expression to an unused register in case there
1041 are any side effects. */
1042 if (TEST_BIT (st_avloc
[bb
->index
], ptr
->index
))
1044 rtx r
= gen_reg_rtx_and_attrs (ptr
->pattern
);
1046 fprintf (dump_file
, "Removing redundant store:\n");
1047 replace_store_insn (r
, XEXP (st
, 0), bb
, ptr
);
1050 SET_BIT (st_avloc
[bb
->index
], ptr
->index
);
1053 for (st
= ptr
->antic_stores
; st
!= NULL
; st
= XEXP (st
, 1))
1055 insn
= XEXP (st
, 0);
1056 bb
= BLOCK_FOR_INSN (insn
);
1057 SET_BIT (st_antloc
[bb
->index
], ptr
->index
);
1061 st_kill
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
1062 sbitmap_vector_zero (st_kill
, last_basic_block
);
1064 st_transp
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
1065 sbitmap_vector_zero (st_transp
, last_basic_block
);
1066 regs_set_in_block
= XNEWVEC (int, max_gcse_regno
);
1070 FOR_BB_INSNS (bb
, insn
)
1074 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
1076 unsigned int ref_regno
= DF_REF_REGNO (*def_rec
);
1077 if (ref_regno
< max_gcse_regno
)
1078 regs_set_in_block
[DF_REF_REGNO (*def_rec
)] = 1;
1082 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1084 if (store_killed_after (ptr
->pattern
, ptr
->pattern_regs
, BB_HEAD (bb
),
1085 bb
, regs_set_in_block
, NULL
))
1087 /* It should not be necessary to consider the expression
1088 killed if it is both anticipatable and available. */
1089 if (!TEST_BIT (st_antloc
[bb
->index
], ptr
->index
)
1090 || !TEST_BIT (st_avloc
[bb
->index
], ptr
->index
))
1091 SET_BIT (st_kill
[bb
->index
], ptr
->index
);
1094 SET_BIT (st_transp
[bb
->index
], ptr
->index
);
1098 free (regs_set_in_block
);
1102 dump_sbitmap_vector (dump_file
, "st_antloc", "", st_antloc
, last_basic_block
);
1103 dump_sbitmap_vector (dump_file
, "st_kill", "", st_kill
, last_basic_block
);
1104 dump_sbitmap_vector (dump_file
, "st_transp", "", st_transp
, last_basic_block
);
1105 dump_sbitmap_vector (dump_file
, "st_avloc", "", st_avloc
, last_basic_block
);
1109 /* Free memory used by store motion. */
1112 free_store_memory (void)
1114 free_store_motion_mems ();
1117 sbitmap_vector_free (st_avloc
);
1119 sbitmap_vector_free (st_kill
);
1121 sbitmap_vector_free (st_transp
);
1123 sbitmap_vector_free (st_antloc
);
1125 sbitmap_vector_free (st_insert_map
);
1127 sbitmap_vector_free (st_delete_map
);
1129 st_avloc
= st_kill
= st_transp
= st_antloc
= NULL
;
1130 st_insert_map
= st_delete_map
= NULL
;
1133 /* Perform store motion. Much like gcse, except we move expressions the
1134 other way by looking at the flowgraph in reverse.
1135 Return non-zero if transformations are performed by the pass. */
1138 one_store_motion_pass (void)
1142 struct st_expr
* ptr
;
1143 int did_edge_inserts
= 0;
1144 int n_stores_deleted
= 0;
1145 int n_stores_created
= 0;
1147 init_alias_analysis ();
1149 /* Find all the available and anticipatable stores. */
1150 num_stores
= compute_store_table ();
1151 if (num_stores
== 0)
1153 htab_delete (store_motion_mems_table
);
1154 store_motion_mems_table
= NULL
;
1155 end_alias_analysis ();
1159 /* Now compute kill & transp vectors. */
1160 build_store_vectors ();
1161 add_noreturn_fake_exit_edges ();
1162 connect_infinite_loops_to_exit ();
1164 edge_list
= pre_edge_rev_lcm (num_stores
, st_transp
, st_avloc
,
1165 st_antloc
, st_kill
, &st_insert_map
,
1168 /* Now we want to insert the new stores which are going to be needed. */
1169 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1171 /* If any of the edges we have above are abnormal, we can't move this
1173 for (x
= NUM_EDGES (edge_list
) - 1; x
>= 0; x
--)
1174 if (TEST_BIT (st_insert_map
[x
], ptr
->index
)
1175 && (INDEX_EDGE (edge_list
, x
)->flags
& EDGE_ABNORMAL
))
1180 if (dump_file
!= NULL
)
1182 "Can't replace store %d: abnormal edge from %d to %d\n",
1183 ptr
->index
, INDEX_EDGE (edge_list
, x
)->src
->index
,
1184 INDEX_EDGE (edge_list
, x
)->dest
->index
);
1188 /* Now we want to insert the new stores which are going to be needed. */
1191 if (TEST_BIT (st_delete_map
[bb
->index
], ptr
->index
))
1193 delete_store (ptr
, bb
);
1197 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
1198 if (TEST_BIT (st_insert_map
[x
], ptr
->index
))
1200 did_edge_inserts
|= insert_store (ptr
, INDEX_EDGE (edge_list
, x
));
1205 if (did_edge_inserts
)
1206 commit_edge_insertions ();
1208 free_store_memory ();
1209 free_edge_list (edge_list
);
1210 remove_fake_exit_edges ();
1211 end_alias_analysis ();
1215 fprintf (dump_file
, "STORE_MOTION of %s, %d basic blocks, ",
1216 current_function_name (), n_basic_blocks
);
1217 fprintf (dump_file
, "%d insns deleted, %d insns created\n",
1218 n_stores_deleted
, n_stores_created
);
1221 return (n_stores_deleted
> 0 || n_stores_created
> 0);
1226 gate_rtl_store_motion (void)
1228 return optimize
> 0 && flag_gcse_sm
1229 && !cfun
->calls_setjmp
1230 && optimize_function_for_speed_p (cfun
)
1231 && dbg_cnt (store_motion
);
1235 execute_rtl_store_motion (void)
1237 delete_unreachable_blocks ();
1238 df_note_add_problem ();
1240 flag_rerun_cse_after_global_opts
|= one_store_motion_pass ();
1244 struct rtl_opt_pass pass_rtl_store_motion
=
1248 "store_motion", /* name */
1249 gate_rtl_store_motion
, /* gate */
1250 execute_rtl_store_motion
, /* execute */
1253 0, /* static_pass_number */
1255 PROP_cfglayout
, /* properties_required */
1256 0, /* properties_provided */
1257 0, /* properties_destroyed */
1258 0, /* todo_flags_start */
1259 TODO_df_finish
| TODO_verify_rtl_sharing
|
1261 TODO_verify_flow
| TODO_ggc_collect
/* todo_flags_finish */