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"
27 #include "diagnostic-core.h"
34 #include "insn-config.h"
39 #include "cfgcleanup.h"
50 #include "tree-pass.h"
54 /* This pass implements downward store motion.
55 As of May 1, 2009, the pass is not enabled by default on any target,
56 but bootstrap completes on ia64 and x86_64 with the pass enabled. */
59 - remove_reachable_equiv_notes is an incomprehensible pile of goo and
60 a compile time hog that needs a rewrite (maybe cache st_exprs to
61 invalidate REG_EQUAL/REG_EQUIV notes for?).
62 - pattern_regs in st_expr should be a regset (on its own obstack).
63 - antic_stores and avail_stores should be VECs instead of lists.
64 - store_motion_mems should be a vec instead of a list.
65 - there should be an alloc pool for struct st_expr objects.
66 - investigate whether it is helpful to make the address of an st_expr
68 - when GIMPLE alias information is exported, the effectiveness of this
69 pass should be re-evaluated.
72 /* This is a list of store expressions (MEMs). The structure is used
73 as an expression table to track stores which look interesting, and
74 might be moveable towards the exit block. */
78 /* Pattern of this mem. */
80 /* List of registers mentioned by the mem. */
82 /* INSN list of stores that are locally anticipatable. */
83 rtx_insn_list
*antic_stores
;
84 /* INSN list of stores that are locally available. */
85 rtx_insn_list
*avail_stores
;
86 /* Next in the list. */
87 struct st_expr
* next
;
88 /* Store ID in the dataflow bitmaps. */
90 /* Hash value for the hash table. */
91 unsigned int hash_index
;
92 /* Register holding the stored expression when a store is moved.
93 This field is also used as a cache in find_moveable_store, see
94 LAST_AVAIL_CHECK_FAILURE below. */
98 /* Head of the list of load/store memory refs. */
99 static struct st_expr
* store_motion_mems
= NULL
;
101 /* These bitmaps will hold the local dataflow properties per basic block. */
102 static sbitmap
*st_kill
, *st_avloc
, *st_antloc
, *st_transp
;
104 /* Nonzero for expressions which should be inserted on a specific edge. */
105 static sbitmap
*st_insert_map
;
107 /* Nonzero for expressions which should be deleted in a specific block. */
108 static sbitmap
*st_delete_map
;
110 /* Global holding the number of store expressions we are dealing with. */
111 static int num_stores
;
113 /* Contains the edge_list returned by pre_edge_lcm. */
114 static struct edge_list
*edge_list
;
116 /* Hashtable helpers. */
118 struct st_expr_hasher
: nofree_ptr_hash
<st_expr
>
120 static inline hashval_t
hash (const st_expr
*);
121 static inline bool equal (const st_expr
*, const st_expr
*);
125 st_expr_hasher::hash (const st_expr
*x
)
127 int do_not_record_p
= 0;
128 return hash_rtx (x
->pattern
, GET_MODE (x
->pattern
), &do_not_record_p
, NULL
, false);
132 st_expr_hasher::equal (const st_expr
*ptr1
, const st_expr
*ptr2
)
134 return exp_equiv_p (ptr1
->pattern
, ptr2
->pattern
, 0, true);
137 /* Hashtable for the load/store memory refs. */
138 static hash_table
<st_expr_hasher
> *store_motion_mems_table
;
140 /* This will search the st_expr list for a matching expression. If it
141 doesn't find one, we create one and initialize it. */
143 static struct st_expr
*
144 st_expr_entry (rtx x
)
146 int do_not_record_p
= 0;
147 struct st_expr
* ptr
;
152 hash
= hash_rtx (x
, GET_MODE (x
), &do_not_record_p
,
153 NULL
, /*have_reg_qty=*/false);
156 slot
= store_motion_mems_table
->find_slot_with_hash (&e
, hash
, INSERT
);
160 ptr
= XNEW (struct st_expr
);
162 ptr
->next
= store_motion_mems
;
164 ptr
->pattern_regs
= NULL_RTX
;
165 ptr
->antic_stores
= NULL
;
166 ptr
->avail_stores
= NULL
;
167 ptr
->reaching_reg
= NULL_RTX
;
169 ptr
->hash_index
= hash
;
170 store_motion_mems
= ptr
;
176 /* Free up an individual st_expr entry. */
179 free_st_expr_entry (struct st_expr
* ptr
)
181 free_INSN_LIST_list (& ptr
->antic_stores
);
182 free_INSN_LIST_list (& ptr
->avail_stores
);
187 /* Free up all memory associated with the st_expr list. */
190 free_store_motion_mems (void)
192 delete store_motion_mems_table
;
193 store_motion_mems_table
= NULL
;
195 while (store_motion_mems
)
197 struct st_expr
* tmp
= store_motion_mems
;
198 store_motion_mems
= store_motion_mems
->next
;
199 free_st_expr_entry (tmp
);
201 store_motion_mems
= NULL
;
204 /* Assign each element of the list of mems a monotonically increasing value. */
207 enumerate_store_motion_mems (void)
209 struct st_expr
* ptr
;
212 for (ptr
= store_motion_mems
; ptr
!= NULL
; ptr
= ptr
->next
)
218 /* Return first item in the list. */
220 static inline struct st_expr
*
223 return store_motion_mems
;
226 /* Return the next item in the list after the specified one. */
228 static inline struct st_expr
*
229 next_st_expr (struct st_expr
* ptr
)
234 /* Dump debugging info about the store_motion_mems list. */
237 print_store_motion_mems (FILE * file
)
239 struct st_expr
* ptr
;
241 fprintf (dump_file
, "STORE_MOTION list of MEM exprs considered:\n");
243 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
245 fprintf (file
, " Pattern (%3d): ", ptr
->index
);
247 print_rtl (file
, ptr
->pattern
);
249 fprintf (file
, "\n ANTIC stores : ");
251 if (ptr
->antic_stores
)
252 print_rtl (file
, ptr
->antic_stores
);
254 fprintf (file
, "(nil)");
256 fprintf (file
, "\n AVAIL stores : ");
258 if (ptr
->avail_stores
)
259 print_rtl (file
, ptr
->avail_stores
);
261 fprintf (file
, "(nil)");
263 fprintf (file
, "\n\n");
266 fprintf (file
, "\n");
269 /* Return zero if some of the registers in list X are killed
270 due to set of registers in bitmap REGS_SET. */
273 store_ops_ok (const_rtx x
, int *regs_set
)
277 for (; x
; x
= XEXP (x
, 1))
280 if (regs_set
[REGNO (reg
)])
287 /* Returns a list of registers mentioned in X.
288 FIXME: A regset would be prettier and less expensive. */
290 static rtx_expr_list
*
291 extract_mentioned_regs (rtx x
)
293 rtx_expr_list
*mentioned_regs
= NULL
;
294 subrtx_var_iterator::array_type array
;
295 FOR_EACH_SUBRTX_VAR (iter
, array
, x
, NONCONST
)
299 mentioned_regs
= alloc_EXPR_LIST (0, x
, mentioned_regs
);
301 return mentioned_regs
;
304 /* Check to see if the load X is aliased with STORE_PATTERN.
305 AFTER is true if we are checking the case when STORE_PATTERN occurs
309 load_kills_store (const_rtx x
, const_rtx store_pattern
, int after
)
312 return anti_dependence (x
, store_pattern
);
314 return true_dependence (store_pattern
, GET_MODE (store_pattern
), x
);
317 /* Go through the entire rtx X, looking for any loads which might alias
318 STORE_PATTERN. Return true if found.
319 AFTER is true if we are checking the case when STORE_PATTERN occurs
323 find_loads (const_rtx x
, const_rtx store_pattern
, int after
)
332 if (GET_CODE (x
) == SET
)
337 if (load_kills_store (x
, store_pattern
, after
))
341 /* Recursively process the insn. */
342 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
344 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0 && !ret
; i
--)
347 ret
|= find_loads (XEXP (x
, i
), store_pattern
, after
);
348 else if (fmt
[i
] == 'E')
349 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
350 ret
|= find_loads (XVECEXP (x
, i
, j
), store_pattern
, after
);
355 /* Go through pattern PAT looking for any loads which might kill the
356 store in X. Return true if found.
357 AFTER is true if we are checking the case when loads kill X occurs
358 after the insn for PAT. */
361 store_killed_in_pat (const_rtx x
, const_rtx pat
, int after
)
363 if (GET_CODE (pat
) == SET
)
365 rtx dest
= SET_DEST (pat
);
367 if (GET_CODE (dest
) == ZERO_EXTRACT
)
368 dest
= XEXP (dest
, 0);
370 /* Check for memory stores to aliased objects. */
372 && !exp_equiv_p (dest
, x
, 0, true))
376 if (output_dependence (dest
, x
))
381 if (output_dependence (x
, dest
))
387 if (find_loads (pat
, x
, after
))
393 /* Check if INSN kills the store pattern X (is aliased with it).
394 AFTER is true if we are checking the case when store X occurs
395 after the insn. Return true if it does. */
398 store_killed_in_insn (const_rtx x
, const_rtx x_regs
, const rtx_insn
*insn
, int after
)
400 const_rtx reg
, note
, pat
;
402 if (! NONDEBUG_INSN_P (insn
))
407 /* A normal or pure call might read from pattern,
408 but a const call will not. */
409 if (!RTL_CONST_CALL_P (insn
))
412 /* But even a const call reads its parameters. Check whether the
413 base of some of registers used in mem is stack pointer. */
414 for (reg
= x_regs
; reg
; reg
= XEXP (reg
, 1))
415 if (may_be_sp_based_p (XEXP (reg
, 0)))
421 pat
= PATTERN (insn
);
422 if (GET_CODE (pat
) == SET
)
424 if (store_killed_in_pat (x
, pat
, after
))
427 else if (GET_CODE (pat
) == PARALLEL
)
431 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
432 if (store_killed_in_pat (x
, XVECEXP (pat
, 0, i
), after
))
435 else if (find_loads (PATTERN (insn
), x
, after
))
438 /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
439 location aliased with X, then this insn kills X. */
440 note
= find_reg_equal_equiv_note (insn
);
443 note
= XEXP (note
, 0);
445 /* However, if the note represents a must alias rather than a may
446 alias relationship, then it does not kill X. */
447 if (exp_equiv_p (note
, x
, 0, true))
450 /* See if there are any aliased loads in the note. */
451 return find_loads (note
, x
, after
);
454 /* Returns true if the expression X is loaded or clobbered on or after INSN
455 within basic block BB. REGS_SET_AFTER is bitmap of registers set in
456 or after the insn. X_REGS is list of registers mentioned in X. If the store
457 is killed, return the last insn in that it occurs in FAIL_INSN. */
460 store_killed_after (const_rtx x
, const_rtx x_regs
, const rtx_insn
*insn
,
461 const_basic_block bb
,
462 int *regs_set_after
, rtx
*fail_insn
)
464 rtx_insn
*last
= BB_END (bb
), *act
;
466 if (!store_ops_ok (x_regs
, regs_set_after
))
468 /* We do not know where it will happen. */
470 *fail_insn
= NULL_RTX
;
474 /* Scan from the end, so that fail_insn is determined correctly. */
475 for (act
= last
; act
!= PREV_INSN (insn
); act
= PREV_INSN (act
))
476 if (store_killed_in_insn (x
, x_regs
, act
, false))
486 /* Returns true if the expression X is loaded or clobbered on or before INSN
487 within basic block BB. X_REGS is list of registers mentioned in X.
488 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
490 store_killed_before (const_rtx x
, const_rtx x_regs
, const rtx_insn
*insn
,
491 const_basic_block bb
, int *regs_set_before
)
493 rtx_insn
*first
= BB_HEAD (bb
);
495 if (!store_ops_ok (x_regs
, regs_set_before
))
498 for ( ; insn
!= PREV_INSN (first
); insn
= PREV_INSN (insn
))
499 if (store_killed_in_insn (x
, x_regs
, insn
, true))
505 /* The last insn in the basic block that compute_store_table is processing,
506 where store_killed_after is true for X.
507 Since we go through the basic block from BB_END to BB_HEAD, this is
508 also the available store at the end of the basic block. Therefore
509 this is in effect a cache, to avoid calling store_killed_after for
510 equivalent aliasing store expressions.
511 This value is only meaningful during the computation of the store
512 table. We hi-jack the REACHING_REG field of struct st_expr to save
514 #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
516 /* Determine whether INSN is MEM store pattern that we will consider moving.
517 REGS_SET_BEFORE is bitmap of registers set before (and including) the
518 current insn, REGS_SET_AFTER is bitmap of registers set after (and
519 including) the insn in this basic block. We must be passing through BB from
520 head to end, as we are using this fact to speed things up.
522 The results are stored this way:
524 -- the first anticipatable expression is added into ANTIC_STORES
525 -- if the processed expression is not anticipatable, NULL_RTX is added
526 there instead, so that we can use it as indicator that no further
527 expression of this type may be anticipatable
528 -- if the expression is available, it is added as head of AVAIL_STORES;
529 consequently, all of them but this head are dead and may be deleted.
530 -- if the expression is not available, the insn due to that it fails to be
531 available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
533 The things are complicated a bit by fact that there already may be stores
534 to the same MEM from other blocks; also caller must take care of the
535 necessary cleanup of the temporary markers after end of the basic block.
539 find_moveable_store (rtx_insn
*insn
, int *regs_set_before
, int *regs_set_after
)
541 struct st_expr
* ptr
;
543 int check_anticipatable
, check_available
;
544 basic_block bb
= BLOCK_FOR_INSN (insn
);
546 set
= single_set (insn
);
550 dest
= SET_DEST (set
);
552 if (! MEM_P (dest
) || MEM_VOLATILE_P (dest
)
553 || GET_MODE (dest
) == BLKmode
)
556 if (side_effects_p (dest
))
559 /* If we are handling exceptions, we must be careful with memory references
560 that may trap. If we are not, the behavior is undefined, so we may just
562 if (cfun
->can_throw_non_call_exceptions
&& may_trap_p (dest
))
565 /* Even if the destination cannot trap, the source may. In this case we'd
566 need to handle updating the REG_EH_REGION note. */
567 if (find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
))
570 /* Make sure that the SET_SRC of this store insns can be assigned to
571 a register, or we will fail later on in replace_store_insn, which
572 assumes that we can do this. But sometimes the target machine has
573 oddities like MEM read-modify-write instruction. See for example
575 if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set
)))
578 ptr
= st_expr_entry (dest
);
579 if (!ptr
->pattern_regs
)
580 ptr
->pattern_regs
= extract_mentioned_regs (dest
);
582 /* Do not check for anticipatability if we either found one anticipatable
583 store already, or tested for one and found out that it was killed. */
584 check_anticipatable
= 0;
585 if (!ptr
->antic_stores
)
586 check_anticipatable
= 1;
589 rtx_insn
*tmp
= ptr
->antic_stores
->insn ();
591 && BLOCK_FOR_INSN (tmp
) != bb
)
592 check_anticipatable
= 1;
594 if (check_anticipatable
)
597 if (store_killed_before (dest
, ptr
->pattern_regs
, insn
, bb
, regs_set_before
))
601 ptr
->antic_stores
= alloc_INSN_LIST (tmp
, ptr
->antic_stores
);
604 /* It is not necessary to check whether store is available if we did
605 it successfully before; if we failed before, do not bother to check
606 until we reach the insn that caused us to fail. */
608 if (!ptr
->avail_stores
)
612 rtx_insn
*tmp
= ptr
->avail_stores
->insn ();
613 if (BLOCK_FOR_INSN (tmp
) != bb
)
618 /* Check that we have already reached the insn at that the check
620 if (LAST_AVAIL_CHECK_FAILURE (ptr
))
623 for (tmp
= BB_END (bb
);
624 tmp
!= insn
&& tmp
!= LAST_AVAIL_CHECK_FAILURE (ptr
);
625 tmp
= PREV_INSN (tmp
))
631 check_available
= store_killed_after (dest
, ptr
->pattern_regs
, insn
,
633 &LAST_AVAIL_CHECK_FAILURE (ptr
));
635 if (!check_available
)
636 ptr
->avail_stores
= alloc_INSN_LIST (insn
, ptr
->avail_stores
);
639 /* Find available and anticipatable stores. */
642 compute_store_table (void)
646 #ifdef ENABLE_CHECKING
652 int *last_set_in
, *already_set
;
653 struct st_expr
* ptr
, **prev_next_ptr_ptr
;
654 unsigned int max_gcse_regno
= max_reg_num ();
656 store_motion_mems
= NULL
;
657 store_motion_mems_table
= new hash_table
<st_expr_hasher
> (13);
658 last_set_in
= XCNEWVEC (int, max_gcse_regno
);
659 already_set
= XNEWVEC (int, max_gcse_regno
);
661 /* Find all the stores we care about. */
662 FOR_EACH_BB_FN (bb
, cfun
)
664 /* First compute the registers set in this block. */
665 FOR_BB_INSNS (bb
, insn
)
668 if (! NONDEBUG_INSN_P (insn
))
671 FOR_EACH_INSN_DEF (def
, insn
)
672 last_set_in
[DF_REF_REGNO (def
)] = INSN_UID (insn
);
675 /* Now find the stores. */
676 memset (already_set
, 0, sizeof (int) * max_gcse_regno
);
677 FOR_BB_INSNS (bb
, insn
)
679 if (! NONDEBUG_INSN_P (insn
))
682 FOR_EACH_INSN_DEF (def
, insn
)
683 already_set
[DF_REF_REGNO (def
)] = INSN_UID (insn
);
685 /* Now that we've marked regs, look for stores. */
686 find_moveable_store (insn
, already_set
, last_set_in
);
688 /* Unmark regs that are no longer set. */
689 FOR_EACH_INSN_DEF (def
, insn
)
690 if (last_set_in
[DF_REF_REGNO (def
)] == INSN_UID (insn
))
691 last_set_in
[DF_REF_REGNO (def
)] = 0;
694 #ifdef ENABLE_CHECKING
695 /* last_set_in should now be all-zero. */
696 for (regno
= 0; regno
< max_gcse_regno
; regno
++)
697 gcc_assert (!last_set_in
[regno
]);
700 /* Clear temporary marks. */
701 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
703 LAST_AVAIL_CHECK_FAILURE (ptr
) = NULL_RTX
;
704 if (ptr
->antic_stores
705 && (tmp
= ptr
->antic_stores
->insn ()) == NULL_RTX
)
706 ptr
->antic_stores
= ptr
->antic_stores
->next ();
710 /* Remove the stores that are not available anywhere, as there will
711 be no opportunity to optimize them. */
712 for (ptr
= store_motion_mems
, prev_next_ptr_ptr
= &store_motion_mems
;
714 ptr
= *prev_next_ptr_ptr
)
716 if (! ptr
->avail_stores
)
718 *prev_next_ptr_ptr
= ptr
->next
;
719 store_motion_mems_table
->remove_elt_with_hash (ptr
, ptr
->hash_index
);
720 free_st_expr_entry (ptr
);
723 prev_next_ptr_ptr
= &ptr
->next
;
726 ret
= enumerate_store_motion_mems ();
729 print_store_motion_mems (dump_file
);
736 /* In all code following after this, REACHING_REG has its original
737 meaning again. Avoid confusion, and undef the accessor macro for
738 the temporary marks usage in compute_store_table. */
739 #undef LAST_AVAIL_CHECK_FAILURE
741 /* Insert an instruction at the beginning of a basic block, and update
742 the BB_HEAD if needed. */
745 insert_insn_start_basic_block (rtx_insn
*insn
, basic_block bb
)
747 /* Insert at start of successor block. */
748 rtx_insn
*prev
= PREV_INSN (BB_HEAD (bb
));
749 rtx_insn
*before
= BB_HEAD (bb
);
752 if (! LABEL_P (before
)
753 && !NOTE_INSN_BASIC_BLOCK_P (before
))
756 if (prev
== BB_END (bb
))
758 before
= NEXT_INSN (before
);
761 insn
= emit_insn_after_noloc (insn
, prev
, bb
);
765 fprintf (dump_file
, "STORE_MOTION insert store at start of BB %d:\n",
767 print_inline_rtx (dump_file
, insn
, 6);
768 fprintf (dump_file
, "\n");
772 /* This routine will insert a store on an edge. EXPR is the st_expr entry for
773 the memory reference, and E is the edge to insert it on. Returns nonzero
774 if an edge insertion was performed. */
777 insert_store (struct st_expr
* expr
, edge e
)
785 /* We did all the deleted before this insert, so if we didn't delete a
786 store, then we haven't set the reaching reg yet either. */
787 if (expr
->reaching_reg
== NULL_RTX
)
790 if (e
->flags
& EDGE_FAKE
)
793 reg
= expr
->reaching_reg
;
794 insn
= gen_move_insn (copy_rtx (expr
->pattern
), reg
);
796 /* If we are inserting this expression on ALL predecessor edges of a BB,
797 insert it at the start of the BB, and reset the insert bits on the other
798 edges so we don't try to insert it on the other edges. */
800 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
801 if (!(tmp
->flags
& EDGE_FAKE
))
803 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
805 gcc_assert (index
!= EDGE_INDEX_NO_EDGE
);
806 if (! bitmap_bit_p (st_insert_map
[index
], expr
->index
))
810 /* If tmp is NULL, we found an insertion on every edge, blank the
811 insertion vector for these edges, and insert at the start of the BB. */
812 if (!tmp
&& bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
814 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
816 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
817 bitmap_clear_bit (st_insert_map
[index
], expr
->index
);
819 insert_insn_start_basic_block (insn
, bb
);
823 /* We can't put stores in the front of blocks pointed to by abnormal
824 edges since that may put a store where one didn't used to be. */
825 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
827 insert_insn_on_edge (insn
, e
);
831 fprintf (dump_file
, "STORE_MOTION insert insn on edge (%d, %d):\n",
832 e
->src
->index
, e
->dest
->index
);
833 print_inline_rtx (dump_file
, insn
, 6);
834 fprintf (dump_file
, "\n");
840 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
841 memory location in SMEXPR set in basic block BB.
843 This could be rather expensive. */
846 remove_reachable_equiv_notes (basic_block bb
, struct st_expr
*smexpr
)
848 edge_iterator
*stack
, ei
;
851 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
854 rtx mem
= smexpr
->pattern
;
856 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
));
858 ei
= ei_start (bb
->succs
);
860 bitmap_clear (visited
);
862 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
870 sbitmap_free (visited
);
873 act
= ei_edge (stack
[--sp
]);
877 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
878 || bitmap_bit_p (visited
, bb
->index
))
882 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
885 bitmap_set_bit (visited
, bb
->index
);
887 if (bitmap_bit_p (st_antloc
[bb
->index
], smexpr
->index
))
889 for (last
= smexpr
->antic_stores
;
890 BLOCK_FOR_INSN (XEXP (last
, 0)) != bb
;
891 last
= XEXP (last
, 1))
893 last
= XEXP (last
, 0);
896 last
= NEXT_INSN (BB_END (bb
));
898 for (insn
= BB_HEAD (bb
); insn
!= last
; insn
= NEXT_INSN (insn
))
899 if (NONDEBUG_INSN_P (insn
))
901 note
= find_reg_equal_equiv_note (insn
);
902 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
906 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
908 remove_note (insn
, note
);
913 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
915 if (EDGE_COUNT (bb
->succs
) > 0)
919 ei
= ei_start (bb
->succs
);
920 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
925 /* This routine will replace a store with a SET to a specified register. */
928 replace_store_insn (rtx reg
, rtx_insn
*del
, basic_block bb
,
929 struct st_expr
*smexpr
)
932 rtx mem
, note
, set
, ptr
;
934 mem
= smexpr
->pattern
;
935 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 (rtx_insn_list
*i
= expr
->avail_stores
; i
; i
= i
->next ())
1002 rtx_insn
*del
= i
->insn ();
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
;
1022 struct st_expr
* ptr
;
1023 unsigned int max_gcse_regno
= max_reg_num ();
1025 /* Build the gen_vector. This is any store in the table which is not killed
1026 by aliasing later in its block. */
1027 st_avloc
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
),
1029 bitmap_vector_clear (st_avloc
, last_basic_block_for_fn (cfun
));
1031 st_antloc
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
),
1033 bitmap_vector_clear (st_antloc
, last_basic_block_for_fn (cfun
));
1035 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1037 for (st
= ptr
->avail_stores
; st
!= NULL
; st
= st
->next ())
1040 bb
= BLOCK_FOR_INSN (insn
);
1042 /* If we've already seen an available expression in this block,
1043 we can delete this one (It occurs earlier in the block). We'll
1044 copy the SRC expression to an unused register in case there
1045 are any side effects. */
1046 if (bitmap_bit_p (st_avloc
[bb
->index
], ptr
->index
))
1048 rtx r
= gen_reg_rtx_and_attrs (ptr
->pattern
);
1050 fprintf (dump_file
, "Removing redundant store:\n");
1051 replace_store_insn (r
, st
->insn (), bb
, ptr
);
1054 bitmap_set_bit (st_avloc
[bb
->index
], ptr
->index
);
1057 for (st
= ptr
->antic_stores
; st
!= NULL
; st
= st
->next ())
1060 bb
= BLOCK_FOR_INSN (insn
);
1061 bitmap_set_bit (st_antloc
[bb
->index
], ptr
->index
);
1065 st_kill
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), num_stores
);
1066 bitmap_vector_clear (st_kill
, last_basic_block_for_fn (cfun
));
1068 st_transp
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), num_stores
);
1069 bitmap_vector_clear (st_transp
, last_basic_block_for_fn (cfun
));
1070 regs_set_in_block
= XNEWVEC (int, max_gcse_regno
);
1072 FOR_EACH_BB_FN (bb
, cfun
)
1074 memset (regs_set_in_block
, 0, sizeof (int) * max_gcse_regno
);
1076 FOR_BB_INSNS (bb
, insn
)
1077 if (NONDEBUG_INSN_P (insn
))
1080 FOR_EACH_INSN_DEF (def
, insn
)
1082 unsigned int ref_regno
= DF_REF_REGNO (def
);
1083 if (ref_regno
< max_gcse_regno
)
1084 regs_set_in_block
[DF_REF_REGNO (def
)] = 1;
1088 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1090 if (store_killed_after (ptr
->pattern
, ptr
->pattern_regs
, BB_HEAD (bb
),
1091 bb
, regs_set_in_block
, NULL
))
1093 /* It should not be necessary to consider the expression
1094 killed if it is both anticipatable and available. */
1095 if (!bitmap_bit_p (st_antloc
[bb
->index
], ptr
->index
)
1096 || !bitmap_bit_p (st_avloc
[bb
->index
], ptr
->index
))
1097 bitmap_set_bit (st_kill
[bb
->index
], ptr
->index
);
1100 bitmap_set_bit (st_transp
[bb
->index
], ptr
->index
);
1104 free (regs_set_in_block
);
1108 dump_bitmap_vector (dump_file
, "st_antloc", "", st_antloc
,
1109 last_basic_block_for_fn (cfun
));
1110 dump_bitmap_vector (dump_file
, "st_kill", "", st_kill
,
1111 last_basic_block_for_fn (cfun
));
1112 dump_bitmap_vector (dump_file
, "st_transp", "", st_transp
,
1113 last_basic_block_for_fn (cfun
));
1114 dump_bitmap_vector (dump_file
, "st_avloc", "", st_avloc
,
1115 last_basic_block_for_fn (cfun
));
1119 /* Free memory used by store motion. */
1122 free_store_memory (void)
1124 free_store_motion_mems ();
1127 sbitmap_vector_free (st_avloc
);
1129 sbitmap_vector_free (st_kill
);
1131 sbitmap_vector_free (st_transp
);
1133 sbitmap_vector_free (st_antloc
);
1135 sbitmap_vector_free (st_insert_map
);
1137 sbitmap_vector_free (st_delete_map
);
1139 st_avloc
= st_kill
= st_transp
= st_antloc
= NULL
;
1140 st_insert_map
= st_delete_map
= NULL
;
1143 /* Perform store motion. Much like gcse, except we move expressions the
1144 other way by looking at the flowgraph in reverse.
1145 Return non-zero if transformations are performed by the pass. */
1148 one_store_motion_pass (void)
1152 struct st_expr
* ptr
;
1153 int did_edge_inserts
= 0;
1154 int n_stores_deleted
= 0;
1155 int n_stores_created
= 0;
1157 init_alias_analysis ();
1159 /* Find all the available and anticipatable stores. */
1160 num_stores
= compute_store_table ();
1161 if (num_stores
== 0)
1163 delete store_motion_mems_table
;
1164 store_motion_mems_table
= NULL
;
1165 end_alias_analysis ();
1169 /* Now compute kill & transp vectors. */
1170 build_store_vectors ();
1171 add_noreturn_fake_exit_edges ();
1172 connect_infinite_loops_to_exit ();
1174 edge_list
= pre_edge_rev_lcm (num_stores
, st_transp
, st_avloc
,
1175 st_antloc
, st_kill
, &st_insert_map
,
1178 /* Now we want to insert the new stores which are going to be needed. */
1179 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1181 /* If any of the edges we have above are abnormal, we can't move this
1183 for (x
= NUM_EDGES (edge_list
) - 1; x
>= 0; x
--)
1184 if (bitmap_bit_p (st_insert_map
[x
], ptr
->index
)
1185 && (INDEX_EDGE (edge_list
, x
)->flags
& EDGE_ABNORMAL
))
1190 if (dump_file
!= NULL
)
1192 "Can't replace store %d: abnormal edge from %d to %d\n",
1193 ptr
->index
, INDEX_EDGE (edge_list
, x
)->src
->index
,
1194 INDEX_EDGE (edge_list
, x
)->dest
->index
);
1198 /* Now we want to insert the new stores which are going to be needed. */
1200 FOR_EACH_BB_FN (bb
, cfun
)
1201 if (bitmap_bit_p (st_delete_map
[bb
->index
], ptr
->index
))
1203 delete_store (ptr
, bb
);
1207 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
1208 if (bitmap_bit_p (st_insert_map
[x
], ptr
->index
))
1210 did_edge_inserts
|= insert_store (ptr
, INDEX_EDGE (edge_list
, x
));
1215 if (did_edge_inserts
)
1216 commit_edge_insertions ();
1218 free_store_memory ();
1219 free_edge_list (edge_list
);
1220 remove_fake_exit_edges ();
1221 end_alias_analysis ();
1225 fprintf (dump_file
, "STORE_MOTION of %s, %d basic blocks, ",
1226 current_function_name (), n_basic_blocks_for_fn (cfun
));
1227 fprintf (dump_file
, "%d insns deleted, %d insns created\n",
1228 n_stores_deleted
, n_stores_created
);
1231 return (n_stores_deleted
> 0 || n_stores_created
> 0);
1236 execute_rtl_store_motion (void)
1238 delete_unreachable_blocks ();
1240 flag_rerun_cse_after_global_opts
|= one_store_motion_pass ();
1246 const pass_data pass_data_rtl_store_motion
=
1248 RTL_PASS
, /* type */
1249 "store_motion", /* name */
1250 OPTGROUP_NONE
, /* optinfo_flags */
1252 PROP_cfglayout
, /* properties_required */
1253 0, /* properties_provided */
1254 0, /* properties_destroyed */
1255 0, /* todo_flags_start */
1256 TODO_df_finish
, /* todo_flags_finish */
1259 class pass_rtl_store_motion
: public rtl_opt_pass
1262 pass_rtl_store_motion (gcc::context
*ctxt
)
1263 : rtl_opt_pass (pass_data_rtl_store_motion
, ctxt
)
1266 /* opt_pass methods: */
1267 virtual bool gate (function
*);
1268 virtual unsigned int execute (function
*)
1270 return execute_rtl_store_motion ();
1273 }; // class pass_rtl_store_motion
1276 pass_rtl_store_motion::gate (function
*fun
)
1278 return optimize
> 0 && flag_gcse_sm
1279 && !fun
->calls_setjmp
1280 && optimize_function_for_speed_p (fun
)
1281 && dbg_cnt (store_motion
);
1287 make_pass_rtl_store_motion (gcc::context
*ctxt
)
1289 return new pass_rtl_store_motion (ctxt
);