1 /* Store motion via Lazy Code Motion on the reverse CFG.
2 Copyright (C) 1997-2016 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"
33 #include "cfgcleanup.h"
35 #include "tree-pass.h"
39 /* This pass implements downward store motion.
40 As of May 1, 2009, the pass is not enabled by default on any target,
41 but bootstrap completes on ia64 and x86_64 with the pass enabled. */
44 - remove_reachable_equiv_notes is an incomprehensible pile of goo and
45 a compile time hog that needs a rewrite (maybe cache st_exprs to
46 invalidate REG_EQUAL/REG_EQUIV notes for?).
47 - pattern_regs in st_expr should be a regset (on its own obstack).
48 - antic_stores and avail_stores should be VECs instead of lists.
49 - store_motion_mems should be a vec instead of a list.
50 - there should be an alloc pool for struct st_expr objects.
51 - investigate whether it is helpful to make the address of an st_expr
53 - when GIMPLE alias information is exported, the effectiveness of this
54 pass should be re-evaluated.
57 /* This is a list of store expressions (MEMs). The structure is used
58 as an expression table to track stores which look interesting, and
59 might be moveable towards the exit block. */
63 /* Pattern of this mem. */
65 /* List of registers mentioned by the mem. */
67 /* INSN list of stores that are locally anticipatable. */
68 rtx_insn_list
*antic_stores
;
69 /* INSN list of stores that are locally available. */
70 rtx_insn_list
*avail_stores
;
71 /* Next in the list. */
72 struct st_expr
* next
;
73 /* Store ID in the dataflow bitmaps. */
75 /* Hash value for the hash table. */
76 unsigned int hash_index
;
77 /* Register holding the stored expression when a store is moved.
78 This field is also used as a cache in find_moveable_store, see
79 LAST_AVAIL_CHECK_FAILURE below. */
83 /* Head of the list of load/store memory refs. */
84 static struct st_expr
* store_motion_mems
= NULL
;
86 /* These bitmaps will hold the local dataflow properties per basic block. */
87 static sbitmap
*st_kill
, *st_avloc
, *st_antloc
, *st_transp
;
89 /* Nonzero for expressions which should be inserted on a specific edge. */
90 static sbitmap
*st_insert_map
;
92 /* Nonzero for expressions which should be deleted in a specific block. */
93 static sbitmap
*st_delete_map
;
95 /* Global holding the number of store expressions we are dealing with. */
96 static int num_stores
;
98 /* Contains the edge_list returned by pre_edge_lcm. */
99 static struct edge_list
*edge_list
;
101 /* Hashtable helpers. */
103 struct st_expr_hasher
: nofree_ptr_hash
<st_expr
>
105 static inline hashval_t
hash (const st_expr
*);
106 static inline bool equal (const st_expr
*, const st_expr
*);
110 st_expr_hasher::hash (const st_expr
*x
)
112 int do_not_record_p
= 0;
113 return hash_rtx (x
->pattern
, GET_MODE (x
->pattern
), &do_not_record_p
, NULL
, false);
117 st_expr_hasher::equal (const st_expr
*ptr1
, const st_expr
*ptr2
)
119 return exp_equiv_p (ptr1
->pattern
, ptr2
->pattern
, 0, true);
122 /* Hashtable for the load/store memory refs. */
123 static hash_table
<st_expr_hasher
> *store_motion_mems_table
;
125 /* This will search the st_expr list for a matching expression. If it
126 doesn't find one, we create one and initialize it. */
128 static struct st_expr
*
129 st_expr_entry (rtx x
)
131 int do_not_record_p
= 0;
132 struct st_expr
* ptr
;
137 hash
= hash_rtx (x
, GET_MODE (x
), &do_not_record_p
,
138 NULL
, /*have_reg_qty=*/false);
141 slot
= store_motion_mems_table
->find_slot_with_hash (&e
, hash
, INSERT
);
145 ptr
= XNEW (struct st_expr
);
147 ptr
->next
= store_motion_mems
;
149 ptr
->pattern_regs
= NULL_RTX
;
150 ptr
->antic_stores
= NULL
;
151 ptr
->avail_stores
= NULL
;
152 ptr
->reaching_reg
= NULL_RTX
;
154 ptr
->hash_index
= hash
;
155 store_motion_mems
= ptr
;
161 /* Free up an individual st_expr entry. */
164 free_st_expr_entry (struct st_expr
* ptr
)
166 free_INSN_LIST_list (& ptr
->antic_stores
);
167 free_INSN_LIST_list (& ptr
->avail_stores
);
172 /* Free up all memory associated with the st_expr list. */
175 free_store_motion_mems (void)
177 delete store_motion_mems_table
;
178 store_motion_mems_table
= NULL
;
180 while (store_motion_mems
)
182 struct st_expr
* tmp
= store_motion_mems
;
183 store_motion_mems
= store_motion_mems
->next
;
184 free_st_expr_entry (tmp
);
186 store_motion_mems
= NULL
;
189 /* Assign each element of the list of mems a monotonically increasing value. */
192 enumerate_store_motion_mems (void)
194 struct st_expr
* ptr
;
197 for (ptr
= store_motion_mems
; ptr
!= NULL
; ptr
= ptr
->next
)
203 /* Return first item in the list. */
205 static inline struct st_expr
*
208 return store_motion_mems
;
211 /* Return the next item in the list after the specified one. */
213 static inline struct st_expr
*
214 next_st_expr (struct st_expr
* ptr
)
219 /* Dump debugging info about the store_motion_mems list. */
222 print_store_motion_mems (FILE * file
)
224 struct st_expr
* ptr
;
226 fprintf (dump_file
, "STORE_MOTION list of MEM exprs considered:\n");
228 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
230 fprintf (file
, " Pattern (%3d): ", ptr
->index
);
232 print_rtl (file
, ptr
->pattern
);
234 fprintf (file
, "\n ANTIC stores : ");
236 if (ptr
->antic_stores
)
237 print_rtl (file
, ptr
->antic_stores
);
239 fprintf (file
, "(nil)");
241 fprintf (file
, "\n AVAIL stores : ");
243 if (ptr
->avail_stores
)
244 print_rtl (file
, ptr
->avail_stores
);
246 fprintf (file
, "(nil)");
248 fprintf (file
, "\n\n");
251 fprintf (file
, "\n");
254 /* Return zero if some of the registers in list X are killed
255 due to set of registers in bitmap REGS_SET. */
258 store_ops_ok (const_rtx x
, int *regs_set
)
262 for (; x
; x
= XEXP (x
, 1))
265 if (regs_set
[REGNO (reg
)])
272 /* Returns a list of registers mentioned in X.
273 FIXME: A regset would be prettier and less expensive. */
275 static rtx_expr_list
*
276 extract_mentioned_regs (rtx x
)
278 rtx_expr_list
*mentioned_regs
= NULL
;
279 subrtx_var_iterator::array_type array
;
280 FOR_EACH_SUBRTX_VAR (iter
, array
, x
, NONCONST
)
284 mentioned_regs
= alloc_EXPR_LIST (0, x
, mentioned_regs
);
286 return mentioned_regs
;
289 /* Check to see if the load X is aliased with STORE_PATTERN.
290 AFTER is true if we are checking the case when STORE_PATTERN occurs
294 load_kills_store (const_rtx x
, const_rtx store_pattern
, int after
)
297 return anti_dependence (x
, store_pattern
);
299 return true_dependence (store_pattern
, GET_MODE (store_pattern
), x
);
302 /* Go through the entire rtx X, looking for any loads which might alias
303 STORE_PATTERN. Return true if found.
304 AFTER is true if we are checking the case when STORE_PATTERN occurs
308 find_loads (const_rtx x
, const_rtx store_pattern
, int after
)
317 if (GET_CODE (x
) == SET
)
322 if (load_kills_store (x
, store_pattern
, after
))
326 /* Recursively process the insn. */
327 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
329 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0 && !ret
; i
--)
332 ret
|= find_loads (XEXP (x
, i
), store_pattern
, after
);
333 else if (fmt
[i
] == 'E')
334 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
335 ret
|= find_loads (XVECEXP (x
, i
, j
), store_pattern
, after
);
340 /* Go through pattern PAT looking for any loads which might kill the
341 store in X. Return true if found.
342 AFTER is true if we are checking the case when loads kill X occurs
343 after the insn for PAT. */
346 store_killed_in_pat (const_rtx x
, const_rtx pat
, int after
)
348 if (GET_CODE (pat
) == SET
)
350 rtx dest
= SET_DEST (pat
);
352 if (GET_CODE (dest
) == ZERO_EXTRACT
)
353 dest
= XEXP (dest
, 0);
355 /* Check for memory stores to aliased objects. */
357 && !exp_equiv_p (dest
, x
, 0, true))
361 if (output_dependence (dest
, x
))
366 if (output_dependence (x
, dest
))
372 if (find_loads (pat
, x
, after
))
378 /* Check if INSN kills the store pattern X (is aliased with it).
379 AFTER is true if we are checking the case when store X occurs
380 after the insn. Return true if it does. */
383 store_killed_in_insn (const_rtx x
, const_rtx x_regs
, const rtx_insn
*insn
, int after
)
385 const_rtx reg
, note
, pat
;
387 if (! NONDEBUG_INSN_P (insn
))
392 /* A normal or pure call might read from pattern,
393 but a const call will not. */
394 if (!RTL_CONST_CALL_P (insn
))
397 /* But even a const call reads its parameters. Check whether the
398 base of some of registers used in mem is stack pointer. */
399 for (reg
= x_regs
; reg
; reg
= XEXP (reg
, 1))
400 if (may_be_sp_based_p (XEXP (reg
, 0)))
406 pat
= PATTERN (insn
);
407 if (GET_CODE (pat
) == SET
)
409 if (store_killed_in_pat (x
, pat
, after
))
412 else if (GET_CODE (pat
) == PARALLEL
)
416 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
417 if (store_killed_in_pat (x
, XVECEXP (pat
, 0, i
), after
))
420 else if (find_loads (PATTERN (insn
), x
, after
))
423 /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
424 location aliased with X, then this insn kills X. */
425 note
= find_reg_equal_equiv_note (insn
);
428 note
= XEXP (note
, 0);
430 /* However, if the note represents a must alias rather than a may
431 alias relationship, then it does not kill X. */
432 if (exp_equiv_p (note
, x
, 0, true))
435 /* See if there are any aliased loads in the note. */
436 return find_loads (note
, x
, after
);
439 /* Returns true if the expression X is loaded or clobbered on or after INSN
440 within basic block BB. REGS_SET_AFTER is bitmap of registers set in
441 or after the insn. X_REGS is list of registers mentioned in X. If the store
442 is killed, return the last insn in that it occurs in FAIL_INSN. */
445 store_killed_after (const_rtx x
, const_rtx x_regs
, const rtx_insn
*insn
,
446 const_basic_block bb
,
447 int *regs_set_after
, rtx
*fail_insn
)
449 rtx_insn
*last
= BB_END (bb
), *act
;
451 if (!store_ops_ok (x_regs
, regs_set_after
))
453 /* We do not know where it will happen. */
455 *fail_insn
= NULL_RTX
;
459 /* Scan from the end, so that fail_insn is determined correctly. */
460 for (act
= last
; act
!= PREV_INSN (insn
); act
= PREV_INSN (act
))
461 if (store_killed_in_insn (x
, x_regs
, act
, false))
471 /* Returns true if the expression X is loaded or clobbered on or before INSN
472 within basic block BB. X_REGS is list of registers mentioned in X.
473 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
475 store_killed_before (const_rtx x
, const_rtx x_regs
, const rtx_insn
*insn
,
476 const_basic_block bb
, int *regs_set_before
)
478 rtx_insn
*first
= BB_HEAD (bb
);
480 if (!store_ops_ok (x_regs
, regs_set_before
))
483 for ( ; insn
!= PREV_INSN (first
); insn
= PREV_INSN (insn
))
484 if (store_killed_in_insn (x
, x_regs
, insn
, true))
490 /* The last insn in the basic block that compute_store_table is processing,
491 where store_killed_after is true for X.
492 Since we go through the basic block from BB_END to BB_HEAD, this is
493 also the available store at the end of the basic block. Therefore
494 this is in effect a cache, to avoid calling store_killed_after for
495 equivalent aliasing store expressions.
496 This value is only meaningful during the computation of the store
497 table. We hi-jack the REACHING_REG field of struct st_expr to save
499 #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
501 /* Determine whether INSN is MEM store pattern that we will consider moving.
502 REGS_SET_BEFORE is bitmap of registers set before (and including) the
503 current insn, REGS_SET_AFTER is bitmap of registers set after (and
504 including) the insn in this basic block. We must be passing through BB from
505 head to end, as we are using this fact to speed things up.
507 The results are stored this way:
509 -- the first anticipatable expression is added into ANTIC_STORES
510 -- if the processed expression is not anticipatable, NULL_RTX is added
511 there instead, so that we can use it as indicator that no further
512 expression of this type may be anticipatable
513 -- if the expression is available, it is added as head of AVAIL_STORES;
514 consequently, all of them but this head are dead and may be deleted.
515 -- if the expression is not available, the insn due to that it fails to be
516 available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
518 The things are complicated a bit by fact that there already may be stores
519 to the same MEM from other blocks; also caller must take care of the
520 necessary cleanup of the temporary markers after end of the basic block.
524 find_moveable_store (rtx_insn
*insn
, int *regs_set_before
, int *regs_set_after
)
526 struct st_expr
* ptr
;
528 int check_anticipatable
, check_available
;
529 basic_block bb
= BLOCK_FOR_INSN (insn
);
531 set
= single_set (insn
);
535 dest
= SET_DEST (set
);
537 if (! MEM_P (dest
) || MEM_VOLATILE_P (dest
)
538 || GET_MODE (dest
) == BLKmode
)
541 if (side_effects_p (dest
))
544 /* If we are handling exceptions, we must be careful with memory references
545 that may trap. If we are not, the behavior is undefined, so we may just
547 if (cfun
->can_throw_non_call_exceptions
&& may_trap_p (dest
))
550 /* Even if the destination cannot trap, the source may. In this case we'd
551 need to handle updating the REG_EH_REGION note. */
552 if (find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
))
555 /* Make sure that the SET_SRC of this store insns can be assigned to
556 a register, or we will fail later on in replace_store_insn, which
557 assumes that we can do this. But sometimes the target machine has
558 oddities like MEM read-modify-write instruction. See for example
560 if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set
),
561 GET_MODE (SET_SRC (set
))))
564 ptr
= st_expr_entry (dest
);
565 if (!ptr
->pattern_regs
)
566 ptr
->pattern_regs
= extract_mentioned_regs (dest
);
568 /* Do not check for anticipatability if we either found one anticipatable
569 store already, or tested for one and found out that it was killed. */
570 check_anticipatable
= 0;
571 if (!ptr
->antic_stores
)
572 check_anticipatable
= 1;
575 rtx_insn
*tmp
= ptr
->antic_stores
->insn ();
577 && BLOCK_FOR_INSN (tmp
) != bb
)
578 check_anticipatable
= 1;
580 if (check_anticipatable
)
583 if (store_killed_before (dest
, ptr
->pattern_regs
, insn
, bb
, regs_set_before
))
587 ptr
->antic_stores
= alloc_INSN_LIST (tmp
, ptr
->antic_stores
);
590 /* It is not necessary to check whether store is available if we did
591 it successfully before; if we failed before, do not bother to check
592 until we reach the insn that caused us to fail. */
594 if (!ptr
->avail_stores
)
598 rtx_insn
*tmp
= ptr
->avail_stores
->insn ();
599 if (BLOCK_FOR_INSN (tmp
) != bb
)
604 /* Check that we have already reached the insn at that the check
606 if (LAST_AVAIL_CHECK_FAILURE (ptr
))
609 for (tmp
= BB_END (bb
);
610 tmp
!= insn
&& tmp
!= LAST_AVAIL_CHECK_FAILURE (ptr
);
611 tmp
= PREV_INSN (tmp
))
617 check_available
= store_killed_after (dest
, ptr
->pattern_regs
, insn
,
619 &LAST_AVAIL_CHECK_FAILURE (ptr
));
621 if (!check_available
)
622 ptr
->avail_stores
= alloc_INSN_LIST (insn
, ptr
->avail_stores
);
625 /* Find available and anticipatable stores. */
628 compute_store_table (void)
635 int *last_set_in
, *already_set
;
636 struct st_expr
* ptr
, **prev_next_ptr_ptr
;
637 unsigned int max_gcse_regno
= max_reg_num ();
639 store_motion_mems
= NULL
;
640 store_motion_mems_table
= new hash_table
<st_expr_hasher
> (13);
641 last_set_in
= XCNEWVEC (int, max_gcse_regno
);
642 already_set
= XNEWVEC (int, max_gcse_regno
);
644 /* Find all the stores we care about. */
645 FOR_EACH_BB_FN (bb
, cfun
)
647 /* First compute the registers set in this block. */
648 FOR_BB_INSNS (bb
, insn
)
651 if (! NONDEBUG_INSN_P (insn
))
654 FOR_EACH_INSN_DEF (def
, insn
)
655 last_set_in
[DF_REF_REGNO (def
)] = INSN_UID (insn
);
658 /* Now find the stores. */
659 memset (already_set
, 0, sizeof (int) * max_gcse_regno
);
660 FOR_BB_INSNS (bb
, insn
)
662 if (! NONDEBUG_INSN_P (insn
))
665 FOR_EACH_INSN_DEF (def
, insn
)
666 already_set
[DF_REF_REGNO (def
)] = INSN_UID (insn
);
668 /* Now that we've marked regs, look for stores. */
669 find_moveable_store (insn
, already_set
, last_set_in
);
671 /* Unmark regs that are no longer set. */
672 FOR_EACH_INSN_DEF (def
, insn
)
673 if (last_set_in
[DF_REF_REGNO (def
)] == INSN_UID (insn
))
674 last_set_in
[DF_REF_REGNO (def
)] = 0;
679 /* last_set_in should now be all-zero. */
680 for (unsigned regno
= 0; regno
< max_gcse_regno
; regno
++)
681 gcc_assert (!last_set_in
[regno
]);
684 /* Clear temporary marks. */
685 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
687 LAST_AVAIL_CHECK_FAILURE (ptr
) = NULL_RTX
;
688 if (ptr
->antic_stores
689 && (tmp
= ptr
->antic_stores
->insn ()) == NULL_RTX
)
690 ptr
->antic_stores
= ptr
->antic_stores
->next ();
694 /* Remove the stores that are not available anywhere, as there will
695 be no opportunity to optimize them. */
696 for (ptr
= store_motion_mems
, prev_next_ptr_ptr
= &store_motion_mems
;
698 ptr
= *prev_next_ptr_ptr
)
700 if (! ptr
->avail_stores
)
702 *prev_next_ptr_ptr
= ptr
->next
;
703 store_motion_mems_table
->remove_elt_with_hash (ptr
, ptr
->hash_index
);
704 free_st_expr_entry (ptr
);
707 prev_next_ptr_ptr
= &ptr
->next
;
710 ret
= enumerate_store_motion_mems ();
713 print_store_motion_mems (dump_file
);
720 /* In all code following after this, REACHING_REG has its original
721 meaning again. Avoid confusion, and undef the accessor macro for
722 the temporary marks usage in compute_store_table. */
723 #undef LAST_AVAIL_CHECK_FAILURE
725 /* Insert an instruction at the beginning of a basic block, and update
726 the BB_HEAD if needed. */
729 insert_insn_start_basic_block (rtx_insn
*insn
, basic_block bb
)
731 /* Insert at start of successor block. */
732 rtx_insn
*prev
= PREV_INSN (BB_HEAD (bb
));
733 rtx_insn
*before
= BB_HEAD (bb
);
736 if (! LABEL_P (before
)
737 && !NOTE_INSN_BASIC_BLOCK_P (before
))
740 if (prev
== BB_END (bb
))
742 before
= NEXT_INSN (before
);
745 insn
= emit_insn_after_noloc (insn
, prev
, bb
);
749 fprintf (dump_file
, "STORE_MOTION insert store at start of BB %d:\n",
751 print_inline_rtx (dump_file
, insn
, 6);
752 fprintf (dump_file
, "\n");
756 /* This routine will insert a store on an edge. EXPR is the st_expr entry for
757 the memory reference, and E is the edge to insert it on. Returns nonzero
758 if an edge insertion was performed. */
761 insert_store (struct st_expr
* expr
, edge e
)
769 /* We did all the deleted before this insert, so if we didn't delete a
770 store, then we haven't set the reaching reg yet either. */
771 if (expr
->reaching_reg
== NULL_RTX
)
774 if (e
->flags
& EDGE_FAKE
)
777 reg
= expr
->reaching_reg
;
778 insn
= gen_move_insn (copy_rtx (expr
->pattern
), reg
);
780 /* If we are inserting this expression on ALL predecessor edges of a BB,
781 insert it at the start of the BB, and reset the insert bits on the other
782 edges so we don't try to insert it on the other edges. */
784 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
785 if (!(tmp
->flags
& EDGE_FAKE
))
787 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
789 gcc_assert (index
!= EDGE_INDEX_NO_EDGE
);
790 if (! bitmap_bit_p (st_insert_map
[index
], expr
->index
))
794 /* If tmp is NULL, we found an insertion on every edge, blank the
795 insertion vector for these edges, and insert at the start of the BB. */
796 if (!tmp
&& bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
798 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
800 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
801 bitmap_clear_bit (st_insert_map
[index
], expr
->index
);
803 insert_insn_start_basic_block (insn
, bb
);
807 /* We can't put stores in the front of blocks pointed to by abnormal
808 edges since that may put a store where one didn't used to be. */
809 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
811 insert_insn_on_edge (insn
, e
);
815 fprintf (dump_file
, "STORE_MOTION insert insn on edge (%d, %d):\n",
816 e
->src
->index
, e
->dest
->index
);
817 print_inline_rtx (dump_file
, insn
, 6);
818 fprintf (dump_file
, "\n");
824 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
825 memory location in SMEXPR set in basic block BB.
827 This could be rather expensive. */
830 remove_reachable_equiv_notes (basic_block bb
, struct st_expr
*smexpr
)
832 edge_iterator
*stack
, ei
;
835 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
838 rtx mem
= smexpr
->pattern
;
840 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
));
842 ei
= ei_start (bb
->succs
);
844 bitmap_clear (visited
);
846 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
854 sbitmap_free (visited
);
857 act
= ei_edge (stack
[--sp
]);
861 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
862 || bitmap_bit_p (visited
, bb
->index
))
866 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
869 bitmap_set_bit (visited
, bb
->index
);
871 if (bitmap_bit_p (st_antloc
[bb
->index
], smexpr
->index
))
873 for (last
= smexpr
->antic_stores
;
874 BLOCK_FOR_INSN (XEXP (last
, 0)) != bb
;
875 last
= XEXP (last
, 1))
877 last
= XEXP (last
, 0);
880 last
= NEXT_INSN (BB_END (bb
));
882 for (insn
= BB_HEAD (bb
); insn
!= last
; insn
= NEXT_INSN (insn
))
883 if (NONDEBUG_INSN_P (insn
))
885 note
= find_reg_equal_equiv_note (insn
);
886 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
890 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
892 remove_note (insn
, note
);
897 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
899 if (EDGE_COUNT (bb
->succs
) > 0)
903 ei
= ei_start (bb
->succs
);
904 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
909 /* This routine will replace a store with a SET to a specified register. */
912 replace_store_insn (rtx reg
, rtx_insn
*del
, basic_block bb
,
913 struct st_expr
*smexpr
)
916 rtx mem
, note
, set
, ptr
;
918 mem
= smexpr
->pattern
;
919 insn
= gen_move_insn (reg
, SET_SRC (single_set (del
)));
921 for (ptr
= smexpr
->antic_stores
; ptr
; ptr
= XEXP (ptr
, 1))
922 if (XEXP (ptr
, 0) == del
)
924 XEXP (ptr
, 0) = insn
;
928 /* Move the notes from the deleted insn to its replacement. */
929 REG_NOTES (insn
) = REG_NOTES (del
);
931 /* Emit the insn AFTER all the notes are transferred.
932 This is cheaper since we avoid df rescanning for the note change. */
933 insn
= emit_insn_after (insn
, del
);
938 "STORE_MOTION delete insn in BB %d:\n ", bb
->index
);
939 print_inline_rtx (dump_file
, del
, 6);
940 fprintf (dump_file
, "\nSTORE_MOTION replaced with insn:\n ");
941 print_inline_rtx (dump_file
, insn
, 6);
942 fprintf (dump_file
, "\n");
947 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
948 they are no longer accurate provided that they are reached by this
949 definition, so drop them. */
950 for (; insn
!= NEXT_INSN (BB_END (bb
)); insn
= NEXT_INSN (insn
))
951 if (NONDEBUG_INSN_P (insn
))
953 set
= single_set (insn
);
956 if (exp_equiv_p (SET_DEST (set
), mem
, 0, true))
958 note
= find_reg_equal_equiv_note (insn
);
959 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
963 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
965 remove_note (insn
, note
);
967 remove_reachable_equiv_notes (bb
, smexpr
);
971 /* Delete a store, but copy the value that would have been stored into
972 the reaching_reg for later storing. */
975 delete_store (struct st_expr
* expr
, basic_block bb
)
979 if (expr
->reaching_reg
== NULL_RTX
)
980 expr
->reaching_reg
= gen_reg_rtx_and_attrs (expr
->pattern
);
982 reg
= expr
->reaching_reg
;
984 for (rtx_insn_list
*i
= expr
->avail_stores
; i
; i
= i
->next ())
986 rtx_insn
*del
= i
->insn ();
987 if (BLOCK_FOR_INSN (del
) == bb
)
989 /* We know there is only one since we deleted redundant
990 ones during the available computation. */
991 replace_store_insn (reg
, del
, bb
, expr
);
997 /* Fill in available, anticipatable, transparent and kill vectors in
998 STORE_DATA, based on lists of available and anticipatable stores. */
1000 build_store_vectors (void)
1003 int *regs_set_in_block
;
1006 struct st_expr
* ptr
;
1007 unsigned int max_gcse_regno
= max_reg_num ();
1009 /* Build the gen_vector. This is any store in the table which is not killed
1010 by aliasing later in its block. */
1011 st_avloc
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
),
1013 bitmap_vector_clear (st_avloc
, last_basic_block_for_fn (cfun
));
1015 st_antloc
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
),
1017 bitmap_vector_clear (st_antloc
, last_basic_block_for_fn (cfun
));
1019 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1021 for (st
= ptr
->avail_stores
; st
!= NULL
; st
= st
->next ())
1024 bb
= BLOCK_FOR_INSN (insn
);
1026 /* If we've already seen an available expression in this block,
1027 we can delete this one (It occurs earlier in the block). We'll
1028 copy the SRC expression to an unused register in case there
1029 are any side effects. */
1030 if (bitmap_bit_p (st_avloc
[bb
->index
], ptr
->index
))
1032 rtx r
= gen_reg_rtx_and_attrs (ptr
->pattern
);
1034 fprintf (dump_file
, "Removing redundant store:\n");
1035 replace_store_insn (r
, st
->insn (), bb
, ptr
);
1038 bitmap_set_bit (st_avloc
[bb
->index
], ptr
->index
);
1041 for (st
= ptr
->antic_stores
; st
!= NULL
; st
= st
->next ())
1044 bb
= BLOCK_FOR_INSN (insn
);
1045 bitmap_set_bit (st_antloc
[bb
->index
], ptr
->index
);
1049 st_kill
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), num_stores
);
1050 bitmap_vector_clear (st_kill
, last_basic_block_for_fn (cfun
));
1052 st_transp
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), num_stores
);
1053 bitmap_vector_clear (st_transp
, last_basic_block_for_fn (cfun
));
1054 regs_set_in_block
= XNEWVEC (int, max_gcse_regno
);
1056 FOR_EACH_BB_FN (bb
, cfun
)
1058 memset (regs_set_in_block
, 0, sizeof (int) * max_gcse_regno
);
1060 FOR_BB_INSNS (bb
, insn
)
1061 if (NONDEBUG_INSN_P (insn
))
1064 FOR_EACH_INSN_DEF (def
, insn
)
1066 unsigned int ref_regno
= DF_REF_REGNO (def
);
1067 if (ref_regno
< max_gcse_regno
)
1068 regs_set_in_block
[DF_REF_REGNO (def
)] = 1;
1072 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1074 if (store_killed_after (ptr
->pattern
, ptr
->pattern_regs
, BB_HEAD (bb
),
1075 bb
, regs_set_in_block
, NULL
))
1077 /* It should not be necessary to consider the expression
1078 killed if it is both anticipatable and available. */
1079 if (!bitmap_bit_p (st_antloc
[bb
->index
], ptr
->index
)
1080 || !bitmap_bit_p (st_avloc
[bb
->index
], ptr
->index
))
1081 bitmap_set_bit (st_kill
[bb
->index
], ptr
->index
);
1084 bitmap_set_bit (st_transp
[bb
->index
], ptr
->index
);
1088 free (regs_set_in_block
);
1092 dump_bitmap_vector (dump_file
, "st_antloc", "", st_antloc
,
1093 last_basic_block_for_fn (cfun
));
1094 dump_bitmap_vector (dump_file
, "st_kill", "", st_kill
,
1095 last_basic_block_for_fn (cfun
));
1096 dump_bitmap_vector (dump_file
, "st_transp", "", st_transp
,
1097 last_basic_block_for_fn (cfun
));
1098 dump_bitmap_vector (dump_file
, "st_avloc", "", st_avloc
,
1099 last_basic_block_for_fn (cfun
));
1103 /* Free memory used by store motion. */
1106 free_store_memory (void)
1108 free_store_motion_mems ();
1111 sbitmap_vector_free (st_avloc
);
1113 sbitmap_vector_free (st_kill
);
1115 sbitmap_vector_free (st_transp
);
1117 sbitmap_vector_free (st_antloc
);
1119 sbitmap_vector_free (st_insert_map
);
1121 sbitmap_vector_free (st_delete_map
);
1123 st_avloc
= st_kill
= st_transp
= st_antloc
= NULL
;
1124 st_insert_map
= st_delete_map
= NULL
;
1127 /* Perform store motion. Much like gcse, except we move expressions the
1128 other way by looking at the flowgraph in reverse.
1129 Return non-zero if transformations are performed by the pass. */
1132 one_store_motion_pass (void)
1136 struct st_expr
* ptr
;
1137 int did_edge_inserts
= 0;
1138 int n_stores_deleted
= 0;
1139 int n_stores_created
= 0;
1141 init_alias_analysis ();
1143 /* Find all the available and anticipatable stores. */
1144 num_stores
= compute_store_table ();
1145 if (num_stores
== 0)
1147 delete store_motion_mems_table
;
1148 store_motion_mems_table
= NULL
;
1149 end_alias_analysis ();
1153 /* Now compute kill & transp vectors. */
1154 build_store_vectors ();
1155 add_noreturn_fake_exit_edges ();
1156 connect_infinite_loops_to_exit ();
1158 edge_list
= pre_edge_rev_lcm (num_stores
, st_transp
, st_avloc
,
1159 st_antloc
, st_kill
, &st_insert_map
,
1162 /* Now we want to insert the new stores which are going to be needed. */
1163 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1165 /* If any of the edges we have above are abnormal, we can't move this
1167 for (x
= NUM_EDGES (edge_list
) - 1; x
>= 0; x
--)
1168 if (bitmap_bit_p (st_insert_map
[x
], ptr
->index
)
1169 && (INDEX_EDGE (edge_list
, x
)->flags
& EDGE_ABNORMAL
))
1174 if (dump_file
!= NULL
)
1176 "Can't replace store %d: abnormal edge from %d to %d\n",
1177 ptr
->index
, INDEX_EDGE (edge_list
, x
)->src
->index
,
1178 INDEX_EDGE (edge_list
, x
)->dest
->index
);
1182 /* Now we want to insert the new stores which are going to be needed. */
1184 FOR_EACH_BB_FN (bb
, cfun
)
1185 if (bitmap_bit_p (st_delete_map
[bb
->index
], ptr
->index
))
1187 delete_store (ptr
, bb
);
1191 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
1192 if (bitmap_bit_p (st_insert_map
[x
], ptr
->index
))
1194 did_edge_inserts
|= insert_store (ptr
, INDEX_EDGE (edge_list
, x
));
1199 if (did_edge_inserts
)
1200 commit_edge_insertions ();
1202 free_store_memory ();
1203 free_edge_list (edge_list
);
1204 remove_fake_exit_edges ();
1205 end_alias_analysis ();
1209 fprintf (dump_file
, "STORE_MOTION of %s, %d basic blocks, ",
1210 current_function_name (), n_basic_blocks_for_fn (cfun
));
1211 fprintf (dump_file
, "%d insns deleted, %d insns created\n",
1212 n_stores_deleted
, n_stores_created
);
1215 return (n_stores_deleted
> 0 || n_stores_created
> 0);
1220 execute_rtl_store_motion (void)
1222 delete_unreachable_blocks ();
1224 flag_rerun_cse_after_global_opts
|= one_store_motion_pass ();
1230 const pass_data pass_data_rtl_store_motion
=
1232 RTL_PASS
, /* type */
1233 "store_motion", /* name */
1234 OPTGROUP_NONE
, /* optinfo_flags */
1236 PROP_cfglayout
, /* properties_required */
1237 0, /* properties_provided */
1238 0, /* properties_destroyed */
1239 0, /* todo_flags_start */
1240 TODO_df_finish
, /* todo_flags_finish */
1243 class pass_rtl_store_motion
: public rtl_opt_pass
1246 pass_rtl_store_motion (gcc::context
*ctxt
)
1247 : rtl_opt_pass (pass_data_rtl_store_motion
, ctxt
)
1250 /* opt_pass methods: */
1251 virtual bool gate (function
*);
1252 virtual unsigned int execute (function
*)
1254 return execute_rtl_store_motion ();
1257 }; // class pass_rtl_store_motion
1260 pass_rtl_store_motion::gate (function
*fun
)
1262 return optimize
> 0 && flag_gcse_sm
1263 && !fun
->calls_setjmp
1264 && optimize_function_for_speed_p (fun
)
1265 && dbg_cnt (store_motion
);
1271 make_pass_rtl_store_motion (gcc::context
*ctxt
)
1273 return new pass_rtl_store_motion (ctxt
);