1 /* Instruction scheduling pass. Selective scheduler and pipeliner.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
24 #include "diagnostic-core.h"
28 #include "hard-reg-set.h"
32 #include "insn-config.h"
33 #include "insn-attr.h"
40 #include "tree-pass.h"
41 #include "sched-int.h"
45 #include "langhooks.h"
46 #include "rtlhooks-def.h"
47 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
49 #ifdef INSN_SCHEDULING
50 #include "sel-sched-ir.h"
51 /* We don't have to use it except for sel_print_insn. */
52 #include "sel-sched-dump.h"
54 /* A vector holding bb info for whole scheduling pass. */
55 VEC(sel_global_bb_info_def
, heap
) *sel_global_bb_info
= NULL
;
57 /* A vector holding bb info. */
58 VEC(sel_region_bb_info_def
, heap
) *sel_region_bb_info
= NULL
;
60 /* A pool for allocating all lists. */
61 alloc_pool sched_lists_pool
;
63 /* This contains information about successors for compute_av_set. */
64 struct succs_info current_succs
;
66 /* Data structure to describe interaction with the generic scheduler utils. */
67 static struct common_sched_info_def sel_common_sched_info
;
69 /* The loop nest being pipelined. */
70 struct loop
*current_loop_nest
;
72 /* LOOP_NESTS is a vector containing the corresponding loop nest for
74 static VEC(loop_p
, heap
) *loop_nests
= NULL
;
76 /* Saves blocks already in loop regions, indexed by bb->index. */
77 static sbitmap bbs_in_loop_rgns
= NULL
;
79 /* CFG hooks that are saved before changing create_basic_block hook. */
80 static struct cfg_hooks orig_cfg_hooks
;
83 /* Array containing reverse topological index of function basic blocks,
84 indexed by BB->INDEX. */
85 static int *rev_top_order_index
= NULL
;
87 /* Length of the above array. */
88 static int rev_top_order_index_len
= -1;
90 /* A regset pool structure. */
93 /* The stack to which regsets are returned. */
102 /* In VV we save all generated regsets so that, when destructing the
103 pool, we can compare it with V and check that every regset was returned
107 /* The pointer of VV stack. */
113 /* The difference between allocated and returned regsets. */
115 } regset_pool
= { NULL
, 0, 0, NULL
, 0, 0, 0 };
117 /* This represents the nop pool. */
120 /* The vector which holds previously emitted nops. */
128 } nop_pool
= { NULL
, 0, 0 };
130 /* The pool for basic block notes. */
131 static rtx_vec_t bb_note_pool
;
133 /* A NOP pattern used to emit placeholder insns. */
134 rtx nop_pattern
= NULL_RTX
;
135 /* A special instruction that resides in EXIT_BLOCK.
136 EXIT_INSN is successor of the insns that lead to EXIT_BLOCK. */
137 rtx exit_insn
= NULL_RTX
;
139 /* TRUE if while scheduling current region, which is loop, its preheader
141 bool preheader_removed
= false;
144 /* Forward static declarations. */
145 static void fence_clear (fence_t
);
147 static void deps_init_id (idata_t
, insn_t
, bool);
148 static void init_id_from_df (idata_t
, insn_t
, bool);
149 static expr_t
set_insn_init (expr_t
, vinsn_t
, int);
151 static void cfg_preds (basic_block
, insn_t
**, int *);
152 static void prepare_insn_expr (insn_t
, int);
153 static void free_history_vect (VEC (expr_history_def
, heap
) **);
155 static void move_bb_info (basic_block
, basic_block
);
156 static void remove_empty_bb (basic_block
, bool);
157 static void sel_merge_blocks (basic_block
, basic_block
);
158 static void sel_remove_loop_preheader (void);
160 static bool insn_is_the_only_one_in_bb_p (insn_t
);
161 static void create_initial_data_sets (basic_block
);
163 static void free_av_set (basic_block
);
164 static void invalidate_av_set (basic_block
);
165 static void extend_insn_data (void);
166 static void sel_init_new_insn (insn_t
, int);
167 static void finish_insns (void);
169 /* Various list functions. */
171 /* Copy an instruction list L. */
173 ilist_copy (ilist_t l
)
175 ilist_t head
= NULL
, *tailp
= &head
;
179 ilist_add (tailp
, ILIST_INSN (l
));
180 tailp
= &ILIST_NEXT (*tailp
);
187 /* Invert an instruction list L. */
189 ilist_invert (ilist_t l
)
195 ilist_add (&res
, ILIST_INSN (l
));
202 /* Add a new boundary to the LP list with parameters TO, PTR, and DC. */
204 blist_add (blist_t
*lp
, insn_t to
, ilist_t ptr
, deps_t dc
)
209 bnd
= BLIST_BND (*lp
);
214 BND_AV1 (bnd
) = NULL
;
218 /* Remove the list note pointed to by LP. */
220 blist_remove (blist_t
*lp
)
222 bnd_t b
= BLIST_BND (*lp
);
224 av_set_clear (&BND_AV (b
));
225 av_set_clear (&BND_AV1 (b
));
226 ilist_clear (&BND_PTR (b
));
231 /* Init a fence tail L. */
233 flist_tail_init (flist_tail_t l
)
235 FLIST_TAIL_HEAD (l
) = NULL
;
236 FLIST_TAIL_TAILP (l
) = &FLIST_TAIL_HEAD (l
);
239 /* Try to find fence corresponding to INSN in L. */
241 flist_lookup (flist_t l
, insn_t insn
)
245 if (FENCE_INSN (FLIST_FENCE (l
)) == insn
)
246 return FLIST_FENCE (l
);
254 /* Init the fields of F before running fill_insns. */
256 init_fence_for_scheduling (fence_t f
)
258 FENCE_BNDS (f
) = NULL
;
259 FENCE_PROCESSED_P (f
) = false;
260 FENCE_SCHEDULED_P (f
) = false;
263 /* Add new fence consisting of INSN and STATE to the list pointed to by LP. */
265 flist_add (flist_t
*lp
, insn_t insn
, state_t state
, deps_t dc
, void *tc
,
266 insn_t last_scheduled_insn
, VEC(rtx
,gc
) *executing_insns
,
267 int *ready_ticks
, int ready_ticks_size
, insn_t sched_next
,
268 int cycle
, int cycle_issued_insns
, int issue_more
,
269 bool starts_cycle_p
, bool after_stall_p
)
274 f
= FLIST_FENCE (*lp
);
276 FENCE_INSN (f
) = insn
;
278 gcc_assert (state
!= NULL
);
279 FENCE_STATE (f
) = state
;
281 FENCE_CYCLE (f
) = cycle
;
282 FENCE_ISSUED_INSNS (f
) = cycle_issued_insns
;
283 FENCE_STARTS_CYCLE_P (f
) = starts_cycle_p
;
284 FENCE_AFTER_STALL_P (f
) = after_stall_p
;
286 gcc_assert (dc
!= NULL
);
289 gcc_assert (tc
!= NULL
|| targetm
.sched
.alloc_sched_context
== NULL
);
292 FENCE_LAST_SCHEDULED_INSN (f
) = last_scheduled_insn
;
293 FENCE_ISSUE_MORE (f
) = issue_more
;
294 FENCE_EXECUTING_INSNS (f
) = executing_insns
;
295 FENCE_READY_TICKS (f
) = ready_ticks
;
296 FENCE_READY_TICKS_SIZE (f
) = ready_ticks_size
;
297 FENCE_SCHED_NEXT (f
) = sched_next
;
299 init_fence_for_scheduling (f
);
302 /* Remove the head node of the list pointed to by LP. */
304 flist_remove (flist_t
*lp
)
306 if (FENCE_INSN (FLIST_FENCE (*lp
)))
307 fence_clear (FLIST_FENCE (*lp
));
311 /* Clear the fence list pointed to by LP. */
313 flist_clear (flist_t
*lp
)
319 /* Add ORIGINAL_INSN the def list DL honoring CROSSES_CALL. */
321 def_list_add (def_list_t
*dl
, insn_t original_insn
, bool crosses_call
)
326 d
= DEF_LIST_DEF (*dl
);
328 d
->orig_insn
= original_insn
;
329 d
->crosses_call
= crosses_call
;
333 /* Functions to work with target contexts. */
335 /* Bulk target context. It is convenient for debugging purposes to ensure
336 that there are no uninitialized (null) target contexts. */
337 static tc_t bulk_tc
= (tc_t
) 1;
339 /* Target hooks wrappers. In the future we can provide some default
340 implementations for them. */
342 /* Allocate a store for the target context. */
344 alloc_target_context (void)
346 return (targetm
.sched
.alloc_sched_context
347 ? targetm
.sched
.alloc_sched_context () : bulk_tc
);
350 /* Init target context TC.
351 If CLEAN_P is true, then make TC as it is beginning of the scheduler.
352 Overwise, copy current backend context to TC. */
354 init_target_context (tc_t tc
, bool clean_p
)
356 if (targetm
.sched
.init_sched_context
)
357 targetm
.sched
.init_sched_context (tc
, clean_p
);
360 /* Allocate and initialize a target context. Meaning of CLEAN_P is the same as
361 int init_target_context (). */
363 create_target_context (bool clean_p
)
365 tc_t tc
= alloc_target_context ();
367 init_target_context (tc
, clean_p
);
371 /* Copy TC to the current backend context. */
373 set_target_context (tc_t tc
)
375 if (targetm
.sched
.set_sched_context
)
376 targetm
.sched
.set_sched_context (tc
);
379 /* TC is about to be destroyed. Free any internal data. */
381 clear_target_context (tc_t tc
)
383 if (targetm
.sched
.clear_sched_context
)
384 targetm
.sched
.clear_sched_context (tc
);
387 /* Clear and free it. */
389 delete_target_context (tc_t tc
)
391 clear_target_context (tc
);
393 if (targetm
.sched
.free_sched_context
)
394 targetm
.sched
.free_sched_context (tc
);
397 /* Make a copy of FROM in TO.
398 NB: May be this should be a hook. */
400 copy_target_context (tc_t to
, tc_t from
)
402 tc_t tmp
= create_target_context (false);
404 set_target_context (from
);
405 init_target_context (to
, false);
407 set_target_context (tmp
);
408 delete_target_context (tmp
);
411 /* Create a copy of TC. */
413 create_copy_of_target_context (tc_t tc
)
415 tc_t copy
= alloc_target_context ();
417 copy_target_context (copy
, tc
);
422 /* Clear TC and initialize it according to CLEAN_P. The meaning of CLEAN_P
423 is the same as in init_target_context (). */
425 reset_target_context (tc_t tc
, bool clean_p
)
427 clear_target_context (tc
);
428 init_target_context (tc
, clean_p
);
431 /* Functions to work with dependence contexts.
432 Dc (aka deps context, aka deps_t, aka struct deps_desc *) is short for dependence
433 context. It accumulates information about processed insns to decide if
434 current insn is dependent on the processed ones. */
436 /* Make a copy of FROM in TO. */
438 copy_deps_context (deps_t to
, deps_t from
)
440 init_deps (to
, false);
441 deps_join (to
, from
);
444 /* Allocate store for dep context. */
446 alloc_deps_context (void)
448 return XNEW (struct deps_desc
);
451 /* Allocate and initialize dep context. */
453 create_deps_context (void)
455 deps_t dc
= alloc_deps_context ();
457 init_deps (dc
, false);
461 /* Create a copy of FROM. */
463 create_copy_of_deps_context (deps_t from
)
465 deps_t to
= alloc_deps_context ();
467 copy_deps_context (to
, from
);
471 /* Clean up internal data of DC. */
473 clear_deps_context (deps_t dc
)
478 /* Clear and free DC. */
480 delete_deps_context (deps_t dc
)
482 clear_deps_context (dc
);
486 /* Clear and init DC. */
488 reset_deps_context (deps_t dc
)
490 clear_deps_context (dc
);
491 init_deps (dc
, false);
494 /* This structure describes the dependence analysis hooks for advancing
495 dependence context. */
496 static struct sched_deps_info_def advance_deps_context_sched_deps_info
=
500 NULL
, /* start_insn */
501 NULL
, /* finish_insn */
502 NULL
, /* start_lhs */
503 NULL
, /* finish_lhs */
504 NULL
, /* start_rhs */
505 NULL
, /* finish_rhs */
507 haifa_note_reg_clobber
,
509 NULL
, /* note_mem_dep */
515 /* Process INSN and add its impact on DC. */
517 advance_deps_context (deps_t dc
, insn_t insn
)
519 sched_deps_info
= &advance_deps_context_sched_deps_info
;
520 deps_analyze_insn (dc
, insn
);
524 /* Functions to work with DFA states. */
526 /* Allocate store for a DFA state. */
530 return xmalloc (dfa_state_size
);
533 /* Allocate and initialize DFA state. */
537 state_t state
= state_alloc ();
540 advance_state (state
);
544 /* Free DFA state. */
546 state_free (state_t state
)
551 /* Make a copy of FROM in TO. */
553 state_copy (state_t to
, state_t from
)
555 memcpy (to
, from
, dfa_state_size
);
558 /* Create a copy of FROM. */
560 state_create_copy (state_t from
)
562 state_t to
= state_alloc ();
564 state_copy (to
, from
);
569 /* Functions to work with fences. */
571 /* Clear the fence. */
573 fence_clear (fence_t f
)
575 state_t s
= FENCE_STATE (f
);
576 deps_t dc
= FENCE_DC (f
);
577 void *tc
= FENCE_TC (f
);
579 ilist_clear (&FENCE_BNDS (f
));
581 gcc_assert ((s
!= NULL
&& dc
!= NULL
&& tc
!= NULL
)
582 || (s
== NULL
&& dc
== NULL
&& tc
== NULL
));
588 delete_deps_context (dc
);
591 delete_target_context (tc
);
592 VEC_free (rtx
, gc
, FENCE_EXECUTING_INSNS (f
));
593 free (FENCE_READY_TICKS (f
));
594 FENCE_READY_TICKS (f
) = NULL
;
597 /* Init a list of fences with successors of OLD_FENCE. */
599 init_fences (insn_t old_fence
)
604 int ready_ticks_size
= get_max_uid () + 1;
606 FOR_EACH_SUCC_1 (succ
, si
, old_fence
,
607 SUCCS_NORMAL
| SUCCS_SKIP_TO_LOOP_EXITS
)
613 gcc_assert (flag_sel_sched_pipelining_outer_loops
);
615 flist_add (&fences
, succ
,
617 create_deps_context () /* dc */,
618 create_target_context (true) /* tc */,
619 NULL_RTX
/* last_scheduled_insn */,
620 NULL
, /* executing_insns */
621 XCNEWVEC (int, ready_ticks_size
), /* ready_ticks */
623 NULL_RTX
/* sched_next */,
624 1 /* cycle */, 0 /* cycle_issued_insns */,
625 issue_rate
, /* issue_more */
626 1 /* starts_cycle_p */, 0 /* after_stall_p */);
630 /* Merges two fences (filling fields of fence F with resulting values) by
631 following rules: 1) state, target context and last scheduled insn are
632 propagated from fallthrough edge if it is available;
633 2) deps context and cycle is propagated from more probable edge;
634 3) all other fields are set to corresponding constant values.
636 INSN, STATE, DC, TC, LAST_SCHEDULED_INSN, EXECUTING_INSNS,
637 READY_TICKS, READY_TICKS_SIZE, SCHED_NEXT, CYCLE, ISSUE_MORE
638 and AFTER_STALL_P are the corresponding fields of the second fence. */
640 merge_fences (fence_t f
, insn_t insn
,
641 state_t state
, deps_t dc
, void *tc
,
642 rtx last_scheduled_insn
, VEC(rtx
, gc
) *executing_insns
,
643 int *ready_ticks
, int ready_ticks_size
,
644 rtx sched_next
, int cycle
, int issue_more
, bool after_stall_p
)
646 insn_t last_scheduled_insn_old
= FENCE_LAST_SCHEDULED_INSN (f
);
648 gcc_assert (sel_bb_head_p (FENCE_INSN (f
))
649 && !sched_next
&& !FENCE_SCHED_NEXT (f
));
651 /* Check if we can decide which path fences came.
652 If we can't (or don't want to) - reset all. */
653 if (last_scheduled_insn
== NULL
654 || last_scheduled_insn_old
== NULL
655 /* This is a case when INSN is reachable on several paths from
656 one insn (this can happen when pipelining of outer loops is on and
657 there are two edges: one going around of inner loop and the other -
658 right through it; in such case just reset everything). */
659 || last_scheduled_insn
== last_scheduled_insn_old
)
661 state_reset (FENCE_STATE (f
));
664 reset_deps_context (FENCE_DC (f
));
665 delete_deps_context (dc
);
667 reset_target_context (FENCE_TC (f
), true);
668 delete_target_context (tc
);
670 if (cycle
> FENCE_CYCLE (f
))
671 FENCE_CYCLE (f
) = cycle
;
673 FENCE_LAST_SCHEDULED_INSN (f
) = NULL
;
674 FENCE_ISSUE_MORE (f
) = issue_rate
;
675 VEC_free (rtx
, gc
, executing_insns
);
677 if (FENCE_EXECUTING_INSNS (f
))
678 VEC_block_remove (rtx
, FENCE_EXECUTING_INSNS (f
), 0,
679 VEC_length (rtx
, FENCE_EXECUTING_INSNS (f
)));
680 if (FENCE_READY_TICKS (f
))
681 memset (FENCE_READY_TICKS (f
), 0, FENCE_READY_TICKS_SIZE (f
));
685 edge edge_old
= NULL
, edge_new
= NULL
;
690 /* Find fallthrough edge. */
691 gcc_assert (BLOCK_FOR_INSN (insn
)->prev_bb
);
692 candidate
= find_fallthru_edge_from (BLOCK_FOR_INSN (insn
)->prev_bb
);
695 || (candidate
->src
!= BLOCK_FOR_INSN (last_scheduled_insn
)
696 && candidate
->src
!= BLOCK_FOR_INSN (last_scheduled_insn_old
)))
698 /* No fallthrough edge leading to basic block of INSN. */
699 state_reset (FENCE_STATE (f
));
702 reset_target_context (FENCE_TC (f
), true);
703 delete_target_context (tc
);
705 FENCE_LAST_SCHEDULED_INSN (f
) = NULL
;
706 FENCE_ISSUE_MORE (f
) = issue_rate
;
709 if (candidate
->src
== BLOCK_FOR_INSN (last_scheduled_insn
))
711 /* Would be weird if same insn is successor of several fallthrough
713 gcc_assert (BLOCK_FOR_INSN (insn
)->prev_bb
714 != BLOCK_FOR_INSN (last_scheduled_insn_old
));
716 state_free (FENCE_STATE (f
));
717 FENCE_STATE (f
) = state
;
719 delete_target_context (FENCE_TC (f
));
722 FENCE_LAST_SCHEDULED_INSN (f
) = last_scheduled_insn
;
723 FENCE_ISSUE_MORE (f
) = issue_more
;
727 /* Leave STATE, TC and LAST_SCHEDULED_INSN fields untouched. */
729 delete_target_context (tc
);
731 gcc_assert (BLOCK_FOR_INSN (insn
)->prev_bb
732 != BLOCK_FOR_INSN (last_scheduled_insn
));
735 /* Find edge of first predecessor (last_scheduled_insn_old->insn). */
736 FOR_EACH_SUCC_1 (succ
, si
, last_scheduled_insn_old
,
737 SUCCS_NORMAL
| SUCCS_SKIP_TO_LOOP_EXITS
)
741 /* No same successor allowed from several edges. */
742 gcc_assert (!edge_old
);
746 /* Find edge of second predecessor (last_scheduled_insn->insn). */
747 FOR_EACH_SUCC_1 (succ
, si
, last_scheduled_insn
,
748 SUCCS_NORMAL
| SUCCS_SKIP_TO_LOOP_EXITS
)
752 /* No same successor allowed from several edges. */
753 gcc_assert (!edge_new
);
758 /* Check if we can choose most probable predecessor. */
759 if (edge_old
== NULL
|| edge_new
== NULL
)
761 reset_deps_context (FENCE_DC (f
));
762 delete_deps_context (dc
);
763 VEC_free (rtx
, gc
, executing_insns
);
766 FENCE_CYCLE (f
) = MAX (FENCE_CYCLE (f
), cycle
);
767 if (FENCE_EXECUTING_INSNS (f
))
768 VEC_block_remove (rtx
, FENCE_EXECUTING_INSNS (f
), 0,
769 VEC_length (rtx
, FENCE_EXECUTING_INSNS (f
)));
770 if (FENCE_READY_TICKS (f
))
771 memset (FENCE_READY_TICKS (f
), 0, FENCE_READY_TICKS_SIZE (f
));
774 if (edge_new
->probability
> edge_old
->probability
)
776 delete_deps_context (FENCE_DC (f
));
778 VEC_free (rtx
, gc
, FENCE_EXECUTING_INSNS (f
));
779 FENCE_EXECUTING_INSNS (f
) = executing_insns
;
780 free (FENCE_READY_TICKS (f
));
781 FENCE_READY_TICKS (f
) = ready_ticks
;
782 FENCE_READY_TICKS_SIZE (f
) = ready_ticks_size
;
783 FENCE_CYCLE (f
) = cycle
;
787 /* Leave DC and CYCLE untouched. */
788 delete_deps_context (dc
);
789 VEC_free (rtx
, gc
, executing_insns
);
794 /* Fill remaining invariant fields. */
796 FENCE_AFTER_STALL_P (f
) = 1;
798 FENCE_ISSUED_INSNS (f
) = 0;
799 FENCE_STARTS_CYCLE_P (f
) = 1;
800 FENCE_SCHED_NEXT (f
) = NULL
;
803 /* Add a new fence to NEW_FENCES list, initializing it from all
806 add_to_fences (flist_tail_t new_fences
, insn_t insn
,
807 state_t state
, deps_t dc
, void *tc
, rtx last_scheduled_insn
,
808 VEC(rtx
, gc
) *executing_insns
, int *ready_ticks
,
809 int ready_ticks_size
, rtx sched_next
, int cycle
,
810 int cycle_issued_insns
, int issue_rate
,
811 bool starts_cycle_p
, bool after_stall_p
)
813 fence_t f
= flist_lookup (FLIST_TAIL_HEAD (new_fences
), insn
);
817 flist_add (FLIST_TAIL_TAILP (new_fences
), insn
, state
, dc
, tc
,
818 last_scheduled_insn
, executing_insns
, ready_ticks
,
819 ready_ticks_size
, sched_next
, cycle
, cycle_issued_insns
,
820 issue_rate
, starts_cycle_p
, after_stall_p
);
822 FLIST_TAIL_TAILP (new_fences
)
823 = &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences
));
827 merge_fences (f
, insn
, state
, dc
, tc
, last_scheduled_insn
,
828 executing_insns
, ready_ticks
, ready_ticks_size
,
829 sched_next
, cycle
, issue_rate
, after_stall_p
);
833 /* Move the first fence in the OLD_FENCES list to NEW_FENCES. */
835 move_fence_to_fences (flist_t old_fences
, flist_tail_t new_fences
)
838 flist_t
*tailp
= FLIST_TAIL_TAILP (new_fences
);
840 old
= FLIST_FENCE (old_fences
);
841 f
= flist_lookup (FLIST_TAIL_HEAD (new_fences
),
842 FENCE_INSN (FLIST_FENCE (old_fences
)));
845 merge_fences (f
, old
->insn
, old
->state
, old
->dc
, old
->tc
,
846 old
->last_scheduled_insn
, old
->executing_insns
,
847 old
->ready_ticks
, old
->ready_ticks_size
,
848 old
->sched_next
, old
->cycle
, old
->issue_more
,
854 FLIST_TAIL_TAILP (new_fences
) = &FLIST_NEXT (*tailp
);
855 *FLIST_FENCE (*tailp
) = *old
;
856 init_fence_for_scheduling (FLIST_FENCE (*tailp
));
858 FENCE_INSN (old
) = NULL
;
861 /* Add a new fence to NEW_FENCES list and initialize most of its data
864 add_clean_fence_to_fences (flist_tail_t new_fences
, insn_t succ
, fence_t fence
)
866 int ready_ticks_size
= get_max_uid () + 1;
868 add_to_fences (new_fences
,
869 succ
, state_create (), create_deps_context (),
870 create_target_context (true),
872 XCNEWVEC (int, ready_ticks_size
), ready_ticks_size
,
873 NULL_RTX
, FENCE_CYCLE (fence
) + 1,
874 0, issue_rate
, 1, FENCE_AFTER_STALL_P (fence
));
877 /* Add a new fence to NEW_FENCES list and initialize all of its data
878 from FENCE and SUCC. */
880 add_dirty_fence_to_fences (flist_tail_t new_fences
, insn_t succ
, fence_t fence
)
882 int * new_ready_ticks
883 = XNEWVEC (int, FENCE_READY_TICKS_SIZE (fence
));
885 memcpy (new_ready_ticks
, FENCE_READY_TICKS (fence
),
886 FENCE_READY_TICKS_SIZE (fence
) * sizeof (int));
887 add_to_fences (new_fences
,
888 succ
, state_create_copy (FENCE_STATE (fence
)),
889 create_copy_of_deps_context (FENCE_DC (fence
)),
890 create_copy_of_target_context (FENCE_TC (fence
)),
891 FENCE_LAST_SCHEDULED_INSN (fence
),
892 VEC_copy (rtx
, gc
, FENCE_EXECUTING_INSNS (fence
)),
894 FENCE_READY_TICKS_SIZE (fence
),
895 FENCE_SCHED_NEXT (fence
),
897 FENCE_ISSUED_INSNS (fence
),
898 FENCE_ISSUE_MORE (fence
),
899 FENCE_STARTS_CYCLE_P (fence
),
900 FENCE_AFTER_STALL_P (fence
));
904 /* Functions to work with regset and nop pools. */
906 /* Returns the new regset from pool. It might have some of the bits set
907 from the previous usage. */
909 get_regset_from_pool (void)
913 if (regset_pool
.n
!= 0)
914 rs
= regset_pool
.v
[--regset_pool
.n
];
916 /* We need to create the regset. */
918 rs
= ALLOC_REG_SET (®_obstack
);
920 if (regset_pool
.nn
== regset_pool
.ss
)
921 regset_pool
.vv
= XRESIZEVEC (regset
, regset_pool
.vv
,
922 (regset_pool
.ss
= 2 * regset_pool
.ss
+ 1));
923 regset_pool
.vv
[regset_pool
.nn
++] = rs
;
931 /* Same as above, but returns the empty regset. */
933 get_clear_regset_from_pool (void)
935 regset rs
= get_regset_from_pool ();
941 /* Return regset RS to the pool for future use. */
943 return_regset_to_pool (regset rs
)
947 if (regset_pool
.n
== regset_pool
.s
)
948 regset_pool
.v
= XRESIZEVEC (regset
, regset_pool
.v
,
949 (regset_pool
.s
= 2 * regset_pool
.s
+ 1));
950 regset_pool
.v
[regset_pool
.n
++] = rs
;
953 #ifdef ENABLE_CHECKING
954 /* This is used as a qsort callback for sorting regset pool stacks.
955 X and XX are addresses of two regsets. They are never equal. */
957 cmp_v_in_regset_pool (const void *x
, const void *xx
)
959 return *((const regset
*) x
) - *((const regset
*) xx
);
963 /* Free the regset pool possibly checking for memory leaks. */
965 free_regset_pool (void)
967 #ifdef ENABLE_CHECKING
969 regset
*v
= regset_pool
.v
;
971 int n
= regset_pool
.n
;
973 regset
*vv
= regset_pool
.vv
;
975 int nn
= regset_pool
.nn
;
979 gcc_assert (n
<= nn
);
981 /* Sort both vectors so it will be possible to compare them. */
982 qsort (v
, n
, sizeof (*v
), cmp_v_in_regset_pool
);
983 qsort (vv
, nn
, sizeof (*vv
), cmp_v_in_regset_pool
);
990 /* VV[II] was lost. */
996 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
)
1035 bool old_p
= nop_pool
.n
!= 0;
1039 nop
= nop_pool
.v
[--nop_pool
.n
];
1043 nop
= emit_insn_before (nop
, insn
);
1046 flags
= INSN_INIT_TODO_SSID
;
1048 flags
= INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SSID
;
1050 set_insn_init (INSN_EXPR (insn
), nop_vinsn
, INSN_SEQNO (insn
));
1051 sel_init_new_insn (nop
, flags
);
1056 /* Remove NOP from the instruction stream and return it to the pool. */
1058 return_nop_to_pool (insn_t nop
, bool full_tidying
)
1060 gcc_assert (INSN_IN_STREAM_P (nop
));
1061 sel_remove_insn (nop
, false, full_tidying
);
1063 if (nop_pool
.n
== nop_pool
.s
)
1064 nop_pool
.v
= XRESIZEVEC (rtx
, nop_pool
.v
,
1065 (nop_pool
.s
= 2 * nop_pool
.s
+ 1));
1066 nop_pool
.v
[nop_pool
.n
++] = nop
;
1069 /* Free the nop pool. */
1071 free_nop_pool (void)
1080 /* Skip unspec to support ia64 speculation. Called from rtx_equal_p_cb.
1081 The callback is given two rtxes XX and YY and writes the new rtxes
1082 to NX and NY in case some needs to be skipped. */
1084 skip_unspecs_callback (const_rtx
*xx
, const_rtx
*yy
, rtx
*nx
, rtx
* ny
)
1089 if (GET_CODE (x
) == UNSPEC
1090 && (targetm
.sched
.skip_rtx_p
== NULL
1091 || targetm
.sched
.skip_rtx_p (x
)))
1093 *nx
= XVECEXP (x
, 0, 0);
1094 *ny
= CONST_CAST_RTX (y
);
1098 if (GET_CODE (y
) == UNSPEC
1099 && (targetm
.sched
.skip_rtx_p
== NULL
1100 || targetm
.sched
.skip_rtx_p (y
)))
1102 *nx
= CONST_CAST_RTX (x
);
1103 *ny
= XVECEXP (y
, 0, 0);
1110 /* Callback, called from hash_rtx_cb. Helps to hash UNSPEC rtx X in a correct way
1111 to support ia64 speculation. When changes are needed, new rtx X and new mode
1112 NMODE are written, and the callback returns true. */
1114 hash_with_unspec_callback (const_rtx x
, enum machine_mode mode ATTRIBUTE_UNUSED
,
1115 rtx
*nx
, enum machine_mode
* nmode
)
1117 if (GET_CODE (x
) == UNSPEC
1118 && targetm
.sched
.skip_rtx_p
1119 && targetm
.sched
.skip_rtx_p (x
))
1121 *nx
= XVECEXP (x
, 0 ,0);
1129 /* Returns LHS and RHS are ok to be scheduled separately. */
1131 lhs_and_rhs_separable_p (rtx lhs
, rtx rhs
)
1133 if (lhs
== NULL
|| rhs
== NULL
)
1136 /* Do not schedule CONST, CONST_INT and CONST_DOUBLE etc as rhs: no point
1137 to use reg, if const can be used. Moreover, scheduling const as rhs may
1138 lead to mode mismatch cause consts don't have modes but they could be
1139 merged from branches where the same const used in different modes. */
1140 if (CONSTANT_P (rhs
))
1143 /* ??? Do not rename predicate registers to avoid ICEs in bundling. */
1144 if (COMPARISON_P (rhs
))
1147 /* Do not allow single REG to be an rhs. */
1151 /* See comment at find_used_regs_1 (*1) for explanation of this
1153 /* FIXME: remove this later. */
1157 /* This will filter all tricky things like ZERO_EXTRACT etc.
1158 For now we don't handle it. */
1159 if (!REG_P (lhs
) && !MEM_P (lhs
))
1165 /* Initialize vinsn VI for INSN. Only for use from vinsn_create (). When
1166 FORCE_UNIQUE_P is true, the resulting vinsn will not be clonable. This is
1167 used e.g. for insns from recovery blocks. */
1169 vinsn_init (vinsn_t vi
, insn_t insn
, bool force_unique_p
)
1171 hash_rtx_callback_function hrcf
;
1174 VINSN_INSN_RTX (vi
) = insn
;
1175 VINSN_COUNT (vi
) = 0;
1178 if (DF_INSN_UID_SAFE_GET (INSN_UID (insn
)) != NULL
)
1179 init_id_from_df (VINSN_ID (vi
), insn
, force_unique_p
);
1181 deps_init_id (VINSN_ID (vi
), insn
, force_unique_p
);
1183 /* Hash vinsn depending on whether it is separable or not. */
1184 hrcf
= targetm
.sched
.skip_rtx_p
? hash_with_unspec_callback
: NULL
;
1185 if (VINSN_SEPARABLE_P (vi
))
1187 rtx rhs
= VINSN_RHS (vi
);
1189 VINSN_HASH (vi
) = hash_rtx_cb (rhs
, GET_MODE (rhs
),
1190 NULL
, NULL
, false, hrcf
);
1191 VINSN_HASH_RTX (vi
) = hash_rtx_cb (VINSN_PATTERN (vi
),
1192 VOIDmode
, NULL
, NULL
,
1197 VINSN_HASH (vi
) = hash_rtx_cb (VINSN_PATTERN (vi
), VOIDmode
,
1198 NULL
, NULL
, false, hrcf
);
1199 VINSN_HASH_RTX (vi
) = VINSN_HASH (vi
);
1202 insn_class
= haifa_classify_insn (insn
);
1204 && (!targetm
.sched
.get_insn_spec_ds
1205 || ((targetm
.sched
.get_insn_spec_ds (insn
) & BEGIN_CONTROL
)
1207 VINSN_MAY_TRAP_P (vi
) = true;
1209 VINSN_MAY_TRAP_P (vi
) = false;
1212 /* Indicate that VI has become the part of an rtx object. */
1214 vinsn_attach (vinsn_t vi
)
1216 /* Assert that VI is not pending for deletion. */
1217 gcc_assert (VINSN_INSN_RTX (vi
));
1222 /* Create and init VI from the INSN. Use UNIQUE_P for determining the correct
1225 vinsn_create (insn_t insn
, bool force_unique_p
)
1227 vinsn_t vi
= XCNEW (struct vinsn_def
);
1229 vinsn_init (vi
, insn
, force_unique_p
);
1233 /* Return a copy of VI. When REATTACH_P is true, detach VI and attach
1236 vinsn_copy (vinsn_t vi
, bool reattach_p
)
1239 bool unique
= VINSN_UNIQUE_P (vi
);
1242 copy
= create_copy_of_insn_rtx (VINSN_INSN_RTX (vi
));
1243 new_vi
= create_vinsn_from_insn_rtx (copy
, unique
);
1247 vinsn_attach (new_vi
);
1253 /* Delete the VI vinsn and free its data. */
1255 vinsn_delete (vinsn_t vi
)
1257 gcc_assert (VINSN_COUNT (vi
) == 0);
1259 return_regset_to_pool (VINSN_REG_SETS (vi
));
1260 return_regset_to_pool (VINSN_REG_USES (vi
));
1261 return_regset_to_pool (VINSN_REG_CLOBBERS (vi
));
1266 /* Indicate that VI is no longer a part of some rtx object.
1267 Remove VI if it is no longer needed. */
1269 vinsn_detach (vinsn_t vi
)
1271 gcc_assert (VINSN_COUNT (vi
) > 0);
1273 if (--VINSN_COUNT (vi
) == 0)
1277 /* Returns TRUE if VI is a branch. */
1279 vinsn_cond_branch_p (vinsn_t vi
)
1283 if (!VINSN_UNIQUE_P (vi
))
1286 insn
= VINSN_INSN_RTX (vi
);
1287 if (BB_END (BLOCK_FOR_INSN (insn
)) != insn
)
1290 return control_flow_insn_p (insn
);
1293 /* Return latency of INSN. */
1295 sel_insn_rtx_cost (rtx insn
)
1299 /* A USE insn, or something else we don't need to
1300 understand. We can't pass these directly to
1301 result_ready_cost or insn_default_latency because it will
1302 trigger a fatal error for unrecognizable insns. */
1303 if (recog_memoized (insn
) < 0)
1307 cost
= insn_default_latency (insn
);
1316 /* Return the cost of the VI.
1317 !!! FIXME: Unify with haifa-sched.c: insn_cost (). */
1319 sel_vinsn_cost (vinsn_t vi
)
1321 int cost
= vi
->cost
;
1325 cost
= sel_insn_rtx_cost (VINSN_INSN_RTX (vi
));
1333 /* Functions for insn emitting. */
1335 /* Emit new insn after AFTER based on PATTERN and initialize its data from
1338 sel_gen_insn_from_rtx_after (rtx pattern
, expr_t expr
, int seqno
, insn_t after
)
1342 gcc_assert (EXPR_TARGET_AVAILABLE (expr
) == true);
1344 new_insn
= emit_insn_after (pattern
, after
);
1345 set_insn_init (expr
, NULL
, seqno
);
1346 sel_init_new_insn (new_insn
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SSID
);
1351 /* Force newly generated vinsns to be unique. */
1352 static bool init_insn_force_unique_p
= false;
1354 /* Emit new speculation recovery insn after AFTER based on PATTERN and
1355 initialize its data from EXPR and SEQNO. */
1357 sel_gen_recovery_insn_from_rtx_after (rtx pattern
, expr_t expr
, int seqno
,
1362 gcc_assert (!init_insn_force_unique_p
);
1364 init_insn_force_unique_p
= true;
1365 insn
= sel_gen_insn_from_rtx_after (pattern
, expr
, seqno
, after
);
1366 CANT_MOVE (insn
) = 1;
1367 init_insn_force_unique_p
= false;
1372 /* Emit new insn after AFTER based on EXPR and SEQNO. If VINSN is not NULL,
1373 take it as a new vinsn instead of EXPR's vinsn.
1374 We simplify insns later, after scheduling region in
1375 simplify_changed_insns. */
1377 sel_gen_insn_from_expr_after (expr_t expr
, vinsn_t vinsn
, int seqno
,
1384 emit_expr
= set_insn_init (expr
, vinsn
? vinsn
: EXPR_VINSN (expr
),
1386 insn
= EXPR_INSN_RTX (emit_expr
);
1387 add_insn_after (insn
, after
, BLOCK_FOR_INSN (insn
));
1389 flags
= INSN_INIT_TODO_SSID
;
1390 if (INSN_LUID (insn
) == 0)
1391 flags
|= INSN_INIT_TODO_LUID
;
1392 sel_init_new_insn (insn
, flags
);
1397 /* Move insn from EXPR after AFTER. */
1399 sel_move_insn (expr_t expr
, int seqno
, insn_t after
)
1401 insn_t insn
= EXPR_INSN_RTX (expr
);
1402 basic_block bb
= BLOCK_FOR_INSN (after
);
1403 insn_t next
= NEXT_INSN (after
);
1405 /* Assert that in move_op we disconnected this insn properly. */
1406 gcc_assert (EXPR_VINSN (INSN_EXPR (insn
)) != NULL
);
1407 PREV_INSN (insn
) = after
;
1408 NEXT_INSN (insn
) = next
;
1410 NEXT_INSN (after
) = insn
;
1411 PREV_INSN (next
) = insn
;
1413 /* Update links from insn to bb and vice versa. */
1414 df_insn_change_bb (insn
, bb
);
1415 if (BB_END (bb
) == after
)
1418 prepare_insn_expr (insn
, seqno
);
1423 /* Functions to work with right-hand sides. */
1425 /* Search for a hash value determined by UID/NEW_VINSN in a sorted vector
1426 VECT and return true when found. Use NEW_VINSN for comparison only when
1427 COMPARE_VINSNS is true. Write to INDP the index on which
1428 the search has stopped, such that inserting the new element at INDP will
1429 retain VECT's sort order. */
1431 find_in_history_vect_1 (VEC(expr_history_def
, heap
) *vect
,
1432 unsigned uid
, vinsn_t new_vinsn
,
1433 bool compare_vinsns
, int *indp
)
1435 expr_history_def
*arr
;
1436 int i
, j
, len
= VEC_length (expr_history_def
, vect
);
1444 arr
= VEC_address (expr_history_def
, vect
);
1449 unsigned auid
= arr
[i
].uid
;
1450 vinsn_t avinsn
= arr
[i
].new_expr_vinsn
;
1453 /* When undoing transformation on a bookkeeping copy, the new vinsn
1454 may not be exactly equal to the one that is saved in the vector.
1455 This is because the insn whose copy we're checking was possibly
1456 substituted itself. */
1457 && (! compare_vinsns
1458 || vinsn_equal_p (avinsn
, new_vinsn
)))
1463 else if (auid
> uid
)
1472 /* Search for a uid of INSN and NEW_VINSN in a sorted vector VECT. Return
1473 the position found or -1, if no such value is in vector.
1474 Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */
1476 find_in_history_vect (VEC(expr_history_def
, heap
) *vect
, rtx insn
,
1477 vinsn_t new_vinsn
, bool originators_p
)
1481 if (find_in_history_vect_1 (vect
, INSN_UID (insn
), new_vinsn
,
1485 if (INSN_ORIGINATORS (insn
) && originators_p
)
1490 EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn
), 0, uid
, bi
)
1491 if (find_in_history_vect_1 (vect
, uid
, new_vinsn
, false, &ind
))
1498 /* Insert new element in a sorted history vector pointed to by PVECT,
1499 if it is not there already. The element is searched using
1500 UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN and SPEC_DS save
1501 the history of a transformation. */
1503 insert_in_history_vect (VEC (expr_history_def
, heap
) **pvect
,
1504 unsigned uid
, enum local_trans_type type
,
1505 vinsn_t old_expr_vinsn
, vinsn_t new_expr_vinsn
,
1508 VEC(expr_history_def
, heap
) *vect
= *pvect
;
1509 expr_history_def temp
;
1513 res
= find_in_history_vect_1 (vect
, uid
, new_expr_vinsn
, true, &ind
);
1517 expr_history_def
*phist
= VEC_index (expr_history_def
, vect
, ind
);
1519 /* It is possible that speculation types of expressions that were
1520 propagated through different paths will be different here. In this
1521 case, merge the status to get the correct check later. */
1522 if (phist
->spec_ds
!= spec_ds
)
1523 phist
->spec_ds
= ds_max_merge (phist
->spec_ds
, spec_ds
);
1528 temp
.old_expr_vinsn
= old_expr_vinsn
;
1529 temp
.new_expr_vinsn
= new_expr_vinsn
;
1530 temp
.spec_ds
= spec_ds
;
1533 vinsn_attach (old_expr_vinsn
);
1534 vinsn_attach (new_expr_vinsn
);
1535 VEC_safe_insert (expr_history_def
, heap
, vect
, ind
, &temp
);
1539 /* Free history vector PVECT. */
1541 free_history_vect (VEC (expr_history_def
, heap
) **pvect
)
1544 expr_history_def
*phist
;
1550 VEC_iterate (expr_history_def
, *pvect
, i
, phist
);
1553 vinsn_detach (phist
->old_expr_vinsn
);
1554 vinsn_detach (phist
->new_expr_vinsn
);
1557 VEC_free (expr_history_def
, heap
, *pvect
);
1562 /* Compare two vinsns as rhses if possible and as vinsns otherwise. */
1564 vinsn_equal_p (vinsn_t x
, vinsn_t y
)
1566 rtx_equal_p_callback_function repcf
;
1571 if (VINSN_TYPE (x
) != VINSN_TYPE (y
))
1574 if (VINSN_HASH (x
) != VINSN_HASH (y
))
1577 repcf
= targetm
.sched
.skip_rtx_p
? skip_unspecs_callback
: NULL
;
1578 if (VINSN_SEPARABLE_P (x
))
1580 /* Compare RHSes of VINSNs. */
1581 gcc_assert (VINSN_RHS (x
));
1582 gcc_assert (VINSN_RHS (y
));
1584 return rtx_equal_p_cb (VINSN_RHS (x
), VINSN_RHS (y
), repcf
);
1587 return rtx_equal_p_cb (VINSN_PATTERN (x
), VINSN_PATTERN (y
), repcf
);
1591 /* Functions for working with expressions. */
1593 /* Initialize EXPR. */
1595 init_expr (expr_t expr
, vinsn_t vi
, int spec
, int use
, int priority
,
1596 int sched_times
, int orig_bb_index
, ds_t spec_done_ds
,
1597 ds_t spec_to_check_ds
, int orig_sched_cycle
,
1598 VEC(expr_history_def
, heap
) *history
, bool target_available
,
1599 bool was_substituted
, bool was_renamed
, bool needs_spec_check_p
,
1604 EXPR_VINSN (expr
) = vi
;
1605 EXPR_SPEC (expr
) = spec
;
1606 EXPR_USEFULNESS (expr
) = use
;
1607 EXPR_PRIORITY (expr
) = priority
;
1608 EXPR_PRIORITY_ADJ (expr
) = 0;
1609 EXPR_SCHED_TIMES (expr
) = sched_times
;
1610 EXPR_ORIG_BB_INDEX (expr
) = orig_bb_index
;
1611 EXPR_ORIG_SCHED_CYCLE (expr
) = orig_sched_cycle
;
1612 EXPR_SPEC_DONE_DS (expr
) = spec_done_ds
;
1613 EXPR_SPEC_TO_CHECK_DS (expr
) = spec_to_check_ds
;
1616 EXPR_HISTORY_OF_CHANGES (expr
) = history
;
1618 EXPR_HISTORY_OF_CHANGES (expr
) = NULL
;
1620 EXPR_TARGET_AVAILABLE (expr
) = target_available
;
1621 EXPR_WAS_SUBSTITUTED (expr
) = was_substituted
;
1622 EXPR_WAS_RENAMED (expr
) = was_renamed
;
1623 EXPR_NEEDS_SPEC_CHECK_P (expr
) = needs_spec_check_p
;
1624 EXPR_CANT_MOVE (expr
) = cant_move
;
1627 /* Make a copy of the expr FROM into the expr TO. */
1629 copy_expr (expr_t to
, expr_t from
)
1631 VEC(expr_history_def
, heap
) *temp
= NULL
;
1633 if (EXPR_HISTORY_OF_CHANGES (from
))
1636 expr_history_def
*phist
;
1638 temp
= VEC_copy (expr_history_def
, heap
, EXPR_HISTORY_OF_CHANGES (from
));
1640 VEC_iterate (expr_history_def
, temp
, i
, phist
);
1643 vinsn_attach (phist
->old_expr_vinsn
);
1644 vinsn_attach (phist
->new_expr_vinsn
);
1648 init_expr (to
, EXPR_VINSN (from
), EXPR_SPEC (from
),
1649 EXPR_USEFULNESS (from
), EXPR_PRIORITY (from
),
1650 EXPR_SCHED_TIMES (from
), EXPR_ORIG_BB_INDEX (from
),
1651 EXPR_SPEC_DONE_DS (from
), EXPR_SPEC_TO_CHECK_DS (from
),
1652 EXPR_ORIG_SCHED_CYCLE (from
), temp
,
1653 EXPR_TARGET_AVAILABLE (from
), EXPR_WAS_SUBSTITUTED (from
),
1654 EXPR_WAS_RENAMED (from
), EXPR_NEEDS_SPEC_CHECK_P (from
),
1655 EXPR_CANT_MOVE (from
));
1658 /* Same, but the final expr will not ever be in av sets, so don't copy
1659 "uninteresting" data such as bitmap cache. */
1661 copy_expr_onside (expr_t to
, expr_t from
)
1663 init_expr (to
, EXPR_VINSN (from
), EXPR_SPEC (from
), EXPR_USEFULNESS (from
),
1664 EXPR_PRIORITY (from
), EXPR_SCHED_TIMES (from
), 0,
1665 EXPR_SPEC_DONE_DS (from
), EXPR_SPEC_TO_CHECK_DS (from
), 0, NULL
,
1666 EXPR_TARGET_AVAILABLE (from
), EXPR_WAS_SUBSTITUTED (from
),
1667 EXPR_WAS_RENAMED (from
), EXPR_NEEDS_SPEC_CHECK_P (from
),
1668 EXPR_CANT_MOVE (from
));
1671 /* Prepare the expr of INSN for scheduling. Used when moving insn and when
1672 initializing new insns. */
1674 prepare_insn_expr (insn_t insn
, int seqno
)
1676 expr_t expr
= INSN_EXPR (insn
);
1679 INSN_SEQNO (insn
) = seqno
;
1680 EXPR_ORIG_BB_INDEX (expr
) = BLOCK_NUM (insn
);
1681 EXPR_SPEC (expr
) = 0;
1682 EXPR_ORIG_SCHED_CYCLE (expr
) = 0;
1683 EXPR_WAS_SUBSTITUTED (expr
) = 0;
1684 EXPR_WAS_RENAMED (expr
) = 0;
1685 EXPR_TARGET_AVAILABLE (expr
) = 1;
1686 INSN_LIVE_VALID_P (insn
) = false;
1688 /* ??? If this expression is speculative, make its dependence
1689 as weak as possible. We can filter this expression later
1690 in process_spec_exprs, because we do not distinguish
1691 between the status we got during compute_av_set and the
1692 existing status. To be fixed. */
1693 ds
= EXPR_SPEC_DONE_DS (expr
);
1695 EXPR_SPEC_DONE_DS (expr
) = ds_get_max_dep_weak (ds
);
1697 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr
));
1700 /* Update target_available bits when merging exprs TO and FROM. SPLIT_POINT
1701 is non-null when expressions are merged from different successors at
1704 update_target_availability (expr_t to
, expr_t from
, insn_t split_point
)
1706 if (EXPR_TARGET_AVAILABLE (to
) < 0
1707 || EXPR_TARGET_AVAILABLE (from
) < 0)
1708 EXPR_TARGET_AVAILABLE (to
) = -1;
1711 /* We try to detect the case when one of the expressions
1712 can only be reached through another one. In this case,
1713 we can do better. */
1714 if (split_point
== NULL
)
1718 toind
= EXPR_ORIG_BB_INDEX (to
);
1719 fromind
= EXPR_ORIG_BB_INDEX (from
);
1721 if (toind
&& toind
== fromind
)
1722 /* Do nothing -- everything is done in
1723 merge_with_other_exprs. */
1726 EXPR_TARGET_AVAILABLE (to
) = -1;
1729 EXPR_TARGET_AVAILABLE (to
) &= EXPR_TARGET_AVAILABLE (from
);
1733 /* Update speculation bits when merging exprs TO and FROM. SPLIT_POINT
1734 is non-null when expressions are merged from different successors at
1737 update_speculative_bits (expr_t to
, expr_t from
, insn_t split_point
)
1739 ds_t old_to_ds
, old_from_ds
;
1741 old_to_ds
= EXPR_SPEC_DONE_DS (to
);
1742 old_from_ds
= EXPR_SPEC_DONE_DS (from
);
1744 EXPR_SPEC_DONE_DS (to
) = ds_max_merge (old_to_ds
, old_from_ds
);
1745 EXPR_SPEC_TO_CHECK_DS (to
) |= EXPR_SPEC_TO_CHECK_DS (from
);
1746 EXPR_NEEDS_SPEC_CHECK_P (to
) |= EXPR_NEEDS_SPEC_CHECK_P (from
);
1748 /* When merging e.g. control & data speculative exprs, or a control
1749 speculative with a control&data speculative one, we really have
1750 to change vinsn too. Also, when speculative status is changed,
1751 we also need to record this as a transformation in expr's history. */
1752 if ((old_to_ds
& SPECULATIVE
) || (old_from_ds
& SPECULATIVE
))
1754 old_to_ds
= ds_get_speculation_types (old_to_ds
);
1755 old_from_ds
= ds_get_speculation_types (old_from_ds
);
1757 if (old_to_ds
!= old_from_ds
)
1761 /* When both expressions are speculative, we need to change
1763 if ((old_to_ds
& SPECULATIVE
) && (old_from_ds
& SPECULATIVE
))
1767 res
= speculate_expr (to
, EXPR_SPEC_DONE_DS (to
));
1768 gcc_assert (res
>= 0);
1771 if (split_point
!= NULL
)
1773 /* Record the change with proper status. */
1774 record_ds
= EXPR_SPEC_DONE_DS (to
) & SPECULATIVE
;
1775 record_ds
&= ~(old_to_ds
& SPECULATIVE
);
1776 record_ds
&= ~(old_from_ds
& SPECULATIVE
);
1778 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to
),
1779 INSN_UID (split_point
), TRANS_SPECULATION
,
1780 EXPR_VINSN (from
), EXPR_VINSN (to
),
1788 /* Merge bits of FROM expr to TO expr. When SPLIT_POINT is not NULL,
1789 this is done along different paths. */
1791 merge_expr_data (expr_t to
, expr_t from
, insn_t split_point
)
1794 expr_history_def
*phist
;
1796 /* For now, we just set the spec of resulting expr to be minimum of the specs
1798 if (EXPR_SPEC (to
) > EXPR_SPEC (from
))
1799 EXPR_SPEC (to
) = EXPR_SPEC (from
);
1802 EXPR_USEFULNESS (to
) += EXPR_USEFULNESS (from
);
1804 EXPR_USEFULNESS (to
) = MAX (EXPR_USEFULNESS (to
),
1805 EXPR_USEFULNESS (from
));
1807 if (EXPR_PRIORITY (to
) < EXPR_PRIORITY (from
))
1808 EXPR_PRIORITY (to
) = EXPR_PRIORITY (from
);
1810 if (EXPR_SCHED_TIMES (to
) > EXPR_SCHED_TIMES (from
))
1811 EXPR_SCHED_TIMES (to
) = EXPR_SCHED_TIMES (from
);
1813 if (EXPR_ORIG_BB_INDEX (to
) != EXPR_ORIG_BB_INDEX (from
))
1814 EXPR_ORIG_BB_INDEX (to
) = 0;
1816 EXPR_ORIG_SCHED_CYCLE (to
) = MIN (EXPR_ORIG_SCHED_CYCLE (to
),
1817 EXPR_ORIG_SCHED_CYCLE (from
));
1819 /* We keep this vector sorted. */
1821 VEC_iterate (expr_history_def
, EXPR_HISTORY_OF_CHANGES (from
),
1824 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to
),
1825 phist
->uid
, phist
->type
,
1826 phist
->old_expr_vinsn
, phist
->new_expr_vinsn
,
1829 EXPR_WAS_SUBSTITUTED (to
) |= EXPR_WAS_SUBSTITUTED (from
);
1830 EXPR_WAS_RENAMED (to
) |= EXPR_WAS_RENAMED (from
);
1831 EXPR_CANT_MOVE (to
) |= EXPR_CANT_MOVE (from
);
1833 update_target_availability (to
, from
, split_point
);
1834 update_speculative_bits (to
, from
, split_point
);
1837 /* Merge bits of FROM expr to TO expr. Vinsns in the exprs should be equal
1838 in terms of vinsn_equal_p. SPLIT_POINT is non-null when expressions
1839 are merged from different successors at a split point. */
1841 merge_expr (expr_t to
, expr_t from
, insn_t split_point
)
1843 vinsn_t to_vi
= EXPR_VINSN (to
);
1844 vinsn_t from_vi
= EXPR_VINSN (from
);
1846 gcc_assert (vinsn_equal_p (to_vi
, from_vi
));
1848 /* Make sure that speculative pattern is propagated into exprs that
1849 have non-speculative one. This will provide us with consistent
1850 speculative bits and speculative patterns inside expr. */
1851 if (EXPR_SPEC_DONE_DS (to
) == 0
1852 && EXPR_SPEC_DONE_DS (from
) != 0)
1853 change_vinsn_in_expr (to
, EXPR_VINSN (from
));
1855 merge_expr_data (to
, from
, split_point
);
1856 gcc_assert (EXPR_USEFULNESS (to
) <= REG_BR_PROB_BASE
);
1859 /* Clear the information of this EXPR. */
1861 clear_expr (expr_t expr
)
1864 vinsn_detach (EXPR_VINSN (expr
));
1865 EXPR_VINSN (expr
) = NULL
;
1867 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr
));
1870 /* For a given LV_SET, mark EXPR having unavailable target register. */
1872 set_unavailable_target_for_expr (expr_t expr
, regset lv_set
)
1874 if (EXPR_SEPARABLE_P (expr
))
1876 if (REG_P (EXPR_LHS (expr
))
1877 && bitmap_bit_p (lv_set
, REGNO (EXPR_LHS (expr
))))
1879 /* If it's an insn like r1 = use (r1, ...), and it exists in
1880 different forms in each of the av_sets being merged, we can't say
1881 whether original destination register is available or not.
1882 However, this still works if destination register is not used
1883 in the original expression: if the branch at which LV_SET we're
1884 looking here is not actually 'other branch' in sense that same
1885 expression is available through it (but it can't be determined
1886 at computation stage because of transformations on one of the
1887 branches), it still won't affect the availability.
1888 Liveness of a register somewhere on a code motion path means
1889 it's either read somewhere on a codemotion path, live on
1890 'other' branch, live at the point immediately following
1891 the original operation, or is read by the original operation.
1892 The latter case is filtered out in the condition below.
1893 It still doesn't cover the case when register is defined and used
1894 somewhere within the code motion path, and in this case we could
1895 miss a unifying code motion along both branches using a renamed
1896 register, but it won't affect a code correctness since upon
1897 an actual code motion a bookkeeping code would be generated. */
1898 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr
)),
1899 REGNO (EXPR_LHS (expr
))))
1900 EXPR_TARGET_AVAILABLE (expr
) = -1;
1902 EXPR_TARGET_AVAILABLE (expr
) = false;
1908 reg_set_iterator rsi
;
1910 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (EXPR_VINSN (expr
)),
1912 if (bitmap_bit_p (lv_set
, regno
))
1914 EXPR_TARGET_AVAILABLE (expr
) = false;
1918 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (EXPR_VINSN (expr
)),
1920 if (bitmap_bit_p (lv_set
, regno
))
1922 EXPR_TARGET_AVAILABLE (expr
) = false;
1928 /* Try to make EXPR speculative. Return 1 when EXPR's pattern
1929 or dependence status have changed, 2 when also the target register
1930 became unavailable, 0 if nothing had to be changed. */
1932 speculate_expr (expr_t expr
, ds_t ds
)
1937 ds_t target_ds
, current_ds
;
1939 /* Obtain the status we need to put on EXPR. */
1940 target_ds
= (ds
& SPECULATIVE
);
1941 current_ds
= EXPR_SPEC_DONE_DS (expr
);
1942 ds
= ds_full_merge (current_ds
, target_ds
, NULL_RTX
, NULL_RTX
);
1944 orig_insn_rtx
= EXPR_INSN_RTX (expr
);
1946 res
= sched_speculate_insn (orig_insn_rtx
, ds
, &spec_pat
);
1951 EXPR_SPEC_DONE_DS (expr
) = ds
;
1952 return current_ds
!= ds
? 1 : 0;
1956 rtx spec_insn_rtx
= create_insn_rtx_from_pattern (spec_pat
, NULL_RTX
);
1957 vinsn_t spec_vinsn
= create_vinsn_from_insn_rtx (spec_insn_rtx
, false);
1959 change_vinsn_in_expr (expr
, spec_vinsn
);
1960 EXPR_SPEC_DONE_DS (expr
) = ds
;
1961 EXPR_NEEDS_SPEC_CHECK_P (expr
) = true;
1963 /* Do not allow clobbering the address register of speculative
1965 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr
)),
1966 expr_dest_regno (expr
)))
1968 EXPR_TARGET_AVAILABLE (expr
) = false;
1984 /* Return a destination register, if any, of EXPR. */
1986 expr_dest_reg (expr_t expr
)
1988 rtx dest
= VINSN_LHS (EXPR_VINSN (expr
));
1990 if (dest
!= NULL_RTX
&& REG_P (dest
))
1996 /* Returns the REGNO of the R's destination. */
1998 expr_dest_regno (expr_t expr
)
2000 rtx dest
= expr_dest_reg (expr
);
2002 gcc_assert (dest
!= NULL_RTX
);
2003 return REGNO (dest
);
2006 /* For a given LV_SET, mark all expressions in JOIN_SET, but not present in
2007 AV_SET having unavailable target register. */
2009 mark_unavailable_targets (av_set_t join_set
, av_set_t av_set
, regset lv_set
)
2012 av_set_iterator avi
;
2014 FOR_EACH_EXPR (expr
, avi
, join_set
)
2015 if (av_set_lookup (av_set
, EXPR_VINSN (expr
)) == NULL
)
2016 set_unavailable_target_for_expr (expr
, lv_set
);
2020 /* Av set functions. */
2022 /* Add a new element to av set SETP.
2023 Return the element added. */
2025 av_set_add_element (av_set_t
*setp
)
2027 /* Insert at the beginning of the list. */
2032 /* Add EXPR to SETP. */
2034 av_set_add (av_set_t
*setp
, expr_t expr
)
2038 gcc_assert (!INSN_NOP_P (EXPR_INSN_RTX (expr
)));
2039 elem
= av_set_add_element (setp
);
2040 copy_expr (_AV_SET_EXPR (elem
), expr
);
2043 /* Same, but do not copy EXPR. */
2045 av_set_add_nocopy (av_set_t
*setp
, expr_t expr
)
2049 elem
= av_set_add_element (setp
);
2050 *_AV_SET_EXPR (elem
) = *expr
;
2053 /* Remove expr pointed to by IP from the av_set. */
2055 av_set_iter_remove (av_set_iterator
*ip
)
2057 clear_expr (_AV_SET_EXPR (*ip
->lp
));
2058 _list_iter_remove (ip
);
2061 /* Search for an expr in SET, such that it's equivalent to SOUGHT_VINSN in the
2062 sense of vinsn_equal_p function. Return NULL if no such expr is
2063 in SET was found. */
2065 av_set_lookup (av_set_t set
, vinsn_t sought_vinsn
)
2070 FOR_EACH_EXPR (expr
, i
, set
)
2071 if (vinsn_equal_p (EXPR_VINSN (expr
), sought_vinsn
))
2076 /* Same, but also remove the EXPR found. */
2078 av_set_lookup_and_remove (av_set_t
*setp
, vinsn_t sought_vinsn
)
2083 FOR_EACH_EXPR_1 (expr
, i
, setp
)
2084 if (vinsn_equal_p (EXPR_VINSN (expr
), sought_vinsn
))
2086 _list_iter_remove_nofree (&i
);
2092 /* Search for an expr in SET, such that it's equivalent to EXPR in the
2093 sense of vinsn_equal_p function of their vinsns, but not EXPR itself.
2094 Returns NULL if no such expr is in SET was found. */
2096 av_set_lookup_other_equiv_expr (av_set_t set
, expr_t expr
)
2101 FOR_EACH_EXPR (cur_expr
, i
, set
)
2103 if (cur_expr
== expr
)
2105 if (vinsn_equal_p (EXPR_VINSN (cur_expr
), EXPR_VINSN (expr
)))
2112 /* If other expression is already in AVP, remove one of them. */
2114 merge_with_other_exprs (av_set_t
*avp
, av_set_iterator
*ip
, expr_t expr
)
2118 expr2
= av_set_lookup_other_equiv_expr (*avp
, expr
);
2121 /* Reset target availability on merge, since taking it only from one
2122 of the exprs would be controversial for different code. */
2123 EXPR_TARGET_AVAILABLE (expr2
) = -1;
2124 EXPR_USEFULNESS (expr2
) = 0;
2126 merge_expr (expr2
, expr
, NULL
);
2128 /* Fix usefulness as it should be now REG_BR_PROB_BASE. */
2129 EXPR_USEFULNESS (expr2
) = REG_BR_PROB_BASE
;
2131 av_set_iter_remove (ip
);
2138 /* Return true if there is an expr that correlates to VI in SET. */
2140 av_set_is_in_p (av_set_t set
, vinsn_t vi
)
2142 return av_set_lookup (set
, vi
) != NULL
;
2145 /* Return a copy of SET. */
2147 av_set_copy (av_set_t set
)
2151 av_set_t res
= NULL
;
2153 FOR_EACH_EXPR (expr
, i
, set
)
2154 av_set_add (&res
, expr
);
2159 /* Join two av sets that do not have common elements by attaching second set
2160 (pointed to by FROMP) to the end of first set (TO_TAILP must point to
2161 _AV_SET_NEXT of first set's last element). */
2163 join_distinct_sets (av_set_t
*to_tailp
, av_set_t
*fromp
)
2165 gcc_assert (*to_tailp
== NULL
);
2170 /* Makes set pointed to by TO to be the union of TO and FROM. Clear av_set
2171 pointed to by FROMP afterwards. */
2173 av_set_union_and_clear (av_set_t
*top
, av_set_t
*fromp
, insn_t insn
)
2178 /* Delete from TOP all exprs, that present in FROMP. */
2179 FOR_EACH_EXPR_1 (expr1
, i
, top
)
2181 expr_t expr2
= av_set_lookup (*fromp
, EXPR_VINSN (expr1
));
2185 merge_expr (expr2
, expr1
, insn
);
2186 av_set_iter_remove (&i
);
2190 join_distinct_sets (i
.lp
, fromp
);
2193 /* Same as above, but also update availability of target register in
2194 TOP judging by TO_LV_SET and FROM_LV_SET. */
2196 av_set_union_and_live (av_set_t
*top
, av_set_t
*fromp
, regset to_lv_set
,
2197 regset from_lv_set
, insn_t insn
)
2201 av_set_t
*to_tailp
, in_both_set
= NULL
;
2203 /* Delete from TOP all expres, that present in FROMP. */
2204 FOR_EACH_EXPR_1 (expr1
, i
, top
)
2206 expr_t expr2
= av_set_lookup_and_remove (fromp
, EXPR_VINSN (expr1
));
2210 /* It may be that the expressions have different destination
2211 registers, in which case we need to check liveness here. */
2212 if (EXPR_SEPARABLE_P (expr1
))
2214 int regno1
= (REG_P (EXPR_LHS (expr1
))
2215 ? (int) expr_dest_regno (expr1
) : -1);
2216 int regno2
= (REG_P (EXPR_LHS (expr2
))
2217 ? (int) expr_dest_regno (expr2
) : -1);
2219 /* ??? We don't have a way to check restrictions for
2220 *other* register on the current path, we did it only
2221 for the current target register. Give up. */
2222 if (regno1
!= regno2
)
2223 EXPR_TARGET_AVAILABLE (expr2
) = -1;
2225 else if (EXPR_INSN_RTX (expr1
) != EXPR_INSN_RTX (expr2
))
2226 EXPR_TARGET_AVAILABLE (expr2
) = -1;
2228 merge_expr (expr2
, expr1
, insn
);
2229 av_set_add_nocopy (&in_both_set
, expr2
);
2230 av_set_iter_remove (&i
);
2233 /* EXPR1 is present in TOP, but not in FROMP. Check it on
2235 set_unavailable_target_for_expr (expr1
, from_lv_set
);
2239 /* These expressions are not present in TOP. Check liveness
2240 restrictions on TO_LV_SET. */
2241 FOR_EACH_EXPR (expr1
, i
, *fromp
)
2242 set_unavailable_target_for_expr (expr1
, to_lv_set
);
2244 join_distinct_sets (i
.lp
, &in_both_set
);
2245 join_distinct_sets (to_tailp
, fromp
);
2248 /* Clear av_set pointed to by SETP. */
2250 av_set_clear (av_set_t
*setp
)
2255 FOR_EACH_EXPR_1 (expr
, i
, setp
)
2256 av_set_iter_remove (&i
);
2258 gcc_assert (*setp
== NULL
);
2261 /* Leave only one non-speculative element in the SETP. */
2263 av_set_leave_one_nonspec (av_set_t
*setp
)
2267 bool has_one_nonspec
= false;
2269 /* Keep all speculative exprs, and leave one non-speculative
2271 FOR_EACH_EXPR_1 (expr
, i
, setp
)
2273 if (!EXPR_SPEC_DONE_DS (expr
))
2275 if (has_one_nonspec
)
2276 av_set_iter_remove (&i
);
2278 has_one_nonspec
= true;
2283 /* Return the N'th element of the SET. */
2285 av_set_element (av_set_t set
, int n
)
2290 FOR_EACH_EXPR (expr
, i
, set
)
2298 /* Deletes all expressions from AVP that are conditional branches (IFs). */
2300 av_set_substract_cond_branches (av_set_t
*avp
)
2305 FOR_EACH_EXPR_1 (expr
, i
, avp
)
2306 if (vinsn_cond_branch_p (EXPR_VINSN (expr
)))
2307 av_set_iter_remove (&i
);
2310 /* Multiplies usefulness attribute of each member of av-set *AVP by
2311 value PROB / ALL_PROB. */
2313 av_set_split_usefulness (av_set_t av
, int prob
, int all_prob
)
2318 FOR_EACH_EXPR (expr
, i
, av
)
2319 EXPR_USEFULNESS (expr
) = (all_prob
2320 ? (EXPR_USEFULNESS (expr
) * prob
) / all_prob
2324 /* Leave in AVP only those expressions, which are present in AV,
2327 av_set_intersect (av_set_t
*avp
, av_set_t av
)
2332 FOR_EACH_EXPR_1 (expr
, i
, avp
)
2333 if (av_set_lookup (av
, EXPR_VINSN (expr
)) == NULL
)
2334 av_set_iter_remove (&i
);
2339 /* Dependence hooks to initialize insn data. */
2341 /* This is used in hooks callable from dependence analysis when initializing
2342 instruction's data. */
2345 /* Where the dependence was found (lhs/rhs). */
2348 /* The actual data object to initialize. */
2351 /* True when the insn should not be made clonable. */
2352 bool force_unique_p
;
2354 /* True when insn should be treated as of type USE, i.e. never renamed. */
2356 } deps_init_id_data
;
2359 /* Setup ID for INSN. FORCE_UNIQUE_P is true when INSN should not be
2362 setup_id_for_insn (idata_t id
, insn_t insn
, bool force_unique_p
)
2366 /* Determine whether INSN could be cloned and return appropriate vinsn type.
2367 That clonable insns which can be separated into lhs and rhs have type SET.
2368 Other clonable insns have type USE. */
2369 type
= GET_CODE (insn
);
2371 /* Only regular insns could be cloned. */
2372 if (type
== INSN
&& !force_unique_p
)
2374 else if (type
== JUMP_INSN
&& simplejump_p (insn
))
2376 else if (type
== DEBUG_INSN
)
2377 type
= !force_unique_p
? USE
: INSN
;
2379 IDATA_TYPE (id
) = type
;
2380 IDATA_REG_SETS (id
) = get_clear_regset_from_pool ();
2381 IDATA_REG_USES (id
) = get_clear_regset_from_pool ();
2382 IDATA_REG_CLOBBERS (id
) = get_clear_regset_from_pool ();
2385 /* Start initializing insn data. */
2387 deps_init_id_start_insn (insn_t insn
)
2389 gcc_assert (deps_init_id_data
.where
== DEPS_IN_NOWHERE
);
2391 setup_id_for_insn (deps_init_id_data
.id
, insn
,
2392 deps_init_id_data
.force_unique_p
);
2393 deps_init_id_data
.where
= DEPS_IN_INSN
;
2396 /* Start initializing lhs data. */
2398 deps_init_id_start_lhs (rtx lhs
)
2400 gcc_assert (deps_init_id_data
.where
== DEPS_IN_INSN
);
2401 gcc_assert (IDATA_LHS (deps_init_id_data
.id
) == NULL
);
2403 if (IDATA_TYPE (deps_init_id_data
.id
) == SET
)
2405 IDATA_LHS (deps_init_id_data
.id
) = lhs
;
2406 deps_init_id_data
.where
= DEPS_IN_LHS
;
2410 /* Finish initializing lhs data. */
2412 deps_init_id_finish_lhs (void)
2414 deps_init_id_data
.where
= DEPS_IN_INSN
;
2417 /* Note a set of REGNO. */
2419 deps_init_id_note_reg_set (int regno
)
2421 haifa_note_reg_set (regno
);
2423 if (deps_init_id_data
.where
== DEPS_IN_RHS
)
2424 deps_init_id_data
.force_use_p
= true;
2426 if (IDATA_TYPE (deps_init_id_data
.id
) != PC
)
2427 SET_REGNO_REG_SET (IDATA_REG_SETS (deps_init_id_data
.id
), regno
);
2430 /* Make instructions that set stack registers to be ineligible for
2431 renaming to avoid issues with find_used_regs. */
2432 if (IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
))
2433 deps_init_id_data
.force_use_p
= true;
2437 /* Note a clobber of REGNO. */
2439 deps_init_id_note_reg_clobber (int regno
)
2441 haifa_note_reg_clobber (regno
);
2443 if (deps_init_id_data
.where
== DEPS_IN_RHS
)
2444 deps_init_id_data
.force_use_p
= true;
2446 if (IDATA_TYPE (deps_init_id_data
.id
) != PC
)
2447 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (deps_init_id_data
.id
), regno
);
2450 /* Note a use of REGNO. */
2452 deps_init_id_note_reg_use (int regno
)
2454 haifa_note_reg_use (regno
);
2456 if (IDATA_TYPE (deps_init_id_data
.id
) != PC
)
2457 SET_REGNO_REG_SET (IDATA_REG_USES (deps_init_id_data
.id
), regno
);
2460 /* Start initializing rhs data. */
2462 deps_init_id_start_rhs (rtx rhs
)
2464 gcc_assert (deps_init_id_data
.where
== DEPS_IN_INSN
);
2466 /* And there was no sel_deps_reset_to_insn (). */
2467 if (IDATA_LHS (deps_init_id_data
.id
) != NULL
)
2469 IDATA_RHS (deps_init_id_data
.id
) = rhs
;
2470 deps_init_id_data
.where
= DEPS_IN_RHS
;
2474 /* Finish initializing rhs data. */
2476 deps_init_id_finish_rhs (void)
2478 gcc_assert (deps_init_id_data
.where
== DEPS_IN_RHS
2479 || deps_init_id_data
.where
== DEPS_IN_INSN
);
2480 deps_init_id_data
.where
= DEPS_IN_INSN
;
2483 /* Finish initializing insn data. */
2485 deps_init_id_finish_insn (void)
2487 gcc_assert (deps_init_id_data
.where
== DEPS_IN_INSN
);
2489 if (IDATA_TYPE (deps_init_id_data
.id
) == SET
)
2491 rtx lhs
= IDATA_LHS (deps_init_id_data
.id
);
2492 rtx rhs
= IDATA_RHS (deps_init_id_data
.id
);
2494 if (lhs
== NULL
|| rhs
== NULL
|| !lhs_and_rhs_separable_p (lhs
, rhs
)
2495 || deps_init_id_data
.force_use_p
)
2497 /* This should be a USE, as we don't want to schedule its RHS
2498 separately. However, we still want to have them recorded
2499 for the purposes of substitution. That's why we don't
2500 simply call downgrade_to_use () here. */
2501 gcc_assert (IDATA_TYPE (deps_init_id_data
.id
) == SET
);
2502 gcc_assert (!lhs
== !rhs
);
2504 IDATA_TYPE (deps_init_id_data
.id
) = USE
;
2508 deps_init_id_data
.where
= DEPS_IN_NOWHERE
;
2511 /* This is dependence info used for initializing insn's data. */
2512 static struct sched_deps_info_def deps_init_id_sched_deps_info
;
2514 /* This initializes most of the static part of the above structure. */
2515 static const struct sched_deps_info_def const_deps_init_id_sched_deps_info
=
2519 deps_init_id_start_insn
,
2520 deps_init_id_finish_insn
,
2521 deps_init_id_start_lhs
,
2522 deps_init_id_finish_lhs
,
2523 deps_init_id_start_rhs
,
2524 deps_init_id_finish_rhs
,
2525 deps_init_id_note_reg_set
,
2526 deps_init_id_note_reg_clobber
,
2527 deps_init_id_note_reg_use
,
2528 NULL
, /* note_mem_dep */
2529 NULL
, /* note_dep */
2532 0, /* use_deps_list */
2533 0 /* generate_spec_deps */
2536 /* Initialize INSN's lhs and rhs in ID. When FORCE_UNIQUE_P is true,
2537 we don't actually need information about lhs and rhs. */
2539 setup_id_lhs_rhs (idata_t id
, insn_t insn
, bool force_unique_p
)
2541 rtx pat
= PATTERN (insn
);
2543 if (NONJUMP_INSN_P (insn
)
2544 && GET_CODE (pat
) == SET
2547 IDATA_RHS (id
) = SET_SRC (pat
);
2548 IDATA_LHS (id
) = SET_DEST (pat
);
2551 IDATA_LHS (id
) = IDATA_RHS (id
) = NULL
;
2554 /* Possibly downgrade INSN to USE. */
2556 maybe_downgrade_id_to_use (idata_t id
, insn_t insn
)
2558 bool must_be_use
= false;
2559 unsigned uid
= INSN_UID (insn
);
2561 rtx lhs
= IDATA_LHS (id
);
2562 rtx rhs
= IDATA_RHS (id
);
2564 /* We downgrade only SETs. */
2565 if (IDATA_TYPE (id
) != SET
)
2568 if (!lhs
|| !lhs_and_rhs_separable_p (lhs
, rhs
))
2570 IDATA_TYPE (id
) = USE
;
2574 for (rec
= DF_INSN_UID_DEFS (uid
); *rec
; rec
++)
2578 if (DF_REF_INSN (def
)
2579 && DF_REF_FLAGS_IS_SET (def
, DF_REF_PRE_POST_MODIFY
)
2580 && loc_mentioned_in_p (DF_REF_LOC (def
), IDATA_RHS (id
)))
2587 /* Make instructions that set stack registers to be ineligible for
2588 renaming to avoid issues with find_used_regs. */
2589 if (IN_RANGE (DF_REF_REGNO (def
), FIRST_STACK_REG
, LAST_STACK_REG
))
2598 IDATA_TYPE (id
) = USE
;
2601 /* Setup register sets describing INSN in ID. */
2603 setup_id_reg_sets (idata_t id
, insn_t insn
)
2605 unsigned uid
= INSN_UID (insn
);
2607 regset tmp
= get_clear_regset_from_pool ();
2609 for (rec
= DF_INSN_UID_DEFS (uid
); *rec
; rec
++)
2612 unsigned int regno
= DF_REF_REGNO (def
);
2614 /* Post modifies are treated like clobbers by sched-deps.c. */
2615 if (DF_REF_FLAGS_IS_SET (def
, (DF_REF_MUST_CLOBBER
2616 | DF_REF_PRE_POST_MODIFY
)))
2617 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (id
), regno
);
2618 else if (! DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
2620 SET_REGNO_REG_SET (IDATA_REG_SETS (id
), regno
);
2623 /* For stack registers, treat writes to them as writes
2624 to the first one to be consistent with sched-deps.c. */
2625 if (IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
))
2626 SET_REGNO_REG_SET (IDATA_REG_SETS (id
), FIRST_STACK_REG
);
2629 /* Mark special refs that generate read/write def pair. */
2630 if (DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
)
2631 || regno
== STACK_POINTER_REGNUM
)
2632 bitmap_set_bit (tmp
, regno
);
2635 for (rec
= DF_INSN_UID_USES (uid
); *rec
; rec
++)
2638 unsigned int regno
= DF_REF_REGNO (use
);
2640 /* When these refs are met for the first time, skip them, as
2641 these uses are just counterparts of some defs. */
2642 if (bitmap_bit_p (tmp
, regno
))
2643 bitmap_clear_bit (tmp
, regno
);
2644 else if (! DF_REF_FLAGS_IS_SET (use
, DF_REF_CALL_STACK_USAGE
))
2646 SET_REGNO_REG_SET (IDATA_REG_USES (id
), regno
);
2649 /* For stack registers, treat reads from them as reads from
2650 the first one to be consistent with sched-deps.c. */
2651 if (IN_RANGE (regno
, FIRST_STACK_REG
, LAST_STACK_REG
))
2652 SET_REGNO_REG_SET (IDATA_REG_USES (id
), FIRST_STACK_REG
);
2657 return_regset_to_pool (tmp
);
2660 /* Initialize instruction data for INSN in ID using DF's data. */
2662 init_id_from_df (idata_t id
, insn_t insn
, bool force_unique_p
)
2664 gcc_assert (DF_INSN_UID_SAFE_GET (INSN_UID (insn
)) != NULL
);
2666 setup_id_for_insn (id
, insn
, force_unique_p
);
2667 setup_id_lhs_rhs (id
, insn
, force_unique_p
);
2669 if (INSN_NOP_P (insn
))
2672 maybe_downgrade_id_to_use (id
, insn
);
2673 setup_id_reg_sets (id
, insn
);
2676 /* Initialize instruction data for INSN in ID. */
2678 deps_init_id (idata_t id
, insn_t insn
, bool force_unique_p
)
2680 struct deps_desc _dc
, *dc
= &_dc
;
2682 deps_init_id_data
.where
= DEPS_IN_NOWHERE
;
2683 deps_init_id_data
.id
= id
;
2684 deps_init_id_data
.force_unique_p
= force_unique_p
;
2685 deps_init_id_data
.force_use_p
= false;
2687 init_deps (dc
, false);
2689 memcpy (&deps_init_id_sched_deps_info
,
2690 &const_deps_init_id_sched_deps_info
,
2691 sizeof (deps_init_id_sched_deps_info
));
2693 if (spec_info
!= NULL
)
2694 deps_init_id_sched_deps_info
.generate_spec_deps
= 1;
2696 sched_deps_info
= &deps_init_id_sched_deps_info
;
2698 deps_analyze_insn (dc
, insn
);
2702 deps_init_id_data
.id
= NULL
;
2707 /* Implement hooks for collecting fundamental insn properties like if insn is
2708 an ASM or is within a SCHED_GROUP. */
2710 /* True when a "one-time init" data for INSN was already inited. */
2712 first_time_insn_init (insn_t insn
)
2714 return INSN_LIVE (insn
) == NULL
;
2717 /* Hash an entry in a transformed_insns hashtable. */
2719 hash_transformed_insns (const void *p
)
2721 return VINSN_HASH_RTX (((const struct transformed_insns
*) p
)->vinsn_old
);
2724 /* Compare the entries in a transformed_insns hashtable. */
2726 eq_transformed_insns (const void *p
, const void *q
)
2728 rtx i1
= VINSN_INSN_RTX (((const struct transformed_insns
*) p
)->vinsn_old
);
2729 rtx i2
= VINSN_INSN_RTX (((const struct transformed_insns
*) q
)->vinsn_old
);
2731 if (INSN_UID (i1
) == INSN_UID (i2
))
2733 return rtx_equal_p (PATTERN (i1
), PATTERN (i2
));
2736 /* Free an entry in a transformed_insns hashtable. */
2738 free_transformed_insns (void *p
)
2740 struct transformed_insns
*pti
= (struct transformed_insns
*) p
;
2742 vinsn_detach (pti
->vinsn_old
);
2743 vinsn_detach (pti
->vinsn_new
);
2747 /* Init the s_i_d data for INSN which should be inited just once, when
2748 we first see the insn. */
2750 init_first_time_insn_data (insn_t insn
)
2752 /* This should not be set if this is the first time we init data for
2754 gcc_assert (first_time_insn_init (insn
));
2756 /* These are needed for nops too. */
2757 INSN_LIVE (insn
) = get_regset_from_pool ();
2758 INSN_LIVE_VALID_P (insn
) = false;
2760 if (!INSN_NOP_P (insn
))
2762 INSN_ANALYZED_DEPS (insn
) = BITMAP_ALLOC (NULL
);
2763 INSN_FOUND_DEPS (insn
) = BITMAP_ALLOC (NULL
);
2764 INSN_TRANSFORMED_INSNS (insn
)
2765 = htab_create (16, hash_transformed_insns
,
2766 eq_transformed_insns
, free_transformed_insns
);
2767 init_deps (&INSN_DEPS_CONTEXT (insn
), true);
2771 /* Free almost all above data for INSN that is scheduled already.
2772 Used for extra-large basic blocks. */
2774 free_data_for_scheduled_insn (insn_t insn
)
2776 gcc_assert (! first_time_insn_init (insn
));
2778 if (! INSN_ANALYZED_DEPS (insn
))
2781 BITMAP_FREE (INSN_ANALYZED_DEPS (insn
));
2782 BITMAP_FREE (INSN_FOUND_DEPS (insn
));
2783 htab_delete (INSN_TRANSFORMED_INSNS (insn
));
2785 /* This is allocated only for bookkeeping insns. */
2786 if (INSN_ORIGINATORS (insn
))
2787 BITMAP_FREE (INSN_ORIGINATORS (insn
));
2788 free_deps (&INSN_DEPS_CONTEXT (insn
));
2790 INSN_ANALYZED_DEPS (insn
) = NULL
;
2792 /* Clear the readonly flag so we would ICE when trying to recalculate
2793 the deps context (as we believe that it should not happen). */
2794 (&INSN_DEPS_CONTEXT (insn
))->readonly
= 0;
2797 /* Free the same data as above for INSN. */
2799 free_first_time_insn_data (insn_t insn
)
2801 gcc_assert (! first_time_insn_init (insn
));
2803 free_data_for_scheduled_insn (insn
);
2804 return_regset_to_pool (INSN_LIVE (insn
));
2805 INSN_LIVE (insn
) = NULL
;
2806 INSN_LIVE_VALID_P (insn
) = false;
2809 /* Initialize region-scope data structures for basic blocks. */
2811 init_global_and_expr_for_bb (basic_block bb
)
2813 if (sel_bb_empty_p (bb
))
2816 invalidate_av_set (bb
);
2819 /* Data for global dependency analysis (to initialize CANT_MOVE and
2823 /* Previous insn. */
2827 /* Determine if INSN is in the sched_group, is an asm or should not be
2828 cloned. After that initialize its expr. */
2830 init_global_and_expr_for_insn (insn_t insn
)
2835 if (NOTE_INSN_BASIC_BLOCK_P (insn
))
2837 init_global_data
.prev_insn
= NULL_RTX
;
2841 gcc_assert (INSN_P (insn
));
2843 if (SCHED_GROUP_P (insn
))
2844 /* Setup a sched_group. */
2846 insn_t prev_insn
= init_global_data
.prev_insn
;
2849 INSN_SCHED_NEXT (prev_insn
) = insn
;
2851 init_global_data
.prev_insn
= insn
;
2854 init_global_data
.prev_insn
= NULL_RTX
;
2856 if (GET_CODE (PATTERN (insn
)) == ASM_INPUT
2857 || asm_noperands (PATTERN (insn
)) >= 0)
2858 /* Mark INSN as an asm. */
2859 INSN_ASM_P (insn
) = true;
2862 bool force_unique_p
;
2865 /* Certain instructions cannot be cloned, and frame related insns and
2866 the insn adjacent to NOTE_INSN_EPILOGUE_BEG cannot be moved out of
2868 if (prologue_epilogue_contains (insn
))
2870 if (RTX_FRAME_RELATED_P (insn
))
2871 CANT_MOVE (insn
) = 1;
2875 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
2876 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
2877 && ((enum insn_note
) INTVAL (XEXP (note
, 0))
2878 == NOTE_INSN_EPILOGUE_BEG
))
2880 CANT_MOVE (insn
) = 1;
2884 force_unique_p
= true;
2887 if (CANT_MOVE (insn
)
2888 || INSN_ASM_P (insn
)
2889 || SCHED_GROUP_P (insn
)
2890 /* Exception handling insns are always unique. */
2891 || (cfun
->can_throw_non_call_exceptions
&& can_throw_internal (insn
))
2892 /* TRAP_IF though have an INSN code is control_flow_insn_p (). */
2893 || control_flow_insn_p (insn
))
2894 force_unique_p
= true;
2896 force_unique_p
= false;
2898 if (targetm
.sched
.get_insn_spec_ds
)
2900 spec_done_ds
= targetm
.sched
.get_insn_spec_ds (insn
);
2901 spec_done_ds
= ds_get_max_dep_weak (spec_done_ds
);
2906 /* Initialize INSN's expr. */
2907 init_expr (INSN_EXPR (insn
), vinsn_create (insn
, force_unique_p
), 0,
2908 REG_BR_PROB_BASE
, INSN_PRIORITY (insn
), 0, BLOCK_NUM (insn
),
2909 spec_done_ds
, 0, 0, NULL
, true, false, false, false,
2913 init_first_time_insn_data (insn
);
2916 /* Scan the region and initialize instruction data for basic blocks BBS. */
2918 sel_init_global_and_expr (bb_vec_t bbs
)
2920 /* ??? It would be nice to implement push / pop scheme for sched_infos. */
2921 const struct sched_scan_info_def ssi
=
2923 NULL
, /* extend_bb */
2924 init_global_and_expr_for_bb
, /* init_bb */
2925 extend_insn_data
, /* extend_insn */
2926 init_global_and_expr_for_insn
/* init_insn */
2929 sched_scan (&ssi
, bbs
, NULL
, NULL
, NULL
);
2932 /* Finalize region-scope data structures for basic blocks. */
2934 finish_global_and_expr_for_bb (basic_block bb
)
2936 av_set_clear (&BB_AV_SET (bb
));
2937 BB_AV_LEVEL (bb
) = 0;
2940 /* Finalize INSN's data. */
2942 finish_global_and_expr_insn (insn_t insn
)
2944 if (LABEL_P (insn
) || NOTE_INSN_BASIC_BLOCK_P (insn
))
2947 gcc_assert (INSN_P (insn
));
2949 if (INSN_LUID (insn
) > 0)
2951 free_first_time_insn_data (insn
);
2952 INSN_WS_LEVEL (insn
) = 0;
2953 CANT_MOVE (insn
) = 0;
2955 /* We can no longer assert this, as vinsns of this insn could be
2956 easily live in other insn's caches. This should be changed to
2957 a counter-like approach among all vinsns. */
2958 gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn
)) == 1);
2959 clear_expr (INSN_EXPR (insn
));
2963 /* Finalize per instruction data for the whole region. */
2965 sel_finish_global_and_expr (void)
2971 bbs
= VEC_alloc (basic_block
, heap
, current_nr_blocks
);
2973 for (i
= 0; i
< current_nr_blocks
; i
++)
2974 VEC_quick_push (basic_block
, bbs
, BASIC_BLOCK (BB_TO_BLOCK (i
)));
2976 /* Clear AV_SETs and INSN_EXPRs. */
2978 const struct sched_scan_info_def ssi
=
2980 NULL
, /* extend_bb */
2981 finish_global_and_expr_for_bb
, /* init_bb */
2982 NULL
, /* extend_insn */
2983 finish_global_and_expr_insn
/* init_insn */
2986 sched_scan (&ssi
, bbs
, NULL
, NULL
, NULL
);
2989 VEC_free (basic_block
, heap
, bbs
);
2996 /* In the below hooks, we merely calculate whether or not a dependence
2997 exists, and in what part of insn. However, we will need more data
2998 when we'll start caching dependence requests. */
3000 /* Container to hold information for dependency analysis. */
3005 /* A variable to track which part of rtx we are scanning in
3006 sched-deps.c: sched_analyze_insn (). */
3009 /* Current producer. */
3012 /* Current consumer. */
3015 /* Is SEL_DEPS_HAS_DEP_P[DEPS_IN_X] is true, then X has a dependence.
3016 X is from { INSN, LHS, RHS }. */
3017 ds_t has_dep_p
[DEPS_IN_NOWHERE
];
3018 } has_dependence_data
;
3020 /* Start analyzing dependencies of INSN. */
3022 has_dependence_start_insn (insn_t insn ATTRIBUTE_UNUSED
)
3024 gcc_assert (has_dependence_data
.where
== DEPS_IN_NOWHERE
);
3026 has_dependence_data
.where
= DEPS_IN_INSN
;
3029 /* Finish analyzing dependencies of an insn. */
3031 has_dependence_finish_insn (void)
3033 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3035 has_dependence_data
.where
= DEPS_IN_NOWHERE
;
3038 /* Start analyzing dependencies of LHS. */
3040 has_dependence_start_lhs (rtx lhs ATTRIBUTE_UNUSED
)
3042 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3044 if (VINSN_LHS (has_dependence_data
.con
) != NULL
)
3045 has_dependence_data
.where
= DEPS_IN_LHS
;
3048 /* Finish analyzing dependencies of an lhs. */
3050 has_dependence_finish_lhs (void)
3052 has_dependence_data
.where
= DEPS_IN_INSN
;
3055 /* Start analyzing dependencies of RHS. */
3057 has_dependence_start_rhs (rtx rhs ATTRIBUTE_UNUSED
)
3059 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3061 if (VINSN_RHS (has_dependence_data
.con
) != NULL
)
3062 has_dependence_data
.where
= DEPS_IN_RHS
;
3065 /* Start analyzing dependencies of an rhs. */
3067 has_dependence_finish_rhs (void)
3069 gcc_assert (has_dependence_data
.where
== DEPS_IN_RHS
3070 || has_dependence_data
.where
== DEPS_IN_INSN
);
3072 has_dependence_data
.where
= DEPS_IN_INSN
;
3075 /* Note a set of REGNO. */
3077 has_dependence_note_reg_set (int regno
)
3079 struct deps_reg
*reg_last
= &has_dependence_data
.dc
->reg_last
[regno
];
3081 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3083 (has_dependence_data
.con
)))
3085 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3087 if (reg_last
->sets
!= NULL
3088 || reg_last
->clobbers
!= NULL
)
3089 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_OUTPUT
;
3092 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_ANTI
;
3096 /* Note a clobber of REGNO. */
3098 has_dependence_note_reg_clobber (int regno
)
3100 struct deps_reg
*reg_last
= &has_dependence_data
.dc
->reg_last
[regno
];
3102 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3104 (has_dependence_data
.con
)))
3106 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3109 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_OUTPUT
;
3112 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_ANTI
;
3116 /* Note a use of REGNO. */
3118 has_dependence_note_reg_use (int regno
)
3120 struct deps_reg
*reg_last
= &has_dependence_data
.dc
->reg_last
[regno
];
3122 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3124 (has_dependence_data
.con
)))
3126 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3129 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_TRUE
;
3131 if (reg_last
->clobbers
)
3132 *dsp
= (*dsp
& ~SPECULATIVE
) | DEP_ANTI
;
3134 /* Handle BE_IN_SPEC. */
3137 ds_t pro_spec_checked_ds
;
3139 pro_spec_checked_ds
= INSN_SPEC_CHECKED_DS (has_dependence_data
.pro
);
3140 pro_spec_checked_ds
= ds_get_max_dep_weak (pro_spec_checked_ds
);
3142 if (pro_spec_checked_ds
!= 0)
3143 /* Merge BE_IN_SPEC bits into *DSP. */
3144 *dsp
= ds_full_merge (*dsp
, pro_spec_checked_ds
,
3145 NULL_RTX
, NULL_RTX
);
3150 /* Note a memory dependence. */
3152 has_dependence_note_mem_dep (rtx mem ATTRIBUTE_UNUSED
,
3153 rtx pending_mem ATTRIBUTE_UNUSED
,
3154 insn_t pending_insn ATTRIBUTE_UNUSED
,
3155 ds_t ds ATTRIBUTE_UNUSED
)
3157 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3158 VINSN_INSN_RTX (has_dependence_data
.con
)))
3160 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3162 *dsp
= ds_full_merge (ds
, *dsp
, pending_mem
, mem
);
3166 /* Note a dependence. */
3168 has_dependence_note_dep (insn_t pro ATTRIBUTE_UNUSED
,
3169 ds_t ds ATTRIBUTE_UNUSED
)
3171 if (!sched_insns_conditions_mutex_p (has_dependence_data
.pro
,
3172 VINSN_INSN_RTX (has_dependence_data
.con
)))
3174 ds_t
*dsp
= &has_dependence_data
.has_dep_p
[has_dependence_data
.where
];
3176 *dsp
= ds_full_merge (ds
, *dsp
, NULL_RTX
, NULL_RTX
);
3180 /* Mark the insn as having a hard dependence that prevents speculation. */
3182 sel_mark_hard_insn (rtx insn
)
3186 /* Only work when we're in has_dependence_p mode.
3187 ??? This is a hack, this should actually be a hook. */
3188 if (!has_dependence_data
.dc
|| !has_dependence_data
.pro
)
3191 gcc_assert (insn
== VINSN_INSN_RTX (has_dependence_data
.con
));
3192 gcc_assert (has_dependence_data
.where
== DEPS_IN_INSN
);
3194 for (i
= 0; i
< DEPS_IN_NOWHERE
; i
++)
3195 has_dependence_data
.has_dep_p
[i
] &= ~SPECULATIVE
;
3198 /* This structure holds the hooks for the dependency analysis used when
3199 actually processing dependencies in the scheduler. */
3200 static struct sched_deps_info_def has_dependence_sched_deps_info
;
3202 /* This initializes most of the fields of the above structure. */
3203 static const struct sched_deps_info_def const_has_dependence_sched_deps_info
=
3207 has_dependence_start_insn
,
3208 has_dependence_finish_insn
,
3209 has_dependence_start_lhs
,
3210 has_dependence_finish_lhs
,
3211 has_dependence_start_rhs
,
3212 has_dependence_finish_rhs
,
3213 has_dependence_note_reg_set
,
3214 has_dependence_note_reg_clobber
,
3215 has_dependence_note_reg_use
,
3216 has_dependence_note_mem_dep
,
3217 has_dependence_note_dep
,
3220 0, /* use_deps_list */
3221 0 /* generate_spec_deps */
3224 /* Initialize has_dependence_sched_deps_info with extra spec field. */
3226 setup_has_dependence_sched_deps_info (void)
3228 memcpy (&has_dependence_sched_deps_info
,
3229 &const_has_dependence_sched_deps_info
,
3230 sizeof (has_dependence_sched_deps_info
));
3232 if (spec_info
!= NULL
)
3233 has_dependence_sched_deps_info
.generate_spec_deps
= 1;
3235 sched_deps_info
= &has_dependence_sched_deps_info
;
3238 /* Remove all dependences found and recorded in has_dependence_data array. */
3240 sel_clear_has_dependence (void)
3244 for (i
= 0; i
< DEPS_IN_NOWHERE
; i
++)
3245 has_dependence_data
.has_dep_p
[i
] = 0;
3248 /* Return nonzero if EXPR has is dependent upon PRED. Return the pointer
3249 to the dependence information array in HAS_DEP_PP. */
3251 has_dependence_p (expr_t expr
, insn_t pred
, ds_t
**has_dep_pp
)
3255 struct deps_desc
*dc
;
3257 if (INSN_SIMPLEJUMP_P (pred
))
3258 /* Unconditional jump is just a transfer of control flow.
3262 dc
= &INSN_DEPS_CONTEXT (pred
);
3264 /* We init this field lazily. */
3265 if (dc
->reg_last
== NULL
)
3266 init_deps_reg_last (dc
);
3270 has_dependence_data
.pro
= NULL
;
3271 /* Initialize empty dep context with information about PRED. */
3272 advance_deps_context (dc
, pred
);
3276 has_dependence_data
.where
= DEPS_IN_NOWHERE
;
3277 has_dependence_data
.pro
= pred
;
3278 has_dependence_data
.con
= EXPR_VINSN (expr
);
3279 has_dependence_data
.dc
= dc
;
3281 sel_clear_has_dependence ();
3283 /* Now catch all dependencies that would be generated between PRED and
3285 setup_has_dependence_sched_deps_info ();
3286 deps_analyze_insn (dc
, EXPR_INSN_RTX (expr
));
3287 has_dependence_data
.dc
= NULL
;
3289 /* When a barrier was found, set DEPS_IN_INSN bits. */
3290 if (dc
->last_reg_pending_barrier
== TRUE_BARRIER
)
3291 has_dependence_data
.has_dep_p
[DEPS_IN_INSN
] = DEP_TRUE
;
3292 else if (dc
->last_reg_pending_barrier
== MOVE_BARRIER
)
3293 has_dependence_data
.has_dep_p
[DEPS_IN_INSN
] = DEP_ANTI
;
3295 /* Do not allow stores to memory to move through checks. Currently
3296 we don't move this to sched-deps.c as the check doesn't have
3297 obvious places to which this dependence can be attached.
3298 FIMXE: this should go to a hook. */
3300 && MEM_P (EXPR_LHS (expr
))
3301 && sel_insn_is_speculation_check (pred
))
3302 has_dependence_data
.has_dep_p
[DEPS_IN_INSN
] = DEP_ANTI
;
3304 *has_dep_pp
= has_dependence_data
.has_dep_p
;
3306 for (i
= 0; i
< DEPS_IN_NOWHERE
; i
++)
3307 ds
= ds_full_merge (ds
, has_dependence_data
.has_dep_p
[i
],
3308 NULL_RTX
, NULL_RTX
);
3314 /* Dependence hooks implementation that checks dependence latency constraints
3315 on the insns being scheduled. The entry point for these routines is
3316 tick_check_p predicate. */
3320 /* An expr we are currently checking. */
3323 /* A minimal cycle for its scheduling. */
3326 /* Whether we have seen a true dependence while checking. */
3327 bool seen_true_dep_p
;
3330 /* Update minimal scheduling cycle for tick_check_insn given that it depends
3331 on PRO with status DS and weight DW. */
3333 tick_check_dep_with_dw (insn_t pro_insn
, ds_t ds
, dw_t dw
)
3335 expr_t con_expr
= tick_check_data
.expr
;
3336 insn_t con_insn
= EXPR_INSN_RTX (con_expr
);
3338 if (con_insn
!= pro_insn
)
3343 if (/* PROducer was removed from above due to pipelining. */
3344 !INSN_IN_STREAM_P (pro_insn
)
3345 /* Or PROducer was originally on the next iteration regarding the
3347 || (INSN_SCHED_TIMES (pro_insn
)
3348 - EXPR_SCHED_TIMES (con_expr
)) > 1)
3349 /* Don't count this dependence. */
3353 if (dt
== REG_DEP_TRUE
)
3354 tick_check_data
.seen_true_dep_p
= true;
3356 gcc_assert (INSN_SCHED_CYCLE (pro_insn
) > 0);
3359 dep_def _dep
, *dep
= &_dep
;
3361 init_dep (dep
, pro_insn
, con_insn
, dt
);
3363 tick
= INSN_SCHED_CYCLE (pro_insn
) + dep_cost_1 (dep
, dw
);
3366 /* When there are several kinds of dependencies between pro and con,
3367 only REG_DEP_TRUE should be taken into account. */
3368 if (tick
> tick_check_data
.cycle
3369 && (dt
== REG_DEP_TRUE
|| !tick_check_data
.seen_true_dep_p
))
3370 tick_check_data
.cycle
= tick
;
3374 /* An implementation of note_dep hook. */
3376 tick_check_note_dep (insn_t pro
, ds_t ds
)
3378 tick_check_dep_with_dw (pro
, ds
, 0);
3381 /* An implementation of note_mem_dep hook. */
3383 tick_check_note_mem_dep (rtx mem1
, rtx mem2
, insn_t pro
, ds_t ds
)
3387 dw
= (ds_to_dt (ds
) == REG_DEP_TRUE
3388 ? estimate_dep_weak (mem1
, mem2
)
3391 tick_check_dep_with_dw (pro
, ds
, dw
);
3394 /* This structure contains hooks for dependence analysis used when determining
3395 whether an insn is ready for scheduling. */
3396 static struct sched_deps_info_def tick_check_sched_deps_info
=
3407 haifa_note_reg_clobber
,
3409 tick_check_note_mem_dep
,
3410 tick_check_note_dep
,
3415 /* Estimate number of cycles from the current cycle of FENCE until EXPR can be
3416 scheduled. Return 0 if all data from producers in DC is ready. */
3418 tick_check_p (expr_t expr
, deps_t dc
, fence_t fence
)
3421 /* Initialize variables. */
3422 tick_check_data
.expr
= expr
;
3423 tick_check_data
.cycle
= 0;
3424 tick_check_data
.seen_true_dep_p
= false;
3425 sched_deps_info
= &tick_check_sched_deps_info
;
3427 gcc_assert (!dc
->readonly
);
3429 deps_analyze_insn (dc
, EXPR_INSN_RTX (expr
));
3432 cycles_left
= tick_check_data
.cycle
- FENCE_CYCLE (fence
);
3434 return cycles_left
>= 0 ? cycles_left
: 0;
3438 /* Functions to work with insns. */
3440 /* Returns true if LHS of INSN is the same as DEST of an insn
3443 lhs_of_insn_equals_to_dest_p (insn_t insn
, rtx dest
)
3445 rtx lhs
= INSN_LHS (insn
);
3447 if (lhs
== NULL
|| dest
== NULL
)
3450 return rtx_equal_p (lhs
, dest
);
3453 /* Return s_i_d entry of INSN. Callable from debugger. */
3455 insn_sid (insn_t insn
)
3460 /* True when INSN is a speculative check. We can tell this by looking
3461 at the data structures of the selective scheduler, not by examining
3464 sel_insn_is_speculation_check (rtx insn
)
3466 return s_i_d
&& !! INSN_SPEC_CHECKED_DS (insn
);
3469 /* Extracts machine mode MODE and destination location DST_LOC
3472 get_dest_and_mode (rtx insn
, rtx
*dst_loc
, enum machine_mode
*mode
)
3474 rtx pat
= PATTERN (insn
);
3476 gcc_assert (dst_loc
);
3477 gcc_assert (GET_CODE (pat
) == SET
);
3479 *dst_loc
= SET_DEST (pat
);
3481 gcc_assert (*dst_loc
);
3482 gcc_assert (MEM_P (*dst_loc
) || REG_P (*dst_loc
));
3485 *mode
= GET_MODE (*dst_loc
);
3488 /* Returns true when moving through JUMP will result in bookkeeping
3491 bookkeeping_can_be_created_if_moved_through_p (insn_t jump
)
3496 FOR_EACH_SUCC (succ
, si
, jump
)
3497 if (sel_num_cfg_preds_gt_1 (succ
))
3503 /* Return 'true' if INSN is the only one in its basic block. */
3505 insn_is_the_only_one_in_bb_p (insn_t insn
)
3507 return sel_bb_head_p (insn
) && sel_bb_end_p (insn
);
3510 #ifdef ENABLE_CHECKING
3511 /* Check that the region we're scheduling still has at most one
3514 verify_backedges (void)
3522 for (i
= 0; i
< current_nr_blocks
; i
++)
3523 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (BB_TO_BLOCK (i
))->succs
)
3524 if (in_current_region_p (e
->dest
)
3525 && BLOCK_TO_BB (e
->dest
->index
) < i
)
3528 gcc_assert (n
<= 1);
3534 /* Functions to work with control flow. */
3536 /* Recompute BLOCK_TO_BB and BB_FOR_BLOCK for current region so that blocks
3537 are sorted in topological order (it might have been invalidated by
3538 redirecting an edge). */
3540 sel_recompute_toporder (void)
3543 int *postorder
, n_blocks
;
3545 postorder
= XALLOCAVEC (int, n_basic_blocks
);
3546 n_blocks
= post_order_compute (postorder
, false, false);
3548 rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
3549 for (n
= 0, i
= n_blocks
- 1; i
>= 0; i
--)
3550 if (CONTAINING_RGN (postorder
[i
]) == rgn
)
3552 BLOCK_TO_BB (postorder
[i
]) = n
;
3553 BB_TO_BLOCK (n
) = postorder
[i
];
3557 /* Assert that we updated info for all blocks. We may miss some blocks if
3558 this function is called when redirecting an edge made a block
3559 unreachable, but that block is not deleted yet. */
3560 gcc_assert (n
== RGN_NR_BLOCKS (rgn
));
3563 /* Tidy the possibly empty block BB. */
3565 maybe_tidy_empty_bb (basic_block bb
, bool recompute_toporder_p
)
3567 basic_block succ_bb
, pred_bb
;
3572 /* Keep empty bb only if this block immediately precedes EXIT and
3573 has incoming non-fallthrough edge, or it has no predecessors or
3574 successors. Otherwise remove it. */
3575 if (!sel_bb_empty_p (bb
)
3576 || (single_succ_p (bb
)
3577 && single_succ (bb
) == EXIT_BLOCK_PTR
3578 && (!single_pred_p (bb
)
3579 || !(single_pred_edge (bb
)->flags
& EDGE_FALLTHRU
)))
3580 || EDGE_COUNT (bb
->preds
) == 0
3581 || EDGE_COUNT (bb
->succs
) == 0)
3584 /* Do not attempt to redirect complex edges. */
3585 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3586 if (e
->flags
& EDGE_COMPLEX
)
3589 free_data_sets (bb
);
3591 /* Do not delete BB if it has more than one successor.
3592 That can occur when we moving a jump. */
3593 if (!single_succ_p (bb
))
3595 gcc_assert (can_merge_blocks_p (bb
->prev_bb
, bb
));
3596 sel_merge_blocks (bb
->prev_bb
, bb
);
3600 succ_bb
= single_succ (bb
);
3604 /* Redirect all non-fallthru edges to the next bb. */
3609 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3613 if (!(e
->flags
& EDGE_FALLTHRU
))
3615 recompute_toporder_p
|= sel_redirect_edge_and_branch (e
, succ_bb
);
3622 if (can_merge_blocks_p (bb
->prev_bb
, bb
))
3623 sel_merge_blocks (bb
->prev_bb
, bb
);
3626 /* This is a block without fallthru predecessor. Just delete it. */
3627 gcc_assert (pred_bb
!= NULL
);
3629 if (in_current_region_p (pred_bb
))
3630 move_bb_info (pred_bb
, bb
);
3631 remove_empty_bb (bb
, true);
3634 if (recompute_toporder_p
)
3635 sel_recompute_toporder ();
3637 #ifdef ENABLE_CHECKING
3638 verify_backedges ();
3644 /* Tidy the control flow after we have removed original insn from
3645 XBB. Return true if we have removed some blocks. When FULL_TIDYING
3646 is true, also try to optimize control flow on non-empty blocks. */
3648 tidy_control_flow (basic_block xbb
, bool full_tidying
)
3650 bool changed
= true;
3653 /* First check whether XBB is empty. */
3654 changed
= maybe_tidy_empty_bb (xbb
, false);
3655 if (changed
|| !full_tidying
)
3658 /* Check if there is a unnecessary jump after insn left. */
3659 if (jump_leads_only_to_bb_p (BB_END (xbb
), xbb
->next_bb
)
3660 && INSN_SCHED_TIMES (BB_END (xbb
)) == 0
3661 && !IN_CURRENT_FENCE_P (BB_END (xbb
)))
3663 if (sel_remove_insn (BB_END (xbb
), false, false))
3665 tidy_fallthru_edge (EDGE_SUCC (xbb
, 0));
3668 first
= sel_bb_head (xbb
);
3669 last
= sel_bb_end (xbb
);
3670 if (MAY_HAVE_DEBUG_INSNS
)
3672 if (first
!= last
&& DEBUG_INSN_P (first
))
3674 first
= NEXT_INSN (first
);
3675 while (first
!= last
&& (DEBUG_INSN_P (first
) || NOTE_P (first
)));
3677 if (first
!= last
&& DEBUG_INSN_P (last
))
3679 last
= PREV_INSN (last
);
3680 while (first
!= last
&& (DEBUG_INSN_P (last
) || NOTE_P (last
)));
3682 /* Check if there is an unnecessary jump in previous basic block leading
3683 to next basic block left after removing INSN from stream.
3684 If it is so, remove that jump and redirect edge to current
3685 basic block (where there was INSN before deletion). This way
3686 when NOP will be deleted several instructions later with its
3687 basic block we will not get a jump to next instruction, which
3690 && !sel_bb_empty_p (xbb
)
3691 && INSN_NOP_P (last
)
3692 /* Flow goes fallthru from current block to the next. */
3693 && EDGE_COUNT (xbb
->succs
) == 1
3694 && (EDGE_SUCC (xbb
, 0)->flags
& EDGE_FALLTHRU
)
3695 /* When successor is an EXIT block, it may not be the next block. */
3696 && single_succ (xbb
) != EXIT_BLOCK_PTR
3697 /* And unconditional jump in previous basic block leads to
3698 next basic block of XBB and this jump can be safely removed. */
3699 && in_current_region_p (xbb
->prev_bb
)
3700 && jump_leads_only_to_bb_p (BB_END (xbb
->prev_bb
), xbb
->next_bb
)
3701 && INSN_SCHED_TIMES (BB_END (xbb
->prev_bb
)) == 0
3702 /* Also this jump is not at the scheduling boundary. */
3703 && !IN_CURRENT_FENCE_P (BB_END (xbb
->prev_bb
)))
3705 bool recompute_toporder_p
;
3706 /* Clear data structures of jump - jump itself will be removed
3707 by sel_redirect_edge_and_branch. */
3708 clear_expr (INSN_EXPR (BB_END (xbb
->prev_bb
)));
3709 recompute_toporder_p
3710 = sel_redirect_edge_and_branch (EDGE_SUCC (xbb
->prev_bb
, 0), xbb
);
3712 gcc_assert (EDGE_SUCC (xbb
->prev_bb
, 0)->flags
& EDGE_FALLTHRU
);
3714 /* It can turn out that after removing unused jump, basic block
3715 that contained that jump, becomes empty too. In such case
3717 if (sel_bb_empty_p (xbb
->prev_bb
))
3718 changed
= maybe_tidy_empty_bb (xbb
->prev_bb
, recompute_toporder_p
);
3719 else if (recompute_toporder_p
)
3720 sel_recompute_toporder ();
3725 /* Purge meaningless empty blocks in the middle of a region. */
3727 purge_empty_blocks (void)
3729 /* Do not attempt to delete preheader. */
3730 int i
= sel_is_loop_preheader_p (BASIC_BLOCK (BB_TO_BLOCK (0))) ? 1 : 0;
3732 while (i
< current_nr_blocks
)
3734 basic_block b
= BASIC_BLOCK (BB_TO_BLOCK (i
));
3736 if (maybe_tidy_empty_bb (b
, false))
3743 /* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true,
3744 do not delete insn's data, because it will be later re-emitted.
3745 Return true if we have removed some blocks afterwards. */
3747 sel_remove_insn (insn_t insn
, bool only_disconnect
, bool full_tidying
)
3749 basic_block bb
= BLOCK_FOR_INSN (insn
);
3751 gcc_assert (INSN_IN_STREAM_P (insn
));
3753 if (DEBUG_INSN_P (insn
) && BB_AV_SET_VALID_P (bb
))
3758 /* When we remove a debug insn that is head of a BB, it remains
3759 in the AV_SET of the block, but it shouldn't. */
3760 FOR_EACH_EXPR_1 (expr
, i
, &BB_AV_SET (bb
))
3761 if (EXPR_INSN_RTX (expr
) == insn
)
3763 av_set_iter_remove (&i
);
3768 if (only_disconnect
)
3770 insn_t prev
= PREV_INSN (insn
);
3771 insn_t next
= NEXT_INSN (insn
);
3772 basic_block bb
= BLOCK_FOR_INSN (insn
);
3774 NEXT_INSN (prev
) = next
;
3775 PREV_INSN (next
) = prev
;
3777 if (BB_HEAD (bb
) == insn
)
3779 gcc_assert (BLOCK_FOR_INSN (prev
) == bb
);
3780 BB_HEAD (bb
) = prev
;
3782 if (BB_END (bb
) == insn
)
3788 clear_expr (INSN_EXPR (insn
));
3791 /* It is necessary to null this fields before calling add_insn (). */
3792 PREV_INSN (insn
) = NULL_RTX
;
3793 NEXT_INSN (insn
) = NULL_RTX
;
3795 return tidy_control_flow (bb
, full_tidying
);
3798 /* Estimate number of the insns in BB. */
3800 sel_estimate_number_of_insns (basic_block bb
)
3803 insn_t insn
= NEXT_INSN (BB_HEAD (bb
)), next_tail
= NEXT_INSN (BB_END (bb
));
3805 for (; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
3806 if (NONDEBUG_INSN_P (insn
))
3812 /* We don't need separate luids for notes or labels. */
3814 sel_luid_for_non_insn (rtx x
)
3816 gcc_assert (NOTE_P (x
) || LABEL_P (x
));
3821 /* Return seqno of the only predecessor of INSN. */
3823 get_seqno_of_a_pred (insn_t insn
)
3827 gcc_assert (INSN_SIMPLEJUMP_P (insn
));
3829 if (!sel_bb_head_p (insn
))
3830 seqno
= INSN_SEQNO (PREV_INSN (insn
));
3833 basic_block bb
= BLOCK_FOR_INSN (insn
);
3835 if (single_pred_p (bb
)
3836 && !in_current_region_p (single_pred (bb
)))
3838 /* We can have preds outside a region when splitting edges
3839 for pipelining of an outer loop. Use succ instead.
3840 There should be only one of them. */
3845 gcc_assert (flag_sel_sched_pipelining_outer_loops
3846 && current_loop_nest
);
3847 FOR_EACH_SUCC_1 (succ
, si
, insn
,
3848 SUCCS_NORMAL
| SUCCS_SKIP_TO_LOOP_EXITS
)
3854 gcc_assert (succ
!= NULL
);
3855 seqno
= INSN_SEQNO (succ
);
3862 cfg_preds (BLOCK_FOR_INSN (insn
), &preds
, &n
);
3863 gcc_assert (n
== 1);
3865 seqno
= INSN_SEQNO (preds
[0]);
3874 /* Find the proper seqno for inserting at INSN. Returns -1 if no predecessors
3875 with positive seqno exist. */
3877 get_seqno_by_preds (rtx insn
)
3879 basic_block bb
= BLOCK_FOR_INSN (insn
);
3880 rtx tmp
= insn
, head
= BB_HEAD (bb
);
3886 return INSN_SEQNO (tmp
);
3888 tmp
= PREV_INSN (tmp
);
3890 cfg_preds (bb
, &preds
, &n
);
3891 for (i
= 0, seqno
= -1; i
< n
; i
++)
3892 seqno
= MAX (seqno
, INSN_SEQNO (preds
[i
]));
3899 /* Extend pass-scope data structures for basic blocks. */
3901 sel_extend_global_bb_info (void)
3903 VEC_safe_grow_cleared (sel_global_bb_info_def
, heap
, sel_global_bb_info
,
3907 /* Extend region-scope data structures for basic blocks. */
3909 extend_region_bb_info (void)
3911 VEC_safe_grow_cleared (sel_region_bb_info_def
, heap
, sel_region_bb_info
,
3915 /* Extend all data structures to fit for all basic blocks. */
3917 extend_bb_info (void)
3919 sel_extend_global_bb_info ();
3920 extend_region_bb_info ();
3923 /* Finalize pass-scope data structures for basic blocks. */
3925 sel_finish_global_bb_info (void)
3927 VEC_free (sel_global_bb_info_def
, heap
, sel_global_bb_info
);
3930 /* Finalize region-scope data structures for basic blocks. */
3932 finish_region_bb_info (void)
3934 VEC_free (sel_region_bb_info_def
, heap
, sel_region_bb_info
);
3938 /* Data for each insn in current region. */
3939 VEC (sel_insn_data_def
, heap
) *s_i_d
= NULL
;
3941 /* A vector for the insns we've emitted. */
3942 static insn_vec_t new_insns
= NULL
;
3944 /* Extend data structures for insns from current region. */
3946 extend_insn_data (void)
3950 sched_extend_target ();
3951 sched_deps_init (false);
3953 /* Extend data structures for insns from current region. */
3954 reserve
= (sched_max_luid
+ 1
3955 - VEC_length (sel_insn_data_def
, s_i_d
));
3957 && ! VEC_space (sel_insn_data_def
, s_i_d
, reserve
))
3961 if (sched_max_luid
/ 2 > 1024)
3962 size
= sched_max_luid
+ 1024;
3964 size
= 3 * sched_max_luid
/ 2;
3967 VEC_safe_grow_cleared (sel_insn_data_def
, heap
, s_i_d
, size
);
3971 /* Finalize data structures for insns from current region. */
3977 /* Clear here all dependence contexts that may have left from insns that were
3978 removed during the scheduling. */
3979 for (i
= 0; i
< VEC_length (sel_insn_data_def
, s_i_d
); i
++)
3981 sel_insn_data_def
*sid_entry
= VEC_index (sel_insn_data_def
, s_i_d
, i
);
3983 if (sid_entry
->live
)
3984 return_regset_to_pool (sid_entry
->live
);
3985 if (sid_entry
->analyzed_deps
)
3987 BITMAP_FREE (sid_entry
->analyzed_deps
);
3988 BITMAP_FREE (sid_entry
->found_deps
);
3989 htab_delete (sid_entry
->transformed_insns
);
3990 free_deps (&sid_entry
->deps_context
);
3992 if (EXPR_VINSN (&sid_entry
->expr
))
3994 clear_expr (&sid_entry
->expr
);
3996 /* Also, clear CANT_MOVE bit here, because we really don't want it
3997 to be passed to the next region. */
3998 CANT_MOVE_BY_LUID (i
) = 0;
4002 VEC_free (sel_insn_data_def
, heap
, s_i_d
);
4005 /* A proxy to pass initialization data to init_insn (). */
4006 static sel_insn_data_def _insn_init_ssid
;
4007 static sel_insn_data_t insn_init_ssid
= &_insn_init_ssid
;
4009 /* If true create a new vinsn. Otherwise use the one from EXPR. */
4010 static bool insn_init_create_new_vinsn_p
;
4012 /* Set all necessary data for initialization of the new insn[s]. */
4014 set_insn_init (expr_t expr
, vinsn_t vi
, int seqno
)
4016 expr_t x
= &insn_init_ssid
->expr
;
4018 copy_expr_onside (x
, expr
);
4021 insn_init_create_new_vinsn_p
= false;
4022 change_vinsn_in_expr (x
, vi
);
4025 insn_init_create_new_vinsn_p
= true;
4027 insn_init_ssid
->seqno
= seqno
;
4031 /* Init data for INSN. */
4033 init_insn_data (insn_t insn
)
4036 sel_insn_data_t ssid
= insn_init_ssid
;
4038 /* The fields mentioned below are special and hence are not being
4039 propagated to the new insns. */
4040 gcc_assert (!ssid
->asm_p
&& ssid
->sched_next
== NULL
4041 && !ssid
->after_stall_p
&& ssid
->sched_cycle
== 0);
4042 gcc_assert (INSN_P (insn
) && INSN_LUID (insn
) > 0);
4044 expr
= INSN_EXPR (insn
);
4045 copy_expr (expr
, &ssid
->expr
);
4046 prepare_insn_expr (insn
, ssid
->seqno
);
4048 if (insn_init_create_new_vinsn_p
)
4049 change_vinsn_in_expr (expr
, vinsn_create (insn
, init_insn_force_unique_p
));
4051 if (first_time_insn_init (insn
))
4052 init_first_time_insn_data (insn
);
4055 /* This is used to initialize spurious jumps generated by
4056 sel_redirect_edge (). */
4058 init_simplejump_data (insn_t insn
)
4060 init_expr (INSN_EXPR (insn
), vinsn_create (insn
, false), 0,
4061 REG_BR_PROB_BASE
, 0, 0, 0, 0, 0, 0, NULL
, true, false, false,
4063 INSN_SEQNO (insn
) = get_seqno_of_a_pred (insn
);
4064 init_first_time_insn_data (insn
);
4067 /* Perform deferred initialization of insns. This is used to process
4068 a new jump that may be created by redirect_edge. */
4070 sel_init_new_insn (insn_t insn
, int flags
)
4072 /* We create data structures for bb when the first insn is emitted in it. */
4074 && INSN_IN_STREAM_P (insn
)
4075 && insn_is_the_only_one_in_bb_p (insn
))
4078 create_initial_data_sets (BLOCK_FOR_INSN (insn
));
4081 if (flags
& INSN_INIT_TODO_LUID
)
4082 sched_init_luids (NULL
, NULL
, NULL
, insn
);
4084 if (flags
& INSN_INIT_TODO_SSID
)
4086 extend_insn_data ();
4087 init_insn_data (insn
);
4088 clear_expr (&insn_init_ssid
->expr
);
4091 if (flags
& INSN_INIT_TODO_SIMPLEJUMP
)
4093 extend_insn_data ();
4094 init_simplejump_data (insn
);
4097 gcc_assert (CONTAINING_RGN (BLOCK_NUM (insn
))
4098 == CONTAINING_RGN (BB_TO_BLOCK (0)));
4102 /* Functions to init/finish work with lv sets. */
4104 /* Init BB_LV_SET of BB from DF_LR_IN set of BB. */
4106 init_lv_set (basic_block bb
)
4108 gcc_assert (!BB_LV_SET_VALID_P (bb
));
4110 BB_LV_SET (bb
) = get_regset_from_pool ();
4111 COPY_REG_SET (BB_LV_SET (bb
), DF_LR_IN (bb
));
4112 BB_LV_SET_VALID_P (bb
) = true;
4115 /* Copy liveness information to BB from FROM_BB. */
4117 copy_lv_set_from (basic_block bb
, basic_block from_bb
)
4119 gcc_assert (!BB_LV_SET_VALID_P (bb
));
4121 COPY_REG_SET (BB_LV_SET (bb
), BB_LV_SET (from_bb
));
4122 BB_LV_SET_VALID_P (bb
) = true;
4125 /* Initialize lv set of all bb headers. */
4131 /* Initialize of LV sets. */
4135 /* Don't forget EXIT_BLOCK. */
4136 init_lv_set (EXIT_BLOCK_PTR
);
4139 /* Release lv set of HEAD. */
4141 free_lv_set (basic_block bb
)
4143 gcc_assert (BB_LV_SET (bb
) != NULL
);
4145 return_regset_to_pool (BB_LV_SET (bb
));
4146 BB_LV_SET (bb
) = NULL
;
4147 BB_LV_SET_VALID_P (bb
) = false;
4150 /* Finalize lv sets of all bb headers. */
4156 /* Don't forget EXIT_BLOCK. */
4157 free_lv_set (EXIT_BLOCK_PTR
);
4165 /* Initialize an invalid AV_SET for BB.
4166 This set will be updated next time compute_av () process BB. */
4168 invalidate_av_set (basic_block bb
)
4170 gcc_assert (BB_AV_LEVEL (bb
) <= 0
4171 && BB_AV_SET (bb
) == NULL
);
4173 BB_AV_LEVEL (bb
) = -1;
4176 /* Create initial data sets for BB (they will be invalid). */
4178 create_initial_data_sets (basic_block bb
)
4181 BB_LV_SET_VALID_P (bb
) = false;
4183 BB_LV_SET (bb
) = get_regset_from_pool ();
4184 invalidate_av_set (bb
);
4187 /* Free av set of BB. */
4189 free_av_set (basic_block bb
)
4191 av_set_clear (&BB_AV_SET (bb
));
4192 BB_AV_LEVEL (bb
) = 0;
4195 /* Free data sets of BB. */
4197 free_data_sets (basic_block bb
)
4203 /* Exchange lv sets of TO and FROM. */
4205 exchange_lv_sets (basic_block to
, basic_block from
)
4208 regset to_lv_set
= BB_LV_SET (to
);
4210 BB_LV_SET (to
) = BB_LV_SET (from
);
4211 BB_LV_SET (from
) = to_lv_set
;
4215 bool to_lv_set_valid_p
= BB_LV_SET_VALID_P (to
);
4217 BB_LV_SET_VALID_P (to
) = BB_LV_SET_VALID_P (from
);
4218 BB_LV_SET_VALID_P (from
) = to_lv_set_valid_p
;
4223 /* Exchange av sets of TO and FROM. */
4225 exchange_av_sets (basic_block to
, basic_block from
)
4228 av_set_t to_av_set
= BB_AV_SET (to
);
4230 BB_AV_SET (to
) = BB_AV_SET (from
);
4231 BB_AV_SET (from
) = to_av_set
;
4235 int to_av_level
= BB_AV_LEVEL (to
);
4237 BB_AV_LEVEL (to
) = BB_AV_LEVEL (from
);
4238 BB_AV_LEVEL (from
) = to_av_level
;
4242 /* Exchange data sets of TO and FROM. */
4244 exchange_data_sets (basic_block to
, basic_block from
)
4246 exchange_lv_sets (to
, from
);
4247 exchange_av_sets (to
, from
);
4250 /* Copy data sets of FROM to TO. */
4252 copy_data_sets (basic_block to
, basic_block from
)
4254 gcc_assert (!BB_LV_SET_VALID_P (to
) && !BB_AV_SET_VALID_P (to
));
4255 gcc_assert (BB_AV_SET (to
) == NULL
);
4257 BB_AV_LEVEL (to
) = BB_AV_LEVEL (from
);
4258 BB_LV_SET_VALID_P (to
) = BB_LV_SET_VALID_P (from
);
4260 if (BB_AV_SET_VALID_P (from
))
4262 BB_AV_SET (to
) = av_set_copy (BB_AV_SET (from
));
4264 if (BB_LV_SET_VALID_P (from
))
4266 gcc_assert (BB_LV_SET (to
) != NULL
);
4267 COPY_REG_SET (BB_LV_SET (to
), BB_LV_SET (from
));
4271 /* Return an av set for INSN, if any. */
4273 get_av_set (insn_t insn
)
4277 gcc_assert (AV_SET_VALID_P (insn
));
4279 if (sel_bb_head_p (insn
))
4280 av_set
= BB_AV_SET (BLOCK_FOR_INSN (insn
));
4287 /* Implementation of AV_LEVEL () macro. Return AV_LEVEL () of INSN. */
4289 get_av_level (insn_t insn
)
4293 gcc_assert (INSN_P (insn
));
4295 if (sel_bb_head_p (insn
))
4296 av_level
= BB_AV_LEVEL (BLOCK_FOR_INSN (insn
));
4298 av_level
= INSN_WS_LEVEL (insn
);
4305 /* Variables to work with control-flow graph. */
4307 /* The basic block that already has been processed by the sched_data_update (),
4308 but hasn't been in sel_add_bb () yet. */
4309 static VEC (basic_block
, heap
) *last_added_blocks
= NULL
;
4311 /* A pool for allocating successor infos. */
4314 /* A stack for saving succs_info structures. */
4315 struct succs_info
*stack
;
4320 /* Top of the stack. */
4323 /* Maximal value of the top. */
4327 /* Functions to work with control-flow graph. */
4329 /* Return basic block note of BB. */
4331 sel_bb_head (basic_block bb
)
4335 if (bb
== EXIT_BLOCK_PTR
)
4337 gcc_assert (exit_insn
!= NULL_RTX
);
4344 note
= bb_note (bb
);
4345 head
= next_nonnote_insn (note
);
4347 if (head
&& (BARRIER_P (head
) || BLOCK_FOR_INSN (head
) != bb
))
4354 /* Return true if INSN is a basic block header. */
4356 sel_bb_head_p (insn_t insn
)
4358 return sel_bb_head (BLOCK_FOR_INSN (insn
)) == insn
;
4361 /* Return last insn of BB. */
4363 sel_bb_end (basic_block bb
)
4365 if (sel_bb_empty_p (bb
))
4368 gcc_assert (bb
!= EXIT_BLOCK_PTR
);
4373 /* Return true if INSN is the last insn in its basic block. */
4375 sel_bb_end_p (insn_t insn
)
4377 return insn
== sel_bb_end (BLOCK_FOR_INSN (insn
));
4380 /* Return true if BB consist of single NOTE_INSN_BASIC_BLOCK. */
4382 sel_bb_empty_p (basic_block bb
)
4384 return sel_bb_head (bb
) == NULL
;
4387 /* True when BB belongs to the current scheduling region. */
4389 in_current_region_p (basic_block bb
)
4391 if (bb
->index
< NUM_FIXED_BLOCKS
)
4394 return CONTAINING_RGN (bb
->index
) == CONTAINING_RGN (BB_TO_BLOCK (0));
4397 /* Return the block which is a fallthru bb of a conditional jump JUMP. */
4399 fallthru_bb_of_jump (rtx jump
)
4404 if (any_uncondjump_p (jump
))
4405 return single_succ (BLOCK_FOR_INSN (jump
));
4407 if (!any_condjump_p (jump
))
4410 /* A basic block that ends with a conditional jump may still have one successor
4411 (and be followed by a barrier), we are not interested. */
4412 if (single_succ_p (BLOCK_FOR_INSN (jump
)))
4415 return FALLTHRU_EDGE (BLOCK_FOR_INSN (jump
))->dest
;
4418 /* Remove all notes from BB. */
4420 init_bb (basic_block bb
)
4422 remove_notes (bb_note (bb
), BB_END (bb
));
4423 BB_NOTE_LIST (bb
) = note_list
;
4427 sel_init_bbs (bb_vec_t bbs
, basic_block bb
)
4429 const struct sched_scan_info_def ssi
=
4431 extend_bb_info
, /* extend_bb */
4432 init_bb
, /* init_bb */
4433 NULL
, /* extend_insn */
4434 NULL
/* init_insn */
4437 sched_scan (&ssi
, bbs
, bb
, new_insns
, NULL
);
4440 /* Restore notes for the whole region. */
4442 sel_restore_notes (void)
4447 for (bb
= 0; bb
< current_nr_blocks
; bb
++)
4449 basic_block first
, last
;
4451 first
= EBB_FIRST_BB (bb
);
4452 last
= EBB_LAST_BB (bb
)->next_bb
;
4456 note_list
= BB_NOTE_LIST (first
);
4457 restore_other_notes (NULL
, first
);
4458 BB_NOTE_LIST (first
) = NULL_RTX
;
4460 FOR_BB_INSNS (first
, insn
)
4461 if (NONDEBUG_INSN_P (insn
))
4462 reemit_notes (insn
);
4464 first
= first
->next_bb
;
4466 while (first
!= last
);
4470 /* Free per-bb data structures. */
4472 sel_finish_bbs (void)
4474 sel_restore_notes ();
4476 /* Remove current loop preheader from this loop. */
4477 if (current_loop_nest
)
4478 sel_remove_loop_preheader ();
4480 finish_region_bb_info ();
4483 /* Return true if INSN has a single successor of type FLAGS. */
4485 sel_insn_has_single_succ_p (insn_t insn
, int flags
)
4489 bool first_p
= true;
4491 FOR_EACH_SUCC_1 (succ
, si
, insn
, flags
)
4502 /* Allocate successor's info. */
4503 static struct succs_info
*
4504 alloc_succs_info (void)
4506 if (succs_info_pool
.top
== succs_info_pool
.max_top
)
4510 if (++succs_info_pool
.max_top
>= succs_info_pool
.size
)
4513 i
= ++succs_info_pool
.top
;
4514 succs_info_pool
.stack
[i
].succs_ok
= VEC_alloc (rtx
, heap
, 10);
4515 succs_info_pool
.stack
[i
].succs_other
= VEC_alloc (rtx
, heap
, 10);
4516 succs_info_pool
.stack
[i
].probs_ok
= VEC_alloc (int, heap
, 10);
4519 succs_info_pool
.top
++;
4521 return &succs_info_pool
.stack
[succs_info_pool
.top
];
4524 /* Free successor's info. */
4526 free_succs_info (struct succs_info
* sinfo
)
4528 gcc_assert (succs_info_pool
.top
>= 0
4529 && &succs_info_pool
.stack
[succs_info_pool
.top
] == sinfo
);
4530 succs_info_pool
.top
--;
4532 /* Clear stale info. */
4533 VEC_block_remove (rtx
, sinfo
->succs_ok
,
4534 0, VEC_length (rtx
, sinfo
->succs_ok
));
4535 VEC_block_remove (rtx
, sinfo
->succs_other
,
4536 0, VEC_length (rtx
, sinfo
->succs_other
));
4537 VEC_block_remove (int, sinfo
->probs_ok
,
4538 0, VEC_length (int, sinfo
->probs_ok
));
4539 sinfo
->all_prob
= 0;
4540 sinfo
->succs_ok_n
= 0;
4541 sinfo
->all_succs_n
= 0;
4544 /* Compute successor info for INSN. FLAGS are the flags passed
4545 to the FOR_EACH_SUCC_1 iterator. */
4547 compute_succs_info (insn_t insn
, short flags
)
4551 struct succs_info
*sinfo
= alloc_succs_info ();
4553 /* Traverse *all* successors and decide what to do with each. */
4554 FOR_EACH_SUCC_1 (succ
, si
, insn
, SUCCS_ALL
)
4556 /* FIXME: this doesn't work for skipping to loop exits, as we don't
4557 perform code motion through inner loops. */
4558 short current_flags
= si
.current_flags
& ~SUCCS_SKIP_TO_LOOP_EXITS
;
4560 if (current_flags
& flags
)
4562 VEC_safe_push (rtx
, heap
, sinfo
->succs_ok
, succ
);
4563 VEC_safe_push (int, heap
, sinfo
->probs_ok
,
4564 /* FIXME: Improve calculation when skipping
4565 inner loop to exits. */
4567 ? si
.e1
->probability
4568 : REG_BR_PROB_BASE
));
4569 sinfo
->succs_ok_n
++;
4572 VEC_safe_push (rtx
, heap
, sinfo
->succs_other
, succ
);
4574 /* Compute all_prob. */
4576 sinfo
->all_prob
= REG_BR_PROB_BASE
;
4578 sinfo
->all_prob
+= si
.e1
->probability
;
4580 sinfo
->all_succs_n
++;
4586 /* Return the predecessors of BB in PREDS and their number in N.
4587 Empty blocks are skipped. SIZE is used to allocate PREDS. */
4589 cfg_preds_1 (basic_block bb
, insn_t
**preds
, int *n
, int *size
)
4594 gcc_assert (BLOCK_TO_BB (bb
->index
) != 0);
4596 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4598 basic_block pred_bb
= e
->src
;
4599 insn_t bb_end
= BB_END (pred_bb
);
4601 if (!in_current_region_p (pred_bb
))
4603 gcc_assert (flag_sel_sched_pipelining_outer_loops
4604 && current_loop_nest
);
4608 if (sel_bb_empty_p (pred_bb
))
4609 cfg_preds_1 (pred_bb
, preds
, n
, size
);
4613 *preds
= XRESIZEVEC (insn_t
, *preds
,
4614 (*size
= 2 * *size
+ 1));
4615 (*preds
)[(*n
)++] = bb_end
;
4620 || (flag_sel_sched_pipelining_outer_loops
4621 && current_loop_nest
));
4624 /* Find all predecessors of BB and record them in PREDS and their number
4625 in N. Empty blocks are skipped, and only normal (forward in-region)
4626 edges are processed. */
4628 cfg_preds (basic_block bb
, insn_t
**preds
, int *n
)
4634 cfg_preds_1 (bb
, preds
, n
, &size
);
4637 /* Returns true if we are moving INSN through join point. */
4639 sel_num_cfg_preds_gt_1 (insn_t insn
)
4643 if (!sel_bb_head_p (insn
) || INSN_BB (insn
) == 0)
4646 bb
= BLOCK_FOR_INSN (insn
);
4650 if (EDGE_COUNT (bb
->preds
) > 1)
4653 gcc_assert (EDGE_PRED (bb
, 0)->dest
== bb
);
4654 bb
= EDGE_PRED (bb
, 0)->src
;
4656 if (!sel_bb_empty_p (bb
))
4663 /* Returns true when BB should be the end of an ebb. Adapted from the
4664 code in sched-ebb.c. */
4666 bb_ends_ebb_p (basic_block bb
)
4668 basic_block next_bb
= bb_next_bb (bb
);
4671 if (next_bb
== EXIT_BLOCK_PTR
4672 || bitmap_bit_p (forced_ebb_heads
, next_bb
->index
)
4673 || (LABEL_P (BB_HEAD (next_bb
))
4674 /* NB: LABEL_NUSES () is not maintained outside of jump.c.
4675 Work around that. */
4676 && !single_pred_p (next_bb
)))
4679 if (!in_current_region_p (next_bb
))
4682 e
= find_fallthru_edge (bb
->succs
);
4685 gcc_assert (e
->dest
== next_bb
);
4693 /* Returns true when INSN and SUCC are in the same EBB, given that SUCC is a
4694 successor of INSN. */
4696 in_same_ebb_p (insn_t insn
, insn_t succ
)
4698 basic_block ptr
= BLOCK_FOR_INSN (insn
);
4702 if (ptr
== BLOCK_FOR_INSN (succ
))
4705 if (bb_ends_ebb_p (ptr
))
4708 ptr
= bb_next_bb (ptr
);
4715 /* Recomputes the reverse topological order for the function and
4716 saves it in REV_TOP_ORDER_INDEX. REV_TOP_ORDER_INDEX_LEN is also
4717 modified appropriately. */
4719 recompute_rev_top_order (void)
4724 if (!rev_top_order_index
|| rev_top_order_index_len
< last_basic_block
)
4726 rev_top_order_index_len
= last_basic_block
;
4727 rev_top_order_index
= XRESIZEVEC (int, rev_top_order_index
,
4728 rev_top_order_index_len
);
4731 postorder
= XNEWVEC (int, n_basic_blocks
);
4733 n_blocks
= post_order_compute (postorder
, true, false);
4734 gcc_assert (n_basic_blocks
== n_blocks
);
4736 /* Build reverse function: for each basic block with BB->INDEX == K
4737 rev_top_order_index[K] is it's reverse topological sort number. */
4738 for (i
= 0; i
< n_blocks
; i
++)
4740 gcc_assert (postorder
[i
] < rev_top_order_index_len
);
4741 rev_top_order_index
[postorder
[i
]] = i
;
4747 /* Clear all flags from insns in BB that could spoil its rescheduling. */
4749 clear_outdated_rtx_info (basic_block bb
)
4753 FOR_BB_INSNS (bb
, insn
)
4756 SCHED_GROUP_P (insn
) = 0;
4757 INSN_AFTER_STALL_P (insn
) = 0;
4758 INSN_SCHED_TIMES (insn
) = 0;
4759 EXPR_PRIORITY_ADJ (INSN_EXPR (insn
)) = 0;
4761 /* We cannot use the changed caches, as previously we could ignore
4762 the LHS dependence due to enabled renaming and transform
4763 the expression, and currently we'll be unable to do this. */
4764 htab_empty (INSN_TRANSFORMED_INSNS (insn
));
4768 /* Add BB_NOTE to the pool of available basic block notes. */
4770 return_bb_to_pool (basic_block bb
)
4772 rtx note
= bb_note (bb
);
4774 gcc_assert (NOTE_BASIC_BLOCK (note
) == bb
4775 && bb
->aux
== NULL
);
4777 /* It turns out that current cfg infrastructure does not support
4778 reuse of basic blocks. Don't bother for now. */
4779 /*VEC_safe_push (rtx, heap, bb_note_pool, note);*/
4782 /* Get a bb_note from pool or return NULL_RTX if pool is empty. */
4784 get_bb_note_from_pool (void)
4786 if (VEC_empty (rtx
, bb_note_pool
))
4790 rtx note
= VEC_pop (rtx
, bb_note_pool
);
4792 PREV_INSN (note
) = NULL_RTX
;
4793 NEXT_INSN (note
) = NULL_RTX
;
4799 /* Free bb_note_pool. */
4801 free_bb_note_pool (void)
4803 VEC_free (rtx
, heap
, bb_note_pool
);
4806 /* Setup scheduler pool and successor structure. */
4808 alloc_sched_pools (void)
4812 succs_size
= MAX_WS
+ 1;
4813 succs_info_pool
.stack
= XCNEWVEC (struct succs_info
, succs_size
);
4814 succs_info_pool
.size
= succs_size
;
4815 succs_info_pool
.top
= -1;
4816 succs_info_pool
.max_top
= -1;
4818 sched_lists_pool
= create_alloc_pool ("sel-sched-lists",
4819 sizeof (struct _list_node
), 500);
4822 /* Free the pools. */
4824 free_sched_pools (void)
4828 free_alloc_pool (sched_lists_pool
);
4829 gcc_assert (succs_info_pool
.top
== -1);
4830 for (i
= 0; i
< succs_info_pool
.max_top
; i
++)
4832 VEC_free (rtx
, heap
, succs_info_pool
.stack
[i
].succs_ok
);
4833 VEC_free (rtx
, heap
, succs_info_pool
.stack
[i
].succs_other
);
4834 VEC_free (int, heap
, succs_info_pool
.stack
[i
].probs_ok
);
4836 free (succs_info_pool
.stack
);
4840 /* Returns a position in RGN where BB can be inserted retaining
4841 topological order. */
4843 find_place_to_insert_bb (basic_block bb
, int rgn
)
4845 bool has_preds_outside_rgn
= false;
4849 /* Find whether we have preds outside the region. */
4850 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4851 if (!in_current_region_p (e
->src
))
4853 has_preds_outside_rgn
= true;
4857 /* Recompute the top order -- needed when we have > 1 pred
4858 and in case we don't have preds outside. */
4859 if (flag_sel_sched_pipelining_outer_loops
4860 && (has_preds_outside_rgn
|| EDGE_COUNT (bb
->preds
) > 1))
4862 int i
, bbi
= bb
->index
, cur_bbi
;
4864 recompute_rev_top_order ();
4865 for (i
= RGN_NR_BLOCKS (rgn
) - 1; i
>= 0; i
--)
4867 cur_bbi
= BB_TO_BLOCK (i
);
4868 if (rev_top_order_index
[bbi
]
4869 < rev_top_order_index
[cur_bbi
])
4873 /* We skipped the right block, so we increase i. We accomodate
4874 it for increasing by step later, so we decrease i. */
4877 else if (has_preds_outside_rgn
)
4879 /* This is the case when we generate an extra empty block
4880 to serve as region head during pipelining. */
4881 e
= EDGE_SUCC (bb
, 0);
4882 gcc_assert (EDGE_COUNT (bb
->succs
) == 1
4883 && in_current_region_p (EDGE_SUCC (bb
, 0)->dest
)
4884 && (BLOCK_TO_BB (e
->dest
->index
) == 0));
4888 /* We don't have preds outside the region. We should have
4889 the only pred, because the multiple preds case comes from
4890 the pipelining of outer loops, and that is handled above.
4891 Just take the bbi of this single pred. */
4892 if (EDGE_COUNT (bb
->succs
) > 0)
4896 gcc_assert (EDGE_COUNT (bb
->preds
) == 1);
4898 pred_bbi
= EDGE_PRED (bb
, 0)->src
->index
;
4899 return BLOCK_TO_BB (pred_bbi
);
4902 /* BB has no successors. It is safe to put it in the end. */
4903 return current_nr_blocks
- 1;
4906 /* Deletes an empty basic block freeing its data. */
4908 delete_and_free_basic_block (basic_block bb
)
4910 gcc_assert (sel_bb_empty_p (bb
));
4915 bitmap_clear_bit (blocks_to_reschedule
, bb
->index
);
4917 /* Can't assert av_set properties because we use sel_aremove_bb
4918 when removing loop preheader from the region. At the point of
4919 removing the preheader we already have deallocated sel_region_bb_info. */
4920 gcc_assert (BB_LV_SET (bb
) == NULL
4921 && !BB_LV_SET_VALID_P (bb
)
4922 && BB_AV_LEVEL (bb
) == 0
4923 && BB_AV_SET (bb
) == NULL
);
4925 delete_basic_block (bb
);
4928 /* Add BB to the current region and update the region data. */
4930 add_block_to_current_region (basic_block bb
)
4932 int i
, pos
, bbi
= -2, rgn
;
4934 rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
4935 bbi
= find_place_to_insert_bb (bb
, rgn
);
4937 pos
= RGN_BLOCKS (rgn
) + bbi
;
4939 gcc_assert (RGN_HAS_REAL_EBB (rgn
) == 0
4940 && ebb_head
[bbi
] == pos
);
4942 /* Make a place for the new block. */
4945 for (i
= RGN_BLOCKS (rgn
+ 1) - 1; i
>= pos
; i
--)
4946 BLOCK_TO_BB (rgn_bb_table
[i
])++;
4948 memmove (rgn_bb_table
+ pos
+ 1,
4950 (RGN_BLOCKS (nr_regions
) - pos
) * sizeof (*rgn_bb_table
));
4952 /* Initialize data for BB. */
4953 rgn_bb_table
[pos
] = bb
->index
;
4954 BLOCK_TO_BB (bb
->index
) = bbi
;
4955 CONTAINING_RGN (bb
->index
) = rgn
;
4957 RGN_NR_BLOCKS (rgn
)++;
4959 for (i
= rgn
+ 1; i
<= nr_regions
; i
++)
4963 /* Remove BB from the current region and update the region data. */
4965 remove_bb_from_region (basic_block bb
)
4967 int i
, pos
, bbi
= -2, rgn
;
4969 rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
4970 bbi
= BLOCK_TO_BB (bb
->index
);
4971 pos
= RGN_BLOCKS (rgn
) + bbi
;
4973 gcc_assert (RGN_HAS_REAL_EBB (rgn
) == 0
4974 && ebb_head
[bbi
] == pos
);
4976 for (i
= RGN_BLOCKS (rgn
+ 1) - 1; i
>= pos
; i
--)
4977 BLOCK_TO_BB (rgn_bb_table
[i
])--;
4979 memmove (rgn_bb_table
+ pos
,
4980 rgn_bb_table
+ pos
+ 1,
4981 (RGN_BLOCKS (nr_regions
) - pos
) * sizeof (*rgn_bb_table
));
4983 RGN_NR_BLOCKS (rgn
)--;
4984 for (i
= rgn
+ 1; i
<= nr_regions
; i
++)
4988 /* Add BB to the current region and update all data. If BB is NULL, add all
4989 blocks from last_added_blocks vector. */
4991 sel_add_bb (basic_block bb
)
4993 /* Extend luids so that new notes will receive zero luids. */
4994 sched_init_luids (NULL
, NULL
, NULL
, NULL
);
4996 sel_init_bbs (last_added_blocks
, NULL
);
4998 /* When bb is passed explicitly, the vector should contain
4999 the only element that equals to bb; otherwise, the vector
5000 should not be NULL. */
5001 gcc_assert (last_added_blocks
!= NULL
);
5005 gcc_assert (VEC_length (basic_block
, last_added_blocks
) == 1
5006 && VEC_index (basic_block
,
5007 last_added_blocks
, 0) == bb
);
5008 add_block_to_current_region (bb
);
5010 /* We associate creating/deleting data sets with the first insn
5011 appearing / disappearing in the bb. */
5012 if (!sel_bb_empty_p (bb
) && BB_LV_SET (bb
) == NULL
)
5013 create_initial_data_sets (bb
);
5015 VEC_free (basic_block
, heap
, last_added_blocks
);
5018 /* BB is NULL - process LAST_ADDED_BLOCKS instead. */
5021 basic_block temp_bb
= NULL
;
5024 VEC_iterate (basic_block
, last_added_blocks
, i
, bb
); i
++)
5026 add_block_to_current_region (bb
);
5030 /* We need to fetch at least one bb so we know the region
5032 gcc_assert (temp_bb
!= NULL
);
5035 VEC_free (basic_block
, heap
, last_added_blocks
);
5038 rgn_setup_region (CONTAINING_RGN (bb
->index
));
5041 /* Remove BB from the current region and update all data.
5042 If REMOVE_FROM_CFG_PBB is true, also remove the block cfom cfg. */
5044 sel_remove_bb (basic_block bb
, bool remove_from_cfg_p
)
5046 unsigned idx
= bb
->index
;
5048 gcc_assert (bb
!= NULL
&& BB_NOTE_LIST (bb
) == NULL_RTX
);
5050 remove_bb_from_region (bb
);
5051 return_bb_to_pool (bb
);
5052 bitmap_clear_bit (blocks_to_reschedule
, idx
);
5054 if (remove_from_cfg_p
)
5055 delete_and_free_basic_block (bb
);
5057 rgn_setup_region (CONTAINING_RGN (idx
));
5060 /* Concatenate info of EMPTY_BB to info of MERGE_BB. */
5062 move_bb_info (basic_block merge_bb
, basic_block empty_bb
)
5064 gcc_assert (in_current_region_p (merge_bb
));
5066 concat_note_lists (BB_NOTE_LIST (empty_bb
),
5067 &BB_NOTE_LIST (merge_bb
));
5068 BB_NOTE_LIST (empty_bb
) = NULL_RTX
;
5072 /* Remove EMPTY_BB. If REMOVE_FROM_CFG_P is false, remove EMPTY_BB from
5073 region, but keep it in CFG. */
5075 remove_empty_bb (basic_block empty_bb
, bool remove_from_cfg_p
)
5077 /* The block should contain just a note or a label.
5078 We try to check whether it is unused below. */
5079 gcc_assert (BB_HEAD (empty_bb
) == BB_END (empty_bb
)
5080 || LABEL_P (BB_HEAD (empty_bb
)));
5082 /* If basic block has predecessors or successors, redirect them. */
5083 if (remove_from_cfg_p
5084 && (EDGE_COUNT (empty_bb
->preds
) > 0
5085 || EDGE_COUNT (empty_bb
->succs
) > 0))
5090 /* We need to init PRED and SUCC before redirecting edges. */
5091 if (EDGE_COUNT (empty_bb
->preds
) > 0)
5095 gcc_assert (EDGE_COUNT (empty_bb
->preds
) == 1);
5097 e
= EDGE_PRED (empty_bb
, 0);
5098 gcc_assert (e
->src
== empty_bb
->prev_bb
5099 && (e
->flags
& EDGE_FALLTHRU
));
5101 pred
= empty_bb
->prev_bb
;
5106 if (EDGE_COUNT (empty_bb
->succs
) > 0)
5108 /* We do not check fallthruness here as above, because
5109 after removing a jump the edge may actually be not fallthru. */
5110 gcc_assert (EDGE_COUNT (empty_bb
->succs
) == 1);
5111 succ
= EDGE_SUCC (empty_bb
, 0)->dest
;
5116 if (EDGE_COUNT (empty_bb
->preds
) > 0 && succ
!= NULL
)
5118 edge e
= EDGE_PRED (empty_bb
, 0);
5120 if (e
->flags
& EDGE_FALLTHRU
)
5121 redirect_edge_succ_nodup (e
, succ
);
5123 sel_redirect_edge_and_branch (EDGE_PRED (empty_bb
, 0), succ
);
5126 if (EDGE_COUNT (empty_bb
->succs
) > 0 && pred
!= NULL
)
5128 edge e
= EDGE_SUCC (empty_bb
, 0);
5130 if (find_edge (pred
, e
->dest
) == NULL
)
5131 redirect_edge_pred (e
, pred
);
5135 /* Finish removing. */
5136 sel_remove_bb (empty_bb
, remove_from_cfg_p
);
5139 /* An implementation of create_basic_block hook, which additionally updates
5140 per-bb data structures. */
5142 sel_create_basic_block (void *headp
, void *endp
, basic_block after
)
5147 gcc_assert (flag_sel_sched_pipelining_outer_loops
5148 || last_added_blocks
== NULL
);
5150 new_bb_note
= get_bb_note_from_pool ();
5152 if (new_bb_note
== NULL_RTX
)
5153 new_bb
= orig_cfg_hooks
.create_basic_block (headp
, endp
, after
);
5156 new_bb
= create_basic_block_structure ((rtx
) headp
, (rtx
) endp
,
5157 new_bb_note
, after
);
5161 VEC_safe_push (basic_block
, heap
, last_added_blocks
, new_bb
);
5166 /* Implement sched_init_only_bb (). */
5168 sel_init_only_bb (basic_block bb
, basic_block after
)
5170 gcc_assert (after
== NULL
);
5173 rgn_make_new_region_out_of_new_block (bb
);
5176 /* Update the latch when we've splitted or merged it from FROM block to TO.
5177 This should be checked for all outer loops, too. */
5179 change_loops_latches (basic_block from
, basic_block to
)
5181 gcc_assert (from
!= to
);
5183 if (current_loop_nest
)
5187 for (loop
= current_loop_nest
; loop
; loop
= loop_outer (loop
))
5188 if (considered_for_pipelining_p (loop
) && loop
->latch
== from
)
5190 gcc_assert (loop
== current_loop_nest
);
5192 gcc_assert (loop_latch_edge (loop
));
5197 /* Splits BB on two basic blocks, adding it to the region and extending
5198 per-bb data structures. Returns the newly created bb. */
5200 sel_split_block (basic_block bb
, rtx after
)
5205 new_bb
= sched_split_block_1 (bb
, after
);
5206 sel_add_bb (new_bb
);
5208 /* This should be called after sel_add_bb, because this uses
5209 CONTAINING_RGN for the new block, which is not yet initialized.
5210 FIXME: this function may be a no-op now. */
5211 change_loops_latches (bb
, new_bb
);
5213 /* Update ORIG_BB_INDEX for insns moved into the new block. */
5214 FOR_BB_INSNS (new_bb
, insn
)
5216 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn
)) = new_bb
->index
;
5218 if (sel_bb_empty_p (bb
))
5220 gcc_assert (!sel_bb_empty_p (new_bb
));
5222 /* NEW_BB has data sets that need to be updated and BB holds
5223 data sets that should be removed. Exchange these data sets
5224 so that we won't lose BB's valid data sets. */
5225 exchange_data_sets (new_bb
, bb
);
5226 free_data_sets (bb
);
5229 if (!sel_bb_empty_p (new_bb
)
5230 && bitmap_bit_p (blocks_to_reschedule
, bb
->index
))
5231 bitmap_set_bit (blocks_to_reschedule
, new_bb
->index
);
5236 /* If BB ends with a jump insn whose ID is bigger then PREV_MAX_UID, return it.
5237 Otherwise returns NULL. */
5239 check_for_new_jump (basic_block bb
, int prev_max_uid
)
5243 end
= sel_bb_end (bb
);
5244 if (end
&& INSN_UID (end
) >= prev_max_uid
)
5249 /* Look for a new jump either in FROM_BB block or in newly created JUMP_BB block.
5250 New means having UID at least equal to PREV_MAX_UID. */
5252 find_new_jump (basic_block from
, basic_block jump_bb
, int prev_max_uid
)
5256 /* Return immediately if no new insns were emitted. */
5257 if (get_max_uid () == prev_max_uid
)
5260 /* Now check both blocks for new jumps. It will ever be only one. */
5261 if ((jump
= check_for_new_jump (from
, prev_max_uid
)))
5265 && (jump
= check_for_new_jump (jump_bb
, prev_max_uid
)))
5270 /* Splits E and adds the newly created basic block to the current region.
5271 Returns this basic block. */
5273 sel_split_edge (edge e
)
5275 basic_block new_bb
, src
, other_bb
= NULL
;
5280 prev_max_uid
= get_max_uid ();
5281 new_bb
= split_edge (e
);
5283 if (flag_sel_sched_pipelining_outer_loops
5284 && current_loop_nest
)
5289 /* Some of the basic blocks might not have been added to the loop.
5290 Add them here, until this is fixed in force_fallthru. */
5292 VEC_iterate (basic_block
, last_added_blocks
, i
, bb
); i
++)
5293 if (!bb
->loop_father
)
5295 add_bb_to_loop (bb
, e
->dest
->loop_father
);
5297 gcc_assert (!other_bb
&& (new_bb
->index
!= bb
->index
));
5302 /* Add all last_added_blocks to the region. */
5305 jump
= find_new_jump (src
, new_bb
, prev_max_uid
);
5307 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
);
5309 /* Put the correct lv set on this block. */
5310 if (other_bb
&& !sel_bb_empty_p (other_bb
))
5311 compute_live (sel_bb_head (other_bb
));
5316 /* Implement sched_create_empty_bb (). */
5318 sel_create_empty_bb (basic_block after
)
5322 new_bb
= sched_create_empty_bb_1 (after
);
5324 /* We'll explicitly initialize NEW_BB via sel_init_only_bb () a bit
5326 gcc_assert (VEC_length (basic_block
, last_added_blocks
) == 1
5327 && VEC_index (basic_block
, last_added_blocks
, 0) == new_bb
);
5329 VEC_free (basic_block
, heap
, last_added_blocks
);
5333 /* Implement sched_create_recovery_block. ORIG_INSN is where block
5334 will be splitted to insert a check. */
5336 sel_create_recovery_block (insn_t orig_insn
)
5338 basic_block first_bb
, second_bb
, recovery_block
;
5339 basic_block before_recovery
= NULL
;
5342 first_bb
= BLOCK_FOR_INSN (orig_insn
);
5343 if (sel_bb_end_p (orig_insn
))
5345 /* Avoid introducing an empty block while splitting. */
5346 gcc_assert (single_succ_p (first_bb
));
5347 second_bb
= single_succ (first_bb
);
5350 second_bb
= sched_split_block (first_bb
, orig_insn
);
5352 recovery_block
= sched_create_recovery_block (&before_recovery
);
5353 if (before_recovery
)
5354 copy_lv_set_from (before_recovery
, EXIT_BLOCK_PTR
);
5356 gcc_assert (sel_bb_empty_p (recovery_block
));
5357 sched_create_recovery_edges (first_bb
, recovery_block
, second_bb
);
5358 if (current_loops
!= NULL
)
5359 add_bb_to_loop (recovery_block
, first_bb
->loop_father
);
5361 sel_add_bb (recovery_block
);
5363 jump
= BB_END (recovery_block
);
5364 gcc_assert (sel_bb_head (recovery_block
) == jump
);
5365 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
);
5367 return recovery_block
;
5370 /* Merge basic block B into basic block A. */
5372 sel_merge_blocks (basic_block a
, basic_block b
)
5374 gcc_assert (sel_bb_empty_p (b
)
5375 && EDGE_COUNT (b
->preds
) == 1
5376 && EDGE_PRED (b
, 0)->src
== b
->prev_bb
);
5378 move_bb_info (b
->prev_bb
, b
);
5379 remove_empty_bb (b
, false);
5380 merge_blocks (a
, b
);
5381 change_loops_latches (b
, a
);
5384 /* A wrapper for redirect_edge_and_branch_force, which also initializes
5385 data structures for possibly created bb and insns. Returns the newly
5386 added bb or NULL, when a bb was not needed. */
5388 sel_redirect_edge_and_branch_force (edge e
, basic_block to
)
5390 basic_block jump_bb
, src
;
5394 gcc_assert (!sel_bb_empty_p (e
->src
));
5397 prev_max_uid
= get_max_uid ();
5398 jump_bb
= redirect_edge_and_branch_force (e
, to
);
5400 if (jump_bb
!= NULL
)
5401 sel_add_bb (jump_bb
);
5403 /* This function could not be used to spoil the loop structure by now,
5404 thus we don't care to update anything. But check it to be sure. */
5405 if (current_loop_nest
5407 gcc_assert (loop_latch_edge (current_loop_nest
));
5409 jump
= find_new_jump (src
, jump_bb
, prev_max_uid
);
5411 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
);
5414 /* A wrapper for redirect_edge_and_branch. Return TRUE if blocks connected by
5415 redirected edge are in reverse topological order. */
5417 sel_redirect_edge_and_branch (edge e
, basic_block to
)
5424 bool recompute_toporder_p
= false;
5426 latch_edge_p
= (pipelining_p
5427 && current_loop_nest
5428 && e
== loop_latch_edge (current_loop_nest
));
5431 prev_max_uid
= get_max_uid ();
5433 redirected
= redirect_edge_and_branch (e
, to
);
5435 gcc_assert (redirected
&& last_added_blocks
== NULL
);
5437 /* When we've redirected a latch edge, update the header. */
5440 current_loop_nest
->header
= to
;
5441 gcc_assert (loop_latch_edge (current_loop_nest
));
5444 /* In rare situations, the topological relation between the blocks connected
5445 by the redirected edge can change (see PR42245 for an example). Update
5446 block_to_bb/bb_to_block. */
5447 if (CONTAINING_RGN (e
->src
->index
) == CONTAINING_RGN (to
->index
)
5448 && BLOCK_TO_BB (e
->src
->index
) > BLOCK_TO_BB (to
->index
))
5449 recompute_toporder_p
= true;
5451 jump
= find_new_jump (src
, NULL
, prev_max_uid
);
5453 sel_init_new_insn (jump
, INSN_INIT_TODO_LUID
| INSN_INIT_TODO_SIMPLEJUMP
);
5455 return recompute_toporder_p
;
5458 /* This variable holds the cfg hooks used by the selective scheduler. */
5459 static struct cfg_hooks sel_cfg_hooks
;
5461 /* Register sel-sched cfg hooks. */
5463 sel_register_cfg_hooks (void)
5465 sched_split_block
= sel_split_block
;
5467 orig_cfg_hooks
= get_cfg_hooks ();
5468 sel_cfg_hooks
= orig_cfg_hooks
;
5470 sel_cfg_hooks
.create_basic_block
= sel_create_basic_block
;
5472 set_cfg_hooks (sel_cfg_hooks
);
5474 sched_init_only_bb
= sel_init_only_bb
;
5475 sched_split_block
= sel_split_block
;
5476 sched_create_empty_bb
= sel_create_empty_bb
;
5479 /* Unregister sel-sched cfg hooks. */
5481 sel_unregister_cfg_hooks (void)
5483 sched_create_empty_bb
= NULL
;
5484 sched_split_block
= NULL
;
5485 sched_init_only_bb
= NULL
;
5487 set_cfg_hooks (orig_cfg_hooks
);
5491 /* Emit an insn rtx based on PATTERN. If a jump insn is wanted,
5492 LABEL is where this jump should be directed. */
5494 create_insn_rtx_from_pattern (rtx pattern
, rtx label
)
5498 gcc_assert (!INSN_P (pattern
));
5502 if (label
== NULL_RTX
)
5503 insn_rtx
= emit_insn (pattern
);
5504 else if (DEBUG_INSN_P (label
))
5505 insn_rtx
= emit_debug_insn (pattern
);
5508 insn_rtx
= emit_jump_insn (pattern
);
5509 JUMP_LABEL (insn_rtx
) = label
;
5510 ++LABEL_NUSES (label
);
5515 sched_init_luids (NULL
, NULL
, NULL
, NULL
);
5516 sched_extend_target ();
5517 sched_deps_init (false);
5519 /* Initialize INSN_CODE now. */
5520 recog_memoized (insn_rtx
);
5524 /* Create a new vinsn for INSN_RTX. FORCE_UNIQUE_P is true when the vinsn
5525 must not be clonable. */
5527 create_vinsn_from_insn_rtx (rtx insn_rtx
, bool force_unique_p
)
5529 gcc_assert (INSN_P (insn_rtx
) && !INSN_IN_STREAM_P (insn_rtx
));
5531 /* If VINSN_TYPE is not USE, retain its uniqueness. */
5532 return vinsn_create (insn_rtx
, force_unique_p
);
5535 /* Create a copy of INSN_RTX. */
5537 create_copy_of_insn_rtx (rtx insn_rtx
)
5541 if (DEBUG_INSN_P (insn_rtx
))
5542 return create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx
)),
5545 gcc_assert (NONJUMP_INSN_P (insn_rtx
));
5547 res
= create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx
)),
5552 /* Change vinsn field of EXPR to hold NEW_VINSN. */
5554 change_vinsn_in_expr (expr_t expr
, vinsn_t new_vinsn
)
5556 vinsn_detach (EXPR_VINSN (expr
));
5558 EXPR_VINSN (expr
) = new_vinsn
;
5559 vinsn_attach (new_vinsn
);
5562 /* Helpers for global init. */
5563 /* This structure is used to be able to call existing bundling mechanism
5564 and calculate insn priorities. */
5565 static struct haifa_sched_info sched_sel_haifa_sched_info
=
5567 NULL
, /* init_ready_list */
5568 NULL
, /* can_schedule_ready_p */
5569 NULL
, /* schedule_more_p */
5570 NULL
, /* new_ready */
5571 NULL
, /* rgn_rank */
5572 sel_print_insn
, /* rgn_print_insn */
5573 contributes_to_priority
,
5574 NULL
, /* insn_finishes_block_p */
5580 NULL
, /* add_remove_insn */
5581 NULL
, /* begin_schedule_ready */
5582 NULL
, /* advance_target_bb */
5586 /* Setup special insns used in the scheduler. */
5588 setup_nop_and_exit_insns (void)
5590 gcc_assert (nop_pattern
== NULL_RTX
5591 && exit_insn
== NULL_RTX
);
5593 nop_pattern
= gen_nop ();
5596 emit_insn (nop_pattern
);
5597 exit_insn
= get_insns ();
5599 set_block_for_insn (exit_insn
, EXIT_BLOCK_PTR
);
5602 /* Free special insns used in the scheduler. */
5604 free_nop_and_exit_insns (void)
5606 exit_insn
= NULL_RTX
;
5607 nop_pattern
= NULL_RTX
;
5610 /* Setup a special vinsn used in new insns initialization. */
5612 setup_nop_vinsn (void)
5614 nop_vinsn
= vinsn_create (exit_insn
, false);
5615 vinsn_attach (nop_vinsn
);
5618 /* Free a special vinsn used in new insns initialization. */
5620 free_nop_vinsn (void)
5622 gcc_assert (VINSN_COUNT (nop_vinsn
) == 1);
5623 vinsn_detach (nop_vinsn
);
5627 /* Call a set_sched_flags hook. */
5629 sel_set_sched_flags (void)
5631 /* ??? This means that set_sched_flags were called, and we decided to
5632 support speculation. However, set_sched_flags also modifies flags
5633 on current_sched_info, doing this only at global init. And we
5634 sometimes change c_s_i later. So put the correct flags again. */
5635 if (spec_info
&& targetm
.sched
.set_sched_flags
)
5636 targetm
.sched
.set_sched_flags (spec_info
);
5639 /* Setup pointers to global sched info structures. */
5641 sel_setup_sched_infos (void)
5643 rgn_setup_common_sched_info ();
5645 memcpy (&sel_common_sched_info
, common_sched_info
,
5646 sizeof (sel_common_sched_info
));
5648 sel_common_sched_info
.fix_recovery_cfg
= NULL
;
5649 sel_common_sched_info
.add_block
= NULL
;
5650 sel_common_sched_info
.estimate_number_of_insns
5651 = sel_estimate_number_of_insns
;
5652 sel_common_sched_info
.luid_for_non_insn
= sel_luid_for_non_insn
;
5653 sel_common_sched_info
.sched_pass_id
= SCHED_SEL_PASS
;
5655 common_sched_info
= &sel_common_sched_info
;
5657 current_sched_info
= &sched_sel_haifa_sched_info
;
5658 current_sched_info
->sched_max_insns_priority
=
5659 get_rgn_sched_max_insns_priority ();
5661 sel_set_sched_flags ();
5665 /* Adds basic block BB to region RGN at the position *BB_ORD_INDEX,
5666 *BB_ORD_INDEX after that is increased. */
5668 sel_add_block_to_region (basic_block bb
, int *bb_ord_index
, int rgn
)
5670 RGN_NR_BLOCKS (rgn
) += 1;
5671 RGN_DONT_CALC_DEPS (rgn
) = 0;
5672 RGN_HAS_REAL_EBB (rgn
) = 0;
5673 CONTAINING_RGN (bb
->index
) = rgn
;
5674 BLOCK_TO_BB (bb
->index
) = *bb_ord_index
;
5675 rgn_bb_table
[RGN_BLOCKS (rgn
) + *bb_ord_index
] = bb
->index
;
5678 /* FIXME: it is true only when not scheduling ebbs. */
5679 RGN_BLOCKS (rgn
+ 1) = RGN_BLOCKS (rgn
) + RGN_NR_BLOCKS (rgn
);
5682 /* Functions to support pipelining of outer loops. */
5684 /* Creates a new empty region and returns it's number. */
5686 sel_create_new_region (void)
5688 int new_rgn_number
= nr_regions
;
5690 RGN_NR_BLOCKS (new_rgn_number
) = 0;
5692 /* FIXME: This will work only when EBBs are not created. */
5693 if (new_rgn_number
!= 0)
5694 RGN_BLOCKS (new_rgn_number
) = RGN_BLOCKS (new_rgn_number
- 1) +
5695 RGN_NR_BLOCKS (new_rgn_number
- 1);
5697 RGN_BLOCKS (new_rgn_number
) = 0;
5699 /* Set the blocks of the next region so the other functions may
5700 calculate the number of blocks in the region. */
5701 RGN_BLOCKS (new_rgn_number
+ 1) = RGN_BLOCKS (new_rgn_number
) +
5702 RGN_NR_BLOCKS (new_rgn_number
);
5706 return new_rgn_number
;
5709 /* If X has a smaller topological sort number than Y, returns -1;
5710 if greater, returns 1. */
5712 bb_top_order_comparator (const void *x
, const void *y
)
5714 basic_block bb1
= *(const basic_block
*) x
;
5715 basic_block bb2
= *(const basic_block
*) y
;
5717 gcc_assert (bb1
== bb2
5718 || rev_top_order_index
[bb1
->index
]
5719 != rev_top_order_index
[bb2
->index
]);
5721 /* It's a reverse topological order in REV_TOP_ORDER_INDEX, so
5722 bbs with greater number should go earlier. */
5723 if (rev_top_order_index
[bb1
->index
] > rev_top_order_index
[bb2
->index
])
5729 /* Create a region for LOOP and return its number. If we don't want
5730 to pipeline LOOP, return -1. */
5732 make_region_from_loop (struct loop
*loop
)
5735 int new_rgn_number
= -1;
5738 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5739 int bb_ord_index
= 0;
5740 basic_block
*loop_blocks
;
5741 basic_block preheader_block
;
5744 > (unsigned) PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_BLOCKS
))
5747 /* Don't pipeline loops whose latch belongs to some of its inner loops. */
5748 for (inner
= loop
->inner
; inner
; inner
= inner
->inner
)
5749 if (flow_bb_inside_loop_p (inner
, loop
->latch
))
5752 loop
->ninsns
= num_loop_insns (loop
);
5753 if ((int) loop
->ninsns
> PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_INSNS
))
5756 loop_blocks
= get_loop_body_in_custom_order (loop
, bb_top_order_comparator
);
5758 for (i
= 0; i
< loop
->num_nodes
; i
++)
5759 if (loop_blocks
[i
]->flags
& BB_IRREDUCIBLE_LOOP
)
5765 preheader_block
= loop_preheader_edge (loop
)->src
;
5766 gcc_assert (preheader_block
);
5767 gcc_assert (loop_blocks
[0] == loop
->header
);
5769 new_rgn_number
= sel_create_new_region ();
5771 sel_add_block_to_region (preheader_block
, &bb_ord_index
, new_rgn_number
);
5772 SET_BIT (bbs_in_loop_rgns
, preheader_block
->index
);
5774 for (i
= 0; i
< loop
->num_nodes
; i
++)
5776 /* Add only those blocks that haven't been scheduled in the inner loop.
5777 The exception is the basic blocks with bookkeeping code - they should
5778 be added to the region (and they actually don't belong to the loop
5779 body, but to the region containing that loop body). */
5781 gcc_assert (new_rgn_number
>= 0);
5783 if (! TEST_BIT (bbs_in_loop_rgns
, loop_blocks
[i
]->index
))
5785 sel_add_block_to_region (loop_blocks
[i
], &bb_ord_index
,
5787 SET_BIT (bbs_in_loop_rgns
, loop_blocks
[i
]->index
);
5792 MARK_LOOP_FOR_PIPELINING (loop
);
5794 return new_rgn_number
;
5797 /* Create a new region from preheader blocks LOOP_BLOCKS. */
5799 make_region_from_loop_preheader (VEC(basic_block
, heap
) **loop_blocks
)
5802 int new_rgn_number
= -1;
5805 /* Basic block index, to be assigned to BLOCK_TO_BB. */
5806 int bb_ord_index
= 0;
5808 new_rgn_number
= sel_create_new_region ();
5810 FOR_EACH_VEC_ELT (basic_block
, *loop_blocks
, i
, bb
)
5812 gcc_assert (new_rgn_number
>= 0);
5814 sel_add_block_to_region (bb
, &bb_ord_index
, new_rgn_number
);
5817 VEC_free (basic_block
, heap
, *loop_blocks
);
5818 gcc_assert (*loop_blocks
== NULL
);
5822 /* Create region(s) from loop nest LOOP, such that inner loops will be
5823 pipelined before outer loops. Returns true when a region for LOOP
5826 make_regions_from_loop_nest (struct loop
*loop
)
5828 struct loop
*cur_loop
;
5831 /* Traverse all inner nodes of the loop. */
5832 for (cur_loop
= loop
->inner
; cur_loop
; cur_loop
= cur_loop
->next
)
5833 if (! TEST_BIT (bbs_in_loop_rgns
, cur_loop
->header
->index
))
5836 /* At this moment all regular inner loops should have been pipelined.
5837 Try to create a region from this loop. */
5838 rgn_number
= make_region_from_loop (loop
);
5843 VEC_safe_push (loop_p
, heap
, loop_nests
, loop
);
5847 /* Initalize data structures needed. */
5849 sel_init_pipelining (void)
5851 /* Collect loop information to be used in outer loops pipelining. */
5852 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
5853 | LOOPS_HAVE_FALLTHRU_PREHEADERS
5854 | LOOPS_HAVE_RECORDED_EXITS
5855 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
);
5856 current_loop_nest
= NULL
;
5858 bbs_in_loop_rgns
= sbitmap_alloc (last_basic_block
);
5859 sbitmap_zero (bbs_in_loop_rgns
);
5861 recompute_rev_top_order ();
5864 /* Returns a struct loop for region RGN. */
5866 get_loop_nest_for_rgn (unsigned int rgn
)
5868 /* Regions created with extend_rgns don't have corresponding loop nests,
5869 because they don't represent loops. */
5870 if (rgn
< VEC_length (loop_p
, loop_nests
))
5871 return VEC_index (loop_p
, loop_nests
, rgn
);
5876 /* True when LOOP was included into pipelining regions. */
5878 considered_for_pipelining_p (struct loop
*loop
)
5880 if (loop_depth (loop
) == 0)
5883 /* Now, the loop could be too large or irreducible. Check whether its
5884 region is in LOOP_NESTS.
5885 We determine the region number of LOOP as the region number of its
5886 latch. We can't use header here, because this header could be
5887 just removed preheader and it will give us the wrong region number.
5888 Latch can't be used because it could be in the inner loop too. */
5889 if (LOOP_MARKED_FOR_PIPELINING_P (loop
))
5891 int rgn
= CONTAINING_RGN (loop
->latch
->index
);
5893 gcc_assert ((unsigned) rgn
< VEC_length (loop_p
, loop_nests
));
5900 /* Makes regions from the rest of the blocks, after loops are chosen
5903 make_regions_from_the_rest (void)
5914 /* Index in rgn_bb_table where to start allocating new regions. */
5915 cur_rgn_blocks
= nr_regions
? RGN_BLOCKS (nr_regions
) : 0;
5917 /* Make regions from all the rest basic blocks - those that don't belong to
5918 any loop or belong to irreducible loops. Prepare the data structures
5921 /* LOOP_HDR[I] == -1 if I-th bb doesn't belong to any loop,
5922 LOOP_HDR[I] == LOOP_HDR[J] iff basic blocks I and J reside within the same
5924 loop_hdr
= XNEWVEC (int, last_basic_block
);
5925 degree
= XCNEWVEC (int, last_basic_block
);
5928 /* For each basic block that belongs to some loop assign the number
5929 of innermost loop it belongs to. */
5930 for (i
= 0; i
< last_basic_block
; i
++)
5935 if (bb
->loop_father
&& !bb
->loop_father
->num
== 0
5936 && !(bb
->flags
& BB_IRREDUCIBLE_LOOP
))
5937 loop_hdr
[bb
->index
] = bb
->loop_father
->num
;
5940 /* For each basic block degree is calculated as the number of incoming
5941 edges, that are going out of bbs that are not yet scheduled.
5942 The basic blocks that are scheduled have degree value of zero. */
5945 degree
[bb
->index
] = 0;
5947 if (!TEST_BIT (bbs_in_loop_rgns
, bb
->index
))
5949 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
5950 if (!TEST_BIT (bbs_in_loop_rgns
, e
->src
->index
))
5951 degree
[bb
->index
]++;
5954 degree
[bb
->index
] = -1;
5957 extend_rgns (degree
, &cur_rgn_blocks
, bbs_in_loop_rgns
, loop_hdr
);
5959 /* Any block that did not end up in a region is placed into a region
5962 if (degree
[bb
->index
] >= 0)
5964 rgn_bb_table
[cur_rgn_blocks
] = bb
->index
;
5965 RGN_NR_BLOCKS (nr_regions
) = 1;
5966 RGN_BLOCKS (nr_regions
) = cur_rgn_blocks
++;
5967 RGN_DONT_CALC_DEPS (nr_regions
) = 0;
5968 RGN_HAS_REAL_EBB (nr_regions
) = 0;
5969 CONTAINING_RGN (bb
->index
) = nr_regions
++;
5970 BLOCK_TO_BB (bb
->index
) = 0;
5977 /* Free data structures used in pipelining of loops. */
5978 void sel_finish_pipelining (void)
5983 /* Release aux fields so we don't free them later by mistake. */
5984 FOR_EACH_LOOP (li
, loop
, 0)
5987 loop_optimizer_finalize ();
5989 VEC_free (loop_p
, heap
, loop_nests
);
5991 free (rev_top_order_index
);
5992 rev_top_order_index
= NULL
;
5995 /* This function replaces the find_rgns when
5996 FLAG_SEL_SCHED_PIPELINING_OUTER_LOOPS is set. */
5998 sel_find_rgns (void)
6000 sel_init_pipelining ();
6008 FOR_EACH_LOOP (li
, loop
, (flag_sel_sched_pipelining_outer_loops
6010 : LI_ONLY_INNERMOST
))
6011 make_regions_from_loop_nest (loop
);
6014 /* Make regions from all the rest basic blocks and schedule them.
6015 These blocks include blocks that don't belong to any loop or belong
6016 to irreducible loops. */
6017 make_regions_from_the_rest ();
6019 /* We don't need bbs_in_loop_rgns anymore. */
6020 sbitmap_free (bbs_in_loop_rgns
);
6021 bbs_in_loop_rgns
= NULL
;
6024 /* Adds the preheader blocks from previous loop to current region taking
6025 it from LOOP_PREHEADER_BLOCKS (current_loop_nest).
6026 This function is only used with -fsel-sched-pipelining-outer-loops. */
6028 sel_add_loop_preheaders (void)
6032 VEC(basic_block
, heap
) *preheader_blocks
6033 = LOOP_PREHEADER_BLOCKS (current_loop_nest
);
6036 VEC_iterate (basic_block
, preheader_blocks
, i
, bb
);
6039 VEC_safe_push (basic_block
, heap
, last_added_blocks
, bb
);
6043 VEC_free (basic_block
, heap
, preheader_blocks
);
6046 /* While pipelining outer loops, returns TRUE if BB is a loop preheader.
6047 Please note that the function should also work when pipelining_p is
6048 false, because it is used when deciding whether we should or should
6049 not reschedule pipelined code. */
6051 sel_is_loop_preheader_p (basic_block bb
)
6053 if (current_loop_nest
)
6057 if (preheader_removed
)
6060 /* Preheader is the first block in the region. */
6061 if (BLOCK_TO_BB (bb
->index
) == 0)
6064 /* We used to find a preheader with the topological information.
6065 Check that the above code is equivalent to what we did before. */
6067 if (in_current_region_p (current_loop_nest
->header
))
6068 gcc_assert (!(BLOCK_TO_BB (bb
->index
)
6069 < BLOCK_TO_BB (current_loop_nest
->header
->index
)));
6071 /* Support the situation when the latch block of outer loop
6072 could be from here. */
6073 for (outer
= loop_outer (current_loop_nest
);
6075 outer
= loop_outer (outer
))
6076 if (considered_for_pipelining_p (outer
) && outer
->latch
== bb
)
6083 /* Checks whether JUMP leads to basic block DEST_BB and no other blocks. */
6085 jump_leads_only_to_bb_p (insn_t jump
, basic_block dest_bb
)
6087 basic_block jump_bb
= BLOCK_FOR_INSN (jump
);
6089 /* It is not jump, jump with side-effects or jump can lead to several
6091 if (!onlyjump_p (jump
)
6092 || !any_uncondjump_p (jump
))
6095 /* Several outgoing edges, abnormal edge or destination of jump is
6097 if (EDGE_COUNT (jump_bb
->succs
) != 1
6098 || EDGE_SUCC (jump_bb
, 0)->flags
& EDGE_ABNORMAL
6099 || EDGE_SUCC (jump_bb
, 0)->dest
!= dest_bb
)
6102 /* If not anything of the upper. */
6106 /* Removes the loop preheader from the current region and saves it in
6107 PREHEADER_BLOCKS of the father loop, so they will be added later to
6108 region that represents an outer loop. */
6110 sel_remove_loop_preheader (void)
6113 int cur_rgn
= CONTAINING_RGN (BB_TO_BLOCK (0));
6115 bool all_empty_p
= true;
6116 VEC(basic_block
, heap
) *preheader_blocks
6117 = LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest
));
6119 gcc_assert (current_loop_nest
);
6120 old_len
= VEC_length (basic_block
, preheader_blocks
);
6122 /* Add blocks that aren't within the current loop to PREHEADER_BLOCKS. */
6123 for (i
= 0; i
< RGN_NR_BLOCKS (cur_rgn
); i
++)
6125 bb
= BASIC_BLOCK (BB_TO_BLOCK (i
));
6127 /* If the basic block belongs to region, but doesn't belong to
6128 corresponding loop, then it should be a preheader. */
6129 if (sel_is_loop_preheader_p (bb
))
6131 VEC_safe_push (basic_block
, heap
, preheader_blocks
, bb
);
6132 if (BB_END (bb
) != bb_note (bb
))
6133 all_empty_p
= false;
6137 /* Remove these blocks only after iterating over the whole region. */
6138 for (i
= VEC_length (basic_block
, preheader_blocks
) - 1;
6142 bb
= VEC_index (basic_block
, preheader_blocks
, i
);
6143 sel_remove_bb (bb
, false);
6146 if (!considered_for_pipelining_p (loop_outer (current_loop_nest
)))
6149 /* Immediately create new region from preheader. */
6150 make_region_from_loop_preheader (&preheader_blocks
);
6153 /* If all preheader blocks are empty - dont create new empty region.
6154 Instead, remove them completely. */
6155 FOR_EACH_VEC_ELT (basic_block
, preheader_blocks
, i
, bb
)
6159 basic_block prev_bb
= bb
->prev_bb
, next_bb
= bb
->next_bb
;
6161 /* Redirect all incoming edges to next basic block. */
6162 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
6164 if (! (e
->flags
& EDGE_FALLTHRU
))
6165 redirect_edge_and_branch (e
, bb
->next_bb
);
6167 redirect_edge_succ (e
, bb
->next_bb
);
6169 gcc_assert (BB_NOTE_LIST (bb
) == NULL
);
6170 delete_and_free_basic_block (bb
);
6172 /* Check if after deleting preheader there is a nonconditional
6173 jump in PREV_BB that leads to the next basic block NEXT_BB.
6174 If it is so - delete this jump and clear data sets of its
6175 basic block if it becomes empty. */
6176 if (next_bb
->prev_bb
== prev_bb
6177 && prev_bb
!= ENTRY_BLOCK_PTR
6178 && jump_leads_only_to_bb_p (BB_END (prev_bb
), next_bb
))
6180 redirect_edge_and_branch (EDGE_SUCC (prev_bb
, 0), next_bb
);
6181 if (BB_END (prev_bb
) == bb_note (prev_bb
))
6182 free_data_sets (prev_bb
);
6186 VEC_free (basic_block
, heap
, preheader_blocks
);
6189 /* Store preheader within the father's loop structure. */
6190 SET_LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest
),