1 /* Store motion via Lazy Code Motion on the reverse CFG.
2 Copyright (C) 1997-2013 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
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
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/>. */
22 #include "coretypes.h"
24 #include "diagnostic-core.h"
31 #include "hard-reg-set.h"
33 #include "insn-config.h"
35 #include "basic-block.h"
41 #include "tree-pass.h"
42 #include "hash-table.h"
46 /* This pass implements downward store motion.
47 As of May 1, 2009, the pass is not enabled by default on any target,
48 but bootstrap completes on ia64 and x86_64 with the pass enabled. */
51 - remove_reachable_equiv_notes is an incomprehensible pile of goo and
52 a compile time hog that needs a rewrite (maybe cache st_exprs to
53 invalidate REG_EQUAL/REG_EQUIV notes for?).
54 - pattern_regs in st_expr should be a regset (on its own obstack).
55 - antic_stores and avail_stores should be VECs instead of lists.
56 - store_motion_mems should be a vec instead of a list.
57 - there should be an alloc pool for struct st_expr objects.
58 - investigate whether it is helpful to make the address of an st_expr
60 - when GIMPLE alias information is exported, the effectiveness of this
61 pass should be re-evaluated.
64 /* This is a list of store expressions (MEMs). The structure is used
65 as an expression table to track stores which look interesting, and
66 might be moveable towards the exit block. */
70 /* Pattern of this mem. */
72 /* List of registers mentioned by the mem. */
74 /* INSN list of stores that are locally anticipatable. */
76 /* INSN list of stores that are locally available. */
78 /* Next in the list. */
79 struct st_expr
* next
;
80 /* Store ID in the dataflow bitmaps. */
82 /* Hash value for the hash table. */
83 unsigned int hash_index
;
84 /* Register holding the stored expression when a store is moved.
85 This field is also used as a cache in find_moveable_store, see
86 LAST_AVAIL_CHECK_FAILURE below. */
90 /* Head of the list of load/store memory refs. */
91 static struct st_expr
* store_motion_mems
= NULL
;
93 /* These bitmaps will hold the local dataflow properties per basic block. */
94 static sbitmap
*st_kill
, *st_avloc
, *st_antloc
, *st_transp
;
96 /* Nonzero for expressions which should be inserted on a specific edge. */
97 static sbitmap
*st_insert_map
;
99 /* Nonzero for expressions which should be deleted in a specific block. */
100 static sbitmap
*st_delete_map
;
102 /* Global holding the number of store expressions we are dealing with. */
103 static int num_stores
;
105 /* Contains the edge_list returned by pre_edge_lcm. */
106 static struct edge_list
*edge_list
;
108 /* Hashtable helpers. */
110 struct st_expr_hasher
: typed_noop_remove
<st_expr
>
112 typedef st_expr value_type
;
113 typedef st_expr compare_type
;
114 static inline hashval_t
hash (const value_type
*);
115 static inline bool equal (const value_type
*, const compare_type
*);
119 st_expr_hasher::hash (const value_type
*x
)
121 int do_not_record_p
= 0;
122 return hash_rtx (x
->pattern
, GET_MODE (x
->pattern
), &do_not_record_p
, NULL
, false);
126 st_expr_hasher::equal (const value_type
*ptr1
, const compare_type
*ptr2
)
128 return exp_equiv_p (ptr1
->pattern
, ptr2
->pattern
, 0, true);
131 /* Hashtable for the load/store memory refs. */
132 static hash_table
<st_expr_hasher
> store_motion_mems_table
;
134 /* This will search the st_expr list for a matching expression. If it
135 doesn't find one, we create one and initialize it. */
137 static struct st_expr
*
138 st_expr_entry (rtx x
)
140 int do_not_record_p
= 0;
141 struct st_expr
* ptr
;
146 hash
= hash_rtx (x
, GET_MODE (x
), &do_not_record_p
,
147 NULL
, /*have_reg_qty=*/false);
150 slot
= store_motion_mems_table
.find_slot_with_hash (&e
, hash
, INSERT
);
154 ptr
= XNEW (struct st_expr
);
156 ptr
->next
= store_motion_mems
;
158 ptr
->pattern_regs
= NULL_RTX
;
159 ptr
->antic_stores
= NULL_RTX
;
160 ptr
->avail_stores
= NULL_RTX
;
161 ptr
->reaching_reg
= NULL_RTX
;
163 ptr
->hash_index
= hash
;
164 store_motion_mems
= ptr
;
170 /* Free up an individual st_expr entry. */
173 free_st_expr_entry (struct st_expr
* ptr
)
175 free_INSN_LIST_list (& ptr
->antic_stores
);
176 free_INSN_LIST_list (& ptr
->avail_stores
);
181 /* Free up all memory associated with the st_expr list. */
184 free_store_motion_mems (void)
186 if (store_motion_mems_table
.is_created ())
187 store_motion_mems_table
.dispose ();
189 while (store_motion_mems
)
191 struct st_expr
* tmp
= store_motion_mems
;
192 store_motion_mems
= store_motion_mems
->next
;
193 free_st_expr_entry (tmp
);
195 store_motion_mems
= NULL
;
198 /* Assign each element of the list of mems a monotonically increasing value. */
201 enumerate_store_motion_mems (void)
203 struct st_expr
* ptr
;
206 for (ptr
= store_motion_mems
; ptr
!= NULL
; ptr
= ptr
->next
)
212 /* Return first item in the list. */
214 static inline struct st_expr
*
217 return store_motion_mems
;
220 /* Return the next item in the list after the specified one. */
222 static inline struct st_expr
*
223 next_st_expr (struct st_expr
* ptr
)
228 /* Dump debugging info about the store_motion_mems list. */
231 print_store_motion_mems (FILE * file
)
233 struct st_expr
* ptr
;
235 fprintf (dump_file
, "STORE_MOTION list of MEM exprs considered:\n");
237 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
239 fprintf (file
, " Pattern (%3d): ", ptr
->index
);
241 print_rtl (file
, ptr
->pattern
);
243 fprintf (file
, "\n ANTIC stores : ");
245 if (ptr
->antic_stores
)
246 print_rtl (file
, ptr
->antic_stores
);
248 fprintf (file
, "(nil)");
250 fprintf (file
, "\n AVAIL stores : ");
252 if (ptr
->avail_stores
)
253 print_rtl (file
, ptr
->avail_stores
);
255 fprintf (file
, "(nil)");
257 fprintf (file
, "\n\n");
260 fprintf (file
, "\n");
263 /* Return zero if some of the registers in list X are killed
264 due to set of registers in bitmap REGS_SET. */
267 store_ops_ok (const_rtx x
, int *regs_set
)
271 for (; x
; x
= XEXP (x
, 1))
274 if (regs_set
[REGNO (reg
)])
281 /* Helper for extract_mentioned_regs. */
284 extract_mentioned_regs_1 (rtx
*loc
, void *data
)
286 rtx
*mentioned_regs_p
= (rtx
*) data
;
289 *mentioned_regs_p
= alloc_EXPR_LIST (0, *loc
, *mentioned_regs_p
);
294 /* Returns a list of registers mentioned in X.
295 FIXME: A regset would be prettier and less expensive. */
298 extract_mentioned_regs (rtx x
)
300 rtx mentioned_regs
= NULL
;
301 for_each_rtx (&x
, extract_mentioned_regs_1
, &mentioned_regs
);
302 return mentioned_regs
;
305 /* Check to see if the load X is aliased with STORE_PATTERN.
306 AFTER is true if we are checking the case when STORE_PATTERN occurs
310 load_kills_store (const_rtx x
, const_rtx store_pattern
, int after
)
313 return anti_dependence (x
, store_pattern
);
315 return true_dependence (store_pattern
, GET_MODE (store_pattern
), x
);
318 /* Go through the entire rtx X, looking for any loads which might alias
319 STORE_PATTERN. Return true if found.
320 AFTER is true if we are checking the case when STORE_PATTERN occurs
324 find_loads (const_rtx x
, const_rtx store_pattern
, int after
)
333 if (GET_CODE (x
) == SET
)
338 if (load_kills_store (x
, store_pattern
, after
))
342 /* Recursively process the insn. */
343 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
345 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0 && !ret
; i
--)
348 ret
|= find_loads (XEXP (x
, i
), store_pattern
, after
);
349 else if (fmt
[i
] == 'E')
350 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
351 ret
|= find_loads (XVECEXP (x
, i
, j
), store_pattern
, after
);
356 /* Go through pattern PAT looking for any loads which might kill the
357 store in X. Return true if found.
358 AFTER is true if we are checking the case when loads kill X occurs
359 after the insn for PAT. */
362 store_killed_in_pat (const_rtx x
, const_rtx pat
, int after
)
364 if (GET_CODE (pat
) == SET
)
366 rtx dest
= SET_DEST (pat
);
368 if (GET_CODE (dest
) == ZERO_EXTRACT
)
369 dest
= XEXP (dest
, 0);
371 /* Check for memory stores to aliased objects. */
373 && !exp_equiv_p (dest
, x
, 0, true))
377 if (output_dependence (dest
, x
))
382 if (output_dependence (x
, dest
))
388 if (find_loads (pat
, x
, after
))
394 /* Check if INSN kills the store pattern X (is aliased with it).
395 AFTER is true if we are checking the case when store X occurs
396 after the insn. Return true if it does. */
399 store_killed_in_insn (const_rtx x
, const_rtx x_regs
, const_rtx insn
, int after
)
401 const_rtx reg
, note
, pat
;
403 if (! NONDEBUG_INSN_P (insn
))
408 /* A normal or pure call might read from pattern,
409 but a const call will not. */
410 if (!RTL_CONST_CALL_P (insn
))
413 /* But even a const call reads its parameters. Check whether the
414 base of some of registers used in mem is stack pointer. */
415 for (reg
= x_regs
; reg
; reg
= XEXP (reg
, 1))
416 if (may_be_sp_based_p (XEXP (reg
, 0)))
422 pat
= PATTERN (insn
);
423 if (GET_CODE (pat
) == SET
)
425 if (store_killed_in_pat (x
, pat
, after
))
428 else if (GET_CODE (pat
) == PARALLEL
)
432 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
433 if (store_killed_in_pat (x
, XVECEXP (pat
, 0, i
), after
))
436 else if (find_loads (PATTERN (insn
), x
, after
))
439 /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
440 location aliased with X, then this insn kills X. */
441 note
= find_reg_equal_equiv_note (insn
);
444 note
= XEXP (note
, 0);
446 /* However, if the note represents a must alias rather than a may
447 alias relationship, then it does not kill X. */
448 if (exp_equiv_p (note
, x
, 0, true))
451 /* See if there are any aliased loads in the note. */
452 return find_loads (note
, x
, after
);
455 /* Returns true if the expression X is loaded or clobbered on or after INSN
456 within basic block BB. REGS_SET_AFTER is bitmap of registers set in
457 or after the insn. X_REGS is list of registers mentioned in X. If the store
458 is killed, return the last insn in that it occurs in FAIL_INSN. */
461 store_killed_after (const_rtx x
, const_rtx x_regs
, const_rtx insn
, const_basic_block bb
,
462 int *regs_set_after
, rtx
*fail_insn
)
464 rtx last
= BB_END (bb
), act
;
466 if (!store_ops_ok (x_regs
, regs_set_after
))
468 /* We do not know where it will happen. */
470 *fail_insn
= NULL_RTX
;
474 /* Scan from the end, so that fail_insn is determined correctly. */
475 for (act
= last
; act
!= PREV_INSN (insn
); act
= PREV_INSN (act
))
476 if (store_killed_in_insn (x
, x_regs
, act
, false))
486 /* Returns true if the expression X is loaded or clobbered on or before INSN
487 within basic block BB. X_REGS is list of registers mentioned in X.
488 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
490 store_killed_before (const_rtx x
, const_rtx x_regs
, const_rtx insn
, const_basic_block bb
,
491 int *regs_set_before
)
493 rtx first
= BB_HEAD (bb
);
495 if (!store_ops_ok (x_regs
, regs_set_before
))
498 for ( ; insn
!= PREV_INSN (first
); insn
= PREV_INSN (insn
))
499 if (store_killed_in_insn (x
, x_regs
, insn
, true))
505 /* The last insn in the basic block that compute_store_table is processing,
506 where store_killed_after is true for X.
507 Since we go through the basic block from BB_END to BB_HEAD, this is
508 also the available store at the end of the basic block. Therefore
509 this is in effect a cache, to avoid calling store_killed_after for
510 equivalent aliasing store expressions.
511 This value is only meaningful during the computation of the store
512 table. We hi-jack the REACHING_REG field of struct st_expr to save
514 #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
516 /* Determine whether INSN is MEM store pattern that we will consider moving.
517 REGS_SET_BEFORE is bitmap of registers set before (and including) the
518 current insn, REGS_SET_AFTER is bitmap of registers set after (and
519 including) the insn in this basic block. We must be passing through BB from
520 head to end, as we are using this fact to speed things up.
522 The results are stored this way:
524 -- the first anticipatable expression is added into ANTIC_STORES
525 -- if the processed expression is not anticipatable, NULL_RTX is added
526 there instead, so that we can use it as indicator that no further
527 expression of this type may be anticipatable
528 -- if the expression is available, it is added as head of AVAIL_STORES;
529 consequently, all of them but this head are dead and may be deleted.
530 -- if the expression is not available, the insn due to that it fails to be
531 available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
533 The things are complicated a bit by fact that there already may be stores
534 to the same MEM from other blocks; also caller must take care of the
535 necessary cleanup of the temporary markers after end of the basic block.
539 find_moveable_store (rtx insn
, int *regs_set_before
, int *regs_set_after
)
541 struct st_expr
* ptr
;
543 int check_anticipatable
, check_available
;
544 basic_block bb
= BLOCK_FOR_INSN (insn
);
546 set
= single_set (insn
);
550 dest
= SET_DEST (set
);
552 if (! MEM_P (dest
) || MEM_VOLATILE_P (dest
)
553 || GET_MODE (dest
) == BLKmode
)
556 if (side_effects_p (dest
))
559 /* If we are handling exceptions, we must be careful with memory references
560 that may trap. If we are not, the behavior is undefined, so we may just
562 if (cfun
->can_throw_non_call_exceptions
&& may_trap_p (dest
))
565 /* Even if the destination cannot trap, the source may. In this case we'd
566 need to handle updating the REG_EH_REGION note. */
567 if (find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
))
570 /* Make sure that the SET_SRC of this store insns can be assigned to
571 a register, or we will fail later on in replace_store_insn, which
572 assumes that we can do this. But sometimes the target machine has
573 oddities like MEM read-modify-write instruction. See for example
575 if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set
)))
578 ptr
= st_expr_entry (dest
);
579 if (!ptr
->pattern_regs
)
580 ptr
->pattern_regs
= extract_mentioned_regs (dest
);
582 /* Do not check for anticipatability if we either found one anticipatable
583 store already, or tested for one and found out that it was killed. */
584 check_anticipatable
= 0;
585 if (!ptr
->antic_stores
)
586 check_anticipatable
= 1;
589 tmp
= XEXP (ptr
->antic_stores
, 0);
591 && BLOCK_FOR_INSN (tmp
) != bb
)
592 check_anticipatable
= 1;
594 if (check_anticipatable
)
596 if (store_killed_before (dest
, ptr
->pattern_regs
, insn
, bb
, regs_set_before
))
600 ptr
->antic_stores
= alloc_INSN_LIST (tmp
, ptr
->antic_stores
);
603 /* It is not necessary to check whether store is available if we did
604 it successfully before; if we failed before, do not bother to check
605 until we reach the insn that caused us to fail. */
607 if (!ptr
->avail_stores
)
611 tmp
= XEXP (ptr
->avail_stores
, 0);
612 if (BLOCK_FOR_INSN (tmp
) != bb
)
617 /* Check that we have already reached the insn at that the check
619 if (LAST_AVAIL_CHECK_FAILURE (ptr
))
621 for (tmp
= BB_END (bb
);
622 tmp
!= insn
&& tmp
!= LAST_AVAIL_CHECK_FAILURE (ptr
);
623 tmp
= PREV_INSN (tmp
))
629 check_available
= store_killed_after (dest
, ptr
->pattern_regs
, insn
,
631 &LAST_AVAIL_CHECK_FAILURE (ptr
));
633 if (!check_available
)
634 ptr
->avail_stores
= alloc_INSN_LIST (insn
, ptr
->avail_stores
);
637 /* Find available and anticipatable stores. */
640 compute_store_table (void)
644 #ifdef ENABLE_CHECKING
649 int *last_set_in
, *already_set
;
650 struct st_expr
* ptr
, **prev_next_ptr_ptr
;
651 unsigned int max_gcse_regno
= max_reg_num ();
653 store_motion_mems
= NULL
;
654 store_motion_mems_table
.create (13);
655 last_set_in
= XCNEWVEC (int, max_gcse_regno
);
656 already_set
= XNEWVEC (int, max_gcse_regno
);
658 /* Find all the stores we care about. */
659 FOR_EACH_BB_FN (bb
, cfun
)
661 /* First compute the registers set in this block. */
662 FOR_BB_INSNS (bb
, insn
)
665 if (! NONDEBUG_INSN_P (insn
))
668 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
669 last_set_in
[DF_REF_REGNO (*def_rec
)] = INSN_UID (insn
);
672 /* Now find the stores. */
673 memset (already_set
, 0, sizeof (int) * max_gcse_regno
);
674 FOR_BB_INSNS (bb
, insn
)
676 if (! NONDEBUG_INSN_P (insn
))
679 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
680 already_set
[DF_REF_REGNO (*def_rec
)] = INSN_UID (insn
);
682 /* Now that we've marked regs, look for stores. */
683 find_moveable_store (insn
, already_set
, last_set_in
);
685 /* Unmark regs that are no longer set. */
686 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
687 if (last_set_in
[DF_REF_REGNO (*def_rec
)] == INSN_UID (insn
))
688 last_set_in
[DF_REF_REGNO (*def_rec
)] = 0;
691 #ifdef ENABLE_CHECKING
692 /* last_set_in should now be all-zero. */
693 for (regno
= 0; regno
< max_gcse_regno
; regno
++)
694 gcc_assert (!last_set_in
[regno
]);
697 /* Clear temporary marks. */
698 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
700 LAST_AVAIL_CHECK_FAILURE (ptr
) = NULL_RTX
;
701 if (ptr
->antic_stores
702 && (tmp
= XEXP (ptr
->antic_stores
, 0)) == NULL_RTX
)
703 ptr
->antic_stores
= XEXP (ptr
->antic_stores
, 1);
707 /* Remove the stores that are not available anywhere, as there will
708 be no opportunity to optimize them. */
709 for (ptr
= store_motion_mems
, prev_next_ptr_ptr
= &store_motion_mems
;
711 ptr
= *prev_next_ptr_ptr
)
713 if (! ptr
->avail_stores
)
715 *prev_next_ptr_ptr
= ptr
->next
;
716 store_motion_mems_table
.remove_elt_with_hash (ptr
, ptr
->hash_index
);
717 free_st_expr_entry (ptr
);
720 prev_next_ptr_ptr
= &ptr
->next
;
723 ret
= enumerate_store_motion_mems ();
726 print_store_motion_mems (dump_file
);
733 /* In all code following after this, REACHING_REG has its original
734 meaning again. Avoid confusion, and undef the accessor macro for
735 the temporary marks usage in compute_store_table. */
736 #undef LAST_AVAIL_CHECK_FAILURE
738 /* Insert an instruction at the beginning of a basic block, and update
739 the BB_HEAD if needed. */
742 insert_insn_start_basic_block (rtx insn
, basic_block bb
)
744 /* Insert at start of successor block. */
745 rtx prev
= PREV_INSN (BB_HEAD (bb
));
746 rtx before
= BB_HEAD (bb
);
749 if (! LABEL_P (before
)
750 && !NOTE_INSN_BASIC_BLOCK_P (before
))
753 if (prev
== BB_END (bb
))
755 before
= NEXT_INSN (before
);
758 insn
= emit_insn_after_noloc (insn
, prev
, bb
);
762 fprintf (dump_file
, "STORE_MOTION insert store at start of BB %d:\n",
764 print_inline_rtx (dump_file
, insn
, 6);
765 fprintf (dump_file
, "\n");
769 /* This routine will insert a store on an edge. EXPR is the st_expr entry for
770 the memory reference, and E is the edge to insert it on. Returns nonzero
771 if an edge insertion was performed. */
774 insert_store (struct st_expr
* expr
, edge e
)
781 /* We did all the deleted before this insert, so if we didn't delete a
782 store, then we haven't set the reaching reg yet either. */
783 if (expr
->reaching_reg
== NULL_RTX
)
786 if (e
->flags
& EDGE_FAKE
)
789 reg
= expr
->reaching_reg
;
790 insn
= gen_move_insn (copy_rtx (expr
->pattern
), reg
);
792 /* If we are inserting this expression on ALL predecessor edges of a BB,
793 insert it at the start of the BB, and reset the insert bits on the other
794 edges so we don't try to insert it on the other edges. */
796 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
797 if (!(tmp
->flags
& EDGE_FAKE
))
799 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
801 gcc_assert (index
!= EDGE_INDEX_NO_EDGE
);
802 if (! bitmap_bit_p (st_insert_map
[index
], expr
->index
))
806 /* If tmp is NULL, we found an insertion on every edge, blank the
807 insertion vector for these edges, and insert at the start of the BB. */
808 if (!tmp
&& bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
810 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
812 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
813 bitmap_clear_bit (st_insert_map
[index
], expr
->index
);
815 insert_insn_start_basic_block (insn
, bb
);
819 /* We can't put stores in the front of blocks pointed to by abnormal
820 edges since that may put a store where one didn't used to be. */
821 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
823 insert_insn_on_edge (insn
, e
);
827 fprintf (dump_file
, "STORE_MOTION insert insn on edge (%d, %d):\n",
828 e
->src
->index
, e
->dest
->index
);
829 print_inline_rtx (dump_file
, insn
, 6);
830 fprintf (dump_file
, "\n");
836 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
837 memory location in SMEXPR set in basic block BB.
839 This could be rather expensive. */
842 remove_reachable_equiv_notes (basic_block bb
, struct st_expr
*smexpr
)
844 edge_iterator
*stack
, ei
;
847 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
848 rtx last
, insn
, note
;
849 rtx mem
= smexpr
->pattern
;
851 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
));
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
);
865 sbitmap_free (visited
);
868 act
= ei_edge (stack
[--sp
]);
872 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
873 || bitmap_bit_p (visited
, bb
->index
))
877 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
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))
888 last
= XEXP (last
, 0);
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))
901 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
903 remove_note (insn
, note
);
908 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
910 if (EDGE_COUNT (bb
->succs
) > 0)
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. */
923 replace_store_insn (rtx reg
, rtx del
, basic_block bb
, struct st_expr
*smexpr
)
925 rtx insn
, mem
, note
, set
, ptr
;
927 mem
= smexpr
->pattern
;
928 insn
= gen_move_insn (reg
, SET_SRC (single_set (del
)));
930 for (ptr
= smexpr
->antic_stores
; ptr
; ptr
= XEXP (ptr
, 1))
931 if (XEXP (ptr
, 0) == del
)
933 XEXP (ptr
, 0) = insn
;
937 /* Move the notes from the deleted insn to its replacement. */
938 REG_NOTES (insn
) = REG_NOTES (del
);
940 /* Emit the insn AFTER all the notes are transferred.
941 This is cheaper since we avoid df rescanning for the note change. */
942 insn
= emit_insn_after (insn
, del
);
947 "STORE_MOTION delete insn in BB %d:\n ", bb
->index
);
948 print_inline_rtx (dump_file
, del
, 6);
949 fprintf (dump_file
, "\nSTORE_MOTION replaced with insn:\n ");
950 print_inline_rtx (dump_file
, insn
, 6);
951 fprintf (dump_file
, "\n");
956 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
957 they are no longer accurate provided that they are reached by this
958 definition, so drop them. */
959 for (; insn
!= NEXT_INSN (BB_END (bb
)); insn
= NEXT_INSN (insn
))
960 if (NONDEBUG_INSN_P (insn
))
962 set
= single_set (insn
);
965 if (exp_equiv_p (SET_DEST (set
), mem
, 0, true))
967 note
= find_reg_equal_equiv_note (insn
);
968 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
972 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
974 remove_note (insn
, note
);
976 remove_reachable_equiv_notes (bb
, smexpr
);
980 /* Delete a store, but copy the value that would have been stored into
981 the reaching_reg for later storing. */
984 delete_store (struct st_expr
* expr
, basic_block bb
)
988 if (expr
->reaching_reg
== NULL_RTX
)
989 expr
->reaching_reg
= gen_reg_rtx_and_attrs (expr
->pattern
);
991 reg
= expr
->reaching_reg
;
993 for (i
= expr
->avail_stores
; i
; i
= XEXP (i
, 1))
996 if (BLOCK_FOR_INSN (del
) == bb
)
998 /* We know there is only one since we deleted redundant
999 ones during the available computation. */
1000 replace_store_insn (reg
, del
, bb
, expr
);
1006 /* Fill in available, anticipatable, transparent and kill vectors in
1007 STORE_DATA, based on lists of available and anticipatable stores. */
1009 build_store_vectors (void)
1012 int *regs_set_in_block
;
1014 struct st_expr
* ptr
;
1015 unsigned int max_gcse_regno
= max_reg_num ();
1017 /* Build the gen_vector. This is any store in the table which is not killed
1018 by aliasing later in its block. */
1019 st_avloc
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
),
1021 bitmap_vector_clear (st_avloc
, last_basic_block_for_fn (cfun
));
1023 st_antloc
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
),
1025 bitmap_vector_clear (st_antloc
, last_basic_block_for_fn (cfun
));
1027 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1029 for (st
= ptr
->avail_stores
; st
!= NULL
; st
= XEXP (st
, 1))
1031 insn
= XEXP (st
, 0);
1032 bb
= BLOCK_FOR_INSN (insn
);
1034 /* If we've already seen an available expression in this block,
1035 we can delete this one (It occurs earlier in the block). We'll
1036 copy the SRC expression to an unused register in case there
1037 are any side effects. */
1038 if (bitmap_bit_p (st_avloc
[bb
->index
], ptr
->index
))
1040 rtx r
= gen_reg_rtx_and_attrs (ptr
->pattern
);
1042 fprintf (dump_file
, "Removing redundant store:\n");
1043 replace_store_insn (r
, XEXP (st
, 0), bb
, ptr
);
1046 bitmap_set_bit (st_avloc
[bb
->index
], ptr
->index
);
1049 for (st
= ptr
->antic_stores
; st
!= NULL
; st
= XEXP (st
, 1))
1051 insn
= XEXP (st
, 0);
1052 bb
= BLOCK_FOR_INSN (insn
);
1053 bitmap_set_bit (st_antloc
[bb
->index
], ptr
->index
);
1057 st_kill
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), num_stores
);
1058 bitmap_vector_clear (st_kill
, last_basic_block_for_fn (cfun
));
1060 st_transp
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), num_stores
);
1061 bitmap_vector_clear (st_transp
, last_basic_block_for_fn (cfun
));
1062 regs_set_in_block
= XNEWVEC (int, max_gcse_regno
);
1064 FOR_EACH_BB_FN (bb
, cfun
)
1066 memset (regs_set_in_block
, 0, sizeof (int) * max_gcse_regno
);
1068 FOR_BB_INSNS (bb
, insn
)
1069 if (NONDEBUG_INSN_P (insn
))
1072 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
1074 unsigned int ref_regno
= DF_REF_REGNO (*def_rec
);
1075 if (ref_regno
< max_gcse_regno
)
1076 regs_set_in_block
[DF_REF_REGNO (*def_rec
)] = 1;
1080 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1082 if (store_killed_after (ptr
->pattern
, ptr
->pattern_regs
, BB_HEAD (bb
),
1083 bb
, regs_set_in_block
, NULL
))
1085 /* It should not be necessary to consider the expression
1086 killed if it is both anticipatable and available. */
1087 if (!bitmap_bit_p (st_antloc
[bb
->index
], ptr
->index
)
1088 || !bitmap_bit_p (st_avloc
[bb
->index
], ptr
->index
))
1089 bitmap_set_bit (st_kill
[bb
->index
], ptr
->index
);
1092 bitmap_set_bit (st_transp
[bb
->index
], ptr
->index
);
1096 free (regs_set_in_block
);
1100 dump_bitmap_vector (dump_file
, "st_antloc", "", st_antloc
,
1101 last_basic_block_for_fn (cfun
));
1102 dump_bitmap_vector (dump_file
, "st_kill", "", st_kill
,
1103 last_basic_block_for_fn (cfun
));
1104 dump_bitmap_vector (dump_file
, "st_transp", "", st_transp
,
1105 last_basic_block_for_fn (cfun
));
1106 dump_bitmap_vector (dump_file
, "st_avloc", "", st_avloc
,
1107 last_basic_block_for_fn (cfun
));
1111 /* Free memory used by store motion. */
1114 free_store_memory (void)
1116 free_store_motion_mems ();
1119 sbitmap_vector_free (st_avloc
);
1121 sbitmap_vector_free (st_kill
);
1123 sbitmap_vector_free (st_transp
);
1125 sbitmap_vector_free (st_antloc
);
1127 sbitmap_vector_free (st_insert_map
);
1129 sbitmap_vector_free (st_delete_map
);
1131 st_avloc
= st_kill
= st_transp
= st_antloc
= NULL
;
1132 st_insert_map
= st_delete_map
= NULL
;
1135 /* Perform store motion. Much like gcse, except we move expressions the
1136 other way by looking at the flowgraph in reverse.
1137 Return non-zero if transformations are performed by the pass. */
1140 one_store_motion_pass (void)
1144 struct st_expr
* ptr
;
1145 int did_edge_inserts
= 0;
1146 int n_stores_deleted
= 0;
1147 int n_stores_created
= 0;
1149 init_alias_analysis ();
1151 /* Find all the available and anticipatable stores. */
1152 num_stores
= compute_store_table ();
1153 if (num_stores
== 0)
1155 store_motion_mems_table
.dispose ();
1156 end_alias_analysis ();
1160 /* Now compute kill & transp vectors. */
1161 build_store_vectors ();
1162 add_noreturn_fake_exit_edges ();
1163 connect_infinite_loops_to_exit ();
1165 edge_list
= pre_edge_rev_lcm (num_stores
, st_transp
, st_avloc
,
1166 st_antloc
, st_kill
, &st_insert_map
,
1169 /* Now we want to insert the new stores which are going to be needed. */
1170 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1172 /* If any of the edges we have above are abnormal, we can't move this
1174 for (x
= NUM_EDGES (edge_list
) - 1; x
>= 0; x
--)
1175 if (bitmap_bit_p (st_insert_map
[x
], ptr
->index
)
1176 && (INDEX_EDGE (edge_list
, x
)->flags
& EDGE_ABNORMAL
))
1181 if (dump_file
!= NULL
)
1183 "Can't replace store %d: abnormal edge from %d to %d\n",
1184 ptr
->index
, INDEX_EDGE (edge_list
, x
)->src
->index
,
1185 INDEX_EDGE (edge_list
, x
)->dest
->index
);
1189 /* Now we want to insert the new stores which are going to be needed. */
1191 FOR_EACH_BB_FN (bb
, cfun
)
1192 if (bitmap_bit_p (st_delete_map
[bb
->index
], ptr
->index
))
1194 delete_store (ptr
, bb
);
1198 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
1199 if (bitmap_bit_p (st_insert_map
[x
], ptr
->index
))
1201 did_edge_inserts
|= insert_store (ptr
, INDEX_EDGE (edge_list
, x
));
1206 if (did_edge_inserts
)
1207 commit_edge_insertions ();
1209 free_store_memory ();
1210 free_edge_list (edge_list
);
1211 remove_fake_exit_edges ();
1212 end_alias_analysis ();
1216 fprintf (dump_file
, "STORE_MOTION of %s, %d basic blocks, ",
1217 current_function_name (), n_basic_blocks_for_fn (cfun
));
1218 fprintf (dump_file
, "%d insns deleted, %d insns created\n",
1219 n_stores_deleted
, n_stores_created
);
1222 return (n_stores_deleted
> 0 || n_stores_created
> 0);
1227 gate_rtl_store_motion (void)
1229 return optimize
> 0 && flag_gcse_sm
1230 && !cfun
->calls_setjmp
1231 && optimize_function_for_speed_p (cfun
)
1232 && dbg_cnt (store_motion
);
1236 execute_rtl_store_motion (void)
1238 delete_unreachable_blocks ();
1240 flag_rerun_cse_after_global_opts
|= one_store_motion_pass ();
1246 const pass_data pass_data_rtl_store_motion
=
1248 RTL_PASS
, /* type */
1249 "store_motion", /* name */
1250 OPTGROUP_NONE
, /* optinfo_flags */
1251 true, /* has_gate */
1252 true, /* has_execute */
1254 PROP_cfglayout
, /* properties_required */
1255 0, /* properties_provided */
1256 0, /* properties_destroyed */
1257 0, /* todo_flags_start */
1258 ( TODO_df_finish
| TODO_verify_rtl_sharing
1259 | TODO_verify_flow
), /* todo_flags_finish */
1262 class pass_rtl_store_motion
: public rtl_opt_pass
1265 pass_rtl_store_motion (gcc::context
*ctxt
)
1266 : rtl_opt_pass (pass_data_rtl_store_motion
, ctxt
)
1269 /* opt_pass methods: */
1270 bool gate () { return gate_rtl_store_motion (); }
1271 unsigned int execute () { return execute_rtl_store_motion (); }
1273 }; // class pass_rtl_store_motion
1278 make_pass_rtl_store_motion (gcc::context
*ctxt
)
1280 return new pass_rtl_store_motion (ctxt
);