1 /* Store motion via Lazy Code Motion on the reverse CFG.
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
3 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
25 #include "diagnostic-core.h"
32 #include "hard-reg-set.h"
34 #include "insn-config.h"
36 #include "basic-block.h"
44 #include "tree-pass.h"
49 /* This pass implements downward store motion.
50 As of May 1, 2009, the pass is not enabled by default on any target,
51 but bootstrap completes on ia64 and x86_64 with the pass enabled. */
54 - remove_reachable_equiv_notes is an incomprehensible pile of goo and
55 a compile time hog that needs a rewrite (maybe cache st_exprs to
56 invalidate REG_EQUAL/REG_EQUIV notes for?).
57 - pattern_regs in st_expr should be a regset (on its own obstack).
58 - antic_stores and avail_stores should be VECs instead of lists.
59 - store_motion_mems should be a VEC instead of a list.
60 - there should be an alloc pool for struct st_expr objects.
61 - investigate whether it is helpful to make the address of an st_expr
63 - when GIMPLE alias information is exported, the effectiveness of this
64 pass should be re-evaluated.
67 /* This is a list of store expressions (MEMs). The structure is used
68 as an expression table to track stores which look interesting, and
69 might be moveable towards the exit block. */
73 /* Pattern of this mem. */
75 /* List of registers mentioned by the mem. */
77 /* INSN list of stores that are locally anticipatable. */
79 /* INSN list of stores that are locally available. */
81 /* Next in the list. */
82 struct st_expr
* next
;
83 /* Store ID in the dataflow bitmaps. */
85 /* Hash value for the hash table. */
86 unsigned int hash_index
;
87 /* Register holding the stored expression when a store is moved.
88 This field is also used as a cache in find_moveable_store, see
89 LAST_AVAIL_CHECK_FAILURE below. */
93 /* Head of the list of load/store memory refs. */
94 static struct st_expr
* store_motion_mems
= NULL
;
96 /* Hashtable for the load/store memory refs. */
97 static htab_t store_motion_mems_table
= NULL
;
99 /* These bitmaps will hold the local dataflow properties per basic block. */
100 static sbitmap
*st_kill
, *st_avloc
, *st_antloc
, *st_transp
;
102 /* Nonzero for expressions which should be inserted on a specific edge. */
103 static sbitmap
*st_insert_map
;
105 /* Nonzero for expressions which should be deleted in a specific block. */
106 static sbitmap
*st_delete_map
;
108 /* Global holding the number of store expressions we are dealing with. */
109 static int num_stores
;
111 /* Contains the edge_list returned by pre_edge_lcm. */
112 static struct edge_list
*edge_list
;
115 pre_st_expr_hash (const void *p
)
117 int do_not_record_p
= 0;
118 const struct st_expr
*const x
= (const struct st_expr
*) p
;
119 return hash_rtx (x
->pattern
, GET_MODE (x
->pattern
), &do_not_record_p
, NULL
, false);
123 pre_st_expr_eq (const void *p1
, const void *p2
)
125 const struct st_expr
*const ptr1
= (const struct st_expr
*) p1
,
126 *const ptr2
= (const struct st_expr
*) p2
;
127 return exp_equiv_p (ptr1
->pattern
, ptr2
->pattern
, 0, true);
130 /* This will search the st_expr list for a matching expression. If it
131 doesn't find one, we create one and initialize it. */
133 static struct st_expr
*
134 st_expr_entry (rtx x
)
136 int do_not_record_p
= 0;
137 struct st_expr
* ptr
;
142 hash
= hash_rtx (x
, GET_MODE (x
), &do_not_record_p
,
143 NULL
, /*have_reg_qty=*/false);
146 slot
= htab_find_slot_with_hash (store_motion_mems_table
, &e
, hash
, INSERT
);
148 return (struct st_expr
*)*slot
;
150 ptr
= XNEW (struct st_expr
);
152 ptr
->next
= store_motion_mems
;
154 ptr
->pattern_regs
= NULL_RTX
;
155 ptr
->antic_stores
= NULL_RTX
;
156 ptr
->avail_stores
= NULL_RTX
;
157 ptr
->reaching_reg
= NULL_RTX
;
159 ptr
->hash_index
= hash
;
160 store_motion_mems
= ptr
;
166 /* Free up an individual st_expr entry. */
169 free_st_expr_entry (struct st_expr
* ptr
)
171 free_INSN_LIST_list (& ptr
->antic_stores
);
172 free_INSN_LIST_list (& ptr
->avail_stores
);
177 /* Free up all memory associated with the st_expr list. */
180 free_store_motion_mems (void)
182 if (store_motion_mems_table
)
183 htab_delete (store_motion_mems_table
);
184 store_motion_mems_table
= NULL
;
186 while (store_motion_mems
)
188 struct st_expr
* tmp
= store_motion_mems
;
189 store_motion_mems
= store_motion_mems
->next
;
190 free_st_expr_entry (tmp
);
192 store_motion_mems
= NULL
;
195 /* Assign each element of the list of mems a monotonically increasing value. */
198 enumerate_store_motion_mems (void)
200 struct st_expr
* ptr
;
203 for (ptr
= store_motion_mems
; ptr
!= NULL
; ptr
= ptr
->next
)
209 /* Return first item in the list. */
211 static inline struct st_expr
*
214 return store_motion_mems
;
217 /* Return the next item in the list after the specified one. */
219 static inline struct st_expr
*
220 next_st_expr (struct st_expr
* ptr
)
225 /* Dump debugging info about the store_motion_mems list. */
228 print_store_motion_mems (FILE * file
)
230 struct st_expr
* ptr
;
232 fprintf (dump_file
, "STORE_MOTION list of MEM exprs considered:\n");
234 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
236 fprintf (file
, " Pattern (%3d): ", ptr
->index
);
238 print_rtl (file
, ptr
->pattern
);
240 fprintf (file
, "\n ANTIC stores : ");
242 if (ptr
->antic_stores
)
243 print_rtl (file
, ptr
->antic_stores
);
245 fprintf (file
, "(nil)");
247 fprintf (file
, "\n AVAIL stores : ");
249 if (ptr
->avail_stores
)
250 print_rtl (file
, ptr
->avail_stores
);
252 fprintf (file
, "(nil)");
254 fprintf (file
, "\n\n");
257 fprintf (file
, "\n");
260 /* Return zero if some of the registers in list X are killed
261 due to set of registers in bitmap REGS_SET. */
264 store_ops_ok (const_rtx x
, int *regs_set
)
268 for (; x
; x
= XEXP (x
, 1))
271 if (regs_set
[REGNO(reg
)])
278 /* Helper for extract_mentioned_regs. */
281 extract_mentioned_regs_1 (rtx
*loc
, void *data
)
283 rtx
*mentioned_regs_p
= (rtx
*) data
;
286 *mentioned_regs_p
= alloc_EXPR_LIST (0, *loc
, *mentioned_regs_p
);
291 /* Returns a list of registers mentioned in X.
292 FIXME: A regset would be prettier and less expensive. */
295 extract_mentioned_regs (rtx x
)
297 rtx mentioned_regs
= NULL
;
298 for_each_rtx (&x
, extract_mentioned_regs_1
, &mentioned_regs
);
299 return mentioned_regs
;
302 /* Check to see if the load X is aliased with STORE_PATTERN.
303 AFTER is true if we are checking the case when STORE_PATTERN occurs
307 load_kills_store (const_rtx x
, const_rtx store_pattern
, int after
)
310 return anti_dependence (x
, store_pattern
);
312 return true_dependence (store_pattern
, GET_MODE (store_pattern
), x
);
315 /* Go through the entire rtx X, looking for any loads which might alias
316 STORE_PATTERN. Return true if found.
317 AFTER is true if we are checking the case when STORE_PATTERN occurs
321 find_loads (const_rtx x
, const_rtx store_pattern
, int after
)
330 if (GET_CODE (x
) == SET
)
335 if (load_kills_store (x
, store_pattern
, after
))
339 /* Recursively process the insn. */
340 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
342 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0 && !ret
; i
--)
345 ret
|= find_loads (XEXP (x
, i
), store_pattern
, after
);
346 else if (fmt
[i
] == 'E')
347 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
348 ret
|= find_loads (XVECEXP (x
, i
, j
), store_pattern
, after
);
353 /* Go through pattern PAT looking for any loads which might kill the
354 store in X. Return true if found.
355 AFTER is true if we are checking the case when loads kill X occurs
356 after the insn for PAT. */
359 store_killed_in_pat (const_rtx x
, const_rtx pat
, int after
)
361 if (GET_CODE (pat
) == SET
)
363 rtx dest
= SET_DEST (pat
);
365 if (GET_CODE (dest
) == ZERO_EXTRACT
)
366 dest
= XEXP (dest
, 0);
368 /* Check for memory stores to aliased objects. */
370 && !exp_equiv_p (dest
, x
, 0, true))
374 if (output_dependence (dest
, x
))
379 if (output_dependence (x
, dest
))
385 if (find_loads (pat
, x
, after
))
391 /* Check if INSN kills the store pattern X (is aliased with it).
392 AFTER is true if we are checking the case when store X occurs
393 after the insn. Return true if it does. */
396 store_killed_in_insn (const_rtx x
, const_rtx x_regs
, const_rtx insn
, int after
)
398 const_rtx reg
, note
, pat
;
400 if (! NONDEBUG_INSN_P (insn
))
405 /* A normal or pure call might read from pattern,
406 but a const call will not. */
407 if (!RTL_CONST_CALL_P (insn
))
410 /* But even a const call reads its parameters. Check whether the
411 base of some of registers used in mem is stack pointer. */
412 for (reg
= x_regs
; reg
; reg
= XEXP (reg
, 1))
413 if (may_be_sp_based_p (XEXP (reg
, 0)))
419 pat
= PATTERN (insn
);
420 if (GET_CODE (pat
) == SET
)
422 if (store_killed_in_pat (x
, pat
, after
))
425 else if (GET_CODE (pat
) == PARALLEL
)
429 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
430 if (store_killed_in_pat (x
, XVECEXP (pat
, 0, i
), after
))
433 else if (find_loads (PATTERN (insn
), x
, after
))
436 /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
437 location aliased with X, then this insn kills X. */
438 note
= find_reg_equal_equiv_note (insn
);
441 note
= XEXP (note
, 0);
443 /* However, if the note represents a must alias rather than a may
444 alias relationship, then it does not kill X. */
445 if (exp_equiv_p (note
, x
, 0, true))
448 /* See if there are any aliased loads in the note. */
449 return find_loads (note
, x
, after
);
452 /* Returns true if the expression X is loaded or clobbered on or after INSN
453 within basic block BB. REGS_SET_AFTER is bitmap of registers set in
454 or after the insn. X_REGS is list of registers mentioned in X. If the store
455 is killed, return the last insn in that it occurs in FAIL_INSN. */
458 store_killed_after (const_rtx x
, const_rtx x_regs
, const_rtx insn
, const_basic_block bb
,
459 int *regs_set_after
, rtx
*fail_insn
)
461 rtx last
= BB_END (bb
), act
;
463 if (!store_ops_ok (x_regs
, regs_set_after
))
465 /* We do not know where it will happen. */
467 *fail_insn
= NULL_RTX
;
471 /* Scan from the end, so that fail_insn is determined correctly. */
472 for (act
= last
; act
!= PREV_INSN (insn
); act
= PREV_INSN (act
))
473 if (store_killed_in_insn (x
, x_regs
, act
, false))
483 /* Returns true if the expression X is loaded or clobbered on or before INSN
484 within basic block BB. X_REGS is list of registers mentioned in X.
485 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
487 store_killed_before (const_rtx x
, const_rtx x_regs
, const_rtx insn
, const_basic_block bb
,
488 int *regs_set_before
)
490 rtx first
= BB_HEAD (bb
);
492 if (!store_ops_ok (x_regs
, regs_set_before
))
495 for ( ; insn
!= PREV_INSN (first
); insn
= PREV_INSN (insn
))
496 if (store_killed_in_insn (x
, x_regs
, insn
, true))
502 /* The last insn in the basic block that compute_store_table is processing,
503 where store_killed_after is true for X.
504 Since we go through the basic block from BB_END to BB_HEAD, this is
505 also the available store at the end of the basic block. Therefore
506 this is in effect a cache, to avoid calling store_killed_after for
507 equivalent aliasing store expressions.
508 This value is only meaningful during the computation of the store
509 table. We hi-jack the REACHING_REG field of struct st_expr to save
511 #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
513 /* Determine whether INSN is MEM store pattern that we will consider moving.
514 REGS_SET_BEFORE is bitmap of registers set before (and including) the
515 current insn, REGS_SET_AFTER is bitmap of registers set after (and
516 including) the insn in this basic block. We must be passing through BB from
517 head to end, as we are using this fact to speed things up.
519 The results are stored this way:
521 -- the first anticipatable expression is added into ANTIC_STORES
522 -- if the processed expression is not anticipatable, NULL_RTX is added
523 there instead, so that we can use it as indicator that no further
524 expression of this type may be anticipatable
525 -- if the expression is available, it is added as head of AVAIL_STORES;
526 consequently, all of them but this head are dead and may be deleted.
527 -- if the expression is not available, the insn due to that it fails to be
528 available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
530 The things are complicated a bit by fact that there already may be stores
531 to the same MEM from other blocks; also caller must take care of the
532 necessary cleanup of the temporary markers after end of the basic block.
536 find_moveable_store (rtx insn
, int *regs_set_before
, int *regs_set_after
)
538 struct st_expr
* ptr
;
540 int check_anticipatable
, check_available
;
541 basic_block bb
= BLOCK_FOR_INSN (insn
);
543 set
= single_set (insn
);
547 dest
= SET_DEST (set
);
549 if (! MEM_P (dest
) || MEM_VOLATILE_P (dest
)
550 || GET_MODE (dest
) == BLKmode
)
553 if (side_effects_p (dest
))
556 /* If we are handling exceptions, we must be careful with memory references
557 that may trap. If we are not, the behavior is undefined, so we may just
559 if (cfun
->can_throw_non_call_exceptions
&& may_trap_p (dest
))
562 /* Even if the destination cannot trap, the source may. In this case we'd
563 need to handle updating the REG_EH_REGION note. */
564 if (find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
))
567 /* Make sure that the SET_SRC of this store insns can be assigned to
568 a register, or we will fail later on in replace_store_insn, which
569 assumes that we can do this. But sometimes the target machine has
570 oddities like MEM read-modify-write instruction. See for example
572 if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set
)))
575 ptr
= st_expr_entry (dest
);
576 if (!ptr
->pattern_regs
)
577 ptr
->pattern_regs
= extract_mentioned_regs (dest
);
579 /* Do not check for anticipatability if we either found one anticipatable
580 store already, or tested for one and found out that it was killed. */
581 check_anticipatable
= 0;
582 if (!ptr
->antic_stores
)
583 check_anticipatable
= 1;
586 tmp
= XEXP (ptr
->antic_stores
, 0);
588 && BLOCK_FOR_INSN (tmp
) != bb
)
589 check_anticipatable
= 1;
591 if (check_anticipatable
)
593 if (store_killed_before (dest
, ptr
->pattern_regs
, insn
, bb
, regs_set_before
))
597 ptr
->antic_stores
= alloc_INSN_LIST (tmp
, ptr
->antic_stores
);
600 /* It is not necessary to check whether store is available if we did
601 it successfully before; if we failed before, do not bother to check
602 until we reach the insn that caused us to fail. */
604 if (!ptr
->avail_stores
)
608 tmp
= XEXP (ptr
->avail_stores
, 0);
609 if (BLOCK_FOR_INSN (tmp
) != bb
)
614 /* Check that we have already reached the insn at that the check
616 if (LAST_AVAIL_CHECK_FAILURE (ptr
))
618 for (tmp
= BB_END (bb
);
619 tmp
!= insn
&& tmp
!= LAST_AVAIL_CHECK_FAILURE (ptr
);
620 tmp
= PREV_INSN (tmp
))
626 check_available
= store_killed_after (dest
, ptr
->pattern_regs
, insn
,
628 &LAST_AVAIL_CHECK_FAILURE (ptr
));
630 if (!check_available
)
631 ptr
->avail_stores
= alloc_INSN_LIST (insn
, ptr
->avail_stores
);
634 /* Find available and anticipatable stores. */
637 compute_store_table (void)
641 #ifdef ENABLE_CHECKING
646 int *last_set_in
, *already_set
;
647 struct st_expr
* ptr
, **prev_next_ptr_ptr
;
648 unsigned int max_gcse_regno
= max_reg_num ();
650 store_motion_mems
= NULL
;
651 store_motion_mems_table
= htab_create (13, pre_st_expr_hash
,
652 pre_st_expr_eq
, NULL
);
653 last_set_in
= XCNEWVEC (int, max_gcse_regno
);
654 already_set
= XNEWVEC (int, max_gcse_regno
);
656 /* Find all the stores we care about. */
659 /* First compute the registers set in this block. */
660 FOR_BB_INSNS (bb
, insn
)
663 if (! NONDEBUG_INSN_P (insn
))
666 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
667 last_set_in
[DF_REF_REGNO (*def_rec
)] = INSN_UID (insn
);
670 /* Now find the stores. */
671 memset (already_set
, 0, sizeof (int) * max_gcse_regno
);
672 FOR_BB_INSNS (bb
, insn
)
674 if (! NONDEBUG_INSN_P (insn
))
677 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
678 already_set
[DF_REF_REGNO (*def_rec
)] = INSN_UID (insn
);
680 /* Now that we've marked regs, look for stores. */
681 find_moveable_store (insn
, already_set
, last_set_in
);
683 /* Unmark regs that are no longer set. */
684 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
685 if (last_set_in
[DF_REF_REGNO (*def_rec
)] == INSN_UID (insn
))
686 last_set_in
[DF_REF_REGNO (*def_rec
)] = 0;
689 #ifdef ENABLE_CHECKING
690 /* last_set_in should now be all-zero. */
691 for (regno
= 0; regno
< max_gcse_regno
; regno
++)
692 gcc_assert (!last_set_in
[regno
]);
695 /* Clear temporary marks. */
696 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
698 LAST_AVAIL_CHECK_FAILURE (ptr
) = NULL_RTX
;
699 if (ptr
->antic_stores
700 && (tmp
= XEXP (ptr
->antic_stores
, 0)) == NULL_RTX
)
701 ptr
->antic_stores
= XEXP (ptr
->antic_stores
, 1);
705 /* Remove the stores that are not available anywhere, as there will
706 be no opportunity to optimize them. */
707 for (ptr
= store_motion_mems
, prev_next_ptr_ptr
= &store_motion_mems
;
709 ptr
= *prev_next_ptr_ptr
)
711 if (! ptr
->avail_stores
)
713 *prev_next_ptr_ptr
= ptr
->next
;
714 htab_remove_elt_with_hash (store_motion_mems_table
,
715 ptr
, ptr
->hash_index
);
716 free_st_expr_entry (ptr
);
719 prev_next_ptr_ptr
= &ptr
->next
;
722 ret
= enumerate_store_motion_mems ();
725 print_store_motion_mems (dump_file
);
732 /* In all code following after this, REACHING_REG has its original
733 meaning again. Avoid confusion, and undef the accessor macro for
734 the temporary marks usage in compute_store_table. */
735 #undef LAST_AVAIL_CHECK_FAILURE
737 /* Insert an instruction at the beginning of a basic block, and update
738 the BB_HEAD if needed. */
741 insert_insn_start_basic_block (rtx insn
, basic_block bb
)
743 /* Insert at start of successor block. */
744 rtx prev
= PREV_INSN (BB_HEAD (bb
));
745 rtx before
= BB_HEAD (bb
);
748 if (! LABEL_P (before
)
749 && !NOTE_INSN_BASIC_BLOCK_P (before
))
752 if (prev
== BB_END (bb
))
754 before
= NEXT_INSN (before
);
757 insn
= emit_insn_after_noloc (insn
, prev
, bb
);
761 fprintf (dump_file
, "STORE_MOTION insert store at start of BB %d:\n",
763 print_inline_rtx (dump_file
, insn
, 6);
764 fprintf (dump_file
, "\n");
768 /* This routine will insert a store on an edge. EXPR is the st_expr entry for
769 the memory reference, and E is the edge to insert it on. Returns nonzero
770 if an edge insertion was performed. */
773 insert_store (struct st_expr
* expr
, edge e
)
780 /* We did all the deleted before this insert, so if we didn't delete a
781 store, then we haven't set the reaching reg yet either. */
782 if (expr
->reaching_reg
== NULL_RTX
)
785 if (e
->flags
& EDGE_FAKE
)
788 reg
= expr
->reaching_reg
;
789 insn
= gen_move_insn (copy_rtx (expr
->pattern
), reg
);
791 /* If we are inserting this expression on ALL predecessor edges of a BB,
792 insert it at the start of the BB, and reset the insert bits on the other
793 edges so we don't try to insert it on the other edges. */
795 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
796 if (!(tmp
->flags
& EDGE_FAKE
))
798 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
800 gcc_assert (index
!= EDGE_INDEX_NO_EDGE
);
801 if (! TEST_BIT (st_insert_map
[index
], expr
->index
))
805 /* If tmp is NULL, we found an insertion on every edge, blank the
806 insertion vector for these edges, and insert at the start of the BB. */
807 if (!tmp
&& bb
!= EXIT_BLOCK_PTR
)
809 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
811 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
812 RESET_BIT (st_insert_map
[index
], expr
->index
);
814 insert_insn_start_basic_block (insn
, bb
);
818 /* We can't put stores in the front of blocks pointed to by abnormal
819 edges since that may put a store where one didn't used to be. */
820 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
822 insert_insn_on_edge (insn
, e
);
826 fprintf (dump_file
, "STORE_MOTION insert insn on edge (%d, %d):\n",
827 e
->src
->index
, e
->dest
->index
);
828 print_inline_rtx (dump_file
, insn
, 6);
829 fprintf (dump_file
, "\n");
835 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
836 memory location in SMEXPR set in basic block BB.
838 This could be rather expensive. */
841 remove_reachable_equiv_notes (basic_block bb
, struct st_expr
*smexpr
)
843 edge_iterator
*stack
, ei
;
846 sbitmap visited
= sbitmap_alloc (last_basic_block
);
847 rtx last
, insn
, note
;
848 rtx mem
= smexpr
->pattern
;
850 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
);
852 ei
= ei_start (bb
->succs
);
854 sbitmap_zero (visited
);
856 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
864 sbitmap_free (visited
);
867 act
= ei_edge (stack
[--sp
]);
871 if (bb
== EXIT_BLOCK_PTR
872 || TEST_BIT (visited
, bb
->index
))
876 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
879 SET_BIT (visited
, bb
->index
);
881 if (TEST_BIT (st_antloc
[bb
->index
], smexpr
->index
))
883 for (last
= smexpr
->antic_stores
;
884 BLOCK_FOR_INSN (XEXP (last
, 0)) != bb
;
885 last
= XEXP (last
, 1))
887 last
= XEXP (last
, 0);
890 last
= NEXT_INSN (BB_END (bb
));
892 for (insn
= BB_HEAD (bb
); insn
!= last
; insn
= NEXT_INSN (insn
))
893 if (NONDEBUG_INSN_P (insn
))
895 note
= find_reg_equal_equiv_note (insn
);
896 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
900 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
902 remove_note (insn
, note
);
907 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
909 if (EDGE_COUNT (bb
->succs
) > 0)
913 ei
= ei_start (bb
->succs
);
914 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
919 /* This routine will replace a store with a SET to a specified register. */
922 replace_store_insn (rtx reg
, rtx del
, basic_block bb
, struct st_expr
*smexpr
)
924 rtx insn
, mem
, note
, set
, ptr
;
926 mem
= smexpr
->pattern
;
927 insn
= gen_move_insn (reg
, SET_SRC (single_set (del
)));
929 for (ptr
= smexpr
->antic_stores
; ptr
; ptr
= XEXP (ptr
, 1))
930 if (XEXP (ptr
, 0) == del
)
932 XEXP (ptr
, 0) = insn
;
936 /* Move the notes from the deleted insn to its replacement. */
937 REG_NOTES (insn
) = REG_NOTES (del
);
939 /* Emit the insn AFTER all the notes are transferred.
940 This is cheaper since we avoid df rescanning for the note change. */
941 insn
= emit_insn_after (insn
, del
);
946 "STORE_MOTION delete insn in BB %d:\n ", bb
->index
);
947 print_inline_rtx (dump_file
, del
, 6);
948 fprintf (dump_file
, "\nSTORE_MOTION replaced with insn:\n ");
949 print_inline_rtx (dump_file
, insn
, 6);
950 fprintf (dump_file
, "\n");
955 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
956 they are no longer accurate provided that they are reached by this
957 definition, so drop them. */
958 for (; insn
!= NEXT_INSN (BB_END (bb
)); insn
= NEXT_INSN (insn
))
959 if (NONDEBUG_INSN_P (insn
))
961 set
= single_set (insn
);
964 if (exp_equiv_p (SET_DEST (set
), mem
, 0, true))
966 note
= find_reg_equal_equiv_note (insn
);
967 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
971 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
973 remove_note (insn
, note
);
975 remove_reachable_equiv_notes (bb
, smexpr
);
979 /* Delete a store, but copy the value that would have been stored into
980 the reaching_reg for later storing. */
983 delete_store (struct st_expr
* expr
, basic_block bb
)
987 if (expr
->reaching_reg
== NULL_RTX
)
988 expr
->reaching_reg
= gen_reg_rtx_and_attrs (expr
->pattern
);
990 reg
= expr
->reaching_reg
;
992 for (i
= expr
->avail_stores
; i
; i
= XEXP (i
, 1))
995 if (BLOCK_FOR_INSN (del
) == bb
)
997 /* We know there is only one since we deleted redundant
998 ones during the available computation. */
999 replace_store_insn (reg
, del
, bb
, expr
);
1005 /* Fill in available, anticipatable, transparent and kill vectors in
1006 STORE_DATA, based on lists of available and anticipatable stores. */
1008 build_store_vectors (void)
1011 int *regs_set_in_block
;
1013 struct st_expr
* ptr
;
1014 unsigned int max_gcse_regno
= max_reg_num ();
1016 /* Build the gen_vector. This is any store in the table which is not killed
1017 by aliasing later in its block. */
1018 st_avloc
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
1019 sbitmap_vector_zero (st_avloc
, last_basic_block
);
1021 st_antloc
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
1022 sbitmap_vector_zero (st_antloc
, last_basic_block
);
1024 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1026 for (st
= ptr
->avail_stores
; st
!= NULL
; st
= XEXP (st
, 1))
1028 insn
= XEXP (st
, 0);
1029 bb
= BLOCK_FOR_INSN (insn
);
1031 /* If we've already seen an available expression in this block,
1032 we can delete this one (It occurs earlier in the block). We'll
1033 copy the SRC expression to an unused register in case there
1034 are any side effects. */
1035 if (TEST_BIT (st_avloc
[bb
->index
], ptr
->index
))
1037 rtx r
= gen_reg_rtx_and_attrs (ptr
->pattern
);
1039 fprintf (dump_file
, "Removing redundant store:\n");
1040 replace_store_insn (r
, XEXP (st
, 0), bb
, ptr
);
1043 SET_BIT (st_avloc
[bb
->index
], ptr
->index
);
1046 for (st
= ptr
->antic_stores
; st
!= NULL
; st
= XEXP (st
, 1))
1048 insn
= XEXP (st
, 0);
1049 bb
= BLOCK_FOR_INSN (insn
);
1050 SET_BIT (st_antloc
[bb
->index
], ptr
->index
);
1054 st_kill
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
1055 sbitmap_vector_zero (st_kill
, last_basic_block
);
1057 st_transp
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
1058 sbitmap_vector_zero (st_transp
, last_basic_block
);
1059 regs_set_in_block
= XNEWVEC (int, max_gcse_regno
);
1063 memset (regs_set_in_block
, 0, sizeof (int) * max_gcse_regno
);
1065 FOR_BB_INSNS (bb
, insn
)
1066 if (NONDEBUG_INSN_P (insn
))
1069 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
1071 unsigned int ref_regno
= DF_REF_REGNO (*def_rec
);
1072 if (ref_regno
< max_gcse_regno
)
1073 regs_set_in_block
[DF_REF_REGNO (*def_rec
)] = 1;
1077 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1079 if (store_killed_after (ptr
->pattern
, ptr
->pattern_regs
, BB_HEAD (bb
),
1080 bb
, regs_set_in_block
, NULL
))
1082 /* It should not be necessary to consider the expression
1083 killed if it is both anticipatable and available. */
1084 if (!TEST_BIT (st_antloc
[bb
->index
], ptr
->index
)
1085 || !TEST_BIT (st_avloc
[bb
->index
], ptr
->index
))
1086 SET_BIT (st_kill
[bb
->index
], ptr
->index
);
1089 SET_BIT (st_transp
[bb
->index
], ptr
->index
);
1093 free (regs_set_in_block
);
1097 dump_sbitmap_vector (dump_file
, "st_antloc", "", st_antloc
, last_basic_block
);
1098 dump_sbitmap_vector (dump_file
, "st_kill", "", st_kill
, last_basic_block
);
1099 dump_sbitmap_vector (dump_file
, "st_transp", "", st_transp
, last_basic_block
);
1100 dump_sbitmap_vector (dump_file
, "st_avloc", "", st_avloc
, last_basic_block
);
1104 /* Free memory used by store motion. */
1107 free_store_memory (void)
1109 free_store_motion_mems ();
1112 sbitmap_vector_free (st_avloc
);
1114 sbitmap_vector_free (st_kill
);
1116 sbitmap_vector_free (st_transp
);
1118 sbitmap_vector_free (st_antloc
);
1120 sbitmap_vector_free (st_insert_map
);
1122 sbitmap_vector_free (st_delete_map
);
1124 st_avloc
= st_kill
= st_transp
= st_antloc
= NULL
;
1125 st_insert_map
= st_delete_map
= NULL
;
1128 /* Perform store motion. Much like gcse, except we move expressions the
1129 other way by looking at the flowgraph in reverse.
1130 Return non-zero if transformations are performed by the pass. */
1133 one_store_motion_pass (void)
1137 struct st_expr
* ptr
;
1138 int did_edge_inserts
= 0;
1139 int n_stores_deleted
= 0;
1140 int n_stores_created
= 0;
1142 init_alias_analysis ();
1144 /* Find all the available and anticipatable stores. */
1145 num_stores
= compute_store_table ();
1146 if (num_stores
== 0)
1148 htab_delete (store_motion_mems_table
);
1149 store_motion_mems_table
= NULL
;
1150 end_alias_analysis ();
1154 /* Now compute kill & transp vectors. */
1155 build_store_vectors ();
1156 add_noreturn_fake_exit_edges ();
1157 connect_infinite_loops_to_exit ();
1159 edge_list
= pre_edge_rev_lcm (num_stores
, st_transp
, st_avloc
,
1160 st_antloc
, st_kill
, &st_insert_map
,
1163 /* Now we want to insert the new stores which are going to be needed. */
1164 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1166 /* If any of the edges we have above are abnormal, we can't move this
1168 for (x
= NUM_EDGES (edge_list
) - 1; x
>= 0; x
--)
1169 if (TEST_BIT (st_insert_map
[x
], ptr
->index
)
1170 && (INDEX_EDGE (edge_list
, x
)->flags
& EDGE_ABNORMAL
))
1175 if (dump_file
!= NULL
)
1177 "Can't replace store %d: abnormal edge from %d to %d\n",
1178 ptr
->index
, INDEX_EDGE (edge_list
, x
)->src
->index
,
1179 INDEX_EDGE (edge_list
, x
)->dest
->index
);
1183 /* Now we want to insert the new stores which are going to be needed. */
1186 if (TEST_BIT (st_delete_map
[bb
->index
], ptr
->index
))
1188 delete_store (ptr
, bb
);
1192 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
1193 if (TEST_BIT (st_insert_map
[x
], ptr
->index
))
1195 did_edge_inserts
|= insert_store (ptr
, INDEX_EDGE (edge_list
, x
));
1200 if (did_edge_inserts
)
1201 commit_edge_insertions ();
1203 free_store_memory ();
1204 free_edge_list (edge_list
);
1205 remove_fake_exit_edges ();
1206 end_alias_analysis ();
1210 fprintf (dump_file
, "STORE_MOTION of %s, %d basic blocks, ",
1211 current_function_name (), n_basic_blocks
);
1212 fprintf (dump_file
, "%d insns deleted, %d insns created\n",
1213 n_stores_deleted
, n_stores_created
);
1216 return (n_stores_deleted
> 0 || n_stores_created
> 0);
1221 gate_rtl_store_motion (void)
1223 return optimize
> 0 && flag_gcse_sm
1224 && !cfun
->calls_setjmp
1225 && optimize_function_for_speed_p (cfun
)
1226 && dbg_cnt (store_motion
);
1230 execute_rtl_store_motion (void)
1232 delete_unreachable_blocks ();
1234 flag_rerun_cse_after_global_opts
|= one_store_motion_pass ();
1238 struct rtl_opt_pass pass_rtl_store_motion
=
1242 "store_motion", /* name */
1243 gate_rtl_store_motion
, /* gate */
1244 execute_rtl_store_motion
, /* execute */
1247 0, /* static_pass_number */
1249 PROP_cfglayout
, /* properties_required */
1250 0, /* properties_provided */
1251 0, /* properties_destroyed */
1252 0, /* todo_flags_start */
1253 TODO_df_finish
| TODO_verify_rtl_sharing
|
1254 TODO_verify_flow
| TODO_ggc_collect
/* todo_flags_finish */