1 /* Store motion via Lazy Code Motion on the reverse CFG.
2 Copyright (C) 1997-2015 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"
28 #include "diagnostic-core.h"
35 #include "insn-config.h"
40 #include "cfgcleanup.h"
51 #include "tree-pass.h"
55 /* This pass implements downward store motion.
56 As of May 1, 2009, the pass is not enabled by default on any target,
57 but bootstrap completes on ia64 and x86_64 with the pass enabled. */
60 - remove_reachable_equiv_notes is an incomprehensible pile of goo and
61 a compile time hog that needs a rewrite (maybe cache st_exprs to
62 invalidate REG_EQUAL/REG_EQUIV notes for?).
63 - pattern_regs in st_expr should be a regset (on its own obstack).
64 - antic_stores and avail_stores should be VECs instead of lists.
65 - store_motion_mems should be a vec instead of a list.
66 - there should be an alloc pool for struct st_expr objects.
67 - investigate whether it is helpful to make the address of an st_expr
69 - when GIMPLE alias information is exported, the effectiveness of this
70 pass should be re-evaluated.
73 /* This is a list of store expressions (MEMs). The structure is used
74 as an expression table to track stores which look interesting, and
75 might be moveable towards the exit block. */
79 /* Pattern of this mem. */
81 /* List of registers mentioned by the mem. */
83 /* INSN list of stores that are locally anticipatable. */
84 rtx_insn_list
*antic_stores
;
85 /* INSN list of stores that are locally available. */
86 rtx_insn_list
*avail_stores
;
87 /* Next in the list. */
88 struct st_expr
* next
;
89 /* Store ID in the dataflow bitmaps. */
91 /* Hash value for the hash table. */
92 unsigned int hash_index
;
93 /* Register holding the stored expression when a store is moved.
94 This field is also used as a cache in find_moveable_store, see
95 LAST_AVAIL_CHECK_FAILURE below. */
99 /* Head of the list of load/store memory refs. */
100 static struct st_expr
* store_motion_mems
= NULL
;
102 /* These bitmaps will hold the local dataflow properties per basic block. */
103 static sbitmap
*st_kill
, *st_avloc
, *st_antloc
, *st_transp
;
105 /* Nonzero for expressions which should be inserted on a specific edge. */
106 static sbitmap
*st_insert_map
;
108 /* Nonzero for expressions which should be deleted in a specific block. */
109 static sbitmap
*st_delete_map
;
111 /* Global holding the number of store expressions we are dealing with. */
112 static int num_stores
;
114 /* Contains the edge_list returned by pre_edge_lcm. */
115 static struct edge_list
*edge_list
;
117 /* Hashtable helpers. */
119 struct st_expr_hasher
: nofree_ptr_hash
<st_expr
>
121 static inline hashval_t
hash (const st_expr
*);
122 static inline bool equal (const st_expr
*, const st_expr
*);
126 st_expr_hasher::hash (const st_expr
*x
)
128 int do_not_record_p
= 0;
129 return hash_rtx (x
->pattern
, GET_MODE (x
->pattern
), &do_not_record_p
, NULL
, false);
133 st_expr_hasher::equal (const st_expr
*ptr1
, const st_expr
*ptr2
)
135 return exp_equiv_p (ptr1
->pattern
, ptr2
->pattern
, 0, true);
138 /* Hashtable for the load/store memory refs. */
139 static hash_table
<st_expr_hasher
> *store_motion_mems_table
;
141 /* This will search the st_expr list for a matching expression. If it
142 doesn't find one, we create one and initialize it. */
144 static struct st_expr
*
145 st_expr_entry (rtx x
)
147 int do_not_record_p
= 0;
148 struct st_expr
* ptr
;
153 hash
= hash_rtx (x
, GET_MODE (x
), &do_not_record_p
,
154 NULL
, /*have_reg_qty=*/false);
157 slot
= store_motion_mems_table
->find_slot_with_hash (&e
, hash
, INSERT
);
161 ptr
= XNEW (struct st_expr
);
163 ptr
->next
= store_motion_mems
;
165 ptr
->pattern_regs
= NULL_RTX
;
166 ptr
->antic_stores
= NULL
;
167 ptr
->avail_stores
= NULL
;
168 ptr
->reaching_reg
= NULL_RTX
;
170 ptr
->hash_index
= hash
;
171 store_motion_mems
= ptr
;
177 /* Free up an individual st_expr entry. */
180 free_st_expr_entry (struct st_expr
* ptr
)
182 free_INSN_LIST_list (& ptr
->antic_stores
);
183 free_INSN_LIST_list (& ptr
->avail_stores
);
188 /* Free up all memory associated with the st_expr list. */
191 free_store_motion_mems (void)
193 delete store_motion_mems_table
;
194 store_motion_mems_table
= NULL
;
196 while (store_motion_mems
)
198 struct st_expr
* tmp
= store_motion_mems
;
199 store_motion_mems
= store_motion_mems
->next
;
200 free_st_expr_entry (tmp
);
202 store_motion_mems
= NULL
;
205 /* Assign each element of the list of mems a monotonically increasing value. */
208 enumerate_store_motion_mems (void)
210 struct st_expr
* ptr
;
213 for (ptr
= store_motion_mems
; ptr
!= NULL
; ptr
= ptr
->next
)
219 /* Return first item in the list. */
221 static inline struct st_expr
*
224 return store_motion_mems
;
227 /* Return the next item in the list after the specified one. */
229 static inline struct st_expr
*
230 next_st_expr (struct st_expr
* ptr
)
235 /* Dump debugging info about the store_motion_mems list. */
238 print_store_motion_mems (FILE * file
)
240 struct st_expr
* ptr
;
242 fprintf (dump_file
, "STORE_MOTION list of MEM exprs considered:\n");
244 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
246 fprintf (file
, " Pattern (%3d): ", ptr
->index
);
248 print_rtl (file
, ptr
->pattern
);
250 fprintf (file
, "\n ANTIC stores : ");
252 if (ptr
->antic_stores
)
253 print_rtl (file
, ptr
->antic_stores
);
255 fprintf (file
, "(nil)");
257 fprintf (file
, "\n AVAIL stores : ");
259 if (ptr
->avail_stores
)
260 print_rtl (file
, ptr
->avail_stores
);
262 fprintf (file
, "(nil)");
264 fprintf (file
, "\n\n");
267 fprintf (file
, "\n");
270 /* Return zero if some of the registers in list X are killed
271 due to set of registers in bitmap REGS_SET. */
274 store_ops_ok (const_rtx x
, int *regs_set
)
278 for (; x
; x
= XEXP (x
, 1))
281 if (regs_set
[REGNO (reg
)])
288 /* Returns a list of registers mentioned in X.
289 FIXME: A regset would be prettier and less expensive. */
291 static rtx_expr_list
*
292 extract_mentioned_regs (rtx x
)
294 rtx_expr_list
*mentioned_regs
= NULL
;
295 subrtx_var_iterator::array_type array
;
296 FOR_EACH_SUBRTX_VAR (iter
, array
, x
, NONCONST
)
300 mentioned_regs
= alloc_EXPR_LIST (0, x
, 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
= 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_insn
*del
, basic_block bb
,
930 struct st_expr
*smexpr
)
933 rtx mem
, note
, set
, ptr
;
935 mem
= smexpr
->pattern
;
936 insn
= gen_move_insn (reg
, SET_SRC (single_set (del
)));
938 for (ptr
= smexpr
->antic_stores
; ptr
; ptr
= XEXP (ptr
, 1))
939 if (XEXP (ptr
, 0) == del
)
941 XEXP (ptr
, 0) = insn
;
945 /* Move the notes from the deleted insn to its replacement. */
946 REG_NOTES (insn
) = REG_NOTES (del
);
948 /* Emit the insn AFTER all the notes are transferred.
949 This is cheaper since we avoid df rescanning for the note change. */
950 insn
= emit_insn_after (insn
, del
);
955 "STORE_MOTION delete insn in BB %d:\n ", bb
->index
);
956 print_inline_rtx (dump_file
, del
, 6);
957 fprintf (dump_file
, "\nSTORE_MOTION replaced with insn:\n ");
958 print_inline_rtx (dump_file
, insn
, 6);
959 fprintf (dump_file
, "\n");
964 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
965 they are no longer accurate provided that they are reached by this
966 definition, so drop them. */
967 for (; insn
!= NEXT_INSN (BB_END (bb
)); insn
= NEXT_INSN (insn
))
968 if (NONDEBUG_INSN_P (insn
))
970 set
= single_set (insn
);
973 if (exp_equiv_p (SET_DEST (set
), mem
, 0, true))
975 note
= find_reg_equal_equiv_note (insn
);
976 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
980 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
982 remove_note (insn
, note
);
984 remove_reachable_equiv_notes (bb
, smexpr
);
988 /* Delete a store, but copy the value that would have been stored into
989 the reaching_reg for later storing. */
992 delete_store (struct st_expr
* expr
, basic_block bb
)
996 if (expr
->reaching_reg
== NULL_RTX
)
997 expr
->reaching_reg
= gen_reg_rtx_and_attrs (expr
->pattern
);
999 reg
= expr
->reaching_reg
;
1001 for (rtx_insn_list
*i
= expr
->avail_stores
; i
; i
= i
->next ())
1003 rtx_insn
*del
= i
->insn ();
1004 if (BLOCK_FOR_INSN (del
) == bb
)
1006 /* We know there is only one since we deleted redundant
1007 ones during the available computation. */
1008 replace_store_insn (reg
, del
, bb
, expr
);
1014 /* Fill in available, anticipatable, transparent and kill vectors in
1015 STORE_DATA, based on lists of available and anticipatable stores. */
1017 build_store_vectors (void)
1020 int *regs_set_in_block
;
1023 struct st_expr
* ptr
;
1024 unsigned int max_gcse_regno
= max_reg_num ();
1026 /* Build the gen_vector. This is any store in the table which is not killed
1027 by aliasing later in its block. */
1028 st_avloc
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
),
1030 bitmap_vector_clear (st_avloc
, last_basic_block_for_fn (cfun
));
1032 st_antloc
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
),
1034 bitmap_vector_clear (st_antloc
, last_basic_block_for_fn (cfun
));
1036 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1038 for (st
= ptr
->avail_stores
; st
!= NULL
; st
= st
->next ())
1041 bb
= BLOCK_FOR_INSN (insn
);
1043 /* If we've already seen an available expression in this block,
1044 we can delete this one (It occurs earlier in the block). We'll
1045 copy the SRC expression to an unused register in case there
1046 are any side effects. */
1047 if (bitmap_bit_p (st_avloc
[bb
->index
], ptr
->index
))
1049 rtx r
= gen_reg_rtx_and_attrs (ptr
->pattern
);
1051 fprintf (dump_file
, "Removing redundant store:\n");
1052 replace_store_insn (r
, st
->insn (), bb
, ptr
);
1055 bitmap_set_bit (st_avloc
[bb
->index
], ptr
->index
);
1058 for (st
= ptr
->antic_stores
; st
!= NULL
; st
= st
->next ())
1061 bb
= BLOCK_FOR_INSN (insn
);
1062 bitmap_set_bit (st_antloc
[bb
->index
], ptr
->index
);
1066 st_kill
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), num_stores
);
1067 bitmap_vector_clear (st_kill
, last_basic_block_for_fn (cfun
));
1069 st_transp
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), num_stores
);
1070 bitmap_vector_clear (st_transp
, last_basic_block_for_fn (cfun
));
1071 regs_set_in_block
= XNEWVEC (int, max_gcse_regno
);
1073 FOR_EACH_BB_FN (bb
, cfun
)
1075 memset (regs_set_in_block
, 0, sizeof (int) * max_gcse_regno
);
1077 FOR_BB_INSNS (bb
, insn
)
1078 if (NONDEBUG_INSN_P (insn
))
1081 FOR_EACH_INSN_DEF (def
, insn
)
1083 unsigned int ref_regno
= DF_REF_REGNO (def
);
1084 if (ref_regno
< max_gcse_regno
)
1085 regs_set_in_block
[DF_REF_REGNO (def
)] = 1;
1089 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1091 if (store_killed_after (ptr
->pattern
, ptr
->pattern_regs
, BB_HEAD (bb
),
1092 bb
, regs_set_in_block
, NULL
))
1094 /* It should not be necessary to consider the expression
1095 killed if it is both anticipatable and available. */
1096 if (!bitmap_bit_p (st_antloc
[bb
->index
], ptr
->index
)
1097 || !bitmap_bit_p (st_avloc
[bb
->index
], ptr
->index
))
1098 bitmap_set_bit (st_kill
[bb
->index
], ptr
->index
);
1101 bitmap_set_bit (st_transp
[bb
->index
], ptr
->index
);
1105 free (regs_set_in_block
);
1109 dump_bitmap_vector (dump_file
, "st_antloc", "", st_antloc
,
1110 last_basic_block_for_fn (cfun
));
1111 dump_bitmap_vector (dump_file
, "st_kill", "", st_kill
,
1112 last_basic_block_for_fn (cfun
));
1113 dump_bitmap_vector (dump_file
, "st_transp", "", st_transp
,
1114 last_basic_block_for_fn (cfun
));
1115 dump_bitmap_vector (dump_file
, "st_avloc", "", st_avloc
,
1116 last_basic_block_for_fn (cfun
));
1120 /* Free memory used by store motion. */
1123 free_store_memory (void)
1125 free_store_motion_mems ();
1128 sbitmap_vector_free (st_avloc
);
1130 sbitmap_vector_free (st_kill
);
1132 sbitmap_vector_free (st_transp
);
1134 sbitmap_vector_free (st_antloc
);
1136 sbitmap_vector_free (st_insert_map
);
1138 sbitmap_vector_free (st_delete_map
);
1140 st_avloc
= st_kill
= st_transp
= st_antloc
= NULL
;
1141 st_insert_map
= st_delete_map
= NULL
;
1144 /* Perform store motion. Much like gcse, except we move expressions the
1145 other way by looking at the flowgraph in reverse.
1146 Return non-zero if transformations are performed by the pass. */
1149 one_store_motion_pass (void)
1153 struct st_expr
* ptr
;
1154 int did_edge_inserts
= 0;
1155 int n_stores_deleted
= 0;
1156 int n_stores_created
= 0;
1158 init_alias_analysis ();
1160 /* Find all the available and anticipatable stores. */
1161 num_stores
= compute_store_table ();
1162 if (num_stores
== 0)
1164 delete store_motion_mems_table
;
1165 store_motion_mems_table
= NULL
;
1166 end_alias_analysis ();
1170 /* Now compute kill & transp vectors. */
1171 build_store_vectors ();
1172 add_noreturn_fake_exit_edges ();
1173 connect_infinite_loops_to_exit ();
1175 edge_list
= pre_edge_rev_lcm (num_stores
, st_transp
, st_avloc
,
1176 st_antloc
, st_kill
, &st_insert_map
,
1179 /* Now we want to insert the new stores which are going to be needed. */
1180 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1182 /* If any of the edges we have above are abnormal, we can't move this
1184 for (x
= NUM_EDGES (edge_list
) - 1; x
>= 0; x
--)
1185 if (bitmap_bit_p (st_insert_map
[x
], ptr
->index
)
1186 && (INDEX_EDGE (edge_list
, x
)->flags
& EDGE_ABNORMAL
))
1191 if (dump_file
!= NULL
)
1193 "Can't replace store %d: abnormal edge from %d to %d\n",
1194 ptr
->index
, INDEX_EDGE (edge_list
, x
)->src
->index
,
1195 INDEX_EDGE (edge_list
, x
)->dest
->index
);
1199 /* Now we want to insert the new stores which are going to be needed. */
1201 FOR_EACH_BB_FN (bb
, cfun
)
1202 if (bitmap_bit_p (st_delete_map
[bb
->index
], ptr
->index
))
1204 delete_store (ptr
, bb
);
1208 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
1209 if (bitmap_bit_p (st_insert_map
[x
], ptr
->index
))
1211 did_edge_inserts
|= insert_store (ptr
, INDEX_EDGE (edge_list
, x
));
1216 if (did_edge_inserts
)
1217 commit_edge_insertions ();
1219 free_store_memory ();
1220 free_edge_list (edge_list
);
1221 remove_fake_exit_edges ();
1222 end_alias_analysis ();
1226 fprintf (dump_file
, "STORE_MOTION of %s, %d basic blocks, ",
1227 current_function_name (), n_basic_blocks_for_fn (cfun
));
1228 fprintf (dump_file
, "%d insns deleted, %d insns created\n",
1229 n_stores_deleted
, n_stores_created
);
1232 return (n_stores_deleted
> 0 || n_stores_created
> 0);
1237 execute_rtl_store_motion (void)
1239 delete_unreachable_blocks ();
1241 flag_rerun_cse_after_global_opts
|= one_store_motion_pass ();
1247 const pass_data pass_data_rtl_store_motion
=
1249 RTL_PASS
, /* type */
1250 "store_motion", /* name */
1251 OPTGROUP_NONE
, /* optinfo_flags */
1253 PROP_cfglayout
, /* properties_required */
1254 0, /* properties_provided */
1255 0, /* properties_destroyed */
1256 0, /* todo_flags_start */
1257 TODO_df_finish
, /* todo_flags_finish */
1260 class pass_rtl_store_motion
: public rtl_opt_pass
1263 pass_rtl_store_motion (gcc::context
*ctxt
)
1264 : rtl_opt_pass (pass_data_rtl_store_motion
, ctxt
)
1267 /* opt_pass methods: */
1268 virtual bool gate (function
*);
1269 virtual unsigned int execute (function
*)
1271 return execute_rtl_store_motion ();
1274 }; // class pass_rtl_store_motion
1277 pass_rtl_store_motion::gate (function
*fun
)
1279 return optimize
> 0 && flag_gcse_sm
1280 && !fun
->calls_setjmp
1281 && optimize_function_for_speed_p (fun
)
1282 && dbg_cnt (store_motion
);
1288 make_pass_rtl_store_motion (gcc::context
*ctxt
)
1290 return new pass_rtl_store_motion (ctxt
);