1 /* Store motion via Lazy Code Motion on the reverse CFG.
2 Copyright (C) 1997-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
24 #include "diagnostic-core.h"
31 #include "hard-reg-set.h"
33 #include "insn-config.h"
35 #include "basic-block.h"
41 #include "tree-pass.h"
42 #include "hash-table.h"
46 /* This pass implements downward store motion.
47 As of May 1, 2009, the pass is not enabled by default on any target,
48 but bootstrap completes on ia64 and x86_64 with the pass enabled. */
51 - remove_reachable_equiv_notes is an incomprehensible pile of goo and
52 a compile time hog that needs a rewrite (maybe cache st_exprs to
53 invalidate REG_EQUAL/REG_EQUIV notes for?).
54 - pattern_regs in st_expr should be a regset (on its own obstack).
55 - antic_stores and avail_stores should be VECs instead of lists.
56 - store_motion_mems should be a vec instead of a list.
57 - there should be an alloc pool for struct st_expr objects.
58 - investigate whether it is helpful to make the address of an st_expr
60 - when GIMPLE alias information is exported, the effectiveness of this
61 pass should be re-evaluated.
64 /* This is a list of store expressions (MEMs). The structure is used
65 as an expression table to track stores which look interesting, and
66 might be moveable towards the exit block. */
70 /* Pattern of this mem. */
72 /* List of registers mentioned by the mem. */
74 /* INSN list of stores that are locally anticipatable. */
76 /* INSN list of stores that are locally available. */
78 /* Next in the list. */
79 struct st_expr
* next
;
80 /* Store ID in the dataflow bitmaps. */
82 /* Hash value for the hash table. */
83 unsigned int hash_index
;
84 /* Register holding the stored expression when a store is moved.
85 This field is also used as a cache in find_moveable_store, see
86 LAST_AVAIL_CHECK_FAILURE below. */
90 /* Head of the list of load/store memory refs. */
91 static struct st_expr
* store_motion_mems
= NULL
;
93 /* These bitmaps will hold the local dataflow properties per basic block. */
94 static sbitmap
*st_kill
, *st_avloc
, *st_antloc
, *st_transp
;
96 /* Nonzero for expressions which should be inserted on a specific edge. */
97 static sbitmap
*st_insert_map
;
99 /* Nonzero for expressions which should be deleted in a specific block. */
100 static sbitmap
*st_delete_map
;
102 /* Global holding the number of store expressions we are dealing with. */
103 static int num_stores
;
105 /* Contains the edge_list returned by pre_edge_lcm. */
106 static struct edge_list
*edge_list
;
108 /* Hashtable helpers. */
110 struct st_expr_hasher
: typed_noop_remove
<st_expr
>
112 typedef st_expr value_type
;
113 typedef st_expr compare_type
;
114 static inline hashval_t
hash (const value_type
*);
115 static inline bool equal (const value_type
*, const compare_type
*);
119 st_expr_hasher::hash (const value_type
*x
)
121 int do_not_record_p
= 0;
122 return hash_rtx (x
->pattern
, GET_MODE (x
->pattern
), &do_not_record_p
, NULL
, false);
126 st_expr_hasher::equal (const value_type
*ptr1
, const compare_type
*ptr2
)
128 return exp_equiv_p (ptr1
->pattern
, ptr2
->pattern
, 0, true);
131 /* Hashtable for the load/store memory refs. */
132 static hash_table
<st_expr_hasher
> *store_motion_mems_table
;
134 /* This will search the st_expr list for a matching expression. If it
135 doesn't find one, we create one and initialize it. */
137 static struct st_expr
*
138 st_expr_entry (rtx x
)
140 int do_not_record_p
= 0;
141 struct st_expr
* ptr
;
146 hash
= hash_rtx (x
, GET_MODE (x
), &do_not_record_p
,
147 NULL
, /*have_reg_qty=*/false);
150 slot
= store_motion_mems_table
->find_slot_with_hash (&e
, hash
, INSERT
);
154 ptr
= XNEW (struct st_expr
);
156 ptr
->next
= store_motion_mems
;
158 ptr
->pattern_regs
= NULL_RTX
;
159 ptr
->antic_stores
= NULL_RTX
;
160 ptr
->avail_stores
= NULL_RTX
;
161 ptr
->reaching_reg
= NULL_RTX
;
163 ptr
->hash_index
= hash
;
164 store_motion_mems
= ptr
;
170 /* Free up an individual st_expr entry. */
173 free_st_expr_entry (struct st_expr
* ptr
)
175 free_INSN_LIST_list (& ptr
->antic_stores
);
176 free_INSN_LIST_list (& ptr
->avail_stores
);
181 /* Free up all memory associated with the st_expr list. */
184 free_store_motion_mems (void)
186 delete store_motion_mems_table
;
187 store_motion_mems_table
= NULL
;
189 while (store_motion_mems
)
191 struct st_expr
* tmp
= store_motion_mems
;
192 store_motion_mems
= store_motion_mems
->next
;
193 free_st_expr_entry (tmp
);
195 store_motion_mems
= NULL
;
198 /* Assign each element of the list of mems a monotonically increasing value. */
201 enumerate_store_motion_mems (void)
203 struct st_expr
* ptr
;
206 for (ptr
= store_motion_mems
; ptr
!= NULL
; ptr
= ptr
->next
)
212 /* Return first item in the list. */
214 static inline struct st_expr
*
217 return store_motion_mems
;
220 /* Return the next item in the list after the specified one. */
222 static inline struct st_expr
*
223 next_st_expr (struct st_expr
* ptr
)
228 /* Dump debugging info about the store_motion_mems list. */
231 print_store_motion_mems (FILE * file
)
233 struct st_expr
* ptr
;
235 fprintf (dump_file
, "STORE_MOTION list of MEM exprs considered:\n");
237 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
239 fprintf (file
, " Pattern (%3d): ", ptr
->index
);
241 print_rtl (file
, ptr
->pattern
);
243 fprintf (file
, "\n ANTIC stores : ");
245 if (ptr
->antic_stores
)
246 print_rtl (file
, ptr
->antic_stores
);
248 fprintf (file
, "(nil)");
250 fprintf (file
, "\n AVAIL stores : ");
252 if (ptr
->avail_stores
)
253 print_rtl (file
, ptr
->avail_stores
);
255 fprintf (file
, "(nil)");
257 fprintf (file
, "\n\n");
260 fprintf (file
, "\n");
263 /* Return zero if some of the registers in list X are killed
264 due to set of registers in bitmap REGS_SET. */
267 store_ops_ok (const_rtx x
, int *regs_set
)
271 for (; x
; x
= XEXP (x
, 1))
274 if (regs_set
[REGNO (reg
)])
281 /* Helper for extract_mentioned_regs. */
284 extract_mentioned_regs_1 (rtx
*loc
, void *data
)
286 rtx
*mentioned_regs_p
= (rtx
*) data
;
289 *mentioned_regs_p
= alloc_EXPR_LIST (0, *loc
, *mentioned_regs_p
);
294 /* Returns a list of registers mentioned in X.
295 FIXME: A regset would be prettier and less expensive. */
298 extract_mentioned_regs (rtx x
)
300 rtx mentioned_regs
= NULL
;
301 for_each_rtx (&x
, extract_mentioned_regs_1
, &mentioned_regs
);
302 return mentioned_regs
;
305 /* Check to see if the load X is aliased with STORE_PATTERN.
306 AFTER is true if we are checking the case when STORE_PATTERN occurs
310 load_kills_store (const_rtx x
, const_rtx store_pattern
, int after
)
313 return anti_dependence (x
, store_pattern
);
315 return true_dependence (store_pattern
, GET_MODE (store_pattern
), x
);
318 /* Go through the entire rtx X, looking for any loads which might alias
319 STORE_PATTERN. Return true if found.
320 AFTER is true if we are checking the case when STORE_PATTERN occurs
324 find_loads (const_rtx x
, const_rtx store_pattern
, int after
)
333 if (GET_CODE (x
) == SET
)
338 if (load_kills_store (x
, store_pattern
, after
))
342 /* Recursively process the insn. */
343 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
345 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0 && !ret
; i
--)
348 ret
|= find_loads (XEXP (x
, i
), store_pattern
, after
);
349 else if (fmt
[i
] == 'E')
350 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
351 ret
|= find_loads (XVECEXP (x
, i
, j
), store_pattern
, after
);
356 /* Go through pattern PAT looking for any loads which might kill the
357 store in X. Return true if found.
358 AFTER is true if we are checking the case when loads kill X occurs
359 after the insn for PAT. */
362 store_killed_in_pat (const_rtx x
, const_rtx pat
, int after
)
364 if (GET_CODE (pat
) == SET
)
366 rtx dest
= SET_DEST (pat
);
368 if (GET_CODE (dest
) == ZERO_EXTRACT
)
369 dest
= XEXP (dest
, 0);
371 /* Check for memory stores to aliased objects. */
373 && !exp_equiv_p (dest
, x
, 0, true))
377 if (output_dependence (dest
, x
))
382 if (output_dependence (x
, dest
))
388 if (find_loads (pat
, x
, after
))
394 /* Check if INSN kills the store pattern X (is aliased with it).
395 AFTER is true if we are checking the case when store X occurs
396 after the insn. Return true if it does. */
399 store_killed_in_insn (const_rtx x
, const_rtx x_regs
, const rtx_insn
*insn
, int after
)
401 const_rtx reg
, note
, pat
;
403 if (! NONDEBUG_INSN_P (insn
))
408 /* A normal or pure call might read from pattern,
409 but a const call will not. */
410 if (!RTL_CONST_CALL_P (insn
))
413 /* But even a const call reads its parameters. Check whether the
414 base of some of registers used in mem is stack pointer. */
415 for (reg
= x_regs
; reg
; reg
= XEXP (reg
, 1))
416 if (may_be_sp_based_p (XEXP (reg
, 0)))
422 pat
= PATTERN (insn
);
423 if (GET_CODE (pat
) == SET
)
425 if (store_killed_in_pat (x
, pat
, after
))
428 else if (GET_CODE (pat
) == PARALLEL
)
432 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
433 if (store_killed_in_pat (x
, XVECEXP (pat
, 0, i
), after
))
436 else if (find_loads (PATTERN (insn
), x
, after
))
439 /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
440 location aliased with X, then this insn kills X. */
441 note
= find_reg_equal_equiv_note (insn
);
444 note
= XEXP (note
, 0);
446 /* However, if the note represents a must alias rather than a may
447 alias relationship, then it does not kill X. */
448 if (exp_equiv_p (note
, x
, 0, true))
451 /* See if there are any aliased loads in the note. */
452 return find_loads (note
, x
, after
);
455 /* Returns true if the expression X is loaded or clobbered on or after INSN
456 within basic block BB. REGS_SET_AFTER is bitmap of registers set in
457 or after the insn. X_REGS is list of registers mentioned in X. If the store
458 is killed, return the last insn in that it occurs in FAIL_INSN. */
461 store_killed_after (const_rtx x
, const_rtx x_regs
, const rtx_insn
*insn
,
462 const_basic_block bb
,
463 int *regs_set_after
, rtx
*fail_insn
)
465 rtx_insn
*last
= BB_END (bb
), *act
;
467 if (!store_ops_ok (x_regs
, regs_set_after
))
469 /* We do not know where it will happen. */
471 *fail_insn
= NULL_RTX
;
475 /* Scan from the end, so that fail_insn is determined correctly. */
476 for (act
= last
; act
!= PREV_INSN (insn
); act
= PREV_INSN (act
))
477 if (store_killed_in_insn (x
, x_regs
, act
, false))
487 /* Returns true if the expression X is loaded or clobbered on or before INSN
488 within basic block BB. X_REGS is list of registers mentioned in X.
489 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
491 store_killed_before (const_rtx x
, const_rtx x_regs
, const rtx_insn
*insn
,
492 const_basic_block bb
, int *regs_set_before
)
494 rtx_insn
*first
= BB_HEAD (bb
);
496 if (!store_ops_ok (x_regs
, regs_set_before
))
499 for ( ; insn
!= PREV_INSN (first
); insn
= PREV_INSN (insn
))
500 if (store_killed_in_insn (x
, x_regs
, insn
, true))
506 /* The last insn in the basic block that compute_store_table is processing,
507 where store_killed_after is true for X.
508 Since we go through the basic block from BB_END to BB_HEAD, this is
509 also the available store at the end of the basic block. Therefore
510 this is in effect a cache, to avoid calling store_killed_after for
511 equivalent aliasing store expressions.
512 This value is only meaningful during the computation of the store
513 table. We hi-jack the REACHING_REG field of struct st_expr to save
515 #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
517 /* Determine whether INSN is MEM store pattern that we will consider moving.
518 REGS_SET_BEFORE is bitmap of registers set before (and including) the
519 current insn, REGS_SET_AFTER is bitmap of registers set after (and
520 including) the insn in this basic block. We must be passing through BB from
521 head to end, as we are using this fact to speed things up.
523 The results are stored this way:
525 -- the first anticipatable expression is added into ANTIC_STORES
526 -- if the processed expression is not anticipatable, NULL_RTX is added
527 there instead, so that we can use it as indicator that no further
528 expression of this type may be anticipatable
529 -- if the expression is available, it is added as head of AVAIL_STORES;
530 consequently, all of them but this head are dead and may be deleted.
531 -- if the expression is not available, the insn due to that it fails to be
532 available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
534 The things are complicated a bit by fact that there already may be stores
535 to the same MEM from other blocks; also caller must take care of the
536 necessary cleanup of the temporary markers after end of the basic block.
540 find_moveable_store (rtx_insn
*insn
, int *regs_set_before
, int *regs_set_after
)
542 struct st_expr
* ptr
;
544 int check_anticipatable
, check_available
;
545 basic_block bb
= BLOCK_FOR_INSN (insn
);
547 set
= single_set (insn
);
551 dest
= SET_DEST (set
);
553 if (! MEM_P (dest
) || MEM_VOLATILE_P (dest
)
554 || GET_MODE (dest
) == BLKmode
)
557 if (side_effects_p (dest
))
560 /* If we are handling exceptions, we must be careful with memory references
561 that may trap. If we are not, the behavior is undefined, so we may just
563 if (cfun
->can_throw_non_call_exceptions
&& may_trap_p (dest
))
566 /* Even if the destination cannot trap, the source may. In this case we'd
567 need to handle updating the REG_EH_REGION note. */
568 if (find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
))
571 /* Make sure that the SET_SRC of this store insns can be assigned to
572 a register, or we will fail later on in replace_store_insn, which
573 assumes that we can do this. But sometimes the target machine has
574 oddities like MEM read-modify-write instruction. See for example
576 if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set
)))
579 ptr
= st_expr_entry (dest
);
580 if (!ptr
->pattern_regs
)
581 ptr
->pattern_regs
= extract_mentioned_regs (dest
);
583 /* Do not check for anticipatability if we either found one anticipatable
584 store already, or tested for one and found out that it was killed. */
585 check_anticipatable
= 0;
586 if (!ptr
->antic_stores
)
587 check_anticipatable
= 1;
590 tmp
= XEXP (ptr
->antic_stores
, 0);
592 && BLOCK_FOR_INSN (tmp
) != bb
)
593 check_anticipatable
= 1;
595 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 tmp
= XEXP (ptr
->avail_stores
, 0);
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
))
622 for (tmp
= BB_END (bb
);
623 tmp
!= insn
&& tmp
!= LAST_AVAIL_CHECK_FAILURE (ptr
);
624 tmp
= PREV_INSN (tmp
))
630 check_available
= store_killed_after (dest
, ptr
->pattern_regs
, insn
,
632 &LAST_AVAIL_CHECK_FAILURE (ptr
));
634 if (!check_available
)
635 ptr
->avail_stores
= alloc_INSN_LIST (insn
, ptr
->avail_stores
);
638 /* Find available and anticipatable stores. */
641 compute_store_table (void)
645 #ifdef ENABLE_CHECKING
651 int *last_set_in
, *already_set
;
652 struct st_expr
* ptr
, **prev_next_ptr_ptr
;
653 unsigned int max_gcse_regno
= max_reg_num ();
655 store_motion_mems
= NULL
;
656 store_motion_mems_table
= new hash_table
<st_expr_hasher
> (13);
657 last_set_in
= XCNEWVEC (int, max_gcse_regno
);
658 already_set
= XNEWVEC (int, max_gcse_regno
);
660 /* Find all the stores we care about. */
661 FOR_EACH_BB_FN (bb
, cfun
)
663 /* First compute the registers set in this block. */
664 FOR_BB_INSNS (bb
, insn
)
667 if (! NONDEBUG_INSN_P (insn
))
670 FOR_EACH_INSN_DEF (def
, insn
)
671 last_set_in
[DF_REF_REGNO (def
)] = INSN_UID (insn
);
674 /* Now find the stores. */
675 memset (already_set
, 0, sizeof (int) * max_gcse_regno
);
676 FOR_BB_INSNS (bb
, insn
)
678 if (! NONDEBUG_INSN_P (insn
))
681 FOR_EACH_INSN_DEF (def
, insn
)
682 already_set
[DF_REF_REGNO (def
)] = INSN_UID (insn
);
684 /* Now that we've marked regs, look for stores. */
685 find_moveable_store (insn
, already_set
, last_set_in
);
687 /* Unmark regs that are no longer set. */
688 FOR_EACH_INSN_DEF (def
, insn
)
689 if (last_set_in
[DF_REF_REGNO (def
)] == INSN_UID (insn
))
690 last_set_in
[DF_REF_REGNO (def
)] = 0;
693 #ifdef ENABLE_CHECKING
694 /* last_set_in should now be all-zero. */
695 for (regno
= 0; regno
< max_gcse_regno
; regno
++)
696 gcc_assert (!last_set_in
[regno
]);
699 /* Clear temporary marks. */
700 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
702 LAST_AVAIL_CHECK_FAILURE (ptr
) = NULL_RTX
;
703 if (ptr
->antic_stores
704 && (tmp
= XEXP (ptr
->antic_stores
, 0)) == NULL_RTX
)
705 ptr
->antic_stores
= XEXP (ptr
->antic_stores
, 1);
709 /* Remove the stores that are not available anywhere, as there will
710 be no opportunity to optimize them. */
711 for (ptr
= store_motion_mems
, prev_next_ptr_ptr
= &store_motion_mems
;
713 ptr
= *prev_next_ptr_ptr
)
715 if (! ptr
->avail_stores
)
717 *prev_next_ptr_ptr
= ptr
->next
;
718 store_motion_mems_table
->remove_elt_with_hash (ptr
, ptr
->hash_index
);
719 free_st_expr_entry (ptr
);
722 prev_next_ptr_ptr
= &ptr
->next
;
725 ret
= enumerate_store_motion_mems ();
728 print_store_motion_mems (dump_file
);
735 /* In all code following after this, REACHING_REG has its original
736 meaning again. Avoid confusion, and undef the accessor macro for
737 the temporary marks usage in compute_store_table. */
738 #undef LAST_AVAIL_CHECK_FAILURE
740 /* Insert an instruction at the beginning of a basic block, and update
741 the BB_HEAD if needed. */
744 insert_insn_start_basic_block (rtx_insn
*insn
, basic_block bb
)
746 /* Insert at start of successor block. */
747 rtx_insn
*prev
= PREV_INSN (BB_HEAD (bb
));
748 rtx_insn
*before
= BB_HEAD (bb
);
751 if (! LABEL_P (before
)
752 && !NOTE_INSN_BASIC_BLOCK_P (before
))
755 if (prev
== BB_END (bb
))
757 before
= NEXT_INSN (before
);
760 insn
= emit_insn_after_noloc (insn
, prev
, bb
);
764 fprintf (dump_file
, "STORE_MOTION insert store at start of BB %d:\n",
766 print_inline_rtx (dump_file
, insn
, 6);
767 fprintf (dump_file
, "\n");
771 /* This routine will insert a store on an edge. EXPR is the st_expr entry for
772 the memory reference, and E is the edge to insert it on. Returns nonzero
773 if an edge insertion was performed. */
776 insert_store (struct st_expr
* expr
, edge e
)
784 /* We did all the deleted before this insert, so if we didn't delete a
785 store, then we haven't set the reaching reg yet either. */
786 if (expr
->reaching_reg
== NULL_RTX
)
789 if (e
->flags
& EDGE_FAKE
)
792 reg
= expr
->reaching_reg
;
793 insn
= as_a
<rtx_insn
*> (gen_move_insn (copy_rtx (expr
->pattern
), reg
));
795 /* If we are inserting this expression on ALL predecessor edges of a BB,
796 insert it at the start of the BB, and reset the insert bits on the other
797 edges so we don't try to insert it on the other edges. */
799 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
800 if (!(tmp
->flags
& EDGE_FAKE
))
802 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
804 gcc_assert (index
!= EDGE_INDEX_NO_EDGE
);
805 if (! bitmap_bit_p (st_insert_map
[index
], expr
->index
))
809 /* If tmp is NULL, we found an insertion on every edge, blank the
810 insertion vector for these edges, and insert at the start of the BB. */
811 if (!tmp
&& bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
813 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
815 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
816 bitmap_clear_bit (st_insert_map
[index
], expr
->index
);
818 insert_insn_start_basic_block (insn
, bb
);
822 /* We can't put stores in the front of blocks pointed to by abnormal
823 edges since that may put a store where one didn't used to be. */
824 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
826 insert_insn_on_edge (insn
, e
);
830 fprintf (dump_file
, "STORE_MOTION insert insn on edge (%d, %d):\n",
831 e
->src
->index
, e
->dest
->index
);
832 print_inline_rtx (dump_file
, insn
, 6);
833 fprintf (dump_file
, "\n");
839 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
840 memory location in SMEXPR set in basic block BB.
842 This could be rather expensive. */
845 remove_reachable_equiv_notes (basic_block bb
, struct st_expr
*smexpr
)
847 edge_iterator
*stack
, ei
;
850 sbitmap visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
853 rtx mem
= smexpr
->pattern
;
855 stack
= XNEWVEC (edge_iterator
, n_basic_blocks_for_fn (cfun
));
857 ei
= ei_start (bb
->succs
);
859 bitmap_clear (visited
);
861 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
869 sbitmap_free (visited
);
872 act
= ei_edge (stack
[--sp
]);
876 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
877 || bitmap_bit_p (visited
, bb
->index
))
881 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
884 bitmap_set_bit (visited
, bb
->index
);
886 if (bitmap_bit_p (st_antloc
[bb
->index
], smexpr
->index
))
888 for (last
= smexpr
->antic_stores
;
889 BLOCK_FOR_INSN (XEXP (last
, 0)) != bb
;
890 last
= XEXP (last
, 1))
892 last
= XEXP (last
, 0);
895 last
= NEXT_INSN (BB_END (bb
));
897 for (insn
= BB_HEAD (bb
); insn
!= last
; insn
= NEXT_INSN (insn
))
898 if (NONDEBUG_INSN_P (insn
))
900 note
= find_reg_equal_equiv_note (insn
);
901 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
905 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
907 remove_note (insn
, note
);
912 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
914 if (EDGE_COUNT (bb
->succs
) > 0)
918 ei
= ei_start (bb
->succs
);
919 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
924 /* This routine will replace a store with a SET to a specified register. */
927 replace_store_insn (rtx reg
, rtx del
, basic_block bb
, struct st_expr
*smexpr
)
930 rtx mem
, note
, set
, ptr
;
932 mem
= smexpr
->pattern
;
933 insn
= as_a
<rtx_insn
*> (gen_move_insn (reg
, SET_SRC (single_set (del
))));
935 for (ptr
= smexpr
->antic_stores
; ptr
; ptr
= XEXP (ptr
, 1))
936 if (XEXP (ptr
, 0) == del
)
938 XEXP (ptr
, 0) = insn
;
942 /* Move the notes from the deleted insn to its replacement. */
943 REG_NOTES (insn
) = REG_NOTES (del
);
945 /* Emit the insn AFTER all the notes are transferred.
946 This is cheaper since we avoid df rescanning for the note change. */
947 insn
= emit_insn_after (insn
, del
);
952 "STORE_MOTION delete insn in BB %d:\n ", bb
->index
);
953 print_inline_rtx (dump_file
, del
, 6);
954 fprintf (dump_file
, "\nSTORE_MOTION replaced with insn:\n ");
955 print_inline_rtx (dump_file
, insn
, 6);
956 fprintf (dump_file
, "\n");
961 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
962 they are no longer accurate provided that they are reached by this
963 definition, so drop them. */
964 for (; insn
!= NEXT_INSN (BB_END (bb
)); insn
= NEXT_INSN (insn
))
965 if (NONDEBUG_INSN_P (insn
))
967 set
= single_set (insn
);
970 if (exp_equiv_p (SET_DEST (set
), mem
, 0, true))
972 note
= find_reg_equal_equiv_note (insn
);
973 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
977 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
979 remove_note (insn
, note
);
981 remove_reachable_equiv_notes (bb
, smexpr
);
985 /* Delete a store, but copy the value that would have been stored into
986 the reaching_reg for later storing. */
989 delete_store (struct st_expr
* expr
, basic_block bb
)
993 if (expr
->reaching_reg
== NULL_RTX
)
994 expr
->reaching_reg
= gen_reg_rtx_and_attrs (expr
->pattern
);
996 reg
= expr
->reaching_reg
;
998 for (i
= expr
->avail_stores
; i
; i
= XEXP (i
, 1))
1001 if (BLOCK_FOR_INSN (del
) == bb
)
1003 /* We know there is only one since we deleted redundant
1004 ones during the available computation. */
1005 replace_store_insn (reg
, del
, bb
, expr
);
1011 /* Fill in available, anticipatable, transparent and kill vectors in
1012 STORE_DATA, based on lists of available and anticipatable stores. */
1014 build_store_vectors (void)
1017 int *regs_set_in_block
;
1019 struct st_expr
* ptr
;
1020 unsigned int max_gcse_regno
= max_reg_num ();
1022 /* Build the gen_vector. This is any store in the table which is not killed
1023 by aliasing later in its block. */
1024 st_avloc
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
),
1026 bitmap_vector_clear (st_avloc
, last_basic_block_for_fn (cfun
));
1028 st_antloc
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
),
1030 bitmap_vector_clear (st_antloc
, last_basic_block_for_fn (cfun
));
1032 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1034 for (st
= ptr
->avail_stores
; st
!= NULL
; st
= XEXP (st
, 1))
1036 insn
= XEXP (st
, 0);
1037 bb
= BLOCK_FOR_INSN (insn
);
1039 /* If we've already seen an available expression in this block,
1040 we can delete this one (It occurs earlier in the block). We'll
1041 copy the SRC expression to an unused register in case there
1042 are any side effects. */
1043 if (bitmap_bit_p (st_avloc
[bb
->index
], ptr
->index
))
1045 rtx r
= gen_reg_rtx_and_attrs (ptr
->pattern
);
1047 fprintf (dump_file
, "Removing redundant store:\n");
1048 replace_store_insn (r
, XEXP (st
, 0), bb
, ptr
);
1051 bitmap_set_bit (st_avloc
[bb
->index
], ptr
->index
);
1054 for (st
= ptr
->antic_stores
; st
!= NULL
; st
= XEXP (st
, 1))
1056 insn
= XEXP (st
, 0);
1057 bb
= BLOCK_FOR_INSN (insn
);
1058 bitmap_set_bit (st_antloc
[bb
->index
], ptr
->index
);
1062 st_kill
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), num_stores
);
1063 bitmap_vector_clear (st_kill
, last_basic_block_for_fn (cfun
));
1065 st_transp
= sbitmap_vector_alloc (last_basic_block_for_fn (cfun
), num_stores
);
1066 bitmap_vector_clear (st_transp
, last_basic_block_for_fn (cfun
));
1067 regs_set_in_block
= XNEWVEC (int, max_gcse_regno
);
1069 FOR_EACH_BB_FN (bb
, cfun
)
1071 memset (regs_set_in_block
, 0, sizeof (int) * max_gcse_regno
);
1073 FOR_BB_INSNS (bb
, insn
)
1074 if (NONDEBUG_INSN_P (insn
))
1077 FOR_EACH_INSN_DEF (def
, insn
)
1079 unsigned int ref_regno
= DF_REF_REGNO (def
);
1080 if (ref_regno
< max_gcse_regno
)
1081 regs_set_in_block
[DF_REF_REGNO (def
)] = 1;
1085 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1087 if (store_killed_after (ptr
->pattern
, ptr
->pattern_regs
, BB_HEAD (bb
),
1088 bb
, regs_set_in_block
, NULL
))
1090 /* It should not be necessary to consider the expression
1091 killed if it is both anticipatable and available. */
1092 if (!bitmap_bit_p (st_antloc
[bb
->index
], ptr
->index
)
1093 || !bitmap_bit_p (st_avloc
[bb
->index
], ptr
->index
))
1094 bitmap_set_bit (st_kill
[bb
->index
], ptr
->index
);
1097 bitmap_set_bit (st_transp
[bb
->index
], ptr
->index
);
1101 free (regs_set_in_block
);
1105 dump_bitmap_vector (dump_file
, "st_antloc", "", st_antloc
,
1106 last_basic_block_for_fn (cfun
));
1107 dump_bitmap_vector (dump_file
, "st_kill", "", st_kill
,
1108 last_basic_block_for_fn (cfun
));
1109 dump_bitmap_vector (dump_file
, "st_transp", "", st_transp
,
1110 last_basic_block_for_fn (cfun
));
1111 dump_bitmap_vector (dump_file
, "st_avloc", "", st_avloc
,
1112 last_basic_block_for_fn (cfun
));
1116 /* Free memory used by store motion. */
1119 free_store_memory (void)
1121 free_store_motion_mems ();
1124 sbitmap_vector_free (st_avloc
);
1126 sbitmap_vector_free (st_kill
);
1128 sbitmap_vector_free (st_transp
);
1130 sbitmap_vector_free (st_antloc
);
1132 sbitmap_vector_free (st_insert_map
);
1134 sbitmap_vector_free (st_delete_map
);
1136 st_avloc
= st_kill
= st_transp
= st_antloc
= NULL
;
1137 st_insert_map
= st_delete_map
= NULL
;
1140 /* Perform store motion. Much like gcse, except we move expressions the
1141 other way by looking at the flowgraph in reverse.
1142 Return non-zero if transformations are performed by the pass. */
1145 one_store_motion_pass (void)
1149 struct st_expr
* ptr
;
1150 int did_edge_inserts
= 0;
1151 int n_stores_deleted
= 0;
1152 int n_stores_created
= 0;
1154 init_alias_analysis ();
1156 /* Find all the available and anticipatable stores. */
1157 num_stores
= compute_store_table ();
1158 if (num_stores
== 0)
1160 delete store_motion_mems_table
;
1161 store_motion_mems_table
= NULL
;
1162 end_alias_analysis ();
1166 /* Now compute kill & transp vectors. */
1167 build_store_vectors ();
1168 add_noreturn_fake_exit_edges ();
1169 connect_infinite_loops_to_exit ();
1171 edge_list
= pre_edge_rev_lcm (num_stores
, st_transp
, st_avloc
,
1172 st_antloc
, st_kill
, &st_insert_map
,
1175 /* Now we want to insert the new stores which are going to be needed. */
1176 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1178 /* If any of the edges we have above are abnormal, we can't move this
1180 for (x
= NUM_EDGES (edge_list
) - 1; x
>= 0; x
--)
1181 if (bitmap_bit_p (st_insert_map
[x
], ptr
->index
)
1182 && (INDEX_EDGE (edge_list
, x
)->flags
& EDGE_ABNORMAL
))
1187 if (dump_file
!= NULL
)
1189 "Can't replace store %d: abnormal edge from %d to %d\n",
1190 ptr
->index
, INDEX_EDGE (edge_list
, x
)->src
->index
,
1191 INDEX_EDGE (edge_list
, x
)->dest
->index
);
1195 /* Now we want to insert the new stores which are going to be needed. */
1197 FOR_EACH_BB_FN (bb
, cfun
)
1198 if (bitmap_bit_p (st_delete_map
[bb
->index
], ptr
->index
))
1200 delete_store (ptr
, bb
);
1204 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
1205 if (bitmap_bit_p (st_insert_map
[x
], ptr
->index
))
1207 did_edge_inserts
|= insert_store (ptr
, INDEX_EDGE (edge_list
, x
));
1212 if (did_edge_inserts
)
1213 commit_edge_insertions ();
1215 free_store_memory ();
1216 free_edge_list (edge_list
);
1217 remove_fake_exit_edges ();
1218 end_alias_analysis ();
1222 fprintf (dump_file
, "STORE_MOTION of %s, %d basic blocks, ",
1223 current_function_name (), n_basic_blocks_for_fn (cfun
));
1224 fprintf (dump_file
, "%d insns deleted, %d insns created\n",
1225 n_stores_deleted
, n_stores_created
);
1228 return (n_stores_deleted
> 0 || n_stores_created
> 0);
1233 execute_rtl_store_motion (void)
1235 delete_unreachable_blocks ();
1237 flag_rerun_cse_after_global_opts
|= one_store_motion_pass ();
1243 const pass_data pass_data_rtl_store_motion
=
1245 RTL_PASS
, /* type */
1246 "store_motion", /* name */
1247 OPTGROUP_NONE
, /* optinfo_flags */
1249 PROP_cfglayout
, /* properties_required */
1250 0, /* properties_provided */
1251 0, /* properties_destroyed */
1252 0, /* todo_flags_start */
1253 TODO_df_finish
, /* todo_flags_finish */
1256 class pass_rtl_store_motion
: public rtl_opt_pass
1259 pass_rtl_store_motion (gcc::context
*ctxt
)
1260 : rtl_opt_pass (pass_data_rtl_store_motion
, ctxt
)
1263 /* opt_pass methods: */
1264 virtual bool gate (function
*);
1265 virtual unsigned int execute (function
*)
1267 return execute_rtl_store_motion ();
1270 }; // class pass_rtl_store_motion
1273 pass_rtl_store_motion::gate (function
*fun
)
1275 return optimize
> 0 && flag_gcse_sm
1276 && !fun
->calls_setjmp
1277 && optimize_function_for_speed_p (fun
)
1278 && dbg_cnt (store_motion
);
1284 make_pass_rtl_store_motion (gcc::context
*ctxt
)
1286 return new pass_rtl_store_motion (ctxt
);