1 /* Instruction scheduling pass. Selective scheduler and pipeliner.
2 Copyright (C) 2006-2017 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"
33 #include "insn-config.h"
34 #include "insn-attr.h"
38 #include "sched-int.h"
39 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
41 #ifdef INSN_SCHEDULING
44 #include "sel-sched-ir.h"
45 /* We don't have to use it except for sel_print_insn. */
46 #include "sel-sched-dump.h"
48 /* A vector holding bb info for whole scheduling pass. */
49 vec
<sel_global_bb_info_def
> sel_global_bb_info
;
51 /* A vector holding bb info. */
52 vec
<sel_region_bb_info_def
> sel_region_bb_info
;
54 /* A pool for allocating all lists. */
55 object_allocator
<_list_node
> sched_lists_pool ("sel-sched-lists");
57 /* This contains information about successors for compute_av_set. */
58 struct succs_info current_succs
;
60 /* Data structure to describe interaction with the generic scheduler utils. */
61 static struct common_sched_info_def sel_common_sched_info
;
63 /* The loop nest being pipelined. */
64 struct loop
*current_loop_nest
;
66 /* LOOP_NESTS is a vector containing the corresponding loop nest for
68 static vec
<loop_p
> loop_nests
;
70 /* Saves blocks already in loop regions, indexed by bb->index. */
71 static sbitmap bbs_in_loop_rgns
= NULL
;
73 /* CFG hooks that are saved before changing create_basic_block hook. */
74 static struct cfg_hooks orig_cfg_hooks
;
77 /* Array containing reverse topological index of function basic blocks,
78 indexed by BB->INDEX. */
79 static int *rev_top_order_index
= NULL
;
81 /* Length of the above array. */
82 static int rev_top_order_index_len
= -1;
84 /* A regset pool structure. */
87 /* The stack to which regsets are returned. */
96 /* In VV we save all generated regsets so that, when destructing the
97 pool, we can compare it with V and check that every regset was returned
101 /* The pointer of VV stack. */
107 /* The difference between allocated and returned regsets. */
109 } regset_pool
= { NULL
, 0, 0, NULL
, 0, 0, 0 };
111 /* This represents the nop pool. */
114 /* The vector which holds previously emitted nops. */
122 } nop_pool
= { NULL
, 0, 0 };
124 /* The pool for basic block notes. */
125 static vec
<rtx_note
*> bb_note_pool
;
127 /* A NOP pattern used to emit placeholder insns. */
128 rtx nop_pattern
= NULL_RTX
;
129 /* A special instruction that resides in EXIT_BLOCK.
130 EXIT_INSN is successor of the insns that lead to EXIT_BLOCK. */
131 rtx_insn
*exit_insn
= NULL
;
133 /* TRUE if while scheduling current region, which is loop, its preheader
135 bool preheader_removed
= false;
138 /* Forward static declarations. */
139 static void fence_clear (fence_t
);
141 static void deps_init_id (idata_t
, insn_t
, bool);
142 static void init_id_from_df (idata_t
, insn_t
, bool);
143 static expr_t
set_insn_init (expr_t
, vinsn_t
, int);
145 static void cfg_preds (basic_block
, insn_t
**, int *);
146 static void prepare_insn_expr (insn_t
, int);
147 static void free_history_vect (vec
<expr_history_def
> &);
149 static void move_bb_info (basic_block
, basic_block
);
150 static void remove_empty_bb (basic_block
, bool);
151 static void sel_merge_blocks (basic_block
, basic_block
);
152 static void sel_remove_loop_preheader (void);
153 static bool bb_has_removable_jump_to_p (basic_block
, basic_block
);
155 static bool insn_is_the_only_one_in_bb_p (insn_t
);
156 static void create_initial_data_sets (basic_block
);
158 static void free_av_set (basic_block
);
159 static void invalidate_av_set (basic_block
);
160 static void extend_insn_data (void);
161 static void sel_init_new_insn (insn_t
, int, int = -1);
162 static void finish_insns (void);
164 /* Various list functions. */
166 /* Copy an instruction list L. */
168 ilist_copy (ilist_t l
)
170 ilist_t head
= NULL
, *tailp
= &head
;
174 ilist_add (tailp
, ILIST_INSN (l
));
175 tailp
= &ILIST_NEXT (*tailp
);
182 /* Invert an instruction list L. */
184 ilist_invert (ilist_t l
)
190 ilist_add (&res
, ILIST_INSN (l
));
197 /* Add a new boundary to the LP list with parameters TO, PTR, and DC. */
199 blist_add (blist_t
*lp
, insn_t to
, ilist_t ptr
, deps_t dc
)
204 bnd
= BLIST_BND (*lp
);
209 BND_AV1 (bnd
) = NULL
;
213 /* Remove the list note pointed to by LP. */
215 blist_remove (blist_t
*lp
)
217 bnd_t b
= BLIST_BND (*lp
);
219 av_set_clear (&BND_AV (b
));
220 av_set_clear (&BND_AV1 (b
));
221 ilist_clear (&BND_PTR (b
));
226 /* Init a fence tail L. */
228 flist_tail_init (flist_tail_t l
)
230 FLIST_TAIL_HEAD (l
) = NULL
;
231 FLIST_TAIL_TAILP (l
) = &FLIST_TAIL_HEAD (l
);
234 /* Try to find fence corresponding to INSN in L. */
236 flist_lookup (flist_t l
, insn_t insn
)
240 if (FENCE_INSN (FLIST_FENCE (l
)) == insn
)
241 return FLIST_FENCE (l
);
249 /* Init the fields of F before running fill_insns. */
251 init_fence_for_scheduling (fence_t f
)
253 FENCE_BNDS (f
) = NULL
;
254 FENCE_PROCESSED_P (f
) = false;
255 FENCE_SCHEDULED_P (f
) = false;
258 /* Add new fence consisting of INSN and STATE to the list pointed to by LP. */
260 flist_add (flist_t
*lp
, insn_t insn
, state_t state
, deps_t dc
, void *tc
,
261 insn_t last_scheduled_insn
, vec
<rtx_insn
*, va_gc
> *executing_insns
,
262 int *ready_ticks
, int ready_ticks_size
, insn_t sched_next
,
263 int cycle
, int cycle_issued_insns
, int issue_more
,
264 bool starts_cycle_p
, bool after_stall_p
)
269 f
= FLIST_FENCE (*lp
);
271 FENCE_INSN (f
) = insn
;
273 gcc_assert (state
!= NULL
);
274 FENCE_STATE (f
) = state
;
276 FENCE_CYCLE (f
) = cycle
;
277 FENCE_ISSUED_INSNS (f
) = cycle_issued_insns
;
278 FENCE_STARTS_CYCLE_P (f
) = starts_cycle_p
;
279 FENCE_AFTER_STALL_P (f
) = after_stall_p
;
281 gcc_assert (dc
!= NULL
);
284 gcc_assert (tc
!= NULL
|| targetm
.sched
.alloc_sched_context
== NULL
);
287 FENCE_LAST_SCHEDULED_INSN (f
) = last_scheduled_insn
;
288 FENCE_ISSUE_MORE (f
) = issue_more
;
289 FENCE_EXECUTING_INSNS (f
) = executing_insns
;
290 FENCE_READY_TICKS (f
) = ready_ticks
;
291 FENCE_READY_TICKS_SIZE (f
) = ready_ticks_size
;
292 FENCE_SCHED_NEXT (f
) = sched_next
;
294 init_fence_for_scheduling (f
);
297 /* Remove the head node of the list pointed to by LP. */
299 flist_remove (flist_t
*lp
)
301 if (FENCE_INSN (FLIST_FENCE (*lp
)))
302 fence_clear (FLIST_FENCE (*lp
));
306 /* Clear the fence list pointed to by LP. */
308 flist_clear (flist_t
*lp
)
314 /* Add ORIGINAL_INSN the def list DL honoring CROSSES_CALL. */
316 def_list_add (def_list_t
*dl
, insn_t original_insn
, bool crosses_call
)
321 d
= DEF_LIST_DEF (*dl
);
323 d
->orig_insn
= original_insn
;
324 d
->crosses_call
= crosses_call
;
328 /* Functions to work with target contexts. */
330 /* Bulk target context. It is convenient for debugging purposes to ensure
331 that there are no uninitialized (null) target contexts. */
332 static tc_t bulk_tc
= (tc_t
) 1;
334 /* Target hooks wrappers. In the future we can provide some default
335 implementations for them. */
337 /* Allocate a store for the target context. */
339 alloc_target_context (void)
341 return (targetm
.sched
.alloc_sched_context
342 ? targetm
.sched
.alloc_sched_context () : bulk_tc
);
345 /* Init target context TC.
346 If CLEAN_P is true, then make TC as it is beginning of the scheduler.
347 Overwise, copy current backend context to TC. */
349 init_target_context (tc_t tc
, bool clean_p
)
351 if (targetm
.sched
.init_sched_context
)
352 targetm
.sched
.init_sched_context (tc
, clean_p
);
355 /* Allocate and initialize a target context. Meaning of CLEAN_P is the same as
356 int init_target_context (). */
358 create_target_context (bool clean_p
)
360 tc_t tc
= alloc_target_context ();
362 init_target_context (tc
, clean_p
);
366 /* Copy TC to the current backend context. */
368 set_target_context (tc_t tc
)
370 if (targetm
.sched
.set_sched_context
)
371 targetm
.sched
.set_sched_context (tc
);
374 /* TC is about to be destroyed. Free any internal data. */
376 clear_target_context (tc_t tc
)
378 if (targetm
.sched
.clear_sched_context
)
379 targetm
.sched
.clear_sched_context (tc
);
382 /* Clear and free it. */
384 delete_target_context (tc_t tc
)
386 clear_target_context (tc
);
388 if (targetm
.sched
.free_sched_context
)
389 targetm
.sched
.free_sched_context (tc
);
392 /* Make a copy of FROM in TO.
393 NB: May be this should be a hook. */
395 copy_target_context (tc_t to
, tc_t from
)
397 tc_t tmp
= create_target_context (false);
399 set_target_context (from
);
400 init_target_context (to
, false);
402 set_target_context (tmp
);
403 delete_target_context (tmp
);
406 /* Create a copy of TC. */
408 create_copy_of_target_context (tc_t tc
)
410 tc_t copy
= alloc_target_context ();
412 copy_target_context (copy
, tc
);
417 /* Clear TC and initialize it according to CLEAN_P. The meaning of CLEAN_P
418 is the same as in init_target_context (). */
420 reset_target_context (tc_t tc
, bool clean_p
)
422 clear_target_context (tc
);
423 init_target_context (tc
, clean_p
);
426 /* Functions to work with dependence contexts.
427 Dc (aka deps context, aka deps_t, aka struct deps_desc *) is short for dependence
428 context. It accumulates information about processed insns to decide if
429 current insn is dependent on the processed ones. */
431 /* Make a copy of FROM in TO. */
433 copy_deps_context (deps_t to
, deps_t from
)
435 init_deps (to
, false);
436 deps_join (to
, from
);
439 /* Allocate store for dep context. */
441 alloc_deps_context (void)
443 return XNEW (struct deps_desc
);
446 /* Allocate and initialize dep context. */
448 create_deps_context (void)
450 deps_t dc
= alloc_deps_context ();
452 init_deps (dc
, false);
456 /* Create a copy of FROM. */
458 create_copy_of_deps_context (deps_t from
)
460 deps_t to
= alloc_deps_context ();
462 copy_deps_context (to
, from
);
466 /* Clean up internal data of DC. */
468 clear_deps_context (deps_t dc
)
473 /* Clear and free DC. */
475 delete_deps_context (deps_t dc
)
477 clear_deps_context (dc
);
481 /* Clear and init DC. */
483 reset_deps_context (deps_t dc
)
485 clear_deps_context (dc
);
486 init_deps (dc
, false);
489 /* This structure describes the dependence analysis hooks for advancing
490 dependence context. */
491 static struct sched_deps_info_def advance_deps_context_sched_deps_info
=
495 NULL
, /* start_insn */
496 NULL
, /* finish_insn */
497 NULL
, /* start_lhs */
498 NULL
, /* finish_lhs */
499 NULL
, /* start_rhs */
500 NULL
, /* finish_rhs */
502 haifa_note_reg_clobber
,
504 NULL
, /* note_mem_dep */
510 /* Process INSN and add its impact on DC. */
512 advance_deps_context (deps_t dc
, insn_t insn
)
514 sched_deps_info
= &advance_deps_context_sched_deps_info
;
515 deps_analyze_insn (dc
, insn
);
519 /* Functions to work with DFA states. */
521 /* Allocate store for a DFA state. */
525 return xmalloc (dfa_state_size
);
528 /* Allocate and initialize DFA state. */
532 state_t state
= state_alloc ();
535 advance_state (state
);
539 /* Free DFA state. */
541 state_free (state_t state
)
546 /* Make a copy of FROM in TO. */
548 state_copy (state_t to
, state_t from
)
550 memcpy (to
, from
, dfa_state_size
);
553 /* Create a copy of FROM. */
555 state_create_copy (state_t from
)
557 state_t to
= state_alloc ();
559 state_copy (to
, from
);
564 /* Functions to work with fences. */
566 /* Clear the fence. */
568 fence_clear (fence_t f
)
570 state_t s
= FENCE_STATE (f
);
571 deps_t dc
= FENCE_DC (f
);
572 void *tc
= FENCE_TC (f
);
574 ilist_clear (&FENCE_BNDS (f
));
576 gcc_assert ((s
!= NULL
&& dc
!= NULL
&& tc
!= NULL
)
577 || (s
== NULL
&& dc
== NULL
&& tc
== NULL
));
582 delete_deps_context (dc
);
585 delete_target_context (tc
);
586 vec_free (FENCE_EXECUTING_INSNS (f
));
587 free (FENCE_READY_TICKS (f
));
588 FENCE_READY_TICKS (f
) = NULL
;
591 /* Init a list of fences with successors of OLD_FENCE. */
593 init_fences (insn_t old_fence
)
598 int ready_ticks_size
= get_max_uid () + 1;
600 FOR_EACH_SUCC_1 (succ
, si
, old_fence
,
601 SUCCS_NORMAL
| SUCCS_SKIP_TO_LOOP_EXITS
)
607 gcc_assert (flag_sel_sched_pipelining_outer_loops
);
609 flist_add (&fences
, succ
,
611 create_deps_context () /* dc */,
612 create_target_context (true) /* tc */,
613 NULL
/* last_scheduled_insn */,
614 NULL
, /* executing_insns */
615 XCNEWVEC (int, ready_ticks_size
), /* ready_ticks */
617 NULL
/* sched_next */,
618 1 /* cycle */, 0 /* cycle_issued_insns */,
619 issue_rate
, /* issue_more */
620 1 /* starts_cycle_p */, 0 /* after_stall_p */);
624 /* Merges two fences (filling fields of fence F with resulting values) by
625 following rules: 1) state, target context and last scheduled insn are
626 propagated from fallthrough edge if it is available;
627 2) deps context and cycle is propagated from more probable edge;
628 3) all other fields are set to corresponding constant values.
630 INSN, STATE, DC, TC, LAST_SCHEDULED_INSN, EXECUTING_INSNS,
631 READY_TICKS, READY_TICKS_SIZE, SCHED_NEXT, CYCLE, ISSUE_MORE
632 and AFTER_STALL_P are the corresponding fields of the second fence. */
634 merge_fences (fence_t f
, insn_t insn
,
635 state_t state
, deps_t dc
, void *tc
,
636 rtx_insn
*last_scheduled_insn
,
637 vec
<rtx_insn
*, va_gc
> *executing_insns
,
638 int *ready_ticks
, int ready_ticks_size
,
639 rtx sched_next
, int cycle
, int issue_more
, bool after_stall_p
)
641 insn_t last_scheduled_insn_old
= FENCE_LAST_SCHEDULED_INSN (f
);
643 gcc_assert (sel_bb_head_p (FENCE_INSN (f
))
644 && !sched_next
&& !FENCE_SCHED_NEXT (f
));
646 /* Check if we can decide which path fences came.
647 If we can't (or don't want to) - reset all. */
648 if (last_scheduled_insn
== NULL
649 || last_scheduled_insn_old
== NULL
650 /* This is a case when INSN is reachable on several paths from
651 one insn (this can happen when pipelining of outer loops is on and
652 there are two edges: one going around of inner loop and the other -
653 right through it; in such case just reset everything). */
654 || last_scheduled_insn
== last_scheduled_insn_old
)
656 state_reset (FENCE_STATE (f
));
659 reset_deps_context (FENCE_DC (f
));
660 delete_deps_context (dc
);
662 reset_target_context (FENCE_TC (f
), true);
663 delete_target_context (tc
);
665 if (cycle
> FENCE_CYCLE (f
))
666 FENCE_CYCLE (f
) = cycle
;
668 FENCE_LAST_SCHEDULED_INSN (f
) = NULL
;
669 FENCE_ISSUE_MORE (f
) = issue_rate
;
670 vec_free (executing_insns
);
672 if (FENCE_EXECUTING_INSNS (f
))
673 FENCE_EXECUTING_INSNS (f
)->block_remove (0,
674 FENCE_EXECUTING_INSNS (f
)->length ());
675 if (FENCE_READY_TICKS (f
))
676 memset (FENCE_READY_TICKS (f
), 0, FENCE_READY_TICKS_SIZE (f
));
680 edge edge_old
= NULL
, edge_new
= NULL
;
685 /* Find fallthrough edge. */
686 gcc_assert (BLOCK_FOR_INSN (insn
)->prev_bb
);
687 candidate
= find_fallthru_edge_from (BLOCK_FOR_INSN (insn
)->prev_bb
);
690 || (candidate
->src
!= BLOCK_FOR_INSN (last_scheduled_insn
)
691 && candidate
->src
!= BLOCK_FOR_INSN (last_scheduled_insn_old
)))
693 /* No fallthrough edge leading to basic block of INSN. */
694 state_reset (FENCE_STATE (f
));
697 reset_target_context (FENCE_TC (f
), true);
698 delete_target_context (tc
);
700 FENCE_LAST_SCHEDULED_INSN (f
) = NULL
;
701 FENCE_ISSUE_MORE (f
) = issue_rate
;
704 if (candidate
->src
== BLOCK_FOR_INSN (last_scheduled_insn
))
706 /* Would be weird if same insn is successor of several fallthrough
708 gcc_assert (BLOCK_FOR_INSN (insn
)->prev_bb
709 != BLOCK_FOR_INSN (last_scheduled_insn_old
));
711 state_free (FENCE_STATE (f
));
712 FENCE_STATE (f
) = state
;
714 delete_target_context (FENCE_TC (f
));
717 FENCE_LAST_SCHEDULED_INSN (f
) = last_scheduled_insn
;
718 FENCE_ISSUE_MORE (f
) = issue_more
;
722 /* Leave STATE, TC and LAST_SCHEDULED_INSN fields untouched. */
724 delete_target_context (tc
);
726 gcc_assert (BLOCK_FOR_INSN (insn
)->prev_bb
727 != BLOCK_FOR_INSN (last_scheduled_insn
));
730 /* Find edge of first predecessor (last_scheduled_insn_old->insn). */
731 FOR_EACH_SUCC_1 (succ
, si
, last_scheduled_insn_old
,
732 SUCCS_NORMAL
| SUCCS_SKIP_TO_LOOP_EXITS
)
736 /* No same successor allowed from several edges. */
737 gcc_assert (!edge_old
);
741 /* Find edge of second predecessor (last_scheduled_insn->insn). */
742 FOR_EACH_SUCC_1 (succ
, si
, last_scheduled_insn
,
743 SUCCS_NORMAL
| SUCCS_SKIP_TO_LOOP_EXITS
)
747 /* No same successor allowed from several edges. */
748 gcc_assert (!edge_new
);
753 /* Check if we can choose most probable predecessor. */
754 if (edge_old
== NULL
|| edge_new
== NULL
)
756 reset_deps_context (FENCE_DC (f
));
757 delete_deps_context (dc
);
758 vec_free (executing_insns
);
761 FENCE_CYCLE (f
) = MAX (FENCE_CYCLE (f
), cycle
);
762 if (FENCE_EXECUTING_INSNS (f
))
763 FENCE_EXECUTING_INSNS (f
)->block_remove (0,
764 FENCE_EXECUTING_INSNS (f
)->length ());
765 if (FENCE_READY_TICKS (f
))
766 memset (FENCE_READY_TICKS (f
), 0, FENCE_READY_TICKS_SIZE (f
));
769 if (edge_new
->probability
> edge_old
->probability
)
771 delete_deps_context (FENCE_DC (f
));
773 vec_free (FENCE_EXECUTING_INSNS (f
));
774 FENCE_EXECUTING_INSNS (f
) = executing_insns
;
775 free (FENCE_READY_TICKS (f
));
776 FENCE_READY_TICKS (f
) = ready_ticks
;
777 FENCE_READY_TICKS_SIZE (f
) = ready_ticks_size
;
778 FENCE_CYCLE (f
) = cycle
;
782 /* Leave DC and CYCLE untouched. */
783 delete_deps_context (dc
);
784 vec_free (executing_insns
);
789 /* Fill remaining invariant fields. */
791 FENCE_AFTER_STALL_P (f
) = 1;
793 FENCE_ISSUED_INSNS (f
) = 0;
794 FENCE_STARTS_CYCLE_P (f
) = 1;
795 FENCE_SCHED_NEXT (f
) = NULL
;
798 /* Add a new fence to NEW_FENCES list, initializing it from all
801 add_to_fences (flist_tail_t new_fences
, insn_t insn
,
802 state_t state
, deps_t dc
, void *tc
,
803 rtx_insn
*last_scheduled_insn
,
804 vec
<rtx_insn
*, va_gc
> *executing_insns
, int *ready_ticks
,
805 int ready_ticks_size
, rtx_insn
*sched_next
, int cycle
,
806 int cycle_issued_insns
, int issue_rate
,
807 bool starts_cycle_p
, bool after_stall_p
)
809 fence_t f
= flist_lookup (FLIST_TAIL_HEAD (new_fences
), insn
);
813 flist_add (FLIST_TAIL_TAILP (new_fences
), insn
, state
, dc
, tc
,
814 last_scheduled_insn
, executing_insns
, ready_ticks
,
815 ready_ticks_size
, sched_next
, cycle
, cycle_issued_insns
,
816 issue_rate
, starts_cycle_p
, after_stall_p
);
818 FLIST_TAIL_TAILP (new_fences
)
819 = &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences
));
823 merge_fences (f
, insn
, state
, dc
, tc
, last_scheduled_insn
,
824 executing_insns
, ready_ticks
, ready_ticks_size
,
825 sched_next
, cycle
, issue_rate
, after_stall_p
);
829 /* Move the first fence in the OLD_FENCES list to NEW_FENCES. */
831 move_fence_to_fences (flist_t old_fences
, flist_tail_t new_fences
)
834 flist_t
*tailp
= FLIST_TAIL_TAILP (new_fences
);
836 old
= FLIST_FENCE (old_fences
);
837 f
= flist_lookup (FLIST_TAIL_HEAD (new_fences
),
838 FENCE_INSN (FLIST_FENCE (old_fences
)));
841 merge_fences (f
, old
->insn
, old
->state
, old
->dc
, old
->tc
,
842 old
->last_scheduled_insn
, old
->executing_insns
,
843 old
->ready_ticks
, old
->ready_ticks_size
,
844 old
->sched_next
, old
->cycle
, old
->issue_more
,
850 FLIST_TAIL_TAILP (new_fences
) = &FLIST_NEXT (*tailp
);
851 *FLIST_FENCE (*tailp
) = *old
;
852 init_fence_for_scheduling (FLIST_FENCE (*tailp
));
854 FENCE_INSN (old
) = NULL
;
857 /* Add a new fence to NEW_FENCES list and initialize most of its data
860 add_clean_fence_to_fences (flist_tail_t new_fences
, insn_t succ
, fence_t fence
)
862 int ready_ticks_size
= get_max_uid () + 1;
864 add_to_fences (new_fences
,
865 succ
, state_create (), create_deps_context (),
866 create_target_context (true),
868 XCNEWVEC (int, ready_ticks_size
), ready_ticks_size
,
869 NULL
, FENCE_CYCLE (fence
) + 1,
870 0, issue_rate
, 1, FENCE_AFTER_STALL_P (fence
));
873 /* Add a new fence to NEW_FENCES list and initialize all of its data
874 from FENCE and SUCC. */
876 add_dirty_fence_to_fences (flist_tail_t new_fences
, insn_t succ
, fence_t fence
)
878 int * new_ready_ticks
879 = XNEWVEC (int, FENCE_READY_TICKS_SIZE (fence
));
881 memcpy (new_ready_ticks
, FENCE_READY_TICKS (fence
),
882 FENCE_READY_TICKS_SIZE (fence
) * sizeof (int));
883 add_to_fences (new_fences
,
884 succ
, state_create_copy (FENCE_STATE (fence
)),
885 create_copy_of_deps_context (FENCE_DC (fence
)),
886 create_copy_of_target_context (FENCE_TC (fence
)),
887 FENCE_LAST_SCHEDULED_INSN (fence
),
888 vec_safe_copy (FENCE_EXECUTING_INSNS (fence
)),
890 FENCE_READY_TICKS_SIZE (fence
),
891 FENCE_SCHED_NEXT (fence
),
893 FENCE_ISSUED_INSNS (fence
),
894 FENCE_ISSUE_MORE (fence
),
895 FENCE_STARTS_CYCLE_P (fence
),
896 FENCE_AFTER_STALL_P (fence
));
900 /* Functions to work with regset and nop pools. */
902 /* Returns the new regset from pool. It might have some of the bits set
903 from the previous usage. */
905 get_regset_from_pool (void)
909 if (regset_pool
.n
!= 0)
910 rs
= regset_pool
.v
[--regset_pool
.n
];
912 /* We need to create the regset. */
914 rs
= ALLOC_REG_SET (®_obstack
);
916 if (regset_pool
.nn
== regset_pool
.ss
)
917 regset_pool
.vv
= XRESIZEVEC (regset
, regset_pool
.vv
,
918 (regset_pool
.ss
= 2 * regset_pool
.ss
+ 1));
919 regset_pool
.vv
[regset_pool
.nn
++] = rs
;
927 /* Same as above, but returns the empty regset. */
929 get_clear_regset_from_pool (void)
931 regset rs
= get_regset_from_pool ();
937 /* Return regset RS to the pool for future use. */
939 return_regset_to_pool (regset rs
)
944 if (regset_pool
.n
== regset_pool
.s
)
945 regset_pool
.v
= XRESIZEVEC (regset
, regset_pool
.v
,
946 (regset_pool
.s
= 2 * regset_pool
.s
+ 1));
947 regset_pool
.v
[regset_pool
.n
++] = rs
;
950 /* This is used as a qsort callback for sorting regset pool stacks.
951 X and XX are addresses of two regsets. They are never equal. */
953 cmp_v_in_regset_pool (const void *x
, const void *xx
)
955 uintptr_t r1
= (uintptr_t) *((const regset
*) x
);
956 uintptr_t r2
= (uintptr_t) *((const regset
*) xx
);
964 /* Free the regset pool possibly checking for memory leaks. */
966 free_regset_pool (void)
970 regset
*v
= regset_pool
.v
;
972 int n
= regset_pool
.n
;
974 regset
*vv
= regset_pool
.vv
;
976 int nn
= regset_pool
.nn
;
980 gcc_assert (n
<= nn
);
982 /* Sort both vectors so it will be possible to compare them. */
983 qsort (v
, n
, sizeof (*v
), cmp_v_in_regset_pool
);
984 qsort (vv
, nn
, sizeof (*vv
), cmp_v_in_regset_pool
);
991 /* VV[II] was lost. */
997 gcc_assert (diff
== regset_pool
.diff
);
1000 /* If not true - we have a memory leak. */
1001 gcc_assert (regset_pool
.diff
== 0);
1003 while (regset_pool
.n
)
1006 FREE_REG_SET (regset_pool
.v
[regset_pool
.n
]);
1009 free (regset_pool
.v
);
1010 regset_pool
.v
= NULL
;
1013 free (regset_pool
.vv
);
1014 regset_pool
.vv
= NULL
;
1018 regset_pool
.diff
= 0;
1022 /* Functions to work with nop pools. NOP insns are used as temporary
1023 placeholders of the insns being scheduled to allow correct update of
1024 the data sets. When update is finished, NOPs are deleted. */
1026 /* A vinsn that is used to represent a nop. This vinsn is shared among all
1027 nops sel-sched generates. */
1028 static vinsn_t nop_vinsn
= NULL
;
1030 /* Emit a nop before INSN, taking it from pool. */
1032 get_nop_from_pool (insn_t insn
)
1036 bool old_p
= nop_pool
.n
!= 0;
1040 nop_pat
= nop_pool
.v
[--nop_pool
.n
];
1042 nop_pat
= nop_pattern
;
1044 nop
= emit_insn_before (nop_pat
, insn
);
1047 flags
= INSN_INIT_TODO_SSID
;
1049 flags
= INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SSID
;
1051 set_insn_init (INSN_EXPR (insn
), nop_vinsn
, INSN_SEQNO (insn
));
1052 sel_init_new_insn (nop
, flags
);
1057 /* Remove NOP from the instruction stream and return it to the pool. */
1059 return_nop_to_pool (insn_t nop
, bool full_tidying
)
1061 gcc_assert (INSN_IN_STREAM_P (nop
));
1062 sel_remove_insn (nop
, false, full_tidying
);
1064 /* We'll recycle this nop. */
1065 nop
->set_undeleted ();
1067 if (nop_pool
.n
== nop_pool
.s
)
1068 nop_pool
.v
= XRESIZEVEC (rtx_insn
*, nop_pool
.v
,
1069 (nop_pool
.s
= 2 * nop_pool
.s
+ 1));
1070 nop_pool
.v
[nop_pool
.n
++] = nop
;
1073 /* Free the nop pool. */
1075 free_nop_pool (void)
1084 /* Skip unspec to support ia64 speculation. Called from rtx_equal_p_cb.
1085 The callback is given two rtxes XX and YY and writes the new rtxes
1086 to NX and NY in case some needs to be skipped. */
1088 skip_unspecs_callback (const_rtx
*xx
, const_rtx
*yy
, rtx
*nx
, rtx
* ny
)
1093 if (GET_CODE (x
) == UNSPEC
1094 && (targetm
.sched
.skip_rtx_p
== NULL
1095 || targetm
.sched
.skip_rtx_p (x
)))
1097 *nx
= XVECEXP (x
, 0, 0);
1098 *ny
= CONST_CAST_RTX (y
);
1102 if (GET_CODE (y
) == UNSPEC
1103 && (targetm
.sched
.skip_rtx_p
== NULL
1104 || targetm
.sched
.skip_rtx_p (y
)))
1106 *nx
= CONST_CAST_RTX (x
);
1107 *ny
= XVECEXP (y
, 0, 0);
1114 /* Callback, called from hash_rtx_cb. Helps to hash UNSPEC rtx X in a correct way
1115 to support ia64 speculation. When changes are needed, new rtx X and new mode
1116 NMODE are written, and the callback returns true. */
1118 hash_with_unspec_callback (const_rtx x
, machine_mode mode ATTRIBUTE_UNUSED
,
1119 rtx
*nx
, machine_mode
* nmode
)
1121 if (GET_CODE (x
) == UNSPEC
1122 && targetm
.sched
.skip_rtx_p
1123 && targetm
.sched
.skip_rtx_p (x
))
1125 *nx
= XVECEXP (x
, 0 ,0);
1133 /* Returns LHS and RHS are ok to be scheduled separately. */
1135 lhs_and_rhs_separable_p (rtx lhs
, rtx rhs
)
1137 if (lhs
== NULL
|| rhs
== NULL
)
1140 /* Do not schedule constants as rhs: no point to use reg, if const
1141 can be used. Moreover, scheduling const as rhs may lead to mode
1142 mismatch cause consts don't have modes but they could be merged
1143 from branches where the same const used in different modes. */
1144 if (CONSTANT_P (rhs
))
1147 /* ??? Do not rename predicate registers to avoid ICEs in bundling. */
1148 if (COMPARISON_P (rhs
))
1151 /* Do not allow single REG to be an rhs. */
1155 /* See comment at find_used_regs_1 (*1) for explanation of this
1157 /* FIXME: remove this later. */
1161 /* This will filter all tricky things like ZERO_EXTRACT etc.
1162 For now we don't handle it. */
1163 if (!REG_P (lhs
) && !MEM_P (lhs
))
1169 /* Initialize vinsn VI for INSN. Only for use from vinsn_create (). When
1170 FORCE_UNIQUE_P is true, the resulting vinsn will not be clonable. This is
1171 used e.g. for insns from recovery blocks. */
1173 vinsn_init (vinsn_t vi
, insn_t insn
, bool force_unique_p
)
1175 hash_rtx_callback_function hrcf
;
1178 VINSN_INSN_RTX (vi
) = insn
;
1179 VINSN_COUNT (vi
) = 0;
1182 if (INSN_NOP_P (insn
))
1185 if (DF_INSN_UID_SAFE_GET (INSN_UID (insn
)) != NULL
)
1186 init_id_from_df (VINSN_ID (vi
), insn
, force_unique_p
);
1188 deps_init_id (VINSN_ID (vi
), insn
, force_unique_p
);
1190 /* Hash vinsn depending on whether it is separable or not. */
1191 hrcf
= targetm
.sched
.skip_rtx_p
? hash_with_unspec_callback
: NULL
;
1192 if (VINSN_SEPARABLE_P (vi
))
1194 rtx rhs
= VINSN_RHS (vi
);
1196 VINSN_HASH (vi
) = hash_rtx_cb (rhs
, GET_MODE (rhs
),
1197 NULL
, NULL
, false, hrcf
);
1198 VINSN_HASH_RTX (vi
) = hash_rtx_cb (VINSN_PATTERN (vi
),
1199 VOIDmode
, NULL
, NULL
,
1204 VINSN_HASH (vi
) = hash_rtx_cb (VINSN_PATTERN (vi
), VOIDmode
,
1205 NULL
, NULL
, false, hrcf
);
1206 VINSN_HASH_RTX (vi
) = VINSN_HASH (vi
);
1209 insn_class
= haifa_classify_insn (insn
);
1211 && (!targetm
.sched
.get_insn_spec_ds
1212 || ((targetm
.sched
.get_insn_spec_ds (insn
) & BEGIN_CONTROL
)
1214 VINSN_MAY_TRAP_P (vi
) = true;
1216 VINSN_MAY_TRAP_P (vi
) = false;
1219 /* Indicate that VI has become the part of an rtx object. */
1221 vinsn_attach (vinsn_t vi
)
1223 /* Assert that VI is not pending for deletion. */
1224 gcc_assert (VINSN_INSN_RTX (vi
));
1229 /* Create and init VI from the INSN. Use UNIQUE_P for determining the correct
1232 vinsn_create (insn_t insn
, bool force_unique_p
)
1234 vinsn_t vi
= XCNEW (struct vinsn_def
);
1236 vinsn_init (vi
, insn
, force_unique_p
);
1240 /* Return a copy of VI. When REATTACH_P is true, detach VI and attach
1243 vinsn_copy (vinsn_t vi
, bool reattach_p
)
1246 bool unique
= VINSN_UNIQUE_P (vi
);
1249 copy
= create_copy_of_insn_rtx (VINSN_INSN_RTX (vi
));
1250 new_vi
= create_vinsn_from_insn_rtx (copy
, unique
);
1254 vinsn_attach (new_vi
);
1260 /* Delete the VI vinsn and free its data. */
1262 vinsn_delete (vinsn_t vi
)
1264 gcc_assert (VINSN_COUNT (vi
) == 0);
1266 if (!INSN_NOP_P (VINSN_INSN_RTX (vi
)))
1268 return_regset_to_pool (VINSN_REG_SETS (vi
));
1269 return_regset_to_pool (VINSN_REG_USES (vi
));
1270 return_regset_to_pool (VINSN_REG_CLOBBERS (vi
));
1276 /* Indicate that VI is no longer a part of some rtx object.
1277 Remove VI if it is no longer needed. */
1279 vinsn_detach (vinsn_t vi
)
1281 gcc_assert (VINSN_COUNT (vi
) > 0);
1283 if (--VINSN_COUNT (vi
) == 0)
1287 /* Returns TRUE if VI is a branch. */
1289 vinsn_cond_branch_p (vinsn_t vi
)
1293 if (!VINSN_UNIQUE_P (vi
))
1296 insn
= VINSN_INSN_RTX (vi
);
1297 if (BB_END (BLOCK_FOR_INSN (insn
)) != insn
)
1300 return control_flow_insn_p (insn
);
1303 /* Return latency of INSN. */
1305 sel_insn_rtx_cost (rtx_insn
*insn
)
1309 /* A USE insn, or something else we don't need to
1310 understand. We can't pass these directly to
1311 result_ready_cost or insn_default_latency because it will
1312 trigger a fatal error for unrecognizable insns. */
1313 if (recog_memoized (insn
) < 0)
1317 cost
= insn_default_latency (insn
);
1326 /* Return the cost of the VI.
1327 !!! FIXME: Unify with haifa-sched.c: insn_cost (). */
1329 sel_vinsn_cost (vinsn_t vi
)
1331 int cost
= vi
->cost
;
1335 cost
= sel_insn_rtx_cost (VINSN_INSN_RTX (vi
));
1343 /* Functions for insn emitting. */
1345 /* Emit new insn after AFTER based on PATTERN and initialize its data from
1348 sel_gen_insn_from_rtx_after (rtx pattern
, expr_t expr
, int seqno
, insn_t after
)
1352 gcc_assert (EXPR_TARGET_AVAILABLE (expr
) == true);
1354 new_insn
= emit_insn_after (pattern
, after
);
1355 set_insn_init (expr
, NULL
, seqno
);
1356 sel_init_new_insn (new_insn
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SSID
);
1361 /* Force newly generated vinsns to be unique. */
1362 static bool init_insn_force_unique_p
= false;
1364 /* Emit new speculation recovery insn after AFTER based on PATTERN and
1365 initialize its data from EXPR and SEQNO. */
1367 sel_gen_recovery_insn_from_rtx_after (rtx pattern
, expr_t expr
, int seqno
,
1372 gcc_assert (!init_insn_force_unique_p
);
1374 init_insn_force_unique_p
= true;
1375 insn
= sel_gen_insn_from_rtx_after (pattern
, expr
, seqno
, after
);
1376 CANT_MOVE (insn
) = 1;
1377 init_insn_force_unique_p
= false;
1382 /* Emit new insn after AFTER based on EXPR and SEQNO. If VINSN is not NULL,
1383 take it as a new vinsn instead of EXPR's vinsn.
1384 We simplify insns later, after scheduling region in
1385 simplify_changed_insns. */
1387 sel_gen_insn_from_expr_after (expr_t expr
, vinsn_t vinsn
, int seqno
,
1394 emit_expr
= set_insn_init (expr
, vinsn
? vinsn
: EXPR_VINSN (expr
),
1396 insn
= EXPR_INSN_RTX (emit_expr
);
1398 /* The insn may come from the transformation cache, which may hold already
1399 deleted insns, so mark it as not deleted. */
1400 insn
->set_undeleted ();
1402 add_insn_after (insn
, after
, BLOCK_FOR_INSN (insn
));
1404 flags
= INSN_INIT_TODO_SSID
;
1405 if (INSN_LUID (insn
) == 0)
1406 flags
|= INSN_INIT_TODO_LUID
;
1407 sel_init_new_insn (insn
, flags
);
1412 /* Move insn from EXPR after AFTER. */
1414 sel_move_insn (expr_t expr
, int seqno
, insn_t after
)
1416 insn_t insn
= EXPR_INSN_RTX (expr
);
1417 basic_block bb
= BLOCK_FOR_INSN (after
);
1418 insn_t next
= NEXT_INSN (after
);
1420 /* Assert that in move_op we disconnected this insn properly. */
1421 gcc_assert (EXPR_VINSN (INSN_EXPR (insn
)) != NULL
);
1422 SET_PREV_INSN (insn
) = after
;
1423 SET_NEXT_INSN (insn
) = next
;
1425 SET_NEXT_INSN (after
) = insn
;
1426 SET_PREV_INSN (next
) = insn
;
1428 /* Update links from insn to bb and vice versa. */
1429 df_insn_change_bb (insn
, bb
);
1430 if (BB_END (bb
) == after
)
1433 prepare_insn_expr (insn
, seqno
);
1438 /* Functions to work with right-hand sides. */
1440 /* Search for a hash value determined by UID/NEW_VINSN in a sorted vector
1441 VECT and return true when found. Use NEW_VINSN for comparison only when
1442 COMPARE_VINSNS is true. Write to INDP the index on which
1443 the search has stopped, such that inserting the new element at INDP will
1444 retain VECT's sort order. */
1446 find_in_history_vect_1 (vec
<expr_history_def
> vect
,
1447 unsigned uid
, vinsn_t new_vinsn
,
1448 bool compare_vinsns
, int *indp
)
1450 expr_history_def
*arr
;
1451 int i
, j
, len
= vect
.length ();
1459 arr
= vect
.address ();
1464 unsigned auid
= arr
[i
].uid
;
1465 vinsn_t avinsn
= arr
[i
].new_expr_vinsn
;
1468 /* When undoing transformation on a bookkeeping copy, the new vinsn
1469 may not be exactly equal to the one that is saved in the vector.
1470 This is because the insn whose copy we're checking was possibly
1471 substituted itself. */
1472 && (! compare_vinsns
1473 || vinsn_equal_p (avinsn
, new_vinsn
)))
1478 else if (auid
> uid
)
1487 /* Search for a uid of INSN and NEW_VINSN in a sorted vector VECT. Return
1488 the position found or -1, if no such value is in vector.
1489 Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */
1491 find_in_history_vect (vec
<expr_history_def
> vect
, rtx insn
,
1492 vinsn_t new_vinsn
, bool originators_p
)
1496 if (find_in_history_vect_1 (vect
, INSN_UID (insn
), new_vinsn
,
1500 if (INSN_ORIGINATORS (insn
) && originators_p
)
1505 EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn
), 0, uid
, bi
)
1506 if (find_in_history_vect_1 (vect
, uid
, new_vinsn
, false, &ind
))
1513 /* Insert new element in a sorted history vector pointed to by PVECT,
1514 if it is not there already. The element is searched using
1515 UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN and SPEC_DS save
1516 the history of a transformation. */
1518 insert_in_history_vect (vec
<expr_history_def
> *pvect
,
1519 unsigned uid
, enum local_trans_type type
,
1520 vinsn_t old_expr_vinsn
, vinsn_t new_expr_vinsn
,
1523 vec
<expr_history_def
> vect
= *pvect
;
1524 expr_history_def temp
;
1528 res
= find_in_history_vect_1 (vect
, uid
, new_expr_vinsn
, true, &ind
);
1532 expr_history_def
*phist
= &vect
[ind
];
1534 /* It is possible that speculation types of expressions that were
1535 propagated through different paths will be different here. In this
1536 case, merge the status to get the correct check later. */
1537 if (phist
->spec_ds
!= spec_ds
)
1538 phist
->spec_ds
= ds_max_merge (phist
->spec_ds
, spec_ds
);
1543 temp
.old_expr_vinsn
= old_expr_vinsn
;
1544 temp
.new_expr_vinsn
= new_expr_vinsn
;
1545 temp
.spec_ds
= spec_ds
;
1548 vinsn_attach (old_expr_vinsn
);
1549 vinsn_attach (new_expr_vinsn
);
1550 vect
.safe_insert (ind
, temp
);
1554 /* Free history vector PVECT. */
1556 free_history_vect (vec
<expr_history_def
> &pvect
)
1559 expr_history_def
*phist
;
1561 if (! pvect
.exists ())
1564 for (i
= 0; pvect
.iterate (i
, &phist
); i
++)
1566 vinsn_detach (phist
->old_expr_vinsn
);
1567 vinsn_detach (phist
->new_expr_vinsn
);
1573 /* Merge vector FROM to PVECT. */
1575 merge_history_vect (vec
<expr_history_def
> *pvect
,
1576 vec
<expr_history_def
> from
)
1578 expr_history_def
*phist
;
1581 /* We keep this vector sorted. */
1582 for (i
= 0; from
.iterate (i
, &phist
); i
++)
1583 insert_in_history_vect (pvect
, phist
->uid
, phist
->type
,
1584 phist
->old_expr_vinsn
, phist
->new_expr_vinsn
,
1588 /* Compare two vinsns as rhses if possible and as vinsns otherwise. */
1590 vinsn_equal_p (vinsn_t x
, vinsn_t y
)
1592 rtx_equal_p_callback_function repcf
;
1597 if (VINSN_TYPE (x
) != VINSN_TYPE (y
))
1600 if (VINSN_HASH (x
) != VINSN_HASH (y
))
1603 repcf
= targetm
.sched
.skip_rtx_p
? skip_unspecs_callback
: NULL
;
1604 if (VINSN_SEPARABLE_P (x
))
1606 /* Compare RHSes of VINSNs. */
1607 gcc_assert (VINSN_RHS (x
));
1608 gcc_assert (VINSN_RHS (y
));
1610 return rtx_equal_p_cb (VINSN_RHS (x
), VINSN_RHS (y
), repcf
);
1613 return rtx_equal_p_cb (VINSN_PATTERN (x
), VINSN_PATTERN (y
), repcf
);
1617 /* Functions for working with expressions. */
1619 /* Initialize EXPR. */
1621 init_expr (expr_t expr
, vinsn_t vi
, int spec
, int use
, int priority
,
1622 int sched_times
, int orig_bb_index
, ds_t spec_done_ds
,
1623 ds_t spec_to_check_ds
, int orig_sched_cycle
,
1624 vec
<expr_history_def
> history
,
1625 signed char target_available
,
1626 bool was_substituted
, bool was_renamed
, bool needs_spec_check_p
,
1631 EXPR_VINSN (expr
) = vi
;
1632 EXPR_SPEC (expr
) = spec
;
1633 EXPR_USEFULNESS (expr
) = use
;
1634 EXPR_PRIORITY (expr
) = priority
;
1635 EXPR_PRIORITY_ADJ (expr
) = 0;
1636 EXPR_SCHED_TIMES (expr
) = sched_times
;
1637 EXPR_ORIG_BB_INDEX (expr
) = orig_bb_index
;
1638 EXPR_ORIG_SCHED_CYCLE (expr
) = orig_sched_cycle
;
1639 EXPR_SPEC_DONE_DS (expr
) = spec_done_ds
;
1640 EXPR_SPEC_TO_CHECK_DS (expr
) = spec_to_check_ds
;
1642 if (history
.exists ())
1643 EXPR_HISTORY_OF_CHANGES (expr
) = history
;
1645 EXPR_HISTORY_OF_CHANGES (expr
).create (0);
1647 EXPR_TARGET_AVAILABLE (expr
) = target_available
;
1648 EXPR_WAS_SUBSTITUTED (expr
) = was_substituted
;
1649 EXPR_WAS_RENAMED (expr
) = was_renamed
;
1650 EXPR_NEEDS_SPEC_CHECK_P (expr
) = needs_spec_check_p
;
1651 EXPR_CANT_MOVE (expr
) = cant_move
;
1654 /* Make a copy of the expr FROM into the expr TO. */
1656 copy_expr (expr_t to
, expr_t from
)
1658 vec
<expr_history_def
> temp
= vNULL
;
1660 if (EXPR_HISTORY_OF_CHANGES (from
).exists ())
1663 expr_history_def
*phist
;
1665 temp
= EXPR_HISTORY_OF_CHANGES (from
).copy ();
1667 temp
.iterate (i
, &phist
);
1670 vinsn_attach (phist
->old_expr_vinsn
);
1671 vinsn_attach (phist
->new_expr_vinsn
);
1675 init_expr (to
, EXPR_VINSN (from
), EXPR_SPEC (from
),
1676 EXPR_USEFULNESS (from
), EXPR_PRIORITY (from
),
1677 EXPR_SCHED_TIMES (from
), EXPR_ORIG_BB_INDEX (from
),
1678 EXPR_SPEC_DONE_DS (from
), EXPR_SPEC_TO_CHECK_DS (from
),
1679 EXPR_ORIG_SCHED_CYCLE (from
), temp
,
1680 EXPR_TARGET_AVAILABLE (from
), EXPR_WAS_SUBSTITUTED (from
),
1681 EXPR_WAS_RENAMED (from
), EXPR_NEEDS_SPEC_CHECK_P (from
),
1682 EXPR_CANT_MOVE (from
));
1685 /* Same, but the final expr will not ever be in av sets, so don't copy
1686 "uninteresting" data such as bitmap cache. */
1688 copy_expr_onside (expr_t to
, expr_t from
)
1690 init_expr (to
, EXPR_VINSN (from
), EXPR_SPEC (from
), EXPR_USEFULNESS (from
),
1691 EXPR_PRIORITY (from
), EXPR_SCHED_TIMES (from
), 0,
1692 EXPR_SPEC_DONE_DS (from
), EXPR_SPEC_TO_CHECK_DS (from
), 0,
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 /* Prepare the expr of INSN for scheduling. Used when moving insn and when
1700 initializing new insns. */
1702 prepare_insn_expr (insn_t insn
, int seqno
)
1704 expr_t expr
= INSN_EXPR (insn
);
1707 INSN_SEQNO (insn
) = seqno
;
1708 EXPR_ORIG_BB_INDEX (expr
) = BLOCK_NUM (insn
);
1709 EXPR_SPEC (expr
) = 0;
1710 EXPR_ORIG_SCHED_CYCLE (expr
) = 0;
1711 EXPR_WAS_SUBSTITUTED (expr
) = 0;
1712 EXPR_WAS_RENAMED (expr
) = 0;
1713 EXPR_TARGET_AVAILABLE (expr
) = 1;
1714 INSN_LIVE_VALID_P (insn
) = false;
1716 /* ??? If this expression is speculative, make its dependence
1717 as weak as possible. We can filter this expression later
1718 in process_spec_exprs, because we do not distinguish
1719 between the status we got during compute_av_set and the
1720 existing status. To be fixed. */
1721 ds
= EXPR_SPEC_DONE_DS (expr
);
1723 EXPR_SPEC_DONE_DS (expr
) = ds_get_max_dep_weak (ds
);
1725 free_history_vect (EXPR_HISTORY_OF_CHANGES (expr
));
1728 /* Update target_available bits when merging exprs TO and FROM. SPLIT_POINT
1729 is non-null when expressions are merged from different successors at
1732 update_target_availability (expr_t to
, expr_t from
, insn_t split_point
)
1734 if (EXPR_TARGET_AVAILABLE (to
) < 0
1735 || EXPR_TARGET_AVAILABLE (from
) < 0)
1736 EXPR_TARGET_AVAILABLE (to
) = -1;
1739 /* We try to detect the case when one of the expressions
1740 can only be reached through another one. In this case,
1741 we can do better. */
1742 if (split_point
== NULL
)
1746 toind
= EXPR_ORIG_BB_INDEX (to
);
1747 fromind
= EXPR_ORIG_BB_INDEX (from
);
1749 if (toind
&& toind
== fromind
)
1750 /* Do nothing -- everything is done in
1751 merge_with_other_exprs. */
1754 EXPR_TARGET_AVAILABLE (to
) = -1;
1756 else if (EXPR_TARGET_AVAILABLE (from
) == 0
1758 && REG_P (EXPR_LHS (from
))
1759 && REGNO (EXPR_LHS (to
)) != REGNO (EXPR_LHS (from
)))
1760 EXPR_TARGET_AVAILABLE (to
) = -1;
1762 EXPR_TARGET_AVAILABLE (to
) &= EXPR_TARGET_AVAILABLE (from
);
1766 /* Update speculation bits when merging exprs TO and FROM. SPLIT_POINT
1767 is non-null when expressions are merged from different successors at
1770 update_speculative_bits (expr_t to
, expr_t from
, insn_t split_point
)
1772 ds_t old_to_ds
, old_from_ds
;
1774 old_to_ds
= EXPR_SPEC_DONE_DS (to
);
1775 old_from_ds
= EXPR_SPEC_DONE_DS (from
);
1777 EXPR_SPEC_DONE_DS (to
) = ds_max_merge (old_to_ds
, old_from_ds
);
1778 EXPR_SPEC_TO_CHECK_DS (to
) |= EXPR_SPEC_TO_CHECK_DS (from
);
1779 EXPR_NEEDS_SPEC_CHECK_P (to
) |= EXPR_NEEDS_SPEC_CHECK_P (from
);
1781 /* When merging e.g. control & data speculative exprs, or a control
1782 speculative with a control&data speculative one, we really have
1783 to change vinsn too. Also, when speculative status is changed,
1784 we also need to record this as a transformation in expr's history. */
1785 if ((old_to_ds
& SPECULATIVE
) || (old_from_ds
& SPECULATIVE
))
1787 old_to_ds
= ds_get_speculation_types (old_to_ds
);
1788 old_from_ds
= ds_get_speculation_types (old_from_ds
);
1790 if (old_to_ds
!= old_from_ds
)
1794 /* When both expressions are speculative, we need to change
1796 if ((old_to_ds
& SPECULATIVE
) && (old_from_ds
& SPECULATIVE
))
1800 res
= speculate_expr (to
, EXPR_SPEC_DONE_DS (to
));
1801 gcc_assert (res
>= 0);
1804 if (split_point
!= NULL
)
1806 /* Record the change with proper status. */
1807 record_ds
= EXPR_SPEC_DONE_DS (to
) & SPECULATIVE
;
1808 record_ds
&= ~(old_to_ds
& SPECULATIVE
);
1809 record_ds
&= ~(old_from_ds
& SPECULATIVE
);
1811 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to
),
1812 INSN_UID (split_point
), TRANS_SPECULATION
,
1813 EXPR_VINSN (from
), EXPR_VINSN (to
),
1821 /* Merge bits of FROM expr to TO expr. When SPLIT_POINT is not NULL,
1822 this is done along different paths. */
1824 merge_expr_data (expr_t to
, expr_t from
, insn_t split_point
)
1826 /* Choose the maximum of the specs of merged exprs. This is required
1827 for correctness of bookkeeping. */
1828 if (EXPR_SPEC (to
) < EXPR_SPEC (from
))
1829 EXPR_SPEC (to
) = EXPR_SPEC (from
);
1832 EXPR_USEFULNESS (to
) += EXPR_USEFULNESS (from
);
1834 EXPR_USEFULNESS (to
) = MAX (EXPR_USEFULNESS (to
),
1835 EXPR_USEFULNESS (from
));
1837 if (EXPR_PRIORITY (to
) < EXPR_PRIORITY (from
))
1838 EXPR_PRIORITY (to
) = EXPR_PRIORITY (from
);
1840 if (EXPR_SCHED_TIMES (to
) > EXPR_SCHED_TIMES (from
))
1841 EXPR_SCHED_TIMES (to
) = EXPR_SCHED_TIMES (from
);
1843 if (EXPR_ORIG_BB_INDEX (to
) != EXPR_ORIG_BB_INDEX (from
))
1844 EXPR_ORIG_BB_INDEX (to
) = 0;
1846 EXPR_ORIG_SCHED_CYCLE (to
) = MIN (EXPR_ORIG_SCHED_CYCLE (to
),
1847 EXPR_ORIG_SCHED_CYCLE (from
));
1849 EXPR_WAS_SUBSTITUTED (to
) |= EXPR_WAS_SUBSTITUTED (from
);
1850 EXPR_WAS_RENAMED (to
) |= EXPR_WAS_RENAMED (from
);
1851 EXPR_CANT_MOVE (to
) |= EXPR_CANT_MOVE (from
);
1853 merge_history_vect (&EXPR_HISTORY_OF_CHANGES (to
),
1854 EXPR_HISTORY_OF_CHANGES (from
));
1855 update_target_availability (to
, from
, split_point
);
1856 update_speculative_bits (to
, from
, split_point
);
1859 /* Merge bits of FROM expr to TO expr. Vinsns in the exprs should be equal
1860 in terms of vinsn_equal_p. SPLIT_POINT is non-null when expressions
1861 are merged from different successors at a split point. */
1863 merge_expr (expr_t to
, expr_t from
, insn_t split_point
)
1865 vinsn_t to_vi
= EXPR_VINSN (to
);
1866 vinsn_t from_vi
= EXPR_VINSN (from
);
1868 gcc_assert (vinsn_equal_p (to_vi
, from_vi
));
1870 /* Make sure that speculative pattern is propagated into exprs that
1871 have non-speculative one. This will provide us with consistent
1872 speculative bits and speculative patterns inside expr. */
1873 if (EXPR_SPEC_DONE_DS (to
) == 0
1874 && (EXPR_SPEC_DONE_DS (from
) != 0
1875 /* Do likewise for volatile insns, so that we always retain
1876 the may_trap_p bit on the resulting expression. However,
1877 avoid propagating the trapping bit into the instructions
1878 already speculated. This would result in replacing the
1879 speculative pattern with the non-speculative one and breaking
1880 the speculation support. */
1881 || (!VINSN_MAY_TRAP_P (EXPR_VINSN (to
))
1882 && VINSN_MAY_TRAP_P (EXPR_VINSN (from
)))))
1883 change_vinsn_in_expr (to
, EXPR_VINSN (from
));
1885 merge_expr_data (to
, from
, split_point
);
1886 gcc_assert (EXPR_USEFULNESS (to
) <= REG_BR_PROB_BASE
);
1889 /* Clear the information of this EXPR. */
1891 clear_expr (expr_t expr
)
1894 vinsn_detach (EXPR_VINSN (expr
));
1895 EXPR_VINSN (expr
) = NULL
;
1897 free_history_vect (EXPR_HISTORY_OF_CHANGES (expr
));
1900 /* For a given LV_SET, mark EXPR having unavailable target register. */
1902 set_unavailable_target_for_expr (expr_t expr
, regset lv_set
)
1904 if (EXPR_SEPARABLE_P (expr
))
1906 if (REG_P (EXPR_LHS (expr
))
1907 && register_unavailable_p (lv_set
, EXPR_LHS (expr
)))
1909 /* If it's an insn like r1 = use (r1, ...), and it exists in
1910 different forms in each of the av_sets being merged, we can't say
1911 whether original destination register is available or not.
1912 However, this still works if destination register is not used
1913 in the original expression: if the branch at which LV_SET we're
1914 looking here is not actually 'other branch' in sense that same
1915 expression is available through it (but it can't be determined
1916 at computation stage because of transformations on one of the
1917 branches), it still won't affect the availability.
1918 Liveness of a register somewhere on a code motion path means
1919 it's either read somewhere on a codemotion path, live on
1920 'other' branch, live at the point immediately following
1921 the original operation, or is read by the original operation.
1922 The latter case is filtered out in the condition below.
1923 It still doesn't cover the case when register is defined and used
1924 somewhere within the code motion path, and in this case we could
1925 miss a unifying code motion along both branches using a renamed
1926 register, but it won't affect a code correctness since upon
1927 an actual code motion a bookkeeping code would be generated. */
1928 if (register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr
)),
1930 EXPR_TARGET_AVAILABLE (expr
) = -1;
1932 EXPR_TARGET_AVAILABLE (expr
) = false;
1938 reg_set_iterator rsi
;
1940 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (EXPR_VINSN (expr
)),
1942 if (bitmap_bit_p (lv_set
, regno
))
1944 EXPR_TARGET_AVAILABLE (expr
) = false;
1948 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (EXPR_VINSN (expr
)),
1950 if (bitmap_bit_p (lv_set
, regno
))
1952 EXPR_TARGET_AVAILABLE (expr
) = false;
1958 /* Try to make EXPR speculative. Return 1 when EXPR's pattern
1959 or dependence status have changed, 2 when also the target register
1960 became unavailable, 0 if nothing had to be changed. */
1962 speculate_expr (expr_t expr
, ds_t ds
)
1965 rtx_insn
*orig_insn_rtx
;
1967 ds_t target_ds
, current_ds
;
1969 /* Obtain the status we need to put on EXPR. */
1970 target_ds
= (ds
& SPECULATIVE
);
1971 current_ds
= EXPR_SPEC_DONE_DS (expr
);
1972 ds
= ds_full_merge (current_ds
, target_ds
, NULL_RTX
, NULL_RTX
);
1974 orig_insn_rtx
= EXPR_INSN_RTX (expr
);
1976 res
= sched_speculate_insn (orig_insn_rtx
, ds
, &spec_pat
);
1981 EXPR_SPEC_DONE_DS (expr
) = ds
;
1982 return current_ds
!= ds
? 1 : 0;
1986 rtx_insn
*spec_insn_rtx
=
1987 create_insn_rtx_from_pattern (spec_pat
, NULL_RTX
);
1988 vinsn_t spec_vinsn
= create_vinsn_from_insn_rtx (spec_insn_rtx
, false);
1990 change_vinsn_in_expr (expr
, spec_vinsn
);
1991 EXPR_SPEC_DONE_DS (expr
) = ds
;
1992 EXPR_NEEDS_SPEC_CHECK_P (expr
) = true;
1994 /* Do not allow clobbering the address register of speculative
1996 if (register_unavailable_p (VINSN_REG_USES (EXPR_VINSN (expr
)),
1997 expr_dest_reg (expr
)))
1999 EXPR_TARGET_AVAILABLE (expr
) = false;
2015 /* Return a destination register, if any, of EXPR. */
2017 expr_dest_reg (expr_t expr
)
2019 rtx dest
= VINSN_LHS (EXPR_VINSN (expr
));
2021 if (dest
!= NULL_RTX
&& REG_P (dest
))
2027 /* Returns the REGNO of the R's destination. */
2029 expr_dest_regno (expr_t expr
)
2031 rtx dest
= expr_dest_reg (expr
);
2033 gcc_assert (dest
!= NULL_RTX
);
2034 return REGNO (dest
);
2037 /* For a given LV_SET, mark all expressions in JOIN_SET, but not present in
2038 AV_SET having unavailable target register. */
2040 mark_unavailable_targets (av_set_t join_set
, av_set_t av_set
, regset lv_set
)
2043 av_set_iterator avi
;
2045 FOR_EACH_EXPR (expr
, avi
, join_set
)
2046 if (av_set_lookup (av_set
, EXPR_VINSN (expr
)) == NULL
)
2047 set_unavailable_target_for_expr (expr
, lv_set
);
2051 /* Returns true if REG (at least partially) is present in REGS. */
2053 register_unavailable_p (regset regs
, rtx reg
)
2055 unsigned regno
, end_regno
;
2057 regno
= REGNO (reg
);
2058 if (bitmap_bit_p (regs
, regno
))
2061 end_regno
= END_REGNO (reg
);
2063 while (++regno
< end_regno
)
2064 if (bitmap_bit_p (regs
, regno
))
2070 /* Av set functions. */
2072 /* Add a new element to av set SETP.
2073 Return the element added. */
2075 av_set_add_element (av_set_t
*setp
)
2077 /* Insert at the beginning of the list. */
2082 /* Add EXPR to SETP. */
2084 av_set_add (av_set_t
*setp
, expr_t expr
)
2088 gcc_assert (!INSN_NOP_P (EXPR_INSN_RTX (expr
)));
2089 elem
= av_set_add_element (setp
);
2090 copy_expr (_AV_SET_EXPR (elem
), expr
);
2093 /* Same, but do not copy EXPR. */
2095 av_set_add_nocopy (av_set_t
*setp
, expr_t expr
)
2099 elem
= av_set_add_element (setp
);
2100 *_AV_SET_EXPR (elem
) = *expr
;
2103 /* Remove expr pointed to by IP from the av_set. */
2105 av_set_iter_remove (av_set_iterator
*ip
)
2107 clear_expr (_AV_SET_EXPR (*ip
->lp
));
2108 _list_iter_remove (ip
);
2111 /* Search for an expr in SET, such that it's equivalent to SOUGHT_VINSN in the
2112 sense of vinsn_equal_p function. Return NULL if no such expr is
2113 in SET was found. */
2115 av_set_lookup (av_set_t set
, vinsn_t sought_vinsn
)
2120 FOR_EACH_EXPR (expr
, i
, set
)
2121 if (vinsn_equal_p (EXPR_VINSN (expr
), sought_vinsn
))
2126 /* Same, but also remove the EXPR found. */
2128 av_set_lookup_and_remove (av_set_t
*setp
, vinsn_t sought_vinsn
)
2133 FOR_EACH_EXPR_1 (expr
, i
, setp
)
2134 if (vinsn_equal_p (EXPR_VINSN (expr
), sought_vinsn
))
2136 _list_iter_remove_nofree (&i
);
2142 /* Search for an expr in SET, such that it's equivalent to EXPR in the
2143 sense of vinsn_equal_p function of their vinsns, but not EXPR itself.
2144 Returns NULL if no such expr is in SET was found. */
2146 av_set_lookup_other_equiv_expr (av_set_t set
, expr_t expr
)
2151 FOR_EACH_EXPR (cur_expr
, i
, set
)
2153 if (cur_expr
== expr
)
2155 if (vinsn_equal_p (EXPR_VINSN (cur_expr
), EXPR_VINSN (expr
)))
2162 /* If other expression is already in AVP, remove one of them. */
2164 merge_with_other_exprs (av_set_t
*avp
, av_set_iterator
*ip
, expr_t expr
)
2168 expr2
= av_set_lookup_other_equiv_expr (*avp
, expr
);
2171 /* Reset target availability on merge, since taking it only from one
2172 of the exprs would be controversial for different code. */
2173 EXPR_TARGET_AVAILABLE (expr2
) = -1;
2174 EXPR_USEFULNESS (expr2
) = 0;
2176 merge_expr (expr2
, expr
, NULL
);
2178 /* Fix usefulness as it should be now REG_BR_PROB_BASE. */
2179 EXPR_USEFULNESS (expr2
) = REG_BR_PROB_BASE
;
2181 av_set_iter_remove (ip
);
2188 /* Return true if there is an expr that correlates to VI in SET. */
2190 av_set_is_in_p (av_set_t set
, vinsn_t vi
)
2192 return av_set_lookup (set
, vi
) != NULL
;
2195 /* Return a copy of SET. */
2197 av_set_copy (av_set_t set
)
2201 av_set_t res
= NULL
;
2203 FOR_EACH_EXPR (expr
, i
, set
)
2204 av_set_add (&res
, expr
);
2209 /* Join two av sets that do not have common elements by attaching second set
2210 (pointed to by FROMP) to the end of first set (TO_TAILP must point to
2211 _AV_SET_NEXT of first set's last element). */
2213 join_distinct_sets (av_set_t
*to_tailp
, av_set_t
*fromp
)
2215 gcc_assert (*to_tailp
== NULL
);
2220 /* Makes set pointed to by TO to be the union of TO and FROM. Clear av_set
2221 pointed to by FROMP afterwards. */
2223 av_set_union_and_clear (av_set_t
*top
, av_set_t
*fromp
, insn_t insn
)
2228 /* Delete from TOP all exprs, that present in FROMP. */
2229 FOR_EACH_EXPR_1 (expr1
, i
, top
)
2231 expr_t expr2
= av_set_lookup (*fromp
, EXPR_VINSN (expr1
));
2235 merge_expr (expr2
, expr1
, insn
);
2236 av_set_iter_remove (&i
);
2240 join_distinct_sets (i
.lp
, fromp
);
2243 /* Same as above, but also update availability of target register in
2244 TOP judging by TO_LV_SET and FROM_LV_SET. */
2246 av_set_union_and_live (av_set_t
*top
, av_set_t
*fromp
, regset to_lv_set
,
2247 regset from_lv_set
, insn_t insn
)
2251 av_set_t
*to_tailp
, in_both_set
= NULL
;
2253 /* Delete from TOP all expres, that present in FROMP. */
2254 FOR_EACH_EXPR_1 (expr1
, i
, top
)
2256 expr_t expr2
= av_set_lookup_and_remove (fromp
, EXPR_VINSN (expr1
));
2260 /* It may be that the expressions have different destination
2261 registers, in which case we need to check liveness here. */
2262 if (EXPR_SEPARABLE_P (expr1
))
2264 int regno1
= (REG_P (EXPR_LHS (expr1
))
2265 ? (int) expr_dest_regno (expr1
) : -1);
2266 int regno2
= (REG_P (EXPR_LHS (expr2
))
2267 ? (int) expr_dest_regno (expr2
) : -1);
2269 /* ??? We don't have a way to check restrictions for
2270 *other* register on the current path, we did it only
2271 for the current target register. Give up. */
2272 if (regno1
!= regno2
)
2273 EXPR_TARGET_AVAILABLE (expr2
) = -1;
2275 else if (EXPR_INSN_RTX (expr1
) != EXPR_INSN_RTX (expr2
))
2276 EXPR_TARGET_AVAILABLE (expr2
) = -1;
2278 merge_expr (expr2
, expr1
, insn
);
2279 av_set_add_nocopy (&in_both_set
, expr2
);
2280 av_set_iter_remove (&i
);
2283 /* EXPR1 is present in TOP, but not in FROMP. Check it on
2285 set_unavailable_target_for_expr (expr1
, from_lv_set
);
2289 /* These expressions are not present in TOP. Check liveness
2290 restrictions on TO_LV_SET. */
2291 FOR_EACH_EXPR (expr1
, i
, *fromp
)
2292 set_unavailable_target_for_expr (expr1
, to_lv_set
);
2294 join_distinct_sets (i
.lp
, &in_both_set
);
2295 join_distinct_sets (to_tailp
, fromp
);
2298 /* Clear av_set pointed to by SETP. */
2300 av_set_clear (av_set_t
*setp
)
2305 FOR_EACH_EXPR_1 (expr
, i
, setp
)
2306 av_set_iter_remove (&i
);
2308 gcc_assert (*setp
== NULL
);
2311 /* Leave only one non-speculative element in the SETP. */
2313 av_set_leave_one_nonspec (av_set_t
*setp
)
2317 bool has_one_nonspec
= false;
2319 /* Keep all speculative exprs, and leave one non-speculative
2321 FOR_EACH_EXPR_1 (expr
, i
, setp
)
2323 if (!EXPR_SPEC_DONE_DS (expr
))
2325 if (has_one_nonspec
)
2326 av_set_iter_remove (&i
);
2328 has_one_nonspec
= true;
2333 /* Return the N'th element of the SET. */
2335 av_set_element (av_set_t set
, int n
)
2340 FOR_EACH_EXPR (expr
, i
, set
)
2348 /* Deletes all expressions from AVP that are conditional branches (IFs). */
2350 av_set_substract_cond_branches (av_set_t
*avp
)
2355 FOR_EACH_EXPR_1 (expr
, i
, avp
)
2356 if (vinsn_cond_branch_p (EXPR_VINSN (expr
)))
2357 av_set_iter_remove (&i
);
2360 /* Multiplies usefulness attribute of each member of av-set *AVP by
2361 value PROB / ALL_PROB. */
2363 av_set_split_usefulness (av_set_t av
, int prob
, int all_prob
)
2368 FOR_EACH_EXPR (expr
, i
, av
)
2369 EXPR_USEFULNESS (expr
) = (all_prob
2370 ? (EXPR_USEFULNESS (expr
) * prob
) / all_prob
2374 /* Leave in AVP only those expressions, which are present in AV,
2375 and return it, merging history expressions. */
2377 av_set_code_motion_filter (av_set_t
*avp
, av_set_t av
)
2382 FOR_EACH_EXPR_1 (expr
, i
, avp
)
2383 if ((expr2
= av_set_lookup (av
, EXPR_VINSN (expr
))) == NULL
)
2384 av_set_iter_remove (&i
);
2386 /* When updating av sets in bookkeeping blocks, we can add more insns
2387 there which will be transformed but the upper av sets will not
2388 reflect those transformations. We then fail to undo those
2389 when searching for such insns. So merge the history saved
2390 in the av set of the block we are processing. */
2391 merge_history_vect (&EXPR_HISTORY_OF_CHANGES (expr
),
2392 EXPR_HISTORY_OF_CHANGES (expr2
));
2397 /* Dependence hooks to initialize insn data. */
2399 /* This is used in hooks callable from dependence analysis when initializing
2400 instruction's data. */
2403 /* Where the dependence was found (lhs/rhs). */
2406 /* The actual data object to initialize. */
2409 /* True when the insn should not be made clonable. */
2410 bool force_unique_p
;
2412 /* True when insn should be treated as of type USE, i.e. never renamed. */
2414 } deps_init_id_data
;
2417 /* Setup ID for INSN. FORCE_UNIQUE_P is true when INSN should not be
2420 setup_id_for_insn (idata_t id
, insn_t insn
, bool force_unique_p
)
2424 /* Determine whether INSN could be cloned and return appropriate vinsn type.
2425 That clonable insns which can be separated into lhs and rhs have type SET.
2426 Other clonable insns have type USE. */
2427 type
= GET_CODE (insn
);
2429 /* Only regular insns could be cloned. */
2430 if (type
== INSN
&& !force_unique_p
)
2432 else if (type
== JUMP_INSN
&& simplejump_p (insn
))
2434 else if (type
== DEBUG_INSN
)
2435 type
= !force_unique_p
? USE
: INSN
;
2437 IDATA_TYPE (id
) = type
;
2438 IDATA_REG_SETS (id
) = get_clear_regset_from_pool ();
2439 IDATA_REG_USES (id
) = get_clear_regset_from_pool ();
2440 IDATA_REG_CLOBBERS (id
) = get_clear_regset_from_pool ();
2443 /* Start initializing insn data. */
2445 deps_init_id_start_insn (insn_t insn
)
2447 gcc_assert (deps_init_id_data
.where
== DEPS_IN_NOWHERE
);
2449 setup_id_for_insn (deps_init_id_data
.id
, insn
,
2450 deps_init_id_data
.force_unique_p
);
2451 deps_init_id_data
.where
= DEPS_IN_INSN
;
2454 /* Start initializing lhs data. */
2456 deps_init_id_start_lhs (rtx lhs
)
2458 gcc_assert (deps_init_id_data
.where
== DEPS_IN_INSN
);
2459 gcc_assert (IDATA_LHS (deps_init_id_data
.id
) == NULL
);
2461 if (IDATA_TYPE (deps_init_id_data
.id
) == SET
)
2463 IDATA_LHS (deps_init_id_data
.id
) = lhs
;
2464 deps_init_id_data
.where
= DEPS_IN_LHS
;
2468 /* Finish initializing lhs data. */
2470 deps_init_id_finish_lhs (void)
2472 deps_init_id_data
.where
= DEPS_IN_INSN
;
2475 /* Note a set of REGNO. */
2477 deps_init_id_note_reg_set (int regno
)
2479 haifa_note_reg_set (regno
);
2481 if (deps_init_id_data
.where
== DEPS_IN_RHS
)
2482 deps_init_id_data
.force_use_p
= true;
2484 if (IDATA_TYPE (deps_init_id_data
.id
) != PC
)
2485 SET_REGNO_REG_SET (IDATA_REG_SETS (deps_init_id_data
.id
), regno
);
2488 /* Make instructions that set stack registers to be ineligible for
2489 renaming to avoid issues with find_used_regs. */
2490 if (IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
))
2491 deps_init_id_data
.force_use_p
= true;
2495 /* Note a clobber of REGNO. */
2497 deps_init_id_note_reg_clobber (int regno
)
2499 haifa_note_reg_clobber (regno
);
2501 if (deps_init_id_data
.where
== DEPS_IN_RHS
)
2502 deps_init_id_data
.force_use_p
= true;
2504 if (IDATA_TYPE (deps_init_id_data
.id
) != PC
)
2505 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (deps_init_id_data
.id
), regno
);
2508 /* Note a use of REGNO. */
2510 deps_init_id_note_reg_use (int regno
)
2512 haifa_note_reg_use (regno
);
2514 if (IDATA_TYPE (deps_init_id_data
.id
) != PC
)
2515 SET_REGNO_REG_SET (IDATA_REG_USES (deps_init_id_data
.id
), regno
);
2518 /* Start initializing rhs data. */
2520 deps_init_id_start_rhs (rtx rhs
)
2522 gcc_assert (deps_init_id_data
.where
== DEPS_IN_INSN
);
2524 /* And there was no sel_deps_reset_to_insn (). */
2525 if (IDATA_LHS (deps_init_id_data
.id
) != NULL
)
2527 IDATA_RHS (deps_init_id_data
.id
) = rhs
;
2528 deps_init_id_data
.where
= DEPS_IN_RHS
;
2532 /* Finish initializing rhs data. */
2534 deps_init_id_finish_rhs (void)
2536 gcc_assert (deps_init_id_data
.where
== DEPS_IN_RHS
2537 || deps_init_id_data
.where
== DEPS_IN_INSN
);
2538 deps_init_id_data
.where
= DEPS_IN_INSN
;
2541 /* Finish initializing insn data. */
2543 deps_init_id_finish_insn (void)
2545 gcc_assert (deps_init_id_data
.where
== DEPS_IN_INSN
);
2547 if (IDATA_TYPE (deps_init_id_data
.id
) == SET
)
2549 rtx lhs
= IDATA_LHS (deps_init_id_data
.id
);
2550 rtx rhs
= IDATA_RHS (deps_init_id_data
.id
);
2552 if (lhs
== NULL
|| rhs
== NULL
|| !lhs_and_rhs_separable_p (lhs
, rhs
)
2553 || deps_init_id_data
.force_use_p
)
2555 /* This should be a USE, as we don't want to schedule its RHS
2556 separately. However, we still want to have them recorded
2557 for the purposes of substitution. That's why we don't
2558 simply call downgrade_to_use () here. */
2559 gcc_assert (IDATA_TYPE (deps_init_id_data
.id
) == SET
);
2560 gcc_assert (!lhs
== !rhs
);
2562 IDATA_TYPE (deps_init_id_data
.id
) = USE
;
2566 deps_init_id_data
.where
= DEPS_IN_NOWHERE
;
2569 /* This is dependence info used for initializing insn's data. */
2570 static struct sched_deps_info_def deps_init_id_sched_deps_info
;
2572 /* This initializes most of the static part of the above structure. */
2573 static const struct sched_deps_info_def const_deps_init_id_sched_deps_info
=
2577 deps_init_id_start_insn
,
2578 deps_init_id_finish_insn
,
2579 deps_init_id_start_lhs
,
2580 deps_init_id_finish_lhs
,
2581 deps_init_id_start_rhs
,
2582 deps_init_id_finish_rhs
,
2583 deps_init_id_note_reg_set
,
2584 deps_init_id_note_reg_clobber
,
2585 deps_init_id_note_reg_use
,
2586 NULL
, /* note_mem_dep */
2587 NULL
, /* note_dep */
2590 0, /* use_deps_list */
2591 0 /* generate_spec_deps */
2594 /* Initialize INSN's lhs and rhs in ID. When FORCE_UNIQUE_P is true,
2595 we don't actually need information about lhs and rhs. */
2597 setup_id_lhs_rhs (idata_t id
, insn_t insn
, bool force_unique_p
)
2599 rtx pat
= PATTERN (insn
);
2601 if (NONJUMP_INSN_P (insn
)
2602 && GET_CODE (pat
) == SET
2605 IDATA_RHS (id
) = SET_SRC (pat
);
2606 IDATA_LHS (id
) = SET_DEST (pat
);
2609 IDATA_LHS (id
) = IDATA_RHS (id
) = NULL
;
2612 /* Possibly downgrade INSN to USE. */
2614 maybe_downgrade_id_to_use (idata_t id
, insn_t insn
)
2616 bool must_be_use
= false;
2618 rtx lhs
= IDATA_LHS (id
);
2619 rtx rhs
= IDATA_RHS (id
);
2621 /* We downgrade only SETs. */
2622 if (IDATA_TYPE (id
) != SET
)
2625 if (!lhs
|| !lhs_and_rhs_separable_p (lhs
, rhs
))
2627 IDATA_TYPE (id
) = USE
;
2631 FOR_EACH_INSN_DEF (def
, insn
)
2633 if (DF_REF_INSN (def
)
2634 && DF_REF_FLAGS_IS_SET (def
, DF_REF_PRE_POST_MODIFY
)
2635 && loc_mentioned_in_p (DF_REF_LOC (def
), IDATA_RHS (id
)))
2642 /* Make instructions that set stack registers to be ineligible for
2643 renaming to avoid issues with find_used_regs. */
2644 if (IN_RANGE (DF_REF_REGNO (def
), FIRST_STACK_REG
, LAST_STACK_REG
))
2653 IDATA_TYPE (id
) = USE
;
2656 /* Setup implicit register clobbers calculated by sched-deps for INSN
2657 before reload and save them in ID. */
2659 setup_id_implicit_regs (idata_t id
, insn_t insn
)
2661 if (reload_completed
)
2666 hard_reg_set_iterator hrsi
;
2668 get_implicit_reg_pending_clobbers (&temp
, insn
);
2669 EXECUTE_IF_SET_IN_HARD_REG_SET (temp
, 0, regno
, hrsi
)
2670 SET_REGNO_REG_SET (IDATA_REG_SETS (id
), regno
);
2673 /* Setup register sets describing INSN in ID. */
2675 setup_id_reg_sets (idata_t id
, insn_t insn
)
2677 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
2679 regset tmp
= get_clear_regset_from_pool ();
2681 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
2683 unsigned int regno
= DF_REF_REGNO (def
);
2685 /* Post modifies are treated like clobbers by sched-deps.c. */
2686 if (DF_REF_FLAGS_IS_SET (def
, (DF_REF_MUST_CLOBBER
2687 | DF_REF_PRE_POST_MODIFY
)))
2688 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (id
), regno
);
2689 else if (! DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
2691 SET_REGNO_REG_SET (IDATA_REG_SETS (id
), regno
);
2694 /* For stack registers, treat writes to them as writes
2695 to the first one to be consistent with sched-deps.c. */
2696 if (IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
))
2697 SET_REGNO_REG_SET (IDATA_REG_SETS (id
), FIRST_STACK_REG
);
2700 /* Mark special refs that generate read/write def pair. */
2701 if (DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
)
2702 || regno
== STACK_POINTER_REGNUM
)
2703 bitmap_set_bit (tmp
, regno
);
2706 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
2708 unsigned int regno
= DF_REF_REGNO (use
);
2710 /* When these refs are met for the first time, skip them, as
2711 these uses are just counterparts of some defs. */
2712 if (bitmap_bit_p (tmp
, regno
))
2713 bitmap_clear_bit (tmp
, regno
);
2714 else if (! DF_REF_FLAGS_IS_SET (use
, DF_REF_CALL_STACK_USAGE
))
2716 SET_REGNO_REG_SET (IDATA_REG_USES (id
), regno
);
2719 /* For stack registers, treat reads from them as reads from
2720 the first one to be consistent with sched-deps.c. */
2721 if (IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
))
2722 SET_REGNO_REG_SET (IDATA_REG_USES (id
), FIRST_STACK_REG
);
2727 /* Also get implicit reg clobbers from sched-deps. */
2728 setup_id_implicit_regs (id
, insn
);
2730 return_regset_to_pool (tmp
);
2733 /* Initialize instruction data for INSN in ID using DF's data. */
2735 init_id_from_df (idata_t id
, insn_t insn
, bool force_unique_p
)
2737 gcc_assert (DF_INSN_UID_SAFE_GET (INSN_UID (insn
)) != NULL
);
2739 setup_id_for_insn (id
, insn
, force_unique_p
);
2740 setup_id_lhs_rhs (id
, insn
, force_unique_p
);
2742 if (INSN_NOP_P (insn
))
2745 maybe_downgrade_id_to_use (id
, insn
);
2746 setup_id_reg_sets (id
, insn
);
2749 /* Initialize instruction data for INSN in ID. */
2751 deps_init_id (idata_t id
, insn_t insn
, bool force_unique_p
)
2753 struct deps_desc _dc
, *dc
= &_dc
;
2755 deps_init_id_data
.where
= DEPS_IN_NOWHERE
;
2756 deps_init_id_data
.id
= id
;
2757 deps_init_id_data
.force_unique_p
= force_unique_p
;
2758 deps_init_id_data
.force_use_p
= false;
2760 init_deps (dc
, false);
2761 memcpy (&deps_init_id_sched_deps_info
,
2762 &const_deps_init_id_sched_deps_info
,
2763 sizeof (deps_init_id_sched_deps_info
));
2764 if (spec_info
!= NULL
)
2765 deps_init_id_sched_deps_info
.generate_spec_deps
= 1;
2766 sched_deps_info
= &deps_init_id_sched_deps_info
;
2768 deps_analyze_insn (dc
, insn
);
2769 /* Implicit reg clobbers received from sched-deps separately. */
2770 setup_id_implicit_regs (id
, insn
);
2773 deps_init_id_data
.id
= NULL
;
2777 struct sched_scan_info_def
2779 /* This hook notifies scheduler frontend to extend its internal per basic
2780 block data structures. This hook should be called once before a series of
2781 calls to bb_init (). */
2782 void (*extend_bb
) (void);
2784 /* This hook makes scheduler frontend to initialize its internal data
2785 structures for the passed basic block. */
2786 void (*init_bb
) (basic_block
);
2788 /* This hook notifies scheduler frontend to extend its internal per insn data
2789 structures. This hook should be called once before a series of calls to
2791 void (*extend_insn
) (void);
2793 /* This hook makes scheduler frontend to initialize its internal data
2794 structures for the passed insn. */
2795 void (*init_insn
) (insn_t
);
2798 /* A driver function to add a set of basic blocks (BBS) to the
2799 scheduling region. */
2801 sched_scan (const struct sched_scan_info_def
*ssi
, bb_vec_t bbs
)
2810 FOR_EACH_VEC_ELT (bbs
, i
, bb
)
2813 if (ssi
->extend_insn
)
2814 ssi
->extend_insn ();
2817 FOR_EACH_VEC_ELT (bbs
, i
, bb
)
2821 FOR_BB_INSNS (bb
, insn
)
2822 ssi
->init_insn (insn
);
2826 /* Implement hooks for collecting fundamental insn properties like if insn is
2827 an ASM or is within a SCHED_GROUP. */
2829 /* True when a "one-time init" data for INSN was already inited. */
2831 first_time_insn_init (insn_t insn
)
2833 return INSN_LIVE (insn
) == NULL
;
2836 /* Hash an entry in a transformed_insns hashtable. */
2838 hash_transformed_insns (const void *p
)
2840 return VINSN_HASH_RTX (((const struct transformed_insns
*) p
)->vinsn_old
);
2843 /* Compare the entries in a transformed_insns hashtable. */
2845 eq_transformed_insns (const void *p
, const void *q
)
2848 VINSN_INSN_RTX (((const struct transformed_insns
*) p
)->vinsn_old
);
2850 VINSN_INSN_RTX (((const struct transformed_insns
*) q
)->vinsn_old
);
2852 if (INSN_UID (i1
) == INSN_UID (i2
))
2854 return rtx_equal_p (PATTERN (i1
), PATTERN (i2
));
2857 /* Free an entry in a transformed_insns hashtable. */
2859 free_transformed_insns (void *p
)
2861 struct transformed_insns
*pti
= (struct transformed_insns
*) p
;
2863 vinsn_detach (pti
->vinsn_old
);
2864 vinsn_detach (pti
->vinsn_new
);
2868 /* Init the s_i_d data for INSN which should be inited just once, when
2869 we first see the insn. */
2871 init_first_time_insn_data (insn_t insn
)
2873 /* This should not be set if this is the first time we init data for
2875 gcc_assert (first_time_insn_init (insn
));
2877 /* These are needed for nops too. */
2878 INSN_LIVE (insn
) = get_regset_from_pool ();
2879 INSN_LIVE_VALID_P (insn
) = false;
2881 if (!INSN_NOP_P (insn
))
2883 INSN_ANALYZED_DEPS (insn
) = BITMAP_ALLOC (NULL
);
2884 INSN_FOUND_DEPS (insn
) = BITMAP_ALLOC (NULL
);
2885 INSN_TRANSFORMED_INSNS (insn
)
2886 = htab_create (16, hash_transformed_insns
,
2887 eq_transformed_insns
, free_transformed_insns
);
2888 init_deps (&INSN_DEPS_CONTEXT (insn
), true);
2892 /* Free almost all above data for INSN that is scheduled already.
2893 Used for extra-large basic blocks. */
2895 free_data_for_scheduled_insn (insn_t insn
)
2897 gcc_assert (! first_time_insn_init (insn
));
2899 if (! INSN_ANALYZED_DEPS (insn
))
2902 BITMAP_FREE (INSN_ANALYZED_DEPS (insn
));
2903 BITMAP_FREE (INSN_FOUND_DEPS (insn
));
2904 htab_delete (INSN_TRANSFORMED_INSNS (insn
));
2906 /* This is allocated only for bookkeeping insns. */
2907 if (INSN_ORIGINATORS (insn
))
2908 BITMAP_FREE (INSN_ORIGINATORS (insn
));
2909 free_deps (&INSN_DEPS_CONTEXT (insn
));
2911 INSN_ANALYZED_DEPS (insn
) = NULL
;
2913 /* Clear the readonly flag so we would ICE when trying to recalculate
2914 the deps context (as we believe that it should not happen). */
2915 (&INSN_DEPS_CONTEXT (insn
))->readonly
= 0;
2918 /* Free the same data as above for INSN. */
2920 free_first_time_insn_data (insn_t insn
)
2922 gcc_assert (! first_time_insn_init (insn
));
2924 free_data_for_scheduled_insn (insn
);
2925 return_regset_to_pool (INSN_LIVE (insn
));
2926 INSN_LIVE (insn
) = NULL
;
2927 INSN_LIVE_VALID_P (insn
) = false;
2930 /* Initialize region-scope data structures for basic blocks. */
2932 init_global_and_expr_for_bb (basic_block bb
)
2934 if (sel_bb_empty_p (bb
))
2937 invalidate_av_set (bb
);
2940 /* Data for global dependency analysis (to initialize CANT_MOVE and
2944 /* Previous insn. */
2948 /* Determine if INSN is in the sched_group, is an asm or should not be
2949 cloned. After that initialize its expr. */
2951 init_global_and_expr_for_insn (insn_t insn
)
2956 if (NOTE_INSN_BASIC_BLOCK_P (insn
))
2958 init_global_data
.prev_insn
= NULL
;
2962 gcc_assert (INSN_P (insn
));
2964 if (SCHED_GROUP_P (insn
))
2965 /* Setup a sched_group. */
2967 insn_t prev_insn
= init_global_data
.prev_insn
;
2970 INSN_SCHED_NEXT (prev_insn
) = insn
;
2972 init_global_data
.prev_insn
= insn
;
2975 init_global_data
.prev_insn
= NULL
;
2977 if (GET_CODE (PATTERN (insn
)) == ASM_INPUT
2978 || asm_noperands (PATTERN (insn
)) >= 0)
2979 /* Mark INSN as an asm. */
2980 INSN_ASM_P (insn
) = true;
2983 bool force_unique_p
;
2986 /* Certain instructions cannot be cloned, and frame related insns and
2987 the insn adjacent to NOTE_INSN_EPILOGUE_BEG cannot be moved out of
2989 if (prologue_epilogue_contains (insn
))
2991 if (RTX_FRAME_RELATED_P (insn
))
2992 CANT_MOVE (insn
) = 1;
2996 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
2997 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
2998 && ((enum insn_note
) INTVAL (XEXP (note
, 0))
2999 == NOTE_INSN_EPILOGUE_BEG
))
3001 CANT_MOVE (insn
) = 1;
3005 force_unique_p
= true;
3008 if (CANT_MOVE (insn
)
3009 || INSN_ASM_P (insn
)
3010 || SCHED_GROUP_P (insn
)
3012 /* Exception handling insns are always unique. */
3013 || (cfun
->can_throw_non_call_exceptions
&& can_throw_internal (insn
))
3014 /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
3015 || control_flow_insn_p (insn
)
3016 || volatile_insn_p (PATTERN (insn
))
3017 || (targetm
.cannot_copy_insn_p
3018 && targetm
.cannot_copy_insn_p (insn
)))
3019 force_unique_p
= true;
3021 force_unique_p
= false;
3023 if (targetm
.sched
.get_insn_spec_ds
)
3025 spec_done_ds
= targetm
.sched
.get_insn_spec_ds (insn
);
3026 spec_done_ds
= ds_get_max_dep_weak (spec_done_ds
);
3031 /* Initialize INSN's expr. */
3032 init_expr (INSN_EXPR (insn
), vinsn_create (insn
, force_unique_p
), 0,
3033 REG_BR_PROB_BASE
, INSN_PRIORITY (insn
), 0, BLOCK_NUM (insn
),
3034 spec_done_ds
, 0, 0, vNULL
, true,
3035 false, false, false, CANT_MOVE (insn
));
3038 init_first_time_insn_data (insn
);
3041 /* Scan the region and initialize instruction data for basic blocks BBS. */
3043 sel_init_global_and_expr (bb_vec_t bbs
)
3045 /* ??? It would be nice to implement push / pop scheme for sched_infos. */
3046 const struct sched_scan_info_def ssi
=
3048 NULL
, /* extend_bb */
3049 init_global_and_expr_for_bb
, /* init_bb */
3050 extend_insn_data
, /* extend_insn */
3051 init_global_and_expr_for_insn
/* init_insn */
3054 sched_scan (&ssi
, bbs
);
3057 /* Finalize region-scope data structures for basic blocks. */
3059 finish_global_and_expr_for_bb (basic_block bb
)
3061 av_set_clear (&BB_AV_SET (bb
));
3062 BB_AV_LEVEL (bb
) = 0;
3065 /* Finalize INSN's data. */
3067 finish_global_and_expr_insn (insn_t insn
)
3069 if (LABEL_P (insn
) || NOTE_INSN_BASIC_BLOCK_P (insn
))
3072 gcc_assert (INSN_P (insn
));
3074 if (INSN_LUID (insn
) > 0)
3076 free_first_time_insn_data (insn
);
3077 INSN_WS_LEVEL (insn
) = 0;
3078 CANT_MOVE (insn
) = 0;
3080 /* We can no longer assert this, as vinsns of this insn could be
3081 easily live in other insn's caches. This should be changed to
3082 a counter-like approach among all vinsns. */
3083 gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn
)) == 1);
3084 clear_expr (INSN_EXPR (insn
));
3088 /* Finalize per instruction data for the whole region. */
3090 sel_finish_global_and_expr (void)
3096 bbs
.create (current_nr_blocks
);
3098 for (i
= 0; i
< current_nr_blocks
; i
++)
3099 bbs
.quick_push (BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (i
)));
3101 /* Clear AV_SETs and INSN_EXPRs. */
3103 const struct sched_scan_info_def ssi
=
3105 NULL
, /* extend_bb */
3106 finish_global_and_expr_for_bb
, /* init_bb */
3107 NULL
, /* extend_insn */
3108 finish_global_and_expr_insn
/* init_insn */
3111 sched_scan (&ssi
, bbs
);
3121 /* In the below hooks, we merely calculate whether or not a dependence
3122 exists, and in what part of insn. However, we will need more data
3123 when we'll start caching dependence requests. */
3125 /* Container to hold information for dependency analysis. */
3130 /* A variable to track which part of rtx we are scanning in
3131 sched-deps.c: sched_analyze_insn (). */
3134 /* Current producer. */
3137 /* Current consumer. */
3140 /* Is SEL_DEPS_HAS_DEP_P[DEPS_IN_X] is true, then X has a dependence.
3141 X is from { INSN, LHS, RHS }. */
3142 ds_t has_dep_p
[DEPS_IN_NOWHERE
];
3143 } has_dependence_data
;
3145 /* Start analyzing dependencies of INSN. */
3147 has_dependence_start_insn (insn_t insn ATTRIBUTE_UNUSED
)
3149 gcc_assert (has_dependence_data
.where
== DEPS_IN_NOWHERE
);
3151 has_dependence_data
.where
= DEPS_IN_INSN
;
3154 /* Finish analyzing dependencies of an insn. */
3156 has_dependence_finish_insn (void)
3158 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3160 has_dependence_data
.where
= DEPS_IN_NOWHERE
;
3163 /* Start analyzing dependencies of LHS. */
3165 has_dependence_start_lhs (rtx lhs ATTRIBUTE_UNUSED
)
3167 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3169 if (VINSN_LHS (has_dependence_data
.con
) != NULL
)
3170 has_dependence_data
.where
= DEPS_IN_LHS
;
3173 /* Finish analyzing dependencies of an lhs. */
3175 has_dependence_finish_lhs (void)
3177 has_dependence_data
.where
= DEPS_IN_INSN
;
3180 /* Start analyzing dependencies of RHS. */
3182 has_dependence_start_rhs (rtx rhs ATTRIBUTE_UNUSED
)
3184 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3186 if (VINSN_RHS (has_dependence_data
.con
) != NULL
)
3187 has_dependence_data
.where
= DEPS_IN_RHS
;
3190 /* Start analyzing dependencies of an rhs. */
3192 has_dependence_finish_rhs (void)
3194 gcc_assert (has_dependence_data
.where
== DEPS_IN_RHS
3195 || has_dependence_data
.where
== DEPS_IN_INSN
);
3197 has_dependence_data
.where
= DEPS_IN_INSN
;
3200 /* Note a set of REGNO. */
3202 has_dependence_note_reg_set (int regno
)
3204 struct deps_reg
*reg_last
= &has_dependence_data
.dc
->reg_last
[regno
];
3206 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3208 (has_dependence_data
.con
)))
3210 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3212 if (reg_last
->sets
!= NULL
3213 || reg_last
->clobbers
!= NULL
)
3214 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_OUTPUT
;
3216 if (reg_last
->uses
|| reg_last
->implicit_sets
)
3217 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_ANTI
;
3221 /* Note a clobber of REGNO. */
3223 has_dependence_note_reg_clobber (int regno
)
3225 struct deps_reg
*reg_last
= &has_dependence_data
.dc
->reg_last
[regno
];
3227 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3229 (has_dependence_data
.con
)))
3231 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3234 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_OUTPUT
;
3236 if (reg_last
->uses
|| reg_last
->implicit_sets
)
3237 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_ANTI
;
3241 /* Note a use of REGNO. */
3243 has_dependence_note_reg_use (int regno
)
3245 struct deps_reg
*reg_last
= &has_dependence_data
.dc
->reg_last
[regno
];
3247 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3249 (has_dependence_data
.con
)))
3251 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3254 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_TRUE
;
3256 if (reg_last
->clobbers
|| reg_last
->implicit_sets
)
3257 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_ANTI
;
3259 /* Merge BE_IN_SPEC bits into *DSP when the dependency producer
3260 is actually a check insn. We need to do this for any register
3261 read-read dependency with the check unless we track properly
3262 all registers written by BE_IN_SPEC-speculated insns, as
3263 we don't have explicit dependence lists. See PR 53975. */
3266 ds_t pro_spec_checked_ds
;
3268 pro_spec_checked_ds
= INSN_SPEC_CHECKED_DS (has_dependence_data
.pro
);
3269 pro_spec_checked_ds
= ds_get_max_dep_weak (pro_spec_checked_ds
);
3271 if (pro_spec_checked_ds
!= 0)
3272 *dsp
= ds_full_merge (*dsp
, pro_spec_checked_ds
,
3273 NULL_RTX
, NULL_RTX
);
3278 /* Note a memory dependence. */
3280 has_dependence_note_mem_dep (rtx mem ATTRIBUTE_UNUSED
,
3281 rtx pending_mem ATTRIBUTE_UNUSED
,
3282 insn_t pending_insn ATTRIBUTE_UNUSED
,
3283 ds_t ds ATTRIBUTE_UNUSED
)
3285 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3286 VINSN_INSN_RTX (has_dependence_data
.con
)))
3288 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3290 *dsp
= ds_full_merge (ds
, *dsp
, pending_mem
, mem
);
3294 /* Note a dependence. */
3296 has_dependence_note_dep (insn_t pro ATTRIBUTE_UNUSED
,
3297 ds_t ds ATTRIBUTE_UNUSED
)
3299 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3300 VINSN_INSN_RTX (has_dependence_data
.con
)))
3302 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3304 *dsp
= ds_full_merge (ds
, *dsp
, NULL_RTX
, NULL_RTX
);
3308 /* Mark the insn as having a hard dependence that prevents speculation. */
3310 sel_mark_hard_insn (rtx insn
)
3314 /* Only work when we're in has_dependence_p mode.
3315 ??? This is a hack, this should actually be a hook. */
3316 if (!has_dependence_data
.dc
|| !has_dependence_data
.pro
)
3319 gcc_assert (insn
== VINSN_INSN_RTX (has_dependence_data
.con
));
3320 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3322 for (i
= 0; i
< DEPS_IN_NOWHERE
; i
++)
3323 has_dependence_data
.has_dep_p
[i
] &= ~SPECULATIVE
;
3326 /* This structure holds the hooks for the dependency analysis used when
3327 actually processing dependencies in the scheduler. */
3328 static struct sched_deps_info_def has_dependence_sched_deps_info
;
3330 /* This initializes most of the fields of the above structure. */
3331 static const struct sched_deps_info_def const_has_dependence_sched_deps_info
=
3335 has_dependence_start_insn
,
3336 has_dependence_finish_insn
,
3337 has_dependence_start_lhs
,
3338 has_dependence_finish_lhs
,
3339 has_dependence_start_rhs
,
3340 has_dependence_finish_rhs
,
3341 has_dependence_note_reg_set
,
3342 has_dependence_note_reg_clobber
,
3343 has_dependence_note_reg_use
,
3344 has_dependence_note_mem_dep
,
3345 has_dependence_note_dep
,
3348 0, /* use_deps_list */
3349 0 /* generate_spec_deps */
3352 /* Initialize has_dependence_sched_deps_info with extra spec field. */
3354 setup_has_dependence_sched_deps_info (void)
3356 memcpy (&has_dependence_sched_deps_info
,
3357 &const_has_dependence_sched_deps_info
,
3358 sizeof (has_dependence_sched_deps_info
));
3360 if (spec_info
!= NULL
)
3361 has_dependence_sched_deps_info
.generate_spec_deps
= 1;
3363 sched_deps_info
= &has_dependence_sched_deps_info
;
3366 /* Remove all dependences found and recorded in has_dependence_data array. */
3368 sel_clear_has_dependence (void)
3372 for (i
= 0; i
< DEPS_IN_NOWHERE
; i
++)
3373 has_dependence_data
.has_dep_p
[i
] = 0;
3376 /* Return nonzero if EXPR has is dependent upon PRED. Return the pointer
3377 to the dependence information array in HAS_DEP_PP. */
3379 has_dependence_p (expr_t expr
, insn_t pred
, ds_t
**has_dep_pp
)
3383 struct deps_desc
*dc
;
3385 if (INSN_SIMPLEJUMP_P (pred
))
3386 /* Unconditional jump is just a transfer of control flow.
3390 dc
= &INSN_DEPS_CONTEXT (pred
);
3392 /* We init this field lazily. */
3393 if (dc
->reg_last
== NULL
)
3394 init_deps_reg_last (dc
);
3398 has_dependence_data
.pro
= NULL
;
3399 /* Initialize empty dep context with information about PRED. */
3400 advance_deps_context (dc
, pred
);
3404 has_dependence_data
.where
= DEPS_IN_NOWHERE
;
3405 has_dependence_data
.pro
= pred
;
3406 has_dependence_data
.con
= EXPR_VINSN (expr
);
3407 has_dependence_data
.dc
= dc
;
3409 sel_clear_has_dependence ();
3411 /* Now catch all dependencies that would be generated between PRED and
3413 setup_has_dependence_sched_deps_info ();
3414 deps_analyze_insn (dc
, EXPR_INSN_RTX (expr
));
3415 has_dependence_data
.dc
= NULL
;
3417 /* When a barrier was found, set DEPS_IN_INSN bits. */
3418 if (dc
->last_reg_pending_barrier
== TRUE_BARRIER
)
3419 has_dependence_data
.has_dep_p
[DEPS_IN_INSN
] = DEP_TRUE
;
3420 else if (dc
->last_reg_pending_barrier
== MOVE_BARRIER
)
3421 has_dependence_data
.has_dep_p
[DEPS_IN_INSN
] = DEP_ANTI
;
3423 /* Do not allow stores to memory to move through checks. Currently
3424 we don't move this to sched-deps.c as the check doesn't have
3425 obvious places to which this dependence can be attached.
3426 FIMXE: this should go to a hook. */
3428 && MEM_P (EXPR_LHS (expr
))
3429 && sel_insn_is_speculation_check (pred
))
3430 has_dependence_data
.has_dep_p
[DEPS_IN_INSN
] = DEP_ANTI
;
3432 *has_dep_pp
= has_dependence_data
.has_dep_p
;
3434 for (i
= 0; i
< DEPS_IN_NOWHERE
; i
++)
3435 ds
= ds_full_merge (ds
, has_dependence_data
.has_dep_p
[i
],
3436 NULL_RTX
, NULL_RTX
);
3442 /* Dependence hooks implementation that checks dependence latency constraints
3443 on the insns being scheduled. The entry point for these routines is
3444 tick_check_p predicate. */
3448 /* An expr we are currently checking. */
3451 /* A minimal cycle for its scheduling. */
3454 /* Whether we have seen a true dependence while checking. */
3455 bool seen_true_dep_p
;
3458 /* Update minimal scheduling cycle for tick_check_insn given that it depends
3459 on PRO with status DS and weight DW. */
3461 tick_check_dep_with_dw (insn_t pro_insn
, ds_t ds
, dw_t dw
)
3463 expr_t con_expr
= tick_check_data
.expr
;
3464 insn_t con_insn
= EXPR_INSN_RTX (con_expr
);
3466 if (con_insn
!= pro_insn
)
3471 if (/* PROducer was removed from above due to pipelining. */
3472 !INSN_IN_STREAM_P (pro_insn
)
3473 /* Or PROducer was originally on the next iteration regarding the
3475 || (INSN_SCHED_TIMES (pro_insn
)
3476 - EXPR_SCHED_TIMES (con_expr
)) > 1)
3477 /* Don't count this dependence. */
3481 if (dt
== REG_DEP_TRUE
)
3482 tick_check_data
.seen_true_dep_p
= true;
3484 gcc_assert (INSN_SCHED_CYCLE (pro_insn
) > 0);
3487 dep_def _dep
, *dep
= &_dep
;
3489 init_dep (dep
, pro_insn
, con_insn
, dt
);
3491 tick
= INSN_SCHED_CYCLE (pro_insn
) + dep_cost_1 (dep
, dw
);
3494 /* When there are several kinds of dependencies between pro and con,
3495 only REG_DEP_TRUE should be taken into account. */
3496 if (tick
> tick_check_data
.cycle
3497 && (dt
== REG_DEP_TRUE
|| !tick_check_data
.seen_true_dep_p
))
3498 tick_check_data
.cycle
= tick
;
3502 /* An implementation of note_dep hook. */
3504 tick_check_note_dep (insn_t pro
, ds_t ds
)
3506 tick_check_dep_with_dw (pro
, ds
, 0);
3509 /* An implementation of note_mem_dep hook. */
3511 tick_check_note_mem_dep (rtx mem1
, rtx mem2
, insn_t pro
, ds_t ds
)
3515 dw
= (ds_to_dt (ds
) == REG_DEP_TRUE
3516 ? estimate_dep_weak (mem1
, mem2
)
3519 tick_check_dep_with_dw (pro
, ds
, dw
);
3522 /* This structure contains hooks for dependence analysis used when determining
3523 whether an insn is ready for scheduling. */
3524 static struct sched_deps_info_def tick_check_sched_deps_info
=
3535 haifa_note_reg_clobber
,
3537 tick_check_note_mem_dep
,
3538 tick_check_note_dep
,
3543 /* Estimate number of cycles from the current cycle of FENCE until EXPR can be
3544 scheduled. Return 0 if all data from producers in DC is ready. */
3546 tick_check_p (expr_t expr
, deps_t dc
, fence_t fence
)
3549 /* Initialize variables. */
3550 tick_check_data
.expr
= expr
;
3551 tick_check_data
.cycle
= 0;
3552 tick_check_data
.seen_true_dep_p
= false;
3553 sched_deps_info
= &tick_check_sched_deps_info
;
3555 gcc_assert (!dc
->readonly
);
3557 deps_analyze_insn (dc
, EXPR_INSN_RTX (expr
));
3560 cycles_left
= tick_check_data
.cycle
- FENCE_CYCLE (fence
);
3562 return cycles_left
>= 0 ? cycles_left
: 0;
3566 /* Functions to work with insns. */
3568 /* Returns true if LHS of INSN is the same as DEST of an insn
3571 lhs_of_insn_equals_to_dest_p (insn_t insn
, rtx dest
)
3573 rtx lhs
= INSN_LHS (insn
);
3575 if (lhs
== NULL
|| dest
== NULL
)
3578 return rtx_equal_p (lhs
, dest
);
3581 /* Return s_i_d entry of INSN. Callable from debugger. */
3583 insn_sid (insn_t insn
)
3588 /* True when INSN is a speculative check. We can tell this by looking
3589 at the data structures of the selective scheduler, not by examining
3592 sel_insn_is_speculation_check (rtx insn
)
3594 return s_i_d
.exists () && !! INSN_SPEC_CHECKED_DS (insn
);
3597 /* Extracts machine mode MODE and destination location DST_LOC
3600 get_dest_and_mode (rtx insn
, rtx
*dst_loc
, machine_mode
*mode
)
3602 rtx pat
= PATTERN (insn
);
3604 gcc_assert (dst_loc
);
3605 gcc_assert (GET_CODE (pat
) == SET
);
3607 *dst_loc
= SET_DEST (pat
);
3609 gcc_assert (*dst_loc
);
3610 gcc_assert (MEM_P (*dst_loc
) || REG_P (*dst_loc
));
3613 *mode
= GET_MODE (*dst_loc
);
3616 /* Returns true when moving through JUMP will result in bookkeeping
3619 bookkeeping_can_be_created_if_moved_through_p (insn_t jump
)
3624 FOR_EACH_SUCC (succ
, si
, jump
)
3625 if (sel_num_cfg_preds_gt_1 (succ
))
3631 /* Return 'true' if INSN is the only one in its basic block. */
3633 insn_is_the_only_one_in_bb_p (insn_t insn
)
3635 return sel_bb_head_p (insn
) && sel_bb_end_p (insn
);
3638 /* Check that the region we're scheduling still has at most one
3641 verify_backedges (void)
3649 for (i
= 0; i
< current_nr_blocks
; i
++)
3650 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (i
))->succs
)
3651 if (in_current_region_p (e
->dest
)
3652 && BLOCK_TO_BB (e
->dest
->index
) < i
)
3655 gcc_assert (n
<= 1);
3660 /* Functions to work with control flow. */
3662 /* Recompute BLOCK_TO_BB and BB_FOR_BLOCK for current region so that blocks
3663 are sorted in topological order (it might have been invalidated by
3664 redirecting an edge). */
3666 sel_recompute_toporder (void)
3669 int *postorder
, n_blocks
;
3671 postorder
= XALLOCAVEC (int, n_basic_blocks_for_fn (cfun
));
3672 n_blocks
= post_order_compute (postorder
, false, false);
3674 rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
3675 for (n
= 0, i
= n_blocks
- 1; i
>= 0; i
--)
3676 if (CONTAINING_RGN (postorder
[i
]) == rgn
)
3678 BLOCK_TO_BB (postorder
[i
]) = n
;
3679 BB_TO_BLOCK (n
) = postorder
[i
];
3683 /* Assert that we updated info for all blocks. We may miss some blocks if
3684 this function is called when redirecting an edge made a block
3685 unreachable, but that block is not deleted yet. */
3686 gcc_assert (n
== RGN_NR_BLOCKS (rgn
));
3689 /* Tidy the possibly empty block BB. */
3691 maybe_tidy_empty_bb (basic_block bb
)
3693 basic_block succ_bb
, pred_bb
, note_bb
;
3694 vec
<basic_block
> dom_bbs
;
3699 /* Keep empty bb only if this block immediately precedes EXIT and
3700 has incoming non-fallthrough edge, or it has no predecessors or
3701 successors. Otherwise remove it. */
3702 if (!sel_bb_empty_p (bb
)
3703 || (single_succ_p (bb
)
3704 && single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3705 && (!single_pred_p (bb
)
3706 || !(single_pred_edge (bb
)->flags
& EDGE_FALLTHRU
)))
3707 || EDGE_COUNT (bb
->preds
) == 0
3708 || EDGE_COUNT (bb
->succs
) == 0)
3711 /* Do not attempt to redirect complex edges. */
3712 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3713 if (e
->flags
& EDGE_COMPLEX
)
3715 else if (e
->flags
& EDGE_FALLTHRU
)
3718 /* If prev bb ends with asm goto, see if any of the
3719 ASM_OPERANDS_LABELs don't point to the fallthru
3720 label. Do not attempt to redirect it in that case. */
3721 if (JUMP_P (BB_END (e
->src
))
3722 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
3724 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
3726 for (i
= 0; i
< n
; ++i
)
3727 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (bb
))
3732 free_data_sets (bb
);
3734 /* Do not delete BB if it has more than one successor.
3735 That can occur when we moving a jump. */
3736 if (!single_succ_p (bb
))
3738 gcc_assert (can_merge_blocks_p (bb
->prev_bb
, bb
));
3739 sel_merge_blocks (bb
->prev_bb
, bb
);
3743 succ_bb
= single_succ (bb
);
3748 /* Save a pred/succ from the current region to attach the notes to. */
3750 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3751 if (in_current_region_p (e
->src
))
3756 if (note_bb
== NULL
)
3759 /* Redirect all non-fallthru edges to the next bb. */
3764 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3768 if (!(e
->flags
& EDGE_FALLTHRU
))
3770 /* We can not invalidate computed topological order by moving
3771 the edge destination block (E->SUCC) along a fallthru edge.
3773 We will update dominators here only when we'll get
3774 an unreachable block when redirecting, otherwise
3775 sel_redirect_edge_and_branch will take care of it. */
3777 && single_pred_p (e
->dest
))
3778 dom_bbs
.safe_push (e
->dest
);
3779 sel_redirect_edge_and_branch (e
, succ_bb
);
3783 /* If the edge is fallthru, but PRED_BB ends in a conditional jump
3784 to BB (so there is no non-fallthru edge from PRED_BB to BB), we
3785 still have to adjust it. */
3786 else if (single_succ_p (pred_bb
) && any_condjump_p (BB_END (pred_bb
)))
3788 /* If possible, try to remove the unneeded conditional jump. */
3789 if (INSN_SCHED_TIMES (BB_END (pred_bb
)) == 0
3790 && !IN_CURRENT_FENCE_P (BB_END (pred_bb
)))
3792 if (!sel_remove_insn (BB_END (pred_bb
), false, false))
3793 tidy_fallthru_edge (e
);
3796 sel_redirect_edge_and_branch (e
, succ_bb
);
3803 if (can_merge_blocks_p (bb
->prev_bb
, bb
))
3804 sel_merge_blocks (bb
->prev_bb
, bb
);
3807 /* This is a block without fallthru predecessor. Just delete it. */
3808 gcc_assert (note_bb
);
3809 move_bb_info (note_bb
, bb
);
3810 remove_empty_bb (bb
, true);
3813 if (!dom_bbs
.is_empty ())
3815 dom_bbs
.safe_push (succ_bb
);
3816 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, false);
3823 /* Tidy the control flow after we have removed original insn from
3824 XBB. Return true if we have removed some blocks. When FULL_TIDYING
3825 is true, also try to optimize control flow on non-empty blocks. */
3827 tidy_control_flow (basic_block xbb
, bool full_tidying
)
3829 bool changed
= true;
3832 /* First check whether XBB is empty. */
3833 changed
= maybe_tidy_empty_bb (xbb
);
3834 if (changed
|| !full_tidying
)
3837 /* Check if there is a unnecessary jump after insn left. */
3838 if (bb_has_removable_jump_to_p (xbb
, xbb
->next_bb
)
3839 && INSN_SCHED_TIMES (BB_END (xbb
)) == 0
3840 && !IN_CURRENT_FENCE_P (BB_END (xbb
)))
3842 if (sel_remove_insn (BB_END (xbb
), false, false))
3844 tidy_fallthru_edge (EDGE_SUCC (xbb
, 0));
3847 first
= sel_bb_head (xbb
);
3848 last
= sel_bb_end (xbb
);
3849 if (MAY_HAVE_DEBUG_INSNS
)
3851 if (first
!= last
&& DEBUG_INSN_P (first
))
3853 first
= NEXT_INSN (first
);
3854 while (first
!= last
&& (DEBUG_INSN_P (first
) || NOTE_P (first
)));
3856 if (first
!= last
&& DEBUG_INSN_P (last
))
3858 last
= PREV_INSN (last
);
3859 while (first
!= last
&& (DEBUG_INSN_P (last
) || NOTE_P (last
)));
3861 /* Check if there is an unnecessary jump in previous basic block leading
3862 to next basic block left after removing INSN from stream.
3863 If it is so, remove that jump and redirect edge to current
3864 basic block (where there was INSN before deletion). This way
3865 when NOP will be deleted several instructions later with its
3866 basic block we will not get a jump to next instruction, which
3869 && !sel_bb_empty_p (xbb
)
3870 && INSN_NOP_P (last
)
3871 /* Flow goes fallthru from current block to the next. */
3872 && EDGE_COUNT (xbb
->succs
) == 1
3873 && (EDGE_SUCC (xbb
, 0)->flags
& EDGE_FALLTHRU
)
3874 /* When successor is an EXIT block, it may not be the next block. */
3875 && single_succ (xbb
) != EXIT_BLOCK_PTR_FOR_FN (cfun
)
3876 /* And unconditional jump in previous basic block leads to
3877 next basic block of XBB and this jump can be safely removed. */
3878 && in_current_region_p (xbb
->prev_bb
)
3879 && bb_has_removable_jump_to_p (xbb
->prev_bb
, xbb
->next_bb
)
3880 && INSN_SCHED_TIMES (BB_END (xbb
->prev_bb
)) == 0
3881 /* Also this jump is not at the scheduling boundary. */
3882 && !IN_CURRENT_FENCE_P (BB_END (xbb
->prev_bb
)))
3884 bool recompute_toporder_p
;
3885 /* Clear data structures of jump - jump itself will be removed
3886 by sel_redirect_edge_and_branch. */
3887 clear_expr (INSN_EXPR (BB_END (xbb
->prev_bb
)));
3888 recompute_toporder_p
3889 = sel_redirect_edge_and_branch (EDGE_SUCC (xbb
->prev_bb
, 0), xbb
);
3891 gcc_assert (EDGE_SUCC (xbb
->prev_bb
, 0)->flags
& EDGE_FALLTHRU
);
3893 /* It can turn out that after removing unused jump, basic block
3894 that contained that jump, becomes empty too. In such case
3896 if (sel_bb_empty_p (xbb
->prev_bb
))
3897 changed
= maybe_tidy_empty_bb (xbb
->prev_bb
);
3898 if (recompute_toporder_p
)
3899 sel_recompute_toporder ();
3902 /* TODO: use separate flag for CFG checking. */
3905 verify_backedges ();
3906 verify_dominators (CDI_DOMINATORS
);
3912 /* Purge meaningless empty blocks in the middle of a region. */
3914 purge_empty_blocks (void)
3918 /* Do not attempt to delete the first basic block in the region. */
3919 for (i
= 1; i
< current_nr_blocks
; )
3921 basic_block b
= BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (i
));
3923 if (maybe_tidy_empty_bb (b
))
3930 /* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true,
3931 do not delete insn's data, because it will be later re-emitted.
3932 Return true if we have removed some blocks afterwards. */
3934 sel_remove_insn (insn_t insn
, bool only_disconnect
, bool full_tidying
)
3936 basic_block bb
= BLOCK_FOR_INSN (insn
);
3938 gcc_assert (INSN_IN_STREAM_P (insn
));
3940 if (DEBUG_INSN_P (insn
) && BB_AV_SET_VALID_P (bb
))
3945 /* When we remove a debug insn that is head of a BB, it remains
3946 in the AV_SET of the block, but it shouldn't. */
3947 FOR_EACH_EXPR_1 (expr
, i
, &BB_AV_SET (bb
))
3948 if (EXPR_INSN_RTX (expr
) == insn
)
3950 av_set_iter_remove (&i
);
3955 if (only_disconnect
)
3960 clear_expr (INSN_EXPR (insn
));
3963 /* It is necessary to NULL these fields in case we are going to re-insert
3964 INSN into the insns stream, as will usually happen in the ONLY_DISCONNECT
3965 case, but also for NOPs that we will return to the nop pool. */
3966 SET_PREV_INSN (insn
) = NULL_RTX
;
3967 SET_NEXT_INSN (insn
) = NULL_RTX
;
3968 set_block_for_insn (insn
, NULL
);
3970 return tidy_control_flow (bb
, full_tidying
);
3973 /* Estimate number of the insns in BB. */
3975 sel_estimate_number_of_insns (basic_block bb
)
3978 insn_t insn
= NEXT_INSN (BB_HEAD (bb
)), next_tail
= NEXT_INSN (BB_END (bb
));
3980 for (; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3981 if (NONDEBUG_INSN_P (insn
))
3987 /* We don't need separate luids for notes or labels. */
3989 sel_luid_for_non_insn (rtx x
)
3991 gcc_assert (NOTE_P (x
) || LABEL_P (x
));
3996 /* Find the proper seqno for inserting at INSN by successors.
3997 Return -1 if no successors with positive seqno exist. */
3999 get_seqno_by_succs (rtx_insn
*insn
)
4001 basic_block bb
= BLOCK_FOR_INSN (insn
);
4002 rtx_insn
*tmp
= insn
, *end
= BB_END (bb
);
4009 tmp
= NEXT_INSN (tmp
);
4011 return INSN_SEQNO (tmp
);
4016 FOR_EACH_SUCC_1 (succ
, si
, end
, SUCCS_NORMAL
)
4017 if (INSN_SEQNO (succ
) > 0)
4018 seqno
= MIN (seqno
, INSN_SEQNO (succ
));
4020 if (seqno
== INT_MAX
)
4026 /* Compute seqno for INSN by its preds or succs. Use OLD_SEQNO to compute
4027 seqno in corner cases. */
4029 get_seqno_for_a_jump (insn_t insn
, int old_seqno
)
4033 gcc_assert (INSN_SIMPLEJUMP_P (insn
));
4035 if (!sel_bb_head_p (insn
))
4036 seqno
= INSN_SEQNO (PREV_INSN (insn
));
4039 basic_block bb
= BLOCK_FOR_INSN (insn
);
4041 if (single_pred_p (bb
)
4042 && !in_current_region_p (single_pred (bb
)))
4044 /* We can have preds outside a region when splitting edges
4045 for pipelining of an outer loop. Use succ instead.
4046 There should be only one of them. */
4051 gcc_assert (flag_sel_sched_pipelining_outer_loops
4052 && current_loop_nest
);
4053 FOR_EACH_SUCC_1 (succ
, si
, insn
,
4054 SUCCS_NORMAL
| SUCCS_SKIP_TO_LOOP_EXITS
)
4060 gcc_assert (succ
!= NULL
);
4061 seqno
= INSN_SEQNO (succ
);
4068 cfg_preds (BLOCK_FOR_INSN (insn
), &preds
, &n
);
4071 /* For one predecessor, use simple method. */
4073 seqno
= INSN_SEQNO (preds
[0]);
4075 seqno
= get_seqno_by_preds (insn
);
4081 /* We were unable to find a good seqno among preds. */
4083 seqno
= get_seqno_by_succs (insn
);
4087 /* The only case where this could be here legally is that the only
4088 unscheduled insn was a conditional jump that got removed and turned
4089 into this unconditional one. Initialize from the old seqno
4090 of that jump passed down to here. */
4094 gcc_assert (seqno
>= 0);
4098 /* Find the proper seqno for inserting at INSN. Returns -1 if no predecessors
4099 with positive seqno exist. */
4101 get_seqno_by_preds (rtx_insn
*insn
)
4103 basic_block bb
= BLOCK_FOR_INSN (insn
);
4104 rtx_insn
*tmp
= insn
, *head
= BB_HEAD (bb
);
4108 /* Loop backwards from INSN to HEAD including both. */
4112 return INSN_SEQNO (tmp
);
4115 tmp
= PREV_INSN (tmp
);
4118 cfg_preds (bb
, &preds
, &n
);
4119 for (i
= 0, seqno
= -1; i
< n
; i
++)
4120 seqno
= MAX (seqno
, INSN_SEQNO (preds
[i
]));
4127 /* Extend pass-scope data structures for basic blocks. */
4129 sel_extend_global_bb_info (void)
4131 sel_global_bb_info
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
4134 /* Extend region-scope data structures for basic blocks. */
4136 extend_region_bb_info (void)
4138 sel_region_bb_info
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
4141 /* Extend all data structures to fit for all basic blocks. */
4143 extend_bb_info (void)
4145 sel_extend_global_bb_info ();
4146 extend_region_bb_info ();
4149 /* Finalize pass-scope data structures for basic blocks. */
4151 sel_finish_global_bb_info (void)
4153 sel_global_bb_info
.release ();
4156 /* Finalize region-scope data structures for basic blocks. */
4158 finish_region_bb_info (void)
4160 sel_region_bb_info
.release ();
4164 /* Data for each insn in current region. */
4165 vec
<sel_insn_data_def
> s_i_d
;
4167 /* Extend data structures for insns from current region. */
4169 extend_insn_data (void)
4173 sched_extend_target ();
4174 sched_deps_init (false);
4176 /* Extend data structures for insns from current region. */
4177 reserve
= (sched_max_luid
+ 1 - s_i_d
.length ());
4178 if (reserve
> 0 && ! s_i_d
.space (reserve
))
4182 if (sched_max_luid
/ 2 > 1024)
4183 size
= sched_max_luid
+ 1024;
4185 size
= 3 * sched_max_luid
/ 2;
4188 s_i_d
.safe_grow_cleared (size
);
4192 /* Finalize data structures for insns from current region. */
4198 /* Clear here all dependence contexts that may have left from insns that were
4199 removed during the scheduling. */
4200 for (i
= 0; i
< s_i_d
.length (); i
++)
4202 sel_insn_data_def
*sid_entry
= &s_i_d
[i
];
4204 if (sid_entry
->live
)
4205 return_regset_to_pool (sid_entry
->live
);
4206 if (sid_entry
->analyzed_deps
)
4208 BITMAP_FREE (sid_entry
->analyzed_deps
);
4209 BITMAP_FREE (sid_entry
->found_deps
);
4210 htab_delete (sid_entry
->transformed_insns
);
4211 free_deps (&sid_entry
->deps_context
);
4213 if (EXPR_VINSN (&sid_entry
->expr
))
4215 clear_expr (&sid_entry
->expr
);
4217 /* Also, clear CANT_MOVE bit here, because we really don't want it
4218 to be passed to the next region. */
4219 CANT_MOVE_BY_LUID (i
) = 0;
4226 /* A proxy to pass initialization data to init_insn (). */
4227 static sel_insn_data_def _insn_init_ssid
;
4228 static sel_insn_data_t insn_init_ssid
= &_insn_init_ssid
;
4230 /* If true create a new vinsn. Otherwise use the one from EXPR. */
4231 static bool insn_init_create_new_vinsn_p
;
4233 /* Set all necessary data for initialization of the new insn[s]. */
4235 set_insn_init (expr_t expr
, vinsn_t vi
, int seqno
)
4237 expr_t x
= &insn_init_ssid
->expr
;
4239 copy_expr_onside (x
, expr
);
4242 insn_init_create_new_vinsn_p
= false;
4243 change_vinsn_in_expr (x
, vi
);
4246 insn_init_create_new_vinsn_p
= true;
4248 insn_init_ssid
->seqno
= seqno
;
4252 /* Init data for INSN. */
4254 init_insn_data (insn_t insn
)
4257 sel_insn_data_t ssid
= insn_init_ssid
;
4259 /* The fields mentioned below are special and hence are not being
4260 propagated to the new insns. */
4261 gcc_assert (!ssid
->asm_p
&& ssid
->sched_next
== NULL
4262 && !ssid
->after_stall_p
&& ssid
->sched_cycle
== 0);
4263 gcc_assert (INSN_P (insn
) && INSN_LUID (insn
) > 0);
4265 expr
= INSN_EXPR (insn
);
4266 copy_expr (expr
, &ssid
->expr
);
4267 prepare_insn_expr (insn
, ssid
->seqno
);
4269 if (insn_init_create_new_vinsn_p
)
4270 change_vinsn_in_expr (expr
, vinsn_create (insn
, init_insn_force_unique_p
));
4272 if (first_time_insn_init (insn
))
4273 init_first_time_insn_data (insn
);
4276 /* This is used to initialize spurious jumps generated by
4277 sel_redirect_edge (). OLD_SEQNO is used for initializing seqnos
4278 in corner cases within get_seqno_for_a_jump. */
4280 init_simplejump_data (insn_t insn
, int old_seqno
)
4282 init_expr (INSN_EXPR (insn
), vinsn_create (insn
, false), 0,
4283 REG_BR_PROB_BASE
, 0, 0, 0, 0, 0, 0,
4284 vNULL
, true, false, false,
4286 INSN_SEQNO (insn
) = get_seqno_for_a_jump (insn
, old_seqno
);
4287 init_first_time_insn_data (insn
);
4290 /* Perform deferred initialization of insns. This is used to process
4291 a new jump that may be created by redirect_edge. OLD_SEQNO is used
4292 for initializing simplejumps in init_simplejump_data. */
4294 sel_init_new_insn (insn_t insn
, int flags
, int old_seqno
)
4296 /* We create data structures for bb when the first insn is emitted in it. */
4298 && INSN_IN_STREAM_P (insn
)
4299 && insn_is_the_only_one_in_bb_p (insn
))
4302 create_initial_data_sets (BLOCK_FOR_INSN (insn
));
4305 if (flags
& INSN_INIT_TODO_LUID
)
4307 sched_extend_luids ();
4308 sched_init_insn_luid (insn
);
4311 if (flags
& INSN_INIT_TODO_SSID
)
4313 extend_insn_data ();
4314 init_insn_data (insn
);
4315 clear_expr (&insn_init_ssid
->expr
);
4318 if (flags
& INSN_INIT_TODO_SIMPLEJUMP
)
4320 extend_insn_data ();
4321 init_simplejump_data (insn
, old_seqno
);
4324 gcc_assert (CONTAINING_RGN (BLOCK_NUM (insn
))
4325 == CONTAINING_RGN (BB_TO_BLOCK (0)));
4329 /* Functions to init/finish work with lv sets. */
4331 /* Init BB_LV_SET of BB from DF_LR_IN set of BB. */
4333 init_lv_set (basic_block bb
)
4335 gcc_assert (!BB_LV_SET_VALID_P (bb
));
4337 BB_LV_SET (bb
) = get_regset_from_pool ();
4338 COPY_REG_SET (BB_LV_SET (bb
), DF_LR_IN (bb
));
4339 BB_LV_SET_VALID_P (bb
) = true;
4342 /* Copy liveness information to BB from FROM_BB. */
4344 copy_lv_set_from (basic_block bb
, basic_block from_bb
)
4346 gcc_assert (!BB_LV_SET_VALID_P (bb
));
4348 COPY_REG_SET (BB_LV_SET (bb
), BB_LV_SET (from_bb
));
4349 BB_LV_SET_VALID_P (bb
) = true;
4352 /* Initialize lv set of all bb headers. */
4358 /* Initialize of LV sets. */
4359 FOR_EACH_BB_FN (bb
, cfun
)
4362 /* Don't forget EXIT_BLOCK. */
4363 init_lv_set (EXIT_BLOCK_PTR_FOR_FN (cfun
));
4366 /* Release lv set of HEAD. */
4368 free_lv_set (basic_block bb
)
4370 gcc_assert (BB_LV_SET (bb
) != NULL
);
4372 return_regset_to_pool (BB_LV_SET (bb
));
4373 BB_LV_SET (bb
) = NULL
;
4374 BB_LV_SET_VALID_P (bb
) = false;
4377 /* Finalize lv sets of all bb headers. */
4383 /* Don't forget EXIT_BLOCK. */
4384 free_lv_set (EXIT_BLOCK_PTR_FOR_FN (cfun
));
4387 FOR_EACH_BB_FN (bb
, cfun
)
4392 /* Mark AV_SET for BB as invalid, so this set will be updated the next time
4393 compute_av() processes BB. This function is called when creating new basic
4394 blocks, as well as for blocks (either new or existing) where new jumps are
4395 created when the control flow is being updated. */
4397 invalidate_av_set (basic_block bb
)
4399 BB_AV_LEVEL (bb
) = -1;
4402 /* Create initial data sets for BB (they will be invalid). */
4404 create_initial_data_sets (basic_block bb
)
4407 BB_LV_SET_VALID_P (bb
) = false;
4409 BB_LV_SET (bb
) = get_regset_from_pool ();
4410 invalidate_av_set (bb
);
4413 /* Free av set of BB. */
4415 free_av_set (basic_block bb
)
4417 av_set_clear (&BB_AV_SET (bb
));
4418 BB_AV_LEVEL (bb
) = 0;
4421 /* Free data sets of BB. */
4423 free_data_sets (basic_block bb
)
4429 /* Exchange data sets of TO and FROM. */
4431 exchange_data_sets (basic_block to
, basic_block from
)
4433 /* Exchange lv sets of TO and FROM. */
4434 std::swap (BB_LV_SET (from
), BB_LV_SET (to
));
4435 std::swap (BB_LV_SET_VALID_P (from
), BB_LV_SET_VALID_P (to
));
4437 /* Exchange av sets of TO and FROM. */
4438 std::swap (BB_AV_SET (from
), BB_AV_SET (to
));
4439 std::swap (BB_AV_LEVEL (from
), BB_AV_LEVEL (to
));
4442 /* Copy data sets of FROM to TO. */
4444 copy_data_sets (basic_block to
, basic_block from
)
4446 gcc_assert (!BB_LV_SET_VALID_P (to
) && !BB_AV_SET_VALID_P (to
));
4447 gcc_assert (BB_AV_SET (to
) == NULL
);
4449 BB_AV_LEVEL (to
) = BB_AV_LEVEL (from
);
4450 BB_LV_SET_VALID_P (to
) = BB_LV_SET_VALID_P (from
);
4452 if (BB_AV_SET_VALID_P (from
))
4454 BB_AV_SET (to
) = av_set_copy (BB_AV_SET (from
));
4456 if (BB_LV_SET_VALID_P (from
))
4458 gcc_assert (BB_LV_SET (to
) != NULL
);
4459 COPY_REG_SET (BB_LV_SET (to
), BB_LV_SET (from
));
4463 /* Return an av set for INSN, if any. */
4465 get_av_set (insn_t insn
)
4469 gcc_assert (AV_SET_VALID_P (insn
));
4471 if (sel_bb_head_p (insn
))
4472 av_set
= BB_AV_SET (BLOCK_FOR_INSN (insn
));
4479 /* Implementation of AV_LEVEL () macro. Return AV_LEVEL () of INSN. */
4481 get_av_level (insn_t insn
)
4485 gcc_assert (INSN_P (insn
));
4487 if (sel_bb_head_p (insn
))
4488 av_level
= BB_AV_LEVEL (BLOCK_FOR_INSN (insn
));
4490 av_level
= INSN_WS_LEVEL (insn
);
4497 /* Variables to work with control-flow graph. */
4499 /* The basic block that already has been processed by the sched_data_update (),
4500 but hasn't been in sel_add_bb () yet. */
4501 static vec
<basic_block
> last_added_blocks
;
4503 /* A pool for allocating successor infos. */
4506 /* A stack for saving succs_info structures. */
4507 struct succs_info
*stack
;
4512 /* Top of the stack. */
4515 /* Maximal value of the top. */
4519 /* Functions to work with control-flow graph. */
4521 /* Return basic block note of BB. */
4523 sel_bb_head (basic_block bb
)
4527 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4529 gcc_assert (exit_insn
!= NULL_RTX
);
4534 rtx_note
*note
= bb_note (bb
);
4535 head
= next_nonnote_insn (note
);
4537 if (head
&& (BARRIER_P (head
) || BLOCK_FOR_INSN (head
) != bb
))
4544 /* Return true if INSN is a basic block header. */
4546 sel_bb_head_p (insn_t insn
)
4548 return sel_bb_head (BLOCK_FOR_INSN (insn
)) == insn
;
4551 /* Return last insn of BB. */
4553 sel_bb_end (basic_block bb
)
4555 if (sel_bb_empty_p (bb
))
4558 gcc_assert (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
4563 /* Return true if INSN is the last insn in its basic block. */
4565 sel_bb_end_p (insn_t insn
)
4567 return insn
== sel_bb_end (BLOCK_FOR_INSN (insn
));
4570 /* Return true if BB consist of single NOTE_INSN_BASIC_BLOCK. */
4572 sel_bb_empty_p (basic_block bb
)
4574 return sel_bb_head (bb
) == NULL
;
4577 /* True when BB belongs to the current scheduling region. */
4579 in_current_region_p (basic_block bb
)
4581 if (bb
->index
< NUM_FIXED_BLOCKS
)
4584 return CONTAINING_RGN (bb
->index
) == CONTAINING_RGN (BB_TO_BLOCK (0));
4587 /* Return the block which is a fallthru bb of a conditional jump JUMP. */
4589 fallthru_bb_of_jump (const rtx_insn
*jump
)
4594 if (!any_condjump_p (jump
))
4597 /* A basic block that ends with a conditional jump may still have one successor
4598 (and be followed by a barrier), we are not interested. */
4599 if (single_succ_p (BLOCK_FOR_INSN (jump
)))
4602 return FALLTHRU_EDGE (BLOCK_FOR_INSN (jump
))->dest
;
4605 /* Remove all notes from BB. */
4607 init_bb (basic_block bb
)
4609 remove_notes (bb_note (bb
), BB_END (bb
));
4610 BB_NOTE_LIST (bb
) = note_list
;
4614 sel_init_bbs (bb_vec_t bbs
)
4616 const struct sched_scan_info_def ssi
=
4618 extend_bb_info
, /* extend_bb */
4619 init_bb
, /* init_bb */
4620 NULL
, /* extend_insn */
4621 NULL
/* init_insn */
4624 sched_scan (&ssi
, bbs
);
4627 /* Restore notes for the whole region. */
4629 sel_restore_notes (void)
4634 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
4636 basic_block first
, last
;
4638 first
= EBB_FIRST_BB (bb
);
4639 last
= EBB_LAST_BB (bb
)->next_bb
;
4643 note_list
= BB_NOTE_LIST (first
);
4644 restore_other_notes (NULL
, first
);
4645 BB_NOTE_LIST (first
) = NULL
;
4647 FOR_BB_INSNS (first
, insn
)
4648 if (NONDEBUG_INSN_P (insn
))
4649 reemit_notes (insn
);
4651 first
= first
->next_bb
;
4653 while (first
!= last
);
4657 /* Free per-bb data structures. */
4659 sel_finish_bbs (void)
4661 sel_restore_notes ();
4663 /* Remove current loop preheader from this loop. */
4664 if (current_loop_nest
)
4665 sel_remove_loop_preheader ();
4667 finish_region_bb_info ();
4670 /* Return true if INSN has a single successor of type FLAGS. */
4672 sel_insn_has_single_succ_p (insn_t insn
, int flags
)
4676 bool first_p
= true;
4678 FOR_EACH_SUCC_1 (succ
, si
, insn
, flags
)
4689 /* Allocate successor's info. */
4690 static struct succs_info
*
4691 alloc_succs_info (void)
4693 if (succs_info_pool
.top
== succs_info_pool
.max_top
)
4697 if (++succs_info_pool
.max_top
>= succs_info_pool
.size
)
4700 i
= ++succs_info_pool
.top
;
4701 succs_info_pool
.stack
[i
].succs_ok
.create (10);
4702 succs_info_pool
.stack
[i
].succs_other
.create (10);
4703 succs_info_pool
.stack
[i
].probs_ok
.create (10);
4706 succs_info_pool
.top
++;
4708 return &succs_info_pool
.stack
[succs_info_pool
.top
];
4711 /* Free successor's info. */
4713 free_succs_info (struct succs_info
* sinfo
)
4715 gcc_assert (succs_info_pool
.top
>= 0
4716 && &succs_info_pool
.stack
[succs_info_pool
.top
] == sinfo
);
4717 succs_info_pool
.top
--;
4719 /* Clear stale info. */
4720 sinfo
->succs_ok
.block_remove (0, sinfo
->succs_ok
.length ());
4721 sinfo
->succs_other
.block_remove (0, sinfo
->succs_other
.length ());
4722 sinfo
->probs_ok
.block_remove (0, sinfo
->probs_ok
.length ());
4723 sinfo
->all_prob
= 0;
4724 sinfo
->succs_ok_n
= 0;
4725 sinfo
->all_succs_n
= 0;
4728 /* Compute successor info for INSN. FLAGS are the flags passed
4729 to the FOR_EACH_SUCC_1 iterator. */
4731 compute_succs_info (insn_t insn
, short flags
)
4735 struct succs_info
*sinfo
= alloc_succs_info ();
4737 /* Traverse *all* successors and decide what to do with each. */
4738 FOR_EACH_SUCC_1 (succ
, si
, insn
, SUCCS_ALL
)
4740 /* FIXME: this doesn't work for skipping to loop exits, as we don't
4741 perform code motion through inner loops. */
4742 short current_flags
= si
.current_flags
& ~SUCCS_SKIP_TO_LOOP_EXITS
;
4744 if (current_flags
& flags
)
4746 sinfo
->succs_ok
.safe_push (succ
);
4747 sinfo
->probs_ok
.safe_push (
4748 /* FIXME: Improve calculation when skipping
4749 inner loop to exits. */
4751 ? (si
.e1
->probability
.initialized_p ()
4752 ? si
.e1
->probability
.to_reg_br_prob_base ()
4754 : REG_BR_PROB_BASE
);
4755 sinfo
->succs_ok_n
++;
4758 sinfo
->succs_other
.safe_push (succ
);
4760 /* Compute all_prob. */
4762 sinfo
->all_prob
= REG_BR_PROB_BASE
;
4763 else if (si
.e1
->probability
.initialized_p ())
4764 sinfo
->all_prob
+= si
.e1
->probability
.to_reg_br_prob_base ();
4766 sinfo
->all_succs_n
++;
4772 /* Return the predecessors of BB in PREDS and their number in N.
4773 Empty blocks are skipped. SIZE is used to allocate PREDS. */
4775 cfg_preds_1 (basic_block bb
, insn_t
**preds
, int *n
, int *size
)
4780 gcc_assert (BLOCK_TO_BB (bb
->index
) != 0);
4782 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4784 basic_block pred_bb
= e
->src
;
4785 insn_t bb_end
= BB_END (pred_bb
);
4787 if (!in_current_region_p (pred_bb
))
4789 gcc_assert (flag_sel_sched_pipelining_outer_loops
4790 && current_loop_nest
);
4794 if (sel_bb_empty_p (pred_bb
))
4795 cfg_preds_1 (pred_bb
, preds
, n
, size
);
4799 *preds
= XRESIZEVEC (insn_t
, *preds
,
4800 (*size
= 2 * *size
+ 1));
4801 (*preds
)[(*n
)++] = bb_end
;
4806 || (flag_sel_sched_pipelining_outer_loops
4807 && current_loop_nest
));
4810 /* Find all predecessors of BB and record them in PREDS and their number
4811 in N. Empty blocks are skipped, and only normal (forward in-region)
4812 edges are processed. */
4814 cfg_preds (basic_block bb
, insn_t
**preds
, int *n
)
4820 cfg_preds_1 (bb
, preds
, n
, &size
);
4823 /* Returns true if we are moving INSN through join point. */
4825 sel_num_cfg_preds_gt_1 (insn_t insn
)
4829 if (!sel_bb_head_p (insn
) || INSN_BB (insn
) == 0)
4832 bb
= BLOCK_FOR_INSN (insn
);
4836 if (EDGE_COUNT (bb
->preds
) > 1)
4839 gcc_assert (EDGE_PRED (bb
, 0)->dest
== bb
);
4840 bb
= EDGE_PRED (bb
, 0)->src
;
4842 if (!sel_bb_empty_p (bb
))
4849 /* Returns true when BB should be the end of an ebb. Adapted from the
4850 code in sched-ebb.c. */
4852 bb_ends_ebb_p (basic_block bb
)
4854 basic_block next_bb
= bb_next_bb (bb
);
4857 if (next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
4858 || bitmap_bit_p (forced_ebb_heads
, next_bb
->index
)
4859 || (LABEL_P (BB_HEAD (next_bb
))
4860 /* NB: LABEL_NUSES () is not maintained outside of jump.c.
4861 Work around that. */
4862 && !single_pred_p (next_bb
)))
4865 if (!in_current_region_p (next_bb
))
4868 e
= find_fallthru_edge (bb
->succs
);
4871 gcc_assert (e
->dest
== next_bb
);
4879 /* Returns true when INSN and SUCC are in the same EBB, given that SUCC is a
4880 successor of INSN. */
4882 in_same_ebb_p (insn_t insn
, insn_t succ
)
4884 basic_block ptr
= BLOCK_FOR_INSN (insn
);
4888 if (ptr
== BLOCK_FOR_INSN (succ
))
4891 if (bb_ends_ebb_p (ptr
))
4894 ptr
= bb_next_bb (ptr
);
4901 /* Recomputes the reverse topological order for the function and
4902 saves it in REV_TOP_ORDER_INDEX. REV_TOP_ORDER_INDEX_LEN is also
4903 modified appropriately. */
4905 recompute_rev_top_order (void)
4910 if (!rev_top_order_index
4911 || rev_top_order_index_len
< last_basic_block_for_fn (cfun
))
4913 rev_top_order_index_len
= last_basic_block_for_fn (cfun
);
4914 rev_top_order_index
= XRESIZEVEC (int, rev_top_order_index
,
4915 rev_top_order_index_len
);
4918 postorder
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
4920 n_blocks
= post_order_compute (postorder
, true, false);
4921 gcc_assert (n_basic_blocks_for_fn (cfun
) == n_blocks
);
4923 /* Build reverse function: for each basic block with BB->INDEX == K
4924 rev_top_order_index[K] is it's reverse topological sort number. */
4925 for (i
= 0; i
< n_blocks
; i
++)
4927 gcc_assert (postorder
[i
] < rev_top_order_index_len
);
4928 rev_top_order_index
[postorder
[i
]] = i
;
4934 /* Clear all flags from insns in BB that could spoil its rescheduling. */
4936 clear_outdated_rtx_info (basic_block bb
)
4940 FOR_BB_INSNS (bb
, insn
)
4943 SCHED_GROUP_P (insn
) = 0;
4944 INSN_AFTER_STALL_P (insn
) = 0;
4945 INSN_SCHED_TIMES (insn
) = 0;
4946 EXPR_PRIORITY_ADJ (INSN_EXPR (insn
)) = 0;
4948 /* We cannot use the changed caches, as previously we could ignore
4949 the LHS dependence due to enabled renaming and transform
4950 the expression, and currently we'll be unable to do this. */
4951 htab_empty (INSN_TRANSFORMED_INSNS (insn
));
4955 /* Add BB_NOTE to the pool of available basic block notes. */
4957 return_bb_to_pool (basic_block bb
)
4959 rtx_note
*note
= bb_note (bb
);
4961 gcc_assert (NOTE_BASIC_BLOCK (note
) == bb
4962 && bb
->aux
== NULL
);
4964 /* It turns out that current cfg infrastructure does not support
4965 reuse of basic blocks. Don't bother for now. */
4966 /*bb_note_pool.safe_push (note);*/
4969 /* Get a bb_note from pool or return NULL_RTX if pool is empty. */
4971 get_bb_note_from_pool (void)
4973 if (bb_note_pool
.is_empty ())
4977 rtx_note
*note
= bb_note_pool
.pop ();
4979 SET_PREV_INSN (note
) = NULL_RTX
;
4980 SET_NEXT_INSN (note
) = NULL_RTX
;
4986 /* Free bb_note_pool. */
4988 free_bb_note_pool (void)
4990 bb_note_pool
.release ();
4993 /* Setup scheduler pool and successor structure. */
4995 alloc_sched_pools (void)
4999 succs_size
= MAX_WS
+ 1;
5000 succs_info_pool
.stack
= XCNEWVEC (struct succs_info
, succs_size
);
5001 succs_info_pool
.size
= succs_size
;
5002 succs_info_pool
.top
= -1;
5003 succs_info_pool
.max_top
= -1;
5006 /* Free the pools. */
5008 free_sched_pools (void)
5012 sched_lists_pool
.release ();
5013 gcc_assert (succs_info_pool
.top
== -1);
5014 for (i
= 0; i
<= succs_info_pool
.max_top
; i
++)
5016 succs_info_pool
.stack
[i
].succs_ok
.release ();
5017 succs_info_pool
.stack
[i
].succs_other
.release ();
5018 succs_info_pool
.stack
[i
].probs_ok
.release ();
5020 free (succs_info_pool
.stack
);
5024 /* Returns a position in RGN where BB can be inserted retaining
5025 topological order. */
5027 find_place_to_insert_bb (basic_block bb
, int rgn
)
5029 bool has_preds_outside_rgn
= false;
5033 /* Find whether we have preds outside the region. */
5034 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
5035 if (!in_current_region_p (e
->src
))
5037 has_preds_outside_rgn
= true;
5041 /* Recompute the top order -- needed when we have > 1 pred
5042 and in case we don't have preds outside. */
5043 if (flag_sel_sched_pipelining_outer_loops
5044 && (has_preds_outside_rgn
|| EDGE_COUNT (bb
->preds
) > 1))
5046 int i
, bbi
= bb
->index
, cur_bbi
;
5048 recompute_rev_top_order ();
5049 for (i
= RGN_NR_BLOCKS (rgn
) - 1; i
>= 0; i
--)
5051 cur_bbi
= BB_TO_BLOCK (i
);
5052 if (rev_top_order_index
[bbi
]
5053 < rev_top_order_index
[cur_bbi
])
5057 /* We skipped the right block, so we increase i. We accommodate
5058 it for increasing by step later, so we decrease i. */
5061 else if (has_preds_outside_rgn
)
5063 /* This is the case when we generate an extra empty block
5064 to serve as region head during pipelining. */
5065 e
= EDGE_SUCC (bb
, 0);
5066 gcc_assert (EDGE_COUNT (bb
->succs
) == 1
5067 && in_current_region_p (EDGE_SUCC (bb
, 0)->dest
)
5068 && (BLOCK_TO_BB (e
->dest
->index
) == 0));
5072 /* We don't have preds outside the region. We should have
5073 the only pred, because the multiple preds case comes from
5074 the pipelining of outer loops, and that is handled above.
5075 Just take the bbi of this single pred. */
5076 if (EDGE_COUNT (bb
->succs
) > 0)
5080 gcc_assert (EDGE_COUNT (bb
->preds
) == 1);
5082 pred_bbi
= EDGE_PRED (bb
, 0)->src
->index
;
5083 return BLOCK_TO_BB (pred_bbi
);
5086 /* BB has no successors. It is safe to put it in the end. */
5087 return current_nr_blocks
- 1;
5090 /* Deletes an empty basic block freeing its data. */
5092 delete_and_free_basic_block (basic_block bb
)
5094 gcc_assert (sel_bb_empty_p (bb
));
5099 bitmap_clear_bit (blocks_to_reschedule
, bb
->index
);
5101 /* Can't assert av_set properties because we use sel_aremove_bb
5102 when removing loop preheader from the region. At the point of
5103 removing the preheader we already have deallocated sel_region_bb_info. */
5104 gcc_assert (BB_LV_SET (bb
) == NULL
5105 && !BB_LV_SET_VALID_P (bb
)
5106 && BB_AV_LEVEL (bb
) == 0
5107 && BB_AV_SET (bb
) == NULL
);
5109 delete_basic_block (bb
);
5112 /* Add BB to the current region and update the region data. */
5114 add_block_to_current_region (basic_block bb
)
5116 int i
, pos
, bbi
= -2, rgn
;
5118 rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
5119 bbi
= find_place_to_insert_bb (bb
, rgn
);
5121 pos
= RGN_BLOCKS (rgn
) + bbi
;
5123 gcc_assert (RGN_HAS_REAL_EBB (rgn
) == 0
5124 && ebb_head
[bbi
] == pos
);
5126 /* Make a place for the new block. */
5129 for (i
= RGN_BLOCKS (rgn
+ 1) - 1; i
>= pos
; i
--)
5130 BLOCK_TO_BB (rgn_bb_table
[i
])++;
5132 memmove (rgn_bb_table
+ pos
+ 1,
5134 (RGN_BLOCKS (nr_regions
) - pos
) * sizeof (*rgn_bb_table
));
5136 /* Initialize data for BB. */
5137 rgn_bb_table
[pos
] = bb
->index
;
5138 BLOCK_TO_BB (bb
->index
) = bbi
;
5139 CONTAINING_RGN (bb
->index
) = rgn
;
5141 RGN_NR_BLOCKS (rgn
)++;
5143 for (i
= rgn
+ 1; i
<= nr_regions
; i
++)
5147 /* Remove BB from the current region and update the region data. */
5149 remove_bb_from_region (basic_block bb
)
5151 int i
, pos
, bbi
= -2, rgn
;
5153 rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
5154 bbi
= BLOCK_TO_BB (bb
->index
);
5155 pos
= RGN_BLOCKS (rgn
) + bbi
;
5157 gcc_assert (RGN_HAS_REAL_EBB (rgn
) == 0
5158 && ebb_head
[bbi
] == pos
);
5160 for (i
= RGN_BLOCKS (rgn
+ 1) - 1; i
>= pos
; i
--)
5161 BLOCK_TO_BB (rgn_bb_table
[i
])--;
5163 memmove (rgn_bb_table
+ pos
,
5164 rgn_bb_table
+ pos
+ 1,
5165 (RGN_BLOCKS (nr_regions
) - pos
) * sizeof (*rgn_bb_table
));
5167 RGN_NR_BLOCKS (rgn
)--;
5168 for (i
= rgn
+ 1; i
<= nr_regions
; i
++)
5172 /* Add BB to the current region and update all data. If BB is NULL, add all
5173 blocks from last_added_blocks vector. */
5175 sel_add_bb (basic_block bb
)
5177 /* Extend luids so that new notes will receive zero luids. */
5178 sched_extend_luids ();
5180 sel_init_bbs (last_added_blocks
);
5182 /* When bb is passed explicitly, the vector should contain
5183 the only element that equals to bb; otherwise, the vector
5184 should not be NULL. */
5185 gcc_assert (last_added_blocks
.exists ());
5189 gcc_assert (last_added_blocks
.length () == 1
5190 && last_added_blocks
[0] == bb
);
5191 add_block_to_current_region (bb
);
5193 /* We associate creating/deleting data sets with the first insn
5194 appearing / disappearing in the bb. */
5195 if (!sel_bb_empty_p (bb
) && BB_LV_SET (bb
) == NULL
)
5196 create_initial_data_sets (bb
);
5198 last_added_blocks
.release ();
5201 /* BB is NULL - process LAST_ADDED_BLOCKS instead. */
5204 basic_block temp_bb
= NULL
;
5207 last_added_blocks
.iterate (i
, &bb
); i
++)
5209 add_block_to_current_region (bb
);
5213 /* We need to fetch at least one bb so we know the region
5215 gcc_assert (temp_bb
!= NULL
);
5218 last_added_blocks
.release ();
5221 rgn_setup_region (CONTAINING_RGN (bb
->index
));
5224 /* Remove BB from the current region and update all data.
5225 If REMOVE_FROM_CFG_PBB is true, also remove the block cfom cfg. */
5227 sel_remove_bb (basic_block bb
, bool remove_from_cfg_p
)
5229 unsigned idx
= bb
->index
;
5231 gcc_assert (bb
!= NULL
&& BB_NOTE_LIST (bb
) == NULL_RTX
);
5233 remove_bb_from_region (bb
);
5234 return_bb_to_pool (bb
);
5235 bitmap_clear_bit (blocks_to_reschedule
, idx
);
5237 if (remove_from_cfg_p
)
5239 basic_block succ
= single_succ (bb
);
5240 delete_and_free_basic_block (bb
);
5241 set_immediate_dominator (CDI_DOMINATORS
, succ
,
5242 recompute_dominator (CDI_DOMINATORS
, succ
));
5245 rgn_setup_region (CONTAINING_RGN (idx
));
5248 /* Concatenate info of EMPTY_BB to info of MERGE_BB. */
5250 move_bb_info (basic_block merge_bb
, basic_block empty_bb
)
5252 if (in_current_region_p (merge_bb
))
5253 concat_note_lists (BB_NOTE_LIST (empty_bb
),
5254 &BB_NOTE_LIST (merge_bb
));
5255 BB_NOTE_LIST (empty_bb
) = NULL
;
5259 /* Remove EMPTY_BB. If REMOVE_FROM_CFG_P is false, remove EMPTY_BB from
5260 region, but keep it in CFG. */
5262 remove_empty_bb (basic_block empty_bb
, bool remove_from_cfg_p
)
5264 /* The block should contain just a note or a label.
5265 We try to check whether it is unused below. */
5266 gcc_assert (BB_HEAD (empty_bb
) == BB_END (empty_bb
)
5267 || LABEL_P (BB_HEAD (empty_bb
)));
5269 /* If basic block has predecessors or successors, redirect them. */
5270 if (remove_from_cfg_p
5271 && (EDGE_COUNT (empty_bb
->preds
) > 0
5272 || EDGE_COUNT (empty_bb
->succs
) > 0))
5277 /* We need to init PRED and SUCC before redirecting edges. */
5278 if (EDGE_COUNT (empty_bb
->preds
) > 0)
5282 gcc_assert (EDGE_COUNT (empty_bb
->preds
) == 1);
5284 e
= EDGE_PRED (empty_bb
, 0);
5285 gcc_assert (e
->src
== empty_bb
->prev_bb
5286 && (e
->flags
& EDGE_FALLTHRU
));
5288 pred
= empty_bb
->prev_bb
;
5293 if (EDGE_COUNT (empty_bb
->succs
) > 0)
5295 /* We do not check fallthruness here as above, because
5296 after removing a jump the edge may actually be not fallthru. */
5297 gcc_assert (EDGE_COUNT (empty_bb
->succs
) == 1);
5298 succ
= EDGE_SUCC (empty_bb
, 0)->dest
;
5303 if (EDGE_COUNT (empty_bb
->preds
) > 0 && succ
!= NULL
)
5305 edge e
= EDGE_PRED (empty_bb
, 0);
5307 if (e
->flags
& EDGE_FALLTHRU
)
5308 redirect_edge_succ_nodup (e
, succ
);
5310 sel_redirect_edge_and_branch (EDGE_PRED (empty_bb
, 0), succ
);
5313 if (EDGE_COUNT (empty_bb
->succs
) > 0 && pred
!= NULL
)
5315 edge e
= EDGE_SUCC (empty_bb
, 0);
5317 if (find_edge (pred
, e
->dest
) == NULL
)
5318 redirect_edge_pred (e
, pred
);
5322 /* Finish removing. */
5323 sel_remove_bb (empty_bb
, remove_from_cfg_p
);
5326 /* An implementation of create_basic_block hook, which additionally updates
5327 per-bb data structures. */
5329 sel_create_basic_block (void *headp
, void *endp
, basic_block after
)
5332 rtx_note
*new_bb_note
;
5334 gcc_assert (flag_sel_sched_pipelining_outer_loops
5335 || !last_added_blocks
.exists ());
5337 new_bb_note
= get_bb_note_from_pool ();
5339 if (new_bb_note
== NULL_RTX
)
5340 new_bb
= orig_cfg_hooks
.create_basic_block (headp
, endp
, after
);
5343 new_bb
= create_basic_block_structure ((rtx_insn
*) headp
,
5345 new_bb_note
, after
);
5349 last_added_blocks
.safe_push (new_bb
);
5354 /* Implement sched_init_only_bb (). */
5356 sel_init_only_bb (basic_block bb
, basic_block after
)
5358 gcc_assert (after
== NULL
);
5361 rgn_make_new_region_out_of_new_block (bb
);
5364 /* Update the latch when we've splitted or merged it from FROM block to TO.
5365 This should be checked for all outer loops, too. */
5367 change_loops_latches (basic_block from
, basic_block to
)
5369 gcc_assert (from
!= to
);
5371 if (current_loop_nest
)
5375 for (loop
= current_loop_nest
; loop
; loop
= loop_outer (loop
))
5376 if (considered_for_pipelining_p (loop
) && loop
->latch
== from
)
5378 gcc_assert (loop
== current_loop_nest
);
5380 gcc_assert (loop_latch_edge (loop
));
5385 /* Splits BB on two basic blocks, adding it to the region and extending
5386 per-bb data structures. Returns the newly created bb. */
5388 sel_split_block (basic_block bb
, rtx after
)
5393 new_bb
= sched_split_block_1 (bb
, after
);
5394 sel_add_bb (new_bb
);
5396 /* This should be called after sel_add_bb, because this uses
5397 CONTAINING_RGN for the new block, which is not yet initialized.
5398 FIXME: this function may be a no-op now. */
5399 change_loops_latches (bb
, new_bb
);
5401 /* Update ORIG_BB_INDEX for insns moved into the new block. */
5402 FOR_BB_INSNS (new_bb
, insn
)
5404 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn
)) = new_bb
->index
;
5406 if (sel_bb_empty_p (bb
))
5408 gcc_assert (!sel_bb_empty_p (new_bb
));
5410 /* NEW_BB has data sets that need to be updated and BB holds
5411 data sets that should be removed. Exchange these data sets
5412 so that we won't lose BB's valid data sets. */
5413 exchange_data_sets (new_bb
, bb
);
5414 free_data_sets (bb
);
5417 if (!sel_bb_empty_p (new_bb
)
5418 && bitmap_bit_p (blocks_to_reschedule
, bb
->index
))
5419 bitmap_set_bit (blocks_to_reschedule
, new_bb
->index
);
5424 /* If BB ends with a jump insn whose ID is bigger then PREV_MAX_UID, return it.
5425 Otherwise returns NULL. */
5427 check_for_new_jump (basic_block bb
, int prev_max_uid
)
5431 end
= sel_bb_end (bb
);
5432 if (end
&& INSN_UID (end
) >= prev_max_uid
)
5437 /* Look for a new jump either in FROM_BB block or in newly created JUMP_BB block.
5438 New means having UID at least equal to PREV_MAX_UID. */
5440 find_new_jump (basic_block from
, basic_block jump_bb
, int prev_max_uid
)
5444 /* Return immediately if no new insns were emitted. */
5445 if (get_max_uid () == prev_max_uid
)
5448 /* Now check both blocks for new jumps. It will ever be only one. */
5449 if ((jump
= check_for_new_jump (from
, prev_max_uid
)))
5453 && (jump
= check_for_new_jump (jump_bb
, prev_max_uid
)))
5458 /* Splits E and adds the newly created basic block to the current region.
5459 Returns this basic block. */
5461 sel_split_edge (edge e
)
5463 basic_block new_bb
, src
, other_bb
= NULL
;
5468 prev_max_uid
= get_max_uid ();
5469 new_bb
= split_edge (e
);
5471 if (flag_sel_sched_pipelining_outer_loops
5472 && current_loop_nest
)
5477 /* Some of the basic blocks might not have been added to the loop.
5478 Add them here, until this is fixed in force_fallthru. */
5480 last_added_blocks
.iterate (i
, &bb
); i
++)
5481 if (!bb
->loop_father
)
5483 add_bb_to_loop (bb
, e
->dest
->loop_father
);
5485 gcc_assert (!other_bb
&& (new_bb
->index
!= bb
->index
));
5490 /* Add all last_added_blocks to the region. */
5493 jump
= find_new_jump (src
, new_bb
, prev_max_uid
);
5495 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
);
5497 /* Put the correct lv set on this block. */
5498 if (other_bb
&& !sel_bb_empty_p (other_bb
))
5499 compute_live (sel_bb_head (other_bb
));
5504 /* Implement sched_create_empty_bb (). */
5506 sel_create_empty_bb (basic_block after
)
5510 new_bb
= sched_create_empty_bb_1 (after
);
5512 /* We'll explicitly initialize NEW_BB via sel_init_only_bb () a bit
5514 gcc_assert (last_added_blocks
.length () == 1
5515 && last_added_blocks
[0] == new_bb
);
5517 last_added_blocks
.release ();
5521 /* Implement sched_create_recovery_block. ORIG_INSN is where block
5522 will be splitted to insert a check. */
5524 sel_create_recovery_block (insn_t orig_insn
)
5526 basic_block first_bb
, second_bb
, recovery_block
;
5527 basic_block before_recovery
= NULL
;
5530 first_bb
= BLOCK_FOR_INSN (orig_insn
);
5531 if (sel_bb_end_p (orig_insn
))
5533 /* Avoid introducing an empty block while splitting. */
5534 gcc_assert (single_succ_p (first_bb
));
5535 second_bb
= single_succ (first_bb
);
5538 second_bb
= sched_split_block (first_bb
, orig_insn
);
5540 recovery_block
= sched_create_recovery_block (&before_recovery
);
5541 if (before_recovery
)
5542 copy_lv_set_from (before_recovery
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
5544 gcc_assert (sel_bb_empty_p (recovery_block
));
5545 sched_create_recovery_edges (first_bb
, recovery_block
, second_bb
);
5546 if (current_loops
!= NULL
)
5547 add_bb_to_loop (recovery_block
, first_bb
->loop_father
);
5549 sel_add_bb (recovery_block
);
5551 jump
= BB_END (recovery_block
);
5552 gcc_assert (sel_bb_head (recovery_block
) == jump
);
5553 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
);
5555 return recovery_block
;
5558 /* Merge basic block B into basic block A. */
5560 sel_merge_blocks (basic_block a
, basic_block b
)
5562 gcc_assert (sel_bb_empty_p (b
)
5563 && EDGE_COUNT (b
->preds
) == 1
5564 && EDGE_PRED (b
, 0)->src
== b
->prev_bb
);
5566 move_bb_info (b
->prev_bb
, b
);
5567 remove_empty_bb (b
, false);
5568 merge_blocks (a
, b
);
5569 change_loops_latches (b
, a
);
5572 /* A wrapper for redirect_edge_and_branch_force, which also initializes
5573 data structures for possibly created bb and insns. */
5575 sel_redirect_edge_and_branch_force (edge e
, basic_block to
)
5577 basic_block jump_bb
, src
, orig_dest
= e
->dest
;
5582 /* This function is now used only for bookkeeping code creation, where
5583 we'll never get the single pred of orig_dest block and thus will not
5584 hit unreachable blocks when updating dominator info. */
5585 gcc_assert (!sel_bb_empty_p (e
->src
)
5586 && !single_pred_p (orig_dest
));
5588 prev_max_uid
= get_max_uid ();
5589 /* Compute and pass old_seqno down to sel_init_new_insn only for the case
5590 when the conditional jump being redirected may become unconditional. */
5591 if (any_condjump_p (BB_END (src
))
5592 && INSN_SEQNO (BB_END (src
)) >= 0)
5593 old_seqno
= INSN_SEQNO (BB_END (src
));
5595 jump_bb
= redirect_edge_and_branch_force (e
, to
);
5596 if (jump_bb
!= NULL
)
5597 sel_add_bb (jump_bb
);
5599 /* This function could not be used to spoil the loop structure by now,
5600 thus we don't care to update anything. But check it to be sure. */
5601 if (current_loop_nest
5603 gcc_assert (loop_latch_edge (current_loop_nest
));
5605 jump
= find_new_jump (src
, jump_bb
, prev_max_uid
);
5607 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
,
5609 set_immediate_dominator (CDI_DOMINATORS
, to
,
5610 recompute_dominator (CDI_DOMINATORS
, to
));
5611 set_immediate_dominator (CDI_DOMINATORS
, orig_dest
,
5612 recompute_dominator (CDI_DOMINATORS
, orig_dest
));
5615 /* A wrapper for redirect_edge_and_branch. Return TRUE if blocks connected by
5616 redirected edge are in reverse topological order. */
5618 sel_redirect_edge_and_branch (edge e
, basic_block to
)
5621 basic_block src
, orig_dest
= e
->dest
;
5625 bool recompute_toporder_p
= false;
5626 bool maybe_unreachable
= single_pred_p (orig_dest
);
5629 latch_edge_p
= (pipelining_p
5630 && current_loop_nest
5631 && e
== loop_latch_edge (current_loop_nest
));
5634 prev_max_uid
= get_max_uid ();
5636 /* Compute and pass old_seqno down to sel_init_new_insn only for the case
5637 when the conditional jump being redirected may become unconditional. */
5638 if (any_condjump_p (BB_END (src
))
5639 && INSN_SEQNO (BB_END (src
)) >= 0)
5640 old_seqno
= INSN_SEQNO (BB_END (src
));
5642 redirected
= redirect_edge_and_branch (e
, to
);
5644 gcc_assert (redirected
&& !last_added_blocks
.exists ());
5646 /* When we've redirected a latch edge, update the header. */
5649 current_loop_nest
->header
= to
;
5650 gcc_assert (loop_latch_edge (current_loop_nest
));
5653 /* In rare situations, the topological relation between the blocks connected
5654 by the redirected edge can change (see PR42245 for an example). Update
5655 block_to_bb/bb_to_block. */
5656 if (CONTAINING_RGN (e
->src
->index
) == CONTAINING_RGN (to
->index
)
5657 && BLOCK_TO_BB (e
->src
->index
) > BLOCK_TO_BB (to
->index
))
5658 recompute_toporder_p
= true;
5660 jump
= find_new_jump (src
, NULL
, prev_max_uid
);
5662 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
, old_seqno
);
5664 /* Only update dominator info when we don't have unreachable blocks.
5665 Otherwise we'll update in maybe_tidy_empty_bb. */
5666 if (!maybe_unreachable
)
5668 set_immediate_dominator (CDI_DOMINATORS
, to
,
5669 recompute_dominator (CDI_DOMINATORS
, to
));
5670 set_immediate_dominator (CDI_DOMINATORS
, orig_dest
,
5671 recompute_dominator (CDI_DOMINATORS
, orig_dest
));
5673 return recompute_toporder_p
;
5676 /* This variable holds the cfg hooks used by the selective scheduler. */
5677 static struct cfg_hooks sel_cfg_hooks
;
5679 /* Register sel-sched cfg hooks. */
5681 sel_register_cfg_hooks (void)
5683 sched_split_block
= sel_split_block
;
5685 orig_cfg_hooks
= get_cfg_hooks ();
5686 sel_cfg_hooks
= orig_cfg_hooks
;
5688 sel_cfg_hooks
.create_basic_block
= sel_create_basic_block
;
5690 set_cfg_hooks (sel_cfg_hooks
);
5692 sched_init_only_bb
= sel_init_only_bb
;
5693 sched_split_block
= sel_split_block
;
5694 sched_create_empty_bb
= sel_create_empty_bb
;
5697 /* Unregister sel-sched cfg hooks. */
5699 sel_unregister_cfg_hooks (void)
5701 sched_create_empty_bb
= NULL
;
5702 sched_split_block
= NULL
;
5703 sched_init_only_bb
= NULL
;
5705 set_cfg_hooks (orig_cfg_hooks
);
5709 /* Emit an insn rtx based on PATTERN. If a jump insn is wanted,
5710 LABEL is where this jump should be directed. */
5712 create_insn_rtx_from_pattern (rtx pattern
, rtx label
)
5716 gcc_assert (!INSN_P (pattern
));
5720 if (label
== NULL_RTX
)
5721 insn_rtx
= emit_insn (pattern
);
5722 else if (DEBUG_INSN_P (label
))
5723 insn_rtx
= emit_debug_insn (pattern
);
5726 insn_rtx
= emit_jump_insn (pattern
);
5727 JUMP_LABEL (insn_rtx
) = label
;
5728 ++LABEL_NUSES (label
);
5733 sched_extend_luids ();
5734 sched_extend_target ();
5735 sched_deps_init (false);
5737 /* Initialize INSN_CODE now. */
5738 recog_memoized (insn_rtx
);
5742 /* Create a new vinsn for INSN_RTX. FORCE_UNIQUE_P is true when the vinsn
5743 must not be clonable. */
5745 create_vinsn_from_insn_rtx (rtx_insn
*insn_rtx
, bool force_unique_p
)
5747 gcc_assert (INSN_P (insn_rtx
) && !INSN_IN_STREAM_P (insn_rtx
));
5749 /* If VINSN_TYPE is not USE, retain its uniqueness. */
5750 return vinsn_create (insn_rtx
, force_unique_p
);
5753 /* Create a copy of INSN_RTX. */
5755 create_copy_of_insn_rtx (rtx insn_rtx
)
5760 if (DEBUG_INSN_P (insn_rtx
))
5761 return create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx
)),
5764 gcc_assert (NONJUMP_INSN_P (insn_rtx
));
5766 res
= create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx
)),
5769 /* Locate the end of existing REG_NOTES in NEW_RTX. */
5770 rtx
*ptail
= ®_NOTES (res
);
5771 while (*ptail
!= NULL_RTX
)
5772 ptail
= &XEXP (*ptail
, 1);
5774 /* Copy all REG_NOTES except REG_EQUAL/REG_EQUIV and REG_LABEL_OPERAND
5775 since mark_jump_label will make them. REG_LABEL_TARGETs are created
5776 there too, but are supposed to be sticky, so we copy them. */
5777 for (link
= REG_NOTES (insn_rtx
); link
; link
= XEXP (link
, 1))
5778 if (REG_NOTE_KIND (link
) != REG_LABEL_OPERAND
5779 && REG_NOTE_KIND (link
) != REG_EQUAL
5780 && REG_NOTE_KIND (link
) != REG_EQUIV
)
5782 *ptail
= duplicate_reg_note (link
);
5783 ptail
= &XEXP (*ptail
, 1);
5789 /* Change vinsn field of EXPR to hold NEW_VINSN. */
5791 change_vinsn_in_expr (expr_t expr
, vinsn_t new_vinsn
)
5793 vinsn_detach (EXPR_VINSN (expr
));
5795 EXPR_VINSN (expr
) = new_vinsn
;
5796 vinsn_attach (new_vinsn
);
5799 /* Helpers for global init. */
5800 /* This structure is used to be able to call existing bundling mechanism
5801 and calculate insn priorities. */
5802 static struct haifa_sched_info sched_sel_haifa_sched_info
=
5804 NULL
, /* init_ready_list */
5805 NULL
, /* can_schedule_ready_p */
5806 NULL
, /* schedule_more_p */
5807 NULL
, /* new_ready */
5808 NULL
, /* rgn_rank */
5809 sel_print_insn
, /* rgn_print_insn */
5810 contributes_to_priority
,
5811 NULL
, /* insn_finishes_block_p */
5817 NULL
, /* add_remove_insn */
5818 NULL
, /* begin_schedule_ready */
5819 NULL
, /* begin_move_insn */
5820 NULL
, /* advance_target_bb */
5828 /* Setup special insns used in the scheduler. */
5830 setup_nop_and_exit_insns (void)
5832 gcc_assert (nop_pattern
== NULL_RTX
5833 && exit_insn
== NULL_RTX
);
5835 nop_pattern
= constm1_rtx
;
5838 emit_insn (nop_pattern
);
5839 exit_insn
= get_insns ();
5841 set_block_for_insn (exit_insn
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
5844 /* Free special insns used in the scheduler. */
5846 free_nop_and_exit_insns (void)
5849 nop_pattern
= NULL_RTX
;
5852 /* Setup a special vinsn used in new insns initialization. */
5854 setup_nop_vinsn (void)
5856 nop_vinsn
= vinsn_create (exit_insn
, false);
5857 vinsn_attach (nop_vinsn
);
5860 /* Free a special vinsn used in new insns initialization. */
5862 free_nop_vinsn (void)
5864 gcc_assert (VINSN_COUNT (nop_vinsn
) == 1);
5865 vinsn_detach (nop_vinsn
);
5869 /* Call a set_sched_flags hook. */
5871 sel_set_sched_flags (void)
5873 /* ??? This means that set_sched_flags were called, and we decided to
5874 support speculation. However, set_sched_flags also modifies flags
5875 on current_sched_info, doing this only at global init. And we
5876 sometimes change c_s_i later. So put the correct flags again. */
5877 if (spec_info
&& targetm
.sched
.set_sched_flags
)
5878 targetm
.sched
.set_sched_flags (spec_info
);
5881 /* Setup pointers to global sched info structures. */
5883 sel_setup_sched_infos (void)
5885 rgn_setup_common_sched_info ();
5887 memcpy (&sel_common_sched_info
, common_sched_info
,
5888 sizeof (sel_common_sched_info
));
5890 sel_common_sched_info
.fix_recovery_cfg
= NULL
;
5891 sel_common_sched_info
.add_block
= NULL
;
5892 sel_common_sched_info
.estimate_number_of_insns
5893 = sel_estimate_number_of_insns
;
5894 sel_common_sched_info
.luid_for_non_insn
= sel_luid_for_non_insn
;
5895 sel_common_sched_info
.sched_pass_id
= SCHED_SEL_PASS
;
5897 common_sched_info
= &sel_common_sched_info
;
5899 current_sched_info
= &sched_sel_haifa_sched_info
;
5900 current_sched_info
->sched_max_insns_priority
=
5901 get_rgn_sched_max_insns_priority ();
5903 sel_set_sched_flags ();
5907 /* Adds basic block BB to region RGN at the position *BB_ORD_INDEX,
5908 *BB_ORD_INDEX after that is increased. */
5910 sel_add_block_to_region (basic_block bb
, int *bb_ord_index
, int rgn
)
5912 RGN_NR_BLOCKS (rgn
) += 1;
5913 RGN_DONT_CALC_DEPS (rgn
) = 0;
5914 RGN_HAS_REAL_EBB (rgn
) = 0;
5915 CONTAINING_RGN (bb
->index
) = rgn
;
5916 BLOCK_TO_BB (bb
->index
) = *bb_ord_index
;
5917 rgn_bb_table
[RGN_BLOCKS (rgn
) + *bb_ord_index
] = bb
->index
;
5920 /* FIXME: it is true only when not scheduling ebbs. */
5921 RGN_BLOCKS (rgn
+ 1) = RGN_BLOCKS (rgn
) + RGN_NR_BLOCKS (rgn
);
5924 /* Functions to support pipelining of outer loops. */
5926 /* Creates a new empty region and returns it's number. */
5928 sel_create_new_region (void)
5930 int new_rgn_number
= nr_regions
;
5932 RGN_NR_BLOCKS (new_rgn_number
) = 0;
5934 /* FIXME: This will work only when EBBs are not created. */
5935 if (new_rgn_number
!= 0)
5936 RGN_BLOCKS (new_rgn_number
) = RGN_BLOCKS (new_rgn_number
- 1) +
5937 RGN_NR_BLOCKS (new_rgn_number
- 1);
5939 RGN_BLOCKS (new_rgn_number
) = 0;
5941 /* Set the blocks of the next region so the other functions may
5942 calculate the number of blocks in the region. */
5943 RGN_BLOCKS (new_rgn_number
+ 1) = RGN_BLOCKS (new_rgn_number
) +
5944 RGN_NR_BLOCKS (new_rgn_number
);
5948 return new_rgn_number
;
5951 /* If X has a smaller topological sort number than Y, returns -1;
5952 if greater, returns 1. */
5954 bb_top_order_comparator (const void *x
, const void *y
)
5956 basic_block bb1
= *(const basic_block
*) x
;
5957 basic_block bb2
= *(const basic_block
*) y
;
5959 gcc_assert (bb1
== bb2
5960 || rev_top_order_index
[bb1
->index
]
5961 != rev_top_order_index
[bb2
->index
]);
5963 /* It's a reverse topological order in REV_TOP_ORDER_INDEX, so
5964 bbs with greater number should go earlier. */
5965 if (rev_top_order_index
[bb1
->index
] > rev_top_order_index
[bb2
->index
])
5971 /* Create a region for LOOP and return its number. If we don't want
5972 to pipeline LOOP, return -1. */
5974 make_region_from_loop (struct loop
*loop
)
5977 int new_rgn_number
= -1;
5980 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5981 int bb_ord_index
= 0;
5982 basic_block
*loop_blocks
;
5983 basic_block preheader_block
;
5986 > (unsigned) PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_BLOCKS
))
5989 /* Don't pipeline loops whose latch belongs to some of its inner loops. */
5990 for (inner
= loop
->inner
; inner
; inner
= inner
->inner
)
5991 if (flow_bb_inside_loop_p (inner
, loop
->latch
))
5994 loop
->ninsns
= num_loop_insns (loop
);
5995 if ((int) loop
->ninsns
> PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_INSNS
))
5998 loop_blocks
= get_loop_body_in_custom_order (loop
, bb_top_order_comparator
);
6000 for (i
= 0; i
< loop
->num_nodes
; i
++)
6001 if (loop_blocks
[i
]->flags
& BB_IRREDUCIBLE_LOOP
)
6007 preheader_block
= loop_preheader_edge (loop
)->src
;
6008 gcc_assert (preheader_block
);
6009 gcc_assert (loop_blocks
[0] == loop
->header
);
6011 new_rgn_number
= sel_create_new_region ();
6013 sel_add_block_to_region (preheader_block
, &bb_ord_index
, new_rgn_number
);
6014 bitmap_set_bit (bbs_in_loop_rgns
, preheader_block
->index
);
6016 for (i
= 0; i
< loop
->num_nodes
; i
++)
6018 /* Add only those blocks that haven't been scheduled in the inner loop.
6019 The exception is the basic blocks with bookkeeping code - they should
6020 be added to the region (and they actually don't belong to the loop
6021 body, but to the region containing that loop body). */
6023 gcc_assert (new_rgn_number
>= 0);
6025 if (! bitmap_bit_p (bbs_in_loop_rgns
, loop_blocks
[i
]->index
))
6027 sel_add_block_to_region (loop_blocks
[i
], &bb_ord_index
,
6029 bitmap_set_bit (bbs_in_loop_rgns
, loop_blocks
[i
]->index
);
6034 MARK_LOOP_FOR_PIPELINING (loop
);
6036 return new_rgn_number
;
6039 /* Create a new region from preheader blocks LOOP_BLOCKS. */
6041 make_region_from_loop_preheader (vec
<basic_block
> *&loop_blocks
)
6044 int new_rgn_number
= -1;
6047 /* Basic block index, to be assigned to BLOCK_TO_BB. */
6048 int bb_ord_index
= 0;
6050 new_rgn_number
= sel_create_new_region ();
6052 FOR_EACH_VEC_ELT (*loop_blocks
, i
, bb
)
6054 gcc_assert (new_rgn_number
>= 0);
6056 sel_add_block_to_region (bb
, &bb_ord_index
, new_rgn_number
);
6059 vec_free (loop_blocks
);
6063 /* Create region(s) from loop nest LOOP, such that inner loops will be
6064 pipelined before outer loops. Returns true when a region for LOOP
6067 make_regions_from_loop_nest (struct loop
*loop
)
6069 struct loop
*cur_loop
;
6072 /* Traverse all inner nodes of the loop. */
6073 for (cur_loop
= loop
->inner
; cur_loop
; cur_loop
= cur_loop
->next
)
6074 if (! bitmap_bit_p (bbs_in_loop_rgns
, cur_loop
->header
->index
))
6077 /* At this moment all regular inner loops should have been pipelined.
6078 Try to create a region from this loop. */
6079 rgn_number
= make_region_from_loop (loop
);
6084 loop_nests
.safe_push (loop
);
6088 /* Initalize data structures needed. */
6090 sel_init_pipelining (void)
6092 /* Collect loop information to be used in outer loops pipelining. */
6093 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
6094 | LOOPS_HAVE_FALLTHRU_PREHEADERS
6095 | LOOPS_HAVE_RECORDED_EXITS
6096 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
);
6097 current_loop_nest
= NULL
;
6099 bbs_in_loop_rgns
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
6100 bitmap_clear (bbs_in_loop_rgns
);
6102 recompute_rev_top_order ();
6105 /* Returns a struct loop for region RGN. */
6107 get_loop_nest_for_rgn (unsigned int rgn
)
6109 /* Regions created with extend_rgns don't have corresponding loop nests,
6110 because they don't represent loops. */
6111 if (rgn
< loop_nests
.length ())
6112 return loop_nests
[rgn
];
6117 /* True when LOOP was included into pipelining regions. */
6119 considered_for_pipelining_p (struct loop
*loop
)
6121 if (loop_depth (loop
) == 0)
6124 /* Now, the loop could be too large or irreducible. Check whether its
6125 region is in LOOP_NESTS.
6126 We determine the region number of LOOP as the region number of its
6127 latch. We can't use header here, because this header could be
6128 just removed preheader and it will give us the wrong region number.
6129 Latch can't be used because it could be in the inner loop too. */
6130 if (LOOP_MARKED_FOR_PIPELINING_P (loop
))
6132 int rgn
= CONTAINING_RGN (loop
->latch
->index
);
6134 gcc_assert ((unsigned) rgn
< loop_nests
.length ());
6141 /* Makes regions from the rest of the blocks, after loops are chosen
6144 make_regions_from_the_rest (void)
6155 /* Index in rgn_bb_table where to start allocating new regions. */
6156 cur_rgn_blocks
= nr_regions
? RGN_BLOCKS (nr_regions
) : 0;
6158 /* Make regions from all the rest basic blocks - those that don't belong to
6159 any loop or belong to irreducible loops. Prepare the data structures
6162 /* LOOP_HDR[I] == -1 if I-th bb doesn't belong to any loop,
6163 LOOP_HDR[I] == LOOP_HDR[J] iff basic blocks I and J reside within the same
6165 loop_hdr
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
6166 degree
= XCNEWVEC (int, last_basic_block_for_fn (cfun
));
6169 /* For each basic block that belongs to some loop assign the number
6170 of innermost loop it belongs to. */
6171 for (i
= 0; i
< last_basic_block_for_fn (cfun
); i
++)
6174 FOR_EACH_BB_FN (bb
, cfun
)
6176 if (bb
->loop_father
&& bb
->loop_father
->num
!= 0
6177 && !(bb
->flags
& BB_IRREDUCIBLE_LOOP
))
6178 loop_hdr
[bb
->index
] = bb
->loop_father
->num
;
6181 /* For each basic block degree is calculated as the number of incoming
6182 edges, that are going out of bbs that are not yet scheduled.
6183 The basic blocks that are scheduled have degree value of zero. */
6184 FOR_EACH_BB_FN (bb
, cfun
)
6186 degree
[bb
->index
] = 0;
6188 if (!bitmap_bit_p (bbs_in_loop_rgns
, bb
->index
))
6190 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
6191 if (!bitmap_bit_p (bbs_in_loop_rgns
, e
->src
->index
))
6192 degree
[bb
->index
]++;
6195 degree
[bb
->index
] = -1;
6198 extend_rgns (degree
, &cur_rgn_blocks
, bbs_in_loop_rgns
, loop_hdr
);
6200 /* Any block that did not end up in a region is placed into a region
6202 FOR_EACH_BB_FN (bb
, cfun
)
6203 if (degree
[bb
->index
] >= 0)
6205 rgn_bb_table
[cur_rgn_blocks
] = bb
->index
;
6206 RGN_NR_BLOCKS (nr_regions
) = 1;
6207 RGN_BLOCKS (nr_regions
) = cur_rgn_blocks
++;
6208 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
6209 RGN_HAS_REAL_EBB (nr_regions
) = 0;
6210 CONTAINING_RGN (bb
->index
) = nr_regions
++;
6211 BLOCK_TO_BB (bb
->index
) = 0;
6218 /* Free data structures used in pipelining of loops. */
6219 void sel_finish_pipelining (void)
6223 /* Release aux fields so we don't free them later by mistake. */
6224 FOR_EACH_LOOP (loop
, 0)
6227 loop_optimizer_finalize ();
6229 loop_nests
.release ();
6231 free (rev_top_order_index
);
6232 rev_top_order_index
= NULL
;
6235 /* This function replaces the find_rgns when
6236 FLAG_SEL_SCHED_PIPELINING_OUTER_LOOPS is set. */
6238 sel_find_rgns (void)
6240 sel_init_pipelining ();
6247 FOR_EACH_LOOP (loop
, (flag_sel_sched_pipelining_outer_loops
6249 : LI_ONLY_INNERMOST
))
6250 make_regions_from_loop_nest (loop
);
6253 /* Make regions from all the rest basic blocks and schedule them.
6254 These blocks include blocks that don't belong to any loop or belong
6255 to irreducible loops. */
6256 make_regions_from_the_rest ();
6258 /* We don't need bbs_in_loop_rgns anymore. */
6259 sbitmap_free (bbs_in_loop_rgns
);
6260 bbs_in_loop_rgns
= NULL
;
6263 /* Add the preheader blocks from previous loop to current region taking
6264 it from LOOP_PREHEADER_BLOCKS (current_loop_nest) and record them in *BBS.
6265 This function is only used with -fsel-sched-pipelining-outer-loops. */
6267 sel_add_loop_preheaders (bb_vec_t
*bbs
)
6271 vec
<basic_block
> *preheader_blocks
6272 = LOOP_PREHEADER_BLOCKS (current_loop_nest
);
6274 if (!preheader_blocks
)
6277 for (i
= 0; preheader_blocks
->iterate (i
, &bb
); i
++)
6279 bbs
->safe_push (bb
);
6280 last_added_blocks
.safe_push (bb
);
6284 vec_free (preheader_blocks
);
6287 /* While pipelining outer loops, returns TRUE if BB is a loop preheader.
6288 Please note that the function should also work when pipelining_p is
6289 false, because it is used when deciding whether we should or should
6290 not reschedule pipelined code. */
6292 sel_is_loop_preheader_p (basic_block bb
)
6294 if (current_loop_nest
)
6298 if (preheader_removed
)
6301 /* Preheader is the first block in the region. */
6302 if (BLOCK_TO_BB (bb
->index
) == 0)
6305 /* We used to find a preheader with the topological information.
6306 Check that the above code is equivalent to what we did before. */
6308 if (in_current_region_p (current_loop_nest
->header
))
6309 gcc_assert (!(BLOCK_TO_BB (bb
->index
)
6310 < BLOCK_TO_BB (current_loop_nest
->header
->index
)));
6312 /* Support the situation when the latch block of outer loop
6313 could be from here. */
6314 for (outer
= loop_outer (current_loop_nest
);
6316 outer
= loop_outer (outer
))
6317 if (considered_for_pipelining_p (outer
) && outer
->latch
== bb
)
6324 /* Check whether JUMP_BB ends with a jump insn that leads only to DEST_BB and
6325 can be removed, making the corresponding edge fallthrough (assuming that
6326 all basic blocks between JUMP_BB and DEST_BB are empty). */
6328 bb_has_removable_jump_to_p (basic_block jump_bb
, basic_block dest_bb
)
6330 if (!onlyjump_p (BB_END (jump_bb
))
6331 || tablejump_p (BB_END (jump_bb
), NULL
, NULL
))
6334 /* Several outgoing edges, abnormal edge or destination of jump is
6336 if (EDGE_COUNT (jump_bb
->succs
) != 1
6337 || EDGE_SUCC (jump_bb
, 0)->flags
& (EDGE_ABNORMAL
| EDGE_CROSSING
)
6338 || EDGE_SUCC (jump_bb
, 0)->dest
!= dest_bb
)
6341 /* If not anything of the upper. */
6345 /* Removes the loop preheader from the current region and saves it in
6346 PREHEADER_BLOCKS of the father loop, so they will be added later to
6347 region that represents an outer loop. */
6349 sel_remove_loop_preheader (void)
6352 int cur_rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
6354 bool all_empty_p
= true;
6355 vec
<basic_block
> *preheader_blocks
6356 = LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest
));
6358 vec_check_alloc (preheader_blocks
, 0);
6360 gcc_assert (current_loop_nest
);
6361 old_len
= preheader_blocks
->length ();
6363 /* Add blocks that aren't within the current loop to PREHEADER_BLOCKS. */
6364 for (i
= 0; i
< RGN_NR_BLOCKS (cur_rgn
); i
++)
6366 bb
= BASIC_BLOCK_FOR_FN (cfun
, BB_TO_BLOCK (i
));
6368 /* If the basic block belongs to region, but doesn't belong to
6369 corresponding loop, then it should be a preheader. */
6370 if (sel_is_loop_preheader_p (bb
))
6372 preheader_blocks
->safe_push (bb
);
6373 if (BB_END (bb
) != bb_note (bb
))
6374 all_empty_p
= false;
6378 /* Remove these blocks only after iterating over the whole region. */
6379 for (i
= preheader_blocks
->length () - 1; i
>= old_len
; i
--)
6381 bb
= (*preheader_blocks
)[i
];
6382 sel_remove_bb (bb
, false);
6385 if (!considered_for_pipelining_p (loop_outer (current_loop_nest
)))
6388 /* Immediately create new region from preheader. */
6389 make_region_from_loop_preheader (preheader_blocks
);
6392 /* If all preheader blocks are empty - dont create new empty region.
6393 Instead, remove them completely. */
6394 FOR_EACH_VEC_ELT (*preheader_blocks
, i
, bb
)
6398 basic_block prev_bb
= bb
->prev_bb
, next_bb
= bb
->next_bb
;
6400 /* Redirect all incoming edges to next basic block. */
6401 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
6403 if (! (e
->flags
& EDGE_FALLTHRU
))
6404 redirect_edge_and_branch (e
, bb
->next_bb
);
6406 redirect_edge_succ (e
, bb
->next_bb
);
6408 gcc_assert (BB_NOTE_LIST (bb
) == NULL
);
6409 delete_and_free_basic_block (bb
);
6411 /* Check if after deleting preheader there is a nonconditional
6412 jump in PREV_BB that leads to the next basic block NEXT_BB.
6413 If it is so - delete this jump and clear data sets of its
6414 basic block if it becomes empty. */
6415 if (next_bb
->prev_bb
== prev_bb
6416 && prev_bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
6417 && bb_has_removable_jump_to_p (prev_bb
, next_bb
))
6419 redirect_edge_and_branch (EDGE_SUCC (prev_bb
, 0), next_bb
);
6420 if (BB_END (prev_bb
) == bb_note (prev_bb
))
6421 free_data_sets (prev_bb
);
6424 set_immediate_dominator (CDI_DOMINATORS
, next_bb
,
6425 recompute_dominator (CDI_DOMINATORS
,
6429 vec_free (preheader_blocks
);
6432 /* Store preheader within the father's loop structure. */
6433 SET_LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest
),