1 /* Instruction scheduling pass. Selective scheduler and pipeliner.
2 Copyright (C) 2006-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
24 #include "diagnostic-core.h"
27 #include "hard-reg-set.h"
32 #include "dominance.h"
37 #include "basic-block.h"
39 #include "insn-config.h"
40 #include "insn-attr.h"
45 #include "sched-int.h"
48 #include "langhooks.h"
49 #include "rtlhooks-def.h"
50 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
52 #ifdef INSN_SCHEDULING
53 #include "sel-sched-ir.h"
54 /* We don't have to use it except for sel_print_insn. */
55 #include "sel-sched-dump.h"
57 /* A vector holding bb info for whole scheduling pass. */
58 vec
<sel_global_bb_info_def
>
59 sel_global_bb_info
= vNULL
;
61 /* A vector holding bb info. */
62 vec
<sel_region_bb_info_def
>
63 sel_region_bb_info
= vNULL
;
65 /* A pool for allocating all lists. */
66 pool_allocator
<_list_node
> sched_lists_pool ("sel-sched-lists", 500);
68 /* This contains information about successors for compute_av_set. */
69 struct succs_info current_succs
;
71 /* Data structure to describe interaction with the generic scheduler utils. */
72 static struct common_sched_info_def sel_common_sched_info
;
74 /* The loop nest being pipelined. */
75 struct loop
*current_loop_nest
;
77 /* LOOP_NESTS is a vector containing the corresponding loop nest for
79 static vec
<loop_p
> loop_nests
= vNULL
;
81 /* Saves blocks already in loop regions, indexed by bb->index. */
82 static sbitmap bbs_in_loop_rgns
= NULL
;
84 /* CFG hooks that are saved before changing create_basic_block hook. */
85 static struct cfg_hooks orig_cfg_hooks
;
88 /* Array containing reverse topological index of function basic blocks,
89 indexed by BB->INDEX. */
90 static int *rev_top_order_index
= NULL
;
92 /* Length of the above array. */
93 static int rev_top_order_index_len
= -1;
95 /* A regset pool structure. */
98 /* The stack to which regsets are returned. */
107 /* In VV we save all generated regsets so that, when destructing the
108 pool, we can compare it with V and check that every regset was returned
112 /* The pointer of VV stack. */
118 /* The difference between allocated and returned regsets. */
120 } regset_pool
= { NULL
, 0, 0, NULL
, 0, 0, 0 };
122 /* This represents the nop pool. */
125 /* The vector which holds previously emitted nops. */
133 } nop_pool
= { NULL
, 0, 0 };
135 /* The pool for basic block notes. */
136 static vec
<rtx_note
*> bb_note_pool
;
138 /* A NOP pattern used to emit placeholder insns. */
139 rtx nop_pattern
= NULL_RTX
;
140 /* A special instruction that resides in EXIT_BLOCK.
141 EXIT_INSN is successor of the insns that lead to EXIT_BLOCK. */
142 rtx_insn
*exit_insn
= NULL
;
144 /* TRUE if while scheduling current region, which is loop, its preheader
146 bool preheader_removed
= false;
149 /* Forward static declarations. */
150 static void fence_clear (fence_t
);
152 static void deps_init_id (idata_t
, insn_t
, bool);
153 static void init_id_from_df (idata_t
, insn_t
, bool);
154 static expr_t
set_insn_init (expr_t
, vinsn_t
, int);
156 static void cfg_preds (basic_block
, insn_t
**, int *);
157 static void prepare_insn_expr (insn_t
, int);
158 static void free_history_vect (vec
<expr_history_def
> &);
160 static void move_bb_info (basic_block
, basic_block
);
161 static void remove_empty_bb (basic_block
, bool);
162 static void sel_merge_blocks (basic_block
, basic_block
);
163 static void sel_remove_loop_preheader (void);
164 static bool bb_has_removable_jump_to_p (basic_block
, basic_block
);
166 static bool insn_is_the_only_one_in_bb_p (insn_t
);
167 static void create_initial_data_sets (basic_block
);
169 static void free_av_set (basic_block
);
170 static void invalidate_av_set (basic_block
);
171 static void extend_insn_data (void);
172 static void sel_init_new_insn (insn_t
, int, int = -1);
173 static void finish_insns (void);
175 /* Various list functions. */
177 /* Copy an instruction list L. */
179 ilist_copy (ilist_t l
)
181 ilist_t head
= NULL
, *tailp
= &head
;
185 ilist_add (tailp
, ILIST_INSN (l
));
186 tailp
= &ILIST_NEXT (*tailp
);
193 /* Invert an instruction list L. */
195 ilist_invert (ilist_t l
)
201 ilist_add (&res
, ILIST_INSN (l
));
208 /* Add a new boundary to the LP list with parameters TO, PTR, and DC. */
210 blist_add (blist_t
*lp
, insn_t to
, ilist_t ptr
, deps_t dc
)
215 bnd
= BLIST_BND (*lp
);
220 BND_AV1 (bnd
) = NULL
;
224 /* Remove the list note pointed to by LP. */
226 blist_remove (blist_t
*lp
)
228 bnd_t b
= BLIST_BND (*lp
);
230 av_set_clear (&BND_AV (b
));
231 av_set_clear (&BND_AV1 (b
));
232 ilist_clear (&BND_PTR (b
));
237 /* Init a fence tail L. */
239 flist_tail_init (flist_tail_t l
)
241 FLIST_TAIL_HEAD (l
) = NULL
;
242 FLIST_TAIL_TAILP (l
) = &FLIST_TAIL_HEAD (l
);
245 /* Try to find fence corresponding to INSN in L. */
247 flist_lookup (flist_t l
, insn_t insn
)
251 if (FENCE_INSN (FLIST_FENCE (l
)) == insn
)
252 return FLIST_FENCE (l
);
260 /* Init the fields of F before running fill_insns. */
262 init_fence_for_scheduling (fence_t f
)
264 FENCE_BNDS (f
) = NULL
;
265 FENCE_PROCESSED_P (f
) = false;
266 FENCE_SCHEDULED_P (f
) = false;
269 /* Add new fence consisting of INSN and STATE to the list pointed to by LP. */
271 flist_add (flist_t
*lp
, insn_t insn
, state_t state
, deps_t dc
, void *tc
,
272 insn_t last_scheduled_insn
, vec
<rtx_insn
*, va_gc
> *executing_insns
,
273 int *ready_ticks
, int ready_ticks_size
, insn_t sched_next
,
274 int cycle
, int cycle_issued_insns
, int issue_more
,
275 bool starts_cycle_p
, bool after_stall_p
)
280 f
= FLIST_FENCE (*lp
);
282 FENCE_INSN (f
) = insn
;
284 gcc_assert (state
!= NULL
);
285 FENCE_STATE (f
) = state
;
287 FENCE_CYCLE (f
) = cycle
;
288 FENCE_ISSUED_INSNS (f
) = cycle_issued_insns
;
289 FENCE_STARTS_CYCLE_P (f
) = starts_cycle_p
;
290 FENCE_AFTER_STALL_P (f
) = after_stall_p
;
292 gcc_assert (dc
!= NULL
);
295 gcc_assert (tc
!= NULL
|| targetm
.sched
.alloc_sched_context
== NULL
);
298 FENCE_LAST_SCHEDULED_INSN (f
) = last_scheduled_insn
;
299 FENCE_ISSUE_MORE (f
) = issue_more
;
300 FENCE_EXECUTING_INSNS (f
) = executing_insns
;
301 FENCE_READY_TICKS (f
) = ready_ticks
;
302 FENCE_READY_TICKS_SIZE (f
) = ready_ticks_size
;
303 FENCE_SCHED_NEXT (f
) = sched_next
;
305 init_fence_for_scheduling (f
);
308 /* Remove the head node of the list pointed to by LP. */
310 flist_remove (flist_t
*lp
)
312 if (FENCE_INSN (FLIST_FENCE (*lp
)))
313 fence_clear (FLIST_FENCE (*lp
));
317 /* Clear the fence list pointed to by LP. */
319 flist_clear (flist_t
*lp
)
325 /* Add ORIGINAL_INSN the def list DL honoring CROSSES_CALL. */
327 def_list_add (def_list_t
*dl
, insn_t original_insn
, bool crosses_call
)
332 d
= DEF_LIST_DEF (*dl
);
334 d
->orig_insn
= original_insn
;
335 d
->crosses_call
= crosses_call
;
339 /* Functions to work with target contexts. */
341 /* Bulk target context. It is convenient for debugging purposes to ensure
342 that there are no uninitialized (null) target contexts. */
343 static tc_t bulk_tc
= (tc_t
) 1;
345 /* Target hooks wrappers. In the future we can provide some default
346 implementations for them. */
348 /* Allocate a store for the target context. */
350 alloc_target_context (void)
352 return (targetm
.sched
.alloc_sched_context
353 ? targetm
.sched
.alloc_sched_context () : bulk_tc
);
356 /* Init target context TC.
357 If CLEAN_P is true, then make TC as it is beginning of the scheduler.
358 Overwise, copy current backend context to TC. */
360 init_target_context (tc_t tc
, bool clean_p
)
362 if (targetm
.sched
.init_sched_context
)
363 targetm
.sched
.init_sched_context (tc
, clean_p
);
366 /* Allocate and initialize a target context. Meaning of CLEAN_P is the same as
367 int init_target_context (). */
369 create_target_context (bool clean_p
)
371 tc_t tc
= alloc_target_context ();
373 init_target_context (tc
, clean_p
);
377 /* Copy TC to the current backend context. */
379 set_target_context (tc_t tc
)
381 if (targetm
.sched
.set_sched_context
)
382 targetm
.sched
.set_sched_context (tc
);
385 /* TC is about to be destroyed. Free any internal data. */
387 clear_target_context (tc_t tc
)
389 if (targetm
.sched
.clear_sched_context
)
390 targetm
.sched
.clear_sched_context (tc
);
393 /* Clear and free it. */
395 delete_target_context (tc_t tc
)
397 clear_target_context (tc
);
399 if (targetm
.sched
.free_sched_context
)
400 targetm
.sched
.free_sched_context (tc
);
403 /* Make a copy of FROM in TO.
404 NB: May be this should be a hook. */
406 copy_target_context (tc_t to
, tc_t from
)
408 tc_t tmp
= create_target_context (false);
410 set_target_context (from
);
411 init_target_context (to
, false);
413 set_target_context (tmp
);
414 delete_target_context (tmp
);
417 /* Create a copy of TC. */
419 create_copy_of_target_context (tc_t tc
)
421 tc_t copy
= alloc_target_context ();
423 copy_target_context (copy
, tc
);
428 /* Clear TC and initialize it according to CLEAN_P. The meaning of CLEAN_P
429 is the same as in init_target_context (). */
431 reset_target_context (tc_t tc
, bool clean_p
)
433 clear_target_context (tc
);
434 init_target_context (tc
, clean_p
);
437 /* Functions to work with dependence contexts.
438 Dc (aka deps context, aka deps_t, aka struct deps_desc *) is short for dependence
439 context. It accumulates information about processed insns to decide if
440 current insn is dependent on the processed ones. */
442 /* Make a copy of FROM in TO. */
444 copy_deps_context (deps_t to
, deps_t from
)
446 init_deps (to
, false);
447 deps_join (to
, from
);
450 /* Allocate store for dep context. */
452 alloc_deps_context (void)
454 return XNEW (struct deps_desc
);
457 /* Allocate and initialize dep context. */
459 create_deps_context (void)
461 deps_t dc
= alloc_deps_context ();
463 init_deps (dc
, false);
467 /* Create a copy of FROM. */
469 create_copy_of_deps_context (deps_t from
)
471 deps_t to
= alloc_deps_context ();
473 copy_deps_context (to
, from
);
477 /* Clean up internal data of DC. */
479 clear_deps_context (deps_t dc
)
484 /* Clear and free DC. */
486 delete_deps_context (deps_t dc
)
488 clear_deps_context (dc
);
492 /* Clear and init DC. */
494 reset_deps_context (deps_t dc
)
496 clear_deps_context (dc
);
497 init_deps (dc
, false);
500 /* This structure describes the dependence analysis hooks for advancing
501 dependence context. */
502 static struct sched_deps_info_def advance_deps_context_sched_deps_info
=
506 NULL
, /* start_insn */
507 NULL
, /* finish_insn */
508 NULL
, /* start_lhs */
509 NULL
, /* finish_lhs */
510 NULL
, /* start_rhs */
511 NULL
, /* finish_rhs */
513 haifa_note_reg_clobber
,
515 NULL
, /* note_mem_dep */
521 /* Process INSN and add its impact on DC. */
523 advance_deps_context (deps_t dc
, insn_t insn
)
525 sched_deps_info
= &advance_deps_context_sched_deps_info
;
526 deps_analyze_insn (dc
, insn
);
530 /* Functions to work with DFA states. */
532 /* Allocate store for a DFA state. */
536 return xmalloc (dfa_state_size
);
539 /* Allocate and initialize DFA state. */
543 state_t state
= state_alloc ();
546 advance_state (state
);
550 /* Free DFA state. */
552 state_free (state_t state
)
557 /* Make a copy of FROM in TO. */
559 state_copy (state_t to
, state_t from
)
561 memcpy (to
, from
, dfa_state_size
);
564 /* Create a copy of FROM. */
566 state_create_copy (state_t from
)
568 state_t to
= state_alloc ();
570 state_copy (to
, from
);
575 /* Functions to work with fences. */
577 /* Clear the fence. */
579 fence_clear (fence_t f
)
581 state_t s
= FENCE_STATE (f
);
582 deps_t dc
= FENCE_DC (f
);
583 void *tc
= FENCE_TC (f
);
585 ilist_clear (&FENCE_BNDS (f
));
587 gcc_assert ((s
!= NULL
&& dc
!= NULL
&& tc
!= NULL
)
588 || (s
== NULL
&& dc
== NULL
&& tc
== NULL
));
593 delete_deps_context (dc
);
596 delete_target_context (tc
);
597 vec_free (FENCE_EXECUTING_INSNS (f
));
598 free (FENCE_READY_TICKS (f
));
599 FENCE_READY_TICKS (f
) = NULL
;
602 /* Init a list of fences with successors of OLD_FENCE. */
604 init_fences (insn_t old_fence
)
609 int ready_ticks_size
= get_max_uid () + 1;
611 FOR_EACH_SUCC_1 (succ
, si
, old_fence
,
612 SUCCS_NORMAL
| SUCCS_SKIP_TO_LOOP_EXITS
)
618 gcc_assert (flag_sel_sched_pipelining_outer_loops
);
620 flist_add (&fences
, succ
,
622 create_deps_context () /* dc */,
623 create_target_context (true) /* tc */,
624 NULL
/* last_scheduled_insn */,
625 NULL
, /* executing_insns */
626 XCNEWVEC (int, ready_ticks_size
), /* ready_ticks */
628 NULL
/* sched_next */,
629 1 /* cycle */, 0 /* cycle_issued_insns */,
630 issue_rate
, /* issue_more */
631 1 /* starts_cycle_p */, 0 /* after_stall_p */);
635 /* Merges two fences (filling fields of fence F with resulting values) by
636 following rules: 1) state, target context and last scheduled insn are
637 propagated from fallthrough edge if it is available;
638 2) deps context and cycle is propagated from more probable edge;
639 3) all other fields are set to corresponding constant values.
641 INSN, STATE, DC, TC, LAST_SCHEDULED_INSN, EXECUTING_INSNS,
642 READY_TICKS, READY_TICKS_SIZE, SCHED_NEXT, CYCLE, ISSUE_MORE
643 and AFTER_STALL_P are the corresponding fields of the second fence. */
645 merge_fences (fence_t f
, insn_t insn
,
646 state_t state
, deps_t dc
, void *tc
,
647 rtx_insn
*last_scheduled_insn
,
648 vec
<rtx_insn
*, va_gc
> *executing_insns
,
649 int *ready_ticks
, int ready_ticks_size
,
650 rtx sched_next
, int cycle
, int issue_more
, bool after_stall_p
)
652 insn_t last_scheduled_insn_old
= FENCE_LAST_SCHEDULED_INSN (f
);
654 gcc_assert (sel_bb_head_p (FENCE_INSN (f
))
655 && !sched_next
&& !FENCE_SCHED_NEXT (f
));
657 /* Check if we can decide which path fences came.
658 If we can't (or don't want to) - reset all. */
659 if (last_scheduled_insn
== NULL
660 || last_scheduled_insn_old
== NULL
661 /* This is a case when INSN is reachable on several paths from
662 one insn (this can happen when pipelining of outer loops is on and
663 there are two edges: one going around of inner loop and the other -
664 right through it; in such case just reset everything). */
665 || last_scheduled_insn
== last_scheduled_insn_old
)
667 state_reset (FENCE_STATE (f
));
670 reset_deps_context (FENCE_DC (f
));
671 delete_deps_context (dc
);
673 reset_target_context (FENCE_TC (f
), true);
674 delete_target_context (tc
);
676 if (cycle
> FENCE_CYCLE (f
))
677 FENCE_CYCLE (f
) = cycle
;
679 FENCE_LAST_SCHEDULED_INSN (f
) = NULL
;
680 FENCE_ISSUE_MORE (f
) = issue_rate
;
681 vec_free (executing_insns
);
683 if (FENCE_EXECUTING_INSNS (f
))
684 FENCE_EXECUTING_INSNS (f
)->block_remove (0,
685 FENCE_EXECUTING_INSNS (f
)->length ());
686 if (FENCE_READY_TICKS (f
))
687 memset (FENCE_READY_TICKS (f
), 0, FENCE_READY_TICKS_SIZE (f
));
691 edge edge_old
= NULL
, edge_new
= NULL
;
696 /* Find fallthrough edge. */
697 gcc_assert (BLOCK_FOR_INSN (insn
)->prev_bb
);
698 candidate
= find_fallthru_edge_from (BLOCK_FOR_INSN (insn
)->prev_bb
);
701 || (candidate
->src
!= BLOCK_FOR_INSN (last_scheduled_insn
)
702 && candidate
->src
!= BLOCK_FOR_INSN (last_scheduled_insn_old
)))
704 /* No fallthrough edge leading to basic block of INSN. */
705 state_reset (FENCE_STATE (f
));
708 reset_target_context (FENCE_TC (f
), true);
709 delete_target_context (tc
);
711 FENCE_LAST_SCHEDULED_INSN (f
) = NULL
;
712 FENCE_ISSUE_MORE (f
) = issue_rate
;
715 if (candidate
->src
== BLOCK_FOR_INSN (last_scheduled_insn
))
717 /* Would be weird if same insn is successor of several fallthrough
719 gcc_assert (BLOCK_FOR_INSN (insn
)->prev_bb
720 != BLOCK_FOR_INSN (last_scheduled_insn_old
));
722 state_free (FENCE_STATE (f
));
723 FENCE_STATE (f
) = state
;
725 delete_target_context (FENCE_TC (f
));
728 FENCE_LAST_SCHEDULED_INSN (f
) = last_scheduled_insn
;
729 FENCE_ISSUE_MORE (f
) = issue_more
;
733 /* Leave STATE, TC and LAST_SCHEDULED_INSN fields untouched. */
735 delete_target_context (tc
);
737 gcc_assert (BLOCK_FOR_INSN (insn
)->prev_bb
738 != BLOCK_FOR_INSN (last_scheduled_insn
));
741 /* Find edge of first predecessor (last_scheduled_insn_old->insn). */
742 FOR_EACH_SUCC_1 (succ
, si
, last_scheduled_insn_old
,
743 SUCCS_NORMAL
| SUCCS_SKIP_TO_LOOP_EXITS
)
747 /* No same successor allowed from several edges. */
748 gcc_assert (!edge_old
);
752 /* Find edge of second predecessor (last_scheduled_insn->insn). */
753 FOR_EACH_SUCC_1 (succ
, si
, last_scheduled_insn
,
754 SUCCS_NORMAL
| SUCCS_SKIP_TO_LOOP_EXITS
)
758 /* No same successor allowed from several edges. */
759 gcc_assert (!edge_new
);
764 /* Check if we can choose most probable predecessor. */
765 if (edge_old
== NULL
|| edge_new
== NULL
)
767 reset_deps_context (FENCE_DC (f
));
768 delete_deps_context (dc
);
769 vec_free (executing_insns
);
772 FENCE_CYCLE (f
) = MAX (FENCE_CYCLE (f
), cycle
);
773 if (FENCE_EXECUTING_INSNS (f
))
774 FENCE_EXECUTING_INSNS (f
)->block_remove (0,
775 FENCE_EXECUTING_INSNS (f
)->length ());
776 if (FENCE_READY_TICKS (f
))
777 memset (FENCE_READY_TICKS (f
), 0, FENCE_READY_TICKS_SIZE (f
));
780 if (edge_new
->probability
> edge_old
->probability
)
782 delete_deps_context (FENCE_DC (f
));
784 vec_free (FENCE_EXECUTING_INSNS (f
));
785 FENCE_EXECUTING_INSNS (f
) = executing_insns
;
786 free (FENCE_READY_TICKS (f
));
787 FENCE_READY_TICKS (f
) = ready_ticks
;
788 FENCE_READY_TICKS_SIZE (f
) = ready_ticks_size
;
789 FENCE_CYCLE (f
) = cycle
;
793 /* Leave DC and CYCLE untouched. */
794 delete_deps_context (dc
);
795 vec_free (executing_insns
);
800 /* Fill remaining invariant fields. */
802 FENCE_AFTER_STALL_P (f
) = 1;
804 FENCE_ISSUED_INSNS (f
) = 0;
805 FENCE_STARTS_CYCLE_P (f
) = 1;
806 FENCE_SCHED_NEXT (f
) = NULL
;
809 /* Add a new fence to NEW_FENCES list, initializing it from all
812 add_to_fences (flist_tail_t new_fences
, insn_t insn
,
813 state_t state
, deps_t dc
, void *tc
,
814 rtx_insn
*last_scheduled_insn
,
815 vec
<rtx_insn
*, va_gc
> *executing_insns
, int *ready_ticks
,
816 int ready_ticks_size
, rtx_insn
*sched_next
, int cycle
,
817 int cycle_issued_insns
, int issue_rate
,
818 bool starts_cycle_p
, bool after_stall_p
)
820 fence_t f
= flist_lookup (FLIST_TAIL_HEAD (new_fences
), insn
);
824 flist_add (FLIST_TAIL_TAILP (new_fences
), insn
, state
, dc
, tc
,
825 last_scheduled_insn
, executing_insns
, ready_ticks
,
826 ready_ticks_size
, sched_next
, cycle
, cycle_issued_insns
,
827 issue_rate
, starts_cycle_p
, after_stall_p
);
829 FLIST_TAIL_TAILP (new_fences
)
830 = &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences
));
834 merge_fences (f
, insn
, state
, dc
, tc
, last_scheduled_insn
,
835 executing_insns
, ready_ticks
, ready_ticks_size
,
836 sched_next
, cycle
, issue_rate
, after_stall_p
);
840 /* Move the first fence in the OLD_FENCES list to NEW_FENCES. */
842 move_fence_to_fences (flist_t old_fences
, flist_tail_t new_fences
)
845 flist_t
*tailp
= FLIST_TAIL_TAILP (new_fences
);
847 old
= FLIST_FENCE (old_fences
);
848 f
= flist_lookup (FLIST_TAIL_HEAD (new_fences
),
849 FENCE_INSN (FLIST_FENCE (old_fences
)));
852 merge_fences (f
, old
->insn
, old
->state
, old
->dc
, old
->tc
,
853 old
->last_scheduled_insn
, old
->executing_insns
,
854 old
->ready_ticks
, old
->ready_ticks_size
,
855 old
->sched_next
, old
->cycle
, old
->issue_more
,
861 FLIST_TAIL_TAILP (new_fences
) = &FLIST_NEXT (*tailp
);
862 *FLIST_FENCE (*tailp
) = *old
;
863 init_fence_for_scheduling (FLIST_FENCE (*tailp
));
865 FENCE_INSN (old
) = NULL
;
868 /* Add a new fence to NEW_FENCES list and initialize most of its data
871 add_clean_fence_to_fences (flist_tail_t new_fences
, insn_t succ
, fence_t fence
)
873 int ready_ticks_size
= get_max_uid () + 1;
875 add_to_fences (new_fences
,
876 succ
, state_create (), create_deps_context (),
877 create_target_context (true),
879 XCNEWVEC (int, ready_ticks_size
), ready_ticks_size
,
880 NULL
, FENCE_CYCLE (fence
) + 1,
881 0, issue_rate
, 1, FENCE_AFTER_STALL_P (fence
));
884 /* Add a new fence to NEW_FENCES list and initialize all of its data
885 from FENCE and SUCC. */
887 add_dirty_fence_to_fences (flist_tail_t new_fences
, insn_t succ
, fence_t fence
)
889 int * new_ready_ticks
890 = XNEWVEC (int, FENCE_READY_TICKS_SIZE (fence
));
892 memcpy (new_ready_ticks
, FENCE_READY_TICKS (fence
),
893 FENCE_READY_TICKS_SIZE (fence
) * sizeof (int));
894 add_to_fences (new_fences
,
895 succ
, state_create_copy (FENCE_STATE (fence
)),
896 create_copy_of_deps_context (FENCE_DC (fence
)),
897 create_copy_of_target_context (FENCE_TC (fence
)),
898 FENCE_LAST_SCHEDULED_INSN (fence
),
899 vec_safe_copy (FENCE_EXECUTING_INSNS (fence
)),
901 FENCE_READY_TICKS_SIZE (fence
),
902 FENCE_SCHED_NEXT (fence
),
904 FENCE_ISSUED_INSNS (fence
),
905 FENCE_ISSUE_MORE (fence
),
906 FENCE_STARTS_CYCLE_P (fence
),
907 FENCE_AFTER_STALL_P (fence
));
911 /* Functions to work with regset and nop pools. */
913 /* Returns the new regset from pool. It might have some of the bits set
914 from the previous usage. */
916 get_regset_from_pool (void)
920 if (regset_pool
.n
!= 0)
921 rs
= regset_pool
.v
[--regset_pool
.n
];
923 /* We need to create the regset. */
925 rs
= ALLOC_REG_SET (®_obstack
);
927 if (regset_pool
.nn
== regset_pool
.ss
)
928 regset_pool
.vv
= XRESIZEVEC (regset
, regset_pool
.vv
,
929 (regset_pool
.ss
= 2 * regset_pool
.ss
+ 1));
930 regset_pool
.vv
[regset_pool
.nn
++] = rs
;
938 /* Same as above, but returns the empty regset. */
940 get_clear_regset_from_pool (void)
942 regset rs
= get_regset_from_pool ();
948 /* Return regset RS to the pool for future use. */
950 return_regset_to_pool (regset rs
)
955 if (regset_pool
.n
== regset_pool
.s
)
956 regset_pool
.v
= XRESIZEVEC (regset
, regset_pool
.v
,
957 (regset_pool
.s
= 2 * regset_pool
.s
+ 1));
958 regset_pool
.v
[regset_pool
.n
++] = rs
;
961 #ifdef ENABLE_CHECKING
962 /* This is used as a qsort callback for sorting regset pool stacks.
963 X and XX are addresses of two regsets. They are never equal. */
965 cmp_v_in_regset_pool (const void *x
, const void *xx
)
967 uintptr_t r1
= (uintptr_t) *((const regset
*) x
);
968 uintptr_t r2
= (uintptr_t) *((const regset
*) xx
);
977 /* Free the regset pool possibly checking for memory leaks. */
979 free_regset_pool (void)
981 #ifdef ENABLE_CHECKING
983 regset
*v
= regset_pool
.v
;
985 int n
= regset_pool
.n
;
987 regset
*vv
= regset_pool
.vv
;
989 int nn
= regset_pool
.nn
;
993 gcc_assert (n
<= nn
);
995 /* Sort both vectors so it will be possible to compare them. */
996 qsort (v
, n
, sizeof (*v
), cmp_v_in_regset_pool
);
997 qsort (vv
, nn
, sizeof (*vv
), cmp_v_in_regset_pool
);
1004 /* VV[II] was lost. */
1010 gcc_assert (diff
== regset_pool
.diff
);
1014 /* If not true - we have a memory leak. */
1015 gcc_assert (regset_pool
.diff
== 0);
1017 while (regset_pool
.n
)
1020 FREE_REG_SET (regset_pool
.v
[regset_pool
.n
]);
1023 free (regset_pool
.v
);
1024 regset_pool
.v
= NULL
;
1027 free (regset_pool
.vv
);
1028 regset_pool
.vv
= NULL
;
1032 regset_pool
.diff
= 0;
1036 /* Functions to work with nop pools. NOP insns are used as temporary
1037 placeholders of the insns being scheduled to allow correct update of
1038 the data sets. When update is finished, NOPs are deleted. */
1040 /* A vinsn that is used to represent a nop. This vinsn is shared among all
1041 nops sel-sched generates. */
1042 static vinsn_t nop_vinsn
= NULL
;
1044 /* Emit a nop before INSN, taking it from pool. */
1046 get_nop_from_pool (insn_t insn
)
1050 bool old_p
= nop_pool
.n
!= 0;
1054 nop_pat
= nop_pool
.v
[--nop_pool
.n
];
1056 nop_pat
= nop_pattern
;
1058 nop
= emit_insn_before (nop_pat
, insn
);
1061 flags
= INSN_INIT_TODO_SSID
;
1063 flags
= INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SSID
;
1065 set_insn_init (INSN_EXPR (insn
), nop_vinsn
, INSN_SEQNO (insn
));
1066 sel_init_new_insn (nop
, flags
);
1071 /* Remove NOP from the instruction stream and return it to the pool. */
1073 return_nop_to_pool (insn_t nop
, bool full_tidying
)
1075 gcc_assert (INSN_IN_STREAM_P (nop
));
1076 sel_remove_insn (nop
, false, full_tidying
);
1078 /* We'll recycle this nop. */
1079 nop
->set_undeleted ();
1081 if (nop_pool
.n
== nop_pool
.s
)
1082 nop_pool
.v
= XRESIZEVEC (rtx_insn
*, nop_pool
.v
,
1083 (nop_pool
.s
= 2 * nop_pool
.s
+ 1));
1084 nop_pool
.v
[nop_pool
.n
++] = nop
;
1087 /* Free the nop pool. */
1089 free_nop_pool (void)
1098 /* Skip unspec to support ia64 speculation. Called from rtx_equal_p_cb.
1099 The callback is given two rtxes XX and YY and writes the new rtxes
1100 to NX and NY in case some needs to be skipped. */
1102 skip_unspecs_callback (const_rtx
*xx
, const_rtx
*yy
, rtx
*nx
, rtx
* ny
)
1107 if (GET_CODE (x
) == UNSPEC
1108 && (targetm
.sched
.skip_rtx_p
== NULL
1109 || targetm
.sched
.skip_rtx_p (x
)))
1111 *nx
= XVECEXP (x
, 0, 0);
1112 *ny
= CONST_CAST_RTX (y
);
1116 if (GET_CODE (y
) == UNSPEC
1117 && (targetm
.sched
.skip_rtx_p
== NULL
1118 || targetm
.sched
.skip_rtx_p (y
)))
1120 *nx
= CONST_CAST_RTX (x
);
1121 *ny
= XVECEXP (y
, 0, 0);
1128 /* Callback, called from hash_rtx_cb. Helps to hash UNSPEC rtx X in a correct way
1129 to support ia64 speculation. When changes are needed, new rtx X and new mode
1130 NMODE are written, and the callback returns true. */
1132 hash_with_unspec_callback (const_rtx x
, machine_mode mode ATTRIBUTE_UNUSED
,
1133 rtx
*nx
, machine_mode
* nmode
)
1135 if (GET_CODE (x
) == UNSPEC
1136 && targetm
.sched
.skip_rtx_p
1137 && targetm
.sched
.skip_rtx_p (x
))
1139 *nx
= XVECEXP (x
, 0 ,0);
1147 /* Returns LHS and RHS are ok to be scheduled separately. */
1149 lhs_and_rhs_separable_p (rtx lhs
, rtx rhs
)
1151 if (lhs
== NULL
|| rhs
== NULL
)
1154 /* Do not schedule constants as rhs: no point to use reg, if const
1155 can be used. Moreover, scheduling const as rhs may lead to mode
1156 mismatch cause consts don't have modes but they could be merged
1157 from branches where the same const used in different modes. */
1158 if (CONSTANT_P (rhs
))
1161 /* ??? Do not rename predicate registers to avoid ICEs in bundling. */
1162 if (COMPARISON_P (rhs
))
1165 /* Do not allow single REG to be an rhs. */
1169 /* See comment at find_used_regs_1 (*1) for explanation of this
1171 /* FIXME: remove this later. */
1175 /* This will filter all tricky things like ZERO_EXTRACT etc.
1176 For now we don't handle it. */
1177 if (!REG_P (lhs
) && !MEM_P (lhs
))
1183 /* Initialize vinsn VI for INSN. Only for use from vinsn_create (). When
1184 FORCE_UNIQUE_P is true, the resulting vinsn will not be clonable. This is
1185 used e.g. for insns from recovery blocks. */
1187 vinsn_init (vinsn_t vi
, insn_t insn
, bool force_unique_p
)
1189 hash_rtx_callback_function hrcf
;
1192 VINSN_INSN_RTX (vi
) = insn
;
1193 VINSN_COUNT (vi
) = 0;
1196 if (INSN_NOP_P (insn
))
1199 if (DF_INSN_UID_SAFE_GET (INSN_UID (insn
)) != NULL
)
1200 init_id_from_df (VINSN_ID (vi
), insn
, force_unique_p
);
1202 deps_init_id (VINSN_ID (vi
), insn
, force_unique_p
);
1204 /* Hash vinsn depending on whether it is separable or not. */
1205 hrcf
= targetm
.sched
.skip_rtx_p
? hash_with_unspec_callback
: NULL
;
1206 if (VINSN_SEPARABLE_P (vi
))
1208 rtx rhs
= VINSN_RHS (vi
);
1210 VINSN_HASH (vi
) = hash_rtx_cb (rhs
, GET_MODE (rhs
),
1211 NULL
, NULL
, false, hrcf
);
1212 VINSN_HASH_RTX (vi
) = hash_rtx_cb (VINSN_PATTERN (vi
),
1213 VOIDmode
, NULL
, NULL
,
1218 VINSN_HASH (vi
) = hash_rtx_cb (VINSN_PATTERN (vi
), VOIDmode
,
1219 NULL
, NULL
, false, hrcf
);
1220 VINSN_HASH_RTX (vi
) = VINSN_HASH (vi
);
1223 insn_class
= haifa_classify_insn (insn
);
1225 && (!targetm
.sched
.get_insn_spec_ds
1226 || ((targetm
.sched
.get_insn_spec_ds (insn
) & BEGIN_CONTROL
)
1228 VINSN_MAY_TRAP_P (vi
) = true;
1230 VINSN_MAY_TRAP_P (vi
) = false;
1233 /* Indicate that VI has become the part of an rtx object. */
1235 vinsn_attach (vinsn_t vi
)
1237 /* Assert that VI is not pending for deletion. */
1238 gcc_assert (VINSN_INSN_RTX (vi
));
1243 /* Create and init VI from the INSN. Use UNIQUE_P for determining the correct
1246 vinsn_create (insn_t insn
, bool force_unique_p
)
1248 vinsn_t vi
= XCNEW (struct vinsn_def
);
1250 vinsn_init (vi
, insn
, force_unique_p
);
1254 /* Return a copy of VI. When REATTACH_P is true, detach VI and attach
1257 vinsn_copy (vinsn_t vi
, bool reattach_p
)
1260 bool unique
= VINSN_UNIQUE_P (vi
);
1263 copy
= create_copy_of_insn_rtx (VINSN_INSN_RTX (vi
));
1264 new_vi
= create_vinsn_from_insn_rtx (copy
, unique
);
1268 vinsn_attach (new_vi
);
1274 /* Delete the VI vinsn and free its data. */
1276 vinsn_delete (vinsn_t vi
)
1278 gcc_assert (VINSN_COUNT (vi
) == 0);
1280 if (!INSN_NOP_P (VINSN_INSN_RTX (vi
)))
1282 return_regset_to_pool (VINSN_REG_SETS (vi
));
1283 return_regset_to_pool (VINSN_REG_USES (vi
));
1284 return_regset_to_pool (VINSN_REG_CLOBBERS (vi
));
1290 /* Indicate that VI is no longer a part of some rtx object.
1291 Remove VI if it is no longer needed. */
1293 vinsn_detach (vinsn_t vi
)
1295 gcc_assert (VINSN_COUNT (vi
) > 0);
1297 if (--VINSN_COUNT (vi
) == 0)
1301 /* Returns TRUE if VI is a branch. */
1303 vinsn_cond_branch_p (vinsn_t vi
)
1307 if (!VINSN_UNIQUE_P (vi
))
1310 insn
= VINSN_INSN_RTX (vi
);
1311 if (BB_END (BLOCK_FOR_INSN (insn
)) != insn
)
1314 return control_flow_insn_p (insn
);
1317 /* Return latency of INSN. */
1319 sel_insn_rtx_cost (rtx_insn
*insn
)
1323 /* A USE insn, or something else we don't need to
1324 understand. We can't pass these directly to
1325 result_ready_cost or insn_default_latency because it will
1326 trigger a fatal error for unrecognizable insns. */
1327 if (recog_memoized (insn
) < 0)
1331 cost
= insn_default_latency (insn
);
1340 /* Return the cost of the VI.
1341 !!! FIXME: Unify with haifa-sched.c: insn_cost (). */
1343 sel_vinsn_cost (vinsn_t vi
)
1345 int cost
= vi
->cost
;
1349 cost
= sel_insn_rtx_cost (VINSN_INSN_RTX (vi
));
1357 /* Functions for insn emitting. */
1359 /* Emit new insn after AFTER based on PATTERN and initialize its data from
1362 sel_gen_insn_from_rtx_after (rtx pattern
, expr_t expr
, int seqno
, insn_t after
)
1366 gcc_assert (EXPR_TARGET_AVAILABLE (expr
) == true);
1368 new_insn
= emit_insn_after (pattern
, after
);
1369 set_insn_init (expr
, NULL
, seqno
);
1370 sel_init_new_insn (new_insn
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SSID
);
1375 /* Force newly generated vinsns to be unique. */
1376 static bool init_insn_force_unique_p
= false;
1378 /* Emit new speculation recovery insn after AFTER based on PATTERN and
1379 initialize its data from EXPR and SEQNO. */
1381 sel_gen_recovery_insn_from_rtx_after (rtx pattern
, expr_t expr
, int seqno
,
1386 gcc_assert (!init_insn_force_unique_p
);
1388 init_insn_force_unique_p
= true;
1389 insn
= sel_gen_insn_from_rtx_after (pattern
, expr
, seqno
, after
);
1390 CANT_MOVE (insn
) = 1;
1391 init_insn_force_unique_p
= false;
1396 /* Emit new insn after AFTER based on EXPR and SEQNO. If VINSN is not NULL,
1397 take it as a new vinsn instead of EXPR's vinsn.
1398 We simplify insns later, after scheduling region in
1399 simplify_changed_insns. */
1401 sel_gen_insn_from_expr_after (expr_t expr
, vinsn_t vinsn
, int seqno
,
1408 emit_expr
= set_insn_init (expr
, vinsn
? vinsn
: EXPR_VINSN (expr
),
1410 insn
= EXPR_INSN_RTX (emit_expr
);
1412 /* The insn may come from the transformation cache, which may hold already
1413 deleted insns, so mark it as not deleted. */
1414 insn
->set_undeleted ();
1416 add_insn_after (insn
, after
, BLOCK_FOR_INSN (insn
));
1418 flags
= INSN_INIT_TODO_SSID
;
1419 if (INSN_LUID (insn
) == 0)
1420 flags
|= INSN_INIT_TODO_LUID
;
1421 sel_init_new_insn (insn
, flags
);
1426 /* Move insn from EXPR after AFTER. */
1428 sel_move_insn (expr_t expr
, int seqno
, insn_t after
)
1430 insn_t insn
= EXPR_INSN_RTX (expr
);
1431 basic_block bb
= BLOCK_FOR_INSN (after
);
1432 insn_t next
= NEXT_INSN (after
);
1434 /* Assert that in move_op we disconnected this insn properly. */
1435 gcc_assert (EXPR_VINSN (INSN_EXPR (insn
)) != NULL
);
1436 SET_PREV_INSN (insn
) = after
;
1437 SET_NEXT_INSN (insn
) = next
;
1439 SET_NEXT_INSN (after
) = insn
;
1440 SET_PREV_INSN (next
) = insn
;
1442 /* Update links from insn to bb and vice versa. */
1443 df_insn_change_bb (insn
, bb
);
1444 if (BB_END (bb
) == after
)
1447 prepare_insn_expr (insn
, seqno
);
1452 /* Functions to work with right-hand sides. */
1454 /* Search for a hash value determined by UID/NEW_VINSN in a sorted vector
1455 VECT and return true when found. Use NEW_VINSN for comparison only when
1456 COMPARE_VINSNS is true. Write to INDP the index on which
1457 the search has stopped, such that inserting the new element at INDP will
1458 retain VECT's sort order. */
1460 find_in_history_vect_1 (vec
<expr_history_def
> vect
,
1461 unsigned uid
, vinsn_t new_vinsn
,
1462 bool compare_vinsns
, int *indp
)
1464 expr_history_def
*arr
;
1465 int i
, j
, len
= vect
.length ();
1473 arr
= vect
.address ();
1478 unsigned auid
= arr
[i
].uid
;
1479 vinsn_t avinsn
= arr
[i
].new_expr_vinsn
;
1482 /* When undoing transformation on a bookkeeping copy, the new vinsn
1483 may not be exactly equal to the one that is saved in the vector.
1484 This is because the insn whose copy we're checking was possibly
1485 substituted itself. */
1486 && (! compare_vinsns
1487 || vinsn_equal_p (avinsn
, new_vinsn
)))
1492 else if (auid
> uid
)
1501 /* Search for a uid of INSN and NEW_VINSN in a sorted vector VECT. Return
1502 the position found or -1, if no such value is in vector.
1503 Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */
1505 find_in_history_vect (vec
<expr_history_def
> vect
, rtx insn
,
1506 vinsn_t new_vinsn
, bool originators_p
)
1510 if (find_in_history_vect_1 (vect
, INSN_UID (insn
), new_vinsn
,
1514 if (INSN_ORIGINATORS (insn
) && originators_p
)
1519 EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn
), 0, uid
, bi
)
1520 if (find_in_history_vect_1 (vect
, uid
, new_vinsn
, false, &ind
))
1527 /* Insert new element in a sorted history vector pointed to by PVECT,
1528 if it is not there already. The element is searched using
1529 UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN and SPEC_DS save
1530 the history of a transformation. */
1532 insert_in_history_vect (vec
<expr_history_def
> *pvect
,
1533 unsigned uid
, enum local_trans_type type
,
1534 vinsn_t old_expr_vinsn
, vinsn_t new_expr_vinsn
,
1537 vec
<expr_history_def
> vect
= *pvect
;
1538 expr_history_def temp
;
1542 res
= find_in_history_vect_1 (vect
, uid
, new_expr_vinsn
, true, &ind
);
1546 expr_history_def
*phist
= &vect
[ind
];
1548 /* It is possible that speculation types of expressions that were
1549 propagated through different paths will be different here. In this
1550 case, merge the status to get the correct check later. */
1551 if (phist
->spec_ds
!= spec_ds
)
1552 phist
->spec_ds
= ds_max_merge (phist
->spec_ds
, spec_ds
);
1557 temp
.old_expr_vinsn
= old_expr_vinsn
;
1558 temp
.new_expr_vinsn
= new_expr_vinsn
;
1559 temp
.spec_ds
= spec_ds
;
1562 vinsn_attach (old_expr_vinsn
);
1563 vinsn_attach (new_expr_vinsn
);
1564 vect
.safe_insert (ind
, temp
);
1568 /* Free history vector PVECT. */
1570 free_history_vect (vec
<expr_history_def
> &pvect
)
1573 expr_history_def
*phist
;
1575 if (! pvect
.exists ())
1578 for (i
= 0; pvect
.iterate (i
, &phist
); i
++)
1580 vinsn_detach (phist
->old_expr_vinsn
);
1581 vinsn_detach (phist
->new_expr_vinsn
);
1587 /* Merge vector FROM to PVECT. */
1589 merge_history_vect (vec
<expr_history_def
> *pvect
,
1590 vec
<expr_history_def
> from
)
1592 expr_history_def
*phist
;
1595 /* We keep this vector sorted. */
1596 for (i
= 0; from
.iterate (i
, &phist
); i
++)
1597 insert_in_history_vect (pvect
, phist
->uid
, phist
->type
,
1598 phist
->old_expr_vinsn
, phist
->new_expr_vinsn
,
1602 /* Compare two vinsns as rhses if possible and as vinsns otherwise. */
1604 vinsn_equal_p (vinsn_t x
, vinsn_t y
)
1606 rtx_equal_p_callback_function repcf
;
1611 if (VINSN_TYPE (x
) != VINSN_TYPE (y
))
1614 if (VINSN_HASH (x
) != VINSN_HASH (y
))
1617 repcf
= targetm
.sched
.skip_rtx_p
? skip_unspecs_callback
: NULL
;
1618 if (VINSN_SEPARABLE_P (x
))
1620 /* Compare RHSes of VINSNs. */
1621 gcc_assert (VINSN_RHS (x
));
1622 gcc_assert (VINSN_RHS (y
));
1624 return rtx_equal_p_cb (VINSN_RHS (x
), VINSN_RHS (y
), repcf
);
1627 return rtx_equal_p_cb (VINSN_PATTERN (x
), VINSN_PATTERN (y
), repcf
);
1631 /* Functions for working with expressions. */
1633 /* Initialize EXPR. */
1635 init_expr (expr_t expr
, vinsn_t vi
, int spec
, int use
, int priority
,
1636 int sched_times
, int orig_bb_index
, ds_t spec_done_ds
,
1637 ds_t spec_to_check_ds
, int orig_sched_cycle
,
1638 vec
<expr_history_def
> history
,
1639 signed char target_available
,
1640 bool was_substituted
, bool was_renamed
, bool needs_spec_check_p
,
1645 EXPR_VINSN (expr
) = vi
;
1646 EXPR_SPEC (expr
) = spec
;
1647 EXPR_USEFULNESS (expr
) = use
;
1648 EXPR_PRIORITY (expr
) = priority
;
1649 EXPR_PRIORITY_ADJ (expr
) = 0;
1650 EXPR_SCHED_TIMES (expr
) = sched_times
;
1651 EXPR_ORIG_BB_INDEX (expr
) = orig_bb_index
;
1652 EXPR_ORIG_SCHED_CYCLE (expr
) = orig_sched_cycle
;
1653 EXPR_SPEC_DONE_DS (expr
) = spec_done_ds
;
1654 EXPR_SPEC_TO_CHECK_DS (expr
) = spec_to_check_ds
;
1656 if (history
.exists ())
1657 EXPR_HISTORY_OF_CHANGES (expr
) = history
;
1659 EXPR_HISTORY_OF_CHANGES (expr
).create (0);
1661 EXPR_TARGET_AVAILABLE (expr
) = target_available
;
1662 EXPR_WAS_SUBSTITUTED (expr
) = was_substituted
;
1663 EXPR_WAS_RENAMED (expr
) = was_renamed
;
1664 EXPR_NEEDS_SPEC_CHECK_P (expr
) = needs_spec_check_p
;
1665 EXPR_CANT_MOVE (expr
) = cant_move
;
1668 /* Make a copy of the expr FROM into the expr TO. */
1670 copy_expr (expr_t to
, expr_t from
)
1672 vec
<expr_history_def
> temp
= vNULL
;
1674 if (EXPR_HISTORY_OF_CHANGES (from
).exists ())
1677 expr_history_def
*phist
;
1679 temp
= EXPR_HISTORY_OF_CHANGES (from
).copy ();
1681 temp
.iterate (i
, &phist
);
1684 vinsn_attach (phist
->old_expr_vinsn
);
1685 vinsn_attach (phist
->new_expr_vinsn
);
1689 init_expr (to
, EXPR_VINSN (from
), EXPR_SPEC (from
),
1690 EXPR_USEFULNESS (from
), EXPR_PRIORITY (from
),
1691 EXPR_SCHED_TIMES (from
), EXPR_ORIG_BB_INDEX (from
),
1692 EXPR_SPEC_DONE_DS (from
), EXPR_SPEC_TO_CHECK_DS (from
),
1693 EXPR_ORIG_SCHED_CYCLE (from
), temp
,
1694 EXPR_TARGET_AVAILABLE (from
), EXPR_WAS_SUBSTITUTED (from
),
1695 EXPR_WAS_RENAMED (from
), EXPR_NEEDS_SPEC_CHECK_P (from
),
1696 EXPR_CANT_MOVE (from
));
1699 /* Same, but the final expr will not ever be in av sets, so don't copy
1700 "uninteresting" data such as bitmap cache. */
1702 copy_expr_onside (expr_t to
, expr_t from
)
1704 init_expr (to
, EXPR_VINSN (from
), EXPR_SPEC (from
), EXPR_USEFULNESS (from
),
1705 EXPR_PRIORITY (from
), EXPR_SCHED_TIMES (from
), 0,
1706 EXPR_SPEC_DONE_DS (from
), EXPR_SPEC_TO_CHECK_DS (from
), 0,
1708 EXPR_TARGET_AVAILABLE (from
), EXPR_WAS_SUBSTITUTED (from
),
1709 EXPR_WAS_RENAMED (from
), EXPR_NEEDS_SPEC_CHECK_P (from
),
1710 EXPR_CANT_MOVE (from
));
1713 /* Prepare the expr of INSN for scheduling. Used when moving insn and when
1714 initializing new insns. */
1716 prepare_insn_expr (insn_t insn
, int seqno
)
1718 expr_t expr
= INSN_EXPR (insn
);
1721 INSN_SEQNO (insn
) = seqno
;
1722 EXPR_ORIG_BB_INDEX (expr
) = BLOCK_NUM (insn
);
1723 EXPR_SPEC (expr
) = 0;
1724 EXPR_ORIG_SCHED_CYCLE (expr
) = 0;
1725 EXPR_WAS_SUBSTITUTED (expr
) = 0;
1726 EXPR_WAS_RENAMED (expr
) = 0;
1727 EXPR_TARGET_AVAILABLE (expr
) = 1;
1728 INSN_LIVE_VALID_P (insn
) = false;
1730 /* ??? If this expression is speculative, make its dependence
1731 as weak as possible. We can filter this expression later
1732 in process_spec_exprs, because we do not distinguish
1733 between the status we got during compute_av_set and the
1734 existing status. To be fixed. */
1735 ds
= EXPR_SPEC_DONE_DS (expr
);
1737 EXPR_SPEC_DONE_DS (expr
) = ds_get_max_dep_weak (ds
);
1739 free_history_vect (EXPR_HISTORY_OF_CHANGES (expr
));
1742 /* Update target_available bits when merging exprs TO and FROM. SPLIT_POINT
1743 is non-null when expressions are merged from different successors at
1746 update_target_availability (expr_t to
, expr_t from
, insn_t split_point
)
1748 if (EXPR_TARGET_AVAILABLE (to
) < 0
1749 || EXPR_TARGET_AVAILABLE (from
) < 0)
1750 EXPR_TARGET_AVAILABLE (to
) = -1;
1753 /* We try to detect the case when one of the expressions
1754 can only be reached through another one. In this case,
1755 we can do better. */
1756 if (split_point
== NULL
)
1760 toind
= EXPR_ORIG_BB_INDEX (to
);
1761 fromind
= EXPR_ORIG_BB_INDEX (from
);
1763 if (toind
&& toind
== fromind
)
1764 /* Do nothing -- everything is done in
1765 merge_with_other_exprs. */
1768 EXPR_TARGET_AVAILABLE (to
) = -1;
1770 else if (EXPR_TARGET_AVAILABLE (from
) == 0
1772 && REG_P (EXPR_LHS (from
))
1773 && REGNO (EXPR_LHS (to
)) != REGNO (EXPR_LHS (from
)))
1774 EXPR_TARGET_AVAILABLE (to
) = -1;
1776 EXPR_TARGET_AVAILABLE (to
) &= EXPR_TARGET_AVAILABLE (from
);
1780 /* Update speculation bits when merging exprs TO and FROM. SPLIT_POINT
1781 is non-null when expressions are merged from different successors at
1784 update_speculative_bits (expr_t to
, expr_t from
, insn_t split_point
)
1786 ds_t old_to_ds
, old_from_ds
;
1788 old_to_ds
= EXPR_SPEC_DONE_DS (to
);
1789 old_from_ds
= EXPR_SPEC_DONE_DS (from
);
1791 EXPR_SPEC_DONE_DS (to
) = ds_max_merge (old_to_ds
, old_from_ds
);
1792 EXPR_SPEC_TO_CHECK_DS (to
) |= EXPR_SPEC_TO_CHECK_DS (from
);
1793 EXPR_NEEDS_SPEC_CHECK_P (to
) |= EXPR_NEEDS_SPEC_CHECK_P (from
);
1795 /* When merging e.g. control & data speculative exprs, or a control
1796 speculative with a control&data speculative one, we really have
1797 to change vinsn too. Also, when speculative status is changed,
1798 we also need to record this as a transformation in expr's history. */
1799 if ((old_to_ds
& SPECULATIVE
) || (old_from_ds
& SPECULATIVE
))
1801 old_to_ds
= ds_get_speculation_types (old_to_ds
);
1802 old_from_ds
= ds_get_speculation_types (old_from_ds
);
1804 if (old_to_ds
!= old_from_ds
)
1808 /* When both expressions are speculative, we need to change
1810 if ((old_to_ds
& SPECULATIVE
) && (old_from_ds
& SPECULATIVE
))
1814 res
= speculate_expr (to
, EXPR_SPEC_DONE_DS (to
));
1815 gcc_assert (res
>= 0);
1818 if (split_point
!= NULL
)
1820 /* Record the change with proper status. */
1821 record_ds
= EXPR_SPEC_DONE_DS (to
) & SPECULATIVE
;
1822 record_ds
&= ~(old_to_ds
& SPECULATIVE
);
1823 record_ds
&= ~(old_from_ds
& SPECULATIVE
);
1825 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to
),
1826 INSN_UID (split_point
), TRANS_SPECULATION
,
1827 EXPR_VINSN (from
), EXPR_VINSN (to
),
1835 /* Merge bits of FROM expr to TO expr. When SPLIT_POINT is not NULL,
1836 this is done along different paths. */
1838 merge_expr_data (expr_t to
, expr_t from
, insn_t split_point
)
1840 /* Choose the maximum of the specs of merged exprs. This is required
1841 for correctness of bookkeeping. */
1842 if (EXPR_SPEC (to
) < EXPR_SPEC (from
))
1843 EXPR_SPEC (to
) = EXPR_SPEC (from
);
1846 EXPR_USEFULNESS (to
) += EXPR_USEFULNESS (from
);
1848 EXPR_USEFULNESS (to
) = MAX (EXPR_USEFULNESS (to
),
1849 EXPR_USEFULNESS (from
));
1851 if (EXPR_PRIORITY (to
) < EXPR_PRIORITY (from
))
1852 EXPR_PRIORITY (to
) = EXPR_PRIORITY (from
);
1854 if (EXPR_SCHED_TIMES (to
) > EXPR_SCHED_TIMES (from
))
1855 EXPR_SCHED_TIMES (to
) = EXPR_SCHED_TIMES (from
);
1857 if (EXPR_ORIG_BB_INDEX (to
) != EXPR_ORIG_BB_INDEX (from
))
1858 EXPR_ORIG_BB_INDEX (to
) = 0;
1860 EXPR_ORIG_SCHED_CYCLE (to
) = MIN (EXPR_ORIG_SCHED_CYCLE (to
),
1861 EXPR_ORIG_SCHED_CYCLE (from
));
1863 EXPR_WAS_SUBSTITUTED (to
) |= EXPR_WAS_SUBSTITUTED (from
);
1864 EXPR_WAS_RENAMED (to
) |= EXPR_WAS_RENAMED (from
);
1865 EXPR_CANT_MOVE (to
) |= EXPR_CANT_MOVE (from
);
1867 merge_history_vect (&EXPR_HISTORY_OF_CHANGES (to
),
1868 EXPR_HISTORY_OF_CHANGES (from
));
1869 update_target_availability (to
, from
, split_point
);
1870 update_speculative_bits (to
, from
, split_point
);
1873 /* Merge bits of FROM expr to TO expr. Vinsns in the exprs should be equal
1874 in terms of vinsn_equal_p. SPLIT_POINT is non-null when expressions
1875 are merged from different successors at a split point. */
1877 merge_expr (expr_t to
, expr_t from
, insn_t split_point
)
1879 vinsn_t to_vi
= EXPR_VINSN (to
);
1880 vinsn_t from_vi
= EXPR_VINSN (from
);
1882 gcc_assert (vinsn_equal_p (to_vi
, from_vi
));
1884 /* Make sure that speculative pattern is propagated into exprs that
1885 have non-speculative one. This will provide us with consistent
1886 speculative bits and speculative patterns inside expr. */
1887 if ((EXPR_SPEC_DONE_DS (from
) != 0
1888 && EXPR_SPEC_DONE_DS (to
) == 0)
1889 /* Do likewise for volatile insns, so that we always retain
1890 the may_trap_p bit on the resulting expression. */
1891 || (VINSN_MAY_TRAP_P (EXPR_VINSN (from
))
1892 && !VINSN_MAY_TRAP_P (EXPR_VINSN (to
))))
1893 change_vinsn_in_expr (to
, EXPR_VINSN (from
));
1895 merge_expr_data (to
, from
, split_point
);
1896 gcc_assert (EXPR_USEFULNESS (to
) <= REG_BR_PROB_BASE
);
1899 /* Clear the information of this EXPR. */
1901 clear_expr (expr_t expr
)
1904 vinsn_detach (EXPR_VINSN (expr
));
1905 EXPR_VINSN (expr
) = NULL
;
1907 free_history_vect (EXPR_HISTORY_OF_CHANGES (expr
));
1910 /* For a given LV_SET, mark EXPR having unavailable target register. */
1912 set_unavailable_target_for_expr (expr_t expr
, regset lv_set
)
1914 if (EXPR_SEPARABLE_P (expr
))
1916 if (REG_P (EXPR_LHS (expr
))
1917 && register_unavailable_p (lv_set
, EXPR_LHS (expr
)))
1919 /* If it's an insn like r1 = use (r1, ...), and it exists in
1920 different forms in each of the av_sets being merged, we can't say
1921 whether original destination register is available or not.
1922 However, this still works if destination register is not used
1923 in the original expression: if the branch at which LV_SET we're
1924 looking here is not actually 'other branch' in sense that same
1925 expression is available through it (but it can't be determined
1926 at computation stage because of transformations on one of the
1927 branches), it still won't affect the availability.
1928 Liveness of a register somewhere on a code motion path means
1929 it's either read somewhere on a codemotion path, live on
1930 'other' branch, live at the point immediately following
1931 the original operation, or is read by the original operation.
1932 The latter case is filtered out in the condition below.
1933 It still doesn't cover the case when register is defined and used
1934 somewhere within the code motion path, and in this case we could
1935 miss a unifying code motion along both branches using a renamed
1936 register, but it won't affect a code correctness since upon
1937 an actual code motion a bookkeeping code would be generated. */
1938 if (register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr
)),
1940 EXPR_TARGET_AVAILABLE (expr
) = -1;
1942 EXPR_TARGET_AVAILABLE (expr
) = false;
1948 reg_set_iterator rsi
;
1950 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (EXPR_VINSN (expr
)),
1952 if (bitmap_bit_p (lv_set
, regno
))
1954 EXPR_TARGET_AVAILABLE (expr
) = false;
1958 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (EXPR_VINSN (expr
)),
1960 if (bitmap_bit_p (lv_set
, regno
))
1962 EXPR_TARGET_AVAILABLE (expr
) = false;
1968 /* Try to make EXPR speculative. Return 1 when EXPR's pattern
1969 or dependence status have changed, 2 when also the target register
1970 became unavailable, 0 if nothing had to be changed. */
1972 speculate_expr (expr_t expr
, ds_t ds
)
1975 rtx_insn
*orig_insn_rtx
;
1977 ds_t target_ds
, current_ds
;
1979 /* Obtain the status we need to put on EXPR. */
1980 target_ds
= (ds
& SPECULATIVE
);
1981 current_ds
= EXPR_SPEC_DONE_DS (expr
);
1982 ds
= ds_full_merge (current_ds
, target_ds
, NULL_RTX
, NULL_RTX
);
1984 orig_insn_rtx
= EXPR_INSN_RTX (expr
);
1986 res
= sched_speculate_insn (orig_insn_rtx
, ds
, &spec_pat
);
1991 EXPR_SPEC_DONE_DS (expr
) = ds
;
1992 return current_ds
!= ds
? 1 : 0;
1996 rtx_insn
*spec_insn_rtx
=
1997 create_insn_rtx_from_pattern (spec_pat
, NULL_RTX
);
1998 vinsn_t spec_vinsn
= create_vinsn_from_insn_rtx (spec_insn_rtx
, false);
2000 change_vinsn_in_expr (expr
, spec_vinsn
);
2001 EXPR_SPEC_DONE_DS (expr
) = ds
;
2002 EXPR_NEEDS_SPEC_CHECK_P (expr
) = true;
2004 /* Do not allow clobbering the address register of speculative
2006 if (register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr
)),
2007 expr_dest_reg (expr
)))
2009 EXPR_TARGET_AVAILABLE (expr
) = false;
2025 /* Return a destination register, if any, of EXPR. */
2027 expr_dest_reg (expr_t expr
)
2029 rtx dest
= VINSN_LHS (EXPR_VINSN (expr
));
2031 if (dest
!= NULL_RTX
&& REG_P (dest
))
2037 /* Returns the REGNO of the R's destination. */
2039 expr_dest_regno (expr_t expr
)
2041 rtx dest
= expr_dest_reg (expr
);
2043 gcc_assert (dest
!= NULL_RTX
);
2044 return REGNO (dest
);
2047 /* For a given LV_SET, mark all expressions in JOIN_SET, but not present in
2048 AV_SET having unavailable target register. */
2050 mark_unavailable_targets (av_set_t join_set
, av_set_t av_set
, regset lv_set
)
2053 av_set_iterator avi
;
2055 FOR_EACH_EXPR (expr
, avi
, join_set
)
2056 if (av_set_lookup (av_set
, EXPR_VINSN (expr
)) == NULL
)
2057 set_unavailable_target_for_expr (expr
, lv_set
);
2061 /* Returns true if REG (at least partially) is present in REGS. */
2063 register_unavailable_p (regset regs
, rtx reg
)
2065 unsigned regno
, end_regno
;
2067 regno
= REGNO (reg
);
2068 if (bitmap_bit_p (regs
, regno
))
2071 end_regno
= END_REGNO (reg
);
2073 while (++regno
< end_regno
)
2074 if (bitmap_bit_p (regs
, regno
))
2080 /* Av set functions. */
2082 /* Add a new element to av set SETP.
2083 Return the element added. */
2085 av_set_add_element (av_set_t
*setp
)
2087 /* Insert at the beginning of the list. */
2092 /* Add EXPR to SETP. */
2094 av_set_add (av_set_t
*setp
, expr_t expr
)
2098 gcc_assert (!INSN_NOP_P (EXPR_INSN_RTX (expr
)));
2099 elem
= av_set_add_element (setp
);
2100 copy_expr (_AV_SET_EXPR (elem
), expr
);
2103 /* Same, but do not copy EXPR. */
2105 av_set_add_nocopy (av_set_t
*setp
, expr_t expr
)
2109 elem
= av_set_add_element (setp
);
2110 *_AV_SET_EXPR (elem
) = *expr
;
2113 /* Remove expr pointed to by IP from the av_set. */
2115 av_set_iter_remove (av_set_iterator
*ip
)
2117 clear_expr (_AV_SET_EXPR (*ip
->lp
));
2118 _list_iter_remove (ip
);
2121 /* Search for an expr in SET, such that it's equivalent to SOUGHT_VINSN in the
2122 sense of vinsn_equal_p function. Return NULL if no such expr is
2123 in SET was found. */
2125 av_set_lookup (av_set_t set
, vinsn_t sought_vinsn
)
2130 FOR_EACH_EXPR (expr
, i
, set
)
2131 if (vinsn_equal_p (EXPR_VINSN (expr
), sought_vinsn
))
2136 /* Same, but also remove the EXPR found. */
2138 av_set_lookup_and_remove (av_set_t
*setp
, vinsn_t sought_vinsn
)
2143 FOR_EACH_EXPR_1 (expr
, i
, setp
)
2144 if (vinsn_equal_p (EXPR_VINSN (expr
), sought_vinsn
))
2146 _list_iter_remove_nofree (&i
);
2152 /* Search for an expr in SET, such that it's equivalent to EXPR in the
2153 sense of vinsn_equal_p function of their vinsns, but not EXPR itself.
2154 Returns NULL if no such expr is in SET was found. */
2156 av_set_lookup_other_equiv_expr (av_set_t set
, expr_t expr
)
2161 FOR_EACH_EXPR (cur_expr
, i
, set
)
2163 if (cur_expr
== expr
)
2165 if (vinsn_equal_p (EXPR_VINSN (cur_expr
), EXPR_VINSN (expr
)))
2172 /* If other expression is already in AVP, remove one of them. */
2174 merge_with_other_exprs (av_set_t
*avp
, av_set_iterator
*ip
, expr_t expr
)
2178 expr2
= av_set_lookup_other_equiv_expr (*avp
, expr
);
2181 /* Reset target availability on merge, since taking it only from one
2182 of the exprs would be controversial for different code. */
2183 EXPR_TARGET_AVAILABLE (expr2
) = -1;
2184 EXPR_USEFULNESS (expr2
) = 0;
2186 merge_expr (expr2
, expr
, NULL
);
2188 /* Fix usefulness as it should be now REG_BR_PROB_BASE. */
2189 EXPR_USEFULNESS (expr2
) = REG_BR_PROB_BASE
;
2191 av_set_iter_remove (ip
);
2198 /* Return true if there is an expr that correlates to VI in SET. */
2200 av_set_is_in_p (av_set_t set
, vinsn_t vi
)
2202 return av_set_lookup (set
, vi
) != NULL
;
2205 /* Return a copy of SET. */
2207 av_set_copy (av_set_t set
)
2211 av_set_t res
= NULL
;
2213 FOR_EACH_EXPR (expr
, i
, set
)
2214 av_set_add (&res
, expr
);
2219 /* Join two av sets that do not have common elements by attaching second set
2220 (pointed to by FROMP) to the end of first set (TO_TAILP must point to
2221 _AV_SET_NEXT of first set's last element). */
2223 join_distinct_sets (av_set_t
*to_tailp
, av_set_t
*fromp
)
2225 gcc_assert (*to_tailp
== NULL
);
2230 /* Makes set pointed to by TO to be the union of TO and FROM. Clear av_set
2231 pointed to by FROMP afterwards. */
2233 av_set_union_and_clear (av_set_t
*top
, av_set_t
*fromp
, insn_t insn
)
2238 /* Delete from TOP all exprs, that present in FROMP. */
2239 FOR_EACH_EXPR_1 (expr1
, i
, top
)
2241 expr_t expr2
= av_set_lookup (*fromp
, EXPR_VINSN (expr1
));
2245 merge_expr (expr2
, expr1
, insn
);
2246 av_set_iter_remove (&i
);
2250 join_distinct_sets (i
.lp
, fromp
);
2253 /* Same as above, but also update availability of target register in
2254 TOP judging by TO_LV_SET and FROM_LV_SET. */
2256 av_set_union_and_live (av_set_t
*top
, av_set_t
*fromp
, regset to_lv_set
,
2257 regset from_lv_set
, insn_t insn
)
2261 av_set_t
*to_tailp
, in_both_set
= NULL
;
2263 /* Delete from TOP all expres, that present in FROMP. */
2264 FOR_EACH_EXPR_1 (expr1
, i
, top
)
2266 expr_t expr2
= av_set_lookup_and_remove (fromp
, EXPR_VINSN (expr1
));
2270 /* It may be that the expressions have different destination
2271 registers, in which case we need to check liveness here. */
2272 if (EXPR_SEPARABLE_P (expr1
))
2274 int regno1
= (REG_P (EXPR_LHS (expr1
))
2275 ? (int) expr_dest_regno (expr1
) : -1);
2276 int regno2
= (REG_P (EXPR_LHS (expr2
))
2277 ? (int) expr_dest_regno (expr2
) : -1);
2279 /* ??? We don't have a way to check restrictions for
2280 *other* register on the current path, we did it only
2281 for the current target register. Give up. */
2282 if (regno1
!= regno2
)
2283 EXPR_TARGET_AVAILABLE (expr2
) = -1;
2285 else if (EXPR_INSN_RTX (expr1
) != EXPR_INSN_RTX (expr2
))
2286 EXPR_TARGET_AVAILABLE (expr2
) = -1;
2288 merge_expr (expr2
, expr1
, insn
);
2289 av_set_add_nocopy (&in_both_set
, expr2
);
2290 av_set_iter_remove (&i
);
2293 /* EXPR1 is present in TOP, but not in FROMP. Check it on
2295 set_unavailable_target_for_expr (expr1
, from_lv_set
);
2299 /* These expressions are not present in TOP. Check liveness
2300 restrictions on TO_LV_SET. */
2301 FOR_EACH_EXPR (expr1
, i
, *fromp
)
2302 set_unavailable_target_for_expr (expr1
, to_lv_set
);
2304 join_distinct_sets (i
.lp
, &in_both_set
);
2305 join_distinct_sets (to_tailp
, fromp
);
2308 /* Clear av_set pointed to by SETP. */
2310 av_set_clear (av_set_t
*setp
)
2315 FOR_EACH_EXPR_1 (expr
, i
, setp
)
2316 av_set_iter_remove (&i
);
2318 gcc_assert (*setp
== NULL
);
2321 /* Leave only one non-speculative element in the SETP. */
2323 av_set_leave_one_nonspec (av_set_t
*setp
)
2327 bool has_one_nonspec
= false;
2329 /* Keep all speculative exprs, and leave one non-speculative
2331 FOR_EACH_EXPR_1 (expr
, i
, setp
)
2333 if (!EXPR_SPEC_DONE_DS (expr
))
2335 if (has_one_nonspec
)
2336 av_set_iter_remove (&i
);
2338 has_one_nonspec
= true;
2343 /* Return the N'th element of the SET. */
2345 av_set_element (av_set_t set
, int n
)
2350 FOR_EACH_EXPR (expr
, i
, set
)
2358 /* Deletes all expressions from AVP that are conditional branches (IFs). */
2360 av_set_substract_cond_branches (av_set_t
*avp
)
2365 FOR_EACH_EXPR_1 (expr
, i
, avp
)
2366 if (vinsn_cond_branch_p (EXPR_VINSN (expr
)))
2367 av_set_iter_remove (&i
);
2370 /* Multiplies usefulness attribute of each member of av-set *AVP by
2371 value PROB / ALL_PROB. */
2373 av_set_split_usefulness (av_set_t av
, int prob
, int all_prob
)
2378 FOR_EACH_EXPR (expr
, i
, av
)
2379 EXPR_USEFULNESS (expr
) = (all_prob
2380 ? (EXPR_USEFULNESS (expr
) * prob
) / all_prob
2384 /* Leave in AVP only those expressions, which are present in AV,
2385 and return it, merging history expressions. */
2387 av_set_code_motion_filter (av_set_t
*avp
, av_set_t av
)
2392 FOR_EACH_EXPR_1 (expr
, i
, avp
)
2393 if ((expr2
= av_set_lookup (av
, EXPR_VINSN (expr
))) == NULL
)
2394 av_set_iter_remove (&i
);
2396 /* When updating av sets in bookkeeping blocks, we can add more insns
2397 there which will be transformed but the upper av sets will not
2398 reflect those transformations. We then fail to undo those
2399 when searching for such insns. So merge the history saved
2400 in the av set of the block we are processing. */
2401 merge_history_vect (&EXPR_HISTORY_OF_CHANGES (expr
),
2402 EXPR_HISTORY_OF_CHANGES (expr2
));
2407 /* Dependence hooks to initialize insn data. */
2409 /* This is used in hooks callable from dependence analysis when initializing
2410 instruction's data. */
2413 /* Where the dependence was found (lhs/rhs). */
2416 /* The actual data object to initialize. */
2419 /* True when the insn should not be made clonable. */
2420 bool force_unique_p
;
2422 /* True when insn should be treated as of type USE, i.e. never renamed. */
2424 } deps_init_id_data
;
2427 /* Setup ID for INSN. FORCE_UNIQUE_P is true when INSN should not be
2430 setup_id_for_insn (idata_t id
, insn_t insn
, bool force_unique_p
)
2434 /* Determine whether INSN could be cloned and return appropriate vinsn type.
2435 That clonable insns which can be separated into lhs and rhs have type SET.
2436 Other clonable insns have type USE. */
2437 type
= GET_CODE (insn
);
2439 /* Only regular insns could be cloned. */
2440 if (type
== INSN
&& !force_unique_p
)
2442 else if (type
== JUMP_INSN
&& simplejump_p (insn
))
2444 else if (type
== DEBUG_INSN
)
2445 type
= !force_unique_p
? USE
: INSN
;
2447 IDATA_TYPE (id
) = type
;
2448 IDATA_REG_SETS (id
) = get_clear_regset_from_pool ();
2449 IDATA_REG_USES (id
) = get_clear_regset_from_pool ();
2450 IDATA_REG_CLOBBERS (id
) = get_clear_regset_from_pool ();
2453 /* Start initializing insn data. */
2455 deps_init_id_start_insn (insn_t insn
)
2457 gcc_assert (deps_init_id_data
.where
== DEPS_IN_NOWHERE
);
2459 setup_id_for_insn (deps_init_id_data
.id
, insn
,
2460 deps_init_id_data
.force_unique_p
);
2461 deps_init_id_data
.where
= DEPS_IN_INSN
;
2464 /* Start initializing lhs data. */
2466 deps_init_id_start_lhs (rtx lhs
)
2468 gcc_assert (deps_init_id_data
.where
== DEPS_IN_INSN
);
2469 gcc_assert (IDATA_LHS (deps_init_id_data
.id
) == NULL
);
2471 if (IDATA_TYPE (deps_init_id_data
.id
) == SET
)
2473 IDATA_LHS (deps_init_id_data
.id
) = lhs
;
2474 deps_init_id_data
.where
= DEPS_IN_LHS
;
2478 /* Finish initializing lhs data. */
2480 deps_init_id_finish_lhs (void)
2482 deps_init_id_data
.where
= DEPS_IN_INSN
;
2485 /* Note a set of REGNO. */
2487 deps_init_id_note_reg_set (int regno
)
2489 haifa_note_reg_set (regno
);
2491 if (deps_init_id_data
.where
== DEPS_IN_RHS
)
2492 deps_init_id_data
.force_use_p
= true;
2494 if (IDATA_TYPE (deps_init_id_data
.id
) != PC
)
2495 SET_REGNO_REG_SET (IDATA_REG_SETS (deps_init_id_data
.id
), regno
);
2498 /* Make instructions that set stack registers to be ineligible for
2499 renaming to avoid issues with find_used_regs. */
2500 if (IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
))
2501 deps_init_id_data
.force_use_p
= true;
2505 /* Note a clobber of REGNO. */
2507 deps_init_id_note_reg_clobber (int regno
)
2509 haifa_note_reg_clobber (regno
);
2511 if (deps_init_id_data
.where
== DEPS_IN_RHS
)
2512 deps_init_id_data
.force_use_p
= true;
2514 if (IDATA_TYPE (deps_init_id_data
.id
) != PC
)
2515 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (deps_init_id_data
.id
), regno
);
2518 /* Note a use of REGNO. */
2520 deps_init_id_note_reg_use (int regno
)
2522 haifa_note_reg_use (regno
);
2524 if (IDATA_TYPE (deps_init_id_data
.id
) != PC
)
2525 SET_REGNO_REG_SET (IDATA_REG_USES (deps_init_id_data
.id
), regno
);
2528 /* Start initializing rhs data. */
2530 deps_init_id_start_rhs (rtx rhs
)
2532 gcc_assert (deps_init_id_data
.where
== DEPS_IN_INSN
);
2534 /* And there was no sel_deps_reset_to_insn (). */
2535 if (IDATA_LHS (deps_init_id_data
.id
) != NULL
)
2537 IDATA_RHS (deps_init_id_data
.id
) = rhs
;
2538 deps_init_id_data
.where
= DEPS_IN_RHS
;
2542 /* Finish initializing rhs data. */
2544 deps_init_id_finish_rhs (void)
2546 gcc_assert (deps_init_id_data
.where
== DEPS_IN_RHS
2547 || deps_init_id_data
.where
== DEPS_IN_INSN
);
2548 deps_init_id_data
.where
= DEPS_IN_INSN
;
2551 /* Finish initializing insn data. */
2553 deps_init_id_finish_insn (void)
2555 gcc_assert (deps_init_id_data
.where
== DEPS_IN_INSN
);
2557 if (IDATA_TYPE (deps_init_id_data
.id
) == SET
)
2559 rtx lhs
= IDATA_LHS (deps_init_id_data
.id
);
2560 rtx rhs
= IDATA_RHS (deps_init_id_data
.id
);
2562 if (lhs
== NULL
|| rhs
== NULL
|| !lhs_and_rhs_separable_p (lhs
, rhs
)
2563 || deps_init_id_data
.force_use_p
)
2565 /* This should be a USE, as we don't want to schedule its RHS
2566 separately. However, we still want to have them recorded
2567 for the purposes of substitution. That's why we don't
2568 simply call downgrade_to_use () here. */
2569 gcc_assert (IDATA_TYPE (deps_init_id_data
.id
) == SET
);
2570 gcc_assert (!lhs
== !rhs
);
2572 IDATA_TYPE (deps_init_id_data
.id
) = USE
;
2576 deps_init_id_data
.where
= DEPS_IN_NOWHERE
;
2579 /* This is dependence info used for initializing insn's data. */
2580 static struct sched_deps_info_def deps_init_id_sched_deps_info
;
2582 /* This initializes most of the static part of the above structure. */
2583 static const struct sched_deps_info_def const_deps_init_id_sched_deps_info
=
2587 deps_init_id_start_insn
,
2588 deps_init_id_finish_insn
,
2589 deps_init_id_start_lhs
,
2590 deps_init_id_finish_lhs
,
2591 deps_init_id_start_rhs
,
2592 deps_init_id_finish_rhs
,
2593 deps_init_id_note_reg_set
,
2594 deps_init_id_note_reg_clobber
,
2595 deps_init_id_note_reg_use
,
2596 NULL
, /* note_mem_dep */
2597 NULL
, /* note_dep */
2600 0, /* use_deps_list */
2601 0 /* generate_spec_deps */
2604 /* Initialize INSN's lhs and rhs in ID. When FORCE_UNIQUE_P is true,
2605 we don't actually need information about lhs and rhs. */
2607 setup_id_lhs_rhs (idata_t id
, insn_t insn
, bool force_unique_p
)
2609 rtx pat
= PATTERN (insn
);
2611 if (NONJUMP_INSN_P (insn
)
2612 && GET_CODE (pat
) == SET
2615 IDATA_RHS (id
) = SET_SRC (pat
);
2616 IDATA_LHS (id
) = SET_DEST (pat
);
2619 IDATA_LHS (id
) = IDATA_RHS (id
) = NULL
;
2622 /* Possibly downgrade INSN to USE. */
2624 maybe_downgrade_id_to_use (idata_t id
, insn_t insn
)
2626 bool must_be_use
= false;
2628 rtx lhs
= IDATA_LHS (id
);
2629 rtx rhs
= IDATA_RHS (id
);
2631 /* We downgrade only SETs. */
2632 if (IDATA_TYPE (id
) != SET
)
2635 if (!lhs
|| !lhs_and_rhs_separable_p (lhs
, rhs
))
2637 IDATA_TYPE (id
) = USE
;
2641 FOR_EACH_INSN_DEF (def
, insn
)
2643 if (DF_REF_INSN (def
)
2644 && DF_REF_FLAGS_IS_SET (def
, DF_REF_PRE_POST_MODIFY
)
2645 && loc_mentioned_in_p (DF_REF_LOC (def
), IDATA_RHS (id
)))
2652 /* Make instructions that set stack registers to be ineligible for
2653 renaming to avoid issues with find_used_regs. */
2654 if (IN_RANGE (DF_REF_REGNO (def
), FIRST_STACK_REG
, LAST_STACK_REG
))
2663 IDATA_TYPE (id
) = USE
;
2666 /* Setup register sets describing INSN in ID. */
2668 setup_id_reg_sets (idata_t id
, insn_t insn
)
2670 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2672 regset tmp
= get_clear_regset_from_pool ();
2674 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
2676 unsigned int regno
= DF_REF_REGNO (def
);
2678 /* Post modifies are treated like clobbers by sched-deps.c. */
2679 if (DF_REF_FLAGS_IS_SET (def
, (DF_REF_MUST_CLOBBER
2680 | DF_REF_PRE_POST_MODIFY
)))
2681 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (id
), regno
);
2682 else if (! DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
2684 SET_REGNO_REG_SET (IDATA_REG_SETS (id
), regno
);
2687 /* For stack registers, treat writes to them as writes
2688 to the first one to be consistent with sched-deps.c. */
2689 if (IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
))
2690 SET_REGNO_REG_SET (IDATA_REG_SETS (id
), FIRST_STACK_REG
);
2693 /* Mark special refs that generate read/write def pair. */
2694 if (DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
)
2695 || regno
== STACK_POINTER_REGNUM
)
2696 bitmap_set_bit (tmp
, regno
);
2699 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
2701 unsigned int regno
= DF_REF_REGNO (use
);
2703 /* When these refs are met for the first time, skip them, as
2704 these uses are just counterparts of some defs. */
2705 if (bitmap_bit_p (tmp
, regno
))
2706 bitmap_clear_bit (tmp
, regno
);
2707 else if (! DF_REF_FLAGS_IS_SET (use
, DF_REF_CALL_STACK_USAGE
))
2709 SET_REGNO_REG_SET (IDATA_REG_USES (id
), regno
);
2712 /* For stack registers, treat reads from them as reads from
2713 the first one to be consistent with sched-deps.c. */
2714 if (IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
))
2715 SET_REGNO_REG_SET (IDATA_REG_USES (id
), FIRST_STACK_REG
);
2720 return_regset_to_pool (tmp
);
2723 /* Initialize instruction data for INSN in ID using DF's data. */
2725 init_id_from_df (idata_t id
, insn_t insn
, bool force_unique_p
)
2727 gcc_assert (DF_INSN_UID_SAFE_GET (INSN_UID (insn
)) != NULL
);
2729 setup_id_for_insn (id
, insn
, force_unique_p
);
2730 setup_id_lhs_rhs (id
, insn
, force_unique_p
);
2732 if (INSN_NOP_P (insn
))
2735 maybe_downgrade_id_to_use (id
, insn
);
2736 setup_id_reg_sets (id
, insn
);
2739 /* Initialize instruction data for INSN in ID. */
2741 deps_init_id (idata_t id
, insn_t insn
, bool force_unique_p
)
2743 struct deps_desc _dc
, *dc
= &_dc
;
2745 deps_init_id_data
.where
= DEPS_IN_NOWHERE
;
2746 deps_init_id_data
.id
= id
;
2747 deps_init_id_data
.force_unique_p
= force_unique_p
;
2748 deps_init_id_data
.force_use_p
= false;
2750 init_deps (dc
, false);
2752 memcpy (&deps_init_id_sched_deps_info
,
2753 &const_deps_init_id_sched_deps_info
,
2754 sizeof (deps_init_id_sched_deps_info
));
2756 if (spec_info
!= NULL
)
2757 deps_init_id_sched_deps_info
.generate_spec_deps
= 1;
2759 sched_deps_info
= &deps_init_id_sched_deps_info
;
2761 deps_analyze_insn (dc
, insn
);
2765 deps_init_id_data
.id
= NULL
;
2769 struct sched_scan_info_def
2771 /* This hook notifies scheduler frontend to extend its internal per basic
2772 block data structures. This hook should be called once before a series of
2773 calls to bb_init (). */
2774 void (*extend_bb
) (void);
2776 /* This hook makes scheduler frontend to initialize its internal data
2777 structures for the passed basic block. */
2778 void (*init_bb
) (basic_block
);
2780 /* This hook notifies scheduler frontend to extend its internal per insn data
2781 structures. This hook should be called once before a series of calls to
2783 void (*extend_insn
) (void);
2785 /* This hook makes scheduler frontend to initialize its internal data
2786 structures for the passed insn. */
2787 void (*init_insn
) (insn_t
);
2790 /* A driver function to add a set of basic blocks (BBS) to the
2791 scheduling region. */
2793 sched_scan (const struct sched_scan_info_def
*ssi
, bb_vec_t bbs
)
2802 FOR_EACH_VEC_ELT (bbs
, i
, bb
)
2805 if (ssi
->extend_insn
)
2806 ssi
->extend_insn ();
2809 FOR_EACH_VEC_ELT (bbs
, i
, bb
)
2813 FOR_BB_INSNS (bb
, insn
)
2814 ssi
->init_insn (insn
);
2818 /* Implement hooks for collecting fundamental insn properties like if insn is
2819 an ASM or is within a SCHED_GROUP. */
2821 /* True when a "one-time init" data for INSN was already inited. */
2823 first_time_insn_init (insn_t insn
)
2825 return INSN_LIVE (insn
) == NULL
;
2828 /* Hash an entry in a transformed_insns hashtable. */
2830 hash_transformed_insns (const void *p
)
2832 return VINSN_HASH_RTX (((const struct transformed_insns
*) p
)->vinsn_old
);
2835 /* Compare the entries in a transformed_insns hashtable. */
2837 eq_transformed_insns (const void *p
, const void *q
)
2840 VINSN_INSN_RTX (((const struct transformed_insns
*) p
)->vinsn_old
);
2842 VINSN_INSN_RTX (((const struct transformed_insns
*) q
)->vinsn_old
);
2844 if (INSN_UID (i1
) == INSN_UID (i2
))
2846 return rtx_equal_p (PATTERN (i1
), PATTERN (i2
));
2849 /* Free an entry in a transformed_insns hashtable. */
2851 free_transformed_insns (void *p
)
2853 struct transformed_insns
*pti
= (struct transformed_insns
*) p
;
2855 vinsn_detach (pti
->vinsn_old
);
2856 vinsn_detach (pti
->vinsn_new
);
2860 /* Init the s_i_d data for INSN which should be inited just once, when
2861 we first see the insn. */
2863 init_first_time_insn_data (insn_t insn
)
2865 /* This should not be set if this is the first time we init data for
2867 gcc_assert (first_time_insn_init (insn
));
2869 /* These are needed for nops too. */
2870 INSN_LIVE (insn
) = get_regset_from_pool ();
2871 INSN_LIVE_VALID_P (insn
) = false;
2873 if (!INSN_NOP_P (insn
))
2875 INSN_ANALYZED_DEPS (insn
) = BITMAP_ALLOC (NULL
);
2876 INSN_FOUND_DEPS (insn
) = BITMAP_ALLOC (NULL
);
2877 INSN_TRANSFORMED_INSNS (insn
)
2878 = htab_create (16, hash_transformed_insns
,
2879 eq_transformed_insns
, free_transformed_insns
);
2880 init_deps (&INSN_DEPS_CONTEXT (insn
), true);
2884 /* Free almost all above data for INSN that is scheduled already.
2885 Used for extra-large basic blocks. */
2887 free_data_for_scheduled_insn (insn_t insn
)
2889 gcc_assert (! first_time_insn_init (insn
));
2891 if (! INSN_ANALYZED_DEPS (insn
))
2894 BITMAP_FREE (INSN_ANALYZED_DEPS (insn
));
2895 BITMAP_FREE (INSN_FOUND_DEPS (insn
));
2896 htab_delete (INSN_TRANSFORMED_INSNS (insn
));
2898 /* This is allocated only for bookkeeping insns. */
2899 if (INSN_ORIGINATORS (insn
))
2900 BITMAP_FREE (INSN_ORIGINATORS (insn
));
2901 free_deps (&INSN_DEPS_CONTEXT (insn
));
2903 INSN_ANALYZED_DEPS (insn
) = NULL
;
2905 /* Clear the readonly flag so we would ICE when trying to recalculate
2906 the deps context (as we believe that it should not happen). */
2907 (&INSN_DEPS_CONTEXT (insn
))->readonly
= 0;
2910 /* Free the same data as above for INSN. */
2912 free_first_time_insn_data (insn_t insn
)
2914 gcc_assert (! first_time_insn_init (insn
));
2916 free_data_for_scheduled_insn (insn
);
2917 return_regset_to_pool (INSN_LIVE (insn
));
2918 INSN_LIVE (insn
) = NULL
;
2919 INSN_LIVE_VALID_P (insn
) = false;
2922 /* Initialize region-scope data structures for basic blocks. */
2924 init_global_and_expr_for_bb (basic_block bb
)
2926 if (sel_bb_empty_p (bb
))
2929 invalidate_av_set (bb
);
2932 /* Data for global dependency analysis (to initialize CANT_MOVE and
2936 /* Previous insn. */
2940 /* Determine if INSN is in the sched_group, is an asm or should not be
2941 cloned. After that initialize its expr. */
2943 init_global_and_expr_for_insn (insn_t insn
)
2948 if (NOTE_INSN_BASIC_BLOCK_P (insn
))
2950 init_global_data
.prev_insn
= NULL
;
2954 gcc_assert (INSN_P (insn
));
2956 if (SCHED_GROUP_P (insn
))
2957 /* Setup a sched_group. */
2959 insn_t prev_insn
= init_global_data
.prev_insn
;
2962 INSN_SCHED_NEXT (prev_insn
) = insn
;
2964 init_global_data
.prev_insn
= insn
;
2967 init_global_data
.prev_insn
= NULL
;
2969 if (GET_CODE (PATTERN (insn
)) == ASM_INPUT
2970 || asm_noperands (PATTERN (insn
)) >= 0)
2971 /* Mark INSN as an asm. */
2972 INSN_ASM_P (insn
) = true;
2975 bool force_unique_p
;
2978 /* Certain instructions cannot be cloned, and frame related insns and
2979 the insn adjacent to NOTE_INSN_EPILOGUE_BEG cannot be moved out of
2981 if (prologue_epilogue_contains (insn
))
2983 if (RTX_FRAME_RELATED_P (insn
))
2984 CANT_MOVE (insn
) = 1;
2988 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
2989 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
2990 && ((enum insn_note
) INTVAL (XEXP (note
, 0))
2991 == NOTE_INSN_EPILOGUE_BEG
))
2993 CANT_MOVE (insn
) = 1;
2997 force_unique_p
= true;
3000 if (CANT_MOVE (insn
)
3001 || INSN_ASM_P (insn
)
3002 || SCHED_GROUP_P (insn
)
3004 /* Exception handling insns are always unique. */
3005 || (cfun
->can_throw_non_call_exceptions
&& can_throw_internal (insn
))
3006 /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
3007 || control_flow_insn_p (insn
)
3008 || volatile_insn_p (PATTERN (insn
))
3009 || (targetm
.cannot_copy_insn_p
3010 && targetm
.cannot_copy_insn_p (insn
)))
3011 force_unique_p
= true;
3013 force_unique_p
= false;
3015 if (targetm
.sched
.get_insn_spec_ds
)
3017 spec_done_ds
= targetm
.sched
.get_insn_spec_ds (insn
);
3018 spec_done_ds
= ds_get_max_dep_weak (spec_done_ds
);
3023 /* Initialize INSN's expr. */
3024 init_expr (INSN_EXPR (insn
), vinsn_create (insn
, force_unique_p
), 0,
3025 REG_BR_PROB_BASE
, INSN_PRIORITY (insn
), 0, BLOCK_NUM (insn
),
3026 spec_done_ds
, 0, 0, vNULL
, true,
3027 false, false, false, CANT_MOVE (insn
));
3030 init_first_time_insn_data (insn
);
3033 /* Scan the region and initialize instruction data for basic blocks BBS. */
3035 sel_init_global_and_expr (bb_vec_t bbs
)
3037 /* ??? It would be nice to implement push / pop scheme for sched_infos. */
3038 const struct sched_scan_info_def ssi
=
3040 NULL
, /* extend_bb */
3041 init_global_and_expr_for_bb
, /* init_bb */
3042 extend_insn_data
, /* extend_insn */
3043 init_global_and_expr_for_insn
/* init_insn */
3046 sched_scan (&ssi
, bbs
);
3049 /* Finalize region-scope data structures for basic blocks. */
3051 finish_global_and_expr_for_bb (basic_block bb
)
3053 av_set_clear (&BB_AV_SET (bb
));
3054 BB_AV_LEVEL (bb
) = 0;
3057 /* Finalize INSN's data. */
3059 finish_global_and_expr_insn (insn_t insn
)
3061 if (LABEL_P (insn
) || NOTE_INSN_BASIC_BLOCK_P (insn
))
3064 gcc_assert (INSN_P (insn
));
3066 if (INSN_LUID (insn
) > 0)
3068 free_first_time_insn_data (insn
);
3069 INSN_WS_LEVEL (insn
) = 0;
3070 CANT_MOVE (insn
) = 0;
3072 /* We can no longer assert this, as vinsns of this insn could be
3073 easily live in other insn's caches. This should be changed to
3074 a counter-like approach among all vinsns. */
3075 gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn
)) == 1);
3076 clear_expr (INSN_EXPR (insn
));
3080 /* Finalize per instruction data for the whole region. */
3082 sel_finish_global_and_expr (void)
3088 bbs
.create (current_nr_blocks
);
3090 for (i
= 0; i
< current_nr_blocks
; i
++)
3091 bbs
.quick_push (BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (i
)));
3093 /* Clear AV_SETs and INSN_EXPRs. */
3095 const struct sched_scan_info_def ssi
=
3097 NULL
, /* extend_bb */
3098 finish_global_and_expr_for_bb
, /* init_bb */
3099 NULL
, /* extend_insn */
3100 finish_global_and_expr_insn
/* init_insn */
3103 sched_scan (&ssi
, bbs
);
3113 /* In the below hooks, we merely calculate whether or not a dependence
3114 exists, and in what part of insn. However, we will need more data
3115 when we'll start caching dependence requests. */
3117 /* Container to hold information for dependency analysis. */
3122 /* A variable to track which part of rtx we are scanning in
3123 sched-deps.c: sched_analyze_insn (). */
3126 /* Current producer. */
3129 /* Current consumer. */
3132 /* Is SEL_DEPS_HAS_DEP_P[DEPS_IN_X] is true, then X has a dependence.
3133 X is from { INSN, LHS, RHS }. */
3134 ds_t has_dep_p
[DEPS_IN_NOWHERE
];
3135 } has_dependence_data
;
3137 /* Start analyzing dependencies of INSN. */
3139 has_dependence_start_insn (insn_t insn ATTRIBUTE_UNUSED
)
3141 gcc_assert (has_dependence_data
.where
== DEPS_IN_NOWHERE
);
3143 has_dependence_data
.where
= DEPS_IN_INSN
;
3146 /* Finish analyzing dependencies of an insn. */
3148 has_dependence_finish_insn (void)
3150 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3152 has_dependence_data
.where
= DEPS_IN_NOWHERE
;
3155 /* Start analyzing dependencies of LHS. */
3157 has_dependence_start_lhs (rtx lhs ATTRIBUTE_UNUSED
)
3159 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3161 if (VINSN_LHS (has_dependence_data
.con
) != NULL
)
3162 has_dependence_data
.where
= DEPS_IN_LHS
;
3165 /* Finish analyzing dependencies of an lhs. */
3167 has_dependence_finish_lhs (void)
3169 has_dependence_data
.where
= DEPS_IN_INSN
;
3172 /* Start analyzing dependencies of RHS. */
3174 has_dependence_start_rhs (rtx rhs ATTRIBUTE_UNUSED
)
3176 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3178 if (VINSN_RHS (has_dependence_data
.con
) != NULL
)
3179 has_dependence_data
.where
= DEPS_IN_RHS
;
3182 /* Start analyzing dependencies of an rhs. */
3184 has_dependence_finish_rhs (void)
3186 gcc_assert (has_dependence_data
.where
== DEPS_IN_RHS
3187 || has_dependence_data
.where
== DEPS_IN_INSN
);
3189 has_dependence_data
.where
= DEPS_IN_INSN
;
3192 /* Note a set of REGNO. */
3194 has_dependence_note_reg_set (int regno
)
3196 struct deps_reg
*reg_last
= &has_dependence_data
.dc
->reg_last
[regno
];
3198 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3200 (has_dependence_data
.con
)))
3202 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3204 if (reg_last
->sets
!= NULL
3205 || reg_last
->clobbers
!= NULL
)
3206 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_OUTPUT
;
3208 if (reg_last
->uses
|| reg_last
->implicit_sets
)
3209 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_ANTI
;
3213 /* Note a clobber of REGNO. */
3215 has_dependence_note_reg_clobber (int regno
)
3217 struct deps_reg
*reg_last
= &has_dependence_data
.dc
->reg_last
[regno
];
3219 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3221 (has_dependence_data
.con
)))
3223 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3226 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_OUTPUT
;
3228 if (reg_last
->uses
|| reg_last
->implicit_sets
)
3229 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_ANTI
;
3233 /* Note a use of REGNO. */
3235 has_dependence_note_reg_use (int regno
)
3237 struct deps_reg
*reg_last
= &has_dependence_data
.dc
->reg_last
[regno
];
3239 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3241 (has_dependence_data
.con
)))
3243 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3246 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_TRUE
;
3248 if (reg_last
->clobbers
|| reg_last
->implicit_sets
)
3249 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_ANTI
;
3251 /* Merge BE_IN_SPEC bits into *DSP when the dependency producer
3252 is actually a check insn. We need to do this for any register
3253 read-read dependency with the check unless we track properly
3254 all registers written by BE_IN_SPEC-speculated insns, as
3255 we don't have explicit dependence lists. See PR 53975. */
3258 ds_t pro_spec_checked_ds
;
3260 pro_spec_checked_ds
= INSN_SPEC_CHECKED_DS (has_dependence_data
.pro
);
3261 pro_spec_checked_ds
= ds_get_max_dep_weak (pro_spec_checked_ds
);
3263 if (pro_spec_checked_ds
!= 0)
3264 *dsp
= ds_full_merge (*dsp
, pro_spec_checked_ds
,
3265 NULL_RTX
, NULL_RTX
);
3270 /* Note a memory dependence. */
3272 has_dependence_note_mem_dep (rtx mem ATTRIBUTE_UNUSED
,
3273 rtx pending_mem ATTRIBUTE_UNUSED
,
3274 insn_t pending_insn ATTRIBUTE_UNUSED
,
3275 ds_t ds ATTRIBUTE_UNUSED
)
3277 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3278 VINSN_INSN_RTX (has_dependence_data
.con
)))
3280 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3282 *dsp
= ds_full_merge (ds
, *dsp
, pending_mem
, mem
);
3286 /* Note a dependence. */
3288 has_dependence_note_dep (insn_t pro ATTRIBUTE_UNUSED
,
3289 ds_t ds ATTRIBUTE_UNUSED
)
3291 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3292 VINSN_INSN_RTX (has_dependence_data
.con
)))
3294 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3296 *dsp
= ds_full_merge (ds
, *dsp
, NULL_RTX
, NULL_RTX
);
3300 /* Mark the insn as having a hard dependence that prevents speculation. */
3302 sel_mark_hard_insn (rtx insn
)
3306 /* Only work when we're in has_dependence_p mode.
3307 ??? This is a hack, this should actually be a hook. */
3308 if (!has_dependence_data
.dc
|| !has_dependence_data
.pro
)
3311 gcc_assert (insn
== VINSN_INSN_RTX (has_dependence_data
.con
));
3312 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3314 for (i
= 0; i
< DEPS_IN_NOWHERE
; i
++)
3315 has_dependence_data
.has_dep_p
[i
] &= ~SPECULATIVE
;
3318 /* This structure holds the hooks for the dependency analysis used when
3319 actually processing dependencies in the scheduler. */
3320 static struct sched_deps_info_def has_dependence_sched_deps_info
;
3322 /* This initializes most of the fields of the above structure. */
3323 static const struct sched_deps_info_def const_has_dependence_sched_deps_info
=
3327 has_dependence_start_insn
,
3328 has_dependence_finish_insn
,
3329 has_dependence_start_lhs
,
3330 has_dependence_finish_lhs
,
3331 has_dependence_start_rhs
,
3332 has_dependence_finish_rhs
,
3333 has_dependence_note_reg_set
,
3334 has_dependence_note_reg_clobber
,
3335 has_dependence_note_reg_use
,
3336 has_dependence_note_mem_dep
,
3337 has_dependence_note_dep
,
3340 0, /* use_deps_list */
3341 0 /* generate_spec_deps */
3344 /* Initialize has_dependence_sched_deps_info with extra spec field. */
3346 setup_has_dependence_sched_deps_info (void)
3348 memcpy (&has_dependence_sched_deps_info
,
3349 &const_has_dependence_sched_deps_info
,
3350 sizeof (has_dependence_sched_deps_info
));
3352 if (spec_info
!= NULL
)
3353 has_dependence_sched_deps_info
.generate_spec_deps
= 1;
3355 sched_deps_info
= &has_dependence_sched_deps_info
;
3358 /* Remove all dependences found and recorded in has_dependence_data array. */
3360 sel_clear_has_dependence (void)
3364 for (i
= 0; i
< DEPS_IN_NOWHERE
; i
++)
3365 has_dependence_data
.has_dep_p
[i
] = 0;
3368 /* Return nonzero if EXPR has is dependent upon PRED. Return the pointer
3369 to the dependence information array in HAS_DEP_PP. */
3371 has_dependence_p (expr_t expr
, insn_t pred
, ds_t
**has_dep_pp
)
3375 struct deps_desc
*dc
;
3377 if (INSN_SIMPLEJUMP_P (pred
))
3378 /* Unconditional jump is just a transfer of control flow.
3382 dc
= &INSN_DEPS_CONTEXT (pred
);
3384 /* We init this field lazily. */
3385 if (dc
->reg_last
== NULL
)
3386 init_deps_reg_last (dc
);
3390 has_dependence_data
.pro
= NULL
;
3391 /* Initialize empty dep context with information about PRED. */
3392 advance_deps_context (dc
, pred
);
3396 has_dependence_data
.where
= DEPS_IN_NOWHERE
;
3397 has_dependence_data
.pro
= pred
;
3398 has_dependence_data
.con
= EXPR_VINSN (expr
);
3399 has_dependence_data
.dc
= dc
;
3401 sel_clear_has_dependence ();
3403 /* Now catch all dependencies that would be generated between PRED and
3405 setup_has_dependence_sched_deps_info ();
3406 deps_analyze_insn (dc
, EXPR_INSN_RTX (expr
));
3407 has_dependence_data
.dc
= NULL
;
3409 /* When a barrier was found, set DEPS_IN_INSN bits. */
3410 if (dc
->last_reg_pending_barrier
== TRUE_BARRIER
)
3411 has_dependence_data
.has_dep_p
[DEPS_IN_INSN
] = DEP_TRUE
;
3412 else if (dc
->last_reg_pending_barrier
== MOVE_BARRIER
)
3413 has_dependence_data
.has_dep_p
[DEPS_IN_INSN
] = DEP_ANTI
;
3415 /* Do not allow stores to memory to move through checks. Currently
3416 we don't move this to sched-deps.c as the check doesn't have
3417 obvious places to which this dependence can be attached.
3418 FIMXE: this should go to a hook. */
3420 && MEM_P (EXPR_LHS (expr
))
3421 && sel_insn_is_speculation_check (pred
))
3422 has_dependence_data
.has_dep_p
[DEPS_IN_INSN
] = DEP_ANTI
;
3424 *has_dep_pp
= has_dependence_data
.has_dep_p
;
3426 for (i
= 0; i
< DEPS_IN_NOWHERE
; i
++)
3427 ds
= ds_full_merge (ds
, has_dependence_data
.has_dep_p
[i
],
3428 NULL_RTX
, NULL_RTX
);
3434 /* Dependence hooks implementation that checks dependence latency constraints
3435 on the insns being scheduled. The entry point for these routines is
3436 tick_check_p predicate. */
3440 /* An expr we are currently checking. */
3443 /* A minimal cycle for its scheduling. */
3446 /* Whether we have seen a true dependence while checking. */
3447 bool seen_true_dep_p
;
3450 /* Update minimal scheduling cycle for tick_check_insn given that it depends
3451 on PRO with status DS and weight DW. */
3453 tick_check_dep_with_dw (insn_t pro_insn
, ds_t ds
, dw_t dw
)
3455 expr_t con_expr
= tick_check_data
.expr
;
3456 insn_t con_insn
= EXPR_INSN_RTX (con_expr
);
3458 if (con_insn
!= pro_insn
)
3463 if (/* PROducer was removed from above due to pipelining. */
3464 !INSN_IN_STREAM_P (pro_insn
)
3465 /* Or PROducer was originally on the next iteration regarding the
3467 || (INSN_SCHED_TIMES (pro_insn
)
3468 - EXPR_SCHED_TIMES (con_expr
)) > 1)
3469 /* Don't count this dependence. */
3473 if (dt
== REG_DEP_TRUE
)
3474 tick_check_data
.seen_true_dep_p
= true;
3476 gcc_assert (INSN_SCHED_CYCLE (pro_insn
) > 0);
3479 dep_def _dep
, *dep
= &_dep
;
3481 init_dep (dep
, pro_insn
, con_insn
, dt
);
3483 tick
= INSN_SCHED_CYCLE (pro_insn
) + dep_cost_1 (dep
, dw
);
3486 /* When there are several kinds of dependencies between pro and con,
3487 only REG_DEP_TRUE should be taken into account. */
3488 if (tick
> tick_check_data
.cycle
3489 && (dt
== REG_DEP_TRUE
|| !tick_check_data
.seen_true_dep_p
))
3490 tick_check_data
.cycle
= tick
;
3494 /* An implementation of note_dep hook. */
3496 tick_check_note_dep (insn_t pro
, ds_t ds
)
3498 tick_check_dep_with_dw (pro
, ds
, 0);
3501 /* An implementation of note_mem_dep hook. */
3503 tick_check_note_mem_dep (rtx mem1
, rtx mem2
, insn_t pro
, ds_t ds
)
3507 dw
= (ds_to_dt (ds
) == REG_DEP_TRUE
3508 ? estimate_dep_weak (mem1
, mem2
)
3511 tick_check_dep_with_dw (pro
, ds
, dw
);
3514 /* This structure contains hooks for dependence analysis used when determining
3515 whether an insn is ready for scheduling. */
3516 static struct sched_deps_info_def tick_check_sched_deps_info
=
3527 haifa_note_reg_clobber
,
3529 tick_check_note_mem_dep
,
3530 tick_check_note_dep
,
3535 /* Estimate number of cycles from the current cycle of FENCE until EXPR can be
3536 scheduled. Return 0 if all data from producers in DC is ready. */
3538 tick_check_p (expr_t expr
, deps_t dc
, fence_t fence
)
3541 /* Initialize variables. */
3542 tick_check_data
.expr
= expr
;
3543 tick_check_data
.cycle
= 0;
3544 tick_check_data
.seen_true_dep_p
= false;
3545 sched_deps_info
= &tick_check_sched_deps_info
;
3547 gcc_assert (!dc
->readonly
);
3549 deps_analyze_insn (dc
, EXPR_INSN_RTX (expr
));
3552 cycles_left
= tick_check_data
.cycle
- FENCE_CYCLE (fence
);
3554 return cycles_left
>= 0 ? cycles_left
: 0;
3558 /* Functions to work with insns. */
3560 /* Returns true if LHS of INSN is the same as DEST of an insn
3563 lhs_of_insn_equals_to_dest_p (insn_t insn
, rtx dest
)
3565 rtx lhs
= INSN_LHS (insn
);
3567 if (lhs
== NULL
|| dest
== NULL
)
3570 return rtx_equal_p (lhs
, dest
);
3573 /* Return s_i_d entry of INSN. Callable from debugger. */
3575 insn_sid (insn_t insn
)
3580 /* True when INSN is a speculative check. We can tell this by looking
3581 at the data structures of the selective scheduler, not by examining
3584 sel_insn_is_speculation_check (rtx insn
)
3586 return s_i_d
.exists () && !! INSN_SPEC_CHECKED_DS (insn
);
3589 /* Extracts machine mode MODE and destination location DST_LOC
3592 get_dest_and_mode (rtx insn
, rtx
*dst_loc
, machine_mode
*mode
)
3594 rtx pat
= PATTERN (insn
);
3596 gcc_assert (dst_loc
);
3597 gcc_assert (GET_CODE (pat
) == SET
);
3599 *dst_loc
= SET_DEST (pat
);
3601 gcc_assert (*dst_loc
);
3602 gcc_assert (MEM_P (*dst_loc
) || REG_P (*dst_loc
));
3605 *mode
= GET_MODE (*dst_loc
);
3608 /* Returns true when moving through JUMP will result in bookkeeping
3611 bookkeeping_can_be_created_if_moved_through_p (insn_t jump
)
3616 FOR_EACH_SUCC (succ
, si
, jump
)
3617 if (sel_num_cfg_preds_gt_1 (succ
))
3623 /* Return 'true' if INSN is the only one in its basic block. */
3625 insn_is_the_only_one_in_bb_p (insn_t insn
)
3627 return sel_bb_head_p (insn
) && sel_bb_end_p (insn
);
3630 #ifdef ENABLE_CHECKING
3631 /* Check that the region we're scheduling still has at most one
3634 verify_backedges (void)
3642 for (i
= 0; i
< current_nr_blocks
; i
++)
3643 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (i
))->succs
)
3644 if (in_current_region_p (e
->dest
)
3645 && BLOCK_TO_BB (e
->dest
->index
) < i
)
3648 gcc_assert (n
<= 1);
3654 /* Functions to work with control flow. */
3656 /* Recompute BLOCK_TO_BB and BB_FOR_BLOCK for current region so that blocks
3657 are sorted in topological order (it might have been invalidated by
3658 redirecting an edge). */
3660 sel_recompute_toporder (void)
3663 int *postorder
, n_blocks
;
3665 postorder
= XALLOCAVEC (int, n_basic_blocks_for_fn (cfun
));
3666 n_blocks
= post_order_compute (postorder
, false, false);
3668 rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
3669 for (n
= 0, i
= n_blocks
- 1; i
>= 0; i
--)
3670 if (CONTAINING_RGN (postorder
[i
]) == rgn
)
3672 BLOCK_TO_BB (postorder
[i
]) = n
;
3673 BB_TO_BLOCK (n
) = postorder
[i
];
3677 /* Assert that we updated info for all blocks. We may miss some blocks if
3678 this function is called when redirecting an edge made a block
3679 unreachable, but that block is not deleted yet. */
3680 gcc_assert (n
== RGN_NR_BLOCKS (rgn
));
3683 /* Tidy the possibly empty block BB. */
3685 maybe_tidy_empty_bb (basic_block bb
)
3687 basic_block succ_bb
, pred_bb
, note_bb
;
3688 vec
<basic_block
> dom_bbs
;
3693 /* Keep empty bb only if this block immediately precedes EXIT and
3694 has incoming non-fallthrough edge, or it has no predecessors or
3695 successors. Otherwise remove it. */
3696 if (!sel_bb_empty_p (bb
)
3697 || (single_succ_p (bb
)
3698 && single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3699 && (!single_pred_p (bb
)
3700 || !(single_pred_edge (bb
)->flags
& EDGE_FALLTHRU
)))
3701 || EDGE_COUNT (bb
->preds
) == 0
3702 || EDGE_COUNT (bb
->succs
) == 0)
3705 /* Do not attempt to redirect complex edges. */
3706 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3707 if (e
->flags
& EDGE_COMPLEX
)
3709 else if (e
->flags
& EDGE_FALLTHRU
)
3712 /* If prev bb ends with asm goto, see if any of the
3713 ASM_OPERANDS_LABELs don't point to the fallthru
3714 label. Do not attempt to redirect it in that case. */
3715 if (JUMP_P (BB_END (e
->src
))
3716 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
3718 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
3720 for (i
= 0; i
< n
; ++i
)
3721 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (bb
))
3726 free_data_sets (bb
);
3728 /* Do not delete BB if it has more than one successor.
3729 That can occur when we moving a jump. */
3730 if (!single_succ_p (bb
))
3732 gcc_assert (can_merge_blocks_p (bb
->prev_bb
, bb
));
3733 sel_merge_blocks (bb
->prev_bb
, bb
);
3737 succ_bb
= single_succ (bb
);
3742 /* Save a pred/succ from the current region to attach the notes to. */
3744 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3745 if (in_current_region_p (e
->src
))
3750 if (note_bb
== NULL
)
3753 /* Redirect all non-fallthru edges to the next bb. */
3758 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3762 if (!(e
->flags
& EDGE_FALLTHRU
))
3764 /* We can not invalidate computed topological order by moving
3765 the edge destination block (E->SUCC) along a fallthru edge.
3767 We will update dominators here only when we'll get
3768 an unreachable block when redirecting, otherwise
3769 sel_redirect_edge_and_branch will take care of it. */
3771 && single_pred_p (e
->dest
))
3772 dom_bbs
.safe_push (e
->dest
);
3773 sel_redirect_edge_and_branch (e
, succ_bb
);
3777 /* If the edge is fallthru, but PRED_BB ends in a conditional jump
3778 to BB (so there is no non-fallthru edge from PRED_BB to BB), we
3779 still have to adjust it. */
3780 else if (single_succ_p (pred_bb
) && any_condjump_p (BB_END (pred_bb
)))
3782 /* If possible, try to remove the unneeded conditional jump. */
3783 if (INSN_SCHED_TIMES (BB_END (pred_bb
)) == 0
3784 && !IN_CURRENT_FENCE_P (BB_END (pred_bb
)))
3786 if (!sel_remove_insn (BB_END (pred_bb
), false, false))
3787 tidy_fallthru_edge (e
);
3790 sel_redirect_edge_and_branch (e
, succ_bb
);
3797 if (can_merge_blocks_p (bb
->prev_bb
, bb
))
3798 sel_merge_blocks (bb
->prev_bb
, bb
);
3801 /* This is a block without fallthru predecessor. Just delete it. */
3802 gcc_assert (note_bb
);
3803 move_bb_info (note_bb
, bb
);
3804 remove_empty_bb (bb
, true);
3807 if (!dom_bbs
.is_empty ())
3809 dom_bbs
.safe_push (succ_bb
);
3810 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, false);
3817 /* Tidy the control flow after we have removed original insn from
3818 XBB. Return true if we have removed some blocks. When FULL_TIDYING
3819 is true, also try to optimize control flow on non-empty blocks. */
3821 tidy_control_flow (basic_block xbb
, bool full_tidying
)
3823 bool changed
= true;
3826 /* First check whether XBB is empty. */
3827 changed
= maybe_tidy_empty_bb (xbb
);
3828 if (changed
|| !full_tidying
)
3831 /* Check if there is a unnecessary jump after insn left. */
3832 if (bb_has_removable_jump_to_p (xbb
, xbb
->next_bb
)
3833 && INSN_SCHED_TIMES (BB_END (xbb
)) == 0
3834 && !IN_CURRENT_FENCE_P (BB_END (xbb
)))
3836 if (sel_remove_insn (BB_END (xbb
), false, false))
3838 tidy_fallthru_edge (EDGE_SUCC (xbb
, 0));
3841 first
= sel_bb_head (xbb
);
3842 last
= sel_bb_end (xbb
);
3843 if (MAY_HAVE_DEBUG_INSNS
)
3845 if (first
!= last
&& DEBUG_INSN_P (first
))
3847 first
= NEXT_INSN (first
);
3848 while (first
!= last
&& (DEBUG_INSN_P (first
) || NOTE_P (first
)));
3850 if (first
!= last
&& DEBUG_INSN_P (last
))
3852 last
= PREV_INSN (last
);
3853 while (first
!= last
&& (DEBUG_INSN_P (last
) || NOTE_P (last
)));
3855 /* Check if there is an unnecessary jump in previous basic block leading
3856 to next basic block left after removing INSN from stream.
3857 If it is so, remove that jump and redirect edge to current
3858 basic block (where there was INSN before deletion). This way
3859 when NOP will be deleted several instructions later with its
3860 basic block we will not get a jump to next instruction, which
3863 && !sel_bb_empty_p (xbb
)
3864 && INSN_NOP_P (last
)
3865 /* Flow goes fallthru from current block to the next. */
3866 && EDGE_COUNT (xbb
->succs
) == 1
3867 && (EDGE_SUCC (xbb
, 0)->flags
& EDGE_FALLTHRU
)
3868 /* When successor is an EXIT block, it may not be the next block. */
3869 && single_succ (xbb
) != EXIT_BLOCK_PTR_FOR_FN (cfun
)
3870 /* And unconditional jump in previous basic block leads to
3871 next basic block of XBB and this jump can be safely removed. */
3872 && in_current_region_p (xbb
->prev_bb
)
3873 && bb_has_removable_jump_to_p (xbb
->prev_bb
, xbb
->next_bb
)
3874 && INSN_SCHED_TIMES (BB_END (xbb
->prev_bb
)) == 0
3875 /* Also this jump is not at the scheduling boundary. */
3876 && !IN_CURRENT_FENCE_P (BB_END (xbb
->prev_bb
)))
3878 bool recompute_toporder_p
;
3879 /* Clear data structures of jump - jump itself will be removed
3880 by sel_redirect_edge_and_branch. */
3881 clear_expr (INSN_EXPR (BB_END (xbb
->prev_bb
)));
3882 recompute_toporder_p
3883 = sel_redirect_edge_and_branch (EDGE_SUCC (xbb
->prev_bb
, 0), xbb
);
3885 gcc_assert (EDGE_SUCC (xbb
->prev_bb
, 0)->flags
& EDGE_FALLTHRU
);
3887 /* It can turn out that after removing unused jump, basic block
3888 that contained that jump, becomes empty too. In such case
3890 if (sel_bb_empty_p (xbb
->prev_bb
))
3891 changed
= maybe_tidy_empty_bb (xbb
->prev_bb
);
3892 if (recompute_toporder_p
)
3893 sel_recompute_toporder ();
3896 #ifdef ENABLE_CHECKING
3897 verify_backedges ();
3898 verify_dominators (CDI_DOMINATORS
);
3904 /* Purge meaningless empty blocks in the middle of a region. */
3906 purge_empty_blocks (void)
3910 /* Do not attempt to delete the first basic block in the region. */
3911 for (i
= 1; i
< current_nr_blocks
; )
3913 basic_block b
= BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (i
));
3915 if (maybe_tidy_empty_bb (b
))
3922 /* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true,
3923 do not delete insn's data, because it will be later re-emitted.
3924 Return true if we have removed some blocks afterwards. */
3926 sel_remove_insn (insn_t insn
, bool only_disconnect
, bool full_tidying
)
3928 basic_block bb
= BLOCK_FOR_INSN (insn
);
3930 gcc_assert (INSN_IN_STREAM_P (insn
));
3932 if (DEBUG_INSN_P (insn
) && BB_AV_SET_VALID_P (bb
))
3937 /* When we remove a debug insn that is head of a BB, it remains
3938 in the AV_SET of the block, but it shouldn't. */
3939 FOR_EACH_EXPR_1 (expr
, i
, &BB_AV_SET (bb
))
3940 if (EXPR_INSN_RTX (expr
) == insn
)
3942 av_set_iter_remove (&i
);
3947 if (only_disconnect
)
3952 clear_expr (INSN_EXPR (insn
));
3955 /* It is necessary to NULL these fields in case we are going to re-insert
3956 INSN into the insns stream, as will usually happen in the ONLY_DISCONNECT
3957 case, but also for NOPs that we will return to the nop pool. */
3958 SET_PREV_INSN (insn
) = NULL_RTX
;
3959 SET_NEXT_INSN (insn
) = NULL_RTX
;
3960 set_block_for_insn (insn
, NULL
);
3962 return tidy_control_flow (bb
, full_tidying
);
3965 /* Estimate number of the insns in BB. */
3967 sel_estimate_number_of_insns (basic_block bb
)
3970 insn_t insn
= NEXT_INSN (BB_HEAD (bb
)), next_tail
= NEXT_INSN (BB_END (bb
));
3972 for (; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3973 if (NONDEBUG_INSN_P (insn
))
3979 /* We don't need separate luids for notes or labels. */
3981 sel_luid_for_non_insn (rtx x
)
3983 gcc_assert (NOTE_P (x
) || LABEL_P (x
));
3988 /* Find the proper seqno for inserting at INSN by successors.
3989 Return -1 if no successors with positive seqno exist. */
3991 get_seqno_by_succs (rtx_insn
*insn
)
3993 basic_block bb
= BLOCK_FOR_INSN (insn
);
3994 rtx_insn
*tmp
= insn
, *end
= BB_END (bb
);
4001 tmp
= NEXT_INSN (tmp
);
4003 return INSN_SEQNO (tmp
);
4008 FOR_EACH_SUCC_1 (succ
, si
, end
, SUCCS_NORMAL
)
4009 if (INSN_SEQNO (succ
) > 0)
4010 seqno
= MIN (seqno
, INSN_SEQNO (succ
));
4012 if (seqno
== INT_MAX
)
4018 /* Compute seqno for INSN by its preds or succs. Use OLD_SEQNO to compute
4019 seqno in corner cases. */
4021 get_seqno_for_a_jump (insn_t insn
, int old_seqno
)
4025 gcc_assert (INSN_SIMPLEJUMP_P (insn
));
4027 if (!sel_bb_head_p (insn
))
4028 seqno
= INSN_SEQNO (PREV_INSN (insn
));
4031 basic_block bb
= BLOCK_FOR_INSN (insn
);
4033 if (single_pred_p (bb
)
4034 && !in_current_region_p (single_pred (bb
)))
4036 /* We can have preds outside a region when splitting edges
4037 for pipelining of an outer loop. Use succ instead.
4038 There should be only one of them. */
4043 gcc_assert (flag_sel_sched_pipelining_outer_loops
4044 && current_loop_nest
);
4045 FOR_EACH_SUCC_1 (succ
, si
, insn
,
4046 SUCCS_NORMAL
| SUCCS_SKIP_TO_LOOP_EXITS
)
4052 gcc_assert (succ
!= NULL
);
4053 seqno
= INSN_SEQNO (succ
);
4060 cfg_preds (BLOCK_FOR_INSN (insn
), &preds
, &n
);
4063 /* For one predecessor, use simple method. */
4065 seqno
= INSN_SEQNO (preds
[0]);
4067 seqno
= get_seqno_by_preds (insn
);
4073 /* We were unable to find a good seqno among preds. */
4075 seqno
= get_seqno_by_succs (insn
);
4079 /* The only case where this could be here legally is that the only
4080 unscheduled insn was a conditional jump that got removed and turned
4081 into this unconditional one. Initialize from the old seqno
4082 of that jump passed down to here. */
4086 gcc_assert (seqno
>= 0);
4090 /* Find the proper seqno for inserting at INSN. Returns -1 if no predecessors
4091 with positive seqno exist. */
4093 get_seqno_by_preds (rtx_insn
*insn
)
4095 basic_block bb
= BLOCK_FOR_INSN (insn
);
4096 rtx_insn
*tmp
= insn
, *head
= BB_HEAD (bb
);
4102 tmp
= PREV_INSN (tmp
);
4104 return INSN_SEQNO (tmp
);
4107 cfg_preds (bb
, &preds
, &n
);
4108 for (i
= 0, seqno
= -1; i
< n
; i
++)
4109 seqno
= MAX (seqno
, INSN_SEQNO (preds
[i
]));
4116 /* Extend pass-scope data structures for basic blocks. */
4118 sel_extend_global_bb_info (void)
4120 sel_global_bb_info
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
4123 /* Extend region-scope data structures for basic blocks. */
4125 extend_region_bb_info (void)
4127 sel_region_bb_info
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
4130 /* Extend all data structures to fit for all basic blocks. */
4132 extend_bb_info (void)
4134 sel_extend_global_bb_info ();
4135 extend_region_bb_info ();
4138 /* Finalize pass-scope data structures for basic blocks. */
4140 sel_finish_global_bb_info (void)
4142 sel_global_bb_info
.release ();
4145 /* Finalize region-scope data structures for basic blocks. */
4147 finish_region_bb_info (void)
4149 sel_region_bb_info
.release ();
4153 /* Data for each insn in current region. */
4154 vec
<sel_insn_data_def
> s_i_d
= vNULL
;
4156 /* Extend data structures for insns from current region. */
4158 extend_insn_data (void)
4162 sched_extend_target ();
4163 sched_deps_init (false);
4165 /* Extend data structures for insns from current region. */
4166 reserve
= (sched_max_luid
+ 1 - s_i_d
.length ());
4167 if (reserve
> 0 && ! s_i_d
.space (reserve
))
4171 if (sched_max_luid
/ 2 > 1024)
4172 size
= sched_max_luid
+ 1024;
4174 size
= 3 * sched_max_luid
/ 2;
4177 s_i_d
.safe_grow_cleared (size
);
4181 /* Finalize data structures for insns from current region. */
4187 /* Clear here all dependence contexts that may have left from insns that were
4188 removed during the scheduling. */
4189 for (i
= 0; i
< s_i_d
.length (); i
++)
4191 sel_insn_data_def
*sid_entry
= &s_i_d
[i
];
4193 if (sid_entry
->live
)
4194 return_regset_to_pool (sid_entry
->live
);
4195 if (sid_entry
->analyzed_deps
)
4197 BITMAP_FREE (sid_entry
->analyzed_deps
);
4198 BITMAP_FREE (sid_entry
->found_deps
);
4199 htab_delete (sid_entry
->transformed_insns
);
4200 free_deps (&sid_entry
->deps_context
);
4202 if (EXPR_VINSN (&sid_entry
->expr
))
4204 clear_expr (&sid_entry
->expr
);
4206 /* Also, clear CANT_MOVE bit here, because we really don't want it
4207 to be passed to the next region. */
4208 CANT_MOVE_BY_LUID (i
) = 0;
4215 /* A proxy to pass initialization data to init_insn (). */
4216 static sel_insn_data_def _insn_init_ssid
;
4217 static sel_insn_data_t insn_init_ssid
= &_insn_init_ssid
;
4219 /* If true create a new vinsn. Otherwise use the one from EXPR. */
4220 static bool insn_init_create_new_vinsn_p
;
4222 /* Set all necessary data for initialization of the new insn[s]. */
4224 set_insn_init (expr_t expr
, vinsn_t vi
, int seqno
)
4226 expr_t x
= &insn_init_ssid
->expr
;
4228 copy_expr_onside (x
, expr
);
4231 insn_init_create_new_vinsn_p
= false;
4232 change_vinsn_in_expr (x
, vi
);
4235 insn_init_create_new_vinsn_p
= true;
4237 insn_init_ssid
->seqno
= seqno
;
4241 /* Init data for INSN. */
4243 init_insn_data (insn_t insn
)
4246 sel_insn_data_t ssid
= insn_init_ssid
;
4248 /* The fields mentioned below are special and hence are not being
4249 propagated to the new insns. */
4250 gcc_assert (!ssid
->asm_p
&& ssid
->sched_next
== NULL
4251 && !ssid
->after_stall_p
&& ssid
->sched_cycle
== 0);
4252 gcc_assert (INSN_P (insn
) && INSN_LUID (insn
) > 0);
4254 expr
= INSN_EXPR (insn
);
4255 copy_expr (expr
, &ssid
->expr
);
4256 prepare_insn_expr (insn
, ssid
->seqno
);
4258 if (insn_init_create_new_vinsn_p
)
4259 change_vinsn_in_expr (expr
, vinsn_create (insn
, init_insn_force_unique_p
));
4261 if (first_time_insn_init (insn
))
4262 init_first_time_insn_data (insn
);
4265 /* This is used to initialize spurious jumps generated by
4266 sel_redirect_edge (). OLD_SEQNO is used for initializing seqnos
4267 in corner cases within get_seqno_for_a_jump. */
4269 init_simplejump_data (insn_t insn
, int old_seqno
)
4271 init_expr (INSN_EXPR (insn
), vinsn_create (insn
, false), 0,
4272 REG_BR_PROB_BASE
, 0, 0, 0, 0, 0, 0,
4273 vNULL
, true, false, false,
4275 INSN_SEQNO (insn
) = get_seqno_for_a_jump (insn
, old_seqno
);
4276 init_first_time_insn_data (insn
);
4279 /* Perform deferred initialization of insns. This is used to process
4280 a new jump that may be created by redirect_edge. OLD_SEQNO is used
4281 for initializing simplejumps in init_simplejump_data. */
4283 sel_init_new_insn (insn_t insn
, int flags
, int old_seqno
)
4285 /* We create data structures for bb when the first insn is emitted in it. */
4287 && INSN_IN_STREAM_P (insn
)
4288 && insn_is_the_only_one_in_bb_p (insn
))
4291 create_initial_data_sets (BLOCK_FOR_INSN (insn
));
4294 if (flags
& INSN_INIT_TODO_LUID
)
4296 sched_extend_luids ();
4297 sched_init_insn_luid (insn
);
4300 if (flags
& INSN_INIT_TODO_SSID
)
4302 extend_insn_data ();
4303 init_insn_data (insn
);
4304 clear_expr (&insn_init_ssid
->expr
);
4307 if (flags
& INSN_INIT_TODO_SIMPLEJUMP
)
4309 extend_insn_data ();
4310 init_simplejump_data (insn
, old_seqno
);
4313 gcc_assert (CONTAINING_RGN (BLOCK_NUM (insn
))
4314 == CONTAINING_RGN (BB_TO_BLOCK (0)));
4318 /* Functions to init/finish work with lv sets. */
4320 /* Init BB_LV_SET of BB from DF_LR_IN set of BB. */
4322 init_lv_set (basic_block bb
)
4324 gcc_assert (!BB_LV_SET_VALID_P (bb
));
4326 BB_LV_SET (bb
) = get_regset_from_pool ();
4327 COPY_REG_SET (BB_LV_SET (bb
), DF_LR_IN (bb
));
4328 BB_LV_SET_VALID_P (bb
) = true;
4331 /* Copy liveness information to BB from FROM_BB. */
4333 copy_lv_set_from (basic_block bb
, basic_block from_bb
)
4335 gcc_assert (!BB_LV_SET_VALID_P (bb
));
4337 COPY_REG_SET (BB_LV_SET (bb
), BB_LV_SET (from_bb
));
4338 BB_LV_SET_VALID_P (bb
) = true;
4341 /* Initialize lv set of all bb headers. */
4347 /* Initialize of LV sets. */
4348 FOR_EACH_BB_FN (bb
, cfun
)
4351 /* Don't forget EXIT_BLOCK. */
4352 init_lv_set (EXIT_BLOCK_PTR_FOR_FN (cfun
));
4355 /* Release lv set of HEAD. */
4357 free_lv_set (basic_block bb
)
4359 gcc_assert (BB_LV_SET (bb
) != NULL
);
4361 return_regset_to_pool (BB_LV_SET (bb
));
4362 BB_LV_SET (bb
) = NULL
;
4363 BB_LV_SET_VALID_P (bb
) = false;
4366 /* Finalize lv sets of all bb headers. */
4372 /* Don't forget EXIT_BLOCK. */
4373 free_lv_set (EXIT_BLOCK_PTR_FOR_FN (cfun
));
4376 FOR_EACH_BB_FN (bb
, cfun
)
4381 /* Mark AV_SET for BB as invalid, so this set will be updated the next time
4382 compute_av() processes BB. This function is called when creating new basic
4383 blocks, as well as for blocks (either new or existing) where new jumps are
4384 created when the control flow is being updated. */
4386 invalidate_av_set (basic_block bb
)
4388 BB_AV_LEVEL (bb
) = -1;
4391 /* Create initial data sets for BB (they will be invalid). */
4393 create_initial_data_sets (basic_block bb
)
4396 BB_LV_SET_VALID_P (bb
) = false;
4398 BB_LV_SET (bb
) = get_regset_from_pool ();
4399 invalidate_av_set (bb
);
4402 /* Free av set of BB. */
4404 free_av_set (basic_block bb
)
4406 av_set_clear (&BB_AV_SET (bb
));
4407 BB_AV_LEVEL (bb
) = 0;
4410 /* Free data sets of BB. */
4412 free_data_sets (basic_block bb
)
4418 /* Exchange lv sets of TO and FROM. */
4420 exchange_lv_sets (basic_block to
, basic_block from
)
4423 regset to_lv_set
= BB_LV_SET (to
);
4425 BB_LV_SET (to
) = BB_LV_SET (from
);
4426 BB_LV_SET (from
) = to_lv_set
;
4430 bool to_lv_set_valid_p
= BB_LV_SET_VALID_P (to
);
4432 BB_LV_SET_VALID_P (to
) = BB_LV_SET_VALID_P (from
);
4433 BB_LV_SET_VALID_P (from
) = to_lv_set_valid_p
;
4438 /* Exchange av sets of TO and FROM. */
4440 exchange_av_sets (basic_block to
, basic_block from
)
4443 av_set_t to_av_set
= BB_AV_SET (to
);
4445 BB_AV_SET (to
) = BB_AV_SET (from
);
4446 BB_AV_SET (from
) = to_av_set
;
4450 int to_av_level
= BB_AV_LEVEL (to
);
4452 BB_AV_LEVEL (to
) = BB_AV_LEVEL (from
);
4453 BB_AV_LEVEL (from
) = to_av_level
;
4457 /* Exchange data sets of TO and FROM. */
4459 exchange_data_sets (basic_block to
, basic_block from
)
4461 exchange_lv_sets (to
, from
);
4462 exchange_av_sets (to
, from
);
4465 /* Copy data sets of FROM to TO. */
4467 copy_data_sets (basic_block to
, basic_block from
)
4469 gcc_assert (!BB_LV_SET_VALID_P (to
) && !BB_AV_SET_VALID_P (to
));
4470 gcc_assert (BB_AV_SET (to
) == NULL
);
4472 BB_AV_LEVEL (to
) = BB_AV_LEVEL (from
);
4473 BB_LV_SET_VALID_P (to
) = BB_LV_SET_VALID_P (from
);
4475 if (BB_AV_SET_VALID_P (from
))
4477 BB_AV_SET (to
) = av_set_copy (BB_AV_SET (from
));
4479 if (BB_LV_SET_VALID_P (from
))
4481 gcc_assert (BB_LV_SET (to
) != NULL
);
4482 COPY_REG_SET (BB_LV_SET (to
), BB_LV_SET (from
));
4486 /* Return an av set for INSN, if any. */
4488 get_av_set (insn_t insn
)
4492 gcc_assert (AV_SET_VALID_P (insn
));
4494 if (sel_bb_head_p (insn
))
4495 av_set
= BB_AV_SET (BLOCK_FOR_INSN (insn
));
4502 /* Implementation of AV_LEVEL () macro. Return AV_LEVEL () of INSN. */
4504 get_av_level (insn_t insn
)
4508 gcc_assert (INSN_P (insn
));
4510 if (sel_bb_head_p (insn
))
4511 av_level
= BB_AV_LEVEL (BLOCK_FOR_INSN (insn
));
4513 av_level
= INSN_WS_LEVEL (insn
);
4520 /* Variables to work with control-flow graph. */
4522 /* The basic block that already has been processed by the sched_data_update (),
4523 but hasn't been in sel_add_bb () yet. */
4524 static vec
<basic_block
>
4525 last_added_blocks
= vNULL
;
4527 /* A pool for allocating successor infos. */
4530 /* A stack for saving succs_info structures. */
4531 struct succs_info
*stack
;
4536 /* Top of the stack. */
4539 /* Maximal value of the top. */
4543 /* Functions to work with control-flow graph. */
4545 /* Return basic block note of BB. */
4547 sel_bb_head (basic_block bb
)
4551 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4553 gcc_assert (exit_insn
!= NULL_RTX
);
4558 rtx_note
*note
= bb_note (bb
);
4559 head
= next_nonnote_insn (note
);
4561 if (head
&& (BARRIER_P (head
) || BLOCK_FOR_INSN (head
) != bb
))
4568 /* Return true if INSN is a basic block header. */
4570 sel_bb_head_p (insn_t insn
)
4572 return sel_bb_head (BLOCK_FOR_INSN (insn
)) == insn
;
4575 /* Return last insn of BB. */
4577 sel_bb_end (basic_block bb
)
4579 if (sel_bb_empty_p (bb
))
4582 gcc_assert (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
4587 /* Return true if INSN is the last insn in its basic block. */
4589 sel_bb_end_p (insn_t insn
)
4591 return insn
== sel_bb_end (BLOCK_FOR_INSN (insn
));
4594 /* Return true if BB consist of single NOTE_INSN_BASIC_BLOCK. */
4596 sel_bb_empty_p (basic_block bb
)
4598 return sel_bb_head (bb
) == NULL
;
4601 /* True when BB belongs to the current scheduling region. */
4603 in_current_region_p (basic_block bb
)
4605 if (bb
->index
< NUM_FIXED_BLOCKS
)
4608 return CONTAINING_RGN (bb
->index
) == CONTAINING_RGN (BB_TO_BLOCK (0));
4611 /* Return the block which is a fallthru bb of a conditional jump JUMP. */
4613 fallthru_bb_of_jump (const rtx_insn
*jump
)
4618 if (!any_condjump_p (jump
))
4621 /* A basic block that ends with a conditional jump may still have one successor
4622 (and be followed by a barrier), we are not interested. */
4623 if (single_succ_p (BLOCK_FOR_INSN (jump
)))
4626 return FALLTHRU_EDGE (BLOCK_FOR_INSN (jump
))->dest
;
4629 /* Remove all notes from BB. */
4631 init_bb (basic_block bb
)
4633 remove_notes (bb_note (bb
), BB_END (bb
));
4634 BB_NOTE_LIST (bb
) = note_list
;
4638 sel_init_bbs (bb_vec_t bbs
)
4640 const struct sched_scan_info_def ssi
=
4642 extend_bb_info
, /* extend_bb */
4643 init_bb
, /* init_bb */
4644 NULL
, /* extend_insn */
4645 NULL
/* init_insn */
4648 sched_scan (&ssi
, bbs
);
4651 /* Restore notes for the whole region. */
4653 sel_restore_notes (void)
4658 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
4660 basic_block first
, last
;
4662 first
= EBB_FIRST_BB (bb
);
4663 last
= EBB_LAST_BB (bb
)->next_bb
;
4667 note_list
= BB_NOTE_LIST (first
);
4668 restore_other_notes (NULL
, first
);
4669 BB_NOTE_LIST (first
) = NULL
;
4671 FOR_BB_INSNS (first
, insn
)
4672 if (NONDEBUG_INSN_P (insn
))
4673 reemit_notes (insn
);
4675 first
= first
->next_bb
;
4677 while (first
!= last
);
4681 /* Free per-bb data structures. */
4683 sel_finish_bbs (void)
4685 sel_restore_notes ();
4687 /* Remove current loop preheader from this loop. */
4688 if (current_loop_nest
)
4689 sel_remove_loop_preheader ();
4691 finish_region_bb_info ();
4694 /* Return true if INSN has a single successor of type FLAGS. */
4696 sel_insn_has_single_succ_p (insn_t insn
, int flags
)
4700 bool first_p
= true;
4702 FOR_EACH_SUCC_1 (succ
, si
, insn
, flags
)
4713 /* Allocate successor's info. */
4714 static struct succs_info
*
4715 alloc_succs_info (void)
4717 if (succs_info_pool
.top
== succs_info_pool
.max_top
)
4721 if (++succs_info_pool
.max_top
>= succs_info_pool
.size
)
4724 i
= ++succs_info_pool
.top
;
4725 succs_info_pool
.stack
[i
].succs_ok
.create (10);
4726 succs_info_pool
.stack
[i
].succs_other
.create (10);
4727 succs_info_pool
.stack
[i
].probs_ok
.create (10);
4730 succs_info_pool
.top
++;
4732 return &succs_info_pool
.stack
[succs_info_pool
.top
];
4735 /* Free successor's info. */
4737 free_succs_info (struct succs_info
* sinfo
)
4739 gcc_assert (succs_info_pool
.top
>= 0
4740 && &succs_info_pool
.stack
[succs_info_pool
.top
] == sinfo
);
4741 succs_info_pool
.top
--;
4743 /* Clear stale info. */
4744 sinfo
->succs_ok
.block_remove (0, sinfo
->succs_ok
.length ());
4745 sinfo
->succs_other
.block_remove (0, sinfo
->succs_other
.length ());
4746 sinfo
->probs_ok
.block_remove (0, sinfo
->probs_ok
.length ());
4747 sinfo
->all_prob
= 0;
4748 sinfo
->succs_ok_n
= 0;
4749 sinfo
->all_succs_n
= 0;
4752 /* Compute successor info for INSN. FLAGS are the flags passed
4753 to the FOR_EACH_SUCC_1 iterator. */
4755 compute_succs_info (insn_t insn
, short flags
)
4759 struct succs_info
*sinfo
= alloc_succs_info ();
4761 /* Traverse *all* successors and decide what to do with each. */
4762 FOR_EACH_SUCC_1 (succ
, si
, insn
, SUCCS_ALL
)
4764 /* FIXME: this doesn't work for skipping to loop exits, as we don't
4765 perform code motion through inner loops. */
4766 short current_flags
= si
.current_flags
& ~SUCCS_SKIP_TO_LOOP_EXITS
;
4768 if (current_flags
& flags
)
4770 sinfo
->succs_ok
.safe_push (succ
);
4771 sinfo
->probs_ok
.safe_push (
4772 /* FIXME: Improve calculation when skipping
4773 inner loop to exits. */
4774 si
.bb_end
? si
.e1
->probability
: REG_BR_PROB_BASE
);
4775 sinfo
->succs_ok_n
++;
4778 sinfo
->succs_other
.safe_push (succ
);
4780 /* Compute all_prob. */
4782 sinfo
->all_prob
= REG_BR_PROB_BASE
;
4784 sinfo
->all_prob
+= si
.e1
->probability
;
4786 sinfo
->all_succs_n
++;
4792 /* Return the predecessors of BB in PREDS and their number in N.
4793 Empty blocks are skipped. SIZE is used to allocate PREDS. */
4795 cfg_preds_1 (basic_block bb
, insn_t
**preds
, int *n
, int *size
)
4800 gcc_assert (BLOCK_TO_BB (bb
->index
) != 0);
4802 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4804 basic_block pred_bb
= e
->src
;
4805 insn_t bb_end
= BB_END (pred_bb
);
4807 if (!in_current_region_p (pred_bb
))
4809 gcc_assert (flag_sel_sched_pipelining_outer_loops
4810 && current_loop_nest
);
4814 if (sel_bb_empty_p (pred_bb
))
4815 cfg_preds_1 (pred_bb
, preds
, n
, size
);
4819 *preds
= XRESIZEVEC (insn_t
, *preds
,
4820 (*size
= 2 * *size
+ 1));
4821 (*preds
)[(*n
)++] = bb_end
;
4826 || (flag_sel_sched_pipelining_outer_loops
4827 && current_loop_nest
));
4830 /* Find all predecessors of BB and record them in PREDS and their number
4831 in N. Empty blocks are skipped, and only normal (forward in-region)
4832 edges are processed. */
4834 cfg_preds (basic_block bb
, insn_t
**preds
, int *n
)
4840 cfg_preds_1 (bb
, preds
, n
, &size
);
4843 /* Returns true if we are moving INSN through join point. */
4845 sel_num_cfg_preds_gt_1 (insn_t insn
)
4849 if (!sel_bb_head_p (insn
) || INSN_BB (insn
) == 0)
4852 bb
= BLOCK_FOR_INSN (insn
);
4856 if (EDGE_COUNT (bb
->preds
) > 1)
4859 gcc_assert (EDGE_PRED (bb
, 0)->dest
== bb
);
4860 bb
= EDGE_PRED (bb
, 0)->src
;
4862 if (!sel_bb_empty_p (bb
))
4869 /* Returns true when BB should be the end of an ebb. Adapted from the
4870 code in sched-ebb.c. */
4872 bb_ends_ebb_p (basic_block bb
)
4874 basic_block next_bb
= bb_next_bb (bb
);
4877 if (next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
4878 || bitmap_bit_p (forced_ebb_heads
, next_bb
->index
)
4879 || (LABEL_P (BB_HEAD (next_bb
))
4880 /* NB: LABEL_NUSES () is not maintained outside of jump.c.
4881 Work around that. */
4882 && !single_pred_p (next_bb
)))
4885 if (!in_current_region_p (next_bb
))
4888 e
= find_fallthru_edge (bb
->succs
);
4891 gcc_assert (e
->dest
== next_bb
);
4899 /* Returns true when INSN and SUCC are in the same EBB, given that SUCC is a
4900 successor of INSN. */
4902 in_same_ebb_p (insn_t insn
, insn_t succ
)
4904 basic_block ptr
= BLOCK_FOR_INSN (insn
);
4908 if (ptr
== BLOCK_FOR_INSN (succ
))
4911 if (bb_ends_ebb_p (ptr
))
4914 ptr
= bb_next_bb (ptr
);
4921 /* Recomputes the reverse topological order for the function and
4922 saves it in REV_TOP_ORDER_INDEX. REV_TOP_ORDER_INDEX_LEN is also
4923 modified appropriately. */
4925 recompute_rev_top_order (void)
4930 if (!rev_top_order_index
4931 || rev_top_order_index_len
< last_basic_block_for_fn (cfun
))
4933 rev_top_order_index_len
= last_basic_block_for_fn (cfun
);
4934 rev_top_order_index
= XRESIZEVEC (int, rev_top_order_index
,
4935 rev_top_order_index_len
);
4938 postorder
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
4940 n_blocks
= post_order_compute (postorder
, true, false);
4941 gcc_assert (n_basic_blocks_for_fn (cfun
) == n_blocks
);
4943 /* Build reverse function: for each basic block with BB->INDEX == K
4944 rev_top_order_index[K] is it's reverse topological sort number. */
4945 for (i
= 0; i
< n_blocks
; i
++)
4947 gcc_assert (postorder
[i
] < rev_top_order_index_len
);
4948 rev_top_order_index
[postorder
[i
]] = i
;
4954 /* Clear all flags from insns in BB that could spoil its rescheduling. */
4956 clear_outdated_rtx_info (basic_block bb
)
4960 FOR_BB_INSNS (bb
, insn
)
4963 SCHED_GROUP_P (insn
) = 0;
4964 INSN_AFTER_STALL_P (insn
) = 0;
4965 INSN_SCHED_TIMES (insn
) = 0;
4966 EXPR_PRIORITY_ADJ (INSN_EXPR (insn
)) = 0;
4968 /* We cannot use the changed caches, as previously we could ignore
4969 the LHS dependence due to enabled renaming and transform
4970 the expression, and currently we'll be unable to do this. */
4971 htab_empty (INSN_TRANSFORMED_INSNS (insn
));
4975 /* Add BB_NOTE to the pool of available basic block notes. */
4977 return_bb_to_pool (basic_block bb
)
4979 rtx_note
*note
= bb_note (bb
);
4981 gcc_assert (NOTE_BASIC_BLOCK (note
) == bb
4982 && bb
->aux
== NULL
);
4984 /* It turns out that current cfg infrastructure does not support
4985 reuse of basic blocks. Don't bother for now. */
4986 /*bb_note_pool.safe_push (note);*/
4989 /* Get a bb_note from pool or return NULL_RTX if pool is empty. */
4991 get_bb_note_from_pool (void)
4993 if (bb_note_pool
.is_empty ())
4997 rtx_note
*note
= bb_note_pool
.pop ();
4999 SET_PREV_INSN (note
) = NULL_RTX
;
5000 SET_NEXT_INSN (note
) = NULL_RTX
;
5006 /* Free bb_note_pool. */
5008 free_bb_note_pool (void)
5010 bb_note_pool
.release ();
5013 /* Setup scheduler pool and successor structure. */
5015 alloc_sched_pools (void)
5019 succs_size
= MAX_WS
+ 1;
5020 succs_info_pool
.stack
= XCNEWVEC (struct succs_info
, succs_size
);
5021 succs_info_pool
.size
= succs_size
;
5022 succs_info_pool
.top
= -1;
5023 succs_info_pool
.max_top
= -1;
5026 /* Free the pools. */
5028 free_sched_pools (void)
5032 sched_lists_pool
.release ();
5033 gcc_assert (succs_info_pool
.top
== -1);
5034 for (i
= 0; i
<= succs_info_pool
.max_top
; i
++)
5036 succs_info_pool
.stack
[i
].succs_ok
.release ();
5037 succs_info_pool
.stack
[i
].succs_other
.release ();
5038 succs_info_pool
.stack
[i
].probs_ok
.release ();
5040 free (succs_info_pool
.stack
);
5044 /* Returns a position in RGN where BB can be inserted retaining
5045 topological order. */
5047 find_place_to_insert_bb (basic_block bb
, int rgn
)
5049 bool has_preds_outside_rgn
= false;
5053 /* Find whether we have preds outside the region. */
5054 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
5055 if (!in_current_region_p (e
->src
))
5057 has_preds_outside_rgn
= true;
5061 /* Recompute the top order -- needed when we have > 1 pred
5062 and in case we don't have preds outside. */
5063 if (flag_sel_sched_pipelining_outer_loops
5064 && (has_preds_outside_rgn
|| EDGE_COUNT (bb
->preds
) > 1))
5066 int i
, bbi
= bb
->index
, cur_bbi
;
5068 recompute_rev_top_order ();
5069 for (i
= RGN_NR_BLOCKS (rgn
) - 1; i
>= 0; i
--)
5071 cur_bbi
= BB_TO_BLOCK (i
);
5072 if (rev_top_order_index
[bbi
]
5073 < rev_top_order_index
[cur_bbi
])
5077 /* We skipped the right block, so we increase i. We accommodate
5078 it for increasing by step later, so we decrease i. */
5081 else if (has_preds_outside_rgn
)
5083 /* This is the case when we generate an extra empty block
5084 to serve as region head during pipelining. */
5085 e
= EDGE_SUCC (bb
, 0);
5086 gcc_assert (EDGE_COUNT (bb
->succs
) == 1
5087 && in_current_region_p (EDGE_SUCC (bb
, 0)->dest
)
5088 && (BLOCK_TO_BB (e
->dest
->index
) == 0));
5092 /* We don't have preds outside the region. We should have
5093 the only pred, because the multiple preds case comes from
5094 the pipelining of outer loops, and that is handled above.
5095 Just take the bbi of this single pred. */
5096 if (EDGE_COUNT (bb
->succs
) > 0)
5100 gcc_assert (EDGE_COUNT (bb
->preds
) == 1);
5102 pred_bbi
= EDGE_PRED (bb
, 0)->src
->index
;
5103 return BLOCK_TO_BB (pred_bbi
);
5106 /* BB has no successors. It is safe to put it in the end. */
5107 return current_nr_blocks
- 1;
5110 /* Deletes an empty basic block freeing its data. */
5112 delete_and_free_basic_block (basic_block bb
)
5114 gcc_assert (sel_bb_empty_p (bb
));
5119 bitmap_clear_bit (blocks_to_reschedule
, bb
->index
);
5121 /* Can't assert av_set properties because we use sel_aremove_bb
5122 when removing loop preheader from the region. At the point of
5123 removing the preheader we already have deallocated sel_region_bb_info. */
5124 gcc_assert (BB_LV_SET (bb
) == NULL
5125 && !BB_LV_SET_VALID_P (bb
)
5126 && BB_AV_LEVEL (bb
) == 0
5127 && BB_AV_SET (bb
) == NULL
);
5129 delete_basic_block (bb
);
5132 /* Add BB to the current region and update the region data. */
5134 add_block_to_current_region (basic_block bb
)
5136 int i
, pos
, bbi
= -2, rgn
;
5138 rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
5139 bbi
= find_place_to_insert_bb (bb
, rgn
);
5141 pos
= RGN_BLOCKS (rgn
) + bbi
;
5143 gcc_assert (RGN_HAS_REAL_EBB (rgn
) == 0
5144 && ebb_head
[bbi
] == pos
);
5146 /* Make a place for the new block. */
5149 for (i
= RGN_BLOCKS (rgn
+ 1) - 1; i
>= pos
; i
--)
5150 BLOCK_TO_BB (rgn_bb_table
[i
])++;
5152 memmove (rgn_bb_table
+ pos
+ 1,
5154 (RGN_BLOCKS (nr_regions
) - pos
) * sizeof (*rgn_bb_table
));
5156 /* Initialize data for BB. */
5157 rgn_bb_table
[pos
] = bb
->index
;
5158 BLOCK_TO_BB (bb
->index
) = bbi
;
5159 CONTAINING_RGN (bb
->index
) = rgn
;
5161 RGN_NR_BLOCKS (rgn
)++;
5163 for (i
= rgn
+ 1; i
<= nr_regions
; i
++)
5167 /* Remove BB from the current region and update the region data. */
5169 remove_bb_from_region (basic_block bb
)
5171 int i
, pos
, bbi
= -2, rgn
;
5173 rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
5174 bbi
= BLOCK_TO_BB (bb
->index
);
5175 pos
= RGN_BLOCKS (rgn
) + bbi
;
5177 gcc_assert (RGN_HAS_REAL_EBB (rgn
) == 0
5178 && ebb_head
[bbi
] == pos
);
5180 for (i
= RGN_BLOCKS (rgn
+ 1) - 1; i
>= pos
; i
--)
5181 BLOCK_TO_BB (rgn_bb_table
[i
])--;
5183 memmove (rgn_bb_table
+ pos
,
5184 rgn_bb_table
+ pos
+ 1,
5185 (RGN_BLOCKS (nr_regions
) - pos
) * sizeof (*rgn_bb_table
));
5187 RGN_NR_BLOCKS (rgn
)--;
5188 for (i
= rgn
+ 1; i
<= nr_regions
; i
++)
5192 /* Add BB to the current region and update all data. If BB is NULL, add all
5193 blocks from last_added_blocks vector. */
5195 sel_add_bb (basic_block bb
)
5197 /* Extend luids so that new notes will receive zero luids. */
5198 sched_extend_luids ();
5200 sel_init_bbs (last_added_blocks
);
5202 /* When bb is passed explicitly, the vector should contain
5203 the only element that equals to bb; otherwise, the vector
5204 should not be NULL. */
5205 gcc_assert (last_added_blocks
.exists ());
5209 gcc_assert (last_added_blocks
.length () == 1
5210 && last_added_blocks
[0] == bb
);
5211 add_block_to_current_region (bb
);
5213 /* We associate creating/deleting data sets with the first insn
5214 appearing / disappearing in the bb. */
5215 if (!sel_bb_empty_p (bb
) && BB_LV_SET (bb
) == NULL
)
5216 create_initial_data_sets (bb
);
5218 last_added_blocks
.release ();
5221 /* BB is NULL - process LAST_ADDED_BLOCKS instead. */
5224 basic_block temp_bb
= NULL
;
5227 last_added_blocks
.iterate (i
, &bb
); i
++)
5229 add_block_to_current_region (bb
);
5233 /* We need to fetch at least one bb so we know the region
5235 gcc_assert (temp_bb
!= NULL
);
5238 last_added_blocks
.release ();
5241 rgn_setup_region (CONTAINING_RGN (bb
->index
));
5244 /* Remove BB from the current region and update all data.
5245 If REMOVE_FROM_CFG_PBB is true, also remove the block cfom cfg. */
5247 sel_remove_bb (basic_block bb
, bool remove_from_cfg_p
)
5249 unsigned idx
= bb
->index
;
5251 gcc_assert (bb
!= NULL
&& BB_NOTE_LIST (bb
) == NULL_RTX
);
5253 remove_bb_from_region (bb
);
5254 return_bb_to_pool (bb
);
5255 bitmap_clear_bit (blocks_to_reschedule
, idx
);
5257 if (remove_from_cfg_p
)
5259 basic_block succ
= single_succ (bb
);
5260 delete_and_free_basic_block (bb
);
5261 set_immediate_dominator (CDI_DOMINATORS
, succ
,
5262 recompute_dominator (CDI_DOMINATORS
, succ
));
5265 rgn_setup_region (CONTAINING_RGN (idx
));
5268 /* Concatenate info of EMPTY_BB to info of MERGE_BB. */
5270 move_bb_info (basic_block merge_bb
, basic_block empty_bb
)
5272 if (in_current_region_p (merge_bb
))
5273 concat_note_lists (BB_NOTE_LIST (empty_bb
),
5274 &BB_NOTE_LIST (merge_bb
));
5275 BB_NOTE_LIST (empty_bb
) = NULL
;
5279 /* Remove EMPTY_BB. If REMOVE_FROM_CFG_P is false, remove EMPTY_BB from
5280 region, but keep it in CFG. */
5282 remove_empty_bb (basic_block empty_bb
, bool remove_from_cfg_p
)
5284 /* The block should contain just a note or a label.
5285 We try to check whether it is unused below. */
5286 gcc_assert (BB_HEAD (empty_bb
) == BB_END (empty_bb
)
5287 || LABEL_P (BB_HEAD (empty_bb
)));
5289 /* If basic block has predecessors or successors, redirect them. */
5290 if (remove_from_cfg_p
5291 && (EDGE_COUNT (empty_bb
->preds
) > 0
5292 || EDGE_COUNT (empty_bb
->succs
) > 0))
5297 /* We need to init PRED and SUCC before redirecting edges. */
5298 if (EDGE_COUNT (empty_bb
->preds
) > 0)
5302 gcc_assert (EDGE_COUNT (empty_bb
->preds
) == 1);
5304 e
= EDGE_PRED (empty_bb
, 0);
5305 gcc_assert (e
->src
== empty_bb
->prev_bb
5306 && (e
->flags
& EDGE_FALLTHRU
));
5308 pred
= empty_bb
->prev_bb
;
5313 if (EDGE_COUNT (empty_bb
->succs
) > 0)
5315 /* We do not check fallthruness here as above, because
5316 after removing a jump the edge may actually be not fallthru. */
5317 gcc_assert (EDGE_COUNT (empty_bb
->succs
) == 1);
5318 succ
= EDGE_SUCC (empty_bb
, 0)->dest
;
5323 if (EDGE_COUNT (empty_bb
->preds
) > 0 && succ
!= NULL
)
5325 edge e
= EDGE_PRED (empty_bb
, 0);
5327 if (e
->flags
& EDGE_FALLTHRU
)
5328 redirect_edge_succ_nodup (e
, succ
);
5330 sel_redirect_edge_and_branch (EDGE_PRED (empty_bb
, 0), succ
);
5333 if (EDGE_COUNT (empty_bb
->succs
) > 0 && pred
!= NULL
)
5335 edge e
= EDGE_SUCC (empty_bb
, 0);
5337 if (find_edge (pred
, e
->dest
) == NULL
)
5338 redirect_edge_pred (e
, pred
);
5342 /* Finish removing. */
5343 sel_remove_bb (empty_bb
, remove_from_cfg_p
);
5346 /* An implementation of create_basic_block hook, which additionally updates
5347 per-bb data structures. */
5349 sel_create_basic_block (void *headp
, void *endp
, basic_block after
)
5352 rtx_note
*new_bb_note
;
5354 gcc_assert (flag_sel_sched_pipelining_outer_loops
5355 || !last_added_blocks
.exists ());
5357 new_bb_note
= get_bb_note_from_pool ();
5359 if (new_bb_note
== NULL_RTX
)
5360 new_bb
= orig_cfg_hooks
.create_basic_block (headp
, endp
, after
);
5363 new_bb
= create_basic_block_structure ((rtx_insn
*) headp
,
5365 new_bb_note
, after
);
5369 last_added_blocks
.safe_push (new_bb
);
5374 /* Implement sched_init_only_bb (). */
5376 sel_init_only_bb (basic_block bb
, basic_block after
)
5378 gcc_assert (after
== NULL
);
5381 rgn_make_new_region_out_of_new_block (bb
);
5384 /* Update the latch when we've splitted or merged it from FROM block to TO.
5385 This should be checked for all outer loops, too. */
5387 change_loops_latches (basic_block from
, basic_block to
)
5389 gcc_assert (from
!= to
);
5391 if (current_loop_nest
)
5395 for (loop
= current_loop_nest
; loop
; loop
= loop_outer (loop
))
5396 if (considered_for_pipelining_p (loop
) && loop
->latch
== from
)
5398 gcc_assert (loop
== current_loop_nest
);
5400 gcc_assert (loop_latch_edge (loop
));
5405 /* Splits BB on two basic blocks, adding it to the region and extending
5406 per-bb data structures. Returns the newly created bb. */
5408 sel_split_block (basic_block bb
, rtx after
)
5413 new_bb
= sched_split_block_1 (bb
, after
);
5414 sel_add_bb (new_bb
);
5416 /* This should be called after sel_add_bb, because this uses
5417 CONTAINING_RGN for the new block, which is not yet initialized.
5418 FIXME: this function may be a no-op now. */
5419 change_loops_latches (bb
, new_bb
);
5421 /* Update ORIG_BB_INDEX for insns moved into the new block. */
5422 FOR_BB_INSNS (new_bb
, insn
)
5424 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn
)) = new_bb
->index
;
5426 if (sel_bb_empty_p (bb
))
5428 gcc_assert (!sel_bb_empty_p (new_bb
));
5430 /* NEW_BB has data sets that need to be updated and BB holds
5431 data sets that should be removed. Exchange these data sets
5432 so that we won't lose BB's valid data sets. */
5433 exchange_data_sets (new_bb
, bb
);
5434 free_data_sets (bb
);
5437 if (!sel_bb_empty_p (new_bb
)
5438 && bitmap_bit_p (blocks_to_reschedule
, bb
->index
))
5439 bitmap_set_bit (blocks_to_reschedule
, new_bb
->index
);
5444 /* If BB ends with a jump insn whose ID is bigger then PREV_MAX_UID, return it.
5445 Otherwise returns NULL. */
5447 check_for_new_jump (basic_block bb
, int prev_max_uid
)
5451 end
= sel_bb_end (bb
);
5452 if (end
&& INSN_UID (end
) >= prev_max_uid
)
5457 /* Look for a new jump either in FROM_BB block or in newly created JUMP_BB block.
5458 New means having UID at least equal to PREV_MAX_UID. */
5460 find_new_jump (basic_block from
, basic_block jump_bb
, int prev_max_uid
)
5464 /* Return immediately if no new insns were emitted. */
5465 if (get_max_uid () == prev_max_uid
)
5468 /* Now check both blocks for new jumps. It will ever be only one. */
5469 if ((jump
= check_for_new_jump (from
, prev_max_uid
)))
5473 && (jump
= check_for_new_jump (jump_bb
, prev_max_uid
)))
5478 /* Splits E and adds the newly created basic block to the current region.
5479 Returns this basic block. */
5481 sel_split_edge (edge e
)
5483 basic_block new_bb
, src
, other_bb
= NULL
;
5488 prev_max_uid
= get_max_uid ();
5489 new_bb
= split_edge (e
);
5491 if (flag_sel_sched_pipelining_outer_loops
5492 && current_loop_nest
)
5497 /* Some of the basic blocks might not have been added to the loop.
5498 Add them here, until this is fixed in force_fallthru. */
5500 last_added_blocks
.iterate (i
, &bb
); i
++)
5501 if (!bb
->loop_father
)
5503 add_bb_to_loop (bb
, e
->dest
->loop_father
);
5505 gcc_assert (!other_bb
&& (new_bb
->index
!= bb
->index
));
5510 /* Add all last_added_blocks to the region. */
5513 jump
= find_new_jump (src
, new_bb
, prev_max_uid
);
5515 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
);
5517 /* Put the correct lv set on this block. */
5518 if (other_bb
&& !sel_bb_empty_p (other_bb
))
5519 compute_live (sel_bb_head (other_bb
));
5524 /* Implement sched_create_empty_bb (). */
5526 sel_create_empty_bb (basic_block after
)
5530 new_bb
= sched_create_empty_bb_1 (after
);
5532 /* We'll explicitly initialize NEW_BB via sel_init_only_bb () a bit
5534 gcc_assert (last_added_blocks
.length () == 1
5535 && last_added_blocks
[0] == new_bb
);
5537 last_added_blocks
.release ();
5541 /* Implement sched_create_recovery_block. ORIG_INSN is where block
5542 will be splitted to insert a check. */
5544 sel_create_recovery_block (insn_t orig_insn
)
5546 basic_block first_bb
, second_bb
, recovery_block
;
5547 basic_block before_recovery
= NULL
;
5550 first_bb
= BLOCK_FOR_INSN (orig_insn
);
5551 if (sel_bb_end_p (orig_insn
))
5553 /* Avoid introducing an empty block while splitting. */
5554 gcc_assert (single_succ_p (first_bb
));
5555 second_bb
= single_succ (first_bb
);
5558 second_bb
= sched_split_block (first_bb
, orig_insn
);
5560 recovery_block
= sched_create_recovery_block (&before_recovery
);
5561 if (before_recovery
)
5562 copy_lv_set_from (before_recovery
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
5564 gcc_assert (sel_bb_empty_p (recovery_block
));
5565 sched_create_recovery_edges (first_bb
, recovery_block
, second_bb
);
5566 if (current_loops
!= NULL
)
5567 add_bb_to_loop (recovery_block
, first_bb
->loop_father
);
5569 sel_add_bb (recovery_block
);
5571 jump
= BB_END (recovery_block
);
5572 gcc_assert (sel_bb_head (recovery_block
) == jump
);
5573 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
);
5575 return recovery_block
;
5578 /* Merge basic block B into basic block A. */
5580 sel_merge_blocks (basic_block a
, basic_block b
)
5582 gcc_assert (sel_bb_empty_p (b
)
5583 && EDGE_COUNT (b
->preds
) == 1
5584 && EDGE_PRED (b
, 0)->src
== b
->prev_bb
);
5586 move_bb_info (b
->prev_bb
, b
);
5587 remove_empty_bb (b
, false);
5588 merge_blocks (a
, b
);
5589 change_loops_latches (b
, a
);
5592 /* A wrapper for redirect_edge_and_branch_force, which also initializes
5593 data structures for possibly created bb and insns. */
5595 sel_redirect_edge_and_branch_force (edge e
, basic_block to
)
5597 basic_block jump_bb
, src
, orig_dest
= e
->dest
;
5602 /* This function is now used only for bookkeeping code creation, where
5603 we'll never get the single pred of orig_dest block and thus will not
5604 hit unreachable blocks when updating dominator info. */
5605 gcc_assert (!sel_bb_empty_p (e
->src
)
5606 && !single_pred_p (orig_dest
));
5608 prev_max_uid
= get_max_uid ();
5609 /* Compute and pass old_seqno down to sel_init_new_insn only for the case
5610 when the conditional jump being redirected may become unconditional. */
5611 if (any_condjump_p (BB_END (src
))
5612 && INSN_SEQNO (BB_END (src
)) >= 0)
5613 old_seqno
= INSN_SEQNO (BB_END (src
));
5615 jump_bb
= redirect_edge_and_branch_force (e
, to
);
5616 if (jump_bb
!= NULL
)
5617 sel_add_bb (jump_bb
);
5619 /* This function could not be used to spoil the loop structure by now,
5620 thus we don't care to update anything. But check it to be sure. */
5621 if (current_loop_nest
5623 gcc_assert (loop_latch_edge (current_loop_nest
));
5625 jump
= find_new_jump (src
, jump_bb
, prev_max_uid
);
5627 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
,
5629 set_immediate_dominator (CDI_DOMINATORS
, to
,
5630 recompute_dominator (CDI_DOMINATORS
, to
));
5631 set_immediate_dominator (CDI_DOMINATORS
, orig_dest
,
5632 recompute_dominator (CDI_DOMINATORS
, orig_dest
));
5635 /* A wrapper for redirect_edge_and_branch. Return TRUE if blocks connected by
5636 redirected edge are in reverse topological order. */
5638 sel_redirect_edge_and_branch (edge e
, basic_block to
)
5641 basic_block src
, orig_dest
= e
->dest
;
5645 bool recompute_toporder_p
= false;
5646 bool maybe_unreachable
= single_pred_p (orig_dest
);
5649 latch_edge_p
= (pipelining_p
5650 && current_loop_nest
5651 && e
== loop_latch_edge (current_loop_nest
));
5654 prev_max_uid
= get_max_uid ();
5656 /* Compute and pass old_seqno down to sel_init_new_insn only for the case
5657 when the conditional jump being redirected may become unconditional. */
5658 if (any_condjump_p (BB_END (src
))
5659 && INSN_SEQNO (BB_END (src
)) >= 0)
5660 old_seqno
= INSN_SEQNO (BB_END (src
));
5662 redirected
= redirect_edge_and_branch (e
, to
);
5664 gcc_assert (redirected
&& !last_added_blocks
.exists ());
5666 /* When we've redirected a latch edge, update the header. */
5669 current_loop_nest
->header
= to
;
5670 gcc_assert (loop_latch_edge (current_loop_nest
));
5673 /* In rare situations, the topological relation between the blocks connected
5674 by the redirected edge can change (see PR42245 for an example). Update
5675 block_to_bb/bb_to_block. */
5676 if (CONTAINING_RGN (e
->src
->index
) == CONTAINING_RGN (to
->index
)
5677 && BLOCK_TO_BB (e
->src
->index
) > BLOCK_TO_BB (to
->index
))
5678 recompute_toporder_p
= true;
5680 jump
= find_new_jump (src
, NULL
, prev_max_uid
);
5682 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
, old_seqno
);
5684 /* Only update dominator info when we don't have unreachable blocks.
5685 Otherwise we'll update in maybe_tidy_empty_bb. */
5686 if (!maybe_unreachable
)
5688 set_immediate_dominator (CDI_DOMINATORS
, to
,
5689 recompute_dominator (CDI_DOMINATORS
, to
));
5690 set_immediate_dominator (CDI_DOMINATORS
, orig_dest
,
5691 recompute_dominator (CDI_DOMINATORS
, orig_dest
));
5693 return recompute_toporder_p
;
5696 /* This variable holds the cfg hooks used by the selective scheduler. */
5697 static struct cfg_hooks sel_cfg_hooks
;
5699 /* Register sel-sched cfg hooks. */
5701 sel_register_cfg_hooks (void)
5703 sched_split_block
= sel_split_block
;
5705 orig_cfg_hooks
= get_cfg_hooks ();
5706 sel_cfg_hooks
= orig_cfg_hooks
;
5708 sel_cfg_hooks
.create_basic_block
= sel_create_basic_block
;
5710 set_cfg_hooks (sel_cfg_hooks
);
5712 sched_init_only_bb
= sel_init_only_bb
;
5713 sched_split_block
= sel_split_block
;
5714 sched_create_empty_bb
= sel_create_empty_bb
;
5717 /* Unregister sel-sched cfg hooks. */
5719 sel_unregister_cfg_hooks (void)
5721 sched_create_empty_bb
= NULL
;
5722 sched_split_block
= NULL
;
5723 sched_init_only_bb
= NULL
;
5725 set_cfg_hooks (orig_cfg_hooks
);
5729 /* Emit an insn rtx based on PATTERN. If a jump insn is wanted,
5730 LABEL is where this jump should be directed. */
5732 create_insn_rtx_from_pattern (rtx pattern
, rtx label
)
5736 gcc_assert (!INSN_P (pattern
));
5740 if (label
== NULL_RTX
)
5741 insn_rtx
= emit_insn (pattern
);
5742 else if (DEBUG_INSN_P (label
))
5743 insn_rtx
= emit_debug_insn (pattern
);
5746 insn_rtx
= emit_jump_insn (pattern
);
5747 JUMP_LABEL (insn_rtx
) = label
;
5748 ++LABEL_NUSES (label
);
5753 sched_extend_luids ();
5754 sched_extend_target ();
5755 sched_deps_init (false);
5757 /* Initialize INSN_CODE now. */
5758 recog_memoized (insn_rtx
);
5762 /* Create a new vinsn for INSN_RTX. FORCE_UNIQUE_P is true when the vinsn
5763 must not be clonable. */
5765 create_vinsn_from_insn_rtx (rtx_insn
*insn_rtx
, bool force_unique_p
)
5767 gcc_assert (INSN_P (insn_rtx
) && !INSN_IN_STREAM_P (insn_rtx
));
5769 /* If VINSN_TYPE is not USE, retain its uniqueness. */
5770 return vinsn_create (insn_rtx
, force_unique_p
);
5773 /* Create a copy of INSN_RTX. */
5775 create_copy_of_insn_rtx (rtx insn_rtx
)
5780 if (DEBUG_INSN_P (insn_rtx
))
5781 return create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx
)),
5784 gcc_assert (NONJUMP_INSN_P (insn_rtx
));
5786 res
= create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx
)),
5789 /* Copy all REG_NOTES except REG_EQUAL/REG_EQUIV and REG_LABEL_OPERAND
5790 since mark_jump_label will make them. REG_LABEL_TARGETs are created
5791 there too, but are supposed to be sticky, so we copy them. */
5792 for (link
= REG_NOTES (insn_rtx
); link
; link
= XEXP (link
, 1))
5793 if (REG_NOTE_KIND (link
) != REG_LABEL_OPERAND
5794 && REG_NOTE_KIND (link
) != REG_EQUAL
5795 && REG_NOTE_KIND (link
) != REG_EQUIV
)
5797 if (GET_CODE (link
) == EXPR_LIST
)
5798 add_reg_note (res
, REG_NOTE_KIND (link
),
5799 copy_insn_1 (XEXP (link
, 0)));
5801 add_reg_note (res
, REG_NOTE_KIND (link
), XEXP (link
, 0));
5807 /* Change vinsn field of EXPR to hold NEW_VINSN. */
5809 change_vinsn_in_expr (expr_t expr
, vinsn_t new_vinsn
)
5811 vinsn_detach (EXPR_VINSN (expr
));
5813 EXPR_VINSN (expr
) = new_vinsn
;
5814 vinsn_attach (new_vinsn
);
5817 /* Helpers for global init. */
5818 /* This structure is used to be able to call existing bundling mechanism
5819 and calculate insn priorities. */
5820 static struct haifa_sched_info sched_sel_haifa_sched_info
=
5822 NULL
, /* init_ready_list */
5823 NULL
, /* can_schedule_ready_p */
5824 NULL
, /* schedule_more_p */
5825 NULL
, /* new_ready */
5826 NULL
, /* rgn_rank */
5827 sel_print_insn
, /* rgn_print_insn */
5828 contributes_to_priority
,
5829 NULL
, /* insn_finishes_block_p */
5835 NULL
, /* add_remove_insn */
5836 NULL
, /* begin_schedule_ready */
5837 NULL
, /* begin_move_insn */
5838 NULL
, /* advance_target_bb */
5846 /* Setup special insns used in the scheduler. */
5848 setup_nop_and_exit_insns (void)
5850 gcc_assert (nop_pattern
== NULL_RTX
5851 && exit_insn
== NULL_RTX
);
5853 nop_pattern
= constm1_rtx
;
5856 emit_insn (nop_pattern
);
5857 exit_insn
= get_insns ();
5859 set_block_for_insn (exit_insn
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
5862 /* Free special insns used in the scheduler. */
5864 free_nop_and_exit_insns (void)
5867 nop_pattern
= NULL_RTX
;
5870 /* Setup a special vinsn used in new insns initialization. */
5872 setup_nop_vinsn (void)
5874 nop_vinsn
= vinsn_create (exit_insn
, false);
5875 vinsn_attach (nop_vinsn
);
5878 /* Free a special vinsn used in new insns initialization. */
5880 free_nop_vinsn (void)
5882 gcc_assert (VINSN_COUNT (nop_vinsn
) == 1);
5883 vinsn_detach (nop_vinsn
);
5887 /* Call a set_sched_flags hook. */
5889 sel_set_sched_flags (void)
5891 /* ??? This means that set_sched_flags were called, and we decided to
5892 support speculation. However, set_sched_flags also modifies flags
5893 on current_sched_info, doing this only at global init. And we
5894 sometimes change c_s_i later. So put the correct flags again. */
5895 if (spec_info
&& targetm
.sched
.set_sched_flags
)
5896 targetm
.sched
.set_sched_flags (spec_info
);
5899 /* Setup pointers to global sched info structures. */
5901 sel_setup_sched_infos (void)
5903 rgn_setup_common_sched_info ();
5905 memcpy (&sel_common_sched_info
, common_sched_info
,
5906 sizeof (sel_common_sched_info
));
5908 sel_common_sched_info
.fix_recovery_cfg
= NULL
;
5909 sel_common_sched_info
.add_block
= NULL
;
5910 sel_common_sched_info
.estimate_number_of_insns
5911 = sel_estimate_number_of_insns
;
5912 sel_common_sched_info
.luid_for_non_insn
= sel_luid_for_non_insn
;
5913 sel_common_sched_info
.sched_pass_id
= SCHED_SEL_PASS
;
5915 common_sched_info
= &sel_common_sched_info
;
5917 current_sched_info
= &sched_sel_haifa_sched_info
;
5918 current_sched_info
->sched_max_insns_priority
=
5919 get_rgn_sched_max_insns_priority ();
5921 sel_set_sched_flags ();
5925 /* Adds basic block BB to region RGN at the position *BB_ORD_INDEX,
5926 *BB_ORD_INDEX after that is increased. */
5928 sel_add_block_to_region (basic_block bb
, int *bb_ord_index
, int rgn
)
5930 RGN_NR_BLOCKS (rgn
) += 1;
5931 RGN_DONT_CALC_DEPS (rgn
) = 0;
5932 RGN_HAS_REAL_EBB (rgn
) = 0;
5933 CONTAINING_RGN (bb
->index
) = rgn
;
5934 BLOCK_TO_BB (bb
->index
) = *bb_ord_index
;
5935 rgn_bb_table
[RGN_BLOCKS (rgn
) + *bb_ord_index
] = bb
->index
;
5938 /* FIXME: it is true only when not scheduling ebbs. */
5939 RGN_BLOCKS (rgn
+ 1) = RGN_BLOCKS (rgn
) + RGN_NR_BLOCKS (rgn
);
5942 /* Functions to support pipelining of outer loops. */
5944 /* Creates a new empty region and returns it's number. */
5946 sel_create_new_region (void)
5948 int new_rgn_number
= nr_regions
;
5950 RGN_NR_BLOCKS (new_rgn_number
) = 0;
5952 /* FIXME: This will work only when EBBs are not created. */
5953 if (new_rgn_number
!= 0)
5954 RGN_BLOCKS (new_rgn_number
) = RGN_BLOCKS (new_rgn_number
- 1) +
5955 RGN_NR_BLOCKS (new_rgn_number
- 1);
5957 RGN_BLOCKS (new_rgn_number
) = 0;
5959 /* Set the blocks of the next region so the other functions may
5960 calculate the number of blocks in the region. */
5961 RGN_BLOCKS (new_rgn_number
+ 1) = RGN_BLOCKS (new_rgn_number
) +
5962 RGN_NR_BLOCKS (new_rgn_number
);
5966 return new_rgn_number
;
5969 /* If X has a smaller topological sort number than Y, returns -1;
5970 if greater, returns 1. */
5972 bb_top_order_comparator (const void *x
, const void *y
)
5974 basic_block bb1
= *(const basic_block
*) x
;
5975 basic_block bb2
= *(const basic_block
*) y
;
5977 gcc_assert (bb1
== bb2
5978 || rev_top_order_index
[bb1
->index
]
5979 != rev_top_order_index
[bb2
->index
]);
5981 /* It's a reverse topological order in REV_TOP_ORDER_INDEX, so
5982 bbs with greater number should go earlier. */
5983 if (rev_top_order_index
[bb1
->index
] > rev_top_order_index
[bb2
->index
])
5989 /* Create a region for LOOP and return its number. If we don't want
5990 to pipeline LOOP, return -1. */
5992 make_region_from_loop (struct loop
*loop
)
5995 int new_rgn_number
= -1;
5998 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5999 int bb_ord_index
= 0;
6000 basic_block
*loop_blocks
;
6001 basic_block preheader_block
;
6004 > (unsigned) PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_BLOCKS
))
6007 /* Don't pipeline loops whose latch belongs to some of its inner loops. */
6008 for (inner
= loop
->inner
; inner
; inner
= inner
->inner
)
6009 if (flow_bb_inside_loop_p (inner
, loop
->latch
))
6012 loop
->ninsns
= num_loop_insns (loop
);
6013 if ((int) loop
->ninsns
> PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_INSNS
))
6016 loop_blocks
= get_loop_body_in_custom_order (loop
, bb_top_order_comparator
);
6018 for (i
= 0; i
< loop
->num_nodes
; i
++)
6019 if (loop_blocks
[i
]->flags
& BB_IRREDUCIBLE_LOOP
)
6025 preheader_block
= loop_preheader_edge (loop
)->src
;
6026 gcc_assert (preheader_block
);
6027 gcc_assert (loop_blocks
[0] == loop
->header
);
6029 new_rgn_number
= sel_create_new_region ();
6031 sel_add_block_to_region (preheader_block
, &bb_ord_index
, new_rgn_number
);
6032 bitmap_set_bit (bbs_in_loop_rgns
, preheader_block
->index
);
6034 for (i
= 0; i
< loop
->num_nodes
; i
++)
6036 /* Add only those blocks that haven't been scheduled in the inner loop.
6037 The exception is the basic blocks with bookkeeping code - they should
6038 be added to the region (and they actually don't belong to the loop
6039 body, but to the region containing that loop body). */
6041 gcc_assert (new_rgn_number
>= 0);
6043 if (! bitmap_bit_p (bbs_in_loop_rgns
, loop_blocks
[i
]->index
))
6045 sel_add_block_to_region (loop_blocks
[i
], &bb_ord_index
,
6047 bitmap_set_bit (bbs_in_loop_rgns
, loop_blocks
[i
]->index
);
6052 MARK_LOOP_FOR_PIPELINING (loop
);
6054 return new_rgn_number
;
6057 /* Create a new region from preheader blocks LOOP_BLOCKS. */
6059 make_region_from_loop_preheader (vec
<basic_block
> *&loop_blocks
)
6062 int new_rgn_number
= -1;
6065 /* Basic block index, to be assigned to BLOCK_TO_BB. */
6066 int bb_ord_index
= 0;
6068 new_rgn_number
= sel_create_new_region ();
6070 FOR_EACH_VEC_ELT (*loop_blocks
, i
, bb
)
6072 gcc_assert (new_rgn_number
>= 0);
6074 sel_add_block_to_region (bb
, &bb_ord_index
, new_rgn_number
);
6077 vec_free (loop_blocks
);
6081 /* Create region(s) from loop nest LOOP, such that inner loops will be
6082 pipelined before outer loops. Returns true when a region for LOOP
6085 make_regions_from_loop_nest (struct loop
*loop
)
6087 struct loop
*cur_loop
;
6090 /* Traverse all inner nodes of the loop. */
6091 for (cur_loop
= loop
->inner
; cur_loop
; cur_loop
= cur_loop
->next
)
6092 if (! bitmap_bit_p (bbs_in_loop_rgns
, cur_loop
->header
->index
))
6095 /* At this moment all regular inner loops should have been pipelined.
6096 Try to create a region from this loop. */
6097 rgn_number
= make_region_from_loop (loop
);
6102 loop_nests
.safe_push (loop
);
6106 /* Initalize data structures needed. */
6108 sel_init_pipelining (void)
6110 /* Collect loop information to be used in outer loops pipelining. */
6111 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
6112 | LOOPS_HAVE_FALLTHRU_PREHEADERS
6113 | LOOPS_HAVE_RECORDED_EXITS
6114 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
);
6115 current_loop_nest
= NULL
;
6117 bbs_in_loop_rgns
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
6118 bitmap_clear (bbs_in_loop_rgns
);
6120 recompute_rev_top_order ();
6123 /* Returns a struct loop for region RGN. */
6125 get_loop_nest_for_rgn (unsigned int rgn
)
6127 /* Regions created with extend_rgns don't have corresponding loop nests,
6128 because they don't represent loops. */
6129 if (rgn
< loop_nests
.length ())
6130 return loop_nests
[rgn
];
6135 /* True when LOOP was included into pipelining regions. */
6137 considered_for_pipelining_p (struct loop
*loop
)
6139 if (loop_depth (loop
) == 0)
6142 /* Now, the loop could be too large or irreducible. Check whether its
6143 region is in LOOP_NESTS.
6144 We determine the region number of LOOP as the region number of its
6145 latch. We can't use header here, because this header could be
6146 just removed preheader and it will give us the wrong region number.
6147 Latch can't be used because it could be in the inner loop too. */
6148 if (LOOP_MARKED_FOR_PIPELINING_P (loop
))
6150 int rgn
= CONTAINING_RGN (loop
->latch
->index
);
6152 gcc_assert ((unsigned) rgn
< loop_nests
.length ());
6159 /* Makes regions from the rest of the blocks, after loops are chosen
6162 make_regions_from_the_rest (void)
6173 /* Index in rgn_bb_table where to start allocating new regions. */
6174 cur_rgn_blocks
= nr_regions
? RGN_BLOCKS (nr_regions
) : 0;
6176 /* Make regions from all the rest basic blocks - those that don't belong to
6177 any loop or belong to irreducible loops. Prepare the data structures
6180 /* LOOP_HDR[I] == -1 if I-th bb doesn't belong to any loop,
6181 LOOP_HDR[I] == LOOP_HDR[J] iff basic blocks I and J reside within the same
6183 loop_hdr
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
6184 degree
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
6187 /* For each basic block that belongs to some loop assign the number
6188 of innermost loop it belongs to. */
6189 for (i
= 0; i
< last_basic_block_for_fn (cfun
); i
++)
6192 FOR_EACH_BB_FN (bb
, cfun
)
6194 if (bb
->loop_father
&& bb
->loop_father
->num
!= 0
6195 && !(bb
->flags
& BB_IRREDUCIBLE_LOOP
))
6196 loop_hdr
[bb
->index
] = bb
->loop_father
->num
;
6199 /* For each basic block degree is calculated as the number of incoming
6200 edges, that are going out of bbs that are not yet scheduled.
6201 The basic blocks that are scheduled have degree value of zero. */
6202 FOR_EACH_BB_FN (bb
, cfun
)
6204 degree
[bb
->index
] = 0;
6206 if (!bitmap_bit_p (bbs_in_loop_rgns
, bb
->index
))
6208 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
6209 if (!bitmap_bit_p (bbs_in_loop_rgns
, e
->src
->index
))
6210 degree
[bb
->index
]++;
6213 degree
[bb
->index
] = -1;
6216 extend_rgns (degree
, &cur_rgn_blocks
, bbs_in_loop_rgns
, loop_hdr
);
6218 /* Any block that did not end up in a region is placed into a region
6220 FOR_EACH_BB_FN (bb
, cfun
)
6221 if (degree
[bb
->index
] >= 0)
6223 rgn_bb_table
[cur_rgn_blocks
] = bb
->index
;
6224 RGN_NR_BLOCKS (nr_regions
) = 1;
6225 RGN_BLOCKS (nr_regions
) = cur_rgn_blocks
++;
6226 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
6227 RGN_HAS_REAL_EBB (nr_regions
) = 0;
6228 CONTAINING_RGN (bb
->index
) = nr_regions
++;
6229 BLOCK_TO_BB (bb
->index
) = 0;
6236 /* Free data structures used in pipelining of loops. */
6237 void sel_finish_pipelining (void)
6241 /* Release aux fields so we don't free them later by mistake. */
6242 FOR_EACH_LOOP (loop
, 0)
6245 loop_optimizer_finalize ();
6247 loop_nests
.release ();
6249 free (rev_top_order_index
);
6250 rev_top_order_index
= NULL
;
6253 /* This function replaces the find_rgns when
6254 FLAG_SEL_SCHED_PIPELINING_OUTER_LOOPS is set. */
6256 sel_find_rgns (void)
6258 sel_init_pipelining ();
6265 FOR_EACH_LOOP (loop
, (flag_sel_sched_pipelining_outer_loops
6267 : LI_ONLY_INNERMOST
))
6268 make_regions_from_loop_nest (loop
);
6271 /* Make regions from all the rest basic blocks and schedule them.
6272 These blocks include blocks that don't belong to any loop or belong
6273 to irreducible loops. */
6274 make_regions_from_the_rest ();
6276 /* We don't need bbs_in_loop_rgns anymore. */
6277 sbitmap_free (bbs_in_loop_rgns
);
6278 bbs_in_loop_rgns
= NULL
;
6281 /* Add the preheader blocks from previous loop to current region taking
6282 it from LOOP_PREHEADER_BLOCKS (current_loop_nest) and record them in *BBS.
6283 This function is only used with -fsel-sched-pipelining-outer-loops. */
6285 sel_add_loop_preheaders (bb_vec_t
*bbs
)
6289 vec
<basic_block
> *preheader_blocks
6290 = LOOP_PREHEADER_BLOCKS (current_loop_nest
);
6292 if (!preheader_blocks
)
6295 for (i
= 0; preheader_blocks
->iterate (i
, &bb
); i
++)
6297 bbs
->safe_push (bb
);
6298 last_added_blocks
.safe_push (bb
);
6302 vec_free (preheader_blocks
);
6305 /* While pipelining outer loops, returns TRUE if BB is a loop preheader.
6306 Please note that the function should also work when pipelining_p is
6307 false, because it is used when deciding whether we should or should
6308 not reschedule pipelined code. */
6310 sel_is_loop_preheader_p (basic_block bb
)
6312 if (current_loop_nest
)
6316 if (preheader_removed
)
6319 /* Preheader is the first block in the region. */
6320 if (BLOCK_TO_BB (bb
->index
) == 0)
6323 /* We used to find a preheader with the topological information.
6324 Check that the above code is equivalent to what we did before. */
6326 if (in_current_region_p (current_loop_nest
->header
))
6327 gcc_assert (!(BLOCK_TO_BB (bb
->index
)
6328 < BLOCK_TO_BB (current_loop_nest
->header
->index
)));
6330 /* Support the situation when the latch block of outer loop
6331 could be from here. */
6332 for (outer
= loop_outer (current_loop_nest
);
6334 outer
= loop_outer (outer
))
6335 if (considered_for_pipelining_p (outer
) && outer
->latch
== bb
)
6342 /* Check whether JUMP_BB ends with a jump insn that leads only to DEST_BB and
6343 can be removed, making the corresponding edge fallthrough (assuming that
6344 all basic blocks between JUMP_BB and DEST_BB are empty). */
6346 bb_has_removable_jump_to_p (basic_block jump_bb
, basic_block dest_bb
)
6348 if (!onlyjump_p (BB_END (jump_bb
))
6349 || tablejump_p (BB_END (jump_bb
), NULL
, NULL
))
6352 /* Several outgoing edges, abnormal edge or destination of jump is
6354 if (EDGE_COUNT (jump_bb
->succs
) != 1
6355 || EDGE_SUCC (jump_bb
, 0)->flags
& (EDGE_ABNORMAL
| EDGE_CROSSING
)
6356 || EDGE_SUCC (jump_bb
, 0)->dest
!= dest_bb
)
6359 /* If not anything of the upper. */
6363 /* Removes the loop preheader from the current region and saves it in
6364 PREHEADER_BLOCKS of the father loop, so they will be added later to
6365 region that represents an outer loop. */
6367 sel_remove_loop_preheader (void)
6370 int cur_rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
6372 bool all_empty_p
= true;
6373 vec
<basic_block
> *preheader_blocks
6374 = LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest
));
6376 vec_check_alloc (preheader_blocks
, 0);
6378 gcc_assert (current_loop_nest
);
6379 old_len
= preheader_blocks
->length ();
6381 /* Add blocks that aren't within the current loop to PREHEADER_BLOCKS. */
6382 for (i
= 0; i
< RGN_NR_BLOCKS (cur_rgn
); i
++)
6384 bb
= BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (i
));
6386 /* If the basic block belongs to region, but doesn't belong to
6387 corresponding loop, then it should be a preheader. */
6388 if (sel_is_loop_preheader_p (bb
))
6390 preheader_blocks
->safe_push (bb
);
6391 if (BB_END (bb
) != bb_note (bb
))
6392 all_empty_p
= false;
6396 /* Remove these blocks only after iterating over the whole region. */
6397 for (i
= preheader_blocks
->length () - 1; i
>= old_len
; i
--)
6399 bb
= (*preheader_blocks
)[i
];
6400 sel_remove_bb (bb
, false);
6403 if (!considered_for_pipelining_p (loop_outer (current_loop_nest
)))
6406 /* Immediately create new region from preheader. */
6407 make_region_from_loop_preheader (preheader_blocks
);
6410 /* If all preheader blocks are empty - dont create new empty region.
6411 Instead, remove them completely. */
6412 FOR_EACH_VEC_ELT (*preheader_blocks
, i
, bb
)
6416 basic_block prev_bb
= bb
->prev_bb
, next_bb
= bb
->next_bb
;
6418 /* Redirect all incoming edges to next basic block. */
6419 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
6421 if (! (e
->flags
& EDGE_FALLTHRU
))
6422 redirect_edge_and_branch (e
, bb
->next_bb
);
6424 redirect_edge_succ (e
, bb
->next_bb
);
6426 gcc_assert (BB_NOTE_LIST (bb
) == NULL
);
6427 delete_and_free_basic_block (bb
);
6429 /* Check if after deleting preheader there is a nonconditional
6430 jump in PREV_BB that leads to the next basic block NEXT_BB.
6431 If it is so - delete this jump and clear data sets of its
6432 basic block if it becomes empty. */
6433 if (next_bb
->prev_bb
== prev_bb
6434 && prev_bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
6435 && bb_has_removable_jump_to_p (prev_bb
, next_bb
))
6437 redirect_edge_and_branch (EDGE_SUCC (prev_bb
, 0), next_bb
);
6438 if (BB_END (prev_bb
) == bb_note (prev_bb
))
6439 free_data_sets (prev_bb
);
6442 set_immediate_dominator (CDI_DOMINATORS
, next_bb
,
6443 recompute_dominator (CDI_DOMINATORS
,
6447 vec_free (preheader_blocks
);
6450 /* Store preheader within the father's loop structure. */
6451 SET_LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest
),