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"
43 #include "tree-pass.h"
48 /* This pass implements downward store motion.
49 As of May 1, 2009, the pass is not enabled by default on any target,
50 but bootstrap completes on ia64 and x86_64 with the pass enabled. */
53 - remove_reachable_equiv_notes is an incomprehensible pile of goo and
54 a compile time hog that needs a rewrite (maybe cache st_exprs to
55 invalidate REG_EQUAL/REG_EQUIV notes for?).
56 - pattern_regs in st_expr should be a regset (on its own obstack).
57 - antic_stores and avail_stores should be VECs instead of lists.
58 - store_motion_mems should be a VEC instead of a list.
59 - there should be an alloc pool for struct st_expr objects.
60 - investigate whether it is helpful to make the address of an st_expr
62 - when GIMPLE alias information is exported, the effectiveness of this
63 pass should be re-evaluated.
66 /* This is a list of store expressions (MEMs). The structure is used
67 as an expression table to track stores which look interesting, and
68 might be moveable towards the exit block. */
72 /* Pattern of this mem. */
74 /* List of registers mentioned by the mem. */
76 /* INSN list of stores that are locally anticipatable. */
78 /* INSN list of stores that are locally available. */
80 /* Next in the list. */
81 struct st_expr
* next
;
82 /* Store ID in the dataflow bitmaps. */
84 /* Hash value for the hash table. */
85 unsigned int hash_index
;
86 /* Register holding the stored expression when a store is moved.
87 This field is also used as a cache in find_moveable_store, see
88 LAST_AVAIL_CHECK_FAILURE below. */
92 /* Head of the list of load/store memory refs. */
93 static struct st_expr
* store_motion_mems
= NULL
;
95 /* Hashtable for the load/store memory refs. */
96 static htab_t store_motion_mems_table
= NULL
;
98 /* These bitmaps will hold the local dataflow properties per basic block. */
99 static sbitmap
*st_kill
, *st_avloc
, *st_antloc
, *st_transp
;
101 /* Nonzero for expressions which should be inserted on a specific edge. */
102 static sbitmap
*st_insert_map
;
104 /* Nonzero for expressions which should be deleted in a specific block. */
105 static sbitmap
*st_delete_map
;
107 /* Global holding the number of store expressions we are dealing with. */
108 static int num_stores
;
110 /* Contains the edge_list returned by pre_edge_lcm. */
111 static struct edge_list
*edge_list
;
114 pre_st_expr_hash (const void *p
)
116 int do_not_record_p
= 0;
117 const struct st_expr
*const x
= (const struct st_expr
*) p
;
118 return hash_rtx (x
->pattern
, GET_MODE (x
->pattern
), &do_not_record_p
, NULL
, false);
122 pre_st_expr_eq (const void *p1
, const void *p2
)
124 const struct st_expr
*const ptr1
= (const struct st_expr
*) p1
,
125 *const ptr2
= (const struct st_expr
*) p2
;
126 return exp_equiv_p (ptr1
->pattern
, ptr2
->pattern
, 0, true);
129 /* This will search the st_expr list for a matching expression. If it
130 doesn't find one, we create one and initialize it. */
132 static struct st_expr
*
133 st_expr_entry (rtx x
)
135 int do_not_record_p
= 0;
136 struct st_expr
* ptr
;
141 hash
= hash_rtx (x
, GET_MODE (x
), &do_not_record_p
,
142 NULL
, /*have_reg_qty=*/false);
145 slot
= htab_find_slot_with_hash (store_motion_mems_table
, &e
, hash
, INSERT
);
147 return (struct st_expr
*)*slot
;
149 ptr
= XNEW (struct st_expr
);
151 ptr
->next
= store_motion_mems
;
153 ptr
->pattern_regs
= NULL_RTX
;
154 ptr
->antic_stores
= NULL_RTX
;
155 ptr
->avail_stores
= NULL_RTX
;
156 ptr
->reaching_reg
= NULL_RTX
;
158 ptr
->hash_index
= hash
;
159 store_motion_mems
= ptr
;
165 /* Free up an individual st_expr entry. */
168 free_st_expr_entry (struct st_expr
* ptr
)
170 free_INSN_LIST_list (& ptr
->antic_stores
);
171 free_INSN_LIST_list (& ptr
->avail_stores
);
176 /* Free up all memory associated with the st_expr list. */
179 free_store_motion_mems (void)
181 if (store_motion_mems_table
)
182 htab_delete (store_motion_mems_table
);
183 store_motion_mems_table
= NULL
;
185 while (store_motion_mems
)
187 struct st_expr
* tmp
= store_motion_mems
;
188 store_motion_mems
= store_motion_mems
->next
;
189 free_st_expr_entry (tmp
);
191 store_motion_mems
= NULL
;
194 /* Assign each element of the list of mems a monotonically increasing value. */
197 enumerate_store_motion_mems (void)
199 struct st_expr
* ptr
;
202 for (ptr
= store_motion_mems
; ptr
!= NULL
; ptr
= ptr
->next
)
208 /* Return first item in the list. */
210 static inline struct st_expr
*
213 return store_motion_mems
;
216 /* Return the next item in the list after the specified one. */
218 static inline struct st_expr
*
219 next_st_expr (struct st_expr
* ptr
)
224 /* Dump debugging info about the store_motion_mems list. */
227 print_store_motion_mems (FILE * file
)
229 struct st_expr
* ptr
;
231 fprintf (dump_file
, "STORE_MOTION list of MEM exprs considered:\n");
233 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
235 fprintf (file
, " Pattern (%3d): ", ptr
->index
);
237 print_rtl (file
, ptr
->pattern
);
239 fprintf (file
, "\n ANTIC stores : ");
241 if (ptr
->antic_stores
)
242 print_rtl (file
, ptr
->antic_stores
);
244 fprintf (file
, "(nil)");
246 fprintf (file
, "\n AVAIL stores : ");
248 if (ptr
->avail_stores
)
249 print_rtl (file
, ptr
->avail_stores
);
251 fprintf (file
, "(nil)");
253 fprintf (file
, "\n\n");
256 fprintf (file
, "\n");
259 /* Return zero if some of the registers in list X are killed
260 due to set of registers in bitmap REGS_SET. */
263 store_ops_ok (const_rtx x
, int *regs_set
)
267 for (; x
; x
= XEXP (x
, 1))
270 if (regs_set
[REGNO(reg
)])
277 /* Helper for extract_mentioned_regs. */
280 extract_mentioned_regs_1 (rtx
*loc
, void *data
)
282 rtx
*mentioned_regs_p
= (rtx
*) data
;
285 *mentioned_regs_p
= alloc_EXPR_LIST (0, *loc
, *mentioned_regs_p
);
290 /* Returns a list of registers mentioned in X.
291 FIXME: A regset would be prettier and less expensive. */
294 extract_mentioned_regs (rtx x
)
296 rtx mentioned_regs
= NULL
;
297 for_each_rtx (&x
, extract_mentioned_regs_1
, &mentioned_regs
);
298 return mentioned_regs
;
301 /* Check to see if the load X is aliased with STORE_PATTERN.
302 AFTER is true if we are checking the case when STORE_PATTERN occurs
306 load_kills_store (const_rtx x
, const_rtx store_pattern
, int after
)
309 return anti_dependence (x
, store_pattern
);
311 return true_dependence (store_pattern
, GET_MODE (store_pattern
), x
);
314 /* Go through the entire rtx X, looking for any loads which might alias
315 STORE_PATTERN. Return true if found.
316 AFTER is true if we are checking the case when STORE_PATTERN occurs
320 find_loads (const_rtx x
, const_rtx store_pattern
, int after
)
329 if (GET_CODE (x
) == SET
)
334 if (load_kills_store (x
, store_pattern
, after
))
338 /* Recursively process the insn. */
339 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
341 for (i
= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
>= 0 && !ret
; i
--)
344 ret
|= find_loads (XEXP (x
, i
), store_pattern
, after
);
345 else if (fmt
[i
] == 'E')
346 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
347 ret
|= find_loads (XVECEXP (x
, i
, j
), store_pattern
, after
);
352 /* Go through pattern PAT looking for any loads which might kill the
353 store in X. Return true if found.
354 AFTER is true if we are checking the case when loads kill X occurs
355 after the insn for PAT. */
358 store_killed_in_pat (const_rtx x
, const_rtx pat
, int after
)
360 if (GET_CODE (pat
) == SET
)
362 rtx dest
= SET_DEST (pat
);
364 if (GET_CODE (dest
) == ZERO_EXTRACT
)
365 dest
= XEXP (dest
, 0);
367 /* Check for memory stores to aliased objects. */
369 && !exp_equiv_p (dest
, x
, 0, true))
373 if (output_dependence (dest
, x
))
378 if (output_dependence (x
, dest
))
384 if (find_loads (pat
, x
, after
))
390 /* Check if INSN kills the store pattern X (is aliased with it).
391 AFTER is true if we are checking the case when store X occurs
392 after the insn. Return true if it does. */
395 store_killed_in_insn (const_rtx x
, const_rtx x_regs
, const_rtx insn
, int after
)
397 const_rtx reg
, note
, pat
;
399 if (! NONDEBUG_INSN_P (insn
))
404 /* A normal or pure call might read from pattern,
405 but a const call will not. */
406 if (!RTL_CONST_CALL_P (insn
))
409 /* But even a const call reads its parameters. Check whether the
410 base of some of registers used in mem is stack pointer. */
411 for (reg
= x_regs
; reg
; reg
= XEXP (reg
, 1))
412 if (may_be_sp_based_p (XEXP (reg
, 0)))
418 pat
= PATTERN (insn
);
419 if (GET_CODE (pat
) == SET
)
421 if (store_killed_in_pat (x
, pat
, after
))
424 else if (GET_CODE (pat
) == PARALLEL
)
428 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
429 if (store_killed_in_pat (x
, XVECEXP (pat
, 0, i
), after
))
432 else if (find_loads (PATTERN (insn
), x
, after
))
435 /* If this insn has a REG_EQUAL or REG_EQUIV note referencing a memory
436 location aliased with X, then this insn kills X. */
437 note
= find_reg_equal_equiv_note (insn
);
440 note
= XEXP (note
, 0);
442 /* However, if the note represents a must alias rather than a may
443 alias relationship, then it does not kill X. */
444 if (exp_equiv_p (note
, x
, 0, true))
447 /* See if there are any aliased loads in the note. */
448 return find_loads (note
, x
, after
);
451 /* Returns true if the expression X is loaded or clobbered on or after INSN
452 within basic block BB. REGS_SET_AFTER is bitmap of registers set in
453 or after the insn. X_REGS is list of registers mentioned in X. If the store
454 is killed, return the last insn in that it occurs in FAIL_INSN. */
457 store_killed_after (const_rtx x
, const_rtx x_regs
, const_rtx insn
, const_basic_block bb
,
458 int *regs_set_after
, rtx
*fail_insn
)
460 rtx last
= BB_END (bb
), act
;
462 if (!store_ops_ok (x_regs
, regs_set_after
))
464 /* We do not know where it will happen. */
466 *fail_insn
= NULL_RTX
;
470 /* Scan from the end, so that fail_insn is determined correctly. */
471 for (act
= last
; act
!= PREV_INSN (insn
); act
= PREV_INSN (act
))
472 if (store_killed_in_insn (x
, x_regs
, act
, false))
482 /* Returns true if the expression X is loaded or clobbered on or before INSN
483 within basic block BB. X_REGS is list of registers mentioned in X.
484 REGS_SET_BEFORE is bitmap of registers set before or in this insn. */
486 store_killed_before (const_rtx x
, const_rtx x_regs
, const_rtx insn
, const_basic_block bb
,
487 int *regs_set_before
)
489 rtx first
= BB_HEAD (bb
);
491 if (!store_ops_ok (x_regs
, regs_set_before
))
494 for ( ; insn
!= PREV_INSN (first
); insn
= PREV_INSN (insn
))
495 if (store_killed_in_insn (x
, x_regs
, insn
, true))
501 /* The last insn in the basic block that compute_store_table is processing,
502 where store_killed_after is true for X.
503 Since we go through the basic block from BB_END to BB_HEAD, this is
504 also the available store at the end of the basic block. Therefore
505 this is in effect a cache, to avoid calling store_killed_after for
506 equivalent aliasing store expressions.
507 This value is only meaningful during the computation of the store
508 table. We hi-jack the REACHING_REG field of struct st_expr to save
510 #define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
512 /* Determine whether INSN is MEM store pattern that we will consider moving.
513 REGS_SET_BEFORE is bitmap of registers set before (and including) the
514 current insn, REGS_SET_AFTER is bitmap of registers set after (and
515 including) the insn in this basic block. We must be passing through BB from
516 head to end, as we are using this fact to speed things up.
518 The results are stored this way:
520 -- the first anticipatable expression is added into ANTIC_STORES
521 -- if the processed expression is not anticipatable, NULL_RTX is added
522 there instead, so that we can use it as indicator that no further
523 expression of this type may be anticipatable
524 -- if the expression is available, it is added as head of AVAIL_STORES;
525 consequently, all of them but this head are dead and may be deleted.
526 -- if the expression is not available, the insn due to that it fails to be
527 available is stored in REACHING_REG (via LAST_AVAIL_CHECK_FAILURE).
529 The things are complicated a bit by fact that there already may be stores
530 to the same MEM from other blocks; also caller must take care of the
531 necessary cleanup of the temporary markers after end of the basic block.
535 find_moveable_store (rtx insn
, int *regs_set_before
, int *regs_set_after
)
537 struct st_expr
* ptr
;
539 int check_anticipatable
, check_available
;
540 basic_block bb
= BLOCK_FOR_INSN (insn
);
542 set
= single_set (insn
);
546 dest
= SET_DEST (set
);
548 if (! MEM_P (dest
) || MEM_VOLATILE_P (dest
)
549 || GET_MODE (dest
) == BLKmode
)
552 if (side_effects_p (dest
))
555 /* If we are handling exceptions, we must be careful with memory references
556 that may trap. If we are not, the behavior is undefined, so we may just
558 if (cfun
->can_throw_non_call_exceptions
&& may_trap_p (dest
))
561 /* Even if the destination cannot trap, the source may. In this case we'd
562 need to handle updating the REG_EH_REGION note. */
563 if (find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
))
566 /* Make sure that the SET_SRC of this store insns can be assigned to
567 a register, or we will fail later on in replace_store_insn, which
568 assumes that we can do this. But sometimes the target machine has
569 oddities like MEM read-modify-write instruction. See for example
571 if (!can_assign_to_reg_without_clobbers_p (SET_SRC (set
)))
574 ptr
= st_expr_entry (dest
);
575 if (!ptr
->pattern_regs
)
576 ptr
->pattern_regs
= extract_mentioned_regs (dest
);
578 /* Do not check for anticipatability if we either found one anticipatable
579 store already, or tested for one and found out that it was killed. */
580 check_anticipatable
= 0;
581 if (!ptr
->antic_stores
)
582 check_anticipatable
= 1;
585 tmp
= XEXP (ptr
->antic_stores
, 0);
587 && BLOCK_FOR_INSN (tmp
) != bb
)
588 check_anticipatable
= 1;
590 if (check_anticipatable
)
592 if (store_killed_before (dest
, ptr
->pattern_regs
, insn
, bb
, regs_set_before
))
596 ptr
->antic_stores
= alloc_INSN_LIST (tmp
, ptr
->antic_stores
);
599 /* It is not necessary to check whether store is available if we did
600 it successfully before; if we failed before, do not bother to check
601 until we reach the insn that caused us to fail. */
603 if (!ptr
->avail_stores
)
607 tmp
= XEXP (ptr
->avail_stores
, 0);
608 if (BLOCK_FOR_INSN (tmp
) != bb
)
613 /* Check that we have already reached the insn at that the check
615 if (LAST_AVAIL_CHECK_FAILURE (ptr
))
617 for (tmp
= BB_END (bb
);
618 tmp
!= insn
&& tmp
!= LAST_AVAIL_CHECK_FAILURE (ptr
);
619 tmp
= PREV_INSN (tmp
))
625 check_available
= store_killed_after (dest
, ptr
->pattern_regs
, insn
,
627 &LAST_AVAIL_CHECK_FAILURE (ptr
));
629 if (!check_available
)
630 ptr
->avail_stores
= alloc_INSN_LIST (insn
, ptr
->avail_stores
);
633 /* Find available and anticipatable stores. */
636 compute_store_table (void)
640 #ifdef ENABLE_CHECKING
645 int *last_set_in
, *already_set
;
646 struct st_expr
* ptr
, **prev_next_ptr_ptr
;
647 unsigned int max_gcse_regno
= max_reg_num ();
649 store_motion_mems
= NULL
;
650 store_motion_mems_table
= htab_create (13, pre_st_expr_hash
,
651 pre_st_expr_eq
, NULL
);
652 last_set_in
= XCNEWVEC (int, max_gcse_regno
);
653 already_set
= XNEWVEC (int, max_gcse_regno
);
655 /* Find all the stores we care about. */
658 /* First compute the registers set in this block. */
659 FOR_BB_INSNS (bb
, insn
)
662 if (! NONDEBUG_INSN_P (insn
))
665 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
666 last_set_in
[DF_REF_REGNO (*def_rec
)] = INSN_UID (insn
);
669 /* Now find the stores. */
670 memset (already_set
, 0, sizeof (int) * max_gcse_regno
);
671 FOR_BB_INSNS (bb
, insn
)
673 if (! NONDEBUG_INSN_P (insn
))
676 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
677 already_set
[DF_REF_REGNO (*def_rec
)] = INSN_UID (insn
);
679 /* Now that we've marked regs, look for stores. */
680 find_moveable_store (insn
, already_set
, last_set_in
);
682 /* Unmark regs that are no longer set. */
683 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
684 if (last_set_in
[DF_REF_REGNO (*def_rec
)] == INSN_UID (insn
))
685 last_set_in
[DF_REF_REGNO (*def_rec
)] = 0;
688 #ifdef ENABLE_CHECKING
689 /* last_set_in should now be all-zero. */
690 for (regno
= 0; regno
< max_gcse_regno
; regno
++)
691 gcc_assert (!last_set_in
[regno
]);
694 /* Clear temporary marks. */
695 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
697 LAST_AVAIL_CHECK_FAILURE (ptr
) = NULL_RTX
;
698 if (ptr
->antic_stores
699 && (tmp
= XEXP (ptr
->antic_stores
, 0)) == NULL_RTX
)
700 ptr
->antic_stores
= XEXP (ptr
->antic_stores
, 1);
704 /* Remove the stores that are not available anywhere, as there will
705 be no opportunity to optimize them. */
706 for (ptr
= store_motion_mems
, prev_next_ptr_ptr
= &store_motion_mems
;
708 ptr
= *prev_next_ptr_ptr
)
710 if (! ptr
->avail_stores
)
712 *prev_next_ptr_ptr
= ptr
->next
;
713 htab_remove_elt_with_hash (store_motion_mems_table
,
714 ptr
, ptr
->hash_index
);
715 free_st_expr_entry (ptr
);
718 prev_next_ptr_ptr
= &ptr
->next
;
721 ret
= enumerate_store_motion_mems ();
724 print_store_motion_mems (dump_file
);
731 /* In all code following after this, REACHING_REG has its original
732 meaning again. Avoid confusion, and undef the accessor macro for
733 the temporary marks usage in compute_store_table. */
734 #undef LAST_AVAIL_CHECK_FAILURE
736 /* Insert an instruction at the beginning of a basic block, and update
737 the BB_HEAD if needed. */
740 insert_insn_start_basic_block (rtx insn
, basic_block bb
)
742 /* Insert at start of successor block. */
743 rtx prev
= PREV_INSN (BB_HEAD (bb
));
744 rtx before
= BB_HEAD (bb
);
747 if (! LABEL_P (before
)
748 && !NOTE_INSN_BASIC_BLOCK_P (before
))
751 if (prev
== BB_END (bb
))
753 before
= NEXT_INSN (before
);
756 insn
= emit_insn_after_noloc (insn
, prev
, bb
);
760 fprintf (dump_file
, "STORE_MOTION insert store at start of BB %d:\n",
762 print_inline_rtx (dump_file
, insn
, 6);
763 fprintf (dump_file
, "\n");
767 /* This routine will insert a store on an edge. EXPR is the st_expr entry for
768 the memory reference, and E is the edge to insert it on. Returns nonzero
769 if an edge insertion was performed. */
772 insert_store (struct st_expr
* expr
, edge e
)
779 /* We did all the deleted before this insert, so if we didn't delete a
780 store, then we haven't set the reaching reg yet either. */
781 if (expr
->reaching_reg
== NULL_RTX
)
784 if (e
->flags
& EDGE_FAKE
)
787 reg
= expr
->reaching_reg
;
788 insn
= gen_move_insn (copy_rtx (expr
->pattern
), reg
);
790 /* If we are inserting this expression on ALL predecessor edges of a BB,
791 insert it at the start of the BB, and reset the insert bits on the other
792 edges so we don't try to insert it on the other edges. */
794 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
795 if (!(tmp
->flags
& EDGE_FAKE
))
797 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
799 gcc_assert (index
!= EDGE_INDEX_NO_EDGE
);
800 if (! TEST_BIT (st_insert_map
[index
], expr
->index
))
804 /* If tmp is NULL, we found an insertion on every edge, blank the
805 insertion vector for these edges, and insert at the start of the BB. */
806 if (!tmp
&& bb
!= EXIT_BLOCK_PTR
)
808 FOR_EACH_EDGE (tmp
, ei
, e
->dest
->preds
)
810 int index
= EDGE_INDEX (edge_list
, tmp
->src
, tmp
->dest
);
811 RESET_BIT (st_insert_map
[index
], expr
->index
);
813 insert_insn_start_basic_block (insn
, bb
);
817 /* We can't put stores in the front of blocks pointed to by abnormal
818 edges since that may put a store where one didn't used to be. */
819 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
821 insert_insn_on_edge (insn
, e
);
825 fprintf (dump_file
, "STORE_MOTION insert insn on edge (%d, %d):\n",
826 e
->src
->index
, e
->dest
->index
);
827 print_inline_rtx (dump_file
, insn
, 6);
828 fprintf (dump_file
, "\n");
834 /* Remove any REG_EQUAL or REG_EQUIV notes containing a reference to the
835 memory location in SMEXPR set in basic block BB.
837 This could be rather expensive. */
840 remove_reachable_equiv_notes (basic_block bb
, struct st_expr
*smexpr
)
842 edge_iterator
*stack
, ei
;
845 sbitmap visited
= sbitmap_alloc (last_basic_block
);
846 rtx last
, insn
, note
;
847 rtx mem
= smexpr
->pattern
;
849 stack
= XNEWVEC (edge_iterator
, n_basic_blocks
);
851 ei
= ei_start (bb
->succs
);
853 sbitmap_zero (visited
);
855 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
863 sbitmap_free (visited
);
866 act
= ei_edge (stack
[--sp
]);
870 if (bb
== EXIT_BLOCK_PTR
871 || TEST_BIT (visited
, bb
->index
))
875 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
878 SET_BIT (visited
, bb
->index
);
880 if (TEST_BIT (st_antloc
[bb
->index
], smexpr
->index
))
882 for (last
= smexpr
->antic_stores
;
883 BLOCK_FOR_INSN (XEXP (last
, 0)) != bb
;
884 last
= XEXP (last
, 1))
886 last
= XEXP (last
, 0);
889 last
= NEXT_INSN (BB_END (bb
));
891 for (insn
= BB_HEAD (bb
); insn
!= last
; insn
= NEXT_INSN (insn
))
892 if (NONDEBUG_INSN_P (insn
))
894 note
= find_reg_equal_equiv_note (insn
);
895 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
899 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
901 remove_note (insn
, note
);
906 act
= (! ei_end_p (ei
)) ? ei_edge (ei
) : NULL
;
908 if (EDGE_COUNT (bb
->succs
) > 0)
912 ei
= ei_start (bb
->succs
);
913 act
= (EDGE_COUNT (ei_container (ei
)) > 0 ? EDGE_I (ei_container (ei
), 0) : NULL
);
918 /* This routine will replace a store with a SET to a specified register. */
921 replace_store_insn (rtx reg
, rtx del
, basic_block bb
, struct st_expr
*smexpr
)
923 rtx insn
, mem
, note
, set
, ptr
;
925 mem
= smexpr
->pattern
;
926 insn
= gen_move_insn (reg
, SET_SRC (single_set (del
)));
928 for (ptr
= smexpr
->antic_stores
; ptr
; ptr
= XEXP (ptr
, 1))
929 if (XEXP (ptr
, 0) == del
)
931 XEXP (ptr
, 0) = insn
;
935 /* Move the notes from the deleted insn to its replacement. */
936 REG_NOTES (insn
) = REG_NOTES (del
);
938 /* Emit the insn AFTER all the notes are transferred.
939 This is cheaper since we avoid df rescanning for the note change. */
940 insn
= emit_insn_after (insn
, del
);
945 "STORE_MOTION delete insn in BB %d:\n ", bb
->index
);
946 print_inline_rtx (dump_file
, del
, 6);
947 fprintf (dump_file
, "\nSTORE_MOTION replaced with insn:\n ");
948 print_inline_rtx (dump_file
, insn
, 6);
949 fprintf (dump_file
, "\n");
954 /* Now we must handle REG_EQUAL notes whose contents is equal to the mem;
955 they are no longer accurate provided that they are reached by this
956 definition, so drop them. */
957 for (; insn
!= NEXT_INSN (BB_END (bb
)); insn
= NEXT_INSN (insn
))
958 if (NONDEBUG_INSN_P (insn
))
960 set
= single_set (insn
);
963 if (exp_equiv_p (SET_DEST (set
), mem
, 0, true))
965 note
= find_reg_equal_equiv_note (insn
);
966 if (!note
|| !exp_equiv_p (XEXP (note
, 0), mem
, 0, true))
970 fprintf (dump_file
, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
972 remove_note (insn
, note
);
974 remove_reachable_equiv_notes (bb
, smexpr
);
978 /* Delete a store, but copy the value that would have been stored into
979 the reaching_reg for later storing. */
982 delete_store (struct st_expr
* expr
, basic_block bb
)
986 if (expr
->reaching_reg
== NULL_RTX
)
987 expr
->reaching_reg
= gen_reg_rtx_and_attrs (expr
->pattern
);
989 reg
= expr
->reaching_reg
;
991 for (i
= expr
->avail_stores
; i
; i
= XEXP (i
, 1))
994 if (BLOCK_FOR_INSN (del
) == bb
)
996 /* We know there is only one since we deleted redundant
997 ones during the available computation. */
998 replace_store_insn (reg
, del
, bb
, expr
);
1004 /* Fill in available, anticipatable, transparent and kill vectors in
1005 STORE_DATA, based on lists of available and anticipatable stores. */
1007 build_store_vectors (void)
1010 int *regs_set_in_block
;
1012 struct st_expr
* ptr
;
1013 unsigned int max_gcse_regno
= max_reg_num ();
1015 /* Build the gen_vector. This is any store in the table which is not killed
1016 by aliasing later in its block. */
1017 st_avloc
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
1018 sbitmap_vector_zero (st_avloc
, last_basic_block
);
1020 st_antloc
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
1021 sbitmap_vector_zero (st_antloc
, last_basic_block
);
1023 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1025 for (st
= ptr
->avail_stores
; st
!= NULL
; st
= XEXP (st
, 1))
1027 insn
= XEXP (st
, 0);
1028 bb
= BLOCK_FOR_INSN (insn
);
1030 /* If we've already seen an available expression in this block,
1031 we can delete this one (It occurs earlier in the block). We'll
1032 copy the SRC expression to an unused register in case there
1033 are any side effects. */
1034 if (TEST_BIT (st_avloc
[bb
->index
], ptr
->index
))
1036 rtx r
= gen_reg_rtx_and_attrs (ptr
->pattern
);
1038 fprintf (dump_file
, "Removing redundant store:\n");
1039 replace_store_insn (r
, XEXP (st
, 0), bb
, ptr
);
1042 SET_BIT (st_avloc
[bb
->index
], ptr
->index
);
1045 for (st
= ptr
->antic_stores
; st
!= NULL
; st
= XEXP (st
, 1))
1047 insn
= XEXP (st
, 0);
1048 bb
= BLOCK_FOR_INSN (insn
);
1049 SET_BIT (st_antloc
[bb
->index
], ptr
->index
);
1053 st_kill
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
1054 sbitmap_vector_zero (st_kill
, last_basic_block
);
1056 st_transp
= sbitmap_vector_alloc (last_basic_block
, num_stores
);
1057 sbitmap_vector_zero (st_transp
, last_basic_block
);
1058 regs_set_in_block
= XNEWVEC (int, max_gcse_regno
);
1062 memset (regs_set_in_block
, 0, sizeof (int) * max_gcse_regno
);
1064 FOR_BB_INSNS (bb
, insn
)
1065 if (NONDEBUG_INSN_P (insn
))
1068 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
1070 unsigned int ref_regno
= DF_REF_REGNO (*def_rec
);
1071 if (ref_regno
< max_gcse_regno
)
1072 regs_set_in_block
[DF_REF_REGNO (*def_rec
)] = 1;
1076 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1078 if (store_killed_after (ptr
->pattern
, ptr
->pattern_regs
, BB_HEAD (bb
),
1079 bb
, regs_set_in_block
, NULL
))
1081 /* It should not be necessary to consider the expression
1082 killed if it is both anticipatable and available. */
1083 if (!TEST_BIT (st_antloc
[bb
->index
], ptr
->index
)
1084 || !TEST_BIT (st_avloc
[bb
->index
], ptr
->index
))
1085 SET_BIT (st_kill
[bb
->index
], ptr
->index
);
1088 SET_BIT (st_transp
[bb
->index
], ptr
->index
);
1092 free (regs_set_in_block
);
1096 dump_sbitmap_vector (dump_file
, "st_antloc", "", st_antloc
, last_basic_block
);
1097 dump_sbitmap_vector (dump_file
, "st_kill", "", st_kill
, last_basic_block
);
1098 dump_sbitmap_vector (dump_file
, "st_transp", "", st_transp
, last_basic_block
);
1099 dump_sbitmap_vector (dump_file
, "st_avloc", "", st_avloc
, last_basic_block
);
1103 /* Free memory used by store motion. */
1106 free_store_memory (void)
1108 free_store_motion_mems ();
1111 sbitmap_vector_free (st_avloc
);
1113 sbitmap_vector_free (st_kill
);
1115 sbitmap_vector_free (st_transp
);
1117 sbitmap_vector_free (st_antloc
);
1119 sbitmap_vector_free (st_insert_map
);
1121 sbitmap_vector_free (st_delete_map
);
1123 st_avloc
= st_kill
= st_transp
= st_antloc
= NULL
;
1124 st_insert_map
= st_delete_map
= NULL
;
1127 /* Perform store motion. Much like gcse, except we move expressions the
1128 other way by looking at the flowgraph in reverse.
1129 Return non-zero if transformations are performed by the pass. */
1132 one_store_motion_pass (void)
1136 struct st_expr
* ptr
;
1137 int did_edge_inserts
= 0;
1138 int n_stores_deleted
= 0;
1139 int n_stores_created
= 0;
1141 init_alias_analysis ();
1143 /* Find all the available and anticipatable stores. */
1144 num_stores
= compute_store_table ();
1145 if (num_stores
== 0)
1147 htab_delete (store_motion_mems_table
);
1148 store_motion_mems_table
= NULL
;
1149 end_alias_analysis ();
1153 /* Now compute kill & transp vectors. */
1154 build_store_vectors ();
1155 add_noreturn_fake_exit_edges ();
1156 connect_infinite_loops_to_exit ();
1158 edge_list
= pre_edge_rev_lcm (num_stores
, st_transp
, st_avloc
,
1159 st_antloc
, st_kill
, &st_insert_map
,
1162 /* Now we want to insert the new stores which are going to be needed. */
1163 for (ptr
= first_st_expr (); ptr
!= NULL
; ptr
= next_st_expr (ptr
))
1165 /* If any of the edges we have above are abnormal, we can't move this
1167 for (x
= NUM_EDGES (edge_list
) - 1; x
>= 0; x
--)
1168 if (TEST_BIT (st_insert_map
[x
], ptr
->index
)
1169 && (INDEX_EDGE (edge_list
, x
)->flags
& EDGE_ABNORMAL
))
1174 if (dump_file
!= NULL
)
1176 "Can't replace store %d: abnormal edge from %d to %d\n",
1177 ptr
->index
, INDEX_EDGE (edge_list
, x
)->src
->index
,
1178 INDEX_EDGE (edge_list
, x
)->dest
->index
);
1182 /* Now we want to insert the new stores which are going to be needed. */
1185 if (TEST_BIT (st_delete_map
[bb
->index
], ptr
->index
))
1187 delete_store (ptr
, bb
);
1191 for (x
= 0; x
< NUM_EDGES (edge_list
); x
++)
1192 if (TEST_BIT (st_insert_map
[x
], ptr
->index
))
1194 did_edge_inserts
|= insert_store (ptr
, INDEX_EDGE (edge_list
, x
));
1199 if (did_edge_inserts
)
1200 commit_edge_insertions ();
1202 free_store_memory ();
1203 free_edge_list (edge_list
);
1204 remove_fake_exit_edges ();
1205 end_alias_analysis ();
1209 fprintf (dump_file
, "STORE_MOTION of %s, %d basic blocks, ",
1210 current_function_name (), n_basic_blocks
);
1211 fprintf (dump_file
, "%d insns deleted, %d insns created\n",
1212 n_stores_deleted
, n_stores_created
);
1215 return (n_stores_deleted
> 0 || n_stores_created
> 0);
1220 gate_rtl_store_motion (void)
1222 return optimize
> 0 && flag_gcse_sm
1223 && !cfun
->calls_setjmp
1224 && optimize_function_for_speed_p (cfun
)
1225 && dbg_cnt (store_motion
);
1229 execute_rtl_store_motion (void)
1231 delete_unreachable_blocks ();
1233 flag_rerun_cse_after_global_opts
|= one_store_motion_pass ();
1237 struct rtl_opt_pass pass_rtl_store_motion
=
1241 "store_motion", /* name */
1242 gate_rtl_store_motion
, /* gate */
1243 execute_rtl_store_motion
, /* execute */
1246 0, /* static_pass_number */
1248 PROP_cfglayout
, /* properties_required */
1249 0, /* properties_provided */
1250 0, /* properties_destroyed */
1251 0, /* todo_flags_start */
1252 TODO_df_finish
| TODO_verify_rtl_sharing
|
1253 TODO_verify_flow
| TODO_ggc_collect
/* todo_flags_finish */