1 /* Store motion via Lazy Code Motion on the reverse CFG.
2 Copyright (C) 1997-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
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. */
75 rtx_insn_list
*antic_stores
;
76 /* INSN list of stores that are locally available. */
77 rtx_insn_list
*avail_stores
;
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
;
160 ptr
->avail_stores
= NULL
;
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 delete store_motion_mems_table
;
187 store_motion_mems_table
= NULL
;
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
*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
*insn
,
462 const_basic_block bb
,
463 int *regs_set_after
, rtx
*fail_insn
)
465 rtx_insn
*last
= BB_END (bb
), *act
;
467 if (!store_ops_ok (x_regs
, regs_set_after
))
469 /* We do not know where it will happen. */
471 *fail_insn
= NULL_RTX
;
475 /* Scan from the end, so that fail_insn is determined correctly. */
476 for (act
= last
; act
!= PREV_INSN (insn
); act
= PREV_INSN (act
))
477 if (store_killed_in_insn (x
, x_regs
, act
, false))
487 /* Returns true if the expression X is loaded or clobbered on or before INSN
488 within basic block BB. X_REGS is list of registers mentioned in X.
489 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
491 store_killed_before (const_rtx x
, const_rtx x_regs
, const rtx_insn
*insn
,
492 const_basic_block bb
, int *regs_set_before
)
494 rtx_insn
*first
= BB_HEAD (bb
);
496 if (!store_ops_ok (x_regs
, regs_set_before
))
499 for ( ; insn
!= PREV_INSN (first
); insn
= PREV_INSN (insn
))
500 if (store_killed_in_insn (x
, x_regs
, insn
, true))
506 /* The last insn in the basic block that compute_store_table is processing,
507 where store_killed_after is true for X.
508 Since we go through the basic block from BB_END to BB_HEAD, this is
509 also the available store at the end of the basic block. Therefore
510 this is in effect a cache, to avoid calling store_killed_after for
511 equivalent aliasing store expressions.
512 This value is only meaningful during the computation of the store
513 table. We hi-jack the REACHING_REG field of struct st_expr to save
515 #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
517 /* Determine whether INSN is MEM store pattern that we will consider moving.
518 REGS_SET_BEFORE is bitmap of registers set before (and including) the
519 current insn, REGS_SET_AFTER is bitmap of registers set after (and
520 including) the insn in this basic block. We must be passing through BB from
521 head to end, as we are using this fact to speed things up.
523 The results are stored this way:
525 -- the first anticipatable expression is added into ANTIC_STORES
526 -- if the processed expression is not anticipatable, NULL_RTX is added
527 there instead, so that we can use it as indicator that no further
528 expression of this type may be anticipatable
529 -- if the expression is available, it is added as head of AVAIL_STORES;
530 consequently, all of them but this head are dead and may be deleted.
531 -- if the expression is not available, the insn due to that it fails to be
532 available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
534 The things are complicated a bit by fact that there already may be stores
535 to the same MEM from other blocks; also caller must take care of the
536 necessary cleanup of the temporary markers after end of the basic block.
540 find_moveable_store (rtx_insn
*insn
, int *regs_set_before
, int *regs_set_after
)
542 struct st_expr
* ptr
;
544 int check_anticipatable
, check_available
;
545 basic_block bb
= BLOCK_FOR_INSN (insn
);
547 set
= single_set (insn
);
551 dest
= SET_DEST (set
);
553 if (! MEM_P (dest
) || MEM_VOLATILE_P (dest
)
554 || GET_MODE (dest
) == BLKmode
)
557 if (side_effects_p (dest
))
560 /* If we are handling exceptions, we must be careful with memory references
561 that may trap. If we are not, the behavior is undefined, so we may just
563 if (cfun
->can_throw_non_call_exceptions
&& may_trap_p (dest
))
566 /* Even if the destination cannot trap, the source may. In this case we'd
567 need to handle updating the REG_EH_REGION note. */
568 if (find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
))
571 /* Make sure that the SET_SRC of this store insns can be assigned to
572 a register, or we will fail later on in replace_store_insn, which
573 assumes that we can do this. But sometimes the target machine has
574 oddities like MEM read-modify-write instruction. See for example
576 if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set
)))
579 ptr
= st_expr_entry (dest
);
580 if (!ptr
->pattern_regs
)
581 ptr
->pattern_regs
= extract_mentioned_regs (dest
);
583 /* Do not check for anticipatability if we either found one anticipatable
584 store already, or tested for one and found out that it was killed. */
585 check_anticipatable
= 0;
586 if (!ptr
->antic_stores
)
587 check_anticipatable
= 1;
590 rtx_insn
*tmp
= ptr
->antic_stores
->insn ();
592 && BLOCK_FOR_INSN (tmp
) != bb
)
593 check_anticipatable
= 1;
595 if (check_anticipatable
)
598 if (store_killed_before (dest
, ptr
->pattern_regs
, insn
, bb
, regs_set_before
))
602 ptr
->antic_stores
= alloc_INSN_LIST (tmp
, ptr
->antic_stores
);
605 /* It is not necessary to check whether store is available if we did
606 it successfully before; if we failed before, do not bother to check
607 until we reach the insn that caused us to fail. */
609 if (!ptr
->avail_stores
)
613 rtx_insn
*tmp
= ptr
->avail_stores
->insn ();
614 if (BLOCK_FOR_INSN (tmp
) != bb
)
619 /* Check that we have already reached the insn at that the check
621 if (LAST_AVAIL_CHECK_FAILURE (ptr
))
624 for (tmp
= BB_END (bb
);
625 tmp
!= insn
&& tmp
!= LAST_AVAIL_CHECK_FAILURE (ptr
);
626 tmp
= PREV_INSN (tmp
))
632 check_available
= store_killed_after (dest
, ptr
->pattern_regs
, insn
,
634 &LAST_AVAIL_CHECK_FAILURE (ptr
));
636 if (!check_available
)
637 ptr
->avail_stores
= alloc_INSN_LIST (insn
, ptr
->avail_stores
);
640 /* Find available and anticipatable stores. */
643 compute_store_table (void)
647 #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
= new hash_table
<st_expr_hasher
> (13);
659 last_set_in
= XCNEWVEC (int, max_gcse_regno
);
660 already_set
= XNEWVEC (int, max_gcse_regno
);
662 /* Find all the stores we care about. */
663 FOR_EACH_BB_FN (bb
, cfun
)
665 /* First compute the registers set in this block. */
666 FOR_BB_INSNS (bb
, insn
)
669 if (! NONDEBUG_INSN_P (insn
))
672 FOR_EACH_INSN_DEF (def
, insn
)
673 last_set_in
[DF_REF_REGNO (def
)] = INSN_UID (insn
);
676 /* Now find the stores. */
677 memset (already_set
, 0, sizeof (int) * max_gcse_regno
);
678 FOR_BB_INSNS (bb
, insn
)
680 if (! NONDEBUG_INSN_P (insn
))
683 FOR_EACH_INSN_DEF (def
, insn
)
684 already_set
[DF_REF_REGNO (def
)] = INSN_UID (insn
);
686 /* Now that we've marked regs, look for stores. */
687 find_moveable_store (insn
, already_set
, last_set_in
);
689 /* Unmark regs that are no longer set. */
690 FOR_EACH_INSN_DEF (def
, insn
)
691 if (last_set_in
[DF_REF_REGNO (def
)] == INSN_UID (insn
))
692 last_set_in
[DF_REF_REGNO (def
)] = 0;
695 #ifdef ENABLE_CHECKING
696 /* last_set_in should now be all-zero. */
697 for (regno
= 0; regno
< max_gcse_regno
; regno
++)
698 gcc_assert (!last_set_in
[regno
]);
701 /* Clear temporary marks. */
702 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
704 LAST_AVAIL_CHECK_FAILURE (ptr
) = NULL_RTX
;
705 if (ptr
->antic_stores
706 && (tmp
= ptr
->antic_stores
->insn ()) == NULL_RTX
)
707 ptr
->antic_stores
= ptr
->antic_stores
->next ();
711 /* Remove the stores that are not available anywhere, as there will
712 be no opportunity to optimize them. */
713 for (ptr
= store_motion_mems
, prev_next_ptr_ptr
= &store_motion_mems
;
715 ptr
= *prev_next_ptr_ptr
)
717 if (! ptr
->avail_stores
)
719 *prev_next_ptr_ptr
= ptr
->next
;
720 store_motion_mems_table
->remove_elt_with_hash (ptr
, ptr
->hash_index
);
721 free_st_expr_entry (ptr
);
724 prev_next_ptr_ptr
= &ptr
->next
;
727 ret
= enumerate_store_motion_mems ();
730 print_store_motion_mems (dump_file
);
737 /* In all code following after this, REACHING_REG has its original
738 meaning again. Avoid confusion, and undef the accessor macro for
739 the temporary marks usage in compute_store_table. */
740 #undef LAST_AVAIL_CHECK_FAILURE
742 /* Insert an instruction at the beginning of a basic block, and update
743 the BB_HEAD if needed. */
746 insert_insn_start_basic_block (rtx_insn
*insn
, basic_block bb
)
748 /* Insert at start of successor block. */
749 rtx_insn
*prev
= PREV_INSN (BB_HEAD (bb
));
750 rtx_insn
*before
= BB_HEAD (bb
);
753 if (! LABEL_P (before
)
754 && !NOTE_INSN_BASIC_BLOCK_P (before
))
757 if (prev
== BB_END (bb
))
759 before
= NEXT_INSN (before
);
762 insn
= emit_insn_after_noloc (insn
, prev
, bb
);
766 fprintf (dump_file
, "STORE_MOTION insert store at start of BB %d:\n",
768 print_inline_rtx (dump_file
, insn
, 6);
769 fprintf (dump_file
, "\n");
773 /* This routine will insert a store on an edge. EXPR is the st_expr entry for
774 the memory reference, and E is the edge to insert it on. Returns nonzero
775 if an edge insertion was performed. */
778 insert_store (struct st_expr
* expr
, edge e
)
786 /* We did all the deleted before this insert, so if we didn't delete a
787 store, then we haven't set the reaching reg yet either. */
788 if (expr
->reaching_reg
== NULL_RTX
)
791 if (e
->flags
& EDGE_FAKE
)
794 reg
= expr
->reaching_reg
;
795 insn
= as_a
<rtx_insn
*> (gen_move_insn (copy_rtx (expr
->pattern
), reg
));
797 /* If we are inserting this expression on ALL predecessor edges of a BB,
798 insert it at the start of the BB, and reset the insert bits on the other
799 edges so we don't try to insert it on the other edges. */
801 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
802 if (!(tmp
->flags
& EDGE_FAKE
))
804 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
806 gcc_assert (index
!= EDGE_INDEX_NO_EDGE
);
807 if (! bitmap_bit_p (st_insert_map
[index
], expr
->index
))
811 /* If tmp is NULL, we found an insertion on every edge, blank the
812 insertion vector for these edges, and insert at the start of the BB. */
813 if (!tmp
&& bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
815 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
817 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
818 bitmap_clear_bit (st_insert_map
[index
], expr
->index
);
820 insert_insn_start_basic_block (insn
, bb
);
824 /* We can't put stores in the front of blocks pointed to by abnormal
825 edges since that may put a store where one didn't used to be. */
826 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
828 insert_insn_on_edge (insn
, e
);
832 fprintf (dump_file
, "STORE_MOTION insert insn on edge (%d, %d):\n",
833 e
->src
->index
, e
->dest
->index
);
834 print_inline_rtx (dump_file
, insn
, 6);
835 fprintf (dump_file
, "\n");
841 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
842 memory location in SMEXPR set in basic block BB.
844 This could be rather expensive. */
847 remove_reachable_equiv_notes (basic_block bb
, struct st_expr
*smexpr
)
849 edge_iterator
*stack
, ei
;
852 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
855 rtx mem
= smexpr
->pattern
;
857 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
));
859 ei
= ei_start (bb
->succs
);
861 bitmap_clear (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_FOR_FN (cfun
)
879 || bitmap_bit_p (visited
, bb
->index
))
883 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
886 bitmap_set_bit (visited
, bb
->index
);
888 if (bitmap_bit_p (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
))
900 if (NONDEBUG_INSN_P (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
)
932 rtx mem
, note
, set
, ptr
;
934 mem
= smexpr
->pattern
;
935 insn
= as_a
<rtx_insn
*> (gen_move_insn (reg
, SET_SRC (single_set (del
))));
937 for (ptr
= smexpr
->antic_stores
; ptr
; ptr
= XEXP (ptr
, 1))
938 if (XEXP (ptr
, 0) == del
)
940 XEXP (ptr
, 0) = insn
;
944 /* Move the notes from the deleted insn to its replacement. */
945 REG_NOTES (insn
) = REG_NOTES (del
);
947 /* Emit the insn AFTER all the notes are transferred.
948 This is cheaper since we avoid df rescanning for the note change. */
949 insn
= emit_insn_after (insn
, del
);
954 "STORE_MOTION delete insn in BB %d:\n ", bb
->index
);
955 print_inline_rtx (dump_file
, del
, 6);
956 fprintf (dump_file
, "\nSTORE_MOTION replaced with insn:\n ");
957 print_inline_rtx (dump_file
, insn
, 6);
958 fprintf (dump_file
, "\n");
963 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
964 they are no longer accurate provided that they are reached by this
965 definition, so drop them. */
966 for (; insn
!= NEXT_INSN (BB_END (bb
)); insn
= NEXT_INSN (insn
))
967 if (NONDEBUG_INSN_P (insn
))
969 set
= single_set (insn
);
972 if (exp_equiv_p (SET_DEST (set
), mem
, 0, true))
974 note
= find_reg_equal_equiv_note (insn
);
975 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
979 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
981 remove_note (insn
, note
);
983 remove_reachable_equiv_notes (bb
, smexpr
);
987 /* Delete a store, but copy the value that would have been stored into
988 the reaching_reg for later storing. */
991 delete_store (struct st_expr
* expr
, basic_block bb
)
995 if (expr
->reaching_reg
== NULL_RTX
)
996 expr
->reaching_reg
= gen_reg_rtx_and_attrs (expr
->pattern
);
998 reg
= expr
->reaching_reg
;
1000 for (i
= expr
->avail_stores
; i
; i
= XEXP (i
, 1))
1003 if (BLOCK_FOR_INSN (del
) == bb
)
1005 /* We know there is only one since we deleted redundant
1006 ones during the available computation. */
1007 replace_store_insn (reg
, del
, bb
, expr
);
1013 /* Fill in available, anticipatable, transparent and kill vectors in
1014 STORE_DATA, based on lists of available and anticipatable stores. */
1016 build_store_vectors (void)
1019 int *regs_set_in_block
;
1021 struct st_expr
* ptr
;
1022 unsigned int max_gcse_regno
= max_reg_num ();
1024 /* Build the gen_vector. This is any store in the table which is not killed
1025 by aliasing later in its block. */
1026 st_avloc
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
),
1028 bitmap_vector_clear (st_avloc
, last_basic_block_for_fn (cfun
));
1030 st_antloc
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
),
1032 bitmap_vector_clear (st_antloc
, last_basic_block_for_fn (cfun
));
1034 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1036 for (st
= ptr
->avail_stores
; st
!= NULL
; st
= XEXP (st
, 1))
1038 insn
= XEXP (st
, 0);
1039 bb
= BLOCK_FOR_INSN (insn
);
1041 /* If we've already seen an available expression in this block,
1042 we can delete this one (It occurs earlier in the block). We'll
1043 copy the SRC expression to an unused register in case there
1044 are any side effects. */
1045 if (bitmap_bit_p (st_avloc
[bb
->index
], ptr
->index
))
1047 rtx r
= gen_reg_rtx_and_attrs (ptr
->pattern
);
1049 fprintf (dump_file
, "Removing redundant store:\n");
1050 replace_store_insn (r
, XEXP (st
, 0), bb
, ptr
);
1053 bitmap_set_bit (st_avloc
[bb
->index
], ptr
->index
);
1056 for (st
= ptr
->antic_stores
; st
!= NULL
; st
= XEXP (st
, 1))
1058 insn
= XEXP (st
, 0);
1059 bb
= BLOCK_FOR_INSN (insn
);
1060 bitmap_set_bit (st_antloc
[bb
->index
], ptr
->index
);
1064 st_kill
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), num_stores
);
1065 bitmap_vector_clear (st_kill
, last_basic_block_for_fn (cfun
));
1067 st_transp
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), num_stores
);
1068 bitmap_vector_clear (st_transp
, last_basic_block_for_fn (cfun
));
1069 regs_set_in_block
= XNEWVEC (int, max_gcse_regno
);
1071 FOR_EACH_BB_FN (bb
, cfun
)
1073 memset (regs_set_in_block
, 0, sizeof (int) * max_gcse_regno
);
1075 FOR_BB_INSNS (bb
, insn
)
1076 if (NONDEBUG_INSN_P (insn
))
1079 FOR_EACH_INSN_DEF (def
, insn
)
1081 unsigned int ref_regno
= DF_REF_REGNO (def
);
1082 if (ref_regno
< max_gcse_regno
)
1083 regs_set_in_block
[DF_REF_REGNO (def
)] = 1;
1087 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1089 if (store_killed_after (ptr
->pattern
, ptr
->pattern_regs
, BB_HEAD (bb
),
1090 bb
, regs_set_in_block
, NULL
))
1092 /* It should not be necessary to consider the expression
1093 killed if it is both anticipatable and available. */
1094 if (!bitmap_bit_p (st_antloc
[bb
->index
], ptr
->index
)
1095 || !bitmap_bit_p (st_avloc
[bb
->index
], ptr
->index
))
1096 bitmap_set_bit (st_kill
[bb
->index
], ptr
->index
);
1099 bitmap_set_bit (st_transp
[bb
->index
], ptr
->index
);
1103 free (regs_set_in_block
);
1107 dump_bitmap_vector (dump_file
, "st_antloc", "", st_antloc
,
1108 last_basic_block_for_fn (cfun
));
1109 dump_bitmap_vector (dump_file
, "st_kill", "", st_kill
,
1110 last_basic_block_for_fn (cfun
));
1111 dump_bitmap_vector (dump_file
, "st_transp", "", st_transp
,
1112 last_basic_block_for_fn (cfun
));
1113 dump_bitmap_vector (dump_file
, "st_avloc", "", st_avloc
,
1114 last_basic_block_for_fn (cfun
));
1118 /* Free memory used by store motion. */
1121 free_store_memory (void)
1123 free_store_motion_mems ();
1126 sbitmap_vector_free (st_avloc
);
1128 sbitmap_vector_free (st_kill
);
1130 sbitmap_vector_free (st_transp
);
1132 sbitmap_vector_free (st_antloc
);
1134 sbitmap_vector_free (st_insert_map
);
1136 sbitmap_vector_free (st_delete_map
);
1138 st_avloc
= st_kill
= st_transp
= st_antloc
= NULL
;
1139 st_insert_map
= st_delete_map
= NULL
;
1142 /* Perform store motion. Much like gcse, except we move expressions the
1143 other way by looking at the flowgraph in reverse.
1144 Return non-zero if transformations are performed by the pass. */
1147 one_store_motion_pass (void)
1151 struct st_expr
* ptr
;
1152 int did_edge_inserts
= 0;
1153 int n_stores_deleted
= 0;
1154 int n_stores_created
= 0;
1156 init_alias_analysis ();
1158 /* Find all the available and anticipatable stores. */
1159 num_stores
= compute_store_table ();
1160 if (num_stores
== 0)
1162 delete store_motion_mems_table
;
1163 store_motion_mems_table
= NULL
;
1164 end_alias_analysis ();
1168 /* Now compute kill & transp vectors. */
1169 build_store_vectors ();
1170 add_noreturn_fake_exit_edges ();
1171 connect_infinite_loops_to_exit ();
1173 edge_list
= pre_edge_rev_lcm (num_stores
, st_transp
, st_avloc
,
1174 st_antloc
, st_kill
, &st_insert_map
,
1177 /* Now we want to insert the new stores which are going to be needed. */
1178 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1180 /* If any of the edges we have above are abnormal, we can't move this
1182 for (x
= NUM_EDGES (edge_list
) - 1; x
>= 0; x
--)
1183 if (bitmap_bit_p (st_insert_map
[x
], ptr
->index
)
1184 && (INDEX_EDGE (edge_list
, x
)->flags
& EDGE_ABNORMAL
))
1189 if (dump_file
!= NULL
)
1191 "Can't replace store %d: abnormal edge from %d to %d\n",
1192 ptr
->index
, INDEX_EDGE (edge_list
, x
)->src
->index
,
1193 INDEX_EDGE (edge_list
, x
)->dest
->index
);
1197 /* Now we want to insert the new stores which are going to be needed. */
1199 FOR_EACH_BB_FN (bb
, cfun
)
1200 if (bitmap_bit_p (st_delete_map
[bb
->index
], ptr
->index
))
1202 delete_store (ptr
, bb
);
1206 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
1207 if (bitmap_bit_p (st_insert_map
[x
], ptr
->index
))
1209 did_edge_inserts
|= insert_store (ptr
, INDEX_EDGE (edge_list
, x
));
1214 if (did_edge_inserts
)
1215 commit_edge_insertions ();
1217 free_store_memory ();
1218 free_edge_list (edge_list
);
1219 remove_fake_exit_edges ();
1220 end_alias_analysis ();
1224 fprintf (dump_file
, "STORE_MOTION of %s, %d basic blocks, ",
1225 current_function_name (), n_basic_blocks_for_fn (cfun
));
1226 fprintf (dump_file
, "%d insns deleted, %d insns created\n",
1227 n_stores_deleted
, n_stores_created
);
1230 return (n_stores_deleted
> 0 || n_stores_created
> 0);
1235 execute_rtl_store_motion (void)
1237 delete_unreachable_blocks ();
1239 flag_rerun_cse_after_global_opts
|= one_store_motion_pass ();
1245 const pass_data pass_data_rtl_store_motion
=
1247 RTL_PASS
, /* type */
1248 "store_motion", /* name */
1249 OPTGROUP_NONE
, /* optinfo_flags */
1251 PROP_cfglayout
, /* properties_required */
1252 0, /* properties_provided */
1253 0, /* properties_destroyed */
1254 0, /* todo_flags_start */
1255 TODO_df_finish
, /* todo_flags_finish */
1258 class pass_rtl_store_motion
: public rtl_opt_pass
1261 pass_rtl_store_motion (gcc::context
*ctxt
)
1262 : rtl_opt_pass (pass_data_rtl_store_motion
, ctxt
)
1265 /* opt_pass methods: */
1266 virtual bool gate (function
*);
1267 virtual unsigned int execute (function
*)
1269 return execute_rtl_store_motion ();
1272 }; // class pass_rtl_store_motion
1275 pass_rtl_store_motion::gate (function
*fun
)
1277 return optimize
> 0 && flag_gcse_sm
1278 && !fun
->calls_setjmp
1279 && optimize_function_for_speed_p (fun
)
1280 && dbg_cnt (store_motion
);
1286 make_pass_rtl_store_motion (gcc::context
*ctxt
)
1288 return new pass_rtl_store_motion (ctxt
);