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"
24 #include "diagnostic-core.h"
31 #include "double-int.h"
40 #include "hard-reg-set.h"
42 #include "insn-config.h"
47 #include "dominance.h"
52 #include "cfgcleanup.h"
53 #include "basic-block.h"
58 #include "tree-pass.h"
59 #include "hash-table.h"
64 /* This pass implements downward store motion.
65 As of May 1, 2009, the pass is not enabled by default on any target,
66 but bootstrap completes on ia64 and x86_64 with the pass enabled. */
69 - remove_reachable_equiv_notes is an incomprehensible pile of goo and
70 a compile time hog that needs a rewrite (maybe cache st_exprs to
71 invalidate REG_EQUAL/REG_EQUIV notes for?).
72 - pattern_regs in st_expr should be a regset (on its own obstack).
73 - antic_stores and avail_stores should be VECs instead of lists.
74 - store_motion_mems should be a vec instead of a list.
75 - there should be an alloc pool for struct st_expr objects.
76 - investigate whether it is helpful to make the address of an st_expr
78 - when GIMPLE alias information is exported, the effectiveness of this
79 pass should be re-evaluated.
82 /* This is a list of store expressions (MEMs). The structure is used
83 as an expression table to track stores which look interesting, and
84 might be moveable towards the exit block. */
88 /* Pattern of this mem. */
90 /* List of registers mentioned by the mem. */
92 /* INSN list of stores that are locally anticipatable. */
93 rtx_insn_list
*antic_stores
;
94 /* INSN list of stores that are locally available. */
95 rtx_insn_list
*avail_stores
;
96 /* Next in the list. */
97 struct st_expr
* next
;
98 /* Store ID in the dataflow bitmaps. */
100 /* Hash value for the hash table. */
101 unsigned int hash_index
;
102 /* Register holding the stored expression when a store is moved.
103 This field is also used as a cache in find_moveable_store, see
104 LAST_AVAIL_CHECK_FAILURE below. */
108 /* Head of the list of load/store memory refs. */
109 static struct st_expr
* store_motion_mems
= NULL
;
111 /* These bitmaps will hold the local dataflow properties per basic block. */
112 static sbitmap
*st_kill
, *st_avloc
, *st_antloc
, *st_transp
;
114 /* Nonzero for expressions which should be inserted on a specific edge. */
115 static sbitmap
*st_insert_map
;
117 /* Nonzero for expressions which should be deleted in a specific block. */
118 static sbitmap
*st_delete_map
;
120 /* Global holding the number of store expressions we are dealing with. */
121 static int num_stores
;
123 /* Contains the edge_list returned by pre_edge_lcm. */
124 static struct edge_list
*edge_list
;
126 /* Hashtable helpers. */
128 struct st_expr_hasher
: typed_noop_remove
<st_expr
>
130 typedef st_expr value_type
;
131 typedef st_expr compare_type
;
132 static inline hashval_t
hash (const value_type
*);
133 static inline bool equal (const value_type
*, const compare_type
*);
137 st_expr_hasher::hash (const value_type
*x
)
139 int do_not_record_p
= 0;
140 return hash_rtx (x
->pattern
, GET_MODE (x
->pattern
), &do_not_record_p
, NULL
, false);
144 st_expr_hasher::equal (const value_type
*ptr1
, const compare_type
*ptr2
)
146 return exp_equiv_p (ptr1
->pattern
, ptr2
->pattern
, 0, true);
149 /* Hashtable for the load/store memory refs. */
150 static hash_table
<st_expr_hasher
> *store_motion_mems_table
;
152 /* This will search the st_expr list for a matching expression. If it
153 doesn't find one, we create one and initialize it. */
155 static struct st_expr
*
156 st_expr_entry (rtx x
)
158 int do_not_record_p
= 0;
159 struct st_expr
* ptr
;
164 hash
= hash_rtx (x
, GET_MODE (x
), &do_not_record_p
,
165 NULL
, /*have_reg_qty=*/false);
168 slot
= store_motion_mems_table
->find_slot_with_hash (&e
, hash
, INSERT
);
172 ptr
= XNEW (struct st_expr
);
174 ptr
->next
= store_motion_mems
;
176 ptr
->pattern_regs
= NULL_RTX
;
177 ptr
->antic_stores
= NULL
;
178 ptr
->avail_stores
= NULL
;
179 ptr
->reaching_reg
= NULL_RTX
;
181 ptr
->hash_index
= hash
;
182 store_motion_mems
= ptr
;
188 /* Free up an individual st_expr entry. */
191 free_st_expr_entry (struct st_expr
* ptr
)
193 free_INSN_LIST_list (& ptr
->antic_stores
);
194 free_INSN_LIST_list (& ptr
->avail_stores
);
199 /* Free up all memory associated with the st_expr list. */
202 free_store_motion_mems (void)
204 delete store_motion_mems_table
;
205 store_motion_mems_table
= NULL
;
207 while (store_motion_mems
)
209 struct st_expr
* tmp
= store_motion_mems
;
210 store_motion_mems
= store_motion_mems
->next
;
211 free_st_expr_entry (tmp
);
213 store_motion_mems
= NULL
;
216 /* Assign each element of the list of mems a monotonically increasing value. */
219 enumerate_store_motion_mems (void)
221 struct st_expr
* ptr
;
224 for (ptr
= store_motion_mems
; ptr
!= NULL
; ptr
= ptr
->next
)
230 /* Return first item in the list. */
232 static inline struct st_expr
*
235 return store_motion_mems
;
238 /* Return the next item in the list after the specified one. */
240 static inline struct st_expr
*
241 next_st_expr (struct st_expr
* ptr
)
246 /* Dump debugging info about the store_motion_mems list. */
249 print_store_motion_mems (FILE * file
)
251 struct st_expr
* ptr
;
253 fprintf (dump_file
, "STORE_MOTION list of MEM exprs considered:\n");
255 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
257 fprintf (file
, " Pattern (%3d): ", ptr
->index
);
259 print_rtl (file
, ptr
->pattern
);
261 fprintf (file
, "\n ANTIC stores : ");
263 if (ptr
->antic_stores
)
264 print_rtl (file
, ptr
->antic_stores
);
266 fprintf (file
, "(nil)");
268 fprintf (file
, "\n AVAIL stores : ");
270 if (ptr
->avail_stores
)
271 print_rtl (file
, ptr
->avail_stores
);
273 fprintf (file
, "(nil)");
275 fprintf (file
, "\n\n");
278 fprintf (file
, "\n");
281 /* Return zero if some of the registers in list X are killed
282 due to set of registers in bitmap REGS_SET. */
285 store_ops_ok (const_rtx x
, int *regs_set
)
289 for (; x
; x
= XEXP (x
, 1))
292 if (regs_set
[REGNO (reg
)])
299 /* Returns a list of registers mentioned in X.
300 FIXME: A regset would be prettier and less expensive. */
303 extract_mentioned_regs (rtx x
)
305 rtx mentioned_regs
= NULL
;
306 subrtx_var_iterator::array_type array
;
307 FOR_EACH_SUBRTX_VAR (iter
, array
, x
, NONCONST
)
311 mentioned_regs
= alloc_EXPR_LIST (0, x
, mentioned_regs
);
313 return mentioned_regs
;
316 /* Check to see if the load X is aliased with STORE_PATTERN.
317 AFTER is true if we are checking the case when STORE_PATTERN occurs
321 load_kills_store (const_rtx x
, const_rtx store_pattern
, int after
)
324 return anti_dependence (x
, store_pattern
);
326 return true_dependence (store_pattern
, GET_MODE (store_pattern
), x
);
329 /* Go through the entire rtx X, looking for any loads which might alias
330 STORE_PATTERN. Return true if found.
331 AFTER is true if we are checking the case when STORE_PATTERN occurs
335 find_loads (const_rtx x
, const_rtx store_pattern
, int after
)
344 if (GET_CODE (x
) == SET
)
349 if (load_kills_store (x
, store_pattern
, after
))
353 /* Recursively process the insn. */
354 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
356 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0 && !ret
; i
--)
359 ret
|= find_loads (XEXP (x
, i
), store_pattern
, after
);
360 else if (fmt
[i
] == 'E')
361 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
362 ret
|= find_loads (XVECEXP (x
, i
, j
), store_pattern
, after
);
367 /* Go through pattern PAT looking for any loads which might kill the
368 store in X. Return true if found.
369 AFTER is true if we are checking the case when loads kill X occurs
370 after the insn for PAT. */
373 store_killed_in_pat (const_rtx x
, const_rtx pat
, int after
)
375 if (GET_CODE (pat
) == SET
)
377 rtx dest
= SET_DEST (pat
);
379 if (GET_CODE (dest
) == ZERO_EXTRACT
)
380 dest
= XEXP (dest
, 0);
382 /* Check for memory stores to aliased objects. */
384 && !exp_equiv_p (dest
, x
, 0, true))
388 if (output_dependence (dest
, x
))
393 if (output_dependence (x
, dest
))
399 if (find_loads (pat
, x
, after
))
405 /* Check if INSN kills the store pattern X (is aliased with it).
406 AFTER is true if we are checking the case when store X occurs
407 after the insn. Return true if it does. */
410 store_killed_in_insn (const_rtx x
, const_rtx x_regs
, const rtx_insn
*insn
, int after
)
412 const_rtx reg
, note
, pat
;
414 if (! NONDEBUG_INSN_P (insn
))
419 /* A normal or pure call might read from pattern,
420 but a const call will not. */
421 if (!RTL_CONST_CALL_P (insn
))
424 /* But even a const call reads its parameters. Check whether the
425 base of some of registers used in mem is stack pointer. */
426 for (reg
= x_regs
; reg
; reg
= XEXP (reg
, 1))
427 if (may_be_sp_based_p (XEXP (reg
, 0)))
433 pat
= PATTERN (insn
);
434 if (GET_CODE (pat
) == SET
)
436 if (store_killed_in_pat (x
, pat
, after
))
439 else if (GET_CODE (pat
) == PARALLEL
)
443 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
444 if (store_killed_in_pat (x
, XVECEXP (pat
, 0, i
), after
))
447 else if (find_loads (PATTERN (insn
), x
, after
))
450 /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
451 location aliased with X, then this insn kills X. */
452 note
= find_reg_equal_equiv_note (insn
);
455 note
= XEXP (note
, 0);
457 /* However, if the note represents a must alias rather than a may
458 alias relationship, then it does not kill X. */
459 if (exp_equiv_p (note
, x
, 0, true))
462 /* See if there are any aliased loads in the note. */
463 return find_loads (note
, x
, after
);
466 /* Returns true if the expression X is loaded or clobbered on or after INSN
467 within basic block BB. REGS_SET_AFTER is bitmap of registers set in
468 or after the insn. X_REGS is list of registers mentioned in X. If the store
469 is killed, return the last insn in that it occurs in FAIL_INSN. */
472 store_killed_after (const_rtx x
, const_rtx x_regs
, const rtx_insn
*insn
,
473 const_basic_block bb
,
474 int *regs_set_after
, rtx
*fail_insn
)
476 rtx_insn
*last
= BB_END (bb
), *act
;
478 if (!store_ops_ok (x_regs
, regs_set_after
))
480 /* We do not know where it will happen. */
482 *fail_insn
= NULL_RTX
;
486 /* Scan from the end, so that fail_insn is determined correctly. */
487 for (act
= last
; act
!= PREV_INSN (insn
); act
= PREV_INSN (act
))
488 if (store_killed_in_insn (x
, x_regs
, act
, false))
498 /* Returns true if the expression X is loaded or clobbered on or before INSN
499 within basic block BB. X_REGS is list of registers mentioned in X.
500 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
502 store_killed_before (const_rtx x
, const_rtx x_regs
, const rtx_insn
*insn
,
503 const_basic_block bb
, int *regs_set_before
)
505 rtx_insn
*first
= BB_HEAD (bb
);
507 if (!store_ops_ok (x_regs
, regs_set_before
))
510 for ( ; insn
!= PREV_INSN (first
); insn
= PREV_INSN (insn
))
511 if (store_killed_in_insn (x
, x_regs
, insn
, true))
517 /* The last insn in the basic block that compute_store_table is processing,
518 where store_killed_after is true for X.
519 Since we go through the basic block from BB_END to BB_HEAD, this is
520 also the available store at the end of the basic block. Therefore
521 this is in effect a cache, to avoid calling store_killed_after for
522 equivalent aliasing store expressions.
523 This value is only meaningful during the computation of the store
524 table. We hi-jack the REACHING_REG field of struct st_expr to save
526 #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
528 /* Determine whether INSN is MEM store pattern that we will consider moving.
529 REGS_SET_BEFORE is bitmap of registers set before (and including) the
530 current insn, REGS_SET_AFTER is bitmap of registers set after (and
531 including) the insn in this basic block. We must be passing through BB from
532 head to end, as we are using this fact to speed things up.
534 The results are stored this way:
536 -- the first anticipatable expression is added into ANTIC_STORES
537 -- if the processed expression is not anticipatable, NULL_RTX is added
538 there instead, so that we can use it as indicator that no further
539 expression of this type may be anticipatable
540 -- if the expression is available, it is added as head of AVAIL_STORES;
541 consequently, all of them but this head are dead and may be deleted.
542 -- if the expression is not available, the insn due to that it fails to be
543 available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
545 The things are complicated a bit by fact that there already may be stores
546 to the same MEM from other blocks; also caller must take care of the
547 necessary cleanup of the temporary markers after end of the basic block.
551 find_moveable_store (rtx_insn
*insn
, int *regs_set_before
, int *regs_set_after
)
553 struct st_expr
* ptr
;
555 int check_anticipatable
, check_available
;
556 basic_block bb
= BLOCK_FOR_INSN (insn
);
558 set
= single_set (insn
);
562 dest
= SET_DEST (set
);
564 if (! MEM_P (dest
) || MEM_VOLATILE_P (dest
)
565 || GET_MODE (dest
) == BLKmode
)
568 if (side_effects_p (dest
))
571 /* If we are handling exceptions, we must be careful with memory references
572 that may trap. If we are not, the behavior is undefined, so we may just
574 if (cfun
->can_throw_non_call_exceptions
&& may_trap_p (dest
))
577 /* Even if the destination cannot trap, the source may. In this case we'd
578 need to handle updating the REG_EH_REGION note. */
579 if (find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
))
582 /* Make sure that the SET_SRC of this store insns can be assigned to
583 a register, or we will fail later on in replace_store_insn, which
584 assumes that we can do this. But sometimes the target machine has
585 oddities like MEM read-modify-write instruction. See for example
587 if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set
)))
590 ptr
= st_expr_entry (dest
);
591 if (!ptr
->pattern_regs
)
592 ptr
->pattern_regs
= extract_mentioned_regs (dest
);
594 /* Do not check for anticipatability if we either found one anticipatable
595 store already, or tested for one and found out that it was killed. */
596 check_anticipatable
= 0;
597 if (!ptr
->antic_stores
)
598 check_anticipatable
= 1;
601 rtx_insn
*tmp
= ptr
->antic_stores
->insn ();
603 && BLOCK_FOR_INSN (tmp
) != bb
)
604 check_anticipatable
= 1;
606 if (check_anticipatable
)
609 if (store_killed_before (dest
, ptr
->pattern_regs
, insn
, bb
, regs_set_before
))
613 ptr
->antic_stores
= alloc_INSN_LIST (tmp
, ptr
->antic_stores
);
616 /* It is not necessary to check whether store is available if we did
617 it successfully before; if we failed before, do not bother to check
618 until we reach the insn that caused us to fail. */
620 if (!ptr
->avail_stores
)
624 rtx_insn
*tmp
= ptr
->avail_stores
->insn ();
625 if (BLOCK_FOR_INSN (tmp
) != bb
)
630 /* Check that we have already reached the insn at that the check
632 if (LAST_AVAIL_CHECK_FAILURE (ptr
))
635 for (tmp
= BB_END (bb
);
636 tmp
!= insn
&& tmp
!= LAST_AVAIL_CHECK_FAILURE (ptr
);
637 tmp
= PREV_INSN (tmp
))
643 check_available
= store_killed_after (dest
, ptr
->pattern_regs
, insn
,
645 &LAST_AVAIL_CHECK_FAILURE (ptr
));
647 if (!check_available
)
648 ptr
->avail_stores
= alloc_INSN_LIST (insn
, ptr
->avail_stores
);
651 /* Find available and anticipatable stores. */
654 compute_store_table (void)
658 #ifdef ENABLE_CHECKING
664 int *last_set_in
, *already_set
;
665 struct st_expr
* ptr
, **prev_next_ptr_ptr
;
666 unsigned int max_gcse_regno
= max_reg_num ();
668 store_motion_mems
= NULL
;
669 store_motion_mems_table
= new hash_table
<st_expr_hasher
> (13);
670 last_set_in
= XCNEWVEC (int, max_gcse_regno
);
671 already_set
= XNEWVEC (int, max_gcse_regno
);
673 /* Find all the stores we care about. */
674 FOR_EACH_BB_FN (bb
, cfun
)
676 /* First compute the registers set in this block. */
677 FOR_BB_INSNS (bb
, insn
)
680 if (! NONDEBUG_INSN_P (insn
))
683 FOR_EACH_INSN_DEF (def
, insn
)
684 last_set_in
[DF_REF_REGNO (def
)] = INSN_UID (insn
);
687 /* Now find the stores. */
688 memset (already_set
, 0, sizeof (int) * max_gcse_regno
);
689 FOR_BB_INSNS (bb
, insn
)
691 if (! NONDEBUG_INSN_P (insn
))
694 FOR_EACH_INSN_DEF (def
, insn
)
695 already_set
[DF_REF_REGNO (def
)] = INSN_UID (insn
);
697 /* Now that we've marked regs, look for stores. */
698 find_moveable_store (insn
, already_set
, last_set_in
);
700 /* Unmark regs that are no longer set. */
701 FOR_EACH_INSN_DEF (def
, insn
)
702 if (last_set_in
[DF_REF_REGNO (def
)] == INSN_UID (insn
))
703 last_set_in
[DF_REF_REGNO (def
)] = 0;
706 #ifdef ENABLE_CHECKING
707 /* last_set_in should now be all-zero. */
708 for (regno
= 0; regno
< max_gcse_regno
; regno
++)
709 gcc_assert (!last_set_in
[regno
]);
712 /* Clear temporary marks. */
713 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
715 LAST_AVAIL_CHECK_FAILURE (ptr
) = NULL_RTX
;
716 if (ptr
->antic_stores
717 && (tmp
= ptr
->antic_stores
->insn ()) == NULL_RTX
)
718 ptr
->antic_stores
= ptr
->antic_stores
->next ();
722 /* Remove the stores that are not available anywhere, as there will
723 be no opportunity to optimize them. */
724 for (ptr
= store_motion_mems
, prev_next_ptr_ptr
= &store_motion_mems
;
726 ptr
= *prev_next_ptr_ptr
)
728 if (! ptr
->avail_stores
)
730 *prev_next_ptr_ptr
= ptr
->next
;
731 store_motion_mems_table
->remove_elt_with_hash (ptr
, ptr
->hash_index
);
732 free_st_expr_entry (ptr
);
735 prev_next_ptr_ptr
= &ptr
->next
;
738 ret
= enumerate_store_motion_mems ();
741 print_store_motion_mems (dump_file
);
748 /* In all code following after this, REACHING_REG has its original
749 meaning again. Avoid confusion, and undef the accessor macro for
750 the temporary marks usage in compute_store_table. */
751 #undef LAST_AVAIL_CHECK_FAILURE
753 /* Insert an instruction at the beginning of a basic block, and update
754 the BB_HEAD if needed. */
757 insert_insn_start_basic_block (rtx_insn
*insn
, basic_block bb
)
759 /* Insert at start of successor block. */
760 rtx_insn
*prev
= PREV_INSN (BB_HEAD (bb
));
761 rtx_insn
*before
= BB_HEAD (bb
);
764 if (! LABEL_P (before
)
765 && !NOTE_INSN_BASIC_BLOCK_P (before
))
768 if (prev
== BB_END (bb
))
770 before
= NEXT_INSN (before
);
773 insn
= emit_insn_after_noloc (insn
, prev
, bb
);
777 fprintf (dump_file
, "STORE_MOTION insert store at start of BB %d:\n",
779 print_inline_rtx (dump_file
, insn
, 6);
780 fprintf (dump_file
, "\n");
784 /* This routine will insert a store on an edge. EXPR is the st_expr entry for
785 the memory reference, and E is the edge to insert it on. Returns nonzero
786 if an edge insertion was performed. */
789 insert_store (struct st_expr
* expr
, edge e
)
797 /* We did all the deleted before this insert, so if we didn't delete a
798 store, then we haven't set the reaching reg yet either. */
799 if (expr
->reaching_reg
== NULL_RTX
)
802 if (e
->flags
& EDGE_FAKE
)
805 reg
= expr
->reaching_reg
;
806 insn
= as_a
<rtx_insn
*> (gen_move_insn (copy_rtx (expr
->pattern
), reg
));
808 /* If we are inserting this expression on ALL predecessor edges of a BB,
809 insert it at the start of the BB, and reset the insert bits on the other
810 edges so we don't try to insert it on the other edges. */
812 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
813 if (!(tmp
->flags
& EDGE_FAKE
))
815 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
817 gcc_assert (index
!= EDGE_INDEX_NO_EDGE
);
818 if (! bitmap_bit_p (st_insert_map
[index
], expr
->index
))
822 /* If tmp is NULL, we found an insertion on every edge, blank the
823 insertion vector for these edges, and insert at the start of the BB. */
824 if (!tmp
&& bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
826 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
828 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
829 bitmap_clear_bit (st_insert_map
[index
], expr
->index
);
831 insert_insn_start_basic_block (insn
, bb
);
835 /* We can't put stores in the front of blocks pointed to by abnormal
836 edges since that may put a store where one didn't used to be. */
837 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
839 insert_insn_on_edge (insn
, e
);
843 fprintf (dump_file
, "STORE_MOTION insert insn on edge (%d, %d):\n",
844 e
->src
->index
, e
->dest
->index
);
845 print_inline_rtx (dump_file
, insn
, 6);
846 fprintf (dump_file
, "\n");
852 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
853 memory location in SMEXPR set in basic block BB.
855 This could be rather expensive. */
858 remove_reachable_equiv_notes (basic_block bb
, struct st_expr
*smexpr
)
860 edge_iterator
*stack
, ei
;
863 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
866 rtx mem
= smexpr
->pattern
;
868 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
));
870 ei
= ei_start (bb
->succs
);
872 bitmap_clear (visited
);
874 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
882 sbitmap_free (visited
);
885 act
= ei_edge (stack
[--sp
]);
889 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
890 || bitmap_bit_p (visited
, bb
->index
))
894 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
897 bitmap_set_bit (visited
, bb
->index
);
899 if (bitmap_bit_p (st_antloc
[bb
->index
], smexpr
->index
))
901 for (last
= smexpr
->antic_stores
;
902 BLOCK_FOR_INSN (XEXP (last
, 0)) != bb
;
903 last
= XEXP (last
, 1))
905 last
= XEXP (last
, 0);
908 last
= NEXT_INSN (BB_END (bb
));
910 for (insn
= BB_HEAD (bb
); insn
!= last
; insn
= NEXT_INSN (insn
))
911 if (NONDEBUG_INSN_P (insn
))
913 note
= find_reg_equal_equiv_note (insn
);
914 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
918 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
920 remove_note (insn
, note
);
925 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
927 if (EDGE_COUNT (bb
->succs
) > 0)
931 ei
= ei_start (bb
->succs
);
932 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
937 /* This routine will replace a store with a SET to a specified register. */
940 replace_store_insn (rtx reg
, rtx_insn
*del
, basic_block bb
,
941 struct st_expr
*smexpr
)
944 rtx mem
, note
, set
, ptr
;
946 mem
= smexpr
->pattern
;
947 insn
= as_a
<rtx_insn
*> (gen_move_insn (reg
, SET_SRC (single_set (del
))));
949 for (ptr
= smexpr
->antic_stores
; ptr
; ptr
= XEXP (ptr
, 1))
950 if (XEXP (ptr
, 0) == del
)
952 XEXP (ptr
, 0) = insn
;
956 /* Move the notes from the deleted insn to its replacement. */
957 REG_NOTES (insn
) = REG_NOTES (del
);
959 /* Emit the insn AFTER all the notes are transferred.
960 This is cheaper since we avoid df rescanning for the note change. */
961 insn
= emit_insn_after (insn
, del
);
966 "STORE_MOTION delete insn in BB %d:\n ", bb
->index
);
967 print_inline_rtx (dump_file
, del
, 6);
968 fprintf (dump_file
, "\nSTORE_MOTION replaced with insn:\n ");
969 print_inline_rtx (dump_file
, insn
, 6);
970 fprintf (dump_file
, "\n");
975 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
976 they are no longer accurate provided that they are reached by this
977 definition, so drop them. */
978 for (; insn
!= NEXT_INSN (BB_END (bb
)); insn
= NEXT_INSN (insn
))
979 if (NONDEBUG_INSN_P (insn
))
981 set
= single_set (insn
);
984 if (exp_equiv_p (SET_DEST (set
), mem
, 0, true))
986 note
= find_reg_equal_equiv_note (insn
);
987 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
991 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
993 remove_note (insn
, note
);
995 remove_reachable_equiv_notes (bb
, smexpr
);
999 /* Delete a store, but copy the value that would have been stored into
1000 the reaching_reg for later storing. */
1003 delete_store (struct st_expr
* expr
, basic_block bb
)
1007 if (expr
->reaching_reg
== NULL_RTX
)
1008 expr
->reaching_reg
= gen_reg_rtx_and_attrs (expr
->pattern
);
1010 reg
= expr
->reaching_reg
;
1012 for (rtx_insn_list
*i
= expr
->avail_stores
; i
; i
= i
->next ())
1014 rtx_insn
*del
= i
->insn ();
1015 if (BLOCK_FOR_INSN (del
) == bb
)
1017 /* We know there is only one since we deleted redundant
1018 ones during the available computation. */
1019 replace_store_insn (reg
, del
, bb
, expr
);
1025 /* Fill in available, anticipatable, transparent and kill vectors in
1026 STORE_DATA, based on lists of available and anticipatable stores. */
1028 build_store_vectors (void)
1031 int *regs_set_in_block
;
1034 struct st_expr
* ptr
;
1035 unsigned int max_gcse_regno
= max_reg_num ();
1037 /* Build the gen_vector. This is any store in the table which is not killed
1038 by aliasing later in its block. */
1039 st_avloc
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
),
1041 bitmap_vector_clear (st_avloc
, last_basic_block_for_fn (cfun
));
1043 st_antloc
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
),
1045 bitmap_vector_clear (st_antloc
, last_basic_block_for_fn (cfun
));
1047 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1049 for (st
= ptr
->avail_stores
; st
!= NULL
; st
= st
->next ())
1052 bb
= BLOCK_FOR_INSN (insn
);
1054 /* If we've already seen an available expression in this block,
1055 we can delete this one (It occurs earlier in the block). We'll
1056 copy the SRC expression to an unused register in case there
1057 are any side effects. */
1058 if (bitmap_bit_p (st_avloc
[bb
->index
], ptr
->index
))
1060 rtx r
= gen_reg_rtx_and_attrs (ptr
->pattern
);
1062 fprintf (dump_file
, "Removing redundant store:\n");
1063 replace_store_insn (r
, st
->insn (), bb
, ptr
);
1066 bitmap_set_bit (st_avloc
[bb
->index
], ptr
->index
);
1069 for (st
= ptr
->antic_stores
; st
!= NULL
; st
= st
->next ())
1072 bb
= BLOCK_FOR_INSN (insn
);
1073 bitmap_set_bit (st_antloc
[bb
->index
], ptr
->index
);
1077 st_kill
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), num_stores
);
1078 bitmap_vector_clear (st_kill
, last_basic_block_for_fn (cfun
));
1080 st_transp
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), num_stores
);
1081 bitmap_vector_clear (st_transp
, last_basic_block_for_fn (cfun
));
1082 regs_set_in_block
= XNEWVEC (int, max_gcse_regno
);
1084 FOR_EACH_BB_FN (bb
, cfun
)
1086 memset (regs_set_in_block
, 0, sizeof (int) * max_gcse_regno
);
1088 FOR_BB_INSNS (bb
, insn
)
1089 if (NONDEBUG_INSN_P (insn
))
1092 FOR_EACH_INSN_DEF (def
, insn
)
1094 unsigned int ref_regno
= DF_REF_REGNO (def
);
1095 if (ref_regno
< max_gcse_regno
)
1096 regs_set_in_block
[DF_REF_REGNO (def
)] = 1;
1100 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1102 if (store_killed_after (ptr
->pattern
, ptr
->pattern_regs
, BB_HEAD (bb
),
1103 bb
, regs_set_in_block
, NULL
))
1105 /* It should not be necessary to consider the expression
1106 killed if it is both anticipatable and available. */
1107 if (!bitmap_bit_p (st_antloc
[bb
->index
], ptr
->index
)
1108 || !bitmap_bit_p (st_avloc
[bb
->index
], ptr
->index
))
1109 bitmap_set_bit (st_kill
[bb
->index
], ptr
->index
);
1112 bitmap_set_bit (st_transp
[bb
->index
], ptr
->index
);
1116 free (regs_set_in_block
);
1120 dump_bitmap_vector (dump_file
, "st_antloc", "", st_antloc
,
1121 last_basic_block_for_fn (cfun
));
1122 dump_bitmap_vector (dump_file
, "st_kill", "", st_kill
,
1123 last_basic_block_for_fn (cfun
));
1124 dump_bitmap_vector (dump_file
, "st_transp", "", st_transp
,
1125 last_basic_block_for_fn (cfun
));
1126 dump_bitmap_vector (dump_file
, "st_avloc", "", st_avloc
,
1127 last_basic_block_for_fn (cfun
));
1131 /* Free memory used by store motion. */
1134 free_store_memory (void)
1136 free_store_motion_mems ();
1139 sbitmap_vector_free (st_avloc
);
1141 sbitmap_vector_free (st_kill
);
1143 sbitmap_vector_free (st_transp
);
1145 sbitmap_vector_free (st_antloc
);
1147 sbitmap_vector_free (st_insert_map
);
1149 sbitmap_vector_free (st_delete_map
);
1151 st_avloc
= st_kill
= st_transp
= st_antloc
= NULL
;
1152 st_insert_map
= st_delete_map
= NULL
;
1155 /* Perform store motion. Much like gcse, except we move expressions the
1156 other way by looking at the flowgraph in reverse.
1157 Return non-zero if transformations are performed by the pass. */
1160 one_store_motion_pass (void)
1164 struct st_expr
* ptr
;
1165 int did_edge_inserts
= 0;
1166 int n_stores_deleted
= 0;
1167 int n_stores_created
= 0;
1169 init_alias_analysis ();
1171 /* Find all the available and anticipatable stores. */
1172 num_stores
= compute_store_table ();
1173 if (num_stores
== 0)
1175 delete store_motion_mems_table
;
1176 store_motion_mems_table
= NULL
;
1177 end_alias_analysis ();
1181 /* Now compute kill & transp vectors. */
1182 build_store_vectors ();
1183 add_noreturn_fake_exit_edges ();
1184 connect_infinite_loops_to_exit ();
1186 edge_list
= pre_edge_rev_lcm (num_stores
, st_transp
, st_avloc
,
1187 st_antloc
, st_kill
, &st_insert_map
,
1190 /* Now we want to insert the new stores which are going to be needed. */
1191 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1193 /* If any of the edges we have above are abnormal, we can't move this
1195 for (x
= NUM_EDGES (edge_list
) - 1; x
>= 0; x
--)
1196 if (bitmap_bit_p (st_insert_map
[x
], ptr
->index
)
1197 && (INDEX_EDGE (edge_list
, x
)->flags
& EDGE_ABNORMAL
))
1202 if (dump_file
!= NULL
)
1204 "Can't replace store %d: abnormal edge from %d to %d\n",
1205 ptr
->index
, INDEX_EDGE (edge_list
, x
)->src
->index
,
1206 INDEX_EDGE (edge_list
, x
)->dest
->index
);
1210 /* Now we want to insert the new stores which are going to be needed. */
1212 FOR_EACH_BB_FN (bb
, cfun
)
1213 if (bitmap_bit_p (st_delete_map
[bb
->index
], ptr
->index
))
1215 delete_store (ptr
, bb
);
1219 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
1220 if (bitmap_bit_p (st_insert_map
[x
], ptr
->index
))
1222 did_edge_inserts
|= insert_store (ptr
, INDEX_EDGE (edge_list
, x
));
1227 if (did_edge_inserts
)
1228 commit_edge_insertions ();
1230 free_store_memory ();
1231 free_edge_list (edge_list
);
1232 remove_fake_exit_edges ();
1233 end_alias_analysis ();
1237 fprintf (dump_file
, "STORE_MOTION of %s, %d basic blocks, ",
1238 current_function_name (), n_basic_blocks_for_fn (cfun
));
1239 fprintf (dump_file
, "%d insns deleted, %d insns created\n",
1240 n_stores_deleted
, n_stores_created
);
1243 return (n_stores_deleted
> 0 || n_stores_created
> 0);
1248 execute_rtl_store_motion (void)
1250 delete_unreachable_blocks ();
1252 flag_rerun_cse_after_global_opts
|= one_store_motion_pass ();
1258 const pass_data pass_data_rtl_store_motion
=
1260 RTL_PASS
, /* type */
1261 "store_motion", /* name */
1262 OPTGROUP_NONE
, /* optinfo_flags */
1264 PROP_cfglayout
, /* properties_required */
1265 0, /* properties_provided */
1266 0, /* properties_destroyed */
1267 0, /* todo_flags_start */
1268 TODO_df_finish
, /* todo_flags_finish */
1271 class pass_rtl_store_motion
: public rtl_opt_pass
1274 pass_rtl_store_motion (gcc::context
*ctxt
)
1275 : rtl_opt_pass (pass_data_rtl_store_motion
, ctxt
)
1278 /* opt_pass methods: */
1279 virtual bool gate (function
*);
1280 virtual unsigned int execute (function
*)
1282 return execute_rtl_store_motion ();
1285 }; // class pass_rtl_store_motion
1288 pass_rtl_store_motion::gate (function
*fun
)
1290 return optimize
> 0 && flag_gcse_sm
1291 && !fun
->calls_setjmp
1292 && optimize_function_for_speed_p (fun
)
1293 && dbg_cnt (store_motion
);
1299 make_pass_rtl_store_motion (gcc::context
*ctxt
)
1301 return new pass_rtl_store_motion (ctxt
);